Виртуальная память

Записаться

Презентацию к данной лекции Вы можете скачать здесь.

Введение

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

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

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

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

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

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

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

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

Принцип управления виртуальной памятью иллюстрируется рис 18.1.

(рис 18.1) Виртуальная память и физическая память.

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

Страничная организация по требованию

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

Преимущества данного подхода:

Основные принципы страничной организации по требованию:

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

(рис 18.2) Преобразование страничной памяти в непрерывное дисковое пространство.

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

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

Первоначально для всех элементов таблицы страниц бит valid/invalid полагается равным 0.

Если в процессе трансляции адреса бит "valid/invalid" в таблице страниц оказыется равным 0, то происходит прерывание по отсутствию страницы в памяти (page fault).

На рис 18.3 приведен пример таблицы страниц, в которой не все страницы присутствуют в основной памяти.

(рис 18.3) Пример таблицы страниц, в которой не все страницы в памяти.

На схеме логическия память процесса состоит из 6 страниц с номерами от 0 до 5. Однако только страницы 0, 2, 5 размещены в основной памяти (бит valid/invalid имеет значение v = 1). Страницы 1, 3, 4 в основной памяти отсутствуют (бит valid/invalid равен i = 0).

Обработка ситуации отсутствия страницы в памяти

Если в таблице страниц имеется ссылка на страницу, отсутствующую в памяти, первое же обращение по такой ссылке приведет к прерыванию и вызову ОС (ситуации page fault – отсутствие страницы в памяти)

ОС по таблицам определяет, что именно произошло:

Если имеет место неверная ссылка (на страницу, отсутствующую в логической памяти), то работа программы прекращается.

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

Этапы обработки ситуации отсутствия страницы в памяти показаны на рис 18.4.

(рис 18.4) Обработка ситуации отсутствия страницы в памяти.

Этап 1 – выполнение команды load M, которая прерывается по отсутствию страницы в памяти; 2 – прерывание и вызов ОС; 3 – обращение к странице, находящейся в файле откачки на диске; 4 – считывание страницы в память на свободный фрейм; 5 – изменение элемента таблицы страниц; 6 – повторное (успешное) выполнение команды.

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

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

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

Дадим общую оценку производительности обработки страниц по требованию.

Введем коэффициент отказов страниц (Page Fault Rate) p:> 0 <= p <= 1.0.

Если p = 0, то имеет место отсутствие отказов страниц.

Если p = 1, то каждое обращение к странице приводит к отказу.

Оценим теперь эффективное время доступа (Effective Access Time - EAT):

EAT = (1 – p) * время доступа к памяти 
+ p * (время реакции на отказ 
+ [ время откачки страницы ]
+ время подкачки страницы 
+ время рестарта)

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

Преимущества виртуальной памяти при создании процессов

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

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

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

Первоначально файл читается с использованием запроса страниц по требованию. Часть файла размером с одну страницу читается из файла в физическую страницу (фрейм). Последующие чтения из файла и записи в файл трактуются как обычные обращения к памяти. Это упрощает доступ к файлу, по сравнению с системными вызовами read() и write(). Это позволяет также нескольким процессам отображать в память один и тот же файл, по тому же принципу, как они совместно используют какие-либо страницы.

На рис 18.5 иллюстрируется концепция файла, отображаемого в память.

(рис 18.5) Файлы, отображаемые в память.

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

Подобный механизм имеется в большинстве операционных систем. Например, в системе Solaris он реализуется командой и системным вызовом mmap (memory map).

Проблема замещения страниц

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

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

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

Пример замещения страниц приведен на рис 18.6.

(рис 18.6) Пример замещения страниц.

В примере имеются два пользовательских процесса, каждый из которых использует по 4 страницы виртуальной памяти. Однако имеется только 6 фреймов в основной памяти, выделенных для пользовательских процессов, (начальные фреймы занимает резидентный монитор ОС). В процессе 1 происходит обращение к данным M, расположенным на странице 3 виртуальной памяти, отсутствующей в основной памяти. В процессе 2 точно так же может произойти обращение к данным B на странице виртуальной памяти 1, которой также нет в основной памяти. Следовательно, ОС должна выполнить замещение страниц, т.е. решить две задачи:

