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)[reply]

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)[reply]

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!

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)[reply]

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)}{ceil({{R_{i}} \over {T_{j}}})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 ceil() 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)[reply]