Talk:Rate-monotonic scheduling
From Wikipedia, the free encyclopedia
Contents |
[edit] 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)
[edit] 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)
[edit] 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.
Then please fix it!
[edit] 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)](../../../../math/c/f/1/cf18cfb006a8764dedb101e39ae2c769.png)
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 
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 
(where Ri is the response time of the process, hp(i) is the set of higher priority processes, Tiis a process's period, Ci is a process's computation time and 
gives the next highest integer to its argument).
The idea is to start with the initial value of Ri as Ci, then iterate through until 
; if 
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)
[edit] 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)
[edit] 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)
