Implementation of RM scheduling algorithm

[hduffddybz]

Hi! Recently my teacher (at yifanwu) are guiding me to the world of RTOS. So the basic work may include the implementation of some classical scheduling algorithm. It has been widely proved that RM(rate monotonic) scheduling is valuable both in academic research and industry filed!

According to the RM scheduling algorithm, tasks are assigned with fixed priorities by their rates, so the task with lower period can get higher priority.

1. But as a real-time operating system, there existed the periodic tasks and aperiodic tasks which can both be essential tasks. It can easily set the priority of periodic tasks by their periods. But the system should not only guarantee that all the periodic tasks can complete within their deadline, but also reduce the response time for aperiodic tasks as much as possible. There existed two kinds of method to solve this problem.
   • The system can schedule the aperiodic tasks by periodic server which allocates a certain amount of budget for aperiodic execution in every period time(Maybe the assignment of period can be a question). Two methods have been put forward in the last century which are the Deferrable Server and Sporadic Server.
   • the Slack Stealing algorithm, the main idea of this algorithm is that there is no benefit for the periodic tasks to complete their tasks much before their deadlines. So when the aperiodic task coming, it steals the available slack from the periodic tasks and execute it as soon as possible.
2. For a hard real-time system, It should guarantee that all the tasks should complete within their deadline, so it should use some off-line mechanism to do the scheduling analysis. The Utilization rule (https://docs.rtems.org/doc-current/share/rtems/html/c_user/Rate-Monotonic-Manager-Processor-Utilization-Rule.html#Rate-Monotonic-Manager-Processor-Utilization-Rule)and first deadline rule(https://docs.rtems.org/doc-current/share/rtems/html/c_user/Rate-Monotonic-Manager-First-Deadline-Rule.html#Rate-Monotonic-Manager-First-Deadline-Rule) was used to test the schedulability of this system. But these analysis can be really difficult because of the calculation of worse-case execution time and the appearance of the aperiodic tasks. And I think we will not implement this off-line tool. Whether it is possible to use the statistical data to guarantee the schedulability of this system next time?

Any more information should be noticed for the implementation of RM?

[grissiom]

IMHO, the core of RM is:

1. tasks with long period has low priority.
2. the system always runs the runnable highest priority task.

So, you will get the latter for free if you use the current kernel. But for the former, how does the kernel would know the period of a task at the time initializing the task? How does the kernel assign the priority for a task relatively to other tasks that has not been initialized by the kernel?

So, IMHO, even for the bare RM algorithm, we need off-line analyze to figure out the priorities for each tasks. Once the off-line analyze is done, than you can assign the priority for each task in rt_thread_{init,create}. Then you get RM for free.

Please correct me if I'm wrong ;-)

BTW, are you going to Harvard? Congratulations!! ;-D

[BernardXiong]

Welcome to do more research base on RT-Thread. To add one or more scheduling algorithm, the scheduler interface need to be modified. If that, please let me know.

[hduffddybz]

how does the kernel would know the period of a task at the time initializing the task?

This period should be set by the programmer since that all this tasks that may include sensor capturing or machine control should be executed at a regular interval all depending on the application.

How does the kernel assign the priority for a task relatively to other tasks that has not been initialized by the kernel?

All the periodic tasks should be initialized when system start up, and all the schedulability analysis should be done before the system start up which made by the off-line tool.What cannot predict for a real-time system may only contains the aperiodic tasks when system is running.

even for the bare RM algorithm, we need off-line analyze to figure out the priorities for each tasks.

What the off-line analysis to do should include that whether the system can be scheduled for these periodic tasks but the assignment of priority for these tasks should be done by the RM scheduling algorithm.

[grissiom]

So, if I understand it right, we are going to implement a "off-line tool" which is powered by the RM algorithm to analyze the schedulability and assign priorities for the priodic tasks, right?

Once we archive this, we may deal with the aperiodic tasks. One step by one step.

[hduffddybz]

@grissiom I think you are wrong! The analysis of the schedulability of Real-Time system should be guaranteed by the application programmer! What the kernel should do include:

1. Assign the priority according to the period(the priority may not be numerical)
2. Implement a periodic server which can run aperiodic and sporadic tasks.
3. When a task miss its deadline or its execution time exceed its wcet(worst case execution time),what the system should do?

when implement this algorithm, I think what should do first include:

1. Implement a queue which has the function "rt_list_priority_insert", this function can enqueue the thread with highest priority to the first place in the queue(May not use the bitmap algorithm because the priority would not be numerical on rm scheduling).
2. When a task miss its deadline, it should raise exception and the task should not execute next time.And I think the proper way to handle the deadline situation is to shut down the system.

[hduffddybz]

Change of the kernel(should be independent from the previous algorithm ) may include:

Change of thread control block

add task criticalness,computation time(worse case execution time),period(task period),relative deadline,utilization factor

Change of thread status

the status of thread should include

1. ready,
2. run,
3. wait,
4. idle(a periodic job enters this state when it completes its execution and has to wait for the beginning of the next period, idle thread should not execute forever as the previous algorithm done,the idle thread should be activated by the timer ),
5. zombie(In the interval of time between the abort operation of the task and the end of its period, this task should be said to be in a ZOMBIE state, you can see an example here: )

List Management

Since the priority of the task depend on the period of it, so the number of task priorities should not limit to 256, and it is not necessary to use bitmap algorithm. Priority queue may be a good alternative, and what am I confused is that whether the insertion of task should be O(1)(any useful algorithm)?

[BernardXiong]

@hduffddybz In RT-Thread, the TCB of each thread, there is a user data filed: struct rt_thread { ... rt_uint32_t user_data; /*< private user data beyond this thread / };

You can extend your scheduler in this field.

Right now, the task queue with READY status is a priority queue. Therefore, you can use current queue implementation.