Prashanth L.A.

2023-08-23

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

- 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

- 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\}\)

- There are 100 tickets

```
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*

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

- 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)
```

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

- a process can temporarily raise or lower the number of tickets it owns
- Dont trust, cut 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...
```

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

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

**Other problems with lottery scheduling?** (Poll)

- How to assign tickets?
- Handling I/O

- Deterministic fair-share scheduling

- Procs: A,B,C
- Tickets: 100, 50, 250
- Stride \(=\) big number/tickets
- Strides: 100, 200, 40 with big number \(=\) 10000

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

- 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

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

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