1. 5 Архитектура операционной системы

1. Классическая архитектура операционной системы ЭВМ. Ядро и вспомогательные модули ОС. Пользовательский и привилегированный режимы. Понятие системного вызова. Микроядерная архитектура ОС. Реализация системного вызова в микроядерной архитектуре. Достоинства и недостатки микроядерной архитектуры.

2. Понятия процессов и потоков в операционных системах ЭВМ. Многозадачность. Создание и завершение процессов. Состояния процесса. Понятие прерывания и его необходимость для поддержания многопоточности. Отличия между процессом и потоком. Способы реализации потоков.

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

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

5. Принципы построения аппаратуры ввода-вывода: категории устройств, контроллер устройства, доступ к управляющим регистрам контроллера и буферам данных. Понятие прямого доступа к памяти – DMA. Принципы программного обеспечения ввода-вывода: задачи программного обеспечения ввода-вывода, способы осуществления операций ввода-вывода, программные уровни ввода-вывода.

6. Основные понятия файловой системы в операционных системах: задачи, иерархия, именование, способы организации хранения файлов, атрибуты файлов, структура файловой системы (на примере FAT, NTFS или UFS), способы реализации файлов в различных файловых системах.

1.5 Архитектура операционной системы
Единой архитектуры операционных систем не существует, но существуют универсальные подходы к их структурированию. Ниже дано описание двух архитектур операционных систем, выполненное по книге Олифера В.Г., Олифера Н.А. «Сетевые операционные системы» [11].
1.5.1 Классическая архитектура
Наиболее общим подходом к структуризации операционной системы является разделение всех ее модулей на две группы:

ядро – модули, выполняющие основные функции операционной системы;
модули, выполняющие вспомогательные функции операционной системы.

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

В состав ядра входят функции, решающие внутрисистемные задачи организации вычислительного процесса, такие как переключение контекстов, загрузка/выгрузка станиц, обработка прерываний. Эти функции недоступны для приложений. Другой класс функций ядра служит для поддержки приложений, создавая для них так называемую прикладную программную среду. Приложения могут обращаться к ядру с запросами – системными вызовами – для выполнения тех или иных действий, например для открытия и чтения файла, вывода графической информации на дисплей, получения системного времени и т. д. Функции ядра, которые могут вызываться приложениями, образуют интерфейс прикладного программирования – API.

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

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

Вспомогательные модули операционной системы обычно подразделяются на следующие группы:

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

ля надежного управления ходом выполнения приложений операционная система должна иметь по отношению к приложениям определенные привилегии. Иначе некорректно работающее приложение может вмешаться в работу системы и, например, разрушить часть ее кодов. Обеспечить привилегии операционной системе невозможно без специальных средств аппаратной поддержки. Аппаратура компьютера должна поддерживать как минимум два режима работы — пользовательский режим (user mode) и привилегированный режим, который также называют режимом ядра (kernel mode). На рисунке 5 представлено такое разделение режимов.

Рисунок 5 – Архитектура операционной системы с ядром в привилегированном режиме

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

Уровней привилегий может быть несколько – 2, 3, 4 и т.д. Между количеством уровней привилегий, реализуемых аппаратно, и количеством уровней привилегий, поддерживаемых операционной системой, нет прямого соответствия. Так, на базе четырех уровней, обеспечиваемых процессорами компании Intel, операционная система OS/2 строит трехуровневую систему привилегий, а операционные системы Windows NT, UNIX и некоторые другие ограничиваются двухуровневой системой.

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

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

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

Рисунок 6 – Смена режимов при выполнении системного вызова к привилегированному ядру

Ядро может состоять из следующих слоев.

