Operating Systems 22AI303

PROCESS SYNCHRONIZATION

The Critical Section Problems

 Consider a system consisting of n processes {Po, P1 , ... ,Pn-1}.
 Each process has a segment of code, called a critical section in which the process may be
changing common variables, updating a table, writing a file, and soon
 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.

The general structure of a typical process Pi is shown in below figure.

 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 reminder section.

General structure of a typical process Pi

A solution to the critical-section problem must satisfy the following three requirements:
1. Mutual exclusion: If process Pi is executing in its critical section, then no other
processes can be executing in their critical sections.

14 Dept. of CSE (AIML), MCE, Hassan

 Operating Systems 22AI303

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 cannot be postponed indefinitely.
3. Bounded 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
 This is a classic software-based solution to the critical-section problem. There are no
guarantees that Peterson's solution will work correctly on modern computer architectures
 Peterson's solution 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 or Pi and Pj
where j = 1-i Peterson's solution requires the two processes to share two data items:
int turn;
boolean flag[2];

 turn: The variable turn indicates whose turn it is to enter its critical section. Ex: if
turn == i, then process Pi is allowed to execute in its critical section
 flag: The flag array is used to indicate if a process is ready to enter its critical section.
Ex: if flag [i] is true, this value indicates that Pi is ready to enter its critical section.

1. 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.
2. 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
over written immediately.

15 Dept. of CSE (AIML), MCE, Hassan

 Operating Systems 22AI303

3. The eventual value of turn determines which of the two processes is allowed to enter its
critical section first.

do {
flag[i] = TRUE; turn =
j;
while (flag[j] && turn == j)
; // do nothing critical
section
flag[i] = FALSE;

remainder section

} while (TRUE);

The structure of process Pi in Peterson's solution

To prove that solution is correct, then we need to show that

1. Mutual exclusion is preserved
2. Progress requirement is satisfied
3. Bounded-waiting requirement is met

1) To prove Mutual exclusion

 Each pi enters its critical section only if either flag [j] == false or turn ==i.
 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 Pi and Pj 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
cannot be both. Hence, one of the processes (Pj) must have successfully executed the
while statement, whereas Pi 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.

2) To prove Progress and Bounded-waiting

 A process Pi can be prevented from entering the critical section only if it is stuck in the

16 Dept. of CSE (AIML), MCE, Hassan

 Operating Systems 22AI303

while loop with the condition flag [j] ==true and turn=== j; this loop is the only one
possible.
 If Pj is not ready to enter the critical section, then flag [j] ==false, and Pi can enter its
critical section.
 If Pj has set flag [j] = true and is also executing in its while statement, then either
turn=== i or turn ===j.
 If turn == i, then Pi will enter the critical section.
 If turn== j, then Pj will enter the critical section.
 However, once Pj exits its critical section, it will reset flag [j] = false, allowing Pi to enter
its critical section.
 If Pj resets flag [j] to true, it must also set turn to i.
 Thus, since Pi does not change the value of the variable turn while executing the while
statement, Pi will enter the critical section (progress) after at most one entry by Pj
(bounded waiting).

SYNCHRONIZATION HARDWARE
 The solution to the critical-section problem requires a simple tool-a lock.
 Race conditions are prevented by requiring that critical regions be protected by locks.
That is, a process must acquire a lock before entering a critical section and it releases the
lock when it exits the critical section

do {
acquire lock
critical section
release lock
remainder section
} while (TRUE);

Solution to the critical-section problem using locks.

 The critical-section problem could be solved simply in a uniprocessor environment if
interrupts are prevented from occurring while a shared variable was being modified. In
this manner, the current sequence of instructions would be allowed to execute in order
without preemption. No other instructions would be run, so no unexpected modifications

17 Dept. of CSE (AIML), MCE, Hassan

 Operating Systems 22AI303

could be made to the shared variable.

 But this solution is not as feasible in a multiprocessor environment. Disabling interrupts
on a multiprocessor can be time consuming, as the message is passed to all the
processors. This message passing delays entry into each critical section, and system
efficiency decreases.

test and set( ) and swap( ) instructions

 Many modern computer systems provide special hardware instructions that allow to
test and modify the content of a word or to swap the contents of two words
atomically, that is, as one uninterruptible unit.
 Special instructions such as test_and_set () and swap() instructions are used to solve
