Реферат: М. В. Ломоносова Факультет вычислительной математики и кибернетики Н. В. Вдовикина, А. В. Казунин, И. В. Машечкин, А. Н. Терехин Системное программное обеспечение: взаимодействие процессов учебно-методическое пособие

Московский Государственный Университет им. М.В. Ломоносова

Факультет вычислительной математики и кибернетики

Н.В.Вдовикина, А.В.Казунин, И.В.Машечкин, А.Н.Терехин

Системное программное обеспечение: взаимодействие процессов.


(учебно-методическое пособие)


Москва

2002

УДК 681.3.06

ББК 32.973-018.2

C40


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

Авторы выражают благодарность Е.М.Шляховой, Ю.О.Нестеровой, А.Н.Розинкину, О.И.Вдовикину за помощь в подготовке пособия.

УДК 681.3.06

ББК 32.973-018.2


Рецензенты:

чл.-корр. РАН Л.Н.Королев

доцент Е.А.Кузьменкова


Вдовикина Н.В., Казунин А.В., Машечкин И.В., Терехин А.Н.


С40 Системное программное обеспечение: взаимодействие процессов: учебно-методическое пособие.


Издательский отдел факультета ВМиК МГУ

(лицензия ИД № 05899 от 24.09.2001), 2002, - 183 c.


Печатается по решению Редакционно-издательского Совета факультета вычислительной математики и кибернетики МГУ им. М.В. Ломоносова


ISBN 5-89407-139-9

© Издательский отдел факультета вычислительной математики и кибернетики МГУ им. М.В. Ломоносова, 2002


ОГЛАВЛЕНИЕ

Часть I. Теоретические основы. 5

1ВВЕДЕНИЕ. 5

2Понятие процесса. 6

2.1Некоторые типы процессов. 6

2.1.1 «Полновесные процессы» 6

2.1.2«Легковесные процессы» 7

^ 2.2Жизненный цикл процесса. 8

3Синхронизация параллельных процессов. 12

3.1Способы реализации взаимного исключения. 16

3.1.1Запрещение прерываний и специальные инструкции. 16

3.1.2Алгоритм Петерсона. 17

3.1.3Активное ожидание. 18

3.1.4Семафоры. 19

3.1.5Мониторы. 20

3.1.6Обмен сообщениями. 22

^ 3.2Классические задачи синхронизации процессов. 25

3.2.1«Обедающие философы» 25

3.2.2Задача «читателей и писателей» 28

3.2.3Задача о «спящем парикмахере» 31

Часть II. реализация процессов. 34

4Реализация процессов в ОС UNIX 34

^ 4.1Понятие процесса в UNIX. 34

4.1.1Контекст процесса. 34

4.1.2Тело процесса. 35

4.1.3Аппаратный контекст. 36

4.1.4Системный контекст. 37

^ 4.2Аппарат системных вызов в OC UNIX. 38

4.3Порождение новых процессов. 40

4.4Механизм замены тела процесса. 45

4.5Завершение процесса. 50

4.6Жизненный цикл процесса в ОС UNIX. 55

4.7Начальная загрузка. Формирование О и 1 процессов. 56

^ 4.8Планирование процессов в ОС UNIX. 58

4.9Принципы организация свопинга. 60

Часть III. реализация взаимодействия процессов. 62

5Элементарные средства межпроцессного взаимодействия. 65

5.1Сигналы. 65

5.2Надежные сигналы. 73

5.3Программные каналы 79

5.4Именованные каналы (FIFO) 87

^ 5.5Нелокальные переходы. 90

5.6Трассировка процессов. 93

6Средства межпроцессного взаимодействия System V. 99

6.1Организация доступа и именования в разделяемых ресурсах. 99

6.1.1Именование разделяемых объектов. 99

6.1.2Генерация ключей: функция ftok(). 100

6.1.3Общие принципы работы с разделяемыми ресурсами. 101

^ 6.2Очередь сообщений. 103

6.2.1Доступ к очереди сообщений. 104

6.2.2Отправка сообщения. 104

6.2.3Получение сообщения. 105

6.2.4Управление очередью сообщений. 106

^ 6.3Разделяемая память 112

