COS 318: Midterm Exam and Suggested Solutions (October 21, 2004)

 

 

1.      (10 points) Processes and threads.

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

Lower overhead of context switch.

Easier to share data.


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


            A parallel application such as a parallelized matrix-multiply running on a shared memory multiprocessor.

 

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

The crash of a process may not affect other processes, since they have separate address spaces.  The crash of a thread often crashes other threads in the same address space.

Processes can have different privileges whereas threads in the same address spaced share the same privilege.


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

            A sequential program.

 

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

 

            User-level threads have a scheduler running at the user level whereas the kernel threads have one at the kernel level.

 

User-level threads in the same address space will block on an I/O even whereas kernel threads will not.

 

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

      Low context-switch overhead is important and there is not much

overlapping between CPU and I/O.


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

 

      Overlapping between CPU and I/O are important and low context-switch overhead is not.

 

 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?

    (16 + (16 – 0.3 + 5) + (21 – 1 + 3)) / 3 = 19.9

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

    (16 + (16 – 1 + 3) + (19 – 0.3 + 5)) / 3 = 19.23

  • (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.

    (3 + (4 – 0.3 + 5) + (9 + 16)) / 3 = 12.23

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.

n (n-1) … (1) = 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.

 

            To approximate SRTF, give short running jobs more tickets and long running jobs fewer tickets.

 

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.


typedef struct {

  Lock lock;
  Condition full, empty;
  int count;
  int head; 
  int tail;
  char msgs[ 100 ][MAX_MSG_SIZE ];
  char sizes[ 100 ];

  } Mbox;









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

    void send( Mbox mbox, char msg[], int size )
    {
      lock_acquire( &mbox.lock );
      while ( mbox.count >= 100 )
        condition_wait( &mbox.lock, &mbox.full );

      strncpy( &mbox.msgs[mbox.head], msg, size );
      mbox.sizes[mbox.head] = size;
      mbox.head = (mbox.head + 1) % 100;
      mbox.count++;

      condition_signal( &mbox.empty );
      lock_release( &mbox.lock);
    }

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

int receive( Mbox mbox, char msg[], int n )
{
  lock_acquire( &mbox.lock );
  while ( mbox.count == 0 )
    condition_wait( &mbox.lock, &mbox.empty );

  if ( mbox.sizes[mbox.tail] < n )
    n = mbox.sizes[mbox.tail];

  strncpy( msg, &mbox.msgs[mbox.tail], n );
  mbox.tail = (mbox.tail + 1) % 100;
  mbox.count--;

  condition_signal( &mbox.full );
  lock_release( &mbox.lock);

 

  return n;
}
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.

    Problem 1:     tapedrive[i].state was never set to USED or BUSY.

    Problem 2:     tapedrive[i].lock is locked in get_tape_drive(), but never released.

    Problem 3:     Variable count is shared among clone-worker threads, but not protected.

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

 

int get_tape_drive(void) {

  int i, drive = -1;

  lock_acquire(tape_lock);
  for (i=0; i<12; i++)
    if (tapedrive[i].state == FREE) {
      tapedrive[i].state = USED;

      drive = i;

      break;
    }

  lock_release(tape_lock);

  return drive;

}

 

void free_tape(int i) {
  lock_acquire(tape_lock);
  tapedrive[i].state = FREE;

  lock_release(tape_lock);
}

 

void clone_worker(void) {

  int i, src = -1, dest = -1;

  while ( src < 0 ) src = get_tape_drive();

  while ( dest < 0 ) dest = get_tape_drive();

 

  while ( count >= 0 ) {

    lock_acquire( count_lock );
    if ( count >= 0 ) {
      i = count;
      count--;
    }

    lock_release( count_lock );                
    clone(src, dest, backup_tapes[i], blanks[i]);
  }
  free_tape(src);
  free_tape(dest);