EE 599-002: Review for Final Exam

In addition to the topics for the first exam, these are all things I think are important to know for the final exam.

7. Scheduling Aperiodic and Sporadic Jobs in Priority-Driven Systems
   1. Aperiodic Jobs
      1. Basic concepts and terms
         1. Budget
         2. Period
         3. Consumption
         4. Replenishment
      2. Polling Server

         Brief Description

         Check (poll) for aperiodic jobs every p_s. If any jobs ready (in aperiodic queue) then run them for e_s or until no more jobs are available.

         Budgeting rules

         Consumption

         1. Consume while running
         2. If no jobs in queue immediately consume entire budget

         Replenishment

         Replenish every p_s

         Schedulability

         Same as a periodic task (p_s, e_s)

      3. Deferrable Server

         Brief Description

         Replenish budget periodically, only consume when running

         Budgeting rules

         Consumption

         Consume only when running

         Replenishment

         Replenish every p_s

         Schedulability

         Fixed Priority

         Check time demand for each periodic task
         w_i(t) = e_i + b_i + e_s + ⌈(t-e_s)/p⌉e_s + Σ_k=1^i-1⌈t/p_k⌉e_k

         EDF

         For each task make sure density of periodic tasks plus extra utilization due to deferrable server is ≤ 1.
         Σ_k=1ⁿ(e_k/min(D_k,p_k) + u_s(1 + (p_s - e_s)/D_i) ≤ 1

      4. Sporadic Server for Fixed Priority Systems

         Brief Description

         Make aperiodic jobs behave like a periodic task, but get better response time than the polled server.

         Budgeting rules

         • t = the current time
         • t_r = last replenishment time
         • t_e = effective replenishment time
         • t_f = first time sporadic server gets to run since t_r
         • next_t_r = next replenishment time
         • BEGIN = start of last contiguous stream of jobs with priority higher than the sporadic sever
         • END = end of last contiguous stream of jobs with priority higher than the sporadic sever. If a higher priority job is running END = ∞.

         Consumption

         1. Consume when running
         2. Consume if sporadic server has run since t_r

         Replenishment

         Initialization

         budget = e_s; t_r = t

         when t = t_f

         if tf = END then
         	te = max(BEGIN, tr)
         else	
         	te = tf
         end
         next_tr = te + ps
         

         budget = e_s

         At t = next_t_r unless:

         1. if next_t_r < t_f (i.e., the sporadic server has been preempted by higher priority tasks since before t_r) then replenish the budget immediately after it is exhausted.
         2. all periodic tasks idle, budget = e_s at min(next_t_r, t_b)

         Schedulability

         Same as a periodic task (p_s, e_s)

      5. Sporadic/Backgroud Server

         Just like the basic sporadic server, but run aperiodic jobs when all periodic tasks are idle

      6. Cumulative Replenishment

         Like the basic sporadic server, but replenish by adding e_s to current budget. Budget left over from before t_r must be consumed before budget from after t_r.

      7. Sporadic Server for EDF

         Brief Description

         Make aperiodic jobs behave like a periodic task, but get better response time than the polled server.

         Budgeting rules

         • d_s = deadline of sporadic server

         Consumption

         1. Consume when running
         2. Consume if d_s ≠ nil and (sporadic server idle) and (no periodic job, J_i with d_i < d_s exists)

         Replenishment

         Initialization

         budget = e_s; t_r = t; t_e = d_s = nil

         when an aperiodic job arrives and aperiodic queue is empty

         if (only jobs with di < tr + ps have run in (tr, t) then
         	te = tr
         else
         	te = t
         end
         

         When t_e ≠ nil,

         ds = next_tr = te + ps
         

         budget = e_s

         At t = next_t_r unless:

         1. if next_t_r < t_f (i.e., the sporadic server has been preempted by higher priority tasks since before t_r) then replenish the budget immediately after it is exhausted.
         2. all periodic tasks idle, budget = e_s at min(next_t_r, t_b)

         Schedulability

         Same as a periodic task (p_s, e_s)

      8. Constant Utilization Sever
         • û_s = instantaneous utilization = execution time / period of all active jobs. (The book uses a '~' over the u instead of a '^' character, but HTML doesn't have a u with a '~'.)
         • e = execution time of aperiodic job

         Brief Description

         Schedule aperiodic jobs like sporadic jobs that use a constant instantaneous utilization

         Budgeting rules

         Consumption

         Consume only when running

         Replenishment

         Initialization

         e_s=0; d_s = 0

         When a job arrives and periodic job queue is empty

         if t  > ds then
         	ds = t + e / ûs
         	es = e
         end
         

         At server deadline, d_s

         if aperiodic server backlogged then
         	take next aperiodic job from queue
         	ds = t + e / ûs
         	es = e
         end
         

         Schedulability

         U + û ≤ 1

         Total Bandwidth Server

         Brief Description

         Schedule aperiodic jobs like sporadic jobs that use a constant instantaneous utilization

         Budgeting rules

         Consumption

         Consume only when running

         Replenishment

         Initialization

         e_s=0; d_s = 0

         When a job arrives and periodic job queue is empty

         ds = max(t, ds) + e / ûs
         es = e
         

         At server deadline, d_s

         if aperiodic server backlogged then
         	take next aperiodic job from queue
         	ds = t + e / ûs
         	es = e
         end
         

         Schedulability

         U + û ≤ 1

   2. Spoaradic Jobs
      1. EDF

         Basic strategy

         keep Δ_s ≤ 1 - Δ

         Acceptance test

         deadlines divide time into intervals
         For each interval k, and e, d of the sporadic job, verify that e / (d - t) + Δ_s,k ≤ 1 -Δ
         

      2. Fixed Priority

         Basic Strategy

         Run sporadic jobs in a sporadic server. Schedule sporadic jobs using EDF amongst themselves.

         Schedulability test

         if ⌊ (d_s,i - t)/p_s⌋e_s - e_s,i - Σ_ds,k<ds,i(e_s,k - ξ_s,k) ≥ 0

      3. Resources and Resource Access Control
         1. Mutual exclusion and critical sections
         2. Effects of contention
         3. Avoiding unbounded priority inversion

            	Non-Preemptive Critical Section	Priority Inheritance Protocol	Priority Ceiling Protocol	Stack-Based Priority Ceiling	Preemption Ceiling
            Strategy	Allow only one job in a critical section at a time	When a job blocks waiting for a reasource, any lower priority jobs that need to run to release the resource inherit the first job's priority	Only jobs with priority higher than current ceiling can lock resources	Like priority ceiling, but block jobs unless they can run to completion without being blocked	Extend priority ceiling to EDF with low overhead
            Jobs not using related resources blocked by current job	Y	N	N	N	N
            Need prior knowledge of resource usage?	N	N	Y	Y	Y
            Prevents deadlock?	Y	N	Y	Y	Y
            Jobs block one time or less?	Y	N	Y	Y	Y
            Avoidance blocking	N	N	Y	Y	Y
            Blocking time with k self suspensions	bi,k(ss) + (k+1)max(bi(rc),bi(np))	bi,k(ss) + max(k+1,vr)bi(rc) + min(k+1,vn)bi(rc)	bi,k(ss) + (k+1)bi(rc) + (k+1)bi(np)

      11. Power-aware scheduling
          1. Reduce dynamic power by reducing frequency and voltage
          2. Static - choose frequency such that all jobs surely complete
          3. Dynamic Voltage (and Frequency) Scaling
             1. ccEDF - adjust instaneous utilization as jobs complete
             2. Feedback DVS - greedily execute current jobs slowly hoping it and others will finish early
11. Real-Time Communication
    1. Message models
    2. Service Disciplines

       Discipline	Acceptance	Scheduling Complexity	End-to-End Delay (k switches)	End-To-End Jitter	Buffer Space	Benefits / Comments
       Priority Based
       WFQ	O(1)	O(n)	&Mac178; E/u + k(e+1)	c×k	c×k	delay & throughput independent of other streams
       Delay-EDD	O(1)	O(log n)	&Mac178; D	c×k	c×k	Schedule like EDF
       Jitter-EDD	O(1)	O(log n)	&Mac178; D	c	c	buffer space independent of k
       WRR Disciplines
       Greedy WRR	O(1)	O(1)	pi + (k-1)RL	pi - ei + (k-1)(RL-1)	c×k	can use all available BW
       S&G WRR (synch. frames)	O(1)	O(1)	pi + kRL	2RL	2wti	minimal buffer space; needs synchronized frames
       S&G WRR	O(1)	O(1)	complicated	2RL	3wti	no synchronous frames; constant buffere size
       BWRR	O(1)	O(1)	pi + (k-1)RL	(k-1)RL - wti +1	2wti	more jitter, but less buffer space than S&G WRR

    3. MAC Layer
       1. CAN - shared medium, with wired AND, priority based messages
       2. Token Ring - shared medium, token holder owns medium, priority based messages
       3. FireWire - isochronous messages scheduled centrally within a frame, some BW reserved for asynchronous messages
    4. Network Layer - RSVP: reserve network resources along path from source(s) to destination(s)
    5. Transport Layer - RTP/RTCP: reliable in order delivery with synchronization
12. Non-Volatile Storage and Filesystems
    1. Types of media - know the characteristics

       Type	Size	Speed	Longevity	Ruggedness	Other
       Disk	20 GB to 500 GB	8 ms - 15 ms access time; ~30 MB/s transfer	3 to 5 years	vibration causes head crashes	big & cheap
       FLASH	256 Kbits to 1 Gbit	read: 100  to 200 ns; write: 1 ms to 20 ms; erase: 20 ms to 5 s	10,000 to 100,000 erease cycles (or 20 years)	good	Must erase a large block at a time, lifetime is limited Used in digital cameras, cell phones, etc
       EEPROM	16 kbits - 4 Mbits	200 to 250 ns	10,000 to 100,000 erase cycles (up to 10.5 years)	good	byte eraseable FLASH, but smaller and more expensive
       BBU RAM	same as SRAM	same as SRAM	life of battery (5 to 10 years)	good	Battery only used when power is off, can be replaced when dead

    2. Filesystems
       1. Ext2/Ext3 - Unix-style filesystem
       2. MS-DOS/FAT - simple; used in compact flash and other embedded media
       3. JFFS2 - Jounrnalling filesystem suited to FLASH characteristics