Session 8: Synchronization through shared memory

Textbook: Sections 2.2

Techniques

lock variable
turn variable
combining them: Peterson's approach

Techniques

Today we're going to look at the question: Can two processes synchronize without operating system support at all? That is, do we need the operating system to do anything? Or can we just synchronize processes via shared memory?

Lock variables

  void lock() {                  void unlock() {
      while(lock == 1);              lock = 0;
      lock = 1;
  }                              }

This is buggy: You can have competitive synchronization problems with this variable. Say we have two processes A and B, and lock initially holds 0. Say process A completes the first statement of lock(), and then its time slice ends before it can execute the second statement. Then process B picks up. It too can complete the first statement of lock() and then set lock to 1. It is now it its critical section.

Now when A gets its time slice, it continues by setting lock to 1 and entering its critical section. Now both A and B have entered their critical section, violating the mutual exclusion property.

So this approach isn't at all valid. We need to try something else.

Turn variables

The next approach assumes that only two processes are trying to synchronize, and they both know their own process ID (me) and the other's process ID (other).

  void lock() {                  void unlock() {
      while(turn != me);             turn = other;
  }                              }

This has the mutual exclusion property, so it's basically valid. But it's problematic for another reason: Let's say A hits its critical section quite often (it's a very fast process), but B does not. This will force A to wait for B every time it hits its critical section, effectively slowing A to B's pace. This is a large performance hit that isn't really acceptable.

Combining them: Peterson's approach

In 1981, Peterson discovered a clever way of combining these two approaches. Again, we assume there are just two processes trying to synchronize.

void lock() {                               void unlock() {
    interested[me] = true;                      interested[me] = false;
    turn = other;
    while(turn != me && interested[other]);
}                                           }

Does this provide the mutual exclusion property? Let's say A and B have both executed the first instruction of lock(). Whichever assigns turn second will be forced to wait: turn will hold the process ID of the first process to assign turn, and that process will be able to continue past the while loop into the critical section. The second process will not be able to continue until that process finally marks itself as being no longer interested.

Peterson's approach is quite solid, but it suffers from two major shortcomings: First, it busy-waits, wasting CPU time in an idle while loop when there's work to be done in other processes. Second, it only applies to two processes. You might be able to work around the second of these problems, but the first one is pretty much endemic to the solution.