cpu-sched-lottery-OSTEP9

Proportional-share scheduler, also known as a fair-share scheduler.
Focus on providing each job a guaranteed percentage of CPU time instead of optimizing turnaround or response time.
An early example: lottery scheduling, as introduced by Waldspurger and Weihl (1994).
Lottery scheduling involves "holding a lottery" to decide which process runs next, with more frequently running processes receiving more chances to win.

Tickets represent a process's share of a resource (CPU time).
Example:
- Process A has 75 tickets; Process B has 25 tickets.
- Objective: A receives 75% CPU time; B receives 25%.
The lottery scheduler operates every time slice, determining which process runs based on a lottery drawn from the total tickets.
Probability of winning is proportional to the number of tickets held by each process.

Lottery scheduling utilizes randomness which provides several benefits:
1. Avoids corner-case behaviors: Randomness prevents strange drawbacks that non-random algorithms face.
2. Low tracking requirement: Requires minimal state to track per-process allocations (just the number of tickets).
3. Speed: Fast decision-making as it relies on generating a random number.
Example of lottery output showing the results of winning tickets, influencing the scheduling of A and B:
- Sample winning tickets: [63, 85, 70, 39, 76, 17, 29, 41, 36, 39, ...]
- Resulting schedules reflect these random outcomes, impacting fairness.

Tickets can be manipulated via several useful mechanisms:
- Ticket Currency: Users can allocate tickets among their jobs as desired, with conversions made to a global value.
- Ticket Transfer: Processes can temporarily transfer tickets to one another for enhanced performance in scenarios like client-server operations.
- Ticket Inflation: Processes can adjust their ticket count to reflect their need, mainly in a trusted environment.

Essential components:
- Random number generator to select a winning ticket.
- Data structure to keep track of processes (like a linked list).
- Count of total tickets to facilitate selection.
Example code for determining the winning ticket revolves around traversing a job list and a counter totaling ticket values until exceeding the random number drawn.

Examines completion times of jobs competing with equal ticket shares and runtimes.
Fairness metric: F = time of first job finish / time of second job finish measures the comparative fairness as job lengths increase.
Graphs demonstrate that fairness improves significantly with longer job runtimes and multiple trials.

Major challenge of lottery scheduling: how to assign tickets effectively.
Possible approach: User-level ticket allocation, but this complicates scheduling efficacy.

An alternative to lottery scheduling, stride scheduling uses deterministic methods for CPU time allocation.
Each job has a stride value, inversely proportional to its ticket count, which gets updated as processes run.
Runs are influenced by maintaining minimum pass values for each process further emphasized by pseudocode for efficient management.

CFS designed to achieve fair-share scheduling with high efficiency.
Introduces virtual runtime (vruntime) to manage CPU time distribution.
- When pauses occur, vruntime helps maintain fairness without excessive context switches.
- Uses latency and granularity to optimize scheduling events.
Processes managed as trees (specifically red-black trees) to ensure fast job retrieval in large process pools.

The chapter outlines various methods of proportional-share scheduling, including notable scheduling algorithms like lottery and stride scheduling, with emphasis on implementation and fairness.
While many complex strategies exist, proportional-share scheduling proves valuable in many domains, such as cloud computing, where effective resource allocation is paramount.