Geum.ru

The design of the unix operating system by Maurice J

Вид материалаРеферат
Подобный материал:
1   ...   47   48   49   50   51   52   53   54   55

│ ся в главном процессоре) │

│ выбрать процесс, имеющий наивысший приоритет │

│ среди загруженных в память; │

│ если (для запуска не подходит ни один из процессов) │

│ не загружать машину, переходящую в состояние про-│

│ стоя; │

│ /* из этого состояния машина выходит в результате│

│ * прерывания */ │

│ } │

│ убрать выбранный процесс из очереди готовых к выполне- │

│ нию; │

│ переключиться на контекст выбранного процесса, возобно- │

│ вить его выполнение; │

│ } │

L-------------------------------------------------------------

Рисунок 12.3. Алгоритм диспетчеризации


-------------------------------------------------------------┐

│ алгоритм syscall /* исправленный алгоритм вызова систем- │

│ * ной функции */ │

│ входная информация: код системной функции │

│ выходная информация: результат выполнения системной функции│

│ { │

│ если (работа ведется на подчиненном процессоре) │

│ { │

│ переустановить значение поля идентификации процессо-│

│ ра в соответствующей записи таблицы процессов; │

│ произвести переключение контекста; │

│ } │

│ выполнить обычный алгоритм реализации системной функции;│

│ перенастроить значение поля идентификации процессора, │

│ чтобы оно указывало на "любой" (подчиненный); │

│ если (на главном процессоре должны выполняться другие │

│ процессы) │

│ произвести переключение контекста; │

│ } │

L-------------------------------------------------------------

Рисунок 12.4. Алгоритм обработки обращения к системной функции

работу главного и заставить его переключить контекст немедленно,

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

Программа обработки прерываний по таймеру на подчиненном про-

цессоре следит за периодичностью перезапуска процессов, не допус-

кая монопольного использования процессора одной задачей. Кроме

того, каждую секунду эта программа выводит подчиненный процессор

из состояния бездействия (простоя). Подчиненный процессор выбира-

ет для выполнения процесс с наивысшим приоритетом среди тех про-

цессов, которые не нуждаются в главном процессоре.

Единственным местом, где целостность структур данных ядра еще

подвергается опасности, является алгоритм диспетчеризации, пос-

кольку он не предохраняет от выбора процесса на выполнение сразу

на двух процессорах. Например, если в конфигурации имеется один

главный процессор и два подчиненных, не исключена возможность то-

го, что оба подчиненных процессора выберут для выполнения в режи-

ме задачи один и тот же процесс. Если оба процессора начнут вы-

полнять его параллельно, осуществляя чтение и запись, это неиз-

бежно приведет к искажению содержимого адресного пространства

процесса.

Избежать возникновения этой проблемы можно двумя способами.

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

чиненных процессоров следует выполнять данный процесс. Если на

каждый процессор направлять несколько процессов, возникает необ-

ходимость в сбалансировании нагрузки (на один из процессоров наз-

начается большое количество процессов, в то время как другие про-

цессоры простаивают). Задача распределения нагрузки между процес-

сорами ложится на главное ядро. Во-вторых, ядро может проследить

за тем, чтобы в каждый момент времени в алгоритме диспетчеризации

принимал участие только один процессор, для этого используются

механизмы, подобные семафорам.

12.3 СЕМАФОРЫ


Поддержка системы UNIX в многопроцессорной конфигурации может

включать в себя разбиение ядра системы на критические участки,

параллельное выполнение которых на нескольких процессорах не до-

пускается. Такие системы предназначались для работы на машинах

AT&T 3B20A и IBM 370, для разбиения ядра использовались семафоры

(см. [Bach 84]). Нижеследующие рассуждения помогают понять суть

данной особенности. При ближайшем рассмотрении сразу же возникают

два вопроса: как использовать семафоры и где определить критичес-

кие участки.

Как уже говорилось в главе 2, если при выполнении критическо-

го участка программы процесс приостанавливается, для защиты

участка от посягательств со стороны других процессов алгоритмы

работы ядра однопроцессорной системы UNIX используют блокировку.

Механизм установления блокировки:

выполнять пока (блокировка установлена) /* операция проверки*/

приостановиться (до снятия блокировки);

установить блокировку;

механизм снятия блокировки:

снять блокировку;

вывести из состояния приостанова все процессы, приостановлен-

ные в результате блокировки;

Блокировки такого рода охватывают некоторые критические

участки, но не работают в многопроцессорных системах, что видно

из Рисунка 12.5. Предположим, что блокировка снята и что два про-


Процесс A/Процессор A Процесс B/Процессор B

----------------------------------------------------------

│ ----------------------------┐

│ │ Блокировка НЕ установлена │

│ L----------------------------

│

│

│ Проверяет, установлена Проверяет, установлена

│ ли блокировка ли блокировка

│ (нет) (нет)

t - + - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

│ Устанавливает Устанавливает

│ блокировку блокировку

│

│ Использует ресурс Использует ресурс

v

Время │ │

L------┐ --------

Опасность нарушения целостности

Рисунок 12.5. Конкуренция за установку блокировки в многопро-

цессорных системах

цесса на разных процессорах одновременно пытаются проверить ее

наличие и установить ее. В момент t они обнаруживают снятие бло-

кировки, устанавливают ее вновь, вступают в критический участок и

создают опасность нарушения целостности структур данных ядра. В

условии одновременности имеется отклонение: механизм не сработа-

ет, если перед тем, как процесс выполняет операцию проверки, ни

один другой процесс не выполнил операцию установления блокировки.

Если, например, после обнаружения снятия блокировки процессор A

обрабатывает прерывание и в этот момент процессор B выполняет

проверку и устанавливает блокировку, по выходе из прерывания про-

цессор A так же установит блокировку. Чтобы предотвратить возник-

новение подобной ситуации, нужно сделать так, чтобы процедура

блокирования была неделимой: проверку наличия блокировки и ее ус-

тановку следует объединить в одну операцию, чтобы в каждый момент

времени с блокировкой имел дело только один процесс.

12.3.1 Определение семафоров


Семафор представляет собой обрабатываемый ядром целочисленный

объект, для которого определены следующие элементарные (недели-

мые) операции:

* Инициализация семафора, в результате которой семафору присва-

ивается неотрицательное значение;

* Операция типа 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&T 3B20 - инструкция read and

clear (прочитать и очистить). При выполнении инструкции read and

clear процессор считывает содержимое ячейки памяти, очищает ее

(сбрасывает в 0) и по результатам сравнения первоначального со-

держимого с 0 устанавливает код завершения инструкции. Если ту же

инструкцию над той же ячейкой параллельно выполняет еще один про-

цессор, один из двух процессоров прочитает первоначальное содер-

жимое, а другой - 0: неделимость операции гарантируется аппарат-

ным путем. Таким образом, за счет использования данной инструкции

функцию Pprim можно было бы реализовать менее сложными средствами

(Рисунок 12.7). Процесс повторяет инструкцию read and clear в

цикле до тех пор, пока не будет считано значение, отличное от ну-

ля. Начальное значение компоненты семафора, связанной с блокиров-

кой, должно быть равно 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; │

│ /* продолжение на следующей странице */ │

L-------------------------------------------------------------


Рисунок 12.6. Реализация семафорной блокировки на Си

семафор используется для блокирования структуры данных, процесс,

обнаружив семафор заблокированным, приостанавливает свое выполне-

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

гого процесса и выполнить другую полезную работу. С помощью функ-

ций Pprim и Vprim можно реализовать более сложный набор семафор-

ных операций, соответствующий тому составу, который определен в

разделе 12.3.1.

Для начала дадим определение семафора как структуры, состоя-

щей из поля блокировки (управляющего доступом к семафору), значе-

ния семафора и очереди процессов, приостановленных по семафору.

Поле блокировки содержит информацию, открывающую во время выпол-

нения операций типа P и V доступ к другим полям структуры только

одному процессу. По завершении операции значение поля сбрасывает-

ся. Это значение определяет, разрешен ли процессу доступ к крити-

ческому участку, защищаемому семафором. В начале выполнения

алгоритма операции P (Рисунок 12.8) ядро с помощью функции Pprim

предоставляет процессу право исключительного доступа к семафору и

уменьшает значение семафора. Если семафор имеет неотрицательное

значение, текущий процесс получает доступ к критическому участку.

По завершении работы процесс сбрасывает блокировку семафора (с

помощью функции Vprim), открывая доступ к семафору для других

