Алгоритмы выталкивания страниц

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

- оптимальный алгоритм,

- алгоритм дольше всех не использовавшейся страницы (LRU),

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

- алгоритм «второго шанса» (FINUFO) или алгоритм часов.

Для иллюстрации указанных алгоритмов рассмотрим процесс, при выполнении которого необходимо загружать в оперативную память страницы со следующими номерами : 2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2 , - с учетом того, что процессу в памяти выделено три страничных кадра.

Оптимальный алгоритм (иначе называемый MIN - minimal) основан на том, что для обеспечения оптимальных скоростных характеристик и эффективного использования ресурсов следует заменять ту страницу, к которой в дальнейшем не будет новых обращений в течение наиболее длительного времени. Для этого алгоритма необходимо знание всей цепочки обращений к страницам, поэтому он не применяется в реальных условиях и служит в основном для сравнительной оценки других алгоритмов. Рис.3.17,а иллюстрирует замещение страниц в соответствии с указанным алгоритмом. Очевидно, что для рассматриваемого примера процесс будет выполняться с тремя прерываниями по отсутствию нужной страницы в памяти.

Алгоритм замещения дольше всего не использовавшейся страницы (LRU от Least-Recently-Used) предусматривает, что вытесняется страница, к которой не было обращения в течение достаточно длительного периода. В его основе лежит гипотеза о локальности обращения к памяти, предполагающая, что за обращением к данной ячейке памяти последует использование ближайшей ячейки. Поэтому если к области памяти не было обращения в течение некоторого времени, то мала вероятность того, что оно возникнет. Последовательность замещения страниц в соответствии с алгоритмом LRU и возникающие при этом прерывания по отсутствию в памяти нужной страницы показаны на рис.3.17,б. Главным недостатком алгоритма LRU является стоимость реализации. Время разбивается на интервалы обычно фиксированной длины, и ведется список тех страничных кадров, к которым не было обращения в самый последний интервал времени. Для каждого из этих страничных кадров отмечается общее число последовательных интервалов, в течение которых к ним не было обращения. Всякий раз, когда новая страница считывается в страничный кадр, последний удаляется из списка. В конце каждого интервала из списка удаляются те фреймы, к которым было обращение в течение этого интервала времени. Чтобы понять, к каким страничным кадрам было обращение в данный интервал времени, нужно иметь другую таблицу, в которой каждому фрейму поставлен в соответствие один бит. В начале интервала все биты устанавливаются в нуль. Каждый раз, когда к фрейму идет обращение, его бит устанавливается в единицу. Если в конце интервала бит фрейма все еще равен нулю, то это означает, что к нему не было обращений. Как правило, для установки и обновления битов страничных кадров используются специальные аппаратные средства.

Рис.3.17.

При алгоритме замещения первой пришедшей страницы (FIFO от First-In-First-Out) замещается страница, которая дольше всех находилась в оперативной памяти. Если обращение к памяти действительно последовательное, то с большой степенью вероятности эта страница не потребуется снова в ближайшее время. К сожалению, на практике алгоритм FIFO часто приводит к замещению активно используемых страниц, поскольку тот факт, что страница находится в оперативной памяти в течение длительного времени вполне может означать, что она постоянно в работе. Основным достоинством алгоритма является простота его реализации : программе планировщику памяти достаточно просто следить за очередью всех страниц, упорядоченных по времени подкачки. Так как максимальное число страничных кадров фиксировано, то это легко сделать. Однако указанный алгоритм характеризуется большим числом прерываний по отсутствию нужной страницы в памяти по сравнению с ранее рассмотренными (как следует из рис.3.17,в). При этом существует так называемая «аномалия FIFO» (известная еще как аномалия Билейди), когда определенные последовательности обращений к страницам приводят к увеличению количества прерываний по отсутствию страницы при увеличении количества страничных кадров, выделяемых процессу.

Алгоритм «второго шанса» (FINUFO - First-In-Not-Used-First-Out) - первый вошел и, если не используется, то первый вышел - является близким алгоритму LRU, но характеризуется, по сравнению с ним, малыми издержками. С каждым страничным кадром связан бит использования U, устанавливаемый в 0, когда во фрейм загружается новая страница, и в 1 - при обращении к уже содержащейся в нем странице. Фреймы упорядочены в круговую очередь с указателем, отмечающим последний занятый страничный кадр. При необходимости загрузки новой страницы указатель продвигается до первого страничного кадра, содержащего страницу с битом использования U, равным нулю (такая страница замещается требуемой). Встречаемые по мере обхода очереди фреймов страницы с установленным в 1 битом U остаются в оперативной памяти (получают второй шанс), а их бит U «сбрасывается» (устанавливается в нуль). Так как продвижение указателя круговой очереди аналогично движению стрелки часов, то указанный алгоритм получил также название часового (Clock). Бит использования устанавливается в 1 во время обращения к странице с помощью программных или аппаратных средств. На рис.3.17,г стрелка соответствует расположению указателя круговой очереди, а символом «*» отмечены страницы, бит использования фреймов которых установлен в 1; количество прерываний по отсутствию страницы при использовании алгоритма часов в данном случае равно трем.

На рис. 3.18 приведены результаты сравнения / 7 / рассмотренных выше алгоритмов замещения.

Из них следует, что :

- алгоритмы можно расположить по убывающей производительности

в следующем порядке : MIN, LRU, Clock, FIFO;

- влияние размера памяти значительно сильнее влияния типа алгоритма замещения. Другими словами, можно добиться более высокой производительности программы за счет увеличения числа фреймов в оперативной памяти, а не за счет совершенствования алгоритмов замещения.

Рис. 3.18. Производительность алгоритмов замещения

Не нашли, что искали? Воспользуйтесь поиском по сайту: