Task planners

Question

It was interesting to talk with some colleagues about the best planning strategies for real-time tasks, but not everyone had a good understanding of common or useful planning strategies.

For your answer, please select one strategy and consider it in detail, instead of giving a little information about several strategies. If you have something to add to the description of someone else, and this is short, add a comment, not a new answer (if it is long or useful or just a much better description, then please use the answer)

• What is the strategy to describe the general case (suppose that people know what the task queue, semaphores, locks, and other OS fundamentals are outside the scheduler itself)
• What optimizes this strategy (latency, efficiency, real time, jitter, resource sharing, etc.).
• It is in real time, or it can be done in real time.

Current strategies:

• Priority Priority
• The slowest hours with the least power

-Adam

Answer 1

As described in a document called Real-time job scheduling for energy-efficient embedded systems , Swaminathan and Chakrabarty describe real-time problems scheduling tasks in low-power (embedded) devices with multiple processor speeds and power profiles. The scheduling algorithm they describe (and, as shown, is only 1% worse than the optimal solution in tests) has an interesting way of scheduling tasks, which they call the LEDF heuristic.

From the article:

The earliest deadline with the least energy heuristic or simply LEDF, is an extension of the well-known early deadline first (EDF) algorithm. LEDF's work is as follows: LEDF maintains a list of all issued tasks, called a "ready-made list." when tasks are released, the task with the next deadline selected is executed. A check is performed to see if the deadline for the task can be satisfied by performing it at a lower voltage (Speed). If the deadline can be satisfied, the LEDF assigns a lower voltage to the task, and the task starts execution. During the execution of tasks, other tasks may be logged on. These are assumed to have tasks automatically in the "finished list." The LED again selects the task using the nearest deadline for execution. As long as there are tasks waiting to be completed, LEDF does not support a bachelor. This process is repeated until all tasks are completed planned.

And in the pseudo code:

Repeat forever { if tasks are waiting to be scheduled { Sort deadlines in ascending order Schedule task with earliest deadline Check if deadline can be met at lower speed (voltage) If deadline can be met, schedule task to execute at lower voltage (speed) If deadline cannot be met, check if deadline can be met at higher speed (voltage) If deadline can be met, schedule task to execute at higher voltage (speed) If deadline cannot be met, task cannot be scheduled: run the exception handler! } } 

Real-time scheduling seems to be an interesting and evolving problem, as small devices with low power are becoming more common. I think this is an area in which we will see a lot of further research, and I look forward to being in the know!

Answer 2

One of the common real-time scheduling schemes is to use priority multitasking with priority. Each task is assigned a different priority level.
The task with the highest priority in the readiness queue will be executed. It will work until it abandons the processor (i.e., delays, wait on semaphore, etc.), or a task with a higher priority will be ready to start.

The advantage of this scheme is that the system designer has full control over which tasks will be performed with which priority. The scheduling algorithm is also simple and must be deterministic.

On the other hand, low priority tasks can be depleted for the CPU. This will indicate a design problem.