Подкачка страниц: различия между версиями

Фиат и др. представили алгоритм маркировки. Этот алгоритм маркирует запрашиваемые страницы. При возникновении ошибки немаркированная страница равномерно выбирается случайным образом и вытесняется из кэша. Если все страницы маркированы и произошла ошибка, алгоритм снимает метки со всех страниц, а затем вытесняет одну из них равномерно случайным образом. Фиат и др. показали, что этот алгоритм является 2Hk -конкурентным. Здесь Hk – это k-е гармоническое число: Hk = 1 + \ + ! + ••• + p. Известно, что ln(k + 1) < Hk < ln(k) + 1. Они также показали, что ни один рандомизированный алгоритм подкачки страниц не может иметь коэффициент конкурентоспособности меньше Hk. Таким образом, алгоритм маркировки не более чем в два раза хуже наилучшего возможного онлайнового алгоритма (с точки зрения коэффициента конкурентоспособности). Рандомизированный алгоритм с коэффициентом конкурентоспособности, строго равным Hk, был приведен Макгиохом и Слейтором [ ]. Он гораздо сложнее алгоритма маркировки.