COS 318 : Midterm Exam 

1.       (10 points total)  Basic Concept Questions.

a)      (3 points) Explain the steps of a process context switch and tell which steps can be avoided if it is a thread context switch instead.

    Save the context of a process:

    Restore the context of a process:

The address space related context can be avoided for a thread context switch.

b)      (2 points) Explain why an OS designer needs to worry about deadlocks involving physical memory but not CPU.

Physical memory is not a preempt-able resource, whereas CPU is a preempt-able resource.  By preemptive scheduling, the OS can take CPU away from a process or thread.

c)      (3 points) Many operating systems (including ours) designed to run only on uniproccessors use disabling of interrupts to create critical sections in the code. Explain how this interrupt disabling prevents multiple threads from entering the critical section.

Suppose two threads can enter a critical section simultaneously on a uniprocessor.  Thread A gets into the critical section first.  Then the scheduler suspends thread A and run thread B.  Thread B gets into the critical section.   This is not possible because the scheduler can only be involved either by calling Yield() or a timer interrupt.  Thread A cannot call Yield() because it is in the critical section.  A timer interrupt is not possible because interrupts are disabled.

d)      (3 points) Explain whether the approach of disabling of interrupts to implementing critical sections will work on a multiprocessor.

Disabling interrupts will not work on a multiprocessor because disabling interrupts only happens on the CPU it runs.  Another thread can run on another CPU and gets into the critical section.
 

2.      (10 points)  CPU Scheduling 

a)      (5 points)There are six jobs whose expected running times are 13, 6, 3, 8, 15, and 2. In what order should they be run to minimize the average response time?  Can you explain why?

2, 3, 6, 8, 13, 15.

      Shortest Time to Completion First gives the minimal average response time.

b)     (5 points) Describe how a lottery scheduling algorithm could be made to approximate a CPU scheduling algorithm that always runs the job that hasn’t run in the longest time.

To approximate a scheduling algorithm that always runs the job that hasn’t run in the longest time, we can make a lottery scheduling algorithm do the following.  At each time slice, the scheduler takes away all tickets from the job it runs next, and gives 1 ticket  to all other jobs .  In this case, the job that hasn't run in the longest time always has the most number of tickets.

3.      (10 points) Synchronizations

Your colleague has designed a synchronization mechanism for editing multiple files simultaneously.   The goal is to maintain consistency to ensure that a user can apply edits to a number of files together.  Your colleague designed MultiLock()  to be called before an editing session and MultiUnlock)() to be called after the session:

       MultiLock( File *fileList[], int n ) {
        int i;
       
        for (i = 0; i < n; i++ )
            Acquire( fileList[i]->lock );
    }

       MultiUnlock( File *fileList[], int n ) {
        int i;
       
        for (i = 0; i < n; i++ )
            Release( fileList[i]->lock );
    }

where File is a structure that has lock as one of the field. 

Your job is to review the design and answer the following questions:

a)      Are there any issues with this design?  If there are, please provide an example to show each issue.

     The primitives above can cause deadlocks.  The following condition may cause a deadlock, user A calls
            fileList[0] = file1; fileList[1] = file2;
     MultiLock( fileList, 2 );

     after user A successfully acquired the lock of file1 but before the lock of file2,  user B calls
            fileList[0] = file2; fileList[1] = file1;
     MultiLock( fileList, 2 );

     if user B successfully acquires file2, the two users will have a deadlock.

b) If there are issues, please show, in pseudo-code, how to fix the design.

The following fix the problem mentioned above:

       MultiLock( fileList[], int n ) {
        int i; FILE sortedList[MAX];
       
        Sort( fileList, sortedList, n );
        for (i = 0; i < n; i++ )
            Acquire( sortedList[i].lock );
    }

   The primitive Sort() sorts fileList according to the value of each file descriptor and stores the results to sortedList.  There is no need to modify MultiUnlock.

4. (10 points) Monitors

A barrier is a convenient primitive to synchronize multiple threads for certain kinds of parallel programs.  When a thread reaches the barrier, it will check to see if other threads have arrived at the barrier. If one or more threads have not arrived, the thread will wait.  When all threads reach the barrier, they can begin their execution of the next phase of the computation.  An example of using a barrier is as follows:

while (true) {

  // First phase computation;

       EnterBarrier();

       // Next phase computation and use other threads’ results;

     }

There are several issues that you need to consider.   First, there is no master thread that controls the threads, waits for each of them to reach the barrier, and then tells them to restart. Instead, the threads must determine themselves when they should wait or proceed. Second, the barrier mechanism should work for many dynamic programs.   The number of threads during the lifetime of the parallel program is unknown in advance, since a thread can spawn another thread, which will start in the same program stage as the thread that created it. Third, a thread may end before the barrier. In all cases, all threads must wait at the barrier for all other threads before anyone is allowed to proceed.

Your job is to design and implement the data structure and primitive operations for barrier.  Your solution must support creation of a new thread (an additional thread that needs to synchronize), termination of a thread (one less thread that needs to synchronize), waiting when a thread reaches the barrier early, and releasing waiting threads when the last thread reaches the barrier.

You should first define the data structure of barrier and then show how to implement the following barrier primitives with Mesa-style monitor pseudo code:

·        barrier = InitBarrier();
Initialize a barrier.

·        ThreadCreated( barrier );
This primitive will be called when a thread is created.

·        ThreadEnded( barrier );
This primitive will be called when a thread terminates.

·        EnterBarrier( barrier );
Threads will call this primitive to enter a barrier.

Your solution should never busy-wait.  You will receive 0 if your solution is busy wait.  You should use only Mesa-style monitor primitives and NOT use any other synchronization primitives in your implementation. Think carefully about efficiency and avoid unnecessary looping.

struct barrier_t {
    int n;           // number of threads to wait for
    int counter;     // number of threads at the barrier
    lock_t lock;
    lond_t cond;
}

barrier_t InitBarrier(void) {
    barrier_t * b;

    b = malloc(sizeof(barrier_t));
    b->n = 0;
    b->counter = 0;
    InitMutex(b->lock);
    InitCond(b->cond);
    return b;
}

ThreadCreated( barrier_t * b ) {
    Acquire( b->lock );
    b->n++;
    Release( b->lock );
}

ThreadEnded( barrier_t * b ) {
    Acquire( b->lock );
    b->n--;
    if ( b->n == b->counter ) {
        b->counter = 0;
        Broadcast( b->cond );
        }
    Release( b->lock );
}

EnterBarrier( barrier_t * b ) {
    Acquire( b->lock );
    b->counter++;
    if ( b->n > b->counter1 )
        Wait( b->lock, b->cond );
    else {
        Broadcast( b->cond );
        b->counter = 0;
        }
    Release( b->lock );
}