Operating systems

Proportional share

Prashanth L.A.


Lecture 11 starts here

Proportional share (aka fair share) scheduler

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

Basic concept: Tickets represent your share


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

Solution: Use lotteries \(\Leftrightarrow\) randomness

Lottery scheduling

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



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

Ticket inflation


    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

unfairness metric U is the time A completes divided by the time B completes


In the long run, everything is fair

Other problems with lottery scheduling? (Poll)


Lecture 12 starts here

Stride scheduling




Take it in your stride and forget lotteries!

The Linux Completely Fair Scheduler (CFS)


A matter of perspective