Deadline-monotonic priority assignment is a priority assignment policy used with
fixed-priority pre-emptive scheduling
Fixed-priority preemptive scheduling is a scheduling system commonly used in real-time systems. With fixed priority preemptive scheduling, the scheduler ensures that at any given time, the processor executes the highest priority task of all those ...
.
With deadline-
monotonic
In mathematics, a monotonic function (or monotone function) is a function between ordered sets that preserves or reverses the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of ord ...
priority
assignment,
tasks are assigned priorities according to their
deadlines. The task with the shortest deadline is assigned the highest priority.
This priority assignment policy is optimal for a set of periodic or sporadic tasks which comply with the following system model:
# All
tasks have deadlines less than or equal to their minimum inter-arrival times (or periods).
# All tasks have
worst-case execution time The worst-case execution time (WCET) of a computational task is the maximum length of time the task could take to execute on a specific hardware platform.
What it is used for
Worst case execution time is typically used in reliable real-time sy ...
s (WCET) that are less than or equal to their deadlines.
# All tasks are independent, and so do not block each other's
execution
Capital punishment, also known as the death penalty, is the state-sanctioned practice of deliberately killing a person as a punishment for an actual or supposed crime, usually following an authorized, rule-governed process to conclude that t ...
(e.g., by accessing mutually exclusive
shared resource
In computing, a shared resource, or network share, is a computer resource made available from one host to other hosts on a computer network.
It is a device or piece of information on a computer that can be remotely accessed from another comput ...
s).
# No task voluntarily suspends itself.
# There is some point in time, referred to as a critical instant, where all of the tasks become ready to execute simultaneously.
# Scheduling overheads (switching from one task to another) are zero.
# All tasks have zero release
jitter
In electronics and telecommunications, jitter is the deviation from true periodicity of a presumably periodic signal, often in relation to a reference clock signal. In clock recovery applications it is called timing jitter. Jitter is a significa ...
(the time from the task arriving to it becoming ready to execute).
If restriction 7 is lifted, then "deadline minus jitter" monotonic priority assignment is optimal.
If restriction 1 is lifted, allowing deadlines greater than periods, then Audsley's optimal priority assignment
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
may be used to find the optimal priority assignment.
Deadline monotonic priority assignment is not optimal for fixed priority non-pre-emptive scheduling.
A fixed priority assignment policy P is referred to as optimal if no task set exists which is schedulable using a different priority assignment policy which is not also schedulable using priority assignment policy P. Or in other words: Deadline-monotonic priority assignment (DMPA) policy is optimal if any process set, Q, that is schedulable by priority scheme W, is also schedulable by DMPA
[
]
See also
*
Dynamic priority scheduling
Dynamic priority scheduling is a type of scheduling algorithm in which the priorities are calculated during the execution of the system. The goal of dynamic priority scheduling is to adapt to dynamically changing progress and to form an optimal co ...
*
Rate-monotonic scheduling In computer science, rate-monotonic scheduling (RMS) is a priority assignment algorithm used in real-time operating systems (RTOS) with a static-priority scheduling class. The static priorities are assigned according to the cycle duration of the job ...
References
Processor scheduling algorithms
{{Comp-sci-stub