09 – Scheduling: Proportional Share

Proportional Share Scheduler

aka Fair-share scheduler

Proportional Share Scheduler

guarantee that each process obtains a certain percentage of CPU time

Proportional Share Scheduler

not necessarily optimizing for turnaround time or response time

Tickets

represent the share of a resource that a process (or user) should receive

Percent of tickets

represents its share of the system resource in question

Lottery

can be held every time slice

Avoids strange corner case behaviors

why random? (1)

Lightweight

why random? (2)

Fast

why random? (3)

Ticket Currency

a user allocates tickets among their own processes in whatever currency they would like

Ticket Currency

the system converts the local currency into the correct global currency value

Ticket Transfer

a process can temporarily hand off its tickets to another process

Ticket Transfer

useful in client-server application with server doing tasks on behalf client

Ticket Inflation

a process can temporarily raise or lower the number of tickets it owns

Ticket Inflation

if any one process needs more CPU time, it can boost its tickets, assumes that a group of processes trust each other to prevent abuse

Fairness metric

the time the first process completes divided by the time that the second process completes

Stride Scheduling

randomness occasionally will not deliver good results especially for processes with short run times

Deterministic Fair Share Scheduler

stride scheduling, invented by Waldspurger

Linux Completely Fair Scheduler

fairely divide a CPU evenly among all competing processes

Virtual Runtime

CFS, uses a counting-based technique called

Lowest vruntime

CFS, when scheduling decision time occurs, pick the process with the _ _

Periodic Timer Interrupt

CFS, can only make decision at fixed time intervals, not affected if time slice is not a multiple of the interrupt timer interval time

Sched_latency and min_granularity

CFS, 2 control parameters

Sched_latency

determines how long one process shoul run before considering a switch

48 ms

typical values of sched_latency

Sched_latency / n processes

formula of sched_latency, time slice for a process

min_granularity

to address too many processes running

6 ms

minimum time slice for a process despite a large n, typically set to

Weighting

allows user/admins to control process priority (nice and renice progams)

+

sign that means lower priority

-

sign that means higher priority

Red Black Trees

how to efficiently (as quickly as possible) find the next process to run?

Height Balanced Tree

logarithmic search time compared to linear search time for lists

Running

CFS places only _ on the RB tree