CS 438, Operating Systems Analysis

Test 1, 12 October 2004 - Processes

  1. Explain how the trap instruction extends the abstract-machine interface.

    The abstract-machine interface consists of the host-system hardware architecture and the system calls implemented by the operating system. The trap instruction is used to implement system calls. See Figure 6.6 in the text.

  2. Does the combination of shortest-job-next selection and voluntary eviction make any sense as a scheduling policy? Explain.

    No: By the definition of SJN, the executing process has the shortest expected execution time. If it voluntarily leaves the CPU, it will be picked by the scheduler to be the next process to get the CPU; that is, it just performed a no-op with context-switch overhead.

    Yes: The SJN property means the executing process has the shortest expected execution time. If a new process with a shorter expected execution time enters the system, the SJN property is violated. By occassionaly giving up the CPU the running process gives the scheduler an opportunity to run a process with a shorter expected execution time.

    Most answers were one or the other of the arguments, with the first one being more popular.

  3. A colleague of yours argues that a non-pre-emptive scheduler would be better than a pre-emptive scheduler if the objective is to improve throughput on a system consisting of compute-bound processes. Do you agree or disagree with your colleague? Explain.

    A system's response time is the total execution time divided by the number of processes executed. The scheduler can effect this by making the total execution time either longer or shorter. Adding context switches to compute-bound processes makes them execute longer due to context-switch overhead; your colleague appears to be correct.

    Many answers got side-tracked by long vs. short process examples without noticing that it's the total execution time that matters.

  4. A colleague of yours is managing a machine that uses round-robin selection and quantum eviction in its scheduler; the machine handles a mixture of process types. Your colleague would like to provide better performance for interactive processes, and modifies the scheduler so that processes leaving the CPU before their quantum expires have their quantum reduced (to some minimum). Your colleague's thinking is that the faster that interactive processes can march through the CPU, the better their performance. Much to your colleague's dismay, this change doesn't improve interactive performance. Explain why.

    Your colleage adjusted the amount of time an interactive process spends in the CPU, but the important measure for responsiveness is the amount of time it takes for the ready process to reach the CPU. Your colleague should have provided a fast-path for interactive process to reach the CPU more quickly; this could have been done by, for example, modifying the ready queue to allow interactive process to enter somewhere in the middle of the queue, or by provided two ready queues, one for interactive processes and the other for non-interactive processes.

This page last modified on 14 November 2004.