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

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

Введение

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

1.1 Основные задачи управления памятью

3.1 Распределение памяти фиксированными разделами

3.2 Распределение памяти динамическими разделами

3.3 Перемещаемые разделы

4.1 Страничный способ распределения виртуальной памяти

4.2 Сегментный способ распределения виртуальной памяти

4.3 Сегментно-страничный способ распределения виртуальной памят

Заключение

Список литературы

Введение

Память является важнейшим ресурсом, требующим тщательного управления со стороны операционной системы.

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

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

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

управление память операционный система

1.1 Основные задачи управления памятью

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

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

выделение памяти для процесса пользователя при его запуске и освобождение этой памяти при завершении процесса;

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

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

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

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

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

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

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

предоставление процессам возможности обмена данными через общие области памяти.

2. Классификация методов распределения памяти

Рис. 1 Классификация методов распределения памяти

3. Управление реальной памятью

3.1 Распределение памяти фиксированными разделами

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

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

Рис. 1.1. Распределение памяти фиксированными разделами:

с общей очередью (а), с отдельными очередями (б)

Подсистема управления памятью в этом случае выполняет следующие задачи:

§ Сравнивает объем памяти, требуемый для вновь поступившего процесса, с размерами свободных разделов и выбирает подходящий раздел;

§ Осуществляет загрузку программы в один из разделов и настройку адресов. Уже на этапе трансляции разработчик программы может задать раздел, в котором ее следует выполнять. Это позволяет сразу, без использования перемещающего загрузчика, получить машинный код, настроенный на конкретную область памяти.

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

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

3.2 Распределение памяти динамическими разделами

В этом случае память машины не делится заранее на разделы. Сначала вся память, отводимая для приложений, свободна. Каждому вновь поступающему на выполнение приложению на этапе создания процесса выделяется вся необходимая ему память (если достаточный объем памяти отсутствует, то приложение не принимается на выполнение и процесс для него не создается). После завершения процесса память освобождается, и на это место может быть загружен другой процесс. Таким образом, в произвольный момент времени оперативная память представляет собой случайную последовательность занятых и свободных участков (разделов) произвольного размера. На рис. 2.1 показано состояние памяти в различные моменты времени при использовании динамического распределения. Так, в момент t0 в памяти находится только ОС, а к моменту t1 память разделена между 5 процессами, причем процесс П4, завершаясь, покидает память. На освободившееся от процесса П4 место загружается процесс П6, поступивший в момент t3.

Рис. 2.1. Распределение памяти динамическими разделами

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

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

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

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

§ После завершения процесса корректировка таблиц свободных и занятых областей.

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

Распределение памяти динамическими разделами лежит в основе подсистем управления памятью многих мультипрограммных операционных системах 60-70-х годов, в частности такой популярной операционной системы, как OS/360.

3.3 Перемещаемые разделы

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

Рис. 3.1. Распределение памяти перемещаемыми разделами

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

Хотя процедура сжатия и приводит к более эффективному использованию памяти, она может потребовать значительного времени, что часто перевешивает преимущества данного метода.

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

4. Управление виртуальной памятью

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

4.1 Страничный способ распределения виртуальной памяти

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

Преимущества: устранение фрагментации памяти, т.е. страницы одинакового размера.

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

В ОС Windows память может быть увеличена до 4 Гб, а размер страниц до 4 Кб.

4.2 Сегментный способ распределения виртуальной памяти

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

- о месте расположения сегмента (в оперативной памяти или на жестком диске);

- права доступа;

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

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

Недостатки: потеря процессорного времени на загрузку сегментов и на обработку информационных структур, информационные структуры требовали для себя памяти, дефрагментация памяти.

4.3 Сегментно - страничный способ распределения виртуальной памяти

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

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

5. Подсистема управления памятью в ОС MS-DOS

MS-DOS - это ОС, работающая в реальном режиме процессора i86, что предполагает использование адресного пространства размером всего лишь 1 Мб. На самом деле, в компьютерах IBM гарантируется наличие лишь 640 Кб основной памяти, старшие же адреса памяти заняты под BIOS и видеопамять, хотя среди них попадаются разрозненные куски оперативной памяти, называемые UMB (верхний блок памяти).

Адрес в реальном режиме записывается в формате [сегмент: смещение], однако здесь сегмент - это не селектор, адресующий строку таблицы сегментов, а просто номер параграфа памяти (1 параграф = 16 байт). Поэтому можно считать, что в MS-DOS используются только физические адреса.

