Страница:
В классической постановке для системы UNIX предполагается использование
однопроцессорной архитектуры, состоящей из одного ЦП, памяти и периферийных
устройств. Многопроцессорная архитектура, напротив, включает в себя два и
более ЦП, совместно использующих общую память и периферийные устройства (Ри-
сунок 12.1), располагая большими возможностями в увеличении производитель-
ности системы, связанными с одновременным исполнением процессов на разных
ЦП. Каждый ЦП функционирует независимо от других, но все они работают с од-
ним и тем же ядром операционной системы. Поведение процессов в такой системе
ничем не отличается от поведения в однопроцессорной системе - с сохранением
семантики обращения к каждой системной функции - но при этом они могут отк-
рыто перемещаться с одного процессора на другой. Хотя, к сожалению, это не
приводит к снижению затрат процессорного времени, связанного с выполнением
процесса. Отдельные многопроцессорные системы называются системами с присое-
диненными процессорами, поскольку в них периферийные устройства доступны не
для всех процессоров. За исключением особо оговоренных случаев, в настоящей
главе не проводится никаких различий между системами с присоединенными про-
цессорами и остальными классами многопроцессорных систем.
Параллельная работа нескольких процессоров в режиме ядра по выполнению
различных процессов создает ряд проблем, связанных с сохранением целостности
данных и решаемых благодаря использованию соответствующих механизмов защиты.
Ниже будет показано, почему классический вариант системы UNIX не может быть
принят в многопроцессорных системах без внесения необходимых изменений, а
также будут рассмотрены два варианта, предназначенные для работы в указанной
среде.
+-----------+ +-----------+ +-----------+
| Процессор | | Процессор | | Процессор |
| 1 | | 2 | ........... | n |
+-----+-----+ +-----+-----+ +-----+-----+
----------+-------+-------+--------------+------------+-----------
+---+----+ +-----------+-------------+
| Память | | Периферийные устройства |
+--------+ +-------------------------+
Рисунок 12.1. Многопроцессорная конфигурация
В главе 2 мы говорили о том, что защита целостности структур данных ядра
системы UNIX обеспечивается двумя способами: ядро не может выгрузить один
процесс и переключиться на контекст другого, если работа производится в ре-
жиме ядра, кроме того, если при выполнении критического участка программы
обработчик возникающих прерываний может повредить структуры данных ядра, все
возникающие прерывания тщательно маскируются. В многопроцессорной системе,
однако, если два и более процессов выполняются одновременно в режиме ядра на
разных процессорах, нарушение целостности ядра может произойти даже несмотря
на принятие защитных мер, с другой стороны, в однопроцессорной системе впол-
не достаточных.
362
+-------------------------------------------------------+
| struct queue { |
| |
| } *bp, *bp1; |
| bp1->forp=bp->forp; |
| bp1->backp=bp; |
| bp->forp=bp1; |
| /* рассмотрите возможность переключения контекста в |
| * этом месте */ |
| bp1->forp->backp=bp1; |
+-------------------------------------------------------+
Рисунок 12.2. Включение буфера в список с двойными указателями
В качестве примера рассмотрим фрагмент программы из главы 2 (Рисунок
12.2), в котором новая структура данных (указатель bp1) помещается в список
после существующей структуры (указатель bp). Предположим, что этот фрагмент
выполняется одновременно двумя процессами на разных ЦП, причем процессор A
пытается поместить вслед за структурой bp структуру bpA, а процессор B -
структуру bpB. По поводу сопоставления быстродействия процессоров не прихо-
дится делать никаких предположений: возможен даже наихудший случай, когда
процессор B исполняет 4 команды языка Си, прежде чем процессор A исполнит
одну. Пусть, например, выполнение программы процессором A приостанавливается
в связи с обработкой прерывания. В результате, даже несмотря на блокировку
остальных прерываний, целостность данных будет поставлена под угрозу (в гла-
ве 2 этот момент уже пояснялся).
Ядро обязано удостовериться в том, что такого рода нарушение не сможет
произойти. Если вопрос об опасности возникновения нарушения целостности ос-
тавить открытым, как бы редко подобные нарушения ни случались, ядро утратит
свою неуязвимость и его поведение станет непредсказуемым. Избежать этого
можно тремя способами:
1. Исполнять все критические операции на одном процессоре, опираясь на
стандартные методы сохранения целостности данных в однопроцессорной сис-
теме;
2. Регламентировать доступ к критическим участкам программы, используя эле-
менты блокирования ресурсов;
3. Устранить конкуренцию за использование структур данных путем соответст-
вующей переделки алгоритмов.
Первые два способа здесь мы рассмотрим подробнее, третьему способу будет
посвящено отдельное упражнение.
Систему с двумя процессорами, один из которых - главный (master) - может
работать в режиме ядра, а другой - подчиненный (slave) - только в режиме за-
дачи, впервые реализовал на машинах типа VAX 11/780 Гобл (см. [Goble 81]).
Эта система, реализованная вначале на двух машинах, получила свое дальнейшее
развитие в системах с одним главным и несколькими подчиненными процессорами.
Главный процессор несет ответственность за обработку всех обращений к опера-
ционной системе и всех прерываний. Подчиненные процессоры ведают выполнением
процессов в режиме задачи и информируют главный процессор о всех производи-
мых обращениях к системным функциям.
Выбор процессора, на котором будет выполняться данный процесс, произво-
дится в соответствии с алгоритмом диспетчеризации (Рисунок 12.3). В соответ-
ствующей записи таблицы процессов появляется новое поле, в которое записыва-
ется идентификатор выбранного процессора; предположим для простоты, что он
показывает, является ли процессор главным или подчиненным. Когда процесс
363
производит обращение к системной функции, выполняясь на подчиненном процес-
соре, подчиненное ядро переустанавливает значение поля идентификации процес-
сора таким образом, чтобы оно указывало на главный процессор, и переключает
контекст на другие процессы (Рисунок 12.4). Главное ядро запускает на выпол-
нение процесс с наивысшим приоритетом среди тех процессов, которые должны
выполняться на главном процессоре. Когда выполнение системной функции завер-
шается, поле идентификации процессора перенастраивается обратно, и процесс
вновь возвращается на подчиненный процессор.
Если процессы должны выполняться на главном процессоре, желательно, что-
бы главный процессор обрабатывал их как можно скорее и не заставлял их ждать
своей очереди чересчур долго. Похожая мотивировка приводится в объяснение
выгрузки процесса из памяти в однопроцессорной системе после выхода из сис-
темной функции с освобождением соответствующих ресурсов для выполнения более
насущных счетных операций. Если в тот момент, когда подчиненный процессор
делает запрос на исполнение системной функции, главный процесс выполняется в
режиме задачи, его выполнение будет продолжаться до следующего переключения
контекста. Главный процессор реагировал бы гораздо быстрее, если бы подчи-
ненный процессор устанавливал при этом глобальный флаг; проверяя установку
флага во время обработки очередного прерывания по таймеру, главный процессор
произвел бы в итоге переключение контекста максимум через один таймерный
тик. С другой стороны, подчиненный процессор мог бы прервать работу главного
и заставить его переключить контекст немедленно, но данная возможность тре-
бует специальной аппаратной реализации.
+------------------------------------------------------------+
| алгоритм schedule_process (модифицированный) |
| входная информация: отсутствует |
| выходная информация: отсутствует |
| { |
| выполнять пока (для запуска не будет выбран один из про-|
| цессов) |
| { |
| если (работа ведется на главном процессоре) |
| для (всех процессов в очереди готовых к выполне- |
| нию) |
| выбрать процесс, имеющий наивысший приоритет |
| среди загруженных в память; |
| в противном случае /* работа ведется на подчинен- |
| * ном процессоре */ |
| для (тех процессов в очереди, которые не нуждают-|
| ся в главном процессоре) |
| выбрать процесс, имеющий наивысший приоритет |
| среди загруженных в память; |
| если (для запуска не подходит ни один из процессов) |
| не загружать машину, переходящую в состояние про-|
| стоя; |
| /* из этого состояния машина выходит в результате|
| * прерывания */ |
| } |
| убрать выбранный процесс из очереди готовых к выполне- |
| нию; |
| переключиться на контекст выбранного процесса, возобно- |
| вить его выполнение; |
| } |
+------------------------------------------------------------+
Рисунок 12.3. Алгоритм диспетчеризации
364
+------------------------------------------------------------+
| алгоритм syscall /* исправленный алгоритм вызова систем- |
| * ной функции */ |
| входная информация: код системной функции |
| выходная информация: результат выполнения системной функции|
| { |
| если (работа ведется на подчиненном процессоре) |
| { |
| переустановить значение поля идентификации процессо-|
| ра в соответствующей записи таблицы процессов; |
| произвести переключение контекста; |
| } |
| выполнить обычный алгоритм реализации системной функции;|
| перенастроить значение поля идентификации процессора, |
| чтобы оно указывало на "любой" (подчиненный); |
| если (на главном процессоре должны выполняться другие |
| процессы) |
| произвести переключение контекста; |
| } |
+------------------------------------------------------------+
Рисунок 12.4. Алгоритм обработки обращения к системной функции
Программа обработки прерываний по таймеру на подчиненном процессоре сле-
дит за периодичностью перезапуска процессов, не допуская монопольного ис-
пользования процессора одной задачей. Кроме того, каждую секунду эта прог-
рамма выводит подчиненный процессор из состояния бездействия (простоя). Под-
чиненный процессор выбирает для выполнения процесс с наивысшим приоритетом
среди тех процессов, которые не нуждаются в главном процессоре.
Единственным местом, где целостность структур данных ядра еще подверга-
ется опасности, является алгоритм диспетчеризации, поскольку он не предохра-
няет от выбора процесса на выполнение сразу на двух процессорах. Например,
если в конфигурации имеется один главный процессор и два подчиненных, не ис-
ключена возможность того, что оба подчиненных процессора выберут для выпол-
нения в режиме задачи один и тот же процесс. Если оба процессора начнут вы-
полнять его параллельно, осуществляя чтение и запись, это неизбежно приведет
к искажению содержимого адресного пространства процесса.
Избежать возникновения этой проблемы можно двумя способами. Во-первых,
главный процессор может явно указать, на каком из подчиненных процессоров
следует выполнять данный процесс. Если на каждый процессор направлять нес-
колько процессов, возникает необходимость в сбалансировании нагрузки (на
один из процессоров назначается большое количество процессов, в то время как
другие процессоры простаивают). Задача распределения нагрузки между процес-
сорами ложится на главное ядро. Во-вторых, ядро может проследить за тем,
чтобы в каждый момент времени в алгоритме диспетчеризации принимал участие
только один процессор, для этого используются механизмы, подобные семафорам.
Поддержка системы UNIX в многопроцессорной конфигурации может включать в
себя разбиение ядра системы на критические участки, параллельное выполнение
которых на нескольких процессорах не допускается. Такие системы предназнача-
лись для работы на машинах AT&T 3B20A и IBM 370, для разбиения ядра исполь-
зовались семафоры (см. [Bach 84]). Нижеследующие рассуждения помогают понять
суть данной особенности. При ближайшем рассмотрении сразу же возникают два
вопроса: как использовать семафоры и где определить критические участки.
Как уже говорилось в главе 2, если при выполнении критического участка
программы процесс приостанавливается, для защиты участка от посягательств со
365
стороны других процессов алгоритмы работы ядра однопроцессорной системы UNIX
используют блокировку. Механизм установления блокировки:
выполнять пока (блокировка установлена) /* операция проверки */
приостановиться (до снятия блокировки);
установить блокировку;
механизм снятия блокировки:
снять блокировку;
вывести из состояния приостанова все процессы, приостановленные в ре-
зультате блокировки;
Процесс A/Процессор A Процесс B/Процессор B
+---------------------------------------------------------
| +---------------------------+
| | Блокировка НЕ установлена |
| - +---------------------------+ -
| - -
| - -
| Проверяет, установлена Проверяет, установлена
| ли блокировка ли блокировка
| (нет) (нет)
t - + - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
| Устанавливает Устанавливает
| блокировку блокировку
|
| Использует ресурс Использует ресурс
v ^ ^
Время | |
+------+ +------+
Опасность нарушения целостности
Рисунок 12.5. Конкуренция за установку блокировки в многопро-
цессорных системах
Блокировки такого рода охватывают некоторые критические участки, но не
работают в многопроцессорных системах, что видно из Рисунка 12.5. Предполо-
жим, что блокировка снята и что два процесса на разных процессорах одновре-
менно пытаются проверить ее наличие и установить ее. В момент t они обнару-
живают снятие блокировки, устанавливают ее вновь, вступают в критический
участок и создают опасность нарушения целостности структур данных ядра. В
условии одновременности имеется отклонение: механизм не сработает, если пе-
ред тем, как процесс выполняет операцию проверки, ни один другой процесс не
выполнил операцию установления блокировки. Если, например, после обнаружения
снятия блокировки процессор A обрабатывает прерывание и в этот момент про-
цессор B выполняет проверку и устанавливает блокировку, по выходе из преры-
вания процессор A так же установит блокировку. Чтобы предотвратить возникно-
вение подобной ситуации, нужно сделать так, чтобы процедура блокирования бы-
ла неделимой: проверку наличия блокировки и ее установку следует объединить
в одну операцию, чтобы в каждый момент времени с блокировкой имел дело толь-
ко один процесс.
Семафор представляет собой обрабатываемый ядром целочисленный объект,
для которого определены следующие элементарные (неделимые) операции:
* Инициализация семафора, в результате которой семафору присваивается не-
отрицательное значение;
* Операция типа P, уменьшающая значение семафора. Если значение семафора
366
опускается ниже нулевой отметки, выполняющий операцию процесс приоста-
навливает свою работу;
* Операция типа V, увеличивающая значение семафора. Если значение семафора
в результате операции становится больше или равно 0, один из процессов,
приостановленных во время выполнения операции P, выходит из состояния
приостанова;
* Условная операция типа P, сокращенно CP (conditional P), уменьшающая
значение семафора и возвращающая логическое значение "истина" в том слу-
чае, когда значение семафора остается положительным. Если в результате
операции значение семафора должно стать отрицательным или нулевым, ника-
ких действий над ним не производится и операция возвращает логическое
значение "ложь".
Определенные таким образом семафоры, безусловно, никак не связаны с се-
мафорами пользовательского уровня, рассмотренными в главе 11.
Дийкстра [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.
367
Как таковую, данную семафорную конструкцию нельзя реализовать в составе
ядра операционной системы, поскольку работающий с ней процесс не выходит из
цикла, пока не достигнет своей цели. Если
+------------------------------------------------------------+
| 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; |
| /* продолжение на следующей странице */ |
+------------------------------------------------------------+
Рисунок 12.6. Реализация семафорной блокировки на Си
семафор используется для блокирования структуры данных, процесс, обнаружив
семафор заблокированным, приостанавливает свое выполнение, чтобы ядро имело
возможность переключиться на контекст другого процесса и выполнить другую
полезную работу. С помощью функций Pprim и Vprim можно реализовать более
сложный набор семафорных операций, соответствующий тому составу, который оп-
ределен в разделе 12.3.1.
Для начала дадим определение семафора как структуры, состоящей из поля
блокировки (управляющего доступом к семафору), значения семафора и очереди
процессов, приостановленных по семафору. Поле блокировки содержит информа-
цию, открывающую во время выполнения операций типа P и V доступ к другим по-
лям структуры только одному процессу. По завершении операции значение поля
сбрасывается. Это значение определяет, разрешен ли процессу доступ к крити-
ческому участку, защищаемому семафором. В начале выполнения алгоритма опера-
ции P (Рисунок 12.8) ядро с помощью функции Pprim предоставляет процессу
право исключительного доступа к семафору и уменьшает значение семафора. Если
семафор имеет неотрицательное значение, текущий процесс получает доступ к
критическому участку. По завершении работы процесс сбрасывает блокировку се-
мафора (с помощью функции Vprim), открывая доступ к семафору для других про-
цессов, и возвращает признак успешного завершения. Если же в результате
уменьшения значение семафора становится отрицательным, ядро приостанавливает
выполнение процесса, используя алгоритм,
368
+------------------------------------------------------------+
| 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. Реализация семафорной блокировки на Си (продолжение)
подобный алгоритму sleep (глава 6): основываясь на значении приоритета, ядро
проверяет поступившие сигналы, включает текущий процесс в список приостанов-
ленных процессов, в котором последние представлены в порядке поступления, и
выполняет переключение контекста. Операция V (Рисунок 12.9) получает исклю-
чительный доступ к семафору через функцию Pprim и увеличивает значение сема-
фора. Если очередь приостановленных по семафору процессов непуста, ядро вы-
бирает из нее первый процесс и переводит его в состояние "готовности к за-
пуску".
Операции P и V по своему действию похожи на функции sleep и wakeup.
Главное различие между ними состоит в том, что семафор является структурой
данных, тогда как используемый функциями sleep и wakeup адрес представляет
собой всего лишь число. Если начальное значение семафора - нулевое, при вы-
полнении операции P над семафором процесс всегда приостанавливается, поэтому
операция P может заменять функцию sleep. Операция V, тем не менее, выводит
из состояния приостанова только один процесс, тогда как однопроцессорная
функция wakeup возобновляет все процессы, приостановленные по адресу, свя-
занному с событием.
С точки зрения семантики использование функции wakeup означает: данное
системное условие более не удовлетворяется, следовательно, все приостанов-
ленные по условию процессы должны выйти из состояния приостанова. Так, нап-
ример, процессы, приостановленные в связи с занятостью буфера, не должны
дальше пребывать в этом состоянии, если буфер больше не используется, поэто-
му они возоб-
новляются ядром. Еще один пример: если несколько процессов выводят данные на
терминал с помощью функции write, терминальный драйвер может перевести их в
369
однопроцессорной архитектуры, состоящей из одного ЦП, памяти и периферийных
устройств. Многопроцессорная архитектура, напротив, включает в себя два и
более ЦП, совместно использующих общую память и периферийные устройства (Ри-
сунок 12.1), располагая большими возможностями в увеличении производитель-
ности системы, связанными с одновременным исполнением процессов на разных
ЦП. Каждый ЦП функционирует независимо от других, но все они работают с од-
ним и тем же ядром операционной системы. Поведение процессов в такой системе
ничем не отличается от поведения в однопроцессорной системе - с сохранением
семантики обращения к каждой системной функции - но при этом они могут отк-
рыто перемещаться с одного процессора на другой. Хотя, к сожалению, это не
приводит к снижению затрат процессорного времени, связанного с выполнением
процесса. Отдельные многопроцессорные системы называются системами с присое-
диненными процессорами, поскольку в них периферийные устройства доступны не
для всех процессоров. За исключением особо оговоренных случаев, в настоящей
главе не проводится никаких различий между системами с присоединенными про-
цессорами и остальными классами многопроцессорных систем.
Параллельная работа нескольких процессоров в режиме ядра по выполнению
различных процессов создает ряд проблем, связанных с сохранением целостности
данных и решаемых благодаря использованию соответствующих механизмов защиты.
Ниже будет показано, почему классический вариант системы UNIX не может быть
принят в многопроцессорных системах без внесения необходимых изменений, а
также будут рассмотрены два варианта, предназначенные для работы в указанной
среде.
+-----------+ +-----------+ +-----------+
| Процессор | | Процессор | | Процессор |
| 1 | | 2 | ........... | n |
+-----+-----+ +-----+-----+ +-----+-----+
----------+-------+-------+--------------+------------+-----------
+---+----+ +-----------+-------------+
| Память | | Периферийные устройства |
+--------+ +-------------------------+
Рисунок 12.1. Многопроцессорная конфигурация
В главе 2 мы говорили о том, что защита целостности структур данных ядра
системы UNIX обеспечивается двумя способами: ядро не может выгрузить один
процесс и переключиться на контекст другого, если работа производится в ре-
жиме ядра, кроме того, если при выполнении критического участка программы
обработчик возникающих прерываний может повредить структуры данных ядра, все
возникающие прерывания тщательно маскируются. В многопроцессорной системе,
однако, если два и более процессов выполняются одновременно в режиме ядра на
разных процессорах, нарушение целостности ядра может произойти даже несмотря
на принятие защитных мер, с другой стороны, в однопроцессорной системе впол-
не достаточных.
362
+-------------------------------------------------------+
| struct queue { |
| |
| } *bp, *bp1; |
| bp1->forp=bp->forp; |
| bp1->backp=bp; |
| bp->forp=bp1; |
| /* рассмотрите возможность переключения контекста в |
| * этом месте */ |
| bp1->forp->backp=bp1; |
+-------------------------------------------------------+
Рисунок 12.2. Включение буфера в список с двойными указателями
В качестве примера рассмотрим фрагмент программы из главы 2 (Рисунок
12.2), в котором новая структура данных (указатель bp1) помещается в список
после существующей структуры (указатель bp). Предположим, что этот фрагмент
выполняется одновременно двумя процессами на разных ЦП, причем процессор A
пытается поместить вслед за структурой bp структуру bpA, а процессор B -
структуру bpB. По поводу сопоставления быстродействия процессоров не прихо-
дится делать никаких предположений: возможен даже наихудший случай, когда
процессор B исполняет 4 команды языка Си, прежде чем процессор A исполнит
одну. Пусть, например, выполнение программы процессором A приостанавливается
в связи с обработкой прерывания. В результате, даже несмотря на блокировку
остальных прерываний, целостность данных будет поставлена под угрозу (в гла-
ве 2 этот момент уже пояснялся).
Ядро обязано удостовериться в том, что такого рода нарушение не сможет
произойти. Если вопрос об опасности возникновения нарушения целостности ос-
тавить открытым, как бы редко подобные нарушения ни случались, ядро утратит
свою неуязвимость и его поведение станет непредсказуемым. Избежать этого
можно тремя способами:
1. Исполнять все критические операции на одном процессоре, опираясь на
стандартные методы сохранения целостности данных в однопроцессорной сис-
теме;
2. Регламентировать доступ к критическим участкам программы, используя эле-
менты блокирования ресурсов;
3. Устранить конкуренцию за использование структур данных путем соответст-
вующей переделки алгоритмов.
Первые два способа здесь мы рассмотрим подробнее, третьему способу будет
посвящено отдельное упражнение.
Систему с двумя процессорами, один из которых - главный (master) - может
работать в режиме ядра, а другой - подчиненный (slave) - только в режиме за-
дачи, впервые реализовал на машинах типа VAX 11/780 Гобл (см. [Goble 81]).
Эта система, реализованная вначале на двух машинах, получила свое дальнейшее
развитие в системах с одним главным и несколькими подчиненными процессорами.
Главный процессор несет ответственность за обработку всех обращений к опера-
ционной системе и всех прерываний. Подчиненные процессоры ведают выполнением
процессов в режиме задачи и информируют главный процессор о всех производи-
мых обращениях к системным функциям.
Выбор процессора, на котором будет выполняться данный процесс, произво-
дится в соответствии с алгоритмом диспетчеризации (Рисунок 12.3). В соответ-
ствующей записи таблицы процессов появляется новое поле, в которое записыва-
ется идентификатор выбранного процессора; предположим для простоты, что он
показывает, является ли процессор главным или подчиненным. Когда процесс
363
производит обращение к системной функции, выполняясь на подчиненном процес-
соре, подчиненное ядро переустанавливает значение поля идентификации процес-
сора таким образом, чтобы оно указывало на главный процессор, и переключает
контекст на другие процессы (Рисунок 12.4). Главное ядро запускает на выпол-
нение процесс с наивысшим приоритетом среди тех процессов, которые должны
выполняться на главном процессоре. Когда выполнение системной функции завер-
шается, поле идентификации процессора перенастраивается обратно, и процесс
вновь возвращается на подчиненный процессор.
Если процессы должны выполняться на главном процессоре, желательно, что-
бы главный процессор обрабатывал их как можно скорее и не заставлял их ждать
своей очереди чересчур долго. Похожая мотивировка приводится в объяснение
выгрузки процесса из памяти в однопроцессорной системе после выхода из сис-
темной функции с освобождением соответствующих ресурсов для выполнения более
насущных счетных операций. Если в тот момент, когда подчиненный процессор
делает запрос на исполнение системной функции, главный процесс выполняется в
режиме задачи, его выполнение будет продолжаться до следующего переключения
контекста. Главный процессор реагировал бы гораздо быстрее, если бы подчи-
ненный процессор устанавливал при этом глобальный флаг; проверяя установку
флага во время обработки очередного прерывания по таймеру, главный процессор
произвел бы в итоге переключение контекста максимум через один таймерный
тик. С другой стороны, подчиненный процессор мог бы прервать работу главного
и заставить его переключить контекст немедленно, но данная возможность тре-
бует специальной аппаратной реализации.
+------------------------------------------------------------+
| алгоритм schedule_process (модифицированный) |
| входная информация: отсутствует |
| выходная информация: отсутствует |
| { |
| выполнять пока (для запуска не будет выбран один из про-|
| цессов) |
| { |
| если (работа ведется на главном процессоре) |
| для (всех процессов в очереди готовых к выполне- |
| нию) |
| выбрать процесс, имеющий наивысший приоритет |
| среди загруженных в память; |
| в противном случае /* работа ведется на подчинен- |
| * ном процессоре */ |
| для (тех процессов в очереди, которые не нуждают-|
| ся в главном процессоре) |
| выбрать процесс, имеющий наивысший приоритет |
| среди загруженных в память; |
| если (для запуска не подходит ни один из процессов) |
| не загружать машину, переходящую в состояние про-|
| стоя; |
| /* из этого состояния машина выходит в результате|
| * прерывания */ |
| } |
| убрать выбранный процесс из очереди готовых к выполне- |
| нию; |
| переключиться на контекст выбранного процесса, возобно- |
| вить его выполнение; |
| } |
+------------------------------------------------------------+
Рисунок 12.3. Алгоритм диспетчеризации
364
+------------------------------------------------------------+
| алгоритм syscall /* исправленный алгоритм вызова систем- |
| * ной функции */ |
| входная информация: код системной функции |
| выходная информация: результат выполнения системной функции|
| { |
| если (работа ведется на подчиненном процессоре) |
| { |
| переустановить значение поля идентификации процессо-|
| ра в соответствующей записи таблицы процессов; |
| произвести переключение контекста; |
| } |
| выполнить обычный алгоритм реализации системной функции;|
| перенастроить значение поля идентификации процессора, |
| чтобы оно указывало на "любой" (подчиненный); |
| если (на главном процессоре должны выполняться другие |
| процессы) |
| произвести переключение контекста; |
| } |
+------------------------------------------------------------+
Рисунок 12.4. Алгоритм обработки обращения к системной функции
Программа обработки прерываний по таймеру на подчиненном процессоре сле-
дит за периодичностью перезапуска процессов, не допуская монопольного ис-
пользования процессора одной задачей. Кроме того, каждую секунду эта прог-
рамма выводит подчиненный процессор из состояния бездействия (простоя). Под-
чиненный процессор выбирает для выполнения процесс с наивысшим приоритетом
среди тех процессов, которые не нуждаются в главном процессоре.
Единственным местом, где целостность структур данных ядра еще подверга-
ется опасности, является алгоритм диспетчеризации, поскольку он не предохра-
няет от выбора процесса на выполнение сразу на двух процессорах. Например,
если в конфигурации имеется один главный процессор и два подчиненных, не ис-
ключена возможность того, что оба подчиненных процессора выберут для выпол-
нения в режиме задачи один и тот же процесс. Если оба процессора начнут вы-
полнять его параллельно, осуществляя чтение и запись, это неизбежно приведет
к искажению содержимого адресного пространства процесса.
Избежать возникновения этой проблемы можно двумя способами. Во-первых,
главный процессор может явно указать, на каком из подчиненных процессоров
следует выполнять данный процесс. Если на каждый процессор направлять нес-
колько процессов, возникает необходимость в сбалансировании нагрузки (на
один из процессоров назначается большое количество процессов, в то время как
другие процессоры простаивают). Задача распределения нагрузки между процес-
сорами ложится на главное ядро. Во-вторых, ядро может проследить за тем,
чтобы в каждый момент времени в алгоритме диспетчеризации принимал участие
только один процессор, для этого используются механизмы, подобные семафорам.
Поддержка системы UNIX в многопроцессорной конфигурации может включать в
себя разбиение ядра системы на критические участки, параллельное выполнение
которых на нескольких процессорах не допускается. Такие системы предназнача-
лись для работы на машинах AT&T 3B20A и IBM 370, для разбиения ядра исполь-
зовались семафоры (см. [Bach 84]). Нижеследующие рассуждения помогают понять
суть данной особенности. При ближайшем рассмотрении сразу же возникают два
вопроса: как использовать семафоры и где определить критические участки.
Как уже говорилось в главе 2, если при выполнении критического участка
программы процесс приостанавливается, для защиты участка от посягательств со
365
стороны других процессов алгоритмы работы ядра однопроцессорной системы UNIX
используют блокировку. Механизм установления блокировки:
выполнять пока (блокировка установлена) /* операция проверки */
приостановиться (до снятия блокировки);
установить блокировку;
механизм снятия блокировки:
снять блокировку;
вывести из состояния приостанова все процессы, приостановленные в ре-
зультате блокировки;
Процесс A/Процессор A Процесс B/Процессор B
+---------------------------------------------------------
| +---------------------------+
| | Блокировка НЕ установлена |
| - +---------------------------+ -
| - -
| - -
| Проверяет, установлена Проверяет, установлена
| ли блокировка ли блокировка
| (нет) (нет)
t - + - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
| Устанавливает Устанавливает
| блокировку блокировку
|
| Использует ресурс Использует ресурс
v ^ ^
Время | |
+------+ +------+
Опасность нарушения целостности
Рисунок 12.5. Конкуренция за установку блокировки в многопро-
цессорных системах
Блокировки такого рода охватывают некоторые критические участки, но не
работают в многопроцессорных системах, что видно из Рисунка 12.5. Предполо-
жим, что блокировка снята и что два процесса на разных процессорах одновре-
менно пытаются проверить ее наличие и установить ее. В момент t они обнару-
живают снятие блокировки, устанавливают ее вновь, вступают в критический
участок и создают опасность нарушения целостности структур данных ядра. В
условии одновременности имеется отклонение: механизм не сработает, если пе-
ред тем, как процесс выполняет операцию проверки, ни один другой процесс не
выполнил операцию установления блокировки. Если, например, после обнаружения
снятия блокировки процессор A обрабатывает прерывание и в этот момент про-
цессор B выполняет проверку и устанавливает блокировку, по выходе из преры-
вания процессор A так же установит блокировку. Чтобы предотвратить возникно-
вение подобной ситуации, нужно сделать так, чтобы процедура блокирования бы-
ла неделимой: проверку наличия блокировки и ее установку следует объединить
в одну операцию, чтобы в каждый момент времени с блокировкой имел дело толь-
ко один процесс.
Семафор представляет собой обрабатываемый ядром целочисленный объект,
для которого определены следующие элементарные (неделимые) операции:
* Инициализация семафора, в результате которой семафору присваивается не-
отрицательное значение;
* Операция типа P, уменьшающая значение семафора. Если значение семафора
366
опускается ниже нулевой отметки, выполняющий операцию процесс приоста-
навливает свою работу;
* Операция типа V, увеличивающая значение семафора. Если значение семафора
в результате операции становится больше или равно 0, один из процессов,
приостановленных во время выполнения операции P, выходит из состояния
приостанова;
* Условная операция типа P, сокращенно CP (conditional P), уменьшающая
значение семафора и возвращающая логическое значение "истина" в том слу-
чае, когда значение семафора остается положительным. Если в результате
операции значение семафора должно стать отрицательным или нулевым, ника-
ких действий над ним не производится и операция возвращает логическое
значение "ложь".
Определенные таким образом семафоры, безусловно, никак не связаны с се-
мафорами пользовательского уровня, рассмотренными в главе 11.
Дийкстра [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.
367
Как таковую, данную семафорную конструкцию нельзя реализовать в составе
ядра операционной системы, поскольку работающий с ней процесс не выходит из
цикла, пока не достигнет своей цели. Если
+------------------------------------------------------------+
| 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; |
| /* продолжение на следующей странице */ |
+------------------------------------------------------------+
Рисунок 12.6. Реализация семафорной блокировки на Си
семафор используется для блокирования структуры данных, процесс, обнаружив
семафор заблокированным, приостанавливает свое выполнение, чтобы ядро имело
возможность переключиться на контекст другого процесса и выполнить другую
полезную работу. С помощью функций Pprim и Vprim можно реализовать более
сложный набор семафорных операций, соответствующий тому составу, который оп-
ределен в разделе 12.3.1.
Для начала дадим определение семафора как структуры, состоящей из поля
блокировки (управляющего доступом к семафору), значения семафора и очереди
процессов, приостановленных по семафору. Поле блокировки содержит информа-
цию, открывающую во время выполнения операций типа P и V доступ к другим по-
лям структуры только одному процессу. По завершении операции значение поля
сбрасывается. Это значение определяет, разрешен ли процессу доступ к крити-
ческому участку, защищаемому семафором. В начале выполнения алгоритма опера-
ции P (Рисунок 12.8) ядро с помощью функции Pprim предоставляет процессу
право исключительного доступа к семафору и уменьшает значение семафора. Если
семафор имеет неотрицательное значение, текущий процесс получает доступ к
критическому участку. По завершении работы процесс сбрасывает блокировку се-
мафора (с помощью функции Vprim), открывая доступ к семафору для других про-
цессов, и возвращает признак успешного завершения. Если же в результате
уменьшения значение семафора становится отрицательным, ядро приостанавливает
выполнение процесса, используя алгоритм,
368
+------------------------------------------------------------+
| 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. Реализация семафорной блокировки на Си (продолжение)
подобный алгоритму sleep (глава 6): основываясь на значении приоритета, ядро
проверяет поступившие сигналы, включает текущий процесс в список приостанов-
ленных процессов, в котором последние представлены в порядке поступления, и
выполняет переключение контекста. Операция V (Рисунок 12.9) получает исклю-
чительный доступ к семафору через функцию Pprim и увеличивает значение сема-
фора. Если очередь приостановленных по семафору процессов непуста, ядро вы-
бирает из нее первый процесс и переводит его в состояние "готовности к за-
пуску".
Операции P и V по своему действию похожи на функции sleep и wakeup.
Главное различие между ними состоит в том, что семафор является структурой
данных, тогда как используемый функциями sleep и wakeup адрес представляет
собой всего лишь число. Если начальное значение семафора - нулевое, при вы-
полнении операции P над семафором процесс всегда приостанавливается, поэтому
операция P может заменять функцию sleep. Операция V, тем не менее, выводит
из состояния приостанова только один процесс, тогда как однопроцессорная
функция wakeup возобновляет все процессы, приостановленные по адресу, свя-
занному с событием.
С точки зрения семантики использование функции wakeup означает: данное
системное условие более не удовлетворяется, следовательно, все приостанов-
ленные по условию процессы должны выйти из состояния приостанова. Так, нап-
ример, процессы, приостановленные в связи с занятостью буфера, не должны
дальше пребывать в этом состоянии, если буфер больше не используется, поэто-
му они возоб-
новляются ядром. Еще один пример: если несколько процессов выводят данные на
терминал с помощью функции write, терминальный драйвер может перевести их в
369