Операционные системы 2011 (1114689), страница 65
Текст из файла (страница 65)
Для решения задачи в компьютере имеется битоваяматрица, размером 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) и который может разделятьсямежду процессами. Заметим, что каждая запись таблиц LDT и GDT хранит полнуюинформацию о сегменте (адрес базы, размер и пр.).
Итак, в селекторе хранится тип242сегмента, после которого следует номер сегмента (номер записи в соответствующейтаблице). Помимо перечисленного, селектор хранит различные атрибуты, касающиесярежимов доступа к сегменту.Преобразование виртуального адреса в физический имеет достаточно простуюорганизацию (Рис. 143). На основе виртуального адреса, посредством использованияинформации из таблиц LDT и GDT, получается 32-разрядный линейный адрес, которыйинтерпретируется в терминах двухуровневой иерархической страничной организации.Последние 12 разрядов отводятся под смещение в физической странице, а первые 20разрядов интерпретируют как 10-разрядный индекс во «внешней» таблице групп страници 10-разрядное смещение в соответствующей таблице второго уровня иерархии.Виртуальный адресИспользование селектора и содержимого таблиц LDT и GDTЛинейный адресДвухуровневая страничная организацияP1P2offset101012Физический адресРис.
143. Схема преобразования адресов.Среди особенностей данной модели можно отметить, что можно «выключать»страничную функцию, и тогда модель Intel начинает работать по сегментномураспределению. А можно не использовать сегментную организацию процесса, и тогдаданная реализация будет работать по страничному распределению памяти.24366.1Управление внешними устройствамиОбщие концепции6.1.1 Архитектура организации управления внешними устройствамиКак отмечалось ранее, при организации взаимодействия работы процессора ивнешних устройств различают два потока информации: поток управляющей информации(т.е.
поток команд какому-либо устройству управления) и поток данных (потокинформации, участвующей в обмене обычно между ОЗУ и внешним устройствами).Рассматривая историю вопроса, необходимо отметить, что управление внешнимиустройствами претерпело достаточно большие изменения.Первой исторической моделью стало непосредственное управление центральнымпроцессором внешними устройствами (Рис. 144.А), когда процессор на уровнемикрокоманд полностью обеспечивал все действия по управлению внешнимиустройствами. Иными словами, поток управления полностью шел через ЦПУ, а наравне сним через процессор шел и поток данных.
Эта модель иллюстрирует синхронноеуправление: если начался обмен, то, пока он не закончится, процессор не продолжаетвычисления (поскольку занят обменом).А.Б.ОЗУОЗУВ.ОЗУВнешнееустройствоЦПЦПконтроллервнешнегоустройстваDMA-контроллер+контроллер илипроцессорввода-выводаВнешнееустройствоВнешнееустройствоЦПРис. 144.
Модели управления внешними устройствами: непосредственное (А),синхронное/асинхронное (Б), с использованием контроллера прямогодоступа или процессора (канала) ввода-вывода (В).Вторая модель, появившаяся с развитием вычислительной техники, связана споявлением специализированных контроллеров устройств, которые концептуальнорасполагались между центральным процессором и соответствующими внешнимиустройствами (Рис.
144.Б). Контроллеры позволяли процессору работать с болеевысокоуровневыми операциями при управлении внешними устройствами. Таким образом,процессор частично освобождался от потока управления внешними устройствами за счеттого, что вместо большого числа микрокоманд конкретного устройства он оперировал244меньшим количеством более высокоуровневых операций.
Но и эта модель оставаласьсинхронной.Следующим этапом стало развитие предыдущей модели до асинхронной,осуществление которой стало возможным благодаря появлению аппарата прерываний.Данная модель позволяла запустить обмен для одного процесса, после этого поставить насчет другую задачу (или же текущий процесс может продолжить выполнять какие-то своивычисления), а по окончании обмена (успешного или неуспешного) в системе возникнетпрерывание, сигнализирующее возможность дальнейшего выполнения первого процесса.Но и эти две модели предполагали, что поток данных идет через процессор.Кардинальным решением проблемы перемещения обработки потока данных изпроцессора стало использование появившихся контроллеров прямого доступа к памяти(или DMA-контроллеров, Direct Memory Access, Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
