2011. Машбук (1114722), страница 64
Текст из файла (страница 64)
Если всистеме реализован этот алгоритм, то при загрузке очередной страницы в памятьоперационная система фиксирует время этой загрузки. Соответственно, данный алгоритмпредполагает откачку той страницы, которая наиболее долго располагается в ОЗУ.Очевидно, что данная стратегия зачастую оказывается неэффективной, посколькувозможна откачка интенсивно используемой страницы. Поэтому существует целый рядмодификаций алгоритма FIFO, нацеленных на сглаживание обозначенной проблемы.Модифицированный алгоритм может иметь следующий вид.
Выбирается самая«старая» страница, затем система проверяет значение признака доступа к этой странице(R-признак). Если R = 0, то эта страница откачивается. Если же R = 1, то этот признакобнуляется, а также время загрузки данной страницы переопределяется текущимвременем (иными словами, данная страница перемещается в конец очереди), после чегоалгоритм начинает свою работу с начала.Данный алгоритм имеет недостатки, связанные с ростом накладных расходов приперемещении страниц по очереди. Поэтому этот алгоритм получил свое развитие, вчастности, в виде алгоритма «Часы».Алгоритм «Часы» подразумевает, что все страницы образуют циклический список(Рис.
140). Имеется некоторый маркер, ссылающийся на некоторую страницу в списке, иэтот маркер может перемещаться, например, только по часовой стрелке.Функционирование алгоритма достаточно просто: если значение R-признака вобозреваемой маркером странице равно нулю, то эта страница выгружается, а на ее местопомещается новая страница, после чего маркер сдвигается. Если же R = 1, то этот признакобнуляется, а маркер сдвигается на следующую позицию.239маркер наобозреваемуюстраницу.....Рис. 140.
Замещение страниц. Алгоритм «Часы».Следующая группа алгоритмов позволяют более адекватно учитывать старение ииспользование страниц и, соответственно, более адекватно осуществлять выбор страницыдля откачки.Алгоритм LRU (Least Recently Used — «наименее недавно» – наиболее давноиспользуемая страница) основан на достаточно сложной аппаратной схеме и действует последующей схеме.Пусть имеется N страниц. Для решения задачи в компьютере имеется битоваяматрица, размером N × N, которая изначально обнуляется. Когда происходит обращение кi-ой странице, то все биты i-ой строки устанавливаются в 1, а весь i-ый столбецобнуляется. Соответственно, когда понадобится выбрать страницу для откачки, товыбирается та страница, для которой соответствующая строка хранит наименьшеедвоичное число.Рассмотренный алгоритм хорош тем, что достаточно адекватно учитываетинтенсивность использования страниц, но этот алгоритм требует сложной аппаратнойреализации.Альтернативой указанному алгоритму может служить алгоритм NFU (NotFrequently Used — редко использовавшаяся страница), основанный на использованиипрограммных счетчиков страниц.Данный алгоритм подразумевает, что с каждой физической страницей с номером iассоциирован программный счетчик Counti.
Изначально для всех i происходит обнулениесчетчиков. А затем, по таймеру происходит увеличение значений всех счетчиков навеличину интенсивности использования, т.е. на величину R-признака: Counti = Counti + Ri.Иными словами, если за последний таймаут было обращение к странице, что значениесчетчика возрастает, иначе — не изменяется. Соответственно, для откачки выбираетсястраница с минимальным значением счетчика Counti.Данная модель также является достаточно адекватной, но она имеет ряд важныхнедостатков.
Первый связан с тем, что счетчик хранит историю: например, если какая-тостраница в некоторый период времени интенсивно использовалась, то значение счетчикастало настолько большим, что при прекращении работы с данной страницей значениесчетчика достаточно долго не даст откачать эту страницу. А второй недостаток связан стем, что при очень интенсивном обращении к странице возможно переполнение счетчика.Чтобы сгладить указанные недостатки, существует модификация данногоалгоритма, основанная на том, что каждый раз по таймеру значение счетчика сдвигаетсяна 1 разряд влево, после чего последний (правый) разряд устанавливается в значение Rпризнака.2405.5Сегментное распределениеНедостатком страничного распределения памяти является то, что при реализацииэтой модели процессу выделяется единый диапазон виртуальных адресов: от нуля донекоторого предельного значения. С одной стороны, ничего плохого в этом нет, но этосвойство оказывается неудобным по следующей причине.
В процессе есть команды, естьстатические переменные, которые, по сути, являются разными объединениями данных сразличными характеристиками использования. Еще большие отличия в использованиииллюстрируют существующие в процессе стек и область динамической памяти,называемой также кучей. И модель страничной организации памяти подразумеваетстатическое разделение единого адресного пространства: выделяются область для команд,область для размещения данных, а также область для стека и кучи. При этом зачастуюстек и куча размещаются в единой области, причем стек прижат к одной границе области,куча — к другой, и «растут» они навстречу друг другу.
Соответственно, возможныситуации, когда они начинают пересекаться (ситуация переполнения стека). Или дажеесли стек будет располагаться в отдельной области памяти, он может переполнитьвыделенное ему пространство. Таковы основные недостатки страничного распределенияпамяти.Избавиться от указанных недостатков на концептуальном уровне призвана модельсегментного распределения памяти (Рис. 141). Данная модель представляет каждыйпроцесс в виде совокупности сегментов, каждый из которых может иметь свой размер.Каждый из сегментов может иметь собственную функциональность: существуютсегменты кода, сегменты статических данных, сегмент стека и т.д.
Для организацииработы с сегментами может использоваться некоторая таблица, в которой хранитсяинформация о каждом сегменте (его номер, размер и пр.). Тогда виртуальный адрес можетбыть проинтерпретирован как номер сегмента и величина смещения в нем.NsegoffsetNsegsizeoffset>sizebaseдаПрерываниенетbase + offsetТаблица сегментовфизический адресРис.
141. Сегментное распределение.Модель сегментного распределения может иметь достаточно эффективноработающую аппаратную реализацию. Существует аппаратная таблица сегментов сфиксированным числом записей. Каждая запись этой таблицы соответствует своемусегменту и хранит информацию о размере сегмента и адрес начала сегмента (т.е.
адресбазы), а также тут могут присутствовать различные атрибуты, которые будут оговариватьправа и режимы доступа к содержимому сегмента.Итак, имея виртуальный адрес, система аппаратным способом извлекает из негономер сегмента i, обращается к i-ой строке таблицы, из которой извлекается информация осегменте. После этого происходит проверка, не превосходит ли величина сегмента241размера самого сегмента.
Если превосходит, то происходит прерывание; иначе, складываябазу со смещением, вычисляется физический адрес.К достоинствам данной модели можно отнести простоту организации, которая, посути, явилась развитием модели распределения разделов. Если модели распределенияразделов каждому процессу выделяется только один сегмент (раздел), то при сегментноймодели распределения процессу выделяется совокупность сегментов, каждый из которыхбудет иметь свои функциональные обязанности.К недостаткам данной модели необходимо отнести то, что каждый сегмент долженцеликом размещаться в памяти (возникает упоминавшаяся выше проблема неявнойнеэффективности, связанная с принципом локальности).
Также возникают проблемы соткачкой/подкачкой: подкачка осуществляется всем процессом или, по крайней мере,целым сегментом, что зачастую оказывается неэффективно. И поскольку каждый сегменттак или иначе должен быть размещен в памяти, то возникает ограничение на предельныйразмер сегмента.5.6Сегментно-страничное распределениеЕстественным развитием рассмотренной модели сегментного распределенияпамяти стала модель сегментно-страничного распределения.
Эта модель рассматриваетвиртуальный адрес как номер сегмента и смещение в нем. Имеется также аппаратнаятаблица сегментов, посредством которой из виртуального адреса получается т.н.линейный адрес, который, в свою очередь, представляется в виде номера страницы ивеличины смещения в ней. А затем, используя таблицу страниц, получаетсянепосредственно физический адрес.Итак, данный механизм подразумевает, что в процессе имеется ряд виртуальныхсегментов, которые дробятся на страницы. Поэтому данная модель сочетает в себе, содной стороны, логическое сегментирование, а с другой стороны, преимуществастраничной организации (когда можно работать с отдельными страницами памяти, нетребуя при этом полного размещения сегмента в ОЗУ).Примером реализации может служить реализация, предложенная компанией Intel.Рассмотрим упрощённую модель этой реализации (Рис.
142). Виртуальный адрес в этоймодели представляется в виде селектора (информации о сегменте) и смещения всегменте.Виртуальный адресселекторNsegлокализацияoffsetзащитаРис. 142. Сегментно-страничное распределение. Упрощенная модель 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}
