Страница 1 из 1

О алгоритме edf

СообщениеДобавлено: 17 апр 2010, 10:14
Gemini
Порылся по инету и кажется понял, как этот алгоритм работает, но все же уточню.
На примере.
Допустим есть 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 и только потом С ? Если приоритет по времени работы, должен же был С отработать первым. Это ошибка на рисунке?

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

СообщениеДобавлено: 17 апр 2010, 10:42
Vladislav_133
какой этот?

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

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

Это то что записали на лекции по СРВ о этом алгоритме. Возможно у меня записанно не точно.

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

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

могу ошибаться :-)

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

СообщениеДобавлено: 17 апр 2010, 22:14
Vladislav_133
А вот вы о чем. А я прочел не внимательно и подумал, что вы что-то предлагаете.

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

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

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

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

Вопрос в следующем - они должны выполняться как задания с наивысшим приоритетом, с времени их первого запуска, или же как задачи с приоритетом "второй после текущего" ?