CS 481:  Operating System Principles



               Assignment # 6:  Due Date =  11/06/98



1. The following is a proposed solution to the Database access problem
   (Readers/Writers problem), with writers having priority over readers
   i.e. a writer gets priority over readers that have arrived before
   it but existing readers are not preempted. 
   For example, if the (i+1)th writer arrives while the ith writer 
   is writing and after one or more readers (who are queued), then
   on completion of the ith writer, the (i+1)th writer should be
   allowed access next. 

   Determine if the following program is buggy. If so, specify an exact
   sequence of reader and writer arrivals and their progress leading to
   deadlock and/or starvation and/or violation of policy.


     WRITER CODE:
  
                wait(y);
                  wcount++;
                  if (wcount == 1) wait(rsem);
                signal(y);
                wait(wsem);
       
                    W
                    R
                    I
                    T
                    E

                signal(wsem);
                wait(y);
                   wcount--;
                   if (wcount == 0) signal(rsem);
                signal(y);  




     READER CODE:


                wait(rsem);
                   wait(z);
                       rcount++:
                       if (rcount == 1) wait(wsem);
                   signal(z);
                signal(rsem);

                      R
                      E
                      A
                      D

                wait(z);
                   rcount--;
                   if (rcount == 0) signal(wsem);
                signal(z):




2. Consider the following solution to the Dining Philosophers Problem.
   Study the code carefully and determine if it works and if it
   guarantees freedom from deadlock and starvation.
   

   
   semaphore s[i];
   semaphore mutex;
   enum PhilosopherState {thinking, hungry, eating};
   PhilosopherState state[5];


         philosopher(int i) {
            while (1) {
                think();
                take_forks(i);
                eat();
                put_forks(i);
            }
         }


         take_forks(int i) {
            wait(mutex);
            state[i] = hungry;
            test(i);
            signal(mutex);
            wait(s[i]);
         }


        put_forks(int i) {
            wait(mutex);
            state[i] = thinking;
            test((i-1)%5);
            test((i+1)%5);
            signal(mutex);
        }
  
 
        test(int i) {
            if (state[i] = hungry 
                && state[(i+1)%5] != eating
                && state[(i-1)%5] != eating) {
                      state[i] = eating;
                      signal(s[i]);
            }
        }