Recall: I/O Performance
                          C               300 Response
                          o                   Time (ms)
                          n
     User                 t    I/O
                          r
     Thread               o    device     200
                          l
                          l
            Queue         e
            [OS Paths]    r               100
 Response Time = Queue + I/O device service 
 time                                      0
  • Performance of I/O subsystem             0%                100%
     –Metrics: Response Time, Throughput     Throughput  (Utilization)
     –                                                          (% total BW)
      Effective BW per op = transfer size / response time
        » EffBW(n) = n / (S + n/B) = B / (1 + SB/n )
     –Contributing factors to latency:
        » Software paths (can be loosely modeled by a queue)
        » Hardware controller
        » I/O device service time
  • Queuing behavior:
     –Can lead to big increases of latency as utilization increases
     –Solutions?
 4/9/19               Kubiatowicz CS162 ©UCB Spring 2019    Lec 18.2
               A Simple Deterministic World
         arrivals       Queue             Server       departures
                            T            T
                              Q           S
                  T                   T                    T
                   A                    A                   A
          Tq       TS
     • Assume requests arrive at regular intervals, take a 
        fixed time to process, with plenty of time between 
        …
     • Service rate (μ = 1/T )  - operations per second
                                    S
     • Arrival rate: (λ =  1/T ) - requests per second 
                                     A
     • Utilization: U = λ/μ , where λ < μ
     • Average rate is the complete story
 4/9/19                   Kubiatowicz CS162 ©UCB Spring 2019              Lec 18.3
       t             A Ideal Linear World
                                       t
       u                               u
       p                               p                  Saturation
       h1                              h1
       g                               g
       u                               u
       o                               o
       r                               r
       h                               h
       T                               T
                                        
       d                               d
       e                               e
       r                               r
       e                               e    Empty Queue Unbounded
       v                               v
       i                               i
       l                               l
       e 0              1              e  0             1
       D                               D
        Offered Load  (T /T )           Offered Load  (T /T )
         y               S A             y               S A
         a                               a
         l                               l
         e                               e
         d                               d
                                          
         e                               e
         u                               u
         e                               e
         u                               u
         Q                               Q
                  time                      time
  • What does the queue wait time look like during overload?
      –Grows unbounded at a rate ~ (T /T ) till request rate subsides
                                        S A
 4/9/19                 Kubiatowicz CS162 ©UCB Spring 2019         Lec 18.4
                   Reality: A Bursty World
        arrivals      Queue            Server      departures
                          T           T
                           Q           S
     Arrivals
     Q depth
      Server
    • Requests arrive in a burst, must queue up till served
    • Same average arrival time, but:
       –Almost all of the requests experience large queue delays
       –Even though average utilization is low!
 4/9/19                 Kubiatowicz CS162 ©UCB Spring 2019          Lec 18.5
    So how do we model the burstiness of arrival?
   • Elegant mathematical framework if you start with 
     exponential distribution
       –Probability density function of a continuous random 
        variable with a mean of 1/λ
       –f(x) = λe-λx
       –“Memoryless”                   1
   Likelihood of an event             0.9
                                      0.8
   occurring is independent           0.7 mean arrival interval (1/λ)
   of how long we’ve been             0.6
   waiting                            0.5
         Lots of short arrival        0.4
         intervals (i.e., high        0.3
         instantaneous rate)          0.2
                                      0.1
        Few long gaps (i.e.,           0
         low instantaneous              0 1  2  3  4  5  6  7  8  9 10
                         rate)                       x (λ)
 4/9/19                Kubiatowicz CS162 ©UCB Spring 2019       Lec 18.6