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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Офлайн формулювання[ред.ред. код]

У цьому формулюванні використовується припущення про те, що алгоритму \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 змінюється залежно від виду робочого навантаження[1].

Примітки[ред.ред. код]

Див. також[ред.ред. код]

Посилання[ред.ред. код]

  • 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)