Example [LWN.net]

Example

Posted Jul 21, 2010 21:58 UTC (Wed) by Shewmaker (subscriber, #1126) [Link]

I think their confusion centers around the implications of allowing separate deadline and period values. If the commenters read Dario's email, then they would have seen his reference to the "sporadic task model" which may have helped.

Perhaps another way to describe your example is that it is specifically constructed to show that when a scheduler tries to allow admission of a task at any time, and not just on period boundaries, then it gets harder. Yes, the scheduler could delay the admission of the new task until the deadline of the existing task, but then you have a periodic scheduler and not one that handles sporadic job arrivals.

I hope that helps.

Example

Posted Jul 21, 2010 22:37 UTC (Wed) by blitzkrieg3 (subscriber, #57873) [Link]

I think their confusion centers around the implications of allowing separate deadline and period values. If the commenters read Dario's email, then they would have seen his reference to the "sporadic task model" which may have helped.

Yeah exactly. I went back and read the email after seeing the response, and the key point is:

one of the tasks can miss its deadline by 3 time units in the worst case (if, and if yes which one, depends on the order with witch they arrive).

Obviously if we have the good fortune of having P2 arrive after 5 time units, we're golden. Before reading the email, I would have assumed that if you're just starting an executable, rather than acting on an event such as a udp packet or something, then you can sacrifice 5 time units.

I've illustrated exactly what I mean http://imgur.com/CKMcp.png

For the purposes of explaining how this works and what these values mean, it might make more sense to use a simple example that isn't schedule-able, no matter what order it comes in, like:


T_1 = (2, 4, 3)


T_2 = (2, 5, 3)

Even if T_2 can be scheduled after 2 time units, using the naive algorithm that I illustrated in the picture, it's clear that they're both going to wake up at the same time after 10 units, at which time you have 3 units to schedule 4 slots of cpu time.

Example

Posted Jul 23, 2010 22:33 UTC (Fri) by giraffedata (subscriber, #1954) [Link]

I think where people really get lost in these explanations is that they appear to describe a system where the scheduler gets to to decide exactly who to give CPU time and when, or where a process requests a precise CPU schedule for itself for the rest of time.

But in reality, the scheduler must wait for a process to request each chunk of time, and even the process can't know exactly when it will do that.

I presume the parameters actually say, "I am going to be requesting CPU time in the future. There will be at least 10 ms between requests. Each one will be for less than 4 ms, but whatever it is, I'll need it all within 5 ms of when I ask for it.

Based on that, the scheduler is supposed to say, "As long as you stick to those constraints, I guarantee I will fill all your requests" or "I can't guarantee that, so don't bother trying to run."

I really don't get the one statement about it being OK to miss the deadline by a bounded amount. If the process is OK with getting its 4ms within 10 ms, why did it state a deadline of 5 ms?