Главная › Телефон › Страничная организация. Список использованной литературы

Страничная организация. Список использованной литературы

Страничная организация памяти применяется только в защищенном режиме , если в регистре управления CR0 бит PG = 1.

Основное применение страничного преобразования адреса связано с реализацией виртуальной памяти, которая позволяет программисту использовать большее пространство памяти, чем физическая основная память.

Принцип виртуальной памяти предполагает, что пользователь при подготовке своей программы имеет дело не с физической ОП, действительно работающей в составе компьютера и имеющей некоторую фиксированную емкость, а с виртуальной (кажущейся) одноуровневой памятью, емкость которой равна всему адресному пространству, определяемому размером адресной шины (L ша) компьютера:

Для 32-разрядного микропроцессора:

Программист имеет в своем распоряжении адресное пространство, ограниченное лишь разрядностью адресной шины, независимо от реальной емкости оперативной памяти компьютера и объемов памяти, которые используются другими программами, параллельно обрабатываемыми в мультипрограммной ЭВМ.

Виртуальная память , обеспечивая возможность программисту обращаться к очень большому объему непрерывного адресного пространства, предоставляемого в его монопольное распоряжение, обладает обычными свойствами: побайтовая адресация, время доступа, сравнимое со временем доступа к оперативной памяти.

На всех этапах подготовки программ, включая загрузку в память, программа представляется в виртуальных адресах, и лишь при выполнении машинной команды виртуальные адреса преобразуются в физические. Для каждой программы, выполняемой в мультипрограммном режиме, создается своя виртуальная память. Каждая программа использует одни и те же виртуальные адреса от нулевого до максимально большого в данной архитектуре.

Для преобразования виртуальных адресов в физические физическая и виртуальная память разбиваются на блоки фиксированной длины, называемые страницами . Объемы виртуальной и физической страниц совпадают. Страницы виртуальной и физической памяти нумеруются. Отсутствующие в физической памяти страницы обычно хранятся во внешней памяти. Фиксированный размер всех страниц позволяет загрузить любую нужную виртуальную страницу в любую физическую.

Как отмечалось выше, при страничном представлении памяти виртуальный (логический) адрес представляет собой номер виртуальной страницы и смещение внутри этой страницы. В свою очередь, физический адрес - это номер физической страницы и смещение в ней.

Правила перевода номеров виртуальных страниц в номера физических страниц обычно задаются в виде таблицы страничного преобразования. Такие таблицы формируются системой управления памятью и модифицируются каждый раз при перераспределении памяти. Операционная система постоянно отслеживает состояние виртуальных страниц той или иной программы и определяет, находится ли она в оперативной памяти, и если находится, то в каком конкретно месте. Прикладные программы не касаются процесса страничного преобразования адреса и могут использовать все адресное пространство. Процессор автоматически формирует особый случай неприсутствия, когда программа обращается к странице, отсутствующей в физической памяти. При обработке этого особого случая ОС загружает затребованную страницу из внешней памяти, при необходимости отправляя некоторую другую страницу на диск (процесс свопинга).

Перевод виртуальных адресов в физические проиллюстрирован на рис. 3.12.

Рис. 3.12. Принцип преобразования виртуального страничного адреса в физический

Рассмотрим пример преобразования адреса виртуальной страницы в адрес физической страницы. Пусть компьютер использует адресное пространство, предполагающее разбиение на страницы объемом V стр = 1I, и имеет оперативную память V ОЗУ = 3 страницы. Пусть на компьютере одновременно выполняются четыре программы, имеющие следующее количество страниц: V A = 2, V B = 1, V C = 3, V D = 2. Переключение между программами происходит через время кванта t k = 1. Время выполнения каждой страницы любой программы составляет t = 2t k . Полагаем, что страницы программ загружаются в оперативную память по мере необходимости и по возможности в свободные области ОЗУ. Если вся память занята, то новая страница замещает ту, к которой дольше всего не было обращений.

При таких условиях таблица загрузки оперативной памяти и таблицы страничного преобразования для каждой программы будут иметь вид, представленный в табл. 3.2.

В таблице распределения оперативной памяти выделены номера активных в данном такте страниц. В таблицах страничного преобразования прочерками отмечены ситуации, когда данная виртуальная страница отсутствует в оперативной памяти.

Таблица 3.2. Пример страничного распределения памяти в мультипрограммной ЭВМ

Страница

Такты

Динамическое распределение оперативной памяти

ОЗУ 0

АО

Таблица страничного преобразования для программы А

A 0

Таблица страничного преобразования для программы В

B 0

Таблица страничного преобразования для программы С

С 0

Таблица страничного преобразования для программы D

D 0

Если каждая страница имеет объем 1000 адресуемых ячеек, то, например, в такте 9 обращение по виртуальному адресу 1100 программы A (виртуальная страница 1, смещение в странице равно 100) приведет к обращению по физическому адресу 2100 (физическая страница 2, смещение в физической странице такое же, как и в виртуальной, то есть 100).

Рассмотрим теперь применение этих общих принципов страничного преобразования адреса в микропроцессоре с архитектурой IA-32 при объеме страницы в 4 Кбайт.

Основой страничного преобразования служит 32-разрядныйлинейный адрес , полученный на этапе сегментного преобразования логического адреса . Страничное преобразование выполняется при значении бита PG = 1 в управляющем регистре CR0.

