Лекция: Алгоритмы, основанные на квантовании

В основе многих вытесняющих алгоритмов планирования лежит концепция квантования. В соответствии с этой концепцией каждому потоку поочередно для выполнения предоставляется ограниченный непрерывный период процессорно­го времени — квант.

Смена активного потока происходит, если:

• поток завершился и покинул систему;

• произошла ошибка;

• поток перешел в состояние ожидания;

• исчерпан квант процессорного времени, отведенный данному потоку.

Поток, который исчерпал свой квант, переводится в состояние готовности и ожи­дает, когда ему будет предоставлен новый квант процессорного времени, а на вы­полнение в соответствии с определенным правилом выбирается новый поток из очереди готовых. Граф состояний потока, изображенный на рис.4, соответству­ет алгоритму планирования, основанному на квантовании.

Рис. 4.Граф состояний потока в системе с квантованием.

Кванты, выделяемые потокам, могут быть одинаковыми для всех потоков или различными. Рассмотрим, например, случай, когда всем потокам предоставляют­ся кванты одинаковой длины q (рис. 5). Если в системе имеется n потоков, то время, которое поток проводит в ожидании следующего кванта, можно грубо оце­нить как q(n-l). Чем больше потоков в системе, тем больше время ожидания, тем меньше возможности вести одновременную интерактивную работу нескольким пользователям. Но если величина кванта выбрана очень небольшой, то значение произведения q(n-l) все равно будет достаточно мало для того, чтобы пользова­тель не ощущал дискомфорта от присутствия в системе других пользователей. Типичное значение кванта в системах разделения времени составляет десятки миллисекунд.

Рис. 5.Иллюстрация расчета времени ожидания в очереди.

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

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

Потоки получают для выполнения квант времени, но некоторые из них ис­пользуют его не полностью, например из-за необходимости выполнить ввод или вывод данных. В результате возникает ситуация, когда потоки с интен­сивными обращениями к вводу-выводу используют только небольшую часть выделенного им процессорного времени. Алгоритм планирования может ис­править эту «несправедливость». В качестве компенсации за неиспользован­ные полностью кванты потоки получают привилегии при последующем об­служивании. Для этого планировщик создает две очереди готовых потоков (рис. 6). Очередь 1 образована потоками, которые пришли в состояние го­товности в результате исчерпания кванта времени, а очередь 2 — потоками, у которых завершилась операция ввода-вывода. При выборе потока для выпол­нения, прежде всего просматривается вторая очередь, и только если она пуста, квант выделяется потоку из первой очереди.

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

В алгоритмах, основанных на квантовании, какую бы цель они не преследовали (предпоч­тение коротких или длинных задач, компенсация недоиспользованного кванта или мини­мизация накладных расходов, связанных с переключениями), не используется никакой предварительной информации о задачах. При поступлении задачи на обработку ОС не имеет никаких сведений о том, является ли она короткой или длинной, насколько интен­сивными будут ее запросы к устройствам ввода-вывода, насколько важно ее быстрое выполнение и т. д. Дифференциация обслуживания при квантовании базируется на «исто­рии существования» потока в системе.

------------------------------------------------------------------------------------------------------------------

Рис. 6. Квантование с предпочтением потоков, интенсивно обращающихся

к вводу-выводу.

Алгоритмы планирования, основанные на приоритетах

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

Приоритет может выражаться целым или дробным, положительным или отрица­тельным значением. В некоторых ОС принято, что приоритет потока тем выше, чем больше (в арифметическом смысле) число, обозначающее приоритет. В дру­гих системах, наоборот, чем меньше число, тем выше приоритет.

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

Во многих ОС предусматривается возможность изменения приоритетов в тече­ние жизни потока.

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

От того, какие приоритеты назначены потокам, существенно зависит эффектив­ность работы всей вычислительной системы. В современных ОС во избежание разбалансировки системы, которая может возникнуть при неправильном назна­чении приоритетов, возможности пользователей влиять на приоритеты процес­сов и потоков стараются ограничивать. При этом обычные пользователи, как правило, не имеют права повышать приоритеты своим потокам, это разрешено делать (да и то в определенных пределах) только администраторам. В большин­стве же случаев ОС присваивает приоритеты потокам по умолчанию. В качестве примера рассмотрим схему назначения приоритетов потокам, приня­тую в операционной системе Windows NT (рис. 7). В системе определено 32 уровня приоритетов и два класса потоков — потоки реального времени и потоки с переменными приоритетами. Диапазон от 1 до 15 включительно отведен для потоков с переменными приоритетами, а от 16 до 31 — для более критичных ко времени потоков реального времени (приоритет 0 зарезервирован для систем­ных целей).

