Доказательство оптимальности алгоритма отдаленного использования

Воспользуемся методом замены для доказательства оптимальности алгоритма от- даленного использования. Рассмотрим произвольную последовательность обраще- ний к памяти D; пусть Spp обозначает план, построенный алгоритмом отдаленного использования, а S* — план с минимально возможным количеством промахов.
Сейчас мы постепенно «преобразуем» S в Spp, обрабатывая одно решение по вы- теснению за раз, без увеличения количества промахов.

Ниже приведен базовый факт, который будет использоваться для выполнения одного шага преобразования.

(4.12) Пусть S — сокращенный план, который принимает те же решения по вытеснению, что и Spp, в первых j элементах последовательности для некоторого j. Тогда существует сокращенный план S', который принимает те же решения, что и Spp, в первых j + 1 элементах и создает не больше промахов, чем S.

Доказательство. Рассмотрим (j + 1)-е обращение к элементу d = d.+ r Так как S и Spp до этого момента были согласованы, содержимое кэша в них не различается. Если d находится в кэше в обоих планах, то решения по вытеснению не требуются (оба плана являются сокращенными), так что S согласуется с Spp на шаге j + 1, и, следовательно, S' = S. Аналогичным образом, если элемент d должен быть вклю- чен в кэш, но S и Spp вытеснят один и тот же элемент, чтобы освободить место для d, и снова S' = S.

Итак, интересная ситуация возникает тогда, когда d необходимо добавить в кэш, причем для этого S вытесняет элементf а Spp вытесняет элемент e ф f. Здесь S и Spp уже не согласуются к шагу j + 1, потому что у S в кэше находится e, а у Spp в кэше находится f. А это означает, что для построения S' необходимо сделать что-то не- тривиальное.

Сначала нужно сделать так, чтобы план S' вытеснял e вместо f Затем нужно убедиться в том, что количество промахов у S' не больше S. Простым решением было бы согласование S' с S в оставшейся части последовательности; однако это не- возможно, так как S и S', начиная с этого момента, имеют разное содержимое кэша. Поэтому мы должны постараться привести кэш S' в такое же состояние, как у S, не создавая ненужных промахов. Когда содержимое кэша будет совпадать, можно будет завершить построение S', просто повторяя поведение S.

А если говорить конкретнее, от запроса j + 2 и далее S' ведет себя в точности как S, пока впервые не будет выполнено одно из следующих условий:

(i) Происходит обращение к элементу g ф e, f, который не находится в кэше S, и S вытесняет e, чтобы освободить для него место.

Так как S' и S различаются только в e иf это означает, что g также не находится в кэше S'; тогда из S' вы- тесняется f и кэши S и S' совпадают. Таким образом, в оставшейся части после- довательности S' ведет себя точно так же, как S.

(ii) Происходит обращение к f и S вытесняет элемент e'. Если e' = e, все просто: S' просто обращается к f из кэша, и после этого шага кэши S и S' совпадают. Если e' ф e, то S' также вытесняет e' и добавляет e из основной памяти; в результате S и S' тоже имеют одинаковое содержимое кэша. Однако здесь необходима осторожность, так как S' уже не является сокращенным планом: элемент e пере- носится в кэш до того, как в нем возникнет прямая необходимость. Итак, чтобы

завершить эту часть построения, мы преобразуем S' в сокращенную форму S1, используя (4.11); количество элементов, включаемых S', при этом не увеличи- вается, и S' по-прежнему согласуется с Spp на шаге j + 1.

Итак, в обоих случаях мы получаем новый сокращенный план S', который со- гласуется с Spp на первых j + 1 элементах и обеспечивает не большее количество промахов, чем S. И здесь принципиально (в соответствии с определяющим свой- ством алгоритма отдаленного использования) то, что один из этих двух случаев возникнет до обращения к e. Дело в том, что на шаге j + 1 алгоритм отдаленного использования вытеснил элемент (e), который понадобится в самом отдаленном будущем; следовательно, обращению к e должно предшествовать обращение к f, и тогда возникнет ситуация (ii). ■

Этот результат позволяет легко завершить доказательство оптимальности. Мы начнем с оптимального плана S и воспользуемся (4.12) для построения плана S1, который согласуется с Spp на первом шаге. Затем мы продолжаем применять (4.12) индуктивно для j = 1, 2, 3, ..., m, строя планы S, согласующиеся с Spp на первых j шагах. Каждый план не увеличивает количество промахов по сравнению с преды- дущим, а по определению Sт = Spp, поскольку планы согласуются на всей последо- вательности.

Таким образом, получаем:

(4.13) SFF порождает не больше промахов, чем любой другой план S* а следова- тельно, является оптимальным.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Доказательство оптимальности алгоритма отдаленного использования:

  1. Принцип недопустимости использования доказательств, полученных с нарушением федерального закона
  2. Использование специальных приемов и методов допроса и склонения к признанию в отсутствие доказательств.11
  3. Отдаленность результата. Нет видимых изменений
  4. Cудебное следствие, т. е. разработка собранных по делу доказательств пред решающими судьями, основывается на трех началах, которые составляют коренные принципы теории доказательств, принявшей внутреннее убеждение мерилом достоверности.
  5. § 82 Доказательства вотчинного права. – Различие между доказательством и укреплением. – Можно ли утвердить вотчинное право по приобретению без укрепления. – Значение и сила неформальных актов
  6. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  7. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  8. АЛГОРИТМ
  9. АЛГОРИТМ УДАЧИ
  10. Алгоритм исцеления:
  11. Раздел III Использование достижений криминалистической психологии при собирании, оценке, использовании личностной информации
  12. Алгоритм избавления от боли
  13. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  14. Оптимальные условия
  15. Алгоритм обработки результатов.