Homework 2 Solutions

22C:116, Spring 1999

Douglas W. Jones
  1. Part A: The function thread_relinquish() uses longjmp() and setjmp() for context switching. Specifically, it uses setjmp to save the state of a thread in a jump buffer, and it uses longjmp to recover a saved thread state and transfer control to that thread.

    Part B: The longjmp() function is used in the thread manager for exception handling. Specifically, it is used to exit the thread manager by long jumps to the jump-buffer thread_death when a thread's stack overflows, when the last thread exits, or when there is a deadlock.

  2. The thread manager is written assuming that a single one UNIX process will support any number of threads, and it ignores the possibility of signals (the UNIX process-level analog of interrupts). Therefore, the critical sections within the thread manager do not need protection.

  3. Here is the code written to run under the thread manager:
    #include 
    #include "threads.h"
    
    void test_thread( int n )
    {
        int j;
        for (j = 0;j < 10; j++) {
            thread_relinquish();
            puts( (char *)n );
        }
    }
    
    int main()
    {
            thread_manager_init();
            thread_startup_report(); /***********/
            thread_launch( 4000, test_thread, (int)"x" );
            thread_launch( 4000, test_thread, (int)"y" );
            thread_manager_start();
            /* control never reaches this point */
    }
    
    This does not produce the same output as the pure UNIX version for a number of reasons:

  4. Question 1 on page 141 of Tannenbaum asks for the percent idle time for a system with 4 processes, each idle 1/2 of the time. The probability that all processes are idle at any instant is the product of the probabilities that any one is idle, so we have (1/2)4 = 1/16.

  5. Question 4 on page 142 of Tannenbaum asks for the fraction of the CPU taken to compress a 1Mbyte heap every second if it takes 0.5 microsec to copy one byte and holes are 0.4 times the size of segments. Assuming each pair of segments is separated by holes, we have 0.4s + s = 1Mbyte or 1.4s = 1Mbyte or s = 0.714Mbytes, where s is the total size of the used portion of the heap. During each compaction, as many as s bytes will be moved, so a compaction cycle may require 0.5s microsuseconds or 0.357 seconds; doing one compaction per second, compactions will require up to 0.357 of the total CPU time.