31. Замещение страниц.

Эффект замещения страниц возникает тогда, когда оказывается, что вся физическая память занята. Т.е. при очередном обращении к логическому адресу не находится ни одного свободного места, куда мог бы войти очередной процесс. Тогда возникает ситуация страничной недостаточности. Разрешается она следующим образом: проверяется наличие бита invalid (valid). Если страница доступна, то идет обращение к физической памяти через базовый адрес. Если оказалось, что данная память не может быть загружена (все занято), тогда из таблицы страниц выбирается страница, которая выгружается из ОП в SWAP file.

Пусть, например, выгружается сегмент А, а надо загрузить сегмент F, который как раз может занять место А. Тогда сегмент А должен быть выгружен в виртуальную память, следовательно там, где находится А корректируется адрес в логической памяти.

Возможен и другой вариант: когда выгрузили, например, сегмент В, он уже в SWAP file, но не выполняется в данный момент (в таблице страниц он помечен как invalid), тогда при обращении к логическому адресу В проверяется его наличие, если его нет, но есть информация, что он в SWAP, тогда его адрес корректируется во всех таблицах и invalid меняется valid, и сегмент В становится доступным.

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

Если страница модифицировалась, то тогда получается двойная загрузка. Сначала из ОЗУ выгружается «страница-жертва» в SW, другая же страница загружена в ОЗУ, и ее адрес модифицируется в таблице страниц.

Этот бит нужен, для того чтобы те страницы, которые не модифицировались не выгружались из памяти, причем загружаемые страницы пишутся поверх них.

32. Алгоритм выбора «жертвы»(замещаемой страницы).

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

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

Замечание: этот алгоритм очень тяжел при реализации, поэтому его используют в основном для тестирования других алгоритмов.

Чаще всего используется алгоритм, фиксирующий время обращения к странице, т.е. «жертвой» становится та страница, у которой было самое большое время обращения, у страницы есть счетчик - часы, который сбрасывается при обращении. В данном случае надо лишь просматривать все время обращения и найти максимальное. Т.е. выгружается страница, к которой дольше всего не обращались.

Второй вариант – использование стека. В стек заносятся только номера страниц.

Как только заносится очередной номер страницы, идет сдвиг ко дну. Как только произошло обращение к странице, она поднимается к вершине. Тогда адрес страницы-«жертвы» определяется как адрес, лежащий на дне стека. Он и выгружается.