Proportional = Fair share

Instead of optimizing turnaround and response time, scheduler guarantee fair amount of CPU share.

Lottery Scheduling - Randomness

Each lottery tickets gives the different share per job.
It does not guarantee the perfect share that the ticket represents, but as the job takes more time, it approximates.

• Randomness:

1. Oftern avoids strange corner-case behaviours that a more traditional algorithm may have trouble handling.
2. Lightweight: It does not have to tract how much CPU the job used; but track how many tickets left.
3. Very fast: Since the decision is simply made by the ticket.

Method

• Ticket Currency: User can freely slice up the given tickets into its own currency. If user A has 100 tickets, it can gives 300 tickets to its programs…
• Ticket Transfer: Process can temporarily transfer the tickets to the another process. It is beneficial to client/server situation.
• Ticket Inflation: It is non-sense in the race condition, but between trusted processes, asks system it needs more tickets.

Implementation

It is very easy to implement - needs randommizer, data structures, total number of tickets.

1
2
3
4
5
6
7
8
9
10

int counter = 0;
int winner = getrandom(0, totaltickets);
node_t *current = head; // To Search job list
while (current){
    counter += current->tickets;
    if (counter > winner) break; 
    current = current->next;
}
// current is now the winner. So ready to run the winner process.
// If the list is descending order of ticekts, it can minimze the search process.

Stride Scheduling - deterministic

As can be seen, randomness can simplify the scheduler but it does not guarantee the exact proportions especially over short time scales.

• Stride Scheduling: a deterministic fair-share scheduler
  • Each job has a stride; inverse in proportion to the number of tickets it has.
  • Each time process runs, increment counter (called pass value) by its stride; track the total CPU usage.
  • Scheduler decides which process to run based on stride and pass values.
    • run the process has the lowest pass values, and increase by its stride.
      Then why do we use the lottery scheduling then?
  • Imagine if there is a new job assigned.
  • What the pass value should be?
  • Lotter scheduling does not have to care about process state (CPU usage, pass values). Only consider tickets.
  • Therefore, it is easier to add a new process in the list.

Summary

For these reasons, Proportional and stride scheduling are not widely used:

1. These approaches do not get along well with IO.
2. Hard to implement tickets allocation; how many to which?

In case of virtualization environment, say I would like to use 25% of system to run the virtual machine, proprotional scheduling might be useful.