Scribes: Cameron Ketcham and Nick Graham

Scheduling

Scheduling Metrics

• how can we prove: "the Linux scheduler sucks?"

Scheduling metrics have been studied long before the first scheduler was made for a CPU. Big companies such as Ford wanted an optimal way put their cars together, making sure they had all the parts at the right times.

Metrics

Task Timeline for factories

• arrival - the first time you know you need to complete a task
• execution begins - first instruction executed
• first output - the first time you know you need to complete a task
• execution ends - last instruction finshed
• wait time - the time between the first arrival and when execution begins
• response time - the time between arrival and the first output (useful for interactive applications)
• turnaround time (latency) - the time between arrival and when the execution ends

the definition of task is critical

• browser opening and closing
• getting a single webpage

when measuring these quantities we use statistics

• average (mean) - the wait time or latency etc.
• variance - how bursty, unreliable, flaky

As programmers we want to try keep the variance small so the users wait about the same amount of time for the same types of tasks.

Side note: Scheduling can apply to CPU (time), disk, memory (RAM), network, battery, etc. We will be dealing with CPU (time)

Statistics for multiple tasks

• throughput (# of Jobs/second)
• fairness - roughly corresponds to 1/(variance in latency etc)

but these two goals conflict

Really Simple Scheduler - FCFS: First Come First Served (FIFO)

example

Schedule

AAAAAδBBδCCCCCCCCCδDDDD

latency = wait time + run time
response = wait time + time to first output

utilization = real work / total work = 20 / (20 + 3δ)
average wait = 5.5 + 1.5δ

FCFS - good properties

• good throughput

FCFS - downside

• not fair
• Because long tasks tend to be CPU-bound, they set up a convoy effect (imagine a lot of fast small cars stuck behind a big slow truck)
• I/O devices are underutilized

Shortest Job First

scheduler always chooses the shortest runnable task (assuming it knows the length of the jobs)

Schedule for SJF

AAAAAδBBδDDDDδCCCCCCCCC

processes A and B are the same as before
utilization = real work / total work = 20 / (20 + 3δ) (same as FCFS)
average wait = 4.25 + 1.5δ (better!)

SJF - good properties

• can be proven to always have the smallest possible average wait time

SJF - downside

• starvation is possible for long jobs (if small jobs keep appearing)

Round Robin (RR)

Preemption increases the power of the scheduler

the units of time that each process is allowed to run for is called a quantum. For this example we will use Q=2

Schedule for RR

AAδBBδCCδDDδAAδCCδDDδAδCCCCC

traded off wait time for utilization
utilization = real work / total work = 20 / (20 + 8δ)
average wait = 1.5 + 1.5δ

FCFS: starvation is impossible
SJF: starvation is possible
RR: starvation? YES if new tasks are put at the beginning of the queue. NO if they are put at the end.

Families

Priority Scheduling

Always schedule the highest priority task first.
priority 1 > priority 2
Priorities can be external (set by user) or internal (set by the OS)
Priority scheduling has starvation problems if any priority scheme is allowed.
One solution: subtract age of task from its priority.

Multi level priority queues

System level queue and interactive tasks queue.
Different algorithm for each queue.
Batch tasks: you can move stuff from one queue to another.

Real Time Schedules

Hard real time

Soft real time

Synchronization

Coordinate actions (of multiple threads) in a shared address space

Fix race condition

Example

int balance = 10;

void deposit(unsigned int n) { // Eggert tries to deposit $1
	balance+= n; 
}

(1)  LD     balance, r1 
(5)  add    n, r1 
(6)  st     r1, balance 

void withdraw(unsigned int n) { // Nephew tries to withdraw $1
	if(n<=balance)
		balance-= n; 
}

(2)  LD     balance, r1 
(3)  sub    n, r1 
(4)  st     r1, balance 

When we're done there are $11 in the account!

_______interface_________
|                        |
|       SYSTEM           |
|                        |
| (stuff going on in //) |
|________________________|