Rate-monotonic scheduling

Last updated

In computer science, rate-monotonic scheduling (RMS) [1] is a priority assignment algorithm used in real-time operating systems (RTOS) with a static-priority scheduling class. [2] The static priorities are assigned according to the cycle duration of the job, so a shorter cycle duration results in a higher job priority.

Contents

These operating systems are generally preemptive and have deterministic guarantees with regard to response times. Rate monotonic analysis is used in conjunction with those systems to provide scheduling guarantees for a particular application.

Introduction

A simple version of rate-monotonic analysis assumes that threads have the following properties:

It is a mathematical model that contains a calculated simulation of periods in a closed system, where round-robin and time-sharing schedulers fail to meet the scheduling needs otherwise. Rate monotonic scheduling looks at a run modeling of all threads in the system and determines how much time is needed to meet the guarantees for the set of threads in question.

Optimality

The rate-monotonic priority assignment is optimal under the given assumptions, meaning that if any static-priority scheduling algorithm can meet all the deadlines, then the rate-monotonic algorithm can too. The deadline-monotonic scheduling algorithm is also optimal with equal periods and deadlines, in fact in this case the algorithms are identical; in addition, deadline monotonic scheduling is optimal when deadlines are less than periods. [3] For the task model in which deadlines can be greater than periods, Audsley's algorithm endowed with an exact schedulability test for this model finds an optimal priority assignment. [4]

Upper bounds on utilization

Least upper bound

Liu & Layland (1973) proved that for a set of n periodic tasks with unique periods, a feasible schedule that will always meet deadlines exists if the CPU utilization is below a specific bound (depending on the number of tasks). The schedulability test for RMS is:

where U is the utilization factor, Ci is the computation time for process i, Ti is the release period (with deadline one period later) for process i, and n is the number of processes to be scheduled. For example, U  0.8284 for two processes. When the number of processes tends towards infinity, this expression will tend towards:

Therefore, a rough estimate when is that RMS can meet all of the deadlines if total CPU utilization, U, is less than 70%. The other 30% of the CPU can be dedicated to lower-priority, non-real-time tasks. For smaller values of n or in cases where U is close to this estimate, the calculated utilization bound should be used.

In practice, for the process, should represent the worst-case (i.e. longest) computation time and should represent the worst-case deadline (i.e. shortest period) in which all processing must occur.

Upper bound for harmonic task sets

Liu and Layland noted that this bound may be relaxed to the maximum possible value of 1.0, if for tasks , where and , is an integer multiple of , which is to say that all tasks have a period that is not just a multiple of the shortest period, , but instead that any task's period is a multiple of all shorter periods. This is known as an harmonic task set. An example of this would be: . It is acknowledged by Liu and Layland that it is not always feasible to have a harmonic task set and that in practice other mitigation measures, such as buffering for tasks with soft-time deadlines or using a dynamic priority assignment approach may be used instead to allow for a higher bound.

Generalization to harmonic chains

Kuo and Mok [5] showed that for a task set made up of K harmonic task subsets (known as harmonic chains), the least upper bound test becomes:

In the instance where no task period is an integer multiple of another, the task set can be thought of as being composed of n harmonic task subsets of size 1 and therefore , which makes this generalization equivalent to Liu and Layland's least upper bound. When , the upper bound becomes 1.0, representing full utilization.

Stochastic bounds

It has been shown that a randomly generated periodic task system will usually meet all deadlines when the utilization is 88% or less, [6] however this fact depends on knowing the exact task statistics (periods, deadlines) which cannot be guaranteed for all task sets, and in some cases the authors found that the utilization reached the least upper bound presented by Liu and Layland.

Hyperbolic bound

The hyperbolic bound [7] is a tighter sufficient condition for schedulability than the one presented by Liu and Layland:

,

where Ui is the CPU utilization for each task. It is the tightest upper bound that can be found using only the individual task utilization factors.

Resource sharing

In many practical applications, resources are shared and the unmodified RMS will be subject to priority inversion and deadlock hazards. In practice, this is solved by disabling preemption or by priority inheritance. Alternative methods are to use lock-free algorithms or avoid the sharing of a mutex/semaphore across threads with different priorities. This is so that resource conflicts cannot result in the first place.

Disabling of preemption

Priority inheritance

Priority inheritance algorithms can be characterized by two parameters. First, is the inheritance lazy (only when essential) or immediate (boost priority before there is a conflict). Second is the inheritance optimistic (boost a minimum amount) or pessimistic (boost by more than the minimum amount):

