Принцип кешування даних

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

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

Часто кеш-пам’яттю називають „швидкий ЗП”. Його вартість більша, і він має порівняно невеликий об’єм. Механізм кеш-пам’яті прозорий (тобто програміст його не бачить). Програміст не повинен повідомляти ніякої інформації по інтенсивність використання даних і не повинен приймати участі у переміщенні даних з ЗП одного типу у ЗП іншого типу. Все це робиться автоматично системними засобами.

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

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

- ознаку модифікації;

- ознаку звертання до даних за деякий останній період часу.

Структура кеш-пам’яті

В системах з кеш-пам’яттю кожний запит до основної пам’яті виконується в такий спосіб:

1) Перегляд вмісту кеш-пам’яті з метою визначення, чи не знаходяться вже потрібні дані в кеш-пам’яті. Кеш-пам’ять не є адресованою, тому пошук потрібних даних виконується за вмістом значення поля “адреси в оперативній пам’яті”, яке береться із запиту.

2) Якщо дані є в кеш-пам’яті, то вони читаються з неї і результат передається в процесор.

3) Якщо потрібних даних в кеш-пам’яті нема, то вони разом із своєю адресою копіюються з основної пам’яті в кеш-пам’ять і результат виконання запиту передається в процесор.

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

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

Покажемо, що середній час доступу до даних залежить від ймовірності “попадання в кеш”. Припустимо, що маємо основний запам’ятовуючий пристрій із середнім часом доступу до даних t₁ та кеш-пам’ять, з середнім часом доступу t₂, зрозуміло, що t₂ < t₁.

Позначимо через t середній час доступу до даних в систем із кеш-пам’яттю, а через p – ймовірність попадання в кеш. За формулою повної ймовірності маємо:

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

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

В реальних системах ймовірність попадання в кеш складає приблизно 0,9. Таке велике значення ймовірності знаходження даних в кеш-пам’яті пов’язано з наявністю у даних об’єктивних властивостей:

- просторова локальність;

- часова локальність.

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

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

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