1
Chapter -6 Process Synchronization
What is process synchronization? Process Synchronization means sharing system resources
by processes in such a way that, Concurrent access to shared data is handled thereby minimizing
the chance of inconsistent data. Maintaining data consistency demands mechanisms to ensure
synchronized execution of cooperating processes.
Background
Recall that back in Chapter 3 we looked at cooperating processes ( those that can effect or
be effected by other simultaneously running processes ), and as an example, we used the
producer-consumer cooperating processes:
Producer code from chapter 3:
item nextProduced;
while( true ) {
/* Produce an item and store it in nextProduced */
nextProduced = makeNewItem( . . . );
/* Wait for space to become available */
while( ( ( in + 1 ) % BUFFER_SIZE ) == out )
; /* Do nothing */
/* And then store the item and repeat the loop. */
buffer[ in ] = nextProduced;
in = ( in + 1 ) % BUFFER_SIZE;
}
Consumer code from chapter 3:
item nextConsumed;
while( true ) {
/* Wait for an item to become available */
while( in == out )
; /* Do nothing */
/* Get the next available item */
nextConsumed = buffer[ out ];
out = ( out + 1 ) % BUFFER_SIZE;
/* Consume the item in nextConsumed
( Do something with it ) */
}
2
The only problem with the above code is that the maximum number of items
which can be placed into the buffer is BUFFER_SIZE - 1. One slot is unavailable
because there always has to be a gap between the producer and the consumer.
We could try to overcome this deficiency by introducing a counter variable, as
shown in the following code segments:
Unfortunately we have now introduced a new problem, because both the producer and the
consumer are adjusting the value of the variable counter, which can lead to a condition
known as a race condition. In this condition a piece of code may or may not work
correctly, depending on which of two simultaneous processes executes first, and more
importantly if one of the processes gets interrupted such that the other process runs
between important steps of the first process. ( Bank balance example discussed in class. )
The particular problem above comes from the producer executing "counter++" at the
same time the consumer is executing "counter--". If one process gets part way through
making the update and then the other process butts in, the value of counter can get left in
an incorrect state.
But, you might say, "Each of those are single instructions - How can they get interrupted
halfway through?" The answer is that although they are single instructions in C++, they
are actually three steps each at the hardware level: (1) Fetch counter from memory into a
register, (2) increment or decrement the register, and (3) Store the new value of counter
3
back to memory. If the instructions from the two processes get interleaved, there could be
serious problems, such as illustrated by the following:
Critical Section Problem
A Critical Section is a code segment that accesses shared variables and has to be executed
as an atomic action. It means that in a group of cooperating processes, at a given point of
time, only one process must be executing its critical section. If any other process also wants
to execute its critical section, it must wait until the first one finishes.
Solution to Critical Section Problem
Any solution to the critical section problem must satisfy three requirements:
4
Mutual Exclusion: If a process is executing in its critical section, then no other process
is allowed to execute in the critical section.
Progress: If no process is in the critical section, then no other process from outside can
block it from entering the critical section.
Bounded Waiting : A limit on the number of times a process can request to enter the
critical section
Peterson's Solution
Peterson’s Solution
Peterson’s Solution is a classical software based solution to the critical section problem.
In Peterson’s solution, we have two shared variables:
boolean flag[i] :Initialized to FALSE, initially no one is interested in entering the critical
section
int turn : The process whose turn is to enter the critical section.
Peterson’s Solution preserves all three conditions :
Mutual Exclusion is assured as only one process can access the critical section at any
time.
Progress is also assured, as a process outside the critical section does not blocks other
processes from entering the critical section.
Bounded Waiting is preserved as every process gets a fair chance.
5
Disadvantages of Peterson’s Solution
o It involves Busy waiting
o It is limited to 2 processes.
Synchronization Hardware
TestAndSet
TestAndSet is a hardware solution to the synchronization problem. In TestAndSet, we have a
shared lock variable which can take either of the two values, 0 or 1.
0 Unlock
1 Lock
Before entering into the critical section, a process inquires about the lock. If it is locked, it keeps
on waiting till it become free and if it is not locked, it takes the lock and executes the critical
section.
In TestAndSet, Mutual exclusion and progress are preserved but bounded waiting cannot be
preserved.
Mutex Locks
The hardware solutions presented above are often difficult for ordinary programmers to
access, particularly on multi-processor machines, and particularly because they are often
platform-dependent.
Therefore most systems offer a software API equivalent called mutex locks or
simply mutexes. ( For mutual exclusion )
The terminology when using mutexes is to acquire a lock prior to entering a critical
section, and to release it when exiting, as shown in Figure 5.8:
Just as with hardware locks, the acquire step will block the process if the lock is in use by
another process, and both the acquire and release operations are atomic.
Acquire and release can be implemented as shown here, based on a boolean variable
"available":
6
Semaphores
A Semaphore is an integer variable, which can be accessed only through two operations wait()
and signal().
There are two types of semaphores : Binary Semaphores and Counting Semaphores
Binary Semaphores : They can only be either 0 or 1. They are also known as mutex
locks, as the locks can provide mutual exclusion. All the processes can share the same
mutex semaphore that is initialized to 1. Then, a process has to wait until the lock
becomes 0. Then, the process can make the mutex semaphore 1 and start its critical
section. When it completes its critical section, it can reset the value of mutex semaphore
to 0 and some other process can enter its critical section.
Counting Semaphores : They can have any value and are not restricted over a certain
domain. They can be used to control access a resource that has a limitation on the number
of simultaneous accesses. The semaphore can be initialized to the number of instances of
the resource. Whenever a process wants to use that resource, it checks if the number of
remaining instances is more than zero, i.e., the process has an instance available. Then,
the process can enter its critical section thereby decreasing the value of the counting
semaphore by 1. After the process is over with the use of the instance of the resource, it
can leave the critical section thereby adding 1 to the number of available instances of the
resource.
7
8
Classic Problems of Synchronization
1. The Bounded-Buffer Problem
This is a generalization of the producer-consumer problem wherein access is controlled to
a shared group of buffers of a limited size.
In this solution, the two counting semaphores "full" and "empty" keep track of the current
number of full and empty buffers respectively ( and initialized to 0 and N respectively. )
The binary semaphore mutex controls access to the critical section. The producer and
consumer processes are nearly identical - One can think of the producer as producing full
buffers, and the consumer producing empty buffers.
[Link] Readers-Writers Problem
In the readers-writers problem there are some processes ( termed readers ) who only read
the shared data, and never change it, and there are other processes ( termed writers ) who
may change the data in addition to or instead of reading it. There is no limit to how many
readers can access the data simultaneously, but when a writer accesses the data, it needs
exclusive access.
There are several variations to the readers-writers problem, most centered around relative
priorities of readers versus writers.
o The first readers-writers problem gives priority to readers. In this problem, if a
reader wants access to the data, and there is not already a writer accessing it, then
access is granted to the reader. A solution to this problem can lead to starvation of
the writers, as there could always be more readers coming along to access the
data. ( A steady stream of readers will jump ahead of waiting writers as long as
there is currently already another reader accessing the data, because the writer is
forced to wait until the data is idle, which may never happen if there are enough
readers. )
o The second readers-writers problem gives priority to the writers. In this problem,
when a writer wants access to the data it jumps to the head of the queue - All
waiting readers are blocked, and the writer gets access to the data as soon as it
becomes available. In this solution the readers may be starved by a steady stream
of writers.
The following code is an example of the first readers-writers problem, and involves an
important counter and two binary semaphores:
o readcount is used by the reader processes, to count the number of readers
currently accessing the data.
o mutex is a semaphore used only by the readers for controlled access to readcount.
o rw_mutex is a semaphore used to block and release the writers. The first reader to
access the data will set this lock and the last reader to exit will release it; The
remaining readers do not touch rw_mutex. ( Eighth edition called this variable
wrt. )
o Note that the first reader to come along will block on rw_mutex if there is
currently a writer accessing the data, and that all following readers will only block
on mutex for their turn to increment readcount.
9
Some hardware implementations provide specific reader-writer locks, which are
accessed using an argument specifying whether access is requested for reading or
writing. The use of reader-writer locks is beneficial for situation in which: (1)
processes can be easily identified as either readers or writers, and (2) there are
significantly more readers than writers, making the additional overhead of the
reader-writer lock pay off in terms of increased concurrency of the readers.
10
The Dining-Philosophers Problem
The dining philosophers problem is a classic synchronization problem involving the
allocation of limited resources amongst a group of processes in a deadlock-free and
starvation-free manner:
o Consider five philosophers sitting around a table, in which there are five
chopsticks evenly distributed and an endless bowl of rice in the center, as
shown in the diagram below. ( There is exactly one chopstick between each
pair of dining philosophers. )
o These philosophers spend their lives alternating between two activities:
eating and thinking.
o When it is time for a philosopher to eat, it must first acquire two chopsticks -
one from their left and one from their right.
o When a philosopher thinks, it puts down both chopsticks in their original
locations.
The situation of the dining philosophers
One possible solution, as shown in the following code section, is to use a set of five
semaphores ( chopsticks[ 5 ] ), and to have each hungry philosopher first wait on their
left chopstick ( chopsticks[ i ] ), and then wait on their right chopstick ( chopsticks[ ( i + 1
)%5])
But suppose that all five philosophers get hungry at the same time, and each starts by
picking up their left chopstick. They then look for their right chopstick, but because it is
unavailable, they wait for it, forever, and eventually all the philosophers starve due to the
resulting deadlock.
11
Some potential solutions to the problem include:
Only allow four philosophers to dine at the same time. ( Limited simultaneous
processes. )
Allow philosophers to pick up chopsticks only when both are available, in a critical
section. ( All or nothing allocation of critical resources. )
Use an asymmetric solution, in which odd philosophers pick up their left chopstick first
and even philosophers pick up their right chopstick first. ( Will this solution always
work? What if there are an even number of philosophers? )
Note carefully that a deadlock-free solution to the dining philosophers problem does not
necessarily guarantee a starvation-free one. ( While some or even most of the philosophers may
be able to get on with their normal lives of eating and thinking, there may be one unlucky soul
who never seems to be able to get both chopsticks at the same time.
Monitors
A type, or abstract data type, encapsulates private data with public methods to operate on that
data. A monitor type presents a set of programmer-defined operations that are provided mutual
exclusion within the monitor. The monitor type also contains the declaration of variables whose
values define the state of an instance of that type, along with the bodies of procedures or
functions that operate on those variables. The syntax of a monitor is shown in Figure 6.16. The
representation of a monitor type cannot be used directly by the various processes. Thus, a
procedure defined within a monitor can access only those variables declared locally within the
monitor and its formal parameters. Similarly, the local variables of a monitor can be accessed by
only the local procedures.
12
The monitor construct ensures that only one process at a time can be active within the monitor.
Consequently, the programmer does not need to code this synchronization constraint explicitly.
A programmer who needs to write a tailor-made synchronization scheme can define one or more
variables of type condition: condition x, y; The only operations that can be invoked on a
condition variable are waito and signal O. The operation [Link]; means that the process
invoking this operation is suspended until another process invokes x. signal 0 ; The x. signal 0
operation resumes exactly one suspended process. If no process is suspended, then the signalO
operation has no effect
Dining-Philosophers Solution Using Monitors
This solution imposes the restriction that a philosopher may pick up her chopsticks only if both
of them are available.
his solution, we need to distinguish among three states in which we may find a philosopher. For
this purpose, we introduce the following data structure:
enum{thinking, hungry, eating} state [5] ;
Philosopher i can set the variable state [i] = eating only if her two neighbors are not eating:
(state[(i+4) % 5] != eating)and(state[(i+1) % 5] ! = eating).
We also need to declare condition self [5] ; where philosopher i can delay herself when she is
hungry but is unable to obtain the chopsticks she needs.
13
The distribution of the chopsticks is controlled by the monitor dp, whose definition is shown below
monitor dp
{
enum {THINKING, HUNGRY, EATING} state [5] ;
condition self[5];
void pickup (int i)
{
state[i] = HUNGRY;
test (i) ;
if (state [i] != EATING)
self [i] .wait ();
}
void putdown(int i)
{
state[i] = THINKING;
test ( (i + 4) % 5);
test((i + 1) % 5);
}
void test (int i)
{
if (( state [ (i + 4) % 5] ! = EATING ) && (state[i] == HUNGRY) && (state [(i + 1) % 5] ! = EATING))
{
state[i] = EATING;
self [i] .signal () ;
}
initialization_code()
{
for (int i = 0; i < 5; i++)
state[i] = THINKING;
}
}
It is easy to show that this solution ensures that no two neighbors are eating simultaneously and
that no deadlocks will occur. We note, however, that it is possible for a philosopher to starve to
death.