Homework I
CS 6210 Operating Systems
Due Date: Friday, February 8, 2002

  1. We discussed why multithreading (MT) is useful and the different MT models. One of these models implements threads at the user level. In this question, you need to explore the implementation of a user-level threads library. Such a library should be portable across different platforms but at the same time, the context that needs to be saved and restored for threads depends on underlying processor architecture. To make portable implementations, operating systems like Solaris provide systems calls such as getcontext() and setcontext(). C library functions such as longjmp() and setjmp() can also be used in the implementation of user level threads.

    2. Carefully study the getcontext() and setcontext() calls. Use these calls to develop an implementation outline of a threads library. In particular, describe the key data structures used by your library and provide implementations of library functions that allow you to create a thread, yield control to another thread and block a thread. Explain why your implementation of threads works correctly. You can just provide pseudo-code for the implementation that you show in this answer.
  2. The SPIN operating system provides a protection model and an extension model. Why is the extension model necessary? Discuss the implementation of an extensible memory management service in SPIN. What benefits does such a service offer compared to memory management implemented by traditional monolithic operating systems.
  3. Exokernel securely binds low level hardware resources to library operating systems. If file systems are implemented by library operating systems, Exokernel must securely bind disk blocks to the different library operating systems. Discuss how such secure binding of disk blocks can be done in Exokernel.
  4. In the Microkernel construction paper, the author measures the cost of a system call that simply returns the PID of the caller. Based on the measured time and the instructions that are executed by the call, the authors can estimate the indirect overheads associated with a system call and the crossing of the user and system boundary. In this question, you are asked to run a similar experiment. First, write a program that allows you to experimentally measure the cost of a system call that simply returns the PID of the caller. Measure this cost carefully. Second, find the clock speed of the processor on which you run this experiment. Assuming that the number of instructions/cycles  needed to execute the system call are the same as in the paper, estimate the cost of the system call. Based on this calculation and the measured cost, discuss the overhead due to indirect costs. What are the sources of the indirect costs?
  5. In the MCS lock implementation, it is claimed that the queue is in the following state at a given time.

    6.  
    1. The current holder of the lock in P1. The next pointer in its node is NULL.

      2.  
    2. There are three other nodes in the queue that are created by threads P2, P3 and P4. The lock variable L points to P4?s node. However, the next pointers in all of these nodes are NULL.

      3.  

       

    Can the queue be in the above state in the MCS algorithm? If your answer is yes, show how this can happen. Otherwise, argue why this state is impossible. Algorithm 6 in the MCS paper gives the implementation of release-lock without a compare-and-swap instruction. Give a state of the queue (e.g., show the nodes and the values of their fields) that is allowed by the algorithm without compare-and-swap, which is impossible when the algorithm in Figure 5 is used.