Алгоритм «первой пришла, первой и ушла»

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

Можно, конечно, найти самый залежалый товар (то есть что-нибудь, чем торгуют уже лет сто двадцать) и избавиться от него на том основании, что им уже больше никто не интересуется. В реальности супермаркет ведет связанный список всех продуктов, имеющихся на текущий момент в продаже, в порядке их поступления. Новый продукт попадает в конец списка, а продукт из самого начала списка удаляется.

Для алгоритма замещения страниц можно воспользоваться той же идеей. Операционная система ведет список всех страниц, находящихся на данный момент в памяти, причем совсем недавно поступившие находятся в хвосте, поступившие раньше всех — в голове списка. При возникновении ошибки отсутствия страницы удаляется страница, находящаяся в голове списка, а к его хвосту добавляется новая страница. Применительно к магазину принцип FIFO может привести к удалению воска для эпиляции усов, но он также может привести и к удалению муки, соли или масла. Применительно к компьютерам может возникнуть та же проблема: самая старая страница все еще может пригодиться. Поэтому принцип FIFO в чистом виде используется довольно редко.

3.4.2.

<< | >>
Источник: Э. ТАНЕНБАУМ Х. БОС. СОВРЕМЕННЫЕ ОПЕРАЦИОННЫЕ СИСТЕМ Ы 4-е ИЗДАНИЕ. 2015

Еще по теме Алгоритм «первой пришла, первой и ушла»:

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