PROCESS
SYNCHRONIZATION
PETERSONS SOLUTION FOR CRITICAL SECTION
• In 1981, G. L. Peterson discovered a much simpler way to achieve mutual
Exclusion.
• Peterson's solution is a classic software-based solution to the critical section
problem.
• The critical section problem ensures that no two processes change or modify a
resource's value simultaneously.
• May not work correctly on modern computer architecture.
• Provides algorithmic description of solving critical-section problem and
illustrates some of the complexities involved in designing software and
addresses requirements of mutual exclusion,progress and bounded waiting.
• Peterson’s solution is restricted to two processes that alternate execution
between critical sections and remainder sections.
• Let's call the process Pi and Pj.
REQUIREMENTS
• int turn Boolean flag [2]
Indicates if a process is ready
Indicates whose turn it is to to enter its critical section
enter its critical section
The structure of process Pi in Peterson solution The structure of process Pj in Peterson solution
do {
do {
flag[j] =true;
flag[i] =true;
turn=i
turn=j;
while(flag[i]&&turn==[i]);
while(flag[j]&&turn==[j]);
Critical Section
Critical Section
flag[j] = false;
flag[i] = false;
Remainder Section
Remainder Section
}while(True);
}while(True);
• 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
block other processes from entering the critical section.
• Bounded Waiting is preserved as every process gets a fair chance.
• Disadvantages of Peterson’s solution:
• It involves busy waiting.(In the Peterson’s solution, the code statement-
“while(flag[j] && turn == j);” is responsible for this. Busy waiting is not
favored because it wastes CPU cycles that could be used to perform
other tasks.)
• It is limited to 2 processes.
• Peterson’s solution cannot be used in modern CPU architectures.
Lock Variables Approach to Critical Section
• Consider having a single, shared (lock) variable, initially 0.
• When a process wants to enter its critical region, it first tests the lock.
• If the lock is 0, the process sets it to 1 and enters the critical region.
• If the lock is already 1, the process just waits until it becomes 0.
• Thus, a 0 means that no process is in its critical region, and a 1 means that
some process is in its critical region.
• Suppose that one process reads the lock and sees that it is 0. Before it can set
the lock to 1, another process is scheduled, runs, and sets the lock to 1.
• When the first process runs again, it will also set the lock to 1, and two
processes will be in their critical regions at the same time.
SYNCHRONIZATION HARDWARE
• The hardware support for critical section are provided in many systems.
• Uniprocessor Systems:
• If we could prevent interrupts from occurring while a shared variable was being modified.
• The critical-section problem could be solved simply in a uniprocessor environment.
• In this manner, we would be assuring that the current sequence of instructions would be allowed to
execute in order without preemption
• No other instructions would be run, so no unexpected modifications could be made to the shared
variable.
• Multiprocessor Systems:
• System efficiency decreases when this massage passing delays entry into each critical section.
• Also the effect on a system’s clock is considered if the clock is kept updated by interrupts.
• So many modern computer systems therefore provide special hardware instructions that allow us that we
can test and modify the content of a word or to swap the contents of two words atomically—that is, as
one uninterruptible unit.
• Atomic h/w instructions : Test and set()
• Swap()
• The three Hardware lock algorithm
• Test and set
• Swap and unlock
• Lock algorithm
• Test and Set
• Test and set algorithm uses a boolean variable 'lock' which is initially
initialized to false.
• This lock variable determines the entry of the process inside the
critical section of the code.
boolean lock = false;
boolean TestAndSet(boolean &target){
boolean returnValue = target;
target = true;
return returnValue;
} Process P2
Process P1 do {
do { while(TestAndSet(lock));
while(TestAndSet(lock)); //do nothing
//do nothing //CRITICAL SECTION
//CRITICAL SECTION CODE; CODE;
lock = false; lock = false;
// REMAINDER SECTION CODE; // REMAINDER SECTION
CODE;
}
}
Explanation
• In the above algorithm the TestAndSet() function takes a boolean value and returns
the same value. TestAndSet() function sets the lock variable to true.
• When lock varibale is initially false the TestAndSet(lock) condition checks for
TestAndSet(false).
• As TestAndSet function returns the same value as its argument, TestAndSet(false)
returns false.
• Now, while loop while(TestAndSet(lock)) breaks and the process enters the critical
section.
• As one process is inside the critical section and lock value is now 'true', if any other
process tries to enter the critical section then the new process checks for
while(TestAndSet(true)) which will return true inside while loop and as a result the
other process keeps executing the while loop.
• Satisfies mutual exclusion.
• Does not satisfy bounded waiting.
• Swap
• Swap function uses two boolean variables lock and key. Both lock and
key variables are initially initialized to false.
• Swap algorithm is the same as lock and set algorithm.
• The Swap algorithm uses a temporary variable to set the lock to true
when a process enters the critical section of the program.
boolean lock = false; • The value of lock and key when P1 enters the critical section
individual key = false; is lock = true and key = false.
• First process will be executed, and in while(key), since
void swap(boolean *a, boolean *b){ key=true , swap will take place and hence lock=true and
boolean temp = *a; key=false.
*a = *b; • Again next iteration takes place while(key) but key=false ,
*b = temp; so while loop breaks and first process will enter in critical
} section.
do{ • .Now another process will try to enter in Critical section, so
key=true; again key=true and hence while(key) loop will run and swap
while(key==true){ takes place so, lock=true and key=true (since lock=true in
swap(&lock,&key); first process).
} • Again on next iteration while(key) is true so this will keep
on executing and another process will not be able to enter in
CRITICAL SECTION CODE critical section.
lock = false; • Therefore Mutual exclusion is ensured. Again, out of the
REMAINDER SECTION CODE critical section, lock is changed to false, so any process
} finding it gets enter the critical section.
• Progress is ensured. However, again bounded waiting is not
ensured for the very same reason.
Unlock and Lock
• Unlock and Lock Algorithm uses TestAndSet to regulate the value of lock but it
adds another value, waiting[i], for each process which checks whether or not a
process has been waiting.
• A ready queue is maintained with respect to the process in the critical section.
• All the processes coming in next are added to the ready queue with respect to their
process number, not necessarily sequentially.
• Once the ith process gets out of the critical section, it does not turn lock to false
so that any process can avail the critical section now, which was the problem with
the previous algorithms.
boolean lock = false; while(1){
Individual key = false; waiting[i] = true;
Individual waiting[i]; key = true;
while(waiting[i] && key){
boolean TestAndSet(boolean &target) key = TestAndSet(lock);
{ }
boolean returnValue = target; CRITICAL SECTION CODE
target = true; j = (i+1) % n;
return returnValue; while(j != i && !waiting[j])
} j = (j+1) % n;
if(j == i)
lock = false;
else
waiting[j] = false;
REMAINDER SECTION CODE
}
explanation
• In Unlock and lock algorithm the lock is not set to false as one process comes out of the critical section.
In other algorithms like swap and Test and set the lock was being set to false as the process comes out of
the critical section so that any other process can enter the critical section.
• But in Unlock and lock, once the ith process comes out of the critical section the algorithm checks the
waiting queue for the next process waiting to enter the critical section i.e jth process. If there is a jth
process waiting in the ready queue to enter the critical section, the waiting[j] of the jth process is set to
false so that the while loop while(waiting[i] && key) becomes false and the jth process enters the critical
section.
• If no process is waiting in the ready queue to enter the critical section the algorithm then sets the lock to
false so that any other process comes and enters the critical section easily.
• Since a ready queue is always maintained for the waiting processes, the Unlock and lock algorithm
ensures bounded waiting.
Strict Alternation Approach to Critical Section
• The integer variable turn, initially 0, keeps track of whose turn it is to enter the critical
region and examine or update the shared memory.
• Initially, process 0 inspects turn, finds it to be 0, and enters its critical region.
• Process 1 also finds it to be 0 and therefore sits in a tight loop continually testing turn
to see when it becomes 1.
• Continuously testing a variable until some value appears is called busy waiting. It
should usually be avoided, since it wastes CPU time.
• Only when there is a reasonable expectation that the wait will be short is busy waiting
used.
• A lock that uses busy waiting is called a spin lock.