UNIT-III
Process Synchronization
1.The critical-section problem
When two or more process cooperates with each other, their order of execution must be
preserved otherwise there can be conflicts in their execution and inappropriate outputs can be
produced.
A cooperative process is the one which can affect the execution of other process or
can be affected by the execution of other process. Such processes need to be
synchronized so that their order of execution can be guaranteed.
The procedure involved in preserving the appropriate order of execution of
cooperative processes is known as Process Synchronization. There are various
synchronization mechanisms that are used to synchronize the processes.
Race Condition
A Race Condition typically occurs when two or more threads try to read, write and
possibly make the decisions based on the memory that they are accessing concurrently.
The code for the producer process can be modified as follows:
while (true) { /* produce an item in next produced */
while (counter == BUFFER SIZE)
; /* do nothing */
buffer[in] = next produced;
in = (in + 1) % BUFFER SIZE;
counter++;
}
The code for the consumer process can be modified as follows:
while (true) { while (counter == 0)
; /* do nothing */
next consumed = buffer[out];
out = (out + 1) % BUFFER SIZE;
counter--;
/* consume the item in next consumed */
}
, We can show that the value of counter may be incorrect as follows. Note that the
statement “counter++” may be implemented in machine language (on a typical
machine) as follows:
register1 = counter
register1 = register1 + 1
counter = register1
where register1 is one of the local CPU registers. Similarly, the statement
“counter--” is implemented as follows:
register2 = counter
register2 = register2 − 1
counter = register2
The concurrent execution of “counter++” and “counter--” is equivalent to a sequential
execution in which the lower-level statements presented previously are interleaved in
some arbitrary order
T0: producer execute register1 = counter {register1 = 5}
T1: producer execute register1 = register1 + 1 {register1 = 6}
T2: consumer execute register2 = counter {register2 = 5}
T3: consumer execute register2 = register2 − 1 {register2 = 4}
T4: producer execute counter = register1 {counter = 6}
T5: consumer execute counter = register2 {counter = 4}
notice that we have arrived at the incorrect state “Counter == 4”
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.
The regions of a program that try to access shared resources and may cause race
conditions are called critical section. To avoid race condition among the processes, we
need to assure that only one process at a time can execute within the critical section.
The critical section is the portion of a process or thread's code where shared
resources (such as data, memory, or devices) are accessed.
The Critical-Section Problem
We begin our consideration of process synchronization by discussing the so called
critical-section problem. Consider a system consisting of n processes {P0, 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 so
on.
, 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.
A solution to the critical section problem must satisfy the following three conditions:
1. Mutual Exclusion Out of a group of cooperating processes, only one process can
be in its critical section at a given point of time.
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 After a process makes a request for getting into its critical
section, there is a limit for how many other processes can get into their critical
section, before this process's request is granted. So after the limit is reached, the
system must grant the process permission to get into its critical section.
2.Peterson's Solution
With the help of this solution whenever a process is executing in any critical state,
then the other process only executes the rest of the code, and vice-versa can happen.
This method also helps to make sure of the thing that only a single process can run in
the critical section at a specific time. This solution preserves all three conditions:
Mutual Exclusion is comforted as at any time only one process can access the
critical section.
Progress is also comforted, as a process that is outside the critical section is unable
to block other processes from entering into the critical section.
, Bounded Waiting is assured as every process gets a fair chance to enter the Critical
section.
Key Variables:
1. flag[i]: A boolean array, where flag[i] = true indicates that process P_i wants to enter
the critical section.
2. turn: A variable to indicate whose turn it is to enter the critical section. It allows the
two processes to coordinate access.
Steps in the Code:
1. Entry Section (Before Entering Critical Section):
o The process sets flag[i] = true to indicate that it wants to enter the critical
section.
o It then sets turn = j, allowing the other process (P_j) to have the first
opportunity to enter the critical section.
o The while loop (while (flag[j] && turn == j);) makes the process wait if:
flag[j] is true, meaning the other process P_j also wants to enter the
critical section.
turn == j, meaning it's the other process's turn.
o Only when P_j is either not interested (i.e., flag[j] = false) or has given up its
turn (turn != j), will P_i proceed to enter the critical section.
1. Critical Section:
o This is where the process performs its tasks that must not be interrupted or
accessed concurrently by the other process.
2. Exit Section (After Leaving Critical Section):
Process Synchronization
1.The critical-section problem
When two or more process cooperates with each other, their order of execution must be
preserved otherwise there can be conflicts in their execution and inappropriate outputs can be
produced.
A cooperative process is the one which can affect the execution of other process or
can be affected by the execution of other process. Such processes need to be
synchronized so that their order of execution can be guaranteed.
The procedure involved in preserving the appropriate order of execution of
cooperative processes is known as Process Synchronization. There are various
synchronization mechanisms that are used to synchronize the processes.
Race Condition
A Race Condition typically occurs when two or more threads try to read, write and
possibly make the decisions based on the memory that they are accessing concurrently.
The code for the producer process can be modified as follows:
while (true) { /* produce an item in next produced */
while (counter == BUFFER SIZE)
; /* do nothing */
buffer[in] = next produced;
in = (in + 1) % BUFFER SIZE;
counter++;
}
The code for the consumer process can be modified as follows:
while (true) { while (counter == 0)
; /* do nothing */
next consumed = buffer[out];
out = (out + 1) % BUFFER SIZE;
counter--;
/* consume the item in next consumed */
}
, We can show that the value of counter may be incorrect as follows. Note that the
statement “counter++” may be implemented in machine language (on a typical
machine) as follows:
register1 = counter
register1 = register1 + 1
counter = register1
where register1 is one of the local CPU registers. Similarly, the statement
“counter--” is implemented as follows:
register2 = counter
register2 = register2 − 1
counter = register2
The concurrent execution of “counter++” and “counter--” is equivalent to a sequential
execution in which the lower-level statements presented previously are interleaved in
some arbitrary order
T0: producer execute register1 = counter {register1 = 5}
T1: producer execute register1 = register1 + 1 {register1 = 6}
T2: consumer execute register2 = counter {register2 = 5}
T3: consumer execute register2 = register2 − 1 {register2 = 4}
T4: producer execute counter = register1 {counter = 6}
T5: consumer execute counter = register2 {counter = 4}
notice that we have arrived at the incorrect state “Counter == 4”
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.
The regions of a program that try to access shared resources and may cause race
conditions are called critical section. To avoid race condition among the processes, we
need to assure that only one process at a time can execute within the critical section.
The critical section is the portion of a process or thread's code where shared
resources (such as data, memory, or devices) are accessed.
The Critical-Section Problem
We begin our consideration of process synchronization by discussing the so called
critical-section problem. Consider a system consisting of n processes {P0, 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 so
on.
, 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.
A solution to the critical section problem must satisfy the following three conditions:
1. Mutual Exclusion Out of a group of cooperating processes, only one process can
be in its critical section at a given point of time.
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 After a process makes a request for getting into its critical
section, there is a limit for how many other processes can get into their critical
section, before this process's request is granted. So after the limit is reached, the
system must grant the process permission to get into its critical section.
2.Peterson's Solution
With the help of this solution whenever a process is executing in any critical state,
then the other process only executes the rest of the code, and vice-versa can happen.
This method also helps to make sure of the thing that only a single process can run in
the critical section at a specific time. This solution preserves all three conditions:
Mutual Exclusion is comforted as at any time only one process can access the
critical section.
Progress is also comforted, as a process that is outside the critical section is unable
to block other processes from entering into the critical section.
, Bounded Waiting is assured as every process gets a fair chance to enter the Critical
section.
Key Variables:
1. flag[i]: A boolean array, where flag[i] = true indicates that process P_i wants to enter
the critical section.
2. turn: A variable to indicate whose turn it is to enter the critical section. It allows the
two processes to coordinate access.
Steps in the Code:
1. Entry Section (Before Entering Critical Section):
o The process sets flag[i] = true to indicate that it wants to enter the critical
section.
o It then sets turn = j, allowing the other process (P_j) to have the first
opportunity to enter the critical section.
o The while loop (while (flag[j] && turn == j);) makes the process wait if:
flag[j] is true, meaning the other process P_j also wants to enter the
critical section.
turn == j, meaning it's the other process's turn.
o Only when P_j is either not interested (i.e., flag[j] = false) or has given up its
turn (turn != j), will P_i proceed to enter the critical section.
1. Critical Section:
o This is where the process performs its tasks that must not be interrupted or
accessed concurrently by the other process.
2. Exit Section (After Leaving Critical Section):
