Geum.ru

The design of the unix operating system by Maurice J

Вид материалаРеферат
12.4 Система tunis
12.5 Узкие места в функционировании многопроцессорных
Распределенные системы
13.1 Периферийные процессоры
Подобный материал:
1   ...   47   48   49   50   51   52   53   54   55
данных. С другой стороны, ядро не может оставить прерывание необ-

работанным. Система 3B20A выстраивает прерывания в очередь и ждет

момента освобождения семафора, когда вызов программы обработки

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

12.3.3.4 Фиктивные процессы

Когда ядро выполняет переключение контекста в однопроцессор-

ной системе, оно функционирует в контексте процесса, уступающего

управление (см. главу 6). Если в системе нет процессов, готовых к

запуску, ядро переходит в состояние простоя в контексте процесса,

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

гих периферийных устройств, оно обрабатывает его в контексте того

же процесса.

В многопроцессорной системе ядро не может простаивать в кон-

тексте процесса, выполнявшегося последним. Посмотрим, что прои-

зойдет после того, как процесс, приостановивший свою работу на

процессоре A, выйдет из состояния приостанова. Процесс в целом

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

тояния приостанова, даже несмотря на то, что его контекст уже на-

ходится в распоряжении процессора A. Если этот процесс выбирается

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

текст и возобновляет его выполнение. Когда в результате прерыва-

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

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

чение контекста. Таким образом, в течение короткого промежутка

времени с одним и тем же адресным пространством (в частности, со

стеком ядра) будут вести работу (и, что весьма вероятно, произво-

дить запись) сразу два процессора.

Решение этой проблемы состоит в создании некоторого фиктивно-

го процесса; когда процессор находится в состоянии простоя, ядро

переключается на контекст фиктивного процесса, делая этот кон-

текст текущим для бездействующего процессора. Контекст фиктивного

процесса состоит только из стека ядра; этот процесс не является

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

сор простаивает в контексте своего собственного фиктивного про-

цесса, навредить друг другу процессоры уже не могут.


12.4 СИСТЕМА TUNIS

Пользовательский интерфейс системы Tunis совместим с анало-

гичным интерфейсом системы UNIX, но ядро этой системы, разрабо-

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

ющих каждой частью системы. Проблема взаимного исключения

решается в системе Tunis довольно просто, так как в каждый момент

времени исполняется не более одной копии управляемого ядром про-

цесса, кроме того, процессы работают только с теми структурами

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

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

программного монитора. Эта процедура усиливает взаимное исключе-

ние, разрешая доступ к своей исполняемой части в каждый момент

времени не более, чем одному процессу. Механизм монитора отлича-

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

ледним усиливается модульность программ (операции P и V присутс-

твуют на входе в процедуру монитора и на выходе из нее), а

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

синхронизации. Холт отмечает, что разработка таких систем облег-

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

ющий понятие параллелизма (см. [Holt 83], стр.190). При всем при

этом внутренняя структура системы Tunis отличается от традицион-

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

12.5 УЗКИЕ МЕСТА В ФУНКЦИОНИРОВАНИИ МНОГОПРОЦЕССОРНЫХ

СИСТЕМ

В данной главе нами были рассмотрены два метода реализации

многопроцессорных версий системы UNIX: конфигурация, состоящая из

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

цессор (главный) функционирует в режиме ядра, и метод, основанный

на использовании семафоров и допускающий одновременное исполнение

в режиме ядра всех имеющихся в системе процессов. Оба метода ин-

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

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

чивается с линейной скоростью, нельзя. Потери производительности

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

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

памяти. Во-вторых, в схеме, основанной на использовании семафо-

ров, к этой конкуренции добавляется соперничество за семафоры;

процессы зачастую обнаруживают семафоры захваченными, больше про-

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

к семафорам. Первая схема, основанная на использовании главного и

подчиненного процессоров, тоже не лишена недостатков: по мере

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

местом в системе, поскольку только он один может функционировать

в режиме ядра. Несмотря на то, что более внимательное техническое

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

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

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

(см., например, [Beck 85]), все построенные с использованием сов-

ременной технологии многопроцессорные системы имеют предел, за

которым расширение состава процессоров не сопровождается увеличе-

нием производительности системы.

12.6 УПРАЖНЕНИЯ

1. Решите проблему функционирования многопроцессорных систем

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

нировать в режиме ядра, но не более одного одновременно. Та-


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

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

чен для реализации функций ядра. Как добиться того, чтобы в


режиме ядра в каждый момент времени находился только один

процессор ? Какую стратегию обработки прерываний при этом

можно считать приемлемой ?

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

памяти, протестируйте программу, реализующую семафорную бло-

кировку (Рисунок 12.6). Последовательности операций P-V над

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

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

вать индикацию и обработку ошибок ?

3. Разработайте алгоритм выполнения операции CP (условный тип

операции P), используя текст алгоритма операции P.