В этом случае старшие 20 разрядов линейного адреса фактически представляют собой номер виртуальной страницы. Однако при прямом одноступенчатом преобразовании этого номера в номер физической страницы необходима таблица из 2 20 элементов длиной 4 байта каждый (20-разрядный номер страницы плюс некоторая дополнительная информация), т. е. 4 Мбайт. В мультипрограммной среде такая таблица может потребоваться для каждой задачи. Эта таблица должна постоянно храниться в оперативной памяти, чтобы существенно не увеличивать время формирования физического адреса. Для этих целей потребуется постоянное резервирование существенной части емкости ОЗУ, что на этапе появления первых ЭВМ на основе МП с архитектурой IA-32 было практически невозможно.

Вместо этого микропроцессор использует двухступенчатое страничное преобразование адреса. Корневая страница, называемая каталогом таблиц страниц (КТС), содержит 1024 32-разрядных элемента каталога таблиц страниц (ЭКТС - PDE page directory entry). Каждый из них адресует подчиненную таблицу страниц (ТС), то есть всего допускается до 1024 подчиненных таблиц страниц. Каждая из таблиц страниц содержит 1024 32-разрядных элемента таблицы страниц (ЭТС - PTE page table entry), каждый из которых и адресует физическую страницу. Таким образом, общее количество адресуемых физических страниц равно 2 20 , то есть все виртуальное адресное пространство (4 Кбайт * 220 элементов = 2 32 байт). Каждая таблица занимает 1024 4 = 4 Кбайт, то есть ровно 1 страницу. Общий объем таблиц, используемых для страничного преобразования, не уменьшился, а даже несколько возрос за счет использования каталога таблиц страниц. Однако, вопервых, практически всегда в системе этот размер можно существенно уменьшить за счет того, что некоторые линейные адреса никогда не будут сформированы (а эту информацию дают таблицы дескрипторов сегментов), и для них не нужно создавать таблицу страниц. А во-вторых, в оперативной памяти должны постоянно находиться лишь каталог таблиц страниц и таблица страниц выполняемой в настоящее время программы. Остальные таблицы страниц могут временно храниться во внешней памяти.

Рис. 3.13. Страничное преобразование линейного адреса в физический

Таким образом, преобразование линейного адреса в физический имеет вид, представленный на рис. 3.13.

Старшие 20 разрядов линейного адреса разбиваются на два 10-разрядных поля: поле номера элемента каталога таблиц страниц и поле номера элемента таблицы страниц . Так как и каталог таблиц страниц , и каждая таблица страниц занимают ровно 1 страницу и выровнены по границе страницы, то младшие 12 разрядов их базового адреса равны нулю, и для определения их физического адреса достаточно 20-разрядного поля.

Для каталога таблиц страниц его 20-разрядный адрес находится в регистре управления CR3. КТС постоянно находится в памяти и не участвует в свопинге.

Старшие 20 разрядов физического адреса таблицы страниц извлекаются из ЭТС. Структуры элемента КТС и элемента ТС схожи (рис. 3.14).

Рис. 3.14. Структура элементов каталога таблиц страниц и таблицы страниц

Старшие 20 разрядов элемента дают базовый адрес таблицы страниц (в ЭКТС) или физической страницы (в ЭТС). Биты P, A, R/W и U/S имеют определенное сходство с аналогичными атрибутами дескриптора сегмента, другие биты имеют специфическое назначение.

Бит присутствия P показывает, отображается ли адрес страничного кадра (таблицы страниц или страницы памяти) на страницу в физической памяти. При P = 1 страница присутствует в ОЗУ. При P = 0 страницы в памяти нет, и обращение к этой странице вызывает прерывание типа "страничное нарушение".

Бит доступа А устанавливается микропроцессором в состояние А = 1 при обращении к данному страничному кадру для записи или чтения информации.

Бит модификации D (Dirty - "грязный") устанавливается процессором равным 1 в элементе ЭТС при записи на данную страницу. Для элементов каталога таблиц страниц значение бита D является неопределенным. При загрузке страницы в память операционная система сбрасывает бит D. Если при необходимости выгрузки страницы во внешнюю память оказывается, что для нее D = 0, это означает, что к странице в памяти не было обращений на запись, во внешней памяти есть ее точная копия, и реально передавать страницу из памяти на диск не нужно. Тем самым экономится время при свопинге.

Бит чтения-записи R/W и бит U/S (user/supervisor - пользователь/супервизор) определяют права доступа к таблице страниц или к странице для программ с различными уровнями привилегий. Для страниц существует только 2 уровня привилегий: уровень супервизора (U/S = 0), соответствующий значению DPL сегмента 0, 1, 2, и уровень пользователя (U/S = 1), соответствующий DPL = 3. Если к странице осуществляется запрос с уровнем привилегий 3 (программы пользователя), то при значении U/S = 0 ему запрещается доступ к соответствующей таблице или странице. Если U/S = 1, то при значении R/W = 0 разрешается только чтение таблицы или страницы, а при R/W = 1 - и чтение, и запись.

При запросах с большими привилегиями (системные программные уровни 0, 1, 2) допускается з0апись и чтение таблиц и страниц при любых значениях U/S, R/W (табл. 3.3).

Биты PWT и PCD используются для управления работой кэш-памяти при страничной адресации. Бит PCD - запрещение кэширования страницы. При PCD = 1 кэширование запрещено. Бит PWT - бит обратной записи страниц. Определяет метод обновления внешней кэш-памяти (кэш 2-го уровня). При PWT= 1 - обновление проводится методом сквозной записи (как для внутреннего кэша), при PWT = 0 - методом обратной записи.

