Introduction to Synchronization

To avoid synchronization problems three software mechanisms are build.

• Semaphores
• Locks
• Monitors

Here follows some explanations for these mechanisms and discussions about how to implement the first one.

Semaphores

A semaphore S is a variable (integer) which can be effected by two operations - P and V (Dutch for wait and signal respectively). The atomic operation P follows:

Operation P:
                      P (S):
                           while S <= 0 do no-op;
                           S = S-1;
Operation V:
                      V (S):
                           S = S + 1;

While one of the operations is modifying the value of the semaphore, no other operations must be allowed to do the same. Therefore the operations must be atomically. Below we will show you how these operations will help to synchronize processes.

Assume two processes A and B with critical sections S1 and S2. Critical sections can not be run at the same time, thus they can manipulate same variable. Semaphore variable S is initialized to 1.

<dir>
  <dir>
    A:
    P(S);
    S1;
    V(S);

    B:
    P(S);
    S2;
    V(S);
  </dir>
</dir>

When process A starts executing, it will decrement the value of S to 0 and will go on to its critical section S1. In the main time if process B wants to enter its own critical section it must wait until process A has signaled (operation V) and incremented the value of S.

There is one disadvantage with this implementation which is called busy waiting. Operation P will test the value until an acceptable value appears, such operations waste CPU time and should be avoided. To solve the problem, processes can be given the right to block themselves, and be placed in a wait queue. Then the CPU scheduler will take control and selects another process to run. When another process executes the V() operation, it will restart a blocked process.

Semaphores are implemented in the threads directory (synch.cc and synch.h). Each semaphore is equipped with a list. So when a process wants to enter a critical section it invokes the P() operation. If the semaphore is available, it grabs it. If not, the process goes to sleep and place itself in the list. The process will wait until it is awaken by the V() operation.

Locks

Locks are another synchronization mechanism. A lock has got two atomic operation (similar to semaphore) to provide mutual exclusion. These two operations are Acquire and Release. A process will acquire a lock before accessing a shared variable, and later it will be released. A process locking a variable will run the following code:

               Lock-Acquire();
                  critical section
               Lock-Release();

The difference between a lock and a semaphore is that a lock is released only by the process that have acquired it earlier. As we discussed above any process can increment the value of the semaphore. To implement locks is part of an assignment, so here are some things you should have in mind:

• To make Acquire() and Release() atomic.
• Build a wait mechanism.
• Making sure that only the process that acquires the lock will release the lock.

Monitors and Condition Variables

When you are using semaphores and locks you must be very careful, because a simple misspelling may lead that the system end up in a deadlock. Monitors are written to make synchronization easier and correctly. Monitors are some procedures, variables, and data structures grouped together in a package. Following is an example monitor:

    monitor synch
       integer i;
       condition c;
       procedure producer(x);
       .
       .
       end;
       procedure consumer(x);
       .
       .
       end;
    end monitor;

There is only one process that can enter a monitor, therefore every monitor has its own waiting list with process waiting to enter the monitor.

Condition Variables

If a process can not enter the monitor it must block itself. This operation is provided by the condition variables. Like locks and semaphores, the condition has got a wait and a signal function. But it also has the broadcast signal. Implementation of condition variables is part of a synch.h; it is your job to implement it. Wait(), Signal() and Broadcast() have the following semantics:

• Wait() releases the lock, gives up the CPU until signaled and then re-acquire the lock.
• Signal() wakes up a thread if there are any waiting on the condition variable.
• Broadcast() wakes up all threads waiting on the condition.

When you implement the condition variable, you must have a queue for the processes waiting on the condition variable.

Continue to Lab 1 Tutorial