CS414 Prelim 1 Solutions

1. Crossword puzzle…

a) Associate a separate mutex semaphore with each square – one semaphore for each letter. Obtain mutual exclusion prior to reading, writing or erasing that letter. Release it immediately after doing so, before obtaining mutex for the next letter.

This approach simply won’t work. If thread A is writing a down-word, perhaps “apple” and it intersects an across-word, thread B might try to write a word that conflicts, like “smith”. Obviously, the two threads want different letters in some square – perhaps A wants a “p” in some square and B wants an “m” there. This non-solution does nothing to prevent chaos – A could write “apple” and yet find “apmle” there, or B could write “smith”and find “spith”.

b) Like (a) in that we have an array of mutex semaphores, one per cell on the puzzle. But this time, obtain mutual exclusion prior to reading, writing or erasing each word, by waiting on the single semaphore associated with the first letter of that word. Release the mutex after reading or writing the whole word. To write “apple”, number 1 down, you wait on the semaphore for the cell containing the “a”, numbered 1-down.

This won’t work either, for exactly the same reason. A and B don’t use the same semaphore even though their words do overlap.

c) Same as (c) but before writing or erasing a word, obtain mutual exclusion for every word your word will overlap. For example, if 9-down crosses 3-across and 6-across, first obtain mutual exclusion using the semaphores associated with all three words. Obtain these in alphabetic order: 3-across, 6-across, 9-down, etc.

This works for writing words (it fixes the problem see above). Here, A and B compete for the same semaphore –the one associated with the square in which their words overlap. If A goes first, then when B gets the semaphore – gets the “lock” – it will see that it can no longer write “smith” because now one of the letters has to be a “p”. Either it will decide to erase “apple” or it will give up on “smith”.

But it doesn’t work for a reader. Lacking a read-lock, a reader may look at the puzzle while a word is being written down. This would be confusing. Instead of “apple” you might see “ap”.

d) Same as (c) but using a reader’s and writers solution, with separate semaphores for each word. If you are reading 9-down and it crosses 3-across, you’ll do a start-read for both words. If you are writing 9-down you’ll do a start-write for both words before writing any letters.

This works for the same reason as the solution in part c. The reader locks have the benefit that one can also read the puzzle without risk of seeing a word in the process of being written down.

e) Does it matter that in (c) and (d) the semaphores are obtained in alphabetical order? Suppose we had said you can do it in a random order. Would that make the solution incorrect? Explain briefly. If the solution would still work, would it be better?

The order matters. In a random order, deadlock can arise. In alphabetic order, we know (from the ordered or “hierarchical” synchronization principles discussed in class) that deadlock is avoided.

2. The Bakery algorithm….

a) Process 2 has not yet left the critical section, yet process 0 doesn’t wait when it executes the while loop “while((number[2],2) < (number[0],0)) loop”

Can’t happen. If process 2 is still in the critical section, number[2] is still equal to 5. Since max(….) must be at least 6, the condition of the while loop will be true and process 0 will wait, looping.

b) Process 2 is able to leave and re-enter the critical section three times before Process 0 is able to enter it even once.

This actually can happen. Although process 0 is “poised” to enter the critical section, until it actually sets choosing[0] to true, no other process knows it is doing so. As a result, other processes won’t wait. A schedule could let process 2 run for quite a while before rescheduling process 0, in which case process 2 could loop around and re-enter the critical section many times.

c) Process 1 enters the critical section three times before process 0 enters it even once.

This is no different than part (b). Process 1 can also sneak in before process 0.

d) When process 0 enters the critical section, it prints number[0]. The value is 1.

This will happen if, by the time process 0 actually does get to execute the critical section entry code, no other process is in the critical section or about to enter. Since all number[i] values will be 0, the max will be 0 and process 0 will pick number 1.

e) Process 0 never enters the critical section, although other processes continue to do so.

We know this can’t happen because of the “eventual progress” (or “finite” progress) assumption. Sooner or later, process 0 gets to execute and once it sets choosing[0] to true, any subsequent process that tries to enter will have to wait until process 0 has done so and exited.

3. File locks….

a) Give a very simple execution example, with as few processes and files as possible, in which a deadlock arises.

There are many answers. A simple one is this: Process A obtains a write lock on file X and requests a write lock on file Y. Meanwhile process B obtains a write lock on file Y and requests a write lock on file X. A is now waiting for an action by B, and B is waiting for an action by A. Deadlock.

b) Suppose that the operating system maintains a process-wait graph, so that if process i holds a lock and process j is trying to obtain that lock, there will be a node for i, a node for j, and an arrow from i to j. Now, suppose that before allowing a process to obtain a requested lock, the operating system adds the associated wait edge to the graph, and runs a reducibility test. It grants the lock request only if the graph is reducible. Otherwise, the lock request fails with the error code “EMIGHTDEADLOCK”. Would this avoid the risk of deadlocks?

Yes, this would avoid deadlocks. A deadlock can only occur if a process actually waits for some action by another process. The change causes the O/S to notice that a deadlock will occur if the request is granted, and since it won’t grant such a request, circular wait cannot arise.

c) Same scenario as part (b). Now suppose that when an application gets the error code EMGHTDEADLOCK it waits for a random amount of time between 0 and 1 second, then requests the lock again, and loops in this manner. Would this result in a correct system? Explain.

This time we may end up with a livelock. Consider the scenario from (a). Once process A has the lock on X and process B has the lock on Y, suppose that A asks for a lock on Y. A is now waiting for B to release this lock – so far so good. Now B asks for a lock on X. It gets an error – EMIGHTDEADLOCK – but simply keeps requesting the same lock anyhow. No progress occurs yet B is doing a lot of work – a livelock.