CSE 451

Operating Systems

Spring 1998

Quiz #4 : Solution 

The code given doesnot guarantee mutual exclusion. The following sequence of events can occur, resulting in both the threads entering the critical section.
  1. In the begining both flag[0] and flag[1] are FALSE
  2. Thread 0 reads flag[1] and sees it is FALSE
  3. Context switch to thread 1
  4. Thread 1 reads flag[0] and sees it is FALSE
  5. Thread 1 sets flag[1] and enters critical section
  6. Context switch to thread 0
  7. Thread 0 sets flag[0] and enters critical section
If the two lines in Enter_Critical_Section() are interchanged, then a deadlock can occur.
  1. In the begining both flag[0] and flag[1] are FALSE
  2. Thread 0 sets flag[0] to TRUE
  3. Context switch to thread 1
  4. Thread 1 sets flag[1] to TRUE
  5. Thread 1 checks flag[0], sees it is TRUE and waits in the while loop
  6. Context switch to thread 0
  7. Thread 0 checks flag[1], sees it is TRUE and waits in the while loop
  8. Both the threads are waiting in the while loop and no progress can occur.
Extra Credit:
For the case of two threads, the following code guarantees mutual exclusion and progress. See the text for the proof.

int  flag[2];  /* flag array is initialized to FALSE */
int  turn = 0;

Enter_Critical_Section(int my_thread_id, int other_thread_id)
{
    flag[my_thread_id] = TRUE;
    turn = other_thread_id;
    while (flag[other_thread_id] == TRUE && turn == other_thread_id)
            /* do nothing, spin wait */;
}

Exit_Critical_Section(int my_thread_id, int other_thread_id)
{
     flag[my_thread_id] = FALSE;
}