ABOUT SNS BCA: OPERATING SYSTEM UNIT II

2. INTERPROCESS COMMUNICATION

Processes frequently need to communicate with other processes. For example, in a shell pipeline, the output of the first process must be passed to the second process, and so on down the line.

Thus there is a need for communication between processes, preferably in a well-structured way not using interrupts. In the following sections we will look at some of the issues related to this Interprocess Communication or IPC

Very briefly, there are three issues here. The first was alluded to above: how one process can pass information to another. The second has to do with making sure two or more processes do not get into each other’s way when engaging in critical activities (suppose two processes each try to grab the last 1 MB of memory). The third concerns proper sequencing when dependencies are present: if process A produces data and process B prints them, B has to wait until A has produced

Some data before starting to print. We will examine all three of these issues starting in the next section.

It is also important to mention that two of these issues apply equally well to threads. The first one—passing information—is easy for threads since they share a common address space (threads in different address spaces that need to communicate fall under the heading of communicating processes). However, the other two—keeping out of each other’s hair and proper sequencing—apply equally well to threads. The same problems exist and the same solutions apply. Below we will discuss the problem in the context of processes, but please keep in mind

that the same problems and solutions also apply to threads.

2.1 RACE CONDITIONS

In some operating systems, processes that are working together may share some common storage that each one can read and write. The shared storage may be in main memory (possibly in a kernel data structure) or it may be a shared file: the location of the shared memory does not change the nature of the communication or the problems that arise. To see how inter process communication works in practice, let us consider a simple but common example: a print spooler.

When a process wants to print a file, it enters the file name in a special spooler directory.

Another process, the printer daemon , periodically checks to see if there are any files to be printed, and if there are, it prints them and then removes their names from the directory.

Imagine that our spooler directory has a very large number of slots, numbered 0, 1, 2, …, each one capable of holding a file name. Also imagine that there are two shared variables, out , which points to the next file to be printed, and in , which points to the next free slot in the directory.

These two variables might well be kept on a two-word file available to all processes. At a certain instant, slots 0 to 3 are empty (the files have already been printed) and slots 4 to 6 are full (with the names of files queued for printing). More or less simultaneously, processes A and B decide they want to queue a file for printing.

Two processes want to access shared memory at the same time.

In jurisdictions where Murphy’s Law [†] is applicable, the following might happen. Process A reads in and stores the value, 7, in a local variable called next_free_slot . Just then a clock interrupt occurs and the CPU decides that process A has run long enough, so it switches to process B , Process B also reads in, and also gets a 7. It too stores it in its local variable next_free_slot . At this instant both processes think that the next available slot is 7.

Process B now continues to run. It stores the name of its file in slot 7 and updates in to be an 8.

Then it goes off and does other things.

Eventually, process A runs again, starting from the place it left off. It looks at next_free_slot , finds a 7 there, and writes its file name in slot 7, erasing the name that process B just put there.

Then it computes next_free_slot + 1, which is 8, and sets in to 8. The spooler directory is now internally consistent, so the printer daemon will not notice anything wrong, but process B will never receive any output. User B will hang around the printer room for years, wistfully hoping for output that never comes. Situations like this, where two or more processes are reading or writing some shared data and the final result depends on who runs precisely when, are called race conditions. Debugging programs containing race conditions is no fun at all. The results of

most test runs are fine, but once in a rare while something weird and unexplained happens.

2.2 CRITICAL REGIONS

How do we avoid race conditions? The key to preventing trouble here and in many other situations involving shared memory, shared files, and shared everything else is to find some way to prohibit more than one process from reading and writing the shared data at the same time. Put in other words, what we need is mutual exclusion, that is, some way of making sure that if one process is using a shared variable or file, the other processes will be excluded from doing the same thing. The difficulty above occurred because process B started using one of the shared variables before process A was finished with it. The choice of appropriate primitive operations

for achieving mutual exclusion is a major design issue in any operating system, and a subject that we will examine in great detail in the following sections.

The problem of avoiding race conditions can also be formulated in an abstract way. art of the time, a process is busy doing internal computations and other things that do not lead to race conditions. However, sometimes a process has to access shared memory or files, or doing other critical things that can lead to races. That part of the program where the shared memory is accessed is called the critical region or critical section. If we could arrange matters such that no two processes were ever in their critical regions at the same time, we could avoid aces. Although this requirement avoids race conditions, this is not sufficient for having parallel processes cooperate correctly and efficiently using shared data. We need four conditions to hold to have a good solution:

1. No two processes may be simultaneously inside their critical regions.

2. No assumptions may be made about speeds or the number of CPUs.

3. No process running outside its critical region may block other processes.

4. No process should have to wait forever to enter its critical region.

In an abstract sense, the behavior that we want is shown in Fig. 2-19. Here process A enters its critical region at time T 1 , A little later, at time T 2 process B attempts to enter its critical region but fails because another process is already in its critical region and we allow only one at a time.

Consequently, B is temporarily suspended until time T 3 when A leaves its critical region, allowing B to enter immediately. Eventually B leaves (at T 4 ) and we are back to the original situation with no processes in their critical regions.

Figure 2-19. Mutual exclusion using critical regions.

In this section we will examine various proposals for achieving mutual exclusion, so that while one process is busy updating shared memory in its critical region, no other process will enter its critical region and cause trouble.

Disabling Interrupts

The simplest solution is to have each process disable all interrupts just after entering its critical region and re-enable them just before leaving it. With interrupts disabled, no clock interrupts can occur. The CPU is only switched from process to process as a result of clock or other interrupts, after all, and with interrupts turned off the CPU will not be switched to another process. Thus, once a process has disabled interrupts, it can examine and update the shared memory without fear that any other process will intervene.

This approach is generally unattractive because it is unwise to give user processes the power to turn off interrupts. Suppose that one of them did it and never turned them on again? That could be the end of the system. Furthermore if the system is a multiprocessor, with two or more CPUs, disabling interrupts affects only the CPU that executed the disable instruction. The other ones will continue running and can access the shared memory.

On the other hand, it is frequently convenient for the kernel itself to disable interrupts for a few instructions while it is updating variables or lists. If an interrupt occurred while the list of ready processes, for example, was in an inconsistent state, race conditions could occur. The conclusion is: disabling interrupts is often a useful technique within the operating system itself but is not appropriate as a general mutual exclusion mechanism for user processes.

Lock Variables

As a second attempt, let us look for a software solution. Consider having a single, shared (lock) variable, initially 0. When a process wants to enter its critical region, it first tests the lock. If the lock is 0, the process sets it to 1 and enters the critical region. If the lock is already 1, the process just waits until it becomes 0. Thus, a 0 means that no process is in its critical region, and a 1 means that some process is in its critical region.

Unfortunately, this idea contains exactly the same fatal flaw that we saw in the spooler directory. Suppose that one process reads the lock and sees that it is 0. Before it can set the lock to 1, another process is scheduled, runs, and sets the lock to 1. When the first process runs again, it will also set the lock to 1, and two processes will be in their critical regions at the same time.

Now you might think that we could get around this problem by first reading out the lock value, then checking it again just before storing into it, but that really does not help. The race now occurs if the second process modifies the lock just after the first process has finished its second check.

Strict Alternation

