cmsc 412 f98

Exam 1

name:

Total points 30. Total time 75 mins. 3 problems over 3 pages. No book, no notes, no calculator.

Unless otherwise mentioned, assume read-write atomicity and weak fairness scheduling.

Program elegance counts. You lose points for long/inelegant code. 

1. [10 pts]  Threads B, C, and D cooperate to add up the contents of an array x of size 20 as follows. B adds up the even elements, x[0], x[2],  . C adds up the odd elements, x[1], x[3],  . D adds up the results of B and C:

Supply variables and code for the boxes so that

• Each thread terminates after finishing its work; it does not wait for other threads to finish.
• B and C are able to access (different entries of) the array concurrently.
• Counting semaphores are the only synchronization constructs (no access to interrupts, process queues, etc.).
• No busy waiting.
• The code for B, C and D together does not exceed 20 lines.

2. [10 pts]  Processes B and C share a pool of N buffers organized in two queues, a queue  of empty buffers and a queue  of full buffers. B repeatedly gets a buffer from eQ, writes it, and puts it in  . C repeatedly gets a buffer from fQ, reads it, and puts it in  .

Supply the variables and code for the boxes so that

• ``get buffer'' is never executed on an empty queue.
• ``put buffer'' is never executed on a queue with N buffers.
• A queue is never accessed by two processes at the same time.
• A ``get buffer'' attempt on a non-empty queue eventually succeeds.
• A ``put buffer'' attempt on a queue with less than N buffers eventually succeeds.
• Counting semaphores are the only synchronization constructs you can use. No busy waiting.

3. [10 pts]  The following is an attempt to solve the 2-process critical section problem in which process P0 has priority over process P1. The idea here is that if P1 and P0 are both hungry then P1 backs off for a while.

For each claim below, decide whether or not it holds. If it holds give a proof. If it does not, give an execution that falsifies the claim.

a.

Claim: At any time at most one process is in its CS.

b.

Claim: If P0 attempts to enter its CS then eventually it enters the CS.

Sun Oct 18 15:47:00 EDT 1998