Параллельные процессы (concurrent processes), страница 3

Такой подход называется жесткой синхронизацией.

Алгоритм Деккера прошел путь развития и был неоднократно модифицирован различными исследователями (Дейкстра, Кнут и многие другие), расширен на ситуацию n-процессов.

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

n  осуществляет чтение переменной;

n  установку нужного значения этой переменной;

n  запись нового значения в область сохранения.

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

В современных ОС проблема взаимоисключения решается в основном средствами ОС. Как я уже упоминал, в Win32 API объекты типа Mutex позволяют синхронизировать доступ к данным со стороны нескольких процессов. Если объект типа mutex занят, то любой другой поток, ожидающий этот объект, будет приостановлен, пока первый поток его не освободит. Если объект свободен, то первый же претендующий на него объект получит его в свое распоряжение.

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

3.4.   Семафоры.

Семафор - это защищенная переменная, значения которой можно опрашивать и менять только при помощи специальных операций Pи V и операции инициализации.

P - первая буква датского слова passeren - пропустить, V - первая буква слова vrygeven - освободить.

Впервые понятие семафора определил в середине 60-х годов Дейкстра. Семафоры являются основным примитивом для синхронизации процессов в UNIX.

Семафоры могут быть двоичные (то есть принимающие только значения ИСТИНА и ЛОЖЬ) и считающие (то есть семафоры со счетчиками, принимающими неотрицательное значение).

Операция P над семафором записывается как P(S) и выполняется следующим образом:

if (S>0)

{ S = S - 1; }

else { wait (S); }

Операция V над семафором S записывается как V(S) и выполняется следующим образом (как эту операцию определил Дейкстра, впоследствии в практическом использовании ее упростили):

if (AnithingIsWaiting(S)) { StartWaitingProcess(); }

else { S = S+ 1; }

Непременным является условие атомарности (неделимости) операций P и V.

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

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

Участки взаимоисключения по семафору S обрамляются операциями P(S) и V(S). Если одновременно несколько процессов пытаются выполнить операцию P(S), то это будет разрешено одному из них (обычно по принципу FIFO), а остальным придется ждать. Семафоры могут быть реализованы как программно, так и аппаратно, обычно их встраивают в ядро системы.

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

Наиболее простой пример использования семафоров - работа с последовательными портами. Допустим, их у вашего компьютера 3. Следовательно, не более чем три потока могут одновременно работать с портом (по одному на каждый порт). Для мониторинга занятости портов заводим семафор со счетчиком, равным 3 (ведь у нас всего три последовательных порта). При этом следует учитывать, что семафор считается свободным, если его ресурс больше 0, и занятым, если счетчик равен 0. При каждом вызове из потока WaitFirSingleObject с передачей ей описателя семафора система проверяет: больше ли 0 счетчик ресурсов у данного семафора. Если да, уменьшает его на 1 и “будит” поток. Если счетчик оказался обнулен, система оставляет поток неактивным до тех пор, пока другой поток освободит данный семафор (то есть увеличит счетчик его ресурсов).