24. Способы отображения основной памяти на кэш.

Существует два основных способа отображения: случайное и детерминированное.

Случайное

Элемент памяти находится в произвольном месте кэша. Элемент хранится вместе с адресом. Поиск ведется по адресу. Это сравнительно дорогой способ.

Детерминированный

Элемент памяти отображается всегда в одно и тоже место кэша. Строки кэша и элементы памяти соотносятся как “один ко многим”. Преобразование адреса элемента в номер строки кэша выполняется некоторой функцией. Этот способ более дешевый.

Случайное отображение

Недостаток этого способа в больших временных затратах на поиск нужного элемента.

Для преодоления недостатка применяется так называемый ассоциативный поиск, при котором сравнение выполняется параллельно со всеми записями КЭШа.

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

Детерминированное отображение

Ранее было сказано что при этом способе используется функция преобразования адреса памяти в адрес КЭШа. В качестве отображающей функции часто используется часть разрядов адреса из ОП. Такой способ часто называется прямым

Например, пусть кэш содержит 1024 (210) записей, тогда в адресе можно выделить 10 разрядов. Это и будет номер строки в КЭШе. Замещение в КЭШе происходит при совпадении адресов.

Комбинированный способ

Этот способ представляет собой компромисс между низкой стоимостью кэша с прямым отображением и гибкостью более дорогого способа со случайным отображением (Рис. 6).

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

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

Системная и пользовательская части ВАП (по 2 Гб каждая).

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

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

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

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

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

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

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

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

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

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

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

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

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

При выборе блока для выгрузки на диск могут быть использованы следующие стратегии замещения (выталкивания):

- первый попавшийся блок (random);

- дольше всего находящийся в памяти блок (правило FIFO);

- наименее часто использовавшийся блок (правило LFU);

- дольше всего не использовавшийся блок (правило LRU);

- не использовавшийся в последнее время блок (правило NUR).

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

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

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

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

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