Группа заданий №3. Моделирование механизмов виртуальной памяти.

Цель работы:

Ознакомление с организацией разрывного размещения задачи в ОП.

Теоретические сведения

1. Управление памятью

Память – важнейший ресурс, разделяемый. Нужно обеспечить, чтобы:

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

в памяти находилось достаточно много задач (чтобы в/в не вызывал простоя)

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

Память и отображения, виртуальное адресное пространство

Программист адресует память с помощью набора символических имён. Имена переменных и входных точек программы - пространство символьных имён(логическое, оно не упорядочено).

Реально программа выполняется в физической памяти, с которой работает ЦП на чтение/запись. Физическая память– упорядоченное множество ячеек реально существующей ОП, к каждой можно обратиться по её порядковому номеру. Число ячеек ограничено и фиксировано.

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

Обычно отображение выполняется в 2 этапа:

• 1-системой программирования,

• 2 – ОС. 2-е – с помощью аппаратных средств ЦП – подсистемы управления памятью.

Между этими этапами обращение к памяти выполняется в форме виртуального адреса (ВА). Множество всех виртуальных адресов для программы – её виртуальное адресное пространствоиливиртуальная память.

Адреса машинной программы (после системы программирования) – виртуальные. Эти адреса м. б. как двоичными, так и символьно-двоичными (иногда двоичные адреса не могут быть определены после трансляции и компоновки и становятся известными только при загрузке программы).

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

Другой полюс – тождество виртуальных и символьных адресов. Здесь отображение делает ОС, которая при выполнении использует таблицу символьных имён. Здесь надо выполнять отображение для каждого нового имени – долго. Такая схема - в интерпретаторах, где трансляция = исполнению. Напр. Бейсик.

Нормально/эффективно - Транслятор/компилятор выдаёт относительныеадреса (виртуальные) и данные оначальном адресе, а ЦП с помощью ОС делает 2-е отображение при каждом обращении к памяти.

Общая схема 2-этапного отображения – 3 ситуации соотношения виртуальной памяти программы и реальной физической памяти К:

Пв<Пф; (в 16-разр.миниЭВМ, сейчас нет,)

Пв=Пф; (бывает, в недорогих вычислительных комплексах – разные методы)

Пв>Пф; (типично)

Сегментная, страничная, сегментно-страничная организация памяти

Разрывная память – набор фрагментов. При этом уменьшается фрагментация, но растёт время доступа. Для адресации задаются адрес начала фрагмента и смещение от него. Т.о. ВА состоит из 2 частей.

Сегментный способ

Программа разбивается на логические части – сегменты – и каждому сегменту выделяется физическая память. Каждый программный модуль м.б. сегментом. Логически обращение к сегменту – имя сегмента и смещение от его начала. Физически имя соотв. адресу, с которого сегмент размещается в памяти. Преобразует имя сегмента в его номер система программирования. Для каждого сегмента она задаёт его объём – это нужно ОС.

ОС размещает сегменты в памяти и ведёт их учёт в Таблице задачи, адрес которой заносится в Регистр таблицы сегментов.

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

В памяти	Адрес начала	Длина	Права доступа
1	20100	2000	R-X

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

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

Сегментная организация позволяет размещать в памяти только нужные в данный момент сегменты. Поэтому Пв>Пф. Коэффициент мультипрограммирования увеличивается.

Но увеличить число задач можно только до определённого предела, т.к. когда в памяти не будет достаточно места, то производительность упадёт из-за частых операций обмена с внешней памятью (либо подкачать на свободное место, либо произвести своппинг).

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

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

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

Дисциплина замещенияпозволяет определить сегмент, который должен быть перемещён во внешнюю память, либо просто замещён:

1. FIFO (first in first out) –

2. LRU(leastrecentlyused) – дольше других неиспользуемый

