Глава_1 (1085730), страница 13

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 13)

Приоритеты процессам могут присваиваться статически или динамически. На военной базе процессу, запущенному генералом, присваивается приоритет 100, полковником — 90, майором — 80, капитаном — 70, лейтенантом — 60 и т. д. А в ком­мерческом компьютерном центре выполнение заданий с высоким приоритетом может стоить 100 долларов в час, со средним — 75, с низким — 50. В системе UNIX есть команда nice, позволяющая пользователю добровольно снизить приоритет своих процессов, чтобы быть вежливым по отношению к остальным пользовате­лям. Этой командой никто никогда не пользуется.

Система может динамически назначать приоритеты для достижения своих це­лей. Например, некоторые процессы сильно ограничены возможностями устройств ввода-вывода и большую часть времени проводят в ожидании завершения опе­раций ввода-вывода. Когда бы ни потребовался процессор такому процессу, его следует немедленно предоставить, чтобы процесс мог начать следующий запрос ввода-вывода, который будет выполняться параллельно с вычислениями другого процесса. Если заставить процесс, ограниченный возможностями устройств вво­да-вывода, длительное время ждать доступа к процессору, он будет неоправданно долго находиться в памяти. Простой алгоритм обслуживания процессов, ограни­ченных возможностями устройств ввода-вывода, состоит в установке приоритета, равного 1/f, где f— часть использованного в последний раз кванта. Процесс, ис­пользовавший всего 1 мс из 50 мс кванта, получит приоритет 50, процесс, исполь­зовавший 25 мс, получит приоритет 2, а процесс, использовавший весь квант, по­лучит приоритет 1.

Часто бывает удобно сгруппировать процессы в классы по приоритетам и исполь­зовать приоритетное планирование среди классов, но циклическое планирование внутри каждого класса. На рис. 2.24 представлена система с четырьмя классами приоритетов. Алгоритм планирования выглядит следующим образом: пока в клас­се 4 есть готовые к запуску процессы, они запускаются один за другим согласно алгоритму циклического планирования, и каждому отводится квант времени. При этом классы с более низким приоритетом не будут их беспокоить. Если в классе 4 нет готовых к запуску процессов, запускаются процессы класса 3 и т. д. Если при­оритеты постоянны, до процессов класса 1 процессор может не дойти никогда.

Несколько очередей

Один из первых приоритетных планировщиков был реализован в системе CTSS (compatible time-shared system — совместимая система с разделением времени). Основной проблемой системы CTSS было слишком медленное переключе­ние процессов, поскольку в памяти компьютера IBM 7094 мог находиться только один процесс. Каждое переключение означало выгрузку текущего процесса на диск и считывание нового процесса с диска. Разработчики CTSS быстро сообразили, что эффективность будет выше, если процессам, ограниченным возможностями про­цессора, выделять больший квант времени, чем если предоставлять им небольшие кванты, но часто. С одной стороны, это уменьшит количество перекачек из памяти на диск, а с другой — приведет к ухудшению времени отклика, как мы уже видели. В результате было разработано решение с классами приоритетов. Процессам клас­са с высшим приоритетом выделялся один квант, процессам следующего класса — два кванта, следующего — четыре кванта и т. д. Когда процесс использовал все от­веденное ему время, он перемещался на класс ниже.

В качестве примера рассмотрим процесс, которому необходимо производить вычисления в течение 100 квантов. Вначале ему будет предоставлен один квант, затем он будет перекачан на диск. В следующий раз ему достанется 2 кванта, за­тем 4,8,16, 32, 64, хотя из 64 он использует только 37. В этом случае понадобится всего 7 перекачек (включая первоначальную загрузку) вместо 100, которые пона­добились бы при использовании циклического алгоритма. Помимо этого, по мере погружения в очереди приоритетов процесс будет все реже запускаться, предо­ставляя процессор более коротким процессам.

