Deadline Monotonic Scheduling
Deadline Monotonic Scheduling (DMS) refers to a scheduling method for hard real-time systems in computer science that is used to manage processes with fixed priorities. Among the scheduling procedures with fixed priorities, it is optimal for any deadline.
Assumptions
Basic restrictions
The theoretical consideration of real-time scheduling methods requires some fundamental restrictions in order to be able to handle the complexity of the analysis.
- Processes can be interrupted at any time
- the overhead for process change is assumed to be 0 time units
- Necessary resources (except CPU time) are unlimited
- all processes are independent (intuitive: the processes can be carried out in any order)
- the load of all processes together must be ≤1
Assumptions for periodic processes
- all processes have deadlines that are less than or equal to their periods
Assumptions for sporadic processes
- All processes have deadlines that are less than or equal to their minimum inter-arrival times (minimum between two arrival times of the same process)
Procedure
Analogous to Rate Monotonic Scheduling (RMS), the process with the highest priority is always carried out with DMS. The priorities are assigned reciprocally to the relative deadline. This means that the shortest deadline has the highest priority. The procedure is preemptive - when a new process with a higher priority arrives, the current process is interrupted in favor of the new one. In order to be able to handle aperiodic jobs, a fictitious periodic process with the minimum inter-arrival time is assumed for them.
Mightiness
DMS is the most powerful of the scheduling processes with fixed priorities. It is a generalization of Rate Monotonic Scheduling, whereby with RMS only a scheduling of a subset of process sets that can be executed with DMS is possible. In the special case that relative deadlines and period lengths are the same for all processes, DMS = RMS applies.