Критическая секция

Из-за чего произошла путаница в предыдущем примере? Очевидно, что из-за того, что процесс прервали тогда, когда он еще не закончил работу с разделяемым ресурсом. Что же делать? Первый ответ – не прерывать процесс во время работы с разделяемым ресурсом. Действительно, проблема, описанная выше, в таком случае не возникнет, но могут возникнуть другие (ведь мы не случайно только что решили, что более защищенной является система с вытесняющей многозадачностью!).

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

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

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

Другим способом является использование блокирующих переменных. С каждым разделяемым ресурсом связывается двоичная переменная, которая принимает значение 1, если ресурс свободен (то есть ни один процесс не находится в данный момент в критической секции, связанной с данным процессом), и значение 0, если ресурс занят. На рисунке 3 показан фрагмент алгоритма процесса, использующего для реализации взаимного исключения доступа к некоторому разделяемому ресурсу блокирующую переменную РЕСУРС_1. Перед входом в критическую секцию процесс проверяет, свободен ли ресурс РЕСУРС_1. Если он занят, то проверка циклически повторяется, если свободен, то значение переменной РЕСУРС_1 устанавливается в 0, и процесс входит в критическую секцию. После того, как процесс выполнит все действия с разделяемым ресурсом, значение переменной РЕСУРС_1 снова устанавливается равным 1.

Процесс А (не совсем верная реализация блокирующих переменных):

если не определена РЕСУРС_1 то определить глобальную переменную РЕСУРС_1 РЕСУРС_1 = 1 конец если повторять пока РЕСУРС_1<>1 конец повтора РЕСУРС_1 = 0 ‘ так нельзя – операция проверки и установки должна быть неделимой, то есть предыдущий цикл и текущая операция присваивания должны выполняться как единая операция «проверка-занятие» Критическая секция: работа с разделяемым ресурсом РЕСУРС_1 = 1

Процесс А (правильный способ – пользуемся системной операцией ПРОВЕРКА_ЗАНЯТИЕ:

если не определена РЕСУРС_1 то определить глобальную переменную РЕСУРС_1 РЕСУРС_1 = 1 конец если повторять пока не ПРОВЕРКА_ЗАНЯТИЕ (РЕСУРС_1) конец повтора Критическая секция: работа с разделяемым ресурсом РЕСУРС_1 = 1

Рисунок 3 - Реализация критических секций с использованием блокирующих переменных

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

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

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

Для устранения таких нежелательных потерь может быть использован так называемый аппарат событий. С помощью этого средства могут решаться не только проблемы взаимного исключения, но и более общие задачи синхронизации процессов. В разных операционных системах аппарат событий реализуется по-своему, но в любом случае используются системные функции аналогичного назначения, которые условно назовем WAIT(x) и POST(x), где x - идентификатор некоторого события. На рисунке 4 показан фрагмент алгоритма процесса, использующего эти функции. Если ресурс занят, то процесс не выполняет циклический опрос, а вызывает системную функцию WAIT(D), здесь D обозначает событие, заключающееся в освобождении ресурса d. Функция WAIT(D) переводит активный процесс в состояние ОЖИДАНИЕ и делает отметку в его дескрипторе о том, что процесс ожидает события D. Процесс, который в это время использует ресурс d, после выхода из критической секции вызывает системную функцию POST(D), в результате чего операционная система просматривает очередь ожидающих процессов и переводит процесс, ожидающий события D, в состояние ГОТОВНОСТЬ.

Рассмотрим пример. Пусть два процесса пишут поочередно сообщения в «почтовый ящик». Ящик считаем безразмерным. Сообщение может быть и длинным и коротким, очевидно, что два сообщения нельзя перемешивать. Заводим блокирующую переменную «МОЖНОПИСАТЬ», сигнализирующую о том, можно ли писать в настоящий момент в «почтовый ящик» (1 – можно писать, 0 – ящик занят). Процессы вводят сообщения от пользователя. Признаком конца сообщения является нажатие клавиши ENTER. Почтовым ящиком сделаем файл Р. Признаком конца всех сообщений F10.

Описание процессов А и В приведены ниже (они одинаковы!)

Процесс А (или В):

если не определена МОЖНОПИСАТЬ то определить глобальную переменную МОЖНОПИСАТЬ МОЖНОПИСАТЬ = 1 конец если S = ввод очередного символа с клавиатуры SL =”” повторять повторять пока S<>F10 и S<>ENTER SL = SL+S S = ввод очередного символа с клавиатуры конец ввода символов WAIT(МОЖНОПИСАТЬ) открыть файл P записать в файл P сообщение SL закрыть файл P POST (МОЖНОПИСАТЬ) конец повтор пока S<>F10

Рисунок 4 - Реализация критической секции с использованием системных функций WAIT(D) и POST(D)

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

V(S): переменная S увеличивается на 1 одним неделимым действием; выборка, инкремент и запоминание не могут быть прерваны, и к S нет доступа другим процессам во время выполнения этой операции.

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

В частном случае, когда семафор S может принимать только значения 0 и 1, он превращается в блокирующую переменную. Операция P заключает в себе потенциальную возможность перехода процесса, который ее выполняет, в состояние ожидания, в то время как V-операция может при некоторых обстоятельствах активизировать другой процесс, приостановленный операцией P (сравните эти операции с системными функциями WAIT и POST).

Применение семафоров необходимо тогда, когда требуется определить степень занятости некоторого ресурса, а не просто получить ответ на вопрос «занят ресурс или свободен». Рассмотрим использование семафоров на классическом примере взаимодействия двух процессов, выполняющихся в режиме мультипрограммирования, один из которых пишет данные в буферный пул (список) в конец, а другой считывает их из буферного пула с первой записи списка и удаляет. Пусть буферный пул состоит из 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(); /* Обработать запись */

}

}

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