В принципе, программы, работающие в MS-DOS, могут получить доступ к памяти за пределами 1 Мб, но для этого требуется специальный драйвер расширенной памяти.

Поскольку делить имеющуюся память между несколькими процессами не приходится, распределение получается бесхитростное.

Рис. 4 Основные области памяти ОС MS-DOS

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

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

Часть системной памяти и вся область пользователя разбита на прилегающие друг к другу блоки, размер которых кратен параграфу. Перед началом каждого блока памяти размещается блок управления памятью (MCB, Memory Control Block), который занимает один параграф и содержит следующие данные:

· признак, определяющий, последний ли это блок памяти или за ним будут еще блоки (соответственно буква `Z" или `M");

· адрес PSP программы, владеющей этим блоком (0 означает свободный блок);

· размер блока в параграфах;

· имя программы-владельца (до 8 символов); это поле избыточно (зная PSP программы, можно найти имя ее файла), оно было добавлено, вероятно, чтобы хоть как-то занять пустующие байты параграфа MCB.

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

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

При запуске программы система выделяет ей два блока памяти: сначала небольшой блок для переменных среды, затем самый большой среди оставшихся свободных блоков для самой программы (блок PSP). Обычно этот блок занимает всю свободную память. Такое решение приемлемо, поскольку других претендентов на память нет.

Почему блок среды выделяется раньше, чем блок PSP?

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

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

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

· Освобождение ранее выделенного блока.

· Изменение размера блока. Уменьшение блока возможно всегда, увеличение - только в том случае, если после данного блока расположен свободный блок достаточного размера.

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

Заключение

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

Список литературы

1. Олифер В. Г. Сетевые операционные системы: учебник для вузов/ В.Г. Олифер, Н.А. Олифер. - СПб.: Питер, 2009. - 539 с.: ил

2. Попов И.И. Операционные системы, среды и оболочки/ И.И. Попов. - М.: Издательство "ФОРУМ: ИНФА-М", 2010. - 400 с. - (Серия "Профессиональное образование")

Размещено на Allbest.ru

Подобные документы

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

лекция , добавлен 24.01.2014


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

презентация , добавлен 27.12.2010


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

курсовая работа , добавлен 01.07.2011


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

курсовая работа , добавлен 02.12.2009


Главная задача компьютерной системы. Виртуальные адресные пространства нескольких программ. Классификация методов распределения памяти. Зависимость загрузки процессора от числа задач и интенсивности ввода-вывода. Схема функционирования кэш-памяти.

презентация , добавлен 14.11.2012


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

контрольная работа , добавлен 23.12.2016


Распределение памяти фиксированными и динамическими, а также перемещаемыми разделами, особенности данного процесса в Windows. Функция VirtualAlloc: переданная и зарезервированная память. Выделение памяти функцией malloc, методика и анализ результатов.

контрольная работа , добавлен 01.12.2013


Сравнительный анализ статической и динамической памяти. Быстродействие и потребление энергии статической памятью. Объем памяти микросхем. Временные диаграммы чтения и записи памяти. Микросхемы синхронной и асинхронной памяти. Режимы модулей памяти.

презентация , добавлен 27.08.2013


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

курсовая работа , добавлен 31.05.2013


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

Функции операционных систем по управлению ресурсами компьютера.

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

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

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

Управление ресурсами включает решение следующих общих, не зависящих от типа ресурса задач:

1 - планирование ресурса – то есть определение, какому процессу, когда и в каком количестве (если ресурс может выделяться частями) следует выделить данный ресурс;

2 - удовлетворение запросов на ресурсы;

3 - отслеживание состояния и учет использования ресурса – то есть поддержание оперативной информации о том, занят или свободен ресурс и какая доля ресурса уже распределена;

4 - разрешение конфликтов между процессами.

Большинство функций управления ресурсами выполняются операционной системой автоматически и прикладному программисту недоступны.

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

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

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

каждого процесса.

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

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

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

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

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

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

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

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

Функциями ОС по управлению памятью в мультипрограммной системе являются:

· отслеживание свободной и занятой памяти,

· выделение памяти процессам и освобождение памяти при завершении процессов,

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

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

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

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

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

Типы адресов

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

· Символьные имена присваивает пользователь при написании программы на алгоритмическом языке или ассемблере.

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

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

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

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

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

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

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

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

Существуют два принципиально отличающихся подхода к преобразованию виртуальных адресов в физические.

Рис. 2.7. Типы адресов

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

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

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

2. Методы распределения памяти без использования дискового пространства

Рис. 2.8. Классификация методов распределения памяти

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

2.1. Распределение памяти фиксированными разделами

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

Подсистема управления памятью в этом случае выполняет следующие задачи :

· сравнивая размер программы, поступившей на выполнение, и свободных разделов, выбирает подходящий раздел,

Рис. 2.9. Распределение памяти фиксированными разделами:
а - с общей очередью; б - с отдельными очередями

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

2.2. Распределение памяти разделами переменной величины

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

На рисунке 2.10 показано состояние памяти в различные моменты времени при использовании динамического распределения. Так в момент t 0 в памяти находится только ОС, а к моменту t 1 память разделена между 5 задачами, причем задача П4, завершаясь, покидает память. На освободившееся после задачи П4 место загружается задача П6, поступившая в момент t 3 .

Задачами операционной системы при реализации данного метода управления памятью являются:

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

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

· после завершения задачи корректировка таблиц свободных и занятых областей.

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

Рис. 2.10. Распределение памяти динамическими разделами

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

2.3. Перемещаемые разделы

Рис. 2.11. Распределение памяти перемещаемыми разделами

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

Хотя процедура сжатия и приводит к более эффективному использованию памяти, она может потребовать значительного времени, что часто перевешивает преимущества данного метода.

Лекция 8. Управление памятью в ОС

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

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

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

В операционных системах различают два вида памяти: основная (первичная) и внешняя (вторичная).

Основная память (main storage) - оперативная память центрального процессора или ее часть, представляющее собой единое пространство памяти.

Внешняя память (external storage) - память, данные в которой доступны центральному процессору посредством операций ввода-вывода.

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

Кроме основной и внешней памяти в современных ЭВМ существует дополнительная быстродействующая память, называемая кэш-памятью .

Все три перечисленных вида памяти образуют иерархию памяти вычислительной машины (см. рис.4.1).

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

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

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

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

• фиксированными блоками равного размера;
• фиксированными разделами неодинакового размера;
• динамическими разделами, размеры которых изменяются в ходе работы вычислительной системы.

Использование основной памяти может осуществляться следующими способами:

• размещение в памяти единовременно только одной программы пользователей;
• размещение в памяти одновременно нескольких программ пользователей;
• размещение программ пользователей в конкретном заранее заданном разделе основной памяти;
• размещение каждой программы пользователя в одном непрерывном (односвязном) пространстве основной памяти;
• размещение программы пользователя в несмежных областях оперативной памяти (при этом ОС осуществляет разбиение размещаемых там программ на отдельные блоки и обеспечивает связь этих блоков между собой).

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

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

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

· когда следует поместить новую программу в память;

· в какое место основной памяти будет размещаться очередная программа;

· как разместить очередную программу в памяти (с минимизацией потерь памяти или с максимизацией скорости размещения);

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

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

Стратегии управления памятью делятся на следующие категории:

· стратегии выборки;

· стратегии размещения;

· стратегии замещения.

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

· стратегии выборки по запросу (по требованию);

· стратегии упреждающей выборки.

Стратегии выборки ставят своей целью определить, когда следует “втолкнуть” очередную программу (или блок программы) или данные в основную память.

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

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

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

Связное распределение памяти - такое распределение основной памяти ЭВМ, при котором каждая программа занимает один непрерывный (связный) блок ячеек памяти.

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

Эффективность той или иной стратегии размещения можно оценить с помощью коэффициента использования памяти h

(4.1)

где V п - объем памяти, занимаемый программами пользователя; V оп - полный объем основной памяти; V ос - объем памяти, занимаемый операционной системой; V о - объем памяти, доступный для распределения.

4.2. Методы связного распределения основной памяти

4.2.1. Связное распределение памяти для одного пользователя

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

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

Организация памяти при связном распределении для одного пользователя показана на рис. 4.2.

Коэффициент использования памяти для рассматриваемого случая вычисляется по формуле

h с1 =V п /V o , (4.2)

где V п - размер программы пользователя; V о - объем доступной для распределения основной памяти ЭВМ.

Функциями ОС в данном случае являются:

· выделение программе необходимого пространства памяти;

· защита памяти;

· освобождение памяти.

Функция выделения памяти сводится к предоставлению программе всей доступной памяти ЭВМ.

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

4.2.2. Связное распределение памяти при мультипрограммной обработке

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

· распределение фиксированными разделами;

· распределение переменными разделами;

· распределение со свопингом.

Распределение фиксированными разделами имеет две модификации:

а) с загрузкой программ в абсолютных адресах;

