Scheduling in RT linux

Initially RTLinux has a quite primitive, preemptive and fixed priority scheduler which does not have protection against impossible schedules (may lead to starvation). Therefor we think that the programmer has to be sure not to put the OS in starvation and not to schedule more processes than the CPU can handle to still manage to complete them in time. And it's much harder for the programmer to know whether the tasks will be executed before deadline or not. If the OS is going to run in a very time critical environment it will probably be desired, if not also needed, to use a more fancy scheduling algorithm. We think the possibility to use the more complex algorithms rate-monotonic scheduling or EDF scheduling makes RTLinux much more useful. If you need to be totally sure that deadlines are met you can use EDF scheduling or, if your processes are periodic, you can use rate-monotonic scheduling and calculate how low your CPU utilization.

1. Rate-Monotonic : 

The most commonly used static scheduling algorithm is the Rate Monotonic(RM) scheduling algorithm.The RM algorithm assigns different priorities proportional to the frequency of tasks.The task with the shortest period gets the highest priority, and the task with the longest period gets the lowest static priority.Rate monotonic algorithm is a dynamic preemptive algorithm based on static prioritiesRM algorithm provides no support for dynamically changing task periods and/or priorities and tasks that may experience priority inversion.A static priority scheduler for periodic tasks where the task with the smallest period is assigned the highest priority. This is provably the optimal policy.

Priority inversion occurs in an RM system where in order to enforce rate monotonicity, a non-critical task with a high frequency of execution is assigned a higher priority than a critical task with lower frequency of execution. A priority ceiling protocol (PCP) can be used to counter priority inversion, wherein a task blocking a higher priority task inherits the higher priority for the duration of the blocked task. The priority ceiling protocol is used to schedule a set dependant periodic tasks that share resources protected by semaphores.

2.Earliest deadline first :

A dynamic priority scheduler in which the task with the nearest deadline is scheduled.Earliest deadline first (EDF) scheduling can be used for both static and dynamic real-time scheduling.A dynamic priority algorithm which uses the deadline of a task as its priority.The task with the earliest deadline has the highest priority A variant of EDF is Minimum Laxity First (MLF) scheduling where a laxity is assigned to each task in the system and minimum laxity tasks are executed first. 

Laxity : The difference between the time until a tasks completion deadline and its remaining processing time requirement.