Synchronisation

Synchronisation

1. Competition for Resources

   • Critical Region
     • Part of the program where the shared resources are accessed
       • Aim to have no two processes in the critical region at the same time
   • Sometimes a process has to access shared resources leading to race conditions
     • Race Condition
       • Multiple threads/processes read and write a shared data item, and the final result is relative to timing of execution
   • Mutual Exclusion
     • Requirement that when one process is in the critical region, no other processes can access those resources
       • Mutual Exclusion Requirements
         • 1. No two processes simultaneously in critical region
         • 2. No assumptions about speeds/numbers in CPUs
         • 3. No process running outside its critical region may block another process (deadlock)
         • 4. No process must wait forever to enter critical region (starvation)
       • Busy Waiting/Spinning
         • Process repeatedly checks to see if a condition is true
           • Consumes processor time
     • Hardware Support
       • Interrupt Disabling
         • Disabling interrupts guarantees mutual exclusion
         • Disadvantages
           • Can be dangerous to allow processes to turn off interrupts
           • Multiprocessing
             • Can't ensure mutual exclusion
       • Special Machine Instructions
         • Atomic Action - Cannot be interrupted
           • Either because it locks the memory bus
           • or blocks interrupt mechanism
       • Test and Set Instruction
         • Advantage of Instructions: Applicable to any number of processes
       • Exchange Instruction
   • Peterson's Solution
     • 'Two Process Solution'
       • LOAD and STORE are atomic (can't be interrupted)
         • Two processes share two variables: int turn, boolean interested[2]
           • turn
             • Indicates whose turn it is to enter critical region
           • interested
             • Array is used to indicate if a process is ready to enter the critical section

2. Semaphores

   • Synchronisation tool which DOESN'T require busy waiting
     • Semaphore S = integer variable for signaling
       • Two atomic operations modify S: wait() and signal()
         • wait()
           • decrements semaphore value
         • signal()
           • increments semaphore value
         • block() and wakeup() implementation - each semaphore has a waiting queue
           • Waiting queue has value (type of integer) and pointer to next record
           • block() - place process invoking operation in waiting queue
           • wakeup() - remove a process in waiting queue and place in ready queue
           • no busy waiting
     • 'Spinlock'
       • Spins waiting for the lock
     • Good solution is processes don't spend long in critical sections
   • Readers-Writers Problem
     • Readers
       • Only read the data set, don't perform updates
     • Writers
       • Can BOTH read and write
     • Problem
       • Only a single writer can access the shared data at the same time
         • Shared data
           • Data set
           • Semaphore mutex
             • Mutex = mutual exclusion
           • Semaphore wrt
           • readcount
     • Dining-Philosophers Problem
       • Deadlock-free solution
         • 1. Allow AT MOST 4 philosophers sit at table
         • 2. Allow a philosopher to pick up their chopsticks only if both are available
         • 3. Use an asymmetric solution - Odd philsopher pciks up first left, then right chopstick, even vice versa
         • Doesn't necessarily prevent starvation

Bilder und Dateien der Mindmap