6.3.1Создание общей памяти. 113

6.3.2Доступ к разделяемой памяти. 113

6.3.3Открепление разделяемой памяти. 114

6.3.4Управление разделяемой памятью. 115

6.4Семафоры. 116

6.4.1Доступ к семафору 117

6.4.2Операции над семафором 118

6.4.3Управление массивом семафоров. 120

7Взаимодействие процессов в сети. 126

^ 7.1Механизм сокетов. 126

7.1.1Типы сокетов. Коммуникационный домен. 127

7.1.2Создание и конфигурирование сокета. 128

7.1.3Предварительное установление соединения. 131

7.1.4Прием и передача данных. 133

7.1.5Завершение работы с сокетом. 135

7.1.6Резюме: общая схема работы с сокетами. 136

^ 7.2Среда параллельного программирования MPI 144

7.2.1Краткий обзор параллельных архитектур. 145

7.2.2Модель программирования MPI. 150

7.2.3 Функции общего назначения. Общая структура программы. 151

7.2.4Прием и передача данных. Общие замечания. 156

7.2.5Коммуникации «точка-точка». Блокирующий режим. 158

7.2.6Коммуникации «точка-точка». Неблокирующий режим. 164

7.2.7Коллективные коммуникации. 171

8Алфавитный указатель упоминаемых библиотечных функций и системных вызовов. 181

9Список литературы 183



^ Часть I. Теоретические основы. 1ВВЕДЕНИЕ.
Вычислительная система (ВС) есть совокупность аппаратных и программных средств, функционирующих как единое целое и предназначенных для решения задач определенного класса. Любая вычислительная система обладает некоторым набором ресурсов. Эти ресурсы включают в себя как реально существующие физические ресурсы (устройства) с их реальными характеристиками, так и устройства, эксплутационные характеристики которых полностью или частично реализованы программным образом – виртуальные (логические) ресурсы (устройства). Под операционной системой (ОС) понимают комплекс программ осуществляющий управление, распределение и контроль за использованием ресурсов вычислительной системы.

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

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

обеспечение жизненного цикла процессов (порождение, выполнение и уничтожение процессов);

распределение ресурсов ВС;

синхронизацию процессов;

организацию межпроцессного взаимодействия.
^ 2Понятие процесса.
Нетрудно найти целый ряд “синонимов” понятия типа “процесс” – процесс, нить, задача, задание или программа, причем в различных ОС могут присутствовать только часть понятий из этого набора, и их интерпретация во многом будет зависеть от конкретной вычислительной среды, где они используются. Таким образом, разные операционные системы оперируют с разными понятиями относительно базовой сущности, с которой работает ОС . Более того эти понятия могут переплетаться, т.е. задача может состоять из нескольких процессов, а процесс имеет многонитевую структуру.

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

