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

Лекция 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. Какие принципиальные изменения в концепции памяти может повлечь за собой увеличение разрядности адреса?

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

Фиксированное распределение

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

Размеры разделов

На рис. 7.2 показаны два примера фиксированного распределения. Одна возможность состоит в использовании разделов одинакового размера. В этом случае любой процесс, размер которого не превышает размер раздела, может быть загружен в любой доступный раздел. Если все разделы заняты и нет ни одного процесса в состоянии готовности или работы, операционная система может выгрузить процесс из любого раздела и загрузить другой процесс, обеспечивая тем самым процессор работой.
При использовании разделов с одинаковым размером имеются две трудности.
Программа может быть слишком велика для размещения в разделе. В этом случае программист должен разрабатывать программу, использующую оверлеи, с тем чтобы в любой момент времени ей требовался только один раздел основной памяти. Когда требуется модуль, который в настоящий момент отсутствует в основной памяти, пользовательская программа должна сама загрузить этот модуль в раздел памяти программы (независимо от того, является ли этот модуль кодом или данными).
Использование основной памяти при этом крайне неэффективно. Любая программа, независимо от ее размера, занимает раздел целиком. Так, в нашем примере программа размером менее мегабайта все равно будет занимать целиком раздел в 8 Мбайт; при этом остаются неиспользованными 7 Мбайт блока. Этот феномен появления неиспользованной памяти из-за того, что загружаемый блок по размеру меньше раздела, называется внутренней фрагментацией (internal fragmentation).
Бороться с этими трудностями (хотя и не устранить полностью) можно посредством использования разделов разных размеров (см. рис. 7.2,б). В этом случае программа размером 16 Мбайт может обойтись без оверлеев, а разделы малого размера позволяют уменьшить внутреннюю фрагментацию при загрузке программ малого размера.

Алгоритм размещения

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


Хотя этот метод представляется оптимальным с точки зрения отдельного раздела, он не оптимален с точки зрения системы в целом. Представим, что в системе, изображенной на рис. 7.2,6, в некоторый момент времени нет ни одного процесса размером от 12 до 16 Мбайт. В результате раздел размером 16 Мбайт будет пустовать, в то время как он мог бы с успехом использоваться меньшими процессами. Таким образом, более предпочтительным подходом является использование одной очереди для всех, процессов (см. рис. 7.3,б). В момент, когда требуется загрузить процесс в основную память, для этого выбирается наименьший доступный раздел, способный вместить данный процесс. Если все разделы заняты, следует принять решение об освобождении одного из них. По-видимому, следует отдать предпочтение процессу, занимающему наименьший раздел, способный вместить загружаемый процесс. Можно учесть и другие факторы, такие, как приоритет процесса или его состояние (заблокирован он или активен).
Использование разделов разного размера по сравнению с использованием разделов одинакового размера придает дополнительную гибкость данному методу. Кроме того, схемы с фиксированными разделами относительно просты, предъявляют минимальные требования к операционной системе; накладные расходы работы процессора невелики. Однако у этих схем имеются серьезные недостатки.
Количество разделов, определенное в момент генерации системы, ограничивает количество активных (не приостановленных) процессов.
Поскольку размеры разделов устанавливаются заранее, в момент генерации системы, небольшие процессы приводит к неэффективному использованию памяти. В средах, где заранее известны потребности в памяти всех задач, применение описанной схемы может быть оправдано, но в большинстве случаев эффективность этой технологии крайне низка.
Фиксированное распределение в настоящее время практически не используется. Примером успешной операционной системы с использованием данной технологии может служить ранняя операционная система IBM для мейнфреймов OS/MFT (многозадачная с фиксированным количеством задач- Multiprogramming with a Fixed number of Tasks).

Динамическое распределение

