Process Synchronisation

Process Synchronisation

1. Solution criteria to critical section problem

   • Mutual exclusion
     • If process Pi is executing it's critical section, no other process can be executing their critical section
   • Progress
     • No process outside critical section should block a process waiting to enter
   • Bounded waiting
     • Bound imposed on number of times a process is allowed to enter critical section after another process has made a request to enter its critical section
       • Must enforce fairness (process not left waiting forever)

2. Peterson's solution

   • Advantages
     • Works if both processes execute at same time
       • 'turn' variable achieves fairness through alternation
   • Problems
     • Still busy waiting
     • Doesn't scale well
     • Only two processes

3. Synchronisation hardware

   • Special atomic (non-interuptible) hardware instructions
     • TestAndSet
       • Test memory address and set in one instruction
       • Solution
         • How
           • Sets variable to TRUE and returns original
           • If returns FALSE, know we are only thread that changed value from FALSE to TRUE
           • If returns TRUE, we know we haven't changed value
         • Problems
           • No bounded waiting; one process could wait forever
         • Advantages
           • Achieves mutual exlusion
         • Bounded mutual exclusion
           • Guarantees mutual exclusion
           • While loop spins constantly which wastes CPU usage
     • Swap
       • Swap contents of two memory addresses in one instruction

4. Sleep and wake

   • Rationale
     • Avoid process spinning waiting to acquire lock
       • Send itself to sleep and awoken only when it has a chance to proceed
   • Problem of losing wake ups
     • Solution to this is long
       • Holds lock when it goes to sleep
         • Final solution is to release lock during sleep()
           • Released prior to context switch with guarantee of no interruption
           • Lock required upon wakeup
           • Complicated - need sleeping lock (semaphore) to hide complexity
     • Don't know if process will wake up when lock is released
       • Decide to go to sleep but when wake up call comes still haven't gone to sleep (missed)

Bilder und Dateien der Mindmap