<p>Had an interesting discussion with some colleagues about the best scheduling strategies for realtime tasks, but not everyone had a good understanding of the common or useful scheduling strategies.</p>

<p>For your answer, please choose one strategy and go over it in some detail, rather than giving a little info on several strategies.  If you have something to add to someone else's description and it's short, add a comment rather than a new answer (if it's long or useful, or simply a much better description, then please use an answer)</p>

<ul>
<li>What is the strategy - describe the general case (assume people know what a task queue is, semaphores, locks, and other OS fundamentals outside the scheduler itself)</li>
<li>What is this strategy optimized for (task latency, efficiency, realtime, jitter, resource sharing, etc)</li>
<li>Is it realtime, or can it be made realtime</li>
</ul>

<p>Current strategies:</p>

<ul>
<li><a href="https://stackoverflow.com/questions/49962/task-schedulers#74894">Priority Based Preemptive</a></li>
<li><a href="https://stackoverflow.com/questions/49962/task-schedulers#50056">Lowest power slowest clock</a></li>
</ul>

<p>-Adam</p>

[{'answer_id': 50056, 'author': 'Sean', 'author_id': 4919, 'author_profile': 'https://Stackoverflow.com/users/4919', 'pm_score': 4, 'selected': True, 'text': '<p>As described in a paper titled <a href="http://www.ee.duke.edu/~krish/wip.pdf" rel="noreferrer">Real-Time Task Scheduling for Energy-Aware Embedded Systems</a>, Swaminathan and Chakrabarty describe the challenges of real-time task scheduling in low-power (embedded) devices with multiple processor speeds and power consumption profiles available. The scheduling algorithm they outline (and is shown to be only about 1% worse than an optimal solution in tests) has an interesting way of scheduling tasks they call the LEDF Heuristic.</p>\n\n<p>From the paper:</p>\n\n<blockquote>\n  <p><em>The low-energy earliest deadline ﬁrst\n  heuristic, or simply LEDF, is an\n  extension of the well-known earliest\n  deadline ﬁrst (EDF) algorithm. The\n  operation of LEDF is as follows: LEDF\n  maintains a list of all released\n  tasks, called the “ready list”. When\n  tasks are released, the task with the\n  nearest deadline is chosen to be\n  executed. A check is performed to see\n  if the task deadline can be met by\n  executing it at the lower voltage\n  (speed). If the deadline can be met,\n  LEDF assigns the lower voltage to the\n  task and the task begins execution.\n  During the task’s execution, other\n  tasks may enter the system. These\n  tasks are assumed to be placed\n  automatically on the “ready list”.\n  LEDF again selects the task with the\n  nearest deadline to be executed. As\n  long as there are tasks waiting to be\n  executed, LEDF does not keep the pro-\n  cessor idle. This process is repeated\n  until all the tasks have been\n  scheduled.</em></p>\n</blockquote>\n\n<p>And in pseudo-code:</p>\n\n<pre><code>Repeat forever {\n    if tasks are waiting to be scheduled {\n        Sort deadlines in ascending order\n        Schedule task with earliest deadline\n        Check if deadline can be met at lower speed (voltage)\n        If deadline can be met,\n            schedule task to execute at lower voltage (speed)\n        If deadline cannot be met,\n            check if deadline can be met at higher speed (voltage)\n        If deadline can be met,\n            schedule task to execute at higher voltage (speed)\n        If deadline cannot be met,\n            task cannot be scheduled: run the exception handler!\n    }\n}\n</code></pre>\n\n<p>It seems that real-time scheduling is an interesting and evolving problem as small, low-power devices become more ubiquitous. I think this is an area in which we\'ll see plenty of further research and I look forward to keeping abreast!</p>\n'}, {'answer_id': 74894, 'author': 'Benoit', 'author_id': 10703, 'author_profile': 'https://Stackoverflow.com/users/10703', 'pm_score': 2, 'selected': False, 'text': '<p>One common real-time scheduling scheme is to use priority-based preemptive multitasking.<br>\nEach tasks is assigned a different priority level.<br>\nThe highest priority task on the ready queue will be the task that runs.  It will run until it either gives up the CPU (i.e. delays, waits on a semaphore, etc...) or a higher priority task becomes ready to run.</p>\n\n<p>The advantage of this scheme is that the system designer has full control over what tasks will run at what priority. The scheduling algorithm is also simple and should be deterministic.</p>\n\n<p>On the other hand, low priority tasks might be starved for CPU. This would indicate a design problem. </p>\n'}]
['https://Stackoverflow.com/questions/49962', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/2915/']