Process Synchronization

Essential criteria to solve critical section problem

1.Mutual exclusion takes care of race condition.
2.Progress means that no process shall be kept from entering its critical section by another process that is stopped outside its critical section i.e if process j blocks in the remainder section it should not affect the entry of i in the critical section.
3.Bound waiting condition guarantees no starvation.If solution provides strict alternation then bounded waiting is inherently satisfied.If access to critical region is arbitrary then starvation is possible.



Mutual exclusion with Hardware 

1. Disabling the interrupts will ensure mutual exclusion but is not practiced for user processes and it is possible only in uniprocessor system. Disabling interrupt would ensure all 3 condition

2. Hardware provides special instruction that allows modification of a word or swap of words atomically
Test and set lock

• atomic(non interruptible) instruction used to write to a memory location 
• returns old value.
• no other process may begin test and set unless first is complete.
• guarantees mutual exclusion and progress but is prone to starvation. 
• starvation possible because access to critical region is in arbitrary fashion.  

initially set lock = false;

boolean TSL (boolean &lock) {
 boolean tmp = lock;
 lock = True;
 return tmp;
}

process p0 code
while(TSL(lock));
CS
lock = false;

gets the present value of the lock and sets it to true
Conditions
1.At time t0 process  p0 checks the while condition, TSL(lock) return false as lock is false initially, and sets lock = true, so p0 enters critical section.
2.At time t1>t0 process p1 tries to enter the critical section on call to TSL(lock)  it return true and sets lock to true again, so p1 is not allowed to enter critical section unless p0 executes the lock= false condition in exit section.
3.At time t2>t1process p0 has executed the lock = false and TSL(lock) returns false and p1 enters CS.

Exchange instruction (swap)
swap instruction executes atomically 
initially lock=false
code for process p0
key=true
while(key) swap(lock,key)
cs
lock=false;

Disadvantages of hardware instructions busy waiting(wasting cpu resource) and starvation possible.

Mutual Exclusion with software
1. Using lock variable alone does not ensures mutual exclusion.

Fig. software lock solution

2. Turn variable only.

3. Peterson's Algorithm

Allows two process p0 and p1 to share a single resource without conflict

Fig. peterson solution

1. Mutual Exclusion condition requires us to prove that if both process are checking the last statement of beginning section, that is while loop, only one of the process would be able to enter the critical section.
 Since value of turn can be either 0 or 1, turn value is not changed in CS or in remaining section, if it is 0 process 0 will enter and p1 would still be waiting and similar for p1.

2. For Progress we need to check if process blocks in the remainder section it does not affect the entry of other process in its critical section. In peterson solution process j set the flag[j] = 0 before entering in to its remainder section.so if process j now blocks in its remainder section then also process i can proceed with its critical section unlike in dekker's solution where if process blocks in the remainder section no other process can proceed to critical section.

3. Bounded waiting we need to check if one of the process is waiting that is in the while loop then eventually it will break out of loop and enter critical section.

Problems
All this solution has problem of
1. Busy waiting wasting cpu resource, frequent testing and waiting in while loop.
2. priority inversion problem
consider process p0 has low priority than process p1 and when p0 is in its critical section p1 comes, scheduler assigns CPU to p1 as its high priority process now
p1 gets CPU but cannot proceed because p0 is already in critical section(mutual exclusion)  while
p0 now waits for CPU assigned to process p1
process p1 gets into waiting state, before cpu could be assigned to p0 another process p2 arrives with priority less than p1 but greater than p0 this process will get the cpu
after p2 finishes p0 get the cpu and executes until it exits the critical section then p1 will get cpu
giving us priority inversion, low priority  process running before high priority process.

//here goes wake and sleep and it sproblems

4. Semaphores
Semaphore solution includes a semaphore variable and two atomic operations P(s) and V(s) semaphore is integer number representing the number of available resources.
if it is 0 means no resource is available and process has to wait.
if it is n means n resource are available and can be allocated.
V(s) executes when resource is released to increment the semaphore value.
semaphore does not distinguishes resources.
prevents race condition and deadlock does not guarantees them.

P(s):
while(1){

if s >= n

  s= s-n;

  break;
}

//here goes semaphore with waiting queue and wake up, sleep

semaphore with waiting queue can result in deadlock and also starvation if queue is LIFO


References
http://www.disi.unige.it/person/DelzannoG/SO1/AA0607/peterson.htm
http://en.wikipedia.org/wiki/Peterson%27s_algorithm
www.arl.wustl.edu/~fredk/Courses/cse422/sp03/.../concurrency1.ppt