/ 0
Related Content: CS604 - VU Lectures, Handouts, PPT Slides, Assignments, Quizzes, Papers & Books of Operating Systems
Summary
- Dining philosophers problem
- High-level synchronization constructs
- Critical region
- Monitor
Dining Philosophers Problem
Several possibilities that remedy the deadlock situation discussed in the last lecture are listed. Each results in a good solution for the problem.
- Allow at most four philosophers to be sitting simultaneously at the table.
- Allow a philosopher to pick up her chopsticks only if both chopsticks are available (to do this she must pick them up in a critical section)
- Use an asymmetric solution; that is, an odd philosopher picks up first her left chopstick, whereas an even philosopher picks up her right chopstick and then her left chopstick.
Removing the possibility of deadlock does not ensure that starvation does not occur.
Imagine that two philosophers are fast thinkers and fast eaters. They think fast and get
hungry fast. Then, they sit down in opposite chairs as shown below. Because they are so
fast, it is possible that they can lock their chopsticks and eat. After finish eating and
before their neighbors can lock the chopsticks and eat, they come back again and lock the
chopsticks and eat. In this case, the other three philosophers, even though they have been
sitting for a long time, they have no chance to eat. This is a starvation. Note that it is not a
deadlock because there is no circular waiting, and everyone has a chance to eat!
High-level Synchronization Constructs
We discussed the problems of deadlock, starvation, and violation of mutual exclusion caused by the poor use of semaphores in lecture 23. We now discuss some high-level synchronization constructs that help solve some of these problems.
Critical regions
Although semaphores provide a convenient and effective mechanism for process
synchronization, their incorrect usage can still result in timing errors that are difficult to
detect, since these errors occur only if some particular execution takes place, and these
sequences do not always happen.
To illustrate how, let us review the solution to the critical section problem using
semaphores. 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.
To deal with the type of errors we outlined above and in lecture 23, a number of highlevel
constructs have been introduced. In this section we describe one fundamental highlevel
synchronization construct—the critical region. We assume that a process consists
of some local data, and a sequential program that can operate on the data. Only the
sequential program code that is encapsulated within the same process can access the local
data. That is, one process cannot directly access the local data of another process.
Processes can however share global data.
The critical region high-level synchronization construct requires that a variable v of
type T, which is to be shared among many processes, be declared as:
The variable v can be accessed only inside a region statement of the following form:
This construct means that, while statement S is being executed, no other process can access the variable v. The expression B is a Boolean expression that governs the access to the critical region. When a process tries to enter the critical-section region, the Boolean expression B is evaluated. If the expression is true, statement S is executed. If it is false, the process relinquishes the mutual exclusion and is delayed until B becomes true and no other process is in the region associated with v. Thus if the two statements,
region v when(true) S1;
region v when(true) S2;
are executed concurrently in distinct sequential processes, the result will be equivalent to
the sequential execution “S1 followed by S2” or “S2 followed by S1”.
The critical region construct can be effectively used to solve several certain general
synchronization problems. We now show use of the critical region construct to solve the
bounded buffer problem. Here is the declaration of buffer:
The producer process inserts a new item (stored in nextp) into the shared buffer by executing
The consumer process removes an item from the shared buffer and puts it in nextc by executing
Monitors
Another high-level synchronization construct is the monitor type. A monitor is characterized by local data and a set of programmer-defined operators that can be used to access this data; local data be accessed only through these 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. Normal scoping rules apply to parameters of a function and to its local variables. The syntax of the monitor is as follows:
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 construct explicitly. While one process is active within a monitor, other processes trying
to access a monitor wait outside the monitor. The following diagram shows the big
picture of a monitor.
However, the monitor construct as defined so far is not powerful enough to model some synchronization schemes. For this purpose we need to define additional synchronization mechanisms. These mechanisms are provided by the condition construct (also called condition variable). A programmer who needs to write her own tailor made synchronization scheme can define one or more variables of type condition.
The only operations that can be invoked on a condition variable are wait and signal. The operation
means that the process invoking this operation is suspended until another process invokes.
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 as though the operation were never executed. This is unlike the signal operation on a semaphore, where a signal operation always increments value of the semaphore by one. Monitors with condition variables can solve more synchronization problems that monitors alone. Still only one process can be active within a monitor but many processes may be waiting for a condition variable within a monitor, as shown in the following diagram.
In the next lecture we will discuss a monitor-based solution for the dining philosophers problem.
Google +