A third approach to the mutual exclusion problem is shown in Fig. 2-20. This program fragment, like nearly all the others in this book, is written in C. C was chosen here because real operating systems are virtually always written in C (or occasionally C++), but hardly ever in languages like Java, Modula 3, or Pascal. C is powerful, efficient, and predictable, characteristics critical for writing operating systems. Java, for example, is not predictable because it might run out of storage at a critical moment and need to invoke the garbage collector at a most inopportune time.

This cannot happen in C because there is no garbage collection in C.

It is to enter the critical region and examine or update the shared memory. Initially, process 0 inspects turn , finds it to be 0, and enters its critical region. Process 1 also finds it to be 0 and therefore sits in a tight loop continually testing turn to see when it becomes 1. Continuously testing a variable until some value appears is called busy waiting . It should usually be avoided, since it wastes CPU time.

Only when there is a reasonable expectation that the wait will be short is busy waiting used. A

lock that uses busy waiting is called a spin lock .

while (TRUE) {

while (turn != 0)/* loop */ ;

critical_region();

turn = 1;

noncritical_region();

}

while (TRUE) {

while (turn != 1);/* loop */ ;

critical_region();

turn = 0;

noncritical_region();

}

(a)

(b)

In both cases, be sure to note the semicolons terminating the while statements.

When process 0 leaves the critical region, it sets turn to 1, to allow process 1 to enter its critical region. Suppose that process 1 finishes its critical region quickly, so both processes are in their noncritical regions, with turn set to 0. Now process 0 executes its whole loop quickly, exiting its critical region and setting turn to 1. At this point turn is 1 and both processes are executing in their noncritical regions.

Suddenly, process 0 finishes its noncritical region and goes back to the top of its loop.

Unfortunately, it is not permitted to enter its critical region now, because turn is 1 and process 1 is busy with its noncritical region. It hangs in its while loop until process 1 sets turn to 0. Put differently, taking turns is not a good idea when one of the processes is much slower than the other.

This situation violates condition 3 set out above: process 0 is being blocked by a process not in its critical region. Going back to the spooler directory discussed above, if we now associate the critical region with reading and writing the spooler directory, process 0 would not be allowed to print another file because process 1 was doing something else.

In fact, this solution requires that the two processes strictly alternate in entering their critical regions, for example, in spooling files. Neither one would be permitted to spool two in a row.

While this algorithm does avoid all races, it is not really a serious candidate as a solution because it violates condition 3.

Peterson’s Solution

By combining the idea of taking turns with the idea of lock variables and warning variables, a Dutch mathematician, T. Dekker, was the first one to devise a software solution to the mutual exclusion problem that does not require strict alternation. For a discussion of Dekkers algorithm, see (Dijkstra, 1965).

In 1981, G.L. Peterson discovered a much simpler way to achieve mutual exclusion, thus rendering Dekker’s solution obsolete. This algorithm consists of two procedures written in ANSI C, which means that function prototypes should be

supplied for all the functions defined and used. However, to save space, we will not show the prototypes in this or subsequent examples.

#define FALSE 0

#define TRUE 1

#define N 2 /* number of processes */

int turn; /* whose turn is it? */

int interested[N]; /* all values initially 0 (FALSE) */

void enter_region(int process) /* process is 0 or 1 */

{

int other; /* number of the other process */

other = 1 - process; /* the opposite of process */

interested[process] = TRUE; /* show that you are interested */

turn = process; /* set flag */

while (turn == process && interested[other] == TRUE) /* null statement */;

}

void leave_region (int process) /* process, who is leaving */

{

interested[process] = FALSE; /* indicate departure from critical region */

}

Before using the shared variables (i.e., before entering its critical region), each process calls enter_region with its own process number, 0 or 1, as parameter. This call will cause it to wait, if need be, until it is safe to enter. After it has finished with the shared variables, the process calls leave_region to indicate that it is done and to allow the other process to enter, if it so desires.

Let us see how this solution works. Initially neither process is in its critical region. Now process 0 calls enter _region. It indicates its interest by setting its array element and sets turn to 0. Since process 1 is not interested, enter_region returns immediately. If process 1 now calls enter_region, it will hang there until interested [0] goes to FALSE , an event that only happens when process 0 calls leave_region to exit the critical region.

Now consider the case that both processes call enter_region almost simultaneously. Both will store their process number in turn. Whichever store is done last is the one that counts; the first one is overwritten and lost. Suppose that process 1 stores last, so turn is 1. When both processes come to the while statement, process 0 executes it zero times and enters its critical region.

Process 1 loops and does not enter its critical region until process 0 exits its critical region.

The TSL Instruction

Now let us look at a proposal that requires a little help from the hardware. Many computers, especially those designed with multiple processors in mind, have an instruction TSL RX,LOCK (Test and Set Lock) that works as follows. It reads the contents of the memory word ock into register RX and then stores a nonzero value at the memory address lock. The operations of reading the word and storing into it are guaranteed to be indivisible—no other processor can access the memory word until the instruction is finished. The CPU executing the TSL instruction locks the memory bus to prohibit other CPUs from accessing memory until it is done.

To use the TSL instruction, we will use a shared variable, lock, to coordinate access to shared memory. When lock is 0, any process may set it to 1 using the TSL instruction and then read or write the shared memory. When it is done, the process sets lock back to 0 using an ordinary move instruction.

or later it will become 0 (when the process currently in its critical region is done with its critical region), and the subroutine returns, with the lock set. Clearing the lock is simple. The program just stores a 0 in lock. No special instructions are needed.

enter_region:

TSL REGISTER, LOCK | copy lock to register and set lock to 1

CMP REGISTER,#0 | was lock zero?

JNE enter_region | if it was non zero, lock was set, so loop

RET | return to caller; critical region entered

leave_region:

MOVE LOCK,#0 | store a 0 in lock

RET | return to caller

One solution to the critical region problem is now straightforward. Before entering its critical region, a process calls enter_region, which does busy waiting until the lock is free; then it acquires the lock and returns. After the critical region the process calls leave_region , which stores a 0 in lock . As with all solutions based on critical regions, the processes must call enter_region and leave_region at the correct times for the method to work. If a process cheats, the mutual exclusion will fail.

2.3 Mutual Exclusion with Busy Waiting

2.3.1Disabling Interrupts

2.3.2Lock Variables

2.3.3Strict Alternation

In Fig. 2-20, the integer variable turn , initially 0, keeps track of whose turn it is to enter the critical region and examine or update the shared memory. Initially, process 0 inspects turn it to be 0, and enters its critical region. Process 1 also finds it to be 0 and therefore sits in a tight loop continually testing turn to see when it becomes 1. Continuously testing a variable until some value appears is called busy waiting . It should usually be avoided, since it wastes CPU time. Only when there is a reasonable expectation that the wait will be short is busy waiting used. A lock that uses busy waiting is called a spin lock .

while (TRUE) {
while (turn != 0)/* loop */ ;
critical_region();
turn = 1;
noncritical_region();
}
while (TRUE) {
while (turn != 1);/* loop */ ;
critical_region();
turn = 0;
noncritical_region();
}

Suddenly, process 0 finishes its noncritical region and goes back to the top of its loop. Unfortunately, it is not permitted to enter its critical region now, because turn is 1 and process 1 is busy with its noncritical region. It hangs in its while loop until process 1 sets turn to 0. Put differently, taking turns is not a good idea when one of the processes is much slower than the other.

In fact, this solution requires that the two processes strictly alternate in entering their critical regions, for example, in spooling files. Neither one would be permitted to spool two in a row. While this algorithm does avoid all races, it is not really a serious candidate as a solution because it violates condition 3.

