COS 318: Midterm Exam (October 21, 2004)

 

1.      (10 points) Processes and threads.

a)      (2 points) Provide two advantages of threads over multiple processes.

 

 

 



b)      (1 point) Suggest an application that would benefit from the use of threads.

 

 

 

c)      (2 points) Provide two disadvantages of threads over multiple processes.

 

 

 



d)       (1 point) Suggest an application that would not benefit from the use of threads.

 



e)      (2 points) What are the two main differences between user-level threads and kernel-supported threads?

 

 

 

 

 

f)        (1 point) Provide a situation that user-level threads are better than kernel-supported threads.

 



g)      (1 point) Provide a situation that user-level threads are worse than kernel-supported threads.

 

 

 2.      (10 points)  CPU Scheduling

a)       (6 points) Suppose that the following processes arrive for execution at the times indicated.  Each process will run the listed amount of time.  In answering the questions, use non-preemptive scheduling and base all decisions on the information you have at the time when the decision must be made. 

Process

Arrival Time (sec)

Running Time (sec)

P1

0.0

16

P2

0.3

5

P3

1.0

3

 

  • (2 points) What is the average turnaround time for these processes with the FCFS scheduling algorithm?



  • (2 points) What is the average turnaround time for these processes with the STCF scheduling algorithm?


 

  • (2 points) The STCF algorithm is supposed to improve performance, but notice that we chose to run process P1 at time 0.0 second because we did not know that shorter processes would arrive soon.  Compute what the average turnaround time will be if the CPU is left idle for the first 1 second and then STCF is used.



b)     (2 points) Suppose that there are n processes in the ready queue to be scheduled on one processor.  How many possible different schedules are there?  Give a formula in terms of n.



c)       (2 points) Describe how a lottery scheduling algorithm could be made to approximate a non-preemptive CPU scheduling algorithm that achieves the shortest average turnaround time.

 

           

 

 

3.      (10 points) Message passing and synchronization
In the lecture, we have discussed about a mailbox abstraction for message passing.   Your job is to sketch the kernel implementation of a mailbox for inter-process communication within the same machine.  You should use the Mesa-style monitor to implement the synchronizations in the send and receive operations.    Note that the grading will focus on synchronization related code; you do not need to work hard on other details.

  • (2 points) Define the data structure of a mailbox Mbox with a buffer of 100 messages and other necessary fields.



 

 






  • (4 points) Provide the implementation of
    void send( Mbox mbox, char msg[], int size );


 

 

 

 

 

 

 

 

 



  • (4 points) Provide the implementation of
    int receive( Mbox mbox, char msg[], int n)
    This call returns the number of bytes received.

4.       (10 points) Deadlocks and Synchronization
Consider a tape library with 12 tape drives at OIT.  In order to clone backup tapes to send the duplicates to offsite for disaster recovery, OIT hired a summer intern to write a utility program to clone backup tapes.  The goal is to use all 12 tape drives if they are available to maximize the throughput of cloning tapes.   You are an expert in deadlocks and synchronization.   Your consulting job is to review the core portion of the code written by the summer intern to find what parts do not work.    

 

...
static int count = N;    /* number of tapes to be cloned */
void utility(void)
{
  thread_T t[6];

  int i;
 
  for (i=0; i<6; i++)
    t[i] = thread_create(clone_worker);

  for (i=0; i<6; i++)
    thread_join(t[i]);
  printf( “cloning completes.\n” );
}

 

int get_tape_drive(void) {

  int i, drive = -1;

  while (drive < 0)
    for (i=0; i<12; i++)
      if (tapedrive[i].state == FREE) {         /* problem 1 */

        lock_acquire(tapedrive[i].lock);     /* problem 2 */

        drive = i;

        break;
      }

  return drive;

}

 

void clone_worker(void) {

  int i, src, dest;

  src = get_tape_drive();

  dest = get_tape_drive();

 

  while( count >= 0 ) {                    /* problem 3 */
    clone(src, dest, backup_tapes[count], blanks[count]);
    count--;
  }
}


  • (3 points)  Identify and explain what parts do not work.


 

 

 

 



  • (7 points)  Fix the parts that do not work.