Курынин Р.В., Машечкин И.В., Терехин А.Н. - Конспект лекций по ОС (1114685), страница 54
Текст из файла (страница 54)
Изначально для всех страницпроцесса признаки R и M обнуляются. По таймеру или по возникновению некоторых событий всистеме происходит программное обнуление всех R-признаков. Когда системе требуется выбратькакую-то страницу для откачки из оперативной памяти, она поступает следующим образом.
Всестраницы, принадлежащие данному процессу, делятся на 4 категории в зависимости от значенияпризнаков R и M.− Класс 0: R = 0, M = 0. Это те страницы, в которых не происходило обращение в последнеевремя и в которых не сделано ни одно изменение.− Класс 1: R = 0, M = 1. Это те страницы, к которым в последний период не было обращений(поскольку программно обнулен R-признак), но в этой странице в свое время произошлоизменение.− Класс 2: R = 1, M = 0. Это те страницы, из которых за последний таймаут читаласьинформация.− Класс 3: R = 1, M = 1. Это те страницы, к которым за последнее время были обращения, в т.ч.обращения на запись, т.е. это активно используемые страницы.Соответственно, алгоритм предлагает выбирать страницу для откачивания случайнымспособом из непустого класса с минимальным номером.Следующий алгоритм, который мы рассмотрим, — это алгоритм FIFO.
Если в системереализован этот алгоритм, то тогда при загрузке очередной страницы в память операционнаясистема фиксирует время этой загрузки. Соответственно, данный алгоритм предполагает откачкутой страницы, которая наиболее долго располагается в ОЗУ.Очевидно, что данная стратегия зачастую оказывается неэффективной, посколькувозможна откачка интенсивно используемой страницы. Поэтому существует целый рядмодификаций алгоритма FIFO, нацеленных на сглаживание обозначенной проблемы.Модифицированный алгоритм может иметь следующий вид.
Выбирается самая «старая»страница, затем система проверяет значение признака доступа к этой странице (R-признак). ЕслиR = 0, то эта страница откачивается. Если же R = 1, то этот признак обнуляется, а такжепереопределяется время загрузки данной страницы текущим временем (иными словами, даннаястраница перемещается в конец очереди), после чего алгоритм начинает свою работу с начала.Данный алгоритм имеет недостатки, связанные с ростом накладных расходов приперемещении страниц по очереди.
Поэтому этот алгоритм получил свое развитие, в частности, ввиде алгоритма «Часы».Алгоритм «Часы» подразумевает, что все страницы образуют циклический список (5.4).Имеется некоторый маркер, ссылающийся на некоторую страницу в списке, и этот маркер можетперемещаться, например, только по часовой стрелке.Функционирование алгоритма достаточно просто: если значение R-признака вобозреваемой маркером странице равно нулю, то эта страница выгружается, а на ее местопомещается новая страница, после чего маркер сдвигается.
Если же R = 1, то этот признакобнуляется, а маркер сдвигается на следующую позицию.208маркер наобозреваемуюстраницу....Рис. 130..Замещение страниц. Алгоритм «Часы».Следующая группа алгоритмов позволяют учитывать более адекватно старение ииспользование страниц и, соответственно, осуществлять выбор страницы для откачки.Алгоритм LRU (Least Recently Used — «наименее недавно» – наиболее давно используемаястраница) основан на достаточно сложной аппаратной схеме и действует по следующей схеме.Пускай имеется N страниц. Для решения задачи в компьютере имеется битовая матрица,размером N × N, которая изначально обнуляется. Когда происходит обращение к i-ой странице, товсе биты i-ой строки устанавливаются в 1, а весь i-ый столбец обнуляется.
Соответственно, когдапонадобится выбрать страницу для откачки, то выбирается та страница, для которойсоответствующая строка хранит наименьшее двоичное число.Рассмотренный алгоритм хорош тем, что достаточно адекватно учитывает интенсивностьиспользования страниц, но этот алгоритм требует сложной аппаратной реализации.Альтернативой указанному алгоритму может служить алгоритм NFU (Not FrequentlyUsed — редко использовавшаяся страница), основанный на использовании программныхсчетчиков страниц.Данный алгоритм подразумевает, что с каждой физической страницей с номером iассоциирован программный счетчик Counti.
Изначально для всех i происходит обнулениесчетчиков. А затем, по таймеру происходит увеличение значений всех счетчиков на величинуинтенсивности использования, т.е. на величину R-признака: Counti = Counti + Ri. Иными словами,если за последний таймаут было обращение к странице, что значение счетчика возрастает,иначе — не изменяется. Соответственно, для откачки выбирается страница с минимальнымзначением счетчика Counti.Данная модель также является достаточно адекватной, но она имеет ряд важныхнедостатков.
Первый связан с тем, что счетчик хранит историю: например, какая-то страница внекоторый период времени интенсивно использовалась, и значение счетчика стало настолькобольшим, что при прекращении работы с данной страницей значение счетчика достаточно долгоне даст откачать эту страницу. А второй недостаток связан с тем, что при очень интенсивномобращении к странице возможно переполнение счетчика.Чтобы сгладить указанные недостатки, существует модификация данного алгоритма,основанного на том, что каждый раз по таймеру значение счетчика сдвигается на 1 разряд влево,после чего последний (правый) разряд устанавливается в значение R-признака.5.5Сегментное распределениеНедостатком страничного распределения памяти является то, что при реализации этоймодели процессу выделяется единый диапазон виртуальных адресов: от нуля до некоторогопредельного значения.
С одной стороны, ничего плохо в этом нет, но это свойство оказываетсянеудобным по следующей причине. В процессе есть команды, есть статические переменные,которые, по сути, являются разными объединениями данных с различными характеристикамииспользования. Еще большие отличия в использовании иллюстрируют существующие в процессе209стек и область динамической памяти, называемой также кучей. И модель страничной организациипамяти подразумевает статическое разделение единого адресного пространства: выделяютсяобласть для команд, область для размещения данных, а также область для стека и кучи. При этомзачастую стек и куча размещаются в единой области, причем стек прижат к одной границеобласти, куча — к другой, и растут они навстречу друг другу.
Соответственно, возможныситуации, когда они начинают пересекаться (ситуация переполнения стека). Или даже если стекбудет располагаться в отдельной области памяти, он может переполнить выделенное емупространство. Итак, вот основные недостатки страничного распределения памяти.Избавиться от указанных недостатков на концептуальном уровне призвана модельсегментного распределения памяти (5.5). Данная модель представляет каждый процесс в видесовокупности сегментов, каждый из которых может иметь свой размер. Каждый из сегментовможет иметь собственную функциональность: существуют сегменты кода, сегменты статическихданных, сегмент стека и т.д. Для организации работы с сегментами может использоватьсянекоторая таблица, в которой хранится информация о каждом сегменте (его номер, размер и пр.).Тогда виртуальный адрес может быть проинтерпретирован, как номер сегмента и величинасмещения в нем.NsegoffsetNsegsizebaseoffset>sizeдаПрерываниенетbase + offsetТаблица сегментовфизический адресРис.
131.Сегментное распределение.Модель сегментного распределения может иметь достаточно эффективно работающуюаппаратную реализацию. Существует аппаратная таблица сегментов с фиксированным числомзаписей. Каждая запись этой таблицы соответствует своему сегменту и хранит информацию оразмере сегмента и адрес начала сегмента (т.е. адрес базы), а также тут могут присутствоватьразличные атрибуты, которые будут оговаривать права и режимы доступа к содержимомусегмента.Итак, имея виртуальный адрес, система аппаратным способом извлекает из него номерсегмента i, обращается к i-ой строке таблицы, из которой извлекается информация о сегменте.После чего происходит проверка, не превосходит ли величина сегмента размера самого сегмента.Если превосходит, то происходит прерывание, иначе, складывая базу со смещением, вычисляетсяфизический адрес.К достоинствам данной модели можно отнести простоту организации, которая, по сути,явилась развитием модели распределения разделов.
Если в той модели каждому процессувыделяется только один сегмент (раздел), то при сегментной модели распределения процессувыделяется совокупность сегментов, каждый из которых будет иметь свои функциональныеобязанности.К недостаткам данной модели необходимо отнести то, что каждый сегмент долженцеликом размещаться в памяти (возникает упоминавшаяся выше проблема неявнойнеэффективности, связанная с принципом локальности). Также возникают проблемы с210откачкой/подкачкой: подкачка осуществляется всем процессом или, по крайней мере, целымсегментом, что зачастую оказывается неэффективно. И поскольку каждый сегмент так или иначедолжен быть размещен в памяти, то возникает ограничение на предельный размер сегмента.5.6Сегментно-страничное распределениеЕстественным развитием рассмотренной модели сегментного распределения памяти сталамодель сегментно-страничного распределения.
Эта модель рассматривает виртуальный адрес, какномер сегмента и смещение в нем. Имеется также аппаратная таблица сегментов, посредствомкоторой из виртуального адреса получается т.н. линейный адрес, который, в свою очередь,представляется в виде номера страницы и величины смещения в ней. А затем, используя таблицустраниц, получается непосредственно физический адрес.Итак, данный механизм подразумевает, что в процессе имеется ряд виртуальных сегментов,которые дробятся на страницы.
Поэтому данная модель сочетает в себе, с одной стороны,логическое сегментирование, а с другой стороны, преимущества страничной организации (когдаможно работать с отдельными страницами памяти, не требуя при этом полного размещениясегмента в ОЗУ).Примером реализации может служить реализация, предложенная компанией Intel.Рассмотрим упрощенную модель этой реализации (5.6). Виртуальный адрес в этой моделипредставляется в виде селектора (информации о сегменте) и смещения в сегменте.Виртуальный адресселекторNsegРис. 132.локализацияoffsetзащитаСегментно-страничное распределение. Упрощенная модель Intel.Селектор содержит информацию о локализации сегмента. В модели Intel сегмент можетбыть одного из двух типов: локальный сегмент, который описывается в таблице локальныхдескрипторов LDT (Local Descriptor Table) и который может быть доступен лишь данномупроцессу, или глобальный сегмент, который описывается в таблице глобальных дескрипторовGDT (Global Descriptor Table) и который может разделяться между процессами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
