Кэширование данных

1. Лекция 4. Кэширование данных.

2. Определение

Кэширование
–
это
способ
совместного
функционирования двух типов запоминающих устройств:
устройства отличаются временем доступа, объемом и
стоимостью хранения данных;
сущность метода: динамическое копирование в
«быстрое», но меньшее по объему ЗУ наиболее часто
используемой информации из «медленного», но более
объемного ЗУ
цели:
1.
2.
уменьшить среднее время доступа к данным
экономить более дорогую быстродействующую память.
Кэш-памятью, или кэшем, часто называют одно из
устройств - «быстрое» ЗУ
2

3. Основные положения

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

4. Содержимое записи кэш-памяти

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

5. Схема функционирования кэш-памяти

Медленный ответ
Источник запросов (кэш-промах)
к медленной
памяти
Запрос
Быстрая
память
Быстрый ответ
(кэш)
(кэш -попадание)
Медленная
память
Структура кэш-памяти
Адрес данных в
медленной памяти
Данные
Управляющая
информация
5

6. Понятия кэш-промаха и кэш-попадания

Если данные обнаруживаются в кэш-памяти, то есть
произошло кэш-попадание (сасhе-hit), они считываются из
нее и результат передается источнику запроса;
Если нужные данные отсутствуют в кэш-памяти, то есть
произошел кэш-промах (сасhе-тiss), они считываются из
основной памяти, передаются источнику запроса и
одновременно с этим копируются в кэш-память.
6

7. Вывод

Среднее время доступа к данным в системе с кэш-памятью
линейно зависит от вероятности попадания в кэш и
изменяется от среднего времени доступа в основное
запоминающее устройство (t1 при p=0) до среднего
времени доступа непосредственно в кэш-память t2 при
р=1.
Отсюда видно, что использование кэш-памяти имеет смысл
только при высокой вероятности кэш-попадания.
7

8. Высокое значение вероятности нахождения данных в кэш-памяти объясняется наличием:

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

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

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

10. Два подхода к решению проблемы согласования данных

Сквозная запись (write through). При каждом запросе к медленной
памяти, в том числе и при записи, просматривается кэш. Если данные
по запрашиваемому адресу отсутствуют, то запись выполняется
только в медленную память. Если же данные, к которым выполняется
обращение, находятся в кэше, то запись выполняется одновременно в
кэш и основную память.
Обратная запись (write back). При возникновении запроса к памяти
выполняется просмотр кэша, и если запрашиваемых данных там нет,
то запись выполняется только в медленную память. В противном же
случае запись производится только в кэш-память, при этом в
описателе данных делается специальная отметка (признак
модификации), которая указывает на то, что при вытеснении этих
данных из кэша (так называемом «сбросе кэша») необходимо
переписать их в медленную память, чтобы актуализировать
устаревшее содержимое этой медленной памяти.
10

11. Алгоритм работы кэш-памяти

1.
2.
3.
4.
5.
6.
7.
Выполнить запрос к медленной памяти.
Выполнить просмотр кэша.
Произошло кэш-попадание. Если да, то
перейти к шагу 4, если нет, то - к шагу 8.
Определить какая операция. Если
«чтение», то перейти к шагу 5, если
«запись» - к шагу 7.
Считать данные из кэша.
Передать данные источнику запроса.
Закончить алгоритм.
Определить режим согласования. Если
«сквозная запись», то произвести запись в
основную память и в кэш, иначе (т.е.
режим «обратной записи») – произвести
запись в кэш и установить признак
модификации. Закончить алгоритм.
11

12. Алгоритм работы кэш-памяти (продолжение – «кэш-промах»)

8.
9.
10.
11.
12.
13.
14.
Определить, какая операция: если «запись»,
то произвести запись в основную память и
закончить алгоритм; если «чтение», перейти
к шагу 9.
Произвести чтение из основной памяти.
Определить, есть ли свободное пространство
в кэше. Если да, то перейти к шагу 13, иначе
– к шагу 11.
Осуществить выбор данных на выгрузку и
объявить соответствующий элемент кэша
свободным.
Определить, были ли выгружаемые данные
модифицированы. Если да, то копировать
выгружаемые данные в основную память.
Копировать данные, считанные из основной
памяти в кэш.
Передать данные источнику запроса.
Закончить алгоритм.
12

13. Двухуровневая кэш-память

Запрос
Кэш 1
Кэш 2
ОП
13

14. Двухуровневая кэш-память (алгоритм работы)

Запрос
на чтение
Поиск в кэше 1
Да
Поиск в кэше 2
Да
Промах
Чтение из
медленной памяти
Копирование в
кэш 2
Промах
1?
Нет
Чтение из кэша 1
Нет
Запрос выполнен
Чтение из кэша 2
Копирование в кэш 1
Запрос выполнен
Запрос выполнен
14

15. ВЫВОДЫ

15

16.

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

17. Функциями ОС по управлению памятью в мультипрограммной системе являются:

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

18.

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

19.

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

20.

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

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

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

22.

сегментная виртуальная память предусматривает
перемещение данных сегментами — частями
виртуального адресного пространства произвольного
размера, полученными с учетом смыслового значения
данных
достоинства — «осмысленность» сегментов упрощает
их защиту;
недостатки — медленное преобразование адреса,
высокий уровень фрагментации;
сегментно-страничная виртуальная память сочетает
достоинства обоих предыдущих подходов.
22

23.

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

24.

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

25.

При кэшировании данных из оперативной памяти широко
используются две основные схемы отображения:
случайное отображение и детерминированное
отображение.
25

26.

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

27.

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