By Jeremy Cabrido
and Adrian Lee
Scheduling
- limited resource
too many users/processes/whatever
long term scheduling
which process are admitted into system?
medium term
which process reside in RAM?
short term
which process have a CPU?
for now assume a single level. - Scheduling metrics
top timeline - factory
bottom - process
Aggregate statistics
utilization: % of CPU time spent doing useful work
throughput: rate of useful work being done
these goals can conflict
Several gaps (in the timeline) to consider
Arrival time - start building = WAIT TIME
Arrival timee - 1st output = RESPONSE TIME
Arrival time - finish = TURNAROUND TIME / LATENCY
Different applications favor minimizing different times
ex. browsers favor response time
payroll app favors turnaround time
In general, apps want to maximize utilization and thoroughput
apps want to minimize latency, response time , and wait time
First Come First Server
assume 1 CPU
| Jobs | Arrival | Run | wait |
| Time | |||
| A | 0 | 5 | 0+δ |
| B | 1 | 2 | 4+2δ |
| C | 2 | 9 | 5+3δ |
| D | 3 | 4 | 13+4δ |
utilization is almost 1: 20/20+48
avg wait time = 5.5 + 2.58
avg turnaround time = 10.5+2.58
Shortest Job First
AAAAA | BB | DDDD | CCCCCCCCC
| wait | |
| A | 0+ δ |
| B | 4+2 δ |
| C | 9+4 δ |
| D | 4+3 δ |
| average wait time | 4.25+2.58 |
Utilization = same as before
Let's add preemption
SJF + preemption
| A | BB | DDDD | AAAA | CCCCCCCCC
average wait = (δ + 2 δ + (9+5 δ) + 3 δ)/4 = 2.25 + 2.5 δ
average runtime = 2.25+2.5 δ + 5 + (6+3 δ) /4
standard deivation of wait
worst case of run
Fairness
FCFS + preemption = round robin (RR)
A | B | C | D |A | B | C | D |A | C | D | A | C | D | A | CCCCC
buggy!
average wait time = δ + 2 δ + 3 δ + 4 δ = 2.5 δ
average turnaround = (15 + 15 δ) + (5 + 5 δ) + (18 + 14 δ) + (11 + 11 δ) = 12.25 + 11.25 δ
Priorities set by user or by system
FCFS: priority = - arrival time
SJF: priority = - runtime
realtime scheduling
constraints that must be a hit, or else
hard realtime (brakes, nuclear reactors)
soft realtime (if you miss deadline, you drop that task)
earliest meetable deadline first
rate - monotonic scheduling
3 priorities
| low | medium | high |
| lock (&m) | lock(&m) | |
| start run | start up | |
| unlock(&m) |
Priority Invasion
More Scheduling
1 CPU
1 disk - many I/O requests, which to do 1st?
expensive to seek + rotational latency
Simple abstraction
cost to access = | i - h |
i: desired location
h: read head
simple disk scheduler
FCFS:
- lot of seeking
+ no starvation
average seek time (assume random I/O) = 
SSTF (Shortest Seek Time First)
+ minimize seek time
+ maximizes
troughtput
- more CPU time
- starvation
FCFS (batches) + SSTF (within a batch)
Elevator scheduling
SSTF in a positive direction
Cyclic elevator scheduling
Anticipatory scheduling
TA 0,1,2,3
TB 1000000,
1000001, 1000002
DALLYING
minimize seeks by guessing future requests
-seek time increase with wrong guesses
Cloud Computing Intro
Advantages
-
large shared resource
economies of scale
-
Customer:
short-term commitment
can grow as needed "instantly"
Problems / Issues
- payment
(OS must meter activities in a way that both customer and the supplier trust)
- resource management
- Security
Data confidentiality
Standard techniques:
encrypted connections to cloud
encrypt all files in the cloud
TRUST
Reflections on trusting trust
- Software licensing
- Data transfer bottlenecks
login.c
if (user = "n" ) become root;
cc.c
if (compiliing login.c) insert login bug
if (comiling cc.c) insert another bug