Thrashing. Свойство локальности. Модель рабочего множества
Что делать, если в распоряжении процесса имеется недостаточное число кадров? Следует ли его приостановить с освобождением всех его кадров. Что нужно понимать под достаточным количеством кадров?
Хотя теоретически возможно уменьшить число кадров процесса до минимума, существует какое-то число активно используемых страниц, без которого процесс часто генерирует faltы. Эта высокая частота страничных нарушений называется трешинг (trashing, иногда употребляется русский термин пробуксовка). Процесс находится в состоянии трешинга, если он больше времени занимается подкачкой страниц, нежели выполнением. Критическая ситуация такого рода возникает вне зависимости от конкретных алгоритмов замещения.
Рис. 10.2 Частота page fault'ов
Часто результатом трешинга является снижение производительности. Один из нежелательных сценариев развития событий может выглядеть следующим образом. При глобальном алгоритме замещения, процесс, которому не хватает кадров, начинает отбирать их у других процессов, а те в свою очередь начинают заниматься тем же. В результате все процессы попадают в очередь запросов к устройству вторичной памяти, а очередь процессов в состоянии готовности пустеет. Загрузка процессора снижается. Процессор видит это и увеличивает степень мультипрограммирования. Таким образом, пропускная способность системы падает из-за трешинга.
Эффект трешинга, возникающий при использовании глобальных алгоритмов, может быть ограничен за счет использования локальных алгоритмов замещения. Если даже один из процессов попал в трешинг, это не сказывается на других процессах. Однако он много времени проводит в очереди к устройству выгрузки, затрудняя подкачку страниц остальных процессов.
Критическая ситуация типа трешинга возникает вне зависимости от конкретных алгоритмов замещения. Единственным алгоритмом, теоретически гарантирующим отсутствие thrashing, является рассмотренный выше не реализуемый на практике оптимальный алгоритм.
Итак, трешинг - высокая частота страничных нарушений. Необходимо ее контролировать. Когда она высока, процесс нуждается в кадрах. Можно, устанавливая желаемую частоту fault'ов, регулировать размер процесса, добавляя или отнимая у него кадры. Как и в случае с рабочим множеством (см. ниже) может оказаться целесообразным придержать процесс, освободив его кадры. Освободившиеся кадры выделяются другим процессам с высокой частотой fault'ов.
Для предотвращения трешинга нужно выделить процессу столько кадров, сколько ему нужно. Но как узнать, сколько ему нужно. Существует несколько подходов. Необходимо попытаться выяснить, как много кадров процесс реально использует. Этот подход определяет модель локальности выполнения процесса.
Концепция локальности
Суть концепции локальности изложена во введении. Изучая свойства локальности в пейджинговых системах, Деннинг (1968) сформулировал теорию рабочего множества программ (см. ниже).
Модель локальности состоит в том, что когда процесс выполняется, он двигается от одной локальности к другой. Локальность - набор страниц, которые активно используются вместе. Программа обычно состоит из нескольких различных локальностей, которые могут перекрываться. Например, когда вызвана процедура, она определяет новую локальность, состоящую из инструкций процедуры, ее локальных переменных, и множества глобальных переменных. После ее завершения процесс оставляет эту локальность, но может вернуться к ней вновь. Таким образом, локальность определяется кодом и данными программы. Заметим, что модель локальности - принцип, положенный в основу работы кэша. Если бы доступ к любым типам данных был случайным, кэш был бы бесполезным.
Если процессу выделять меньше кадров, чем ему нужно для поддержки его локальности он будет находиться в состоянии трешинга.