Livelock

• A program cannot make progress

  • In deadlock, the threads are inactive
  • In livelock, the threads are still active

• Livelock can result from badly done deadlock avoidance

  • A thread cannot get a lock
  • Instead of blocking indefinitely, it backs off and tries again

Livelock Example

void funcA() {
  bool locked = false;
  
  while (!locked) {
    std::lock_guard lck_guard(mut1);  // lock mut1
    std::this_thread::sleep_for(1s);
    locked = mut2.try_lock();         // try to lock mut2
  }
}

void funcB() {
  // Same as funcA, but with mut1 and mut2 interchanged
}

Livelock Analogy

• Imagine two very polite people
• They walk down a corridor together
• They reach a narrow door
  • They each try to go through the door at the same time
  • Each one stops and waits for the other to go through the door
  • Then they both try to go through the door at the same time
  • Then each one stops and waits for the other to go through the door, etc.

Livelock Avoidance

• Use std::stoped_lock or std::lock()
  • The thread can acquire multiple locks in a single operation
  • Built-in deadlock avoidance

void funcA() {
  std::scoped_lock scoped_lck(mut1, mut2);   // lock both mutexes
  // ...
}

void funcA() {
  std::scoped_lock scoped_lck(mut2, mut1);   // lock both mutexes
  // ...
}

Thread Priority

• We could assign different priorities to threads
• Not directly supported by C++
• Most thread implementations allow it
  • Accessible via std::thread native_handle()
  • A high priority thread will run more often
  • A low priority thread will be suspended or interrupted more often
• The high priority thread will lock the mutex first
• The low priority thread will lock the mutex afterwards

Resource Starvation

• A thread cannot get the resources it needs to run
  • In deadlock and livelock, the thread cannot acquire a lock
• Lack of system resources can prevent a thread starting
  • System memory exhausted
  • Maximum supported number of threads is already running
• Low priority threads may get starved of processor time
  • Higher priority threads are given preference by the scheduler
  • Good schedulers try to avoid this