Одной из целей создания и поддержания такой структуры является возможность продолжения корректной работы процесса после приостановки его функционирования на процессоре. В момент выделения следующему процессу вычислительных ресурсов происходит так называемое переключение контекста, в результате которого происходит сохранение контекста текущего процесса и передача управления новому.
^ 2.1Некоторые типы процессов. 2.1.1 «Полновесные процессы»
Существует понятие «полновесные процессы» - это процессы, выполняющиеся внутри защищенных участков памяти операционной системы, то есть имеющие собственные виртуальные адресные пространства для статических и динамических данных. Для «полновесных процессов» можно сказать, что операционная система поддерживает их обособленность: у каждого процесса имеется свое виртуальное адресное пространство, каждому процессу назначаются свои ресурсы - файлы, окна, семафоры и т.д. Такая обособленность нужна для того, чтобы защитить один процесс от другого, поскольку они, совместно используя все ресурсы ВС, конкурируют с друг другом. В общем случае процессы принадлежат разным пользователям, разделяющим один компьютер, и ОС берет на себя все функции, связанные с распределением ресурсов между конкурирующими процессами. В операционных системах управление такими процессами тесно связанно с управлением и защитой памяти, поэтому переключение процессора с выполнения одного процесса на выполнение другого является достаточно дорогой операцией по времени.
^ 2.1.2«Легковесные процессы»
Наряду с «полновесными процессами» существуют и «легковесные процессы», они же нити, которые в той или иной степени присутствуют в различных операционных системах. При мультипрограммировании повышается пропускная способность системы, но отдельный процесс никогда не может быть выполнен быстрее, чем если бы он выполнялся в однопрограммном режиме. Однако задача, решаемая в рамках одного процесса, может обладать внутренним параллелизмом, который позволяет ускорить ее выполнение. Например, в ходе выполнения задачи происходит обращение к внешнему устройству, и на время этой операции можно не блокировать полностью выполнение процесса, а продолжить вычисления по другой "ветви" процесса. Для этих целей современные ОС предлагают использовать механизм многонитевой обработки (multithreading). При этом вводится новое понятие "нить" (thread). Нити, относящиеся к одному процессу, не настолько изолированы друг от друга, как процессы в традиционной многозадачной системе, между ними легко организовать тесное взаимодействие. Нити, или «легковесные процессы», во многих отношениях схожи с процессами. Каждая нить выполняется строго последовательно и имеет свой собственный программный счетчик и стек. Нити, как и процессы, могут, например, порождать нити-потомки, могут переходить из состояния в состояние. Подобно традиционным процессам (то есть процессам, состоящим из одной нити), нити могут находится в одном из следующих состояний: ВЫПОЛНЕНИЕ, ОЖИДАНИЕ и ГОТОВНОСТЬ. Пока одна нить заблокирована, другая нить того же процесса может выполняться. Нити разделяют процессор так, как это делают процессы, в соответствии с различными вариантами планирования.

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

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

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

Обобщая сказанное, отметим, что понятие процесса в любой ОС включает в себя:

исполняемый код;

собственное виртуальное адресное пространство;

совокупность ресурсов, выделенных данному процессу операционной системой;

хотя бы одну исполняемую нить.
^ 2.2Жизненный цикл процесса.
С момента запуска и до завершения выполнения процесс может находиться в различных активных или пассивных состояниях, которые в совокупности описывают жизненный цикл процесса в вычислительной системе. Количество и характеристики таких состояний может меняться в зависимости от конкретной вычислительной системы. Можно выделить несколько основных состояний процесса:

ПОРОЖДЕНИЕ – состояние процесса, когда он уже создан, но не готов к запуску, при этом создаются информационные структуры, описывающие данный процесс; загружается кодовый сегмент процесса в оперативную память или в область свопинга.

ВЫПОЛНЕНИЕ - активное состояние процесса, во время которого процесс обладает всеми необходимыми ресурсами и непосредственно выполняется процессором;

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

ГОТОВНОСТЬ - также пассивное состояние процесса: процесс имеет все требуемые для него ресурсы, он готов выполняться, однако процессор занят выполнением другого процесса.

ЗАВЕРШЕНИЕ – конечное состояние в жизненном цикле процесса, процесс выгружается из памяти и разрушаются все структуры данных, связанные с ним.

Рис. 1 Общая схема состояний процесса.

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

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

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

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

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

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

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

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

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

Таким образом, необходимо уметь решать две важнейшие задачи:

Распределение ресурсов между процессами.

Организация защиты ресурсов, выделенных определенному процессу, от неконтролируемого доступа со стороны других процессов.

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

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

void echo()

{

char in;

input(in);

output(in)

}

В данном примере мы используем некоторые условные функции input() и output(), так как в данный момент для нас неважно, как конкретно реализован ввод/вывод в данной системе. Поскольку такой кусок кода будет использоваться практически в любой программе, его удобно сделать разделяемым, когда ОС загружает в некоторую область памяти, доступную всем процессам, одну-единственную копию данной программы, и все процессы используют эту копию совместно. Заметим, что в этом случае переменная in является разделяемой. Представим теперь ситуацию, изображенную на Рис. 2:




^ Рис. 2 Конкуренция процессов за ресурс.

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

Процесс В тоже вызывает функцию echo(). После выполнения функции echo() переменная in содержит уж новое значение, считанное с клавиатуры.

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

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

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

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

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

