C++ Three Solutions | Detailed Explanation | One Liner | Follow Up Questions
This is a typical textbook question for operation system courses although it appears to be poorly defined in first glance, it was originally formulated in 1965 
This is a typical textbook question for operation system courses although it appears to be poorly defined in first glance, it was originally formulated in 1965 by Edsger Dijkstra as a student exam exercise.\nYou will not see this question in an interview but understanding it is the fundamental of cracking other multi-threading questions.\n\n**Solution 0: Let philosophers eat one by one**\nLeetCode accepts this solution but it is generally **WRONG**. Why?\n1. Using raw mutex is very unprofessional, we don\u2019t know how `pickLeftFork()` `pickRightFork()` `eat()` `putLeftFork()` `putRightFork()` are implemented, if any of them throws exception, our mutex will **never** be unlocked! Always wrap mutex with `lock_guard` or `unique_lock`\n\n2. This approach destroys advantage of multithreading, only one thread can be executed at a time.\n```\nclass DiningPhilosophers {\nprivate:\n    mutex mtx; // 5 philosophers share 1 single mutex\npublic:\n    DiningPhilosophers() { }\n    void wantsToEat(int philosopher, function<void()> pickLeftFork, function<void()> pickRightFork, function<void()> eat, function<void()> putLeftFork, function<void()> putRightFork) {\n        mtx.lock();\n        pickLeftFork(); pickRightFork(); eat(); putLeftFork(); putRightFork();\n        mtx.unlock();\n    }\n};\n```\n\n**Solution 1: Lock the table then pick up both forks together**\nVery similar to `Solution 0`, but we release locks immediately after picking up **both forks**, then `eat()` method can take as long as it requires without blocking other threads.\n**However** isn\'t a nice approach either, it has great performance impact as table size grows, imagin if we have 50 threads try to `eat()`, every single one need to `lock()/unlock()` the table for picking up both forks while other 49 threads will have to `wait()`.\n```\nclass DiningPhilosophers {\nprivate:\n    mutex mtxFork[5];\n    mutex mtxTable;\n    \npublic:\n    DiningPhilosophers() { }\n    void wantsToEat(int philosopher, function<void()> pickLeftFork, function<void()> pickRightFork, function<void()> eat, function<void()> putLeftFork, function<void()> putRightFork) {\n        int left = philosopher;\n        int right = (philosopher + 1) % 5;\n\t\t\n        unique_lock<mutex> lckTable(mtxTable);\n        unique_lock<mutex> lckForkLeft(mtxFork[left]);\n        unique_lock<mutex> lckForkRight(mtxFork[right]);\n        lckTable.unlock(); // after locking both forks, we can safely unlock table\n        \n        pickLeftFork(); pickRightFork(); eat(); putRightFork(); putLeftFork();\n        // locks will be automatically released due to unique_lock RAII design\n    }\n};\n```\n\n**Solution 2: Change forks picking order**\nLet even philosophers pick up **left** forks before **right** forks.\nLet odd philosophers pick up **right** forks before **left** forks.\nBefore diving into final answer, lets see an easy to understand solution with raw mutex\n```\nclass DiningPhilosophers {\nprivate:\n    mutex mtx[5];\n    \npublic:\n    DiningPhilosophers() { }\n    void wantsToEat(int philosopher, function<void()> pickLeftFork, function<void()> pickRightFork, function<void()> eat, function<void()> putLeftFork, function<void()> putRightFork) {\n        int left = philosopher;\n        int right = (philosopher + 1) % 5;\n        \n        if(philosopher % 2 == 0){\n            mtx[right].lock(); // lock right before left\n            mtx[left].lock();\n            pickLeftFork(); pickRightFork();\n        }\n\t\telse{\n            mtx[left].lock(); // lock left before right\n            mtx[right].lock();\n            pickLeftFork(); pickRightFork();\n        }\n        \n        eat(); putRightFork(); putLeftFork();\n        mtx[left].unlock();\n        mtx[right].unlock();\n    }\n};\n```\nThen lets wrap up raw mutex with unique_lock.\nBe aware that unique_lock needs to be put outside of if statement, otherwise its scoop will be limited in if statement **only**\n```\nclass DiningPhilosophers {\nprivate:\n    mutex mtx[5];\n    \npublic:\n    DiningPhilosophers() { }\n    void wantsToEat(int philosopher, function<void()> pickLeftFork, function<void()> pickRightFork, function<void()> eat, function<void()> putLeftFork, function<void()> putRightFork) {\n        int left = philosopher;\n        int right = (philosopher + 1) % 5;\n        \n        unique_lock<mutex> lck1(mtx[left], defer_lock); // defer_lock: init lck1 without locking mtx\n        unique_lock<mutex> lck2(mtx[right], defer_lock);\n        \n        if(philosopher % 2 == 0){\n            lck1.lock(); // do NOT use std::lock(lck1, lck2)\n            lck2.lock();\n            pickLeftFork(); pickRightFork();\n        }\n\t\telse{\n            lck2.lock();\n            lck1.lock();\n            pickLeftFork(); pickRightFork();\n        }\n        eat(); putRightFork(); putLeftFork();\n        // lck1 & lck2 are auto released after this line\n    }\n};\n```\n\n**Solution 3: Limit 4 philosophers to eat at same time**\nUse Semaphore to limit max of 4 philosophers can eat at same time, at least one philosopher will get both forks.\n\n```\nclass Semaphore {\nprivate:\n\tint count;\n    mutex mtx;\n    condition_variable cv;\n\t\npublic:\n    Semaphore(int n = 0) : count(n) { }\n    void Set(int n) { count = n; }\n    void Signal() {\n        unique_lock<mutex> lck(mtx);\n        ++count;\n        cv.notify_one();\n    }\n    void Wait() {\n        unique_lock<mutex> lck(mtx);\n        cv.wait(lck, [&](){ return count > 0; }); // standard format of wait() lambda expression\n        --count;\n    }\n};\n\nclass DiningPhilosophers {\nprivate:\n    mutex mtx[5];\n    Semaphore sem;\n    \npublic:\n    DiningPhilosophers() { sem.Set(4); }\n    void wantsToEat(int philosopher, function<void()> pickLeftFork, function<void()> pickRightFork, function<void()> eat, function<void()> putLeftFork, function<void()> putRightFork) {\n        int left = philosopher;\n        int right = (philosopher + 1) % 5;\n        \n        sem.Wait(); // if there are 4 philosophers eating, thread will wait here\n\n        unique_lock<mutex> lckLeft(mtx[left]);\n        unique_lock<mutex> lckRight(mtx[right]);\n        \n        pickLeftFork(); pickRightFork(); eat(); putRightFork(); putLeftFork();\n        \n        lckLeft.unlock();\n        lckRight.unlock();\n\n        sem.Signal(); // finish eating, release 1 spot for other philosophers\n    }\n};\n```\nwhy bother writing our own `Semaphore` class?  Why don\'t we use `#include "semaphore.h"` like other solutions?\nBecause `semaphore.h` is only available for Linux, while `CreateSemaphore()` is only available for windows, in real life writing following code breaks portability and readability.\n```\n#ifdef UNIX\n\t// code for Linux\n#else\n\t// code for Windows\n#endif\n```\nIs there a way to solve above problem without writing our own Semaphore class?\nYes, we can use c++ 20 `<semaphore>` header, sadly LeetCode seems don\'t have c++ 20 support so following code won\'t compile :(\n```\n#include <thread>\n#include <chrono>\n#include <semaphore> // ERROR: compiler unable to find this header\n\nclass DiningPhilosophers {\nprivate:\n    mutex mtx[5];\n    counting_semaphore<4> sem(4);\n    \npublic:\n    DiningPhilosophers() { }\n    void wantsToEat(int philosopher, function<void()> pickLeftFork, function<void()> pickRightFork, function<void()> eat, function<void()> putLeftFork, function<void()> putRightFork) {\n        int left = philosopher;\n        int right = (philosopher + 1) % 5;\n        \n        sem.acquire(); // if there are 4 philosophers eating, thread will wait here\n\n        unique_lock<mutex> lckLeft(mtx[left]);\n        unique_lock<mutex> lckRight(mtx[right]);\n        \n        pickLeftFork(); pickRightFork(); eat(); putRightFork(); putLeftFork();\n        \n        lckLeft.unlock();\n        lckRight.unlock();\n\n        sem.release(); // finish eating, release 1 spot for other philosophers\n    }\n};\n```\n**Last Solution for fun: ON LINER**\n```\nclass DiningPhilosophers {\nprivate:\n    mutex mtx[5];\npublic:\n    void wantsToEat(int philosopher, function<void()> pickLeftFork, function<void()> pickRightFork, function<void()> eat, function<void()> putLeftFork, function<void()> putRightFork) {\n        scoped_lock lck(mtx[philosopher], mtx[(philosopher + 1) % 5]);\n        pickLeftFork(); pickRightFork(); eat(); putLeftFork(); putRightFork();\n    }\n};\n```\n**Interview Follow Ups:**\n1. For solution 2, can we use `lock(lck1, lck2)`, instead of `lck1.lock(); lck2.lock();`? Why?\n2. For solution 3, can we call `lckRight.unlock()` before `lckLeft.unlock()`? Why?\n3. For solution 3, can we call `cv.notify_all()` instead of `cv.notify_one()`? Why?\n4. For last solution, one liner gets TLEed sometime, explain why this approach is slow?\n\nDon\'t forget to **Upvote**
['C']