4. Объясните, зачем в алгоритмах операций P и V (Рисунки 12.8 и

12.9) нужна блокировка прерываний. В какие моменты ее следу-

ет осуществлять ?

5. Почему при выполнении "циклической блокировки" вместо строки:

while (! CP(семафор));

ядро не может использовать операцию P безусловного типа ? (В

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

если процесс запустит операцию P и приостановится ?)

6. Обратимся к алгоритму getblk, приведенному в главе 3. Опиши-

те реализацию алгоритма в многопроцессорной системе для слу-

чая, когда блок отсутствует в буферном кеше.

*7. Предположим, что при выполнении алгоритма выделения буфера

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

лежащий списку свободных буферов. Разработайте схему ослаб-

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

на два подсписка.

*8. Предположим, что у терминального драйвера имеется семафор,

значение которого при инициализации сбрасывается в 0 и по

которому процессы приостанавливают свою работу в случае пе-

реполнения буфера вывода на терминал. Когда терминал готов к

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

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

тайте схему возобновления процессов, использующую операции

типа P и V. В случае необходимости введите дополнительные

флаги и семафоры. Как должна вести себя схема в том случае,

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

но при этом текущий процессор не имеет возможности блокиро-

вать прерывания на других процессорах ?

*9. Если точки входа в драйвер защищаются семафорами, должно

соблюдаться условие освобождения семафора в случае перехода

процесса в состояние приостанова. Как это реализуется на

практике ? Каким образом должна производиться обработка пре-

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

локирован ?

10. Обратимся к системным функциям установки и контроля систем-

ного времени (глава 8). Разные процессоры могут иметь раз-

личную тактовую частоту. Как в этом случае указанные функции

должны работать ?

РАСПРЕДЕЛЕННЫЕ СИСТЕМЫ


В предыдущей главе нами были рассмотрены сильносвязанные мно-

гопроцессорные системы с общей памятью, общими структурами данных

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

ние. Часто, однако, бывает желательно в целях обеспечения сов-

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

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

эксплуатации. Пусть, например, пользователю персональной ЭВМ нуж-

но обратиться к файлам, находящимся на более крупной машине, но

сохранить при этом контроль над персональной ЭВМ. Несмотря на то,

что отдельные программы, такие как uucp, поддерживают передачу

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

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

что он работает в сети. Кроме того, надо заметить, что программы,

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

ными, не работают. Пользователи должны располагать стандартным

набором функций системы UNIX и, за исключением возможной потери в

быстродействии, не должны ощущать пересечения машинных границ.

Так, например, работа системных функций open и read с файлами на

удаленных машинах не должна отличаться от их работы с файлами,

принадлежащими локальным системам.

Архитектура распределенной системы представлена на Рисунке

13.1. Каждый компьютер, показанный на рисунке, является автоном-

ным модулем, состоящим из ЦП, памяти и периферийных устройств.

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

ютер не располагает локальной файловой системой: он должен иметь

периферийные устройства для связи с другими машинами, а все при-

надлежащие ему файлы могут располагаться и на ином компьютере.

Физическая память, доступная каждой машине, не зависит от процес-

сов, выполняемых на других машинах. Этой особенностью распреде-

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

систем, рассмотренных в предыдущей главе. Соответственно, и ядро

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

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

│ │ Процессоры │ │ │ │ Процессоры │ │

│ L-----T------- │ │ L-----T------- │

│ ----T-------+------T------- │ │ ----T-------+------T------- │

│ ----+----┐ --------+------┐ │ │ ----+----┐ --------+------┐ │

│ │ Память │ │ Периферийные │ │ │ │ Память │ │ Периферийные │ │

│ │ │ │ устройства │ │ │ │ │ │ устройства │ │

│ L--------- L--------------- +-┐--+ L--------- L--------------- │

L------------------------------ +- L------------------------------

│

--------------+---------------┐

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

│ │ Процессоры │ │

│ L-----T------- │

│ ----T-------+------T------- │

│ ----+----┐ --------+------┐ │

│ │ Память │ │ Периферийные │ │

│ │ │ │ устройства │ │

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

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

Рисунок 13.1. Модель системы с распределенной архитектурой

системы на каждой машине функционирует независимо от внешних ус-

ловий эксплуатации распределенной среды.

Распределенные системы, хорошо описанные в литературе, тради-

ционно делятся на следующие категории:

* периферийные системы, представляющие собой группы машин, от-

личающихся ярковыраженной общностью и связанных с одной

(обычно более крупной) машиной. Периферийные процессоры делят

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

ему все обращения к операционной системе. Цель периферийной

системы состоит в увеличении общей производительности сети и

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

цессу в операционной среде UNIX. Система запускается как от-

дельный модуль; в отличие от других моделей распределенных

систем, периферийные системы не обладают реальной автономией,

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

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

