Задача заміщення сторінок (ЗЗС) є задачею керування пам'яттю комп'ютера, що полягає у наступному: припустимо, що є два види пам'яті, швидка та повільна, в кожній з них містяться сторінки. Якщо надходить запит на сторінку, що міститься у повільній пам'яті, то алгоритм заміщення сторінок вирішує, яка сторінка з швидкої пам'яті має бути заміщена на ту, на яку прийшов запит. Критерієм оптимальності є число сторінок, що потрібно витіснити у повільну пам'ять.
Офлайн формулювання ред.
У цьому формулюванні використовується припущення про те, що алгоритму відома вся послідовність запитів. В такому разі ЗЗС є поліноміально розв'язуваною за допомогою алгоритму Беладі.
Онлайн формулювання ред.
У практичних ситуаціях, зазвичай, точна послідовність запитів невідома . Тому цікавішою є онлайн постановка ЗЗС, в якій алгоритму нічого невідомо про . В цьому випадку ЗЗС є -важкою задачею. З погляду точності у найгіршому випадку класичні результати були отримані Слейтором і Тарьяном стосовно алгоритмів та .
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 змінюється залежно від виду робочого навантаження.
Примітки ред.
- ARC: A Self-Tuning, Low Overhead Replacement Cache. [ 8 лютого 2010 у Wayback Machine.](англ.)
Див. також ред.
Література ред.
- 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)
| Це незавершена стаття про алгоритми. Ви можете допомогти проєкту, виправивши або дописавши її. |
| Ця стаття потребує додаткових посилань на джерела для поліпшення її перевірності. (грудень 2015) |
| Цю статтю треба вікіфікувати для відповідності стандартам якості Вікіпедії. (січень 2016) |