CS 111 - Lecture 19 - 3 June 2010
by Adam Wyatt

Scheduling

Scheduling:

1. Limited resources
Too many users/processes/whatever

• Long term scheduling
• Which processes are admitted into system?
• Medium term scheduling
• Which processes reside in RAM?
• Short term scheduling
• Which processes have the CPU?

For now assume a single level:
2. Scheduling metrics

Process:
                         Exec     first (write)                   exit
__________________|_______|______________________|_____________
Time:  ^arrival    ^start  ^first Build                 ^finish output
            |---wait time---|
            |---response time---|
            |--------latency/ turnaround time (TT)--------|

Context switching time - time to go from one process to the other

Aggregate statistics:
Utilization - % of CPU time spent doing useful work
Throughput - rate of useful work being done Σ(run times)/(total time)

Simple scheduler:

First come first served: [assume 1 CPU]
|AAAAA|BB|CCCCCCCCC|DDDD
Utilization = almost 1. 20/(20+4d)
Avg wait time = 5.5 + 2.5d
Avg turnaround time = 10.5 + 2.5d

Shortest Job First: [assumption: know job length]
|AAAAA|BB|DDDD|CCCCCCCCC
Utilization = almost 1. 20/(20+4d) [same as before]
Avg wait time = 4.5 + 2.5d
Avg turnaround time = 10.5 + 2.5d

Shortest Job First + preemption:
|A|BB|DDDD|AAAA|CCCCCCCCC
Avg wait time = 2.25 + 2.5d

FCFS + preemption = round robin (RR):
|A|B|C|D|A|B|C|D|A|C|D|A|C|D|A|CCCCC -- Buggy!
Avg wait time = 2.5d
Avg turnaround = 12.25 + 11.25d

Priorities:
Set by user or set by system
FCFS: priority = arrival time
SJF: priority = runtime
Real time apps set as very high priority

Real-time Scheduling:
Constraints that must be hit, or else

Hard real-time:
Cannot miss deadline
Ex. Brakes, nuclear reactors

Soft real-time:
If you miss deadline, drop that ask
Ex. Video player
Earliest meetable deadline first
Rate-monotonic scheduling

Ex. Mars Rover
3 priorities: low, medium, high
Priority inversion occurred.
While a low priority process occupied a spin lock, a medium process started.
Then the low level process could never finish and release the spin lock.
Therefore the high priority process could not run.
Solve by high priority task lending priority to low priority task with the spin lock

More Scheduling:
1 CPU
1 disk
Many I/O requests. Which to do 1st?
Disk expensive to seek + rotational latency


Simple abstraction:

Disk:_____________________________________________________
           ^read head        ^desired location
Cost to access = |i-h| = |(desired location) - (read head location)|

Simplest disk scheduler:
FCFS:
- lots of seeking
+ no starvation


SSTF Shortest Seek Time First:
+ minimizes seek time
+ maximizes throughput
- starvation

FCFS[in batches] + SSTF[within a batch]:
+ no starvation
+ faster than FCFS
- not as fast as SSTF

Elevator Scheduling:
= SSTF in a positive direction
- not fair

Cyclic elevator scheduling:
- less throughput
+ fair

Anticipatory scheduling:
Ta 0,1,2,3
Tb 10000000, 10000001, 100000002
This would cause long bounce between sectors
Minimize seeks by guessing future requests. DALLYING

Cloud Computing Intro:

Advantages:

• Large shared resources:
• Economies of Scale
• Customer:
• Short term commitment
• Can grow as needed instantly
• Good for unknown demand or varying demand

Problems/issues:

• Payment
• OS must meter activities (in a way both customer & supplier trust)
• Resource management
• Security
• Data confidentiality
• Standard techniques:
• Encrypt connection to cloud
• Encrypt all files in the cloud
• Software licensing
• Data transfer bottlenecks
• Vendor lock-in
• TRUST [Reflections on Trusting Trust. ACM]