2023-08-23

# Proportional share (aka fair share) scheduler

• How can we design a scheduler to share the CPU in a proportional manner?

• What are the key mechanisms for doing so?

• How effective are they?

Guarantee that each job gets a certain percentage of CPU time
Forget turnaround and response times

# Basic concept: Tickets represent your share

## Example

• Two processes: A and B
• Process A has 75 tickets
• Process B has 25 tickets

Want: A gets 75% of CPU and B 25%

Solution: Use lotteries $$\Leftrightarrow$$ randomness

# Lottery scheduling

• The scheduler picks a winning ticket uniformly at random
• Process holding the ticket gets the CPU
• Example
• There are 100 tickets
• Process A has 75 tickets: 0 ~ 74
• Process B has 25 tickets: 75 ~ 99
• Scheduler picks a random number in $$\{0,\ldots,99\}$$
Number: 63  85  70  39  76  17  29  41  36  39  10  99  68  83  63
Schedule: A B A A B A A A A A A B A B A A A A A A 

B got $$20\%$$ instead of $$25\%$$. Longer run $$\implies$$ sample averages would agree with their mean values

# Ticket currency

• Users allocate tickets among their own jobs in whatever currency they would like;
• OS converts said currency into the correct global value

## Example

• Users A, B with 100 tickets each
• User A has two procs A1, A2; B has one proc B1
User A -> 500 (A’s currency) to A1 -> 50 (global currency)
-> 500 (A’s currency) to A2 -> 50 (global currency)
User B -> 10 (B’s currency) to B1 -> 100 (global currency)

# Some more ticketing stuff

## Ticket transfer

• process can temporarily hand off its tickets to another process
• useful in client-server model

## Ticket inflation

• a process can temporarily raise or lower the number of tickets it owns
• Dont trust, cut inflation

# Implementation

    int counter            = 0;
int winner             = random() % gtickets; // get winner

// loop until the sum of ticket values is > the winner
while (current) {
counter = counter + current->tickets;
if (counter > winner)
break; // found the winner
current = current->next;
}
// current is the winner: schedule it...

# Unfairness metric

• Study completion time of two jobs A, B
• Both have 100 tickets and run time $$R$$
unfairness metric U is the time A completes divided by the time B completes

## Example

• A completes at 10, B at 20. $$U=?$$
• If both A, B complete almost at the same time, then $$U \approx 1$$

# In the long run, everything is fair

Other problems with lottery scheduling? (Poll)

# Problems

• How to assign tickets?
• Handling I/O

# Stride scheduling

• Deterministic fair-share scheduling

## Example

• Procs: A,B,C
• Tickets: 100, 50, 250
• Stride $$=$$ big number/tickets
• Strides: 100, 200, 40 with big number $$=$$ 10000

## Algorithm

• Each time a proc runs, pass value counter increments
• At any time, pick the process with the lowest pass value to run

# Take it in your stride and forget lotteries!

• C ran five times, A twice, and B just once, exactly in proportion to tickets 250, 100,50
• Lottery scheduling achieves the proportions probabilistically over time
• Is there any benefit to lotter scheduling?
• If a new proc enters, strides become complicated

# The Linux Completely Fair Scheduler (CFS)

• As each process runs, it accumulates vruntime
• When a scheduling decision occurs, CFS willpick proc with lowest vruntime

## Example

• sched_latency say 48ms, 4 procs A,B,C,D
• Time slice $$=\frac{48}{4}=12$$ms.

• Problem?
• Too many procs $$\Rightarrow$$ low time slice
• Fix: have a min timeslice