pessimisticoptimistic
immediateOS_ENTER_CRITICAL() / OS_EXIT_CRITICAL()splx(), highest locker
lazypriority ceiling protocol, basic priority inheritance protocol

In practice there is no mathematical difference (in terms of the Liu-Layland system utilization bound) between the lazy and immediate algorithms, and the immediate algorithms are more efficient to implement, and so they are the ones used by most practical systems.[ citation needed ]

An example of usage of basic priority inheritance is related to the "Mars Pathfinder reset bug" [13] [14] which was fixed on Mars by changing the creation flags for the semaphore so as to enable the priority inheritance.

Interrupt Service Routines

All interrupt service routines (ISRs), whether they have a hard real-time deadline or not should be included in RMS analysis to determine schedulability in cases where ISRs have priorities above all scheduler-controlled tasks. An ISR may already be appropriately prioritized under RMS rules if its processing period is shorter than that of the shortest, non-ISR process. However, an ISR with a period/deadline longer than any non-ISR process period with a critical deadline results in a violation of RMS and prevents the use of the calculated bounds for determining schedulability of a task set.

Mitigating mis-prioritized ISRs

One method for mitigating a mis-prioritized ISR is to adjust the analysis by reducing the ISR's period to be equal to that of the shortest period, if possible. Imposing this shorter period results in prioritization that conforms to RMS, but also results in a higher utilization factor for the ISR and therefore for the total utilization factor, which may still be below the allowable bound and therefore schedulability can be proven. As an example, consider a hardware ISR that has a computation time, of 500 microseconds and a period, , of 4 milliseconds. If the shortest scheduler-controlled task has a period, of 1 millisecond, then the ISR would have a higher priority, but a lower rate, which violates RMS. For the purposes of proving schedulability, set and recalculate the utilization factor for the ISR (which also raises the total utilization factor). In this case, will change from to . This utilization factor would be used when adding up the total utilization factor for the task set and comparing to the upper bound to prove schedulability. It should be emphasized that adjusting the period of the ISR is for analysis only and that the true period of the ISR remains unchanged.

Another method for mitigating a mis-prioritized ISR is to use the ISR to only set a new semaphore/mutex while moving the time-intensive processing to a new process that has been appropriately prioritized using RMS and will block on the new semaphore/mutex. When determining schedulability, a margin of CPU utilization due to ISR activity should be subtracted from the least upper bound. ISRs with negligible utilization may be ignored.

Examples

Example 1

ProcessExecution timePeriod
P118
P225
P3210

Under RMS, P2 has the highest rate (i.e. the shortest period) and so would have the highest priority, followed by P1 and finally P3.

Least Upper Bound

The utilization will be: .

The sufficient condition for processes, under which we can conclude that the system is schedulable is:

Because , and because being below the Least Upper Bound is a sufficient condition, the system is guaranteed to be schedulable.

Example 2

ProcessExecution timePeriod
P1316
P225
P3210

Under RMS, P2 has the highest rate (i.e. the shortest period) and so would have the highest priority, followed by P3 and finally P1.

Least Upper Bound

Using the Liu and Layland bound, as in Example 1, the sufficient condition for processes, under which we can conclude that the task set is schedulable, remains:

The total utilization will be: .

Since the system is determined to not be guaranteed to be schedulable by the Liu and Layland bound.

Hyperbolic Bound

Using the tighter Hyperbolic bound as follows:

it is found that the task set is schedulable.

Example 3

ProcessExecution timePeriod
P1732
P225
P3210

Under RMS, P2 has the highest rate (i.e. the shortest period) and so would have the highest priority, followed by P3 and finally P1.

Least Upper Bound

Using the Liu and Layland bound, as in Example 1, the sufficient condition for processes, under which we can conclude that the task set is schedulable, remains:

The total utilization will be: .

Since the system is determined to not be guaranteed to be schedulable by the Liu and Layland bound.

Hyperbolic Bound

Using the tighter Hyperbolic bound as follows:

Since the system is determined to not be guaranteed to be schedulable by the Hyperbolic bound.

Harmonic Task Set Analysis

Because , tasks 2 and 3 can be considered a harmonic task subset. Task 1 forms its own harmonic task subset. Therefore, the number of harmonic task subsets, K, is 2.

Using the total utilization factor calculated above (0.81875), since the system is determined to be schedulable.

