Зависимость частоты отказов от объема реальной памяти
Рисунок 3.7. Зависимость частоты отказов от объема реальной памяти
С точки зрения стратегии размещения не имеет значения, какой страничный кадр занимать при подкачке. Но как выбрать один кадр из всего пула кадров? Конечно, наилучшим кандидатом является полностью свободный кадр - такой, который еще не занимался или был когда-то распределен процессу, ныне уже закончившемуся. Но если суммарный объем виртуальных адресных пространств всех процессов существенно превышает объем реальной памяти, то такие страницы являются более чем дефицитным ресурсом. Выход состоит в том, что для каждого распределенного кадра в таблице страничных кадров (и/или в таблице дескрипторов) ведется учет факторов, определяющих выбор его в качестве жертвы для вытеснения, и из всех кадров выбирается тот, который является лучшим (с точки зрения принятой стратегии) кандидатом в жертвы (OS/2, Windows 95). Несколько более сложное решение - ОС ведет список свободных (условно свободных) кадров и очередная жертва выбирается из этого списка. Страничный кадр попадает в список жертв, если его "показатель жертвенности" превышает некоторое граничное значение, но может быть еще "спасен" из списка жертв, если во время пребывания в этом списке он будет востребован. Помещение кадра в список жертв может выполняться либо сразу по достижении "показателя жертвенности" граничного значения (VM), либо (ленивая политика - Unix) размер списка поддерживается в определенных границах за счет периодического его пополнения путем просмотра всей таблицы страничных кадров.
В качестве образцов для сравнения в литературе рассматриваются стратегии вытеснения RANDOM и OPT. Стратегия RANDOM заключается в том, что страница для вытеснения выбирается случайным образом. Понятно, что достичь высокой эффективности при такой стратегии невозможно, и любая другая введенная нами стратегия может считаться сколько-нибудь разумной только в том случае, если она, по крайней мере, не хуже стратегии RANDOM. Стратегия OPT требует, чтобы в первую очередь вытеснялась страница, к которой дольше всего не будет обращений в будущем. Интуитивно понятно и строго доказано, что эта стратегия является наилучшей из всех возможных. Но, к сожалению, эта стратегия в идеальном варианте нереализуема из-за невозможности точно прогнозировать требования. Реально применяемые стратегии могут оцениваться по степени приближения их результатов к результатам OPT.
Стратегия FIFO - первый на входе - первый на выходе - является простейшей. Согласно этой стратегии из реальной памяти вытесняется та страница, которая была раньше других в нее подкачана. Для реализации этой стратегии ОС достаточно организовать список-очередь страниц в реальной памяти с занесением подкачиваемой страницы в "голову" списка и выборкой страницы для вытеснения из "хвоста" списка. Хотя стратегия FIFO и лучше, чем RANDOM, она не учитывает частоты обращений: может быть вытеснена страница, к которой происходят постоянные обращения. Более того, при некоторых комбинациях страничных требований FIFO может давать аномальные результаты: увеличение числа страничных отказов при увеличении числа доступных страничных кадров (см. задания в конце главы).
Многие используемые в современных ОС стратегии вытеснения могут рассматриваться как разновидности стратегии LRU (least recently used) - наименее используемая в настоящее время: вытесняется та страница, к которой дольше всего не было обращений. Это можно рассматривать как попытку приближения к стратегии OPT путем экстраполяции потока страничных требований из прошлого на будущее. Разновидности LRU различаются тем, как они учитывают время использования страницы. Очевидно, что запоминание точного времени обращения к каждой странице обошлось бы слишком дорого. Стратегии LRU используют биты used и dirty дескриптора страницы для оценки этого времени. Бит used устанавливается в 1 аппаратно при любом обращении к странице, бит dirty устанавливается аппаратно при обращении к странице для записи; оба бита сбрасывается ОС по своему усмотрению. Все множество присутствующих в реальной памяти страниц разбивается на четыре подмножества, в зависимости от значений этих полей:
- неиспользованные чистые (used=0, dirty=0),
- неиспользованные грязные (used=0, dirty=1),
- использованные чистые (used=1, dirty=0),
- использованные грязные (used=1, dirty=1).
Чем меньше номер подмножества, в которое входит страница, тем желательнее она в роли жертвы. Внутри одного подмножества жертва может выбираться методом циклического поиска или случайным образом. ОС должна выбрать момент, когда она будет сбрасывать биты used в 0. Ленивая политика состоит в том, чтобы делать это только, когда уже не остается неиспользованных страниц. Противоположные вариант - при каждом поиске жертвы сбрасывать биты used для всех страниц или только для проверенных в ходе поиска. Наконец, общий сброс битов used может производиться по таймеру.
Интересным образом используется бит dirty в стратегии SCC (second cycle chance) - цикл второго шанса. Алгоритм этого варианта стратегии LRU осуществляет циклический просмотр таблицы страничных кадров. Разумеется, лучшим кандидатом является неиспользованная страница (подмножества 1 и 2). Но если таковых нет, то выбирается страница с нулевым полем dirty (подмножество 3). Просмотренные страницы, оказавшиеся грязными, ОС не трогает (пока), но сбрасывает в них поле dirty. Таким образом, даже если при полном обороте поиска не будет найдена жертва, она обязательно найдется при втором обороте. "Второй шанс" здесь состоит в том, что страница, принудительно отмеченная как чистая, может еще в промежутке между двумя поисками восстановить поле dirty. При такой стратегии поле dirty уже не отражает истинного состояния страницы, ОС должна сохранять действительное состояние в расширении дескриптора страницы.
Более сложные варианты стратегии LRU предусматривают более, чем одноразрядный, учет времени. Метод временного штампа (timestamp) предусматривает хранение для каждой страницы многоразрядного кода. Периодически этот код сдвигается на разряд влево, а в освободившийся старший разряд заносится текущее значение поля used, после чего поле used сбрасывается в 0. Код временного штампа хранит, таким образом, предысторию использования страниц. Наилучшей жертвой оказывается та страница, у которой значение штампа (если интерпретировать его как целое число без знака) минимальное.
Метод возраста страницы (Unix) подобен предыдущему, но здесь с каждой страницей связывается число - ее "возраст". При периодическом просмотре таблицы страничных кадров для страницы, у которой бит used равен 0, возраст увеличивается на 1, если же бит used установлен в 1, то он сбрасывается в 0, а возраст не меняется. Когда системный процесс "сборщик страниц" пополняет список свободных страниц, он заносит в него те страницы, для которых превышен установленный граничный возраст.
Выше мы использовали биты used и dirty, предполагая, что они поддерживаются аппаратно. Однако, возможна реализация указанных стратегий и при отсутствии такой аппаратной поддержки. В этом случае недостающие поля содержатся в расширении дескриптора страницы, а вместо них ОС сбрасывает в 0 бит present. Бит present в дескрипторе уже не отражает истинного состояния и дублируется в расширении. Обращение к такой странице вызывает ловушку "страничный отказ", однако ОС убеждается по расширению дескриптора, что страница на самом деле уже есть в реальной памяти, и вместо ее подкачки корректирует бит present в основном дескрипторе, одновременно устанавливая used в расширении.
Указанные стратегии применимы как к локальному, так и к глобальному управлению памятью. В первом случае каждому процессу выделяется статический пул страничных кадров и свопинг ведется в пределах этого пула (например, AS/400). Это дает возможность применять для разнотипных процессов разные стратегии, но требует принятия решения о размере каждого пула. В случае же глобального управления выбранная стратегия применяется по всему доступному множеству страничных кадров и производится постоянное перераспределение ресурсов между процессами (например, VM, MVS). Динамическое перераспределение - качество полезное, но, если оно не учитывает уровень мультипрограммирования, то может привести к толкотне.
Ряд глобальных стратегий, управляющих уровнем мультипрограммирования, основывается на идее рабочего набора - WS (working set). Идея эта базируется на явлении локализации обращений к памяти. Любая программа не обращается ко всему своему адресному пространство одновременно. На каждом временном отрезке программа работает только с некоторым подмножеством адресов и, соответственно, с некоторым подмножеством страниц. Временной отрезок, на котором это подмножество квазипостоянно, называется фазой программы. Почти полное обновление этого подмножества называется сменой фазы. Рабочим набором процесса S(w) называется перечень страниц, к которым процесс обращался в течении последнего интервала виртуального времени w. Методы, основанные на идее рабочего набора, стремятся к тому, чтобы выполняющийся процесс постоянно имел свой рабочий набор в реальной памяти и страницы, входящие в рабочие наборы выполняющихся процессов не вытеснялись. Если у ОС нет возможности разместить в реальной памяти весь рабочий набор процесса, она снижает уровень мультипрограммирования, переводя процесс в состояние ожидания. При разблокировании процесса ОС имеет возможность перед его активизацией выполнить упреждающую подкачку (preload) всего его рабочего набора и тем самым значительно снизить частоту страничных отказов.
На практике, однако, идеальная реализация стратегии WS не представляется возможной по тем же соображениям, что и для идеальной LRU: нет возможности запоминать время каждого обращения. Адаптированный метод WS состоит в его определении через фиксированные интервалы времени. В начале каждого интервала все страницы, для которых распределены страничные кадры, считаются входящими в рабочий набор. В течение интервала все запросы процесса на новые страницы удовлетворяются. По окончании интервала те страницы, которые не были использованы (бит used), удаляются из рабочего набора. Зафиксированный в конце интервала рабочий набор служит исходным для следующего интервала.
Некоторые методы стратегии WS не сохраняют полный перечень страниц, входящих в рабочий набор, а только определяют его обобщенные показатели. Алгоритм метода рабочего размера замеряет только размер рабочего набора и выделяет процессу соответствующее число страничных кадров (VM). Метод частоты страничных отказов основан на измерении интервала виртуального времени между двумя страничными отказами, если этот интервал меньше нижней границы, процессу выделяется дополнительный страничный кадр, если интервал больше верхней границы, у процесса отбирается один страничный кадр. Естественно, что методы, не сохраняющие всего списка рабочего набора, не имеют возможности выполнять упреждающую его подкачку.
При страничном свопинге, как и при сегментном, применяется, как правило, стратегия подкачки по запросу (demand paging), так как реализовать полностью безубыточную стратегию упреждающей подкачки невозможно. Тем не менее, в стратегии WS появляется возможность упреждающей подкачки с минимальными убытками. В системах, имеющих большой объем памяти и не особенно заботящихся о минимизации ее потерь иногда применяется также кластеризация подкачки. Этот метод также базируется на локализации и исходит из того, что если произошло обращение к некоторой странице, то с большой вероятностью можно ожидать в ближайшем будущем обращений к соседним с ней страницам, которые и подкачиваются, не дожидаясь этих обращений.
Системные вызовы страничной модели "не видят" страничной структуры и обращаются к памяти как к линейному пространству виртуальных адресов.
Выделение памяти происходит при помощи системного вызова: vaddr = getMem(size) который возвращает виртуальный адрес выделенной области заданного размера. На самом деле размер выделенной области кратен размеру страницы, а ее адрес выровнен по границе страницы.
Освобождение памяти: freeMem(vaddr)
Поскольку память выделяется страницами, при выделении памяти для маленьких (существенно меньших размера страницы) объектов образуются значительные внутренние дыры. Для того, чтобы избежать этих потерь, некоторые системы обеспечивают работу с кучей (heap) - заранее выделенной областью памяти размером в одну или несколько страниц с последующим выделением памяти для маленьких объектов в куче. Соответствующие системные вызовы: heapId = createHeap(size); vaddr = getHeapMem(heapID,size) freeHeapMem(vaddr)
