2.6.7.Стратегии управления виртуальной памятью

Механизм управления виртуальной памятью должен обеспечить, по крайней мере, следующие операции: перенесение блоков из файлов подкачки в реальную память компьютера (вталкивание), размещение блоков на свободных участках (кадрах) памяти и решение задачи перераспределения памяти между участвующими в работе процессами (выталкивание). Таким образом, стратегии управления виртуальной памятью делятся на три категории:

СТРАТЕГИИ ВТАЛКИВАНИЯ реализуют перенесение страницы из виртуального в реальное адресное пространство. Их цель - определить, в какой момент следует переписать страницу или сегмент из внешней памяти в основную. Применяются следующие подходы:

а) вталкивание по запросу, т.е. при появлении явной ссылки (при обращении по некоторому адресу и отсутствии страницы с этим адресом в основной памяти происходит перемещение страницы из виртуального адресного пространства в реальное). Эта стратегия имеет свои проблемы. Процесс должен накапливать в памяти требуемые страницы по одной. При появлении ссылки на каждую новую страницу процессу приходится ждать, когда эта страница будет загружена в память. В зависимости от того, сколько страниц данного процесса уже находятся в основной памяти, эти периоды ожидания будут обходиться все более дорого, поскольку ожидающие процессы будут занимать все больший объем памяти. Для оценки использования памяти процессом используется произведение "пространство*время". Уменьшение этого произведения за счет периодов ожидания процессом нужных ему страниц является важнейшей целью всех стратегий управления памятью;

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

СТРАТЕГИИ РАЗМЕЩЕНИЯ должны определить место в реальной памяти для размещения очередного поступающего сегмента или страницы из виртуальной памяти. В системах со страничной памятью решение о размещении принимается достаточно тривиально, поскольку поступающая страница может быть помещена в любой свободный страничный кадр. В системах с сегментной организацией виртуальной памяти требуется использование более развитых средств размещения. Это обусловлено необходимостью борьбы с фрагментацией реальной памяти компьютера. Чаще всего применяются:

а) стратегия наиболее подходящего участка реальной памяти. Поступающий сегмент помещается в тот участок памяти, в котором ему наиболее "тесно", так что остается минимально возможное неиспользуемое пространство;

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

в) стратегия наименее подходящего участка. При размещении сегмента выбирается максимально свободный участок. Предполагается, что после размещения останется достаточно места для помещения еще одного (или более) сегмента.

СТРАТЕГИИ ВЫТАЛКИВАНИЯ. Целью этих стратегий является обеспечение процедуры смены блоков (страниц или сегментов), принадлежащих различным процессам, в реальной памяти. Необходимость выталкивания из основной памяти в виртуальное пространство обусловлена различной протяженностью реального адресного пространства компьютера и суммы виртуальных адресных пространств действующих процессов. Выталкивание позволяет разместить поступающие блоки, даже если реальная память полностью занята.

Рассмотрим следующие подходы:

а) принцип оптимальности - следует заменять ту страницу, к которой не будет обращений. Реализовать эту стратегию невозможно, так как методов, позволяющих совершенно гарантированно предсказать будущее, не существует;

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

в) FIFO (First In - First Out). Выталкивается та страница, которая дольше остальных находится в памяти. Аргумент для приме- нения такой стратегии весьма существенен: у выталкиваемой страницы уже был высокий шанс использования, и пора дать подобные возможности другой странице. К сожалению, стратегия FIFO с большой вероятностью будет приводить к замещению активно используемых страниц, поскольку тот факт, что страница находится в основной памяти в течении длительного времени, может означать, что она постоянно в работе. Если ее вытолкнуть из основной памяти по принципу FIFO, ее почти немедленно придется вталкивать обратно. Исследователями была обнаружена аномалия, присущая стратегии FIFO: при увеличении количества страничных кадров, выделенных процессу, возможно увеличение числа прерываний по отсутствию страницы в реальной памяти. Рассмотрим пример. Процесс в течении некоторого времени работает со страницами A, B, C, D и E. Последовательность работы со страницами определена левым столбцом на рисунке. В первом случае процессу выделено 3 страничных кадра, во втором - 4. При отсутствии страницы в памяти возникает прерывание. Подсчитаем количество прерываний:

г) LRU (Least Recently Used). Выталкивается та страница, которая дольше не использовалась; Эта стратегия требует, чтобы при каждом обращении к странице обновлялась связанная с ней временная метка. Процедура выталкивания может найти страницу с максимальным значением временной метки;

д) LFU (Least Frecuently Used). Эта стратегия нацелена на выталкивание той страницы, которая реже использовалась. Здесь контролируется интенсивность использования страницы. Однако, велика вероятность, что наименее интенсивно используемой окажется страница, которая только что была загружена в основную память и к которой было только одно обращение; е) NUR (Not Used Recently). Стратегия обеспечивает выталкивание страницы, которая не использовалась в последнее время. Эта стратегия близка к LRU и характеризуется малыми издержками. Основанием для применения стратегии считается следующее утверждение: к страницам, которые в последнее время не использовались, вряд ли будут обращения в ближайшем будущем, так что их можно заменять на вновь поступающие страницы. Поскольку желательно заменять ту страницу, которая в период нахождения в основной памяти не изменялась (чтобы не переписывать ее в файл подкачки), стратегия предусматривает введение двух битов-признаков в дескрипторе страницы:

A - доступ (обращение): устанавливается в 1 перед записью или чтением;

D - модификация: устанавливается в 1 если была выполнена запись в таблицу.

Первоначально биты-признаки для всех страниц устанавливаются в 0. При обращении к какой-либо странице бит A устанавливается в 1, а в случае изменения содержимого страницы устанавливается D=1. Когда нужно выбрать страницу для выталкивания, находят страницу, к которой не было обращений (A=0). Если таких страниц нет, ищем страницу, у которой D=0.

В системах с разделением времени основная память работает активно, так что очень скоро у всех страниц бит обращения будет установлен в 1. Один из широко используемых методов решения этой проблемы заключается в том, что все биты обращений немодифицированных страниц периодически сбрасываются в 0.

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