Задача заміщення сторінок

Задача заміщення сторінок (ЗЗС) є задачею керування пам'яттю комп'ютера, що полягає у наступному: припустимо, що є два види пам'яті, швидка та повільна, в кожній з них містяться сторінки. Якщо надходить запит на сторінку, що міститься у повільній пам'яті, то алгоритм заміщення сторінок вирішує, яка сторінка з швидкої пам'яті має бути заміщена на ту, на яку прийшов запит. Критерієм оптимальності є число сторінок, що потрібно витіснити у повільну пам'ять.

Офлайн формулювання

У цьому формулюванні використовується припущення про те, що алгоритму $\mathbb {A}$ відома вся послідовність $\sigma$ запитів. В такому разі ЗЗС є поліноміально розв'язуваною за допомогою алгоритму Беладі.

Онлайн формулювання

У практичних ситуаціях, зазвичай, точна послідовність запитів невідома $\sigma$. Тому цікавішою є онлайн постановка ЗЗС, в якій алгоритму нічого невідомо про $\sigma$. В цьому випадку ЗЗС є ${\mathcal {NP}}$-важкою задачею. З погляду точності у найгіршому випадку класичні результати були отримані Слейтором і Тарьяном стосовно алгоритмів $\mathbf {FIFO}$ та $\mathbf {LRU}$.

ARC

Спроби впровадження алгоритмів, що забезпечують результати кращі, ніж у алгоритму LRU (Least Recently Used), не вдавалися з причин великих накладних витрат і потреби в попередньому налаштуванні. Адаптивний алгоритм заміщення кешу (Adaptive Replacement Cache - ARC) перевершує LRU і позбавлений цих недоліків. Алгоритм передбачає підтримку двох списків сторінок - L1 і L2. Максимальна довжина обох списків становить 2c, де c - розмір кешу в сторінках. Обидва списки формуються в стилі LRU. При переміщенні в кеш сторінки, номер якої відсутній в обох списках, цей номер заноситься в початок списку L1. При зверненні до сторінки, номер якої фігурує в одному зі списків, цей номер переноситься в початок списку L2. Важливою особливістю алгоритму є те, що тільки на початку кожного зі списків (підсписки T1 і T2) знаходяться номери сторінок, що знаходяться в кеші, тобто підтримується історія сторінок, недавно витіснених з кешу. Сторінка для заміщення вибирається з кінця списку T1 або T2 залежно від значення параметра p, що визначає поточну допустиму довжину списку T1 (а тим самим, і довжину T2). Адаптивність алгоритму полягає в тому, що значення p змінюється залежно від виду робочого навантаження.

Див. також

• Комбінаторна оптимізація
• Сторінкова пам'ять

Література

• Belady, L.A.: A study of replacement algorithms for virtual storage computers. IBM Syst. J. 5, 78-101(1966)
• Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. of the ACM 28, 202–208 (1985)
• Albers, S. Online algorithms: a survey // Math. Program., Ser. B 97: 3-26 (2003)