Alternative to EDF Algorithm

Question

I want to know if alternatives to the Early Termination Planning (EDF) algorithm are available. If yes, provide links.

Thanks.

Answer 1

Timing planning can be divided into two categories: 1) what the real-time computing community thinks; and 2) what the planning theory community is thinking about. Category 1 is a subset of category 2. Most real-time practitioners are not aware of category 2.

The main difference is that category 1 assumes a relatively simple special case when the deadlines are either met or missed, and the missing deadlines are a failure, so the criterion for optimal planning meets all deadlines (the so-called “hard” real-time). Earliest Deadline (EDF) is the most common deadline planning algorithm in Category 1. There is a tremendous amount of literature on scheduling dates for category 1 — for example, in the IEEE symposium in real time. A good book is Stankovic et al. Scheduling for real-time systems - EDF and related algorithms .

AFAIK, there are currently no COTS real-time operating system products that implement scheduling, in particular EDF. Several commercial products were taken (for example, DEC, IBM), but they refused because of various difficulties, such as integrating EDF with other resource management (for example, synchronizers, unplanned actions) in the OS while maintaining backward compatibility. The solution is scheduling (EDF and other algorithms) as an integral part of the OS from scratch. I know about the three real-time COTS OS products that did this, none of which entered the market for organizational reasons not related to the OS: DECs Libra, IBM OS / 2 for PowerPC (done in collaboration with DEC) and Open Software Foundation OSF-1 Mk7.3a (implemented in collaboration with DEC and IBM). Some research OSs developed and deployed with bare hardware (such as Jensen Alpha in the CMU) have been able to include scheduling. Alpha took full advantage of the freedom to enable arbitrary scheduling algorithms, including EDF and Utility Acrual. Other research OSes sought to expand Linux (see Jonathan Anderson's VA Tech ChronOS Project). ChronOS is limited to the Linux base, but also supports Utility Accrual accrual scheduling algorithms.

Category 2 covers the whole topic of timing planning in general, of which category 1 is an easier subset. In particular, category 2 recognizes the concepts of wounding and being late in relation to the deadline. Planning optimality criteria include minimizing the number of missed deadlines, minimizing the average delay, the minimum maximum delay, and many (any) others. Technically, category 2 minus the subcategory of category 1 is “soft” in real time, although real-time practitioners and even researchers use many different inaccurate and inaccurate descriptions of the term “soft” real-time. This is a schedule for category 1. However, it is more realistic and more widely applicable, used in many industries (for example, in the field of transport, manufacturing, etc.). There is an even greater volume of literature than for category 1. A good textbook is Pindo Plan tion: theory, algorithms, and systems .

Answer 2

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

• SCHED_FIFO - real-time priority scheduling FIFO
• SCHED_RR - Real-time Priority Scheduling
• SCHED_OTHER - not in real time, best planning

Noticeably absent if your question is asked by EDF, or even a time-oriented scheduler. Why not? Well, the number of drivers who want to do the analysis needed to use the scheduler, and the complications with integrating it with other planning policies, can be drivers. An LWN article discusses scheduling on Linux around 2009.

Some efforts have attempted to provide additional planning policies for Linux. Some good examples are the UNC LitmusRT project and the Virginia Tech ChronOS project . LitmusRT focuses on a family of soft real-time schedulers and accompanying synchronization primitives. ChronOS is in the same domain, but is mainly focused on planning based on Utility-Accrual (UA) (see, for example, this thesis and time-utility functions on the Jensen page) and synchronization policies.

A recent implementation of the EDF scheduler also appeared (which I did not use and did not notice before answering this question.) "Evidence" EDF scheduler .

There are also commercial Linux vendors that have other real-time scheduler implementers. Their availability can be a bit confusing. For example, Concurrent RedHawk linux , a planning-oriented policy. Detailed information about the OS is given in the data table . RedHawk is used in many real-time DoD applications and distributed applications.