Outline:
- CPU scheduling
(take this discussion to do review of CPU scheduling)
Next week:
- give out a sample midterm on thursday (?)
- review during the discussion
- make suggestion on what to talk about in the suggestion box
- will not go over any sample questions or topics unless i'm asked
- in-class midterm oct 28 (a week from tomorrow)
- project #2 is out tomorrow (memory management) START EARLY!
- Grading hw3
- grades sometime over the weekend
- Grading project
- grades some time next week
CPU scheduling:
Evaluation criteria for scheduling algorithms:
- efficiency (CPU/IO utilization): percentage of time CPU/IO is working
- response time: time from the submission of a job to its complition
- throughput: number of jobs per hour
- minimize context switching (related to efficiency)
- memory limitations or cost of keeping I/O waiting processes in memory
- fairness (semantics varies): each process gets a fair share of the CPU
Can't get optimal values for all.
Common scheduling algorithms:
----------------------------------------------------------------------------
First-Come-First-Serve
----------------------------------------------------------------------------
FCFS
P1 P1 P1 P1 P1 P1 P1 P1 P1 P1 P2 P3 P3 P4 P5 P5 P5 P5 P5
0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1
0 1 2 3 4 5 6 7 8
Process Time
P1 10
P2 11
P3 13
P4 14
P5 19
13.4
Answer to 2 part (b) Advantages of FCFS
-- simple: to understand and implement (one queue, run to completion)
-- dont need to know running time of processes
-- while penalizing short jobs it benefits long ones
eg., give an example of poor response time for an interactive job
(from prof chen's lecture notes)
ready queue = 100ms, 1ms
average response = 100.5ms
-- guarantees minimal number of context switching
----------------------------------------------------------------------------
Round Robin w quantum (timeslice) of X
----------------------------------------------------------------------------
RR
P1 P2 P3 P4 P5 P1 P3 P5 P1 P5 P1 P5 P1 P5 P1 P1 P1 P1 P1
0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1
0 1 2 3 4 5 6 7 8
Process Time
P1 19
P2 2
P3 7
P4 4
P5 14
9.2
Answer to 2 part (c) Advantages of round-robin
-- fair
-- gives good response time
eg., same as FCFS example average response time 51.5
? does RR always achieve better response time than FCFS?
eg., same size jobs (mentioned in prof prakash's notes)
ready queue = 2ms, 2ms, 2ms
FCFS avg = 2
RR = 5
-- dont need to know running time of processes
-- won't allow one process to take over the CPU
-- good for short jobs: allows for shorter jobs to execute quickly when
stuck behind long jobs (only adds a small amount to the long job's
response time)
- issues: quantum length
eg., too short and waste time context switching
if quantum = 1 => Process sharing
eg., too long and average response time goes up as it penalizes short jobs
if quantum = infinity => FCFS
-- example from the lecture
p1 1000ms, p2 1000ms, p3 1ms/10ms IO.
with RR
run p1 for 100ms, run p2 for 100ms, run p3 for 1ms,...
disk is only utilized 10%
---------------------------------------------------------------------------
Shortest Job First with/without Preemption
---------------------------------------------------------------------------
SJF or STCF (shortest-time-to-completion-first)
P2 P4 P3 P3 P5 P5 P5 P5 P5 P1 P1 P1 P1 P1 P1 P1 P1 P1 P1
0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1
0 1 2 3 4 5 6 7 8
Process Time
P1 19
P2 1
P3 4
P4 2
P5 9
7
Answer to 1 part (b) SJF gives the lowest average response time.
SJF is optimal when processes arrive at the same time.
Answer to 2 part (a) Disadvantages for STCF-P
(pro: while STCF provides optimal average response time)
-- starvation (of long jobs) is possible
-- overhead in keeping sorted list of jobs and ability to preempt
-- hard to estimate the running time for a process (other algorithms either
run each job to completion or timeslice execution).
what if we let the user tell the OS the running time? then how do we handle
malicous users who would provide incorrect information. one solution is to
kill the process if it used up available time...
-- how to estimate?
aging: average current measured value and previous estimate.
t_a0 - actual time at time 0
t_e0 - estimated time at time 0
t_a0, t_e0
t_e1 = a*t_e0 + (1-a)*t_e0
-- unfair (it penalizes long jobs)
-- without preemption. SJF is optimal only if all processes arrive at the
same time.
----------------------------------------------------------------------------
Priority Scheduling with/without Preemption
----------------------------------------------------------------------------
Priority
P4 P1 P1 P1 P1 P1 P1 P1 P1 P1 P1 P3 P3 P5 P5 P5 P5 P5 P2
0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1
0 1 2 3 4 5 6 7 8
Process Time
P1 11
P2 19
P3 13
P4 1
P5 18
12.4
Answer to 2 part (d) Disadvantages of non-preemptive priority
-- starvation (of low priority jobs) is possible.
-- similar to STCF, assignment of priorities to processes is hard?
-- a process (with a high priority) can take over the CPU
- priority inversion (low priority grabs the lock, high prioriy cant run)
- estimating priority:
- static assignment
- dynamic assignment: time_executed/time_allocated
eg., timeslice 100ms.
I/O job = 2ms/100ms = .05 -> priority = 50
cpu job = 50ms/100ms = .2 -> priority = 2
inserting a short I/O wait before a long CPU burst will bump the
process's priority....
- static assignment would benefit more from preemption.
-----------------------------------------------------------------------------
Real-time scheduling:
-----------------------------------------------------------------------------
Covered in Tanenbaum in ch 7.
- earliest deadline first
- dynamic assignment of priorities
- scheduler keeps the list of runnable processes sorted on deadline
- it's preemptive (if a job with a closer than currently running arrives
the running process is preempted.
- how to compute if the system is schedulable?
if process i has period Pi and required Ci of CPU, then
sum_of_all_i(Ci/Pi) <= 1 if it's not system is not schedulable.
eg., A runs every 30ms (33time/sec) B runs every 40ms (25times/sec)
and C runs every 10ms (25times/sec)
- rate monotonic
- is optimal but only works when each processes have same job sizes
(CPU bursts)
(e) Advantages and disadvantages of an earliest-deadline first algorithm.
pro: EDF is optimal. it will meet all deadlines if possible
con: ?
-- needs priority queues for storing deadlines
-- behaves badly under overload
-- somewhere i read: a job that missed its deadline is allowed to continue
causing a domino-effect of missed deadlines