Questions On Proportional Share Thread Scheduling (Page 2 of 2) in pdf

CS 3430/5430

Lecture 5

Name:_____________

b) weighted fair queuing (WFQ)/stride scheduling/virtual time round-robin scheduling (VTRR) - uniform

time-slice, but smaller allocation threads sit out some round-robin rotations through the runnable-thread list.

Consider three threads we want to run with the following proportions. If we want to run all three in 32 ms with a

4 ms uniform time-slice, what percentage of the round-robin rotations would a thread participate?

Thread

Proportion of CPU

Percentage participation in

round-robin rotations

Draw the Gantt chart for this schedule

c) lottery scheduling - uniform time slice, but large allocation threads win lottery more often

Consider three threads we want to run with the following proportions.

Thread

Proportion of CPU

Range of lottery tickets for thread

If there is a 4 ms uniform time-slice and the random numbers used for scheduling are 3, 5, 1, 4, 5, 8, 2, 7, 8, 1, 6,

then draw the Gantt chart for this schedule.

3. Lottery scheduling is rarely used on real systems because a thread might have bad luck and not “win” the

scheduling lottery for a long time (e.g., a second). Which performance criteria (throughput or response time) is

most effected by a lottery scheduler?

4. “Recent” versions of Linux use the Completely Fair Scheduler (CFS) to schedule on a processor (with an

independent load-balancing mechanism to distribute threads across processors). Characteristics of CFS are:

each thread has a niceness level (-20 [highest priority] to 19 [lowest priority]). Each niceness level has a

weight associated with it (e.g., niceness 0 →1024, 5 →335, etc. via some geometric progression).

the scheduler round-robins through the threads trying to complete a “pass” in a target time (e.g. 6 ms default

on uniprocessor)

each thread is given a time slice proportional to its weight/(total weights of all runnable threads)

(a minimum time slice default is used if proportional time slice is less)

a) Which type of proportional-share scheduling is CFS?

b) Which performance criteria (throughput or response time) is most effected by adjusting the “target time” for a

round-robin pass?

c) Which performance criteria (throughput or response time) is most effected by adjusting the “minimum time

slice”?

Lecture 5 Page 2

Questions On Proportional Share Thread Scheduling Page 2