Биты 9…11 в ЭКТС и ЭТС зарезервированы за операционной системой. Процессор никогда не использует и не изменяет эти биты. Разработчики ОС могут привлечь эти биты для хранения информации о "старении" страниц, чтобы определять страницы, подлежащие замене из внешней памяти, и для других целей.

Старшие 10 разрядов линейного адреса совместно с содержимым регистра управления CR3 определяют необходимый элемент каталога таблиц страниц . Следующие 10 разрядов линейного адреса содержат номер элемента в выбранной таблице страниц.

Так как и ЭКТС, и ЭТС имеют длину 4 байта, для получения смещения начала элемента относительно начала соответствующей таблицы необходимо его номер умножить на 4.

Последние 12 разрядов линейного адреса содержат смещение в странице. Таким образом, сумма смещения в странице и базового адреса страницы, извлеченного из ЭТС, дает физический адрес искомого байта.

Страничная организация виртуальной памяти

В большинстве современных операционных систем виртуальная память организуется с помощью страничной адресации. Оперативная память делится на страницы: области памяти фиксированной длины (например, 4096 байт), которые являются минимальной единицей выделяемой памяти (то есть даже запрос на 1 байт от приложения приведёт к выделению ему страницы памяти). Процесс обращается к памяти с помощью адреса виртуальной памяти, который содержит в себе номер страницы и смещение внутри страницы. Процессор преобразует номер виртуальной страницы в адрес соответствующей ей физической страницы при помощи буфера ассоциативной трансляции. Если ему не удалось это сделать, то требуется обращение к таблице страниц (так называемый Page Walk), что может сделать либо сам процессор, либо операционная система (в зависимости от архитектуры).

(слайд №12)

Рис. 16.4. Пример страничной организации.

Страничная организация (paging) – стратегия управления памятью, при которой:

· логическая память делится на страницы – смежные области одинаковой длины, обычно – степень 2 (например, 512 слов);

· физическая память, соответственно, делится на фреймы такого же размера;

· распределение логической памяти происходит с точностью до страницы;

· физическая память процесса может не быть непрерывной;

· связь между логической и физической памятью процесса осуществляется с помощью таблицы страниц – системной структуры, выделяемой процессу для трансляции его логических адресов в физические .

При страничной организации ОС хранит информацию обо всех свободных фреймах. Поскольку память выделяется с точностью до страницы, возможна внутренняя фрагментация.

Цели страничной организации – обеспечить возможность не смежного распределения физической памяти для процессов, а также расширить пространство логической памяти.

На рис. 16.4 приведен пример страничной организации, который демонстрирует, что, в отличие от непрерывной логической памяти процесса, соответствующие фреймы страниц в основной памяти могут быть расположены не смежно: логической странице 0 соответствует фрейм 1, странице 1 – фрейм 4, странице 2 – фрейм 3, странице 3 – фрейм 7.

(слайд №13)

Рис. 16.5. Пример страничной организации блоками по 4 страницы.

На рис. 16.5 приведен другой возможный пример страничной организации: логическая и физическая память разбита на блоки по 4 страницы подряд; в таблице страниц хранится не номер страницы, а номер блока страниц. Например, в элементе 0 таблицы страниц хранится номер блока 5, по которому адрес начала блока вычисляется домножением содержимого элемента таблицы страниц на размер блока, равный 4 (результат – 20).

Реализация таблицы страниц

Использование ассоциативной памяти. Таблица страниц – непрерывная область физической памяти. В системе имеется базовый регистр таблицы страниц (page table base register – PTBR), указывающий на таблицу страниц и хранящий ее длину.

Таким образом, при страничной организации любой доступ к памяти требует фактически не одного, а двух обращений в память – одно в таблицу страниц, другое – непосредственно к данным или команде. В этом – некоторый недостаток и неэффективность страничной организации, по сравнению с более простыми методами управления памятью.

(слайд №14)

Рис. 16.3. Архитектура трансляции адресов при страничной организации.

При страничной организации логический адрес обрабатывается системой особым образом – как структура (p, d): его старшие разряды обозначают номер страницы , младшие – смещение внутри страницы. Номер страницы (p) трактуется как индекс в таблице страниц, соответствующий элемент которой содержит базовый адрес начала страницы в физической памяти . Смещение внутри страницы (d) добавляется к ее базовому адресу. В результате формируется физический адрес, передаваемый в устройство управления памятью. Архитектура трансляции адресов при страничной организации изображена на рис. 16.3 .

(слайд №15)

Рис. 16.7. Схема трансляции адресов с использованием ассоциативной памяти.

Проблема двух обращений решается введением ассоциативной памяти (cache) страниц, называемой также буфер трансляции адресов (translation lookaside buffer – TLB). Ассоциативная память, по существу, является ассоциативным списком пар вида: (номер страницы, номер фрейма). Ее быстродействие значительно выше, чем у основной памяти и у регистров.

Схема трансляции адресов с использованием ассоциативной памяти изменяется: если номер страницы из логического адреса найден в ассоциативной памяти, то из ее элемента извлекается соответствующий номер фрейма. Если же номер страницы отсутствует в ассоциативной памяти, он выбирается обычным образом из таблицы страниц, но заносится в ассоциативную память. Таким образом, в ассоциативной памяти накапливается информация о наиболее часто используемых страницах.

Модифицированная схема трансляции адресов с использованием TLB иллюстрируется рис. 16.7 .

