Операционные системы. Процессы и потоки. Илюшкин Б.И. - 83 стр.

UptoLike

Составители:

Рубрика:

нибудь сегмента во внешнюю память. Для решения проблемы заме-

щения сегментов используются следующие алгоритмы [2]:

• FIFO ( First – In, First – Out, «первым прибыл - первым выбыва-

ет»);

• LRU (Least Recently Used, «последний из недавно используе-

мых» или «дольше всего неиспользуемый»);

• LFU (Least Frequently Used, «используемый реже всех осталь-

ных»);

• Random (случайный выбор сегмента).

Алгоритмы FIFO и Random наиболее просты в реализации.

Так, для алгоритма FIFO операционная система поддерживает список

всех сегментов, находящихся в данный момент в памяти. Первый

сегмент списка является старейшим, а в конце списка находятся не-

давно попавшие сегменты. При возникновении прерывания для за-

мещения выбирается наиболее старый сегмент из головы списка, а

новый сегмент добавляется в его конец. Алгоритм FIFO учитывает

только время нахождения сегментов в памяти, а не их фактическое

использование. Для реализации алгоритмов LRU и LFU необходимо

использовать дополнительные аппаратные средства процессора, на-

пример, бит обращения, который менял бы свое значение при обра-

щении к дескриптору сегмента для получения физического адреса

размещения сегмента в памяти. При этом данная информация должна

накапливаться по каждому сегменту в таблице дескрипторов выпол-

няющихся задач. Тогда диспетчер памяти сможет просматривать таб-

лицы дескрипторов для обработки статистической информации об

обращениях к сегментам [2]. В результате возможно составление спи-

ска, упорядоченного либо по длительности неиспользования (для

LRU), либо по частоте использования (для LFU).