Lecture 6 - More Process Synchronization

"You know better than to trust a strange computer!"
- C3PO, The Empire Strikes Back


Agenda

Announcements

  • The second half of Project 1 is due Wednesday night/Thursday morning. Remember, that's one-third of the project grade!
  • Textbooks: if you want to buy one from Water Street, do so this week. Any leftovers will be sent back on Friday.
  • Lab: TCL312b is now available with 4 extra FreeBSD systems. You can work there as well as in the regular lab.
  • Producer-Consumer Problem

    Last time we started to look at the producer-consumer problem. Here, we consider the bounded buffer case.

    Bounded Buffer, buffer size n

    For simplicity, we will assume the objects being produced and consumed are int values.

    This solution leaves one buffer entry empty at all times:

    Is there any danger with this solution in terms of concurrency? Remember that these processes can be interleaved in any order - the system could preempt the producer at any time and run the consumer.. Things to be careful about are shared references to variables.

    Note that only one of the processes can modify the variables in and out. Both use the values, but only the producer modifies in and only the consumer modifies out. Try to come up with a situation that causes incorrect behavior - hopefully you cannot.

    Perhaps we want to use the entire buffer...let's add a variable to keep track of how many items are in the buffer, so we can tell the difference between an empty and a full buffer:

    We can now use the entire buffer. However, there is a potential danger here. We modify counter in both the producer and the consumer.

    Everything looks fine, but let's think about how a computer actually executes those statements to increment or decrement counter.

    counter++ really requires three machine instructions: (i) load a register with the value of counter's memory location, (ii) increment the register, and (iii) store the register value back in counter's memory location. There's no reason that the operating system can't switch the process out in the middle of this.

    Consider the two statements that modify counter:
    Producer Consumer
    P1 R0 = counter; C1 R1 = counter;
    P2 R0 = R0 + 1; C2 R1 = R1 - 1;
    P3 counter = R0; C3 counter = R1;

    Consider one possible ordering: P1 P2 C1 P3 C2 C3 , where counter=17 before starting. Uh oh.

    What we have here is a race condition. We need to make sure that when one process starts modifying counter, that it finishes before the other can try to modify it. This requires synchronization of the processes.

    If there were mutliple producers or consumers, we would have the same issue with the modification of in and out.

    We need to make those statements that increment and decrement counter atomic. We say that the modification of counter is a critical section.

    Critical Sections

    The Critical-Section problem:

  • n processes, all competing to use some shared data
  • each process has a code segment (the critical section) in which shared data is accessed
      while (1) {
         <CS Entry>
         critical section
         <CS Exit>
         non-critical section
      }
    
  • Need to ensure that when one process is executing in its critical section, no other process is allowed to do so
  • Any solution to the critical section problem must satisfy three conditions:

    1. Mutual exclusion: If process Pi is executing in its critical section, then no other processes can be executing in their critical sections. "One at a time."
    2. Progress: If no process is executing in its critical section and there exist some processes that wish to enter their critical section, then the selection of the processes that will enter the critical section next cannot be postponed indefinitely. "no unnecessary waiting."
    3. Bounded waiting: A bound must exist on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted. "no starvation." (We must assume that each process executes at non-zero speed, but make no assumptions about relative speeds of processes)

    We first attempt to solve this for two processes, P0 and P1. They share some variables to synchronize. We fill in <CS Entry> and <CS Exit> from above with code that should satisfy the three conditions.

    Critical Section Algorithm 1

    Note the semicolon at the end of the while statement's condition at the line labeled "busy wait" above. This means that Pi just keeps comparing turn to i over and over until it succeeds. This is sometimes called a spin lock. For now, this is our only method of making one process wait for something to happen. More on this later.

    This does satisfy mutual exclusion, but not progress (alternation is forced).

    Critical Section Algorithm 2

    We'll avoid this alternation problem by having a process wait only when the other has "indicated interest" in the critical section.

    flag[i] set to true means that Pi is requsting access to the critical section.

    This one also satisties mutual exclusion, but not progress.

    If we swap the order of the flag[i]=true; and while (flag[j]); statements, we no longer satisfy mutual exclusion.

    Critical Section Algorithm 3

    We combine the two previous approaches:

    So, we first indicate interest. Then we set turn=j;, effectively saying "no, you first" to the other process. Even if both processes are interested and both get to the while loop at the "same" time, only one can proceed. Whoever set turn first gets to go first.

    This one satisfies all three of our conditions. This is known as Peterson's Algorithm.

    Bakery algorithm

    Can we generalize this for n processes? The Bakery Algorithm (think deli/bakery "now serving customer X" systems) does this.

    The idea is that each process, when it wants to enter the critical section, takes a number. Whoever has the smallest number gets to go in. This is more complex than the bakery ticket-spitters because two processes may grab the same number (to guarantee that they wouldn't would require mutual exclusion - exactly the thing we're trying to implement), and because there is no attendant to call out the next number - the processes all must come to agreement on who should proceed next into the critical section.

    We break ties by allowing the process with the lower process identifier (PID) to proceed. For Pi, we call it i. This assumes PIDs from 0 to n-1 for n processes, but this can be generalized.

    Although two processes that try to pick a number at about the same time may get the same number, we do guarantee that once a process with number k is in, all processes choosing numbers will get a number > k.

    Notation used below: an ordered pair (number, pid) fully identifies a process' number. We define a lexicographic order of these:

  • (a,b) < (c,d) is a < c or if a = c and b < d
  • The algorithm:

    So great, we have a solution. But...problems:

    1. That's a lot of code. Lots of while loops and for loops. Could be expensive if we're going to do this a lot.
    2. If this is a highly popular critical section, the numbers might never reset, and we could overflow our integers. Unlikely, but think what could happen if we did.
    3. It's kind of inconvenient and in some circumstances, unreasonable, to have these arrays of n values. There may not always be n processes, as some may come and go.