Homework 2 Solutions

22C:116, Fall 1999

Douglas W. Jones

  1. Part A: Disregarding questions of implementation, what is the difference between the abstract operations of a process relinquishing the CPU and a process being preempted?
    The word relinquish implies a voluntary act, while the word preempt implies an involuntary act. A process or thread may voluntarily relinquish the CPU, for example, by calling a relinquish service, or the system or thread manager may forcefully preempt a process or thread when a time-slice ends.

    Part B: What information must be included in the jump buffer used by longjmp(), and what information that the definition of longjmp() says may not be well defined must actually be saved and restored?

    The jump buffer must contain, at minimum, the value of the return address passed to setjmp(), and the value of the frame-pointer or stack-pointer on entry to setjmp().

    Relinquish itself has no local variables, so whether or not setjmp saves or restores the local variables of relinquish is not an issue. On the other hand, the local variables of the functions that called relinquish() or other routines in the thread package MUST remain in memory during the time the calling threads are in the ready list. If these local variables are copied into some secondary buffer, it would make it impossible to pass pointers to local variables to other threads.

  2. Part A: Why do both the then and else clauses in the example programs get executed?
    In the first example, the then clause is executed by the parent that called fork(), while the else clause id executed by the child process. From an abstract perspective, these are executed in parallel.

    In the second example, the else clause executes because the call to setjmp() always returns false. The else clause ends with a call to longjmp(), and this transfers control to the then clause via a second return from setjmp().

    Part B: Why is the output of the two programs different?

    In the example using longjmp(), there is only one variable i, operated on successively by the increment and decrement operations, so the net result is zero. In the example using fork(), the variable i is copied, prior to any increment or decrement operations, and the copy decremented by the child is discarded, while the copy incremented by the parent is the one that gets printed at the end.

  3. The Problem When the producer is hardware and the consumer is software, how does the producer signal the consumer that data is ready?
    The hardware, on producing an item of data, requests an interrupt. The interrupt software responds to the interrupt, obtains the data item and typically enqueues the data in a software queue before signalling the consumer (using a semaphore). If this architecture is used, the consumer may be written in exactly the same way it would be written if the producer were hardware.