Information Technology Reference
In-Depth Information
Giant optimization, but
7.4
Real-time scheduling
Meet deadlines by doing edf, but how do we keep from missing deadlines?
control theory: adjust processing rate to ensure meet goals, but if there's a
delay between adjusting the rate and seeing the change in your metric, then can
get an unstable system.
7.5
Queuing theory
7.5.1
Load v. response time
queuing delay {> response time increases when load increases < suppose system
takes 100ms to process each request suppose that requests arrive perfectly evenly
spaced what is response time (DRAW GRAPH) 1/sec 2/sec (every 500ms) 3/sec
(every 333 1/3 ms) ... 9/sec 9.99999/sec (every 100.001ms) 10.0001/sec (every
99.999ms) 10/sec (every 100ms exactly)
suppose requests arrive in bursts at the start of each second. What is re-
sponse time (DRAW GRAPH) 1/sec 2/sec ...
suppose requests arrive "randomly" { a bunch of dierent users sending re-
quests s.t., receiving a request from user A doesn't aect the expected time to
next request from some other user {> exponential distribution (dene); memo-
ryless
memoryless is an approximation, a model, that allows us to abstract away
time markov graph { we can calculate precisely how often system is in various
states these graphs allow us to calculate the impact of scheduling choices (such
as RR vs. FIFO) on response time and throughput
if arrivals/service times are random, scheduling is FIFO, and arrivals don't
depend on wait times, graph looks like this: t = 1/(1-utilization)
notice it is between "perfectly even" arrivals and "perfectly bursty" arrivals
what happens to queue length as we increase load? under perfectly even,
zero under perfectly bursty, size of burst under random, grows unbounded with
utilization
what happen to throughput as we increase load? ditto
Some more corner cases:
what if we increase load beyond what the system can handle? If arrivals are
independent of response time, then system will get innite queues { its not a
steady state.
