Correct solution of the Dining Philosophers problem

CS 300, Parallel and Distributed Computing (PDC)
Due Monday, January 12, 2015

Preliminary material

• Correct solutions to Dining Philosophers

Laboratory exercises

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

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

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

   1. Copy Sync.h 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 Sync.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.

   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.

   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.

3. Algorithm 1: Waiter solution.

   Here are some suggestions for the implementation.

   1. Start with a copy wdp.cpp of your dp.cpp deadlock.cpp from the previous lab, and make a copy WSync.h of your refactored Sync.h. Also modify wdp.cpp to #include the file WSync.h instead of Sync.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).

   3. Add an integer state variable freechops, initially zero, to the class SyncServer. 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.

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

   Design and implement the Chandy-Misra solution to the Dining Philosophers problem.

Deliverables

    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

See lab1 Deliverables section if you need to set up the cluster you used for git.

If you did your work on two different clusters, submit work from both of them using one of the strategies in lab1 Deliverables.

This lab is due by Monday, January 12, 2015.

rab@stolaf.edu, January 12, 2015