SFIT, Borivali
Class-SE (A&B) Subject:Operating System Subject Teacher: [Link] Rane
*************************************************************************************
Module 2: Process Co-ordination
Introduction:
# Interprocess Communication:
Processes executing concurrently in the operating system may be either independent processes or
cooperating processes. A process is independent if it cannot affect or be affected by the other processes
executing in the system. Any process that does not share data with any other process is independent. A
process is cooperating if it can affect or be affected by the other processes executing in the system.
Clearly, any process that shares data with other processes is a cooperating process.
There are several reasons for providing an environment that allows process cooperation:
1. Information sharing- Since several users may be interested in the same piece of information (for
instance, a shared file), we must provide an environment to allow concurrent access to such information.
[Link] speedup- If we want a particular task to run faster, we must break it into subtasks, each
of which will be executing in parallel with the others. Notice that such a speedup can be achieved only if
the computer has multiple processing elements (such as CPUs or I/O channels).
3. Modularity-We may want to construct the system in a modular fashion, dividing the system functions
into separate processes or threads.
4. Convenience- Even an individual user may work on many tasks at the same time. For instance, a user
may be editing, printing, and compiling in parallel.
A cooperating process is one that can affect or be affected by other processes executing in the system.
Cooperating processes can either directly share a logical address space (that is, both code and data) or be
allowed to share data only through files or messages.
Cooperating processes require an interprocess communication (IPC) mechanism that will allow them to
exchange data and information. There are two fundamental models of interprocess communication: (1)
shared memory and (2) message passing.
1
SFIT, Borivali
Class-SE (A&B) Subject:Operating System Subject Teacher: [Link] Rane
*************************************************************************************
Figure. Communications models. (a) Message passing. (b) Shared memory.
Both of the models just discussed are common in operating systems, and many systems implement
both. Message passing is useful for exchanging smaller amounts of data, because no conflicts need be
avoided. Message passing is also easier to implement than is shared memory for intercomputer
communication. Shared memory allows maximum speed and convenience of communication. Shared
memory is faster than message passing, as message passing systems are typically implemented using
system calls and thus require the more time-consuming task of kernel intervention. In contrast, in shared
memory systems, system calls are required only to establish shared-memory regions. Once shared
memory is established, all accesses are treated as routine memory accesses, and no assistance from the
kernel is required.
Concurrent access to shared data may result in data inconsistency, however. In this chapter, we discuss
various mechanisms to ensure the orderly execution of cooperating processes that share a logical address
space, so that data consistency is maintained.
To illustrate the concept of cooperating processes, let's consider the producer-consumer problem,
which is a common paradigm for cooperating processes.
• A producer process produces information that is consumed by a consumer process. For example,
a compiler may produce assembly code, which is consumed by an assembler. The assembler, in
turn, may produce object modules, which are consumed by the loader.
• The producer-consumer problem also provides a useful metaphor for the client-server paradigm.
• We generally think of a server as a producer and a client as a consumer. For example, a Web
server produces (that is, provides) HTML files and images, which are consumed (that is, read) by
the client Web browser requesting the resource
2
SFIT, Borivali
Class-SE (A&B) Subject:Operating System Subject Teacher: [Link] Rane
*************************************************************************************
A bounded buffer could be used to enable processes to share memory. In producer consumer problem
original solution allowed at most BUFFER_SIZE - 1 items in the buffer at the same time. Suppose we want
to modify the algorithm to remedy this deficiency, we add an integer variable counter, initialized to 0.
counter is incremented every time we add a new item to the buffer and is decremented every time we
remove one item from the buffer.
The code for the producer process can be modified as follows:
The code for the consumer process can be modified as follows:
Although both the producer and consumer routines shown above are correct separately, they may not
function correctly when executed concurrently. suppose that the value of the variable counter is currently
5 and that the producer and consumer processes execute the statements "counter++" and "counter--"
concurrently. Following the execution of these two statements, the value of the variable counter may be
4, 5, or 6! The only correct result, though, is counter == 5, which is generated correctly if the producer and
consumer execute separately.
where register1 is one of the local CPU registers. Similarly, the statement register2"counter--" is
implemented as follows:
3
SFIT, Borivali
Class-SE (A&B) Subject:Operating System Subject Teacher: [Link] Rane
*************************************************************************************
After interleaving is”
We would arrive at this incorrect state because we allowed both processes to manipulate the variable
counter concurrently. A situation like this, where several processes access and manipulate the same data
concurrently and the outcome of the execution depends on the particular order in which the access takes
place, is called a race condition. To guard against the race condition above, we need to ensure that only
one process at a time can be manipulating the variable counter. To make such a guarantee, we require
that the processes be synchronized in some way.
Critical Section Problem:
Consider a system consisting of n processes {Po, P1 , ... , Pn _ I}. Each process has a segment of code, called
critical section in which the process may be changing common variables, updating a table, writing a file,
and so on. The important feature of the system is that, when one process is executing in its critical section,
no other process is to be allowed to execute in its critical section. That is, no two processes are executing
in their critical sections at the same time. The critical-section problem is to design a protocol that the
processes can use to cooperate. Each process must request permission to enter its critical section. The
section of code implementing this request is the entry section. The critical section may be followed by an
exit section. The remaining code is the remainder section. The general structure of a typical process Pi is
shown in Figure.
4
SFIT, Borivali
Class-SE (A&B) Subject:Operating System Subject Teacher: [Link] Rane
*************************************************************************************
The entry section and exit section are enclosed in boxes to highlight these important segments of code. A
solution to the critical-section problem must satisfy the following three requirements:
[Link] exclusion: If process Pi is executing in its critical section, then no other processes can be
executing in their critical sections.
2. Progress. If no process is executing in its critical section and some processes wish to enter their critical
sections, then only those processes that are not executing in their remainder sections can participate in
deciding which will enter its critical section next, and this selection can not be postponed indefinitely.
[Link] waiting. There exists a bound, or limit, on the number of times that other processes are
allowed to enter their critical sections after a process has made a request to enter its critical section and
before that request is granted.
# Peterson's solution
A classic software-based solution to the critical-section problem known as Peterson's solution. Because of
the way modern computer architectures perform basic machine-language instructions, such as load and
store, there are no guarantees that Peterson's solution will work correctly on such architectures. we
present the solution because it provides a good algorithmic description of solving the critical-section
problem and illustrates some of the complexities involved in designing software that addresses the
requirements of mutual exclusion, progress, and bounded waiting.
Peterson's solution is restricted to two processes that alternate execution between their critical sections
and remainder sections. The processes are numbered Po and P1. For convenience, when presenting Pi,
we use Pj to denote the other process; that is, j equals 1 - i.
Peterson's solution requires the two processes to share two data items:
int turn;
boolean flag[2];
The variable turn indicates whose turn it is to enter its critical section. That is, if turn == i, then process
Pi is allowed to execute in its critical section. The flag array is used to indicate if a process is ready to enter
its critical section. For example, if flag [i] is true, this value indicates that Pi is ready to enter its critical
5
SFIT, Borivali
Class-SE (A&B) Subject:Operating System Subject Teacher: [Link] Rane
*************************************************************************************
section. With an explanation of these data structures complete, we are now ready to describe the
algorithm shown in Figure.
To enter the critical section, process Pi first sets flag [i] to be true and then sets turn to the value j, thereby
asserting that if the other process wishes to enter the critical section, it can do so. If both processes try to
enter at the same time, turn will be set to both i and j at roughly the same time. Only one of these
assignments will last; the other will occur but will be overwritten immediately.
The eventual value of turn determines which of the two processes is allowed to enter its critical section
first. We now prove that this solution is correct. We need to show that: Mutual exclusion is preserved.
The progress requirement is satisfied. The bounded-waiting requirement is met.
To prove property 1, we note that each P; enters its critical section only if either flag [j] == false or turn ==
i. Also note that, if both processes can be executing in their critical sections at the same time, then flag
[0] == flag [1] ==true. These two observations imply that Po and P1 could not have successfully executed
their while statements at about the same time, since the value of turn can be either 0 or 1 but camwt be
both. Hence, one of the processes -say, Pi -must have successfully executed the while statencent, whereas
P; had to execute at least one additional statement ("turn== j"). However, at that time, flag [j] == true and
turn == j, and this condition will persist as long as Pi is in its critical section; as a result, mutual exclusion
is preserved. To prove properties 2 and 3, we note that a process P; can be prevented from entering the
critical section only if it is stuck in the while loop with the condition flag [j] ==true and turn=== j; this loop
is the only one possible. If Pi is not ready to enter the critical section, then flag [j] ==false, and P; can enter
its critical section. If Pj has set flag [j] to true and is also executing in its while statement, then either turn
=== i or turn === j. If turn == i, then P; will enter the critical section. If turn== j, then Pi will enter the critical
section. However, once Pi exits its critical section, it will reset flag [j] to false, allowing P; to enter its critical
section. If Pi resets flag [j] to true, it must also set turn to i. Thus, since P; does not change the value of the
variable turn while executing the while statement, P; will enter the critical section (progress) after at most
one entry by P1 (bounded waiting).
#Synchronization Hardware:
However, as mentioned, software-based solutions such as Peterson's are not guaranteed to work on
modern computer architectures. Instead, we can generally state that any solution to the critical-section
problem requires a simple tool-a lock. Race conditions are prevented by requiring that critical regions be
6
SFIT, Borivali
Class-SE (A&B) Subject:Operating System Subject Teacher: [Link] Rane
*************************************************************************************
protected by locks. That is, a process must acquire a lock before entering a critical section; it releases the
lock when it exits the critical section. This is illustrated in Figure
# semaphore
The hardware-based solutions to the critical-section problem presented are complicated for application
programmers to use. To overcome this difficulty, we can use a synchronization tool called a semaphore .
A semaphore S is an integer variable that, apart from initialization, is accessed only through two standard
atomic operations: wait () and signal (). The wait () operation was originally termed P (from the Dutch
proberen, "to test"); signal() was originally called V (from verhogen, "to increment"). The definition of wait
() is as follows:
The definition of signal() is as follows:
All modifications to the integer value of the semaphore in the wait () and signal() operations must be
executed indivisibly. That is, when one process modifies the semaphore value, no other process can
simultaneously modify that same semaphore value. In addition, in the case of wait (S), the testing of the
integer value of S (S <= 0), as well as its possible modification (S--), must be executed without interruption.
#Semaphore as General Synchronization Tool
Operating systems often distinguish between counting and binary semaphores. The value of a counting
semaphore can range over an unrestricted domain. The value of a binary semaphore can range only
between 0 and 1. On some systems, binary semaphores are known as mutex locks, as they are locks that
provide mutual exclusion. We can use binary semaphores to deal with the critical-section problem for
multiple processes. Then processes share a semaphore, mutex, initialized to 1. Each process Pi is organized
as shown in Figure.
7
SFIT, Borivali
Class-SE (A&B) Subject:Operating System Subject Teacher: [Link] Rane
*************************************************************************************
Counting semaphores can be used to control access to a given resource consisting of a finite number of
instances. The semaphore is initialized to the number of resources available. Each process that wishes to
use a resource performs a wait() operation on the semaphore (thereby decrementing the count). When
a process releases a resource, it performs a signal() operation (incrementing the count). When the count
for the semaphore goes to 0, all resources are being used. After that, processes that wish to use a resource
will block until the count becomes greater than 0.
Implementation: The main disadvantage of the semaphore definition given here is that it requires busy
waiting. While a process is in its critical section, any other process that tries to enter its critical section
must loop continuously in the entry code. This continual looping is clearly a problem in a real
multiprogramming system, where a single CPU is shared among many processes. Busy waiting wastes CPU
cycles that some other process might be able to use productively. This type of semaphore is also called
spinlock a because the process "spins" while waiting for the lock. (Spinlocks do have an advantage in that
no context switch is required when a process must wait on a lock, and a context switch may take
considerable time. Thus, when locks are expected to be held for short times, spinlocks are useful; they are
often employed on multiprocessor systems where one thread can "spin" on one processor while another
thread performs its critical section on another processor.)
#Classical Problems of Synchronization
In this section, we present a number of synchronization problems as examples of a large class of
concurrency-control problems. These problems are used for testing nearly every newly proposed
synchronization scheme. In our solutions to the problems, we use semaphores for synchronization.
1 The Bounded-Buffer Problem-
it is commonly used to illustrate the power of synchronization primitives. We assume that the pool
consists of n buffers, each capable of holding one item. The mutex semaphore provides mutual exclusion
for accesses to the buffer pool and is initialized to the value 1. The empty and full semaphores count the
number of empty and full buffers. The semaphore empty is initialized to the value n; the semaphore full
is initialized to the value 0.
The code for the producer process is shown in Figure.
8
SFIT, Borivali
Class-SE (A&B) Subject:Operating System Subject Teacher: [Link] Rane
*************************************************************************************
the code for the consumer process is shown in Figure.
We can interpret this code as the producer producing full buffers for the consumer or as the consumer
producing empty buffers for the producer.
2 The Readers-Writers Problem
Suppose that a database is to be shared among several concurrent processes. Some of these processes
may want only to read the database, whereas others may want to update (that is, to read and write) the
database. We distinguish between these two types of processes by referring to the former as readers and
to the latter as writers. Obviously, if two readers access the shared data simultaneously, no adverse
effects will result. However, if a writer and some other process (either a reader or a writer) access the
database simultaneously, chaos may ensue.
9
SFIT, Borivali
Class-SE (A&B) Subject:Operating System Subject Teacher: [Link] Rane
*************************************************************************************
To ensure that these difficulties do not arise, we require that the writers have exclusive access to the
shared database while writing to the database. This synchronization problem is referred to as the readers-
writers problem.
Since it was originally stated, it has been used to test nearly every new synchronization primitive. The
readers-writers problem has several variations, all involving priorities. The simplest one, referred to as the
first readers-writers problem, requires that no reader be kept waiting unless a writer has already obtained
permission to use the shared object. In other words, no reader should wait for other readers to finish
simply because a writer is waiting. The second readerswriters problem requires that, once a writer is
ready, that writer performs its write as soon as possible. In other words, if a writer is waiting to access the
object, no new readers may start reading. A solution to either problem may result in starvation. In the
first case, writers may starve; in the second case, readers may starve. For this reason, other variants of
the problem have been proposed. Next, we present a solution to the first readers-writers problem.
In the solution to the first readers-writers problem, the reader processes share the following data
structures: semaphore mutex, wrt; int readcount;
The semaphores mutex and wrt are initialized to 1; readcount is initialized to 0. The semaphore wrt is
common to both reader and writer processes. The mutex semaphore is used to ensure mutual exclusion
when the variable readcount is updated. The readcount variable keeps track of how many processes are
currently reading the object. The semaphore wrt functions as a mutual-exclusion semaphore for the
writers. It is also used by the first or last reader that enters or exits the critical section. It is not used by
readers who enter or exit while other readers are in their critical sections. The code for a writer process
is shown in Figure
10
SFIT, Borivali
Class-SE (A&B) Subject:Operating System Subject Teacher: [Link] Rane
*************************************************************************************
the code for a reader process is shown in Figure.
If a writer is in the critical section and n readers are waiting, then one reader is queued on wrt, and n- 1
readers are queued on mutex. Also observe that, when a writer executes signal ( wrt), we may resume
the execution of either the waiting readers or a single waiting writer. The selection is made by the
scheduler.
The selection is made by the scheduler. The readers-writers problem and its solutions have been
generalized to provide reader-writer locks on some systems. Acquiring a reader-writer lock requires
specifying the mode of the lock either read or write access. When a process wishes only to read shared
data, it requests the reader-writer lock in read mode; a process wishing to modify the shared data must
request the lock in write mode. Multiple processes are permitted to concurrently acquire a reader-writer
lock in read mode, but only one process may acquire the lock for writing, as exclusive access is required
for writers.
Reader-writer locks are most useful in the following situations:
-In applications where it is easy to identify which processes only read shared data and which processes
only write shared data.
-In applications that have more readers than writers. This is because reader-writer locks generally require
more overhead to establish than semaphores or mutual-exclusion locks. The increased concurrency of
allowing multiple readers compensates for the overhead involved in setting up the reader-writer lock.
3 The Dining-Philosophers Problem
Consider five philosophers who spend their lives thinking and eating. The philosophers share a circular
table surrounded by five chairs, each belonging to one philosopher. In the center of the table is a bowl of
rice, and the table is laid with five single chopsticks shown in figure.
11
SFIT, Borivali
Class-SE (A&B) Subject:Operating System Subject Teacher: [Link] Rane
*************************************************************************************
When a philosopher thinks, she does not interact with her colleagues. From time to time, a philosopher
gets hungry and tries to pick up the two chopsticks that are closest to her (the chopsticks that are between
her and her left and right neighbors). A philosopher may pick up only one chopstick at a time. Obviously,
she cannot pick up a chopstick that is already in the hand of a neighbor. When a hungry philosopher has
both her chopsticks at the same time, she eats without releasing her chopsticks. When she is finished
eating, she puts down both of her chopsticks and starts thinking again.
It is a simple representation of the need to allocate several resources among several processes in a
deadlock-free and starvation-free manner.
One simple solution is to represent each chopstick with a semaphore. A philosopher tries to grab a
chopstick by executing a wait () operation on that semaphore; she releases her chopsticks by executing
the signal() operation on the appropriate semaphores. Thus, the shared data are
semaphore chopstick[5];
where all the elements of chopstick are initialized to 1.
The structure of philosopher i is shown in Figure-
12
SFIT, Borivali
Class-SE (A&B) Subject:Operating System Subject Teacher: [Link] Rane
*************************************************************************************
Although this solution guarantees that no two neighbors are eating simultaneously, it nevertheless must
be rejected because it could create a deadlock. Suppose that all five philosophers become hungry
simultaneously and each grabs her left chopstick. All the elements of chopstick will now be equal to 0.
When each philosopher tries to grab her right chopstick, she will be delayed forever.
Several possible remedies to the deadlock problem are listed:
[Link] at most four philosophers to be sitting simultaneously at the table.
[Link] 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).
[Link] an asymmetric solution; that is, an odd philosopher picks up first her left chopstick and then her
right chopstick, whereas an even philosopher picks up her right chopstick and then her left chopstick
13