Homework 4

22C:116, Spring 1999

Due Friday Feb 19, 1999, in class

1. Background: The dining philosopher's problem is the basis of the cover illustration on Tannenbaum's text and it is discussed, at length, on pages 57 to 59 of the text. There are many solutions to this problem!

   Consider the following implementation of the think() operation for use under our example thread package:

   void think()
   {
       int i;
       do {
           thread_relinquish();
       while (random() & 7);
   }
   

   Problem: Use our thread manager to implement the solution given by Tannenbaum, using the above version of think.

2. Consider a system with a disk that has 64 cylinders shared by 5 users behaving as described by the following code:

   void user( int n )
   {
       int i;      /* count of disk operations */
       int cyl;    /* selected cylinder */
       struct thread_semaphore done;
       thread_semaphore_init( &done, 0 );
       cyl = (int)random();
       for (i = 1; i <= n; i++) { /* do n disk operations */
           while (random() & 3) thread_relinquish(); /* take some time */
           if (((random() & 3) == 0)) cyl = (int)random();
           cyl = cyl & 63;
           enqueue( cyl, &done ); /* post one disk request */
           thread_wait( &done );
       }
   }
   

   The disk service routine can be simulated by the following:

   void disk( int n )
   {
       int cyl = 0; /* cylinder number */
       int ocyl;    /* old cylinder number */
       int diff;    /* difference cylinder numbers */
       int i,j;     /* loop counters */
       int time = 0;/* a measure of the total time taken */
       struct thread_semaphore * done;
   
       for (i = 0; i < n; i++) {
           ocyl = cyl;
           dequeue( &cyl, &done );
           diff = cyl - ocyl;
           if (diff < 0) diff = -diff;
           for (j = 0; j <= diff; j++) {
               thread_relinquish();
               time++;
           }
           thread_signal( done );
       }
       printf( "time = %d\n", time );
   }
   

   The parameters to each thread indicate the number of iterations before termination of the simulation run. The routines enqueue() and dequeue() access the disk request queue and completely encapsulate the disk scheduling code.

   Part A: Write a program incorporating 5 user threads and one disk thread, where the disk queue is FIFO and each user enqueues 20 disk requests. Arrange things so that the program outputs the value of the disk thread's time variable as it terminates.

   Part B: Modify your code from part A so it uses the elevator algorithm, and report how this improves its performance.