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