Возникновение так называемых тупиков (deadlocks). Рассмотрим следующую ситуацию (см. Рис. 3): имеются процессы А и В, каждому из которых в некоторый момент требуется иметь доступ к двум ресурсам R1и R2. Процесс А получил доступ к ресурсу R1, и следовательно, никакой другой процесс не может иметь к нему доступ, пока процесс А не закончит с ним работать. Одновременно процесс В завладел ресурсом R2. В этой ситуации каждый из процессов ожидает освобождения недостающего ресурса, но оба ресурса никогда не будут освобождены, и процессы никогда не смогут выполнить необходимые действия.



^ Рис. 3 Возникновение тупиковой ситуации.

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

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

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

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

Далее мы рассмотрим различные механизмы организации взаимного исключения для синхронизации доступа к разделяемым ресурсам и обсудим достоинства, недостатки и области применения этих подходов.
^ 3.1Способы реализации взаимного исключения. 3.1.1Запрещение прерываний и специальные инструкции.
Простейшее умозаключение, которое, на первый взгляд, решает проблему синхронизации доступа к критическим ресурсам, заключается в следующем: некорректная работа с разделяемыми ресурсами возникает в том случае, если переключение процессов происходит в тот момент, когда выполняющийся процесс начал работу с разделяемым ресурсом, но не закончил ее, т.е. находится в своей критической секции. Чтобы этого не происходило, процесс должен запретить все прерывания непосредственно после входа в критическую секцию и разрешить их перед самым выходом из нее. Если прерывания запрещены, то переключения процессов не происходит, так как передача управления планировщику может быть реализована только с использованием прерываний (это может быть как прерывание по таймеру, так и другие прерывания, например, при заказе обмена). Таким образом, запрещение прерываний гарантирует процессу, что никакой другой процесс не обратится к разделяемому ресурсу, пока прерывания не будут разрешены.

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

Для организации взаимного исключения на многопроцессорной системе с общей памятью могут использоваться специальные машинные инструкции. Примером такой инструкции может служить TSL – test and set lock, реализующая чтение ячейки памяти и запись нового значения в ту же ячейку как единую операцию. При этом гарантируется, что совокупность операций чтения и записи ячейки памяти является неделимой, т.е. доступ к ячейке памяти со стороны других процессоров блокируется на все время исполнения инструкции. Вариацией этой идеи является специальная инструкция exchange, которая меняет местами содержимое регистра и ячейки памяти. Здесь опять гарантируется, что на все время выполнения инструкции доступ к ячейке памяти блокируется.

Используя эти инструкции и дополнительную разделяемую переменную, значение которой говорит о том, можно ли в данный момент войти в критическую секцию, процессы могут синхронизировать свою работу. Возможность считывать старое значение и записывать новое за одну операцию позволяет избежать ситуации, когда процесс, считав значение переменной, говорящее ему о том, что он может войти в свою критическую секцию, не успеет изменить ее значение на «занято» и будет в этот момент прерван; другой же процесс, получивший управление, считает неизмененное значение переменной, которое позволит и ему войти в критическую секцию, в результате чего два процесса одновременно окажутся в критических секциях.
^ 3.1.2Алгоритм Петерсона.
Другим подходом к решению задачи организации взаимного исключения является изобретение различных алгоритмов, позволяющих процессам синхронизировать свою работу программно. Одним из первых программных решений является алгоритм Петерсона.

Алгоритм Петерсона для случая 2х процессов представлен на Рис. 4.




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

Элементы массива flag символизируют собой желание соответствующего процесса попасть в критическую секцию. Каждый из процессов видит все элементы массива flag, но модифицирует только «свой» элемент. Переменная turn устанавливает очередность прохождения критической секции при обоюдном желании процессов вступить в нее. Благодаря тому, что каждый из процессов прежде всего устанавливает флаг очередности в пользу другого процесса, исключается ситуация «монополизации» ресурса одним из процессов и вечного блокирования второго.
^ 3.1.3Активное ожидание.
Общим недостатком рассмотренных выше решений является то, что процесс, желающий получить доступ к занятому ресурсу, блокируется в состоянии так называемого активного ожидания (в англоязычной литературе – busy waiting), т.е. в цикле постоянно проверяет, не наступило ли условие, при котором он сможет войти в критическую секцию. Использование активного ожидания приводит к бесполезному расходованию процессорного времени и как следствие, снижению общей производительности системы. Кроме того, при некоторых стратегиях планирования времени ЦП в целом корректный алгоритм с активным ожиданием может привести к тупику. Примером может служить стратегия планирования с приоритетами, когда процесс, имеющий больший приоритет, загружается на выполнение и переходит в состояние активного ожидания, в то время как процесс с меньшим приоритетом захватил необходимый ресурс, но был выгружен до того, как освободил его. Поскольку процесс с большим приоритетом не блокирован, а готов к продолжению выполнения, переключение процессов не происходит, и процесс, владеющий ресурсом, никогда не сможет его освободить.

