Investigating Non-Work-Conserving Scheduling in Event-Driven Real-Time Systems

Investigating Non-Work-Conserving Scheduling in Event-Driven Real-Time Systems

van Ofwegen, Nathan (TU Delft Electrical Engineering, Mathematics and Computer Science)

Nasri Nasrabadi, M. (mentor)
Zuniga, Marco (graduation committee)
Verbraeck, A. (graduation committee)

Delft University of Technology

Electrical Engineering | Embedded Systems

2020-11-02

Embeddedreal-time systems that have cost or energy constraints are usually limited inprocessing power and memory. This limitation typically leads to applyingsimpler execution models such as non-preemptive scheduling. A problem with anon-preemptive real-time system is that finding a schedule without causingdeadline misses is NP-hard. Finding a schedule is therefore done with online schedulingpolicies, i.e. policies that make decisions upon arrival or after execution ofa task to schedule the next one. Onlinenon-preemptive scheduling policies are typically priority based, namely, theypick the highest priority job to schedule based on criteria as period or absolutedeadline. These are work-conserving policies which cannot keep the processoridle while there are still pending jobs in the ready queue. Non-work-conservingpolicies allow an idle cpu while there are still jobs in the ready queue. Whilethis increases schedulability, it also has an increased overhead. Current stateof the art policies like Precautious Rate Monotonic (PRM) and Critical WindowsEarliest Deadline First (CW-EDF) have an idle-time insertion policy which caninsert an idle time in the schedule (between the execution of the jobs) whilestill having pending jobs. PRM verifies whether the highest priority job in theready queue is able to finish without causing a deadline miss for the highestpriority task in the system, which is the task with the lowest period. PRMimproves schedulability with increased overhead of O(1).CW-EDF comes with additional overhead O(n log n) in which it verifies ifscheduling the highest priority pending job will result in a deadline miss for thenext job of all other tasks in the system. PRM has low overhead, while CW-EDFhas better schedulability despite having higher overhead. Alimitation of these non-work-conserving policies is the missing support for event-triggeredtask, where jobs are released at unknown time instants. Namely, the existingnon-work-conserving policies are designed for strict periodic tasks. In thisthesis we will introduce a policy which has schedulability as high as CW-EDF,but prior to running the system it detects the critical tasks which have aninfluence on the idle-time insertion policy. We ignore the non-critical tasks duringthe idle-time insertion policy, reducing the runtime overhead. We also introducea policy which will support time-triggered tasks, by using an arrival curvewhich stores the possible behavior of the event-triggered task. With this arrivalcurve we will reduce the number of deadline misses compared to the existingnon-work-conserving policies.  

real-time systems
non-work-conserving
event-triggered
arrival curve

http://resolver.tudelft.nl/uuid:d9eb6a9a-f4e4-41dd-8269-62257baeb195

Student theses

master thesis

© 2020 Nathan van Ofwegen