CSC 469F | Sample Term Test 1 | Fall 2006

First Term Test

1. Definitions: [15 points; 3 each] Define the following terms in the context of this course.
   1. virtual machine monitor
   2. IPC
   3. contention
   4. convoying
   5. gang scheduling


2. [9 points] Contrast the SPIN approach to system extensibility with that of loadable kernel modules. What is the primary benefit and drawback of each?


3. [9 points] In the paper "Operating system support for virtual machines", the authors classify VMMs as belonging to one of two classes (Type I and Type II) in their terminology. What is the defining characteristic of each class? In which category does Xen belong? VMWare Workstation?


4. Performance: [12 points; 4 each]
   1. You have a program that spends 60 percent of its time doing I/O and 40 percent of its time doing computation. If you double the performance of the I/O system, what is the resulting speedup? (Show your calculations)
   2. Which of the following can be explained using Amdahl's Law?
      1. Processor speed has been doubling every 18 months.
      2. The gap between processing and I/O is widening.
      3. Application performance has not been growing as rapidly as processor performance.
      Explain it.
   3. You have just profiled your system extensively. Which scenario below gives you the greatest confidence you will be able to improve the performance of the system? Explain.
      1. Two routines together account for 80 percent of the total execution time.
      2. Each subroutine accounts for approximately 1 percent of the total execution time.
      3. One routine accounts for 10 percent of the total execution time.


5. [12 points; 4 each] Event notification:
   1. What is the primary source of inefficiency in the traditional Unix poll() or select() mechanisms?
   2. Explain how the FreeBSD kqueue() mechanism addresses this problem.
   3. Why was Unix poll() an acceptable design in the 1970's? What changes to hardware and applications made a mechanism like kqueue feasible and necessary for today's systems?


6. [12 points; 8 and 4]
   1. [8 points]Here is the definition of a push() operation for a lock-free stack:

      typedef struct node {
              long key;
              struct node *next;
              struct node *mr_next; /* for limbo list */
      } node_t;
      
      /* Visible to all threads; initially NULL. */
      node_t *stack_top;
      
      void push (long t)
      {
              node_t *n = new_node ();
              n->key = t;
              do {
                 node->next = stack_top;
              } while (!CAS(&stack_top, node, node->next));
      }
      
      

      CAS returns TRUE on success and FALSE on failure.
      Write the corresponding pop() operation. Assume you have access to a deferred deletion function free_node_later (node_t *), so you don't have to worry about the ABA problem.
   2. [4 points] Explain how the ABA problem can occur in the lock-free stack pop() if you do not have a deferred deletion function.
7. [10 points] Question sketch. Given a description of a set of jobs (i.e., arrival time, number of threads, required CPU time) construct a gang schedule showing the jobs that are grouped together. Identify the total number of wasted CPU cycles (time slices on some CPU when nothing was scheduled) due to gang scheduling.