Лекции по предмету Операционные системы
средствами
соответствующие программные примитивы, которые бы запрещали прерывания на
протяжении всей операции проверки и установки.
Реализация критических секций с использованием блокирующих переменных имеет
существенный недостаток: в течение времени, когда один процесс находится в
критической секции, другой процесс, которому требуется тот же ресурс, будет
выполнять рутинные действия по опросу блокирующей переменной, бесполезно
тратя процессорное время. Для устранения таких ситуаций может быть
использован так называемый аппарат событий. С помощью этого средства могут
решаться не только проблемы взаимного исключения, но и более общие задачи
синхронизации процессов. В разных операционных системах аппарат событий
реализуется по своему, но в любом случае используются системные функции
аналогичного назначения, которые условно назовем WAIT(x) и POST(x), где x -
идентификатор некоторого события. На рисунке 2.5 показан фрагмент алгоритма
процесса, использующего эти функции. Если ресурс занят, то процесс не
выполняет циклический опрос, а вызывает системную функцию WAIT(D), здесь D
обозначает событие, заключающееся в освобождении ресурса D. Функция WAIT(D)
переводит активный процесс в состояние ОЖИДАНИЕ и делает отметку в его
дескрипторе о том, что процесс ожидает события D. Процесс, который в это
время использует ресурс D, после выхода из критической секции выполняет
системную функцию POST(D), в результате чего операционная система
просматривает очередь ожидающих процессов и переводит процесс, ожидающий
события D, в состояние ГОТОВНОСТЬ.
Обобщающее средство синхронизации процессов предложил Дейкстра, который
ввел два новых примитива. В абстрактной форме эти примитивы, обозначаемые P
и V, оперируют над целыми неотрицательными переменными, называемыми
семафорами. Пусть S такой семафор. Операции определяются следующим образом:
V(S) : переменная S увеличивается на 1 одним неделимым действием; выборка,
инкремент и запоминание не могут быть прерваны, и к S нет доступа другим
процессам во время выполнения этой операции.
P(S) : уменьшение S на 1, если это возможно. Если S=0, то невозможно
уменьшить S и остаться в области целых неотрицательных значений, в этом
случае процесс, вызывающий P-операцию, ждет, пока это уменьшение станет
возможным. Успешная проверка и уменьшение также является неделимой
операцией.
[pic]
Рис. 2.5. Реализация критической секции с использованием системных
функций WAIT(D) и POST(D)
В частном случае, когда семафор 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(); /* Обработать запись */
}
}
Тупики
Приведенный выше пример поможет нам проиллюстрировать еще одну проблему
синхронизации - взаимные блокировки, называемые также дедлоками
(deadlocks), клинчами (clinch) или тупиками. Если переставить местами
операции P(e) и P(b) в программе "писателе", то при некотором стечении
обстоятельств эти два процесса могут взаимно заблокировать друг друга.
Действительно, пусть "писатель" первым войдет в критическую секцию и
обнаружит отсутствие свободных буферов; он начнет ждать, когда "читатель"
возьмет очередную запись из буфера, но "читатель" не сможет этого сделать,
так как для этого необходимо войти в критическую секцию, вход в которую
заблокирован процессом "писателем".
Рассмотрим еще один пример тупика. Пусть двум процессам, выполняющимся в
режиме мультипрограммирования, для выполнения их работы нужно два ресурса,
например, принтер и диск. На рисунке 2.6,а показаны фрагменты
соответствующих программ. И пусть после того, как процесс А занял принтер
(установил блокирующую переменную), он был прерван. Управление получил
процесс В, который сначала занял диск, но при выполнении следующей команды
был заблокирован, так как принтер оказался уже занятым процессом А.
Управление снова получил процесс А, который в соответствии со своей
программой сделал попытку занять диск и был заблокирован: диск уже
распределен процессу В. В таком положении процессы А и В могут находиться
сколь угодно долго.
В зависимости от соотношения скоростей процессов, они могут либо совершенно
независимо использовать разделяемые ресурсы (г), либо образовывать очереди
к разделяемым ресурсам (в), либо взаимно блокировать друг друга (б).
Тупиковые ситуации надо отличать от простых очередей, хотя и те и другие
возникают при совместном использовании ресурсов и внешне выглядят похоже:
процесс приостанавливается и ждет освобождения ресурса. Однако очередь -
это нормальное явление, неотъемлемый признак высокого коэффициента
использования ресурсов при случайном поступлении запросов. Она возникает
тогда, когда ресурс недоступен в данный момент, но через некоторое время он
освобождается, и процесс продолжает свое выполнение. Тупик же, что видно из
его названия, является в некотором роде неразрешимой ситуацией.
[pic]
Рис. 2.6. (a) фрагменты программ А и В, разделяющих принтер и диск;
(б) взаимная блокировка (клинч);(в) очередь к разделяемому диску;
(г) независимое использование ресурсов
В рассмотренных примерах тупик был образован двумя процессами, но взаимно
блокировать друг друга могут и большее число процессов.
Проблема тупиков включает в себя следующие задачи:
. предотвращение тупиков,
. распознавание тупиков,
. восстановление системы после тупиков.
Тупики могут быть предотвращены на стадии написания программ, то есть
программы должны быть написаны таким образом, чтобы тупик не мог возникнуть
ни при каком соотношении взаимных скоростей процессов. Так, если бы в
предыдущем примере процесс А и процесс В запрашивали ресурсы в одинаковой
последовательности, то тупик был бы в принципе невозможен. Второй подход к
предотвращению тупиков называется динамическим и заключается в
использовании определенных правил при назначении ресурсов процессам,
например, ресурсы могут выделяться в определенной последовательности, общей
для всех процессов.
В некоторых случаях, когда тупиковая ситуация образована многими
процессами, использующими много ресурсов, распознавание тупика является
нетривиальной задачей. Существуют формальные, программно-реализованные
методы распознавания тупиков, основанные на ведении таблиц распределения
ресурсов и таблиц запросов к занятым ресурсам. Анализ этих таблиц позволяет
обнаружить взаимные блокировки.
Если же тупиковая ситуация возникла, то не обязательно снимать с выполнения
все заблокированные процессы. Можно снять только часть из них, при этом
освобождаются ресурсы, ожидаемые остальными процессами, можно вернуть
некоторые процессы в область свопинга, можно совершить "откат" некоторых
процессов до так называемой контрольной точки, в которой запоминается вся
информация, необходимая для восстановления выполнения программы с данного
места. Контрольные точки расставляются в программе в местах, после которых
возможно возникновение тупика.
Из всего вышесказанного ясно, что использовать семафоры нужно очень
осторожно, так как одна незначительная ошибка может привести к останову
системы. Для того, чтобы облегчить написание корректных прог
| |  скачать работу |
Лекции по предмету Операционные системы |
