Monitors

Monitors

Although semaphores provide a convenient and effective mechanism for process synchronization, using them incorrectly can result in timing errors that are difficult to detect, since these errors happen only if some particular execution sequences take place and these sequences do not always occur. We have seen an example of such errors in the use of counters in our solution to the producer-consumer problem (Section 6.1). In that example, the timing problem happened only rarely, and even then the counter value appeared to be reasonable—off by only 1- Nevertheless, the solution is obviously not an acceptable one. It is for this reason that semaphores were introduced in the first place.

Unfortunately, such timing errors can still occur when semaphores are used. To illustrate how, we review the semaphore solution to the criticalsection problem. All processes share a semaphore variable mutex, which is. initialized to 1. Each process must execute wait (mutex) before entering the critical section and signal (mutex) afterward. If this sequence is not observed, two processes may be in their critical sections simultaneously. Let us examine the various difficulties that may result. Note that these difficulties will arise even if a single process is not well behaved. This situation may be caused by an honest programming error or an uncooperative programmer.

• Suppose that a process interchanges the order in which the wait(j and signal () operations on the semaphore mutex are executed, resulting in the following execution:

signal(mutex);

critical section

wait(mutex);

In this situation, several processes may be executing in their critical sections simultaneously, violating the mutual-exclusion requirement. This error may be discovered only if several processes are simultaneously active in their critical sections. Note that this situation may not always be reproducible.

• Suppose that a process replaces signal (mutex) with wait (mutex). That is, it executes

 wait(mutex);

critical section

 wait(mutex);

In this case, a deadlock will occur.

• Suppose that a process omits the wait (mutex), or the signal (mutex), or both. In this case, either mutual exclusion is violated or a deadlock will occur. These examples illustrate that various types of errors can be generated easily when programmers use semaphores incorrectly to solve the critical-section problem.. To deal with such errors, researchers have developed high-level language constructs. In this section, we describe one fundamental high-level synchronization construct—the monitor type.

Usage

 A type, or abstract data type, encapsulates private data with public methods to operate on that data. A monitor type presents a set of programmer-defined operations that are provided mutual exclusion within the monitor. The monitor type also contains the declaration of variables whose values define the state of an instance of that type, along with the bodies of procedures or functions that operate on those variables. The syntax of a monitor is shown in Figure 6.16. The representation of a monitor type cannot be used directly by the various processes. Thus, a procedure defined within a monitor can access only those variables declared locally within the monitor and its formal parameters. Similarly, the local variables of a monitor can be accessed by only the local procedures.

 The monitor construct ensures that only one process at a time can be active within the monitor. Consequently, the programmer does not need to code this synchronization constraint explicitly (Figure 6.17). However, the monitor construct, as defined so far, is not sufficiently powerful for modeling some synchronization schemes. For this purpose, we need to define additional synchronization mechanisms. These mechanisms are provided by the condition construct. A programmer who needs to write a tailor-made synchronization scheme can define one or more variables of type condition:

 condition x, y;

The only operations that can be invoked on a condition variable are wait () and signal(). The operation x.waitO ; means that the process invoking this operation is suspended until another process invokes x.signal(); The x. signal () operation resumes exactly one suspended process. If no process is suspended, then the signal () operation has no effect; that is, the state of x is the same as if the operation had never been executed (Figure 6.18). Contrast this operation with the signal () operation associated with semaphores, which always affects the state of the semaphore.

Now suppose that, when the x. s ignal () operation is invoked by a process P, there is a suspended process Q associated with condition x. Clearly, if the suspended process Q is allowed to resume its execution, the signaling process P must wait. Otherwise, both P and Q would be active simultaneously within the monitor. Note, however, that both processes can conceptually continue with their execution. Two possibilities exist:

1. Signal and wait. P either waits until Q leaves the monitor or waits for another condition.

2. Signal and continue. Q either waits until P leaves the monitor or waits for another condition. There are reasonable arguments in favor of adopting either option. On the one hand, since P was already executing in the monitor, the signal-and-continue method seems more reasonable. On the other hand, if we allow thread P to continue, then by the time Q is resumed, the logical condition for which Q was waiting may no longer hold. A compromise between these two choices was adopted in the language Concurrent Pascal. When thread P executes the signal operation, it immediately leaves the monitor. Hence, Q is immediately resumed

Dining-Philosophers Solution Using Monitors

We now illustrate monitor concepts by presenting a deadlock-free solution to the dining-philosophers problem. This solution imposes the restriction that a philosopher may pick up her chopsticks only if both of them are available. To code this solution, we need to distinguish among three states in which we may find a philosopher. For this purpose, we introduce the following data structure: enum {thinking, hungry, eating} stat e [5] ; Philosopher i can set the variable stat e [i] = eating only if her two neighbors are not eating: (state [(i+4) °/» 5] != eating) and (state [(i+1) % 5] != eating). We also need to declare condition self [5]; where philosopher ;' can delay herself when she is hungry but is unable to obtain the chopsticks she needs. We are now in a position to describe our solution to the diiiing-philosophers problem. The distribution of the chopsticks is controlled by the monitor dp, whose definition is shown in Figure 6.19. Each philosopher, before starting to eat, must invoke the operation pi ckup (). This may result in the suspension of the philosopher process.

After the successful completion of the operation, the philosopher may eat. Following this, the philosopher invokes the putdownO operation. Thus, philosopher i must invoke the operations pi ckup () and putdownO in the following sequence:

dp.pickup(i);

eat dp.putdown(i);

It is easy to show that this solution ensures that no two neighbors are eating simultaneously and that no deadlocks will occur. We note, however, that it is possible for a philosopher to starve to death. We do not present a solution to this problem but rather leave it as an exercise for you.

Implementing a Monitor Using Semaphores

We now consider a possible implementation of the monitor mechanism using semaphores. For each monitor, a semaphore mut ex (initialized to 1) is provided. A process must execute wait (mutex) before entering the monitor and must execute signal (mutex) after leaving the monitor. Since a signaling process must wait until the resumed process either leaves or waits, an additional semaphore, next, is introduced, initialized to 0, on which the signaling processes may suspend themselves. An integer variable next-count is also provided to count the number of processes suspended on next. Thus, each external procedure F is replaced by

wait(mutex);

body of F if (next_count > 0)

signal(next);

else

signal(mutex);

 Mutual exclusion within a monitor is ensured. We can now describe how condition variables are implemented. For each condition x, we introduce a semaphore x_sem and an integer variable x_count, both initialized to 0. The operation x. wait () can now be implemented as

 x_count++;

 if (next_count > 0)

signal(next);

 else

 signal(mutex);

 wait(x_sem);

 x_count—;

The operation x. signal () can be implemented as if (x_count > 0) { next_count++; signal(x_sem); wait(next) ; next_count—; This implementation is applicable to the definitions of monitors given by both Hoare and Brinch-Hansen. In some cases, however, the generality of the implementation is unnecessary, and a significant improvement in efficiency is possible.

Resuming Processes Within a Monitor We turn now to the subject of process-resumption order within a monitor. If several processes are suspended on condition x, and an x. signal () operation is executed by some process, then how do we determine which of the suspended processes should be resumed next? One simple solution is to use an FCFS ordering, so that the process waiting the longest is resumed first. In many circumstances, however, such a simple scheduling scheme is not adequate. For this purpose, the conditional-wait construct can be used; it has the form

x.wait(c);

where c is an integer expression that is evaluated when the wait () operation is executed. The value of c, which is called a priority number, is then stored with the name of the process that is suspended. When x. signal () is executed, the process with the smallest associated priority number is resumed next. To illustrate this new mechanism, we consider the ResourceAllocator monitor shown in Figure 6.20, which controls the allocation of a single resource among competing processes.

 Each process, when requesting an allocation of this resource, specifies the maximum time it plans to use the resource. The monitor allocates the resource to the process that has the shortest timeallocation request. A process that needs to access the resource in question must observe the following sequence:

 R.acquire(t);

 access the resource;

 R. releaseO ;

where R is an instance of type ResourceAllocator. Unfortunately, the monitor concept cannot guarantee that the preceding access sequence will be observed. In particular, the following problems can occur:

• A process might access a resource without first gaining access permission to the resource.

 • A process might never release a resource once it has been granted access to the resource.

• A process might attempt to release a resource that it never requestecj.

• A process might request the same resource twice (without first releasing the resource). The same difficulties are encountered with the use of semaphores, and these difficulties are similar in nature to those that encouraged us to develop the monitor constructs in the first place.

 Previously, we had to worry about the correct use of semaphores. Now, we have to worry about the correct use of higher-level programmer-defined operations, with which the compiler can no longer assist us. One possible solution to the current problem is to include the resourceaccess operations within the ResourceAllocator monitor. However, using this solution will mean that scheduling is done according to the built-in monitor-scheduling algorithm rather than the one we have coded. To ensure that the processes observe the appropriate sequences, we must inspect all the programs that make use of the ResourceAllocator monitor and its managed resource. We must check two conditions to establish the correctness of this system.

First, user processes must always make their calls on the monitor in a correct sequence. Second, we must be sure that an uncooperative process does not simply ignore the mutual-exclusion gateway provided by the monitor and try to access the shared resource directly, without using the access protocols. Only if these two conditions can be ensured can we guarantee that no time-dependent errors will occur and that the scheduling algorithm will not be defeated. Although this inspection may be possible for a small, static system, it is not reasonable for a large system or a dynamic system. This access-control problem can be solved only by additional mechanisms that will be described in Chapter 14. Many programming languages have incorporated the idea of the monitor as described in this section, including Concurrent Pascal, Mesa, C# (pronounced C-sharp), and Java. Other languages—such as Erlang—provide some type of concurrency support using a similar mechanism.

Frequently Asked Questions