СТРАНИЧНАЯ ОРГАНИЗАЦИЯ

Как разделы с разными фиксированными размерами, так и разделы переменного размера недостаточно эффективно используют память. Результатом работы первых становится внутренняя фрагментация, результатом работы последних - внешняя. Предположим, однако, что основная память разделена на одинаковые блоки относительно небольшого фиксированного размера. Тогда блоки процесса, известные как страницы (pages), могут быть связаны со свободными блоками памяти, известными как кадры (frames), или фреймы. Каждый кадр может содержать одну страницу данных. При такой организации памяти, как вы узнаете из этого раздела, внешняя фрагментация отсутствует вовсе, а потери из-за внутренней фрагментации ограничены частью последней страницы процесса.

На рис. 7.9 показано использование страниц и кадров. В любой момент времени некоторые из кадров памяти используются, а некоторые свободны. Операционная система поддерживает список свободных кадров. Процесс А, хранящийся на диске, состоит из четырех страниц. Когда приходит время загрузить этот процесс в память, операционная система находит четыре свободных кадра и загружает страницы процесса А в эти кадры (рис. 7.9,6). Затем загружаются процесс В, состоящий из трех страниц, и процесс С, состоящий из четырех страниц. После этого процесс В приостанавливается и выгружается из основной памяти. Позже наступает момент, когда все процессы в памяти оказываются заблокированы, и операционная система загружает в память новый процесс D, состоящий из пяти страниц.

Теперь предположим, что, как в только что рассмотренном выше примере, не имеется одной непрерывной области кадров, достаточной для размещения процесса целиком. Помешает ли это операционной системе загрузить процесс D? Нет, поскольку в этой ситуации можно воспользоваться концепцией логических адресов. Однако одного регистра базового адреса в этой ситуации недостаточно, и для каждого процесса операционная система должна поддерживать таблицу страниц. Таблица страниц указывает расположение кадров каждой страницы процесса. Внутри программы логический адрес состоит из номера страницы и смещения внутри нее. Вспомним, что в случае простого распределения логический адрес представляет собой расположение слова относительно начала программы, которое процессор транслирует в физический адрес. При страничной организации преобразование логических адресов в физические также остается задачей аппаратного уровня, решаемой процессором. Теперь процессор должен иметь информацию о том, где находится таблица страниц текущего процесса. Представленный логический адрес (номер страницы и смещение) процессор превращает с использованием таблицы страниц в физический адрес (номер кадра, смещение).

На рис. 7.10 показаны различные таблицы страниц, после того как процесс D оказывается загруженным в страницы 4, 5, 6, 11 и 12. Таблица страниц содержит по одной записи для каждой страницы процесса, так что таблицу легко проиндексировать номером страницы, начиная с 0. Каждая запись содержит номер фрейма в основной памяти (если таковой имеется), в котором хранится соответствующая страница. Кроме того, операционная система поддерживает единый список свободных (т.е. не занятых никаким процессом и доступных для размещения в них страниц) кадров.

Таким образом, описанная здесь простая страничная организация подобна фиксированному распределению. Отличия заключаются в достаточно малом размере разделов, которые к тому же могут не быть смежными.

Для удобства работы с такой схемой добавим правило, в соответствии с которым размер страницы (а, следовательно, и размер кадра) должен представлять собой степень 2. При использовании такого размера страниц легко показать, что относительный адрес, который определяется относительно начала программы, и логический адрес, представляющий собой номер кадра и смещение, идентичны. Соответствующий пример приведен на рис. 7.11. Здесь используется 16-битовый адрес и страницы размером 1 Кбайт = 1024 байт. Относительный адрес 1502 в бинарном виде записывается как 0000010111011110. При размере страницы в 1 Кбайт поле смещения требует 10 бит, оставляя 6 бит для номера страницы. Таким образом, программа может состоять максимум из 2 6 = 64 страниц по 1 Кбайт каждая. Как показано на рис. 7.11, относительный адрес 1502 соответствует смещению 478 (0111011110) на странице 1 (000001), что дает то же бинарное число 0000010111011110.

Использование страниц с размером, равным степени двойки, приводит к таким следствиям. Во-первых, схема логической адресации прозрачна для программиста, ассемблера и компоновщика. Каждый логический адрес (номер страницы и смещение) программы идентичен относительному адресу. Во-вторых, при этом относительно просто реализуется аппаратная функция преобразования адресов во время работы. Рассмотрим адрес из п+т бит, где крайние слева п бит представляют собой номер страницы, а крайние справа m бит - смещение. В нашем примере (рис. 7.11,6) п = 6 и т = 10. Для преобразования адреса необходимо выполнить следующие шаги.

Выделить номер страницы, который представлен п левыми битами логического адреса.

Используя номер страницы в качестве индекса в таблице страниц процесса, найти номер кадра k.

Начальный физический адрес кадра - k´2"", и интересующий нас физический адрес представляет собой это число плюс смещение. Такой адрес не надо вычислять - он получается в результате простого добавления номера кадра к смещению.

В нашем примере имеется логический адрес 0000010111011110, представляющий страницу номер 1 и смещение 478. Предположим, что эта страница размещена в кадре основной памяти номер 6 (бинарное представление - 000110). В таком случае физический адрес представляет собой кадр 6, смещение 478, т.е. 0001100111011110 (рис. 7.12,а).