* распределенные системы типа "Newcastle", позволяющие осу-

ществлять дистанционную связь по именам удаленных файлов в

библиотеке (название взято из статьи "The Newcastle

Connection" - см. [Brownbridge 82]). Удаленные файлы имеют

спецификацию (составное имя), которая в указании пути поиска

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

имени, предшествующую корню файловой системы. Реализация это-

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

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

риваемые в этой главе, но менее гибок.

* абсолютно "прозрачные" распределенные системы, в которых для

обращения к файлам, расположенным на других машинах, доста-

точно указания их стандартных составных имен; распознавание

этих файлов как удаленных входит в обязанности ядра. Маршруты

поиска файлов, указанные в их составных именах, пересекают

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

чек ни было сформировано при монтировании файловых систем на

дисках.

В настоящей главе мы рассмотрим архитектуру каждой модели;

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

разработок, а на информации, публиковавшейся в различных техни-

ческих статьях. При этом предполагается, что забота об адресации,

маршрутизации, управлении потоками, обнаружении и исправлении

ошибок возлагается на модули протоколов и драйверы устройств,

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

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

щем разделе для периферийных систем, работают аналогичным образом

и для систем типа Newcastle и для абсолютно "прозрачных" систем,

о которых пойдет речь позже; поэтому в деталях мы их рассмотрим

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

вимся в основном на особенностях, отличающих эти модели от всех

остальных.

13.1 ПЕРИФЕРИЙНЫЕ ПРОЦЕССОРЫ


Архитектура периферийной системы показана на Рисунке 13.2.


Цель такой конфигурации состоит в повышении общей производитель-

ности сети за счет перераспределения выполняемых процессов между

центральным и периферийными процессорами. У каждого из периферий-

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

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

процессором. Файловая система и все устройства находятся в распо-

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

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

периферийными процессорами не перемещаются; будучи однажды пере-

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

риферийный процессор содержит облегченный вариант операционной

системы, предназначенный для обработки локальных обращений к сис-

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

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

процессором.

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

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

кальную операционную систему. Любой выполняемый на периферии про-

цесс связан с процессом-спутником, принадлежащим центральному

процессору (см. [Birrell 84]); когда процесс, протекающий на пе-

риферийном процессоре, вызывает системную функцию, которая нужда-

ется в услугах исключительно центрального процессора, периферий-

ный процесс связывается со своим спутником и запрос поступает на

обработку на центральный процессор. Процесс-спутник исполняет

системную функцию и посылает результаты обратно на периферийный

процессор. Взаимоотношения периферийного процесса со своим спут-

ником похожи на отношения клиента и сервера, подробно рассмотрен-

ные нами в главе 11: периферийный процесс выступает клиентом сво-

его спутника, поддерживающего функции работы с файловой системой.

При этом удаленный процесс-сервер имеет только одного клиента. В

разделе 13.4 мы рассмотрим процессы-серверы, имеющие несколько

клиентов.

Центральный процессор Периферийный процессор

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

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

│ │ Процессоры │ │ │ │ Процессоры │ │

│ L-----T------- │ │ L-----T------- │

│ ----T-------+------T------- │ │ ----T-------+-------------- │

│ ----+----┐ --------+------┐ │ │ ----+----┐ │

│ │ Память │ │ Периферийные │ │ │ │ Память │ │

│ │ │ │ устройства │ │ │ │ │ │

│ L--------- L--------------- +-┐--+ L--------- │

L------------------------------ +- L------------------------------

│


--------------+---------------┐

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

Периферийный │ │ Процессоры │ │

процессор │ L-----T------- │

│ ----T-------+-------------- │

│ ----+----┐ │

│ │ Память │ │

│ │ │ │

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

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

Рисунок 13.2. Конфигурация периферийной системы


Когда периферийный процесс вызывает системную функцию, кото-

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

запрос процессу-спутнику. Так, например, в целях получения допол-

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

функцию sbrk. Однако, если требуются услуги центрального процес-

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

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

процесса в некое сообщение, посылаемое процессу-спутнику (Рисунок

13.3). Сообщение включает в себя признак, из которого следует,

что системная функция выполняется процессом-спутником от имени

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

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

фикации), которые для разных функций различны. Оставшаяся часть

сообщения представляет собой данные переменной длины (например,

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

цией write).

Процесс-спутник ждет поступления запросов от периферийного

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

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

в ответ, посылаемый периферийному процессу. Ответ, помимо резуль-

татов выполнения системной функции, включает в себя сообщение об

Формат сообщения

-----------------T----------T---------------T--------------------┐

│ Признак вызова │Параметры │Данные о среде │ Составное имя │

│ системной функ-│системной │выполнения про-│ или │

│ ции │функции │цесса │ поток данных │

L----------------+----------+---------------+---------------------

Ответ

-------------T-----------T---------T---------------------┐

│ Результаты │ Сообщение │ Номер │ │