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

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

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

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

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

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

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

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

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

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

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

Проблема синхронизации легко решается, если потребовать, чтобы процессы ПР1 и ПР2 входили в свои критические интервалы попеременно. Для этого можно использовать одну общую переменную, которая будет хранить указатель того, чья очередь войти в критическую секцию. Текст такого решения на языке, близком к Pascal, приведен в Листинге 6.1.