Итак, в случае простой страничной организации основная память разделяется на множество небольших кадров одинакового размера. Каждый процесс разделяется на страницы того же размера, что и кадры; малые процессы требуют меньшего количества кадров, большие - большего. При загрузке процесса в память все его страницы загружаются в свободные кадры, и информация о размещении страниц заносится в соответствующую таблицу. Такой подход позволяет избежать множества присущих распределению памяти проблем.

СЕГМЕНТАЦИЯ

Альтернативным способом распределения пользовательской программы является сегментация. В этом случае программа и связанные с нею данные разделяются на ряд сегментов. Хотя и существует максимальный размер сегмента, на них не накладывается условие равенства размеров. Как и при страничной организации, логический адрес состоит из двух частей, в данном случае - номера сегмента и смещения.

Использованием сегментов разного размера этот способ похож на динамическое распределение памяти. Если не используются оверлеи и виртуальная память, то для выполнения программы все ее сегменты должны быть загружены в память; однако в отличие от динамического распределения в этом случае сегменты могут занимать несколько разделов, которые, к тому же, могут не быть смежными. Сегментация устраняет внутреннюю фрагментацию, однако, как и динамическое распределение, страдает от фрагментации внешней. Тем не менее ее степень снижается, в силу того что процесс разбивается на ряд небольших частей.

В то время как страничная организация невидима для программиста, сегментация, как правило, видима и обычно используется при размещении кода и данных в разных сегментах. При использовании принципов модульного программирования как код, так и данные могут быть дополнительно разбиты на сегменты. Главным недостатком при работе с сегментами является необходимость заботиться о том, чтобы размер сегмента не превысил максимальный.

Еще одно следствие того, что сегменты имеют разные размеры, состоит в отсутствии простого соотношения между логическими и физическими адресами. Аналогично страничной организации, схема простой сегментации использует таблицу сегментов для каждого процесса и список свободных блоков основной памяти. Каждая запись таблицы сегментов должна содержать стартовый адрес сегмента в основной памяти и его длину, чтобы обезопасить систему от использования некорректных адресов. При работе процесса адрес его таблицы сегментов заносится в специальный регистр, используемый аппаратным обеспечением. Рассмотрим адрес из п+т бит, где крайние слева п бит являются номером сегмента, а правые т бит - смещением. В нашем примере, помещенном на рис. 7.11,в, n = 4 и т - 12. Таким образом, максимальный размер сегмента составляет 2 12 = 4096. Для трансляции адреса необходимо выполнение следующих действий.

Выделить из логического адреса п крайних слева битов, получив таким образом номер сегмента.

Используя номер сегмента в качестве индекса в таблице сегментов процесса, найти физический адрес начала сегмента.

Сравнить смещение, представляющее собой крайние справа т бит, с длиной сегмента. Если смещение больше длины, адрес некорректен.

Требуемый физический адрес представляет собой сумму физического адреса начала сегмента и смещения.

В нашем примере имеется логический адрес 0001001011110000, представляющий собой сегмент номер 1, смещение 752, Предположим, что этот сегмент располагается в основной памяти начиная с физического адреса 0010000000100000. Тогда интересующий нас физический адрес равен 0010000000100000+001011110000 = 0010001100010000 (см. рис. 7.12,6).

Итак, в случае простой сегментации процесс разделяется на ряд сегментов, размер которых может быть разным. При загрузке процесса все его сегменты размещаются в свободных областях памяти, и соответствующая информация вносится в таблицу сегментов.

РЕЗЮМЕ, КЛЮЧЕВЫЕ ТЕРМИНЫ И КОНТРОЛЬНЫЕ ВОПРОСЫ

Одной из наиболее важных и сложных задач операционной системы является управление памятью. Основная память может рассматриваться как ресурс, который распределяется и совместно используется рядом активных процессов. Для эффективного использования процессора и устройств ввода-вывода желательно размещение в основной памяти максимально возможного количества процессов. Кроме того, желательно дать программисту возможность разрабатывать программы без ограничений их размера.

Основными инструментами управления памятью являются страничная организация и сегментация. При страничной организации каждый процесс разделяется на относительно малые страницы фиксированного размера; сегментация позволяет использовать части разного размера. Кроме того, возможно комбинирование сегментации и страничной организации в единой схеме управления памятью.

Ключевые термины

Внешняя фрагментация Логический адрес Страница

Внутренняя фрагментация Относительный адрес Страничная организация

времени исполнения Переносимая загрузка Уплотнение

Динамическое распределение Распределение Управление памятью

Динамическое связывание Редактор связей Физическая организация

Защита Сегментация Фиксированное

Кадр Система двойников распределение

Контрольные вопросы

7.1. Каким требованиям должно удовлетворять управление памятью?

7.2. Почему желательно обеспечить возможность переноса процессов?

7.3. Почему невозможно обеспечить защиту памяти во время компиляции программы?

7.4. По каким причинам может потребоваться обеспечение доступа к одной области памяти нескольким процессам?

7.5. В чем состоит преимущество использования разделов разного размера при использовании схемы фиксированного распределения?

7.6. В чем состоит отличие между внутренней и внешней фрагментацией?

7.7. В чем заключается различие между логическим, относительным и физическим адресами?

7.8. В чем разница между страницей и кадром?

7.9. В чем разница между страницей и сегментом?

Поскольку распределение вытесняется технологиями виртуальной памяти, большинство книг предлагают только поверхностный обзор рассматриваемых в данной главе методов. Одной из наиболее полных и интересных работ является ; обсуждение стратегий распределения памяти имеется и в .