Кратко алгоритм замещения страниц можно сформулировать следующим образом:

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

(рис 18.7) Замещение страниц с откачкой жертвы на диск.

Этапы замещения страниц: 1 – откачка жертвы; 2 – изменение ее элемента таблицы страниц (бит valid заменяется на invalid); 3 – подкачка на освободившееся место желаемой страницы; 4 – изменение элемента таблицы страниц для новой страницы (бит invalid заменяется на valid; запоминается физический адрес подкачанной страницы).

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

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

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

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

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.

График зависимости числа отказов страниц от числа фреймов в основной памяти изображен на рис 18.8.

(рис 18.8) Зависимость числа отказов страниц от числа фреймов.

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

Алгоритм FIFO (First-In-First-Out).Наиболее простой алгоритм замещения страниц – в качестве жертвы всегда выбирается фрейм, первым из имеющихся считанный в основную память.

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

Пусть строка запросов имеет вид: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.

Случай 1: 3 фрейма (3 страницы могут быть одновременно в памяти для одного процесса). Пусть имеются три процесса. Их таблицы страниц примут вид:

(1, 2, 3) (4, 1, 2) (5, 3, 4).

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

Случай 2: 4 фрейма. Пусть имеются по-прежнему три процесса. Таблицы страниц в данном случае будут иметь вид:

(1, 2, 3, 4) (5, 1, 2, 3) (4, 5)

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

Данная аномалия называется аномалией Belady.

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

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

(рис 18.9) Пример работы алгоритма FIFO.

На рис 18.10 изображен график зависимости числа отказов страниц от числа фреймов при алгоритме FIFO, отображающий аномалию Belady.

(рис 18.10) Аномалия Belady при использовании алгоритма FIFO замещения страниц.

Оптимальный алгоритм замещения страниц

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

Рассмотрим пример применения данного алгоритма с той же строкой запроса и с четырьмя максимально возможными фреймами у каждого процесса:

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

Нетрудно видеть, что будет иметь место всего 6 отказов страниц (в отличие от алгоритма FIFO с 10 отказами страниц).

Пример использования оптимального алгоритма замещения страниц с той же строкой запроса, которая применялась на рис 18.9 для алгоритма FIFO, приведен на рис 18.11.

(рис 18.11) Пример использования оптимального алгоритма замещения страниц.

Алгоритм Least Recently Used (LRU)

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

Для примера со строкой запросов: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 число отказов страниц равно всего 4.

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

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

Пример использования алгоритма замещения страниц LRU с той же строкой запроса, что и на рис 18.9 и рис 18.11 для других алгоритмов, приведен на рис 18.12.

(рис 18.12) Пример использования алгоритма замещения страниц LRU.

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

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

(рис 18.13) Использование стека в алгоритме LRU для хранения самых недавних обращений к страницам.

Алгоритмы, близкие к LRU

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

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

Схема алгоритма второго шанса изображена на рис 18.14.

(рис 18.14) Алгоритм второго шанса.

Алгоритмы со счетчиком

Идея, родственная идее алгоритма LRU, - хранить счетчики числа обращений к каждой странице. На основе этой идеи существуют два алгоритма:

Выделение фреймов

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

Однако различные аппаратные платформы имеют свои особенности, что тоже приходится учитывать. Например, в системе IBM 370 требуется 6 (!) страниц, чтобы обработать команду MOVE (пересылки) формата SS (Storage-Storage). В самом деле, длина команды - 6 байтов, так что она может размещается на двух соседних страницах. Кроме того, максимум две страницы требуются для обработки источника и максимум две страницы – для обработки получателя. Разумеется, подобный казус не может произойти в RISC-системах.

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

Фиксированное выделение фреймов.Наиболее простой вариант - равномерное распределение фреймов процессам. Например, если имеется 100 фреймов и 5 процессов, каждому выделяется по 20 страниц. Используется также пропорциональное распределение – выделять фреймы в соответствии со следующим принципом: если общее число фреймов m, размер процесса – s, а общий размер всех процессов – S, то общее число фреймов, выделенных процессу, равно:

a = m * (s / S).

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

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

Thrashing

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

Неформально, thrashing означает катастрофическую нехватку фреймов в основной памяти. На практике для пользователя это выглядит следующим образом (автор сам неоднократно испытывал подобные ощущения, вынужденный работать на SPARC-станции с очень малым объемом памяти): жесткий диск буквально "надрывается" от непрерывных обращений, а процесс исполняется крайне медленно. Интересно отметить, что SPARC-станция с 32 мегабайтами памяти и ОС Solaris успешно выдерживали эти экстремальные нагрузки (причем на данной конфигурации пропускалась достаточно большая Java-программа). Это говорит о высокой надежности системы Solaris.

Другой реальный пример – использование ОС Windows XP (Service Pack 3) на компьютере с 512 мегабайтами памяти. При этом возникает почти такое же ощущение - сначала кажется, что неисправен жесткий диск, но затем сразу осознаешь, что все дело в нехватке памяти: самые простые программы, такие как Internet Explorer, Windows Explorer и др., будучи вызванными одновременно (что является обычной практикой) переполняют основную память и вынуждают операционную систему при любом дополнительном действии пользователя (даже при простом передвижении полосы прокрутки по именам файлов в Windows Explorer) непрерывной откачкой и подкачкой.

На рис 18.15 приведен график зависимости использования процессора от коэффициента мультипрограммирования. При очень большом числе обрабатываемых процессов полезность использования процессора резко падает из-за постоянных откачек и подкачек. Это и есть thrashing.

(рис 18.15)

Модель рабочего множества

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

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

Для борьбы с подобными явлениями в операционных системах для распределения фреймов используется модель рабочего множества. Обозначим через $$\Delta$$ (рабочее множество) фиксированное число обращений к страницам.

Рассмотрим WSSi (рабочее множество процесса Pi ) - общее число обращений к страницам в самой недавней $$\Delta$$ (меняется в зависимости от времени).

Если $$\Delta$$ очень мало, не рассматриваем полную локальную потребность.

Если $$\Delta$$ слишком велико, рассматриваем несколько локальных потребностей.

Если $$\Delta = \infty$$, рассматриваем всю программу.

Вычислим величину $$D = \sum WSS_{i}$$ - общий объем требований фреймов всех процессов. Пусть m – размер основной памяти.

Если D > m то Thrashing ( m - общий размер памяти).

Политика ОС по борьбе с thrashing’ом заключается в том, чтобы, если D > m, приостановить один из процессов.

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

(рис 18.16) Пример использования рабочего множества.

Страничная организация по требованию в Windows NT

ОС Windows NT использует страничную организацию "по требованию" и кластеризацию, т.е. подкачку страниц, смежных с затребованной. Процессам выделяются минимальное и максимальное рабочие множества. Минимальное рабочее множество – это набор страниц, которые процесс гарантированно имеет в памяти. Процесс может иметь в памяти число страниц до максимума рабочего множества. Если объем свободной памяти в системе становится меньше некоторого порогового значения (threshold), то ОС выполняет сокращение рабочих множеств процессов (working set trimming).Сокращение рабочих множеств – это изъятие у процессов "лишних" страниц в оперативной памяти, которые превышают минимальный размер их рабочих множеств.

Страничная организация в Solaris

В ОС Solaris поддерживается список свободных страниц для выделения процессам, в которых происходят отказы страниц. Используется lotsfree – пороговый параметр для начала подкачки страниц. Управление страницами выполняет процесс pageout. Процесс pageout сканирует страницы, используя модифицированный алгоритм, основанный на показаниях часов. Используется также scanrate – коэффициент, характеризующий процесс сканирования. Диапазон - от slowscan до fastscan. Процесс pageout вызывается более часто, в зависимости от размера свободной памяти.

Ключевые термины