Чтобы процессу, который при запуске считался долгим, но позже стал интерак­тивным, не погибнуть в недрах планирования, была разработана следующая страте­гия. Как только с терминала приходит сигнал возврата каретки, процесс, соответ­ствующий этому терминалу, переносится в класс высшего приоритета, поскольку предполагается, что он становится интерактивным. Однажды пользователь, запу­стивший процесс, сильно ограниченный возможностями процессора, обнаружил, что бездумное нажимание клавиши возврата каретки существенно уменьшает вре­мя отклика, и рассказал об этом друзьям. Мораль этой истории такова: осуще­ствить задуманное на практике гораздо сложней, чем в теории.

Для разделения процессов по классам используются также многие другие алго­ритмы. Например, в системе XDS 940, разработанной в Беркли, было четыре класса приоритетов, называвшихся: терминал, ввод-вывод, короткий квант и длин­ный квант. Когда запускался процесс, ожидающий вывода на терминал, он пере­мещался в класс высшего приоритета (терминал). Когда снималась блокировка процесса, ожидавшего доступа к диску, он перемещался во второй класс. Если к кон­цу отведенного времени процесс все еще работал, он сначала перемещался в третий класс. Если процесс слишком много раз полностью использовал свой квант време­ни, не блокируясь на терминале или другом устройстве ввода-вывода, он переме­щался в последний класс. Этот метод используется во многих системах для пре­доставления преимущества интерактивным процессам по сравнению с фоновыми.

«Самый короткий процесс — следующий»

Поскольку алгоритм «Кратчайшая задача — первая» минимизирует среднее оборот­ное время в системах пакетной обработки, хотелось бы использовать его и в интерактивных системах. В известной степени это возможно. Интерактивные процес­сы чаще всего следуют схеме «ожидание команды, исполнение команды, ожида­ние команды, исполнение команды...» Если рассматривать выполнение каждой команды как отдельную задачу, можно минимизировать общее среднее время от­клика, запуская первой самую короткую задачу. Единственная проблема состоит в том, чтобы понять, какой из ожидающих процессов самый короткий.

Один из методов основывается на оценке длины процесса, базирующейся на предыдущем поведении процесса. При этом запускается процесс, у которого оце­ненное время самое маленькое. Допустим, что предполагаемое время исполнения команды равно T_о и предполагаемое время следующего запуска равно T₁. Можно улучшить оценку времени, взяв взвешенную сумму этих времен а T_о + (1 - а T₁. Выбирая соответствующее значение а, мы можем заставить алгоритм оценки быс­тро забывать о предыдущих запусках или, наоборот, помнить о них в течение дол­гого времени. Взяв а = 1/2, мы получим серию оценок:

T_о , T_о /2 + T₁,/2, T_о /4 + T₁/4 + T₂/2, T_о/8 + T₁,/8 + T₂/4 + T₃/2. После трех запусков вес T_о в оценке уменьшится до 1/8.

Метод оценки следующего значения серии через взвешенное среднее предыду­щего значения и предыдущей оценки часто называют старением. Этот метод при­меним во многих ситуациях, где необходима оценка по предыдущим значениям. Проще всего реализовать старение при а = 1/2. На каждом шаге нужно всего лишь добавить к текущей оценке новое значение и разделить сумму пополам (сдвинув вправо на 1 бит).

Гарантированное планирование

Принципиально другим подходом к планированию является предоставление пользователям реальных обещаний и затем их выполнение. Вот одно обещание, которое легко произнести и легко выполнить: если вместе с вами процессором пользуются п пользователей, вам будет предоставлено 1/n мощности процессора. И в системе с одним пользователем и n запущенными процессорами каждому дос­танется 1/n циклов процессора.

Чтобы выполнить это обещание, система должна отслеживать распределение процессора между процессами с момента создания каждого процесса. Затем сис­тема рассчитывает количество ресурсов процессора, на которое процесс имеет пра­во, например время с момента создания, деленное на п. Теперь можно сосчитать отношение времени, предоставленного процессу, к времени, на которое он имеет право. Полученное значение 0,5 означает, что процессу выделили только полови­ну положенного, а 2,0 означает, что процессу досталось в два раза больше, чем по­ложено. Затем запускается процесс, у которого это отношение наименьшее, пока оно не станет больше, чем у его ближайшего соседа.

Лотерейное планирование

Хотя идея обещаний пользователям и их выполнения хороша, но ее трудно реали­зовать. Для более простой реализации предсказуемых результатов используется другой алгоритм, называемый лотерейным планированием .

В основе алгоритма лежит раздача процессам лотерейных билетов на доступ к различным ресурсам, в том числе и к процессору. Когда планировщику необходимо принять решение, выбирается случайным образом лотерейный билет, и его облада­тель получает доступ к ресурсу. Что касается доступа к процессору, «лотерея» может происходить 50 раз в секунду, и победитель получает 20 мс времени процессора.

Если перефразировать Джорджа Оруэлла: «Все процессы равны, но некоторые равнее других». Более важным процессам можно раздать дополнительные биле­ты, чтобы увеличить вероятность выигрыша. Если всего 100 билетов и 20 из них находятся у одного процесса, то ему достанется 20 % времени процессора. В отличие от приоритетного планировщика, в котором очень трудно оценить, что означает, ска­жем, приоритет 40, в лотерейном планировании все очевидно. Каждый процесс получит процент ресурсов, примерно равный проценту имеющихся у него билетов.

Лотерейное планирование характеризуется несколькими интересными свой­ствами. Например, если при создании процессу достается несколько билетов, то уже в следующей лотерее его шансы на выигрыш пропорциональны количеству билетов. Другими словами, лотерейное планирование обладает высокой отзывчи­востью.

Взаимодействующие процессы могут при необходимости обмениваться биле­тами. Так, если клиентский процесс посылает сообщение серверному процессу и затем блокируется, он может передать все свои билеты серверному процессу, что­бы увеличить шанс запуска сервера. Когда серверный процесс заканчивает рабо­ту, он может вернуть все билеты обратно. Действительно, если клиентов нет, то серверу билеты вовсе не нужны.

Лотерейное планирование позволяет решать задачи, которые не решить с по­мощью других алгоритмов. В качестве примера можно привести видеосервер, на котором несколько процессов передают своим клиентам потоки видеоинформации с различной частотой кадров. Предположим, что процессы используют частоты 10, 20 и 25 кадров в секунду. Предоставив процессам соответственно 10, 20 и 25 биле­тов, можно реализовать загрузку процессора в желаемой пропорции 10:20:25.

Справедливое планирование

До сих пор мы предполагали, что каждый процесс управляется независимо от того, кто его хозяин. Поэтому если пользователь 1 создаст 9 процессов, а пользо­ватель 2 — 1 процесс, то с использованием циклического планирования или в слу­чае равных приоритетов пользователю 1 достанется 90 % процессора, а пользова­телю 2 всего 10.

Чтобы избежать подобных ситуаций, некоторые системы обращают внимание на хозяина процесса перед планированием. В такой модели каждому пользователю достается некоторая доля процессора, и планировщик выбирает процесс в соот­ветствии с этим фактом. Если в нашем примере каждому из пользователей было обещано по 50 % процессора, то им достанется по 50 % процессора, независимо от количества процессов.

В качестве примера рассмотрим систему и двух пользователей, каждому из ко­торых отведено по 50 % процессора. У первого пользователя четыре процесса: А, В, С и D, у второго один процесс Е. Если используется циклическое планирование, цепочка процессов, удовлетворяющая всем требованиям, будет выглядеть следу­ющим образом:

AEBECEDEAEBECEDE...

С другой стороны, если первому пользователю положено вдвое больше ресур­сов, чем второму, мы получим

ABECDEABECDE...

Существует множество других решений, используемых в зависимости от кон­кретных представлений о справедливости.

Планирование в системах реального времени

В системах реального времени существенную роль играет время. Чаще всего одно или несколько внешних физических устройств генерируют входные сигналы, и компьютер должен адекватно на них реагировать в течение заданного промежут­ка времени. Например, компьютер в проигрывателе компакт-дисков получает биты от дисковода и должен за очень маленький промежуток времени конвертировать их в музыку. Если процесс конвертации будет слишком долгим, звук окажется искаженным. Подобные системы также используются для наблюдения за пациен­тами в палатах интенсивной терапии, в качестве автопилота самолета, для управления роботами на автоматизированном производстве.

Характеристики

Список файлов книги