Модель преобразования виртуального адреса в физический

БАЛТИЙСКАЯ ГОСУДАРСТВЕННАЯ АКАДЕМИЯ

РЫБОПРОМЫСЛОВОГО ФЛОТА

Курсовая работа по операционным системам

на тему «Модель преобразования виртуального адреса в физический»

Вариант № 5

Выполнил:

Студент группы 10АСУС (404)

Лубнин А. В

Приняла:

Костромина И.Г.________________

Калининград 2013

1. Основания для разработки

1.1 Исходные данные и результаты работы

2. Методы распределения виртуальной памяти

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

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

3. Преобразование виртуального адреса в физический

3.1 Модель оперативной памяти

3.2 Алгоритм преобразования виртуального адреса в физический

4. Контрольные примеры

Введение

Виртуамльная паммять (англ. Virtual memory) — технология управления памятью ЭВМ, разработанная для многозадачных операционных систем. При использовании данной технологии для каждой программы используются независимые схемы адресации памяти, отображающиеся тем или иным способом на физические адреса в памяти ЭВМ. Позволяет увеличить эффективность использования памяти несколькими одновременно работающими программами, организовав множество независимых адресных пространств, и обеспечить защиту памяти между разными приложениями. Также позволяет программисту использовать больше памяти, чем установлено в компьютере, за счет откачки неиспользуемых страниц на вторичное хранилище При использовании виртуальной памяти упрощается программирование, так как программисту больше не нужно учитывать ограниченность памяти, или согласовывать использование памяти с другими приложениями. Для программы выглядит доступным и непрерывным все допустимое адресное пространство, вне зависимости от наличия в ЭВМ соответствующего объема ОЗУ.

Применение механизма виртуальной памяти позволяет:

— упростить адресацию памяти клиентским программным обеспечением;

— рационально управлять оперативной памятью компьютера (хранить в ней только активно используемые области памяти);

— изолировать процессы друг от друга (процесс полагает, что монопольно владеет всей памятью).

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

1. Основания для разработки

1.1 Исходные данные и результаты работы Исходные данные для выполнения курсовой работы:

— организация виртуальной памяти — сегментно-страничная;

— разрядность виртуального адреса — 32;

— количество сегментов не более 16;

— размер физической страницы — 4 Кбайт;

— объем оперативной памяти — 256 физических страниц;

— количество физических страниц в таблице страниц процесса — не более 32;

— виртуальный адрес вводится с клавиатуры.

Результаты выполнения модели должны включать в себя:

— виртуальный адрес;

— физический адрес;

— содержимое таблицы сегментов и таблицы страниц.

2. Методы распределения виртуальной памяти

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

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

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

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

Более подробная информация о сегментном и страничном методах распределения памяти дана в приложениях 1 и 2 соответственно.

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

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

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

Рисунок 1 — Принцип получения физического адреса при сегментно-страничной организации виртуальной памяти Часто поле тегов называют аргументом, а поле с данными — функцией. В качестве аргумента при доступе к ассоциативной памяти выступают номер сегмента и номер виртуальной страницы, а в качестве функции от этих аргументов получаем номер физической страницы. Остается приписать номер ячейки в странице к полученному номеру, и мы получаем искомую команду или операнд.

Оценивая достоинства сегментно-страничного способа, можно выделить следующее. Разбиение программы на сегменты позволяет размещать сегменты в памяти целиком. Сегменты разбиты на страницы, все страницы сегмента загружаются в память. Это позволяет уменьшить обращения к отсутствующим страницам, поскольку вероятность выхода за пределы сегмента меньше вероятности выхода за пределы страницы. Страницы исполняемого сегмента находятся в памяти, но при этом они могут находиться не рядом друг с другом, а «россыпью», поскольку диспетчер памяти манипулирует страницами. Наличие сегментов облегчает реализацию разделения программных модулей между параллельными процессами. Возможна и динамическая компоновка задачи. А выделение памяти страницами позволяет минимизировать фрагментацию.

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

3. Преобразование виртуального адреса в физический

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 — Таблица сегментов

Таблица 2 — Таблица страниц

Пример 1

1. Возьмем произвольный виртуальный адрес — число в шестнадцатеричной системе исчисления, например, «F1С250». Следуя алгоритму, преобразуем данный адрес в бинарный код «11 110 000 011 100 099 979 509 760».

2. Следующим шагом будет поиск сегмента памяти с адресом «1 111». Проверим, имеется ли этот сегмент: «1 111» в десятичной системе исчисления равно 15, следовательно, такой сегмент имеется.

3. Дальше, в этом сегменте найдем виртуальную страницу, хранящую адрес физической страницы. Следующие десять бит дают номер искомой страницы — «11 100». Так же проверяем, имеется ли эта страница: в десятичной системе число «11 100» равно 28. Это тоже удовлетворят требованиям работы.

4. Последним шагом преобразования будет получение физического адреса путем добавления смещения, равного «100 101 000 000», к адресу физической страницы, который был получен предыдущим действием.

5. В полученной виртуальной странице хранился физический адрес «100 110». Добавляя к нему смещение «100 101 000 000» получается, что физический адрес равен «100 110 100 101 000 000» или «26 940» в шестнадцатеричной системе исчисления.

Пример 2

1. Возьмем другой произвольный виртуальный адрес — число в шестнадцатеричной системе исчисления, например, «A66976». Следуя алгоритму, преобразуем данный адрес в бинарный код «101 000 011 001 100 092 684 894 208».

2. Следующим шагом будет поиск сегмента памяти с адресом «1 010». Проверим, имеется ли этот сегмент: «1 010» в десятичной системе исчисления равно 10, следовательно, такой сегмент имеется.

3. Дальше, в этом сегменте найдем виртуальную страницу, хранящую адрес физической страницы. Следующие десять бит дают номер искомой страницы — «1 100 110». Так же проверяем, имеется ли эта страница: в десятичной системе число «1 100 110» равно 102. Эта страница либо находится за пределами рассматриваемой области памяти, либо отсутствует вовсе. Следовательно, дальнейшее преобразование адреса невозможно.

Пример 3

1. Возьмем еще один произвольный виртуальный адрес — число в шестнадцатеричной системе исчисления, например, «A66976». Следуя алгоритму, преобразуем данный адрес в бинарный код «1 000 101 101 101 100 030 696 095 744».

2. Следующим шагом будет поиск сегмента памяти с адресом «100 010». Проверим, имеется ли этот сегмент: «100 010» в десятичной системе исчисления равно 34. Номер данного сегмента не удовлетворяет условиям курсовой работы. Сегмента с таким номером не существует, а значит и преобразование виртуального адреса не возможно.