б) с загрузкой перемещаемых модулей.

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

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

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

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

Коэффициенты использования памяти при распределении с фиксированными разделами вычисляется по формулам:

(4.3)

(4.4)

где h СMi - коэффициент использования памяти i-го раздела; V Оi - размер i-го раздела; V Пi - длина программы, помещенной в i-ый раздел; N Ф - количество разделов; V О - общий объем оперативной памяти, доступной для распределения.

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

Способ распределения памяти фиксированными разделами используется в операционных системах ОС ЕС и IBM/360 в режиме MFT, в котором загрузка программ выполняется перемещаемыми модулями.

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

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

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

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

На рис.4.4. показано проявление фрагментации оперативной памяти.

Уровень фрагментации можно оценить коэффициентом фрагментации K ф, вычисляемый по формуле

(4.5)

Где V дi - размер i-ой “дыры”, т.е. i-го участка свободной памяти, ограниченного программами пользователей; N Д - количество “дыр”, т.е. участков свободной памяти, лежащих между программами пользователей; V o - объем оперативной памяти, доступной для распределения.

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

Распределение памяти переменными разделами предназначено для повышения эффективности использования оперативной памяти ЭВМ. Суть способа распределения памяти переменными разделами состоит в том, что заданиям, когда они поступают, выделяется такой объем памяти, который им требуется, т.е. размер раздела оперативной памяти, выделяемой каждому заданию, в точности соответствует размеру этого задания. Поэтому “перерасхода” памяти, как это происходит при распределении фиксированными разделами, в данном способе не наблюдается.

