Механизмы синхронизации

Межпроцессное взаимодействие (IPC, interprocess communication) разбивается на три пункта:

- передача информации от одного процесса другому;

- контроль над деятельностью процессов (процессы не должны пересекаться в критических ситуациях);

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

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

Пусть каталог спулинга состоит из сегментов, пронумерованных 0, 1, 2,..., в каждом их которых может храниться имя файла. Имеются совместно используемые переменные: out – указывающая на следующий файл для печати; in – указывающая на следующий свободный сегмент. Эти переменные можно хранить в одном файле, доступном всем процессам. Сегменты с 0 по 3 пусты, так как файлы напечатаны, в сегментах с 4 по 6 файлы ждут своей очереди на печать. Конкурирующие процессы А и В решают поставить файл в очередь на печать (рис. 3.6.). Возможна следующая ситуация.

Процесс А считывает значение переменной in и сохраняет его в локальной переменной, например, next_free_slot. После этого происходит прерывание по таймеру, и процессор переключается на процесс В. Процесс В считывает значение переменной in и сохраняет его в своей локальной переменной next_free_slot. В данный момент оба процесса считают, что следующий свободный сегмент – седьмой. Процесс В сохраняет в каталоге спулинга имя файла и заменяет значение in на 8, затем продолжает заниматься другими задачами. Затем управление переходит к процессу А, который продолжает с того места, на котором остановился. Он обращается к переменной next_free_slot, считывает ее значение и записывает в седьмой сегмент свое имя файла, удаляя имя файла, записанное туда процессом В. Затем он заменяет значение in на 8 (next_free_slot +1 = 8). Структура каталога спулинга не нарушена и демон печати не заметит изменений, поэтому файл процесса В не будет напечатан. Ситуации, в которых два и более процесса считывают или записывают данные одновременно и конечный результат зависит от того, какой из них был первым, называются состояниями состязания.

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

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

- два процесса не должны одновременно находиться в критических областях;

- в программе не должно быть предположений о скорости или количестве процессоров;

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

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

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

1.Запрещение прерываний при входе процесса в критическую область и разрешение прерываний при выходе из нее.

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

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

4.Алгоритм Петерсона. Датский математик Деккер первым разработал программное решение проблемы взаимного исключения, не требующее строгого чередования. В 1981 году Петерсон разработал более простой алгоритм взаимного исключения, который состоит из двух процедур, написанных на ANSI С, что предполагает необходимость прототипов для всех определяемых и используемых функций. Прежде чем обратиться к совместно используемым переменным (войти в критическую область), процесс вызывает процедуру enter_region со своим параметром (0 или 1). Поэтому процессу при необходимости придется подождать, прежде чем входить в критическую область. После выхода из критической области процесс вызывает процедуру leave_region, чтобы обозначить свой выход и тем самым разрешить другому процессу вход в критическую область.

5.Команда TSL. Данное решение требует участия аппаратного обеспечения. Многие процессоры имеют команду TSL RX.LOCK (Test and Set Lock – проверить и заблокировать), которая действует следующим образом. В регистр RX считывается содержимое слова памяти lock, а в ячейке памяти lock сохраняется некоторое ненулевое значение. Гарантируется, что операция считывания слова и сохранения неделима – другой процесс не может обратиться к слову в памяти, пока команда не выполнена. Процессор, выполняющий команду TSL, блокирует шину памяти, чтобы остальные процессоры не могли обратиться к памяти. Прежде чем попасть в критическую область, процесс вызывает процедуру enter_region, которая выполняет активное ожидание вплоть до снятия блокировки, затем она устанавливает блокировку и возвращается. По выходе из критической области процесс вызывает процедуру leave_region, помещающую 0 в переменную lock. Для корректной работы процесс должен вызывать эти процедуры своевременно, в противном случае взаимное исключение не удастся.

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

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

В 1965 году Дейкстра (Е.W. Dijkstra) предложил использовать семафоры – целые переменные для подсчета сигналов запуска, сохраненных на будущее. Значение семафоров изменяется от нуля (в случае отсутствия сохраненных сигналов активизации) до некоторого положительного числа, соответствующего количеству отложенных активизирующих сигналов. Дейкстра предложил две операции: down и up (обобщения sleep и wakeup):

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

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

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

В ряде случаев используется упрощенная версия семафора – мьютекс (mutex от mutual exclusion – взаимное исключение), который управляет взаимным исключением доступа к совместно используемым ресурсам или кодам. Мьютексы часто используются в случае потоков, действующих только в пространстве пользователя. Мьютекс представляет собой переменную, которая может находиться в одном из двух состояний: блокированном или неблокированном, поэтому для описания мьютекса требуется один бит. Часто используется целая переменная, у которой 0 означает неблокированное состояние, а остальные значения соответствуют блокированному состоянию. Значение мьютекса устанавливается двумя процедурами.

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

Чтобы упростить написание программ, в 1974 году Хоар (Ноаге) и Бринч Хансен (Brinch Hansen) предложили примитив синхронизации более высокого уровня – монитор, который представляет собой набор процедур, переменных и других структур данных, объединенных в особый модуль или пакет. Процессы могут вызывать процедуры монитора, но у процедур, объявленных вне монитора, нет прямого доступа к внутренним структурам данных монитора. Реализации взаимных исключений способствует важное свойство монитора: при обращении к монитору в любой момент времени активным может быть только один процесс.

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

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

- send (destination, &message) – послать сообщение заданному адресату;

- receive (source, message) – получить сообщение от указанного источника.

Если сообщения нет, второй запрос блокируется до поступления сообщения либо немедленно возвращает код ошибки. Примитивы send и receive имеют скрытый механизм взаимоисключения, в большинстве систем они имеют и скрытый механизм блокировки при чтении из пустого буфера и при записи в полностью заполненный буфер. Однако, не смотря на простоту использования, передача сообщений в пределах одного компьютера происходит существенно медленнее, чем работа с семафорами и мониторами.

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

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

Дата добавления: 2014-01-07