Рассмотрим еще пример. Пусть Вам надо запрограммировать следующую задачу: пусть процесс ВВОД вводит с клавиатуры очередное слово на русском языке, конец слова определяется по символу ENTER. Признаком завершения ввода является ввод подряд двух ENTER. Это слово заносится в некоторый буфер, например, текстовый файл. Процесс ПЕРЕВОД выбирает по одному слова из файла, переводит их на английский язык и показывает на экране пользователя. Запись в файл сделаем ограниченной, то есть разрешим записывать не более чем N слов. Тогда процесс писатель должен приостановиться, если файл уже заполнен. Процесс перевод, выбирающий слова из файла, наоборот, должен приостановиться, если слов в файле не осталось. Таким образом, нам потребуется два семафора: «КВОСЛОВ» (количество слов) и «КВОСВМЕСТА» (количество свободного места).

Процесс ВВОД:

Процесс ПЕРЕВОД:

если не определено КВОСЛОВ то определить семафор КВОСЛОВ КВОСЛОВ = 0 конец если если не определено КВОСВМЕСТА то определить семафор КВОСВМЕСТА КВОСВМЕСТА = N конец если открыть файл P S = ввод очередного символа с клавиатуры SL =”” повторять повторять пока S<>ENTER SL = SL+S конец повтора ввода символов если SL<>”” то начало_крит_секции уменьшить(КВОСВМЕСТА) увеличить(КВОСЛОВ) перейти в конец файла записать в файл P слово SL конец_крит_секции конец если конец повтора пока SL<>”” закрыть файл P

если не определено КВОСЛОВ то определить семафор КВОСЛОВ КВОСЛОВ = 0 конец если если не определено КВОСВМЕСТА то определить семафор КВОСВМЕСТА КВОСВМЕСТА = N конец если открыть файл P повторять пока ИСТИНА начало_крит_секции уменьшить(КВОСЛОВ) увеличить(КВОСВМЕСТА) перейти в начало файла прочесть слово передвинуть слова в файле вверх конец_крит_секции перевести слово вывести на экран конец повтора закрыть файл P

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