Имеется две модификации способа распределения переменными разделами:

· распределение переменными неперемещаемыми разделами;

· распределение переменными перемещаемыми разделами.

При распределении памяти переменными неперемещаемыми разделами (динамическими разделами) операционная система создает две таблицы: таблицу учета распределенных областей памяти и таблицу учета свободных областей памяти (“дыр”).

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

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

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

Таблица 4.1. Таблица распределенных областей

Таблица 4.2. Таблица свободных областей

Предположим, что через некоторое время закончились задания А и С (см. рис.4.5б). Таблицы областей приобретают вид, показанный в табл. 4.3 и 4.4.

Таблица 4.3. Таблица распределенных областей: закончилось задание А

Таблица 4.4. Таблица свободных областей: закончилось задание А

Можно видеть, что несмотря на наличие 274К свободной памяти, достаточной для размещения задания Е, стоящего первым в очереди, ОС не имеет возможности это сделать, т.к. свободная память разбита на два фрагмента по 100К каждый, в которых разместить программы, стоящие в очереди, невозможно. Этот пример иллюстрирует главный недостаток способа распределения переменными неперемещаемыми разделами - склонность к фрагментации основной памяти, что снижает эффективность работы вычислительной системы.

При распределении памяти переменными перемещаемыми разделами операционная система осуществляет действия, называемые уплотнением памяти, состоящими в перемещении всех занятых участков к одному или другому краю основной памяти. Благодаря этому вместо большого количества небольших “дыр”, образующихся при использовании распределения переменными неперемещаемыми разделами, формируется единый (связный) участок свободной памяти. На рис.4.5в показан результат уплотнения, когда находящиеся в основной памяти программы В, Д и Е перемещены на свободные участки после окончания работы программ А и С. Свободная память теперь представляет собой непрерывную область размером 274К, в которую ОС может поместить стоящее в очереди задание F. Этот процесс называют также дефрагментацией памяти.

Дефрагментация памяти, применяемая при распределении перемещаемыми разделами, имеет свои недостатки:

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

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

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

4.2.3. Стратегии размещения информации в памяти

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

• размещение с выбором первого подходящего (стратегия “первый подходящий”):
• размещение с выбором наиболее подходящего (стратегия “самый подходящий”);
• алгоритм с выбором наименее подходящего (стратегия “самый неподходящий”).

