Рабочее множество

Рабочее множество (англ. working set) — понятие в информатике, определяющее количество памяти, требующееся процессу в заданный интервал времени.

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

Определение

Питер Деннинг (1968) определяет «рабочее множество информации $W(t,\tau )$ процесса в момент времени $t$ как совокупность информации, на которую ссылается процесс в течение интервала времени $(t-\tau ,t)$». Обычно за единицу информации берётся страница памяти. Предлагается считать рабочее множество приближенной оценкой множества страниц, к которым процесс обратится в будущем (например, в течение следующих $\tau$ единиц времени), и, что более важно, — показателем того, какие страницы следует сохранить в основной памяти, чтобы выполнение процесса осуществлялось быстрее.

Обоснование

Для производительности имеет значение, какие именно страницы останутся в основной памяти (в отличие от страниц, выгружаемых во вспомогательную память): если оставить в основной памяти слишком много страниц, принадлежащих процессу, то снизится количество процессов, которые можно выполнять одновременно. Если оставить в основной памяти слишком мало страниц процесса, то частота ошибок страниц резко возрастёт и число выполняющихся в данный момент активных процессов будет стремиться к нулю.

Согласно модели рабочего множества, процесс может находиться в ОЗУ тогда и только тогда, когда множество всех его страниц, используемых в настоящее время (или множество последних по времени использования страниц, которое часто используется как его приближение) могут находиться в ОЗУ. Модель работает по принципу «всё или ничего», то есть, если число нужных процессу страниц памяти растёт и в ОЗУ нет свободного места, то процесс выгружается из памяти целиком, чтобы освободить память для использования другими процессами.

Часто сильно загруженный компьютер может иметь столько процессов в очереди, что, если позволить им запуститься в один и тот же квант времени, то объём памяти, на который они будут ссылаться, превысит объём ОЗУ, вследствие чего возникнет пробуксовка виртуальной памяти.

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

Реализация

Основная сложность в реализации описанной модели — это отслеживание рабочего множества. Для этого из всего потока обращений процесса к страницам памяти отслеживаются последние обращения за интервал времени $\tau$, называемый окном рабочего множества. При каждом обращении к памяти новая ссылка на страницу добавляется в начало окна, а наиболее старая ссылка оказывается за его пределами. Страница считается принадлежащей рабочему множеству, если на неё есть ссылка в окне рабочего множества.

Чтобы избежать накладных расходов, связанных с хранением большого числа ссылок на страницы памяти, вычисление рабочего множества часто реализуется путём отслеживания времени последнего обращения к странице памяти. Страница считается принадлежащей рабочему множеству, если разница между текущим моментом времени и временем последнего обращения не превышает размера окна рабочего множества. Если эта разница превышает размер окна, страница может быть удалена.

Стратегия рабочего множества не является алгоритмом замены страниц, однако алгоритмы замены страниц могут учитывать рабочее множество процесса и не удалять принадлежащие ему страницы. Например, существует модифицированная версия алгоритма часов под названием WSClock.

См. также

• Locality of reference
• Resident set size

Литература

• Э. Танненбаум. Архитектура компьютера = Structured Computer Organization. — 5-е изд. — СПб.: Питер, 2013. — С. 483. — 884 с. — ISBN 978-5-469-01274-0.
• Denning, P.J. (1980). Working Sets Past and Present. IEEE Transactions on Software Engineering, 1/1980, Volume SE-6, pp. 64-84
• Silberschatz, A., Galvin, P.B., & Gagne, G. (2005). Operating System Concepts, 7th edition. Palatino: Wiley. pp. 346.