\n 1\r\n 2\r\n 3\r\n 4\r\n 5\r\n 6\r\n 7\r\n 8\r\n 9\r\n10\r\n11\r\n12\r\n13\r\n14\r\n15\r\n16\r\n17\r\n18\r\n19\r\n20\r\n21\r\n22\r\n23\r\n24\r\n25\r\n26\r\n27\r\n28\r\n29\r\n30\r\n31\r\n32\r\n33\r\n34\r\n35\r\n36\r\n37\r\n38\r\n39\r\n40\r\n41\r\n42\r\n43\r\n44\r\n45\r\n46\r\n47\r\n48\r\n49\r\n50\r\n51\r\n52\r\n53\r\n54\r\n55<\/pre>\n<\/td>\n\n\/\/ dp_1.cpp<\/span>\r\n#include <iostream><\/span>\r\n#include <thread><\/span>\r\n#include <chrono><\/span>\r\n\r\nint<\/span> myrand<\/span>(int<\/span> min, int<\/span> max) {\r\n return<\/span> rand()%<\/span>(max-<\/span>min)+<\/span>min;\r\n}\r\n\r\nvoid<\/span> lock<\/span>(int<\/span>&<\/span> m) {\r\n m=<\/span>1<\/span>;\r\n}\r\n\r\nvoid<\/span> unlock<\/span>(int<\/span>&<\/span> m) {\r\n m=<\/span>0<\/span>;\r\n}\r\n\r\nvoid<\/span> phil<\/span>(int<\/span> ph, int<\/span>&<\/span> ma, int<\/span>&<\/span> mb) {\r\n while<\/span>(true<\/span>) {\r\n int<\/span> duration=<\/span>myrand(1000<\/span>, 2000<\/span>);\r\n std::<\/span>cout<<<\/span>ph<<<\/span>\" thinks \"<\/span><<<\/span>duration<<<\/span>\"ms<\/span>\\n<\/span>\"<\/span>;\r\n std::<\/span>this_thread::<\/span>sleep_for(std::<\/span>chrono::<\/span>milliseconds(duration));\r\n\r\n lock(ma);\r\n std::<\/span>cout<<<\/span>\"<\/span>\\t\\t<\/span>\"<\/span><<<\/span>ph<<<\/span>\" got ma<\/span>\\n<\/span>\"<\/span>;\r\n std::<\/span>this_thread::<\/span>sleep_for(std::<\/span>chrono::<\/span>milliseconds(1000<\/span>));\r\n\r\n lock(mb);\r\n std::<\/span>cout<<<\/span>\"<\/span>\\t\\t<\/span>\"<\/span><<<\/span>ph<<<\/span>\" got mb<\/span>\\n<\/span>\"<\/span>;\r\n\r\n duration=<\/span>myrand(1000<\/span>, 2000<\/span>);\r\n std::<\/span>cout<<<\/span>\"<\/span>\\t\\t\\t\\t<\/span>\"<\/span><<<\/span>ph<<<\/span>\" eats \"<\/span><<<\/span>duration<<<\/span>\"ms<\/span>\\n<\/span>\"<\/span>;\r\n std::<\/span>this_thread::<\/span>sleep_for(std::<\/span>chrono::<\/span>milliseconds(duration));\r\n\r\n unlock(mb);\r\n unlock(ma);\r\n }\r\n}\r\n\r\nint<\/span> main<\/span>() {\r\n std::<\/span>cout<<<\/span>\"dp_1<\/span>\\n<\/span>\"<\/span>;\r\n srand(time(nullptr));\r\n\r\n int<\/span> m1{0<\/span>}, m2{0<\/span>}, m3{0<\/span>}, m4{0<\/span>};\r\n\r\n std::<\/span>thread<\/span> t1([&<\/span>] {phil(1<\/span>, m1, m2);});\r\n std::<\/span>thread<\/span> t2([&<\/span>] {phil(2<\/span>, m2, m3);});\r\n std::<\/span>thread<\/span> t3([&<\/span>] {phil(3<\/span>, m3, m4);});\r\n std::<\/span>thread<\/span> t4([&<\/span>] {phil(4<\/span>, m4, m1);});\r\n\r\n t1.join();\r\n t2.join();\r\n t3.join();\r\n t4.join();\r\n}\r\n<\/pre>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n\n <\/p>\n The main() function<\/code> establishes random numbers in line 42. We set the random number generator seed value to the number of seconds since 1st January 1970. We define our fork resources in line 44. Then we start four threads beginning in line 46. To avoid premature thread termination, we join the threads beginning in line 51. The thread function phil()<\/code> has a forever loop. The while(true)<\/code> statement is always true<\/code>, therefore the thread will never terminate. The problem description says, “he thinks for some random duration”. First, we calculate a random duration with the function myrand(<\/code>), see line 20 and line 6. The function myrand()<\/code> produces a pseudo-random return value in the range of [min, max). For program trace, we log the philosopher’s number, his current state of “he thinks,” and the duration to the console. The sleep_for()<\/code> statement lets the scheduler put the thread for the duration into the waiting state. In a “real” program application, source code uses up time instead of sleep_for()<\/code>.After the philosopher’s thread thinking time ends, he “gets his first fork”. See line 24. We use a function lock()<\/code> to perform the “gets fork” thing. Currently, the function lock()<\/code> is very simple because we don’t know better. We just set the fork resource to the value 1. See line 10. After the philosopher thread obtained his first fork, he proudly announces the new state with a.”got ma<\/code>” console output. Now the thread “gets his second fork”. See line 28. The corresponding console output is “got mb<\/code>“. The next state is “he eats<\/code>“. Again, we determine the duration, produce a console output, and occupy the thread with a sleep_for()<\/code>. See line 31. After the state.”he eats<\/code>” the philosopher puts down his forks. See lines 35 and 14. The unlock()<\/code> function is again really simple and sets the resource back to 0.<\/p>\nPlease compile the program without compiler optimization. We will see the reason later. The console output of our program looks promising:<\/p>\n ![\"dp](\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2022\/01\/dp_1.png\") <\/p>\n<\/div>\n \n Have we already solved the dining philosophers’ problem? Well, the program output is not detailed enough to answer this question.<\/p>\n Multiple Resource Use with Logging<\/h2>\nWe should add some more logging. Currently, the function lock()<\/code> does not check if the fork is available before the resource is used. The improved version of lock()<\/code> in program dp_2.cpp<\/code> is:<\/p>\n<\/div>\n<\/p>\n \n void<\/span> lock<\/span>(int<\/span>&<\/span> m) {\r\n if<\/span> (m) {\r\n std::<\/span>cout<<<\/span>\"<\/span>\\t\\t\\t\\t\\t\\t<\/span>ERROR lock<\/span>\\n<\/span>\"<\/span>;\r\n }\r\n m=<\/span>1<\/span>;\r\n}\r\n<\/pre>\n<\/div>\n <\/p>\n \n Program version 2 produces the following output:<\/div>\n <\/div>\n ![\"dp](\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2022\/01\/dp_2.png\") <\/div>\n <\/p>\n<\/div>\n \n We see “ERROR lock<\/code>” console output. This output tells us that two philosophers use the same resource simultaneously. What can we do?<\/p>\nErroneous Busy Waiting without Resource Hierarchy<\/h2>\nWe can change the if statement in lock()<\/code> into a while statement. This while statement produces a spinlock. A spinlock is a fancy word for busy waiting. While the fork resource is in use, the thread is busy waiting for a change from the state in use to the state available. At this very moment, we set the fork resource again to state in use. In the program, dp_3.cpp<\/code> we have:<\/p>\n <\/p>\n<\/div>\n <\/p>\n \n void<\/span> lock<\/span>(int<\/span>&<\/span> m) {\r\n while<\/span> (m)\r\n ; \/\/ busy waiting<\/span>\r\n m=<\/span>1<\/span>;\r\n}\r\n<\/pre>\n<\/div>\n <\/p>\n \n Please believe that this little change is still not a CORRECT solution for the dining philosophers’ problem. We no longer have the wrong resource usage. But we have another problem. See program version 3 output:<\/div>\n <\/p>\n ![\"dp](\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2022\/01\/dp_3.png\") <\/div>\n \n \n <\/p>\n Every philosopher thread takes his first fork resource and then can not take the second fork. What can we do? Andrew S. Tanenbaum wrote, “Another way to avoid the circular wait is to provide a global numbering of all the resources. The rule is this: processes can request resources whenever they want to, but all requests must be made in numerical order.” [ref 2006; Tanenbaum; Operating Systems. Design and Implementation, 3rd edition; chapter 3.3.5]<\/p>\n Erroneous Busy Waiting with Resource Hierarchy<\/h2>\nThis solution is known as resource hierarchy or partial ordering. For the dining philosopher’s problem, partial ordering is easy. The first fork taken has to be the fork with the lower number. For philosophers 1 to 3, the resources are taken in the correct order. Only philosopher thread 4 needs a change for correct partial ordering. First, get fork resource 1, then get fork resource 4. See the main program in the file dp_4.cpp<\/code>:<\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/p>\n \n int<\/span> main<\/span>() {\r\n std::<\/span>cout<<<\/span>\"dp_4<\/span>\\n<\/span>\"<\/span>;\r\n srand(time(nullptr));\r\n\r\n int<\/span> m1{0<\/span>}, m2{0<\/span>}, m3{0<\/span>}, m4{0<\/span>};\r\n\r\n std::<\/span>thread<\/span> t1([&<\/span>] {phil(1<\/span>, m1, m2);});\r\n std::<\/span>thread<\/span> t2([&<\/span>] {phil(2<\/span>, m2, m3);});\r\n std::<\/span>thread<\/span> t3([&<\/span>] {phil(3<\/span>, m3, m4);});\r\n std::<\/span>thread<\/span> t4([&<\/span>] {phil(4<\/span>, m1, m4);});\r\n\r\n t1.join();\r\n t2.join();\r\n t3.join();\r\n t4.join();\r\n}\r\n<\/pre>\n<\/div>\n <\/p>\n \n Program version 4 output looks fine:<\/div>\n <\/div>\n ![\"dp](\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2022\/01\/dp_4.png\") <\/div>\n \n \n <\/div>\n Now there is no longer wrong resource usage nor do we have a deadlock. We get brave and use compiler optimization. We want to have a good program that executes fast! This is program version 4 output with compiler optimization:<\/p>\n ![\"dp](\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2022\/01\/dp_4opt.png\") <\/div>\n<\/div>\n<\/div>\n<\/div>\n \n <\/div>\n It is always the same philosopher thread that eats. Is it possible that the setting of compiler optimization can change the behavior of a program? Yes, it is possible. The philosopher threads read from memory the value of fork resource. The compiler optimization optimizes some of these memory reads away. Everything has a price!<\/p>\n Still Erroneous Busy Waiting with Resource Hierarchy<\/h2>\nThe programming language C++ has the atomic template to define an atomic type. The behavior is well-defined if one thread writes to an atomic object while another reads from it. In the file dp_5.cpp<\/code> we use | | ![\"An](\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2022\/01\/An_illustration_of_the_dining_philosophers_problem.png\")
<\/p>\n