Сторінковий обмін

Підкочування або свопінг (від англ. swapping — обмін) — це процес вивантаження рідко використовуваних областей віртуального адресного простору програми на диск або інший пристрій масової пам'яті. Така масова пам'ять завжди набагато дешевше оперативною, хоча і набагато повільніше.
У багатьох підручниках по ОС наводяться таблиці, аналогічні таблиці. 5.2.

Таблиця 5.2. Порівняльні характеристики і вартість різних типів пам'яті

При розробці системи завжди є бажання зробити пам'ять як можна швидшою. З іншого боку, потреби в пам'яті дуже великі і постійно зростають.

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

Вочевидь, що система з десятками гігабайтів статичного ОЗУ матиме вартість, скажімо так, абсолютно не характерну для персонапь-ных систем, не говорячи вже про габарити, споживаній потужності і іншому. На щастя, далеко не все, що зберігається в пам'яті системи, використовується одночасно. У кожен заданий момент виконується лише частина встановленого в системі програмного забезпечення, і працюючі програми використовують лише частину даних.
Емпіричне правило "80—20", часто спостережуване в комерційних системах обробки транзакцій, свідчить, що 80% операцій здійснюються над 20% файлу [Heising 1963]. У ряді робіт, присвячених побудові оптимізуючих компіляторів, посилаються на правило "90-10" (90% часу виповнюється 10% коди) — втім, є серйозні підстави сумніватися в тому, що в даному випадку співвідношення саме таке [Кнут 2000, т. 3].
Насправді, дивно велика кількість функцій розподілу реальних дискретних величин (починаючи від кількості транзакцій на рядок таблиці і закінчуючи розподілом багатства людей або капіталізації акціонерних суспільств) підкоряються закону Парето [Pareto 1897]:

Р = ck^-1,

де — число в діапазоні від 0 до 1, до — значення величини (у нашому випадку — кількість звернень до даного запису) р — кількість записів, до яких відбувається до звернень з — нормалізуючий коефіцієнт (правило "80—20" відповідає ==log80/log20 = 0,1386) або його частному злучаю розподілу Зіпфа [Zipf 1949]:

р = c/ до.

Детальне обговорення цього явища, на жаль, не доходить до глибинних його причин, наводиться в [Кнут 200, т. 3]. Як один з результатів обговорення пропонується концепція файлу", що "самоорганизующегося, — для прискорення пошуку в несортованому масиві пропонується пересувати записи ближче на початок масиву. Якщо звернення до масиву розподілені відповідно до закону Зіпфа, записи, що найбільш зажадалися, концентруються на початку масиву і пошук прискорюється в c/ ln N разів, де N — розмір масиву, а з — константа, залежна від використовуваної стратегії переміщення елементів.
При довільному доступі до даних (наприклад, по покажчиках або по ключах хэш-таблицы) переміщення до початку масиву не має настільки благотворного ефекту — якщо лише вся пам'ять має одну і ту ж швидкість доступу. Але ми бачили, що різні типи пристроїв, що запам'ятовують, різко розрізняються по цьому параметру.
Ця відмінність наводить нас до ідеї багатошаровою або багаторівневій пам'яті коли в швидкій пам'яті зберігаються часто використовувані код або дані, а рідко використовувані поступово мігрують на повільніші пристрої. В разі дискової пам'яті така міграція здійснюється уручну: адміністратор системи скидає на стрічки рідко використовувані дані і заповнює місце, що звільнилося, чимось потрібним. Для великих і сильно завантажених систем існують спеціальні програми, які визначають, що є малоцінним, а що — ні. Управління міграцією з ОЗУ на диск інколи здійснюється користувачем, але часто це виявляється дуже утомливо. В разі міграції між кеш-пам'яттю і ОЗУ Робити щось уручну просто фізично неможливо.