See also

Related Research Articles

Real-time computing (RTC) is the computer science term for hardware and software systems subject to a "real-time constraint", for example from event to system response. Real-time programs must guarantee response within specified time constraints, often referred to as "deadlines".

A real-time operating system (RTOS) is an operating system (OS) for real-time computing applications that processes data and events that have critically defined time constraints. An RTOS is distinct from a time-sharing operating system, such as Unix, which manages the sharing of system resources with a scheduler, data buffers, or fixed task prioritization in a multitasking or multiprogramming environment. Processing time requirements need to be fully understood and bound rather than just kept as a minimum. All processing must occur within the defined constraints. Real-time operating systems are event-driven and preemptive, meaning the OS can monitor the relevant priority of competing tasks, and make changes to the task priority. Event-driven systems switch between tasks based on their priorities, while time-sharing systems switch the task based on clock interrupts.

<span class="mw-page-title-main">Sigmoid function</span> Mathematical function having a characteristic S-shaped curve or sigmoid curve

A sigmoid function is any mathematical function whose graph has a characteristic S-shaped curve or sigmoid curve.

<span class="mw-page-title-main">Inequality (mathematics)</span> Mathematical relation expressed with < or ≤

In mathematics, an inequality is a relation which makes a non-equal comparison between two numbers or other mathematical expressions. It is used most often to compare two numbers on the number line by their size. There are several different notations used to represent different kinds of inequalities:

Collision detection is the computational problem of detecting an intersection of two or more spatial objects, commonly computer graphics objects. It has applications in various computing fields, primarily in computer graphics, computer games, computer simulations, robotics and computational physics. Collision detection is a classic problem of computational geometry. Collision detection algorithms can be divided into operating on 2D or 3D spatial objects.

In mathematics, a Hermitian matrix is a complex square matrix that is equal to its own conjugate transpose—that is, the element in the i-th row and j-th column is equal to the complex conjugate of the element in the j-th row and i-th column, for all indices i and j:

In computing, scheduling is the action of assigning resources to perform tasks. The resources may be processors, network links or expansion cards. The tasks may be threads, processes or data flows.

<span class="mw-page-title-main">Mechanism design</span> Field in game theory

Mechanism design is a field in economics and game theory that takes an objectives-first approach to designing economic mechanisms or incentives, toward desired objectives, in strategic settings, where players act rationally. Because it starts at the end of the game, then goes backwards, it is also called reverse game theory. It has broad applications, from economics and politics in fields such as market design, auction theory and social choice theory to networked-systems.

Default logic is a non-monotonic logic proposed by Raymond Reiter to formalize reasoning with default assumptions.

Micro-Controller Operating Systems is a real-time operating system (RTOS) designed by Jean J. Labrosse in 1991. It is a priority-based preemptive real-time kernel for microprocessors, written mostly in the programming language C. It is intended for use in embedded systems.

In mathematics, the Dirichlet–Jordan test gives sufficient conditions for a real-valued, periodic function f to be equal to the sum of its Fourier series at a point of continuity. Moreover, the behavior of the Fourier series at points of discontinuity is determined as well. It is one of many conditions for the convergence of Fourier series.

Least slack time (LST) scheduling is an algorithm for dynamic priority scheduling. It assigns priorities to processes based on their slack time. Slack time is the amount of time left after a job if the job was started now. This algorithm is also known as least laxity first. Its most common use is in embedded systems, especially those with multiple processors. It imposes the simple constraint that each process on each available processor possesses the same run time, and that individual processes do not have an affinity to a certain processor. This is what lends it a suitability to embedded systems.

In computer science, gang scheduling is a scheduling algorithm for parallel systems that schedules related threads or processes to run simultaneously on different processors. Usually these will be threads all belonging to the same process, but they may also be from different processes, where the processes could have a producer-consumer relationship or come from the same MPI program.

Deadline-monotonic priority assignment is a priority assignment policy used with fixed-priority pre-emptive 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 configuration in a self-sustained manner. It can be very hard to produce well-defined policies to achieve the goal depending on the difficulty of a given problem.

The Stack Resource Policy (SRP) is a resource allocation policy used in real-time computing, used for accessing shared resources when using earliest deadline first scheduling. It was defined by T. P. Baker. SRP is not the same as the Priority ceiling protocol which is for fixed priority tasks (FP).

<span class="mw-page-title-main">Brain Fuck Scheduler</span> Process scheduler in Linux