3. LFU(leastfrequentlyused– реже других используемый

4. Random– случайный выбор

1-й и последний –наиболее простые, но не учитывают актуальность и диспетчер може выгрузить сегмент, который сразу потребуется. (вероятность). К тому же 1-е сегменты могут содержать общие переменные.

Для 2-й и 3-й ЦП должен иметь доп. Средства – для фиксации обращений.

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

Плюсы сегментной организации:

Размещать части программ в памяти по необходимости

Некоторые программные модули можно сделать разделяемыми между задачами

Минусы:

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

Время на локализацию ячейки. Здесь можно использовать кэширование– текущие дескрипторы могут быть размещены в сверхоперативной памяти (спец. регистры ЦП).

Сегментный способ применён в OS/2v.1.

Страничный способ

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

В некоторых ОС страницы выгружаются не в файл, а в спец. раздел на диске. (UNIX)

Такое разбиение ОП – даёт двумерное адресное пространство:

1-я координата адресного пространства – номер страницы

2-я – номер ячейки внутри страницы – индекс

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

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

Для каждой задачи строится Таблица страниц, нужная для отображения адресных пространств. Дескриптор для каждой страницы – не имеет размера страницы (в отличие от сегментной организации).

Бит присутствия

Номер физической страницы или адрес на диске

Права доступа

Принцип формирования адреса - как в сегментной организации.

Защитастраничной памяти также основана на уровне доступа к каждой странице.

Возможны такие уровни доступа:

1. Только чтение

2. Чтение и запись

3. Только выполнение

При отображении адресов коды доступа сравниваются с запросом, при несовпадении – прерывание.

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

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

Большинство ОС используют дисциплину замещения LRU(OS/2 иLinux) но вWindowsиспользуетсяFIFO, для независимости от аппаратных возможностей ЦП. Для компенсации недостатковFIFOбыла введена «буферизация» страниц, которые должны писаться в файл подкачки. Принцип буферизации: перед выгрузкой страница помечается как кандидат на выгрузку, и если в следующий раз к ней придёт обращение, она не выгружается, а уходит в коней списка. Буфер невелик, поэтому часты пробуксовки.

Для ускорения при страничной организации используется кэширование страничных дескрипторов.– для 8086 на 32 страничных дескриптора. Т.к. размер страницы 4 К. то есть быстрое обращение к 128кб.

Плюс – малая фрагментация.

Минус – время на формирование адреса, а главное – программа разбивается на страницы без учёта логики, поэтому межстраничные перходы более часты, чем в сегментах.

Сегментно-страничный способ.

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

Итоги:

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

Минусы: метод сложный, трудно реализовать, долгий, поэтому используется редко, только в дорогих мощных вычислительных комплексах. Эта возможность заложена в архитектуре 8086, но не используется.

Задание:

1. Разработать 2 рабочих процесса, имитирующих обработку некоторой информации с обращением к сегментированному массиву данных.

2. Реализовать диспетчер памяти с сегментным или страничным способом размещения в памяти с имитацией нехватки физического пространства для размещения всего массива.

3. Разработать модуль подкачки с визуализацией процесса подкачки страниц или сегментов.

4. В качестве стратегии размещения и замещения выбрать 1 из следующих вариантов:

а) стратегии размещения (только для сегментов)поиск свободного места в ОП для подгрузки нового сегмента

1. - первый подходящий

2. - наиболее подходящий

3. - наименее подходящий

б) стратегия замещения сегментов и страниц выборка кандидатов на выгрузку (замещение)

1. - первый попавшийся

2. - тот, к которому меньше всего обращались

3. - тот, который только что исполнился

4. - тот, который давно не исполнялся

Номер варианта

С т р а т е г и я з а м е щ е н и я

С т р а т е г и я р а з м е щ е н и я	1	2	3	4
1	14	15	16	17
2	18	19	20	21
3	22	23	24	25

Требования к реализации:

1. Структура программы:

2 рабочих модуля, диспетчер памяти, модуль подкачки.

2. Сымитировать ситуацию нехватки физической памяти.

3. Разработать способ обращения к виртуальному адресу без сканирования всего виртуального адресного пространства.

4. Четко проработать механизм определения физического адреса по виртуальному.

5. Разработать структуру, имитирующую таблицу дескрипторов сегментов (сначала обосновать, а потом разработать).

Требования к пояснительной записке:

• Описание методов управления памятью в операционных системах

• Постановка задачи

• Обоснование выбора метода решения

• Описание процессов, используемых в курсовой работе

• блок-схема диспетчера памяти

• описание структуры, имитирующей таблицу дескрипторов сегментов с обоснованием ее структуры.

• описание способов обращения к виртуальному адресу, без сканирования своего адресного пространства

• формула вычисления виртуального адреса и алгоритм преобразования А_вирт–> А_физ

• Интерпретация результатов

• Список используемой литературы

Вопросы к защите:

1. Иерархия памяти, управление памятью. Типы адресов.

2. Общая классификация методов распределения памяти. Метод размещения с динамически перемещаемыми разделами.

3. Методы распределения памяти с использованием дискового пространства. Техника раеализации, достоинства и недостатки. Свопинг.