Earliest deadline first scheduling

Are you an EPFL student looking for a semester project?

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Earliest deadline first (EDF) or least time to go is a dynamic priority scheduling algorithm used in real-time operating systems to place processes in a priority queue. Whenever a scheduling event occurs (task finishes, new task released, etc.) the queue will be searched for the process closest to its deadline. This process is the next to be scheduled for execution. EDF is an optimal scheduling algorithm on preemptive uniprocessors, in the following sense: if a collection of independent jobs, each characterized by an arrival time, an execution requirement and a deadline, can be scheduled (by any algorithm) in a way that ensures all the jobs complete by their deadline, the EDF will schedule this collection of jobs so they all complete by their deadline. With scheduling periodic processes that have deadlines equal to their periods, EDF has a utilization bound of 100%. Thus, the schedulability test for EDF is: where the are the worst-case computation-times of the processes and the are their respective inter-arrival periods (assumed to be equal to the relative deadlines). That is, EDF can guarantee that all deadlines are met provided that the total CPU utilization is not more than 100%. Compared to fixed priority scheduling techniques like rate-monotonic scheduling, EDF can guarantee all the deadlines in the system at higher loading. Note that use the schedulability test formula under deadline as period. When deadline is less than period, things are different. Here is an example: The four periodic tasks needs scheduling, where each task is depicted as TaskNo( computation time, relative deadline, period). They are T0(5,13,20), T1(3,7,11), T2(4,6,10) and T3(1,1,20). This task group meets utilization is no greater than 1.0, where utilization is calculated as 5/20+3/11+4/10+1/20 = 0.97 (two digits rounded), but it's still unscheduable, check EDF Scheduling Failure figure for details. EDF is also an optimal scheduling algorithm on non-preemptive uniprocessors, but only among the class of scheduling algorithms that do not allow inserted idle time.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (77)

Related people (25)

Related units (12)

Related concepts (3)

Related courses (1)

Related lectures (23)

Explores time-determinator model checking, U-Pool scheduling, worst-case execution time analysis, and statistical model checking for cyber-physical systems.

Delves into building efficient safety-critical systems, emphasizing the importance of worst-case execution times and the challenges of integrating efficiency considerations into design processes.

Explores RTOS scheduler mechanisms, semaphores, mutexes, and communication methods between tasks.

Activity-based models offer the potential for a far deeper understanding of daily mobility behaviour than trip-based models. Based on the fundamental assumption that travel demand is derived from the need to do activities, they are flexible tools that aim ...

EPFL2024

This paper focuses on 5G RAN slicing, where the 5G radio resources must be divided across slices (or enterprises) so as to achieve high spectrum efficiency, fairness and isolation across slices, and the ability for each slice to customize how the radio res ...

USENIX ASSOC2023

Simulating intra-household interactions for in- and out-of-home activity scheduling

Michel Bierlaire, Timothy Michael Hillel, Negar Rezvany

Various interactions, time arrangements, and constraints exist for individuals scheduling their day as a member of a household, which affect their in-home as well as out-of-home activity schedule. However, the existing activity-based models are mostly base ...

2023

Explores time-determinator model checking, U-Pool scheduling, worst-case execution time analysis, and statistical model checking for cyber-physical systems.

Delves into building efficient safety-critical systems, emphasizing the importance of worst-case execution times and the challenges of integrating efficiency considerations into design processes.

Explores RTOS scheduler mechanisms, semaphores, mutexes, and communication methods between tasks.

In computer science, rate-monotonic scheduling (RMS) is a priority assignment algorithm used in real-time operating systems (RTOS) with a static-priority scheduling class. The static priorities are assigned according to the cycle duration of the job, so a shorter cycle duration results in a higher job priority. These operating systems are generally preemptive and have deterministic guarantees with regard to response times. Rate monotonic analysis is used in conjunction with those systems to provide scheduling guarantees for a particular application.

A real-time operating system (RTOS) is an operating system (OS) for real-time computing applications that processes data and events that have critically defined time constraints. An RTOS is distinct from a time-sharing operating system, such as Unix, which manages the sharing of system resources with a scheduler, data buffers, or fixed task prioritization in a multitasking or multiprogramming environment. Processing time requirements need to be fully understood and bound rather than just kept as a minimum.

In computing, scheduling is the action of assigning resources to perform tasks. The resources may be processors, network links or expansion cards. The tasks may be threads, processes or data flows. The scheduling activity is carried out by a process called scheduler. Schedulers are often designed so as to keep all computer resources busy (as in load balancing), allow multiple users to share system resources effectively, or to achieve a target quality-of-service.

Hardware-software co-design is a well known concept in embedded system design.It is also a concept required in designing FPGA-accelerators in data-centers.This course teaches how to transform algorith