Вопросы компоновки и загрузки рассматриваются во многих книгах, посвященных разработке программ, архитектуре компьютеров и операционным системам. Здесь можно порекомендовать обратиться к книгам [ВЕСК90] и .

ВЕСК90 BeckL. System Software, - Reading, MA: Addison-Wesley, 1990.

CLAR98Clarke D., Merusi D. System Software Programming: The Way Thing Work. - Upper Saddle River, HJ: Prentice Hall, 1998.

KNUT97Кнут Д.Э. Искусство программирования. Том 1. Основные алгоритмы, 3-е изд. - М.: Издательский дом "Вильяме", 2000.

MILE92Milenkovic M. Operating Systems: Concepts and Design. - New York: I- McGraw-Hill, 1992.

ЗАДАЧИ

7.1. В разделе 2.3 были перечислены пять целей управления памятью, а в разделе 7.1 - пять требований. Обоснуйте взаимосвязанность этих списков.

7.2. Рассмотрите схему динамического распределения. Покажите, что в среднем количество свободных блоков памяти ("дыр") в два раза меньше количества выделенных процессам разделов.

7.3. Для реализации различных алгоритмов распределения, обсуждавшихся при рассмотрении динамического распределения (раздел 7.2), необходима поддержка списка свободных блоков памяти. Какова средняя продолжительность поиска для каждого из рассмотренных методов (наилучшего, первого и следующего подходящего)?

7.4. Рассмотрите еще один алгоритм размещения при динамическом распределении - метод наихудшего подходящего, при котором для размещения процесса используется наибольший свободный блок памяти. Каковы его достоинства и недостатки по сравнению с другими рассмотренными методами? Какова средняя длина поиска при этом методе?

7.5. Система двойников используется для распределения блока размером 1 Мбайт.

а. Изобразите в виде, подобном приведенному на рис. 7.6, результат выполнения такой последовательности запросов: запрос А = 70 Кбайт, запрос В = 35 Кбайт, запрос С = 80 Кбайт, освобождение А, запрос D = 60 Кбайт, освобождение В, освобождение D, освобождение С.

б. Приведите представление системы двойников в виде бинарного дерева после освобождения В.

7.6. Рассмотрим систему двойников, в которой некий только что выделенный блок имеет адрес 011011110000.

а. Если размер блока равен 4, то каков бинарный адрес его двойника?

б. Если размер блока равен 16, то каков бинарный адрес его двойника?

7.7. Пусть buddy k (x) - адрес того блока размером 2 k , который является двойником блока по адресу х. Запишите выражение для buddy k (х) .

7.8. Последовательность Фибоначчи определяется следующим образом:

F 0 =0, F l =l,...,F n+2 =F n+1 +F n , n>0

а. Можно ли использовать эту последовательность для разработки системы двойников?

б. Каким достоинством должна обладать такая система двойников по сравнению с описанной в данной главе?

7.9. Во время выполнения программы процессор увеличивает содержимое регистра команд (счетчика кода) на одно слово после выборки каждой команды. Однако если встречаются команды ветвления или вызова подпрограммы, то содержимое данного регистра вызывает продолжение выполнения в некотором другом месте программы. Рассмотрим рис. 7.8. Имеется альтернатива.

В регистре команд использовать относительный адрес и выполнять трансляцию адресов динамически, с содержимым регистра команд в качестве входных данных. Команды ветвления или вызова подпрограммы генерируют относительный адрес, который и заносится в регистр команд.

В регистре команд содержать абсолютный адрес. В этом случае команды ветвления или вызова подпрограммы генерируют относительный адрес, который динамически транслируется, и результат трансляции заносится в регистр команд.

Какой подход следует предпочесть?

7.10. Виртуальный адрес а в страничной системе представляет собой пару (p,w), в которой р - номер страницы, a w - номер байта этой страницы. Пусть z -количество байтов в странице. Найдите формулу, представляющую р и w как функции от z и а.

7.11. Рассмотрим память, в которой смежные сегменты S 1 , S 2 , ..., S n размещаются в порядке их создания от одного конца памяти к другому, как показано ниже:

S 1

S 2

…

S n

Свободно

При создании сегмента S n +1 он размещается непосредственно после сегмента S n даже если некоторые из сегментов S 1 , S 2 , ..., S n были к этому моменту удалены. Когда граница между сегментами (используемыми или удаленными) и свободной памятью достигает конца памяти, используемые сегменты уплотняются, а. Покажите, что доля времени F, затрачиваемая на уплотнение, удовлетворяет следующему неравенству:

s - средняя длина сегмента в словах,

t - среднее время жизни сегмента (в обращениях к памяти),

f - доля памяти, не используемая в установившихся условиях.

Указание: найдите среднюю скорость, с которой рассматриваемая граница движется по памяти, и предположите, что копирование одного слова требует как минимум двух обращений к памяти.

б. Определите F для f = 0.2, t = 1000 и s = 50.

микропроцессора :

Программист имеет в своем распоряжении адресное пространство , ограниченное лишь разрядностью адресной шины, независимо от реальной емкости оперативной памяти компьютера и объемов памяти, которые используются другими программами, параллельно обрабатываемыми в мультипрограммной ЭВМ.

Виртуальная память , обеспечивая возможность программисту обращаться к очень большому объему непрерывного адресного пространства, предоставляемого в его монопольное распоряжение, обладает обычными свойствами: побайтовая адресация , время доступа , сравнимое со временем доступа к оперативной памяти.

