16. Планирование в системах реального времени: динамический алгоритм edf

Еще одним популярным алгоритмом планирования работы в режиме реального времени является алгоритм с приоритетом для процесса с ближайшим истекающим крайним сроком — EDF (Earliest Deadline First). Это динамический алгоритм, не требующий, как алгоритм RMS, чтобы процесс был периодическим. Он также не требует постоянства интервалов времени использования центрального процессора, как этого требует алгоритм RMS. Как только процесс нуждается в процессорном времени, он объявляет о своем присутствии и своем крайнем сроке. Планировщик ведет список готовых к работе процессов, отсортированный по их крайним срокам. Согласно алгоритму запускается процесс, который идет первым по списку, то есть тот процесс, у которого раньше всех наступит крайний срок. Как только будет готов новый процесс, система проверяет, не наступает ли его крайний срок раньше, чем у процесса, работающего в данный момент. При положительном ответе текущий процесс вытесняется новым процессом. Изначально к работе готовы все три процесса. Они запускаются в порядке близости их крайних сроков. Процесс А должен завершиться к моменту времени t = 30, процесс В должен завершиться к моменту времени t = 40, а процесс С должен завершиться к моменту времени t = 50, стало быть, ближайший крайний срок у процесса А, и он должен быть запущен первым. Вплоть до отметки времени t = 90 выбор процессов такой же, как и при использовании алгоритма RMS. К моменту времени t = 90, процесс А опять готов к работе, и его крайний срок наступает к моменту времени t =120, что совпадает с крайним сроком процесса В. Планировщик может вполне законно выбрать запуск любого из этих двух процессов, но поскольку овладение процессорным временем со стороны процесса В обходится без связанных с этим издержек, то лучше позволить процессу В продолжить его работу, чем нести затраты на переключение процессов. Чтобы избавиться от заблуждения, что RMS и EDF всегда приводят к одинаковым результатам, давайте рассмотрим еще один пример, показанный на рис. 7.14.

В этом примере периоды процессов А, В и С такие же, как и прежде, но теперь процессу А требуется уже не 10, а 15 мс процессорного времени на каждый интервал. Проверка на возможность планирования работы дает следующее вычисление задействованности центрального процессора: 0,500 + 0,375 + 0,100 = 0,975. Остается только 2,5% процессорного времени, но теоретически процессор не перегружен, поэтому есть реальная возможность спланировать его работу.

При использовании алгоритма RMS приоритеты трех процессов по-прежнему имеют значения 33, 25 и 20, поскольку на них влияет период, а не время выполнения. Это время — В1, не заканчивается до момента времени t = 30, к которому процесс А опять готов к работе. Ко времени окончания работы процесса А на отметке t = 45 процесс В опять готов к работе, и он запускается, поскольку у него приоритет выше, чем у процесса С, в результате чего процесс С не выдерживает своего крайнего срока. Алгоритм RMS терпит неудачу.

Теперь посмотрим, как с этим же случаем справляется алгоритм EDF. На отметке t = 30 возникает конкуренция между А2 и С1. Поскольку крайний срок для С1 равен 50, а для А2 он равен 60, то планируется работа процесса С. Здесь поведение алгоритма отличается от поведения алгоритма RMS, при котором выигрывает процесс А, как имеющий более высокий уровень приоритета. К моменту времени t = 90 процесс А готов запуститься в четвертый раз. Крайний срок для А такой же, как и у текущего процесса (120), поэтому у планировщика есть выбор, вытеснять этот процесс или нет. Как и прежде, лучше без необходимости не вытеснять процесс, поэтому ВЗ разрешается завершить свою работу. В примере на рис. 7.14 центральный процессор до момента времени t = 150 загружен на все 100%. Но со временем у него будет простой, так как он используется только на 97,5%. Поскольку все начальные и конечные моменты времени являются кратными 5 мс, простой составит 5 мс. Для достижения 2,5% простоя 5-миллисекундные перерывы в работе должны случаться каждые 200 мс, поэтому они и не показаны на рис. 7.14.

Возникает интересный вопрос, почему же алгоритм RMS потерпел неудачу. Вообще-то, при использовании статических приоритетов работа возможна только в том случае, если загруженность центрального процессора не слишком высока. Лю и Лэйлэнд (1973) доказали, что для любой системы, имеющей периодические процессы, если соблюдается условие

то алгоритм RMS работает надежно. Для 3,4,5,10,20 и 100 процессов максимально разрешенная загруженность процессора составляет соответственно 0,780; 0,757; 0,743; 0,718; 0,705 и 0,696. При m → ∞ максимальная загруженность асимптотически стремится к ln 2. Иными словами, Лю и Лэйлэнд доказали, что для трех процессов, алгоритм RMS всегда срабатывает, если загруженность центрального процессора ниже или равна 0,780. В нашем первом примере она была равна 0,808, но RMS paботал, нам в данном случае просто повезло. При работе с другими периодами и продолжительностями работы и загруженность 0,808 могла привести к неудаче. Во втором примере загруженность центрального процессора была настолько высокой (0, 975), что на работоспособность алгоритма RMS не оставалось никакой надежды. В отличие от этого алгоритм EDF всегда работает при любом поддающемся планированию наборе процессов. При нем может достигаться загруженность процессора, равная 100%. Но за это приходится платить усложнением алгоритма. Таким образом, если на настоящем видеосервере загруженность центрального процессора не превышает лимитов RMS, то на нем может использоваться алгоритм RMS. В противном случае нужно выбирать алгоритм EDF.