2.3.4Peterson’s Solution

In 1981, G.L. Peterson discovered a much simpler way to achieve mutual exclusion, thus rendering Dekker’s solution obsolete. Peterson’s algorithm is shown in Fig. 2-21. This algorithm consists of two procedures written in ANSI C, which means that function prototypes should be supplied for all the functions defined and used. However, to save space, we will not show the prototypes in this or subsequent examples.

#define FALSE 0
#define TRUE 1
#define N 2 /* number of processes */

int turn; /* whose turn is it? */int interested[N]; /* all values initially 0 (FALSE) */

void enter_region(int process) /* process is 0 or 1 */

{ int other; /* number of the other process */ other = 1 - process; /* the opposite of process */

interested[process] = TRUE; /* show that you are interested */

turn = process; /* set flag */

while (turn == process && interested[other] == TRUE) /* null statement */;}

void leave_region (int process) /* process, who is leaving */

{ interested[process] = FALSE; /* indicate departure from critical region */}

2.3.5The TSL Instruction

Now let us look at a proposal that requires a little help from the hardware. Many computers, especially those designed with multiple processors in mind, have an instruction

TSL RX,LOCK

(Test and Set Lock) that works as follows. It reads the contents of the memory word lock register RX and then stores a nonzero value at the memory address lock. The operations of reading the word and storing into it are guaranteed to be indivisible—no other processor can access the memory word until the instruction is finished. The CPU executing the TSL instruction locks the memory bus to prohibit other CPUs from accessing memory until it is done.

To use the TSL instruction, we will use a shared variable, lock , to coordinate access to shared memory. When lock is 0, any process may set it to 1 using the TSL instruction and then read or write the shared memory. When it is done, the process sets lock back to 0 using an ordinary move instruction.

How can this instruction be used to prevent two processes from simultaneously entering their critical regions? The solution is given in Fig. 2-22. There a four-instruction subroutine in a fictitious (but typical) assembly language is shown. The first instruction copies the old value of lock to the register and then sets lock to 1. Then the old value is compared with 0. If it is nonzero, the lock was already set, so the program just goes back to the beginning and tests it again. Sooner or later it will become 0 (when the process currently in its critical region is done with its critical region), and the subroutine returns, with the lock set. Clearing the lock is simple. The program just stores a 0 in lock . No special instructions are needed.

enter_region:

TSL REGISTER,LOCK | copy lock to register and set lock to 1

CMP REGISTER,#0 | was lock zero?

JNE enter_region | if it was non zero, lock was set, so loop

RET | return to caller; critical region entered

leave_region:

MOVE LOCK,#0 | store a 0 in lock

RET | return to caller

One solution to the critical region problem is now straightforward. Before entering its critical region, a process calls enter_region, which does busy waiting until the lock is free; then it acquires the lock and returns. After the critical region the process calls leave_region stores a 0 in lock . As with all solutions based on critical regions, the processes must call enter_region and leave_region at the correct times for the method to work. If a process cheats, the mutual exclusion will fail.

2.4 SLEEP AND WAKEUP

