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

(1) <math>\mathcal{A}(\sigma) \le с \cdot ОРТ(\sigma) + b</math>.

Коэффициентом конкурентоспособности алгоритма <math>\mathcal{A}</math> является наименьшее значение <math>c</math>, такое, что <math>\mathcal{A}</math> остается c-конкурентным. Это определение очень похоже на определение коэффициента аппроксимации для алгоритмов аппроксимации. Однако следует отметить, что на онлайновый алгоритм не накладывается никаких вычислительных ограничений. В частности, ему разрешается использовать экспоненциальное время для принятия решений. Таким образом, коэффициент конкурентоспособности измеряет исключительно потерю производительности, возникающую из-за незнания будущего.

Фиат и др. [3] рассмотрели ''рандомизированные'' алгоритмы подкачки страниц. Рандомизированному онлайновому алгоритму при принятии решений разрешается использовать случайные биты. Чтобы измерить его производительность, необходимо рассмотреть матожидание стоимости для определенной входной последовательности и сравнить его с оптимальной стоимостью для этой последовательности. Таким образом, рандомизированный онлайновый алгоритм <math>\mathcal{A}</math> является c-конкурентным, если существует константа <math>k</math>, такая, что для каждой последовательности запросов <math>\sigma</math> выполняется соотношение

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