{"id":2357,"date":"2017-01-20T12:05:17","date_gmt":"2017-01-20T10:05:17","guid":{"rendered":"http:\/\/mariusbancila.ro\/blog\/?p=2357"},"modified":"2017-01-20T12:05:17","modified_gmt":"2017-01-20T10:05:17","slug":"dining-philosophers-in-c11-chandy-misra-algorithm","status":"publish","type":"post","link":"https:\/\/mariusbancila.ro\/blog\/2017\/01\/20\/dining-philosophers-in-c11-chandy-misra-algorithm\/","title":{"rendered":"Dining philosophers in C++11: Chandy-Misra algorithm"},"content":{"rendered":"<p>In my previous post, <a href=\"http:\/\/mariusbancila.ro\/blog\/2017\/01\/16\/dining-philosophers-in-cpp11\/\">Dining Philosophers in C++11<\/a>, I have provided an implementation for the dining philosophers problem using modern C++ features, such as threads and mutexes. However, it was <a href=\"http:\/\/mariusbancila.ro\/blog\/2017\/01\/16\/dining-philosophers-in-cpp11\/#comment-390346\">noted in the comments<\/a> that the implementation did not prevent the philosophers starving to death when you remove the waiting times.<\/p>\n<p>An algorithm that prevents the philosophers from starving was proposed by Mani Chandy and J. Misra and is known as the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Dining_philosophers_problem#Chandy.2FMisra_solution\">Chandy\/Misra solution<\/a>. This is a bit different than the original problem because it requires the philosophers to communicate with each other. The algorithm, as described on Wikipedia, is the following:<\/p>\n<blockquote>\n<ol>\n<li>For every pair of philosophers contending for a resource, create a fork and give it to the philosopher with the lower ID (n for agent Pn). Each fork can either be dirty or clean. Initially, all forks are dirty.<\/li>\n<li>When a philosopher wants to use a set of resources (i.e. eat), said philosopher must obtain the forks from their contending neighbors. For all such forks the philosopher does not have, they send a request message.<\/li>\n<li>When a philosopher with a fork receives a request message, they keep the fork if it is clean, but give it up when it is dirty. If the philosopher sends the fork over, they clean the fork before doing so.<\/li>\n<li>After a philosopher is done eating, all their forks become dirty. If another philosopher had previously requested one of the forks, the philosopher that has just finished eating cleans the fork and sends it.<\/li>\n<\/ol>\n<\/blockquote>\n<p>In order to implement this, we must make several changes to the solution proposed in the previous post:<\/p>\n<ul>\n<li>forks and philosophers must have identifiers<\/li>\n<li>there is an initial setup of both forks and philosophers<\/li>\n<li>use <tt>std::condition_variable<\/tt> to communicate between threads<\/li>\n<li>increase the number of philosophers<\/li>\n<\/ul>\n<p>Because it has been also argued that <tt>string_view<\/tt> is only available in C++17 and this implementation is supposed to work in C++11, I have replaced that with <tt>std::string const&<\/tt>.<\/p>\n<p>In this implementation, philosophers, i.e. threads, need to communicate with each other to request the forks, i.e. resources. For this, we will use a <tt>std::condition_variable<\/tt>, which is a synchronization primitive that enables the blocking of one or more threads until another thread notifies it. A <tt>std::condition_variable<\/tt> requires a <tt>std::mutex<\/tt> to protect access to a shared variable. The following class, <tt>sync_channel<\/tt>, contains both a condition variable and a mutex and provides two methods: one that waits on the condition variable, blocking the calling thread(s), and one that notifies the condition variable, unblocking all the threads that are waiting for a signal.<\/p>\n<pre class=\"lang:c++ decode:true \" >class sync_channel\r\n{\r\n   std::mutex              mutex;\r\n   std::condition_variable cv;\r\n\r\npublic:\r\n   void wait()\r\n   {\r\n      std::unique_lock&lt;std::mutex&gt; lock(mutex);\r\n      cv.wait(lock);\r\n   }\r\n\r\n   void notifyall()\r\n   {\r\n      std::unique_lock&lt;std::mutex&gt; lock(mutex);\r\n      cv.notify_all();\r\n   }\r\n};<\/pre>\n<p>The <tt>table<\/tt> class from the previous implementation is modified: the forks are no longer defined here, but a sync_channel is used to prevent philosophers start dining until the table setup is completed. Its name has been changed to <tt>table_setup<\/tt>.<\/p>\n<pre class=\"lang:c++ decode:true \" >struct table_setup\r\n{\r\n   std::atomic&lt;bool&gt; done{ false };\r\n   sync_channel      channel;\r\n};<\/pre>\n<p>The <tt>fork<\/tt> class is no longer a wrapper for a mutex. It has an identifier, an owner, a flag to indicate whether it is dirty or clean, a <tt>mutex<\/tt>, and a <tt>sync_channel<\/tt> that enables owners to request used forks. It has two methods:<\/p>\n<ul>\n<li><tt>request()<\/tt> that enables a philosopher to request the fork. If the fork is dirty, it is set to clean, and the ownership is given to the philosopher that asked for it. If the fork is clean (i.e. the current owner is eating), than the philosopher that asked for it will block, waiting for it to become dirty (i.e. the current owner has finished eating).\n<pre class=\"lang:c++ decode:true \" >\r\nvoid request(int const ownerId)\r\n{\r\n   while (owner != ownerId)\r\n   {\r\n      if (dirty)\r\n      {\r\n         std::lock_guard&lt;std::mutex&gt; lock(mutex);\r\n\r\n         dirty = false;\r\n         owner = ownerId;\r\n      }\r\n      else\r\n      {\r\n         channel.wait();\r\n      }\r\n   }\r\n}<\/pre>\n<\/li>\n<li><tt>done_using()<\/tt> a philosopher indicates that has finished eating and notifies other philosopher that is waiting for the fork that it can have it.\n<pre class=\"lang:c++ decode:true \" >\r\nvoid done_using()\r\n{\r\n   dirty = true;\r\n   channel.notifyall();\r\n}<\/pre>\n<\/li>\n<\/ul>\n<p>There are less changes to the <tt>philosopher<\/tt> class: it has an identifier, and there are no more waiting times to simulate eating and thinking. There are some small changes to the following methods:<\/p>\n<ul>\n<li><tt>dine()<\/tt>: each philosopher only starts eating after the entire table has been setup. A condition variable, from the <tt>table_setup<\/tt> object is used for this.\n<pre class=\"lang:c++ decode:true \" >\r\nvoid dine()\r\n{\r\n   setup.channel.wait();\r\n\r\n   do\r\n   {\r\n      think();\r\n      eat();\r\n   } while (!setup.done);\r\n}<\/pre>\n<\/li>\n<li><tt>eat()<\/tt>: each philosopher first requests the left and right fork. When they are available, they are locked using <tt>std::lock()<\/tt> to avoid possible deadlocks, and then their ownership is transfered to a <tt>std::lock_guard<\/tt> object, so they are properly released when done. After eating, the fork is set as dirty and other philosophers waiting for it are notified of this.\n<pre class=\"lang:c++ decode:true \" >\r\nvoid eat()\r\n{\r\n   left_fork.request(id);\r\n   right_fork.request(id);\r\n\r\n   std::lock(left_fork.getmutex(), right_fork.getmutex());\r\n\r\n   std::lock_guard&lt;std::mutex&gt; left_lock(left_fork.getmutex(), std::adopt_lock);\r\n   std::lock_guard&lt;std::mutex&gt; right_lock(right_fork.getmutex(), std::adopt_lock);\r\n\r\n   print(\" started eating.\");\r\n   print(\" finished eating.\");\r\n\r\n   left_fork.done_using();\r\n   right_fork.done_using();\r\n}<\/pre>\n<\/li>\n<\/ul>\n<p>According to the initial setup, each fork is given to the philosopher with the lower ID. That means fokm 1, placed between philosopher 1 and N, goes to philosopher 1. Fork 2, placed between philosophers 2 and 3 is given to philosopher 2. Eventually, fork N, placed between philosophers N and 1, is given to philosopher 1. Overall, this means all philosophers have initially 1 fork, except for the first one that has two, and the last philosopher, that has none.<\/p>\n<p>Put all together, the code looks like this:<\/p>\n<pre class=\"lang:c++ decode:true \" >\r\n#include &lt;array&gt;\r\n#include &lt;mutex&gt;\r\n#include &lt;thread&gt;\r\n#include &lt;atomic&gt;\r\n#include &lt;chrono&gt;\r\n#include &lt;iostream&gt;\r\n#include &lt;string&gt;\r\n#include &lt;iomanip&gt;\r\n#include &lt;condition_variable&gt;\r\n\r\nstd::mutex g_lockprint;\r\nconstexpr  int no_of_philosophers = 7;\r\n\r\nclass sync_channel\r\n{\r\n   std::mutex              mutex;\r\n   std::condition_variable cv;\r\n\r\npublic:\r\n   void wait()\r\n   {\r\n      std::unique_lock&lt;std::mutex&gt; lock(mutex);\r\n      cv.wait(lock);\r\n   }\r\n\r\n   void notifyall()\r\n   {\r\n      std::unique_lock&lt;std::mutex&gt; lock(mutex);\r\n      cv.notify_all();\r\n   }\r\n};\r\n\r\nstruct table_setup\r\n{\r\n   std::atomic&lt;bool&gt; done{ false };\r\n   sync_channel      channel;\r\n};\r\n\r\nclass fork\r\n{\r\n   int            id;\r\n   int            owner;\r\n   bool           dirty;\r\n   std::mutex     mutex;\r\n   sync_channel   channel;\r\n\r\npublic:\r\n   fork(int const forkId, int const ownerId):\r\n      id(forkId), owner(ownerId), dirty(true)\r\n   {}\r\n\r\n   void request(int const ownerId)\r\n   {\r\n      while (owner != ownerId)\r\n      {\r\n         if (dirty)\r\n         {\r\n            std::lock_guard&lt;std::mutex&gt; lock(mutex);\r\n\r\n            dirty = false;\r\n            owner = ownerId;\r\n         }\r\n         else\r\n         {\r\n            channel.wait();\r\n         }\r\n      }\r\n   }\r\n\r\n   void done_using()\r\n   {\r\n      dirty = true;\r\n      channel.notifyall();\r\n   }\r\n\r\n   std::mutex&amp; getmutex() { return mutex; }\r\n};\r\n\r\nstruct philosopher\r\n{\r\nprivate:\r\n   int               id;\r\n   std::string const name;\r\n   table_setup&amp;      setup;\r\n   fork&amp;             left_fork;\r\n   fork&amp;             right_fork;\r\n   std::thread       lifethread;\r\npublic:\r\n   philosopher(int const id, std::string const &amp; n, table_setup &amp; s, fork &amp; l, fork &amp; r) :\r\n      id(id), name(n), setup(s), left_fork(l), right_fork(r), lifethread(&amp;philosopher::dine, this)\r\n   {\r\n   }\r\n\r\n   ~philosopher()\r\n   {\r\n      lifethread.join();\r\n   }\r\n\r\n   void dine()\r\n   {\r\n      setup.channel.wait();\r\n\r\n      do\r\n      {\r\n         think();\r\n         eat();\r\n      } while (!setup.done);\r\n   }\r\n\r\n   void print(std::string const &amp; text)\r\n   {\r\n      std::lock_guard&lt;std::mutex&gt; cout_lock(g_lockprint);\r\n      std::cout\r\n         &lt;&lt; std::left &lt;&lt; std::setw(10) &lt;&lt; std::setfill(' ')\r\n         &lt;&lt; name &lt;&lt; text &lt;&lt; std::endl;\r\n   }\r\n\r\n   void eat()\r\n   {\r\n      left_fork.request(id);\r\n      right_fork.request(id);\r\n\r\n      std::lock(left_fork.getmutex(), right_fork.getmutex());\r\n\r\n      std::lock_guard&lt;std::mutex&gt; left_lock(left_fork.getmutex(), std::adopt_lock);\r\n      std::lock_guard&lt;std::mutex&gt; right_lock(right_fork.getmutex(), std::adopt_lock);\r\n\r\n      print(\" started eating.\");\r\n      print(\" finished eating.\");\r\n\r\n      left_fork.done_using();\r\n      right_fork.done_using();\r\n   }\r\n\r\n   void think()\r\n   {\r\n      print(\" is thinking \");\r\n   }\r\n};\r\n\r\nclass table\r\n{\r\n   table_setup    setup;\r\n\r\n   std::array&lt;fork, no_of_philosophers&gt; forks\r\n   {\r\n      {\r\n         { 1, 1 },\r\n         { 2, 2 },\r\n         { 3, 3 },\r\n         { 4, 4 },\r\n         { 5, 5 },\r\n         { 6, 6 },\r\n         { 7, 1 },\r\n      }\r\n   };\r\n\r\n   std::array&lt;philosopher, no_of_philosophers&gt; philosophers\r\n   {\r\n      {\r\n         { 1, \"Aristotle\", setup, forks[0], forks[1] },\r\n         { 2, \"Platon\",    setup, forks[1], forks[2] },\r\n         { 3, \"Descartes\", setup, forks[2], forks[3] },\r\n         { 4, \"Kant\",      setup, forks[3], forks[4] },\r\n         { 5, \"Nietzsche\", setup, forks[4], forks[5] },\r\n         { 6, \"Hume\",      setup, forks[5], forks[6] },\r\n         { 7, \"Russell\",   setup, forks[6], forks[0] },\r\n      }\r\n   };\r\n\r\npublic:\r\n   void start()\r\n   {\r\n      setup.channel.notifyall();\r\n   }\r\n\r\n   void stop()\r\n   {\r\n      setup.done = true;\r\n   }\r\n};\r\n\r\nvoid dine()\r\n{\r\n   std::cout &lt;&lt; \"Dinner started!\" &lt;&lt; std::endl;\r\n\r\n   {\r\n      table table;\r\n\r\n      table.start();\r\n      std::this_thread::sleep_for(std::chrono::seconds(60));\r\n      table.stop();\r\n   }\r\n\r\n   std::cout &lt;&lt; \"Dinner done!\" &lt;&lt; std::endl;\r\n}\r\n\r\nint main()\r\n{  \r\n   dine();\r\n\r\n   return 0;\r\n}<\/pre>\n<p>The output of the program looks like this:<\/p>\n<pre class=\"lang:default decode:true \" >Dinner started!\r\nRussell    is thinking\r\nHume       is thinking\r\nNietzsche  is thinking\r\nKant       is thinking\r\nPlaton     is thinking\r\nDescartes  is thinking\r\nAristotle  is thinking\r\nRussell    started eating.\r\nNietzsche  started eating.\r\nNietzsche  finished eating.\r\nRussell    finished eating.\r\nPlaton     started eating.\r\nNietzsche  is thinking\r\nKant       started eating.\r\nHume       started eating.\r\nRussell    is thinking\r\nPlaton     finished eating.\r\nKant       finished eating.\r\nHume       finished eating.\r\nPlaton     is thinking\r\n...\r\nNietzsche  started eating.\r\nDescartes  finished eating.\r\nRussell    started eating.\r\nNietzsche  finished eating.\r\nPlaton     started eating.\r\nRussell    finished eating.\r\nKant       started eating.\r\nPlaton     finished eating.\r\nHume       started eating.\r\nKant       finished eating.\r\nAristotle  started eating.\r\nHume       finished eating.\r\nAristotle  finished eating.\r\nDinner done!<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>In my previous post, Dining Philosophers in C++11, I have provided an implementation for the dining philosophers problem using modern C++ features, such as threads and mutexes. However, it was noted in the comments that the implementation did not prevent the philosophers starving to death when you remove the waiting times. An algorithm that prevents &#8230; <a title=\"Dining philosophers in C++11: Chandy-Misra algorithm\" class=\"read-more\" href=\"https:\/\/mariusbancila.ro\/blog\/2017\/01\/20\/dining-philosophers-in-c11-chandy-misra-algorithm\/\" aria-label=\"Read more about Dining philosophers in C++11: Chandy-Misra algorithm\">Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_uag_custom_page_level_css":"","advgb_blocks_editor_width":"","advgb_blocks_columns_visual_guide":"","_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[7],"tags":[451,345,502,504,190,503,346],"class_list":["post-2357","post","type-post","status-publish","format-standard","hentry","category-c","tag-c","tag-c11","tag-mutex","tag-philosophers","tag-problem","tag-synchronization","tag-thread"],"aioseo_notices":[],"aioseo_head":"\n\t\t<!-- All in One SEO 5.0.1.1 - aioseo.com -->\n\t<meta name=\"description\" content=\"A C++11 implementation of the Chandy-Misra algorithm for the dining philosophers problem.\" \/>\n\t<meta name=\"robots\" content=\"max-image-preview:large\" \/>\n\t<meta name=\"author\" content=\"Marius Bancila\"\/>\n\t<meta name=\"keywords\" content=\"c++,c++11,mutex,philosophers,problem,synchronization,thread\" \/>\n\t<link rel=\"canonical\" href=\"https:\/\/mariusbancila.ro\/blog\/2017\/01\/20\/dining-philosophers-in-c11-chandy-misra-algorithm\/\" \/>\n\t<meta name=\"generator\" content=\"All in One SEO (AIOSEO) 5.0.1.1\" \/>\n\t\t<meta property=\"og:locale\" content=\"en_US\" \/>\n\t\t<meta property=\"og:site_name\" content=\"Marius Bancila&#039;s Blog | About code. Mostly on C++\" \/>\n\t\t<meta property=\"og:type\" content=\"article\" \/>\n\t\t<meta property=\"og:title\" content=\"Dining philosophers in C++11: Chandy-Misra algorithm\" \/>\n\t\t<meta property=\"og:description\" content=\"A C++11 implementation of the Chandy-Misra algorithm for the dining philosophers problem.\" \/>\n\t\t<meta property=\"og:url\" content=\"https:\/\/mariusbancila.ro\/blog\/2017\/01\/20\/dining-philosophers-in-c11-chandy-misra-algorithm\/\" \/>\n\t\t<meta property=\"article:published_time\" content=\"2017-01-20T10:05:17+00:00\" \/>\n\t\t<meta property=\"article:modified_time\" content=\"2017-01-20T10:05:17+00:00\" \/>\n\t\t<meta name=\"twitter:card\" content=\"summary\" \/>\n\t\t<meta name=\"twitter:title\" content=\"Dining philosophers in C++11: Chandy-Misra algorithm\" \/>\n\t\t<meta name=\"twitter:description\" content=\"A C++11 implementation of the Chandy-Misra algorithm for the dining philosophers problem.\" \/>\n\t\t<script type=\"application\/ld+json\" class=\"aioseo-schema\">\n\t\t\t{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2017\\\/01\\\/20\\\/dining-philosophers-in-c11-chandy-misra-algorithm\\\/#article\",\"name\":\"Dining philosophers in C++11: Chandy-Misra algorithm\",\"headline\":\"Dining philosophers in C++11: Chandy-Misra algorithm\",\"author\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/author\\\/admin\\\/#author\"},\"publisher\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/#organization\"},\"datePublished\":\"2017-01-20T12:05:17+02:00\",\"dateModified\":\"2017-01-20T12:05:17+02:00\",\"inLanguage\":\"en-US\",\"commentCount\":3,\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2017\\\/01\\\/20\\\/dining-philosophers-in-c11-chandy-misra-algorithm\\\/#webpage\"},\"isPartOf\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2017\\\/01\\\/20\\\/dining-philosophers-in-c11-chandy-misra-algorithm\\\/#webpage\"},\"articleSection\":\"C++, C++, C++11, mutex, philosophers, problem, synchronization, thread\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2017\\\/01\\\/20\\\/dining-philosophers-in-c11-chandy-misra-algorithm\\\/#breadcrumblist\",\"itemListElement\":[{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog#listItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\",\"nextItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/#listItem\",\"name\":\"IT\"}},{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/#listItem\",\"position\":2,\"name\":\"IT\",\"item\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/\",\"nextItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/software\\\/#listItem\",\"name\":\"Software\"},\"previousItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog#listItem\",\"name\":\"Home\"}},{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/software\\\/#listItem\",\"position\":3,\"name\":\"Software\",\"item\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/software\\\/\",\"nextItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/software\\\/c\\\/#listItem\",\"name\":\"C++\"},\"previousItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/#listItem\",\"name\":\"IT\"}},{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/software\\\/c\\\/#listItem\",\"position\":4,\"name\":\"C++\",\"item\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/software\\\/c\\\/\",\"nextItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2017\\\/01\\\/20\\\/dining-philosophers-in-c11-chandy-misra-algorithm\\\/#listItem\",\"name\":\"Dining philosophers in C++11: Chandy-Misra algorithm\"},\"previousItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/software\\\/#listItem\",\"name\":\"Software\"}},{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2017\\\/01\\\/20\\\/dining-philosophers-in-c11-chandy-misra-algorithm\\\/#listItem\",\"position\":5,\"name\":\"Dining philosophers in C++11: Chandy-Misra algorithm\",\"previousItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/software\\\/c\\\/#listItem\",\"name\":\"C++\"}}]},{\"@type\":\"Organization\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/#organization\",\"name\":\"Marius Bancila's Blog\",\"description\":\"About code. Mostly on C++\",\"url\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/\"},{\"@type\":\"Person\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/author\\\/admin\\\/#author\",\"url\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/author\\\/admin\\\/\",\"name\":\"Marius Bancila\",\"image\":{\"@type\":\"ImageObject\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2017\\\/01\\\/20\\\/dining-philosophers-in-c11-chandy-misra-algorithm\\\/#authorImage\",\"url\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/a84dd2831d955c38355ddea55df4df260809b88f36408bc14fd4eab8f7f131c9?s=96&d=mm&r=g\",\"width\":96,\"height\":96,\"caption\":\"Marius Bancila\"}},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2017\\\/01\\\/20\\\/dining-philosophers-in-c11-chandy-misra-algorithm\\\/#webpage\",\"url\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2017\\\/01\\\/20\\\/dining-philosophers-in-c11-chandy-misra-algorithm\\\/\",\"name\":\"Dining philosophers in C++11: Chandy-Misra algorithm\",\"description\":\"A C++11 implementation of the Chandy-Misra algorithm for the dining philosophers problem.\",\"inLanguage\":\"en-US\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/#website\"},\"breadcrumb\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2017\\\/01\\\/20\\\/dining-philosophers-in-c11-chandy-misra-algorithm\\\/#breadcrumblist\"},\"author\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/author\\\/admin\\\/#author\"},\"creator\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/author\\\/admin\\\/#author\"},\"datePublished\":\"2017-01-20T12:05:17+02:00\",\"dateModified\":\"2017-01-20T12:05:17+02:00\"},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/#website\",\"url\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/\",\"name\":\"Marius Bancila's Blog\",\"description\":\"About code. Mostly on C++\",\"inLanguage\":\"en-US\",\"publisher\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/#organization\"}}]}\n\t\t<\/script>\n\t\t<!-- All in One SEO -->\n\n","aioseo_head_json":{"title":"Dining philosophers in C++11: Chandy-Misra algorithm","description":"A C++11 implementation of the Chandy-Misra algorithm for the dining philosophers problem.","canonical_url":"https:\/\/mariusbancila.ro\/blog\/2017\/01\/20\/dining-philosophers-in-c11-chandy-misra-algorithm\/","robots":"max-image-preview:large","keywords":"c++,c++11,mutex,philosophers,problem,synchronization,thread","webmasterTools":{"miscellaneous":""},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/mariusbancila.ro\/blog\/2017\/01\/20\/dining-philosophers-in-c11-chandy-misra-algorithm\/#article","name":"Dining philosophers in C++11: Chandy-Misra algorithm","headline":"Dining philosophers in C++11: Chandy-Misra algorithm","author":{"@id":"https:\/\/mariusbancila.ro\/blog\/author\/admin\/#author"},"publisher":{"@id":"https:\/\/mariusbancila.ro\/blog\/#organization"},"datePublished":"2017-01-20T12:05:17+02:00","dateModified":"2017-01-20T12:05:17+02:00","inLanguage":"en-US","commentCount":3,"mainEntityOfPage":{"@id":"https:\/\/mariusbancila.ro\/blog\/2017\/01\/20\/dining-philosophers-in-c11-chandy-misra-algorithm\/#webpage"},"isPartOf":{"@id":"https:\/\/mariusbancila.ro\/blog\/2017\/01\/20\/dining-philosophers-in-c11-chandy-misra-algorithm\/#webpage"},"articleSection":"C++, C++, C++11, mutex, philosophers, problem, synchronization, thread"},{"@type":"BreadcrumbList","@id":"https:\/\/mariusbancila.ro\/blog\/2017\/01\/20\/dining-philosophers-in-c11-chandy-misra-algorithm\/#breadcrumblist","itemListElement":[{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog#listItem","position":1,"name":"Home","item":"https:\/\/mariusbancila.ro\/blog","nextItem":{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/#listItem","name":"IT"}},{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/#listItem","position":2,"name":"IT","item":"https:\/\/mariusbancila.ro\/blog\/category\/it\/","nextItem":{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/#listItem","name":"Software"},"previousItem":{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog#listItem","name":"Home"}},{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/#listItem","position":3,"name":"Software","item":"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/","nextItem":{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/c\/#listItem","name":"C++"},"previousItem":{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/#listItem","name":"IT"}},{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/c\/#listItem","position":4,"name":"C++","item":"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/c\/","nextItem":{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/2017\/01\/20\/dining-philosophers-in-c11-chandy-misra-algorithm\/#listItem","name":"Dining philosophers in C++11: Chandy-Misra algorithm"},"previousItem":{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/#listItem","name":"Software"}},{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/2017\/01\/20\/dining-philosophers-in-c11-chandy-misra-algorithm\/#listItem","position":5,"name":"Dining philosophers in C++11: Chandy-Misra algorithm","previousItem":{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/c\/#listItem","name":"C++"}}]},{"@type":"Organization","@id":"https:\/\/mariusbancila.ro\/blog\/#organization","name":"Marius Bancila's Blog","description":"About code. Mostly on C++","url":"https:\/\/mariusbancila.ro\/blog\/"},{"@type":"Person","@id":"https:\/\/mariusbancila.ro\/blog\/author\/admin\/#author","url":"https:\/\/mariusbancila.ro\/blog\/author\/admin\/","name":"Marius Bancila","image":{"@type":"ImageObject","@id":"https:\/\/mariusbancila.ro\/blog\/2017\/01\/20\/dining-philosophers-in-c11-chandy-misra-algorithm\/#authorImage","url":"https:\/\/secure.gravatar.com\/avatar\/a84dd2831d955c38355ddea55df4df260809b88f36408bc14fd4eab8f7f131c9?s=96&d=mm&r=g","width":96,"height":96,"caption":"Marius Bancila"}},{"@type":"WebPage","@id":"https:\/\/mariusbancila.ro\/blog\/2017\/01\/20\/dining-philosophers-in-c11-chandy-misra-algorithm\/#webpage","url":"https:\/\/mariusbancila.ro\/blog\/2017\/01\/20\/dining-philosophers-in-c11-chandy-misra-algorithm\/","name":"Dining philosophers in C++11: Chandy-Misra algorithm","description":"A C++11 implementation of the Chandy-Misra algorithm for the dining philosophers problem.","inLanguage":"en-US","isPartOf":{"@id":"https:\/\/mariusbancila.ro\/blog\/#website"},"breadcrumb":{"@id":"https:\/\/mariusbancila.ro\/blog\/2017\/01\/20\/dining-philosophers-in-c11-chandy-misra-algorithm\/#breadcrumblist"},"author":{"@id":"https:\/\/mariusbancila.ro\/blog\/author\/admin\/#author"},"creator":{"@id":"https:\/\/mariusbancila.ro\/blog\/author\/admin\/#author"},"datePublished":"2017-01-20T12:05:17+02:00","dateModified":"2017-01-20T12:05:17+02:00"},{"@type":"WebSite","@id":"https:\/\/mariusbancila.ro\/blog\/#website","url":"https:\/\/mariusbancila.ro\/blog\/","name":"Marius Bancila's Blog","description":"About code. Mostly on C++","inLanguage":"en-US","publisher":{"@id":"https:\/\/mariusbancila.ro\/blog\/#organization"}}]},"og:locale":"en_US","og:site_name":"Marius Bancila's Blog | About code. Mostly on C++","og:type":"article","og:title":"Dining philosophers in C++11: Chandy-Misra algorithm","og:description":"A C++11 implementation of the Chandy-Misra algorithm for the dining philosophers problem.","og:url":"https:\/\/mariusbancila.ro\/blog\/2017\/01\/20\/dining-philosophers-in-c11-chandy-misra-algorithm\/","article:published_time":"2017-01-20T10:05:17+00:00","article:modified_time":"2017-01-20T10:05:17+00:00","twitter:card":"summary","twitter:title":"Dining philosophers in C++11: Chandy-Misra algorithm","twitter:description":"A C++11 implementation of the Chandy-Misra algorithm for the dining philosophers problem."},"aioseo_meta_data":{"post_id":"2357","title":"Dining philosophers in C++11: Chandy-Misra algorithm","description":"A C++11 implementation of the Chandy-Misra algorithm for the dining philosophers problem.","keywords":[{"label":"C++","value":"C++"},{"label":"C++11","value":"C++11"},{"label":"mutex","value":"mutex"},{"label":"philosophers","value":"philosophers"},{"label":"problem","value":"problem"},{"label":"synchronization","value":"synchronization"},{"label":"thread","value":"thread"}],"keyphrases":null,"primary_term":null,"canonical_url":null,"og_title":null,"og_description":null,"og_object_type":"default","og_image_type":"default","og_image_url":null,"og_image_width":null,"og_image_height":null,"og_image_custom_url":null,"og_image_custom_fields":null,"og_video":null,"og_custom_url":null,"og_article_section":null,"og_article_tags":null,"twitter_use_og":false,"twitter_card":"default","twitter_image_type":"default","twitter_image_url":null,"twitter_image_custom_url":null,"twitter_image_custom_fields":null,"twitter_title":null,"twitter_description":null,"schema":{"blockGraphs":[],"customGraphs":[],"default":{"data":{"Article":[],"Course":[],"Dataset":[],"FAQPage":[],"Movie":[],"Person":[],"Product":[],"ProductReview":[],"Car":[],"Recipe":[],"Service":[],"SoftwareApplication":[],"WebPage":[]},"graphName":"","isEnabled":true},"graphs":[]},"schema_type":null,"schema_type_options":null,"pillar_content":false,"robots_default":true,"robots_noindex":false,"robots_noarchive":false,"robots_nosnippet":false,"robots_nofollow":false,"robots_noimageindex":false,"robots_noodp":false,"robots_notranslate":false,"robots_max_snippet":null,"robots_max_videopreview":null,"robots_max_imagepreview":"large","priority":null,"frequency":null,"location":null,"local_seo":null,"breadcrumb_settings":null,"limit_modified_date":false,"ai":null,"created":"2021-03-18 21:07:10","updated":"2025-12-12 07:45:21","seo_analyzer_scan_date":null,"focus_keyword":null,"additional_keywords":null,"truseo_locale":null},"author_meta":{"display_name":"Marius Bancila","author_link":"https:\/\/mariusbancila.ro\/blog\/author\/admin\/"},"featured_img":null,"jetpack_publicize_connections":[],"uagb_featured_image_src":{"full":false,"thumbnail":false,"medium":false,"medium_large":false,"large":false,"1536x1536":false,"2048x2048":false},"uagb_author_info":{"display_name":"Marius Bancila","author_link":"https:\/\/mariusbancila.ro\/blog\/author\/admin\/"},"uagb_comment_info":3,"uagb_excerpt":"In my previous post, Dining Philosophers in C++11, I have provided an implementation for the dining philosophers problem using modern C++ features, such as threads and mutexes. However, it was noted in the comments that the implementation did not prevent the philosophers starving to death when you remove the waiting times. An algorithm that prevents&hellip;","coauthors":[],"tax_additional":{"categories":{"linked":["<a href=\"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/c\/\" class=\"advgb-post-tax-term\">C++<\/a>"],"unlinked":["<span class=\"advgb-post-tax-term\">C++<\/span>"]},"tags":{"linked":["<a href=\"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/c\/\" class=\"advgb-post-tax-term\">C++<\/a>","<a href=\"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/c\/\" class=\"advgb-post-tax-term\">C++11<\/a>","<a href=\"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/c\/\" class=\"advgb-post-tax-term\">mutex<\/a>","<a href=\"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/c\/\" class=\"advgb-post-tax-term\">philosophers<\/a>","<a href=\"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/c\/\" class=\"advgb-post-tax-term\">problem<\/a>","<a href=\"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/c\/\" class=\"advgb-post-tax-term\">synchronization<\/a>","<a href=\"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/c\/\" class=\"advgb-post-tax-term\">thread<\/a>"],"unlinked":["<span class=\"advgb-post-tax-term\">C++<\/span>","<span class=\"advgb-post-tax-term\">C++11<\/span>","<span class=\"advgb-post-tax-term\">mutex<\/span>","<span class=\"advgb-post-tax-term\">philosophers<\/span>","<span class=\"advgb-post-tax-term\">problem<\/span>","<span class=\"advgb-post-tax-term\">synchronization<\/span>","<span class=\"advgb-post-tax-term\">thread<\/span>"]}},"comment_count":"3","relative_dates":{"created":"Posted 10 years ago","modified":"Updated 10 years ago"},"absolute_dates":{"created":"Posted on January 20, 2017","modified":"Updated on January 20, 2017"},"absolute_dates_time":{"created":"Posted on January 20, 2017 12:05 pm","modified":"Updated on January 20, 2017 12:05 pm"},"featured_img_caption":"","series_order":"","jetpack_shortlink":"https:\/\/wp.me\/pYNdv-C1","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/posts\/2357","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/comments?post=2357"}],"version-history":[{"count":5,"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/posts\/2357\/revisions"}],"predecessor-version":[{"id":2362,"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/posts\/2357\/revisions\/2362"}],"wp:attachment":[{"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/media?parent=2357"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/categories?post=2357"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/tags?post=2357"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}