Synchronisation

If a process has global variables and multiple threads, we hit race conditions with the modification of that variable.

To prevent this, we declare code that queries/modifies the variable a 'critical region' or 'critical section' - and only one thread can be in a critical region at a time.

critical%20regios.png

Solving a Race Condition

To correctly fix a critical region we have to make sure:

  • Access is mutually exclusive (one at a time)
  • They're bounded (waiting is not infinite)
  • Progress occurs (we can't block each other outside of critical regions)
  • It doesn't matter how many CPUs there are

Implementing Solutions

  • Locks
    • Lots of busy waiting
  • Mutex by Interrupt disabling
    • Only available in the kernel
  • Hardware mutex
    • Super easy but spinlock (busy wait consumes CPU)
  • Semaphores (check/sleep and wakeup)
    • Put process to sleep until the lock is available, when we wake it up
    • Can be a one access lock or can solve producer/consumer issues
    • But we have to make sure there's a signal for every wait and vice versa

Deadlocks

A deadlock occurs when multiple process compete for the same variables in such a way that one or more process/thread ends up unable to ever move.

E.g. dining philosopher's problem if they all reach for left cutlery.

We fix this by ensuring we always acquire things in the same order everywhere, and always release the inverse of acquiring.

Defining Deadlock

Four Conditions Required:

  1. Mutual Exclusion of resources
  2. Can request multiple at a time
  3. Can't forcibly take away resources
  4. 2 or more processes locked together waiting for a resource held by the next member in the chain

Handling Deadlocks

Ignorance

If deadlocks don't occur often and there's a big cost, we can trade off correctness in favour of convenience and just ignore them.

Detection

We can draw directed graphs of processes to resources or matrices and then apply detection algorithms.

E.g. if we have 5 resources, each has a quantity and 4 processes each want some quantity of the resource, we make a 5*4 matrix storing the desired quantities. We then store a 5*1 vector of 'free' quantities of the resources.

We want to allocate each row, and then free each row. To allocate a row, each desired quantity must be less than the free quantity. If there is no row allocation order then all leftover rows are deadlocked.

Recovery

  • Prevention
    • Take a resource away from something else (not always possible)
  • Rollback
    • Go back to a state that did have a finishing path (safe state)
      • Safe states don't always end well, but they always *can* end well, even if everything requests their max resources
      • Unsafe states don't always end badly, but we can't guarantee a good ending.
  • Death
    • Kill a process (Free up its resources). Choose one that can be rerun from the beginning.

Avoidance

If we know the max number of each resource that will be required, it's possible to avoid a deadlock.

Prevention

Prevent one of the requirements; the first 3 are all recipes for disaster! (race conditions! Can't assume we'll know what we need at the start. and forcibly stop something printing? Nope) - so we should attack the last one. As above:

We fix this by ensuring we always acquire things in the same order everywhere, and always release the inverse of acquiring.

Starvation.

We also have to be careful nothing waits forever for a resource even though it becomes available. Often we use a simple first-come first-serve policy to make sure things get their fair turn.