Alternative of EDF algorithm

Question

I want to know whether any alternatives to Earliest Deadline First (EDF) scheduling algorithm are available. If yes, please provide the reference links.

Thanks.

Answer 1

Deadline scheduling can be divided into two categories: 1) as thought of by the real-time computing community; and 2) as thought of by the scheduling theory community. Category 1 is a subset of category 2. Most practitioners of real-time computing are unaware of category 2.

The primary distinction is that category 1 assumes the relatively simple special case that deadlines are either met or missed, and that missing deadlines is a failure, so the scheduling optimality criterion is to meet all deadlines (so-called "hard" real-time). Earliest Deadline First (EDF) is the most common category 1 deadline scheduling algorithm. There is a vast body of literature on category 1 deadline scheduling -- e.g., in the proceedings of the IEEE Real-Time Systems Symposium. A good book is Stankovic et al.'s Deadline Scheduling for Real-Time Systems - EDF and Related Algorithms.

AFAIK, there are no extant real-time operating system COTS products that implement deadline scheduling, particularly EDF. Several commercial products have been attempted (e.g., DEC, IBM) but abandoned due to various difficulties, such as integrating EDF with other resource management (e.g., synchronizers, non-scheduled activities) in the OS while maintaining backwards compatibility. The solution is to design deadline scheduling (EDF and other algorithms) as an integral part of the OS from scratch. I am aware of three COTS real-time OS products that did that, none of which made it to the market for organizational reasons unrelated to the OS: DECs Libra, IBMs OS/2 for PowerPC (done in collaboration with DEC), and the Open Software Foundation's OSF-1 Mk7.3a (done in collaboration with DEC and IBM). Some research OSs designed and implemented from the bare hardware up (e.g., Jensen's Alpha at CMU) have succeeded at incorporating deadline scheduling. Alpha took advantage of having total freedom by allowing arbitrary scheduling algorithms to be plugged in, including EDF and Utility Acrual ones. Other research OSs have sought to augment Linux (cf. VA Tech's ChronOS project cited by Jonatan Anderson's post). ChronOS is constrained by being Linux-based but also supports Utility Accrual scheduling algorithms.

Category 2 encompasses the entire topic of deadline scheduling in general, of which category 1 is an easier subset. In particular, category 2 recognizes the concepts of earliness and tardiness with respect to a deadline. Scheduling optimality criteria include minimizing the number of missed deadlines, minimizing the mean tardiness, minimzing the maximum tardiness, and many (any) others. Technically, category 2 minus the category 1 subset is "soft" real-time," although real-time practitioners and even researchers use many different imprecise and inaccurate descriptions of the term "soft" real-time. Category 2 scheduling is more difficult than is category 1 scheduling. However, it is more realistic and more widely applicable, used in many industries (e.g., transportation, manufacturing, etc.). There is an even greater body of literature than for category 1. A good textbook is Pindo's Scheduling: Theory, Algorithms, and Systems.

Answer 2

The stock linux kernel only supports the following scheduling policies (for the CPU):

• SCHED_FIFO -- FIFO real-time priority scheduling
• SCHED_RR -- Round-robin real-time priority scheduling
• SCHED_OTHER -- non real-time, best-effort scheduling

Notably absent given your question is EDF, or indeed any deadline-driven scheduler. Why not? Well, the number of applications willing to do the analysis required to make use of a deadline scheduler and the complications with integrating it with other scheduling policies may be the drivers. An LWN article does discuss deadline scheduling in Linux, circa 2009.

Some efforts have attempted to provide additional scheduling policies for Linux. A couple of good examples would be UNC's LitmusRT project and Virginia Tech's ChronOS project. LitmusRT focuses on a family of soft real-time schedulers and accompanying synchronization primitives. ChronOS is in the same domain, but is primarily focused on Utility-Accrual (UA) driven scheduling (see, e.g., this thesis and time-utility functions on Jensen's page) and synchronization policies.

There also appears to be a recent EDF scheduler implementation (which I haven't used, and hadn't noticed until answering this question.) "Evidence" EDF scheduler.

There are also commercial linux vendors which have other real-time scheduler implementations. Their availability can be a bit confusing. An example is Concurrent's RedHawk linux, which includes a time-driven scheduling policy. Details of the OS are covered in the datasheet. RedHawk is in use in a number of real-time and distributed US DoD applications.