the critical-section problem.
 The test_and_set () instruction can be defined as shown in Figure. The important
characteristic of this instruction is that it is executed atomically.

Definition:

boolean test_and_set(boolean *target)

{

boolean rv = *target;
*target = true;
return rv;
}

The definition of the test_and_set () instruction.

 Thus, if two TestAndSet () instructions are executed simultaneously, they will be
executed sequentially in some arbitrary order. If the machine supports the TestAndSet ()
instruction, then implementation of mutual exclusion can be done by declaring a Boolean
variable lock, initialized to false.

18 Dept. of CSE (AIML), MCE, Hassan

 Operating Systems 22AI303

do {
while ( test_and_set (&lock ))
; // do nothing
// critical section
lock =false;
// remainder section
} while (true);

Mutual-exclusion implementation with test_and_Set ()

 The Swap() instruction, operates on the contents of two words, it is defined as shown
below

Definition:
voidSwap (boolean *a, boolean *b)
{

boolean temp = *a;

*a = *b;
*b = temp:
}
The definition of the Swap( ) instruction
 Swap() it is executed atomically. If the machine supports the Swap() instruction,
then mutual exclusion can be provided as follows.
 A global Boolean variable lock is declared and is initialized to false. In addition,
each process has a local Boolean variable key. The structure of process Pi is shown in
below.

do {
key = TRUE;
while ( key == TRUE)
Swap (&lock, &key );

// critical section
lock =FALSE;
// remainder section
} while (TRUE);

Mutual-exclusion implementation with the Swap() instruction

19 Dept. of CSE (AIML), MCE, Hassan

 Operating Systems 22AI303

 These algorithms satisfy the mutual-exclusion requirement, they do not satisfy the
bounded- waiting requirement.
 Below algorithm using the test_and_set () instruction that satisfies all the critical-
section requirements. The common data structures are
boolean waiting[n];
boolean lock;

These data structures are initialized to false.

do {
waiting[i] = true;
key = true;
while (waiting[i] && key)
key = test_and_set(&lock);
waiting[i] = false;

// critical section
j= (i + 1) % n;
while ((j != i) && !waiting[j])
j=(j + 1) % n;
if (j == i)
lock = false;
else
waiting[j] = false;
// remainder section
} while (true);

Bounded-waiting mutual exclusion with test_and_set ()

1) To prove the mutual exclusion requirement

 Note that process Pi can enter its critical section only if either waiting [i] == false or
key==false.
 The value of key can become false only if the test_and_set( ) is executed.
 The first process to execute the test_and_set( ) will find key== false; all others must wait.
 The variable waiting[i] can become false only if another process leaves its critical
section; only one waiting[i] is set to false, maintaining the mutual-exclusion requirement.

20 Dept. of CSE (AIML), MCE, Hassan

 Operating Systems 22AI303

2) To prove the progress requirement

Note that, the arguments presented for mutual exclusion also apply here, since a process
exiting the critical section either sets lock to false or sets waiting[j] to false. Both allow a
process that is waiting to enter its critical section to proceed.

3) To prove the bounded-waiting requirement

 Note that, when a process leaves its critical section, it scans the array waiting in the
cyclic ordering (i + 1, i + 2, ... , n 1, 0, ... , i 1).
 It designates the first process in this ordering that is in the entry section
(waiting[j]==true) as the next one to enter the critical section. Any process waiting to
enter its critical section will thus do so within n - 1 turns.

SEMAPHORE
 A semaphore is a synchronization tool is used solve various synchronization problem and
can be implemented efficiently.
 Semaphores do not require busy waiting.
 A semaphore S is an integer variable that is accessed only through two standard atomic
operations: wait () and signal (). The wait () operation was originally termed P and
signal() was called V.

Definition of wait ():

wait (S) {
while S <= 0
; // busy wait
S--;
}

Definition of signal ():

signal (S) {
S++;}

21 Dept. of CSE (AIML), MCE, Hassan

 Operating Systems 22AI303

 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.

Binary semaphore
 The value of a binary semaphore can range only between 0 and 1.
 Binary semaphores are known as mutex locks, as they are locks that provide mutual
exclusion. 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 below figure

do {
wait (mutex);
// Critical Section signal
(mutex);
// remainder section
} while (TRUE);

