Самый ранний срок планирования

Question

Я хочу реализовать ранние сроки в C, но не могу найти алгоритм в сети.

Я понимаю пример ниже, что когда время равно 0, прибывают и А1, и В1. Поскольку у А1 самый ранний срок, он запланирован первым. Когда A1 завершается, процессор получает B1. Когда время равно 20, приходит A2. Поскольку у А2 более ранний срок, чем у В1, В1 прерывается, так что А2 может выполняться до завершения. Затем B1 возобновляется, когда время равно 30. Когда время равно 40, приходит A3. Тем не менее, B1 имеет более ранний крайний срок окончания и может выполняться до завершения, когда время составляет 45. Затем A3 получает процессор и завершает работу, когда время составляет 55. Однако я не могу найти решение. Пожалуйста, помогите мне найти алгоритм. Спасибо..

Изображение примера

http://imageshack.us/photo/my-images/840/scheduling.png/

Answer 1

• когда процесс заканчивается (и в начале), возьмите процесс с самым низким processTimeToDeadline - processTimeToExecute как новый текущий процесс
• Когда приходит новый процесс, замените текущий процесс тогда и только тогда, когда newProcessTimeToDeadline - newProcessTimeToExecute < currentProcessTimeToDeadline - currentProcessTimeStillNeededToExecute,

Примечание: если вы делаете это с несколькими процессорами, у вас возникает проблема планирования многопроцессорных систем, то есть выполнение NP завершено.

Answer 2

В предыдущем ответе описан планировщик "Самый ранний выполнимый крайний срок - первый" (EFDF), и он идеально подходит к изображению из вопроса. Планировщик "Самый ранний срок - первый" (EDF) является более простым. Планировщик просто запускает задание с самым ранним сроком. И это все.