Skip to content

Liveness

Deadlock

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// Two philosophers, thinking and eating sushi
#include <mutex>
#include <thread>

int sushi_count = 5000;

void philosopher(std::mutex& first_chopstick, std::mutex& second_chopstick) {
  while (sushi_count > 0) {
    first_chopstick.lock();
    second_chopstick.lock();
    if (sushi_count) {
      sushi_count--;
    }
    second_chopstick.unlock();
    first_chopstick.unlock();
  }
}

int main() {
  std::mutex chopstick_a, chopstick_b;
  std::thread barron(philosopher, std::ref(chopstick_a), std::ref(chopstick_b));
  std::thread olivia(philosopher, std::ref(chopstick_b), std::ref(chopstick_a));
  barron.join();
  olivia.join();
  printf("The philosophers are done eating.\n");
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// Two philosophers, thinking and eating sushi
#include <mutex>
#include <thread>

int sushi_count = 5000;

void philosopher(std::mutex& first_chopstick, std::mutex& second_chopstick) {
  while (sushi_count > 0) {
    first_chopstick.lock();
    second_chopstick.lock();
    if (sushi_count) {
      sushi_count--;
    }
    second_chopstick.unlock();
    first_chopstick.unlock();
  }
}

int main() {
  std::mutex chopstick_a, chopstick_b;
  std::thread barron(philosopher, std::ref(chopstick_a), std::ref(chopstick_b));
  std::thread olivia(philosopher, std::ref(chopstick_a), std::ref(chopstick_b));
  barron.join();
  olivia.join();
  printf("The philosophers are done eating.\n");
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// Two philosophers, thinking and eating sushi
#include <mutex>
#include <thread>

int sushi_count = 5000;

void philosopher(std::mutex& first_chopstick, std::mutex& second_chopstick) {
  while (sushi_count > 0) {
    std::scoped_lock lock(first_chopstick, second_chopstick);
    if (sushi_count) {
      sushi_count--;
    }
  }
}

int main() {
  std::mutex chopstick_a, chopstick_b;
  std::thread barron(philosopher, std::ref(chopstick_a), std::ref(chopstick_b));
  std::thread olivia(philosopher, std::ref(chopstick_b), std::ref(chopstick_a));
  barron.join();
  olivia.join();
  printf("The philosophers are done eating.\n");
}

Abandoned lock

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// Two philosophers, thinking and eating sushi
#include <mutex>
#include <thread>

int sushi_count = 5000;

void philosopher(std::mutex& chopsticks) {
  while (sushi_count > 0) {
    chopsticks.lock();
    if (sushi_count) {
      --sushi_count;
    }
    chopsticks.unlock();
  }
}

int main() {
  std::mutex chopsticks;
  std::thread barron(philosopher, std::ref(chopsticks));
  std::thread olivia(philosopher, std::ref(chopsticks));
  barron.join();
  olivia.join();
  printf("The philosophers are done eating.\n");
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// Two philosophers, thinking and eating sushi#include <mutex>
#include <thread>

int sushi_count = 5000;

void philosopher(std::mutex& chopsticks) {
  while (sushi_count > 0) {
    std::scoped_lock lock(chopsticks);
    if (sushi_count) {
      --sushi_count;
    }
    if (sushi_count == 10) {
      printf("This philosopher has had enough!\n");
      break;
    }
  }
}

int main() {
  std::mutex chopsticks;
  std::thread barron(philosopher, std::ref(chopsticks));
  std::thread olivia(philosopher, std::ref(chopsticks));
  barron.join();
  olivia.join();
  printf("The philosophers are done eating.\n");
}

Starvation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// Too many philosophers, thinking and eating sushi
#include <array>
#include <mutex>
#include <thread>

int sushi_count = 5000;

void philosopher(std::mutex& chopsticks) {
  int sushi_eaten = 0;
  while (sushi_count > 0) {
    std::scoped_lock lock(chopsticks);
    if (sushi_count) {
      --sushi_count;
      ++sushi_eaten;
    }
  }
  printf("Philosopher %d ate %d.\n", std::this_thread::get_id(), sushi_eaten);
}

int main() {
  std::mutex chopsticks;
  std::array<std::thread, 2> philosophers;
  for (size_t i = 0; i < philosophers.size(); ++i) {
    philosophers[i] = std::thread(philosopher, std::ref(chopsticks));
  }
  for (size_t i = 0; i < philosophers.size(); ++i) {
    philosophers[i].join();
  }
  printf("The philosophers are done eating.\n");
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// Too many philosophers, thinking and eating sushi
#include <array>
#include <mutex>
#include <thread>

int sushi_count = 5000;

void philosopher(std::mutex& chopsticks) {
  int sushi_eaten = 0;
  while (sushi_count > 0) {
    std::scoped_lock lock(chopsticks);
    if (sushi_count) {
      --sushi_count;
      ++sushi_eaten;
    }
  }
  printf("Philosopher %d ate %d.\n", std::this_thread::get_id(), sushi_eaten);
}

int main() {
  std::mutex chopsticks;
  std::array<std::thread, 200> philosophers;
  for (size_t i = 0; i < philosophers.size(); ++i) {
    philosophers[i] = std::thread(philosopher, std::ref(chopsticks));
  }
  for (size_t i = 0; i < philosophers.size(); ++i) {
    philosophers[i].join();
  }
  printf("The philosophers are done eating.\n");
}

Livelock

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// Exceptionally polite philosophers, thinking and eating sushi
#include <mutex>
#include <thread>

int sushi_count = 5000;

void philosopher(std::mutex& first_chopstick, std::mutex& second_chopstick) {
  while (sushi_count > 0) {
    first_chopstick.lock();
    second_chopstick.lock();
    if (sushi_count) {
      --sushi_count;
    }
    second_chopstick.unlock();
    first_chopstick.unlock();
  }
}

int main() {
  std::mutex chopstick_a, chopstick_b;
  std::thread barron(philosopher, std::ref(chopstick_a), std::ref(chopstick_b));
  std::thread olivia(philosopher, std::ref(chopstick_b), std::ref(chopstick_a));
  barron.join();
  olivia.join();
  printf("The philosophers are done eating.\n");
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// Exceptionally polite philosophers, thinking and eating sushi
#include <mutex>
#include <thread>

int sushi_count = 5000;

void philosopher(std::mutex& first_chopstick, std::mutex& second_chopstick) {
  while (sushi_count > 0) {
    first_chopstick.lock();
    if (!second_chopstick.try_lock()) {
      first_chopstick.unlock();
    } else {
      if (sushi_count) {
        --sushi_count;
      }
      second_chopstick.unlock();
      first_chopstick.unlock();
    }
  }
}

int main() {
  std::mutex chopstick_a, chopstick_b;
  std::thread barron(philosopher, std::ref(chopstick_a), std::ref(chopstick_b));
  std::thread olivia(philosopher, std::ref(chopstick_b), std::ref(chopstick_a));
  std::thread steve(philosopher, std::ref(chopstick_a), std::ref(chopstick_b));
  std::thread nikki(philosopher, std::ref(chopstick_b), std::ref(chopstick_a));
  barron.join();
  olivia.join();
  steve.join();
  nikki.join();
  printf("The philosophers are done eating.\n");
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// Exceptionally polite philosophers, thinking and eating sushi
#include <mutex>
#include <thread>

int sushi_count = 5000;

void philosopher(std::mutex& first_chopstick, std::mutex& second_chopstick) {
  while (sushi_count > 0) {
    first_chopstick.lock();
    if (!second_chopstick.try_lock()) {
      first_chopstick.unlock();
      // allow current thread to wait a moment (don't pick the first_chopstick
      // so fast, so other threads can have chances to pick the first_chopstick)
      std::this_thread::yield();
    } else {
      if (sushi_count) {
        --sushi_count;
      }
      second_chopstick.unlock();
      first_chopstick.unlock();
    }
  }
}

int main() {
  std::mutex chopstick_a, chopstick_b;
  std::thread barron(philosopher, std::ref(chopstick_a), std::ref(chopstick_b));
  std::thread olivia(philosopher, std::ref(chopstick_b), std::ref(chopstick_a));
  std::thread steve(philosopher, std::ref(chopstick_a), std::ref(chopstick_b));
  std::thread nikki(philosopher, std::ref(chopstick_b), std::ref(chopstick_a));
  barron.join();
  olivia.join();
  steve.join();
  nikki.join();
  printf("The philosophers are done eating.\n");
}