44. Иерархия памяти. Локальность.
Иерархия памяти вычислительной системы представляет многоуровневую структуру.
При работе процессор пытается использовать данные с более высоких уровней. Предполагается, что данные, находящиеся на более высоком уровне, дублируются на более низком уровне.
Скорость доступа к данным возрастает к верху иерархии, объемы уменьшаются, следовательно, стоимость каждого бита информации вверху пирамиды значительно выше, чем внизу.
Если данные не находятся на верхнем уровне, то ищутся на более низком, при этом работа процессора с каждым уровнем будет все медленней и медленней.
Данные, находящиеся ниже оперативной памяти, не могут обрабатываться без размещения в оперативную память, т.е. их необходимо копировать на более высокий уровень с более низкого.
Для обеспечения целостности данных, в дальнейшем данные с более высокого уровня должны в новом измененном виде быть скопированы на более низкий уровень.
Локальность – свойство реальных программ, согласно которому в течении небольшого периода времени процесс использует небольшое количество страниц логического пространства.
45. Понятие физического и виртуального адреса. Связывание адресов. Физическая память представляет собой линейную последовательность ячеек в памяти. В многозадачной системе сложно организовать работу процессов, если они все будут работать в физ. адресном пространстве, т.е. оперировать на прямую физ. адресами. Поэтому ОС представляет абстракцию между процессом и физической памятью, логическое адресное пространство. Процессы могут работать в едином логическом адресном пространстве, но в современных ОС каждый процесс оперирует своим логическим адресным пространством. Алгоритм процесса оперирует адресами линейного пространства от 0 и выше, которые при работе преобразовываются в адреса физ. пространства. Это преобразование называют связыванием или трансляцией адреса. Связывание может производиться: 1) Во время компиляции. При компиляции, переменные заменяются не на относительные логические адреса, а на абсолютные физические. В следствие чего может быть загружена по одному конкретному адресу в памяти. Дальнейшего преобразования адреса уже не требуется. Нед-ток: нескольким процессам может понадобиться загрузка в одну и ту же область в памяти, в таком случае они совместно работать не смогут. 2) Во время запуска. В процессе компиляции, переменные заменяются на относительные логические адреса. Процесс может быть загружен в любое место в памяти. При запуске, каждая относительное значение адреса заменяется на абсолютное значение физ. адреса. Недостаток: в дальнейшем процесс не может быть перемещен в памяти. После свопинга должен быть загружен обратно в то же место. 3) В процессе выполнения. При запуске образ процесса загружается в память в неизменном виде со всеми относительными адресными ссылками. При каждом обращении по лог. адресу, производится трансляция этого адреса в физический абсолютный. Достоинства: процесс может безболезненно перемещаться в памяти во время работы. Недостаток: замедление работы в следствие преобразования адреса при каждом обращении. Недостаток нивелируется использованием устройства MMU (устройство управления памятью), которое непосредственно участвует в трансляции адреса.
46. Статическое распределение памяти: разделы с фиксированными границами. Каждый процесс получает ровно столько памяти, сколько ему необходимо, тем самым физическое адресное пространство делится на фиксированные разделы различной длины. В процессе функционирования системы эти разделы начинают освобождаться и в них могут размещаться новые процессы. Возможна ситуация, когда суммарный объем свободных разделов велик, но раздела способного уместить новый процесс - нет. Этот недостаток называется внутренняя фрагментация. Решением проблемы является уплотнение памяти, но для этого должен использоваться перемещаемый код и связывание на этапе выполнения. Стратегии выделение свободного раздела новому процессу:
Best Fit(самая подходящая). Выделяется раздел максимально похожий по размеру на необходимый процессу объем. При этом, останется свободным минимум пространства. А значит минимизируются потери от фрагментацию.
Worth Fit(хуже всего подходящая). Выделяется тот раздел, в котором останется больше всего места. В результате большие объемы свободного места разбиваются между нескольким процессами, тем самым минимизируя потери от фрагментации.
Random Fit. Процесс размещается в первом подходящем по размеру пространстве. С точки зрения фрагментации best fit работает лучше, чем worth fit. Random хуже всех, но за счет отсутствия поиска наиболее или наименее подходящего, Random fit функционирует более производительно чем первые две стратегии.
47. Статическое распределение памяти: один процесс в памяти. Все доступное для прикладных процессов адресное пространство выделяется одному процессу, при этом размеры логического пространства не могут превышать размеры логического. При необходимости запуска других процессов, процесс должен из памяти выгружаться.
48. Динамическое распределение памяти: разделы с подвижными границами. Уплотнение памяти. Свопинг. Страничная память. Физ. адресное пространство разбивается на фреймы одинакового размера. Лог. пространство процесса разбивается на участи такого же размера, который называется страницами. Страницы всех процессов размещаются в свободных фреймах физической памяти, причем необязательно по порядку. Адрес в логическом адресном пространстве представляет собой пару чисел «номер страницы»: «смещение внутри страницы». Каждый процесс содержит табл. страниц, кот. указывает соответствие лог. страниц и физ. фреймов+ некоторая служебная информация. При каждом обращении к памяти по номеру страницы из таблицы страниц выбирается номер физического фрейма, после чего зная номер и размер фрейма а также смещение вычисляется адрес физической ячейки, к которой происходит обращение. Дос-ва: +Минимизация фрагментации: чем меньше страниц тем меньше фрагментация, но тем больше объем таблиц страниц. Чем больше размер страницы, тем меньше таблицы страниц, тем больше фрагментация. -Многоуровневые таблицы страниц. Каждому процессу соответствует не одна таблица страниц а несколько, адрес побитно содержит сначала номер страницы второго уровня, потом номер строки в этой странице, потом смещение. При связывании адреса из таблицы первого уровня получается адрес фрейма в котором хранится нужная таблица второго уровня, а уже в ней по номеру страницы получается адрес фрейма. +Уменьшение используемой памяти для таблиц страниц –Инвер-ная таблица страниц. Вместо табл. страниц каждого процесса есть одна общая таблица с соответствием фреймов и страниц процессов, которые находятся в этих фреймах. Благодаря этому объем памяти для таблиц знач. уменьшается, но поскольку эта табл. отсортирована по номерам фреймов, то поиск нужного фрейма по номеру страницы затруднен. Для улучшения может использоваться хеширование.
49. Сегментная организация памяти. Логическое адресное пространство разбивается на участки по смыслу, называемые сегментами, обычно это сегменты данных, кода, стека и т.д. Каждый сегмент отображается в свободном месте свободного адресного пространства. Поскольку нет разбиения адресного пространства на равные участки, то появляется проблема фрагментации физического пространства. Логический адрес представляет собой пару чисел «номер сегмента»: «смещение». По номеру сегмента из таблицы сегментов процесса получается адрес его начала в физической памяти с добавлением смещения этого адреса получается номер физической ячейки.
50. Страничная организация памяти. Страничная организация памяти. Логическое адресное пространство разбивается на страницы. Смысл в том, чтобы найти свободный фрейм для каждой страницы. Физическое адресное пространство разбивается на фреймы или кадры одинакового размера. Логическое пространство процесса разбивается на участки такого же размера, которые называются страницами. Страницы всех процессов размещаются в свободных фреймах физической памяти. Причем, необязательно по порядку. Адрес в логическом адресном пространстве представляет собой пару чисел номер страницы:смещение внутри этой страницы. Каждый процесс содержит таблицу страниц, в которой указывается соответствие логических страниц и физических фреймов, а также некоторая служебная информация относительно каждой страницы. Получается, что для каждого процесса есть эта таблица P:F. По этой таблице страниц и получается физический адрес. При каждом обращении к памяти по номеру страницы из таблицы страниц выбирается номер физического фрейма, после чего, зная номер и размер фрейма, а также смещение и размер фрейма, вычисляется адрес физической ячейки, к которой происходит обращение. Физ. адрес: (f-1)*f+d. Достоинства страничной организации: минимизация фрагментации. Причем, чем меньше размер страницы, тем меньше будут потери. Чем меньше размер страницы, тем меньше фрагментация, но тем больше объем таблиц страниц. Чем больше размер страницы, тем меньше таблицы страниц, но тем больше фрагментация.
Таблицы страниц: одноуровневые, многоуровневые, инвертированные. Одноуровневые: адрес в логическом адресном пространстве представляет собой пару чисел номер страницы: смещение внутри этой страницы. Каждый процесс содержит таблицу страниц, в которой указывается соответствие логических страниц и физических фреймов, а также некоторая служебная информация относительно каждой страницы. Получается, что для каждого процесса есть эта таблица P:F. По этой таблице страниц и получается физический адрес. При каждом обращении к памяти по номеру страницы из таблицы страниц выбирается номер физического фрейма, после чего, зная номер и размер фрейма, а также смещение и размер фрейма, вычисляется адрес физической ячейки, к которой происходит обращение. Физ. адрес: (f-1)*f+d.
Многоуровневые: Каждому процессу соответствует не одна таблица страниц, а несколько. Адрес побитно содержит сначала номер страницы второго уровня, потом номер строки в этой странице, потом смещение. При связывании адреса из таблицы первого уровня получается адрес фрейма, в котором хранится нужная таблица второго уровня, а уже в ней по номеру страницы получается адрес фрейма. Достоинства: уменьшение используемой памяти для таблиц страниц.
Инвертированные: вместо таблиц страниц каждого процесса есть одна общая таблица с соответствием фреймов и страниц процесса, которые находятся в этих фреймах. Благодаря этому объем памяти, использующейся для таблиц, значительно уменьшается. Но, поскольку эта таблица отсортирована по номерам фреймов, то поиск нужного фрейма по номеру страницы затруднен. Для облегчения может использоваться хеширование.
Сегментно-страничная организация памяти. Логическое пространство процесса разбивается по смыслу на сегменты, каждый из которых разбивается на страницы одинакового размера. Страницы отображаются в фреймах физического пространства. Логический адрес представляет собой тройку чисел:
1) номер сегмента, по которому получается его таблица страниц
2) номер страницы, по которой получается номер фрейма, в которой она отображена.
3) смещение внутри страницы, с использованием которого получается адрес физической ячейки.
Достоинства: осмысленность разбиения на сегменты сочетается с отсутствием фрагментации страничного подхода.
Понятие виртуальной памяти. Страничный механизм трансляции. Виртуальная память, в отличие от свопинга, позволяет отображать в физической памяти в физическом адресном пространстве только некоторую часть логического адресного пространства процесса, загружая и выгружая нужные части по необходимости.
Достоинства: логическое пространство процесса может быть значительно больше, чем физическая память, и практически не ограничивается по размеру. Увеличивается число процессов, которые могут одновременно отображаться в физическую память.
Недостаток: возможная потеря производительности из-за необходимости периодической загрузки и выгрузки частей процесса во вторичную память (на жесткий диск).
Страничное нарушение (page fault) – это исключение, происходящее при обращении процесса к ячейке памяти, принадлежащей той части логического адресного пространства, которая в данный момент не отображена в физическую память. Виртуальная память может реализовываться страничной или сегментно-страничной схемой, поэтому страничное нарушение происходит при обращении к странице, которой нет в физической памяти. Локальность – это свойство реальных программ, согласно которому в течение небольшого периода времени процесс использует небольшое количество страниц логического пространства.
Рабочее множество процесса (working set) – это набор виртуальных страниц, к которым, согласно свойству локальности, процесс будет обращаться в ближайшее время. С течением времени рабочее множество изменяется качественно, не сильно меняясь количественно.
Резидентное множество процесса – набор физических фреймов, выделенных процессу. Соответствие между логической страницей и физическим фреймом фиксируется в таблице страниц процесса, каждая запись которой содержит также биты доступа, бит модификации, счетчик обращений (необязательный).
Строка обращений – это последовательность страниц, к которым в течение жизнедеятельности обращается процесс.
Трэшинг (thrashing) – пробуксовка – ситуация, при которой процессор тратит значительно больше времени на организацию загрузки-выгрузки страниц, чем на выполнение кода.
pf
n
При появлении трэшинга приходится увеличивать размер резидентного множества процесса, уменьшая количество фреймов, выделенных другим процессом. Вследствие этого попытка избежать трэшинга для одного процесса может привести к трэшингу других. Подсистема управления виртуальной памятью вынуждена постоянно следить за резидентными и рабочими множествами, изменять их параметры и используемые алгоритмы во избежание трэшинга.
СТРАНИЧНЫЙ МЕХАНИЗМ ТРАНСЛЯЦИИ
Стратегии управления виртуальной памятью. 1. Стратегия подкачки. Заключается в следующем, когда загружать в физическую память логические страницы и в каком количестве. Варианты: 1) по запросу страница загружается только тогда, когда к ней производится обращение. 2) подкачка с упреждением. Наряду с запрошенной страницей, загружается также несколько соседних. Поскольку предполагается, что согласно свойству локальности в ближайшее время будут обращения и к ним тоже. Поскольку размер блока чтения-записи на жесткий диск обычно в несколько раз превышает размер страницы, то используется подкачка с упреждением: за один цикл чтения загружается несколько страниц.
2. Стратегия размещения. Заключается в следующем: куда загрузить новую страницу. Загружаемые страницы размещаются в любом свободном физическом фрейме.
3. Стратегия замещения. Заключается в следующем: какую страницу из загруженных можно выгрузить во вторичную память для того, чтобы освободить место для новой страницы. Процесс замещения заключается в следующем: при страничном нарушении управление передается менеджеру страниц, который определяет необходимость выгрузки какой-либо страницы. После этого, согласно алгоритму замещения, выбирает страницу, которая будет выгружена. Определяет, модифицировалась ли эта страница. Если да, то перезаписывает её во вторичной памяти. После этого загружает новую страницу, соответствующим образом изменяет таблицу страниц процесса и возвращает управление процессу в ту же команду, которая вызвала страничное нарушение.
Дисциплины замещения страниц: FIFO. Алгоритм FIFO ассоциирует с каждым сегментом время, когда он был помещен в память. Для замещения выбирается наиболее старый сегмент. Учет времени необязателен, когда все сегменты в памяти связаны в FIFO-очередь и каждый помещаемый в память сегмент добавляется в хвост этой очереди. Алгоритм учитывает только время нахождения сегмента в памяти, но не учитывает фактическое использование сегментов.
Например, первые загруженные сегменты программы могут содержать переменные, используемые на протяжении работы всей программы. Это приводит к немедленному возвращению к только что замещенному сегменту.
Недостаток алгоритма: самая старая страница может быть одной из самых используемых, а, значит, в ближайшее время будут к ней обращения и страничные нарушения.
Дисциплины замещения страниц: оптимальный алгоритм
Выталкивается та страница, обращений к которой не будет в течение максимального времени.
На момент возникновения ошибки отсутствия страницы в памяти находится определенный набор страниц. К некоторым из этих страниц будет осуществляться обращение буквально из следующих команд (эти команды содержатся на странице). К другим страницам обращения может не быть и через 10, 100 или, возможно, даже через 1000 команд. Каждая страница может быть помечена количеством команд, которые должны быть выполнены до первого обращения к странице.
Оптимальный алгоритм замещения страниц гласит, что должна быть удалена страница, имеющая пометку с наибольшим значением. Если какая-то страница не будет использоваться на протяжении 8 миллионов команд, а другая какая-нибудь страница не будет использоваться на протяжении 6 миллионов команд, то удаление первой из них приведет к ошибке отсутствия страницы, в результате которой она будет снова выбрана с диска в самом отдаленном будущем. Компьютеры, как и люди, пытаются по возможности максимально отсрочить неприятные события.
Единственной проблемой такого алгоритма является невозможность его реализации. К тому времени, когда произойдет ошибка отсутствия страницы, у операционной системы не будет способа узнать, когда каждая из страниц будет востребована в следующий раз. Тем не менее при прогоне программы на симуляторе и отслеживании всех обращений к страницам появляется возможность реализовать оптимальный алгоритм замещения страниц при втором прогоне, воспользовавшись информацией об обращении к страницам, собранной во время первого прогона.