Добавлен: 29.10.2018
Просмотров: 48044
Скачиваний: 190
2.4. Планирование
191
большую часть своего времени в ожидании завершения операций ввода-вывода. Как
только такому процессу понадобится центральный процессор, он должен быть предо-
ставлен немедленно, чтобы процесс мог приступить к обработке следующего запроса
на ввод-вывод данных, который затем может выполняться параллельно с другим про-
цессом, занятым вычислениями. Если заставить процесс, ограниченный скоростью
работы устройств ввода-вывода, долго ждать предоставления центрального процессора,
это будет означать, что он занимает оперативную память неоправданно долго. Про-
стой алгоритм успешного обслуживания процессов, ограниченных скоростью работы
устройств ввода-вывода, предусматривает установку значения приоритета в 1/f, где
f — это часть последнего кванта времени, использованного этим процессом. Процесс,
использовавший только 1 мс из отпущенных ему 50 мс кванта времени, должен полу-
чить приоритет 50, в то время как процесс, проработавший до блокировки 25 мс, по-
лучит приоритет, равный 2, а процесс, использовавший весь квант времени, получит
приоритет, равный 1.
Зачастую бывает удобно группировать процессы по классам приоритетности и ис-
пользовать приоритетное планирование применительно к этим классам, а внутри
каждого класса использовать циклическое планирование. На рис. 2.23 показана система
с четырьмя классами приоритетности. Алгоритм планирования выглядит следующим
образом: если есть готовые к запуску процессы с классом приоритетности 4, следует
запустить каждый из них на один квант времени по принципу циклического плани-
рования, при этом вовсе не беспокоясь о классах с более низким приоритетом. Когда
класс с уровнем приоритета 4 опустеет, в циклическом режиме запускаются процессы
с классом приоритетности 3. Если опустеют оба класса, 4 и 3, в циклическом режиме
запускаются процессы с классом приоритетности 2 и т. д. Если приоритеты каким-то
образом не будут уточняться, то все классы с более низким уровнем приоритета могут
«умереть голодной смертью».
Рис. 2.23. Алгоритм планирования для четырех классов приоритетности
Использование нескольких очередей
Одной из самых ранних систем приоритетного планирования была CTSS (Compatible
Time Sharing System — совместимая система разделения времени), разработанная
в Массачусетском технологическом институте, которая работала на машине IBM 7094
(Corbato et al., 1962). CTSS страдала от проблемы очень медленного переключения про-
цессов, поскольку машина 7094 была способна содержать в оперативной памяти лишь
один процесс. Каждое переключение означало сброс текущего процесса на диск и счи-
тывание нового процесса с диска. Разработчики CTSS быстро поняли, что эффективнее
192
Глава 2. Процессы и потоки
было бы время от времени выделять процессам, ограниченным скоростью вычислений,
более существенные кванты времени, вместо того чтобы слишком часто выделять им
небольшие кванты времени (чтобы сократить обмен данными с диском). В то же время
предоставление всем процессам больших квантов времени обернется увеличением време-
ни отклика, о чем мы уже упоминали. Разработчики приняли решение учредить классы
приоритетов. Процессы, относящиеся к наивысшему классу, запускались на 1 квант
времени, процессы следующего по нисходящей класса — на 2 кванта времени, процессы
следующего класса — на 4 кванта времени и т. д. Как только процесс использовал все
выделенные ему кванты времени, его класс понижался.
В качестве примера рассмотрим процесс, который нужен для вычислений продол-
жительностью в 100 квантов времени. Сначала ему будет выделен 1 квант времени,
после чего он будет выгружен на диск. В следующий раз ему перед выгрузкой на диск
будут выделены 2 кванта времени. При последующих запусках он будет получать 4,
8, 16, 32 и 64 кванта времени, хотя из финальных 64 квантов он для завершения своей
работы использует лишь 37. Вместо 100 обменов данными с диском, которые потребо-
вались бы при использовании циклического алгоритма, потребуется только 7 (включая
начальную загрузку). Более того, по мере погружения процесса в очередь приоритетов
он будет запускаться все реже и реже, сберегая время центрального процессора для
коротких интерактивных процессов.
Чтобы уберечь процесс, нуждающийся в длительной работе при первом запуске, но
потом ставший интерактивным, от постоянных «наказаний», была выбрана следующая
политика: когда на терминале набирался символ возврата каретки (нажималась кла-
виша
Enter
), процесс, принадлежащий терминалу, перемещался в класс с более высо-
ким приоритетом, поскольку предполагалось, что он собирался стать интерактивным.
В один прекрасный день некий пользователь, в чьих интересах работал процесс, сильно
ограниченный скоростью вычислений, обнаружил, что, бездумно просиживая время
за терминалом и беспорядочно набирая символ возврата каретки каждые несколько
секунд, можно буквально творить чудеса со временем отклика. Он рассказал об этом
своим друзьям. А они рассказали своим друзьям. Мораль этой истории такова: понять,
что получится из задуманного, на практике куда сложнее, чем усвоить сам принцип
идеи.
Выбор следующим самого короткого процесса
Поскольку предоставление первоочередного запуска самым коротким заданиям приво-
дит к минимизации среднего времени отклика для пакетных систем, было бы неплохо
воспользоваться этим же принципом и для интерактивных процессов. И отчасти это
возможно. Обычно интерактивные процессы следуют схеме, при которой ожидается
ввод команды, затем она выполняется, ожидается ввод следующей команды, затем
выполняется эта команда и т. д. Если выполнение каждой команды рассматривать как
отдельное «задание», то мы можем минимизировать общее время отклика, запустив
первой выполнение самой короткой команды. Проблема состоит в определении того,
какой из находящихся в состоянии готовности процессов является самым коротким.
Один из методов заключается в оценке предыдущего поведения и запуске процесса
с самым коротким вычисленным временем выполнения. Предположим, что для какого-
то терминала оценка времени выполнения одной команды составляет T
0
. Теперь пред-
положим, что следующая оценка этого времени составляет T
1
. Мы можем обновить
2.4. Планирование
193
наш расчет, взяв взвешенную сумму этих двух чисел, то есть aT
0
+ (1 − a)T
1
. Выбирая
значение a, мы можем решить, стоит ли при оценке процесса быстро забывать его
предыдущие запуски или нужно запоминать их надолго. При a = 1/2 мы получаем
следующую последовательность вычислений:
T
0
; T
0
/2 + T
1
/2; T
0
/4 + T
1
/4 + T
2
/2; T
0
/8 + T
1
/8 + T
2
/4 + T
3
/2.
После трех новых запусков значимость T
0
при новой оценке снижается до 1/8.
Технология вычисления следующего значения в серии путем расчета взвешенной
суммы текущего измеренного значения и предыдущих вычислений иногда называется
распределением по срокам давности
. Она применяется во многих ситуациях, где на
основе предыдущих значений нужно выдавать какие-нибудь предсказания. Распреде-
ление по срокам давности особенно просто реализуется при a = 1/2. Все, что при этом
нужно, — добавить новое значение к текущей оценке и разделить сумму на 2 (за счет
сдвига вправо на один бит).
Гарантированное планирование
Совершенно иной подход к планированию заключается в предоставлении пользовате-
лям реальных обещаний относительно производительности, а затем в выполнении этих
обещаний. Одно из обещаний, которое можно дать и просто выполнить, заключается
в следующем: если в процессе работы в системе зарегистрированы n пользователей, то
вы получите 1/n от мощности центрального процессора. Аналогично этому в однополь-
зовательской системе, имеющей n работающих процессов, при прочих равных условиях
каждый из них получит 1/n от общего числа процессорных циклов. Это представляется
вполне справедливым решением.
Чтобы выполнить это обещание, система должна отслеживать, сколько процессорного
времени затрачено на каждый процесс с момента его создания. Затем она вычисляет ко-
личество процессорного времени, на которое каждый из них имел право, а именно время
с момента его создания, деленное на n. Поскольку также известно и количество времени
центрального процессора, уже полученное каждым процессом, нетрудно подсчитать
соотношение израсходованного и отпущенного времени центрального процессора. Со-
отношение 0,5 означает, что процесс получил только половину от того, что должен был
получить, а соотношение 2,0 означает, что процесс получил вдвое больше времени, чем
то, на которое он имел право. Согласно алгоритму, после этого будет запущен процесс
с самым низким соотношением, который будет работать до тех пор, пока его соотношение
не превысит соотношение его ближайшего конкурента. Затем для запуска в следующую
очередь выбирается этот процесс.
Лотерейное планирование
Выдача пользователям обещаний с последующим их выполнением — идея неплохая, но
реализовать ее все же нелегко. Но есть и другой, более простой в реализации алгоритм,
который можно использовать для получения столь же предсказуемых результатов. Он
называется лотерейным планированием (Waldspurger and Weihl, 1994).
Основная идея состоит в раздаче процессам лотерейных билетов на доступ к различным
системным ресурсам, в том числе к процессорному времени. Когда планировщику нуж-
но принимать решение, в случайном порядке выбирается лотерейный билет, и ресурс
194
Глава 2. Процессы и потоки
отдается процессу, обладающему этим билетом. Применительно к планированию про-
цессорного времени система может проводить лотерейный розыгрыш 50 раз в секунду,
и каждый победитель будет получать в качестве приза 20 мс процессорного времени.
Перефразируя Джорджа Оруэлла, можно сказать: «Все процессы равны, но некоторые
из них равнее остальных». Более важным процессам, чтобы повысить их шансы на
выигрыш, могут выдаваться дополнительные билеты. Если есть 100 неразыгранных
билетов и один из процессов обладает двадцатью из них, то он будет иметь 20 %-ную ве-
роятность выигрыша в каждой лотерее. В конечном счете он получит около 20 %
процессорного времени. В отличие от приоритетного планирования, где очень трудно
сказать, что на самом деле означает приоритет со значением 40, здесь действует вполне
определенное правило: процесс, имеющий долю из f билетов, получит примерно f долей
рассматриваемого ресурса.
У лотерейного планирования есть ряд интересных свойств. Например, если появится
новый процесс и ему будет выделено несколько билетов, то уже при следующем ло-
терейном розыгрыше он получит шанс на выигрыш, пропорциональный количеству
полученных билетов. Иными словами, лотерейное планирование очень быстро реаги-
рует на изменение обстановки.
Взаимодействующие процессы могут по желанию обмениваться билетами. Например,
когда клиентский процесс отправляет сообщение серверному процессу, а затем блоки-
руется, он может передать все свои билеты серверному процессу, чтобы повысить его
шансы быть запущенным следующим. Когда сервер завершит свою работу, он возвра-
щает билеты, чтобы клиент мог возобновить свою работу. Фактически при отсутствии
клиентов серверам билеты вообще не нужны.
Лотерейное планирование может быть использовано для решения проблем, с которыми
трудно справиться другими методами. В качестве одного из примеров можно привести
видеосервер, в котором несколько процессов предоставляют своим клиентам видеопо-
токи, имеющие разную частоту кадров. Предположим, что процессам нужны скорости
10, 20 и 25 кадров в секунду. Распределяя этим процессам 10, 20 и 25 билетов соот-
ветственно, можно автоматически разделить процессорное время примерно в нужной
пропорции, то есть 10 : 20 : 25.
Справедливое планирование
До сих пор мы предполагали, что каждый процесс фигурирует в планировании сам по
себе, безотносительно своего владельца. В результате, если пользователь 1 запускает
9 процессов, а пользователь 2 запускает 1 процесс, то при циклическом планировании
или при равных приоритетах пользователь 1 получит 90 % процессорного времени,
а пользователь 2 — только 10 %.
Чтобы избежать подобной ситуации, некоторые системы перед планированием ра-
боты процесса берут в расчет, кто является его владельцем. В этой модели каждому
пользователю распределяется некоторая доля процессорного времени и планировщик
выбирает процессы, соблюдая это распределение. Таким образом, если каждому из
двух пользователей было обещано по 50 % процессорного времени, то они его получат,
независимо от количества имеющихся у них процессов.
В качестве примера рассмотрим систему с двумя пользователями, каждому из которых
обещано 50 % процессорного времени. У первого пользователя четыре процесса, A, B,
C и D, а у второго пользователя только один процесс — E. Если используется цикли-
2.4. Планирование
195
ческое планирование, то возможная последовательность планируемых процессов,
соответствующая всем ограничениям, будет иметь следующий вид:
AEBECEDEAEBECEDE...
Но если первому пользователю предоставлено вдвое большее время, чем второму, то
мы можем получить следующую последовательность:
ABECDEABECDE…
Разумеется, существует масса других возможностей, используемых в зависимости от
применяемых понятий справедливости.
2.4.4. Планирование в системах реального времени
Системы реального времени относятся к тому разряду систем, в которых время играет
очень важную роль. Обычно одно или несколько физических устройств, не имеющих
отношения к компьютеру, генерируют входные сигналы, а компьютер в определенный
промежуток времени должен соответствующим образом на них реагировать. К приме-
ру, компьютер в проигрывателе компакт-дисков получает биты от привода и должен
превращать их в музыку за очень короткий промежуток времени. Если вычисления
занимают слишком много времени, музыка приобретет довольно странное звучание.
Другими системами реального времени являются система отслеживания параметров
пациента в палате интенсивной терапии, автопилот воздушного судна, устройство
управления промышленными роботами на автоматизированном предприятии. Во всех
этих случаях получение верного результата, но с запозданием, зачастую так же непри-
емлемо, как и неполучение его вообще.
Системы реального времени обычно делятся на жесткие системы реального времени
(системы жесткого реального времени), в которых соблюдение крайних сроков обяза-
тельно, и гибкие системы реального времени (системы мягкого реального времени),
в которых нерегулярные несоблюдения крайних сроков нежелательны, но вполне
допустимы. В обоих случаях режим реального времени достигается за счет разделе-
ния программы на несколько процессов, поведение каждого из которых вполне пред-
сказуемо и заранее известно. Эти процессы являются, как правило, быстротечными
и способными успешно завершить свою работу за секунду. При обнаружении внешнего
события планировщик должен так спланировать работу процессов, чтобы были со-
блюдены все крайние сроки.
События, на которые должна реагировать система реального времени, могут быть
определены как периодические (происходящие регулярно) или апериодические (про-
исходящие непредсказуемо). Возможно, системе придется реагировать на несколько
периодических потоковых событий. В зависимости от времени, необходимого на обра-
ботку каждого события, с обработкой всех событий система может даже не справиться.
Например, если происходит m периодических событий, событие i возникает с периодом
P
i
и для обработки каждого события требуется C
i
секунд процессорного времени, то
поступающая информация может быть обработана только в том случае, если