(8) Scheduling Flashcards
What are the four classes of Schedulers?
Batch (throughput oriented e.g Pixar rendering)
Interactive (response time oriented)
Real time (deadline driven e.g embedded systems)
Parallel (Speedup-driven e.g space shared use of 1000 processor machine)
Give some examples of scheduling goals
– maximize CPU utilization
– maximize throughput (requests completed / s)
– minimize average response time (->completion)
– minimize average waiting time (->start)
– minimize energy (joules per instruction)
What is the difference between non-preemptive and preemptive schedulers?
Non-preemptive - Once given green light they have it until the relinquish it
-an I/O op, allocation of memory in a system without swapping
Preemptive - Can revisit a decision, but this involves some overhead
What is the utilization law?
U = X * S U is utilization X is throughput S is average service time (U is constant provided the workload can be processed)
What is Little’s law?
N = X * R
N is average number in the system
X is throughput
R is average response time
Better average response time <=> fewer in system
What are R and N at a single server under FIFO?
R = S/(1-U) N = U/(1-U)
R is response time
N is average number in the system
U is utilization
S is average service time
What is a problem with FIFO scheduling
Convoy effect -short processes wait behind longer processes.
May lead to poor utilization of other resources
May result in poor overlap of CPU and I/O activity (E.g., a CPU-intensive job prevents an I/O-intensive job from a
small bit of computation, preventing it from going back and
keeping the I/O subsystem busy)
Describe SJF
Shortest job first
Associate each process with the length of its next burst and schedule accordingly.
SJF is optimal - minimum average wait time for a set of processes
Hard to know the length of the next CPU request
How can you determine the length of the next CPU burst?
You can only estimate based on prior performance.
Use exponential averaging.
Tn = actual length of nth CPU burst
Pn+1 = predicted value for next CPU burst
a, 0<=a<=1 (usually 0.5)
Pn=1 = a Tn + (1-a)Pn
Describe Round Robin
Each process gets a small unit of CPU time, time quantum unit q, usually 10-100ms.
With n processes and time quantum q each process gets 1/n of the CPU time in chunks of at most q time at once. No process waits over (n-1)q units.
Timer interrupts every quantum to schedule next process.
If q is large performance is similar to FIFO.
If q is small then overhead for switching can be too high.
Describe priority scheduling
A priority number is associated with each process.
CPU is allocated to the process with the highest priority (smallest integer).
Starvation may be a problem so add aging to processes increasing priority.
Describe MLFQ
Discriminate against old proceses.
Hierarchy of queues.
Priority ordering among the queues.
Requests enter the highest priority queue.
Each queue is a Round Robin
Requests move between queues based on execution history.
