Geum.ru

The design of the unix operating system by Maurice J

Вид материалаРеферат
9.3 Система смешанного типа со свопингом и подкачкой
Подсистема управления
Подобный материал:
1   ...   35   36   37   38   39   40   41   42   ...   55

9.27.


Запись таблицы страниц - Процесс A

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

│ Страница 828: доступна, копируется при записи +-┐

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

│

Запись таблицы страниц - Процесс B │ ------------┐

------------------------------------------------┐ L->│ Страничный│

│ Страница 828: доступна, копируется при записи +--->│ блок 828 │


L------------------------------------------------ -->│ Счетчик │

│ │ ссылок 3 │

Запись таблицы страниц - Процесс C │ L------------

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

│ Страница 828: доступна, копируется при записи +--

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


(а) Перед тем, как процесс B получил отказ системы защиты


Запись таблицы страниц - Процесс A

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

│ Страница 828: доступна, копируется при записи +-┐ │ Страничный│

L------------------------------------------------ │ │ блок 828 │

L->│ Счетчик │

Запись таблицы страниц - Процесс B -->│ ссылок 2 │

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

│ Страница 828: доступна +┐│

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

L│->│ Страничный│

Запись таблицы страниц - Процесс C │ │ блок 786 │

------------------------------------------------┐ │ │ Счетчик │

│ Страница 828: доступна, копируется при записи +-- │ ссылок 1 │

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


(б) После запуска программы обработки отказа системы защиты

для процесса B


Рисунок 9.26. Отказ системы защиты из-за установки бита копи-

рования при записи


Перед завершением программа обработки отказа системы защиты

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

рования при записи. Она пересчитывает приоритет процесса и прове-

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

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

работки отказа из-за недопустимости данных.


Процесс, получающий отказы при

обращении к странице "Сборщик" страниц

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

│

│

│ Блокирует область

│

│

│ Отказ системы защиты

│ Приостанов - область

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

│

│ Выгрузка страницы - бит

│ допустимости сброшен

│

│

│

│ Выводит из приостанова

│ процессы, ожидающие

│ снятия с области

│ блокировки

│ Выход из приостанова

│

│

│

│ Проверка бита доступ-

│ ности - сброшен

│ Выход из программы обра-

│ ботки отказа системы за-

│ щиты

│

│

│

│ Отказ из-за недоступ-

│ ности данных

v

Время


Рисунок 9.27. Взаимодействие отказа системы защиты и отказа

из-за недоступности данных


9.2.4 Замещение страниц на менее сложной технической базе


Наибольшая действенность алгоритмов замещения страниц по зап-

росу (обращению) достигается в том случае, если биты упоминания и

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

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

щую признак "копирования при записи". Тем не менее, указанные ал-

горитмы вполне применимы даже тогда, когда аппаратура распознает

только бит доступности и код защиты. Если бит доступности, уста-

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

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

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

ровать установку остальных битов программным путем. Так, напри-

мер, в машине VAX-11 бит упоминания отсутствует (см. [Levy 82]).

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

для страницы и дальше работать по следующему плану. Если процесс

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

ности сброшен, и в игру вступает программа обработки отказа, исс-

ледующая страницу. Поскольку "программный" бит доступности уста-

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

находится в памяти; оно устанавливает "программный" бит упомина-

ния и "аппаратный" бит доступности, но ему еще предстоит узнать о

том, что на страницу была сделана ссылка. Последующие ссылки на

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

установлен. Когда с ней будет работать "сборщик" страниц, он

вновь сбросит "аппаратный" бит доступности, вызывая тем самым от-


Аппарат- Программ- Программ- Аппарат- Программ- Программ-

ный бит ный бит ный бит ный бит ный бит ный бит

доступ- доступ- упомина- доступ- доступ- упомина-

ности ности ния ности ности ния

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

│ Нет │ Да │ Нет │ │ Да │ Да │ Да │

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


(а) До модифицирования (б) После модифицирования

страницы страницы


Рисунок 9.28. Имитация установки "аппаратного" бита модифика-

ции программными средствами


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

к началу цикла. Этот случай показан на Рисунке 9.28.


9.3 СИСТЕМА СМЕШАННОГО ТИПА СО СВОПИНГОМ И ПОДКАЧКОЙ