Mutual-exclusion implementation with semaphores

Counting semaphore
 The value of a counting semaphore can range over an unrestricted domain.
 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. When a process
releases a resource, it performs a signal() operation.
 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 requires busy waiting.
 While a process is in its critical section, any other process that tries to enter its

22 Dept. of CSE (AIML), MCE, Hassan

 Operating Systems 22AI303

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 a spinlock because the process
"spins" while waiting for the lock.

Semaphore implementation with no busy waiting

 The definition of the wait() and signal() semaphore operations is modified.
 When a process executes the wait () operation and finds that the semaphore value is not
positive, it must wait.
 However, rather than engaging in busy waiting, the process can block itself. The block
operation places a process into a waiting queue associated with the semaphore, and the
state of the process is switched to the waiting state. Then control is transferred to the CPU
scheduler, which selects another process to execute.
 A process that is blocked, waiting on a semaphore S, should be restarted when some other
process executes a signal() operation. The process is restarted by a wakeup( ) operation,
which changes the process from the waiting state to the ready state. The process is then
placed in the ready queue.
 To implement semaphores under this definition, we define a semaphore as a "C' struct:

typedef struct {
int value;
struct process *list;
} semaphore;

 Each semaphore has an integer value and a list of processes list. When a process must
wait on a semaphore, it is added to the list of processes. A signal() operation removes one
process from the list of waiting processes and awakens that process.
 The wait() semaphore operation can now be defined as:

23 Dept. of CSE (AIML), MCE, Hassan

 Operating Systems 22AI303

wait(semaphore *S) {
S->value--;
if (S->value < 0) {
add this process to S->list;
block();
}}

 The signal () semaphore operation can now be defined as:

signal(semaphore
*S) {
S->value++;
if (S->value <= 0) {
remove a process P from
S->list;
wakeup(P);
}

 The block() operation suspends the process that invokes it. The wakeup(P) operation
resumes the execution of a blocked process P. These two operations are provided by the
operating system as basic system calls.
 In this implementation semaphore values may be negative. If a semaphore value is
negative, its magnitude is the number of processes waiting on that semaphore.

Deadlocks and Starvation

 The implementation of a semaphore with a waiting queue may result in a situation where
two or more processes are waiting indefinitely for an event that can be caused only by
one of the waiting processes. The event in question is the execution of a signal( )
operation. When such a state is reached, these processes are said to be deadlocked.
 To illustrate this, consider a system consisting of two processes, Po and P1, each
accessing two semaphores, S and Q, set to the value 1.

24 Dept. of CSE (AIML), MCE, Hassan

 Operating Systems 22AI303

Po P1

wait(S); wait(Q);
wait(Q); wait(S);
..

..

signal(S); signal(Q);
signal(Q); signal(S);

 Suppose that Po executes wait (S) and then P1 executes wait (Q). When Po executes wait
(Q), it must wait until P1 executes signal (Q). Similarly, when P1 executes wait (S), it
must wait until Po executes signal(S). Since these signal() operations cam1ot be
executed, Po and P1 are deadlocked.
 Another problem related to deadlocks is indefinite blocking or starvation: A
situation in which processes wait indefinitely within the semaphore.
 Indefinite blocking may occur if we remove processes from the list associated with a
semaphore in LIFO (last-in, first-out) order.

CLASSICAL PROBLEMS OF SYNCHRONIZATION

 Bounded-Buffer Problem
 Readers and Writers Problem
 Dining-Philosophers Problem

1) Bounded-Buffer Problem
 N buffers, each can hold one item
 Semaphore mutex initialized to the value 1
 Semaphore full initialized to the value 0
 Semaphore empty initialized to the value N.

25 Dept. of CSE (AIML), MCE, Hassan

 Operating Systems 22AI303

The structure of the producer process

The structure of the consumer process

2) Readers-Writers Problem
 A data set is shared among a number of concurrent processes
 Readers – only read the data set; they do not perform any updates
 Writers – can both read and write.
 Problem – allow multiple readers to read at the same time. Only one single writer
can access the shared data at the same time.
 Shared Data
 Dataset
 Semaphore mutex initialized to 1.
 Semaphore wrt initialized to1.
 Integer readcount initialized to 0.