The Brain Fuck Scheduler (BFS) is a process scheduler designed for the Linux kernel in August 2009 based on earliest eligible virtual deadline first scheduling (EEVDF), as an alternative to the Completely Fair Scheduler (CFS) and the O(1) scheduler. BFS was created by Con Kolivas.

In probability theory and statistics, the Poisson binomial distribution is the discrete probability distribution of a sum of independent Bernoulli trials that are not necessarily identically distributed. The concept is named after Siméon Denis Poisson.

Earliest deadline first (EDF) or least time to go is a dynamic priority scheduling algorithm used in real-time operating systems to place processes in a priority queue. Whenever a scheduling event occurs the queue will be searched for the process closest to its deadline. This process is the next to be scheduled for execution.

<span class="mw-page-title-main">Bucket queue</span> Data structure for integer priorities

A bucket queue is a data structure that implements the priority queue abstract data type: it maintains a dynamic collection of elements with numerical priorities and allows quick access to the element with minimum priority. In the bucket queue, the priorities must be integers, and it is particularly suited to applications in which the priorities have a small range. A bucket queue has the form of an array of buckets: an array data structure, indexed by the priorities, whose cells contain collections of items with the same priority as each other. With this data structure, insertion of elements and changes of their priority take constant time. Searching for and removing the minimum-priority element takes time proportional to the number of buckets or, by maintaining a pointer to the most recently found bucket, in time proportional to the difference in priorities between successive operations.

References

  1. Liu, C. L.; Layland, J. (1973), "Scheduling algorithms for multiprogramming in a hard real-time environment", Journal of the ACM, 20 (1): 46–61, CiteSeerX   10.1.1.36.8216 , doi:10.1145/321738.321743, S2CID   207669821 .
  2. Bovet, Daniel P.; Cesati, Marco, Understanding the Linux Kernel, http://oreilly.com/catalog/linuxkernel/chapter/ch10.html#85347 Archived 2014-09-21 at the Wayback Machine .
  3. Leung, J. Y.; Whitehead, J. (1982), "On the complexity of fixed-priority scheduling of periodic, real-time tasks", Performance Evaluation, 2 (4): 237–250, doi:10.1016/0166-5316(82)90024-4 .
  4. Alan Burns and Andy Wellings (2009), Real-Time Systems and Programming Languages (4th ed.), Addison-Wesley, pp. 391, 397, ISBN   978-0-321-41745-9
  5. T.-W. Kuo; A.K. Mok (1991). "Load adjustment in adaptive real-time systems". [1991] Proceedings Twelfth Real-Time Systems Symposium. pp. 160–170. doi:10.1109/REAL.1991.160369. ISBN   0-8186-2450-7. S2CID   31127772.
  6. Lehoczky, J.; Sha, L.; Ding, Y. (1989), "The rate monotonic scheduling algorithm: exact characterization and average case behavior", IEEE Real-Time Systems Symposium, pp. 166–171, doi:10.1109/REAL.1989.63567, ISBN   978-0-8186-2004-1, S2CID   206524469 .
  7. Enrico Bini; Giorgio C. Buttazzo; Giuseppe M. Buttazzo (2003), "Rate Monotonic Analysis: the Hyperbolic Bound", IEEE Transactions on Computers, 52 (7): 933–942, doi:10.1109/TC.2003.1214341, hdl: 11382/200358
  8. Lampson, B. W.; Redell, D. D. (1980), "Experience with processes and monitors in Mesa", Communications of the ACM, 23 (2): 105–117, CiteSeerX   10.1.1.46.7240 , doi:10.1145/358818.358824, S2CID   1594544 .
  9. Buttazzo, Giorgio (2011), Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications (Third ed.), New York, NY: Springer, p. 225
  10. "Real-Time Linux Wiki". kernel.org. 2008-03-26. Retrieved 2014-03-14.
  11. Sha, L.; Rajkumar, R.; Lehoczky, J. P. (1990), "Priority inheritance protocols: an approach to real-time synchronization", IEEE Transactions on Computers, 39 (9): 1175–1185, doi:10.1109/12.57058 .
  12. Buttazzo, Giorgio (2011), Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications (Third ed.), New York, NY: Springer, p. 212
  13. "Mike Jones at Microsoft Research".
  14. "Mars Pathfinder Reset Bug - Anthology of Interest". Archived from the original on 2011-10-05. Retrieved 2008-09-09.

Further reading