Алгоритм fifo
Другим требующим небольших издержек алгоритмом является FIFO (First-In, First-Out). Чтобы проиллюстрировать его работу, рассмотрим универсам, на полках которого можно выставить ровно k различных продуктов. Он предлагает новую удобную пищу: растворимый, «глубоко замороженный», экологически чистый йогурт, который можно мгновенно приготовить в микроволновой печи. Покупатели тут же обратили внимание на этот продукт, и наш ограниченный в размерах универсам, для того чтобы продавать новинку, должен избавиться от одного из старых товаров. Один из вариантов решения состоит в том, чтобы найти продукт, который супермаркет продает дольше всего, и освободить от него магазин на том основании, что им никто больше не интересуется. Имеется номенклатура всех продаваемых в данный момент в универсаме товаров, упорядоченная по времени их появления. Новый продукт помещается в конец перечня, а из начала списка удаляется старый.
Операционная система поддерживает список всех страниц, находящихся в данный момент в памяти, в котором первая страница является старейшей, а страницы в хвосте списка попали в него совсем недавно. Когда происходит страничное прерывание, выгружается из памяти страница в голове списка, а новая страница добавляется в его конец. Применительно к тому же магазину: если удалить воск для усов, согласно алгоритму FIFO, мы также можем лишиться и муки, соли или масла. Та же проблема встает и в отношении компьютеров. По этой причине алгоритм FIFO редко используется в своей исходной форме.
Аномалия Билэди
На первый взгляд кажется очевидным, что чем больше в памяти страничных кадров, тем реже будут иметь место page faults. Удивительно, но это не всегда так. Как установил Билэди, определенные последовательности обращений к страницам в действительности приводят к росту числа страничных нарушений при увеличении кадров, выделенных процессу. Это явление носит название «аномалии Билэди», или «аномалии FIFO». Система с тремя кадрами (9 faults) оказывается более производительной, чем с четырьмя кадрами (10 faults), для строки обращений к памяти 012301401234 при выборе стратегии FIFO.
Рис 6. Аномалия Билэди: a – FIFO с тремя страничными кадрами; b – FIFO с четырьмя страничными кадрами
Аномалию Билэди следует считать скорее курьезом, чем фактором, требующим серьезного отношения, который иллюстрирует сложность ОС, где интуитивный подход не всегда приемлем.
Оптимальный алгоритм (opt)
Одним из последствий открытия аномалии Билэди стал поиск оптимального алгоритма, который при заданной строке обращений имел бы минимальную частоту page faults среди всех других алгоритмов. Такой алгоритм был найден. Он замещает страницу, которая не будет использоваться в течение самого длительного периода времени. Каждая страница должна быть помечена числом инструкций, которые будут выполнены, прежде чем на эту страницу будет сделана первая ссылка. Выталкиваться должна страница, для которой это число наибольшее. Этот алгоритм легко описать, но реализовать невозможно. ОС не знает, к какой странице будет следующее обращение. (Ранее такие проблемы возникали при планировании процессов – алгоритм SJF.) Зато мы можем сделать вывод, что для того, чтобы алгоритм замещения был максимально близок к идеальному алгоритму, система должна как можно точнее предсказывать обращения процессов к памяти. Данный алгоритм применяется для оценки качества реализуемых алгоритмов. OPT – наилучший из возможных алгоритмов замещения страниц, который легко описать, но невозможно реализовать. Он действует так. В тот момент, когда происходит страничное прерывание, в памяти находится некоторый набор страниц. К одной из этих страниц будет обращаться следующая команда процессора (к странице, содержащей требуемую команду). На другие страницы, возможно, не будет ссылок в течение следующих 10, 100 или даже 1000 команд. Каждая страница может быть помечена количеством команд, которые будут выполняться перед первым к ней обращением. Оптимальный страничный алгоритм просто сообщает, что должна быть выгружена страница с наибольшей меткой. Если одна страница не будет использоваться в течение 8 млн. команд, а другая – в течение 6 млн. команд, удаление первой отодвинет в будущее на возможно максимальный срок страничное прерывание, которое вернет ее назад. Компьютеры, подобно людям, пытаются отложить неприятные события настолько, насколько это возможно.
С этим алгоритмом связана только одна проблема: он невыполним. В момент страничного прерывания операционная система не имеет возможности узнать, когда произойдет следующее обращение к каждой странице. (Мы рассматривали аналогичную ситуацию раньше, когда обсуждали алгоритм планирования «кратчайшая задача – первая»: как система может сказать, какая из задач самая короткая?) Тем не менее, выполняя программу на модели и следя за всеми обращениями к страницам, оптимальную замену можно осуществить при втором запуске, опираясь на информацию о ссылках на страницы, собранную во время первого запуска. В этом случае можно сравнивать производительность реализуемых алгоритмов с наилучшим. Если операционная система добивается производительности, скажем, всего на один процент ниже, чем при работе оптимального алгоритма, усилия, потраченные на поиск лучшего алгоритма, повысят продуктивность схемы максимум на 1%. Чтобы избежать возможных недоразумений, следует прояснить, что полученный протокол обращений к страницам относится только к одной хорошо спланированной программе и, кроме того, к определенным входным данным. Таким образом, алгоритм замещения страниц, выведенный из него, будет характерен только для этой программы с именно этими входными данными. Хотя такой метод полезен для оценки алгоритмов замещения страниц, он не используется в практических системах. Ниже мы изучим алгоритмы, которые являются применимыми в реальных ситуациях.