Аномалия Belady

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

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

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

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

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

Аномалию FIFO следует считать скорее курьезом, чем фактором, требующим серьезного отношения, который иллюстрирует сложность ОС, где интуитивный подход не всегда приемлем.

Дата добавления: 2014-12-16