Scheduling: Proportional Share

Tickets Map to Desired Shares

Proportional-share scheduling stops treating shortest completion or fastest response as the primary goal and instead lets every job obtain processor time in proportion to its ticket count. The system records the grand total of tickets and, at the start of each slice, draws a number uniformly from that range; the job that owns the number runs immediately. More tickets yield a higher chance of being chosen, so over a long period the observed occupancy approaches the ticket ratio.

Steps of the Random Draw

Implementation needs only a list of jobs and their ticket counts. After a winning number is drawn, the list is walked while tickets are accumulated; the walk stops as soon as the running sum exceeds the winner, and that job is selected. Placing high-ticket jobs near the front shortens the average walk, yet the order never changes correctness. Because successive draws are independent, the observed ratio can swing noticeably in a short interval.

Three Practical Ticket Operations

A user may first distribute tickets among its own jobs in a private currency; the system later converts those amounts into global tickets. A client job can temporarily hand its tickets to a server that is working on its behalf, giving the server higher priority while the request is outstanding, then reclaim the tickets. Inside a mutually trusting set of jobs, one job may raise or lower its own ticket count to advertise a momentary need without further negotiation.

Fairness Improves with Longer Runs

Each decision is an independent random event, so the shorter a job runs the more its slice count may deviate from the ticket ratio. As competition continues, the law of large numbers takes effect and the observed share moves closer to the target encoded by the tickets. The method therefore suits long-running jobs that do not demand exact instantaneous fairness.

Pitfalls

• Treating the random draw as a deterministic quota and expecting short jobs to receive exactly the time implied by their tickets.
• Allowing jobs to inflate their own tickets in an untrusted setting, so one job can easily seize the entire processor.
• Using a low-quality pseudo-random generator, so shares fail to converge even after a long run.

Minimum C11 · complete program · Download .c

#include <stdio.h>

int main(void) {
    int tickets[2] = {75, 25};
    char names[2] = {'A', 'B'};
    int winners[20] = {42, 81, 15, 67, 92, 3, 55, 78, 29, 88, 11, 60, 73, 95, 8, 34, 49, 71, 19, 84};
    printf("Winning tickets: ");
    for (int i = 0; i < 20; i++) {
        printf("%d ", winners[i]);
    }
    printf("\nSchedule: ");
    for (int i = 0; i < 20; i++) {
        int winner = winners[i];
        int counter = 0;
        int j;
        for (j = 0; j < 2; j++) {
            counter += tickets[j];
            if (counter > winner) {
                break;
            }
        }
        printf("%c ", names[j]);
    }
    printf("\n");
    return 0;
}

Compile locally

gcc -std=c11 -Wall -Wextra -Wpedantic -Werror ostep-09-lottery.c -o example && ./example

Expected result

Winning tickets: 42 81 15 67 92 3 55 78 29 88 11 60 73 95 8 34 49 71 19 84 
Schedule: A B A A B A A B A B A A A B A A A A A B 

CHECK YOUR UNDERSTANDING

Close the answer. Explain it.

Job P holds 65 tickets and job Q holds 35. Supply any five winning numbers between 0 and 99 and the resulting run sequence. Why is it almost impossible for these five draws to produce exactly the 3.25:1.75 ratio?

Check the sources

• OSTEP chapter PDF

Drafts and official chapters change. The version mark is only the example’s minimum.