Средства аппаратной поддержки операционной системы. К операционной системе относят, естественно, не все аппаратные устройства компьютера, а только средства её аппаратной поддержки, то есть те, которые прямо участвуют в организации вычислительных процессов: средства поддержки привилегированного режима, систему прерываний, средства переключения контекстов процессов, средства защиты областей памяти и т.п.
Машинно-зависимые компоненты операционной системы. Этот слой образуют программные модули, в которых отражается специфика аппаратной платформы компьютера. В идеале этот слой полностью экранирует вышележащие слои ядра от особенностей аппаратуры.
Базовые механизмы ядра. Этот слой выполняет наиболее примитивные операции ядра, такие как программное переключение контекстов процессов, диспетчеризацию прерываний, перемещение страниц из памяти на диск и обратно и т. п.
Менеджеры ресурсов. Этот слой состоит из мощных функциональных модулей, реализующих стратегические задачи по управлению основными ресурсами вычислительной системы. Обычно на данном слое работают менеджеры (называемые также диспетчерами) процессов, ввода-вывода, файловой системы и оперативной памяти.
Интерфейс системных вызовов. Этот слой является самым верхним слоем ядра и взаимодействует непосредственно с приложениями и системными утилитами, образуя прикладной программный интерфейс операционной системы. Функции API, обслуживающие системные вызовы, предоставляют доступ к ресурсам системы в удобной и компактной форме, без указания деталей их физического расположения.

Приведенное разбиение ядра операционной системы на слои является достаточно условным. В реальной системе количество слоев и распределение функций между ними может быть и иным.

Архитектура операционной системы, основанная на привилегированном ядре и приложениях пользовательского режима, стала, по существу, классической. Ее используют многие популярные операционные системы, в том числе многочисленные версии UNIX, IBM OS/390, OS/2, и с определенными модификациями – Windows NT.

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

Рисунок 7 – Перенос основного объема функций ядра в пользовательское пространство

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

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

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

Рисунок 8 – Реализация системного вызова в микроядерной архитектуре

Достоинства микроядерной архитектуры:

1 Переносимость. Высокая степень переносимости обусловлена тем, что весь машинно-зависимый код изолирован в микроядре, поэтому для переноса системы на новый процессор требуется меньше изменений и все они логически сгруппированы вместе.

2 Расширяемость присуща микроядерной операционной системе в очень высокой степени.

3 Конфигурируемость. При микроядерном подходе конфигурируемость операционной системы не вызывает никаких проблем и не требует особых мер – достаточно изменить файл с настройками начальной конфигурации системы или же остановить не нужные больше серверы в ходе работы обычными для остановки приложений средствами.

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

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

К основному и очень существенному недостатку относится низкая производительность операционной системы микроядерного типа. При классической организации операционной системы выполнение системного вызова сопровождается двумя переключениями режимов, а при микроядерной организации – четырьмя (Рисунок 9).

Рисунок 9 – Смена режимов при выполнении системного вызова: в классической архитектуре (а); в микроядерной (б)

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

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

2.1 Процессы
В многозадачной системе процессор переключается между программами, предоставляя каждой от десятков до сотен миллисекунд. В каждый конкретный момент времени процессор работает только с одной программой, создавая иллюзию параллельной работы, т.е. псевдопараллелизм [14]. Настоящая параллельная работа присутствует в многопроцессорных и многоядерных системах, таких как Core 2 Duo. Следить за работой параллельно идущих процессов достаточно трудно, поэтому со временем разработчики операционных систем создали концептуальную модель последовательных процессов, упрощающую эту работу.

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

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

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

Существует четыре основных события, приводящие к созданию процессов:

инициализация системы;
выполнение изданного работающим процессом системного запроса на создание процесса;
запрос пользователя на создание процесса;
инициирование пакетного задания.

Программист для создания процесса в UNIX должен вызвать комбинацию из двух функций fork и execve, а в Windows – CreateProcess [12].

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

обычный выход (преднамеренно);
выход по ошибке (преднамеренно);
выход по неисправимой ошибке (непреднамеренно);
уничтожение другим процессом (непреднамеренно).

Для завершения процесса программист в UNIX должен вызвать системный запрос kill, соответствующая функция в Win32 API – TerminateProcess.

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

а

а

Рисунок 10 – 4 программы в многозадачном режиме (а); модель 4 независимых последовательных процессов (б); в каждый момент времени активна только одна программа (в)

Процесс может находиться в 3 возможных состояниях (Рисунок 11):

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

Рисунок 11 – Процесс может находиться в рабочем, готовом и заблокированном состоянии

Переходы между состояниями:

1) процесс блокируется, ожидая входных данных;

2) планировщик выбирает другой процесс;

3) планировщик выбирает этот процесс;

4) доступны входные данные.

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

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

Управление процессом

Управление памятью

Управление файлами

Регистры

Счетчик команд

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

Указатель стека