ПО ЗАПРОСУ


Несмотря на то, что в системах с замещением страниц по запро-

су обращение с памятью отличается большей гибкостью по сравнению

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

в которых "сборщик" страниц и программа обработки отказов из-за

недоступности данных начинают мешать друг другу из-за нехватки

памяти. Если сумма рабочих множеств всех процессов превышает объ-

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

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

дальше становится невозможным. "Сборщик" страниц не сможет доста-

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

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

кольку ядро тратит слишком много времени на верхнем уровне, с

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

Ядро в версии V манипулирует алгоритмами подкачки процессов и

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

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

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

вательский процесс в состояние, эквивалентное состоянию "готов-

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

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

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

ной памяти в системе не превысит верхнюю отметку. На каждый выг-

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

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

Ядро загружает эти процессы не с помощью обычного алгоритма под-

качки, а путем обработки отказов при обращении к соответствующим

страницам. На последующих итерациях процесса подкачки при условии

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

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

Применение такого метода ведет к снижению частоты возникновения

системных отказов и устранению соперничества: по идеологии он

близок к методам, используемым в операционной системе VAX/VMS

([Levy 82]).


9.4 ВЫВОДЫ


Прочитанная глава была посвящена рассмотрению алгоритмов под-

качки процессов и замещения страниц, используемых в версии V сис-

темы UNIX. Алгоритм подкачки процессов реализует перемещение про-

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

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

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

exec и sbrk или в результате естественного увеличения стека), или

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

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

(процесс 0), который запускается всякий раз, как на устройстве

выгрузки появляются процессы, готовые к выполнению. Процесс под-

качки не прекращает своей работы до тех пор, пока на устройстве

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

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

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

но в его обязанности входит также слежение за соблюдением требо-

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

цессов в памяти (в целях предотвращения холостой перекачки); по

этой причине процесс подкачки не всегда достигает успеха в своей

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

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

рамма обработки прерываний по таймеру.

В системе с замещением страниц по запросу процессы могут ис-

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

жено в память не полностью; поэтому виртуальный размер процесса

может превышать объем доступной физической памяти в системе. Ког-

да ядро испытывает потребность в свободных страницах, "сборщик"

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

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

этого, и в конечном итоге откачивает их на устройство выгрузки.

Когда процесс обращается к виртуальной странице, которая в насто-

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

тупности данных. Ядро запускает программу обработки отказа, кото-

рая назначает области новую физическую страницу памяти и копирует

в нее содержимое виртуальной страницы.

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

ритма замещения страниц по запросу можно несколькими способами.

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

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

мая необходимость в физическом копировании страниц. Во-вторых,

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

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

для незамедлительного считывания файла в память. Это способствует

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

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

су, и устраняет излишнюю холостую перекачку, имеющую место в том

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

до того, как в них возникает потребность.


9.5 УПРАЖНЕНИЯ


1. Набросайте схему реализации алгоритма mfree, который осво-

бождает пространство памяти и возвращает его таблице свобод-

ного пространства.

2. В разделе 9.1.2 утверждается, что система блокирует переме-

щаемый процесс, чтобы другие процессы не могли его трогать с

места до момента окончания операции. Что произошло бы, если

бы система не делала этого ?

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

ются таблицы используемых процессом сегментов и страниц. Ка-

ким образом ядро может выгрузить это пространство из памяти?

4. Если стек ядра находится внутри адресного пространства про-

цесса, почему процесс не может выгружать себя сам ? Какой на

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

сов, как она должна запускаться ?

*5. Предположим, что ядро пытается выгрузить процесс, чтобы ос-

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

устройства выгрузки. Если ни на одном из устройств выгрузки

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

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

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

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

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

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

6. Рассмотрите еще раз пример, приведенный на Рисунке 9.10, при

условии, что в памяти есть место только для 1 процесса.

7. Обратимся к примеру, приведенному на Рисунке 9.11. Составьте

подобный пример, в котором процессу постоянно требуется для

работы центральный процессор. Существует ли какой-нибудь

способ снятия подобной напряженности ?


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

│ main() │

│ { │

│ f(); │

│ g(); │

│ } │

│ │

│ f() │

