Кэш в СХД Кривых Алексей Зольников Павел Самунь Виктор IT Summer SPb 2012

Что такое кэш? Кэш – промежуточный буфер с быстрым доступом, содержащий информацию, которая может быть запрошена с наибольшей вероятностью 2

Терминология Вся кэш память разбивается на сегменты, размер одного сегмента равен размеру страйпа На рисунке A1 A2 A3 A p A q - страйп 3

Классификация сегментов Чистые сегменты – сегменты, содержащие копию данных, хранимых на диске Грязные сегменты – сегменты, содержащие данные, более новые, чем на диске Пустые Используемые 4

Чтение Кэш попадание – ситуация, когда запрашиваемые данные есть в кэше Кэш промах – ситуация, обратная к кэш попаданию 5

Чтение (look through) t = t cache + t disk 6

Чтение (look aside) t = min {t cache, t disk } 7

Запись (write through) 8

Запись (write back) + : скорость - : безопасность 9

Задача Разработать действующую модель кэша СХД AVRORA для измерения эффективности работы отдельных ее компонент – Реализация модели – Верификация модели Попытаться ускорить работу системы кэширования -Вытеснение сегментов кэша 10

Поиск в кэше При чтении, сначала происходит поиск данных в кэше Для этого в кэше ищется адрес данных на диске Какую структуру данных использовать для хранения адресов? 11

Вытеснение сегментов кэша Рано или поздно пустые сегменты кончатся При записи новых данных в кэш необходимо вытеснить старые Необходимо определить правило, по которому будет происходить вытеснение 12

Алгоритмы вытеснения LRU (Least Recently Used) LRU\k MRU (Most Recently Used) LFU (Least Frequently Used) ARC (Adaptive Replacement Cache) … 13

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