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