EE 599-002: Review for Exam 1

These are all things I think are important to know for exam 1.

1. Definitions & Modeling
   1. Hard vs. soft RT
   2. Jobs & Tasks
   3. Job Parameters (release time, absolute deadline, relative deadline)
   4. Task Parameters (phase, period)
   5. Periodic tasks
   6. Aperiodic jobs
   7. Sporadic jobs
   8. Dependencies, precedence graphs, task graphs
2. Clock-Driven Scheduling

   Periodically run a statically determined schedule

   Advantages

   Simple (low overhead, predictable, easy to validate, no concurrency)

   Disadvantages

   Inflexible (fixed release times, need to run offline algorithm to add or remove tasks, all possible task combinations must be known apriori, does not handle event driven tasks well)

   1. Timer driven schedulers (fit all jobs into hyperperiod)
   2. Cyclic schedulers (divide hyperperiod into frames to add structure)
   3. Aperiodic jobs (background execution vs. slack stealing)
   4. Sporadic jobs (run acceptance test and schedule)

3. Priority-Driven Scheduling

   If any jobs are runnable, run the one with the highest priority

   Advantages

   Handles dynamically changing workloads better

   Disadvantages

   harder to validate, cannot created feasible schedules when knowledge of future events required

   1. Fixed Priority

      RM (DM)

      shortest period (relative deadline) has highest priority

      Arbitrary

      Choose priority of tasks based on application

      Advantages of Fixed Priority

      More predictable (esp. with job overruns)

      Disadvantages

      Cannot schedule some systems that are scheduleable by priority schedulers

   2. Dynamic Priority

      Task-level

      Tasks can change priority, but once a job is released its priority is fixed (EDF)

      Job-level

      Jobs can change priority after release (LST)

      Advantages

      Higher scheduleable utilization (EDF and LST can schedule any system that can be scheduled by any priority driven algorithm)

      Disadvantages

      Less predictable than fixed priority algorithms

   3. Schedulability

      EDF

      Σⁿ_i=1(e_i/min(D_i,p_i) ≤ 1 ⇔ schedulable

      DM

      Best fixed priority algorithm (can schedule any system that is schedulable by a fixed priority algorithm)

      RM

      Simply periodic tasks: U ≤ 1 ⇔ schedulable
      generic tasks: U ≤ U_RM(n) = n(2^1/n - 1) ⇒ schedulable

      Time-demand Analysis

      Works for any fixed priority algorithm

      for D_i ≤ p_i
      demand = w_i(t) = e_i + Σ^i-1_k=1⌈t/p_k⌉⋅e_k + b_i, 0 < t ≤ p_i
      solve w_i(t) = t to get W_i
      T_i is schedulable if W_i ≤ D_i

      for D_i>p_i find length of the level-π_i busy interval
      solve t =Σⁱ_k=1⌈t/p_k⌉e_k + b_i, to find B_i
      number of jobs in interval = n_i = ⌈B_i/p_i⌉
      w_i,j(t) = j⋅e_i + Σⁱ⁼¹_k=1⌈t/p_k⌉e_k + b_i, (j-1)p_i ≤ t ≤ w_i,j(t), j = 1, 2, 3,... , n_i
      solve w_i,j((j-1)p_i + t) - (j-1)p_i = t
      to find W_i,j
      if all W_i,j < D_i then T_i is schedulable

      Blocking

      non-preemptability: b_i(np) = max_{i+1 ≤ k ≤ n} θ_k

      self-suspension: b_i = b_i(ss) + (K_i + 1)b_i(np)

      context switches

      e_i' = e_i + 2(K_i + 1)CS

      schedulable utilization with blocking

      Fixed Priority: Σ^i-1_k=1(e_k/p_k) + (e_i + b_i)/p_i ≤ U_X(n) ⇒ T_i schedulable (test forall i)

      EDF: Σⁿ_k=1(e_k/min(D_k, p_k) + b_i/min(D_i, p_i) ≤ 1 ⇔ T_i schedulable (test for all i)

Good book problems to study for chapter 6: 6.4, 6.5, 6.7, 6.13, 6.15, 6.21, 6.31