На всех этапах подготовки программ, включая загрузку в память, программа представляется в виртуальных адресах , и лишь при выполнении машинной команды виртуальные адреса преобразуются в физические. Для каждой программы, выполняемой в мультипрограммном режиме, создается своя виртуальная память . Каждая программа использует одни и те же виртуальные адреса от нулевого до максимально большого в данной архитектуре.

Как отмечалось выше, при страничном представлении памяти виртуальный ( логический) адрес представляет собой номер виртуальной страницы и смещение внутри этой страницы. В свою очередь , физический адрес - это номер физической страницы и смещение в ней.

Правила перевода номеров виртуальных страниц в номера физических страниц обычно задаются в виде таблицы страничного преобразования . Такие таблицы формируются системой управления памятью и модифицируются каждый раз при перераспределении памяти. Операционная система постоянно отслеживает состояние виртуальных страниц той или иной программы и определяет, находится ли она в оперативной памяти, и если находится, то в каком конкретно месте. Прикладные программы не касаются процесса и могут использовать все адресное пространство . Процессор автоматически формирует особый случай неприсутствия, когда программа обращается к странице, отсутствующей в физической памяти. При обработке этого особого случая ОС загружает затребованную страницу из внешней памяти, при необходимости отправляя некоторую другую страницу на диск (процесс свопинга).

Перевод виртуальных адресов в физические проиллюстрирован на рис. 3.12 .

Рис. 3.12.

Рассмотрим пример преобразования адреса виртуальной страницы в адрес физической страницы . Пусть компьютер использует адресное пространство , предполагающее разбиение на страницы объемом V стр = 1I , и имеет оперативную память V ОЗУ = 3 страницы. Пусть на компьютере одновременно выполняются четыре программы, имеющие следующее количество страниц: V A = 2 , V B = 1 , V C = 3 , V D = 2 . Переключение между программами происходит через время кванта t k = 1 . Время выполнения каждой страницы любой программы составляет t = 2t k . Полагаем, что страницы программ загружаются в оперативную память по мере необходимости и по возможности в свободные области ОЗУ . Если вся память занята, то новая страница замещает ту, к которой дольше всего не было обращений.

Таблица 3.2. Пример страничного распределения памяти в мультипрограммной ЭВМ

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
Страница	Такты
	Динамическое распределение оперативной памяти
ОЗУ 0	АО	АО	АО	DO	DO	DO	CO	CO	CO	C1	C1	C1	C1	C1	C1	C1
1		B0	B0	B0	A0	A0	A0	D0	D0	D0	D1	D1	D1	D1	D1	D1
2			C0	C0	C0	B0	B0	B0	A1	A1	A1	A1	A1	A1	C2	C2
	Таблица страничного преобразования для программы А
A 0	0	0	-	-	1	1	1	-	-	-	-	-	-	-	-	-
1	-	-	-	-	-	-	-	-	2	2	2	2	2	2	-	-
	Таблица страничного преобразования для программы В
B 0	-	1	1	1	-	2	2	2	-	-	-	-	-	-	-	-
	Таблица страничного преобразования для программы С
С 0	-	-	2	2	2	-	0	0	0	-	-	-	-	-	-	-
1	-	-	-	-	-	-	-	-	-	0	0	0	0	0	0	0
2	-	-	-	-	-	-	-	-	-	-	-	-	-	-	2	2
	Таблица страничного преобразования для программы D
D 0	-	-	-	0	0	0	-	1	1	1	-	-	-	-	-	-
1	-	-	-	-	-	-	-	-	-	-	1	1	1	1	1	1

Если каждая страница имеет объем 1000 адресуемых ячеек, то, например, в такте 9 обращение по виртуальному адресу 1100 программы A ( виртуальная страница 1, смещение в странице равно 100) приведет к обращению по физическому адресу 2100 ( физическая страница 2, смещение в физической странице такое же, как и в виртуальной, то есть 100).

Основой страничного преобразования служит 32-разрядный линейный адрес , полученный на этапе сегментного преобразования логического адреса . Страничное преобразование выполняется при значении бита PG = 1 в управляющем регистре CR0 .

В этом случае старшие 20 разрядов линейного адреса фактически представляют собой номер виртуальной страницы . Однако при прямом одноступенчатом преобразовании этого номера в номер физической страницы необходима таблица из 2 20 элементов длиной 4 байта каждый (20-разрядный номер страницы плюс некоторая дополнительная информация ), т. е. 4 Мбайт. В мультипрограммной среде такая таблица может потребоваться для каждой задачи. Эта таблица должна постоянно храниться в оперативной памяти, чтобы существенно не увеличивать время формирования физического адреса . Для этих целей потребуется постоянное резервирование существенной части емкости ОЗУ , что на этапе появления первых ЭВМ на основе МП с архитектурой IA-32 было практически невозможно.

