Алгоритмы замещения страниц - презентация

1 Когда происходит страничное прерывание, операционная система должна выбрать страницу для удаления из памяти, чтобы освободить место для страницы, кото­рую нужно перенести в память. Если удаляемая страница была изменена за время своего присутствия в памяти, ее необходимо переписать на диск, чтобы обновить копию, хранящуюся там. Однако если страница не была модифицирована (на­пример, она содержит текст программы), копия на диске уже является самой но­вой и ее не надо переписывать. Тогда страница, которую нужно прочитать, просто считывается поверх выгружаемой страницы.

2 Используются биты обращения (R-Referenced) и изменения (M-Modified) в таблице страниц. При обращении бит R выставляется в 1, через некоторое время ОС не переведет его в 0. M переводится в 0, только после записи на диск. Благодаря этим битам можно получить 4-ре класса страниц: не было обращений и изменений (R=0, M=0) не было обращений, было изменение (R=0, M=1) было обращение, не было изменений (R=1, M=0) было обращений и изменений (R=1, M=1)

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

4 В таком алгоритме часто используемая страница никогда не покинет память. Но в этом алгоритме приходится часто перемещать страницы по списку.

5 Чтобы избежать перемещения страниц по списку, можно использовать указатель, который перемещается по списку.

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

7 Замещение страниц по запросу - когда страницы загружаются по требованию, а не заранее, т.е. процесс прерывается и ждет загрузки страницы. Буксование - когда каждую следующую страницу приходится процессу загружать в память. Чтобы не происходило частых прерываний, желательно чтобы часто запрашиваемые страницы загружались заранее, а остальные подгружались по необходимости. Рабочий набор - множество страниц (к), которое процесс использовал до момента времени (t). Т.е. можно записать функцию w(k,t).

8 Т.е. рабочий набор выходит в насыщение, значение w(k,t) в режиме насыщения может служить для рабочего набора, который необходимо загружать до запуска процесса. Алгоритм заключается в том, чтобы определить рабочий набор, найти и выгрузить страницу, которая не входит в рабочий набор. Этот алгоритм можно реализовать, записывая, при каждом обращении к памяти, номер страницы в специальный сдвигающийся регистр, затем удалялись бы дублирующие страницы. Но это дорого. В принципе можно использовать множество страниц, к которым обращался процесс за последние t секунд.

9 Текущее виртуальное время (Tv) - время работы процессора, которое реально использовал процесс. Время последнего использования (Told) - текущее время при R=1, т.е. все страницы проверяются на R=1, и если да то текущее время записывается в это поле. Теперь можно вычислить возраст страницы (не обновления) Tv-Told, и сравнить с t, если больше, то страница не входит в рабочий набор, и страницу можно выгружать. Получается три варианта: если R=1, то текущее время запоминается в поле время последнего использования если R=0 и возраст > t, то страница удаляется если R=0 и возраст =< t, то эта страница входит в рабочий набор

10 Алгоритм основан на алгоритме "часы", но использует рабочий набор. Используются битов R и M, а также время последнего использования. Это достаточно реальный алгоритм, который используется на практике.

11 Алгоритмы заключаются в том, что бы определить рабочий набор, найти и выгрузить страницу, которая не входит в рабочий набор. Текущее виртуальное время-это время работы процессора, который реально использует процессор.