Correct solution of the Dining Philosophers problem
Split SPLIT_ID

CS 300, Parallel and Distributed Computing (PDC)
Due Monday, October 8, 2018

Laboratory exercises

The goal of this lab is to implement at least one of the solutions to the Dining Philosophers problem discussed in class.

Log into an admin node for a cluster, and create subdirectories ~/PDC/lab4, then change into the lab4 subdirectory.

In order to manage the code in the SyncServer class more easily, refactor your synchronization server (i.e., rewrite that code to have a better design) as follows.

1. Copy dp.h from your lab3 subdirectory to your lab4 subdirectory, then delete the keyword static before the run() method of the class SyncServer. This makes run() an instance method instead of a class method.

   Test this modified version of dp.h by copying a running version of dp.cpp from the previous lab, and modifying the copy as follows.

   • In the code for the synchronization server machine, replace the class-method call SyncServer::run() by a call of the instance method run() for a SyncServer object:

     SyncServer ss;
     ss.run();
     

   Then compile and run dp.cpp, and verify that it operates as it did before.

   Create a commit recording this work as follows:

   cumulus$  cp dp.cpp dp1.cpp
   cumulus$  cp dp.h dp1.h
   

   cumulus$  git add {dp,dp1}.{cpp,h} 
   cumulus$  git commit -m "lab4: SyncServer::run as an instance method"
   

2. Make buff[] a state variable of SyncServer, instead of just a local variable in main(), so all SyncServer methods will be able to access it.

   Test your code to see that it still runs correctly, perhaps using a program similar to the first simple test you wrote for Sync.h in the previous lab.

3. Write a method do_quit(int source) for carrying out the following actions when a QUIT message is received:

   char msg[] = "bye";
   MPI_Send(msg, strlen(msg), MPI_CHAR, status.MPI_SOURCE, ACK, MPI_COMM_WORLD);
   cout << "Shutting down MPI_COMM_WORLD" << endl;
   MPI_Abort(MPI_COMM_WORLD, MPI_SUCCESS);
   

   Now, replace the code for the QUIT case by the following:

   case QUIT: 
     do_quit(status.MPI_SOURCE);
     return 0;
     break;
   

   Note: A helper method like do_quit() is sometimes called a handler or callback for QUIT messages.

4. Also replace the body of the PRINT case by a call to a three-line class method do_print(int source), followed by that case's break;. Test that the code still works after these changes.

5. Proceed to replace the bodies of cases for ECHO, GETCHOP, GETCHOP_BLOCKING, and PUTCHOP by calls to new callback methods, one for each of those operations.

   In the case of PUTCHOP, GETCHOP, and GETCHOP_BLOCKING, convert the array chop[] into a state variable.

If you add new services to the class SyncServer in the future, use this callback approach to keep the code well organized.

Create a commit recording this work as follows:

cumulus$  cp dp.cpp dp2.cpp
cumulus$  cp dp.h dp2.h

cumulus$  git add {dp,dp2}.{cpp,h} 
cumulus$  git commit -m "lab4: Refactor SyncServer to use handler methods"

---

[The remainder of this lab is optional for Section B.]

Algorithm 1: Waiter solution.

Here are some suggestions for the implementation.

1. Start with a copy wdp.cpp of your deadlock.cpp from the previous lab, and make a copy wdp.h of your refactored dp.h (for this lab). Also modify wdp.cpp to #include the file wdb.h instead of db.h.

2. Now change the callback SyncServer::do_getchop_blocking() to act as the waiter. That callback should:

   • allow a requesting philosopher to obtain a chopstick c if at least two chopsticks remain unallocated, including c, in the array chop[],

   • allow a requesting philosopher to obtain its right chopstick even if that is the last unallocated chopstick,

   • (optional) allow a requesting philosopher to obtain its left chopstick c if some other philosopher currently possesses both of its chopsticks, as indicated in the array chop[], even if c is the last unallocated chopstick, and

   • otherwise refuse to allocate the chopstick c (i.e., if c is already allocated or c was the last unallocated chopstick in an "unsafe" state).

   Test these changes using wdp.cpp (whose only change is one header file).

   Create a commit recording this work as follows:

   cumulus$  cp wdp.cpp wdp1.cpp
   cumulus$  cp wdp.h wdp1.h
   

   cumulus$  git add {wdp,wdp1}.{cpp,h} 
   cumulus$  git commit -m "lab4: Implement the waiter in SyncServer::do_getchop_blocking()"
   

3. Add an integer state variable freechops, initialized at the total number of chopsticks, to the class SyncServer in wdb.h. freechops has the following invariant: At all times, freechops holds the number of unallocated chopsticks in chops[].

   To maintain the invariant for freechops (i.e., that it holds the number of unallocated chopsticks), be sure to subtract 1 from freechops every time do_getchop() allocates any chopstick, and add 1 to freechops every time do_putchop() deallocates any chopstick. The purpose of freechops is to avoid having to count unallocated chopsticks in a loop within do_getchop() every time the waiter do_getchop() considers whether to allocate a free chopstick.

   Create a commit recording this work as follows:

   cumulus$  cp wdp.cpp wdp2.cpp
   cumulus$  cp wdp.h wdp2.h
   

   cumulus$  git add {wdp,wdp2}.{cpp,h} 
   cumulus$  git commit -m "lab4: Maintain counter freechops in SyncServer"
   

---

Algorithm 2: Chandy-Misra's solution. (OPTIONAL)

Design and implement the Chandy-Misra solution to the Dining Philosophers problem, described in Correct solution of the Dining Philosophers problem.

---

cumulus$  git commit --amend

    lab4: complete

cumulus$  git pull origin master
cumulus$  git push origin master

mist$  cd ~/PDC
mist$  git pull origin master
mist$  git add -A
mist$  git commit -m "Lab 4 submit (mist)"
mist$  git push origin master