CMSC621

Homework 1

Due: by Midnight on Sep 30, 1999

 

1. Consider the readers/writers problem where writers have priority. In other words, as long as a writer wishes to write, the readers must wait.  Implement solutions using semaphores, serializers, and path expressions. (30 points)
2. Consider a takeout pizza place where there are multiple servers. Customers come in and wait. When a server is free s/he takes a customers order, and then goes to bake the pizza. Upon completion, s/he gives the pizza to the customer, who exits the shop. When there are no waiting customers, the server takes a rest. When there are no free servers, a customer must wait. The customer can rest (assume there are enough chairs available) while his order is being processed. Write a solution for the customer and server processes using semaphores. Your solution cannot use any busy waiting. (15 points)
3. In the Schiper-Eggli-Sandoz Protocol to causally order messages, a special data structure VP has to be maintained. This contains tuples of the form (P,t),  where P is a process id and t a timestamp. In class, we saw when to add to the structure. Suppose we now desire to remove tuples from the structure. Argue if it is possible to do this, and if possible, under what conditions. (15 points)
4. Would the Ricart-Agarwala algorithm still work if the messages were not delivered in FIFO order ? Justify your position. (10 points)