Страничный способ организации виртуальной памяти

Как мы уже сказали, при таком способе все фрагменты программы, на которые она разбивается (за исключением последней её части), получаются одинаковыми. Одинаковыми полагаются и единицы памяти, которые мы предоставляем для размещения фрагментов программы. Эти одинаковые части называют страницами и говорят, что память разбивается на физические страницы, а программа – на виртуальные страницы. Часть виртуальных страниц задачи размещается в опе­ративной памяти, а часть – во внешней. Обычно место во внешней памяти, в ка­честве которой в абсолютном большинстве случаев выступают накопители на магнитных дисках (поскольку они относятся к быстродействующим устройствам с прямым доступом), называют файлом подкачки или страничным файлом (paging file). Иногда этот файл называют swap-файлом, тем самым подчеркивая, что записи этого файла – страницы – замещают друг друга в оперативной памя­ти. В некоторых ОС выгруженные страницы располагаются не в файле, а в спе­циальном разделе дискового пространства. В UNIX-системах для этих целей вы­деляется специальный раздел, но кроме него могут быть использованы и файлы, выполняющие те же функции, если объёма раздела недостаточно.

Разбиение всей оперативной памяти на страницы одинаковой величины, причем величина каждой страницы выбирается кратной степени двойки, приводит к тому, что вместо одномерного адресного пространства памяти можно говорить о двумерном. Первая координата адресного пространства – это номер страницы, а вторая координата – номер ячейки внутри выбранной страницы (его называют индексом). Таким образом, физический адрес определяется парой (P_p, i), а вир­туальный адрес – парой (P_v, i), где P_v – это номер виртуальной страницы, P_p – это номер физической страницы и i – это индекс ячейки внутри страницы. Коли­чество битов, отводимое под индекс, определяет размер страницы, а количество битов, отводимое под номер виртуальной страницы, – объём возможной вирту­альной памяти, которой может пользоваться программа. Отображение, осущест­вляемое системой во время исполнения, сводится к отображению P_v в P_p и при­писывании к полученному значению битов адреса, задаваемых величиной i. При этом нет необходимости ограничивать число виртуальных страниц числом фи­зических, то есть не поместившиеся страницы можно размещать во внешней па­мяти, которая в данном случае служит расширением оперативной.

Для отображения виртуального адресного пространства задачи на физическую память, как и в случае с сегментным способом организации, для каждой задачи необходимо иметь таблицу страниц для трансляции адресных пространств. Для описания каждой страницы диспетчер памяти ОС заводит соответствующий де­скриптор, который отличается от дескриптора сегмента прежде всего тем, что в нем нет необходимости иметь поле длины – ведь все страницы имеют одина­ковый размер. По номеру виртуальной страницы в таблице дескрипторов стра­ниц текущей задачи находится соответствующий элемент (дескриптор). Если бит присутствия имеет единичное значение, значит, данная страница сейчас раз­мещена в оперативной, а не во внешней памяти и мы в дескрипторе имеем номер физической страницы, отведенной под данную виртуальную. Если же бит при­сутствия равен нулю, то в дескрипторе мы будем иметь адрес виртуальной стра­ницы, расположенной сейчас во внешней памяти. Таким образом и осуществ­ляется трансляция виртуального адресного пространства на физическую память. Этот механизм трансляции проиллюстрирован на рис. 2.8.

Защита страничной памяти, как и в случае с сегментным механизмом, основана на контроле уровня доступа к каждой странице. Как правило, возможны следующие уровни доступа: только чтение; чтение и запись; только выполнение. В этом случае каждая страница снабжается соответствующим кодом уровня доступа. При трансформации логического адреса в физический сравнивается значение кода разрешенного уровня доступа с фактически требуемым. При их несовпаде­нии работа программы прерывается.

Рис. 2.8. Страничный способ организации виртуальной памяти

При обращении к виртуальной странице, не оказавшейся в данный момент в оперативной памяти, возникает прерывание и управление передаётся диспетче­ру памяти, который должен найти свободное место. Обычно предоставляется первая же свободная страница. Если свободной физической страницы нет, то диспетчер памяти по одной из вышеупомянутых дисциплин замещения (LRU, LFU, FIFO, random) определит страницу, подлежащую расформированию или сохранению во внешней памяти. На её место он разместит ту новую виртуаль­ную страницу, к которой было обращение из задачи, но её не оказалось в опера­тивной памяти.

Напомним, что алгоритм выбирает для замещения ту страницу, на которую не было ссылки на протяжении наиболее длинного периода времени. Дисциплина LRU (least recently used) ассоциирует с каждой страницей время последнего её использования. Для замещения выбирается та страница, которая дольше всех не использовалась.