│ { │

│ vfork(); │

│ } │

│ │

│ g() │

│ { │

│ int blast[100],i; │

│ for (i = 0; i < 100; i++) │

│ blast[i] = i; │

│ } │

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


Рисунок 9.29


8. Что произойдет в результате выполнения программы, приведен-

ной на Рисунке 9.29, в системе BSD 4.2 ? Каким будет стек

процесса-родителя ?

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

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

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

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

первым ?

*10. Алгоритм обработки отказа из-за недоступности данных, изло-

женный в тексте, загружает страницы поодиночке. Его эффек-

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

страницы, вызвавшей отказ, и все соседние с ней страницы.

Переработайте исходный алгоритм с учетом указанной операции.

11. В алгоритмах работы "сборщика" страниц и программы обработки

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

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

нить в этих алгоритмах для того, чтобы они работали и в тех

случаях, когда указанное равенство не соблюдается ?

*12. Когда процесс вызывает функцию fork (ветвится), значение

счетчика ссылок на каждую разделяемую страницу (в таблице

pfdata) увеличивается. Предположим, что "сборщик" страниц

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

один из процессов (скажем, родитель) впоследствии получает

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

теперь располагается на физической странице. Объясните, по-

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

ную копию страницы, даже после того, как процесс-родитель

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

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

дисковой копией ?

13. Что следует предпринять программе обработки отказов в том

случае, если в системе исчерпаны страницы памяти ?

*14. Составьте алгоритм выгрузки редко используемых компонент яд-

ра. Какие из компонент нельзя выгружать и как их в таком

случае следует обозначить ?

15. Придумайте алгоритм, отслеживающий выделение пространства на

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

в настоящей главе, битовый массив. Сравните эффективность

обоих методов.

16. Предположим, что в машине нет аппаратно-устанавливаемого би-

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

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

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

го бита доступности.

17. В машине VAX-11 перед проверкой наличия отказов из-за недос-

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

отказов системы защиты. Как это отражается на алгоритмах об-

работки отказов ?

18. Системная функция plock дает суперпользователю возможность

устанавливать и снимать блокировку (в памяти) на областях

команд и данных вызывающего процесса. Процесс подкачки и

"сборщик" страниц не могут выгружать заблокированные страни-

цы из памяти. Процессам, использующим эту системную функцию,

не приходится дожидаться загрузки страниц, поэтому им гаран-

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

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

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

объем заблокированных областей превысит размер доступной па-

мяти в машине ?

19. Что делает программа, приведенная на Рисунке 9.30 ? Подумай-

те над альтернативной стратегией замещения страниц, в соот-

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

включается максимально-возможное число страниц.


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

│ struct fourmeg │

│ { │

│ int page[512]; /* пусть int занимает 4 байта */ │

│ } fourmeg[2048]; │

│ │

│ main() │

│ { │

│ for (;;) │

│ { │

│ switch(fork()) │

│ { │

│ case -1: /* процесс-родитель не может выполнить │

│ * fork --- слишком много потомков */ │

│ case 0: /* потомок */ │

│ func(); │

│ default: │

│ continue; │

│ } │

│ } │

│ } │

│ │

│ func() │

│ { │

│ int i; │

│ │

│ for (;;) │

│ { │

│ printf("процесс %d повторяет цикл\n",getpid()); │

│ for (i = 0; i < 2048; i++) │

│ fourmeg[i].page[0] = i; │

│ } │

│ } │

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


Рисунок 9.30

ПОДСИСТЕМА УПРАВЛЕНИЯ

ВВОДОМ-ВЫВОДОМ


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

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

тели на магнитных дисках и лентах, терминалы, принтеры и сети, с

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

и именуются драйверами устройств, с другой. Между драйверами уст-

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

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

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

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

ными накопителями. Если в системе имеются однотипные устройства,

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

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

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

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

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

ности команд. Один драйвер управляет множеством физических уст-

ройств данного типа. Например, один терминальный драйвер может

управлять всеми терминалами, подключенными к системе. Драйвер

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

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

гой.

Система поддерживает "программные устройства", с каждым из

которых не связано ни одно конкретное физическое устройство. Нап-

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

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

ется периферийным устройством. Команда ps обращается к

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