В. Столлингс - Операционные системы (1114679), страница 78
Текст из файла (страница 78)
Однако этот алгоритм являетсв"', этом, с которым сравниваются реальные алгоритмы. -"'';4'- . На рис. 8.15 приведен пример оптимальной стратегии. Предполагаетай~.. а данного процесса используется фиксированное распределение аксированный размер резидентного множества, состоящего из трех к шолнение процесса приводит к обращениям к пяти различным стРани эцессе работы обращения к страницам выполняются в следующем поряд :з 2 3 2 1 5 2 4 5 3 2 5 2 Оптим тимальная стратегия приводит после заполнения всего множества ,г::ь.,: 'м прерываниям обращения к странице ~обозначенным на рисунке буквами С атеги тр тегия дольше всех неиспользовавшегося элемента замещает в ~траницу, обращений к которой не было дольше, чем к другим.
Со АНЦИП ло ц пу локализации можно ожидать, что эта страница не будет использ и в ближайшем будущем. Эта стратегия и в самом деле недалека от тьной. ной. сновная проблема заключается и сложности ее реализации. О ~иантов реализации предполагает отмечать время последнего обращ анице; это должно делаться при каждом обращении к памяти, независ о, выполняется ли обращение к коду или данным. Деже в случае ацпа 5 2 4 5 3 2 5 2 Оптимгльный 3 3 3 3 3 3 3 3 3 3 фййййййй А,торитм 3 3 3 .,"..-.:::.. Иййййййййййй йерецм Вышел Ф Ф 2 5* * 3' 3' 3 Ф 3" 3* 3 2' 2* 2* 2 2 2 2* 1* ! 1 4* А 4 4 5" 5" .Г Г Г Г Г Чгсоеой алгоритм рис.
8.15. Поведение четырех алгоритмов замеигениа страниц На рис. 8.15 приведен пример выполнения алгоритма дольше всех неиспользовавшегося элемента с тем же потоком данных, что и для оптимального алгоритма. Стратегия "первым вошел — первым вышел" рассматривает кадры страниц процесса как циклический буфер, с циклическим же удалением страниц из него. Все, что требуется для реализации этой стратегии, — это указатель, циклически проходящий по кадрам страниц процесса. Таким образом, это одна из простейших в реализации стратегий замещения. Логика ее работы заключается в том, что замещается страница, находящаяся в основной памяти дольше других. Од"ако далеко не всегда эта страница редко используется; очень часто некоторая область данных или кода интенсивно используется программой, и страницы из этой области при использовании описанной стратегии будут загружаться и выгружаться вновь и вновь.
На рис. 8.15 описанная стратегия приводит к шести прерываниям из-за отсутствия страницы. Заметим, что предыдущая стратегия распознает, что чаще других используются страницы 2 и 5, в то время как стратегия "первым во— первым вышел" на это неспособна. ~отя стратегия дольше всех неиспользовавшегося элемента и близка к оптим мальвой, она трудна в реализации и приводит к значительным накладным р~~~одам. Стратегия "первым вошел — первым вышел" реализуется очень просто но относительно редко приводит к хорошим результатам.
В течение долгого врем Ремени разработчики операционных систем испытывали различные алгоритмы, пыта ~~ась достичь увеличения производительности стратегии дольше всех неис- поддержки этой схемы накладные расходы слишком велики. Еще один вариант предполагает поддержание стека обращений к страницам, что тоже обходится недешево для производительности системы.
417 лава 8. Виртуальная намять Часть 3. Первый кадр буфера кадров, являющихся кандидатами для замещения а) Состояние буфера непосредственно перед замещением страницы ва 8- Виртуальная память Часть 3;, 419 звавшегося элемента при значительном снижении накладных ракк" ге из этих алгоритмОв представляют собОй варианты схемы~ извести ' 1я стратегия «с)ос)с ро))су). 1 простейшей схеме часовой стратегии с каждым кадром связывается'." кг нительный бпт„известный как бнт использования. Когда страница и " .кается в кадр. бит использования устанавливается равным 1.
При их Ооращениях к странице, вызвавших прерывание нз-за отсутствия': , этот бит устанавливается равным 1. Прн работе алгоритма заме ество кадров, являющихся кандидатами на замещение «текущий .ьная область видимости, вся основная память или глобальная обла ;ти'), рассматривается как циклический буфер, с которым связан При замезцении страницы указатель перемещается к следующему ~е. Когда наступает время замещения страницы, Операционная систе ;т буфер для поиска кадра, бит использования которого равен О. ;огда в процессе поиска встречается кадр с битом использования, равВ:: расывается в О. Первый же встреченный кадр с нулевым битом испол " ~ыбирается для замещения.
Если все кадры имеют бит использованза ' 1, указатель совершает полный круг и возвращается к начальному заменяя страницу в этом кадре. Как видим, эта стратегия схожа со "'первым вошел — первым вышел", но огличается тем, что кадры, нмв ' :Овленный бит использования, пропускаются алгоритмом Буфер К- ~иц представлен в виде круга, откуда и произошло название стратегнз)в:" щионных систем используют различные варианты часовой гнмер, МНИ1сз «СОВВ681). На рис. 8.16 приведен простейший пример использования часовой: Для замещения доступны и — 1 кадры основной памяти, представл циклического буфера.
Непосредственно перед тем, как заместить 1зере загружаемой из вторичной памяти страницей 727, указателЬ:, авает на кадр 2, содержащий страницу 45. Теперь приступим к вы юго алгоритма. Поскольку бит использования страницы 45 в кадре'. "-' а страница не замещается; вместо этого ее бит использования сбрас '„, кзатель перемещается к следующему кадру Не замещается также кз кадра 3; в соответствии с алгоритмом сбрасывается ее бит испол адующем кадре «номер 4) бит использования страницы равен О. Та страница 556 замещается загружаемой в основную память стран использования которой устанавливается равным 1.
Далее указатель: ходит к кадру 5, и на этом выполнение алгоритма завершается. Для~:-', места на рис. 8,16 бит использования обозначен как иве. Поведение часового алгоритма показано на рис. 8.15. Наличие 3 чает, что бит использования соответствующей страницы равен 1, а ывает текущее положение указателя. Заметим, что данный алгори™. защитить страницы 2 и 5 От замещения. Концепция области види. ности рассматривается в подразделе "Облает = каяекцения" на стр. 424. б) Сожоянив буфера непосредственно после замещения страницы Рис.
8.16. Пример рабаты' часового аягорит,иа рпс. 8.17 показаны результаты эксперимента цВАЕВ801), в к зва -лись четыре рассмотренных в этом разделе алгоритма; предпол ли 1ество отводимых процессу кадров постоянно. Результат основан и~„' -' нип 0.25х10 обращений к памяти в программе на языке ГОВТИАЯ ', " званием страниц размером 256 слов. Эксперимент проводился с выде4~ф-" оцессу 6, 8, 10, 12 и 14 кадров.
Различия в используемых алгоритмаХ1 четко видны при малом количестве кадров 1пРи этом алгоРитм "пер первым вышел'* более чем в два раза хуже оптимального). Прае акпе же результаты представлены в ~Р1)ч1К881, где максимальное откло'"в анже оказывалось больше„чем в 2 раза. В этой работе моделироваэ~" ше различных стратегий на сгенерированной последовательности обр "- ; страницам длиной 10000 обращений к виртуальному пространству из пц, Для достижения эффекта локализации использовалось экспоненц еспределение вероятности ссылок к конкретной странице. 35 '~ж 30 3в 25 20 15 Ех 10 14 Количеетео еьщеленнцх хедрое ,44- Рис. 8.17. Сравнение различных стратегий гамешения страниц Проводились также исследования по сравнению алгоритмов при расР и переменного количества кадров процессу, а также при глобальной ной областях видимости ЦСАВВ81, САВВ841).
Как выяснилось, по и пьности часовой алгоритм наиболее близок к алгоритму дольше всеи-, зовавшегося. Повысить эффективность часового алгоритма можно путем увеличен ичеиия,:. ства используемых при его работе битова. Во всех поддерживающих: ~ую организацию процессорах с каждой страницей в основной памяти ( .„'. яти (в . тельно, с каждым кадром) связан бит модификации. Этот бит испол указания того, что данная страница не может быть замещена до о тех ,е е содержимое не будет записано обратно во вторичную память. ет использоваться часовым алгоритмом следующим образом.
Прин иним ~ С другой стороны, уменьшение количества 6итов до нуля дает нам ~ым вошел — первым вышел"'. внимание биты использования и модификации, все кадры можно разделить на ч тырс категории: использован давно, не модифицирован 1и = О. т = О); использован недавно, не модифицирован ~и = 1, т = 0); использован давно, модифицирован (и = О, т = 1); ь использован недавно, модифицирован (и - — — 1, т = 1). Используя эту классификацию, изменим часовой алгоритм, который теперь будет описан следующим образом. 1. Сканируем буфер кадров, начиная с текущего положения.
В процессе сканирования бит использования не изменяется. Первая же страница с состоянием (и = О, т = 0) замещается. 2. Если выполнение первого шага алгоритма не увенчалось успехом, ищем страницу с параметрами (и = О, т = 1). Если таковая найдена, она замещается. В процессе выполнения данного шага у всех просмотренных страниц сбрасывается бит использования. 8.
Если выполнение предыдущего шага не дало результата, указатель возвращается в исходное положение, но у всех страниц значение бита использования сброшено в О. Повторим, шаг 1 и, при необходимости, шаг 2. Очевидно, на этот раз требуемая страница будет найдена.
Итак, часовой алгоритм циклически проходит по всем страницам буфера в поисках страницы, которая не была модифицирована со времени загрузки и давно не использовалась. Такая страница — хороший кандидат на замещение, особенно с учетом того, что ее не надо записывать на диск. Если при первом проходе кандидатов на замещение не нашлось, алгоритм снова проверяет буфер, тегерь уже в поисках модифицированной, давно не использовавшейся страницы. Хотя такая страница и должна быть записана перед замещением, в соответствии с принципом локализации она вряд ли понадобится в ближайшем будущем.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
