Алгоритм FIFO (выталкивание первой пришедшей страницы)

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

Аномалия Belady

Не всегда чем больше страничных кадров имеет память, тем реже будут иметь место page fault'ы. Как установил Белейди (рис.11.1), определенные последовательности обращений к страницам приводят в действительности к увеличению числа страничных нарушений при увеличении кадров, выделенных процессу. Это явление носит название аномалии FIFO.

Три кадра (9 faults) оказываются лучше, чем 4 кадра (10 faults) для 012301401234 цепочки чередования страниц при выборе стратегии FIFO.

Рисунок 11.1 - Аномалия Belady. (a) FIFO с тремя страничными кадрами. (b) FIFO с четырьмя страничными кадрами.