Стратегия “первый подходящий” состоит в выполнении следующих шагов:

• возрастания адресов ;
• поместить информацию в первый встретившийся участок основной памяти размером не менее требуемого.

Стратегия “самый подходящий” реализует следующую последовательность действий:

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

Стратегия “самый неподходящий” выполняет следующие действия:

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

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

4.3. Организация виртуальной памяти

4.3.1. Основные концепции виртуальной памяти

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

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

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

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

Адреса, которые реально существуют в первичной памяти, называются реальными (физическими) адресами.

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

Диапазон реальных адресов, существующих в конкретной вычислительной машине, называется пространством реальных адресов R этой ЭВМ.

Несмотря на то, что процессы обращаются только к виртуальным адресам, в действительности они должны работать с реальной памятью. Для установления соответствия между виртуальными и реальными адресами разработаны механизмы динамического преобразования адресов ДПА (или ДАТ - от англ.Dynamics Adress Transformation), обеспечивающие преобразование виртуальных адресов в реальные во время выполнения процесса. Все подобные системы обладают общим свойством (см.рис.4.6) - смежные адреса виртуального адресного пространства процесса не обязательно будут смежными в реальной памяти.

Это свойство называют “искусственной смежностью”. Тем самым пользователь освобождается от необходимости рассматривать физическую память с ее уникальными характеристиками.

Виртуальная память строится, как правило, по двухуровневой схеме (см.рис.4.7).

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

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

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

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

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

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

Адреса в системе поблочного отображения являются двухкомпонентными (двумерными). Чтобы обратиться к конкретному элементу данных, программа указывает блок, в котором расположен этот элемент, и смещение элемента относительно начала блока (см.рис.4.8). Виртуальный адрес n указывает при помощи упорядоченной пары (b, d), где b- номер блока, в котором размещается соответствующий элемент данных, а d - смещение относительно начального адреса этого блока.

Преобразование адреса виртуальной памяти n =(b, d) в адрес реальной памяти r осуществляется следующим образом (см.рис.4.9). Каждый процесс имеет собственную таблицу отображения блоков, которую операционная система ведет в реальной памяти. Реальный адрес a этой таблицы загружается в специальный регистр центрального процессора, называемый регистром начального адреса таблицы отображения блоков процесса.

Таблицы отображения блоков содержат по одной строке для каждого блока процесса, причем эти блоки идут последовательно: сначала блок 0, затем блок 1 и т.д. Номер блока b суммируется с начальным адресом а таблицы, образуя реальный адрес строки таблицы для блока b. Найденная строка содержит реальный адрес b начала блока b в реальной памяти. К этому начальному адресу b прибавляется смещение d, так что образуется искомый реальный адрес r=b’+d.

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

4.3.2. Страничная организация виртуальной памяти

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

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

r - признак наличия страницы в первичной памяти (r=0 - страницы в первичной памяти нет; 1 - страница находится в первичной памяти):

S - адрес страницы во внешней памяти (при r=0):

p’ - номер страничного кадра в первичной памяти, где размещена виртуальная страница с номером p.

4.3.3. Сегментная организация виртуальной памяти

Виртуальный адрес при сегментной организации виртуальной памяти - это упорядоченная пара n = (s, d) , где s - номер сегмента виртуальной памяти, а d - смещение в рамках этого сегмента. Процесс может выполняться только в том случае, если его текущий сегмент находится в первичной памяти, Сегменты передаются из внешней памяти в первичную целиком. Все ячейки, относящиеся к сегменту, занимают смежные адреса первичной памяти. Для размещения поступающих из внешней памяти сегментов в свободные участки первичной памяти применяются те же стратегии размещения, как и при распределении переменными неперемещаемыми разделами - “первый подходящий”, “самый подходящий”, “самый неподходящий” (см.п.4.2.3). Динамическое преобразование виртуальных адресов в реальные адреса осуществляется в соответствии со схемой прямого отображения, приведенной на рис. 4.9.

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

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

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

Таблица сегментов процесса содержит в своих строках информацию о количестве страниц в сегменте и о начальных адресах s’ размещения таблиц страниц сегментов в первичной памяти ЭВМ.

Каждая страница таблиц сегмента содержит в своих строках информацию о начальном адресе p’ размещения в первичной памяти страничного кадра для данной страницы виртуальной памяти.

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

