Глава 4 – Процессы и примитивы

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

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

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

В современной литературе независимые программы, которым соответствуют отдельные записи в очереди диспетчера, принято называть процессами. В системах IBM такая единица называется задачей. Правила захватов ресурсов процессами в различных ОС не совпадают!

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

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

При вызове с запросом на синхронизацию запись вызвавшей программы может замещаться в очереди диспетчера записью вызванной.

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

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

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

В ОС IBM и др. фирм принят несколько иной порядок работы, и информация о завершении процессов помещается в специально выделенный блок управления событиями (ECB - Event Control Block). В некоторых системах вызывающая программа может проверить окончание процесса с помощью макрокоманды, обычно называемой CHECK. В любой момент времени после выдачи, например, запроса на вывод эта команда позволяет определить, завершился ли процесс, запущенный по команде WRITE. Если процесс вывода еще не завершен, то программа может заняться другой работой, либо, при ее отсутствии, продолжать посылать команду CHECK, пока буфер не освободится.

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

Нетрудно видеть, что понятие POST-операции и БУС (ECB) фактически представляют собой реализацию P- и V-механизмов, упорядочивающих доступ к ресурсам. Но в отличие от P- и V-аппарата, данный аппарат синхронизации допускает прерывания в процессе работы и относится к одному из высоких уровней иерархической структуры ОС.

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

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

В реальных ОС процессы синхронизации содержат более сложные механизмы.

Глава 5 – Организация диспетчеров

5.1 Диспетчирование и состояние процессов

Диспетчер - это фундаментальный элемент ядра ОС. Однако в принципе обязанности диспетчера могут выполняться на более высоком уровне ОС, либо самими прикладными программами.

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

Процесс диспетчирования в основных чертах предусматривает выполнение следующих действий:

· сохранение информации о состоянии прерывающейся программы с целью обеспечения возможности последующего ее продолжения;

· выборку очередей программы для выполнения;

· определение способности выбранной программы к выполнению;

· запуск программы с соответствующего места;

В системах, имеющих отдельную программу - диспетчер, все указанные действия строго формализованы. Рабочая область программы получает статус управляющего блока, называемого записью активации (Activation Record), записью представления (Incarnation Record), блоком управления диспетчированием (Dispatch Control Block), блоком управления процессом (Process Control Block) и блоком управления задачей (Task Control Block). Содержимое блока зависит от конкретной ОС.

В качестве элементов блока обычно выступают:

· имя или идентификатор программы;

· адрес области сохранения;

· указатели на элементы системных таблиц, содержащих информацию о распределении устройств ввода-вывода;

· информация о выделенной программе области памяти;

· информация о состоянии процесса;

· значения приоритетов;

· указатели на системные таблицы, содержащие сведения о конкретных программах, формирующих данный процесс.

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

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

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

· завершение операций в/в;

· открытия семафора;

· окончания работы другого процесса (например, для использования информации, подготовленной этим процессом);

· завершения операций страничного обмена (в машинах со страничной организацией памяти) и др. системах:

ФИ - "финиш" - задача загружена в ОЗУ и уже выполнилась, либо еще не выполнялась;

ГТ - "готовность" - процесс готов к выполнению;

ВП - "выполнение" - процесс выполняется;

ОЖ - "ожидание" - процесс в стадии заблокирования.

5.2 Алгоритмы управления обработкой очередей

Алгоритм FIFO (First In - First Out - первый пришел - первый обслужен) - обслуживание в порядке поступления требований. Новые заявки помещают в конце очереди, а первыми обслуживаются заявки, находящиеся в ее начале. Чтобы определить очередь, достаточно знать месторасположение первой заявки и число заявок в очереди.

Алгоритм LIFO (Last In - First Out - последний пришел - первый обслужен) является как бы обратным алгоритму FIFO. Здесь последняя пришедшая заявка обслуживается первой. Данный алгоритм используют для организации так называемой магазинной памяти, что часто является весьма необходимым для некоторых элементов ОС.

Круговой циклический алгоритм RR (Round Robin). По этому алгоритму заявки обслуживаются некоторым устройством (например, процессором) в порядке их поступления, причем каждая обслуживается обычно в течение некоторого кванта времени (квант обслуживания). Если работа, соответствующая заявке, например программа в процессоре, была выполнена в течение этого кванта времени, то заявка покидает очередь. На обработку поступает следующая заявка из очереди. В противном случае заявка ставится в конец имеющейся очереди, где она будет ожидать дальнейшего обслуживания. Схематически работу алгоритма RR можно изобразить в виде, приведенном на рис. 5.2.1, а.

Алгоритм FB_N (Fareground - Background). Согласно этому алгоритму организуется N очередей (рис. 5.2.1, б). Поступившая на обработку заявка занимает конец первой очереди. Первая заявка из очереди с номером n >1 (n =1,..., N) поступает на обработку только тогда, когда нет очередей (пустые очереди) с меньшими номерами. При n<N заявка обрабатывается в течение кванта времени, и если за этот период она выполняется, то выводятся результаты (заявка покидает систему), далее на обработку поступает первая заявка из непустой очереди с низшим номером. В противном случае недообслуженная заявка (например, незавершенная программа) попадает в конец очереди с номером n +1. При поступлении новых заявок в систему возможны различные стратегии по отношению к текущей обрабатываемой заявке на уровне n.

Алгоритм Корбато. Это алгоритм (рис. 5.2.1, в) рассчитан на обработку многих очередей. Поступающая в систему программа попадает не в самую первую очередь (как в алгоритме FB_N), а в очередь с номером, зависящим от параметров входящей программы. В данном алгоритме существует определенное правило присвоения приоритетов для новых программ в системе. Уровень приоритета, присвоенный каждой новой программе, соответствует номеру очереди, в конец которой данная программа и будет помещена. Правило присвоения приоритетов основано на предположении, что время счета программы пропорционально ее объему.

Правило присвоения приоритетов новым программам можно записать в виде

где n - уровень приоритета, т.е. номер очереди, куда первоначально поступает программа; W_p - объем программы в словах; W_q - количество слов, которое может быть передано в ОЗУ из внешней памяти и в обратном направлении за квант времени обработки программы, равный q; [ x ] - целая часть x.

Дисциплина обслуживания в алгоритме Корбато построена следующим образом. Из всех имеющихся в наличии очередей каждый раз в период планирования (в конце кванта обслуживания и при завершении программы) выбирается на обслуживание первая непустая очередь с минимальным номером (уровнем приоритета), равным n (n =0,..., N). Каждая очередь, с любым уровнем приоритета, обслуживается по алгоритму FIFO. Попадая первоначально в очередь с номером n, программа получает квант времени обслуживания . Если к концу выделенного кванта данная программа не закончилась на уровне n, то она, как и в случае алгоритма FB_N "штрафуется" - переводится в конец очереди с номером n+ 1. На уровне n +1 ей представляется через некоторое время возможность "исправиться" - назначается новый квант обслуживания . Далее действия аналогичны. В крайнем случае, программа может быть "наказана" максимально и попасть на уровень N. Один из возможных способов определения максимального числа очередей

где W_pmax - наибольший допустимый размер программы. В алгоритме Корбато, как и в FB_N, возможны различные стратегии поведения системы по отношению к новым заявкам, поступающим в систему.

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

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

Обслуживание в порядке динамических приоритетов. Приоритет заявки зависит от времени пребывания ее в системе. Приоритет заявки может либо повышаться, либо, наоборот, понижаться.