CS414 Fall ’00 : Review Questions (Practice Prelim !!!)

1) Consider the following Flight Reservation Algorithm, used to book tickets from and to Ithaca, Miami, Dallas, San Diego and Seattle:

• There is exactly one server used for reservation in each city and it only holds information regarding outgoing flights from that city.
• Each server can process only a single request at a time, and the request has to be of a flight from the city where the server is located. So the server in Ithaca can only take decisions of flights leaving from Ithaca.
• A server will not process another request till it has finished serving the current one.
• A client could request connecting flights, for example lets suppose Mr. A requests a trip from Ithaca to San Diego via Dallas. In this case the server would issue a ticket to Mr. A only if a seat were available on both legs of his trip, i.e. from Ithaca to Dallas, and from Dallas to San Diego. So the server in Ithaca will wait till it gets a reply from the server in Dallas.
• If Mr. B also requests a ticket from Ithaca, he will not be serviced till either Mr. A has been granted or rejected a ticket.

1. There is a synchronization problem at each server:

An incoming request is not served till the server is free and a server should not do any work unless some client process has made a request.

Write down the client and the server process to solve this synchronization problem. Each client

should have a make request section and the server should have a service request section.

2. In the situation described above, a deadlock is possible!!! Describe when it could happen, and show that the 4 necessary conditions for deadlock hold in this situation. (One sentence for each condition is sufficient.) Could deadlock still occur of each city had 5 servers to process requests? Argue in favor or against it!!

3. What strategy could you use to remove this deadlock? Propose briefly any solution based on Deadlock Prevention that was discussed in class. Could the Resource-Allocation Graph Algorithm be used to avoid deadlock if each city had 5 servers? If no, then explain why?

2) An operating system is running 3 concurrent processes, P1, P2 and P3 for 3 different users. Each process requires six units of completion time. Process P1 consists of a single thread. Process P2 consists of 2 threads, each requiring 3 units of time. Process P3 has three threads each requiring 2 units of time. Assume that the threads never block and the processes are always in main memory.

a) If the threads are kernel supported, and if the kernel implements a preemptive, round robin scheduling of threads with a quantum of one time unit. Of the first six time units, how many will be devoted to each of the three processes.

b) Repeat part (a) if the threads are at the user level.

3) In this question we will propose another powerful design of a monitor. Suppose we permitted monitors to communicate, i.e. a process executing in a procedure in a monitor could call a procedure in some other monitor. But still we cannot have more than one process in a monitor since that is one reason why monitors were proposed, so the calling process might have to wait for its turn to get in the other monitor. At the same time it would not relinquish control of its original monitor, since it has not finished execution and is also not waiting on a condition variable. Is this construct of monitors as good and as powerful as Hoare’s monitors? Present a brief argument!!

(5 points)