Страница:
процессора. Контекст фиктивного процесса состоит только из стека ядра; этот
процесс не является выполнимым и не выбирается для запуска. Поскольку каждый
процессор простаивает в контексте своего собственного фиктивного процесса,
навредить друг другу процессоры уже не могут.
378
Пользовательский интерфейс системы Tunis совместим с аналогичным интер-
фейсом системы UNIX, но ядро этой системы, разработанное на языке Concurrent
Euclid, состоит из процессов, управляющих каждой частью системы. Проблема
взаимного исключения решается в системе Tunis довольно просто, так как в
каждый момент времени исполняется не более одной копии управляемого ядром
процесса, кроме того, процессы работают только с теми структурами данных,
которые им принадлежат. Системные процессы активизируются запросами на ввод,
защиту очереди запросов осуществляет процедура программного монитора. Эта
процедура усиливает взаимное исключение, разрешая доступ к своей исполняемой
части в каждый момент времени не более, чем одному процессу. Механизм мони-
тора отличается от механизма семафоров тем, что, во-первых, благодаря пос-
ледним усиливается модульность программ (операции P и V присутствуют на вхо-
де в процедуру монитора и на выходе из нее), а во-вторых, сгенерированный
компилятором код уже содержит элементы синхронизации. Холт отмечает, что
разработка таких систем облегчается, если используется язык, поддерживающий
мониторы и включающий понятие параллелизма (см. [Holt 83], стр.190). При
всем при этом внутренняя структура системы Tunis отличается от традиционной
реализации системы UNIX радикальным образом.
В данной главе нами были рассмотрены два метода реализации многопроцес-
сорных версий системы UNIX: конфигурация, состоящая из главного и подчинен-
ного процессоров, в которой только один процессор (главный) функционирует в
режиме ядра, и метод, основанный на использовании семафоров и допускающий
одновременное исполнение в режиме ядра всех имеющихся в системе процессов.
Оба метода инвариантны к количеству процессоров, однако говорить о том, что
с ростом числа процессоров общая производительность системы увеличивается с
линейной скоростью, нельзя. Потери производительности возникают, во-первых,
как следствие конкуренции за ресурсы памяти, которая выражается в увеличении
продолжительности обращения к памяти. Во-вторых, в схеме, основанной на ис-
пользовании семафоров, к этой конкуренции добавляется соперничество за сема-
форы; процессы зачастую обнаруживают семафоры захваченными, больше процессов
находится в очереди, долгое время ожидая получения доступа к семафорам. Пер-
вая схема, основанная на использовании главного и подчиненного процессоров,
тоже не лишена недостатков: по мере увеличения числа процессоров главный
процессор становится узким местом в системе, поскольку только он один может
функционировать в режиме ядра. Несмотря на то, что более внимательное техни-
ческое проектирование позволяет сократить конкуренцию до разумного минимума
и в некоторых случаях приблизить скорость повышения производительности сис-
темы при увеличении числа процессоров к линейной (см., например, [Beck 85]),
все построенные с использованием современной технологии многопроцессорные
системы имеют предел, за которым расширение состава процессоров не сопровож-
дается увеличением производительности системы.
1. Решите проблему функционирования многопроцессорных систем таким обра-
зом, чтобы все процессоры в системе могли функционировать в режиме яд-
ра, но не более одного одновременно. Такое решение будет отличаться от
первой из предложенных в тексте схем, где только один процессор (глав-
ный) предназначен для реализации функций ядра. Как добиться того, чтобы
в режиме ядра в каждый момент времени находился только один процессор ?
Какую стратегию обработки прерываний при этом можно считать приемлемой?
379
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). Разные процессоры могут иметь различную тактовую частоту.
Как в этом случае указанные функции должны работать ?
380
процесс не является выполнимым и не выбирается для запуска. Поскольку каждый
процессор простаивает в контексте своего собственного фиктивного процесса,
навредить друг другу процессоры уже не могут.
378
Пользовательский интерфейс системы Tunis совместим с аналогичным интер-
фейсом системы UNIX, но ядро этой системы, разработанное на языке Concurrent
Euclid, состоит из процессов, управляющих каждой частью системы. Проблема
взаимного исключения решается в системе Tunis довольно просто, так как в
каждый момент времени исполняется не более одной копии управляемого ядром
процесса, кроме того, процессы работают только с теми структурами данных,
которые им принадлежат. Системные процессы активизируются запросами на ввод,
защиту очереди запросов осуществляет процедура программного монитора. Эта
процедура усиливает взаимное исключение, разрешая доступ к своей исполняемой
части в каждый момент времени не более, чем одному процессу. Механизм мони-
тора отличается от механизма семафоров тем, что, во-первых, благодаря пос-
ледним усиливается модульность программ (операции P и V присутствуют на вхо-
де в процедуру монитора и на выходе из нее), а во-вторых, сгенерированный
компилятором код уже содержит элементы синхронизации. Холт отмечает, что
разработка таких систем облегчается, если используется язык, поддерживающий
мониторы и включающий понятие параллелизма (см. [Holt 83], стр.190). При
всем при этом внутренняя структура системы Tunis отличается от традиционной
реализации системы UNIX радикальным образом.
В данной главе нами были рассмотрены два метода реализации многопроцес-
сорных версий системы UNIX: конфигурация, состоящая из главного и подчинен-
ного процессоров, в которой только один процессор (главный) функционирует в
режиме ядра, и метод, основанный на использовании семафоров и допускающий
одновременное исполнение в режиме ядра всех имеющихся в системе процессов.
Оба метода инвариантны к количеству процессоров, однако говорить о том, что
с ростом числа процессоров общая производительность системы увеличивается с
линейной скоростью, нельзя. Потери производительности возникают, во-первых,
как следствие конкуренции за ресурсы памяти, которая выражается в увеличении
продолжительности обращения к памяти. Во-вторых, в схеме, основанной на ис-
пользовании семафоров, к этой конкуренции добавляется соперничество за сема-
форы; процессы зачастую обнаруживают семафоры захваченными, больше процессов
находится в очереди, долгое время ожидая получения доступа к семафорам. Пер-
вая схема, основанная на использовании главного и подчиненного процессоров,
тоже не лишена недостатков: по мере увеличения числа процессоров главный
процессор становится узким местом в системе, поскольку только он один может
функционировать в режиме ядра. Несмотря на то, что более внимательное техни-
ческое проектирование позволяет сократить конкуренцию до разумного минимума
и в некоторых случаях приблизить скорость повышения производительности сис-
темы при увеличении числа процессоров к линейной (см., например, [Beck 85]),
все построенные с использованием современной технологии многопроцессорные
системы имеют предел, за которым расширение состава процессоров не сопровож-
дается увеличением производительности системы.
1. Решите проблему функционирования многопроцессорных систем таким обра-
зом, чтобы все процессоры в системе могли функционировать в режиме яд-
ра, но не более одного одновременно. Такое решение будет отличаться от
первой из предложенных в тексте схем, где только один процессор (глав-
ный) предназначен для реализации функций ядра. Как добиться того, чтобы
в режиме ядра в каждый момент времени находился только один процессор ?
Какую стратегию обработки прерываний при этом можно считать приемлемой?
379
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). Разные процессоры могут иметь различную тактовую частоту.
Как в этом случае указанные функции должны работать ?
380