Основы организации операционных систем

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

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

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

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

 

Рисунок 5.6 – Выполнение операции разблокирования процесса.

Использование термина "код  пользователя" не ограничивает

общности рисунка только пользовательскими процессами

Как в реальности может проистекать  операция разблокирования процесса, ожидающего ввода-вывода (см. рисунок 5.6)? При исполнении процессором некоторого процесса (на рисунке - процесс 1) возникает прерывание от устройства ввода-вывода, сигнализирующее об окончании операций на устройстве. Над выполняющимся процессом производится операция приостановка. Далее, операционная система разблокирует процесс, инициировавший запрос на ввод-вывод (на рисунке - процесс 2), и осуществляет запуск приостановленного или нового процесса, выбранного при выполнении планирования (на рисунке был выбран разблокированный процесс). Как видим, в результате обработки информации об окончании операции ввода-вывода возможна смена процесса, находящегося в состоянии исполнение.

Для корректного переключения процессора с одного процесса на другой необходимо сохранить контекст исполнявшегося процесса и восстановить контекст процесса, на который будет переключен процессор. Такая процедура сохранения/восстановления работоспособности процессов называется переключением контекста. Время, затраченное на переключение контекста, не используется вычислительной системой для совершения полезной работы и представляет собой накладные расходы, снижающие производительность системы. Оно меняется от машины к машине и обычно находится в диапазоне от 1 до 1000 микросекунд. Существенно сократить накладные расходы в современных операционных системах позволяет расширенная модель процессов, включающая в себя понятие threads of execution (нити исполнения или просто нити).

 

Выводы

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

 

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

Планирование задач может осуществляться на основании следующих алгоритмов:

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

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

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

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

Алгоритм Корбато. Этот алгоритм рассчитан на обработку многих очередей. Поступающая в систему программа попадает не в самую первую очередь (как в алгоритме 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, возможны различные стратегии поведения системы по отношению к новым заявкам, поступающим в систему.

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

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

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

 

Типы планировщиков в ОС

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

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

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

процесс был неактивен некоторое  время;

процесс имеет низкий приоритет;

процесс часто вызывает ошибки страниц (page fault);

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

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

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

 

Глава 6 (лекция 9)

Организация взаимодействия процессов

 

Жизнь процессов в  вычислительной системе напоминает жизнь соседей в коммунальной квартире. Постоянное ожидание в очереди к местам общего пользования (к процессору?) и постоянная борьба за другие ресурсы (кто опять занял все конфорки на плите?). Для нормального функционирования процессов операционная система старается максимально обособить их друг от друга. Каждый процесс имеет свое собственное адресное пространство (каждая семья должна жить в отдельной комнате), нарушение которого, как правило, приводит к аварийной остановке процесса (вызов милиции). Каждому процессу, по возможности, предоставляются свои собственные дополнительные ресурсы (у каждой семьи желателен свой собственный холодильник). Тем не менее, для решения некоторых задач (приготовление праздничного стола на всю квартиру) процессы могут объединять свои усилия. Настоящая глава описывает причины, по которым взаимодействуют процессы, способы их взаимодействия и возникающие при этом проблемы (попытайтесь отремонтировать общую квартиру так, чтобы не переругались все проживающие в ней семьи).