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.

IS215 - Concurrent Processes Exercises - 1

1. Give two examples of competing processes in an actual system. Do the same for cooperating processes.

2. Write a procedure (different from what was given in this book earlier) use_resource() illustrating the following mutual exclusion problems:

a) starvation
b) mutual exclusion violated
c) deadlock

3. What is a monitor as used for regulating concurrent access to shared resources? Give examples of problems that may be eliminated by the use of a monitor.

4. Describe an approach to process synchronization. Illustrate your answer by outlining an algorithm for a cyclic buffering system; show how your algorithm works by considering the progress of a consumer and a producer processes as they advance through critical regions, get delayed on queues, etc.

5. When, and why, do processes need to synchronize their activities. Describe an approach to process synchronization based upon semaphores. Show how these may be used to solve two typical synchronization problems.

6. Illustrate or argue the correctness of the Dekker's algorithm? Do the same for the Paterson's algorithm and the engineering solution.

7. In order for the engineering solution to execute correctly, the test&set() function must be executed in one CPU cycle. Why is this so? What happens if this is not executed in one CPU cycle?

8. The readers and writers problem models access to a database. Consider a big database with many competing processes wishing to read and write into it. It is acceptable to have multiple processes reading the database at the same time, but if one process is writing, no other process may have access to the database, not even readers. Write a program employing semaphores that ensure correct execution of this.

9. What does the initial value of the semaphore s stands for?

10. Show that counting semaphores can be implemented using binary semaphores.