Resource Sharing and Management:Mutual Exclusion Revisited and Critical Sections

Mutual Exclusion Revisited: Critical Sections

We have earlier seen that for devices like printers, an OS must provide for mutual exclusion in operation. It is required for memory access as well. Whenever there is a shared area accessed by two or more processes, we have to ensure that only one process has write access at one time. The main motivation is to avoid a race condition amongst processes. When a race occurs between processes (acting independent of each other), each may annul others' operations (as we saw in our spooler example). Transaction- oriented processing is notorious for the race conditions as it may lead to data integrity problems. These problems are best taken care of by ensuring the process has exclusive access to the data area (or the resource) where it has to perform the operation. So each process operates in exclusion of access to the others. Hence, the term mutual exclusion. Next we define a critical section of a program code in this context. By a “critical section” we mean that section of code (in a process) which is executed exclusively, i.e. none of its operations can be annulled. To prevent shared variables from being overwritten by another process, a process must enter its critical section. Operating in critical sections ensures mutual exclusion of processes. Well, how does one ensure such an operation? OSs, including Unix, provides a facility called semaphore to allow processes to make use of critical sections in exclusion to other processes. A semaphore is essentially a variable which is treated in a special way. Access to a semaphore and operations on it are permitted only when it is in a free state. If a process locks a semaphore, others cannot get access to it. However, every process must release the semaphore upon exiting its critical section. In other words, a process may enter a critical section by checking and manipulating a semaphore. When a process has entered its critical section, other processes are prevented from accessing this shared variable. When a process leaves the critical section, it changes the state of semaphore from locked to free. This permits anyone of the waiting processes to now enter their critical sections and use the shared variable. To make sure that the system actually works correctly, a notion of atomicity or indivisibility is invoked, i.e. semaphore operations are run to completion without interruptions as explained in the next section.

Basic Properties of Semaphores

Semaphores have the following properties.

• A semaphore takes only integer values. We, however, would limit to semaphores that take only binary values. In general, we may even have a data-structure in which every entry is a semaphore. Usually, such structures are required for establishing a set of processes that need to communicate. These are also required when a complex data structure like a record is shared.
• There are only two operations possible on a semaphore.

• A wait operation on a semaphore decreases its value by one.

wait(s): while s < 0 do noop; s := s - 1;

• A signal operation increments its value, i.e. signal(s): s : = s + 1;

• A semaphore operation is atomic and indivisible. This essentially ensures both wait and signal operations are carried out without interruption. This may be done using some hardware support and can be explained as follows. Recall in Section 1.2, we noticed that in Figure 1.3, the fetch, execute and decode steps are done indivisibly. The interrupt signal is recognized by the processor only after these steps have been carried out. Essentially, this means it is possible to use disable and enable signals to enforce indivisibility of operations. The wait and signal operations are carried out indivisibly in this sense.

Note that a process is blocked (busy waits) if its wait operation evaluates to a negative semaphore value. Also, a blocked process can be unblocked when some other process executes signal operation to increment semaphore to a zero or positive value. We next show some examples using semaphores.

Usage of Semaphore

Suppose we have two processes P1 and P2 that need mutual exclusion. We shall use a shared semaphore variable use with an initial value = 0. This variable is accessible from both P1 and P2. We may require that both these processes have a program structure that uses repeat – until pair as a perpetual loop. The program shall have the structure as shown

below:

repeat

Some process code here

wait (use);

enter the critical section (the process manipulates a shared area);

signal (use);

the rest of the process code.

until false;

With the repeat{until sequence as defined above, we have an infinite loop for both the processes. On tracing the operations for P1 and P2 we notice that only one of these processes can be in its critical section. The following is a representative operational sequence. Initially, neither process is in critical section and, therefore, use is 0.

• Process P1 arrives at the critical section first and calls wait (use).
• It succeeds and enters the critical section setting use = - 1.
• Process P2 wants to enter its critical section. Calls wait procedure.
• As use < 0. P2 does a busy wait.
• Process P1 executes signal and exits its critical section. use = 0 now.
• Process P2 exits busy wait loop. It enters its critical section use = -1. The above sequence continues.

Yet another good use of a semaphore is in synchronization amongst processes. A process typically may have a synchronizing event. Typically one process generates an event and the other process awaits the occurrence of that event to proceed further. Suppose we have our two processes, Pi and Pj . Pj can execute some statement sj only after a statement si in process Pi has been executed. This synchronization can be achieved with a semaphore se initialized to -1 as follows:

• In Pi execute the sequence si; signal (se);
• In Pj execute wait (se); sj ; Now process Pj must wait completion of si before it can execute sj . With this example, we have demonstrated use of semaphores for inter-process communication. We shall next discuss a few operational scenarios where we can use semaphores gainfully.

Some Additional Points

The primary use of semaphore which we have seen so far was to capture when a certain resource is “in use" or “free". Unix provides a wait instruction to invoke a period of indefinite wait till a certain resource may be in use. Also, when a process grabs a resource, the resource is considered to be “locked".

So far we have seen the use of a two valued or binary semaphore. Technically, one may have a multi-valued semaphore. Such a semaphore may have more than just two values to capture the sense of multiple copies of a type of resource. Also, we can define an array of semaphores i.e. each element of the array is a semaphore. In that case, the array can be used as a combination for several resources or critical operations. This is most useful in databases where we sometimes need to lock records, and even lock fields. This is particularly true of transaction processing systems like bank accounts, air lines ticket booking, and such other systems.

Since, semaphore usually has an integer value which is stored somewhere, it is information the system can use. Therefore, there are processes with permission to access, a time stamp of creation and other system-based attributes. Lastly, we shall give syntax for defining semaphore in Unix environment.

semaphoreId = semget(key_sem, no_sem, flag_sem)

Here semget is a system call, key_sem provides a key to access, no_sem= defines the number of semaphores required in the set. Finally, flag_sem is a standard access control defined by IPC_CREAT | 644 to give a rw-r--r-- access control.

In the next chapter we shall see the use of semaphore, as also, the code for other interprocess communication mechanisms.