Для преодоления сложностей, связанных с фиксированным распределением, был разработан альтернативный подход, известный как динамическое распределение. Этот подход в настоящее время также вытеснен более сложными и эффективными технологиями управления памятью. В свое время динамическое распределение использовала операционная система IBM для мейнфреймов OS/MVT (многозадачная с переменным количеством задач - Multiprogramming with a Variable number of Tasks).
При динамическом распределении образуется переменное количество разделов переменной длины. При размещении процесса в основной памяти для него выделяется строго необходимое количество памяти, и не более. В качестве примера рассмотрим использование 6.4 Мбайт основной памяти (рис. 7.4). Изначально вся память пуста, за исключением области, используемой операционной системой (рис. 7.4,а). Первые три процесса загружаются в память, начиная с адреса, которым заканчивается операционная система, и используя ровно столько памяти, сколько требуется данному процессу (рис. 7.4,б-г). После этого в конце основной памяти остается "дыра", слишком малая для размещения четвертого процесса. В некоторый момент все процессы в памяти оказываются неактивными, и операционная система выгружает второй процесс (рис. 7.4,д), после которого остается достаточно памяти для загрузки нового, четвертого процесса (рис. 7.4,е). Поскольку процесс 4 меньше процесса 2, создается еще одна небольшая "дыра" в памяти. После того как в некоторый момент времени все процессы в памяти оказываются неактивными, но зато готов к работе процесс 2, свободного места в памяти для него не находится, и операционная система вынуждена выгрузить процесс 1, чтобы освободить необходимое место (рис. 7.4,ж) и разместить процесс 2 в основной памяти (рис. 7.4,з).

Как показывает данный пример, этот метод хорошо начинает работу, но плохо продолжает - в конечном счете он приводит к наличию множества мелких дыр в памяти. Со временем память становится все более и более фрагментированной, и снижается эффективность ее использования. Это явление называется внешней фрагментацией (external fragmentation), что отражает тот факт, что сильно фрагментированной становится память, внешняя по отношению ко всем разделам (в отличие от рассмотренной ранее внутренней фрагментации).
Один из методов преодоления этого явления сострит в уплотнении (compaction): время от времени операционная система перемещает процессы в памяти так, чтобы они занимали смежные области памяти; свободная память при этом собирается в один блок. Например, на рис. 7.4,з после уплотнения памяти мы получим блок свободной памяти размером 16 Мбайт, чего может оказаться вполне достаточно для загрузки нового процесса. Сложность применения уплотнения состоит в том, что при этом расходуется дополнительное время; кроме того, уплотнение требует динамического перемещения процессов в памяти, т.е. должна быть обеспечена возможность перемещения программы из одной области основной памяти в другую без потери корректности ее обращений к памяти (см. приложение к данной главе).

Алгоритм размещения

Поскольку уплотнение памяти вызывает дополнительные расходы времени процессора, разработчик операционной системы должен принять разумное решение о том, каким образом размещать процессы в памяти (образно говоря, каким образом затыкать дыры). Когда наступает момент загрузки процесса восновную память и имеется несколько блоков свободной памяти достаточного размера, операционная система должна принять решение о том, какой именно свободный блок использовать.
Можно рассматривать три основных алгоритма - наилучший подходящий, первый подходящий, следующий подходящий. Все они, само собой разумеется, ограничены выбором среди свободных блоков размера, достаточно большого для размещения процесса. Метод наилучшего подходящего выбирает блок, размер которого наиболее близок к требуемому; метод первого подходящего проверяет все свободные блоки с начала памяти и выбирает первый достаточный по размеру для размещения процесса. Метод следующего подходящего работает так же, как и метод первого подходящего, однако начинает проверку с того места, где был выделен блок в последний раз (по достижении конца памяти он продолжает работу с ее начала).
На рис. 7.5,а показан пример конфигурации памяти после ряда размещений и выгрузки процессов из памяти. Последним использованным блоком был Мок размером 22 Мбайт, в котором был создан раздел в 14 Мбайт. На рис. 7,5,6 показано различие в технологии наилучшего, первого и следующего подходящего при выполнении запроса на выделение блока размером 16 Мбайт. Метод наилучшего подходящего просматривает все свободные блоки и выбирает наиболее близкий по размеру блок в 18 Мбайт, оставляя фрагмент размером 2 Мбайт. Метод первого подходящего в данной ситуации оставляет фрагмент свободной памяти размером б Мбайт, а метод следующего подходящего - 20 Мбайт.

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

Алгоритм замещения

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

Система двойников

Как фиксированное, так и динамическое распределение памяти имеют свои недостатки. Фиксированное распределение ограничивает количество активных процессов и неэффективно использует память при несоответствии между размерами разделов и процессов. Динамическое распределение реализуется более сложно и включает накладные расходы по уплотнению памяти. Интересным компромиссом в этом плане является система двойников (, [РБТЕ77]).
В системе двойников память распределяется блоками размером 2,к < К < U ,
где
21 - минимальный размер выделяемого блока памяти;
2и - наибольший распределяемый блок; вообще говоря, 2и представляет собой размер всей доступной для распределения памяти.
Вначале все доступное для распределения пространство рассматривается как единый блок размера 2u. При запросе размером s, таким, что 2 u- l< s <2и, выделяется весь блок. В противном случае блок разделяется на два эквивалентных двойника с размерами 2u-1. Если 2 U-2 < s<2 u- l, то по запросу выделяется один из двух двойников; в противном случае один из двойников вновь делится пополам. Этот процесс продолжается до тех пору пока не будет сгенерирован наименьший блок, размер которого не меньше 8. Система двойников постоянно ведет список "дыр" (доступных блоков) для каждого размера 2l. Дыра может быть удалена из списка (i+1) разделением ее пополам и внесением двух новых дыр размера 2l в список i. Когда пара двойников в списке i оказывается освобожденной, они удаляются из списка и объединяются в единый блок в списке (i+1). Ниже приведен рекурсивный алгоритм () для удовлетворения запроса размера 2i-l void get_hole(int i)
{
if (i = = (U+1))
< Ошибка >;
if (< Список 1 пуст >)
{
get_hоle(i+l);
< Разделить дыру на двойники >;
< Поместить двойники в список i >;
}
< Взять первую дыру из списка i >;
}
На рис. 7.6 приведен пример использования блока с начальным размером 1 Мбайт. Первый запрос А - на 100 Кбайт (для него требуется блок размером 128 Кбайт); Для этого начальный блок делится на два двойника по 512 Кбайт. Первый из них делится на двойники размером 256 Кбайт, и, в свою очередь, первый из получившихся при этом разделении двойников также делится пополам. Один из получившихся двойников размером 128 Кбайт выделяется запросу А. Следующий запрос В требует 256 Кбайт. Такой блок имеется в наличии и выделяется. Процесс продолжается с разделением и слиянием двойников при необходимости. Обратите внимание, что после освобождения блока Е происходит слияние двойников по 128 Кбайт в один блок размером 256 Кбайт, который, в свою очередь, тут же сливается со своим двойником.


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

Система двойников представляет собой разумный компромисс для преодоления недостатков схем фиксированного и динамического распределения, но в современных операционных системах ее превосходит виртуальная память, основанная на страничной организации и сегментации. Однако система двойников нашла применение в параллельных системах как эффективное средство распределения и освобождения параллельных программ (см., например, ). Модифицированная версия системы двойников используется для распределения памяти ядром UNIX (подробнее об этом вы узнаёте в главе 8, "Виртуальная память").

Перемещение

Перед тем как мы рассмотрим способы, с помощью которых можно избежать недостатков распределения, следует до конца разобраться в вопросах, связанных с размещением процессов в памяти. При использовании фиксированной схемы распределения, показанной на рис. 7.3,а, можно ожидать, что процесс всегда будет назначаться одному и тому же разделу памяти. Это означает, что какой бы раздел ни был выбран для нового процесса, для размещения этого процесса после выгрузки и последующей загрузки в память всегда будет использоваться именно этот раздел. В данном случае можно использовать простейший загрузчик, описанный в приложении к данной главе: при загрузке процесса все относительные ссылки в коде замещаются абсолютными адресами памяти, определенными на основе базового адреса загруженного процесса.
Если размеры разделов равны (рис. 7.2) и существует единая очередь процессов для разделов разного размера (рис. 7.3,б), процесс по ходу работы может занимать разные разделы. При первом создании образа процесса он загружается в некоторый раздел памяти; позже, после того как он был выгружен из памяти и вновь загружен, процесс может оказаться в другом разделе (не в том, в котором он размещался в последний раз). Та же ситуация возможна и при динамическом распределении. Так, на рис. 7.4,в и 3процесс 2 занимает при размещении в памяти различные места. Кроме того, при выполнении уплотнения процессы также перемещаются в основной памяти. Таким образом, расположение команд и данных, к которым обращается процесс, не является фиксированным и изменяется всякий раз при выгрузке и загрузке (или перемещении) процесса. Для решения этой проблемы следует различать типы адресов. Логический адрес представляет собой ссылку на ячейку памяти, не зависящую от текущего расположения данных в памяти; перед тем как получить доступ к этой ячейке памяти, необходимо транслировать логический адрес в физический. Относительный адрес представляет собой частный случай логического адреса, когда адрес определяется положением относительно некоторой известной точки (обычно - начала программы). Физический адрес (известный также как абсолютный) представляет собой действительное расположение интересующей нас ячейки основной памяти.
Если программа использует относительные адреса, это означает, что все ссылки на память в загружаемом процессе даны относительно начала этой программы. Таким образом, для корректной работы программы требуется аппаратный механизм, который бы транслировал относительные адреса в физические в процессе выполнения команды, которая обращается к памяти.
На рис. 7.8 показан обычно используемый способ трансляции адреса. Когда процесс переходит в состояние выполнения, в специальный регистр процессора, иногда называемый базовым, загружается начальный адрес процесса в основной памяти. Кроме того, используется "граничный" (bounds) регистр, в котором содержится адрес последней ячейки памяти программы. Эти значения заносятся в регистры при загрузке программы в основную память. При выполнении процесса встречающиеся в командах относительные адреса обрабатываются процессором в два этапа. Сначала к относительному адресу прибавляется значение базового регистра для получения абсолютного адреса. Затем полученный абсолютный адрес сравнивается со значением в граничном регистре. Если полученный абсолютный адрес принадлежит данному процессу, команда может быть выполнена; в противном случае генерируется соответствующее данной ошибке прерывание операционной системы.
Схема, представленная на рис. 7.8, обеспечивает возможность выгрузки и загрузки программ в основную память в процессе их выполнения; кроме того, образ каждого процесса ограничен адресами, содержащимися в базовом и граничном регистрах, и защищен от нежелательного доступа со стороны других процессов.

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

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

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

Загрузку ОП в ОС Windowsможно посмотреть в Taskmanager.

Рассмотрим основные инструменты управления памятью.

Инструменты управления памятью

• Регистры база-предел
• Свoп
• Страницы (также таблицы страниц)
• Сегменты (таблицы сегментов)
• Страничное прерывание (page fauet) и виртуальная память

В данной статье рассматриваются два первых: регистр база0предел и своп.

Современные ОС

Основным механизмом абстракции в современных ОС является виртуальная память(virtual memory) , используется повсеместно, так как:

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

Аппаратная поддержка для VM(virtual memory )

Виртуальная память требует аппаратной поддержки:

• MMU (memory management unit ) -Блок управления памятью
• TLB (Translation lookaside buffe ) — Буфер ассоциативной трансляции
• Таблицы страниц
• Обработка страничных прерываний

Обычно есть поддержка свопинга и ограниченной сегментации.

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

По сути это неэффективное использование памяти.

Очевидный минус – снижается объем доступной памяти.

Существует 2 типа фрагментации:

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

Внутренняя фрагментация

внутренняя фрагментация ОП

Поступает запрос в ОС на выделение блока памяти, длиной N-байт.

Система неким образом(любым алгоритмом) выделяет кусок памяти.

В силу того, что алгоритмы выделения кусков памяти разные, часто реально выделается не N-байт, а N+K байт, где К- значение или 0 или вполне реальное.

Все «выделители» памяти работают таким образом, обычно никогда не выделяется ровно столько памяти, сколько запрашивается процессом, т.е. внутри выделенного блока памяти есть неиспользованное пространство (К) — это есть внутренняя фрагментация – фрагментация внутри блока . Эти К при использовании многих блоков накапливаются, они вроде бы и есть, но использовать их нельзя.

Внешняя фрагментация

Внешняя фрагментация памяти

В ОП выделяется много кусков памяти и какие то из них освободились (процессы закончили работать и освободили ОП). В результате получилось 4 занятых куска и 1 и 2 свободные.

Поступает запрос на выделение большого куска памяти. Если суммировать 1+2 блоки памяти, то вполне хватит, но они разбросаны. Поэтому процессу память не выделится, будет получен отказ.

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

Эволюция памяти

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

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

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

Свопинг

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

Исторически свопинг – это замена одной программы на другую.

Мультипрограммирование

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

При этом возникают требования к менеджеру памяти:

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

Вводится понятие виртуальных адресов.

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

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

Адресное пространство – это множество виртуальных адресов, которые могут использовать процессы. Это было самое начало того, что сейчас называется «виртуальной памятью». Но в данном случае, это гораздо примитивнее.

Метод фиксированных разделов

Это самый простой метод — метод разбивки физической памяти на разделы фиксированной длины .

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

Аппаратная поддержка в виде регистров база-предел.

Преобразование адресов осуществляется по формуле:

Физический адрес = виртуальный адрес + база

Базовый регистр загружается ОС при переключении процесса.

Простая защита : Если виртуальный адрес больше база+предел, тогда наступает определенное системой событие – отказ в доступе или выводится ошибка. Есть механизм, который позволяет это отследить.

