CMPS 3600 Lab-7 - Preventing Thread Deadlock and Starvation

Goals

resources:

Start with your 3600/7/dining.c that we wrote in class together.

   $ cd
   $ cd 3600
   $ ./lab-start.sh
   $ cd 7
   $ cp /home/fac/gordon/public_html/3600/examples/7/*.c . 
   $ cp /home/fac/gordon/public_html/3600/examples/7/Makefile . 
   $ cp /home/fac/gordon/public_html/3600/examples/7/cleanipc.sh . 
   $ ./cleanipc.sh you
   $ 
The vrlab7.c program will demonstrate that all philosophers get something
to eat. It is also a good program to demonstrate how Linux does thread
scheduling.

For this you need two terminal windows.
From one terminal window start top as follows.

  $ top -H -u username -d .5  # H to toggle your threads display to on

  • From within top hit 'f' to access the fields screen.
  • From that screen arrow to 'P' field [Last Used CPU].
  • Hit Space to toggle P on.
  • Arrow down to 'nth' [Number of Threads].
  • Hit 'Space' to toggle that on. Hit 'q'.

Jump to the second terminal window and execute:

    $ ./lab7 40

Watch what happens with top. You should see all threads spawned and joined.
You should also see the threads scheduled across multiple CPUs.

Add a new feature to vrlab7.c

Add this fibonacci function...

int fib(int n)
{
    if (n == 1 || n == 2)
        return 1;
    return fib(n-1) + fib(n-2);
}


Your lab programming assignment:
1. Add a recursive Fibonacci function to the program.
   
   Call fib from within the philosopher thread loop, to control execution speed.
   Get n for fib() from the command-line input.


2. Add command-line input to the main() function.
   Usage will be:
         Usage: ./lab7 <how many eats> <thread delay>

   These are optional command-line arguments for the user, but are required by
   the programmer.


3. Add a feature:
   (this was already done in class)
   When any philosopher is full, end all threads, and end the program.
   Full means a philosopher has eaten a given number of times.
   Get this value as the 1st command-line argument.
   For example:
       ./lab7 10 40
       This will execute lab7,
       calculate the 40th fibonacci number inside the philosopher thread loop,
       stop the program when any philosopher has eaten 10 times.

   This feature can help us to spot thread starvation happening.


4. Modify (refactor) the existing code.
   Replace the POSIX semaphores with System-V semaphores.
   Replace the POSIX Mutex with one System-V semaphore.


5. Use the wait-for-zero strategy for your semaphore grab operation.

   Find this in the sem_ctrl.c sample program.


6.  Use the POSIX mutex as an arbiter to control who gets to grab their forks. 


7. You may increase the number of philosophers.



Sample output.
Each philosopher will eat a maximum of 4 times.
Each thread will compute the 10th fibonacci number inside the thread loop.
We can see some starvation happening with the 5th philosopher (at index 4).
Increasing number of eats should reduce starvation.

$ ./lab7 4 10 0 eating 1 0 0 0 0 1 eating 1 1 0 0 0 0 eating 2 1 0 0 0 0 eating 3 1 0 0 0 3 eating 3 1 0 1 0 0 eating 4 1 0 1 0 2 eating 4 1 1 1 0 1 eating 4 2 1 1 0 3 eating 4 2 1 2 0
Files to be collected at 12:30pm...

    3600/7/vrlab7.c
    3600/7/Makefile
    3600/7/foo
    3600/7/dining.c