mmap (memory map) – команда и системный вызов в ОС Solaris для организации файла, отображаемого в память.

Thrashing – ситуация критической нехватки основной памяти в системе, при которой процессор занят в основном откачкой и подкачкой страниц.

Алгоритм FIFO (First-In-First-Out) замещения страниц - наиболее простой алгоритм замещения страниц, при котором в качестве жертвы всегда выбирается фрейм, первым из имеющихся считанный в основную память.

Алгоритм Least Frequently Used (LFU) замещения страниц – алгоритм, при котором замещается страница с минимальным значением счетчика обращений (к которой было меньше всего обращений).

Алгоритм Least Recently Used (LRU) замещения страниц – алгоритм, при котором замещается та страница, которая раньше всего использовалась.

Алгоритм Most Frequently Used (MFU) замещения страниц – алгоритм, при котором замещается страница с максимальным значением счетчика обращений (к которой было больше всего обращений).

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

Аномалия Belady – рост числа отказов страниц в алгоритме FIFO при четырех свободных фреймах у процесса, по сравнению с числом отказов страниц при трех свободных фреймах.

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

Бит ссылки (reference bit) – бит элемента таблицы страниц, равный 0, если к странице не было обращения, и 1, если обращение к странице было.

Бит "valid/invalid" – бит элемента таблицы страниц, указывающий на присутствие или отсутствие страницы в основной памяти.

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

Выделение фреймов по приоритетам – выделение процессам фреймов страниц в основной памяти, в соответствии с приоритетами процессов: при замещении страниц замещается страница процесса с более низким приоритетом.

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

Замещение страницы (page replacement) – подкачка операционной системой страницы, к которой произошло обращение, вместо другой страницы, с откачкой последней, если она требуется.

Копирование при записи (Copy-on-Write) – стратегия создания процесса, при которой новый процесс разделяет адресное пространство с процессом-родителем до первой записи в адресное пространство, после чего для дочернего процесса создается новое адресное пространство – копия родительского.

Коэффициент отказов страниц (Page Fault Rate) – число от 0 до 1, характеризующее вероятность отказа страницы.

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

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

Отказ страницы ( page fault) – прерывание по отсутствию страницы в основной памяти.

Пропорциональное выделение фреймов – выделение процессам фреймов страниц в основной памяти, пропорционально размерам процессов в памяти.

Рабочее множество – набор страниц, используемых процессом.

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

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

Файл, отображаемый в память (Memory-Mapped File) – файл, блоки которого отображены в основную память через таблицу страниц.

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

Эффективное время доступа (Effective Access Time - EAT) – математическое ожидание времени доступа к странице.

Краткие итоги

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

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

Страничная организация по требованию – схема страничной организации, при которой страница подкачивается в основную память только при обращении к ней.При отсутствии адресуемой страницы в основной памяти происходит прерывание – отказ страницы (page fault). Бит valid-invalid элемента таблицы страниц указывает, присутствует ли страница в основной памяти.

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

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

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

Число отазов страниц обратно пропорционально зависит от числа свободных фреймов у каждого процесса: чем больше фреймов, тем меньше отказов страниц. Исключение – аномалия Belady: возрастание числа отказов при четырех фреймах, по сравнению с тремя в алгоритме FIFO.

Используются следующие алгоритмы замещения страниц: FIFO (замещается страница, загруженная в память раньше всех); оптимальный алгоритм (замещается страница, которая не использовалась в течение наибольшего периода времени); LRU (замещается страница, к которой раньше всего было обращение); LRU с использованием стека страниц с самой ранней по обращению страницей на вершине; замещение страниц с нулевым битом ссылки; алгоритм второго шанса (замещение второй по давности обращений страницы, с сохранением первой в памяти); LFU – замещение реже всего используемой страницы; MFU – замещение чаще всего используемой страницы.

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

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

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

В системе Solaris имеется пороговое значение для подкачки страниц; управление страницами выполняется на основе модифицированных показаний часов.

Набор для практики

Вопросы

Упражнения

Темы для курсовых работ, рефератов, эссе