Nachos, CPU Scheduling

Tom Kelliher, CS42

Sept. 23, 1996


  1. On-line info:

  2. Root of Nachos source tree: ~kelliher/pub/cs42/nachos-3.4/code/.

  3. Use a recursive copy to make one copy.

  4. nachos group: allows you to share your work.

  5. Do a recursive chown to make the group nachos for the source tree.

  6. Before each editing session be sure to do the following:
    lisp% umask 7

  7. Places to find documentation; printing and viewing Postscript files.

  8. On reserve in Mack:
    1. W. A. Christopher, S. J. Proctor, and T. E. Anderson, The Nachos Instructional Operating System.

    2. T. Narten, A Road Map Through Nachos.

    3. A. D. Birrell, An Introduction to Programming with Threads.

  9. Using gdb: see

  10. Read handouts, thread source for Friday.

CPU Scheduling


What are the three schedulers, and how do they function?

Model of a process: CPU-I/O burst cycles:

Distribution of bursts.

CPU bursts terminate due to:

  1. Process waits on event (blocked, suspended).

  2. Process' quantum expires (back to ready Q).

Preemptive Scheduling

  1. Non-Preemptive scheduling.

    Context switches occur:

    1. Running process terminates.

    2. Running process blocks.

    I.e., running process controls the show.

    New process takes over if running process blocks.

  2. Preemptive scheduling.

    Principle: Highest priority ready process runs.

    Quantum timers come into play.

    Additional context switches:

    1. Higher priority process changes state from blocked to ready, preempting running process.

    2. Quantum expires (kernel preempts).

    Higher overhead.

  3. Selective preemptive scheduling.

Comparison Criteria

User oriented, performance related criteria.

User oriented, other criteria

System oriented, performance related criteria

System oriented, other criteria

The Priority Function

Examples of Priority Functions

Implemented using queues or priority queues.

  1. FCFS, FIFO --- non-preemptive. Run oldest process. Standard batch priority function

  2. LIFO --- non-preemptive. Run newest process. Not real useful.

  3. SJF --- shortest job first. Non-preemptive. Run process with shortest required CPU time.

    Provably optimal from turnaround/waiting point of view:

  4. SRT --- (shortest remaining time) preemptive version of SJF.

  5. RR --- (round robin) preemptive FCFS with a time quantum limitation. Used in time sharing systems.

  6. Multi-level queues --- prioritized set of queues, to .

    1. Processes in queue i always have priority over queues > i.

    2. A process remains within the same queue.

    3. Each queue may have its own scheduling algorithm.

    4. Alternative: each queue gets some fixed slice of the total CPU cycles.

    5. Example: Queue for interactive jobs, RR scheduling; queue for batch jobs, FCFS.

  7. Multi-level feedback queues --- similar to multi-level queues, except that a process can move between different queues, based upon CPU usage.

    1. Must specify rules for moving the processes between queues.

    2. Ordinarily, lower priority queues have greater quantums, etc.

    3. Unix uses this method, with a 100ms quantum for all queues. 128 priorities, with 32 queues.

Scheduling Examples

Suppose the following jobs arrive for processing at the times indicated and run with the specified CPU bursts (at the end of a burst a process waits for one time unit on a resource). Assume that a just-created job enters the ready queue after any job entering the ready queue from the wait queue.

Calculate the average turnaround time for each of the scheduling disciplines listed:

  1. First Come First Served.
  2. Shortest Remaining Time (assume that the running time is the sum of the CPU bursts).
  3. Round robin with a quantum of 1.

Don't forget the ``bubble'' cycles (where no process is runnable), if required.

Thomas P. Kelliher
Sat Sep 21 15:03:56 EDT 1996
Tom Kelliher