Модель преобразования виртуального адреса в физический
БАЛТИЙСКАЯ ГОСУДАРСТВЕННАЯ АКАДЕМИЯ
РЫБОПРОМЫСЛОВОГО ФЛОТА
Курсовая работа по операционным
системам
на тему «Модель преобразования
виртуального адреса в физический»
Вариант №5
Выполнил:
Студент
группы 10АСУС(404)
Лубнин А.В
Приняла:
Костромина
И.Г.________________
Калининград 2013
ОГЛАВЛЕНИЕ
Введение
. Основания для разработки
.1 Исходные данные и результаты работы
. Методы распределения виртуальной памяти
.1 Страничная и сегментная организации виртуальной памяти
.2 Сегментно-страничная организация виртуальной памяти
. Преобразование виртуального адреса в физический
.1 Модель оперативной памяти
.2 Алгоритм преобразования виртуального адреса в физический
. Контрольные примеры
Введение
Виртуа́льная па́мять (англ. Virtual memory) - технология
управления памятью ЭВМ, разработанная для многозадачных операционных систем.
При использовании данной технологии для каждой программы используются
независимые схемы адресации памяти, отображающиеся тем или иным способом на
физические адреса в памяти ЭВМ. Позволяет увеличить эффективность использования
памяти несколькими одновременно работающими программами, организовав множество
независимых адресных пространств, и обеспечить защиту памяти между разными
приложениями. Также позволяет программисту использовать больше памяти, чем
установлено в компьютере, за счет откачки неиспользуемых страниц на вторичное
хранилище
При использовании виртуальной памяти упрощается программирование, так как
программисту больше не нужно учитывать ограниченность памяти, или согласовывать
использование памяти с другими приложениями. Для программы выглядит доступным и
непрерывным все допустимое адресное пространство, вне зависимости от наличия в
ЭВМ соответствующего объема ОЗУ.
Применение механизма виртуальной памяти позволяет:
- упростить адресацию памяти клиентским программным
обеспечением;
- рационально управлять оперативной памятью компьютера (хранить
в ней только активно используемые области памяти);
- изолировать процессы друг от друга (процесс полагает, что
монопольно владеет всей памятью).
В настоящее время эта технология имеет аппаратную поддержку на всех
современных бытовых процессорах. В то же время во встраиваемых системах и в
системах специального назначения, где требуется либо очень быстрая работа, либо
есть ограничения на длительность отклика (системы реального времени),
виртуальная память используется относительно редко. Также в таких системах реже
встречается многозадачность и сложные иерархии памяти.
1. Основания для разработки
.1 Исходные данные и результаты работы
Исходные данные для выполнения курсовой работы:
- организация виртуальной памяти - сегментно-страничная;
- разрядность виртуального адреса - 32;
- количество сегментов не более 16;
- размер физической страницы - 4 Кбайт;
- объем оперативной памяти - 256 физических страниц;
- количество физических страниц в таблице страниц процесса - не
более 32;
- виртуальный адрес вводится с клавиатуры.
Результаты выполнения модели должны включать в себя:
- виртуальный адрес;
- физический адрес;
- содержимое таблицы сегментов и таблицы страниц.
2. Методы распределения виртуальной памяти
.1 Страничная и сегментная организации
виртуальной памяти
виртуальный память программный распределение
В большинстве современных операционных систем виртуальная память
организуется с помощью страничной адресации. Оперативная память делится на
страницы: области памяти фиксированной длины (например, 4096 байт), которые
являются минимальной единицей выделяемой памяти (то есть даже запрос на 1 байт
от приложения приведёт к выделению ему страницы памяти). Процесс обращается к
памяти с помощью адреса виртуальной памяти, который содержит в себе номер
страницы и смещение внутри страницы. Процессор преобразует номер виртуальной
страницы в адрес соответствующей ей физической страницы при помощи буфера
ассоциативной трансляции.
Если страница выгружена из оперативной памяти, то операционная система
подкачивает страницу с жёсткого диска. При запросе на выделение памяти
операционная система может «сбросить» на жёсткий диск страницы, к которым давно
не было обращений. Критические данные (например, код запущенных и работающих
программ, код и память ядра системы) обычно находятся в оперативной памяти
(исключения существуют, однако они не касаются тех частей, которые отвечают за
обработку аппаратных прерываний, работу с таблицей страниц и использование
файла подкачки).
Второй принцип организации виртуальной памяти, при котором виртуальное
пространство делится на части произвольного размера - сегменты - сегментный.
Этот механизм позволяет, к примеру, разбить данные процесса на логические
блоки. Для каждого сегмента, как и для страницы, могут быть назначены права
доступа к нему пользователя и его процессов. При загрузке процесса часть
сегментов помещается в оперативную память (при этом для каждого из этих сегментов
операционная система подыскивает подходящий участок свободной памяти), а часть
сегментов размещается в дисковой памяти.
Сегменты одной программы могут занимать в оперативной памяти несмежные
участки. Во время загрузки система создает таблицу сегментов процесса
(аналогичную таблице страниц), в которой для каждого сегмента указывается
начальный физический адрес сегмента в оперативной памяти, размер сегмента,
правила доступа, признак модификации, признак обращения к данному сегменту за
последний интервал времени и некоторая другая информация. Система с сегментной
организацией функционирует аналогично системе со страничной организацией: время
от времени происходят прерывания, связанные с отсутствием нужных сегментов в
памяти, при необходимости освобождения памяти некоторые сегменты выгружаются,
при каждом обращении к оперативной памяти выполняется преобразование
виртуального адреса в физический. Кроме того, при обращении к памяти
проверяется, разрешен ли доступ требуемого типа к данному сегменту. Недостатком
данного метода распределения памяти является фрагментация на уровне сегментов и
более медленное по сравнению со страничной организацией преобразование адреса.
Более подробная информация о сегментном и страничном методах
распределения памяти дана в приложениях 1 и 2 соответственно.
2.2 Сегментно-страничная организация виртуальной
памяти
Как и в сегментном способе распределения памяти, программа разбивается на
логически законченные части - сегменты - и виртуальный адрес содержит указание
на номер соответствующего сегмента. Вторая составляющая виртуального адреса -
смещение относительно начала сегмента - в свою очередь, может состоять из двух
полей: виртуальной страницы и индекса. Другими словами, получается, что
виртуальный адрес теперь состоит из трех компонентов: сегмент, страница,
индекс. Получение физического адреса и извлечение из памяти необходимого
элемента для этого способа представлено на рисунке 1.
Из рисунка сразу видно, что этот способ организации виртуальной памяти
вносит ещё большую задержку доступа к памяти. Необходимо сначала вычислить
адрес дескриптора сегмента и прочитать его, затем вычислить адрес элемента
таблицы страниц этого сегмента и извлечь из памяти необходимый элемент, и уже
только после этого можно к номеру физической страницы приписать номер ячейки в
странице (индекс). Задержка доступа к искомой ячейке получается по крайней мере
в три раза больше, чем при простой прямой адресации. Чтобы избежать этой
неприятности, вводится кэширование, причем кэш, как правило, строится по
ассоциативному принципу. Другими словами, просмотры двух таблиц в памяти могут
быть заменены одним обращением к ассоциативной памяти.
Принцип действия ассоциативного запоминающего устройства предполагает,
что каждой ячейке памяти такого устройства ставится в соответствие ячейка, в
которой записывается некий ключ (признак, адрес), позволяющий однозначно
идентифицировать содержимое ячейки памяти. Сопутствующую ячейку с информацией,
позволяющей идентифицировать основные данные, обычно называют полем тега.
Просмотр полей тега всех ячеек ассоциативного устройства памяти осуществляется
одновременно, то есть в каждой ячейке тега есть необходимая логика, позволяющая
посредством побитовой конъюнкции найти данные по их признаку за одно обращение
к памяти (если они там, конечно, присутствуют).
Рисунок 1 - Принцип получения физического адреса при сегментно-страничной
организации виртуальной памяти
Часто поле тегов называют аргументом, а поле с данными - функцией. В
качестве аргумента при доступе к ассоциативной памяти выступают номер сегмента
и номер виртуальной страницы, а в качестве функции от этих аргументов получаем
номер физической страницы. Остается приписать номер ячейки в странице к
полученному номеру, и мы получаем искомую команду или операнд.
Оценивая достоинства сегментно-страничного способа, можно выделить
следующее. Разбиение программы на сегменты позволяет размещать сегменты в
памяти целиком. Сегменты разбиты на страницы, все страницы сегмента загружаются
в память. Это позволяет уменьшить обращения к отсутствующим страницам,
поскольку вероятность выхода за пределы сегмента меньше вероятности выхода за
пределы страницы. Страницы исполняемого сегмента находятся в памяти, но при
этом они могут находиться не рядом друг с другом, а «россыпью», поскольку
диспетчер памяти манипулирует страницами. Наличие сегментов облегчает
реализацию разделения программных модулей между параллельными процессами.
Возможна и динамическая компоновка задачи. А выделение памяти страницами
позволяет минимизировать фрагментацию.
Однако, поскольку этот способ распределения памяти требует очень
значительных затрат вычислительных ресурсов и его не так просто реализовать,
используется он редко, причем в дорогих, мощных вычислительных системах.
Возможность реализовать сегментно-страничное распределение памяти заложена и в
семейство микропроцессоров x86, однако вследствие слабой аппаратной поддержки,
трудностей при создании систем программирования и операционной системы,
практически он не используется в ПК.
3. Преобразование виртуального адреса в
физический
.1 Модель оперативной памяти
Чтобы описать алгоритм преобразования виртуального адреса в физический,
сначала необходимо разобраться с параметрами памяти и создать ее модель.
Сделать это можно на основе предоставленных исходных данных.
Объем оперативной памяти равен 256 физическим страницам, каждая из
которых фиксированного размера в 4 килобайта. То есть общий объем
предоставленной памяти равен 1 Мб. Он разбит на 16 сегментов, каждый из которых
может содержать до 32 страниц. Для удобства сделаем модель, которая будет
содержать сегменты различных размеров: 8 сегментов по 8 страниц, 4 сегмента по
16 страниц, и 4 по 32 страницы.
Так как разрядность виртуального адреса - 32 бита, то каждая страница
может содержать только 1024 адреса. Каждый адрес хранит в себе номер сегмента,
номер виртуальной страницы и смещение. Первые десять бит отвечают за сегменты,
следующие десять - за страницы, и оставшиеся двенадцать бит определяют смещение
внутри страницы. Нумерация сегментов, страниц и смещения начинается всегда с
нуля.
Таким образом, модель памяти можно представить следующей схемой.
Схема 1 - Модель оперативной памяти
3.2 Алгоритм преобразования виртуального адреса
в физический
Каждый виртуальный адрес представляет собой число, закодированное в
шестнадцатеричной системе исчисления. Для того чтобы из этого числа получить
необходимый физический адрес, надо выполнить следующие действия:
- шестнадцатеричное число преобразовать в бинарный код;
- по вторым десяти разрядам в таблице виртуальных страниц
данного сегмента найти ту страницу, которая содержит номер физической страницы;
- оставшиеся двенадцать разрядов дают смещение в физической
странице;
- объединив номер страницы и смещение, получим искомый
физический адрес.
Данный алгоритм наглядно представлен на рисунке 4.
Рисунок 4 - Алгоритм преобразования виртуального адреса в физический при
сегментно-страничной организации памяти
Изобразить этот же алгоритм преобразования с помощью блок-схемы можно
следующим образом:
Схема 2 - Алгоритм преобразования виртуального адреса в физический
4. Контрольные примеры
Для того чтобы наглядно представить, как работает данный алгоритм
преобразования адресов, необходимо привести несколько контрольных примеров с
числовыми значениями. В таблице 1 представлена часть имеющихся сегментов,
которые рассматриваются в курсовой работе. Таблица 2 содержит в себе некоторые
из виртуальных страниц, через которые находится физический адрес. Рассмотрим
три примера преобразования виртуального адреса в физический: когда существует
сегмент и в нем виртуальная страница; когда существует сегмент, но в нем
отсутствует виртуальная страница; когда отсутствует запрашиваемый сегмент.
Таблица 1 - Таблица сегментов
Адрес сегмента памяти
|
Адрес виртуальной страницы
в сегменте
|
0000001111
|
0000011100
|
0000000011
|
0000000111
|
0000001010
|
0000011010
|
0000000110
|
0000001110
|
Таблица 2 - Таблица страниц
Адрес виртуальной страницы
|
Адрес физической страницы
|
0000011100
|
0000100110
|
0000001101
|
0000011001
|
0000011001
|
0001001110
|
0000000111
|
0000010111
|
0000001110
|
0000110011
|
0000010011
|
0000001001
|
0000011010
|
0000010001
|
0000000001
|
0001001101
|
Пример 1
1. Возьмем произвольный виртуальный адрес - число в шестнадцатеричной
системе исчисления, например, «F1С250».
Следуя алгоритму, преобразуем данный адрес в бинарный код
«00000011110000011100100101000000».
2. Следующим шагом будет поиск сегмента памяти с адресом
«0000001111». Проверим, имеется ли этот сегмент: «0000001111» в десятичной
системе исчисления равно 15, следовательно, такой сегмент имеется.
. Дальше, в этом сегменте найдем виртуальную страницу, хранящую
адрес физической страницы. Следующие десять бит дают номер искомой страницы -
«0000011100». Так же проверяем, имеется ли эта страница: в десятичной системе
число «0000011100» равно 28. Это тоже удовлетворят требованиям работы.
. Последним шагом преобразования будет получение физического
адреса путем добавления смещения, равного «100101000000», к адресу физической
страницы, который был получен предыдущим действием.
. В полученной виртуальной странице хранился физический адрес
«0000100110». Добавляя к нему смещение «100101000000» получается, что
физический адрес равен «0000100110100101000000» или «26940» в шестнадцатеричной
системе исчисления.
Пример 2
1. Возьмем другой произвольный виртуальный адрес - число в
шестнадцатеричной системе исчисления, например, «A66976». Следуя алгоритму, преобразуем данный адрес в бинарный
код «000000101000011001100100101110100».
. Следующим шагом будет поиск сегмента памяти с адресом «0000001010».
Проверим, имеется ли этот сегмент: «0000001010» в десятичной системе исчисления
равно 10, следовательно, такой сегмент имеется.
3. Дальше, в этом сегменте найдем виртуальную страницу, хранящую
адрес физической страницы. Следующие десять бит дают номер искомой страницы -
«0001100110». Так же проверяем, имеется ли эта страница: в десятичной системе
число «0001100110» равно 102. Эта страница либо находится за пределами
рассматриваемой области памяти, либо отсутствует вовсе. Следовательно,
дальнейшее преобразование адреса невозможно.
Пример 3
1. Возьмем еще один произвольный виртуальный адрес - число в шестнадцатеричной
системе исчисления, например, «A66976».
Следуя алгоритму, преобразуем данный адрес в бинарный код
«00001000101101101100010010100101».
. Следующим шагом будет поиск сегмента памяти с адресом «0000100010».
Проверим, имеется ли этот сегмент: «0000100010» в десятичной системе исчисления
равно 34. Номер данного сегмента не удовлетворяет условиям курсовой работы.
Сегмента с таким номером не существует, а значит и преобразование виртуального
адреса не возможно.