<<
>>

Модель рабочего набора

В простейшей схеме замещения страниц в момент запуска процессов нужные им страницы отсутствуют в памяти. Как только центральный процессор пытается выбрать первую команду, он получает ошибку отсутствия страницы, побуждающую операционную систему перенести в память страницу, содержащую первую команду.
Обычно следом быстро происходят ошибки отсутствия страниц для глобальных переменных и стека. Через некоторое время в памяти скапливается большинство необходимых процессу страниц, и он приступает к работе с относительно незначительным количеством ошибок отсутствия страниц. Этот метод называется замещением страниц по запросу (demand paging), так как страницы загружаются в память по требованию, а не заранее.

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

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

Множество страниц, которое процесс использует в данный момент, называется рабочим набором [31, 32]. Если рабочий набор целиком находится в памяти, процесс выполняется, не вызывая большого количества ошибок, пока он не перейдет к другой фазе выполнения (к следующему проходу в случае компилятора). Если доступная память слишком мала, чтобы содержать полный рабочий набор, процесс инициирует множество ошибок отсутствия страниц и замедляется, так как выполнение среднестатистической команды занимает несколько наносекунд, а чтение страницы с диска обычно требует 10 мс.

При скорости одна или две команды на 10 мс для завершения программы понадобятся века. Говорят, что программа пробуксовывает (thrashing), когда она вызывает ошибку отсутствия страницы каждые несколько команд [32].

В системах разделения времени процессы часто сбрасываются на диск (то есть все их страницы удаляются из памяти) с целью позволить другим процессам получить доступ к центральному процессору. Возникает вопрос, что делать, когда процесс снова загружается в память. С формальной точки зрения делать ничего не нужно. Процесс будет вызывать одну за другой ошибки отсутствия страниц до тех пор, пока в память не загрузится весь его рабочий набор. Проблема в том, что наличие 20, 100 или даже 1000 ошибок отсутствия страниц при каждой загрузке процесса значительно замедляет систему, кроме того, впустую тратится много времени центрального процессора, до нескольких миллисекунд, столько, сколько требуется операционной системе для обработки каждой ошибки отсутствия страницы.

Поэтому многие системы замещения страниц пытаются отслеживать рабочий набор каждого процесса и обеспечивают его нахождение в памяти еще до запуска процесса. Такой подход носит название модели рабочего набора [33]. Эта модель призвана значительно снизить процент ошибок отсутствия страниц. Загрузка страниц перед тем, как разрешить процессу работать, также называется опережающим замещением страниц (prepaging). Заметьте, что рабочий набор с течением времени изменяется.

Давно известно, что большинство программ обращается к различным областям своего адресного пространства не в случайном порядке. Напротив, обращения группируются на небольшом количестве страниц. При обращении к памяти может выполняться чтение данных, чтение команды или запись данных. В любой момент времени £ существует набор, включающий все страницы к, последних обращений к памяти. Этот набор, тю(к, £), является рабочим. Поскольку с увеличением ^ мы все дальше «заглядываем в прошлое», число страниц рабочего набора не может уменьшаться.

Другими словами, функция т®(к, £) представляет собой монотонно неубывающую функцию от Кроме того, у этой функции есть конечный предел, поскольку программа не может обратиться к большему числу страниц, чем есть в ее адресном пространстве. Случаи, когда программа обращается ко всем страницам своей памяти, очень редки. График зависимости размера рабочего набора от числа последних обращений к памяти представлен на рис. 4.17.

Рис. 4.17. Рабочий набор — это множество страниц, использованных при последних к обращениях к памяти. Функция \л/(к, I) представляет собой размер рабочего набора в момент времени I

Быстрый рост кривой вначале и его последующее резкое замедление говорят о том, что программы, как правило, имеют доступ к большинству своих страниц, однако рабочий набор не подвержен значительным изменениям во времени. Например, если программа исполняет цикл, занимающий 2 страницы памяти, и использует данные, расположенные на 4 других страницах, то, возможно, за 1000 команд осуществляется обращение ко всем 6 страницам, а последнее обращение, например, к странице 7 случилось миллион команд назад на этапе инициализации программы. Из-за такого асимптотического поведения содержимое рабочего набора нечувствительно к выбранному значению Другими словами, существует большое количество значений к, для которых рабочие наборы одинаковы. Это позволяет, на основе знаний о страницах, использованных при последнем завершении программы, разумно спрогнозировать множество страниц, которые потребуются на начальной стадии работы программы при следующем ее запуске.

Благодаря опережающему замещению страниц эти страницы загружают в память перед тем, как процесс получает разрешение на запуск.

Для реализации модели рабочего набора необходимо, чтобы операционная система отслеживала, какие страницы в нем находятся. Один из способов получить такую информацию — использовать описанный ранее алгоритм старения. Пусть установленный старший бит счетчика у страницы означает, что она входит в рабочий набор. Если в течение п последовательных тактов часов к такой странице не было сделано обращений, она удаляется из рабочего набора. Параметр п придется определить экспериментальным путем, но производительность системы обычно не слишком чувствительна к его точному значению.

При помощи информации рабочего набора можно повысить производительность алгоритма часов. Обычно, когда «стрелка часов» показывает на страницу, у которой бит Я равен нулю, эта страница удаляется. Чтобы улучшить алгоритм, можно дополнительно проверять, входит ли страница в рабочий набор текущего процесса, и если да, оставлять ее. Такой алгоритм называется тэсЬск.

4.5.2.

<< | >>
Источник: Э. ТАНЕНБАУМ, А. ВУДХАЛЛ. ОПЕРАЦИОННЫЕ СИСТЕМЫ Разработка и реализация 3-е издание. 2007

Еще по теме Модель рабочего набора:

  1. 1.2.1.1. Общая продолжительность рабочего времени. Неполный и сокращенный рабочий день.
  2. Неполнота набора альтернатив.
  3. Набор черт или нечто большее?
  4. «Ролевой набор» («role-set») и референтная группа*
  5. Таблица 4. Стандартный набор трав для лечения по методу Лессура
  6. 1.2.1.2. Режим рабочего времени. Особый режим рабочего времени.
  7. Модель личности журналиста: профессиональные, социально-гражданские, нравственные, психологические и социально-демографические характеристики. Модификация общей модели для разных специализаций (репортер, аналитик, расследователь, публицист, ведущий-модератор и т.п.).
  8. 1.2.1 Рабочее время
  9. МЕСТО РАБОЧЕЕ: ПОЛЕ ИНФОРМАЦИОННОЕ
  10. 6. "Рабочие чертежи".
  11. 3. От имени рабочих (А. Ф. Бережной)
  12. 5. Критическая теория и рабочий класс.
  13. 4.5. Проектирование системы практической подготовки рабочих
  14. Масса, демократия и рабочий класс
  15. 4.1. Личностный потенциал рабочего и его проектирование
  16. РАБОЧИЙ ЛИСТОК ТЕКУЩЕЙ ДЕЯТЕЛЬНОСТИ.
  17. Рабочие определения предмета социологии