процессов, и возвращает признак успешного завершения. Если же в

результате уменьшения значение семафора становится отрицательным,

ядро приостанавливает выполнение процесса, используя алгоритм,


-------------------------------------------------------------┐

│ 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; │

│ } │

L-------------------------------------------------------------

Рисунок 12.6. Реализация семафорной блокировки на Си (про-

должение)

подобный алгоритму sleep (глава 6): основываясь на значении прио-

ритета, ядро проверяет поступившие сигналы, включает текущий про-

цесс в список приостановленных процессов, в котором последние

представлены в порядке поступления, и выполняет переключение кон-

текста. Операция V (Рисунок 12.9) получает исключительный доступ

к семафору через функцию Pprim и увеличивает значение семафора.

Если очередь приостановленных по семафору процессов непуста, ядро

выбирает из нее первый процесс и переводит его в состояние "го-

товности к запуску".

Операции P и V по своему действию похожи на функции sleep и

wakeup. Главное различие между ними состоит в том, что семафор

является структурой данных, тогда как используемый функциями

sleep и wakeup адрес представляет собой всего лишь число. Если

начальное значение семафора - нулевое, при выполнении операции P

над семафором процесс всегда приостанавливается, поэтому операция

P может заменять функцию sleep. Операция V, тем не менее, выводит

из состояния приостанова только один процесс, тогда как однопро-

цессорная функция wakeup возобновляет все процессы, приостанов-

ленные по адресу, связанному с событием.

С точки зрения семантики использование функции wakeup означа-

ет: данное системное условие более не удовлетворяется, следова-

тельно, все приостановленные по условию процессы должны выйти из

состояния приостанова. Так, например, процессы, приостановленные

в связи с занятостью буфера, не должны дальше пребывать в этом

состоянии, если буфер больше не используется, поэтому они возоб-

--------------------------------------------------------┐


│ 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; │

│ } │

L--------------------------------------------------------

Рисунок 12.7. Операции над семафором, использующие инструкцию

read and clear

новляются ядром. Еще один пример: если несколько процессов выво-

дят данные на терминал с помощью функции write, терминальный

драйвер может перевести их в состояние приостанова в связи с не-

возможностью обработки больших объемов информации. Позже, когда

драйвер будет готов к приему следующей порции данных, он возобно-

вит все приостановленные им процессы. Использование операций P и

V в тех случаях, когда устанавливающие блокировку процессы полу-

чают доступ к ресурсу поочередно, а все остальные процессы - в

порядке поступления запросов, является более предпочтительным. В

сравнении с однопроцессорной процедурой блокирования (sleep-lock)

данная схема обычно выигрывает, так как если при наступлении со-

бытия все процессы возобновляются, большинство из них может вновь

наткнуться на блокировку и снова перейти в состояние приостанова.

С другой стороны, в тех случаях, когда требуется вывести из сос-

тояния приостанова все процессы одновременно, использование опе-

раций P и V представляет известную сложность.

Если операция возвращает значение семафора, является ли она

эквивалентной функции wakeup ?

while (value(semaphore) < 0)

V(semaphore);

Если вмешательства со стороны других процессов нет, ядро пов-

торяет цикл до тех пор, пока значение семафора не станет больше

или равно 0, ибо это означает, что в состоянии приостанова по се-

мафору нет больше ни одного процесса. Тем не менее, нельзя исклю-

-------------------------------------------------------------┐

│ алгоритм P /* операция над семафором типа P */ │

│ входная информация: (1) семафор │

│ (2) приоритет │

│ выходная информация: 0 - в случае нормального завершения │

│ -1 - в случае аварийного выхода из │

│ состояния приостанова по сигналу, при-│

│ нятому в режиме ядра │

│ { │

│ Pprim(semaphore.lock); │

│ уменьшить (semaphore.value); │

│ если (semaphore.value >= 0) │

│ { │

│ Vprim(semaphore.lock); │

│ вернуть (0); │

│ } │

│ /* следует перейти в состояние приостанова */ │

│ если (проверяются сигналы) │

│ { │

│ если (имеется сигнал, прерывающий нахождение в сос- │

│ тоянии приостанова) │

│ { │

│ увеличить (semaphore.value); │

│ если (сигнал принят в режиме ядра) │

│ { │

│ Vprim(semaphore.lock); │

│ вернуть (-1); │