Talk:Rate-monotonic scheduling

Mistakes in article?

Hi! I'm no expert, but on LKML it was said that this article is not 100% correct: "((Notice: The article gets it wrong on the priority inheritance/ceiling stuff...))" (Source: http://lkml.org/lkml/2005/7/27/233) --81.173.254.97 21:41, 28 July 2005 (UTC) MULL UP! —Preceding unsigned comment added by 134.148.5.118 (talk) 07:49, 19 November 2007 (UTC)

What sounded (almost) wrong was a statement in reference to the 'chained blocking', which sounded like it was confusing chained blocking with unbounded inversion. I've re-worked the protocol descriptions and clarified this. Alexeicolin (talk) 06:20, 14 March 2014 (UTC)

Typo?

"in the fact the algorithms are identical" -- Shouldn't that be "in fact, the algorithms are identical" or am I reading it wrong?

Since nobody reacted upon this suggestion I felt free to improve the wordings a little. Micha 11:26, 5 January 2007 (UTC)

A Mistake

"An optimal static-priority scheduling algorithm when deadlines are greater than periods is an open problem."

This is false. It is known that the Audsley's algorithm finds the priority ordering for this problem. The algorithm can be found in RTS text books such as the Burns & Wellings one.

Could you please give a direct quote? Audsley's priority assignment algorithm is pitched as handling tasks with known phases (where the critical instant of simultaneous job release cannot happen). For tasks with deadlines less than periods, the deadline-monotonic priority assignment algorithm is optimal. For tasks with deadlines greater than periods, though, is the question here. Alexeicolin (talk) 06:18, 14 March 2014 (UTC)

And, the quote is on page 398 of Burns and Wellings 4th edition: "for arbitrary deadlines an optimal ordering is found [by Audsley's priority assignment algorithm]." Indeed, the fact that the algorithm works for task sets where the critical instant is not necessarily the worst case, is the clue. The algorithm uses as a subroutine the schedulability test for arbitrary deadlines, which checks checks all possible releases (see Section 11.10.2).Alexeicolin (talk) 23:33, 11 April 2014 (UTC)

Use of Expert

Why is this tagged as needing an expert? Its factually correct, but it just needs clean-up.64.126.164.3 04:48, 30 April 2007 (UTC)

It's correct so far as it goes, but there's more to the subject that should be included. For example, the utilisation bound :$U=\sum _{i=1}^{n}{\frac {C_{i}}{T_{i}}}\leq n({\sqrt[{n}]{2}}-1)$ is a sufficient condition for the processes to be schedulable but not a necessary one. Take as an example the process set

Process	Execution Time	Period
a	40	80
b	10	40
c	5	20

This gives utilisation of ${\frac {40}{80}}+{\frac {10}{40}}+{\frac {5}{20}}=1.0$ or 100%, but the system can still be scheduled!

(starting at time t=0, first process c runs to completion at t=5, then b runs to completion. a then runs for 5 time units before being preempted by c again, which runs to completion and allows a to run for another 15 time units. Once this cycle is repeated again it's obvious that a gets the requisite 40 units of execution time, b runs to completion twice and c runs to completion four times within an 80-unit major cycle, so all deadlines are met despite the utilisation bound not being met.)

Not quite sure how to correct this; probably the thing to do would be to start a new article on Response-time analysis, link it in here and under the realtime section in response time, but I'm still new to wiki'ing and I'm not sure I'm the person for the job.

Response-time analysis gives a necessary and sufficient proof of schedulability though; it's based on iterating $R_{i}=C_{i}+\sum _{j\in hp(i)}{\lceil {{R_{i}} \over {T_{j}}}\rceil C_{j}}$ (where $R_{i}$ is the response time of the process, hp(i) is the set of higher priority processes, $T_{i}$is a process's period, $C_{i}$ is a process's computation time and $\lceil \rceil$ gives the next highest integer to its argument).

The idea is to start with the initial value of $R_{i}$ as $C_{i}$, then iterate through until $R_{i}^{n}+1=R_{i}^{n}$; if $R_{i}\leq T_{i}$ for all the processes then it can be scheduled.

If someone could wikify that then the article would make a bit more sense :-) I'm supposed to be revising for an exam on this stuff, but if nobody's done it in a week or so then I'll give it a shot. Stonejag 21:37, 4 June 2007 (UTC)

Someone who knows the topic well needs to explain clearly for the reader what $U$ actually is. The upper limit on it is defined by what quantity is actually compared to that upper limit? Admittedly, I'm new to this topic, but as it stands this article needs some clarification by an expert in the field. 130.217.188.50 (talk) 21:53, 13 November 2016 (UTC)

Verified

You are correct, I have almost failed an exam because this factual error (utilization bound). It is just a sufficient condition.

So I have changed 'theoretical limit' to 'sufficient condition'. But someone expert should revise the whole article.

A student of Budapest University of Technology and Economics -- 145.236.125.221 (talk) 22:09, 20 March 2008 (UTC)

lack of actual definition

funny how this article has a introduction and fancy equations but doesnt actually say what the algorithm is.... 199.111.224.90 (talk) 02:01, 7 April 2008 (UTC)

tried to fix this. 217.84.121.48 (talk) 17:07, 30 March 2009 (UTC)

Disabling of Preemption

This section only discusses disabling of all processor or device interrupts. There are multiple OSes which allow tasks/threads to selective disable preemption at the task level. Would you all mind if I modified this section to highlight the difference and provide some examples. Maybe a two-level bullet structure (disable interrupts and disable thread preemption). I know I include this distinction when I teach Mutual Exclusion theory in my RTEMS class. --JoelSherrill (talk) 17:17, 19 August 2009 (UTC)

This section and the following on Priority inheritance don't seem to be directly relevant to rate-monotonic scheduling, so they removed from this article. Starblue (talk) 07:42, 18 February 2011 (UTC)

Separate discussion of RMS from the discussion of priority inversion

Indeed, RMS and priority inversion are two different issues and should not be included in the same article. 87.161.173.208 (talk) 13:19, 22 October 2011 (UTC)

Taxonomy: Rate-monotonic is a priority assignment algorithm

'Rate-Monotonic' refers to a priority assignment algorithm. A priority assignment algorithm is used within the context of a fixed-priority scheduler. The scheduler itself is a separate entity and is orthogonal to the priority assignment algorithm. The scheduler generally implements the Highest-Priority-First job selection policy. This article should be renamed to 'Rate-Monotonic Priority Assignment Algorithm'. The sibling pages would be 'Deadline-Monotonic Priority Assignment Algorithm', and 'Audsley's Priority Assignment Algorithm'. Each priority assignment algorithm listed above is applicable to a different variant of the task model and comes with a different schedulability analysis. We need to define a proper taxonomy and place the existing material into it correctly. Alexeicolin (talk) 06:34, 14 March 2014 (UTC)

Where is the algorithm description?

1. I cannot find any description of the algorithm in the page.

(220.244.119.107 (talk) 12:45, 28 August 2016 (UTC))