3. Задача замещения при управлении виртуальной памятью, часовой алгоритм.
Целью этой задачи является выбор среди пространства ОП той страницы, которую следует переместить во внешнюю память. Задача решается, когда обнаруживается отсутствие свободной страницы в ОП, а вместе с тем следует запрос на размещение новых страниц. Первый, наиболее простой подход, заключается в остановке процесса, потребовавшего страницу ОП в ситуации, когда вся память распределена. В этом случае управление передается другому процессу, у которого нет требований на дополнительную память, а в отношении приостановленного процесса либо не принимается никаких действий, либо все его страницы выгружаются во внешнюю память. Недостаток этого подхода- дискриминации подвергается тот процесс, в ходе выполнения которого возникла потребность замещения.
Идеальная стратегия замещения: должна быть замещена та страница, к которой дольше всего не будет обращений в будущем.
Существуют следующие стратегии:
- для замещения выбирается страница случайным образом;
- выбирается страница, которая дольше всего была в ОП;
- FIFO (удаляется та страница, которая раньше всех была распределена какому-либо процессу). Фактически, это реализация предыдущей стратегии, но она может быть реализована для различных процессов;
- алгоритм удаления дольше всех неиспользовавшейся страницы. Если долго обращения к странице не было, следовательно, в будущем тоже не предвидится.
В простейшем случае, с каждой страницей для этой стратегии связывается бит использования. Этот бит установлен в 1 при обращении к странице, а способ сброса бита в 0 и определяет способы реализации данной стратегии.
В настоящее время для решения задачи замещения находят применение варианты «часового» алгоритма.
И
меется
циклический буфер размерности n,
в каждом элементе хранится номер страницы
и бит использования. Бит использования
устанавливается в 1, когда к странице
произведено обращение, этот бит также
устанавливается при первой загрузке
страницы в ОП. Указатель буфера указывает
на последнюю замещенную страницу. Когда
возникает потребность решить задачу
замещения, указатель перемещается на
следующий элемент буфера. Если бит
использования установлен в 0, то
производится замещение соответствующей
страницы. Если же окажется, что бит
использования равен 1, то страница не
замещается, бит использования
устанавливается в 0, а указатель
перемещается на следующий элемент
буфера. Перемещение указателя
осуществляется до тех пор, пока не будет
обнаружена страница с 0 (нулевым) битом
использования. Повысить эффективность
часового алгоритма можно путем увеличения
количества используемых при его работе
битов. Практически, во всех системах
страничной организации со страницей
связывается бит модификации.
Этот бит указывает, что страница не
может быть замещена до тех пор, пока её
содержимое не будет переписано во
внешнюю память. Соответственно может
быть 4 комбинации битов использования
и битов модификации:
n m
0 0 n=0-давно использован
1 0 1-недавно использован
0 1 m=0- не модифицирован
1 1 1- модифицирован
Часовой алгоритм выглядит следующим образом:
Сканируем буфер, начиная с текущего положения. В процессе сканирования бит использования не изменяется. Первая страница с состоянием битов (0,0) замещается.
Если такой страницы нет, то ищем страницу с параметрами (0,1). Если такая страница найдена, она замещается. В процессе выполнения данного шага у всех просмотренных страниц сбрасывается бит использования.
Если выполнение шага 2 не дало результата, значит, у всех страниц будет сброшен бит использования, указатель буфера вернется в исходное положение, затем повторяем шаг 1 и, при необходимости, 2.
Явление пробуксовки наблюдается тогда, когда ОП имеет небольшие размеры, а программы велики по размеру. В этом случае может возникнуть ситуация частого замещения страниц, и большая часть процессорного времени тратится на выполнение служебных функций. Следовательно, резко замедляется выполнение пользовательских программ.