CS 414 Fall 1999: Homework 1 Solutions

1. Bakery algorithm with a crash, assuming crash means “stop executing”

a) Could the safety property of the solution be violated?

As stated, no. Unless the critical section “leave” code is executed, no other process can get in, so safety cannot be violated.

A few people asked about the following case: suppose that the operating system notices that the process has crashed, and the critical section leave code is automatically executed in this case (NT does something like this under some conditions). This isn’t really what the problem asked, but if the O/S were to work this way, safety could be violated, because we would now have a first process that was in the critical section and a second process that entered before the first one left under normal conditions. For example, if the first process died of a null pointer violation while updating a linked list, the list might also be left in an inconsistent state.

b) Could the progress part of the liveness property be violated?

Yes.  The crashed process is no longer executing in its critical section, but when other processes wish to enter their critical sections, they will be unable to do so, as explained above.

c) Could the bounded waiting part of liveness be violated?

No.  By definition of bounded waiting, in the textbook, this property can be violated only if a process makes a request to enter its critical section but other processes are granted entry an unbounded number of times.  We showed above that no process will enter its critical section after the crash.  Notice that the definition does not say that the waiting time is bounded.

2. A “fair” solution to the mutual exclusion problem using test-and-set can be found in the book, Figure 6-10.

3. Code for get_handle and release_handle:

var nhandles: Semaphore := k, mutex: Semaphore := 0;

var handles: array(0..k) of handle;

var flags: array(0..k) of Boolean := {false…}

var whichone: array(0..k) of integer;

get_handle(i):

wait(nhandles); // wait until a handle is available

wait(mutex); // obtain mutual exclusion

for j := 0..k // at least one is available

if(flags[j] = false) { // found a free handle

flags[j] = true; // note that it is now in use

whichone[i] := j; // remember which one for later

signal(mutex);

return(handles[j]);

}

release_handle(hndl, i):

wait(mutex);

flags[whichone[i]] := false; // the one I was using is free now

signal(nhandles); // signal anyone waiting for it

signal(mutex);