Кэш-память

Размещено на http://www.allbest.ru/

1. Кэш-память. Принципы действия кэш-памяти

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

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

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

Размещено на http://www.allbest.ru/

Рис.1 Принцип действия кэш-памяти

Содержание кэш-памяти представляет собой совокупность записей обо всех данных из основной памяти (ОП), загруженных в нее. (Рис.2)

Время доступа пропорционально вероятности попадания в кэш, которая составляет не менее 90%. Чем объясняется такая высокая степень попадания в кэш?

Рис.2 Содержание кэш-памяти

Высокая степень попадания в кэш объясняется некоторыми объективными свойствами компьютерных данных. К таким свойствам относятся:

Временная локальность

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

Пространственная локальность

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

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

Свойство пространственной локальности делает целесообразным копировать в кэш не одну единицу данных, а целый блок данных.

Рис.3 Алгоритм действия кэш-памяти

Проблема согласования данных

Две копии данных: в памяти и кэше порождает проблему согласования, т.е. версии данных в памяти и КЭШе в конечном итоге должны совпадать.

Применяется два подхода при записи в память:

Сквозная запись (write through) - если данные находятся в кэше, то запись производится и в кэш и в память.

Обратная запись (write back) - если данные находятся в кэше, то запись производится только в кэш и устанавливается признак модификации (в кэш).

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

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

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

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

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

Недостаток этого способа в больших временных затратах на поиск нужного элемента. Для преодоления недостатка применяется так называемый ассоциативный поиск, при котором сравнение выполняется параллельно со всеми записями кэша. (Рис. 4)

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

Рис.4 Ассоциативный поиск

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

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

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

Рис.5 Детерминированное отображение

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

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

Рис.5 Комбинированный способ отображения

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

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

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

Рис.7. Виртуальные адресные пространства нескольких процессов

Рис.8. Типы виртуальных адресных пространств

3. Алгоритмы распределения памяти

Рис.9 Основные методы распределения памяти

Алгоритмы распределения памяти без использования внешней памяти. Распределение памяти фиксированными разделами

Рис.10 Основные способы распределения памяти фиксированными разделами

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

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

Функции ОС:

-ведение таблиц свободных и занятых участков;

-поиск участка;

-загрузка и корректировка таблиц;

-после завершения процесса корректировка таблиц.

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

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

В этом методе разработчики попытались учесть достоинства и недостатки предыдущего.

Один из способов борьбы с фрагментацией - сжатие, таким образом, чтобы вся свободная память образовала непрерывную область - дефрагментация. Такой метод был применен в ранних версиях OS/2.

кэш память виртуальный данные

Рис.11 Распределение памяти перемещаемыми разделами

Недостаток - низкая производительность.

Алгоритмы распределения памяти с использованием внешней памяти

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

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

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

Такая подмена (виртуализация) оперативной памяти дисковой памятью существенно повышает уровень мультипрограммирования.

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

Для виртуализации применяются два основных подхода:

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

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

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

Страничное распределение

При страничном распределении виртуальная память делится на части одинакового и фиксированного для данной системы размера, называемыми виртуальными страницами. Вся оперативная память также делится на части такого же размера, называемые физическими страницами. Размер страницы выбирается равным степени двойки: 512, 1024, 4096 и т.д.

Рис. 12 Страничное распределение

где, таблица страниц - это внутренняя структура ОС. Адрес страницы входит в контекст процесса. Таблица страниц состоит из дескрипторов. Каждый дескриптор включает:

-номер физической таблицы;

-признак присутствия в ОЗУ (формируется аппаратно);

-признак модификации (формируется аппаратно);

-признак обращения (формируется аппаратно);

-виртуальный адрес, который представлен парой (p, sv) преобразуется в (n, sf).

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

Например. Если размер страницы = 1кб (210), то 50718 = 101 000 111 0012, 108=28 - номер страницы.

Схема обращения к физической памяти по виртуальному адресу при страничном распределении

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

Аппаратно, из регистра извлекается адрес таблицы страниц. На основании номера страницы Р и длины записи L, определяется адрес дескриптора (A=AT+P*L).

Из таблицы извлекается номер физической страницы N. К номеру N присоединяется смещение S.

Размер страниц, (часто 4096) влияет на размер таблиц, а это в свою очередь отражается на производительности. для устранения этого недостатка ВАП может делится на разделы, а в каждом разделе формируется своя таблица страниц. Этот вариант ускоряет поиск.

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

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

Разбиение адресного пространства на "осмысленные" части устраняет эти недостатки и называется сегментным распределением. Примеры сегментов: код программы, массив исходных данных и пр.

На этапе создания процесса, ОС создает таблицу сегментов процесса, аналогичную таблице страниц (рис.13).

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

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

где, физический адрес получается путем сложения по модулю 2.

К недостаткам сегментного распределения можно отнести следующие:

· Использование операции сложения при формировании физического адреса приводит к понижению производительности

· Избыточность. Т.к. сегмент в общем случае может быть больше страницы, то следовательно единица обмена между ОЗУ и диском более крупная, что приводит к замедлению работы.

Сегментное - страничное распределение

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

Виртуальная память делится на сегменты, а каждый сегмент - на страницы.

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

Рис.16. Схема преобразования виртуального адреса в физический при сегментно - страничном распределении

Размещено на Allbest.ru