Process Synchronization
Process Synchronization
• Process Synchronization is the coordination of execution of
multiple processes in a multi-process system to ensure that
they access shared resources in a controlled and predictable
manner.
• It aims to resolve the problem of race conditions and other
synchronization issues in a concurrent system.
Process Synchronization
• The main objective of process synchronization is to ensure that
multiple processes access shared resources without interfering
with each other and to prevent the possibility of inconsistent
data due to concurrent access.
Process Synchronization
• Best technique to implement synchronization is to block a
process until an appropriate condition is fulfilled.
• Two kind of Synchronization
– Control Synchronization
• A process performs an action only when some other processes reach specific
points in their execution.
– Data Access Synchronization
• Race conditions should not arise when concurrent processes access shared
data.
Critical Section Problem
• Each process has a segment of code is called as Critical
Section.
• Process may be changing common variables, updating a table,
writing a file and so on.
• The critical section is a sequence of instructions with a clearly
marked beginning and end.
• It safeguards updating of one or more shared variables.
Critical Section Problem
• When a process enters a critical section, it must complete all
instructions there in before any other process is allowed to enter
the same critical section.
• Only the process executing the critical section is allowed to
access the shared variable.
• It is often referred as Mutual Exclusion.
Critical Section Problem
• Solution to mutual exclusion problem
– When more than one process wishes to enter critical section, grant
entrance to one of them in finite time.
General Structure of a Typical Process pi
do
{
entry section
critical section
exit section
remainder section
}while(1);
Critical Section Problem
• Software Approach
– Concurrent processes executes on multiprocessor machine with shared memory.
• Processes
– When processes wish to enter their critical sections, then only those processes that
are not executing in their remainder section can participate by deciding which will
enter its critical section next. Selection can not be postponed indefinitely.
• Bound
– Number of times that processes are allowed to enter their critical sections
First Algorithm
• Constraints- only one process access to memory location at a time.
• Using this constraint reserve a global memory location labeled turn.
• A process (P0 or P1) wishing to execute its critical section
• First examines the content of turn label.
• If the value of turn is equal to the number of the process, then the process may proceed
to its critical section.
• Otherwise, it is forced to wait.
• Waiting process repeatedly reads the value of turn until it is allowed to enter its critical
section.
• This procedure is known as busy waiting because the thwarted process can do nothing
productive until it gets permission to enter its critical section.
• After a process has gained access to its critical section and after it has completed that
section, it must update the value of turn label.
int turn=0;
/*Process 0*/
while(turn!=0)
/*do nothing*/
/*Critical Section*/
turn=1;
while(turn!=1)
/*do nothing*/
/*Critical Section*/
turn=0;
• Disadvantage
– Speed of execution is dictated by the slower of the two processes.
– If one process fails, the other process is permanently blocked
Second Algorithm
• Problem with the first algorithm is that it stores the name of
the process that may enter its critical section, when in fact we
need state information about both processes.
• Each process should have its own key to the critical section so
that if one fails, the other can still access its critical section.
• To meet this requirement a Boolean vector flag is defined with
flag[0] corresponding to P0 and flag[1] corresponding to P1.
• Each process may examine the others flag but may not alter it.
• When a process wishes to enter its critical section it
periodically checks the other’s flag until if that flag has value
false, indicating that the other process is not in its critical
section.
• The process immediately sets its own flag to true and proceeds
to its critical section.
• When it leaves its critical section, it sets its flag to false.
• If a process fails inside its critical section or
after setting its flag to true just before
entering its critical section, then the other
process is permanently blocked.
• Consider following sequence
– P0 executes the while statement and finds flag[1]
set to false
– P1 executes the while statement and finds flag[0]
set to false
– P0 sets flag[0] to true and enter its critical section.
– P1 sets flag[1] to true and enter its critical section.
• Because both processes are now in their critical sections, the
second algorithm is incorrect.
/*Process 0*/
While(flag[1])
/*do nothing*/;
/*Critical Section*/
flag[0]=false;
/*Process 1*/
While(flag[0])
/*do nothing*/;
/*Critical Section*/
flag[1]=false;
Third Algorithm
• Because a process can change its state after the other
process has checked it but before the other process can
enter its critical section, the second algorithm failed.
• We can fix this problem with interchange of two
statements.
• Once P0 has set flag[0] to true, P1 cannot enter its critical
section until after P0 has entered and left its critical
section. So on.
• This guarantees mutual exclusion but creates yet another
problem.
• If both processes set their flags to true before either has
executed the while statement, then each will think that
the other has entered its critical section, causing
deadlock.
• Consider following sequence
– P0 sets flag[0] to true
– P1 sets flag[1] to true
– P0 checks flag[1]
– P1 checks flag[0]
– P0 sets flag[0] to false
– P1 sets flag[1] to false
– P0 sets flag[0] to true
– P1 sets flag[1] to true
This sequence could be extended indefinitely and
neither process could enter its critical section
/*Process 0*/
flag[0]=true;
While(flag[1])
/*do nothing*/;
/*Critical Section*/
flag[0]=false;
/*Process 1*/
flag[1]=true;
While(flag[0])
/*do nothing*/;
Semaphores
• Concept
• Implementation
• Deadlock and Starvation
• Binary Semaphores
Semaphore (Dijkstra)
• Synchronization tool that does not require busy waiting
• Semaphore S – is a shared and having positive integer variable
• Two standard operations modify S: acquire() and release()
– Originally called P() (Proberen) and V() (Verhogen)
– P(): An automic operation that waits for semaphore to become
positive then decrement it by 1
– V(): An automic operation that increments semaphore by 1 and
wakes up a waiting tread at P(), if any
• Can only be accessed via two indivisible (atomic) operations
• It is a protected variable and can be accessed and altered only
by the operations P & V
• It is guaranteed that once a semaphore operations has started,
no other process can access the semaphore until operation has
completed
Binary Semaphore
• Binary semaphore – integer value can
range only between 0 and 1
– Also known as mutex locks
P(): waits until value is not 1
Then set it to 0
V(): Sets the value to 1
- wakes up a thread waiting at P(), if any
• Logic
struct binary_semaphore
{
Enum (zero,one) value;
queueType queue;
};
void waitB(binary_semaphore S)
{
if([Link]==1)
[Link]=0
else
{
place this process in [Link];
block this process;
}
}
void signalB(binary_semaphore S)
{
if([Link] is_empty)
[Link]=1;
else
{
remove a process P from [Link];
Place process P on ready list;
}
}
Semaphore Implementation with no Busy waiting
• With each semaphore there is an
associated waiting queue and a value
(of type integer).
• Two operations:
– block – place the process invoking the
operation on the appropriate waiting
queue.
– wakeup – remove one of processes in the
waiting queue and place it in the ready
queue.
• Strong Semaphore
– The process that has been blocked the longest is released from the
queue first
• Weak Semaphore
– A semaphore that does not specify the order in which processes are
removed from the queue
Deadlock and Starvation
• Deadlock – two or more processes are waiting indefinitely for an event that can be caused by only
one of the waiting processes
• Let S and Q be two binary semaphores.
P0 P1
[Link](); [Link]();
[Link](); [Link]();
. .
. .
. .
[Link](); [Link]();
[Link](); [Link]();
• Starvation – indefinite blocking. A process may never be removed from the semaphore queue in
which it is suspended.
Void writer()
{
while(true)
{
wait(write);
/*write data*/
signal(write);
}
}
Void parentprocess()
{
Readercount=0;
Signal(mutex);
Signal(write);
Initiate readers,writers;
}
Critical Section
• A critical section for a data item d is a section of code which
cannot be executed concurrently with itself or with other
critical section(s) for d.
• A critical section is represented by a dashed rectangular box in
a program.
• Properties of Critical Section
– Correctness
• At most one process may execute a critical section at
any given moment
– Progress
• When critical section not in use, one of the processes
wishing to enter it will be granted entry to the critical
section
– Bounded Wait
• Entry for the process to the critical section is bounded
by a finite integer.
– Deadlock Freedom
• The implementation is free of deadlocks.
Classical Problems of synchronization
• Bounded buffer problem
• Readers and Writers Problem
• Dining-Philosophers problem
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.
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 writer can access the shared data at the same time.
Readers and Writers Problem
• A reader never modifies the shared data structure, whereas a writer may
both read it and write into it.
• A number of readers may use the shared data structure concurrently
because no matter how they are interleaved.
• Writers, on the other hand, must be granted exclusive access to data.
• The writer process waits on binary semaphore WRITE to grant it
permission to enter the critical section and to use the shared resources.
• A reader goes through two critical sections, one before and one after using the
resource.
• An integer READERCOUNT is used to keep track of the number of readers actively
using the resource.
• While reader is reading data, semaphore mutex is free.
• When readercount reaches to zero writers can enter in critical section, till then writter
is in waiting queue.
int readercount;
binary_semaphore mutex, write;
void reader()
{
while(true)
{
wait(mutex);
readercount++;
if(readercount==1)
wait(write);
signal(mutex);
/*read data*/
wait(mutex);
readercount--;
if(readercount==0)
signal(write);
}
}
Dining-Philosophers Problem (Dijkstra)
• Shared data
– Bowl of rice (data set)
– Semaphore chopStick [5] initialized to 1
Dining-Philosophers problem
• Consider 5 philosophers who spend their lives thinking and eating.
• Philosophers share a common circular table surrounded by 5 chairs, each belonging
to one philosopher.
• In the center of table is a bowl of rice, and the table is laid with 5 single chopsticks.
• When a philosopher thinks, he/she does not interact with his/her colleagues.
• From time to time a philosopher gets hungry and tries to pick the two chopsticks that
are closest to them.
• A philosopher may pick up only one chopstick at a time
• When a hungry philosopher has both his/her chopsticks at the same time , he/she eats
without releasing his/her chopstick.
• When he/she finished eating, she puts down both of his/her chopsticks and starts
thinking again.
• Simple solution is to represent each chopstick as a semaphore.
• Philosopher tries to grab the chopstick by executing a wait operation on that.
• They release their chopsticks by executing the signal operation on that appropriate
semaphore.
do{
wait(chopsticks[i]);
wait(chopsticks[i+1]%5);
----
eat
---
signal(chopsticks[i]);
signal(chopsticks[i+1]%5);
---
Think
}while(1);
• Solution guarantees that no two neighbors are eating
simultaneously
• When every philosopher is hungry, simultaneously each tries
to grab right chopstick and he/she will delayed forever
• So all has to pick chopstick if both are available