Состояние процесса

Приоритет

Параметры планирования

Идентификатор процесса

Родительский процесс

Группа процесса

Сигналы
Время начала процесса

Использованное процессорное время

Процессорное время дочернего процесса

Указатель на текстовый сегмент
Указатель на сегмент данных

Указатель на сегмент стека

Корневой каталог

Рабочий каталог

Дескрипторы файла

Идентификатор пользователя

Идентификатор группы

Большое значение для создания иллюзии многопоточности на компьютерах с одним процессором имеет значение понятия прерывания. Прерывание (англ. interrupt) – сигнал, сообщающий процессору о совершении какого-либо асинхронного события [14]. При этом выполнение текущей последовательности команд приостанавливается, и управление передаётся обработчику прерывания, который выполняет работу по обработке события и возвращает управление в прерванный код.

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

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

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

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

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

У каждого потока свой собственный стек. Стек (англ. stack – стопка) – структура данных с методом доступа к элементам LIFO (англ. Last In – First Out, «последним пришел – первым вышел») [14].

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

Элементы процесса

Элементы потока

Адресное пространство

Глобальные переменные

Открытые файлы

Дочерние процессы

Необработанные аварийные сигналы

Сигналы и их обработчики

Информация об использовании ресурсов

Счетчик команд

Регистры

Стек
Состояние

Преимущества использования нескольких потоков перед несколькими процессами:

возможность совместного использования параллельными объектами адресного пространства и всех содержащихся в нём данных;
создание и уничтожение потоков происходит в примерно в 100 раз быстрее, чем для процессов;
увеличивается производительность.

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

Рисунок 12 – Пакет потоков в пространстве пользователя (а); пакет потоков, управляемый ядром (б)

Однако, у первого способа есть серьёзные недостатки по отношению со вторым, например проблема добровольной отдачи процессора одним из потоков, или блокирование одного потока, что приводит к блокированию всего процесса. Поэтому на настоящий момент в большинстве известных ОС потоки реализуются в ядре или используется смешанное использование обоих способов.
2.3 Межпроцессное взаимодействие
Процессам часто бывает необходимо взаимодействовать между собой. Поэтому необходимо правильно организованное взаимодействие между процессами, по возможности не использующее прерываний. Проблема межпроцессного взаимодействия разбивается на 3 пункта [14]:

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

Эти же пункты, не считая первого, относятся и к потокам.

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

Часть программы, в которой есть обращение к совместно используемым данным, называется критической областью или секцией. Несмотря на то, что это требование исключает состязание, его недостаточно для правильной совместной работы параллельных процессов и эффективного использования общих данных. Для этого необходимо выполнение 4 условий:

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

Рисунок 13 – Взаимное исключение с использованием критических областей

В абстрактном виде требуемое поведение процессов представлено на рисунке 13. Процесс А попадает в критическую область в момент времени T₁. Чуть позже, в момент времени T₂, процесс Б пытается попасть в критическую область, но ему это не удается, поскольку в критической области уже находится процесс А, а два процесса не должны одновременно находиться в критических областях. Поэтому процесс Б временно приостанавливается, до наступления момента времени T₃, когда процесс А выходит из критической области. В момент времени T₄ процесс Б также покидает критическую область, и происходит возвращение в исходное состояние, когда ни одного процесса в критической области не было.
2.3.1 Взаимное исключение с активным ожиданием
Здесь рассмотрены различные способы реализации взаимного исключения с целью избежать вмешательства в критическую область одного процесса при нахождении там другого и связанных с этим проблем.

1 Запрещение прерывания

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

2 Переменные блокировки

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

3 Строгое чередование

Третий метод проиллюстрирован на листинге 1.

//процесс 0

while (TRUE){

while (turn!=0) ;

critical_region();

turn=1;

noncritical_region();

}

//процесс 1

while (TRUE){

while (turn!=1) ;

critical_region();

turn=0;

noncritical_region();

}

Листинг 1 – Решение проблемы критической области методом строгого чередования

Целая переменная turn, изначально равная 0, отслеживает, чья очередь входить в критическую область. Здесь для того, чтобы 0-ой процесс вошел в область, turn должна быть равна 0, а 1-ой – turn равна 1.

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

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

4 Алгоритм Петерсона