26 Dept. of CSE (AIML), MCE, Hassan

 Operating Systems 22AI303

The structure of a writer process

The structure of a reader process

3) 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.

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. When a hungry philosopher has both her chopsticks at the same

27 Dept. of CSE (AIML), MCE, Hassan

 Operating Systems 22AI303

time, she eats without releasing the chopsticks. When she is finished eating, she puts down both
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.
Solution: 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 is
shown

Several possible remedies to the deadlock problem are replaced by:

 Allow at most four philosophers to be sitting simultaneously at the table.
 Allow a philosopher to pickup her chopsticks only if both chopsticks are available.
 Use an asymmetric solution—that is, an odd-numbered philosopher picks up first her left
chopstick and then her right chopstick, whereas an even numbered philosopher picks up
her right chopstick and then her left chopstick.

Problems with Semaphores

Correct use of semaphore operations:
 signal (mutex) …. wait (mutex) : Replace signal with wait and vice-versa
 wait (mutex) … wait(mutex)
 Omitting of wait (mutex) or signal (mutex) (or both)

28 Dept. of CSE (AIML), MCE, Hassan

 Operating Systems 22AI303

Monitor
 An abstract data type—or ADT—encapsulates data with a set of functions to operate on
that data that are independent of any specific implementation of the ADT.
 A monitor type is an ADT that includes a set of programmer defined operations that are
provided with mutual exclusion within the monitor. The monitor type also declares the
variables whose values define the state of an instance of that type, along with the bodies
of functions that operate on those variables.
 The monitor construct ensures that only one process at a time is active within the monitor.

 To have a powerful Synchronization schemes a condition construct is added to the

Monitor. So synchronization scheme can be defined with one or more variables of type
condition Two operations on a condition variable:
Condition x, y
 The only operations that can be invoked on a condition variable are wait() and signal().
The operation
[Link] () – a process that invokes the operation is suspended.
[Link] () – resumes one of processes (if any) that invoked [Link] ()

29 Dept. of CSE (AIML), MCE, Hassan

 Operating Systems 22AI303

Monitor with Condition Variables

Solution to Dining Philosophers

 Each philosopher I invokes the operations pickup() and putdown() in the following

30 Dept. of CSE (AIML), MCE, Hassan

 Operating Systems 22AI303

 For each monitor, a semaphore mutex (initialized to 1) is provided. A process must

execute wait(mutex) before entering the monitor and must execute signal(mutex) after
leaving the monitor.
 Since a signaling process must wait until the resumed process either leaves or waits, an
additional semaphore, next, is introduced, initialized to 0. The signaling processes can
use next to suspend themselves. An integer variable next_count is also provided to count
the number of processes suspended on next. Thus, each external function F is replaced by

 For each condition x, we introduce a semaphore x sem and an integer variable x count,
both initialized to 0. The operation [Link]() can now be implemented as

 The operation [Link]() can be implemented as

Resuming Processes within a Monitor

If several processes are suspended on condition x, and an [Link]() operation is executed by
some process, then to determine which of the suspended processes should be resumed next, one
simple solution is to use a first-come, first-served (FCFS) ordering, so that the process that
has been waiting the longest is resumed first. For this purpose, the conditional-wait construct

31 Dept. of CSE (AIML), MCE, Hassan

 Operating Systems 22AI303

can be used. This construct has the form

[Link](c);
where c is an integer expression that is evaluated when the wait() operation is executed. The
value of c, which is called a priority number, is then stored with the name of the process that is
suspended. When [Link]() is executed, the process with the smallest priority number is
resumed next.

 The Resource Allocator monitor shown in the above Figure, which controls the
allocation of a single resource among competing processes.
 A process that needs to access the resource in question must observe the
following sequence:
[Link](t);
..…
access the resource;
…..
[Link]();
where, R is an instance of type Resource Allocator.

32 Dept. of CSE (AIML), MCE, Hassan

 Operating Systems 22AI303

 The monitor concept cannot guarantee that the preceding access sequence will
be observed. In particular, the following problems can occur:
 A process might access a resource without first gaining access permission to
the resource.
 A process might never release a resource once it has been granted access to
the resource.
 A process might attempt to release a resource that it never requested.
 A process might request the same resource twice (without first releasing the resource).

33 Dept. of CSE (AIML), MCE, Hassan