Раздел IV. Управление памятью
Лекция 10. Методы управления памятью
Типы адресов и их преобразований. Классификация методов управ- ления памятью. Методы управления памятью, использующие раз- делы. Страничный, сегментный и сегментно-страничный методы управления виртуальной памятью. Механизм свопинга. Принцип работы кэш-памяти.
В программе можно выделить три типа адресов: символьные имена, виртуальные адреса и физические адреса (рис.10.1). Сим- вольные имена являются идентификаторами переменных в про- грамме. Виртуальные адреса – это условные адреса, вырабатывае- мые транслятором исходного кода в объектный код. В простейшем случае транслятор может выполнять преобразование символьных имен непосредственно в физические адреса. Физические адреса – это номера ячеек в памяти. Данные номера выставляются централь- ным процессором на адресную шину при доступе к оперативной па- мяти.
Преобразование виртуального адреса в физический адрес мо- жет выполняться двумя способами. При загрузке программы в па- мять виртуальные адреса отображаются использованием перемеща- ющего загрузчика. Его работа состоит из загрузки программы в по- следовательные ячейки, начиная с некоторого базового адреса, и настройки смещений внутри программы относительно этого адреса
(рис. 10.2).
Динамическое преобразование происходит при каждом обра- щении по виртуальному адресу в темпе обращений. Для такого пре- образования используется аппаратура компьютера и операционная система.
87
Рис. 10.1. Типы адресов и их преобразований
Рис. 10.2. Схема работы перемещающего загрузчика
Символьные имена
Виртуальные адреса
Физические адреса
Транслятор преобразует идентификаторы в адреса
Перемещающий загрузчик
Динамическое преобразование
Виртуальное адресное пространство
Физическое
адресное пространствоJump #10
Jump #110
#0
#0
#100
Базовый адрес загрузки
88
Методы управления памятью. Существует два основных подхода к реализации процедур управления памятью: с использова- нием дискового пространства и без использования дискового про- странства. Методы фиксированных разделов, динамических разде- лов и перемещаемых разделов не используют дисковое простран- ство. Страничный, сегментный и сегментно-страничный метод ис- пользуют дисковую память. Специальными приемами управления памятью являются свопинг и кэширование.
Реализацию метода фиксированных разделов иллюстрирует рис. 10.3. Перед началом работы оператор разделяет физическую память на разделы заданного размера. Поступающие в систему зада- чи либо занимают свободный раздел подходящего размера, либо попадают в очередь. Очередь может быть общей для всех разделов или индивидуальной для каждого раздела.
Рис. 10.3. Метод фиксированных разделов
Достоинством данного метода является простота реализации.
Вместе с тем, присутствует недостаточная гибкость. Например, уро- вень мультипрограммирования жестко ограничен числом выделен- ных разделов. В современных операционных системах пользователь также может вручную управлять разделами внутри виртуального
Физическое адресное пространство
Раздел
ОС
Раздел 1
Раздел 2
Раздел 3
Раздел 4
Общая очередь задач к разделам
Индивидуальные очере- ди задач к разделам
89 адресного пространства процесса. Пример такого приема описан в лекции 12.
Динамические разделы. При использовании динамических разделов распределение памяти по разделам заранее неизвестно.
Операционная система ведет таблицы занятых и свободных разде- лов. При поступлении новой задачи для ее загрузки выбирается сво- бодный раздел подходящего размера. Возможны разные стратегии выбора свободного раздела: первый по порядку подходящий, наименьший по размеру подходящий, наибольший по размеру под- ходящий раздел.
Рис. 10.4. Метод динамических разделов, возникновение фрагментации
Достоинства способа – это большая гибкость по сравнению с методом фиксированных разделов и отсутствие зависимости уровня мультипрограммирования от начального разбиения на разделы. Не- достатком является эффект фрагментации памяти (рис. 10.4). Он за- ключается в появлении с течением времени большого числа не- больших несмежных сегментов. Суммарный объем свободной памя- ти, содержащийся в таких сегментах, может быть большим, однако малый размер каждого отдельного сегмента не позволяет загрузить
Физическое адресное пространство
ОС
ОС
ОС
ОС
90 программу. Варьирование стратегий выбора свободного раздела может уменьшить фрагментацию. В современных операционных системах такой способ используется для управления кучей (динами- ческой памятью) процесса.
Перемещаемые разделы. Данный способ расширяет управле- ние динамическими разделами путем добавления процедуры сжатия: перемещения занятых разделов в одну последовательную область старших или младших адресов. В результате свободная память раз- мещается в последовательно расположенных ячейках памяти. До- стоинством такой организации является отсутствие фрагментации памяти. Однако в отличие от предыдущих способов нельзя исполь- зовать перемещающий загрузчик. Процедура сжатия может быть затратной по времени. Поэтому обычно сжатие выполняется, когда не удается выполнить загрузку программы или во время простоя си- стемы.
Страничный способ. Мотивом использования дискового ад- ресного пространства является предоставление виртуальной памяти.
Виртуальная память – это совокупность программно-аппаратных средств, позволяющих исполнять программы, размер которых пре- восходит доступную оперативную память компьютера. Для при- кладного программиста механизм виртуальной памяти является про- зрачным. То есть он не требует от него дополнительных усилий по управлению памятью.
При страничной организации памяти виртуальное простран- ство процессов делится на страницы равного размера. Размер стра- ницы кратен степени двойки. Физическое адресное пространство делится на страницы такого же размера. Схема организации стра- ничной памяти показана на рис.10.5.
Страницы процесса при таком разбиении размещаются в фи- зическом адресном пространстве произвольным образом, необяза- тельно по непрерывным адресам. Часть адресного пространства процесса может быть выгружена во внешнюю память.
91
Рис. 10.5. Схема страничной организации памяти
Рис. 10.6. Схема преобразования адреса при страничной организации памяти
Обращение к памяти выполняется по следующей схеме. В слу- чае если виртуальная страница присутствует в физической памяти, старшие биты виртуального адреса (Р) содержат номер виртуальной страницы. По таблице страниц устанавливается соответствующий адрес физической страницы. Он конкатенируется с младшими k раз-
Виртуальные адресные пространства процессов
Страница 11
Страница12
Страница13
Страница 21
Страница22
Страница23
Физическое адресное пространство
Страница 13
Страница 22
Страница 11
Таблицы страниц процессов
11 12
ВП
13 21
ВП
22 23
ВП
Таблица активного процесса
ВП
Номер виртуальной страницы P
Смещение S
Таблица страниц процесса
P
Номер физической страницы P’
Номер физической страницы P’
Смещение S
k
92 рядами виртуального адреса. Получается физический адрес. Схема преобразования виртуального адреса в физический адрес показана на рис.10.6.
В случае если виртуальный адрес отсутствует в физической памяти (клетка ВП, содержимое располагается во внешней памяти), происходит страничное прерывание. Процесс переходит к ожида- нию на системном объекте ядра,
запускается процедура загрузки страниц, а контекст переключается на следующий готовый процесс.
Для загрузки страниц определяется место в физической памя- ти. Если оно есть, то выполняется загрузка, коррекция таблицы страниц, перевод процесса в готовое состояние. В противном случае выбирается страница для вытеснения. Если страница была модифи- цирована, то предварительно необходимо записать страницу на диск, иначе содержание страницы переписывается загружаемой страницей. Кандидаты на выгрузку определяются управляющей ин- формацией операционной системы.
Сегментный способ. При страничном распределении памяти адресное пространство делится механически на страницы равного размера. При сегментном распределении памяти размеры сегментов произвольны, сегменты снабжены атрибутами, определяющими способ их использования. Разделение программы на сегменты опре- деляется программистом или компилятором. Атрибуты сегмента определяют способ его использования: для исполнения, чтения, за- писи. Также сегментное распределение позволяет разделять сегмен- ты между процессами.
В таблице сегментов указывается базовый адрес сегмента в физической памяти, а не номер, как в случае страничного способа.
Размер сегмента не фиксирован, в отличие от страничного способа адресации. Он хранится в таблице сегментов и используется для контроля выхода за границы сегмента. Из-за разницы в размерах сегментов, как и в случае с динамическими разделами, для сегмент- ного способа управления памятью характерно явление фрагмента- ции памяти.
Сегментно-страничный способ. Цель сегментно-страничной организации памяти: решить проблему фрагментации физической памяти, сохраняя преимущество сегментного распределения, кото- рое заключается в осмысленном распределении памяти.
93
Рис. 10.7. Схема преобразования адреса при сегментно-страничной организации памяти
При сегментно-страничной организации виртуальный адрес состоит из 3 частей: номера сегмента g, номера страницы в сегменте p и смещения внутри страницы S. Номер сегмента
преобразуется с использованием таблицы сегментов, а номер страницы – с использо- ванием таблицы страниц (рис.10.7). В результате линейный физиче- ский адрес состоит из 2 частей: номера физической страницы n и смещения S.
Свопинг. Виртуализация памяти в ранних операционных си- стемах осуществлялась на основе свопинга. Свопинг (swapping) – способ управления памятью, при котором образы процессов выгру- жаются на диск и возвращаются в оперативную память целиком.
Свопинг представляет собой частный, более простой в реализации, вариант виртуальной памяти, позволяющий совместно использовать оперативную память и диск.
Цель применения свопинга в ранних многозадачных операци- онных системах иллюстрирует рис.10.8. Если на компьютере одно- временно выполняется большое число вычислительных задач и за- дач с интенсивным вводом/выводом, то удается добиться высокой эффективности использования центрального процессора. Это проис- ходит за счет того, что в такой конфигурации на время выполнения ввода/вывода одной задачи процессор можно переключить на дру-
Номер виртуальной страницы P
Смещение S
Номер сегмента G
Таблица сегментов
Таблица страниц
G
Таблица страниц сегмента
P
Номер физической страницы P
’Смещение S
Номер физической страницы P
’
94 гую задачу. Так как положение участка насыщения на графике эф- фективности (рис.10.8) обычно находилось за пределами числа за- дач, которое можно было разместить в оперативной памяти, ожида- ющие завершения ввода/вывода задачи было целесообразно сбрасы- вать на диск.
Рис. 10.8. Повышение загрузки процессора при использовании свопинга
Кэш-память – способ организации совместной работы устройств хранения, различающихся стоимостью хранения единицы информации и скоростью доступа (рис.10.9). Цель применения кэш- памяти: увеличить скорость доступа и понизить стоимость хранения за счет размещения часто используемой информации в более быст- ром запоминающем устройстве. Механизм кэша, аналогично стра- ничному и сегментному способам управления памятью, прозрачен для пользователя.
Принцип работы кэша оперативной памяти заключается в сле- дующем (рис.10.10). Кэш одновременно с памятью «прослушивает» запрос центрального процессора, но если данные есть в самом кэше ответить успевает быстрее. Хранение информации в кэш-памяти ор- ганизуется по ассоциативному принципу. Ключом для доступа (те- гом) является адрес нескольких последовательно расположенных
100 %
Загрузка процессора
Число задач
С учетом свопинга
Только в ОЗУ
95
Рис. 10.9. К определению кэш-памяти ячеек. Последствия такой организации памяти для программиста: память разбивается на кэш-линии (несколько последовательных яче- ек, адресуемых одним тегом). Это приводит к тому, что в некоторых случаях для оптимизации скорости работы программ необходимо выполнять выравнивание данных по границе кэш-линии. Такая необходимость возникает, например, в случае возникновения эф- фекта ложного разделения (см. лекцию 7).
Рис. 10.10. Принцип работы кэш-памяти
Работа кэша основана на принципах пространственной и вре- менной локальности, обеспечивающих высокий процент «попада- ния» в кэш p. Это приводит к снижению среднего времени доступа к памяти: t доступа
=p·t кэш
+ (1-p)·t памяти
; p90%.
Кэш
Кэш
ВЗУ
ОЗУ
Регистры
Стоимость хранения
Скорость доступа
Тег (адрес)
Данные
Атрибуты
ЦП
Кэш
Память
«Медленный» ответ
«Быстрый» ответ
Адресная шина
96
Пространственная локальность – если в некоторый момент времени t происходит обращение по адресу A , то с большой долей вероятности в момент времени t+1 происходит обращение по адресу
А±1.
Временная локальность – если в некоторый момент времени t произошло обращение по адресу A, то существует большая вероят- ность того, что в течение некоторого временного интервала (t, t+τ] снова произойдет обращение по адресу А.
Лекция 11. Средства аппаратной поддержки
управления памятью в архитектуре x86_32
Режимы работы микропроцессора x86_32. Сегментный механизм, структуры данных, схема преобразования виртуального адреса.
Страничный механизм, структуры данных, схемы преобразования адреса. Средства вызова подпрограмм и задач.
Режимы работы микропроцессора i386. Общие принципы управления памятью с использованием внешней памяти представ- лены в лекции 10. Рассмотрим конкретный пример управления па- мятью в 32-разрядной архитектуре микропроцессоров семейства
Intel x86. Изложение ведется на примере микропроцессора i386.
Старшие модели 32 разрядных процессоров Intel имеют сходную архитектуру.
Микропроцессор i386 имеет два режима работы: реальный (re- al mode) и защищенный (protected mode). В защищенном режиме доступны сегментный и страничный механизмы виртуальной памя- ти. В реальном режиме процессор работает как 16-разрядный про- цессор 8086, но с расширенным набором команд. Размер адресуемо- го пространства в данном режиме составляет 1 Мб. Для работы в адресном пространстве 1Мб надо сформировать адрес определен- ным образом, как показано на рис. 11.1.
97
Рис. 11.1. Формирование адреса в реальном режиме
Реальный режим устанавливается по сбросу и используется для начальной инициализации системы. Путем записи управляющих битов в регистры командой MOV процессор переводится в защи- щенный режим. В защищенном режиме всегда включен сегментный механизм и может быть установлен режим v86 (virtual 86), при кото- ром процессор работает как несколько процессоров 8086 с общей памятью. Кроме того, в защищенном режиме может быть включен режим страничной адресации.
Сегментный механизм. В сегментном механизме управления памятью используются следующие структуры данных. Селектор – это структура данных, которая служит для выбора записи в глобаль- ной или локальной дескрипторной таблице (рис.11.2). Селекторы хранятся в сегментных регистрах и в некоторых типах записей внут- ри самих дескрипторных таблиц. Дескрипторные таблицы – это ана- лог таблицы сегментов (см. лекцию 10). Однако на практике кроме описания сегментов в них содержится дополнительная информация.
Рис. 11.2. Селектор
GDT – глобальная дескрипторная таблица
LDT – локальная дескрипторная таблица
98
Регистр GDTR описывает положение глобальной дескриптор- ной таблицы в физической памяти (рис.11.3). В нем также указыва- ется размер таблицы в байтах. Поскольку в сегментном регистре на указание индекса дескриптора сегмента отводится 13 бит, всего сег- ментов 2 13
= 8192.
Рис. 11.3. Регистр GDTR
Формат дескриптора сегмента данных и кода показан на рис.11.4.
Размер дескриптора 8 байт; с учетом 8192 возможных сегментов размер дескрипторной таблицы составит 8·8192 = 2 16
= 64 Кб. Бит G определяет способ изменения размера сегмента (в байтах – G=0, или в страницах – G=1). Если G=0, то размер сегмента 2 20
= 1 Мб (совме- стимость с 8086, используется в режиме v86). Если G=1, то при 4Кб страницах, 4Кб·2 20
= 4 Гб.
Рис. 11.4. Дескриптор сегмента данных и кода
16
База GDT в физи- ческой памяти
Размер (в байтах)
32
99
Бит D определяет выравнивание сегментов по 32-битной (D=1) или 16-битной границе (D=0).
Бит P – бит присутствия сегмента в физической памяти. Если он не установлен, то сегмент выгружен на диск. Обращение к сег- менту невозможно и приводит к прерыванию.
Биты DPL определяют уровень привилегий дескриптора, то есть возможность обращения к сегменту с данным уровнем приви- легий задачи. Если CPL≤DPL – доступ разрешен, иначе возникает прерывание.
Тип сегментов определяет бит S. Если S=0, то данный де- скриптор описывает системный сегмент или имеет специальное назначение. К системным сегментам, например, относятся LDT – локальная дескрипторная таблица, TSS – сегмент состояния задачи, в который отображается содержимое контекста при переключении задач. Дескрипторы специального назначения – ловушки (шлюзы) вызова, предназначенные для межсегментного вызова с повышени- ем уровня привилегий.
Пользовательские сегменты имеют бит S=1. К пользователь- ским сегментам относятся сегменты данных E=0 и сегменты кода
Е=1. В пользовательских сегментах имеются следующие управляю- щие биты. Бит ED – бит распространения сегмента. Если ED=0 сег- мент распространяется в сторону старших адресов, если ED=1 – в сторону младших адресов. В сторону младших адресов распростра- няются сегменты стека. Бит W – бит разрешения записи в сегмент.
Бит А – бит доступа к сегменту. Если А=1 – произошел доступ к сегменту. Анализ этого бита позволяет оценить интенсивность об- ращений к сегменту для выбора наименее используемого сегмента с целью вытеснения его на диск. Бит С – бит подчинения. Если C=1, то проверка CPL≤DPL игнорируется и можно вызвать более приви- легированный сегмент кода, чем тот сегмент кода, из которого вы- полняется вызов. Наконец, бит R используется для указания на воз- можность чтения кодового сегмента.
100
Рис. 11.5. Схема обращения к сегментам кода и данных
Рассмотрим схему обращения к сегментам кода и данных при использовании глобальных и локальных дескрипторных таб- лиц (рис. 11.5). Если используется адресация из таблицы GDT, то индекс сдвигается влево на 3 разряда, так как дескриптор имеет размер 8 б = 2 3
. Получается смещение в таблице GDT. Далее прове- ряется, не выходит ли смещение за границы таблицы. Для этого ана- лизируются младшие 16 разрядов GDTR, хранящих ее размер. Далее берется 32-битный адрес GDT и складывается с этим смещением. В итоге получается 32-битный адрес дескриптора в физической памя- ти. При этом определяется, присутствует ли сегмент в физической памяти и разрешен ли доступ к нему. Если доступ разрешен, то бе- рется базовый адрес сегмента из дескриптора (база) и складывается со смещением из команды. Также на этой стадии производится кон- троль выхода за границу сегмента. Результатом является 32-битный адрес в физической памяти.
Если обращение идет через локальную дескрипторную табли- цу LDT (см. соответствующий признак в селекторе), то используется
101 регистр LDTR, который указывает на дескриптор LDT в глобальной дескрипторной таблице GDT. С использованием этого дескриптора вычисляется базовый адрес LDT в физической памяти. Далее преоб- разование происходит аналогичным способом.
Для увеличения скорости преобразования адреса каждому из шести сегментных регистров соответствует теневой 8-байтный ре- гистр,
хранящий дескриптор, соответствующий значению сегмент- ного регистра.
Таким образом, для инициализации системы в защищенном режиме необходимо как минимум создать дескрипторную таблицу с одним входом и проинициализировать GDTR.
Если включен страничный механизм, то вычисленный 32- битный адрес подвергается дальнейшему преобразованию блоком управления страничной памятью.
Скачать 2.09 Mb.