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

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

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

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

Семафоры

Фундаментальный принцип взаимодействия двух или несколь­ких процессов заключается в использовании обмена сигналами [3]. Для сигнализации используются специальные переменные, называе­мые семафорами. Для передачи сигнала через семафор s процесс вы­полняет примитив signal (s),а для получения сигнала - примитив wait(s). В последнем случае процесс приостанавливается до тех пор, пока не осуществится передача соответствующего сигнала.

Будем рассматривать семафор как переменную, принимающую целые значения, над которой определены три операции:

1. Семафор инициализируется неотрицательным значением.

2. Операция wait уменьшает значение семафора. Если это значе­ние становится отрицательным, процесс, выполняющий опера­цию wait, блокируется.

3. Операция signal увеличивает значение семафора. Если это значение становится отрицательным, то заблокированный опе­рацией wait процесс деблокируется.

Пусть имеется массив P (i),i=l,..., n процессов. Каждый про­цесс перед входом в критическую секцию выполняет вызов wait (s).Если s<0, процесс приостанавливается. Если s=l, то s: =0 и процесс входит в критическую секцию. Поскольку s не является больше положительным, любой другой процесс при попытке войти в критическую секцию обнаружит, что она занята. При этом данный процесс блокируется и s:=-l. Пытаться войти в критическую сек­цию может любое количество процессов, при этом значение семафо­ра каждый раз уменьшается на единицу. После того как процесс, на­ходившийся в критической секции, покидает ее, s:=s + l и один из заблокированных процессов удаляется из очереди и активизируется, т.е. перемещается из списка приостановленных процессов в список готовых к выполнению процессов. Данный процесс сможет войти в критическую секцию, как только планировщик операционной систе­мы выберет его.

В случае потоков, выполняющихся в пространстве пользователя, используется упрощенная версия семафора, называемая мъютексом (mutex, сокращение от mutual exclusion - взаимное исключение) [5]. Мъютекс может управлять взаимным исключением доступа к совме­стно используемым ресурсам, и его реализация более проста и эф­фективна.

Мъютекс — переменная, которая может находиться в одном из двух состояний: блокированном (<>0) или неблокированном (=0). Значе­ние мьютекса устанавливается двумя процедурами. Для входа в кри­тическую секцию поток или процесс вызывает процедуру mutexlock. Если мьютекс не заблокирован, поток может войти в критическую секцию [5]. В противном случае вызывающий поток блокируется до тех пор, пока другой поток, находящийся в критиче­ской секции, не выйдет из нее, вызвав процедуру mutexunlock. Если мьютекс блокирует несколько потоков, то из них случайным образом выбирается один.

Процедура mutexlock отличается от вышеприведенной процедуры enterregion следующим образом. Процедура
enterregion находится в состоянии активного ожидания, т.е. проверяет в цикле наличие блокировки до тех пор, пока критическая секция не освободится или планировщик не передаст управление другому процессу по истечении кванта времени. Однако в случае потоков ситуация меняется, поскольку нет прерываний по таймеру, останавливающих слишком долго работающие потоки [5]. Поток, пытающийся получить доступ к семафору и находящийся в состоянии активного ожидания, зациклится навсегда, так как он не позволит
предоставить процессор другому потоку, желающему снять блокировку. Поэтому, если войти в критическую секцию невозможно,mutex_lock вызывает thread_yield, чтобы предоставить процессор другому потоку. При следующем запуске поток снова проверяет блокировку. Поскольку вызов threadyield является обращением к планировщику потоков в пространстве пользователя, обращения к ядру не требуется, и он выполняется быстро. Синхрониза­ция потоков на уровне пользователя происходит полностью в про­странстве пользователя.

 

Семафоры (дополнения)

 

Реализация семафоров

Дийкстра показал, что семафоры можно реализовать без использования специальных машинных инструкций. Функция Pprim блокирует семафор по результатам проверки значений, содержащихся в массиве val; каждый процессор в системе управляет значением одного элемента массива. Прежде чем заблокировать семафор, процессор проверяет, не заблокирован ли уже семафор другими процессорами (соответствующие им элементы в массиве val тогда имеют значения, равные 2), а также не предпринимаются ли попытки в данный момент заблокировать семафор со стороны процессоров с более низким кодом идентификации (соответствующие им элементы имеют значения, равные 1). Если любое из условий выполняется, процессор переустанавливает значение своего элемента в 1 и повторяет попытку. Когда функция Pprim открывает внешний цикл, переменная цикла имеет значение, на единицу превышающее код идентификации того процессора, который использовал ресурс последним, тем самым гарантируется, что ни один из процессоров не может монопольно завладеть. Функция Vprim освобождает семафор и открывает для других процессоров возможность получения исключительного доступа к ресурсу путем очистки соответствующего текущему процессору элемента в массиве val и перенастройки значения lastid. Чтобы защитить ресурс, следует выполнить следующий набор команд:

 

Pprim(семафор);

команды использования ресурса;

Vprim(семафор);

 

В большинстве машин имеется набор элементарных (неделимых) инструкций, реализующих операцию блокирования более дешевыми средствами, ибо циклы, входящие в функцию Pprim, работают медленно и снижают производительность системы. Так, например, в машинах серии IBM 370 поддерживается инструкция compare and swap (сравнить и переставить), в машине AT&T 3B20 - инструкция read and clear (прочитать и очистить). При выполнении инструкции read and clear процессор считывает содержимое ячейки памяти, очищает ее (сбрасывает в 0) и по результатам сравнения первоначального содержимого с 0 устанавливает код завершения инструкции. Если ту же инструкцию над той же ячейкой параллельно выполняет еще один процессор, один из двух процессоров прочитает первоначальное содержимое, а другой - 0: неделимость операции гарантируется аппаратным путем. Таким образом, за счет использования данной инструкции функцию Pprim можно было бы реализовать менее сложными средствами.

 

Тупиковые ситуации.

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

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

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

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

Проблема тупиков включает в себя следующие задачи:

· предотвращение тупиков,

· распознавание тупиков,

· восстановление системы после тупиков.

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

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

Если же тупиковая ситуация возникла, то не обязательно снимать с выполнения все заблокированные процессы. Можно снять только часть из них, при этом освобождаются ресурсы, ожидаемые остальными процессами, можно вернуть некоторые процессы в область свопинга, можно совершить "откат" некоторых процессов до так называемой контрольной точки, в которой запоминается вся информация, необходимая для восстановления выполнения программы с данного места. Контрольные точки расставляются в программе в местах, после которых возможно возникновение тупика. Из всего вышесказанного ясно, что использовать семафоры нужно очень осторожно, так как одна незначительная ошибка может привести к останову системы. Для того чтобы облегчить написание корректных программ, было предложено высокоуровневое средство синхронизации, называемое монитором. Монитор - это набор процедур, переменных и структур данных. Процессы могут вызывать процедуры монитора, но не имеют доступа к внутренним данным монитора. Мониторы имеют важное свойство, которое делает их полезными для достижения взаимного исключения: только один процесс может быть активным по отношению к монитору. Компилятор обрабатывает вызовы процедур монитора особым образом. Обычно, когда процесс вызывает процедуру монитора, то первые несколько инструкций этой процедуры проверяют, не активен ли какой-либо другой процесс по отношению к этому монитору. Если да, то вызывающий процесс приостанавливается, пока другой процесс не освободит монитор. Таким образом, исключение входа нескольких процессов в монитор реализуется не программистом, а компилятором, что делает ошибки менее вероятными.

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

 

Предотвращение тупиковых ситуаций

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