cmsc 412 s99         Exam 2         name:

Total points 30. Total time 75 mins. 4 problems over 4 pages. No book, no notes, no calculator. 1. [9 pts]  Below are the arrival and service times (in seconds) for a stream of jobs arriving to a queue. Service times are known to the scheduler.

       arrival   service
   J1      0       12
   J2      2        8
   J3      3        4
   J4      7        9
   
 This repeats every 35 seconds [i.e. J5 arrives at 35 with service 12,
                                     J6 arrives at 37 with service 8, etc.]

a.

For FCFS discipline, determine the average response time, the maximum number of jobs in the system at any time, and the average number of jobs in the system.

b.

Repeat part (a) for SJFP (i.e. Shortest Job First Preemptive) discipline.

c.

Repeat part (a) but with the server replaced by a server that is 10% slower; that is, if the old server required 10 s to serve a customer, the new server requires 11 s to serve that customer.

2. [9 pts]  Implement binary semaphores in terms of counting semaphores. Do not use any other synchronization constructs. For constructs other than semaphores, assume only read/write atomicity and weak fairness progress. Your solution must be less than 30 lines and have no busy waiting. Elegance counts.

3. [8 pts]  Consider an operating system that provides user processes with the following message-passing service:

• Send(pid, m): send message m to process pid. Blocks until process pid is at a corresponding receive.
• Receive(pid, m): receive message m from process pid. Blocks until process pid is at a corresponding send.
• If two processes are at corresponding send and receive, then the communication eventually takes place.

The following questions are with regard to processes using the message-passing service. Give brief and precise answers. Irrelevant material will cost you points.

a.

Explain how processes (using the message-passing service) can become deadlocked.

b.

Does it makes sense for the OS to provide a deadlock prevention method. If yes, describe one such method.

c.

Does it makes sense for the OS to provide a deadlock avoidance method. If yes, describe one such method.

d.

Does it makes sense for the OS to provide a deadlock detection/recovery method. If yes, describe one such method.

4. [4 pts]  Consider a computer system where processes can have user-level threads. The cpu scheduler uses two-level round-robin as follows: A ready process is either in level A or level B. A-processes are served in round-robin order. B-processes are served in round-robin order but only when only when there are no A-processes. A A-process that accumulates more than 20 milliseconds of cpu time becomes a B-process. A B-process remains so until it stops being ready (i.e. ready or running).

Suppose the system has a set of processes that access a shared data structure using critical sections That is, the processes share a semaphore mutex initially 1, and every access is preceded by P(mutex) and succeeded by V(mutex).

Is it possible for the cpu scheduling and the processes to interact in a way that severely degrades the performance. Explain briefly?