Основные теоретические положения. Программа синхронизации на основе семафоров и мьютексов

Программа синхронизации на основе семафоров и мьютексов

Цель работы: Освоить средства синхронизации и взаимодействия процессов на основе построения P- и V-системы.

Понятия, относящиеся к проблеме взаимоисключения, Дейкстра обобщил в своей концепции семафоров. Семафор – это переменная специального типа, которая доступна параллельным процессам для проведения над ней только двух операций: "закрытия" и "открытия", названных соответственно P- и V- операциями. Значение семафора можно опрашивать и менять только при помощи примитивов P и V и операции инициализации. Семафоры могут быть двоичными (принимать значения только 0 или 1) или считающими (принимать целые неотрицательные значения). Операции P и V неделимы в своем выполнении и взаимно исключают друг друга.

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

Пусть S – семафор. Операция V над семафором S записывается как V(S) и увеличивает переменную S на единицу одним неделимым действием, т.е. выборка, инкремент и запоминание не могут быть прерваны, и к S нет доступа другим процессам во время операции V(S). Операция P над семафором S записывается как P(S) и уменьшает переменную S на единицу, если это возможно. Если было S=0, то уменьшение S невозможно и процесс, вызвавший P -операцию, ждет, пока значение S не увеличится. Проверка и уменьшение значения S также являются одним неделимым действием.

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

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

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

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

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

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

Для работы с мьютексом имеется ряд функций: создание (CreateMutex), открытие (OpenMutex), ожидание событий (WaitForSingleObject и WaitForMultipleObjects), освобождение (ReleaseMutex). Конкретные обращения к этим функциям и перечни их параметров приводятся в документации на соответствующую ОС.

Рассмотрим использование семафоров на классическом примере взаимодействия двух процессов, выполняющихся в режиме мультипрограммирования, один из которых пишет данные в буферный пул, а другой считывает их из буферного пула. Пусть буферный пул состоит из N буферов, каждый из которых может содержать одну запись. Процесс "писатель" должен приостанавливаться, когда все буфера оказываются занятыми, и активизироваться при освобождении хотя бы одного буфера. Напротив, процесс "читатель" приостанавливается, когда все буферы пусты, и активизируется при появлении хотя бы одной записи. Введем два семафора: e - число пустых буферов и f - число заполненных буферов. Предположим, что запись в буфер и считывание из буфера являются критическими секциями. Введем также двоичный семафор b, используемый для обеспечения взаимного исключения. Тогда процессы могут быть описаны следующим образом:

// Глобальные переменные

#define N 256

int e = N, f = 0, b = 1;

void Writer ()

{

while(1)

{

PrepareNextRecord(); /* подготовка новой записи */

P(e); /* Уменьшить число свободных буферов, если они есть */

/* в противном случае - ждать, пока они освободятся */

P(b); /* Вход в критическую секцию */

AddToBuffer(); /* Добавить новую запись в буфер */

V(b); /* Выход из критической секции */

V(f); /* Увеличить число занятых буферов */

}

}

void Reader ()

{

while(1)

{

P(f); /* Уменьшить число занятых буферов, если они есть */

/* в противном случае ждать, пока они появятся */

P(b); /* Вход в критическую секцию */

GetFromBuffer(); /* Взять запись из буфера */

V(b); /* Выход из критической секции */

V(e); /* Увеличить число свободных буферов */

ProcessRecord(); /* Обработать запись */

}

}

Задание

(выполняются с использованием справочных изданий)

Создать и реализовать модель взаимодействия двух процессов: «писателя» и «читателя» в соответствии с теоретическими положениями о применении семафоров.

При выполнении задания рекомендуется придерживаться следующей методики.

1. Используйте Вашу среду исследования функционирования операционной системы.

2. Для моделирования используйте 2 процесса.

3. Создайте буферный пул с количеством буферов, равным двадцати.

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

5. Запустите процессы записи и чтения с визуализацией происходящего.

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

Контрольные вопросы

1. Алгоритм Деккера реализации взаимного исключения, его достоинства и недостатки; программная реализация.

2. Проблема взаимного исключения; концепция семафоров: определение семафорной переменной, P- и V-примитивы.

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

4. Семафорные механизмы: определение, программная реализация. Виды семафоров.

5. Мьютексы – определение, назначение.

Р а з д е л V II

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