Далее мы рассмотрим ряд подходов, которые позволяют реализовать взаимное исключение без использования активного ожидания. Основная идея всех этих подходов в том, чтобы блокировать ожидающий процесс, вместо того, чтобы оставлять его в состоянии активного ожидания, а затем, при наступлении возможности использования нужного ресурса, разблокировать один из ранее заблокированных процессов. Для этого, однако, требуется определенная поддержка со стороны ОС, так как именно в ее ведении находится переключение состояний процессов.
3.1.4Семафоры.
Первый из таких подходов был предложен Дейкстрой в 1965 г. Дейкстра предложил новый тип данных, именуемый семафором. Семафор представляет собой переменную целого типа, над которой определены две операции: down(P) и up(V).2 Операция down проверяет значение семафора, и если оно больше нуля, то уменьшает его на 1. Если же это не так, процесс блокируется, причем операция down считается незавершенной. Важно отметить, что вся операция является неделимой, т.е. проверка значения, его уменьшение и, возможно, блокирование процесса производятся как одно атомарное действие, которое не может быть прервано. Операция up увеличивает значение семафора на 1. При этом, если в системе присутствуют процессы, блокированные ранее при выполнении down на этом семафоре, ОС разблокирует один из них с тем, чтобы он завершил выполнение операции down, т.е. вновь уменьшил значение семафора. При этом также постулируется, что увеличение значения семафора и, возможно, разблокирование одного из процессов и уменьшение значения являются атомарной неделимой операцией.

Чтобы прояснить смысл использования семафоров для синхронизации, можно привести простую аналогию из повседневной жизни. Представим себе супермаркет, посетители которого, прежде чем войти в торговый зал, должны обязательно взять себе инвентарную тележку. В момент открытия магазина на входе имеется N свободных тележек – это начальное значение семафора. Каждый посетитель забирает одну из тележек (уменьшая тем самым количество оставшихся на 1) и проходит в торговый зал – это аналог операции down. При выходе посетитель возвращает тележку на место, увеличивая тележек на 1 – это аналог операции up. Теперь представим себе, что очередной посетитель обнаруживает, что свободных тележек нет – он вынужден блокироваться на входе в ожидании появления тележки. Когда один из посетителей, находящихся в торговом зале, покидает его, посетитель, ожидающий тележку, разблокируется, забирает тележку и проходит в зал. Таким образом, наш семафор в виде тележек позволяет находиться в торговом зале (аналоге критической секции) не более чем N посетителям одновременно. Положив N = 1, получим реализацию взаимного исключения. Семафор, начальное (и максимальное) значение которого равно 1, называется двоичным семафором (так как имеет только 2 состояния: 0 и 1). Использование двоичного семафора для организации взаимного исключения проиллюстрировано на Рис. 5.



^ Рис. 5 Взаимное исключение с использованием семафора

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

С целью облегчить написание корректных программ были предложены более высокоуровневые средства синхронизации, которые мы рассмотрим далее.
3.1.5Мониторы.
Идея монитора была впервые сформулирована в 1974 г. Хоаром. В отличие от других средств, монитор представляет собой языковую конструкцию, т.е. некоторое средство, предоставляемое языком программирования и поддерживаемое компилятором. Монитор представляет собой совокупность процедур и структур данных, объединенных в программный модуль специального типа. Постулируются три основных свойства монитора:

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

Процесс «входит» в монитор путем вызова одной из его процедур

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

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