О алгоритме edf

Интересные алгоритмы, олимпиадные задачи, эффектные и эффективные решения. freepascal, delphi, c, c++, c#, java, javascript, perl, ruby, python, php, bash, wsh и т.д. Компиляторы, интерпретаторы, линкеры, отладчики, системы контроля версий и многое другое.

Модератор: xdsl

О алгоритме edf

Сообщение Gemini 17 апр 2010, 10:14

Порылся по инету и кажется понял, как этот алгоритм работает, но все же уточню.
На примере.
Допустим есть 3 процесса
Название, периодичность запуска, время работы.
A 30 15
B 40 15
C 50 5
Так вот, в соответствии с этим алгоритмом они должны работать так.
Название процесса, номер запуска, время начала работы, время окончания работы, оставшееся время, замороженному процессу.
A 1 0 15 0
B 1 15 30 0
C 1 30 35 0 // вот в этом особенность,да? Если бы это был алгоритм rms, то в этот момент должен был бы запуститься процесс A, но так как уже,
A 2 35 50 0 // "теоритически" запущен процесс C, и время его работы меньше чем у процесса A, то первым отработает он.
B 2 50 65 0 // - и здесь процесс B не прерван, т.к. ему осталось работать меньше, чем готовому к работе процессу A.
С 2 65 70 0 // - потом запустился C, т.к. он "готов к запуску" и имеет время работы меньшее,чем у процесса A.

Выводы я делал основываясь на вот этом рисунке

Но появляется вопросы. Почему при запуске отрабатывают процессы A и B и только потом С ? Если приоритет по времени работы, должен же был С отработать первым. Это ошибка на рисунке?
Не относитесь к этой жизни слишком серьезно,господа.Все равно вам из неё живым не выбраться.
Gemini
 
Сообщения: 90
Зарегистрирован: 13 янв 2009, 12:42
Откуда: Сейчас в Ша
Полное имя: Плешков Сергей Александрович

Re: О алгоритме edf

Сообщение Vladislav_133 17 апр 2010, 10:42

какой этот?
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: О алгоритме edf

Сообщение Gemini 17 апр 2010, 13:37

Алгоритм edf (early deadline first) - алгоритм планирования не требующий от процесса периодичности и постоянства временных интервалов использования процессора. Суть алгоритма: Каждый раз, когда процессу требуется процессорное время, он объявляет о своем присутствии и своем сроке выполнения задания (каждый раз, один и тот же процесс может требовать разное количество времени). Планировщик хранит список процессов отсортированный по срокам выполнения заданий (процессов). Алгоритм запускает самый первый процесс в этом списке (процесс, которому работать осталось меньше всего). Когда новый процесс переходит в состояние активности (готовности к запуску) планировщик сравнивает срок его выполнения со сроком выполнения текущего процесса. Если срок выполнения нового процесса меньше, он прерывает работу текущего процесса и начинает выполняться.

Это то что записали на лекции по СРВ о этом алгоритме. Возможно у меня записанно не точно.
Не относитесь к этой жизни слишком серьезно,господа.Все равно вам из неё живым не выбраться.
Gemini
 
Сообщения: 90
Зарегистрирован: 13 янв 2009, 12:42
Откуда: Сейчас в Ша
Полное имя: Плешков Сергей Александрович

Re: О алгоритме edf

Сообщение LMP 17 апр 2010, 21:36

приоритет берётся по времени до дедлайна. у процесса A наименьший период выполнения, поэтому он стартует первым, а процесс C имеет наибольший период, он стартует последним. в edf вообще не важно время выполнения процесса (для выбора последовательности запуска).

могу ошибаться :-)
LMP
Elite
 
Сообщения: 49
Зарегистрирован: 26 янв 2009, 22:05
Полное имя: Кобелев Денис

Re: О алгоритме edf

Сообщение Vladislav_133 17 апр 2010, 22:14

А вот вы о чем. А я прочел не внимательно и подумал, что вы что-то предлагаете.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: О алгоритме edf

Сообщение Gemini 17 апр 2010, 23:00

LMP

Спасибо.Это проясняет ситуацию.

На данный момент написал невытесняющий edf планировщик, который может обрабатывать входные файлы из 3 и 4 лаб. Осталась одна закавырка с процессами имеющими периодичность 0.

Вопрос в следующем - они должны выполняться как задания с наивысшим приоритетом, с времени их первого запуска, или же как задачи с приоритетом "второй после текущего" ?
Не относитесь к этой жизни слишком серьезно,господа.Все равно вам из неё живым не выбраться.
Gemini
 
Сообщения: 90
Зарегистрирован: 13 янв 2009, 12:42
Откуда: Сейчас в Ша
Полное имя: Плешков Сергей Александрович


Вернуться в Алгоритмизация и программирование

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 3

cron