Вместо этого микропроцессор использует двухступенчатое страничное преобразование адреса . Корневая страница, называемая каталогом таблиц страниц (КТС), содержит 1024 32-разрядных элемента каталога таблиц страниц (ЭКТС - PDE page directory entry ). Каждый из них адресует подчиненную таблицу страниц (ТС), то есть всего допускается до 1024 подчиненных таблиц страниц. Каждая из таблиц страниц содержит 1024 32-разрядных элемента таблицы страниц (ЭТС - PTE page table entry ), каждый из которых и адресует физическую страницу. Таким образом, общее количество адресуемых физических страниц равно 2 20 , то есть все виртуальное адресное пространство (4 Кбайт * 2 20 элементов = 2 32 байт ). Каждая таблица занимает 1024 * 4 = 4 Кбайт, то есть ровно 1 страницу. Общий объем таблиц, используемых для страничного преобразования , не уменьшился, а даже несколько возрос за счет использования каталога таблиц страниц . Однако, во-первых, практически всегда в системе этот размер можно существенно уменьшить за счет того, что некоторые линейные адреса никогда не будут сформированы (а эту информацию дают таблицы дескрипторов сегментов), и для них не нужно создавать таблицу страниц. А во-вторых, в оперативной памяти должны постоянно находиться лишь каталог таблиц страниц и таблица страниц выполняемой в настоящее время программы. Остальные таблицы страниц могут временно храниться во внешней памяти.

Рис. 3.13.

Таким образом, преобразование линейного адреса в физический имеет вид, представленный на рис. 3.13 .

Рис. 3.14.

Старшие 20 разрядов элемента дают базовый адрес таблицы страниц (в ЭКТС) или физической страницы (в ЭТС). Биты P , A , R/W и U/S имеют определенное сходство с аналогичными атрибутами дескриптора сегмента, другие биты имеют специфическое назначение.

Фрагментация

Фрагментация – это дробление памяти на мелкие не смежные свободные области маленького размера. Фрагментация возникает после выполнения системой большого числа запросов на память, таких, что размеры подходящих свободных участков памяти оказываются немного больше, чем требуемые. Например, если имеется 100 смежных свободных областей памяти по 1000 слов, то после выполнения 100 запросов на память по 999 слов каждый в списке свободной памяти останутся 1000 областей по одному слову.

Фрагментация бывает внутренняя и внешняя . При внешней фрагментации имеется достаточно большая область свободной памяти, но она не является непрерывной. Внутренняя фрагментация может возникнуть вследствие применения системой специфической стратегии выделения памяти, при которой фактически в ответ на запрос память выделяется несколько большего размера, чем требуется, - например, с точностью до страницы (листа ), размер которого – степень двойки. Страничная организация памяти подробно рассматривается далее в данной лекции.

Внешняя фрагментация может быть уменьшена или ликвидирована путем применения компактировки (compaction) – сдвига или перемешивания памяти с целью объединения всех не смежных свободных областей в один непрерывный блок. Компактировка может выполняться либо простым сдвигом всех свободных областей памяти, либо путем перестановки занятых областей, с выбором на каждом шаге подходящей свободной области методом наиболее подходящего. Компактировка возможна, только если связывание адресов и перемещение (см. лекцию 15) происходит динамически. Компактировка выполняется во время исполнения программы.

При компактировке памяти и анализе свободных областей может быть выявлена проблема зависшей задачи : какая-либо задача может "застрять" в памяти, так как выполняет ввод-вывод в свою область памяти (по этой причине откачать ее невозможно). Решение данной проблемы: ввод-вывод должен выполняться только в специальные буфера, выделяемой для этой цели операционной системой.

Страничная организация (paging) – стратегия управления памятью, при которой:

логическая память делится на страницы – смежные области одинаковой длины, обычно – степень 2 (например, 512 слов);
физическая память, соответственно, делится на фреймы такого же размера;
распределение логической памяти происходит с точностью до страницы;
физическая память процесса может не быть непрерывной;
связь между логической и физической памятью процесса осуществляется с помощью таблицы страниц – системной структуры, выделяемой процессу для трансляции его логических адресов в физические .

При страничной организации ОС хранит информацию обо всех свободных фреймах. Поскольку память выделяется с точностью до страницы, возможна внутренняя фрагментация (см. п. 16.5).

Архитектура трансляции адресов при страничной организации изображена на рис. 16.3.

Рис. 16.3. Архитектура трансляции адресов при страничной организации.

Рис. 16.4. Пример страничной организации.

Рис. 16.5. Пример страничной организации блоками по 4 страницы.

Использования списка свободных фреймов иллюстрируется на рис. 16.6.

увеличить изображение
Рис. 16.6. Список свободных фреймов.

Первоначально список состоит из 5 фреймов. При вводе в систему нового процесса с логической памятью из 4 страниц, после загрузки процесса в память, последовательные логические страницы процесса размещаются в первых по списку физических фреймах. В результате в списке свободных фреймов остается один элемент.

Реализация таблицы страниц

Таким образом, при страничной организации любой доступ к памяти требует фактически не одного, а двух обращений в память – одно в таблицу страниц, другок – непосредственно к данным или команде. В этом – некоторый недостаток и неэффективность страничной организации, по сравнению с более простыми методами управления памятью.

В системах с теговой архитектурой, например, "Эльбрус", регистр таблицы страниц (регистр таблицы страниц пользователя – РТСП) содержит дескриптор таблицы страниц, который, кроме ее адреса, содержит также ее длину.

Проблема двух обращений решается введением ассоциативной памяти (cache) страниц, называемой также буфер трансляции адресов (translation lookaside buffer – TLB). Ассоциативная память, по существу, является ассоциативным списком пар вида: (номер страницы, номер фрейма). Ее быстродействие значитель выше, чем у основной памяти и у регистров.

Модифицированная схема трансляции адресов с использованием TLB иллюстрируется рис. 16.7.

увеличить изображение
Рис. 16.7. Схема трансляции адресов с использованием ассоциативной памяти.