Хранение страничной памяти на диске
Статическая область свопинга
После запуска процесса он занимает определенную память, на диске сразу ему выделяется такое же пространство. Поэтому файл подкачки должен быть не меньше памяти. А в случае нехватки памяти даже больше. Как только процесс завершится, он освободит память и место на диске.
На диске всегда есть дубликат страницы, которая находится в памяти.
Этот механизм наиболее простой.
Статический и динамический методы организации свопинга.
Динамическая область свопинга
Предполагается не выделять страницам место на диске, а выделять только при выгрузке страницы, и как только страница вернется в память освобождать место на диске.
Этот механизм сложнее, так как процессы не привязаны к какому-то пространству на диске, и нужно хранить информацию (карту диска) о местоположении на диске каждой страницы.
Алгоритмы замещения страниц
Идеальный алгоритм заключается в том, что бы выгружать ту страницу, которая будет запрошена позже всех.
Но этот алгоритм не осуществим, т.к. нельзя знать какую страницу, когда запросят. Можно лишь набрать статистику использования.
Алгоритм NRU (NotRecentlyUsed - не использовавшаяся в последнее время страница)
Используются биты обращения (R-Referenced) и изменения (M-Modified) в таблице страниц.
При обращении бит R выставляется в 1, через некоторое время ОС не переведет его в 0.
M переводится в 0, только после записи на диск.
|
|
|
Благодаря этим битам можно получить 4-ре класса страниц:
1. не было обращений и изменений (R=0, M=0)
2. не было обращений, было изменение (R=0, M=1)
3. было обращение, не было изменений (R=1, M=0)
4. было обращений и изменений (R=1, M=1)
Алгоритм FIFO (первая прибыла - первая выгружена)
Недостаток заключается в том, что наиболее часто запрашиваемая страница может быть выгружена.
7.1.3 Алгоритм "вторая попытка"
Подобен FIFO, но если R=1, то страница переводится в конец очереди, если R=0, то страница выгружается.
Алгоритм "вторая попытка"
В таком алгоритме часто используемая страница никогда не покинет память.
Но в этом алгоритме приходится часто перемещать страницы по списку.
7.1.4 Алгоритм "часы"
Чтобы избежать перемещения страниц по списку, можно использовать указатель, который перемещается по списку.
Алгоритм "часы"
Алгоритм LRU (LeastRecentlyUsed - использовавшаяся реже всего)
Первый метод:
Чтобы реализовать этот алгоритм, можно поддерживать список, в котором выстраивать страницы по количеству использования. Эта реализация очень дорога.
Второй метод:
В таблице страниц добавляется запись - счетчик обращений к странице. Чем меньше значение счетчика, тем реже она использовалась.
|
|
|
7.1.6 Алгоритм "рабочий набор"
Замещение страниц по запросу - когда страницы загружаются по требованию, а не заранее, т.е. процесс прерывается и ждет загрузки страницы.
Буксование - когда каждую следующую страницу приходится процессу загружать в память.
Чтобы не происходило частых прерываний, желательно чтобы часто запрашиваемые страницы загружались заранее, а остальные подгружались по необходимости.
Рабочий набор - множество страниц (к), которое процесс использовал до момента времени (t). Т.е. можно записать функцию w(k,t).
Зависимость рабочего набора w(k,t) от количества запрошенных страниц
Т.е. рабочий набор выходит в насыщение, значение w(k,t) в режиме насыщения может служить для рабочего набора, который необходимо загружать до запуска процесса.
Алгоритм заключается в том, чтобы определить рабочий набор, найти и выгрузить страницу, которая не входит в рабочий набор.
Этот алгоритм можно реализовать, записывая, при каждом обращении к памяти, номер страницы в специальный сдвигающийся регистр, затем удалялись бы дублирующие страницы. Но это дорого.
В принципе можно использовать множество страниц, к которым обращался процесс за последние t секунд.
|
|
|
Текущее виртуальное время (Tv) - время работы процессора, которое реально использовал процесс.
Время последнего использования (Told) - текущее время при R=1, т.е. все страницы проверяются на R=1, и если да то текущее время записывается в это поле.
Теперь можно вычислить возраст страницы (не обновления) Tv-Told, и сравнить с t, если больше, то страница не входит в рабочий набор, и страницу можно выгружать.
Получается три варианта:
o если R=1, то текущее время запоминается в поле время последнего использования
o если R=0 и возраст > t, то страница удаляется
o если R=0 и возраст =< t, то эта страница входит в рабочий набор
Алгоритм WSClock
Алгоритм основан на алгоритме "часы", но использует рабочий набор.
Используются битов R и M, а также время последнего использования.
Работа алгоритма WSClock
Это достаточно реальный алгоритм, который используется на практике.
Распределение памяти
Дата добавления: 2018-08-06; просмотров: 342; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!