Nachos - Synchronization

Etching by Dr.Ravi Mukkamala.

Synchronization

Processes sometimes (in fact frequently) need to communicate with other processes. There needs to be a well-structured way for this communication to occur which does not rely on interrupts. There needs to be a well defined way of passing information between processes, coordinating process activity. There are three high level synchronization techniques which provide Synchronization. They are Semaphores, locks and Monitors & condition variables.

Semaphores

Two or more processes can cooperate by means of simple signals, such that a process can be forced to stop at a specified place until it has recieved a specific signal. Any complex coordination requirement can be satisfied by the appropriate structure of signals. For signalling, special variables called semaphores are used. To transmit a signal via semaphore s, a process executes the primitive signal(s). To recieve a signal via semaphore s, a process executes the primitive wait(s). If the corresponding signal has not yet been transmitted, the process is suspended until the transmission takes place.

To achieve the desired effect, we can view teh semaphore as a variable that has an integer value upon which three operations are defined:

A semaphore may be initialised to a nonnegative value.
The wait operation decrements the semaphore value. If the value becomes negative, then the process executing the wait is blocked.
The signal operation increments the semaphore value. If the value is not positive, then a process blocked by a wait operation is unblocked.

Other than these three operations, there is no way to inspect or manipulate semaphores.

The wait and signal primitives are assumed to be atomic; that is, they cannot be interrupted and each routine can be treated as an indivisible step. A queue is used to hold processes waiting on the semaphore usually FIFO.

A Definition of Semaphore primitives


	                   war s: semaphore;
 
                           wait(s):
			     s.count:= s.count - 1;
			     if s.count < 0
			       then begin
			         place this process in s.queue;
				 block this process
			       end;

			   signal(s):
			     s.count:= s.count + 1;
			     if s.count <= 0
			       then begin
			         remove a process P from s.queue;
				 place process P on ready list
			       end;

The testing and modification of the value of the semaphore in both the operations must be done atomically, i.e., when one process is testing or modifying the semaphore value, no other process can modify the value. To see how these operations can be used to synchronize two processes, assume two processes A and B, executing statements S1 and S2 respectively. The condition is that S2 can be executed only after S1.

Implementation in Nachos:

Locks

A lock is used to support mutual exclusion principle. To support the mutual exclusion there are two operations provided which are Acquire() and Require(). When a process wants to enter critical section of a shared variable, it has to Acquire the lock. After the work with the shared variable is over it has to Release the lock. The lock can be in two modes, free or busy. Initially all locks are free. When a process acquires a lock when it is free. When a lock is held by a process then the lock is said to be busy. Any process that attempts to enter its critical section while another process is in its critical section, is made to wait because the lock is busy. The code executed during this stage is as follows:


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

Implementation in Nachos:

Monitors

Another high level sychronisation construct is the monitor type. A monitor is characterized by a set of programmer-defined operators. The representation of a monitor type consists of declarations of variables whose values define the state of an instance of the type, as well as the bodies of procedures or functions that implement operations on the type. The syntax of a monitor is


                      type monitor-name = monitor
		           variable declarations
			   
			   procedure entry P1(..);
			      begin .. end;
			            ..
				    ..
			      begin
			         initialization code
			      end

The representation of a monitor type cannot be used directly by the various processes. The local variables are accessible only by the monitor's procedures and not by any external procedure.
A process enters the monitor by invoking one of its procedures.
Only one process may be executing in the monitor at a time; any other process that has invoked the monitor is suspended, waiting for the monitor to become available.

By enforcing the principle of one process at a time, the monitor is able to provide a mutual exclusion facility. The data variables in the monitor can be accessed by only one process at a time. Thus, a shared data structure can be protected by placing it in a monitor. If the data in a monitor represent some resource, then the monitor provides mutual exclusion facility for accessing the resource. By turning all the critical region procedures into monitor mode, no two procedure will ever execute their critical regions at the same time.

Condition Variables:

A monitor supports synchronization by the use of condition variables that are contained within the monitor and accessible only within the monitor. Two functions operate on condition variables:

cwait(c): Suspend execution of the calling process on condition c. The monitor is now available for use by another process.
csignal(c): Resume execution of some process suspended after a cwait on the same condition. If there are several such processes, choose one of them;if there is no such process, do nothing.

Note that monitor wait/signal operations are different from those for the semaphore. If a process in monitor signals and no task is waiting on the condition variable, the signal is lost.