0

To deal with transient overloads with a real-time system scheduled with rate-monotonic scheduling, one can use period transformation to reduce the period of important processes so that they have greater priority. In Scheduling Hard Real-Time Systems: a Review, A. Burns says (pages 4 to 5 of the PDF) that this can be done by:

  1. either adding two delay requests into the body of the code.
  2. or instructing the runtime system to schedule it as three shorter processes.

I understand how splitting it into smaller pieces can work, but how does adding delay requests work? Does the scheduler look at the process and use the the delay requests as the dividing points for splitting it into three pieces, meaning that for #1 above the programmer is explicitly telling the scheduler how to divide it into pieces, while for #2 the scheduler is guessing about how to split it?

NOTE: I'm trying to understand the theory of period transformation; I'm not asking for the purpose of implementing anything.

|improve this question
  • If you have a half-decent scheduler, then it will cause other processes/tasks to run when the currently running task/process requests a delay. Even if a delay of 0 ms is requested, typically the scheduler will let another task of the same priority run. – Bart van Ingen Schenau Oct 25 '14 at 7:57
  • But, as far as I can understand, the paper says that you can increase the priority of a process by inserting delay requests into it. – Matthew Cline Oct 25 '14 at 8:01
0

Burns's paper (being a review) leaves out the affects of inserting delays, so we'll have to turn elsewhere for an answer. The particular section references "Task scheduling in distributed real-time systems" by L. Sha, J.P. Lehoczky, and R. Rajkumar. If you could get ahold of that paper, it should clarify how delay insertion reduces task periods. Sadly, I cannot, so have to resort to supposition.

What happens is almost what you suppose, but the scheduler doesn't need to inspect the process's internals (i.e. it doesn't need to check for the delay) or make any decisions; the natural affects of the delay do the necessary scheduling work. By "delay", I'm assuming a call to sleep() (or similar), which allows for cooperative multitasking. When considering the following, keep in mind how the scheduler determines period: by keeping track of how long it's been since the process was last schedulable (perhaps using exponential averaging).

There are two relevant affects of sleep(): the process will be suspended (i.e. removed from scheduling), and will get rescheduled after the delay ends. When the process wakes up, the most recent period began when the process was last schedulable, which is the delay period plus the previous execution time. Consequently, the subtasks can be considered to be tasks with period equal to the delay plus the previous subtask's execution time (note that the subtask period could be considered as consisting of other delay times or subtask execution times; to simplify matters, the requested delays should be equal and the subtask execution times be as close as possible). In other words, a task of period p and average execution time e is turned into n subtasks with period p/n and execution time e/n.

For example, Burns's paper mentions a process P2 that runs every 30 seconds for 3 seconds. Inserting two calls to sleep(9) around 1 and 2 seconds along transforms the task into three subtasks of period 10 and average execution time of 1 second. I believe the delay must be 9 seconds, as shortening the delays would increases the period between the 3rd and 1st subtasks (when it comes around again), increasing the period for the 1st subtask, which would reduce its priority.

|improve this answer
  • But using the 30 second example, when doing it dynamically, wouldn't the scheduler consider it to have a period of 30 before the first sleep, a period of 20 seconds after the first sleep, and a period of 10 after the second sleep? Since it doesn't know that there are sleeps before it runs, or where they're going to run? Or would that just apply to the first time that task ran, and on subsequent runs it would remember the sleeps and adjust? – Matthew Cline Oct 26 '14 at 19:40
  • @MatthewCline: as mentioned in the answer, the scheduler doesn't monitor the sleep calls, it only checks whether or not the process is schedulable. Consider how the scheduler determines the period: it tracks the time since the process was last ready for scheduling (perhaps using exponential averaging). Before the first time P<sub>2</sub>' runs, it has no known period. When the 2nd subtask runs, it's 10s after the process was first scheduled, so it has a period of 10s. The same holds for the 3rd subtask (which happens 10s after the 2nd). – outis Oct 27 '14 at 0:15
  • ... The same holds each additional time the process wakes up to run a subtask (assuming both that the execution time remains fairly regular, and that the process start isn't dependent on something that happens in subtask 3, such as sending a message over the network). – outis Oct 27 '14 at 0:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.