В 1981 году датский математик Петерсон разработал простой алгоритм взаимного исключения, представленный на листинге 2 [17].

#define FALSE 0

#define TRUE 1

#define N 2 //количество процессов

int turn; //чья сейчас очередь

int interested[N]; //все переменные изначально равны 0

void enter_region(int process) //процесс 0 или 1

{

int other; //номер второго процесса

other=1-process; //противоположный процесс

interested[process]=TRUE; //индикатор интереса

turn=process; //установка флага

while (turn==process && interested[other]==TRUE);

}

void leav_region(int process)

{

interested[process]=FALSE; //индикатор выхода из критической области

}

Листинг 2 – Решение Петерсона для взаимного исключения

Перед тем, как войти в критическую область процесс вызывает процедуру enter_region со своим номером в качестве параметра. После выхода из критической области процесс вызывает leav_region.

Исходно оба процесса находятся вне критических областей. Процесс 0 вызывает enter_region, задает элементы массива и устанавливает переменную turn равной 0. Поскольку процесс 1 не заинтересован в попадании в критическую область, процедура возвращается. Теперь, если процесс 1 вызовет enter_region, ему придется подождать, пока interested[0] примет значение FALSE, а это произойдет только в тот момент, когда процесс 0 вызовет процедуру leave_region, чтобы покинуть критическую область.

Если оба процесса вызвали enter_region практически одновременно, то оба сохранят свои номера в turn. Сохранится номер того процесса, который был вторым, а предыдущий номер будет утерян. Предположим, что вторым был процесс 1, так что значение turn равно 1. Когда оба процесса дойдут до оператора while, процесс 0 войдет в критическую область, а процесс 1 останется в цикле и будет ждать, пока процесс 0 выйдет из критической области.

5 Команда TSL

Это решение требует участия аппаратного обеспечения. Многие компьютеры имеют команду:

TSL RX, LOCK

(Test and Set Lock – проверить и заблокировать), которая действует следующим образом. В регистр RX считывается содержимое слова памяти LOCK, а в ячейке памяти LOCK сохраняется некоторое ненулевое значение. Операция считывания слова неделима. Процессор, выполняющий команду TSL, блокирует шину памяти, чтобы остальные процессоры, если они есть, не могли обратиться к памяти.

На листинге 3 представлены функции для входа и выхода из критической области, выполненные в синтаксисе Ассемблера.
enter_region:

TSL REGISTER,LOCK ; значение LOCK копируется в регистр, значение

переменной устанавливается равной 1

GMP REGISTER,#0 ; старое значение LOCK сравнивается с нулем

JNE enter_region ; если оно ненулевое, значит блокировка уже

была установлена, поэтому цикл завершается

RET

leave_region:

MOVE LOCK,#0 ; сохранение 0 в переменной LOCK

RET

Листинг 3 – Вход и выход из критической области с помощью команды TSL
Прежде чем попасть в критическую область, процесс вызывает процедуру enter_region, которая выполняет активное ожидание вплоть до снятия блокировки, затем она устанавливает блокировку и возвращается. По выходе из критической области процесс вызывает процедуру leave_region, помещающую 0 в переменную LOCK. Как и во всех остальных решениях проблемы критической области, для корректной работы процесс должен вызывать эти процедуры своевременно, в противном случае взаимное исключение не удастся.
2.3.2 Примитивы межпроцессного взаимодействия
Решение Петерсона и с помощью команды TSL корректны, но у них один и тот же недостаток – использование активного ожидания. Т.е. процесс входит в цикл, ожидая возможности войти в критическую область.

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

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

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

Это решение кажется достаточно простым, но оно приводит к состояниям состязания. Нужна переменная count для отслеживания количества элементов в буфере. Если максимальное число элементов, хранящихся в буфере, равно N, программа производителя должна проверить, не равно ли N значение count прежде, чем поместить в буфер следующую порцию данных. Если значение count равно N, то производитель уходит в состояние ожидания; в противном случае производитель помещает данные в буфер и увеличивает значение count.

Код программы потребителя прост: сначала проверить, не равно ли значение count нулю. Если равно, то уйти в состояние ожидания; иначе забрать порцию данных из буфера и уменьшить значение count. Каждый из процессов также должен проверять, не следует ли активизировать другой процесс, и в случае необходимости проделывать это. Программы обоих процессов представлены в листинге 4.