`Both Peterson’s solution and the solution using TSL are correct, but both have the defect of requiring busy waiting. In essence, what these solutions do is this: when a process wants to enter its critical region, it checks to see if the entry is allowed. If it is not, the process just sits in a tight loop waiting until it is.

Not only does this approach waste CPU time, but it can also have unexpected effects. Consider a computer with two processes, H , with high priority and L , with low priority. The scheduling rules are such that H is run whenever it is in ready state. At a certain moment, with L in its critical region, H becomes ready to run (e.g., an I/O operation completes). H now begins busy waiting, but since L is never scheduled while H is running, L never gets the chance to leave its critical region, so H loops forever. This situation is sometimes referred to as the priority inversion problem.

Now let us look at some interprocess communication primitives that block instead of wasting CPU time when they are not allowed to enter their critical regions. One of the simplest is the pair sleep and wakeup . Sleep is a system call that causes the caller to block, that is, be suspended until another process wakes it up. The wakeup call has one parameter, the process to be awakened. Alternatively, both sleep and wakeup each have one parameter, a memory address used to match up sleep s with wakeup s.

The Producer-Consumer Problem

As an example of how these primitives can be used, let us consider the producer-consumer problem (also known as the bounded-buffer problem). Two processes share a common, fixed size buffer. One of them, the producer, puts information into the buffer, and the other one, the consumer, takes it out. (It is also possible to generalize the problem to have m producers and n consumers, but we will only consider the case of one producer and one consumer because this assumption simplifies the solutions).

Trouble arises when the producer wants to put a new item in the buffer, but it is already full. The solution is for the producer to go to sleep, to be awakened when the consumer has removed one or more items. Similarly, if the consumer wants to remove an item from the buffer and sees that the buffer is empty, it goes to sleep until the producer puts something in the buffer and wakes it up.

This approach sounds simple enough, but it leads to the same kinds of race conditions we saw earlier with the spooler directory. To keep track of the number of items in the buffer, we will need a variable, count . If the maximum number of items the buffer can hold is N , the producer’s code will first test to see if count is N . If it is, the producer will go to sleep; if it is not, the producer will add an item and increment count .

The consumer’s code is similar: first test count to see if it is 0. If it is, go to sleep, if it is nonzero, remove an item and decrement the counter. Each of the processes also tests to see if the other should be awakened, and if so, wakes it up.

#define N 100 /* number of slots in the buffer */

int count = 0; /* number of items in the buffer */

void producer (void)

{

int item;

while (TRUE) { /* repeat forever */

item = produce_item(); /* generate next item */

if (count == N) sleep(); /* if buffer is full, go to sleep */

insert_item(item); /* put item in buffer */

count = count + 1; /* increment count of items in buffer */

if (count == 1) wakeup(consumer); /* was buffer empty? */

}

void consumer(void)

{

int item;

while (TRUE) { /* repeat forever */

if (count == 0) sleep(); /* if buffer is empty, got to sleep */

item = remove_item(); /* take item out of buffer */

count = count - 1; /* decrement count of items in buffer */

if (count == N - 1) wakeup(producer); /* was buffer full? */

consume_item(item); /* print item */

}

To express system calls such as sleep and wakeup in C, we will show them as calls to library routines. They are not part of the standard C library but presumably would be available on any system that actually had these system calls. The procedures insert_item and remove_item, which are not shown, handle the bookkeeping of putting items into the buffer and taking items out of the buffer.

Now let us get back to the race condition. It can occur because access to count is unconstrained.

The following situation could possibly occur. The buffer is empty and the consumer has just read count to see if it is 0. At that instant, the scheduler decides to stop running the consumer temporarily and start running the producer. The producer inserts an item in the buffer, increments count , and notices that it is now 1. Reasoning that count was just 0, and thus the consumer must be sleeping, the producer calls wakeup to wake the consumer up.

Unfortunately, the consumer is not yet logically asleep, so the wakeup signal is lost. When the consumer next runs, it will test the value of count it previously read, find it to be 0, and go to sleep. Sooner or later the producer will fill up the buffer and also go to sleep. Both will sleep forever.

The essence of the problem here is that a wakeup sent to a process that is not (yet) sleeping is lost. If it were not lost, everything would work. A quick fix is to modify the rules to add a wakeup waiting bit to the picture. When a wakeup is sent to a process that is still awake, this bit is set. Later, when the process tries to go to sleep, if the wakeup waiting bit is on, it will be turned off, but the process will stay awake. The wakeup waiting bit is a piggy bank for wakeup signals.

While the wakeup waiting bit saves the day in this simple example, it is easy to construct examples with three or more processes in which one wakeup waiting bit is insufficient. We could make another patch and add a second wakeup waiting bit, or maybe 8 or 32 of them, but in principle the problem is still there.

2.5 SEMAPHORES

This was the situation in 1965, when E. W. Dijkstra (1965) suggested using an integer variable to count the number of wakeups saved for future use. In his proposal, a new variable type, called a semaphore, was introduced. A semaphore could have the value 0, indicating that no wakeups were saved, or some positive value if one or more wakeups were pending.

Dijkstra proposed having two operations, down and up (generalizations of sleep and wakeup respectively). The down operation on a semaphore checks to see if the value is greater than 0. If so, it decrements the value (i.e., uses up one stored wakeup) and just continues. If the value is 0, the process is put to sleep without completing the down for the moment. Checking the value, changing it and possibly going to sleep, is all done as a single, indivisible atomic action . It is guaranteed that once a semaphore operation has started, no other process can access the semaphore until the operation has completed or blocked. This atomicity is absolutely essential to solving synchronization problems and avoiding race conditions.

The up operation increments the value of the semaphore addressed. If one or more processes were sleeping on that semaphore, unable to complete an earlier down operation, one of them is chosen by the system (e.g., at random) and is allowed to complete its down . Thus, after an up on a semaphore with processes sleeping on it, the semaphore will still be 0, but there will be one fewer process sleeping on it. The operation of incrementing the semaphore and waking up one process is also indivisible. No process ever blocks doing an up , just as no process ever blocks

doing a wakeup in the earlier model.

As an aside, in Dijkstra’s original paper, he used the names P and V instead of down and up respectively, but since these have no mnemonic significance to people who do not speak Dutch (and only marginal significance to those who do), we will use the terms down and up instead.

These were first introduced in Algol 68.

Solving the Producer-Consumer Problem using Semaphores

Semaphores solve the lost-wakeup problem, as shown in Fig. 2-24. It is essential that they be implemented in an indivisible way. The normal way is to implement up and down as system calls, with the operating system briefly disabling all interrupts while it is testing the semaphore, updating it, and putting the process to sleep, if necessary. As all of these actions take only a few instructions, no harm is done in disabling interrupts. If multiple CPUs are being used, each semaphore should be protected by a lock variable, with the TSL instruction used to make sure

that only one CPU at a time examines the semaphore. Be sure you understand that using TSL to prevent several CPUs from accessing the semaphore at the same time is quite different from busy waiting by the producer or consumer waiting for the other to empty or fill the buffer. The semaphore operation will only take a few microseconds, whereas the producer or consumer might take arbitrarily long.

#define N 100 /* number of slots in the buffer */

typedef int semaphore;/* semaphores are a special kind of int */

semaphore mutex = 1;/* controls access to critical region */

semaphore empty = N;/* counts empty buffer slots */

semaphore full = 0;/* counts full buffer slots */

void producer(void)

{

int item;

while (TRUE) { /* TRUE is the constant 1 */

item = produce_item(); /* generate something to put in buffer */

down(&empty); /* decrement empty count */

down(&mutex);/* enter critical region */

insert_item(item); /* put new item in buffer */

up(&mutex); /* leave critical region */

up(&full); /* increment count of full slots */

}

void consumer(void)

{

int item;

while (TRUE) {/* infinite loop */

down(&full);/* decrement full count */

down(&mutex);/* enter critical region */

item a= remove_item();/* take item from buffer */

up(&mutex);/* leave critical region */

up(&empty);/* increment count of empty slots */

consume_item(item);/* do something with the item */

}

This solution uses three semaphores: one called full for counting the number of slots that are full, one called empty for counting the number of slots that are empty, and one called mutex to make sure the producer and consumer do not access the buffer at the same time. Full is initially 0, empty is initially equal to the number of slots in the buffer, and mutex is initially 1. Semaphores that are initialized to 1 and used by two or more processes to ensure that only one of them can enter its critical region at the same time are called binary semaphores . If each process does a down just before entering its critical region and an up just after leaving it, mutual exclusion is guaranteed.

Now that we have a good interprocess communication primitive at our disposal, let us go back and look at the interrupt sequence of Fig. 2-5 again. In a system using semaphores, the natural way to hide interrupts is to have a semaphore, initially set to 0, associated with each I/O device. Just after starting an I/O device, the managing process does a down on the associated semaphore, thus blocking immediately. When the interrupt comes in, the interrupt handler then does an up on

the associated semaphore, which makes the relevant process ready to run again. In this model, step 5 in Fig. 2-5 consists of doing an up on the device’s semaphore, so that in step 6 the scheduler will be able to run the device manager. Of course, if several processes are now ready, the scheduler may choose to run an even more important process next. We will look at some of the algorithms used for scheduling later on in this chapter.

we have actually used semaphores in two different ways. This difference is important enough to make explicit. The mutex semaphore is used for mutual exclusion. It is designed to guarantee that only one process at a time will be reading or writing the buffer and the associated variables. This mutual exclusion is required to prevent chaos. We will study mutual exclusion and how to achieve it more in the next section.

The other use of semaphores is for synchronization . The full and empty semaphores are needed to guarantee that certain event sequences do or do not occur. In this case, they ensure that the producer stops running when the buffer is full, and the consumer stops running when it is empty. This use is different from mutual exclusion.

2.6 MUTEXES

When the semaphore’s ability to count is not needed, a simplified version of the semaphore, called a mutex, is sometimes used. Mutexes are good only for managing mutual exclusion to some shared resource or piece of code. They are easy and efficient to implement, which makes them especially useful in thread packages that are implemented entirely in user space. A mutex is a variable that can be in one of two states: unlocked or locked. Consequently, only 1 bit is required to represent it, but in practice an integer often is used, with 0 meaning unlocked and all other values meaning locked. Two procedures are used with mutexes. When a thread (or

process) needs access to a critical region, it calls mutex_lock . If the mutex is current unlocked (meaning that the critical region is available), the call succeeds and the calling thread is free to enter the critical region.

On the other hand, if the mutex is already locked, the calling thread is blocked until the thread in the critical region is finished and calls mutex_unlock . If multiple threads are blocked on the mutex, one of them is chosen at random and allowed to acquire the lock.

Because mutexes are so simple, they can easily be implemented in user space if a T SL instruction is available. The code for mutex_lock and mutex_unlock for use with a user-level threads package

mutex_lock:

TSL REGISTER,MUTEX | copy mutex to register and set mutex to 1

CMP REGISTERS,#0| was mutex zero?

JZE ok| if it was zero, mutex was unlocked, so return

CALL thread_yield| mutex is busy; schedule another thread

JMP mutex_lock| try again later

ok: RET | return to caller; critical region entered

mutex_unlock:

MOVE MUTEX,#0 | store a 0 in mutex

RET | return to caller

The code of mutex_lock is similar to the code of enter_region of Fig. 2-22 but with a crucial difference. When enter_region fails to enter the critical region, it keeps testing the lock repeatedly (busy waiting). Eventually, the clock runs out and some other process is scheduled to run. Sooner or later the process holding the lock gets to run and releases it.

With threads, the situation is different because there is no clock that stops threads that have run too long. Consequently, a thread that tries to acquire a lock by busy waiting will loop forever and never acquire the lock because it never allows any other thread to run and release the lock.

That is where the difference between enter_region and mutex_lock comes in. When the later fails to acquire a lock, it calls thread_yield to give up the CPU to another thread. Consequently there is no busy waiting. When the thread runs the next time, it tests the lock again.

Since thread_yield is just a call to the thread scheduler in user space, it is very fast. As a consequence, neither mutex_lock nor mutex_unlock requires any kernel calls. Using them, userlevel threads can synchronize entirely in user space using procedures that require only a handful of instructions.

The mutex system that we have described above is a bare bones set of calls. With all software, there is always a demand for more features, and synchronization primitives are no exception. For example, sometimes a thread package offers a call mutex_trylock that either acquires the lock or returns a code for failure, but does not block. This call gives the thread the flexibility to decide what to do next if there are alternatives to just waiting.

Up until now there is an issue that we have glossed over lightly but which is worth at least making explicit. With a user-space threads package there is no problem with multiple threads having access to the same mutex since all the threads operate in a common address space.

However, with most of the earlier solutions, such as Peterson’s algorithm and semaphores, there is an unspoken assumption that multiple processes have access to at least some shared memory, perhaps only one word, but something. If processes have disjoint address spaces, as we have consistently said, how can they share the turn variable in Peterson’s algorithm, or semaphores or a common buffer?

There are two answers. First, some of the shared data structures, such as the semaphores, can be stored in the kernel and only accessed via system calls. This approach eliminates the problem.

Second, most modern operating systems (including UNIX and Windows) offer a way for processes to share some portion of their address space with other processes. In this way, buffers and other data structures can be shared. In the worst case, that nothing else is possible, a shared file can be used.

If two or more processes share most or all of their address spaces, the distinction between processes and threads becomes somewhat blurred but is nevertheless present. Two processes that share a common address space still have different open files, alarm timers, and other per-process properties, whereas the threads within a single process share them. And it is always true that multiple processes sharing a common address space never have the efficiency of user-level

threads since the kernel is deeply involved in their management.

2.7 MONITORS

With semaphores interprocess communication looks easy, right? Forget it. Look closely at the order of the down s before inserting or removing items from the buffer in Fig. 2-24. Suppose that the two down s in the producer’s code were reversed in order, so mutex was decremented before empty instead of after it. If the buffer were completely full, the producer would block, with mutex set to 0. Consequently, the next time the consumer tried to access the buffer, it would do a down on mutex, now 0, and block too. Both processes would stay blocked forever and no more work would ever be done. This unfortunate situation is called a deadlock.

This problem is pointed out to show how careful you must be when using semaphores. One subtle error and everything comes to a grinding halt. It is like programming in assembly language, only worse, because the errors are race conditions, deadlocks, and other forms of unpredictable and irreproducible behavior.

To make it easier to write correct programs, Hoare (1974) and Brinch Hansen (1975) proposed a higher-level synchronization primitive called a monitor . Their proposals differed slightly, as described below. A monitor is a collection of procedures, variables, and data structures that are all grouped together in a special kind of module or package. Processes may call the procedures in a monitor whenever they want to, but they cannot directly access the monitor’s internal data structures from procedures declared outside the monitor.

monitor example

integer i ;

condition c ;

procedure producer ( );

end ;

procedure consumer ( );

end ;

end monitor ;

Figure 2-26. A monitor.

Monitors have an important property that makes them useful for achieving mutual exclusion: only one process can be active in a monitor at any instant. Monitors are a programming language construct, so the compiler knows they are special and can handle calls to monitor procedures differently from other procedure calls. Typically, when a process calls a monitor procedure, the first few instructions of the procedure will check to see, if any other process is currently active within the monitor. If so, the calling process will be suspended until the other process has left the monitor. If no other process is using the monitor, the calling process may enter.

It is up to the compiler to implement the mutual exclusion on monitor entries, but a common way is to use a mute or binary semaphore. Because the compiler, not the programmer, is arranging for the mutual exclusion, it is much less likely that something will go wrong. In any event, the person writing the monitor does not have to be aware of how the compiler arranges for mutual exclusion. It is sufficient to know that by turning all the critical regions into monitor procedures, no two processes will ever execute their critical regions at the same time.

Although monitors provide an easy way to achieve mutual exclusion, as we have seen above, that is not enough. We also need a way for processes to block when they cannot proceed. In the producer-consumer problem, it is easy enough to put all the tests for buffer-full and buffer-empty in monitor procedures, but how should the producer block when it finds the buffer full?

The solution lies in the introduction of condition variables , along with two operations on them, wait and signal . When a monitor procedure discovers that it cannot continue (e.g., the producer finds the buffer full), it does a wait on some condition variable, say, full . This action causes the calling process to block. It also allows another process that had been previously prohibited from entering the monitor to enter now.

This other process, for example, the consumer, can wake up its sleeping partner by doing a signal on the condition variable that its partner is waiting on. To avoid having two active processes in the monitor at the same time, we need a rule telling what happens after a signal . Hoare proposed letting the newly awakened process run, suspending the other one. Brinch Hansen proposed finessing the problem by requiring that a process doing a signal must exit the monitor immediately. In other words, a signal statement may appear only as the final statement in a monitor procedure. We will use Brinch Hansen’s proposal because it is conceptually simpler and is also easier to implement. If a signal is done on a condition variable on which several processes are waiting, only one of them, determined by the system scheduler, is revived.

As an aside, there is also a third solution, not proposed by either Hoare or Brinch Hansen. This is to let the signaler continue to run and allow the waiting process to start running only after the signaler has exited the monitor.

Condition variables are not counters. They do not accumulate signals for later use the way semaphores do. Thus if a condition variable is signaled with no one waiting on it, the signal is lost forever. In other words, the wait must come before the signal . This rule makes the implementation much simpler. In practice it is not a problem because it is easy to keep track of the state of each process with variables, if need be.

A process that might otherwise do a signal can see that this operation is not necessary by looking at the variables.

monitor ProducerConsumer

condition full , empty ;

integer count ;

procedure insert (item : integer );

begin

if count = N then wait (full );

insert_item (item );

count := count + 1:

if count = 1 then signal (empty )

end ;

function remove : integer ;

begin

if count = 0 then wait (empty);

remove = remove_item ;

count := count - 1;

if count = N - 1 then signal (full )

end ;

count := 0;

end monitor ;

procedure producer ;

begin

while true do

begin

item = produce_item ;

ProducerConsumer .insert (item )

end

end ;

procedure consumer ;

begin

while true do

begin

item = ProducerConsumer .remove ;

consume_item (item )

end

end ;

Only one monitor procedure at a time is active. The buffer has N slots.

You may be thinking that the operations wait and signal look similar to sleep and wakeup , which we saw earlier had fatal race conditions. They are very similar, but with one crucial difference:

sleep and wakeup failed because while one process was trying to go to sleep, the other one was trying to wake it up. With monitors, that cannot happen. The automatic mutual exclusion on monitor procedures guarantees that if, say, the producer inside a monitor procedure discovers that the buffer is full, it will be able to complete the wait operation without having to worry about the possibility that the scheduler may switch to the consumer just before the wait completes. The consumer will not even be let into the monitor at all until the wait is finished and the producer

has been marked as no longer run able.

Although Pidgin Pascal is an imaginary language, some real programming languages also support monitors, although not always in the form designed by Hoare and Brinch Hansen. One such language is Java. Java is an object-oriented language that supports user-level threads and also allows methods (procedures) to be grouped together into classes. By adding the keyword synchronized to a method declaration, Java guarantees that once any thread has started executing that method, no other thread will be allowed to start executing any other synchronized method in that class.

The solution consists of four classes. The outer class, ProducerConsumer , creates and starts two threads, p and c . The second and third classes, producer and consumer , respectively, contain the code for the producer and consumer. Finally, the class our_monitor , is the monitor. It contains two synchronized threads that are used for actually inserting items into the shared buffer and taking them out. Unlike in the previous examples, we have finally shown the full code of insert and remove here.

The producer and consumer threads are functionally identical to their counterparts in all our previous examples. The producer has an infinite loop generating data and putting it into the common buffer. The consumer has an equally infinite loop taking data out of the common buffer and doing some fun thing with it.

The interesting part of this program is the class our_monitor , which contains the buffer, the administration variables, and two synchronized methods. When the producer is active inside insert , it knows for sure that the consumer cannot be active inside remove , making it safe to update the variables and the buffer without fear of race conditions. The variable count keeps track of how many items are in the buffer. It can take on any value from 0 through and including N - 1. The variable lo is the index of the buffer slot where the next item is to be fetched.

Similarly, hi is the index of the buffer slot where the next item is to be placed. It is permitted that lo = hi , which means either that 0 items or N items are in the buffer. The value of count tells which case holds.

Synchronized methods in Java differ from classical monitors in an essential way: Java does not have condition variables. Instead, it offers two procedures, wait and notify that are the equivalent of sleep and wakeup except that when they are used inside synchronized methods, they are not subject to race conditions. In theory, the method wait can be interrupted, which is what the code surrounding it is all about. Java requires that the exception handling be made explicit. For our purposes, just imagine that go_to_sleep is the way to go to sleep.

public class

ProducerConsumer {

static final int N = 100; // constant giving the buffer size

static producer p = new producer(); // instantiate a new producer thread

static consumer c = new consumer(); // instantiate a new consumer thread

static our_monitor mon = new our_monitor(); // instantiate a new monitor

public static void main(String args[ ]) {

p.start(); // start the producer thread

c.start(); // start the consumer thread

}

static class producer extends Thread {

public void run( ) { // run method contains the thread code

int item;

while(true) { // producer loop

item = produce_item();

mon.insert(item);

}

private int produce_item ( ){ … }// actually produce

}

static class consumer extends Thread {

public void run() { // run method contains the thread code

int item;

while(true) { // consumer loop

item = mon.remove();

consume_item (item);

}

private void consume_item (int item) { … } // actually consume

}

static class our_monitor { // this is a monitor

private int buffer[ ] = new int[N];

private int count = 0, lo = 0, hi = 0; // counters and indices

public synchronized void insert (int val) {

if(count == N) go_to_sleep(); //if the buffer is full, go to sleep

buffer [hi] = val; // insert an item into the buffer

hi = (hi + 1) % N; // slot to place next item in

count = count + 1; // one more item in the buffer now

if(count == 1) notify( ); // if consumer was sleeping, wake it up

}

public synchronized int remove( ) {

int val;

if(count == 0) go_to_sleep( ); // if the buffer is empty, go to sleep

val = buffer [lo]; // fetch an item from the buffer

lo = (lo + 1) % N; // slot to fetch next item from

count = count - 1; // one few items in the buffer

if(count == N - 1) notify(); // if producer was sleeping, wake it up

return val;

}

private void go_to_sleep() { try{wait( );} catch{ InterruptedException exc) {};}

}

By making the mutual exclusion of critical regions automatic, monitors make parallel programming much less error-prone than with semaphores. Still, they too have some drawbacks.

It is not for nothing that our two examples of monitors were in Pidgin Pascal and Java instead of C, as are the other examples in this book. As we said earlier, monitors are a programming language concept. The compiler must recognize them and arrange for the mutual exclusion somehow. C, Pascal, and most other languages do not have monitors, so it is unreasonable to expect their compilers to enforce any mutual exclusion rules. In fact, how could the compiler even know which procedures were in monitors and which were not?

These same languages do not have semaphores either, but adding semaphores is easy: All you need to do is add two short assembly code routines to the library to issue the up and down system calls. The compilers do not even have to know that they exist. Of course, the operating systems have to know about the semaphores, but at least if you have a semaphore-based operating system, you can still write the user programs for it in C or C++ (or even assembly language if you are masochistic enough). With monitors, you need a language that has them built in.

Another problem with monitors, and also with semaphores, is that they were designed for solving the mutual exclusion problem on one or more CPUs that all have access to a common memory.

By putting the semaphores in the shared memory and protecting them with TSL instructions, we can avoid races. When we go to a distributed system consisting of multiple CPUs, each with its own private memory, connected by a local area network, these primitives become inapplicable.

The conclusion is that semaphores are too low level and monitors are not usable except in a few programming languages. Also, none of the primitives provide for information exchange between machines. Something else is needed.

2.8 MESSAGE PASSING

That something else is message passing . This method of interprocess communication uses two primitives, send and receive , which, like semaphores and unlike monitors, are system calls rather than language constructs. As such, they can easily be put into library procedures, such as send(destination, &message);and

receive(source, &message);The former call sends a message to a given destination and the latter one receives a message from a given source (or from ANY , if the receiver does not care). If no message is available, the receiver can block until one arrives. Alternatively, it can return immediately with an error code.

Design Issues for Message Passing Systems

Message passing systems have many challenging problems and design issues that do not arise with semaphores or monitors, especially if the communicating processes are on different machines connected by a network. For example, messages can be lost by the network. To guard against lost messages, the sender and receiver can agree that as soon as a message has been received, the receiver will send back a special acknowledgement message. If the sender has not received the acknowledgement within a certain time interval, it retransmits the message.

Now consider what happens if the message itself is received correctly, but the acknowledgement is lost. The sender will retransmit the message, so the receiver will get it twice. It is essential that the receiver be able to distinguish a new message from the retransmission of an old one. Usually, this problem is solved by putting consecutive sequence numbers in each original message. If the receiver gets a message bearing the same sequence number as the previous message, it knows

that the message is a duplicate that can be ignored. Successfully communicating in the face of unreliable message passing is a major part of the study of computer networks

Message systems also have to deal with the question of how processes are named, so that the process specified in a send or receive call is unambiguous. Authentication is also an issue in message systems: how can the client tell that he is communicating with the real file server, and not with an imposter?

At the other end of the spectrum, there are also design issues that are important when the sender and receiver are on the same machine. One of these is performance. Copying messages from one process to another is always slower than doing a semaphore operation or entering a monitor.

Much work has gone into making message passing efficient. Cheriton (1984), for example, suggested limiting message size to what will fit in the machine’s registers, and then doing message passing using the registers.

The Producer-Consumer Problem with Message Passing

Now let us see how the producer-consumer problem can be solved with message passing and no shared memory. A solution is given in Fig. 2-29. We assume that all messages are the same size and that messages sent but not yet received are buffered automatically by the operating system.

In this solution, a total of N messages is used, analogous to the N slots in a shared memory buffer. The consumer starts out by sending N empty messages to the producer. Whenever the producer has an item to give to the consumer, it takes an empty message and sends back a full one. In this way, the total number of messages in the system remains constant in time, so they can be stored in a given amount of memory known in advance.

If the producer works faster than the consumer, all the messages will end up full, waiting for the consumer: the producer will be blocked, waiting for an empty to come back. If the consumer works faster, then the reverse happens: all the messages will be empties waiting for the producer to fill them up: the consumer will be blocked, waiting for a full message.

#define N 100 /* number of slots in the buffer */

void producer(void)

{

int item;

message m;/* message buffer */

while (TRUE) {

item = produce_item( );/* generate something to put in buffer */

receive(consumer, &m);/* wait for an empty to arrive */

build_message (&m, item);/* construct a message to send */

send(consumer, &m);/* send item to consumer */

}

void consumer(void) {

int item, i;

message m;

for (i = 0; i < N; i++) send(producer, &m);/* send N empties */

while (TRUE) {

receive(producer, &m);/* get message containing item */

item = extract_item(&m);/* extract item from message */

send(producer, &m);/* send back empty reply */

consume_item(tem);/* do something with the item */

}

The producer-consumer problem with N messages.

Many variants are possible with message passing. For starters, let us look at how messages are addressed. One way is to assign each process a unique address and have messages be addressed to processes.

A different way is to invent a new data structure, called a mailbox. A mailbox is a place to buffer a certain number of messages, typically specified when the mailbox is created.

When mailboxes are used, the address parameters, in the send and receive calls, are mailboxes,

not processes. When a process tries to send to a mailbox that is full, it is suspended until a message is removed from that mailbox, making room for a new one.

For the producer-consumer problem, both the producer and consumer would create mailboxes large enough to hold N messages. The producer would send messages containing data to the consumer’s mailbox, and the consumer would send empty messages to the producer’s mailbox.

When mailboxes are used, the buffering mechanism is clear: the destination mailbox holds messages that have been sent to the destination process but have not yet been accepted.

The other extreme from having mailboxes is to eliminate all buffering. When this approach is followed, if the send is done before the receive , the sending process

is blocked until the receive happens, at which time the message can be copied directly from the sender to the receiver, with no intermediate buffering. Similarly, if the receive is done first, the receiver is blocked until a send happens. This strategy is often known as a rendezvous . It is easier to implement than a buffered message scheme but is less flexible since the sender and receiver are forced to run in

lockstep.

Message passing is commonly used in parallel programming systems. One well-known message passing system, for example, is MPI (Message-Passing Interface ).

2.9 CLASSICAL IPC PROBLEMS

The operating systems literature is full of interesting problems that have been widely discussed and analyzed using a variety of synchronization methods. In the following sections we will examine three of the better-known problems.

2.9.1 The Dining Philosophers Problem

In 1965, Dijkstra posed and solved a synchronization problem he called the dining philosophers problem . Since that time, everyone inventing yet another synchronization primitive has felt obligated to demonstrate how wonderful the new primitive is by showing how elegantly it solves the dining philosophers problem. The problem can be stated quite simply as follows. Five philosophers are seated around a circular table. Each philosopher has a plate of spaghetti. The spaghetti is so slippery that a philosopher needs two forks to eat it. Between each pair of plates is

one fork.

The life of a philosopher consists of alternate periods of eating and thinking. (This is something of an abstraction, even for philosophers, but the other activities are irrelevant here.) When a philosopher gets hungry, she tries to acquire her left and right fork, one at a time, in either order.

If successful in acquiring two forks, she eats for a while, then puts down the forks, and continues to think. The key question is: Can you write a program for each philosopher that does what it is supposed to do and never gets stuck? (It has been pointed out that the two-fork requirement is somewhat artificial; perhaps we should switch from Italian food to Chinese food, substituting rice for spaghetti and chopsticks for forks.)

The procedure take_fork waits until the specified fork is available and then seizes it. Unfortunately, the obvious solution is wrong. Suppose that all five philosophers take their left forks simultaneously. None will be able to take their right forks, and there will be a deadlock.

#define N 5/* number of philosophers */

void philosopher(int i)/* i: philosopher number, from 0 to 4 */

{

while (TRUE) {

think( ); /* philosopher is thinking */

take_fork(i); /* take left fork */

take_fork((i+1) % N);/* take right fork; % is modulo operator */

eat(); /* yum-yum, spaghetti */

put_fork(i); /* Put left fork back on the table */

put_fork((i+1) % N);/* put right fork back on the table */

}

A nonsolution to the dining philosophers problem.

We could modify the program so that after taking the left fork, the program checks to see if the right fork is available. If it is not, the philosopher puts down the left one, waits for some time, and then repeats the whole process. This proposal too, fails, although for a different reason. With a little bit of bad luck, all the philosophers could start the algorithm simultaneously, picking up their left forks, seeing that their right forks were not available, putting down their left forks, waiting, picking up their left forks again simultaneously, and so on, forever. A situation like this, in which all the programs continue to run indefinitely but fail to make any progress is called

starvation . (It is called starvation even when the problem does not occur in an Italian or a Chinese restaurant.)

Now you might think, “if the philosophers would just wait a random time instead of the same time after failing to acquire the right-hand fork, the chance that everything would continue in lockstep for even an hour is very small.” This observation is true, and in nearly all applications trying again later is not a problem. For example, in the popular Ethernet local area network, if two computers send a packet at the same time, each one waits a random time and tries again; in practice this solution works fine. However, in a few applications one would prefer a solution that always works and cannot fail due to an unlikely series of random numbers. Think about safety control in a nuclear power plant.

One improvement to Fig. 2-32 that has no deadlock and no starvation is to protect the five statements following the call to think by a binary semaphore. Before starting to acquire forks, a philosopher would do a down on mutex. After replacing the forks, she would do an up on mutex .

From a theoretical viewpoint, this solution is adequate. From a practical one, it has a performance bug: only one philosopher can be eating at any instant. With five forks available, we should be able to allow two philosophers to eat at the same time.

The solution presented in Fig. 2-33 is deadlock-free and allows the maximum parallelism for an arbitrary number of philosophers. It uses an array, state , to keep track of whether a philosopher is eating, thinking, or hungry (trying to acquire forks). A philosopher may move only into eating state if neither neighbor is eating. Philosopher i ’s neighbors are defined by the macros LEFT and RICHT . In other words, if i is 2, LEFT is 1 and RIGHT is 3.

The program uses an array of semaphores, one per philosopher, so hungry philosophers can block if the needed forks are busy. Note that each process runs the procedure philosopher as its main code, but the other procedures, take_forks , put_forks, and test are ordinary procedures and not separate processes.

#define N5/* number of philosophers */

#define LEFT(i+N-1)%N/* number of i's left neighbor */

#define RIGHT(i+1)%N/* number of i's right neighbor */

#define THINKING0/* philosopher is thinking */

#define HUNGRY1/* philosopher is trying to get forks */

#define EATING2/* philosopher is eating */

typedef int semaphore;/* semaphores are a special kind of int */

int state[N];/* array to keep track of everyone's state */

semaphore mutex = 1;/* mutual exclusion for critical regions */

semaphore s[N];/* one semaphore per philosopher */

void philosopher (int i)/* i: philosopher number, from 0 to N-1 */

{

while (TRUE) {/* repeat forever */

think();/* philosopher is thinking */

take_forks(i);/* acquire two forks or block */

eat();/* yum-yum, spaghetti */

put_forks(i);/* put both forks back on table */

}

void take_forks(int i)/* i: philosopher number, from 0 to N-1 */

{

down(&mutex); /* enter critical region */

state[i] = HUNGRY;/* record fact that philosopher i is hungry */

test(i);/* try to acquire 2 forks */

up(&mutex); /* exit critical region */

down(&s[i]); /* block if forks were not acquired */

}

void put_forks(i)/* i: philosopher number, from 0 to N-1 */

{

down(&mutex); /* enter critical region */

state[i] = THINKING;/* philosopher has finished eating */

test(LEFT); /* see if left neighbor can now eat */

test(RIGHT);/* see if right neighbor can now eat */

up(&mutex); /* exit critical region */

}

void test(i)/* i: philosopher number, from 0 to N-1 */

{

if (state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING) {

state[i] = EATING;

up(&s[i]);

}

A solution to the dining philosophers problem.

2.9.2 The readers and writers problem

The dining philosophers problem is useful for modeling processes that are competing for exclusive access to a limited number of resources, such as I/O devices. Another famous problem is the readers and writers problem (Courtois et al., 1971), which models access to a database.

Imagine, for example, an airline reservation system, with many competing processes wishing to read and write it. It is acceptable to have multiple processes reading the database at the same time, but if one process is updating (writing) the database, no other processes may have access to the database, not even readers. The question is how do you program the readers and the writers?

In this solution, the first reader to get access to the database does a down on the semaphore db .

Subsequent readers merely increment a counter, rc . As readers leave, they decrement the counter and the last one out does an up on the semaphore, allowing a blocked writer, if there is one, to get in.

The solution presented here implicitly contains a subtle decision that is worth commenting on.

Suppose that while a reader is using the database, another reader comes along. Since having two readers at the same time is not a problem, the second reader is admitted. A third and subsequent readers can also be admitted if they come along.

Now suppose that a writer comes along. The writer cannot be admitted to the database, since writers must have exclusive access, so the writer is suspended. Later, additional readers show up.

As long as at least one reader is still active, subsequent readers are admitted. As a consequence of this strategy, as long as there is a steady supply of readers, they will all get in as soon as they arrive. The writer will be kept suspended until no reader is present. If a new reader arrives, say, every 2 seconds, and each reader takes 5 seconds to do its work, the writer will never get in.

To prevent this situation, the program could be written slightly differently: when a reader arrives and a writer is waiting, the reader is suspended behind the writer instead of being admitted immediately. In this way, a writer has to wait for readers that were active when it arrived to finish but does not have to wait for readers that came along after it. The disadvantage of this solution is that it achieves less concurrency and thus lower performance. Courtois et al. present a solution

that gives priority to writers. For details, we refer you to the paper.

typedef int semaphore;/* use your imagination */

semaphore mutex = 1;/* controls access to 'rc' */

semaphore db = 1;/* controls access to the database */

int rc = 0;/* # of processes reading or wanting to */

void reader(void)

{

while (TRUE) {/* repeat forever */

down(&mutex); /* get exclusive access to 'rc' */

rc = rc + 1;/* one reader more now */

if (re == 1) down(&db); /* if this is the first reader… */

up{&mutex);/* release exclusive access to 'rc' */

read_data_base();/* access the data */

down(&mutex);/* get exclusive access to 'rc' */

rc = rc - 1; /* one reader fewer now */

if (rc == 0) up(&db);/* if this is the last reader… */

up(&mutex);/* release exclusive access to 'rc' */

use_data_read();/* noncritical region */

}

void writer(void)

{

while (TRUE) {/* repeat forever */

think_up_data(); /* noncritical region */

down(&db);/* get exclusive access */

write_data_base(); /* update the data */

up(&db); /* release exclusive access */

}

A solution to the readers and writers problem.

2.9.3 The Sleeping Barber Problem

Another classical IPC problem takes place in a barber shop. The barber shop has one barber, one barber chair, and n chairs for waiting customers, if any, to sit on. If there are no customers present, the barber sits down in the barber chair and falls asleep, when a customer arrives, he has to wake up the sleeping barber. If additional customers arrive while the barber is cutting a customer’s hair, they either sit down (if there are empty chairs) or leave the shop (if all chairs are full). The problem is to program the barber and the customers without getting into race conditions. This problem is similar to various queuing situations, such as a militiaperson helpdesk with a computerized call waiting system for holding a limited number of incoming calls.

The sleeping barber.

Our solution uses three semaphores: customers , which counts waiting customers (excluding the customer in the barber chair, who is not waiting), barbers , the number of barbers (0 or 1) who are idle, waiting for customers, and mutex , which is used for mutual exclusion. We also need a variable, waiting , which also counts the waiting customers. It is essentially a copy of customers .

The reason for having waiting is that there is no way to read the current value of a semaphore. In this solution, a customer entering the shop has to count the number of waiting customers. If it is less than the number of chairs, he stays; otherwise, he leaves.

When the barber shows up for work in the morning, he executes the procedure barber, causing him to block on the semaphore customers because it is

initially 0. The barber then goes to sleep, as shown in Fig. 2-35. He stays asleep until the first customer shows up.

#define CHAIRS 5 /* # chairs for waiting customers */

typedef int semaphore; /* use your imagination */

semaphore customers = 0; /* # of customers waiting for service */

semaphore barbers = 0; /* # of barbers waiting for customers */

semaphore mutex = 1; /* for mutual exclusion */

int waiting = 0;/* customers are waiting (not being cut) */

void barber(void)

{

white (TRUE) {

down(&customers);/* go to sleep if # of customers is 0 */

down(&mutex);/* acquire access to 'waiting' */

waiting = waiting - 1;/* decrement count of waiting customers */

up(&barbers);/* one barber is now ready to cut hair */

up(&mutex);/* release 'waiting' */

cut_hair();/* cut hair (outside critical region) */

}

void customer(void)

{

down(&mutex);/* enter critical region */

if (waiting < CHAIRS) { /* if there are no free chairs, leave */

waiting = waiting + 1;/* increment count of waiting customers */

up(&customers);/* wake up barber if necessary */

up(&mutex);/* release access to 'waiting' */

down(&barbers);/* go to sleep if # of free barbers is 0 */

get_haircut();/* be seated and be serviced */

} else {

up(&mutex);/* shop is full; do not wait */

}

A solution to the sleeping barber problem.

When a customer arrives, he executes customer , starting by acquiring mutex to enter a critical region. If another customer enters shortly thereafter, the second one will not be able to do anything until the first one has released mutex . The customer then checks to see if the number of waiting customers is less than the number of chairs. If not, he releases mutex and leaves without a haircut.

If there is an available chair, the customer increments the integer variable, waiting . Then he does an up on the semaphore customers , thus waking up the barber. At this point, the customer and barber are both awake. When the customer releases mutex , the barber grabs it, does some housekeeping, and begins the haircut.

When the haircut is over, the customer exits the procedure and leaves the shop. Unlike our earlier examples, there is no loop for the customer because each one gets only one haircut. The barber loops, however, to try to get the next customer. If one is present, another haircut is given. If not, the barber goes to sleep.

As an aside, it is worth pointing out that although the readers and writers and sleeping barber problems do not involve data transfer, they are still belong to the area of IPC because they involve synchronization between multiple processes.

Monday, 7 April 2014

OPERATING SYSTEM UNIT II

No comments:

Post a Comment

Total Pageviews

Pages

About