Сравнительный анализ локальной и глобальной политики

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

Главный вопрос, связанный с этим выбором (который мы до сих пор тщательно обходили стороной): как должна быть распределена память между конкурирующими работоспособными процессами?

Посмотрите на рис.

3.20, а. На нем изображены три процесса: А, В и С, составляющие набор работоспособных процессов. Предположим, что процесс А сталкивается с ошибкой отсутствия страницы. Должен ли алгоритм замещения страниц попытаться найти наиболее давно использованную страницу, рассматривая лишь шесть страниц, выделенных на данный момент процессу А, или же он должен рассматривать все страницы, имеющиеся в памяти? Если он осуществляет поиск только среди страниц, принадлежащих процессу А, то страницей с наименьшим значением возраста будет А5, и мы получим ситуацию, показанную на рис. 3.20, б.

Рис. 3.20. Сравнение локального и глобального алгоритмов замещения страниц: а — исходная конфигурация; б — работа локального алгоритма замещения страниц; в — работа глобального алгоритма замещения страниц


В то же время, если страница с наименьшим значением возраста удаляется независимо от того, какому процессу она принадлежит, то будет выбрана страница В3, и мы получим ситуацию, показанную на рис. 3.20, в. Алгоритм, чья работа показана на рис. 3.20, б, называется локальным алгоритмом замещения страниц, а алгоритм, чья работа показана на рис. 3.20, в, называется глобальным алгоритмом замещения страниц. Локальный алгоритм хорошо подходит для выделения каждому процессу фиксированной доли памяти. При использовании глобальных алгоритмов страничные блоки распределяются среди работоспособных процессов в динамическом режиме. Поэтому со временем изменяется количество страничных блоков, выделенных каждому процессу.

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

Другой подход заключается в использовании алгоритма выделения процессам страничных блоков. Один из способов заключается в периодическом определении количества работающих процессов и выделении каждому процессу равной доли. Таким образом, при наличии 12 416 доступных (то есть не принадлежащих операционной системе) страничных блоков и 10 процессов каждый процесс получает 1241 страничный блок. Оставшиеся шесть блоков переходят в резерв для использования в случае возникновения ошибки отсутствия страницы.

Хотя этот метод может показаться справедливым, едва ли есть смысл предоставлять одинаковые доли памяти процессу в 10 Кбайт и процессу в 300 Кбайт. Вместо этого страницы должны быть распределены пропорционально общему размеру каждого процесса, чтобы процессу в 300 Кбайт было выделено в 30 раз больше блоков, чем процессу в 10 Кбайт.

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

При использовании глобального алгоритма может появиться возможность запускать каждый процесс с некоторым количеством страниц пропорционально размеру процесса, но как только процессы будут запущены, распределение должно динамически обновляться. Одним из способов управления распределением является использование алгоритма частоты возникновения ошибки отсутствия страницы (Page Fault Frequency (PFF)). Он подсказывает, когда нужно увеличивать или уменьшать количество выделенных процессу страниц, но ничего не говорит о том, какую страницу следует удалить в случае возникновения ошибки. Он всего лишь контролирует размер выделенного набора.

Ранее уже говорилось, что для большого класса алгоритмов замещения страниц, включая LRU, известно, что чем больше выделено страниц, тем меньше уровень ошибок. Данное предположение положено в основу алгоритма PFF. Это свойство проиллюстрировано на рис. 3.21.

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

Рис. 3.21. Уровень ошибок как функция от количества выделенных страничных блоков


уровню ошибок отсутствия страницы, поэтому, чтобы снизить этот уровень, процесс, в котором происходят ошибки, получает больше страничных блоков. Пунктирная линия, обозначенная буквой B, соответствует слишком низкому уровню ошибок отсутствия страницы, который позволяет предположить, что процессу выделено чрезмерно много памяти. В этом случае страничные блоки у него могут быть отобраны. Таким образом алгоритм PFF пытается сохранить для каждого процесса уровень подкачки страниц в пределах приемлемых границ.

Важно отметить, что некоторые алгоритмы замещения страниц могут работать как с локальной, так и с глобальной политикой замещения. Например, FIFO может заменять самые старые страницы во всем пространстве памяти (глобальный алгоритм) или самые старые страницы, принадлежащие текущему процессу (локальный алгоритм). Точно так же алгоритм LRU или приближения к его реализации могут заменять наиболее давно использованную страницу во всей памяти (глобальный алгоритм) или наиболее давно использованную страницу, принадлежащую текущему процессу (локальный алгоритм). В некоторых случаях выбор локальной, а не глобальной стратегии не зависит от алгоритма.

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

3.5.2.

<< | >>
Источник: Э. ТАНЕНБАУМ Х. БОС. СОВРЕМЕННЫЕ ОПЕРАЦИОННЫЕ СИСТЕМ Ы 4-е ИЗДАНИЕ. 2015

Еще по теме Сравнительный анализ локальной и глобальной политики:

  1. 1. Программа учебного курса «Сравнительное правоведение (основные правовые системы современности)» Общая часть Введение в теорию и историю сравнительного правоведения
  2. ПСИХОФИЗИОЛОГИЯ ПОРАЖЕНИЙ ЛОКАЛЬНЫХ МОЗГА ГОЛОВНОГО
  3. МОЗГ ГОЛОВНОЙ: ПСИХОФИЗИОЛОГИЯ ПОРАЖЕНИЙ ЛОКАЛЬНЫХ
  4. ЛОКАЛЬНЫЙ
  5. Идея глобального демократического правления (Хелд)
  6. 2.3. Принципі оптимального поєднання централізованого і локального правового регулювання
  7. 4.3. Акти договірного та локального характеру у сфері трудового права
  8. Аспекты, исходящие от планет разной локальной детер- минации
  9. 1.2. Хартия Глобального информационного общества (Окинава)
  10. CNN International – глобальная служба теленовостей.
  11. § 3. Интервью в глобальной сети
  12. ОБРАЗ ОПЕРАТИВНЫЙ ГЛОБАЛЬНЫЙ
  13. Глава 3. Электронные средства массовой информации в глобальных коммуникационных процессах
  14. Причины возникновения «глобальных городов»
  15. Курс включает четыре глобальных направления: