An Overview of EDF and SRP

EDF (Earliest Deadline First) is a scheduling policy used in real-time systems and SRP (Stack Resource Policy) is a resource allocation policy in real-time systems. The two work well together to create a deterministic process and memory management system. The following is a brief overview of the policies. Exact implementation details of the policies and current research in these areas can be found online in the ACM Digital Library.

Introduction to EDF

Earliest deadline first (EDF) or “least time to go” is a dynamic scheduling algorithm used in real-­time operating systems to place processes in a priority queue. In this scheme, the scheduler is invoked at specific ‘decision points’. The decision points or scheduling events occur whenever a job finishes, or a new job is released and added to the ready queue. At these points, the scheduler is invoked and the ready queue will be searched for the process closest to its deadline. This process is then selected for execution and dispatched.

Intuitively, this policy of dispatching jobs that are closest to the deadline means that jobs with earlier deadlines have a higher priority than jobs with later deadlines. This can be explained in a simple, easy-to-remember phrase: “tasks that are due sooner are done sooner”.

EDF is an optimal scheduling algorithm on preemptive uniprocessors. An optimal scheduler means that if a feasible schedule exists for a certain task set, then that scheduler will be able to execute it without any deadline misses. EDF can guarantee that all deadlines are met provided that the total CPU utilization is not more than 100%. However, when the system is overloaded, some or all jobs of tasks in the task set will miss their deadlines. This set of jobs that will miss deadlines is mostly unpredictable, and it depends on the conditions of overload i.e. the exact deadlines and the time of overload.

So, a schedulability test must be done on the task set to determine if it is schedulable or not. If there is a possibility of a job missing its deadline, then the task set is reported as not 100% schedulable (depending on the conditions of overload), and EDF cannot give any guarantees about jobs adhering to their deadlines. In this case, in a hard real-time system, some of the tasks will have to be excluded from the task set in order to guarantee schedulability for the remaining tasks. In systems whose failure can cause catastrophes, it is essential to ensure that every possible task set that can execute on the system will be 100% schedulable with no deadline misses. Some degree of error can be tolerated in soft real-time systems where adhering to the deadline is a measure of performance, but missing the deadline is not particularly catastrophic.

Introduction to SRP

The overall RAM requirement of any system is the sum of many factors, global variables, dynamically allocated heap memory, operating system variables and stack space requirements for local variables and function call parameters. The RAM requirement must be made deterministic for real-­time systems. Of all the mentioned factors, the stack space requirements can be a significant factor. Also, it can be limited with appropriate OS memory management policies. Ideally, there should be no dynamic heap in hard real­-time systems.

The Stack Resource Policy (SRP) is a resource allocation policy which permits processes with different priorities to share a single runtime stack. SRP integrates very easily and elegantly with systems that are scheduled using the Earliest Deadline First (EDF) scheduling algorithm.

Resource sharing in priority­-based systems can give rise to priority-­inversion and blocking, wherein a job’s execution is delayed because a lower­ priority job holds some resource that is needed for execution. The Stack Resource Policy (SRP) can be used to reduce such blocking in EDF-­scheduled systems. It has been shown that under the SRP, no job is blocked for more than the length of one outer­most critical section of any lower ­priority job.

SRP is based on the idea of non­-interleaved execution. The principles followed are as follows:

1) Once a job has been started, it cannot be blocked till completion. It can only be preempted by higher priority jobs.
2) Task executions are perfectly nested. When a job J is preempted by a job J’, J continues to hold its stack space and J’ is allocated space immediately above it on the stack. The requirement for SRP is that if J is preempted, it cannot resume execution until all the jobs that occupy stack space above it have completed. Since these jobs must have higher priority, this requirement is consistent with priority scheduling.
3) If task preemption is limited to occur only between selected task groups, it is possible to bound the maximum number of task frames concurrently active in the stack, therefore reducing the maximum requirement of RAM space for the stack (which is the only way the OS can limit RAM requirements).

The SRP policy has a number of advantages: It prevents deadlock, bounds the maximum blocking times of tasks, reduces the number of context switches, can be easily extended to multi-­unit resources, and allows tasks to share a unique stack.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s