Homework 6
			 DUE:  Tuesday, Apr. 2

CLARIFICATIONS:  (Added Tuesday, April 2)
  Based on office hours, here are some points that I hope clarify hw6.
  Part 1:  The lesson is that even if each philosopher eats only
           once, there might still be deadlock.  Show a trace (scenario)
           where the deadlock happens.
  Part 2:  The lesson is that if we add a "ONE BIG LOCK"
           _in addition_ to the mutex locks around each fork,
           then we will no longer see deadlock.  In order to show this,
           change the given file, mc-philosophers-deadlock.c,
            (a) to add the "ONE BIG LOCK"; and
            (b) to make each philosopher either eat many times (e.g., 100),
                or else to eat infinitely many times (adding 'while (1)').
            (c) If you choose 'while (1)', you should interrupt
                   ./part2-philosophers > output2.txt
                after a few minutes.  But the printf() call
                is actually saving all your output, and it will
                push the output only when the output is really large.
                To fix this, add 'fflush(stdout);' immediately
                after each call to 'printf(...);'.
  Part 3:  The lesson is that "ONE BIG LOCK" is inefficient.
           If one philosopher is eating, a philosopher at the
           other end of the table has to wait.  To make the program faster,
           we replace the "ONE BIG LOCK" with a semaphore that
           allows all _except_ one of the philosophers (NUM_THREADS - 1)
           to eat simultaneously.  Now, if there is a threat of
           a deadlock, we can look at the philosopher who is not eating.
           One of his/her neighbors should already have one fork,
           and they can then grab a second fork from the philosopher
           who is not eating.

In this homework, you will practice using mutexes (mutual exclusion)
to create critical sections in your code where only one thread may
execute at a time.  This will allow you to safely use variables that
are shared among multiple threads.  You will also write an improved
solution using semaphores.

The concepts to be covered in this homework and the next one are subtle.
In order to better understand the concepts, please carefully review the
course lectures and the corresponding sections in the "Concurrency"
section of the textbook, ostep.org.  The appropriate sections from
ostep.org are listed in the syllabus.  Note also my own lecture
notes on threads, provided at: 
  https://course.ccs.neu.edu/cs3650/parent/thread-synch/

You will solve the dining philosopher problem.  The dining philosopher
problem is stated in this Wikipedia article:
  https://en.wikipedia.org/wiki/Dining_philosophers_problem
(I sometimes refer to the utensils as chopsticks, but Wikipedia is
correct in stating that the original formulation required each
philosopher to use two forks.)

This homework has three parts:

In Part 1, you will analyze the given naive solution (with mutexes)
for Dining Philosophers, which could deadlock due to a race condition.
When you run the given naive solution, it appears to work, and the
deadlock is not exhibited.  You will then examine the code, and you
will describe (in a text file) how deadlock can still occur.

In Part 2, you will write a correct solution to Dining Philosophers,
still using mutexes.

In Part 3, you will implement an alternative solution to Dining
Philosophers, using semaphores.


======================
PART 1: Dining Philosophers (using mcmini model checker)
        [ We will not use the mcmini model checker until the next hw. ]

  1. Read the "naive" code in test/mc-philosophers-deadlock.c.
     Observe that there is a clear deadlock possible.
  2. Make the executable:  (cd test && make mc-philosophers-deadlock)
     Run the executable:   ./test/mc-philosophers-deadlock
     ( Observe that this succeeds on login at Khoury, with all three
       philosophers managing to eat.  We don't see any deadlock. )

  Then, please include in your text file a brief description in which you
  explain in plain English a deadlock scenario.  Explain which resources
  are held by which threads, and for each thread, what mutex will it
  block at next if it tries to continue executing.

======================
PART 2: Dining Philosophers (using mutexes correctly)

In Part 2, you must fix the bug in Dining Philosophers using mutexes.
Your solution must work for num_threads set to 6 or less.  The solution
must allow more than one philosopher to potentially eat at the same time.

SUGGESTED DESIGN:
  Create a global mutex that is visible to all philosophers.  If a
  philosopher wants to eat, insist that the philosopher should acquire the
  global mutex before acquiring the the mutexes for the left and right
  fork.  It should then release the global mutex before it eats (so that
  another philosopher can attempt to eat at the same time).

======================
PART 3: Dining Philosophers (using semaphores)

The problem of the dining philosophers occurs only when all
philosophers try to eat at the same time.  So, we can avoid
deadlock if we can guarantee that for N philosophers, no more
than N-1 philosophers are allowed to dine at the same time.

Add to the dining philosophers program some code that adds a
semaphore, 'sem_t sem_dining;'.  It will have the English meaning
of the number of philosophers allowed to dine in parallel.
If we assume NUM_THREADS philosophers, then we should initialize
'sem_dining' to NUM_THREADS-1.  Before a philosopher can try to grab
any fork, it must first do a sem_wait on 'sem_dining', and it
must call 'sem_post' when it is done dining.

MOTIVATION (WHEN IS THIS ALTERNATIVE SOLUTION BETTER?):
  This solution is more efficient than the one using a global mutex.
  The problem with the previous solution is that if philosopher A is
  eating, then philosopher B will succeed in acquiring the global mutex.
  But philosopher B will then try to acquire its left fork, and it will
  have to wait until philosopher A is finished eating.  In the meantime,
  no other philosopher can begin to eat, because they must first acquire
  the global mutex, and philosopher B is still holding the global mutex.

======================
HAND IN:  hw6
By the due date, you will have to submit these things in your .tar.gz file:
 1. your source code (e.g., part2-philosophers-mutex.c,
    part3-philosophers-sem.c, etc.)
 2. a working Makefile;  The Makefile must have a 'check' target.
      The 'check' target must include a dependency containing the executables
      for your C programs, and it must include separate targets to
      compile your C programs into executables.
      The actions of the Makefile must be to run (execute) your
      "Part 2" C program, and then your "Part 3" C program.
 3. A README file:  As usual, what works or doesn't work?
 4. the output of running your programs on a computer with at least
      6 cores (e.g., Khoury's login), to show correct behavior.
      An easy way to do this might be:  ./philosophers > output.txt
      If you'd like to monitor the progress, try:
        ./philosophers | tee - > output.txt
 5. part1.txt (the output for Part 1:  Show a scenario (a thread trace)
      describing the order of thread operations that can produce deadlock.
      Explain why the trace leads to deadlock.

Place all of your files in a subdirectory, hw6.
Then:
  tar cvf hw6.tar ./hw6
  gzip hw6.tar
Or simply:
  tar zcvf hw6.tar.gz ./hw6
Then:
  /course/cs3650/homework/submit-cs3650-hw6 hw6.tar.gz