Lecture 11 starts here

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
    struct node_t *current = head;

    // 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

Lecture 12 starts here

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

A matter of perspective