Страница:
Алгоритм планирования использования процессорного времени, рассмотренный
в предыдущей главе, в сильной степени зависит от выбранной стратегии управ-
ления памятью. Процесс может выполняться, если он хотя бы частично присутст-
вует в основной памяти; ЦП не может исполнять процесс, полностью выгруженный
во внешнюю память. Тем не менее, основная память - чересчур дефицитный ре-
сурс, который зачастую не может вместить все активные процессы в системе.
Если, например, в системе имеется основная память объемом 8 Мбайт, то девять
процессов размером по 1 Мбайту каждый уже не смогут в ней одновременно поме-
щаться. Какие процессы в таком случае следует размещать в памяти (хотя бы
частично), а какие нет, решает подсистема управления памятью, она же управ-
ляет участками виртуального адресного пространства процесса, не резидентными
в памяти. Она следит за объемом доступного пространства основной памяти и
имеет право периодически переписывать процессы на устройство внешней памяти,
именуемое устройством выгрузки, освобождая в основной памяти дополнительное
место. Позднее ядро может вновь поместить данные с устройства выгрузки в ос-
новную память.
В ранних версиях системы UNIX процессы переносились между основной па-
мятью и устройством выгрузки целиком и, за исключением разделяемой области
команд, отдельные независимые части процесса не могли быть объектами переме-
щения. Такая стратегия управления памятью называется свопингом (подкачкой).
Такую стратегию имело смысл реализовывать на машине типа PDP-11, где макси-
мальный размер процесса составлял 64 Кбайта. При использовании этой страте-
гии размер процесса ограничивается объемом физической памяти, доступной в
системе. Система BSD (версия 4.0) явилась главным полигоном для применения
другой стратегии, стратегии "подкачки по обращению" (demand paging), в соот-
ветствии с которой основная память обменивается с внешней не процессами, а
страницами памяти; эта стратегия поддерживается и в последних редакциях вер-
сии V системы UNIX. Держать в основной памяти весь выполняемый процесс нет
необходимости, и ядро загружает в память только отдельные страницы по запро-
су выполняющегося процесса, ссылающегося на них. Преимущество стратегии под-
качки по обращению состоит в том, что благодаря ей отображение виртуального
адресного пространства процесса на физическую память машины становится более
гибким: допускается превышение размером процесса объема доступной физической
памяти и одновременное размещение в основной памяти большего числа процес-
сов. Преимущество стратегии свопинга состоит в простоте реализации и облег-
чении "надстроечной" части системы. Обе стратегии управления памятью расс-
матриваются в настоящей главе.
Описание алгоритма свопинга можно разбить на три части: управление прос-
транством на устройстве выгрузки, выгрузка процессов из основной памяти и
подкачка процессов в основную память.
Устройство выгрузки является устройством блочного типа, которое предс-
тавляет собой конфигурируемый раздел диска. Тогда как обычно ядро выделяет
место для файлов по одному блоку за одну операцию, на устройстве выгрузки
253
пространство выделяется группами смежных блоков. Пространство, выделяемое
для файлов, используется статическим образом; поскольку схема назначения
пространства под файлы действует в течение длительного периода времени, ее
гибкость понимается в смысле сокращения числа случаев фрагментации и, следо-
вательно, объемов неиспользуемого пространства в файловой системе. Выделение
пространства на устройстве выгрузки, напротив, является временным, в сильной
степени зависящим от механизма диспетчеризации процессов. Процесс, размещае-
мый на устройстве выгрузки, в конечном итоге вернется в основную память, ос-
вобождая место на внешнем устройстве. Поскольку время является решающим фак-
тором и с учетом того, что ввод-вывод данных за одну мультиблочную операцию
происходит быстрее, чем за несколько одноблочных операций, ядро выделяет на
устройстве выгрузки непрерывное пространство, не беря во внимание возможную
фрагментацию.
Так как схема выделения пространства на устройстве выгрузки отличается
от схемы, используемой для файловых систем, структуры данных, регистрирующие
свободное пространство, должны также отличаться. Пространство, свободное в
файловых системах, описывается с помощью связного списка свободных блоков,
доступ к которому осуществляется через суперблок файловой системы, информа-
ция о свободном пространстве на устройстве выгрузки собирается в таблицу,
именуемую "карта памяти устройства". Карты памяти, помимо устройства выгруз-
ки, используются и другими системными ресурсами (например, драйверами неко-
торых устройств), они дают возможность распределять память устройства (в ви-
де смежных блоков) по методу первого подходящего.
Каждая строка в карте памяти состоит из адреса распределяемого ресурса и
количества доступных единиц ресурса; ядро интерпретирует элементы строки в
соответствии с типом карты. В самом начале карта памяти состоит из одной
строки, содержащей адрес и общее количество ресурсов. Если карта описывает
распределение памяти на устройстве выгрузки, ядро трактует каждую единицу
ресурса как группу дисковых блоков, а адрес - как смещение в блоках от нача-
ла области выгрузки. Первоначальный вид карты памяти для устройства выгруз-
ки, состоящего из 10000 блоков с начальным адресом, равным 1, показан на Ри-
сунке 9.1. Выделяя и освобождая ресурсы,
ядро корректирует карту памяти, заботясь о том, чтобы в ней постоянно содер-
жалась точная информация о свободных ресурсах в системе.
На Рисунке 9.2 представлен алгоритм выделения пространства с помощью
карт памяти (malloc). Ядро просматривает карту в поисках первой строки, со-
держащей количество единиц ресурса, достаточное для удовлетворения запроса.
Если запрос покрывает все количество единиц, содержащееся в строке, ядро
удаляет строку и уплотняет карту (то есть в карте становится на одну строку
меньше). В противном случае ядро переустанавливает адрес и число оставшихся
единиц в строке в соответствии с числом единиц, выделенных по запросу. На
Рисунке 9.3 показано, как меняется вид карты памяти для устройства выгрузки
после выделения 100, 50 и вновь 100 единиц ресурса. В конечном итоге карта
памяти принимает вид, показывающий, что первые 250 единиц ресурса выделены
по запросам, и что теперь остались свободными 9750 единиц, начиная с адреса
251.
Адрес Число единиц ресурса
+------------------------------------+
| 1 10000 |
+------------------------------------+
Рисунок 9.1. Первоначальный вид карты памяти для устройства выгрузки
254
+------------------------------------------------------------+
| алгоритм malloc /* алгоритм выделения пространства с ис-|
| пользованием карты памяти */ |
| входная информация: (1) адрес /* указывает на тип ис- |
| пользуемой карты */ |
| (2) требуемое число единиц ресурса |
| выходная информация: адрес - в случае успешного завершения |
| 0 - в противном случае |
| { |
| для (каждой строки карты) |
| { |
| если (требуемое число единиц ресурса располагается в |
| строке карты) |
| { |
| если (требуемое число == числу единиц в строке) |
| удалить строку из карты; |
| в противном случае |
| отрегулировать стартовый адрес в строке; |
| вернуть (первоначальный адрес строки); |
| } |
| } |
| вернуть (0); |
| } |
+------------------------------------------------------------+
Рисунок 9.2. Алгоритм выделения пространства с помощью карт памяти
Освобождая ресурсы, ядро ищет для них соответствующее место в карте по
адресу. При этом возможны три случая:
Адрес Число единиц ресурса Адрес Число единиц ресурса
+------------------------------+ +------------------------------+
| 1 10000 | | 101 9900 |
+------------------------------+ +------------------------------+
(а) (б)
Адрес Число единиц ресурса Адрес Число единиц ресурса
+------------------------------+ +------------------------------+
| 151 9850 | | 251 9750 |
+------------------------------+ +------------------------------+
(в) (г)
Рисунок 9.3. Выделение пространства на устройстве выгрузки
1. Освободившиеся ресурсы полностью закрывают пробел в карте памяти. Други-
ми словами, они имеют смежные адреса с адресами ресурсов из строк, не-
посредственно предшествующей и следующей за данной. В этом случае ядро
объединяет вновь освободившиеся ресурсы с ресурсами из указанных строк в
одну строку карты памяти.
2. Освободившиеся ресурсы частично закрывают пробел в карте памяти. Если
они имеют адрес, смежный с адресом ресурсов из строки, непосредственно
предшествующей или непосредственно следующей за данной (но не с адресами
из обеих строк), ядро переустанавливает значение адреса и числа ресурсов
в соответствующей строке с учетом вновь освободившихся ресурсов. Число
строк в карте памяти остается неизменным.
3. Освободившиеся ресурсы частично закрывают пробел в карте памяти, но их
255
адреса не соприкасаются с адресами каких-либо других ресурсов карты. Яд-
ро создает новую строку и вставляет ее в соответствующее место в карте.
Возвращаясь к предыдущему примеру, отметим, что если ядро освобождает 50
единиц ресурса, начиная с адреса 101, в карте памяти появится новая строка,
поскольку освободившиеся ресурсы имеют адреса, не соприкасающиеся с адресами
существующих строк карты. Если же затем ядро освободит 100 единиц ресурса,
начиная с адреса 1, первая строка карты будет расширена, поскольку освобо-
дившиеся ресурсы имеют адрес, смежный с адресом первой строки. Эволюция сос-
тояний карты памяти для данного случая показана на Рисунке 9.4.
Предположим, что ядру был сделан запрос на выделение 200 единиц (блоков)
пространства устройства выгрузки. Поскольку первая строка карты содержит ин-
формацию только о 150 единицах, ядро привлекает для удовлетворения запроса
информацию из второй строки (см. Рисунок 9.5). Наконец, предположим, что яд-
ро освобождает 350
Адрес Число единиц ресурса Адрес Число единиц ресурса
+------------------------------+ +------------------------------+
| 251 9750 | | 101 50 |
+------------------------------+ +------------------------------+
| 251 9750 |
(а) +------------------------------+
(б)
Адрес Число единиц ресурса
+------------------------------+
| 1 150 |
+------------------------------+
| 251 9750 |
+------------------------------+
(в)
Рисунок 9.4. Освобождение пространства на устройстве выгрузки
Адрес Число единиц ресурса Адрес Число единиц ресурса
+------------------------------+ +------------------------------+
| 1 150 | | 1 150 |
+------------------------------+ +------------------------------+
| 251 9750 | | 451 9550 |
+------------------------------+ +------------------------------+
(а) (б)
Рисунок 9.5. Выделение пространства на устройстве выгрузки,
описанного во второй строке карты памяти
единиц пространства, начиная с адреса 151. Несмотря на то, что эти 350 еди-
ниц были выделены ядром в разное время, не существует причины, по которой
ядро не могло бы освободить их все сразу. Ядро узнает о том, что освободив-
шиеся ресурсы полностью закрывают разрыв между первой и второй строками кар-
ты, и вместо прежних двух создает одну строку, в которую включает и освобо-
дившиеся ресурсы.
В традиционной реализации системы UNIX используется одно устройство выг-
рузки, однако в последних редакциях версии V допускается уже наличие множес-
256
тва устройств выгрузки. Ядро выбирает устройство выгрузки по схеме "кольце-
вого списка" при условии, что на устройстве имеется достаточный объем непре-
рывного адресного пространства. Администраторы могут динамически создавать и
удалять из системы устройства выгрузки. Если устройство выгрузки удаляется
из системы, ядро не выгружает данные на него; если же данные подкачиваются с
удаляемого устройства, сначала оно опорожняется и только после освобождения
принадлежащего устройству пространства устройство может быть удалено из сис-
темы.
Ядро выгружает процесс, если испытывает потребность в свободной памяти,
которая может возникнуть в следующих случаях:
1. Произведено обращение к системной функции fork, которая должна выделить
место в памяти для процесса-потомка.
2. Произведено обращение к системной функции brk, увеличивающей размер про-
цесса.
3. Размер процесса увеличился в результате естественного увеличения стека
процесса.
4. Ядру нужно освободить в памяти место для подкачки ранее выгруженных про-
цессов.
Обращение к системной функции fork выделено в особую ситуацию, поскольку
это единственный случай, когда пространство памяти, ранее занятое процессом
(родителем), не освобождается.
Когда ядро принимает решение о том, что процесс будет выгружен из основ-
ной памяти, оно уменьшает значение счетчика ссылок, ассоциированного с каж-
дой областью процесса, и выгружает те области, у которых счетчик ссылок стал
равным 0. Ядро выделяет место на устройстве выгрузки и блокирует процесс в
памяти (в случаях 1-3), запрещая его выгрузку (см. упражнение 9.12) до тех
пор, пока не закончится текущая операция выгрузки. Адрес места выгрузки об-
ластей ядро сохраняет в соответствующих записях таблицы областей.
За одну операцию ввода-вывода, в которой участвуют устройство выгрузки и
адресное пространство задачи и которая осуществляется через буферный кеш,
ядро выгружает максимально-возможное количество данных. Если аппаратура не в
состоянии передать за одну операцию содержимое нескольких страниц памяти,
перед программами ядра встает задача осуществить передачу содержимого памяти
за несколько шагов по одной странице за каждую операцию. Таким образом, точ-
ная скорость и механизм передачи данных определяются, помимо всего прочего,
возможностями дискового контроллера и стратегией распределения памяти. Нап-
ример, если используется страничная организация памяти, существует вероят-
ность, что выгружаемые данные занимают несмежные участки физической памяти.
Ядро обязано собирать информацию об адресах страниц с выгружаемыми данными,
которую впоследствии использует дисковый драйвер, осуществляющий управление
процессом ввода-вывода. Перед тем, как выгрузить следующую порцию данных,
программа подкачки (выгрузки) ждет завершения предыдущей операции ввода-вы-
вода.
При этом перед ядром не встает задача переписать на устройство выгрузки
содержимое виртуального адресного пространства процесса полностью. Вместо
этого ядро копирует на устройство выгрузки содержимое физической памяти, от-
веденной процессу, игнорируя неиспользуемые виртуальные адреса. Когда ядро
подкачивает процесс обратно в память, оно имеет у себя карту виртуальных ад-
ресов процесса и может переназначить процессу новые адреса. Ядро считывает
копию процесса из буферного кеша в физическую память, в те ячейки, для кото-
рых установлено соответствие с виртуальными адресами процесса.
На Рисунке 9.6 приведен пример отображения образа процесса в памяти на
адресное пространство устройства выгрузки (*). Процесс располагает тремя об-
ластями: команд, данных и стека. Область команд заканчивается на виртуальном
257
---------------------------------------
(*) Для простоты виртуальное адресное пространство процесса на этом и на
всех последующих рисунках изображается в виде линейного массива точек
входа в таблицу страниц, не принимая во внимание тот факт, что каждая
область обычно имеет свою отдельную таблицу страниц.
Расположение виртуальных адресов Устройство выгрузки
Виртуальные, физические адреса
+----------------------+ +-----------------+
Область | 0 278К ----+-------684--+---> |
команд +----------------------+ +-----------------+
| 1К 432К ----+------------+---> |
+----------------------+ +-----------------+
| пусто | +--------+---> |
+----------------------+ - +-----------------+
| - | -+-------+---> |
| - | -- +-----------------+
| - | --+------+---> |
+----------------------+ --- +-----------------+
Область | 64К 573К ----+---+-- +----+---> |
данных +----------------------+ -- - +-----------------+
| 65К 647К ----+----+- 690 | |
+----------------------+ - - +-----------------+
| 66К 595К ----+-----+ -
+----------------------+ -
| пусто | -
+----------------------+ -
| - | -
| - | -
+----------------------+ -
Область |128К 401К ----+-------+
стека +----------------------+
| пусто |
+----------------------+
Рисунок 9.6. Отображение пространства процесса на устройство выгрузки
адресе 2К, а область данных начинается с адреса 64К, таким образом в вирту-
альном адресном пространстве образовался пропуск в 62 Кбайта. Когда ядро
выгружает процесс, оно выгружает содержимое страниц памяти с адресами 0, 1К,
64К, 65К, 66К и 128К; на устройстве выгрузки не будет отведено место под
пропуск в 62 Кбайта между областями команд и данных, как и под пропуск в 61
Кбайт между областями данных и стека, ибо пространство на устройстве выгруз-
ки заполняется непрерывно. Когда ядро загружает процесс обратно в память,
оно уже знает из карты памяти процесса о том, что процесс имеет в своем
пространстве неиспользуемый участок размером 62К, и с учетом этого соответс-
твенно выделяет физическую память. Этот случай проиллюстрирован с помощью
Рисунка 9.7. Сравнение Рисунков 9.6 и 9.7 показывает, что физические адреса,
занимаемые процессом до и после выгрузки, не
совпадают между собой; однако, на пользовательском уровне процесс не обраща-
ет на это никакого внимания, поскольку содержимое его виртуального простран-
ства осталось тем же самым.
Теоретически все пространство памяти, занятое процессом, в том числе его
личное адресное пространство и стек ядра, может быть выгружено, хотя ядро и
может временно заблокировать область в памяти на время выполнения критичес-
кой операции. Однако практически, ядро не выгружает содержимое адресного
258
Расположение виртуальных адресов Устройство выгрузки
Виртуальные, физические адреса
+----------------------+ +-----------------+
Область | 0 401К <---+-------684--+---- |
команд +----------------------+ +-----------------+
| 1К 370К <---+------------+---- |
+----------------------+ +-----------------+
| пусто | +--------+---- |
+----------------------+ - +-----------------+
| - | -+-------+---- |
| - | -- +-----------------+
| - | --+------+---- |
+----------------------+ --- +-----------------+
Область | 64К 788К <---+---+-- +----+---- |
данных +----------------------+ -- - +-----------------+
| 65К 492К <---+----+- 690 | |
+----------------------+ - - +-----------------+
| 66К 647К <---+-----+ -
+----------------------+ -
| пусто | -
+----------------------+ -
| - | -
| - | -
+----------------------+ -
Область |128К 955К <---+-------+
стека +----------------------+
| пусто |
+----------------------+
Рисунок 9.7. Загрузка процесса в память
пространства процесса, если в нем находятся таблицы преобразования адресов
(адресные таблицы) процесса. Практическими соображениями так же диктуются
условия, при которых процесс может выгрузить самого себя или потребовать
своей выгрузки другим процессом (см. упражнение 9.4).
В описании системной функции fork (раздел 7.1) предполагалось, что про-
цесс-родитель получил в свое распоряжение память, достаточную для создания
контекста потомка. Если это условие не выполняется, ядро выгружает процесс
из памяти, не освобождая пространство памяти, занимаемое его (родителя) ко-
пией. Когда процедура выгрузки завершится, процесс-потомок будет распола-
гаться на устройстве выгрузки; процесс-родитель переводит своего потомка в
состояние "готовности к выполнению" (см. Рисунок 6.1) и возвращается в режим
задачи. Поскольку процесс-потомок находится в состоянии "готовности к выпол-
нению", программа подкачки в конце концов загрузит его в память, где ядро
запустит его на выполнение; потомок завершит тем самым свою роль в выполне-
нии системной функции fork и вернется в режим задачи.
Если процесс испытывает потребность в дополнительной физической памяти,
либо в результате расширения стека, либо в результате запуска функции brk, и
если эта потребность превышает доступные резервы памяти, ядро выполняет опе-
рацию выгрузки процесса с расширением его размера на устройстве выгрузки. На
устройстве выгрузки ядро резервирует место для размещения процесса с учетом
259
Первоначальное Расширенный
расположение формат
Виртуальные, Виртуальные, Устройство
физические адреса физические адреса выгрузки
+------------+ +------------+ +---------+
Область| 0 278К | | 0 278К -+-----684--+---> |
команд +------------+ +------------+ +---------+
| 1К 432К | | 1К 432К -+----------+---> |
+------------+ +------------+ +---------+
| пусто | | пусто | +--------+---> |
+------------+ +------------+ - +---------+
| - | | - | -+-------+---> |
| - | | - | -- +---------+
| - | | - | --+------+---> |
+------------+ +------------+ --- +---------+
Область| 64К 573К | | 64К 573К -+-+-- +----+---> |
данных +------------+ +------------+ -- - +---------+
| 65К 647К | | 65К 647К -+--+- 690 | |
+------------+ +------------+ - - +---------+
| 66К 595К | | 66К 595К -+---+ 691 +|---> |
+------------+ +------------+ - -+---------+
| пусто | | пусто | - -
+------------+ +------------+ - -
| - | | - | - -
| - | | - | - -
+------------+ +------------+ - -
Область|128К 401К | |128К 401К -+-----+ -
стека +------------+ +------------+ -
| пусто | Новая |129К ... -+---------+
+------------+ страница+------------+
| пусто |
+------------+
Рисунок 9.8. Перенастройка карты памяти в случае выгрузки с расширением
расширения его размера. Затем производится перенастройка таблицы преобразо-
вания адресов процесса с учетом дополнительного виртуального пространства,
но без выделения физической памяти (в связи с ее отсутствием). Наконец, ядро
выгружает процесс, выполняя процедуру выгрузки обычным порядком и обнуляя
вновь выделенное пространство на устройстве (см. Рисунок 9.8). Когда нес-
колько позже ядро будет загружать процесс обратно в память, физическое прос-
транство будет выделено уже с учетом нового состояния таблицы преобразования
адресов. В момент возобновления у процесса уже будет в распоряжении память
достаточного объема.
Нулевой процесс (процесс подкачки) является единственным процессом, заг-
ружающим другие процессы в память с устройств выгрузки. Процесс подкачки на-
чинает работу по выполнению этой своей единственной функции по окончании
инициализации системы (как уже говорилось в разделе 7.9). Он загружает про-
цессы в память и, если ему не хватает места в памяти, выгружает оттуда неко-
торые из процессов, находящихся там. Если у процесса подкачки нет работы
(например, отсутствуют процессы, ожидающие загрузки в память) или же он не в
состоянии выполнить свою работу (ни один из процессов не может быть выгру-
жен), процесс подкачки приостанавливается; ядро периодически возобновляет
260
его выполнение. Ядро планирует запуск процесса подкачки точно так же, как
делает это в отношении других процессов, ориентируясь на более высокий прио-
ритет, при этом процесс подкачки выполняется только в режиме ядра. Процесс
подкачки не обращается к функциям операционной системы, а использует в своей
работе только внутренние функции ядра; он является архетипом всех процессов
ядра.
Как уже вкратце говорилось в главе 8, программа обработки прерываний по
таймеру измеряет время нахождения каждого процесса в памяти или в состоянии
выгрузки. Когда процесс подкачки возобновляет свою работу по загрузке про-
цессов в память, он просматривает все процессы, находящиеся в состоянии "го-
товности к выполнению, будучи выгруженными", и выбирает из них один, который
находится в этом состоянии дольше остальных (см. Рисунок 9.9). Если имеется
достаточно свободной памяти, процесс подкачки загружает выбранный процесс,
выполняя операции в последовательности, обратной выгрузке процесса. Сначала
выделяется физическая память, затем с устройства выгрузки считывается нужный
процесс и освобождается место на устройстве.
Если процесс подкачки выполнил процедуру загрузки успешно, он вновь
просматривает совокупность выгруженных, но готовых к выполнению процессов в
поисках следующего процесса, который предполагается загрузить в память, и
повторяет указанную последовательность действий. В конечном итоге возникает
одна из следующих ситуаций:
* На устройстве выгрузки больше нет ни одного процесса, готового к выпол-
нению. Процесс подкачки приостанавливает свою работу до тех пор, пока не
возобновится процесс на устройстве выгрузки или пока ядро не выгрузит
процесс, готовый к выполнению. (Вспомним диаграмму состояний на Рисунке
6.1).
* Процесс подкачки обнаружил процесс, готовый к загрузке, но в системе не-
в предыдущей главе, в сильной степени зависит от выбранной стратегии управ-
ления памятью. Процесс может выполняться, если он хотя бы частично присутст-
вует в основной памяти; ЦП не может исполнять процесс, полностью выгруженный
во внешнюю память. Тем не менее, основная память - чересчур дефицитный ре-
сурс, который зачастую не может вместить все активные процессы в системе.
Если, например, в системе имеется основная память объемом 8 Мбайт, то девять
процессов размером по 1 Мбайту каждый уже не смогут в ней одновременно поме-
щаться. Какие процессы в таком случае следует размещать в памяти (хотя бы
частично), а какие нет, решает подсистема управления памятью, она же управ-
ляет участками виртуального адресного пространства процесса, не резидентными
в памяти. Она следит за объемом доступного пространства основной памяти и
имеет право периодически переписывать процессы на устройство внешней памяти,
именуемое устройством выгрузки, освобождая в основной памяти дополнительное
место. Позднее ядро может вновь поместить данные с устройства выгрузки в ос-
новную память.
В ранних версиях системы UNIX процессы переносились между основной па-
мятью и устройством выгрузки целиком и, за исключением разделяемой области
команд, отдельные независимые части процесса не могли быть объектами переме-
щения. Такая стратегия управления памятью называется свопингом (подкачкой).
Такую стратегию имело смысл реализовывать на машине типа PDP-11, где макси-
мальный размер процесса составлял 64 Кбайта. При использовании этой страте-
гии размер процесса ограничивается объемом физической памяти, доступной в
системе. Система BSD (версия 4.0) явилась главным полигоном для применения
другой стратегии, стратегии "подкачки по обращению" (demand paging), в соот-
ветствии с которой основная память обменивается с внешней не процессами, а
страницами памяти; эта стратегия поддерживается и в последних редакциях вер-
сии V системы UNIX. Держать в основной памяти весь выполняемый процесс нет
необходимости, и ядро загружает в память только отдельные страницы по запро-
су выполняющегося процесса, ссылающегося на них. Преимущество стратегии под-
качки по обращению состоит в том, что благодаря ей отображение виртуального
адресного пространства процесса на физическую память машины становится более
гибким: допускается превышение размером процесса объема доступной физической
памяти и одновременное размещение в основной памяти большего числа процес-
сов. Преимущество стратегии свопинга состоит в простоте реализации и облег-
чении "надстроечной" части системы. Обе стратегии управления памятью расс-
матриваются в настоящей главе.
Описание алгоритма свопинга можно разбить на три части: управление прос-
транством на устройстве выгрузки, выгрузка процессов из основной памяти и
подкачка процессов в основную память.
Устройство выгрузки является устройством блочного типа, которое предс-
тавляет собой конфигурируемый раздел диска. Тогда как обычно ядро выделяет
место для файлов по одному блоку за одну операцию, на устройстве выгрузки
253
пространство выделяется группами смежных блоков. Пространство, выделяемое
для файлов, используется статическим образом; поскольку схема назначения
пространства под файлы действует в течение длительного периода времени, ее
гибкость понимается в смысле сокращения числа случаев фрагментации и, следо-
вательно, объемов неиспользуемого пространства в файловой системе. Выделение
пространства на устройстве выгрузки, напротив, является временным, в сильной
степени зависящим от механизма диспетчеризации процессов. Процесс, размещае-
мый на устройстве выгрузки, в конечном итоге вернется в основную память, ос-
вобождая место на внешнем устройстве. Поскольку время является решающим фак-
тором и с учетом того, что ввод-вывод данных за одну мультиблочную операцию
происходит быстрее, чем за несколько одноблочных операций, ядро выделяет на
устройстве выгрузки непрерывное пространство, не беря во внимание возможную
фрагментацию.
Так как схема выделения пространства на устройстве выгрузки отличается
от схемы, используемой для файловых систем, структуры данных, регистрирующие
свободное пространство, должны также отличаться. Пространство, свободное в
файловых системах, описывается с помощью связного списка свободных блоков,
доступ к которому осуществляется через суперблок файловой системы, информа-
ция о свободном пространстве на устройстве выгрузки собирается в таблицу,
именуемую "карта памяти устройства". Карты памяти, помимо устройства выгруз-
ки, используются и другими системными ресурсами (например, драйверами неко-
торых устройств), они дают возможность распределять память устройства (в ви-
де смежных блоков) по методу первого подходящего.
Каждая строка в карте памяти состоит из адреса распределяемого ресурса и
количества доступных единиц ресурса; ядро интерпретирует элементы строки в
соответствии с типом карты. В самом начале карта памяти состоит из одной
строки, содержащей адрес и общее количество ресурсов. Если карта описывает
распределение памяти на устройстве выгрузки, ядро трактует каждую единицу
ресурса как группу дисковых блоков, а адрес - как смещение в блоках от нача-
ла области выгрузки. Первоначальный вид карты памяти для устройства выгруз-
ки, состоящего из 10000 блоков с начальным адресом, равным 1, показан на Ри-
сунке 9.1. Выделяя и освобождая ресурсы,
ядро корректирует карту памяти, заботясь о том, чтобы в ней постоянно содер-
жалась точная информация о свободных ресурсах в системе.
На Рисунке 9.2 представлен алгоритм выделения пространства с помощью
карт памяти (malloc). Ядро просматривает карту в поисках первой строки, со-
держащей количество единиц ресурса, достаточное для удовлетворения запроса.
Если запрос покрывает все количество единиц, содержащееся в строке, ядро
удаляет строку и уплотняет карту (то есть в карте становится на одну строку
меньше). В противном случае ядро переустанавливает адрес и число оставшихся
единиц в строке в соответствии с числом единиц, выделенных по запросу. На
Рисунке 9.3 показано, как меняется вид карты памяти для устройства выгрузки
после выделения 100, 50 и вновь 100 единиц ресурса. В конечном итоге карта
памяти принимает вид, показывающий, что первые 250 единиц ресурса выделены
по запросам, и что теперь остались свободными 9750 единиц, начиная с адреса
251.
Адрес Число единиц ресурса
+------------------------------------+
| 1 10000 |
+------------------------------------+
Рисунок 9.1. Первоначальный вид карты памяти для устройства выгрузки
254
+------------------------------------------------------------+
| алгоритм malloc /* алгоритм выделения пространства с ис-|
| пользованием карты памяти */ |
| входная информация: (1) адрес /* указывает на тип ис- |
| пользуемой карты */ |
| (2) требуемое число единиц ресурса |
| выходная информация: адрес - в случае успешного завершения |
| 0 - в противном случае |
| { |
| для (каждой строки карты) |
| { |
| если (требуемое число единиц ресурса располагается в |
| строке карты) |
| { |
| если (требуемое число == числу единиц в строке) |
| удалить строку из карты; |
| в противном случае |
| отрегулировать стартовый адрес в строке; |
| вернуть (первоначальный адрес строки); |
| } |
| } |
| вернуть (0); |
| } |
+------------------------------------------------------------+
Рисунок 9.2. Алгоритм выделения пространства с помощью карт памяти
Освобождая ресурсы, ядро ищет для них соответствующее место в карте по
адресу. При этом возможны три случая:
Адрес Число единиц ресурса Адрес Число единиц ресурса
+------------------------------+ +------------------------------+
| 1 10000 | | 101 9900 |
+------------------------------+ +------------------------------+
(а) (б)
Адрес Число единиц ресурса Адрес Число единиц ресурса
+------------------------------+ +------------------------------+
| 151 9850 | | 251 9750 |
+------------------------------+ +------------------------------+
(в) (г)
Рисунок 9.3. Выделение пространства на устройстве выгрузки
1. Освободившиеся ресурсы полностью закрывают пробел в карте памяти. Други-
ми словами, они имеют смежные адреса с адресами ресурсов из строк, не-
посредственно предшествующей и следующей за данной. В этом случае ядро
объединяет вновь освободившиеся ресурсы с ресурсами из указанных строк в
одну строку карты памяти.
2. Освободившиеся ресурсы частично закрывают пробел в карте памяти. Если
они имеют адрес, смежный с адресом ресурсов из строки, непосредственно
предшествующей или непосредственно следующей за данной (но не с адресами
из обеих строк), ядро переустанавливает значение адреса и числа ресурсов
в соответствующей строке с учетом вновь освободившихся ресурсов. Число
строк в карте памяти остается неизменным.
3. Освободившиеся ресурсы частично закрывают пробел в карте памяти, но их
255
адреса не соприкасаются с адресами каких-либо других ресурсов карты. Яд-
ро создает новую строку и вставляет ее в соответствующее место в карте.
Возвращаясь к предыдущему примеру, отметим, что если ядро освобождает 50
единиц ресурса, начиная с адреса 101, в карте памяти появится новая строка,
поскольку освободившиеся ресурсы имеют адреса, не соприкасающиеся с адресами
существующих строк карты. Если же затем ядро освободит 100 единиц ресурса,
начиная с адреса 1, первая строка карты будет расширена, поскольку освобо-
дившиеся ресурсы имеют адрес, смежный с адресом первой строки. Эволюция сос-
тояний карты памяти для данного случая показана на Рисунке 9.4.
Предположим, что ядру был сделан запрос на выделение 200 единиц (блоков)
пространства устройства выгрузки. Поскольку первая строка карты содержит ин-
формацию только о 150 единицах, ядро привлекает для удовлетворения запроса
информацию из второй строки (см. Рисунок 9.5). Наконец, предположим, что яд-
ро освобождает 350
Адрес Число единиц ресурса Адрес Число единиц ресурса
+------------------------------+ +------------------------------+
| 251 9750 | | 101 50 |
+------------------------------+ +------------------------------+
| 251 9750 |
(а) +------------------------------+
(б)
Адрес Число единиц ресурса
+------------------------------+
| 1 150 |
+------------------------------+
| 251 9750 |
+------------------------------+
(в)
Рисунок 9.4. Освобождение пространства на устройстве выгрузки
Адрес Число единиц ресурса Адрес Число единиц ресурса
+------------------------------+ +------------------------------+
| 1 150 | | 1 150 |
+------------------------------+ +------------------------------+
| 251 9750 | | 451 9550 |
+------------------------------+ +------------------------------+
(а) (б)
Рисунок 9.5. Выделение пространства на устройстве выгрузки,
описанного во второй строке карты памяти
единиц пространства, начиная с адреса 151. Несмотря на то, что эти 350 еди-
ниц были выделены ядром в разное время, не существует причины, по которой
ядро не могло бы освободить их все сразу. Ядро узнает о том, что освободив-
шиеся ресурсы полностью закрывают разрыв между первой и второй строками кар-
ты, и вместо прежних двух создает одну строку, в которую включает и освобо-
дившиеся ресурсы.
В традиционной реализации системы UNIX используется одно устройство выг-
рузки, однако в последних редакциях версии V допускается уже наличие множес-
256
тва устройств выгрузки. Ядро выбирает устройство выгрузки по схеме "кольце-
вого списка" при условии, что на устройстве имеется достаточный объем непре-
рывного адресного пространства. Администраторы могут динамически создавать и
удалять из системы устройства выгрузки. Если устройство выгрузки удаляется
из системы, ядро не выгружает данные на него; если же данные подкачиваются с
удаляемого устройства, сначала оно опорожняется и только после освобождения
принадлежащего устройству пространства устройство может быть удалено из сис-
темы.
Ядро выгружает процесс, если испытывает потребность в свободной памяти,
которая может возникнуть в следующих случаях:
1. Произведено обращение к системной функции fork, которая должна выделить
место в памяти для процесса-потомка.
2. Произведено обращение к системной функции brk, увеличивающей размер про-
цесса.
3. Размер процесса увеличился в результате естественного увеличения стека
процесса.
4. Ядру нужно освободить в памяти место для подкачки ранее выгруженных про-
цессов.
Обращение к системной функции fork выделено в особую ситуацию, поскольку
это единственный случай, когда пространство памяти, ранее занятое процессом
(родителем), не освобождается.
Когда ядро принимает решение о том, что процесс будет выгружен из основ-
ной памяти, оно уменьшает значение счетчика ссылок, ассоциированного с каж-
дой областью процесса, и выгружает те области, у которых счетчик ссылок стал
равным 0. Ядро выделяет место на устройстве выгрузки и блокирует процесс в
памяти (в случаях 1-3), запрещая его выгрузку (см. упражнение 9.12) до тех
пор, пока не закончится текущая операция выгрузки. Адрес места выгрузки об-
ластей ядро сохраняет в соответствующих записях таблицы областей.
За одну операцию ввода-вывода, в которой участвуют устройство выгрузки и
адресное пространство задачи и которая осуществляется через буферный кеш,
ядро выгружает максимально-возможное количество данных. Если аппаратура не в
состоянии передать за одну операцию содержимое нескольких страниц памяти,
перед программами ядра встает задача осуществить передачу содержимого памяти
за несколько шагов по одной странице за каждую операцию. Таким образом, точ-
ная скорость и механизм передачи данных определяются, помимо всего прочего,
возможностями дискового контроллера и стратегией распределения памяти. Нап-
ример, если используется страничная организация памяти, существует вероят-
ность, что выгружаемые данные занимают несмежные участки физической памяти.
Ядро обязано собирать информацию об адресах страниц с выгружаемыми данными,
которую впоследствии использует дисковый драйвер, осуществляющий управление
процессом ввода-вывода. Перед тем, как выгрузить следующую порцию данных,
программа подкачки (выгрузки) ждет завершения предыдущей операции ввода-вы-
вода.
При этом перед ядром не встает задача переписать на устройство выгрузки
содержимое виртуального адресного пространства процесса полностью. Вместо
этого ядро копирует на устройство выгрузки содержимое физической памяти, от-
веденной процессу, игнорируя неиспользуемые виртуальные адреса. Когда ядро
подкачивает процесс обратно в память, оно имеет у себя карту виртуальных ад-
ресов процесса и может переназначить процессу новые адреса. Ядро считывает
копию процесса из буферного кеша в физическую память, в те ячейки, для кото-
рых установлено соответствие с виртуальными адресами процесса.
На Рисунке 9.6 приведен пример отображения образа процесса в памяти на
адресное пространство устройства выгрузки (*). Процесс располагает тремя об-
ластями: команд, данных и стека. Область команд заканчивается на виртуальном
257
---------------------------------------
(*) Для простоты виртуальное адресное пространство процесса на этом и на
всех последующих рисунках изображается в виде линейного массива точек
входа в таблицу страниц, не принимая во внимание тот факт, что каждая
область обычно имеет свою отдельную таблицу страниц.
Расположение виртуальных адресов Устройство выгрузки
Виртуальные, физические адреса
+----------------------+ +-----------------+
Область | 0 278К ----+-------684--+---> |
команд +----------------------+ +-----------------+
| 1К 432К ----+------------+---> |
+----------------------+ +-----------------+
| пусто | +--------+---> |
+----------------------+ - +-----------------+
| - | -+-------+---> |
| - | -- +-----------------+
| - | --+------+---> |
+----------------------+ --- +-----------------+
Область | 64К 573К ----+---+-- +----+---> |
данных +----------------------+ -- - +-----------------+
| 65К 647К ----+----+- 690 | |
+----------------------+ - - +-----------------+
| 66К 595К ----+-----+ -
+----------------------+ -
| пусто | -
+----------------------+ -
| - | -
| - | -
+----------------------+ -
Область |128К 401К ----+-------+
стека +----------------------+
| пусто |
+----------------------+
Рисунок 9.6. Отображение пространства процесса на устройство выгрузки
адресе 2К, а область данных начинается с адреса 64К, таким образом в вирту-
альном адресном пространстве образовался пропуск в 62 Кбайта. Когда ядро
выгружает процесс, оно выгружает содержимое страниц памяти с адресами 0, 1К,
64К, 65К, 66К и 128К; на устройстве выгрузки не будет отведено место под
пропуск в 62 Кбайта между областями команд и данных, как и под пропуск в 61
Кбайт между областями данных и стека, ибо пространство на устройстве выгруз-
ки заполняется непрерывно. Когда ядро загружает процесс обратно в память,
оно уже знает из карты памяти процесса о том, что процесс имеет в своем
пространстве неиспользуемый участок размером 62К, и с учетом этого соответс-
твенно выделяет физическую память. Этот случай проиллюстрирован с помощью
Рисунка 9.7. Сравнение Рисунков 9.6 и 9.7 показывает, что физические адреса,
занимаемые процессом до и после выгрузки, не
совпадают между собой; однако, на пользовательском уровне процесс не обраща-
ет на это никакого внимания, поскольку содержимое его виртуального простран-
ства осталось тем же самым.
Теоретически все пространство памяти, занятое процессом, в том числе его
личное адресное пространство и стек ядра, может быть выгружено, хотя ядро и
может временно заблокировать область в памяти на время выполнения критичес-
кой операции. Однако практически, ядро не выгружает содержимое адресного
258
Расположение виртуальных адресов Устройство выгрузки
Виртуальные, физические адреса
+----------------------+ +-----------------+
Область | 0 401К <---+-------684--+---- |
команд +----------------------+ +-----------------+
| 1К 370К <---+------------+---- |
+----------------------+ +-----------------+
| пусто | +--------+---- |
+----------------------+ - +-----------------+
| - | -+-------+---- |
| - | -- +-----------------+
| - | --+------+---- |
+----------------------+ --- +-----------------+
Область | 64К 788К <---+---+-- +----+---- |
данных +----------------------+ -- - +-----------------+
| 65К 492К <---+----+- 690 | |
+----------------------+ - - +-----------------+
| 66К 647К <---+-----+ -
+----------------------+ -
| пусто | -
+----------------------+ -
| - | -
| - | -
+----------------------+ -
Область |128К 955К <---+-------+
стека +----------------------+
| пусто |
+----------------------+
Рисунок 9.7. Загрузка процесса в память
пространства процесса, если в нем находятся таблицы преобразования адресов
(адресные таблицы) процесса. Практическими соображениями так же диктуются
условия, при которых процесс может выгрузить самого себя или потребовать
своей выгрузки другим процессом (см. упражнение 9.4).
В описании системной функции fork (раздел 7.1) предполагалось, что про-
цесс-родитель получил в свое распоряжение память, достаточную для создания
контекста потомка. Если это условие не выполняется, ядро выгружает процесс
из памяти, не освобождая пространство памяти, занимаемое его (родителя) ко-
пией. Когда процедура выгрузки завершится, процесс-потомок будет распола-
гаться на устройстве выгрузки; процесс-родитель переводит своего потомка в
состояние "готовности к выполнению" (см. Рисунок 6.1) и возвращается в режим
задачи. Поскольку процесс-потомок находится в состоянии "готовности к выпол-
нению", программа подкачки в конце концов загрузит его в память, где ядро
запустит его на выполнение; потомок завершит тем самым свою роль в выполне-
нии системной функции fork и вернется в режим задачи.
Если процесс испытывает потребность в дополнительной физической памяти,
либо в результате расширения стека, либо в результате запуска функции brk, и
если эта потребность превышает доступные резервы памяти, ядро выполняет опе-
рацию выгрузки процесса с расширением его размера на устройстве выгрузки. На
устройстве выгрузки ядро резервирует место для размещения процесса с учетом
259
Первоначальное Расширенный
расположение формат
Виртуальные, Виртуальные, Устройство
физические адреса физические адреса выгрузки
+------------+ +------------+ +---------+
Область| 0 278К | | 0 278К -+-----684--+---> |
команд +------------+ +------------+ +---------+
| 1К 432К | | 1К 432К -+----------+---> |
+------------+ +------------+ +---------+
| пусто | | пусто | +--------+---> |
+------------+ +------------+ - +---------+
| - | | - | -+-------+---> |
| - | | - | -- +---------+
| - | | - | --+------+---> |
+------------+ +------------+ --- +---------+
Область| 64К 573К | | 64К 573К -+-+-- +----+---> |
данных +------------+ +------------+ -- - +---------+
| 65К 647К | | 65К 647К -+--+- 690 | |
+------------+ +------------+ - - +---------+
| 66К 595К | | 66К 595К -+---+ 691 +|---> |
+------------+ +------------+ - -+---------+
| пусто | | пусто | - -
+------------+ +------------+ - -
| - | | - | - -
| - | | - | - -
+------------+ +------------+ - -
Область|128К 401К | |128К 401К -+-----+ -
стека +------------+ +------------+ -
| пусто | Новая |129К ... -+---------+
+------------+ страница+------------+
| пусто |
+------------+
Рисунок 9.8. Перенастройка карты памяти в случае выгрузки с расширением
расширения его размера. Затем производится перенастройка таблицы преобразо-
вания адресов процесса с учетом дополнительного виртуального пространства,
но без выделения физической памяти (в связи с ее отсутствием). Наконец, ядро
выгружает процесс, выполняя процедуру выгрузки обычным порядком и обнуляя
вновь выделенное пространство на устройстве (см. Рисунок 9.8). Когда нес-
колько позже ядро будет загружать процесс обратно в память, физическое прос-
транство будет выделено уже с учетом нового состояния таблицы преобразования
адресов. В момент возобновления у процесса уже будет в распоряжении память
достаточного объема.
Нулевой процесс (процесс подкачки) является единственным процессом, заг-
ружающим другие процессы в память с устройств выгрузки. Процесс подкачки на-
чинает работу по выполнению этой своей единственной функции по окончании
инициализации системы (как уже говорилось в разделе 7.9). Он загружает про-
цессы в память и, если ему не хватает места в памяти, выгружает оттуда неко-
торые из процессов, находящихся там. Если у процесса подкачки нет работы
(например, отсутствуют процессы, ожидающие загрузки в память) или же он не в
состоянии выполнить свою работу (ни один из процессов не может быть выгру-
жен), процесс подкачки приостанавливается; ядро периодически возобновляет
260
его выполнение. Ядро планирует запуск процесса подкачки точно так же, как
делает это в отношении других процессов, ориентируясь на более высокий прио-
ритет, при этом процесс подкачки выполняется только в режиме ядра. Процесс
подкачки не обращается к функциям операционной системы, а использует в своей
работе только внутренние функции ядра; он является архетипом всех процессов
ядра.
Как уже вкратце говорилось в главе 8, программа обработки прерываний по
таймеру измеряет время нахождения каждого процесса в памяти или в состоянии
выгрузки. Когда процесс подкачки возобновляет свою работу по загрузке про-
цессов в память, он просматривает все процессы, находящиеся в состоянии "го-
товности к выполнению, будучи выгруженными", и выбирает из них один, который
находится в этом состоянии дольше остальных (см. Рисунок 9.9). Если имеется
достаточно свободной памяти, процесс подкачки загружает выбранный процесс,
выполняя операции в последовательности, обратной выгрузке процесса. Сначала
выделяется физическая память, затем с устройства выгрузки считывается нужный
процесс и освобождается место на устройстве.
Если процесс подкачки выполнил процедуру загрузки успешно, он вновь
просматривает совокупность выгруженных, но готовых к выполнению процессов в
поисках следующего процесса, который предполагается загрузить в память, и
повторяет указанную последовательность действий. В конечном итоге возникает
одна из следующих ситуаций:
* На устройстве выгрузки больше нет ни одного процесса, готового к выпол-
нению. Процесс подкачки приостанавливает свою работу до тех пор, пока не
возобновится процесс на устройстве выгрузки или пока ядро не выгрузит
процесс, готовый к выполнению. (Вспомним диаграмму состояний на Рисунке
6.1).
* Процесс подкачки обнаружил процесс, готовый к загрузке, но в системе не-