Понятие операционной системы; эволюция развития операционных систем; функции операционных систем и подходы к построению операционных систем



страница7/15
Дата14.04.2017
Размер0.56 Mb.
Просмотров4429
Скачиваний3
1   2   3   4   5   6   7   8   9   10   ...   15

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


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

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



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

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

  • Объем ввода-вывода для выгрузки части программы на диск может быть меньше, чем в варианте классического свопинга, в итоге каждая программа будет работать быстрее.

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

Архитектурные средства поддержки виртуальной памяти делятся на сегментные, страничные и сегментно-страничные распределения памяти.

Сегментный

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

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

img00019

Логически обращение к элементам программы в этом случае будет состоять из имени сегмента и смещения относительно начала этого сегмента.

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


При размещении каждого из сегментов в оперативной или внешней памяти ОС отмечает в дескрипторе текущее местоположение сегмента.

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

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

Поэтому:


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

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

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

FIFO (First In First Out) первый пришёл – первый ушёл

LRU (Least Recently Used ) не используемый дольше других

LFU (Least Frequently Used) используемый реже других

Random-случайный выбор сегмента

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

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

Место во внешней памяти называют файлом подкачки, или страничным файлом(paging file). Иногда это файл называют swap – файлом, тем самым подчеркивая, что записи этого файла – страницы – замещают друг друга в ОП

img00017.gif

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

Таким образом, физический адрес определяется парой (Рр, i), а виртуальный адрес – парой (Pv, i), где Pv – номер виртуальной страницы, Рр – номер физической страницы, i – индекс ячейки внутри страницы

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

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

Однако в ОС Windows NT/2000/XP разработчики, желая сделать их максимально независимыми от аппаратных возможностей процессора, отказались от этой дисциплины и применили правило FIFO. Поэтому, чтобы компенсировать ее неэффективность была введена «буферизация» тех страниц, которые должны быть записаны в файл подкачки на диск или просто расформированы. Принцип буферизации следующий: прежде чем замещаемая страница действительно окажется во внешней памяти или просто расформированной, она помечается как «кандидат на выгрузку».

Если в следующий раз произойдет обращение к странице, находящейся в таком «буфере», то страница никуда не выгружается и уходит в конец списка FIFO

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

Величина «буфера» не может быть большой, поэтому эффективность страничной реализации памяти в Windows NT/2000/XP намного ниже, чем в других ОС, и явление пробуксовки проявляется даже при относительно большом объеме ОП

Структура таблицы страниц

Многоуровневые таблицы страниц

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

В 32-битном адресном пространстве при размере страницы 4 Кбайт (Intel) получаем 232/212=220, то есть приблизительно 106 страниц – таблица должна иметь примерно 106 строк, а запись в строке состоит из нескольких байтов. Каждый процесс нуждается в своей таблице страниц.

Для того чтобы избежать размещения в памяти огромной таблицы, ее разбивают на ряд фрагментов.

В ОП хранят лишь некоторые, необходимые для конкретного момента исполнения фрагмента таблицы страниц.

В силу свойства локальности число таких фрагментов относительно невелико.



Локальность – способность в течение ограниченного отрезка времени работать с небольшим набором адресов памяти.

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

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


При помощи одной таблицы второго уровня можно охватить 4Мбайт ОП. Для размещения процесса с большим объемом занимаемой памяти достаточно иметь в ОП одну таблицу первого уровня и несколько таблиц второго уровня. Очевидно, что суммарное количество строк в этих таблицах много меньше 220.

Количество уровней в таблице страниц зависит от конкретных особенностей архитектуры.

Примером реализации одноуровневого (DEC PDP-11), двухуровневого (Intel, DEC VAX), трехуровневого (Sun SPARC, DEC Alpha) пейджинга, а также пейджинга с заданным количеством уровней (Motorola).

Инвертированная таблица страниц

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

Например, для Pentium с 256 Мбайт ОП нужна таблица размером 64 Кбайт строк.

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

Один из способов решения данной проблемы – использование хеш-таблицы виртуальных адресов.

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



Инвертированная таблица страниц

Каждой странице физической памяти соответствует одна запись в хеш-таблице и инвертированной таблице страниц.

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

Ассоциативная память

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

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

Это устройство называют ассоциативной памятью или буфером поиска трансляции (translation lookaside buffer - TLB).

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

Общая схема функционирования

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

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

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

Число удачных поисков номера страницы в ассоциативной памяти по отношению к общему числу поисков называется hit ratio («процент попаданий в кэш»).

Обращение к одним и тем же страницам повышает hit ratio (чем больше hit ratio, тем меньше среднее время доступа к данным, находящимся в ОП).



Пример: Если для доступа к памяти через таблицу страниц необходимо 100 нс, а для доступа через ассоциативную память – 20 нс. Если hit ratio = 90%, то среднее время доступа -> 0,9x20+0,1x100=28нс.

Минус: При переключении контекста процесса при использовании ассоциативной памяти требуется ее «очистка», что ведет к увеличению времени переключения контекста.

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

Метод представляет собой комбинацию сегментного и страничного распределения памяти и сочетает в себе достоинства обоих подходов.

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

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

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

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

Виртуальный адрес состоит из двух составляющих:

1. указание на номер сегмента

2. смещение относительно начала сегмента

2.1. виртуальная страница

2.2. индекс

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



пример двухуровневой таблицы страниц

+Разбиение программы на сегменты позволяет размещать отдельные сегменты в памяти целиком, что позволяет сократить число обращений к отсутствующим страницам, так как вероятность выхода за пределы сегмента меньше вероятности выхода за пределы страницы;

+Наличие сегментов облегчает разделение программных модулей между параллельными процессами;

+Возможна динамическая компоновка задачи;

+Выделение памяти страницам позволяет минимизировать фрагментацию.

-Сложность реализации и высокие вычислительные затраты позволяют использовать его редко в дорогих и мощных вычислительных системах.

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



  1. Поделитесь с Вашими друзьями:
1   2   3   4   5   6   7   8   9   10   ...   15


База данных защищена авторским правом ©nethash.ru 2017
обратиться к администрации

войти | регистрация
    Главная страница


загрузить материал