Site hosted by Angelfire.com: Build your free website today!

Department of Computer Science, UMass Amherst Andrew H. Fagg

Announcements/Reminders

˛ HW 1 now due tonight.

˛ HW 2 is available from the website.

˛ Lab 1 due Friday

CMPSCI 377: Operating Systems Lecture 6, Page 1

Department of Computer Science, UMass Amherst Andrew H. Fagg

Last Class: Threads and Scheduling

˛ Thread: sequential execution stream within a process

˛ Kernel threads versus user-level threads

˛ Goals for Scheduling:

{ Minimize average response time

{ Maximize throughput

{ Share CPU equally

{ Other goals?

˛ Scheduling Algorithms:

{ Selecting a scheduling algorithm is a policy decision

{ FCFS: simple, but typically fails to meet above goals

CMPSCI 377: Operating Systems Lecture 6, Page 2

Department of Computer Science, UMass Amherst Andrew H. Fagg

Today: More on Scheduling Algorithms

˛ Round Robin

˛ SJF

˛ Multilevel Feedback Queues

˛ Lottery Scheduling

CMPSCI 377: Operating Systems Lecture 6, Page 3

Department of Computer Science, UMass Amherst Andrew H. Fagg

Round Robin Scheduling

˛ Variants of round robin are used in most time sharing systems

˛ Add a timer and use a preemptive policy.

˛ After each time slice, move the running thread to the back of the queue.

˛ Selecting a time slice:

{ Too large - waiting time suŽers, degenerates to FCFS if processes are

never preempted.

{ Too small - throughput suŽers because too much time is spent context

switching.

) Balance these tradeoŽs by selecting a time slice where context

switching is roughly 1% of the time slice.

CMPSCI 377: Operating Systems Lecture 6, Page 4

Department of Computer Science, UMass Amherst Andrew H. Fagg

Round Robin Scheduling (cont)

˛ Today: typical time slice= 10-100 ms, context switch time= 0.1-1ms

˛ Advantage: It's fair; each job gets an equal shot at the CPU.

˛ Disadvantage: Average waiting time can be bad.

CMPSCI 377: Operating Systems Lecture 6, Page 5

Department of Computer Science, UMass Amherst Andrew H. Fagg

Round Robin Scheduling: Example 1

˛ Example: 5 jobs, 100 seconds each, time slice 1 second, context switch

time of 0

Completion Time Wait Time

Job length FCFS Round Robin FCFS Round Robin

1 100

2 100

3 100

4 100

5 100

Average

CMPSCI 377: Operating Systems Lecture 6, Page 6

Department of Computer Science, UMass Amherst Andrew H. Fagg

Example 1: FCFS

Time

Job

J1

J2

J3

J4

J5

CMPSCI 377: Operating Systems Lecture 6, Page 7

Department of Computer Science, UMass Amherst Andrew H. Fagg

Example 1: FCFS

Time

Job 1 2 ... 100 101 ... 200 201 ... 300 301 ... 400

J1 1 ... 100

J2 1 ... 100

J3 1 ... 100

J4 1 ... 100

J5

And Job 5 is scheduled for 401 to 500...

CMPSCI 377: Operating Systems Lecture 6, Page 8

Department of Computer Science, UMass Amherst Andrew H. Fagg

Example 1: Round Robin

Time

Job

J1

J2

J3

J4

J5

CMPSCI 377: Operating Systems Lecture 6, Page 9

Department of Computer Science, UMass Amherst Andrew H. Fagg

Example 1: Round Robin

Time

Job 1 2 3 4 5 6 7 8 9 10 ... 496 497 498 499 500

J1 1 2 ... 100

J2 1 2 ... 100

J3 1 2 ... 100

J4 1 2 ... 100

J5 1 2 ... 100

CMPSCI 377: Operating Systems Lecture 6, Page 10

Department of Computer Science, UMass Amherst Andrew H. Fagg

Round Robin Scheduling: Example 1

˛ Example: 5 jobs, 100 seconds each, time slice 1 second, context switch

time of 0

Completion Time Wait Time

Job length FCFS Round Robin FCFS Round Robin

1 100 100 496 0 396

2 100 200 497 100 397

3 100 300 498 200 398

4 100 400 499 300 399

5 100 500 500 400 400

Average 300 498 200 398

CMPSCI 377: Operating Systems Lecture 6, Page 11

Department of Computer Science, UMass Amherst Andrew H. Fagg

Round Robin Scheduling: Example 2

˛ Example: 5 jobs, of length 50, 40, 30, 20, and 10 seconds each, time

slice 1 second, context switch time of 0 seconds

Completion Time Wait Time

Job length FCFS Round Robin FCFS Round Robin

1 50

2 40

3 30

4 20

5 10

Average

CMPSCI 377: Operating Systems Lecture 6, Page 12

Department of Computer Science, UMass Amherst Andrew H. Fagg

Example 2: FCFS

Time

Job

J1

J2

J3

J4

J5

CMPSCI 377: Operating Systems Lecture 6, Page 13

Department of Computer Science, UMass Amherst Andrew H. Fagg

Example 2: FCFS

Time

Job 1 ... 50 51 ... 90 91 ... 120 121 ... 140 141 ... 150

J1 1 ... 50

J2 1 ... 40

J3 1 ... 30

J4 1 ... 20

J5 1 ... 10

CMPSCI 377: Operating Systems Lecture 6, Page 14

Department of Computer Science, UMass Amherst Andrew H. Fagg

Example 2: Round Robin

Time

Job 1 2 3 4 5 ... 46 47 48 49 50 51 52 53 54 55 ...

J1 1 ... 10 11 12

J2 1 ... 10 11

J3 1 ... 10 11

J4 1 ... 10 11

J5 1 ... 10

CMPSCI 377: Operating Systems Lecture 6, Page 15

Department of Computer Science, UMass Amherst Andrew H. Fagg

Example 2: Round Robin (cont)

Time

Job 51 52 53 54 ... 87 88 89 90 91 92 93 ... 118

J1 11 ... 20 21 30

J2 11 ... 20 21

J3 11 ... 20 21

J4 11 ... 20

J5

CMPSCI 377: Operating Systems Lecture 6, Page 16

Department of Computer Science, UMass Amherst Andrew H. Fagg

Example 2: Round Robin (cont)

Time

Job 118 119 120 121 122 ... 139 140 141 ... 150

J1 30 31 ... 40 41 ... 50

J2 30 31 ... 40

J3 30

J4

J5

CMPSCI 377: Operating Systems Lecture 6, Page 17

Department of Computer Science, UMass Amherst Andrew H. Fagg

Round Robin Scheduling: Example 2

˛ Example: 5 jobs, of length 50, 40, 30, 20, and 10 seconds each, time

slice 1 second, context switch time of 0 seconds

Completion Time Wait Time

Job length FCFS Round Robin FCFS Round Robin

1 50 50 150 0 100

2 40 90 140 50 100

3 30 120 120 90 90

4 20 140 90 120 70

5 10 150 50 140 40

Average 110 110 80 80

CMPSCI 377: Operating Systems Lecture 6, Page 18

Department of Computer Science, UMass Amherst Andrew H. Fagg

SJF/SRTF: Shortest Job First

˛ Schedule the job that has the least (expected) amount of work (CPU

time) to do until its next I/O request or termination.

˛ Advantages:

{ Provably optimal with respect to minimizing the average waiting time

{ Works for preemptive and non-preemptive schedulers

{ Preemptive SJF is called SRTF - shortest remaining time ¯rst

) I/O bound jobs get priority over CPU bound jobs

˛ Disadvantages:

{ Impossible to predict the amount of CPU time a job has left

{ Long running CPU bound jobs can starve

CMPSCI 377: Operating Systems Lecture 6, Page 19

Department of Computer Science, UMass Amherst Andrew H. Fagg

SJF: Example

˛ 5 jobs, of length 50, 40, 30, 20, and 10 seconds each, time slice 1 second,

context switch time of 0 seconds

Completion Time Wait Time

Job length FCFS Round Robin SJF FCFS Round Robin SJF

1 50

2 40

3 30

4 20

5 10

Average

CMPSCI 377: Operating Systems Lecture 6, Page 20

Department of Computer Science, UMass Amherst Andrew H. Fagg

SJF: Example

˛ Example: 5 jobs, of length 50, 40, 30, 20, and 10 seconds each, time

slice 1 second, context switch time of 0 seconds

Completion Time Wait Time

Job length FCFS Round Robin SJF FCFS Round Robin SJF

1 50 50 150 150 0 100 100

2 40 90 140 100 50 100 60

3 30 120 120 60 90 90 30

4 20 140 90 30 120 70 10

5 10 150 50 10 140 40 0

Average 110 110 70 80 80 40

CMPSCI 377: Operating Systems Lecture 6, Page 21

Department of Computer Science, UMass Amherst Andrew H. Fagg

Problems with SJF:

˛ It is impossible to predict the amount of CPU time a job has left to

perform. What we try to do is to use the previous activity to predict the

future. (It is nice to know an optimal solution, but since perfect

prediction is impossible, how do we approximate this knowledge?)

˛ Analysis does not acknowledge the fact that many jobs rely heavily on

I/O.

˛ Modi¯ed algorithm: favor I/O bound jobs since they typically have the

least amount of work before the next I/O operation.

˛ But, must be careful: long running CPU-bound jobs can starve.

CMPSCI 377: Operating Systems Lecture 6, Page 22

Department of Computer Science, UMass Amherst Andrew H. Fagg

Multilevel Feedback Queues (MLFQ)

˛ Multilevel feedback queues use past behavior to predict the future and

assign job priorities

) overcome the prediction problem in SJF

˛ If a process is I/O bound in the past, it is also likely to be I/O bound in

the future (we assume that programs are not completely random).

˛ To exploit this behavior, the scheduler can favor jobs that have used the

least amount of CPU time, thus approximating SJF.

˛ This policy is adaptive because it relies on past behavior and changes in

behavior result in changes to scheduling decisions.

CMPSCI 377: Operating Systems Lecture 6, Page 23

Department of Computer Science, UMass Amherst Andrew H. Fagg

Approximating SJF: Multilevel Feedback Queues

˛ Multiple queues with diŽerent priorities.

˛ Use Round Robin scheduling at each priority level, running the jobs in

highest priority queue ¯rst.

˛ Once those ¯nish, run jobs at the next highest priority queue, etc. (Can

lead to starvation.)

˛ Round robin time slice increases exponentially at lower priorities.

G F A

B

E

C

D

Priority

1

2

3

4

Time Slice

1

8

4

2

CMPSCI 377: Operating Systems Lecture 6, Page 24

Department of Computer Science, UMass Amherst Andrew H. Fagg

Adjusting Priorities in MLFQ

˛ Job starts in highest priority queue.

˛ If job's time slices expires, drop its priority one level.

˛ If job's time slices does not expire (the context switch comes from an I/O

request instead), then increase its priority one level, up to the top priority

level.

) CPU bound jobs drop like a rock in priority and I/O bound jobs stay at a

high priority.

CMPSCI 377: Operating Systems Lecture 6, Page 25

Department of Computer Science, UMass Amherst Andrew H. Fagg

Multilevel Feedback Queues: Example 1

˛ 3 jobs, of length 30, 20, and 10 seconds each, initial time slice 1 second,

context switch time of 0 seconds, all CPU bound (no I/O), 3 queues

Completion Time Wait Time

Job length RR MLFQ RR MLFQ

1 30

2 20

3 10

Average

Time

Queue Slice Job

1 1

2 2

3 4

CMPSCI 377: Operating Systems Lecture 6, Page 26

Department of Computer Science, UMass Amherst Andrew H. Fagg

Multilevel Feedback Queues: Example 1

Time

Job 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

J1

J2

J3

CMPSCI 377: Operating Systems Lecture 6, Page 27

Department of Computer Science, UMass Amherst Andrew H. Fagg

Multilevel Feedback Queues: Example 1

Time

Job 1 2 3 4 5 6 7 8 9

J1 1 # Q2 3 # Q3

J2 1 # Q2 3 # Q3

J3 1 # Q2 3 # Q3

CMPSCI 377: Operating Systems Lecture 6, Page 28

Department of Computer Science, UMass Amherst Andrew H. Fagg

Multilevel Feedback Queues: Example 1 (cont)

Time

Job 10 11 12 13 14 15 16 17 18 19 20 21

J1 4:::7

J2 4:::7

J3 4:::7

Time

Job 22 23 24 25 26 27 28 29 30 31 32

J1 8:::11

J2 8:::11

J3 8:::10

... and round robin for J1 and J2 from here...

CMPSCI 377: Operating Systems Lecture 6, Page 29

Department of Computer Science, UMass Amherst Andrew H. Fagg

Multilevel Feedback Queues: Example 1

˛ 3 jobs, of length 30, 20, and 10 seconds each, initial time slice 1 second,

context switch time of 0 seconds, all CPU bound (no I/O), 3 queues

Completion Time Wait Time

Job length RR MLFQ RR MLFQ

1 30 60 60 30 30

2 20 50 53 30 33

3 10 30 32 20 22

Average 46 2/3 48 1/3 26 2/3 28 1/3

Time

Queue Slice Job

1 1 11

1; 21

2; 31

3

2 2 13

5; 23

7; 33

9

3 4 17

13; 27

17; 37

21

111

25; 211

29; 310

32 : : :

CMPSCI 377: Operating Systems Lecture 6, Page 30

Department of Computer Science, UMass Amherst Andrew H. Fagg

Multilevel Feedback Queues: Example 2

˛ 3 jobs, of length 30, 20, and 10 seconds, the 10 sec job has 1 sec of I/0

every other sec, initial time slice 2 sec, context switch time of 0 sec, 2

queues.

Completion Time Wait Time

Job length RR MLFQ RR MLFQ

1 30

2 20

3 10

Average

Time

Queue Slice Job

1 2

2 4

CMPSCI 377: Operating Systems Lecture 6, Page 31

Department of Computer Science, UMass Amherst Andrew H. Fagg

Multilevel Feedback Queues: Example 2

Time

Job 1 2 3 4 5 6 7 8 9 10

J1

J2

J3

Time

Job 11 12 13 14 15 16 17 18 19 ... 22

J1

J2

J3

CMPSCI 377: Operating Systems Lecture 6, Page 32

Department of Computer Science, UMass Amherst Andrew H. Fagg

Multilevel Feedback Queues: Example 2

Time

Job 1 2 3 4 5 6 7 8 9 10

J1 1:::2 # Q2 3

J2 1:::2 # Q2 3

J3 1:::2 I=O 3:::4 I=O

CMPSCI 377: Operating Systems Lecture 6, Page 33

Department of Computer Science, UMass Amherst Andrew H. Fagg

Multilevel Feedback Queues: Example 2

Time

Job 1 2 3 4 5 6 7 8 9 10

J1 1:::2 # Q2 3

J2 1:::2 # Q2 3

J3 1:::2 I=O 3:::4 I=O

Time

Job 11 12 13 14 15 16 17 18 19 ... 22

J1 4 5:::8

J2 4

J3 5:::6 I=O 7:::8 I=O 9:::10 I=O

... Round Robin from here between J1 and J2...

CMPSCI 377: Operating Systems Lecture 6, Page 34

Department of Computer Science, UMass Amherst Andrew H. Fagg

Multilevel Feedback Queues: Example 2

˛ This is one possible solution. Other solutions are possible depending on

when the 10 sec job starts its I/O.

Completion Time Wait Time

Job length RR MLFQ RR MLFQ

1 30 60 60 30 30

2 20 50 50 30 30

3 10 30 19 20 8

Average 46 2/3 43 26 2/3 22 1/3

Time

Queue Slice Job

1 2 12

2; 22

4; 32

6

34

9; 36

12; 38

15; 310

18

2 4 13

7; 23

10; 14

13; 24

16; 18

22; 28

26;

112

30; 212

34; 116

38; 216

42; 120

46; 220

50;

130

60

CMPSCI 377: Operating Systems Lecture 6, Page 35

Department of Computer Science, UMass Amherst Andrew H. Fagg

Improving Fairness

Since SJF is optimal, but unfair, any increase in fairness by giving long jobs

a fraction of the CPU when shorter jobs are available will degrade average

waiting time.

Possible solutions:

˛ Give each queue a fraction of the CPU time. This solution is only fair if

there is an even distribution of jobs among queues.

˛ Adjust the priority of jobs as they do not get serviced (Unix originally did

this.) This ad hoc solution avoids starvation but average waiting time

suŽers when the system is overloaded because all the jobs end up with a

high priority,.

CMPSCI 377: Operating Systems Lecture 6, Page 36

Department of Computer Science, UMass Amherst Andrew H. Fagg

Lottery Scheduling

˛ Give every job some number of lottery tickets.

˛ On each time slice, randomly pick a winning ticket.

˛ On average, CPU time is proportional to the number of tickets given to

each job.

˛ Assign tickets by giving the most to short running jobs, and fewer to long

running jobs (approximating SJF). To avoid starvation, every job gets at

least one ticket.

˛ Degrades gracefully as load changes. Adding or deleting a job aŽects all

jobs proportionately, independent of the number of tickets a job has.

CMPSCI 377: Operating Systems Lecture 6, Page 37

Department of Computer Science, UMass Amherst Andrew H. Fagg

Lottery Scheduling: Example

˛ Short jobs get 10 tickets, long jobs get 1 ticket each.

# short jobs / % of CPU each % of CPU each

# long jobs short job gets long job gets

1/1 91% 9%

0/2

2/0

10/1

1/10

CMPSCI 377: Operating Systems Lecture 6, Page 38

Department of Computer Science, UMass Amherst Andrew H. Fagg

Lottery Scheduling Example

˛ Short jobs get 10 tickets, long jobs get 1 ticket each.

# short jobs / % of CPU each % of CPU each

# long jobs short job gets long job gets

1/1 91% (10/11) 9% (1/11)

0/2 50% (1/2)

2/0 50% (10/20)

10/1 10% (10/101) < 1% (1/101)

1/10 50% (10/20) 5% (1/20)

CMPSCI 377: Operating Systems Lecture 6, Page 39

Department of Computer Science, UMass Amherst Andrew H. Fagg

Summary of Scheduling Algorithms:

FCFS: Not fair, and average waiting time is poor.

Round Robin: Fair, but average waiting time is poor.

SJF: Not fair, but average waiting time is minimized assuming we can

accurately predict the length of the next CPU burst. Starvation is

possible.

Multilevel Queuing: An implementation (approximation) of SJF.

Lottery Scheduling: Fairer with a low average waiting time, but less

predictable.

) Our modeling assumed that context switches took no time, which

is unrealistic.

CMPSCI 377: Operating Systems Lecture 6, Page 40

Department of Computer Science, UMass Amherst Andrew H. Fagg

Next Time

˛ Friday: Java threads and scheduling.

˛ Friday: Lab 2 handed out oącially

˛ Monday: Synchronization: Chapter 7 (¯rst 9 pages)

CMPSCI 377: Operating Systems Lecture 6, Page 41