Тема 6.

Синхронизация процессов на нижнем уровне.

Содержание.

1. Проблемы синхронизации процессов.

2. Блокировка памяти.

3. Операция «Проверка и установка».

4. Семафоры.

Проблемы синхронизации процессов.

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

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

Для эффективного использования аппаратных и программных ресурсов те и другие подлежат разделению. У аппаратных и программных ресурсов есть общие свойства. Рассмотрим систему управления файлами, которая в каждый момент может обслуживать запросы только одного процесса. Даже если система управления файлами – программный ресурс, ее разделение организуется так же, как и разделение многих аппаратных ресурсов. Когда несколько процессов пытаются одновременно воспользоваться системой управления файлами, она может стать столь же опасным узким местом, как и диск или центральный процессор. Физические устройства называются физическими, или естественными ресурсами. Часть программного обеспечения, которая ведет себя так, как будто она физический ресурс, называется логическим ресурсом. Логические ресурсы существуют только в виде программ. Например, чтобы сделать возможным разделение диска между несколькими процессами, в системе может быть программно реализовано много логических дисков, которые разделяют один физический. Каждый логический диск представляет собой процесс, который связан с дисковым каналом. Когда какой-нибудь процесс использует логический диск, он «считает», что в его распоряжении находится целый диск. В действительности все, что у него есть,– это логический диск, который имитирует целое физическое устройство, посылая и получая команды от дискового канала. Процессу, пользующемуся ресурсом, неважно, что это за ресурс – логический, т. е. реализованный программно, или физический, т. е. реализованный аппаратно. Единственное, что процессу важно, – это чтобы ресурс делал то, что положено. Поэтому, рассматривая разделение ресурсов, не будем различать логические и физические ресурсы, поскольку их внешнее поведение по существу одинаково.

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

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

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

Рис. 6.1. Пример необходимости синхронизации.

ей итерации, запишет имя файла также в позицию 4, поверх имени файла процесса S.

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

Требования, предъявляемые к алгоритмам синхронизации процессов.

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

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

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

3. Если процесс Pi исполняется в своем критическом участке, то не существует никаких других процессов, которые исполняются в своих соответствующих критических секциях. Это условие получило название условия взаимоисключения (mutual exclusion).

4. Процессы, которые находятся вне своих критических участков и не собираются входить в них, не могут препятствовать другим процессам входить в их собственные критические участки. Если нет процессов в критических секциях, и имеются процессы, желающие войти в них, то только те процессы, которые не исполняются в remainder section, должны принимать решение о том, какой процесс войдет в свою критическую секцию. Такое решение не должно приниматься бесконечно долго. Это условие получило название условия прогресса (progress).

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

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