Преимущества:

• Простой метод

Недостатки:

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

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

Метод фиксированных разделов

Есть виртуальный адрес, он дает нам смещение.

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

Регистр базы на рисунке равен 6Кб. Процесс будет располагаться между 6 и 8Кб.

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

Аппаратные требования те же: регистр база-предел

Физический адрес = виртуальный адрес + база

Защита – проверять если физический адрес больше, чем виртуальный адрес + предел

Преимущества:

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

Недостатки:

• внешняя фрагментация: загрузка/выгрузка задач оставляет необъединяемые «дыры» в памяти.

Все тоже самое, но в памяти появились свободные пространства.

Метод фиксированных разделов

устранение внешней фрагментации

Как бороться с внешней фрагментацией?

На помощь приходит свопинг .

1. Выгрузить программ;
2. Загрузить ее по другому адресу;
3. Исправить регистр базы.

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

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

Современный подход к решению этой проблемы – организация памяти в виде страниц.

Другие основные инструменты управления памятью мы рассмотрим в следующей статье.

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

В ранних ОС управление памятью сводилось просто к загрузке программы и ее данных из некоторого внешнего накопителя (перфоленты, магнитной ленты или магнитного диска) в ОЗУ. При этом память разделялась между программой и ОС. На рис. 6.3 показаны три варианта такой схемы. Первая модель раньше применялась на мэйнфреймах и мини-компьютерах. Вторая схема сейчас используется на некоторых карманных компьютерах и встроенных системах, третья модель была характерна для ранних персональных компьютеров с MS-DOS.

Рис. 6.3. Варианты распределения памяти

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

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

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

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

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

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

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

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

Совокупность виртуальных адресов процесса называется виртуальным адресным пространством. Диапазон адресов виртуального пространства у всех процессов один и тот же и определяется разрядностью адреса процессора (для Pentium адресное пространство составляет объем, равный 2 32 байт, с диапазоном адресов от 0000.0000 16 до FFFF.FFFF 16).

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

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

Распределение памяти

Существует ряд базовых вопросов управления памятью, которые в различных ОС решаются по-разному. Например, следует ли назначать каждому процессу одну непрерывную область физической памяти или можно выделять память участками? Должны ли сегменты программы, загруженные в память, находиться на одном месте в течение всего периода выполнения процесса или их можно время от времени сдвигать? Что делать, если сегменты программы не помещаются в имеющуюся память? Как сократить затраты ресурсов системы на управление памятью? Имеется и ряд других не менее интересных проблем управления памятью [5 , 10 , 13 , 17 ].

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

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

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

Рис. 6.6. Варианты фиксированного распределения памяти

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

1. Программа может быть слишком велика для размещения в разделе. В этом случае программист должен разрабатывать программу, использующую оверлеи, чтобы в любой момент времени требовался только один раздел памяти. Когда требуется модуль, отсутствующий в данный момент в ОП, пользовательская программа должна сама его загрузить в раздел памяти программы. Таким образом, в данном случае управление памятью во многом возлагается на программиста.
2. Использование ОП крайне неэффективно. Любая программа, независимо от ее размера, занимает раздел целиком. При этом могут оставаться неиспользованные участки памяти большого размера. Этот феномен появления неиспользованной памяти называется внутренней фрагментацией (internal fragmentation).

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

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

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

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

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

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

Для преодоления сложностей, связанных с фиксированным распределением, был разработан альтернативный подход, известный как динамическое распределение. В свое время этот подход был применен фирмой IBM в операционной системе для мэйнфреймов в OS/MVT (мультипрограммирование с переменным числом задач –Multiprogramming With a Variable number of Tasks). Позже этот же подход к распределению памяти использован в ОС ЕС ЭВМ [12 ] .

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

Рис. 6.7. Вариант использования памяти

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

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

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

1. Перемещение всех занятых участков в сторону старших или младших адресов при каждом завершении процесса или для вновь создаваемого процесса в случае отсутствия раздела достаточного размера.
2. Коррекция таблиц свободных и занятых областей.
3. Изменение адресов команд и данных, к которым обращаются процессы при их перемещении в памяти, за счет использования относительной адресации .
4. Аппаратная поддержка процесса динамического преобразования относительных адресов в абсолютные адреса основной памяти.
5. Защита памяти, выделяемой процессу, от взаимного влияния других процессов.

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

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

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

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

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

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

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

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

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

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

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