 |
Алгоритм FIFO (первая прибыла - первая выгружена)
|
|
|
|
Недостаток заключается в том, что наиболее часто запрашиваемая страница может быть выгружена.
7.1.3 Алгоритм "вторая попытка"
Подобен FIFO, но если R=1, то страница переводится в конец очереди, если R=0, то страница выгружается.
Алгоритм "вторая попытка"
В таком алгоритме часто используемая страница никогда не покинет память.
Но в этом алгоритме приходится часто перемещать страницы по списку.
7.1.4 Алгоритм "часы"
Чтобы избежать перемещения страниц по списку, можно использовать указатель, который перемещается по списку.
Алгоритм "часы"
Алгоритм LRU (Least Recently Used - использовавшаяся реже всего)
Первый метод:
Чтобы реализовать этот алгоритм, можно поддерживать список, в котором выстраивать страницы по количеству использования. Эта реализация очень дорога.
Второй метод:
В таблице страниц добавляется запись - счетчик обращений к странице. Чем меньше значение счетчика, тем реже она использовалась.
7.1.6 Алгоритм "рабочий набор"
Замещение страниц по запросу - когда страницы загружаются по требованию, а не заранее, т.е. процесс прерывается и ждет загрузки страницы.
Буксование - когда каждую следующую страницу приходится процессу загружать в память.
Чтобы не происходило частых прерываний, желательно чтобы часто запрашиваемые страницы загружались заранее, а остальные подгружались по необходимости.
Рабочий набор - множество страниц (к), которое процесс использовал до момента времени (t). Т.е. можно записать функцию w(k,t).
Зависимость рабочего набора w(k,t) от количества запрошенных страниц
Т.е. рабочий набор выходит в насыщение, значение w(k,t) в режиме насыщения может служить для рабочего набора, который необходимо загружать до запуска процесса.
|
|
|
Алгоритм заключается в том, чтобы определить рабочий набор, найти и выгрузить страницу, которая не входит в рабочий набор.
Этот алгоритм можно реализовать, записывая, при каждом обращении к памяти, номер страницы в специальный сдвигающийся регистр, затем удалялись бы дублирующие страницы. Но это дорого.
В принципе можно использовать множество страниц, к которым обращался процесс за последние t секунд.
Текущее виртуальное время (Tv) - время работы процессора, которое реально использовал процесс.
Время последнего использования (Told) - текущее время при R=1, т.е. все страницы проверяются на R=1, и если да то текущее время записывается в это поле.
Теперь можно вычислить возраст страницы (не обновления) Tv-Told, и сравнить с t, если больше, то страница не входит в рабочий набор, и страницу можно выгружать.
Получается три варианта:
· если R=1, то текущее время запоминается в поле время последнего использования
· если R=0 и возраст > t, то страница удаляется
· если R=0 и возраст =< t, то эта страница входит в рабочий набор
Алгоритм WSClock
Алгоритм основан на алгоритме "часы", но использует рабочий набор.
Используются битов R и M, а также время последнего использования.
Работа алгоритма WSClock
Это достаточно реальный алгоритм, который используется на практике.
Распределение памяти
Политика распределения памяти
Алгоритмы замещения бывают:
· локальные
· глобальные
Пример глобального и локального алгоритма
В целом глобальный алгоритм работает лучше.
Можно поровну распределять страничные блоки между процессами.
Такой подход справедлив, но не эффективен, т.к. процессы разные.
|
|
|
