UNIX Scheduling

Process states:






The scheduler picks the next process to move from ready to running
• What’s the “Application Profile”:
– A program alternates between CPU usage and I/O
– Relevant question for scheduling: is a program compute-bound
(mostly CPU usage) or I/O-bound (mostly I/O wait)
• When scheduling occurs:
– When a process is created
– When a process terminates
– When a process issues a blocking call (I/O, semaphores)
– On a clock interrupt
– On I/O interrupt (e.g., disk transfer finished, mouse click)
– System calls for IPC (e.g., up on semaphore, signal, etc.)
• Multi-level scheduling (e.g., 2-level in Unix)
– Swapper decides which processes should reside in memory
– Scheduler decides which ready process gets the CPU next
Scheduling Issues
• Can preemption occur?
– Preemptive schedulers can take control from a process at interrupt
– Non-preemptive scheduler doesn’t
• What are we trying to optimize?
– CPU utilization: Fraction of time CPU is in use
– Throughput: average number of jobs completed per time unit
– Turnaround Time: average time between job submission and
completion
– Waiting Time: average amount of time a process is ready but waiting
– Response Time: time until the system responds to a command
– Response Ratio: (Turnaround Time)/(Execution Time) -- long jobs
should wait

Basic Scheduling Algorithm

• FCFS - First-Come, First-Served
– Non-preemptive
– Ready queue is a FIFO queue
– Jobs arriving are placed at the end of queue
– Dispatcher selects first job in queue and this job
runs to completion of CPU burst
• Advantages: simple, low overhead
• Disadvantages: inappropriate for interactive
systems, large fluctuations in average turnaround time are possible.
• Example workload
Job 1: 24 units, Job 2: 3 units, Job 3: 3 units
• FCFS schedule:
Job 1 Job 2 Job 3
0 24 27 30
• Total waiting time: 0 + 24 + 27 = 51
• Average waiting time: 51/3 = 17
• Total turnaround time: 24 + 27 + 30 = 81
• Average turnaround time: 81/3 = 27

• SJF - Shortest Job First
• Non-preemptive
• Ready queue treated as a priority queue based on
smallest CPU-time requirement
• arriving jobs inserted at proper position in queue
• dispatcher selects shortest job (1st in queue) and runs to
completion
• Advantages
• provably optimal average turnaround time
• Disadvantages:
• starvation possible
• can’t actually be implemented.
• Can do it approximately: use exponential averaging to
predict length of next CPU burst
• pick shortest predicted burst next
• Example workload
Job 1: 24 units, Job 2: 3 units, Job 3: 3 units
• SJF schedule:
Job 2 Job 3 Job 1
0 3 6 30
• Total waiting time: 6 + 0 + 3 = 9
• Average waiting time: 3
• Total turnaround time: 30 + 3 + 6 = 39
• Average turnaround time: 39/3 = 13
• SJF always gives minimum waiting time and turnaround time Exponent

Exponential Averaging
t n+1 = a tn + (1 - a) ) t n
• t n+1 : predicted length of next CPU burst
• tn : actual length of last CPU burst
• t n : previous prediction
• a = 0 implies make no use of recent history
(t n+1 = t n)
• a = 1 implies t n+1 = tn (past prediction not used).
• a = 1/2 implies weighted (older bursts get less and
less weight).


• RR - Round Robin
• Preemptive version of FCFS
• Circular ready queue
– arriving jobs are placed at end
– dispatcher selects first job in queue and runs until completion of CPU burst, or until time quantum expires
– if quantum expires, job is again placed at end
• Example workload:
Job 1: 24 units, Job 2: 3 units, Job 3: 3 units
• RR schedule with time quantum=3:
Job 1 Job 2 Job 3 Job 1
0 3 6 9 30
• Total waiting time: 6 + 3 + 6 = 15
• Average waiting time: 5
• Total turnaround time: 30 + 6 + 9 = 45
• Average turnaround time: 15
• RR gives intermediate wait and turnaround time (compared to SJF and FCFS)

• Advantages: simple, low overhead, works for
interactive systems
• Disadvantages: if quantum is too small, too much
time wasted in context switching; if too large (i.e.
longer than mean CPU burst), approaches FCFS.
• Typical value: 20 – 40 msec
• Rule of thumb: Choose quantum so that large
majority (80 – 90%) of jobs finish CPU burst in
one quantum
• RR makes the assumption that all processes are
equally important

Importance of a good Quantum Factor
• Context switching is expensive
– hundreds of instructions
– if quantum is too small, much of the CPU time will
be wasted on context switching overhead
• … and the machine will seem slower than it really is
• Interactivity requires rapid response time
– Interactive processes need service quickly,
especially after I/O occurs
– if quantum is too large, waiting time is increased
• … and the machine will seem slower than it really is
• Quantum must be >> context switch cost, but
<<>
• HPF - Highest Priority First
• General class of algorithms ==> priority scheduling
• Each job assigned a priority which may change dynamically
• May be preemptive or non-preemptive
• Central problem: how to select / compute priorities?

• Multi-Level Feedback (FB)
• Each priority level has a ready queue, and a time quantum
• process enters highest priority queue initially, and (next) lower queue
with each timer interrupt (penalized for long CPU usage)
• bottom queue is standard Round Robin
• process in a given queue not scheduled until all higher queues are empty

Scheduling in Unix
• Based on multi-level feedback queues
• Priorities range from -64 to 63 (lower number means higher
priority)
• Negative numbers reserved for processes waiting in kernel mode
(that is, just woken up by interrupt handlers) (why do they have a
higher priority?)
• Time quantum = 1/10 sec (empirically found to be the longest
quantum that could be used without loss of the desired response
for interactive jobs such as editors)
– short time quantum means better interactive response
– long time quantum means higher overall system throughput since
less context switch overhead and less processor cache flush.
• Priority dynamically adjusted to reflect
– resource requirement (e.g., blocked awaiting an event)
– resource consumption (e.g., CPU time)

Unix CPU Scheduler
• Two values (stored in the PCB/process table entry)
– p_cpu: an estimate of the recent CPU use
– p_nice: a user/OS settable weighting factor (-20..20) for flexibility;
default = 0; negative increases priority; positive decreases priority
• Each process' priority calculated periodically
priority = base + p_cpu + p_nice
and the process is moved into the appropriate ready queue
• CPU utilization, p_cpu, is incremented each time the system clock
ticks and the process is found to be executing.
• p_cpu is adjusted once every second (time decay)
– Possible adjustment: divide by 2 (that is, shift right)
– Motivation: Recent usage penalizes more than past usage
– Precise details differ in different versions (e.g. 4.3 BSD uses current
load (number of ready processes) also in the adjustment formula)