Design and implementation of different scheduling algorithms in RTLinux

Welcome to the homepage for the CSC-714 project for group 10. Our goal is to design and implement various scheduling algorithms over RTLinux including EDF, PIP and PCEP. 

The Earliest  Deadline First (EDF)  algorithm is a dynamic priority-scheduling  algorithm in which the priorities of individual  jobs are based on their  absolute deadlines. An EDF algorithm can generate a feasible schedule  for a system of  N independent, pre-emptable tasks as  long as  the total density of the system are less than 1. Hence EDF is an optimal scheduling algorithm. We propose to implement EDF and its enhancements in RTLinux. 

The EDF scheduler  essentially  focuses on scheduling  the processor  for  each process. However, in addition to the processor, each job may require some other resource in order to execute. This resource contention affects the execution behavior and schedulability of jobs. There are various access-control protocols that work to reduce the undesirable effect of resource contention. Priority Inheritance Protocol (PIP) and Priority Ceiling Protocol (PCEP) are two such protocols.

In the priority inheritance protocol (PIP), the resource holder  inherits the  priority of the highest priority blocked process. When a thread tries to lock a resource using this protocol and is blocked, the resource owner temporarily receives  the blocked  thread's  priority, if  that  priority  is  higher  than the owner's. It recovers its original priority when it unlocks the resource. 

Priority Ceiling means that while a process owns the resource lock it runs at a priority higher than any other process that may acquire the resource. In the priority ceiling solution each shared resource is initialized to a priority ceiling. Whenever a process locks this resource, the priority of the process is raised to the priority ceiling. This works as long as the priority ceiling is greater than the priorities of any process that may lock the resource.

One advantage of PCEP over PIP is that PCEP does not lead to deadlocks while PIP can lead to deadlocks.

_____________________________________________________________________