Рис. 7.Схема назначения приоритетов в Windows NT

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

Относительные и абсолютные приоритеты

Существуют две разновидности приоритетного планирования: обслуживание с относительными приоритетами и обслуживание с абсолютными приоритетами.

В обоих случаях выбор потока на выполнение из очереди готовых осуществляет­ся одинаково: выбирается поток, имеющий наивысший приоритет. Однако про­блема определения момента смены активного потока решается по-разному.

• В сис­темах с относительными приоритетами активный поток выполняется до тех пор, пока он сам не покинет процессор, перейдя в состояние ожидания (или же про­изойдет ошибка, или поток завершится). На рис. 8, а показан граф состояний потока в системе с относительными приоритетами.
• В системах с абсолютными приоритетами выполнение активного потока преры­вается кроме указанных выше причин, еще при одном условии: если в очереди готовых потоков появился поток, приоритет которого выше приоритета активно­го потока. В этом случае прерванный поток переходит в состояние готовности (рис. 8, б).

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

Рис. 8.Графы состояний потоков в системах с относительными и абсолютными приоритетами.

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

Смешанные алгоритмы планирования

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

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

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

Жесткие и мягкие системы

При разработке алгоритмов планирования для систем реального времени необ­ходимо учитывать, какие последствия в этих системах возникают при несоблю­дении временных ограничений. Если эти последствия катастрофичны, как, на­пример, для системы управления полетами или атомной электростанцией, то операционная система реального времени, на основе которой строится управле­ние объектом, называется жесткой (hard). Если же последствия нарушения вре­менных ограничений не столь серьезны, то есть сравнимы с той пользой, кото­рую приносит система управления объектом, то система является мягкой (soft) системой реального времени. Примером мягкой системы реального времени яв­ляется система резервирования билетов. Если из-за временных нарушений опе­ратору не удается зарезервировать билет, это не очень страшно — можно просто послать запрос на резервирование заново.

В жестких системах реального времени время завершения выполнения каждой. из критических задач должно быть гарантировано для всех возможных сценари­ев работы системы. Такие гарантии могут быть даны либо в результате исчерпы­вающего тестирования всех возможных сценариев поведения управляемого объ­екта и управляющих программ, либо в результате построения статического расписания, либо в результате выбора математически обоснованного динамиче­ского алгоритма планирования. При построении расписания надо иметь в виду, что для некоторых наборов задач в принципе невозможно найти расписания, при котором бы удовлетворялись заданные временные характеристики. С целью определения возможности существования расписания могут быть использованы различные критерии. Например, в качестве простейшего критерия может слу­жить условие, что разность между предельным сроком выполнения задачи (по­сле появления запроса на ее выполнение) и временем ее вычисления (при усло­вии непрерывного выполнения) всегда должна быть положительной. Очевидно, что такой критерий является необходимым, но недостаточным. Точные крите­рии, гарантирующие наличие расписания, являются очень сложными в вычисли­тельном отношении.

В мягких системах реального времени предполагается, что заданные временные ограничения могут иногда нарушаться, поэтому здесь обычно применяются ме­нее затратные способы планирования.

Периодические и спорадические задачи

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

Планирование зависимых и независимых задач.

При выборе алгоритма планирования следует учитывать данные о возможной зависимости задач. Эта зависимость может выступать, например, в виде ограни­чений на последовательность выполнения задач или их синхронизации, вызван­ной взаимными исключениями (запрете выполнения некоторых задач в течение определенных периодов времени). С практической точки зрения алгоритмы планирования зависимых задач более важны, чем алгоритмы планирования независимых задач. При наличии дешевых микроконтроллеров нет смысла организовывать мультипрограммное выполнение большого количества независимых задач на одном компьютере, так как при этом значительно возрастает сложность программного обеспечения. Обычно одновре­менно выполняющиеся задачи должны обмениваться информацией и получать доступ к общим данным для достижения общей цели системы, то есть являются зависимыми задачами. Проблема планирования зависимых задач очень сложна, нахождение ее оптималь­ного решения требует больших вычислительных ресурсов, сравнимых с теми, которые требуются для собственно выполнения задач управления.

Динамические приоритеты

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