Диспетчеризация задач с использованием динамических приоритетов

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

Рассмотрим, например, как реализован механизм динамических приоритетов в ОС Windows NT, которая не относится к операционным системам реального времени (ОСРВ). Каждый поток имеет базовый уровень приоритета, ко­торый лежит в диапазоне от двух уровней ниже базового приоритета процесса, его породившего, до двух уровней выше этого приоритета, как показано на рис. 1.4. Базовый приоритет процесса определяет, сколь сильно могут различаться при­оритеты потоков процесса и как они соотносятся с приоритетами потоков дру­гих процессов. Поток наследует этот базовый приоритет и может изменять его так, чтобы он стал немного больше или немного меньше. В результате получает­ся приоритет планирования, с которым поток и начинает исполняться. В процес­се исполнения потока его приоритет может отклоняться от базового.

На рис. 1.4 показан динамический приоритет потока, нижней границей кото­рого является базовый приоритет потока, а верхняя – зависит от вида работ, исполняемых потоком. Например, если поток обрабатывает пользовательский ввод, то диспетчер задач Windows NT поднимает его динамический приоритет; если же он выполняет вычисления, то диспетчер постепенно снижает его при­оритет до базового. Снижая приоритет одного процесса и поднимая приоритет другого, подсистемы могут управлять относительной приоритетностью потоков внутри процесса.

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

Существует группа очередей – по одной для каждого приоритета. Windows NT поддерживает 32 уровня приоритетов; потоки делятся на два класса: реального времени и переменного приоритета. Потоки реального времени, имеющие при­оритеты от 16 до 31, – это высокоприоритетные потоки, используемыми про­граммами с критическим временем выполнения, то есть требующие немедленно­го внимания системы (по терминологии Microsoft).

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

Большинство потоков в системе относятся к классу переменного приоритета с уровнями приоритета (номером очереди) от 1 до 15. Эти очереди используются потоками с переменным приоритетом (variable priority), так как диспетчер задач корректирует их приоритеты по мере выполнения задач для оптимизации откли­ка системы. Диспетчер приостанавливает исполнение текущего потока после того, как тот израсходует свой квант времени. При этом, если прерванный поток – это поток переменного приоритета, то диспетчер задач понижает его приоритет на единицу и перемещает в другую очередь. Таким образом, приоритет потока, вы­полняющего много вычислений, постепенно понижается (до значения его базо­вого приоритета). С другой стороны, диспетчер повышает приоритет потока по­сле освобождения задачи (потока) из состояния ожидания. Обычно добавка к приоритету потока определяется кодом исполнительной системы, находящимся вне ядра ОС, однако величина этой добавки зависит от типа события, которого ожидал заблокированный поток. Так, например, поток, ожидавший ввода очеред­ного байта с клавиатуры, получает бо2льшую добавку к значению своего приори­тета, чем процесс ввода/вывода, работавший с дисковым накопителем. Однако в любом случае значение приоритета не может достигнуть 16.

1.3. Память и отображения,
виртуальное адресное пространство

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

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

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

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

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

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

1) объем виртуального адресного пространства программы VVменьше объема физической памяти Vp;

2) VV= Vp;

3) VV> Vp.

Первая ситуация, при которой VV< Vp, ныне практически не встречается. Ситуация, когда VV= Vpособенно характерна была для недорогих вычислительных комплексов. Для этого случая имеется большое количество методов распределения оперативной памяти. В наше время ситуация VV> Vp– самая распространенная ситуация, и для нее имеется несколько методов рас­пределения памяти, отличающихся как сложностью, так и эффективностью.

1.4. Простое непрерывное распределение
и распределение с перекрытием

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

• область, занимаемая операционной системой;

• область, в которой размещается исполняемая задача;

• не занятая ничем (свободная) область памяти.

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

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

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

Схема простого непрерывного рас­пределения памяти характерна для MS-DOS.

Если есть необходимость создать программу, логическое (и виртуальное) адрес­ное пространство которой должно быть больше, чем свободная область памяти, или даже больше, чем весь возможный объем оперативной памяти, то исполь­зуетсяраспределение с перекрытием (так называемые оверлейные структуры). Этот метод распределения предполагает, что вся программа может быть разбита на части – сегменты. Каждая оверлейная программа имеет одну главную часть (main) и несколько сегментов (segment), причем в памяти машины одновремен­но могут находиться только ее главная часть и один или несколько не перекры­вающихся сегментов.

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

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