scheduled-tasksreal-timertos

Assumptions taken in Rate Monotonic Scheduling Algorithm?


I'm doing a Real Time Systems course, and we in the class are stuck in some assumptions in the section 4 of the paper of Liu and Layland about Rate-Monotonic Scheduling that we can not fully understand:

If floor(T2/T1) is the number of Times that Task1 interferes in Task2 why the function applied to T2/T1 is floor and not ceil?

Also, there are these equations:

According to the paper, and as we clearly see in the image, equation (1) is a necessary condition but not sufficient, while equation (2) is a sufficient condition. This gives sense to me, but why do the authors state as a conclusion this:

In other words, whenever the T1 < T2 and C1,C2 are such that the task scheduling is feasible with Task2 at higher priority than Task1, it is also feasible with Task1 at higher priority than Task2 (but opposite is not true)[...] Specifically, tasks with higher request rates will have higher priorities.

If the second equation, where Task2 have the highest priority, is a sufficient condition, why could we assume that the task scheduling would be feasible if Task1 have the highest priority instead of Task2?

I hope i explained myself well, please feel free to tell me also if i've understood wrong the article statements.

EDIT: As requested, here is a little explanation to the terms in the article and presented in this question.

In the article, T1 refers to the Period (and Deadline) of Task1, and T2 to the Period (and Deadline) of Task2. C1 and C2 refer to the runtime of Task1 and Task2 each one.


Solution

  • First of all, too bad you didn't include what T's and C's mean. I had to read the article.

    The first equation (1) defines what is the highest possible T2 period value - it cannot be longer than C2 (time needed to execute task 2) plus C1 multiplied by the number of times task 1 is requested during period T2 (hence, floor(T1/T2)) AND CAN FULLY EXECUTE. If T1 is requested, it's executed no matter what, as in this case it's the highest priority task. Task 2 is not able to execute if task 1 is currently executing.

    Consider the equation (1) with certain values. Let's use the values suggested in the article. T2 = 5, T1 = 2, C1 = C2 = 1. The floor(T2/T1) gives us the number of requests of task 1 that occur during task 2 period. It's 2 (floor(5/2)). If it would be ceiling(T2/T1) than the result would be 3, which is obviously wrong, as the third request was indeed executed (as depicted in Figure 2), but the period didn't end. To understand it better, consider the same case, but extend the task 1 execution time C1 to 1.5. Below is the timeline for such a system, which is feasible. It fulfills the equaiton (1). If we would use ceiling(T2/T1) then the equation would not be fulfilled, and you clearly see below that the system is fine. I think this will help you see and understand the difference - we need to take into account not the number of times the task is requested, but the number of times the full period of a higher priority task can fit in the period of the lower priority task).

    Tasks timeline. Image made using Excel. One "column" is 0.5 unit of time