CS4411 Reading List: Week 3

Textbook Material
Read the following materials
  • Chapter 4
  • Section 6.1 to Section 6.4
  • Slides for Chapter 6 are available in the common directory: chap06-1.pdf to chap06-4.pdf.
    • We will discuss Chapter 5 later.

Do the following problems
From our text
  • Problem 4.2, 4.3, 4.4, 4.8, 4.10, 4.11 (p. 174)
  • Problem 6.1, 6.2, 6.8, 6.9, 6.13, 6.14 (p. 267)
Food for Thought
  • The following solution to the mutual exclusion problem for two processes is due to H. Hyman in 1966: 
    bool  flag[2];   // global flags
int   turn;      // global turn variable

Process i (i = 0 or 1)
----------------------
flag[i] = TRUE;          // I am interested
while (turn != i) {      // while it is not my turn
     while (flag[j])     //   while you are interested
          ;              //     do nothing: busy waiting
     turn = i;           //   because your are interested, it is my turn
}
// critical section
flag[i] = FALSE          // I am done and not interested
    Unfortunately, this is an incorrect solution. Find the problem.
  • Consider the following solution to the mutual exclusion problem for two processes P0 and P1, where flag[2] is a Boolean array of two elements and turn is an integer variable. Both are global to P0 and P1. Show that mutual exclusion is implemented correctly. 
    Process P0                      Process P1

while (true) do                  while (true) do
   ......                           ......
   flag[0] := true;                 flag[1] := true;
   while flag[1] do                 while flag[0] do
      if turn = 1 then                 if turn = 0 then
         flag[0] := false;                flag[1] := false;
         while turn = 1 do                while turn = 0 do
            ;                                ;
         flag[0] := true;                 flag[1] := true;
      end if                           end if
   end while                        end while

   // Critical Section           // Critical Section

   turn := 1;                       turn := 0;
   flag[0] := false;                flag[1] := false;
   ......                           ......
end while;                       end while;

You do not have to turn in your paper. What I really expect you to do is using these problems to gauge your understanding of the subject. So, do the problems after finish reading the above sections.