CS3331 Reading List: Week 5

Course Material
Slides used in class are available in the common directory with filenames 04-Thread.pdf, 05-Sync-Basics.pdf and 06-Sync-Soft-Hardware.pdf
Study Unix Multiprocess Programming
If you wish to print these slides, print them double-sided and print as many slides as possible on the same page. Let us save a tree!

Programming Material
Do Programming Assignment II.

Homework Assignment
Answer the following questions: Answers to these questions can be found in the above mentioned slides.
  • Understand why synchronization is needed? In particular, understand the two examples shown on my slides.
  • Define race conditions.
  • Do your program #1 and program #2 have race conditions?
  • What is a critical section?
  • What is mutual exclusion?
  • Three conditions must be meet in order to design a good solution to the critical section problem. What are these three conditions?
  • What is the difference(s) between progress and bounded waiting?
  • What is the difference(s) between "finite" and "bounded"?
Answer the following questions:
  • Suppose we have the following two processes A and B running concurrently, and x is a variable in shared memory. 
    Process A                         Process B

for (i = 1; i <= 5; i++)          for (i = 1; i <= 5; i++)
     x = x + 1;                        x = x + 1;
    If x is initialized to 0 and x must be loaded into a register before being incremented. What are all possible values for x after both processes have finished the for loop.
    (Answer: The values 2 through 10 inclusive)
  • Consider a banking system with two functions: deposit(amount) and withdraw(amount). These two functions are passed the amount that is to be deposited or withdrawn from a back account. Assume a shared bank account exists between a husband and wife and concurrently the husband calls the withdraw() function and the wife calls deposit(). Describe how a race condition is possible and what might be done to prevent the race condition from occurring.
  • Suppose we have two process P0 and P1 and two shared variables flag[2] and turn as shown below. 
    bool  flag[2];   // global flags
int   turn;      // global turn variable

Process 0                Process 1

flag[0] = TRUE;          flag[1] = TRUE;        // I am interested
while (turn != 0) {      while (turn != 1)  {   // while it is not my turn
     while (flag[1])           while (flag[0])  //   while you are interested
          ;                        ;            //     do nothing: busy waiting
     turn = 0;                 turn = 1;        //   you are not interested, it is my turn
}                        }
                // critical section
flag[0] = FALSE;         flag[1] = FALSE;       // I am done and not interested
    Answer the following questions and elaborate your findings:
    • Are there any race conditions? In particular, will turn = 0 in P0 and turn = 1 in P1 cause a race condition?
      (Answer: No! Why?)
    • Is it possible that process P0 and P1 be in their critical sections at the same time?
      (Answer: Yes, they may be in their critical sections at the same time. Find an execution sequence to demonstrate this possibility.)
Answer the following questions: Answers to these questions can be found in the above mentioned slides.
  • Which conditions do the first attempt violate? Why? Use a step-by-step execution to explain your answer.
  • Which conditions do the second attempt violate? Why? Use a step-by-step execution to explain your answer.
  • Understand the proof which shows Peterson's algorithm does satisfy all three conditions.
Answer the following questions:
  • Consider the following solution to the critical section problem. The shared variable "lock" variable has an initial value 0 (i.e., lock open). 
    Process 0                          Process 1

while (lock != 0)                  while (lock != 0)
     ;                                 ;
lock = 1;                          lock = 1;
               in critical section
lock = 0;                          lock = 0;
    Show step-by-step that this solution does not satisfy the mutual exclusion condition. Does this solution satisfy the progress and bounded waiting conditions?
  • Consider the following solution to the critical section problem. The shared variable "turn" variable has an initial value 0. 
    Process 0                         Process 1

while (turn != 0)                 while (turn != 1)
     ;                                 ;
               in critical section
turn = 1;                         turn = 0;
    Does this solution satisfy the mutual, progress and bounded waiting conditions?
  • Consider the following solution to the critical section problem. The shared variables flag[0] and flag[1] are both initialized to FALSE. 
    Process 0                         Process 1

while (flag[1])                   while (flag[0])
     ;                                 ;
flag[0] = TRUE;                   flag[1] = TRUE;
in critical section               in critical section
flag[0] = FALSE;                  flag[1] = FALSE;
    Show step-by-step that this solution does not satisfy the mutual exclusion condition. Does this solution satisfy the progress and bounded waiting conditions?
  • Consider the following solution to the critical section problem. The shared variables flag[0] and flag[1] are both initialized to FALSE. 
    Process 0                         Process 1

flag[0] = TRUE;                   flag[1] = TRUE;
while (flag[1]) {                 while (flag[0]) {
     flag[0] = FALSE;                  flag[1] = FALSE;
     while (flag[1])                   while (flag[0])
          ;                                 ;
     flag[0] = TRUE;                   flag[1] = TRUE;
}                                 }
in critical section               in critical section
flag[0] = FALSE;                  flag[1] = FALSE;
    Does this solution satisfy the progress and bounded waiting conditions? Does this solution satisfy the mutual exclusion condition?
  • Suppose we have two process P0 and P1 and two shared variables flag[2] and turn as shown below. 
    bool  flag[2];   // global flags, initially FALSE
int   turn;      // global turn variable, initially 0 or 1

Process 0                         Process 1

flag[0] = TRUE;                   flag[1] = TRUE;             // I am interested
while (flag[1]) {                 while (flag[0]) {           // wait as long as you are interested
     if (turn == 1) {                  if (turn == 0) {       //    if it is your turn ...
          flag[0] = FALSE;                  flag[1] = FALSE;  //       I am no more interested
          while (turn != 0)                 while (turn != 1) //       wait for my turn
               ;                                 ;
          flag[0] = TRUE;                   flag[1] = TRUE;   //       let me try again
     }                                  }
}                                 }
in critical section               in critical section
turn = 1;                         turn = 0;                   // it is your turn now
flag[0] = FALSE;                  flag[1] = FALSE;            // I am not interested
    Do the following problems:
    • Show that this solution satisfies the mutual exclusion condition.
      (Hint: Process 0 can enter only if flag[0] is TRUE and flag[1] is FALSE)
    • Show that this solution satisfies the progress condition.
      (Hint: Suppose process 0 is entering. Then, consider the conditions process 1 will see.)
    • Show that this solution satisfies the bounded waiting condition. What is the bound?
      (Hint: Suppose process 0 is entering. Think about three possible cases: (1) process 1 is outside of its critical section, (2) process 1 is in its critical section, and (3) process 1 is also entering. Case (2) eventually becomes case (3). Then, one of process 0 and process 1 will exit. What would happen to the variable turn?)
    This is the Dekker solution (1965) to the critical section problem. Thus, it satisfies all the conditions: mutual exclusion, progress conditions and bounded waiting.
We do not collect your practice work; but, similar problems will appear in quizzes and exams in the future. Note that I will not make any announcement in class for these short quizzes. In other word, short quizzes may take place at any time as long as I see it is appropriate.