Nachos, CPU Scheduling

Tom Kelliher, CS42

Sept. 23, 1996

Nachos

1. On-line info: http://http.cs.berkeley.edu/~tea/nachos/.

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 http://keystone.westminster.edu/~kelliher/cs23/gdb.html.

10. Read handouts, thread source for Friday.

CPU Scheduling

Motivation:

• Traditionally: keep the CPU busy.

• Now:
  • Promote modular design.

  • Increase throughput (a multi-threaded server).

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.

• Response time --- time from submission of request to receipt of first output.

• Turnaround time --- time from submission of request to its completion.

• Waiting time --- turnaround time minus CPU time; time spent waiting for resources.

• Deadlines --- When deadlines are specified, percentage of deadlines which are met.

User oriented, other criteria

• Predictability --- the same job should run in about the same amount of time and cost regardless of other system activity.

System oriented, performance related criteria

• Throughput --- number of processes completed per unit of time.

• CPU utilization --- percentage of time CPU is performing actual work.

System oriented, other criteria

• Fairness --- processes should generally be treated the same, with no process starving.

• Priority enforcement --- when priorities are assigned, they should be adhered to.

• Balancing Resources --- keep all system resources busy, adjust priorities accordingly. This can come in at the long-term scheduler level.

The Priority Function

• CPU time --- usually the most important factor

• memory requirements --- a major criterion in batch systems; in timesharing systems give a good measure of swapping overhead

• wall time --- important for process ``aging'' --- increase priority of older jobs.

• total required CPU time --- specify max runtime for job (batch) or take some average of previous runtimes.

• external priorities --- batch, interactive, realtime, VIP, etc. Let user pick priority and charge for higher priorities.

• system load --- increasing quantum may offset swapping overhead, increasing utilization. Continue giving good response to high priority jobs, making others suffer. Graceful degradation.

Examples of Priority Functions

Implemented using queues or priority queues.

1. FCFS, FIFO --- non-preemptive. Run oldest process. Standard batch priority function
   • Implemented with a simple queue for the ready Q

   • New jobs, jobs previously in wait or running state put at end of ready Q

   • Next job to run taken from head of ready Q

   • Priority function: time in ready Q

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

3. SJF --- shortest job first. Non-preemptive. Run process with shortest required CPU time.
   • Time is time of next CPU burst.

   • Implement with priority Q

   • Estimate of next CPU burst:

     

     where is the estimated time and t is the actual time. is an exponential average of history.

   • Priority function:

   Provably optimal from turnaround/waiting point of view:

   

4. SRT --- (shortest remaining time) preemptive version of SJF.
   • Another possibility --- Time is remaining CPU time:

        Current->RemainingTime -= LastCPUBurst;
     

   • Total estimated CPU time is submitted with job. If exceeded, job is terminated.

5. RR --- (round robin) preemptive FCFS with a time quantum limitation. Used in time sharing systems.
   • Uses FCFS's priority function

   • Additional factor in decision epoch: expiration of quantum timer

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.