Scheduling – The Glorified Bouncer

Problems

Limited resources
Too many processes

Goals

Long Term – Who is even admitted into the system. Permissions may restrict processes from even waiting for system time.

Medium Term – Once a process is allowed into the system does it reside in RAM or secondary storage. They can start running almost immediately if they are in RAM whereas secondary storage can take a long time to start.

Short Term – Who currently has the CPU's attention.

A good scheduler will try to meet all of these goals.

How to know if a scheduler is good -

Scheduling metrics date back past computers.

People who ran physical factories first did this. To build a car many tasks must be completed but there is only so much space, time, and workers.

TIME -

arrival – for order
start building
1^st car exists assembly line
finish

Process is start to finish.

Waiting for process to start is wait time.

Response time is the time until something is actually done from when started.

Turn around time is oder time to finish.

Context switch time is time to change from making A to making B.

Aggregate Statistics -

Utilization - % of CPU time spent doing useful work.
Throughput – rate of useful work being done = sum of run times divided by total time.

Goals

Max utilization and minimize all other times. Unfortunately these goals often conflict.

Simplest scheduler is a FIFO data structure and does not have problem of starvation.

Shortest job first can be faster than FIFO but does have the problem of starvation.

A preemptive scheduler has the best wait time but still has the problem of starvation.

Putting everything together gives a round robin scheduler that still has the problem of starvation.

First come first serve is often used for real time applications. The priority = -arrival time. This is often called hard realtime.

Soft realtime can be thought of as a media player that will simply drop a frame if a deadline is missed. The earliest meetable deadline is used for these applications but this is not fair.

mars rover

3 priorities

low medium high

lock(&m)

run start up lock(&m) but must wait

unlock(&m)

run forever and kept thing locked and high couldn't run because waiting on lock

priority inversion - lost mars rover

fix -> high priority spin temporarily gives low its high priority so low finishes and unlocks

doesn't matter on # of cpus

so far all scheduling has been for 1 cpu