Lecture Notes for Operating Systems Concepts

23 September 2002 - Scheduling

1. motivation - several processes running at the same time; utilization (batch), fairness (time sharing)

2. objectives - implement the computing abstraction using the cpu; manage (that is, multiplex) the cpu abstraction among all processes

   1. performance

      1. responsiveness, utilization

      2. queuing theory

   2. strategy - how to juggle processes; economics; proportional priority manipulation; optimal scheduling is hard (real-time) or impossible (non-closed systems)

      1. process measures - service time, wait time, turnaround time

      2. system measures - throughput rate, job turnaround time, response time

      3. the compute-io mix - component processes interspersed by io

3. two questions - when to stop and what to start

   1. yanking the running process

      1. voluntary surrender - non-preemptive

         1. a yield or a sleep

         2. yield to another process (coroutines) or yield to the scheduler

         3. good - inexpensive (one or two context switches), simple, effective scheduling

         4. bad - subject to abuse, hard to do well, subtle errors

      2. involuntary surrender - preemptive

         1. the running process is removed

         2. removal by a combination of process action, timer expiry, rank pulling

         3. time slice, quantum

   2. non-preemptive process selection - all selection is priority bases; the difference is in how the priorities are assigned

      1. fcfs - a queue of jobs; easy to implement; non-optimal; no starvation

      2. shortest job next - jobs ordered by total service time; easy to implement; optimal average turnaround; large jobs starved

      3. deadline - jobs ordered by deadline; easy to implement; optimal; non-admittance possible

      4. priority - assign arbitrary priority

   3. preemptive scheduling -

      1. round-robin - equal priorities, a ring of processes

      2. multiple-level queues - handles job classes

         1. foreground-background - batch interactive jobs

         2. unix scheduling - multiple run queues

         3. nt scheduling - real-time and variable levels

4. implementation

   1. organization

      1. parts - arbitrator, context-switcher, queues

   2. process context

      1. context is process state - registers, cache, mmu

      2. a context switch is a save-restore pair - two context switches required

      3. context switches are expensive - user-kernel, save-restore, lost information

   3. process state diagrams

This page last modified on 18 September 2002.