Для использования дисциплин LRU и LFU в процессоре должны быть соответствующие аппаратные средства. В дескрипторе страницы размещается бит обращения (подразумевается, что на рис. 2.8 этот бит расположен в последнем поле), и этот бит становится единичным при обращении к дескриптору.

Если объём физической памяти небольшой и даже часто требуемые страницы не удается разместить в оперативной памяти, то возникает так называемая «про­буксовка». Другими словами, пробуксовка – это ситуация, при которой загрузка нужной нам страницы вызывает перемещение во внешнюю память той страни­цы, с которой мы тоже активно работаем. Очевидно, что это очень плохое явле­ние. Чтобы его не допускать, желательно увеличить объём оперативной памяти (сейчас это стало самым простым решением), уменьшить количество параллель­но выполняемых задач либо попробовать использовать более эффективные дис­циплины замещения. В абсолютном большинстве современных ОС используется дисциплина замеще­ния страниц LRU как самая эффективная. Так, именно эта дисциплина исполь­зуется в OS/2 и Linux. Однако в такой ОС, как Windows NT, разработчики, желая сделать систему максимально независимой от аппаратных возможностей процессора, пошли на отказ от этой дисциплины и применили правило FIFO. А для того, чтобы хоть как-нибудь сгладить её неэффективность, была введена «буферизация» тех страниц, которые должны быть записаны в файл подкачки на диск1 или просто расформированы. Принцип буферирования прост. Прежде чем замещаемая страница действительно будет перемещена во внешнюю память или просто расформирована, она помечается как кандидат на выгрузку. Если в сле­дующий раз произойдет обращение к странице, находящейся в таком «буфере», то страница никуда не выгружается и уходит в конец списка FIFO. В противном случае страница действительно выгружается, а на её место в «буфере» попадает следующий «кандидат». Величина такого «буфера» не может быть большой, по­этому эффективность страничной реализации памяти в Windows NT намного ниже, чем у вышеназванных ОС, и явление пробуксовки начинается даже при сущест­венно большем объёме оперативной памяти.

В ряде ОС с пакетным режимом работы для борьбы с пробуксовкой использует­ся метод «рабочего множества». Рабочее множество – это множество «активных» страниц задачи за некоторой интервал То есть тех страниц, к которым было об­ращение за этот интервал времени. Реально количество активных страниц зада­чи (за интервал Т) все время изменяется, и это естественно, но, тем не менее, для каждой задачи можно определить среднее количество её активных страниц. Это среднее число активных страниц и есть рабочее множество задачи. Наблюдения за исполнением множества различных программ показали [28, 37, 49], что даже если Т равно времени выполнения всей работы, то размер рабочего множества часто существенно меньше, чем общее число страниц программы. Таким обра­зом, если ОС может определить рабочие множества исполняющихся задач, то для предотвращения пробуксовки достаточно планировать на выполнение толь­ко такое количество задач, чтобы сумма их рабочих множеств не превышала воз­можности системы.

Как и в случае с сегментным способом организации виртуальной памяти, стра­ничный механизм приводит к тому, что без специальных аппаратных средств он будет существенно замедлять работу вычислительной системы. Поэтому обычно используется кэширование страничных дескрипторов. Наиболее эффективным способом кэширования является использование ассоциативного кэша. Именно такой ассоциативный кэш и создан в 32-разрядных микропроцессорах i80x86. Начиная с i80386, который поддерживает страничный способ распределения па­мяти, в этих микропроцессорах имеется кэш на 32 страничных дескриптора. Поскольку размер страницы в этих микропроцессорах равен 4 Кбайт, возможно бы­строе обращение к 128 Кбайт памяти.

Итак, основным достоинством страничного способа распределения памяти явля­ется минимально возможная фрагментация. Поскольку на каждую задачу может приходиться по одной незаполненной странице, то становится очевидно, что па­мять можно использовать достаточно эффективно; этот метод организации вир­туальной памяти был бы одним из самых лучших, если бы не два следующих об­стоятельства.

Первое – эта то, что страничная трансляция виртуальной памяти требует суще­ственных накладных расходов. В самом деле, таблицы страниц нужно тоже раз­мещать в памяти. Кроме этого, эти таблицы нужно обрабатывать; именно с ними работает диспетчер памяти.

Второй существенный недостаток страничной адресации заключается в том, что программы разбиваются на страницы случайно, без учета логических взаимосвя­зей, имеющихся в коде. Это приводит к тому, что межстраничные переходы, как правило, осуществляются чаще, нежели межсегментные, и к тому, что становит­ся трудно организовать разделение программных модулей между выполняющи­мися процессами.

Для того чтобы избежать второго недостатка, постаравшись сохранить достоин­ства страничного способа распределения памяти, был предложен ещё один спо­соб – сегментно-страничный. Правда, за счёт дальнейшего увеличения наклад­ных расходов на его реализацию.