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

Abstract

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.