Ієрархія запам'ятовуючих пристроїв.
Пам'ять обчислювальної машини являє собою ієрархію запам'ятовуючих пристроїв (внутрішні регістри процесора, різні типи сверхоперативной і оперативної пам'яті, диски, стрічки), що відрізняються середнім часом доступу і вартістю збереження даних у розрахунку на один біт (малюнок ). Користувачу хотілося б мати і недорогу і швидку пам'ять. Кеш-пам'ять представляє деяке компромісне рішення цієї проблеми. thumb|300px|
Кеш-пам'ять — це спосіб організації спільного функціонування двох типів запам'ятовуючих пристроїв, що відрізняються часом доступу і вартістю збереження даних, що дозволяє зменшити середній час доступу до даних за рахунок динамічного копіювання в "швидке" ЗУ найбільше часто використовуваної інформації з "повільного" ЗУ. Кеш-пам'яттю часто називають не тільки спосіб організації роботи двох типів запам'ятовуючих пристроїв, але й один із пристроїв — "швидке" ЗУ. Воно коштує дорожче і, як правило, має порівняно невеликий обсяг. Важливо, що механізм кеш-пам'яті є прозорим для користувача, що не повинний повідомляти ніякої інформації про інтенсивність використання даних і не повинний ніяк брати участь у переміщенні даних із ЗУ одного типу в ЗУ іншого типу, усе це робиться автоматично системними засобами. Розглянемо окремий випадок використання кеш-пам'яті для зменшення середнього часу доступу до даних, що зберігається в оперативній пам'яті. Для цього між процесором і оперативною пам'яттю міститься швидке ЗУ, називане просто кеш-пам'яттю (малюнок). У якості такого може бути використана, наприклад, асоціативна пам'ять. Уміст кеш-пам'яті являє собою сукупність записів про всіх завантажених у неї елементах даних. Кожен запис про елемент даних містить у собі адресаа, що цей елемент даних має в оперативній пам'яті, і керуючу інформацію: ознака модифікації й ознака звертання до даних за деякий останній період часу.
У системах, оснащених кеш-пам'яттю, кожен запит до оперативної пам'яті виконується у відповідності з наступним алгоритмом: Проглядається вміст кеш-пам'яті з метою визначення, чи не знаходяться потрібні дані в кеш- пам'яті; кеш-пам'ять не є адресуемой, тому пошук потрібних даних здійснюється по вмісту — значенню поля "адресу в оперативній пам'яті", узятому з запиту. Якщо дані виявляються в кеш-пам'яті, то вони зчитуються з її, і результат передається в процесор. Якщо потрібних даних ні, то вони разом зі своєю адресою копіюються з оперативної пам'яті в кеш-пам'ять, і результат виконання запиту передається в процесор. При копіюванні даних може виявитися, що в кеш-пам'яті немає вільного місця, тоді вибираються дані, до яких в останній період було найменше звертань, для витиснення з кеш-пам'яті. Якщо витісня дані були модифіковані за час перебування в кеш-пам'яті, то вони листуються в оперативну пам'ять. Якщо ж ці дані не були модифіковані, то їхнє місце в кеш-пам'яті з'являється вільним. На практиці в кеш-пам'ять зчитується не один елемент даних, до якого відбулося звертання, а цілий блок даних, це збільшує імовірність так називаного "влучення в кэш", тобто перебування потрібних даних у кеш-пам'яті. Покажемо, як середній час доступу до даних залежить від імовірності влучення в кэш. Нехай є основне запам'ятовуючі пристрій із середнім часом доступу до даних t1 і кеш-пам'ять, що має час доступу t2, мабуть, що t2<t1. Позначимо через t середній час доступу до даних у системі з кеш- пам'яттю, а через p -імовірність влучення в кэш. По формулі повної імовірності маємо:
t = t1((1 — p) + t2*p
З її видно, що середній час доступу до даних у системі з кеш-пам'яттю лінійно залежить від імовірності влучення в кэш і змінюється від середнього часу доступу в основне ЗУ (при р=0) до середнього часу доступу безпосередньо в кеш-пам'ять (при р=1). У реальних системах імовірність влучення в кэш складає приблизно 0,9. Високе значення імовірності перебування даних у кеш-пам'яті зв'язано з наявністю в даних об'єктивних властивостей: просторової і тимчасової локальності. • Просторова локальність. Якщо відбулося звертання по деякій адресі, то з високим ступенем імовірності найближчим часом відбудеться звертання до сусідніх адрес. • Тимчасова локальність. Якщо відбулося звертання по деякій адресі, то наступне звертання по цій же адресі з великою імовірністю відбудеться найближчим часом. Усі попередні міркування справедливі і для інших пар запам'ятовуючих пристроїв, наприклад, для оперативної пам'яті і зовнішньої пам'яті. У цьому випадку зменшується середній час доступу до даних, розташованим на диску, і роль кеш-пам'яті виконує буфер в оперативній пам'яті.