4.4. Управление виртуальной памятью

4.4.1. Стратегии управления виртуальной памятью

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

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

Целью стратегий размещения является определить, в какое место первичной памяти помещать поступающую страницу или сегмент.

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

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

Свойство локальности проявляется как во времени, так и в пространстве.

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

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

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

Для оценивания эффективности стратегий управления памятью в операционных системах применяют показатель “пространство-время”, вычисляемый по формуле

S = VЧ T, (4.6)

где S - показатель “пространство-время”; V - объем первичной памяти, занимаемый процессом; T - длительность ожидания процессом подкачки необходимой страницы или сегмента.

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

4.4.2. Стратегии вталкивания (подкачки)

Для управления вталкиванием применяются следующие стратегии:

· вталкивание (подкачка) по запросу (по требованию);

· вталкивание (подкачка) с упреждением (опережением).

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

К положительным сторонам относятся:

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

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

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

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

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

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

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

· размещение с выбором первого подходящего свободного участка;

· размещение с выбором самого подходящего свободного участка;

· размещение с выбором наименее подходящего свободного участка.

Подробное описание действий для реализации перечисленных стратегий размещения приведено в п.4.2.3.

4.4.4. Стратегии выталкивания

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

• выталкивание случайных страниц или сегментов;
• выталкивание первой пришедшей страницы или сегмента (FIFO);
• выталкивание дольше всего не использовавшихся страниц или сегментов (LRU);
• выталкивание наименее часто использовавшихся страниц или сегментов (LFU);
• выталкивание не использовавшихся в последнее время страниц или сегментов (NUR).

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

Стратегия выталкивания первой пришедшей страницы или сегмента (FIFO-стратегия) реализует принцип “первый пришел - первый ушел”. В этом случае в момент поступления каждой страницы (сегмента) в первичную память ей (ему) присваивается метка времени. Когда появляется необходимость удалить из первичной памяти какую-либо страницу (сегмент), выбирается та страница (сегмент), у которой метка времени имеет наименьшее значение. Аргументом в пользу такой стратегии выталкивания является довод, что у данной страницы уже были возможности “использовать свой шанс”, и пора дать подобные возможности другой странице. Однако стратегия FIFO с большой вероятностью будет приводить к удалению из первичной памяти активно используемых страниц (сегментов), поскольку тот факт, что страница (сегмент) находится в первичной памяти в течение длительного времени, вполне может означать, что эта страница или сегмент постоянно находится в работе.

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

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

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

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

· бит-признак b 0 обращения к странице (сегменту);

· бит-признак b 1 модификации страницы (сегмента).

Первоначально все b 0 и b 1 устанавливаются в 0. При обращении к странице (сегменту) соответствующий бит-признак b 0 устанавливается в 1. В случае изменения содержимого страницы (сегмента) соответствующий бит-признак b 1 устанавливается в 1. NUR-стратегия предусматривает существование четырех групп страниц (сегментов), показанных в табл. 4.5.

Таблица 4.5. Группы страниц (сегментов)

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

Учет времени, в течение которого к страницам (сегментам) не было обращений, осуществляется периодическим сбрасыванием в 0 всех битов-признаков, выполняемым операционной системой.

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

Контрольные вопросы

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

2. В чем достоинства и недостатки преобразования виртуальных адресов в реальные во время выполнения программы? Какая часть работы по этому преобразованию выполняется аппаратным обеспечением, а какая - ОС?

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

4. Почему при поиске свободной памяти стратегия "самый подходящий" оказывается хуже, чем "первый подходящий".

5. Сравните сегментную и страничную модели виртуальной памяти. Какая из них представляется Вам лучшей и почему?

6. Дополните приведенные в разделе 3.5. соображения по поводу выбора размера страницы.

7. Смоделируйте ситуацию применения дисциплины вытеснения FCFS, в которой увеличение числа реальных страниц приведет к увеличению числа страничных отказов.

8. Что такое кластерная подкачка страниц? Почему в современных ОС она становится все более популярной?

9. Каким образом ОС может определять, к каким страницам будут обращения в ближайшее время?

10. Большой размер виртуальной памяти процесса может приводить к тому, что даже таблица страниц не будет помещаться в реальной памяти. Какими путями решается эта проблема в современных ОС?

11. Каким образом снижение стоимости памяти влияет на дисциплины управления памятью?

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