MODULE-II
Process Synchronization
Concurrent access to shared data may result in data inconsistency
Maintaining data consistency requires mechanisms to ensure the orderly
execution of cooperating processes
Suppose that we wanted to provide a solution to the consumer-producer problem
that fills all the buffers. We can do so by having an integer count that keeps track
of the number of full buffers. Initially, count is set to 0. It is incremented by the
producer after it produces a new buffer and is decremented by the consumer
after it consumes a buffer.
Pseudocode for Producer Process Pseudocode for Consumer Process
while (true) { while (true) {
/* produce an item and put in while (count == 0)
nextProduced */
; // do nothing
while (count == BUFFER_SIZE)
nextConsumed = buffer[out];
; // do nothing
out = (out + 1) %
buffer [in] = nextProduced; BUFFER_SIZE;
in = (in + 1) % BUFFER_SIZE; count--;
count++; /* consume the item in
Race Condition nextConsumed
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.
count++ could be implemented as
register1 = count
, register1 = register1 + 1
count = register1
count-- could be implemented as
register2 = count
register2 = register2 - 1
count = register2
Consider this execution interleaving with “count = 5” initially:
S0: producer execute register1 = count {register1 = 5}
S1: producer execute register1 = register1 + 1 {register1 = 6}
S2: consumer execute register2 = count {register2 = 5}
S3: consumer execute register2 = register2 - 1 {register2 = 4}
S4: producer execute count = register1 {count = 6 }
S5: consumer execute count = register2 {count = 4}
Critical Section Problem
A section of code, common to n cooperating processes, in which the processes may be
accessing common variables.
A Critical Section Environment contains:
Entry Section Code requesting entry into the critical section.
Critical Section Code in which only one process can execute at any one time.
Exit Section The end of the critical section, releasing or allowing others in.
Remainder Section Rest of the code AFTER the critical se
,
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 important feature of the system is that, when one process is executing in its
critical section, no other process is 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.
Solution to Critical Section Problem
Mutual Exclusion - If process Pi is executing in its critical section, then no other
processes can be executing in their critical sections
Progress - If no process is executing in its critical section and there exist some
processes that wish to enter their critical section, then the selection of the
processes that will enter the critical section next cannot be postponed indefinitely
Bounded Waiting - A bound must exist 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
Assume that each process executes at a nonzero speed
No assumption concerning relative speed of the N processes
, Peterson’s Solution
Two process solution
Assume that the LOAD and STORE instructions are atomic; that is, cannot be
interrupted.
The two processes share two variables:
int turn;
Boolean flag[2]
The variable turn indicates whose turn it is to enter the critical section.
The flag array is used to indicate if a process is ready to enter the critical section.
flag[i] = true implies that process Pi is ready!
Hardware Synchronization
Many systems provide hardware support for critical section code
Uniprocessors – could disable interrupts
Currently running code would execute without preemption
Generally too inefficient on multiprocessor systems
Operating systems using this not broadly scalable
Modern machines provide special atomic hardware instructions
Atomic = non-interruptable
Process Synchronization
Concurrent access to shared data may result in data inconsistency
Maintaining data consistency requires mechanisms to ensure the orderly
execution of cooperating processes
Suppose that we wanted to provide a solution to the consumer-producer problem
that fills all the buffers. We can do so by having an integer count that keeps track
of the number of full buffers. Initially, count is set to 0. It is incremented by the
producer after it produces a new buffer and is decremented by the consumer
after it consumes a buffer.
Pseudocode for Producer Process Pseudocode for Consumer Process
while (true) { while (true) {
/* produce an item and put in while (count == 0)
nextProduced */
; // do nothing
while (count == BUFFER_SIZE)
nextConsumed = buffer[out];
; // do nothing
out = (out + 1) %
buffer [in] = nextProduced; BUFFER_SIZE;
in = (in + 1) % BUFFER_SIZE; count--;
count++; /* consume the item in
Race Condition nextConsumed
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.
count++ could be implemented as
register1 = count
, register1 = register1 + 1
count = register1
count-- could be implemented as
register2 = count
register2 = register2 - 1
count = register2
Consider this execution interleaving with “count = 5” initially:
S0: producer execute register1 = count {register1 = 5}
S1: producer execute register1 = register1 + 1 {register1 = 6}
S2: consumer execute register2 = count {register2 = 5}
S3: consumer execute register2 = register2 - 1 {register2 = 4}
S4: producer execute count = register1 {count = 6 }
S5: consumer execute count = register2 {count = 4}
Critical Section Problem
A section of code, common to n cooperating processes, in which the processes may be
accessing common variables.
A Critical Section Environment contains:
Entry Section Code requesting entry into the critical section.
Critical Section Code in which only one process can execute at any one time.
Exit Section The end of the critical section, releasing or allowing others in.
Remainder Section Rest of the code AFTER the critical se
,
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 important feature of the system is that, when one process is executing in its
critical section, no other process is 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.
Solution to Critical Section Problem
Mutual Exclusion - If process Pi is executing in its critical section, then no other
processes can be executing in their critical sections
Progress - If no process is executing in its critical section and there exist some
processes that wish to enter their critical section, then the selection of the
processes that will enter the critical section next cannot be postponed indefinitely
Bounded Waiting - A bound must exist 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
Assume that each process executes at a nonzero speed
No assumption concerning relative speed of the N processes
, Peterson’s Solution
Two process solution
Assume that the LOAD and STORE instructions are atomic; that is, cannot be
interrupted.
The two processes share two variables:
int turn;
Boolean flag[2]
The variable turn indicates whose turn it is to enter the critical section.
The flag array is used to indicate if a process is ready to enter the critical section.
flag[i] = true implies that process Pi is ready!
Hardware Synchronization
Many systems provide hardware support for critical section code
Uniprocessors – could disable interrupts
Currently running code would execute without preemption
Generally too inefficient on multiprocessor systems
Operating systems using this not broadly scalable
Modern machines provide special atomic hardware instructions
Atomic = non-interruptable
