ГЛАВА 9. АЛГОРИТМЫ УПРАВЛЕНИЯ ПАМЯТЬЮ Алгоритм планирования использования процессорного времени, рассмотренный в предыдущей главе, в сильной степени зависит от выбранной стратегии управ- ления памятью. Процесс может выполняться, если он хотя бы частично присутст- вует в основной памяти; ЦП не может исполнять процесс, полностью выгруженный во внешнюю память. Тем не менее, основная память - чересчур дефицитный ре- сурс, который зачастую не может вместить все активные процессы в системе. Если, например, в системе имеется основная память объемом 8 Мбайт, то девять процессов размером по 1 Мбайту каждый уже не смогут в ней одновременно поме- щаться. Какие процессы в таком случае следует размещать в памяти (хотя бы частично), а какие нет, решает подсистема управления памятью, она же управ- ляет участками виртуального адресного пространства процесса, не резидентными в памяти. Она следит за объемом доступного пространства основной памяти и имеет право периодически переписывать процессы на устройство внешней памяти, именуемое устройством выгрузки, освобождая в основной памяти дополнительное место. Позднее ядро может вновь поместить данные с устройства выгрузки в ос- новную память. В ранних версиях системы UNIX процессы переносились между основной па- мятью и устройством выгрузки целиком и, за исключением разделяемой области команд, отдельные независимые части процесса не могли быть объектами переме- щения. Такая стратегия управления памятью называется свопингом (подкачкой). Такую стратегию имело смысл реализовывать на машине типа PDP-11, где макси- мальный размер процесса составлял 64 Кбайта. При использовании этой страте- гии размер процесса ограничивается объемом физической памяти, доступной в системе. Система BSD (версия 4.0) явилась главным полигоном для применения другой стратегии, стратегии "подкачки по обращению" (demand paging), в соот- ветствии с которой основная память обменивается с внешней не процессами, а страницами памяти; эта стратегия поддерживается и в последних редакциях вер- сии V системы UNIX. Держать в основной памяти весь выполняемый процесс нет необходимости, и ядро загружает в память только отдельные страницы по запро- су выполняющегося процесса, ссылающегося на них. Преимущество стратегии под- качки по обращению состоит в том, что благодаря ей отображение виртуального адресного пространства процесса на физическую память машины становится более гибким: допускается превышение размером процесса объема доступной физической памяти и одновременное размещение в основной памяти большего числа процес- сов. Преимущество стратегии свопинга состоит в простоте реализации и облег- чении "надстроечной" части системы. Обе стратегии управления памятью расс- матриваются в настоящей главе. 9.1 СВОПИНГ Описание алгоритма свопинга можно разбить на три части: управление прос- транством на устройстве выгрузки, выгрузка процессов из основной памяти и подкачка процессов в основную память. 9.1.1 Управление пространством на устройстве выгрузки Устройство выгрузки является устройством блочного типа, которое предс- тавляет собой конфигурируемый раздел диска. Тогда как обычно ядро выделяет место для файлов по одному блоку за одну операцию, на устройстве выгрузки 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 тва устройств выгрузки. Ядро выбирает устройство выгрузки по схеме "кольце- вого списка" при условии, что на устройстве имеется достаточный объем непре- рывного адресного пространства. Администраторы могут динамически создавать и удалять из системы устройства выгрузки. Если устройство выгрузки удаляется из системы, ядро не выгружает данные на него; если же данные подкачиваются с удаляемого устройства, сначала оно опорожняется и только после освобождения принадлежащего устройству пространства устройство может быть удалено из сис- темы. 9.1.2 Выгрузка процессов Ядро выгружает процесс, если испытывает потребность в свободной памяти, которая может возникнуть в следующих случаях: 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). 9.1.2.1 Выгрузка при выполнении системной функции fork В описании системной функции fork (раздел 7.1) предполагалось, что про- цесс-родитель получил в свое распоряжение память, достаточную для создания контекста потомка. Если это условие не выполняется, ядро выгружает процесс из памяти, не освобождая пространство памяти, занимаемое его (родителя) ко- пией. Когда процедура выгрузки завершится, процесс-потомок будет распола- гаться на устройстве выгрузки; процесс-родитель переводит своего потомка в состояние "готовности к выполнению" (см. Рисунок 6.1) и возвращается в режим задачи. Поскольку процесс-потомок находится в состоянии "готовности к выпол- нению", программа подкачки в конце концов загрузит его в память, где ядро запустит его на выполнение; потомок завершит тем самым свою роль в выполне- нии системной функции fork и вернется в режим задачи. 9.1.2.2 Выгрузка с расширением Если процесс испытывает потребность в дополнительной физической памяти, либо в результате расширения стека, либо в результате запуска функции 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). Когда нес- колько позже ядро будет загружать процесс обратно в память, физическое прос- транство будет выделено уже с учетом нового состояния таблицы преобразования адресов. В момент возобновления у процесса уже будет в распоряжении память достаточного объема. 9.1.3 Загрузка (подкачка) процессов Нулевой процесс (процесс подкачки) является единственным процессом, заг- ружающим другие процессы в память с устройств выгрузки. Процесс подкачки на- чинает работу по выполнению этой своей единственной функции по окончании инициализации системы (как уже говорилось в разделе 7.9). Он загружает про- цессы в память и, если ему не хватает места в памяти, выгружает оттуда неко- торые из процессов, находящихся там. Если у процесса подкачки нет работы (например, отсутствуют процессы, ожидающие загрузки в память) или же он не в состоянии выполнить свою работу (ни один из процессов не может быть выгру- жен), процесс подкачки приостанавливается; ядро периодически возобновляет 260 его выполнение. Ядро планирует запуск процесса подкачки точно так же, как делает это в отношении других процессов, ориентируясь на более высокий прио- ритет, при этом процесс подкачки выполняется только в режиме ядра. Процесс подкачки не обращается к функциям операционной системы, а использует в своей работе только внутренние функции ядра; он является архетипом всех процессов ядра. Как уже вкратце говорилось в главе 8, программа обработки прерываний по таймеру измеряет время нахождения каждого процесса в памяти или в состоянии выгрузки. Когда процесс подкачки возобновляет свою работу по загрузке про- цессов в память, он просматривает все процессы, находящиеся в состоянии "го- товности к выполнению, будучи выгруженными", и выбирает из них один, который находится в этом состоянии дольше остальных (см. Рисунок 9.9). Если имеется достаточно свободной памяти, процесс подкачки загружает выбранный процесс, выполняя операции в последовательности, обратной выгрузке процесса. Сначала выделяется физическая память, затем с устройства выгрузки считывается нужный процесс и освобождается место на устройстве. Если процесс подкачки выполнил процедуру загрузки успешно, он вновь просматривает совокупность выгруженных, но готовых к выполнению процессов в поисках следующего процесса, который предполагается загрузить в память, и повторяет указанную последовательность действий. В конечном итоге возникает одна из следующих ситуаций: * На устройстве выгрузки больше нет ни одного процесса, готового к выпол- нению. Процесс подкачки приостанавливает свою работу до тех пор, пока не возобновится процесс на устройстве выгрузки или пока ядро не выгрузит процесс, готовый к выполнению. (Вспомним диаграмму состояний на Рисунке 6.1). * Процесс подкачки обнаружил процесс, готовый к загрузке, но в системе не- достаточно памяти для его размещения. Процесс подкачки пытается загру- зить другой процесс и в случае успеха перезапускает алгоритм подкачки, продолжая поиск загружаемых процессов. Если процессу подкачки нужно выгрузить процесс, он просматривает все процессы в памяти. Прекратившие свое существование процессы не подходят для выгрузки, поскольку они не занимают физическую память; также не могут быть выгружены процессы, заблокированные в памяти, например, выполняющие операции над областями. Ядро предпочитает выгружать приостановленные процессы, пос- кольку процессы, готовые к выполнению, имеют больше шансов быть вскоре выб- ранными на выполнение. Решение о выгрузке процесса принимается ядром на ос- новании его приоритета и продолжительности его пребывания в памяти. Если в памяти нет ни одного приостановленного процесса, решение о том, какой из процессов, готовых к выполнению, следует выгрузить, зависит от значения, присвоенного процессу функцией nice, а также от продолжительности пребывания процесса в памяти. Процесс, готовый к выполнению, должен быть резидентным в памяти в тече- ние по меньшей мере 2 секунд до того, как уйти из нее, а процесс, загружае- мый в память, должен по меньшей мере 2 секунды пробыть на устройстве выгруз- ки. Если процесс подкачки не может найти ни одного процесса, подходящего для выгрузки, или ни одного процесса, подходящего для загрузки, или ни одного процесса, перед выгрузкой не менее 2 секунд (**) находившегося в памяти, он приостанавливает свою работу по причине того, что ему нужно загрузить про- цесс в память, а в памяти нет места для его размещения. В этой ситуации тай- мер возобновляет выполнение процесса подкачки через каждую секунду. Ядро --------------------------------------- (**) В версии 6 системы UNIX процесс не может быть выгружен из памяти с целью расчистки места для загружаемого процесса до тех пор, пока загру- жаемый процесс не проведет на диске 3 секунды. Уходящий из памяти про- цесс должен провести в памяти не менее 2 секунд. Временной интервал та- ким образом делится на части, в результате чего повышается производи- тельность системы. 261 +------------------------------------------------------------+ | алгоритм swapper /* загрузка выгруженных процессов, | | * выгрузка других процессов с целью | | * расчистки места в памяти */ | | входная информация: отсутствует | | выходная информация: отсутствует | | { | | loop: | | для (всех выгруженных процессов, готовых к выполнению)| | выбрать процесс, находящийся в состоянии выгружен-| | ности дольше остальных; | | если (таких процессов нет) | | { | | приостановиться (до момента, когда возникнет необ-| | ходимость в загрузке процессов); | | перейти на loop; | | } | | если (в основной памяти достаточно места для размеще- | | ния процесса) | | { | | загрузить процесс; | | перейти на loop; | | } | | /* loop2: сюда вставляются исправления, внесенные в алго- | | * ритм */ | | для (всех процессов, загруженных в основную память, | | кроме прекративших существование и заблокированных в | | памяти) | | { | | если (есть хотя бы один приостановленный процесс) | | выбрать процесс, у которого сумма приоритета и| | продолжительности нахождения в памяти наи- | | большая; | | в противном случае /* нет ни одного приостанов- | | * ленного процесса */ | | выбрать процесс, у которого сумма продолжи- | | тельности нахождения в памяти и значения nice| | наибольшая; | | } | | если (выбранный процесс не является приостановленным | | или не соблюдены условия резидентности) | | приостановиться (до момента, когда появится воз- | | можность загрузить процесс); | | в противном случае | | выгрузить процесс; | | перейти на loop; /* на loop2 в исправленном алгорит-| | * ме */ | | } | +------------------------------------------------------------+ Рисунок 9.9. Алгоритм подкачки также возобновляет работу процесса подкачки в том случае, когда один из про- цессов переходит в состояние приостанова, так как последний может оказаться более подходящим для выгрузки процессом по сравнению с ранее рассмотренными. Если процесс подкачки расчистил место в памяти или если он был приостановлен по причине невозможности сделать это, он возобновляет свою работу с переза- пуска алгоритма подкачки (с самого его начала), вновь предпринимая попытку 262 загрузить ожидающие выполнения процессы. На Рисунке 9.10 показана динамика выполнения пяти процессов с указанием моментов их участия в реализации алгоритма подкачки. Положим для простоты, что все процессы интенсивно используют ресурсы центрального процессора и что они не производят обращений к системным функциям; следовательно, переключе- ние контекста происходит только в результате возникновения прерываний по таймеру с интервалом в 1 секунду. Процесс подкачки исполняется с наивысшим приоритетом планирования, поэтому он всегда укладывается в секундный интер- вал, когда ему есть что делать. Предположим далее, что процессы имеют одина- ковый размер и что в основной памяти могут одновременно поместиться только два процесса. Сначала в памяти находятся процессы A и B, остальные процессы выгружены. Процесс подкачки не может стронуть с места ни один процесс в те- чение первых двух секунд, поскольку этого требует условие нахождения переме- щаемого процесса в течение этого интервала на одном месте (в памяти или на устройстве выгрузки), однако по истечении 2 секунд процесс подкачки выгружа- ет процессы A и B и загружает на их место процессы C и D. Он пытается также загрузить и процесс E, но терпит неудачу, поскольку в основной памяти недос- таточно места для этого. На 3-секундной отметке процесс E все еще годен для загрузки, поскольку он находился все 3 секунды на устройстве выгрузки, но процесс подкачки не может выгрузить из памяти ни один из процессов, ибо они находятся в памяти менее 2 секунд. На 4-секундной отметке процесс подкачки выгружает процессы C и D и загружает вместо них процессы E и A. Процесс подкачки выбирает процессы для загрузки, основываясь на продол- жительности их пребывания на устройстве выгрузки. В качестве другого крите- рия может применяться более высокий приоритет загружаемого процесса по срав- нению с остальными, готовыми к выполнению процессами, поскольку такой про- цесс более предпочтителен для запуска. Практика показала, что такой подход "несколько" повышает пропускную способность системы в условиях сильной заг- руженности (см. [Peachey 84]). Алгоритм выбора процесса для выгрузки из памяти с целью освобождения места требуемого объема имеет, однако, более серьезные изъяны. Во-первых, процесс подкачки производит выгрузку на основании приоритета, продолжитель- ности нахождения в памяти и значения nice. Несмотря на то, что он производит выгрузку процесса с единственной целью - освободить в памяти место для заг- ружаемого процесса, он может выгрузить и процесс, который не освобождает место требуемого размера. Например, если процесс подкачки пытается загрузить в память процесс размером 1 Мбайт, а в системе отсутствует свободная память, будет далеко не достаточно выгрузить процесс, занимающий только 2 Кбайта па- мяти. В качестве альтернативы может быть предложена стратегия выгрузки групп процессов при условии, что они освобождают место, достаточное для размещения загружаемых процессов.Эксперименты с использованием машины PDP 11/23 показа- ли,что в условиях сильной загруженности такая стратегия может увеличить про- изводительность системы почти на 10 процентов (см. [Peachey 84]). Во-вторых, если процесс подкачки приостановил свою работу изза того, что в памяти не хватило места для загрузки процесса, после возобновления он вновь выбирает процесс для загрузки в память, несмотря на то, что ранее им уже был сделан выбор. Причина такого поведения заключается в том, что за прошедшее время в состояние готовности к выполнению могли перейти другие выгруженные процессы, более подходящие для загрузки в память по сравнению с ранее выбранным процессом. Однако от этого мало утешения для ранее выбранно- го процесса, все еще пытающегося загрузиться в память. В некоторых реализа- циях процесс подкачки стремится к тому, чтобы перед загрузкой в память одно- го крупного процесса выгрузить большое количество процессов маленького раз- мера, это изменение в базовом алгоритме подкачки отражено в комментариях к алгоритму (Рисунок 9.9). В-третьих, если процесс подкачки выбирает для выгрузки процесс, находя- щийся в состоянии "готовности к выполнению", не исключена возможность того, что этот процесс после загрузки в память ни разу не был запущен на исполне- ние. Этот случай показан на Рисунке 9.11, из которого видно, что ядро загру- 263 жает процесс D на 2- секундной отметке, запускает процесс C, а затем на 3-секундной отметке процесс D выгружается в пользу процесса E (уступая пос- леднему в значении nice), несмотря на то, что процессу D так и не был пре- доставлен ЦП. Понятно, что такая ситуация является нежелательной. Следует упомянуть еще об одной опасности. Если при попытке выгрузить процесс на устройстве выгрузки не будет найдено свободное место, в системе может возникнуть тупиковая ситуация, при которой: все процессы в основной Время Процесс A B C D E --+--------------+-----------+-----------+-----------+----------- 0| 0 | 0 | выгружен | выгружен | выгружен | запущен | | 0 | 0 | 0 | | | | | | | | | | | | | | | | | | | | --+- 1 | 1 | 1 | 1 | 1 1| | запущен | | | | | | | | | | | | | | | | | | | | | | | --+- 2 |