--+ +-----+--------+++-------+---------+ | | | | 67К | | ||| | | | | | | +-----+--------+++-------+---------+ +----+------+----+ Рисунок 9.22. Иллюстрация к отказу из-за недоступности данных 280 лучил отказ при обращении к виртуальному адресу 64К (Рисунок 9.22). Просмат- ривая кеш, ядро устанавливает, что страничный блок с номером 1861 связан с дисковым блоком 1206. Ядро перенастраивает запись таблицы страниц с вирту- альным адресом 64К на страницу с номером 1861, устанавливает бит доступности и передает управление программе обработки отказа. Таким образом, номер дис- кового блока связывает вместе записи таблицы страниц и таблицы pfdata, чем и объясняется его запоминание в обеих таблицах. Как и ядру, программе обработки отказа не нужно считывать страницу в па- мять, если какой-то иной процесс уже получил отказ по той же самой странице, но еще не полностью загрузил ее. Программа находит область с записью таблицы Записи Дескрипторы таблицы страниц дисковых блоков Страничные блоки Физи- ческая Диско- Виртуаль- стра- Состо- Состо- Стра- вый Счет- ный адрес ница яние яние Блок ница блок чик +-----+--------+++-------+---------+ +----+------+----+ 66К | 1776| Доступ-|||На дис-| 847 | |1776| 847 | 1 | | | на |||ке | | | | | | +-----+--------+++-------+---------+ +----+------+----+ Рисунок 9.23. Результат загрузки страницы в память Процесс A Процесс B +------------------------------------------------------------ | Отказ при обращении к стра- - - | нице - - | Виртуальный адрес страницы - - | верен - - | Приостанов до завершения - - | считывания страницы - - | - - Отказ при обращении к стра- | - - нице | - - Виртуальный адрес страницы | - - верен | - - Загрузка страницы в память | - - Приостанов до окончания | - - загрузки | - - - | Выход из приостанова -- - - | страница в памяти - - | Страница помечается как - - | доступная - - | Выход из приостанова других - - | процессов - - | - Выход из приостанова | Возобновление выполнения - - | - - - | - - Возобновление выполнения | - - - | - - - | Время - v Рисунок 9.24. Два отказа на одной странице 281 страниц, которую она уже ранее заблокировала. Она дожидается, пока будет за- кончен цикл обработки предыдущего отказа, после чего обнаруживает, что стра- ница стала доступной, и завершает свою работу. Эта процедура прослеживается на Рисунке 9.24. Если копия страницы находится не на устройстве выгрузки, а в исполняемом файле (случай 3), ядро загружает страницу из файла. Программа обработки от- каза обращается к дескриптору дискового блока, ищет соответствующий номер логического блока внутри файла, содержащего страницу, и индекс, ассоцииро- ванный с записью таблицы областей. Номер логического блока используется программой в качестве смещения внутри списка номеров дисковых блоков, присо- единенного к индексу во время выполнения функции exec. По номеру блока на диске программа считывает страницу в память. Так, например, дескриптор дис- кового блока, связанный с виртуальным адресом 1К, показывает, что содержимое страницы располагается в исполняемом файле, внутри логического блока с номе- ром 3 (см. Рисунок 9.22). Если процесс получил отказ при обращении к странице, имеющей пометку "заполняемая при обращении" или "обнуляемая при обращении" (случаи 4 и 5), ядро выделяет свободную страницу в памяти и корректирует соответствующую за- пись таблицы страниц. Если страница "обнуляемая при обращении", ядро также очищает ее содержимое. В завершение обработки флаги "заполняемая при обраще- нии" и "обнуляемая при обращении" сбрасываются. Теперь страница находится в памяти, доступна процессам и ее содержимое не имеет аналогов ни на устройст- ве выгрузки, ни в файловой системе. Так происходит, если процесс обращается к страницам с виртуальными адресами 3К и 65К (см. Рисунок 9.22): ни один из процессов не обращался к этим страницам с тех пор, как файл был запущен на выполнение функцией exec. В завершение своей работы программа обработки отказов из-за отсутствия (недоступности) данных устанавливает бит доступности страницы и сбрасывает бит модификации. Приоритет процесса при этом пересчитывается, ибо во время выполнения программы процесс мог приостановить свое выполнение на уровне яд- ра, получая тем самым по возвращении в режим задачи незаслуженное преимущес- тво перед другими процессами. И, наконец, возвращаясь в режим задачи, прог- рамма проверяет, не было ли за время обработки отказа поступления каких-либо сигналов. 9.2.3.2 Обработка прерываний по отказу системы защиты Вторым типом отказа, встречающегося при обращении к странице, является отказ системы защиты, который означает, что процесс обратился к существующей странице памяти, но судя по разрядам, описывающим права доступа к странице, доступ к ней со стороны текущего процесса не разрешен. (Вспомним пример, описывающий попытку процесса произвести запись данных в область команд; см. Рисунок 7.22). Отказ данного типа имеет место также тогда, когда процесс предпринимает попытку записать что-то на страницу, для которой во время вы- полнения системной функции fork был установлен бит копирования при записи. Ядро должно различать между собой ситуации, когда отказ произошел по причине того, что страница требует копирования при записи, и когда имело место дейс- твительно что-то недопустимое. Программа обработки отказа системы защиты автоматически получает вирту- альный адрес, по которому произошел отказ, и ведет поиск соответствующей об- ласти и записи таблицы страниц (Рисунок 9.25). Она блокирует область, чтобы "сборщик" страниц не мог выгрузить страницу, пока связанный с ней отказ не будет обработан. Если программа обработки отказа устанавливает, что причиной отказа послужила установка бита копирования при записи, и если страницу ис- пользуют сразу несколько процессов, ядро выделяет в памяти новую страницу и копирует в нее содержимое старой страницы; ссылки других процессов на старую 282 страницу сохраняют свое значение. После копирования и внесения в запись таб- лицы страниц нового номера страницы ядро уменьшает значение счетчика ссылок в записи таблицы pfdata, соответствующей старой странице. Вся процедура по- казана на Рисунке 9.26, где три процесса совместно используют физическую страницу с номером 828. Процесс B считывает страницу, но поскольку бит копи- рования при записи установлен, получает отказ системы защиты. Программа об- работки отказа выделяет страницу с номером 786, копирует в нее содержимое страницы 828, уменьшает значение счетчика ссылок на скопированную страницу и перенастраивает соответствующую запись таблицы страниц на страницу с номером 786. Если бит копирования при записи установлен, но страница используется только одним процессом, ядро дает процессу возможность воспользоваться физи- ческой страницей повторно. Оно отключает бит копирования при записи и разры- вает связь страницы с ее копией на диске (если таковая существует), посколь- ку не исключена возможность того, что дисковой копией пользуются другие про- цессы. Затем ядро убирает запись таблицы pfdata из очереди страниц, ибо но- вая +------------------------------------------------------------+ | алгоритм pfault /* обработка отказа системы защиты */ | | входная информация: адрес, по которому получен отказ | | выходная информация: отсутствует | | { | | найти область, запись в таблице страниц, дескриптор дис-| | кового блока, связанные с адресом, по которому получен | | отказ, заблокировать область; | | если (страница недоступна в памяти) | | перейти на out; | | если (бит копирования при записи не установлен) | | перейти на out; /* программная ошибка - сигнал */| | если (счетчик ссылок на страничный блок > 1) | | { | | выделить новую физическую страницу; | | скопировать в нее содержимое старой страницы; | | уменьшить значение счетчика ссылок на старый стра- | | ничный блок; | | перенастроить запись таблицы страниц на новую физи- | | ческую страницу; | | } | | в противном случае /* убрать страницу, поскольку она | | * никем больше не используется */ | | { | | если (копия страницы имеется на устройстве выгрузки)| | освободить место на устройстве, разорвать связь| | со страницей; | | если (страница находится в хеш-очереди страниц) | | убрать страницу из хеш-очереди; | | } | | в записи таблицы страниц установить бит модификации, | | сбросить бит копирования при записи; | | пересчитать приоритет процесса; | | проверить, не поступали ли сигналы; | | out: снять блокировку с области; | | } | +------------------------------------------------------------+ Рисунок 9.25. Алгоритм обработки отказа системы защиты 283 копия виртуальной страницы располагается не на устройстве выгрузки. Кроме того, ядро уменьшает значение счетчика ссылок на страницу в таблице исполь- зования области подкачки, и если это значение становится равным 0, освобож- дает место на устройстве (см. упражнение 9.11). Если запись в таблице страниц указывает на то, что страница недоступна, и ее бит копирования при записи установлен, выступая поводом для отказа сис- темы защиты, допустим, что система при обращении к странице сначала обраба- тывает отказ из-за недоступности данных (обратная очередность рассматривает- ся в упражнении 9.17). Несмотря на это, программа обработки отказа системы защиты все равно обязана убедиться в доступности страницы, поскольку при ус- тановке блокировки на область программа может приостановиться, а "сборщик" страниц тем временем может выгрузить страницу из памяти. Если страница не- доступна (бит доступности сброшен), программа немедленно завершит работу и процесс получит отказ из-за недоступности данных. Ядро обработает этот от- каз, но процесс вновь получит отказ системы защиты. Более чем вероятно, что заключительный отказ системы защиты будет обработан без каких-либо препятст- вий и помех, поскольку пройдет довольно значительный период времени, прежде чем страница достаточно "созреет" для выгрузки из памяти. Описанная последо- вательность событий показана на Рисунке 9.27. Запись таблицы страниц - Процесс A +-----------------------------------------------+ | Страница 828: доступна, копируется при записи +-+ +-----------------------------------------------+ | | Запись таблицы страниц - Процесс B | +-----------+ +-----------------------------------------------+ +->| Страничный| | Страница 828: доступна, копируется при записи +--->| блок 828 | +-----------------------------------------------+ +->| Счетчик | | | ссылок 3 | Запись таблицы страниц - Процесс C | +-----------+ +-----------------------------------------------+ | | Страница 828: доступна, копируется при записи +-+ +-----------------------------------------------+ (а) Перед тем, как процесс B получил отказ системы защиты Запись таблицы страниц - Процесс A +-----------------------------------------------+ +-----------+ | Страница 828: доступна, копируется при записи +-+ | Страничный| +-----------------------------------------------+ | | блок 828 | +->| Счетчик | Запись таблицы страниц - Процесс B +->| ссылок 2 | +-----------------------------------------------+ | +-----------+ | Страница 828: доступна ++| +-----------------------------------------------+|| +-----------+ +|->| Страничный| Запись таблицы страниц - Процесс C | | блок 786 | +-----------------------------------------------+ | | Счетчик | | Страница 828: доступна, копируется при записи +-+ | ссылок 1 | +-----------------------------------------------+ +-----------+ (б) После запуска программы обработки отказа системы защиты для процесса B Рисунок 9.26. Отказ системы защиты из-за установки бита копи- рования при записи 284 Перед завершением программа обработки отказа системы защиты устанавлива- ет биты модификации и защиты, но сбрасывает бит копирования при записи. Она пересчитывает приоритет процесса и проверяет, не поступали ли за время ее работы сигналы, предназначенные процессу, в точности повторяя то, что дела- ется по завершении обработки отказа из-за недопустимости данных. Процесс, получающий отказы при обращении к странице "Сборщик" страниц +------------------------------------------------------------ | - - | - Блокирует область | - - | Отказ системы защиты - | Приостанов - область - | заблокирована - | - - | - Выгрузка страницы - бит | - допустимости сброшен | - - | - - | - Выводит из приостанова | - процессы, ожидающие | - снятия с области | - блокировки | Выход из приостанова - | - - | - - | Проверка бита доступ- - | ности - сброшен - | Выход из программы обра- - | ботки отказа системы за- - | щиты - | - - | - - | Отказ из-за недоступ- - | ности данных - v Время Рисунок 9.27. Взаимодействие отказа системы защиты и отказа из-за недоступности данных 9.2.4 Замещение страниц на менее сложной технической базе Наибольшая действенность алгоритмов замещения страниц по запросу (обра- щению) достигается в том случае, если биты упоминания и модификации устанав- ливаются аппаратным путем и тем же путем вызывается отказ системы защиты при попытке записи в страницу, имеющую признак "копирования при записи". Тем не менее, указанные алгоритмы вполне применимы даже тогда, когда аппаратура распознает только бит доступности и код защиты. Если бит доступности, уста- навливаемый аппаратно, дублируется программно-устанавливаемым битом, показы- вающим, действительно ли страница доступна или нет, ядро могло бы отключить аппаратно-устанавливаемый бит и проимитировать установку остальных битов программным путем. Так, например, в машине VAX-11 бит упоминания отсутствует (см. [Levy 82]). Ядро может отключить аппаратно-устанавливаемый бит доступ- ности для страницы и дальше работать по следующему плану. Если процесс ссы- лается на страницу, он получает отказ, поскольку бит доступности сброшен, и 285 в игру вступает программа обработки отказа, исследующая страницу. Поскольку "программный" бит доступности установлен, ядро знает, что страница действи- тельно доступна и находится в памяти; оно устанавливает "программный" бит упоминания и "аппаратный" бит доступности, но ему еще предстоит узнать о том, что на страницу была сделана ссылка. Последующие ссылки на страницу уже не встретят отказ, ибо "аппаратный" бит доступности установлен. Когда с ней будет работать "сборщик" страниц, он вновь сбросит "аппаратный" бит доступ- ности, вызывая тем самым от- Аппарат- Программ- Программ- Аппарат- Программ- Программ- ный бит ный бит ный бит ный бит ный бит ный бит доступ- доступ- упомина- доступ- доступ- упомина- ности ности ния ности ности ния +---------+----------+---------+ +---------+----------+---------+ | Нет | Да | Нет | | Да | Да | Да | +---------+----------+---------+ +---------+----------+---------+ (а) До модифицирования (б) После модифицирования страницы страницы Рисунок 9.28. Имитация установки "аппаратного" бита модифика- ции программными средствами казы на все последующие обращения к странице и возвращая систему к началу цикла. Этот случай показан на Рисунке 9.28. 9.3 СИСТЕМА СМЕШАННОГО ТИПА СО СВОПИНГОМ И ПОДКАЧКОЙ ПО ЗАПРОСУ Несмотря на то, что в системах с замещением страниц по запросу обращение с памятью отличается большей гибкостью по сравнению с системами подкачки процессов, возможно возникновение ситуаций, в которых "сборщик" страниц и программа обработки отказов из-за недоступности данных начинают мешать друг другу из-за нехватки памяти. Если сумма рабочих множеств всех процессов пре- вышает объем физической памяти в машине, программа обработки отказов обычно приостанавливается, поскольку выделять процессам страницы памяти дальше ста- новится невозможным. "Сборщик" страниц не сможет достаточно быстро освобо- дить место в памяти, ибо все страницы принадлежат рабочему множеству. Произ- водительность системы падает, поскольку ядро тратит слишком много времени на верхнем уровне, с безумной скоростью перестраивая память. Ядро в версии V манипулирует алгоритмами подкачки процессов и замещения страниц так, что проблемы соперничества перестают быть неизбежными. Когда ядро не может выделить процессу страницы памяти, оно возобновляет работу процесса подкачки и переводит пользовательский процесс в состояние, эквива- лентное состоянию "готовности к запуску, будучи зарезервированным". В этом состоянии одновременно могут находиться несколько процессов. Процесс подкач- ки выгружает один за другим целые процессы, пока объем доступной памяти в системе не превысит верхнюю отметку. На каждый выгруженный процесс приходит- ся один процесс, загруженный в память из состояния "готовности к выполнению, будучи зарезервированным". Ядро загружает эти процессы не с помощью обычного алгоритма подкачки, а путем обработки отказов при обращении к соответствую- щим страницам. На последующих итерациях процесса подкачки при условии нали- чия в системе достаточного объема свободной памяти будут обработаны отказы, полученные другими пользовательскими процессами. Применение такого метода ведет к снижению частоты возникновения системных отказов и устранению сопер- ничества: по идеологии он близок к методам, используемым в операционной сис- теме VAX/VMS ([Levy 82]). 286 9.4 ВЫВОДЫ Прочитанная глава была посвящена рассмотрению алгоритмов подкачки про- цессов и замещения страниц, используемых в версии V системы UNIX. Алгоритм подкачки процессов реализует перемещение процессов целиком между основной памятью и устройством выгрузки. Ядро выгружает процессы из памяти, если их размер поглощает всю свободную память в системе (в результате выполнения функций fork, exec и sbrk или в результате естественного увеличения стека), или в том случае, если требуется освободить память для загрузки процесса. Загрузку процессов выполняет специальный процесс подкачки (процесс 0), кото- рый запускается всякий раз, как на устройстве выгрузки появляются процессы, готовые к выполнению. Процесс подкачки не прекращает своей работы до тех пор, пока на устройстве выгрузки не останется ни одного такого процесса или пока в основной памяти не останется свободного места. В последнем случае процесс подкачки пытается выгрузить что-нибудь из основной памяти, но в его обязанности входит также слежение за соблюдением требования минимальной про- должительности пребывания выгружаемых процессов в памяти (в целях предотвра- щения холостой перекачки); по этой причине процесс подкачки не всегда дости- гает успеха в своей работе. Возобновление процесса подкачки в случае возник- новения необходимости в нем производит с интервалом в одну секунду программа обработки прерываний по таймеру. В системе с замещением страниц по запросу процессы могут исполняться, даже если их виртуальное адресное пространство загружено в память не пол- ностью; поэтому виртуальный размер процесса может превышать объем доступной физической памяти в системе. Когда ядро испытывает потребность в свободных страницах, "сборщик" страниц просматривает все активные страницы в каждой области, помечая для выгрузки те из них, которые достаточно "созрели" для этого, и в конечном итоге откачивает их на устройство выгрузки. Когда про- цесс обращается к виртуальной странице, которая в настоящий момент выгружена из памяти, он получает отказ из-за недоступности данных. Ядро запускает программу обработки отказа, которая назначает области новую физическую стра- ницу памяти и копирует в нее содержимое виртуальной страницы. Повысить производительность системы при использовании алгоритма замеще- ния страниц по запросу можно несколькими способами. Во-первых, если процесс вызывает функцию fork, ядро использует бит копирования при записи, тем самым в большинстве случаев снимая необходимость в физическом копировании страниц. Во-вторых, ядро может запросить содержимое страницы исполняемого файла прямо из файловой системы, устраняя потребность в вызове функции exec для незамед- лительного считывания файла в память. Это способствует повышению производи- тельности, поскольку не исключена возможность того, что подобные страницы так никогда и не потребуются процессу, и устраняет излишнюю холостую пере- качку, имеющую место в том случае, если "сборщик" страниц выгружает эти страницы из памяти до того, как в них возникает потребность. 9.5 УПРАЖНЕНИЯ 1. Набросайте схему реализации алгоритма mfree, который освобождает прост- ранство памяти и возвращает его таблице свободного пространства. 2. В разделе 9.1.2 утверждается, что система блокирует перемещаемый про- цесс, чтобы другие процессы не могли его трогать с места до момента окончания операции. Что произошло бы, если бы система не делала этого ? 3. Предположим, что в адресном пространстве процесса располагаются таблицы используемых процессом сегментов и страниц. Каким образом ядро может выгрузить это пространство из памяти? 4. Если стек ядра находится внутри адресного пространства процесса, почему процесс не может выгружать себя сам ? Какой на Ваш взгляд должна быть системная программа выгрузки процессов, как она должна запускаться ? *5. Предположим, что ядро пытается выгрузить процесс, чтобы освободить мес- 287 то в памяти для других процессов, загружаемых с устройства выгрузки. Если ни на одном из устройств выгрузки для данного процесса нет места, процесс подкачки приостанавливает свою работу до тех пор, пока место не появится. Возможна ли ситуация, при которой все процессы, находящиеся в памяти, приостановлены, а все готовые к выполнению процессы находятся на устройстве выгрузки ? Что нужно предпринять ядру для того, чтобы ис- править это положение ? 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; | | } | +----------------------------------+ Рисунок 9.29 8. Что произойдет в результате выполнения программы, приведенной на Рисун- ке 9.29, в системе BSD 4.2 ? Каким будет стек процесса-родителя ? 9. Почему после выполнения функции fork процесса-потомка предпочтительнее запускать впереди процесса-родителя, если на разделяемых страницах биты копирования при записи установлены ? Каким образом ядро может заставить потомка запуститься первым ? *10. Алгоритм обработки отказа из-за недоступности данных, изложенный в тек- сте, загружает страницы поодиночке. Его эффективность можно повысить, если подготовить к загрузке помимо страницы, вызвавшей отказ, и все со- седние с ней страницы. Переработайте исходный алгоритм с учетом указан- ной операции. 11. В алгоритмах работы "сборщика" страниц и программы обработки отказов из-за недоступности данных предполагается, что размер страницы равен размеру дискового блока. Что нужно изменить в этих алгоритмах для того, чтобы они работали и в тех случаях, когда указанное равенство не соблю- дается ? *12. Когда процесс вызывает функцию fork (ветвится), значение счетчика ссы- лок на каждую разделяемую страницу (в таблице pfdata) увеличивается. Предположим, что "сборщик" страниц выгружает разделяемую страницу на устройство выгрузки, и один из процессов (скажем, родитель) впоследст- вии получает отказ при обращении к ней. Содержимое виртуальной страницы теперь располагается на физической странице. Объясните, почему про- цесс-потомок всегда имеет возможность получить верную копию страницы, 288 даже после того, как процесс-родитель что-то запишет на нее. Почему, когда процесс-родитель ведет запись на страницу, он должен немедленно порвать связь с ее дисковой копией ? 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]290ge[0] = i; | | } } | +------------------------------------------------------------+ 289