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

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

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

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

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

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

Див. також

• Комбінаторна оптимізація

Сторінкова пам'ять

Посилання

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