Ієрархія запам'ятовуючих пристроїв. Кешування даних

Всю пам'ять обчислювальної машини можна представити у вигляді дерева запам'ятовуючих пристроїв рис. 17, що відрізняються середнім часом доступу і вартістю збереження даних у розрахунку на один біт. Для ефективного використання обчислювальних ресурсів необхідна наявність швидкої пам'яті, одночасно з доступною вартістю. Кеш-пам'ять представляє деяке компромісне вирішення цієї проблеми.

Рис. 17. Ієрархія запам’ятовуючих пристроїв

Кеш-пам'ять — спосіб організації спільного функціонування двох типів запам'ятовуючих пристроїв, що відрізняються часом доступу, вартістю збереження даних, для зменшення середнього часу доступу до даних за рахунок динамічного копіювання в "швидкий" запам’ятовуючий пристрій найбільш часто використовуваної інформації з "повільного" запам’ятовуючого пристрою.

Кеш-пам'яттю часто називають не тільки спосіб організації роботи двох типів запам'ятовуючих пристроїв, але й пристрій швидкого запам'ятовування. Він коштує дорожче і, як правило, має порівняно невеликий обсяг.

Розглянемо окремий випадок використання кеш-пам'яті для зменшення середнього часу доступу до даних, що зберігається у зовнішній пам'яті. Для цього між процесором і зовнішньою пам'яттю розміщується швидкий запам’ятовуючий пристрій, кеш-пам'ять. Вміст кеш-пам'яті являє собою сукупність записів про всі завантажені в неї елементи даних. Кожен запис про елемент даних містить у собі адресу цього елементу даних в оперативній пам'яті, і управляючу інформацію: ознака модифікації й ознака звертання до даних за деякий останній проміжок часу.

У системах, обладнаних кеш-пам'яттю, кожен запит до оперативної пам'яті виконується у відповідності з наступним алгоритмом:

1) переглядається вміст кеш-пам'яті з метою визначення, чи не знаходяться потрібні дані в кеш-пам'яті; кеш-пам'ять не адресується, тому пошук потрібних даних здійснюється по вмісту - значенню поля "адреси в оперативній пам'яті", узятому з запиту; 2) якщо дані виявляються в кеш-пам'яті, то вони зчитуються з неї, результат передається процесору; 3) якщо потрібних даних немає, то вони копіюються з оперативної пам'яті в кеш-пам'ять, і результат виконання запиту передається процесору;

При копіюванні даних може виявитися, що в кеш-пам'яті відсутнє вільне місце, тоді, для витіснення з кеш-пам'яті обираються дані, до яких в останній період було найменше звертань. Якщо витіснені дані були модифіковані за час перебування в кеш-пам'яті, то вони переміщаються в оперативну пам'ять. Якщо ж ці дані не були модифіковані, то їх місце в кеш-пам'яті звільняється.

На практиці у кеш-пам'ять зчитується не один елемент даних, до якого відбулося звертання, а цілий блок даних, це збільшує ймовірність так званого “влучання у кеш”, тобто перебування потрібних даних у кеш-пам'яті.

Покажемо, як середній час доступу до даних залежить від ймовірності влучання у кеш. Нехай маємо основний запам'ятовуючий пристрій із середнім часом доступу до даних t₁ і кеш-пам'ять, що має час доступу t₂, відповідно t₂<t₁. Позначимо через t середній час доступу до даних у системі з кеш-пам'яттю, а через p - імовірність влучання у кеш. Відповідно до формули повної імовірності:

t = t₁((1 - p) + t₂(1-p)

З неї видно, що середній час доступу до даних у системі з кеш-пам'яттю лінійно залежить від імовірності влучання у кеш і змінюється від середнього часу доступу до основного запам’ятовуючого пристрою (при р=0) до середнього часу доступу безпосередньо до кеш-пам'яті (при р=1). У реальних системах імовірність влучання у кеш складає приблизно 0,9. Високе значення імовірності перебування даних у кеш-пам'яті пов'язано з наявністю в даних об'єктивних властивостей: просторової і часової локальності.

Просторова локальність. Якщо відбулося звертання до деякої адреси, то існує досить велика ймовірність, що найближчим часом відбудеться звертання до сусідніх адрес.

Часова локальність. Якщо відбулося звертання до деякої адреси, то існує досить велика ймовірність, що наступне звертання до цієї ж адреси відбудеться найближчим часом.

Рис. 18. Організація дискової кеш-пам'яті

Усі попередні викладки справедливі і для інших пар запам'ятовуючих пристроїв, наприклад, оперативна пам'ять-зовнішня пам'ять, у цьому випадку зменшується середній час доступу до даних, розташованих на диску, і функцію кеш-пам'яті виконує буфер в оперативній пам'яті (рис. 18).