Раздел 3

Виртуальный адрес – смещение от начала ВАП, одно число.

Сегментированное ВАП

Виртуальный адрес – пара чисел (n,m), где n определяет сегмент, а m – смещение внутри сегмента.

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

и включает решение следующих задач:

действия:

таблицы страниц
При размере страниц в 4 Кбайт, 32-разрядное адресное

пространство имеет 1 миллион страниц, а 64-разрядное адресное пространство состоит из 252страниц. Таблица страниц должна содержать запись о каждой виртуальной странице. Если каждая запись будет занимать 8 байт, то размер таблицы превысит 8 миллионов байт для 32 разрядной архитектуры и 30 миллионов байт для 64-разрядной. При этом каждому процессу требуется своя собственная таблица страниц.

быть помечена количеством команд, которые выполняются до первого обращения к

странице.

Суть алгоритма:

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

дескрипторе страницы:
Бит R (обращения), бит М (модификации).
Суть алгоритма
При запуске процесса

R=0, M=0 для всех его страниц.
При каждом прерывании по таймеру бит R сбрасывается, чтобы отличить те страницы, к которым в последнее время не было обращений, от тех, к которым такие обращения были.
При возникновении ошибки отсутствия страницы ОС просматривает все дескрипторы страниц и делит их на четыре категории:
Класс 0: в последнее время не было ни обращений, ни модификаций
Класс 1: обращений в последнее время не было, но страница модифицирована.
Класс 2: в последнее время были обращения, но модификаций не было.
Класс 3: в последнее время были и обращения и модификации.

Алгоритм исключения недавно использовавшейся страницы — NRU(Not Recently Used) удаляет произвольную страницу, относящуюся к самому низкому непустому классу.

список всех страниц, находящихся на данный момент в памяти, причем

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

Суть алгоритма

часто востребуемой страницы - проверка бита R самой старой страницы.

Если R=0, значит, страница не только старая, но и невостребованная, поэтому она тут же удаляется. Если бит R =1, он сбрасывается, а страница помещается в конец списка страниц, и время ее загрузки обновляется, как будто она только что поступила в память. Затем поиск продолжается.

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

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

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

матрицу n Х n битов. При обращении к страничному блоку

k, аппаратно сначала устанавливаются все биты строки k в 1,а затем обнуляются все биты столбца k.

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

(Not Frequently Used)
Организуем программный счетчик для каждой страницы. При каждом

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

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

процессы начинают свою работу, не имея в памяти вообще никаких

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

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

глобальных дескрипторов процесса - по 8 Кбайт (213) сегментов каждого

типа, всего 16 Кбайт сегментов. Максимальный размер сегмента 4 Гбайт.

Каждый процесс при сегментной организации виртуальной памяти может работать в виртуально адресном пространстве размером 64 Тбайт.

сегментном режиме распределения памяти

таблица дескрипторов LDT
Система безопасности на основе привилегий
Аппаратные ограничения в

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

— бит разрешения записи в страницу;
 U — бит пользователь/супервизор;
 А —

признак имевшего место доступа к странице;
 D — признак модификации содержимого страницы;
 PWT и PCD — управляют механизмом кэширования страниц (введены начиная с процессора i486);
 AVL — резерв для нужд операционной системы (AVaiLable for use).

и стоимостью хранения данных, который за счет динамического копирования в

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

время доступа к кэш памяти
t - среднее время доступа в

системе с кэш-памятью
р –вероятность кэш-попадания

t = t1 (1-p) + t2 p = (t2 –t1 )p +t1

на одном с ним кристалле и входит в состав функциональных

блоков. В современных процессорах обычно кэш L1 разделен на два кэша, кэш команд (инструкций) и кэш данных (Гарвардская архитектура). Большинство процессоров без L1 кэша не могут функционировать. L1 кэш работает на частоте процессора, и, в общем случае, обращение к нему может производиться каждый такт. Зачастую является возможным выполнять несколько операций чтения/записи одновременно. Латентность доступа обычно равна 2−4 тактам ядра. Объём обычно невелик — не более 128 Кбайт.

L2-cache — кэш второго уровня, Второй по быстродействию. Обычно он расположен на кристалле, как и L1. В старых процессорах — набор микросхем на системной плате. Объём L2 кэша от 128 Кбайт до 1−12 Мбайт. В современных многоядерных процессорах кэш второго уровня, находясь на том же кристалле, является памятью раздельного пользования — при общем объёме кэша в nM Мбайт на каждое ядро приходится по nM/nC Мбайта, где nC количество ядер процессора. Обычно латентность L2 кэша, расположенного на кристалле ядра, составляет от 8 до 20 тактов ядра.

L3-cache Кэш третьего уровня наименее быстродействующий, но он может быть очень внушительного размера — более 24 Мбайт. L3 кэш медленнее предыдущих кэшей, но всё равно значительно быстрее, чем оперативная память. В многопроцессорных системах находится в общем пользовании и предназначен для синхронизации данных различных L2.

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

если b0=0 и b1=0
L1, если b0=0 и b1=1
L2, если b0=1

и b2=0
L3, если b0=1 и b2=1

v – бит действительности
b0, b1, b2 – биты обращения

совместного доступа нескольких процессов к одному и тому же сегменту

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


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