Livelock Practical

  • The previous attempt resulted in deadlock
    • All the philosophers picked up their left fork
    • None of the right forks were available
    • The philosophers were stuck in the "thinking" state

Deadlock Avoidance

  • We try to avoid the deadlock
  • Add a time-out and retry:
    • Philosopher picks up left fork
    • Philosopher tries to pick up right fork
    • Philosopher cannot pick up right fork
    • Philosopher puts down left fork
    • Philosopher waits
    • Philosopher picks up left fork again

Livelock

  • This creates a situation of Livelock:

    • All the philosophers pick up their left forks at the same time
    • All the philosophers try to pick up their right fork
    • All the philosophers put down their left forks at the same time
    • All the philosophers pick up their left forks at the same time

  • The philosopher threads are livelocked

    • The philosophers are active, but cannot enter the "eating" state

Solutions

  • Add randomness

    • The philosophers pick up and put down their forks at different time
    • Reduces the probability of starvation
    • Does not completely eliminate it

  • Provide a central arbitrator to coordinate the philosophers

    • Only allows one philosopher to pick up a fork at a time
    • Only one philosopher can eat at a time
    • Reduces parallelism

  • Use a shared lock

    • In effect, a philosopher picks up both forks at the same time

  • Introduce a fork hierarchy

    • The philosophers must pick up the lower-numbered fork first

    • A picks up fork 0

    • B picks up fork 1

    • C picks up fork 2

    • D picks up fork 3

    • E tries to pick up fork 0

    • This leaves fork 4 available

      • D picks up fork 3
      • D starts eating