COS 318: Suggested Solution to Midterm Exam

 

1.  Short Questions (10 points)

1.1      (5 points) Answer the following questions with “True” or “False”.  Then use exactly one sentence to describe why you chose your answer.  Without stating the reasoning, you will not get any points.

·         The code that changes the system clock runs in user mode.

False.  It requires a privileged instruction to change the clock.

·         Without kernel-level support, when a user-level thread blocks, it will block all the other threads in the same process.

True.  When a user-level thread blocks on an I/O operation, the kernel takes control to run another process.

·         Context switching between two kernel threads has about the same overhead as that between two user processes.

False.  A context switch between two user processes require crossing the protection boundary twice, whereas a context switch between two kernel threads does not require crossing the protection boundary.

·         A thread can be blocked on multiple condition variables simultaneously.

False.  In a monitor, there is no primitive that allows a thread to wait on two condition variables.

·         A device driver call is a kind of system call in the Unix operating system.

False.  A device driver call is a kernel call that is not available for applications to call directly, whereas a system call is.

 

1.2       (5 points) Use no more than 3 sentences to concisely answer each of the following questions.

·         (2 points) Priority scheduling allows processes or threads with higher priority to run before those with lower priority.  Some operating systems (e.g. Unix) allow priorities to be dynamically adjusted.  Explain the main reason why they do not simply use statically assigned priorities.

 

The main reason is that it is impossible for a scheduler to distinguish I/O-intensive processes from CPU-intensive ones. Thus, in order to run I/O-intensive processes at higher priorities to increase the chance to overlap I/O processes with CPU processes, Unix raises the priority of a process when it is doing an I/O operation.  With statically assigned priorities, it is not possible for the scheduler to achieve this goal. 

 

·         (3 points) When the operating system initiates a DMA operation to transfer the data in a kernel buffer to an I/O device controller’s buffer, the data can be transferred without CPU’s further help.  However, it is possible that the CPU modified the data in the kernel buffer right before the DMA operation. Since most of the L2 cache implementations on modern CPUs use write-back policies, the DRAM of the kernel memory may still have the old data at the time of initiation of the DMA operation.  Explain why or why not the operating system for modern CPUs needs to worry about the consistency between the L2 cache and DRAM for such DMA transfers.

 

There is no need to worry about the consistency between the L2 cache and DRAM for such DMA transfers, because modern processors maintain such consistency as part of the cache consistency protocol.  An alternative is to invalidate or flush the related L2 cache blocks before a DMA operation is initiated.  This approach requires a special privileged instruction and needs more complex hardware to implement.

 

2      CPU Scheduling (10 points)

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

Processes

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 under 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 under 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. However, notice that we chose to run process P1 at time 0.0 second because we did not know that shorter-running processes would arrive soon.  Compute what the average turnaround time would be if the CPU were left idle for the first 1 second and then STCF were used.

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

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

n (n-1) … (1) = n!

 

2.3       (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      Deadlocks (10 points)

 

3.1         (5 points) In lecture, we talked about spooling as a method to eliminate deadlocks when using printers, tapes and other I/O devices.  Can spooling be used to eliminate deadlocks when using resources such as CPU, memory and disk space?  Why or why not?

No, spooling cannot be used to eliminate deadlocks for CPU, memory and disk resources.  For CPU, spooling does not help since CPU is a preemptive resource.  CPU virtualization can be achieved by scheduling among processes or by implementing a virtual machine monitor.  Memory and disk resources are random access storage that are sometimes used to store shared data.  Spooling cannot eliminate deadlocks of shared data.   For example, Process P holds memory pages that are required by process Q, while process Q is holding the CPU that is required by P.  The best way is to use preemption method to eliminate deadlocks.

 

3.2      (5 points) Consider a system consisting of m resources of the same type, being shared by n processes.  Resources can be requested and released by processes only one at a time.  Show that the system is deadlock-free if each process needs at most m resources and the sum of all needs is less than m + n.

 

Suppose that maxi, needi, and alloci are the maximum, needed and allocated resources of process i respectively.  Then, we have the following:

 

(a) 

(b)  for all ,

          Since , if there is a deadlock, then

(c) 

 

But,  (see (a))

or,

or,

This implies that there exists process such that  But,  (see (b)).
There is a contradiction.

4. Monitor and Message Passing (10 points)

 

In lecture, we discussed 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 are asked to first define the data structure of the mailbox object Mbox and then show the implementations of four primitives:

·         Mbox Open(int n): Open mbox with n messages.

·         Close(Mbox mbox): Close mbox.

·         Send(Mbox mbox, char buffer[], int size):

Send a message to mbox.  The message is in buffer in size bytes.

·         int Recv(Mbox mbox, char *buffer):

Receive a message from mbox and put the result in buffer and return the size of the message.

You should use the Mesa-style monitor to implement the synchronization in the send and receive operations. Note that the grading will focus on synchronization related code; there is no need to work hard on other details.

 

This question is to test the data structure and synchronization primitives of Mesa-style monitors.  The data structure definition, open and close are given 2 points.  Send and Recv primitives are given 4 points each.

 

#define MAX_MSGS 1000

#define MAX_MSG_SIZE 128

 

typedef struct {

  Lock lock;

  Condition full, empty;

  Int n;

  int count;

  int head;

  int tail;

  char *msgs[MAX_MSGS];

  int sizes[MAX_MSGS];

  } Mbox;

 

Mbox Open(int n) {

  int i; Mbox *mbox;

 

  if (n > MAX_MSGS) return NULL;

  mbox = malloc(sizeof(Mbox));

  for (i=0; i<n; i++) {

    mbox->msgs[i] = malloc(MAX_MSG_SIZE);

    mbox->sizes[i] = 0;

    }

  mbox->n = n;

  mbox->count = 0;

  mbox->head = 0;

  mbox->tail = 0;

}

 

Close( Mbox mbox) {

  int i;

  for (i=0; i<n; i++)

    free(mbox.msgs[i]);

  free(mbox);

}

 

void send( Mbox mbox, char msg[], int size )

{

  Acquire( &mbox.lock );

  while ( mbox.count >= mbox.n )

    Wait( &mbox.lock, &mbox.full );

 

  strncpy( &mbox.msgs[mbox.head], msg, size );

  mbox.sizes[mbox.head] = size;

  mbox.head = (mbox.head + 1) % n;

  mbox.count++;

 

  Signal( &mbox.empty );

  Release( &mbox.lock);

}

 

int recv( Mbox mbox, char msg[])

{

  int size;

  Acquire( &mbox.lock );

  while ( mbox.count == 0 )

    Wait( &mbox.lock, &mbox.empty );

 

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

    size = mbox.sizes[mbox.tail];

 

  strncpy( msg, &mbox.msgs[mbox.tail], size );

  mbox.tail = (mbox.tail + 1) % 100;

  mbox.count--;

 

  Signal( &mbox.full );

  Release( &mbox.lock);

 

  return size;

}