Дуже важливою, специфічною формою буферизації є кешування . Цей термін означає використання порівняно невеликий за обсягом, але швидкодіючої пам'яті для того, щоб зменшити кількість звертань до більш повільної пам'яті великого обсягу.
Ідея кешування грунтується на так званій гіпотезі про локальності посилань. Ця гіпотеза полягає в наступному. Якщо в якийсь момент часу відбулося звернення до певної ділянки даних, то найближчим часом можна з високою ймовірністю очікувати повторення звернень до тих же самим даними або ж до сусідніх ділянок даних. Звичайно, локальність посилань не можна вважати законом, однак практика показує, що ця гіпотеза виправдовується для переважної більшості програм.
У сучасних обчислювальних системах може використовуватися кілька рівнів кешування. В даному курсі не розглядається апаратний кеш процесора, що дозволяє скоротити число звернень до основної пам'яті за рахунок використання швидкодіючих регістрів. До роботи ОС більш пряме відношення має програмне кешування пристроїв довільного доступу (дискових накопичувачів). У цьому випадку гіпотезу про локальності посилань можна переформулювати більш конкретно: якщо програма виконала читання або запис даних з деякого блоку диска, то досить імовірно, що в недалекому майбутньому послідують ще операції читання або запису даних з того ж блоку.
У ролі швидкодіючої пам'яті (кешу) тут виступає масив буферів, розміщений в системній пам'яті. Кожен буфер складається із заголовка і блоку даних, відповідного за розміром блоку (сектору) диска. Тема буфера містить адресу блоку диска, копія якого в даний момент міститься в буфері, і кілька прапорів, що характеризують стан буфера.
Коли система одержує запит на читання або запис певного блоку даних диска, вона перш за все перевіряє, не міститься в даний момент копія цього блоку в одному з буферів кеша. Для цього потрібно виконати пошук за заголовками буферів. Якщо блок знайдений в кеші, то звернення до диска виконуватися не буде. Замість цього дані читаються з буфера або, відповідно, записуються в буфер. У разі запису даних слід також у заголовку буфера відзначити за допомогою спеціального прапора, що буфер став «брудним», тобто його вміст не відповідає даним на диску.
Якщо необхідний блок диска не знайдений в кеші, то для нього повинен бути виділений буфер. Проблема в тому, що загальна кількість буферів кеша обмежена. Щоб віддати один з них під необхідний блок, треба «витіснити» з кешу один з блоків, які там зберігалися. При цьому, якщо витісняється блок «брудний», то він повинен бути «очищений», тобто записаний на диск. При витісненні «чистого» блоку ніяких операцій з диском виконувати не треба.
Який з блоків, що зберігаються в кеші, слід вибрати для витіснення, щоб скоротити загальну кількість звернень до диска? Це вкрай важливе питання, і якщо він буде вирішуватися неправильно, то вся робота системи може загальмуватися через постійні звернень до диска.
Є теоретично оптимальне рішення даної задачі, яке полягає в наступному. Число звернень до диска буде мінімально, якщо кожного разу вибирати для витіснення той блок даних, до якого в майбутньому найдовше не буде звернень. На жаль, скористатися цим правилом на практиці неможливо, оскільки послідовність звернень до блоків диска непередбачувана. Даний теоретичний результат корисний тільки як недосяжний ідеал, з яким можна порівнювати результати застосування більш реалістичних алгоритмів вибору.
Серед алгоритмів, використовуваних на практиці, найкращим вважається алгоритм LRU (Least Recently Used, у вільному перекладі «давно не використовувався»). Він полягає в наступному: вибирати для витіснення слід той блок, до якого найдовше не було звернень. Тут як раз використовується принцип локальності посилань: раз звернень давно не було, то, ймовірно, їх і не буде найближчим часом.
Як на практиці реалізується вибір блоку за правилом LRU? Очевидне рішення - при кожному зверненні до буферу записувати в його заголовку поточний час, а при виборі для витіснення шукати саму ранню запис - занадто громіздко і повільно. Є набагато краща можливість.
Всі буфери кеша зв'язуються в лінійний список. У заголовку кожного буфера зберігається посилання на наступний по порядку списку буфер (фактично зберігається індекс цього буфера в масиві буферів). При кожному зверненні до блоку даних для читання або запису виконується також переміщення відповідного буфера в кінець списку. Це не означає переміщення даних, що зберігаються в буфері, змінюються лише кілька посилань в заголовках.
В результаті постійного переміщення використаних блоків в кінець списку буферів цей список виявляється відсортованим за зростанням часу останнього звернення. На початку списку виявляється той буфер, до даних якого найдовше не було звернень. Він-то нам і потрібен як кандидат на витіснення.
2-3 показаний масив буферів, пов'язаний в список.
Рис. 1‑3
Тепер про «брудні» буферах. У яких випадках повинна виконуватися їх «очищення», тобто запис блоку даних з кеш-буфера на диск? Можна назвати три таких випадки.
· Вибір блоку для витіснення з кешу.
· Закриття файлу, до якого відносяться «брудні» блоки. Загальноприйнято, що при закритті файлу повинна виконуватися його збереження на диску.
· Операція примусового очищення всіх буферів або тільки буферів, що відносяться до певного файлу. Подібна операція може виконуватися для підвищення надійності зберігання даних, як страховка від можливих збоїв. В ОС UNIX, наприклад, очищення всіх буферів традиційно виконується кожні 30 с.
Слід визнати, що кешування операцій запису на диск, на відміну від кешування читання, завжди створює певну небезпеку втрати даних. У разі випадкового збою системи, відключення живлення і т.п. може виявитися, що важлива інформація, яку слід було записати на диск, застрягла в брудних буферах кеша і була тому втрачена. [3] Це неминуча плата за значне підвищення продуктивності системи. Програми, що вимагають високої надійності роботи з даними (наприклад, банківські програми), зазвичай записують дані прямо на диск. При цьому кеш або не використовується взагалі, або в кеш-буфер заноситься копія даних, яка може стати в нагоді при подальших операціях читання.
«Вузьким місцем» кешування дисків є пошук необхідного блоку даних в кеші. Як було описано вище, для цього система переглядає заголовки буферів. Якщо кеш складається з декількох сотень буферів, час пошуку буде відчутно. Один з можливих прийомів прискорення пошуку, використовуваний в UNIX, показаний на рис. 2-4.
Рис. 1‑4
В UNIX кожен кеш-буфер може входити одночасно в два лінійних списку. Один з них, званий «списком вільних блоків», це знайомий нам LRU-список, використовуваний для визначення блоку, що підлягає витісненню. Слово «вільний» не означає «порожній»; в даному випадку це слово означає блок, не зайнятий у поточний момент в операції читання / запису, виконуваної якимось процесом. Інший список називається «хеш-ланцюжком» і використовується для прискорення пошуку потрібного блоку.
При запису в буфер даних, відповідних деякого блоку диска, номер хеш-ланцюжка, в яку буде поміщений цей буфер, визначається як залишок від ділення номера блоку на N - кількість хеш-ланцюжків. Для наочності на малюнку прийнято значення N = 10. Таким чином, блоки з номерами 120, 40, 90 потрапляють в ланцюжок 0, блоки 91, 1, 71 - в ланцюжок 1 і т.д. Коли система шукає в кеші блок з певним номером, вона перш за все за номером блоку визначає, в якій з хеш-ланцюжків цей блок повинен знаходитися. Якщо блоку немає в цьому ланцюжку, то його взагалі немає в кеші. Таким способом вдається скоротити пошук в кращому випадку в N разів (це якщо всі ланцюжки виявляться однакової довжини).
Переміщення буфера з однієї хеш-ланцюжки в іншу, як і його переміщення в кінець списку вільних блоків, не вимагає перезапису всього блоку даних у пам'яті і виконується шляхом зміни посилань в заголовках блоків.
Ще одна особливість кешування дисків в UNIX полягає в тому, що при виявленні на початку списку вільних блоків «брудних» буферів система запускає процеси їх очищення, але не чекає завершення цих процесів, а вибирає для витіснення перший по списку чистий блок. Після завершення очищення блоки повертаються в початок списку вільних блоків, залишаючись першими кандидатами на витіснення.