4846
правок
Подкачка страниц: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 23: | Строка 23: | ||
Используя это определение, Слейтор и Тарьян дают строгие границы наилучшего коэффициента конкурентоспособности, который может быть достигнут детерминированным алгоритмом. Они показывают, что два известных алгоритма имеют коэффициент конкурентоспособности k: | Используя это определение, Слейтор и Тарьян дают строгие границы наилучшего коэффициента конкурентоспособности, который может быть достигнут детерминированным алгоритмом. Они показывают, что два известных алгоритма имеют коэффициент конкурентоспособности <math>k</math>: | ||
• FIFO (первым пришел – первым вышел), который при ошибке вытесняет страницу, которая была загружена в кэш раньше всех; | • FIFO (первым пришел – первым вышел), который при ошибке вытесняет страницу, которая была загружена в кэш раньше всех; | ||
• LRU (наиболее давно использовавшийся), который при ошибке вытесняет страницу, которая была запрошена давнее всего. | • LRU (наиболее давно использовавшийся), который при ошибке вытесняет страницу, которая была ''запрошена'' давнее всего. | ||
Кроме того, они показывают, что любой детерминированный алгоритм имеет коэффициент конкурентоспособности не менее k, что означает, что k – это наилучшее значение, которое может быть достигнуто. | Кроме того, они показывают, что любой детерминированный алгоритм имеет коэффициент конкурентоспособности не менее <math>k</math>, что означает, что <math>k</math> – это наилучшее значение, которое может быть достигнуто. | ||
Фиат и др. [3] рассмотрели ''рандомизированные'' алгоритмы подкачки страниц. Рандомизированному онлайновому алгоритму при принятии решений разрешается использовать случайные биты. Чтобы измерить его производительность, необходимо рассмотреть матожидание стоимости для определенной входной последовательности и сравнить его с оптимальной стоимостью для этой последовательности. Таким образом, рандомизированный онлайновый алгоритм <math>\mathcal{A}</math> является c-конкурентным, если существует константа <math>k</math>, такая, что для каждой последовательности запросов <math>\sigma</math> выполняется соотношение | |||
(2) <math>\mathbb{E}(\mathcal{A}(\sigma)) \le с \cdot ОРТ(\sigma) + b</math>. | |||
(2) | |||