| Предыдущий раздел | Оглавление | Следующий раздел |
4.5.3. Алгоритм FIFO
Другим низкозатратным алгоритмом замещения страниц является алгоритм FIFO (First In, First Out — «первым пришел, первым ушел»). Чтобы проиллюстрировать его работу, рассмотрим супермаркет, у которого вполне достаточно полок для представления как раз k различных товаров. И вот однажды какая-то компания представляет новый удобный продукт — быстрорастворимый, полученный в результате сублимационной сушки натуральный йогурт, который может быть восстановлен в микроволновой печи. Он сразу же приобретает популярность, поэтому наш забитый под завязку супермаркет должен избавиться от одного старого продукта, чтобы запастись новым.
Можно, конечно, найти самый залежалый товар (то есть что-нибудь, чем торгуют уже лет сто двадцать) и избавиться от него на том основании, что им уже больше никто не интересуется. В реальности супермаркет ведет связанный список всех продуктов, имеющихся на текущий момент в продаже, в порядке их поступления. Новый продукт попадает в конец списка, а продукт из самого начала списка удаляется.
Для алгоритма замещения страниц можно воспользоваться той же идеей. Операционная система ведет список всех страниц, находящихся на данный момент в памяти, причем совсем недавно поступившие находятся в хвосте, поступившие раньше всех — в голове списка. При возникновении ошибки отсутствия страницы удаляется страница, находящаяся в голове списка, а к его хвосту добавляется новая страница. Применительно к магазину принцип FIFO может привести к удалению воска для эпиляции усов, но он также может привести и к удалению муки, соли или масла. Применительно к компьютерам может возникнуть та же проблема: самая старая страница все еще может пригодиться. Поэтому принцип FIFO в чистом виде используется довольно редко.
| Предыдущий раздел | Оглавление | Следующий раздел |