Embedded Systems - Real-Time Systems

Embedded Systems - Sharif University of Technology

• Embedded System Instructor: Dr. Mohsen Ansari
• Real Time Instructor: Dr. Sepideh Safari

Contents

Fixed Priority Servers

Assumption: Periodics are scheduled under RM (utilization bound = n(2^(1/n)-1) ).

• Polling Server

  • The server asks periodically from aperioci tasks if there are any aperiodic ones.

• Deferrable Server

  • In this algorithm we have a server, and it has a priority based on its rate (if the algm is RM).
  • In the periods, it is charged up to its capacity (wcet aperiodic).
  • The difference between this algorithm and the "Polling Server" is that polling server polls and asks in a periodic way if there are any aperiodic tasks waiting, but deferrable server waits for the aperiodic task to come.

• Priority Exchange

  • This algorithm is created for soft real-time aperiodic tasks.
  • It has worse performance in terms of DS (Deferrable Server).
  • The server capacity is passed through other tasks so that it can take the capacity back for executing aperiodic tasks.

• Sporadic Server

  • It enhances average response time of aperiodic tasks without degrading the utilization bound for periodic tasks.
  • It shifts the time of charging the server capacity.
  • RT = Replenishment Time = t_A + T_S
  • RA = Replenishment Amount = the capacity consumed at [t_A, t_i].
  • t_i = the last time that SS is active (SS is active when the aperiodic task is running or the task that is running, has a higher priority than aperiodic one).
  • comsuming server capacity is gradually but charging is suddenly (at once, the server capacity is increased by RA).
  • Question: What if the RA continues till RT?!

• Slack Stealing

  • slack_time = abs_deadline - time - remaining_c
  • Policy: Shift everything in a way that periodic tasks dont miss!

Dynamic Priority Servers

Question: Why do we call it "dynamic"?

Goal: Enhance Average Response Time of Aperiodic Tasks (without compromising schedulability of hard periodic tasks)

Assumption: Periodic tasks are scheduled by EDF (utilization bound = 1).

Assumption: All periodic tasks have hard deadlines, and aperiodics dont have deadline and they should be scheduled ASAP.

• Dynamic Priority Exchange (DPE) Server
  • server can trade its capacity with lower-priority tasks (EDF: has longer deadline).
  • server capacity (runtime is never wasted?!).
• Dynamic Sporadic Server
  • extension of SS
  • Question: Difference between it and fixed one?
• Total Bandwidth Server
  • d_k = max(r_k, d_{k-1}) + C_k/U_S
  • U_S + U_p = 1
• Earliset Deadline Late
  • Schedule as late as possible
• Improved Priority Exchange
  • First run EDL (Earliest Deadline Late) on the tasks.
  • Then at the slack times, charge the server (amount of charge = length of edl slack time).
  • charge and decharge the amounts (pass the amounts between each other) as said in priority exchange.
• Improving TBS (Improving Total Bandwidth)
  • we can shorten the time, it means that we can make the deadline closer.
  • do some iterations using this formula:
    • f_{s, k} = t + C_{a, k} + Ip(t, d_{s, k})
    • Ip = Interfernces (the tasks that begin before t and end between t and ...).

Resource Access Protocols

• NPP : None-Preemptive Protocol

• HLP : Highest Locker Priority

• PIP : Priority Inheritance Protocol

• PCP : Priority Ceiling Protocol

• SRP : Stack Resource Policy

TO DO

• Add the scheduling algorithms and their Demo (Visualization)
• Add different algorithms (code) in the real-time systems course
• Upload the lecture notes
• Upload useful slides
• Upload Useful assignments and answers
• Add links of useful courses (videos) and their assignments with answers
• The previous suggestion can be converted into a bank of questions that is useful for teaching assisstants to design homeworks
• Upload the source books of both courses