IS215 - Concurrent Processes Exercises - 2

11. Write a monitor solution to the readers and writers problem given in (8).

12. Outline a method of handling (detecting and recovering from) lost messages in a message passing system.

13. What issues are true for message passing implemented in distributed systems and that are not issues when message passing is implemented in single processor systems.

14. Trace the execution of the program for reading and writing to a buffer. Try to illustrate all possible executions of this program.

read()
{
while (TRUE) {
read(&item)
/* wait for empty buffer */
RECEIVE(write@uplb,&m);
construct_message(&m,item);
SEND(write@uplb,&m);
}
}

write()
{
while (TRUE) {
RECEIVE(read@upd,&m);
extract_item(&m,&item);
write(item);
SEND(read@upd,&m);
}
}

15. Compare and contrast the merits of semaphores over message passing and vice versa.

16. Show that semaphores, monitors and message passing solutions to the concurrency problem are equivalent.

17. Write a solution to the Dining Philosophers problem that contains

a) starvation problem
b) mutual exclusion violated

18. Write a correct solution to the Dining Philosophers problem that is different from the one given in book.

19. Show the correctness of the following solution to the Dining Philosophers problem:

int fork[5];

philosopher(i)
{
for( ; ; ) {
think;
while does not have both forks {
wait(fork[i]);
if (fork[(i+1) mod 5)] is free
wait(fork[(i+1) mod 5]);
else
signal(fork[i]);
}
eat;
signal(fork[i]);
signal(fork[(i+1) mod 5]);
}
}

20. Two brothers are seated opposite each other on a table with a plate of Palabok and fork. The action of each brother consists of alternate periods of picking food and chewing. The action starts by taking control of the fork, if successful starts to pick the food, then put the fork back on the table and starts to chew. After this, the cycle is repeated. A possible solution to this problem is the following:

jollibee()
{
/* execute in parallel */
brother(1) || brother(2);
}

brother(i)
{
while (TRUE) {
pick_fork();
pick_palabok();
put-Down_fork();
chew();
}
}

a) What are the possible problems that will be encountered by this solution?
b) When do the problems you identified occur? Give one instance for each problem.
c) Improve the solution using semaphores.