#define N 100

int count = 0;

void producer()

{

int item;

while (TRUE) {

item=produce_item(); //сформировать следующий элемент

if (count==N) sleep(); //буфер полон – состояние ожидания

insert_item(item); //поместить элемент в буфер

count++;

if (count==1) wakeup(consumer);

}

}
void consumer()

{

int item;

while (TRUE) {

if (count==0) sleep(); //буфер пуст – состояние ожидания

item=remove_item(item); //забрать элемент из буфера

count--;

if (count==N-1) wakeup(producer);

}

Листинг 4 – Проблема производителя и потребителя с состоянием соревнования

Для описания на языке С системных вызовов sleep и wakeup они были представлены в виде вызовов библиотечных процедур. В стандартной библиотеке С их нет, но они будут доступны в любой системе, в которой присутствуют такие системные вызовы. Процедуры insert_item и remove_item помещают элементы в буфер и извлекают их оттуда.

Возникновение состояния состязания возможно, поскольку доступ к переменной count не ограничен. Может возникнуть следующая ситуация: буфер пуст, и потребитель только что считал значение переменной count, чтобы проверить, не равно ли оно нулю. В этот момент планировщик передал управление производителю, производитель поместил элемент в буфер и увеличил значение count, проверив, что теперь оно стало равно 1. Зная, что перед этим оно было равно 0 и потребитель находился в состоянии ожидания, производитель активизирует его с помощью вызова wakeup.

Но потребитель не был в состоянии ожидания, так что сигнал активизации пропал впустую. Когда управление перейдет к потребителю, он вернется к считанному когда-то значению count, обнаружит, что оно равно 0, и уйдет в состояние ожидания. Рано или поздно производитель наполнит буфер и также уйдет в состояние ожидания. Оба процесса так и останутся в этом состоянии.

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

Несмотря на то, что введение бита ожидания запуска спасло положение в этом примере, легко сконструировать ситуацию с несколькими процессами, в которой одного бита будет недостаточно. Можно добавить еще один бит, или 8, или 32, но это не решит проблему.

В 1965 году Дейкстра [16] предложил использовать семафор – переменную для подсчета сигналов запуска. Семафор – объект синхронизации, который может регулировать доступ к некоторому ресурсу. Также было предложено использовать вместо sleep и wakeup две операции down и up. Их отличие в следующем: если значение семафора больше нуля, то down просто уменьшает его на 1 и возвращает управление процессу, в противном случае процесс переводится в режим ожидания. Все операции проверки значения семафора, его изменения и перевода процесса в состояние ожидания выполняются как единое и неделимое элементарное действие, т.е. в это время ни один процесс не может получить доступ к этому семафору. Операция up увеличивает значение семафора. Если с этим семафором связаны один или несколько ожидающих процессов, которые не могут завершить более раннюю операцию down, один из них выбирается системой и разблокируется. Проблема производителя и потребителя легко решается с помощью семафоров.

Иногда используется упрощенная версия семафора, называемая мьютексом. Мьютекс – переменная, которая может находиться в одном из двух состояний: блокированном или неблокированном. Поэтому для описания мьютекса требуется всего один бит. Мьютекс может охранять неразделенный ресурс, к которому в каждый момент времени допускается только один поток, а семафор может охранять ресурс, с которым может одновременно работать не более N потоков.

Недостатком семафоров является то, что одна маленькая ошибка при их реализации программистом приводит к остановке всей операционной системы. Чтобы упростить написание программ в 1974 году было предложено использовать примитив синхронизации более высокого уровня, называемый монитором. Монитор – набор процедур, переменных и других структур данных, объединенных в особый модуль или пакет. Процессы могут вызывать процедуры монитора, но у процедур объявленных вне монитора, нет прямого доступа к внутренним структурам данных монитора. При обращении к монитору в любой момент времени активным может быть только один процесс. Монитор похож по своей структуре на класс в C++. Не все языки программирования поддерживают мониторы и не во всех операционных системах есть их встроенная реализация. Так в Windows их нет.

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

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

Литература по операционным системам содержит множество интересных проблем, которые широко обсуждались и анализировались с применением различных методов синхронизации. Часть из них описана в работе [14].

3.1 Основы управления памятью