Страница:
алгоритм schedule_process (модифицированный)
входная информация: отсутствует
выходная информация: отсутствует
{
do while (для запуска не будет выбран один из процессов) {
if (работа ведется на главном процессоре)
for (всех процессов в очереди готовых к выполнению)
выбрать процесс, имеющий наивысший приоритет среди загруженных в память;
else /* работа ведется на подчиненном процессоре */
for (тех процессов в очереди, которые не нуждаются в главном процессоре)
выбрать процесс, имеющий наивысший приоритет среди загруженных в память;
if (для запуска не подходит ни один из процессов)
не загружать машину, переходящую в состояние простоя; /* из этого состояния машина выходит в результате прерывания */
}
убрать выбранный процесс из очереди готовых к выполнению;
переключиться на контекст выбранного процесса, возобновить его выполнение;
}
Рисунок 12.3. Алгоритм диспетчеризации
алгоритм syscall /* исправленный алгоритм вызова системной функции */
входная информация: код системной функции
выходная информация: результат выполнения системной функции
{
if (работа ведется на подчиненном процессоре) {
переустановить значение поля идентификации процессора в соответствующей записи таблицы процессов;
произвести переключение контекста;
}
выполнить обычный алгоритм реализации системной функции;
перенастроить значение поля идентификации процессора, чтобы оно указывало на "любой" (подчиненный);
if (на главном процессоре должны выполняться другие процессы)
произвести переключение контекста;
}
Рисунок 12.4. Алгоритм обработки обращения к системной функции
Программа обработки прерываний по таймеру на подчиненном процессоре следит за периодичностью перезапуска процессов, не допуская монопольного использования процессора одной задачей. Кроме того, каждую секунду эта программа выводит подчиненный процессор из состояния бездействия (простоя). Подчиненный процессор выбирает для выполнения процесс с наивысшим приоритетом среди тех процессов, которые не нуждаются в главном процессоре.
Единственным местом, где целостность структур данных ядра еще подвергается опасности, является алгоритм диспетчеризации, поскольку он не предохраняет от выбора процесса на выполнение сразу на двух процессорах. Например, если в конфигурации имеется один главный процессор и два подчиненных, не исключена возможность того, что оба подчиненных процессора выберут для выполнения в режиме задачи один и тот же процесс. Если оба процессора начнут выполнять его параллельно, осуществляя чтение и запись, это неизбежно приведет к искажению содержимого адресного пространства процесса.
Избежать возникновения этой проблемы можно двумя способами. Во-первых, главный процессор может явно указать, на каком из подчиненных процессоров следует выполнять данный процесс. Если на каждый процессор направлять несколько процессов, возникает необходимость в сбалансировании нагрузки (на один из процессоров назначается большое количество процессов, в то время как другие процессоры простаивают). Задача распределения нагрузки между процессорами ложится на главное ядро. Во-вторых, ядро может проследить за тем, чтобы в каждый момент времени в алгоритме диспетчеризации принимал участие только один процессор, для этого используются механизмы, подобные семафорам.
12.3 СЕМАФОРЫ
Поддержка системы UNIX в многопроцессорной конфигурации может включать в себя разбиение ядра системы на критические участки, параллельное выполнение которых на нескольких процессорах не допускается. Такие системы предназначались для работы на машинах AT amp;T 3B20A и IBM 370, для разбиения ядра использовались семафоры (см. [Bach 84]). Нижеследующие рассуждения помогают понять суть данной особенности. При ближайшем рассмотрении сразу же возникают два вопроса: как использовать семафоры и где определить критические участки.
Как уже говорилось в главе 2, если при выполнении критического участка программы процесс приостанавливается, для защиты участка от посягательств со стороны других процессов алгоритмы работы ядра однопроцессорной системы UNIX используют блокировку. Механизм установления блокировки:
выполнять пока (блокировка установлена) /* операция проверки */
приостановиться (до снятия блокировки);
установить блокировку;
механизм снятия блокировки:
снять блокировку;
вывести из состояния приостанова все процессы, приостановленные в результате блокировки;
Рисунок 12.5. Конкуренция за установку блокировки в многопроцессорных системах
Блокировки такого рода охватывают некоторые критические участки, но не работают в многопроцессорных системах, что видно из Рисунка 12.5. Предположим, что блокировка снята и что два процесса на разных процессорах одновременно пытаются проверить ее наличие и установить ее. В момент t они обнаруживают снятие блокировки, устанавливают ее вновь, вступают в критический участок и создают опасность нарушения целостности структур данных ядра. В условии одновременности имеется отклонение: механизм не сработает, если перед тем, как процесс выполняет операцию проверки, ни один другой процесс не выполнил операцию установления блокировки. Если, например, после обнаружения снятия блокировки процессор A обрабатывает прерывание и в этот момент процессор B выполняет проверку и устанавливает блокировку, по выходе из прерывания процессор A так же установит блокировку. Чтобы предотвратить возникновение подобной ситуации, нужно сделать так, чтобы процедура блокирования была неделимой: проверку наличия блокировки и ее установку следует объединить в одну операцию, чтобы в каждый момент времени с блокировкой имел дело только один процесс.
Как уже говорилось в главе 2, если при выполнении критического участка программы процесс приостанавливается, для защиты участка от посягательств со стороны других процессов алгоритмы работы ядра однопроцессорной системы UNIX используют блокировку. Механизм установления блокировки:
выполнять пока (блокировка установлена) /* операция проверки */
приостановиться (до снятия блокировки);
установить блокировку;
механизм снятия блокировки:
снять блокировку;
вывести из состояния приостанова все процессы, приостановленные в результате блокировки;
Блокировки такого рода охватывают некоторые критические участки, но не работают в многопроцессорных системах, что видно из Рисунка 12.5. Предположим, что блокировка снята и что два процесса на разных процессорах одновременно пытаются проверить ее наличие и установить ее. В момент t они обнаруживают снятие блокировки, устанавливают ее вновь, вступают в критический участок и создают опасность нарушения целостности структур данных ядра. В условии одновременности имеется отклонение: механизм не сработает, если перед тем, как процесс выполняет операцию проверки, ни один другой процесс не выполнил операцию установления блокировки. Если, например, после обнаружения снятия блокировки процессор A обрабатывает прерывание и в этот момент процессор B выполняет проверку и устанавливает блокировку, по выходе из прерывания процессор A так же установит блокировку. Чтобы предотвратить возникновение подобной ситуации, нужно сделать так, чтобы процедура блокирования была неделимой: проверку наличия блокировки и ее установку следует объединить в одну операцию, чтобы в каждый момент времени с блокировкой имел дело только один процесс.
12.3.1 Определение семафоров
Семафор представляет собой обрабатываемый ядром целочисленный объект, для которого определены следующие элементарные (неделимые) операции:
• Инициализация семафора, в результате которой семафору присваивается неотрицательное значение;
• Операция типа P, уменьшающая значение семафора. Если значение семафора опускается ниже нулевой отметки, выполняющий операцию процесс приостанавливает свою работу;
• Операция типа V, увеличивающая значение семафора. Если значение семафора в результате операции становится больше или равно 0, один из процессов, приостановленных во время выполнения операции P, выходит из состояния приостанова;
• Условная операция типа P, сокращенно CP (conditional P), уменьшающая значение семафора и возвращающая логическое значение "истина" в том случае, когда значение семафора остается положительным. Если в результате операции значение семафора должно стать отрицательным или нулевым, никаких действий над ним не производится и операция возвращает логическое значение "ложь".
Определенные таким образом семафоры, безусловно, никак не связаны с семафорами пользовательского уровня, рассмотренными в главе 11.
• Инициализация семафора, в результате которой семафору присваивается неотрицательное значение;
• Операция типа P, уменьшающая значение семафора. Если значение семафора опускается ниже нулевой отметки, выполняющий операцию процесс приостанавливает свою работу;
• Операция типа V, увеличивающая значение семафора. Если значение семафора в результате операции становится больше или равно 0, один из процессов, приостановленных во время выполнения операции P, выходит из состояния приостанова;
• Условная операция типа P, сокращенно CP (conditional P), уменьшающая значение семафора и возвращающая логическое значение "истина" в том случае, когда значение семафора остается положительным. Если в результате операции значение семафора должно стать отрицательным или нулевым, никаких действий над ним не производится и операция возвращает логическое значение "ложь".
Определенные таким образом семафоры, безусловно, никак не связаны с семафорами пользовательского уровня, рассмотренными в главе 11.
12.3.2 Реализация семафоров
Дийкстра [Dijkstra 65] показал, что семафоры можно реализовать без использования специальных машинных инструкций. На Рисунке 12.6 представлены реализующие семафоры функции, написанные на языке Си. Функция Pprim блокирует семафор по результатам проверки значений, содержащихся в массиве val; каждый процессор в системе управляет значением одного элемента массива. Прежде чем заблокировать семафор, процессор проверяет, не заблокирован ли уже семафор другими процессорами (соответствующие им элементы в массиве val тогда имеют значения, равные 2), а также не предпринимаются ли попытки в данный момент заблокировать семафор со стороны процессоров с более низким кодом идентификации (соответствующие им элементы имеют значения, равные 1). Если любое из условий выполняется, процессор переустанавливает значение своего элемента в 1 и повторяет попытку. Когда функция Pprim открывает внешний цикл, переменная цикла имеет значение, на единицу превышающее код идентификации того процессора, который использовал ресурс последним, тем самым гарантируется, что ни один из процессоров не может монопольно завладеть ресурсом (в качестве доказательства сошлемся на [Dijkstra 65] и [Coffman 73]). Функция Vprim освобождает семафор и открывает для других процессоров возможность получения исключительного доступа к ресурсу путем очистки соответствующего текущему процессору элемента в массиве val и перенастройки значения lastid. Чтобы защитить ресурс, следует выполнить следующий набор команд:
Pprim(семафор);
команды использования ресурса;
Vprim(семафор);
В большинстве машин имеется набор элементарных (неделимых) инструкций,
реализующих операцию блокирования более дешевыми средствами, ибо циклы, входящие в функцию Pprim, работают медленно и снижают производительность системы. Так, например, в машинах серии IBM 370 поддерживается инструкция compare and swap (сравнить и переставить), в машине AT amp;T 3B20 — инструкция read and clear (прочитать и очистить). При выполнении инструкции read and clear процессор считывает содержимое ячейки памяти, очищает ее (сбрасывает в 0) и по результатам сравнения первоначального содержимого с 0 устанавливает код завершения инструкции. Если ту же инструкцию над той же ячейкой параллельно выполняет еще один процессор, один из двух процессоров прочитает первоначальное содержимое, а другой — 0: неделимость операции гарантируется аппаратным путем. Таким образом, за счет использования данной инструкции функцию Pprim можно было бы реализовать менее сложными средствами (Рисунок 12.7). Процесс повторяет инструкцию read and clear в цикле до тех пор, пока не будет считано значение, отличное от нуля. Начальное значение компоненты семафора, связанной с блокировкой, должно быть равно 1.
Как таковую, данную семафорную конструкцию нельзя реализовать в составе ядра операционной системы, поскольку работающий с ней процесс не выходит из цикла, пока не достигнет своей цели. Если семафор используется для блокирования структуры данных, процесс, обнаружив семафор заблокированным, приостанавливает свое выполнение, чтобы ядро имело возможность переключиться на контекст другого процесса и выполнить другую полезную работу. С помощью функций Pprim и Vprim можно реализовать более сложный набор семафорных операций, соответствующий тому составу, который определен в разделе 12.3.1.
struct semaphore {
int val[NUMPROCS]; /* замок 1 элемент на каждый процессор */
int lastid; /* идентификатор процессора, получившего семафор последним */
};
int procid; /* уникальный идентификатор процессора */
int lastid; /* идентификатор процессора, получившего семафор последним */
INIT(semaphore)
struct semaphore semaphore;
{
int i;
for (i = 0; i ‹ NUMPROCS; i++) semaphore.val[i] = 0;
}
Pprim(semaphore)
struct semaphore semaphore;
{
int i, first;
loop:
first = lastid;
semaphore.val[procid] = 1;
forloop:
for (i = first; i ‹ NUMPROCS; i++) {
if (i == procid) {
semaphore.val[i] = 2;
for (i = 1; i ‹ NUMPROCS; i++) if (i != procid && semaphore.val[i] == 2) goto loop;
lastid = procid;
return; /* успешное завершение, ресурс можно использовать */
}
else if (semaphore.val[i]) goto loop;
}
first = 1;
goto forloop;
}
Vprim(semaphore)
struct semaphore semaphore;
{
lastid = (procid + 1) % NUMPROCS;
/* на следующий процессор */
semaphore.val[procid] = 0;
}
Рисунок 12.6. Реализация семафорной блокировки на Си
Для начала дадим определение семафора как структуры, состоящей из поля блокировки (управляющего доступом к семафору), значения семафора и очереди процессов, приостановленных по семафору. Поле блокировки содержит информацию, открывающую во время выполнения операций типа P и V доступ к другим полям структуры только одному процессу. По завершении операции значение поля сбрасывается. Это значение определяет, разрешен ли процессу доступ к критическому участку, защищаемому семафором. В начале выполнения алгоритма операции P (Рисунок 12.8) ядро с помощью функции Pprim предоставляет процессу право исключительного доступа к семафору и уменьшает значение семафора. Если семафор имеет неотрицательное значение, текущий процесс получает доступ к критическому участку. По завершении работы процесс сбрасывает блокировку семафора (с помощью функции Vprim), открывая доступ к семафору для других процессов, и возвращает признак успешного завершения. Если же в результате уменьшения значение семафора становится отрицательным, ядро приостанавливает выполнение процесса, используя алгоритм, подобный алгоритму sleep (глава 6): основываясь на значении приоритета, ядро проверяет поступившие сигналы, включает текущий процесс в список приостановленных процессов, в котором последние представлены в порядке поступления, и выполняет переключение контекста. Операция V (Рисунок 12.9) получает исключительный доступ к семафору через функцию Pprim и увеличивает значение семафора. Если очередь приостановленных по семафору процессов непуста, ядро выбирает из нее первый процесс и переводит его в состояние "готовности к запуску".
Операции P и V по своему действию похожи на функции sleep и wakeup. Главное различие между ними состоит в том, что семафор является структурой данных, тогда как используемый функциями sleep и wakeup адрес представляет собой всего лишь число. Если начальное значение семафора — нулевое, при выполнении операции P над семафором процесс всегда приостанавливается, поэтому операция P может заменять функцию sleep. Операция V, тем не менее, выводит из состояния приостанова только один процесс, тогда как однопроцессорная функция wakeup возобновляет все процессы, приостановленные по адресу, связанному с событием.
С точки зрения семантики использование функции wakeup означает: данное системное условие более не удовлетворяется, следовательно, все приостановленные по условию процессы должны выйти из состояния приостанова. Так, например, процессы, приостановленные в связи с занятостью буфера, не должны дальше пребывать в этом состоянии, если буфер больше не используется, поэтому они возобновляются ядром. Еще один пример: если несколько процессов выводят данные на терминал с помощью функции write, терминальный драйвер может перевести их в состояние приостанова в связи с невозможностью обработки больших объемов информации. Позже, когда драйвер будет готов к приему следующей порции данных, он возобновит все приостановленные им процессы. Использование операций P и V в тех случаях, когда устанавливающие блокировку процессы получают доступ к ресурсу поочередно, а все остальные процессы — в порядке поступления запросов, является более предпочтительным. В сравнении с однопроцессорной процедурой блокирования (sleep-lock) данная схема обычно выигрывает, так как если при наступлении события все процессы возобновляются, большинство из них может вновь наткнуться на блокировку и снова перейти в состояние приостанова. С другой стороны, в тех случаях, когда требуется вывести из состояния приостанова все процессы одновременно, использование операций P и V представляет известную сложность.
struct semaphore {
int lock;
};
Init(semaphore)
struct semaphore semaphore;
{
semaphore.lock = 1;
}
Pprim(semaphore)
struct semaphore semaphore;
{
while (read_and_clear(semaphore.lock));
}
Vprim(semaphore)
struct semaphore semaphore;
{
semaphore.lock = 1;
}
Рисунок 12.7. Операции над семафором, использующие инструкцию read_and_clear
Если операция возвращает значение семафора, является ли она эквивалентной функции wakeup?
while (value(semaphore) ‹ 0) V(semaphore);
Если вмешательства со стороны других процессов нет, ядро повторяет цикл до тех пор, пока значение семафора не станет больше или равно 0, ибо это означает, что в состоянии приостанова по семафору нет больше ни одного процесса. Тем не менее, нельзя исключить и такую возможность, что сразу после того, как процесс A при тестировании семафора на одноименном процессоре обнаружил нулевое значение семафора, процесс B на своем процессоре выполняет операцию P, уменьшая значение семафора до -1 (Рисунок 12.10). Процесс A продолжит свое выполнение, думая, что им возобновлены все приостановленные по семафору процессы. Таким образом, цикл выполнения операции не дает гарантии возобновления всех приостановленных процессов, поскольку он не является элементарным.
алгоритм P /* операция над семафором типа P */
входная информация:
(1) семафор
(2) приоритет
выходная информация:
0 — в случае нормального завершения
-1 — в случае аварийного выхода из состояния приостанова по сигналу, принятому в режиме ядра
{
Pprim(semaphore.lock);
уменьшить (semaphore.value);
if (semaphore.value ›= 0) {
Vprim(semaphore.lock);
return (0);
}
/* следует перейти в состояние приостанова */
if (проверяются сигналы) {
if (имеется сигнал, прерывающий нахождение в состоянии приостанова) {
увеличить (semaphore.value);
if (сигнал принят в режиме ядра) {
Vprim(semaphore.lock);
return(-1);
}
else {
Vprim(semaphore.lock);
longjmp;
}
}
}
поставить процесс в конец списка приостановленных по семафору;
Vprim(semaphore.lock);
выполнить переключение контекста;
проверить сигналы (см. выше);
return(0);
}
Рисунок 12.8. Алгоритм выполнения операции P
Рассмотрим еще один феномен, связанный с использованием семафоров в однопроцессорной системе. Предположим, что два процесса, A и B, конкурируют за семафор. Процесс A обнаруживает, что семафор свободен и что процесс B приостановлен; значение семафора равно -1. Когда с помощью операции V процесс A освобождает семафор, он выводит тем самым процесс B из состояния приостанова и вновь делает значение семафора нулевым. Теперь предположим, что процесс A, по-прежнему выполняясь в режиме ядра, пытается снова заблокировать семафор. Производя операцию P, процесс приостановится, поскольку семафор имеет нулевое значение, несмотря на то, что ресурс пока свободен. Системе придется "раскошелиться" на дополнительное переключение контекста. С другой стороны, если бы блокировка была реализована на основе однопроцессорной схемы (sleep-lock), процесс A получил бы право на повторное использование ресурса, поскольку за это время ни один из процессов не смог бы заблокировать его. Для этого случая схема sleep-lock более подходит, чем схема с использованием семафоров.
алгоритм V /* операция над семафором типа V */
входная информация: адрес семафора
выходная информация: отсутствует
{
Pprim(semaphore.lock);
увеличить (semaphore.value);
if (semaphore.value ‹= 0) {
удалить из списка процессов, приостановленных по семафору, первый по счету процесс;
перевести его в состояние готовности к запуску;
}
Vprim(semaphore.lock);
}
Рисунок 12.9. Алгоритм выполнения операции V
Когда блокируются сразу несколько семафоров, очередность блокирования должна исключать возникновение тупиковых ситуаций. В качестве примера рассмотрим два семафора, A и B, и два алгоритма, требующих одновременной блокировки семафоров. Если бы алгоритмы устанавливали блокировку на семафоры в обратном порядке, как следует из Рисунка 12.11, последовало бы возникновение тупиковой ситуации; процесс A на одноименном процессоре захватывает семафор SA, в то время как процесс B на своем процессоре захватывает семафор SB. Процесс A пытается захватить и семафор SB, но в результате операции P переходит в состояние приостанова, поскольку значение семафора SB не превышает 0. То же самое происходит с процессом B, когда последний пытается захватить семафор SA. Ни тот, ни другой процессы продолжаться уже не могут.
Для предотвращения возникновения подобных ситуаций используются соответствующие алгоритмы обнаружения опасности взаимной блокировки, устанавливающие наличие опасной ситуации и ликвидирующие ее. Тем не менее, использование таких алгоритмов "утяжеляет" ядро. Поскольку число ситуаций, в которых процесс должен одновременно захватывать несколько семафоров, довольно ограничено, легче было бы реализовать алгоритмы, предупреждающие возникновение тупиковых ситуаций еще до того, как они будут иметь место. Если, к примеру, какой-то набор семафоров всегда блокируется в одном и том же порядке, тупиковая ситуация никогда не возникнет. Но в том случае, когда захвата семафоров в обратном порядке избежать не удается, операция CP предотвратит возникновение тупиковой ситуации (см. Рисунок 12.12): если операция завершится неудачно, процесс B освободит свои ресурсы, дабы избежать взаимной блокировки, и позже запустит алгоритм на выполнение повторно, скорее всего тогда, когда процесс A завершит работу с ресурсом.
Чтобы предупредить одновременное обращение процессов к ресурсу, программа обработки прерываний, казалось бы, могла воспользоваться семафором, но из-за того, что она не может приостанавливать свою работу (см. главу 6), использовать операцию P в этой программе нельзя. Вместо этого можно использовать "циклическую блокировку" (spin lock) и не переходить в состояние приостанова, как в следующем примере:
Рисунок 12.10. Неудачное имитация функции wakeup при использовании операции V
Рисунок 12.11. Возникновение тупиковой ситуации из-за смены очередности блокирования
Рисунок 12.12. Использование операции P условного типа для предотвращения взаимной блокировки
Операция повторяется в цикле до тех пор, пока значение семафора не превысит 0; программа обработки прерываний не приостанавливается и цикл завершается только тогда, когда значение семафора станет положительным, после чего это значение будет уменьшено операцией CP.
Чтобы предотвратить ситуацию взаимной блокировки, ядру нужно запретить все прерывания, выполняющие "циклическую блокировку". Иначе выполнение процесса, захватившего семафор, будет прервано еще до того, как он сможет освободить семафор; если программа обработки прерываний попытается захватить этот семафор, используя "циклическую блокировку", ядро заблокирует само себя. В качестве примера обратимся к Рисунку 12.13. В момент возникновения прерывания значение семафора не превышает 0, поэтому результатом выполнения операции CP всегда будет "ложь". Проблема решается путем запрещения всех прерываний на то время, пока семафор захвачен процессом.
Рисунок 12.13. Взаимная блокировка при выполнении программы обработки прерывания
Pprim(семафор);
команды использования ресурса;
Vprim(семафор);
В большинстве машин имеется набор элементарных (неделимых) инструкций,
реализующих операцию блокирования более дешевыми средствами, ибо циклы, входящие в функцию Pprim, работают медленно и снижают производительность системы. Так, например, в машинах серии IBM 370 поддерживается инструкция compare and swap (сравнить и переставить), в машине AT amp;T 3B20 — инструкция read and clear (прочитать и очистить). При выполнении инструкции read and clear процессор считывает содержимое ячейки памяти, очищает ее (сбрасывает в 0) и по результатам сравнения первоначального содержимого с 0 устанавливает код завершения инструкции. Если ту же инструкцию над той же ячейкой параллельно выполняет еще один процессор, один из двух процессоров прочитает первоначальное содержимое, а другой — 0: неделимость операции гарантируется аппаратным путем. Таким образом, за счет использования данной инструкции функцию Pprim можно было бы реализовать менее сложными средствами (Рисунок 12.7). Процесс повторяет инструкцию read and clear в цикле до тех пор, пока не будет считано значение, отличное от нуля. Начальное значение компоненты семафора, связанной с блокировкой, должно быть равно 1.
Как таковую, данную семафорную конструкцию нельзя реализовать в составе ядра операционной системы, поскольку работающий с ней процесс не выходит из цикла, пока не достигнет своей цели. Если семафор используется для блокирования структуры данных, процесс, обнаружив семафор заблокированным, приостанавливает свое выполнение, чтобы ядро имело возможность переключиться на контекст другого процесса и выполнить другую полезную работу. С помощью функций Pprim и Vprim можно реализовать более сложный набор семафорных операций, соответствующий тому составу, который определен в разделе 12.3.1.
struct semaphore {
int val[NUMPROCS]; /* замок 1 элемент на каждый процессор */
int lastid; /* идентификатор процессора, получившего семафор последним */
};
int procid; /* уникальный идентификатор процессора */
int lastid; /* идентификатор процессора, получившего семафор последним */
INIT(semaphore)
struct semaphore semaphore;
{
int i;
for (i = 0; i ‹ NUMPROCS; i++) semaphore.val[i] = 0;
}
Pprim(semaphore)
struct semaphore semaphore;
{
int i, first;
loop:
first = lastid;
semaphore.val[procid] = 1;
forloop:
for (i = first; i ‹ NUMPROCS; i++) {
if (i == procid) {
semaphore.val[i] = 2;
for (i = 1; i ‹ NUMPROCS; i++) if (i != procid && semaphore.val[i] == 2) goto loop;
lastid = procid;
return; /* успешное завершение, ресурс можно использовать */
}
else if (semaphore.val[i]) goto loop;
}
first = 1;
goto forloop;
}
Vprim(semaphore)
struct semaphore semaphore;
{
lastid = (procid + 1) % NUMPROCS;
/* на следующий процессор */
semaphore.val[procid] = 0;
}
Рисунок 12.6. Реализация семафорной блокировки на Си
Для начала дадим определение семафора как структуры, состоящей из поля блокировки (управляющего доступом к семафору), значения семафора и очереди процессов, приостановленных по семафору. Поле блокировки содержит информацию, открывающую во время выполнения операций типа P и V доступ к другим полям структуры только одному процессу. По завершении операции значение поля сбрасывается. Это значение определяет, разрешен ли процессу доступ к критическому участку, защищаемому семафором. В начале выполнения алгоритма операции P (Рисунок 12.8) ядро с помощью функции Pprim предоставляет процессу право исключительного доступа к семафору и уменьшает значение семафора. Если семафор имеет неотрицательное значение, текущий процесс получает доступ к критическому участку. По завершении работы процесс сбрасывает блокировку семафора (с помощью функции Vprim), открывая доступ к семафору для других процессов, и возвращает признак успешного завершения. Если же в результате уменьшения значение семафора становится отрицательным, ядро приостанавливает выполнение процесса, используя алгоритм, подобный алгоритму sleep (глава 6): основываясь на значении приоритета, ядро проверяет поступившие сигналы, включает текущий процесс в список приостановленных процессов, в котором последние представлены в порядке поступления, и выполняет переключение контекста. Операция V (Рисунок 12.9) получает исключительный доступ к семафору через функцию Pprim и увеличивает значение семафора. Если очередь приостановленных по семафору процессов непуста, ядро выбирает из нее первый процесс и переводит его в состояние "готовности к запуску".
Операции P и V по своему действию похожи на функции sleep и wakeup. Главное различие между ними состоит в том, что семафор является структурой данных, тогда как используемый функциями sleep и wakeup адрес представляет собой всего лишь число. Если начальное значение семафора — нулевое, при выполнении операции P над семафором процесс всегда приостанавливается, поэтому операция P может заменять функцию sleep. Операция V, тем не менее, выводит из состояния приостанова только один процесс, тогда как однопроцессорная функция wakeup возобновляет все процессы, приостановленные по адресу, связанному с событием.
С точки зрения семантики использование функции wakeup означает: данное системное условие более не удовлетворяется, следовательно, все приостановленные по условию процессы должны выйти из состояния приостанова. Так, например, процессы, приостановленные в связи с занятостью буфера, не должны дальше пребывать в этом состоянии, если буфер больше не используется, поэтому они возобновляются ядром. Еще один пример: если несколько процессов выводят данные на терминал с помощью функции write, терминальный драйвер может перевести их в состояние приостанова в связи с невозможностью обработки больших объемов информации. Позже, когда драйвер будет готов к приему следующей порции данных, он возобновит все приостановленные им процессы. Использование операций P и V в тех случаях, когда устанавливающие блокировку процессы получают доступ к ресурсу поочередно, а все остальные процессы — в порядке поступления запросов, является более предпочтительным. В сравнении с однопроцессорной процедурой блокирования (sleep-lock) данная схема обычно выигрывает, так как если при наступлении события все процессы возобновляются, большинство из них может вновь наткнуться на блокировку и снова перейти в состояние приостанова. С другой стороны, в тех случаях, когда требуется вывести из состояния приостанова все процессы одновременно, использование операций P и V представляет известную сложность.
struct semaphore {
int lock;
};
Init(semaphore)
struct semaphore semaphore;
{
semaphore.lock = 1;
}
Pprim(semaphore)
struct semaphore semaphore;
{
while (read_and_clear(semaphore.lock));
}
Vprim(semaphore)
struct semaphore semaphore;
{
semaphore.lock = 1;
}
Рисунок 12.7. Операции над семафором, использующие инструкцию read_and_clear
Если операция возвращает значение семафора, является ли она эквивалентной функции wakeup?
while (value(semaphore) ‹ 0) V(semaphore);
Если вмешательства со стороны других процессов нет, ядро повторяет цикл до тех пор, пока значение семафора не станет больше или равно 0, ибо это означает, что в состоянии приостанова по семафору нет больше ни одного процесса. Тем не менее, нельзя исключить и такую возможность, что сразу после того, как процесс A при тестировании семафора на одноименном процессоре обнаружил нулевое значение семафора, процесс B на своем процессоре выполняет операцию P, уменьшая значение семафора до -1 (Рисунок 12.10). Процесс A продолжит свое выполнение, думая, что им возобновлены все приостановленные по семафору процессы. Таким образом, цикл выполнения операции не дает гарантии возобновления всех приостановленных процессов, поскольку он не является элементарным.
алгоритм P /* операция над семафором типа P */
входная информация:
(1) семафор
(2) приоритет
выходная информация:
0 — в случае нормального завершения
-1 — в случае аварийного выхода из состояния приостанова по сигналу, принятому в режиме ядра
{
Pprim(semaphore.lock);
уменьшить (semaphore.value);
if (semaphore.value ›= 0) {
Vprim(semaphore.lock);
return (0);
}
/* следует перейти в состояние приостанова */
if (проверяются сигналы) {
if (имеется сигнал, прерывающий нахождение в состоянии приостанова) {
увеличить (semaphore.value);
if (сигнал принят в режиме ядра) {
Vprim(semaphore.lock);
return(-1);
}
else {
Vprim(semaphore.lock);
longjmp;
}
}
}
поставить процесс в конец списка приостановленных по семафору;
Vprim(semaphore.lock);
выполнить переключение контекста;
проверить сигналы (см. выше);
return(0);
}
Рисунок 12.8. Алгоритм выполнения операции P
Рассмотрим еще один феномен, связанный с использованием семафоров в однопроцессорной системе. Предположим, что два процесса, A и B, конкурируют за семафор. Процесс A обнаруживает, что семафор свободен и что процесс B приостановлен; значение семафора равно -1. Когда с помощью операции V процесс A освобождает семафор, он выводит тем самым процесс B из состояния приостанова и вновь делает значение семафора нулевым. Теперь предположим, что процесс A, по-прежнему выполняясь в режиме ядра, пытается снова заблокировать семафор. Производя операцию P, процесс приостановится, поскольку семафор имеет нулевое значение, несмотря на то, что ресурс пока свободен. Системе придется "раскошелиться" на дополнительное переключение контекста. С другой стороны, если бы блокировка была реализована на основе однопроцессорной схемы (sleep-lock), процесс A получил бы право на повторное использование ресурса, поскольку за это время ни один из процессов не смог бы заблокировать его. Для этого случая схема sleep-lock более подходит, чем схема с использованием семафоров.
алгоритм V /* операция над семафором типа V */
входная информация: адрес семафора
выходная информация: отсутствует
{
Pprim(semaphore.lock);
увеличить (semaphore.value);
if (semaphore.value ‹= 0) {
удалить из списка процессов, приостановленных по семафору, первый по счету процесс;
перевести его в состояние готовности к запуску;
}
Vprim(semaphore.lock);
}
Рисунок 12.9. Алгоритм выполнения операции V
Когда блокируются сразу несколько семафоров, очередность блокирования должна исключать возникновение тупиковых ситуаций. В качестве примера рассмотрим два семафора, A и B, и два алгоритма, требующих одновременной блокировки семафоров. Если бы алгоритмы устанавливали блокировку на семафоры в обратном порядке, как следует из Рисунка 12.11, последовало бы возникновение тупиковой ситуации; процесс A на одноименном процессоре захватывает семафор SA, в то время как процесс B на своем процессоре захватывает семафор SB. Процесс A пытается захватить и семафор SB, но в результате операции P переходит в состояние приостанова, поскольку значение семафора SB не превышает 0. То же самое происходит с процессом B, когда последний пытается захватить семафор SA. Ни тот, ни другой процессы продолжаться уже не могут.
Для предотвращения возникновения подобных ситуаций используются соответствующие алгоритмы обнаружения опасности взаимной блокировки, устанавливающие наличие опасной ситуации и ликвидирующие ее. Тем не менее, использование таких алгоритмов "утяжеляет" ядро. Поскольку число ситуаций, в которых процесс должен одновременно захватывать несколько семафоров, довольно ограничено, легче было бы реализовать алгоритмы, предупреждающие возникновение тупиковых ситуаций еще до того, как они будут иметь место. Если, к примеру, какой-то набор семафоров всегда блокируется в одном и том же порядке, тупиковая ситуация никогда не возникнет. Но в том случае, когда захвата семафоров в обратном порядке избежать не удается, операция CP предотвратит возникновение тупиковой ситуации (см. Рисунок 12.12): если операция завершится неудачно, процесс B освободит свои ресурсы, дабы избежать взаимной блокировки, и позже запустит алгоритм на выполнение повторно, скорее всего тогда, когда процесс A завершит работу с ресурсом.
Чтобы предупредить одновременное обращение процессов к ресурсу, программа обработки прерываний, казалось бы, могла воспользоваться семафором, но из-за того, что она не может приостанавливать свою работу (см. главу 6), использовать операцию P в этой программе нельзя. Вместо этого можно использовать "циклическую блокировку" (spin lock) и не переходить в состояние приостанова, как в следующем примере:
Операция повторяется в цикле до тех пор, пока значение семафора не превысит 0; программа обработки прерываний не приостанавливается и цикл завершается только тогда, когда значение семафора станет положительным, после чего это значение будет уменьшено операцией CP.
Чтобы предотвратить ситуацию взаимной блокировки, ядру нужно запретить все прерывания, выполняющие "циклическую блокировку". Иначе выполнение процесса, захватившего семафор, будет прервано еще до того, как он сможет освободить семафор; если программа обработки прерываний попытается захватить этот семафор, используя "циклическую блокировку", ядро заблокирует само себя. В качестве примера обратимся к Рисунку 12.13. В момент возникновения прерывания значение семафора не превышает 0, поэтому результатом выполнения операции CP всегда будет "ложь". Проблема решается путем запрещения всех прерываний на то время, пока семафор захвачен процессом.
12.3.3 Примеры алгоритмов
В данном разделе мы рассмотрим четыре алгоритма ядра, реализованных с использованием семафоров. Алгоритм выделения буфера иллюстрирует сложную схему блокирования, на примере алгоритма wait показана синхронизация выполнения процессов, схема блокирования драйверов реализует изящный подход к решению данной проблемы, и наконец, метод решения проблемы холостой работы процессора показывает, что нужно сделать, чтобы избежать конкуренции между процессами.
12.3.3.1 Выделение буфера
Обратимся еще раз к алгоритму getblk, рассмотренному нами в главе 3. Алгоритм работает с тремя структурами данных: заголовком буфера, хеш-очередью буферов и списком свободных буферов. Ядро связывает семафор со всеми экземплярами каждой структуры. Другими словами, если у ядра имеются в распоряжении 200 буферов, заголовок каждого из них включает в себя семафор, используемый для захвата буфера; когда процесс выполняет над семафором операцию P, другие процессы, тоже пожелавшие захватить буфер, приостанавливаются до тех пор, пока первый процесс не исполнит операцию V. У каждой хеш-очереди буферов также имеется семафор, блокирующий доступ к очереди. В однопроцессорной системе блокировка хеш-очереди не нужна, ибо процесс никогда не переходит в состояние приостанова, оставляя очередь в несогласованном (неупорядоченном) виде. В многопроцессорной системе, тем не менее, возможны ситуации, когда с одной и той же хеш-очередью работают два процесса; в каждый момент времени семафор открывает доступ к очереди только для одного процесса. По тем же причинам и список свободных буферов нуждается в семафоре для защиты содержащейся в нем информации от искажения.
алгоритм getblk /* многопроцессорная версия */
входная информация:
номер файловой системы
номер блока
выходная информация: захваченный буфер, предназначенный для обработки содержимого блока
{
алгоритм getblk /* многопроцессорная версия */
входная информация:
номер файловой системы
номер блока
выходная информация: захваченный буфер, предназначенный для обработки содержимого блока
{