Midterm 1 Solution

CS 26

October 4, 1996

1. Short Answer. Solve each of the problems. (60 pts.)
   1. Draw the process state graph, showing process states and transition edges. Briefly describe the reason(s) behind each transition.

      

   2. Can mailboxes be used to simulate semaphores? Justify your answer.

      Yes. Semaphore wait() corresponds to a mailbox receive(), assuming that the
      receive() blocks on an empty mailbox. Semaphore signal() corresponds to a mailbox send() of an empty message. To initialize a semaphore to n, send n empty messages to the mailbox.

   3. Name and describe three CPU-based system protection mechanisms ( not synchronization mechanisms).
      1. Dual-mode operation: The CPU operates in user-mode and supervisor-mode. Some instructions are illegal in user-mode. The halt instruction is an example.

      2. Bounds registers: All memory accesses must be between the bounds registers.

      3. Interval timer: A timer which can be set in supervisor-mode and generates an interrupt when it expires.

   4. Compare and contrast the two types of threads.

      

   5. Compare and contrast I/O controlled by spin-loops and controlled by interrupts.

      Spin-loops waste CPU cycles unless the I/O wait is shorter than the overhead involved in interrupt handling (not usually the case). Interrupt-driven I/O permits the CPU to be doing useful work while the I/O takes place.

   6. What is a critical section? Name and define the three characteristics which a solution to the critical section problem must possess.

      A critical section is any section of a process' code in which shared variables are accessed. The three characteristics are:

      1. Mutual Exclusion --- if is executing in one of its critical sections, no , , is executing in its critical sections.

      2. Progress --- a process operating outside of its critical section cannot prevent other processes from entering theirs; processes attempting to enter their critical sections simultaneously must decide which process enters eventually.

      3. Bounded Waiting --- a process attempting to enter its critical region will be able to do so eventually.

2. Long Answer. Solve two of the following problems. Ensure that I will be able to determine which two to grade. (40 pts.)
   1. Suppose the following jobs arrive for processing at the times indicated and run with the specified CPU bursts (between bursts, assume that each process voluntarily relinquishes the CPU, forcing a context switch, by blocking on I/O which completes in one time unit). Ties are resolved in favor of the currently executing process (to reduce context switch time) followed by RR manner within the ready queue.

      

      Calculate the average turnaround time for each of the three scheduling disciplines listed:

      1. Non-preemptive First Come First Served.
      2. Preemptive Shortest Remaining Time (assume that the running time is the sum of the CPU bursts).
      3. Preemptive Round Robin, with a quantum of 1.

      

   2. The following has been proposed as a ``solution'' to the critical section problem for two processes, P0 and P1.

          global:
             int flag[2] = { 0, 0 };
      
          mutexbegin:
             do
                flag[i] = 1 - flag[1-i];
             while (flag[1-i] != 0);
             
          mutexend:
             flag[i] = 0;
      

      Does this ``solution'' satisfy the three requirements of a solution to the critical section problem? Justify your answer.

      No, because mutual exclusion can be violated. Suppose both processes are trying to enter critical sections. Each process can read the other process' flag (0) and set their own to 1. This causes them each to repeat the do-while. On the next iteration through the loop, they can each again read the other process' flag (1) and reset their own to 0. The do-while condition is now violated and both processes enter their respective critical sections, violating mutual exclusion.

      The big hint on this problem was calling the algorithm a ``solution.''