Рабочий набор - Working set

Рабочий набор это концепция в Информатика который определяет объем памяти, который процесс требуется в заданный промежуток времени.

Определение

Питер Деннинг (1968) определяет «рабочий набор информации ${\displaystyle W(t,\tau )}$ из процесс вовремя ${\displaystyle t}$ быть набором информации, на которую ссылается процесс в течение интервала времени процесса ${\displaystyle (t-\tau ,t)}$".^[1]Обычно рассматриваемые единицы информации считаются страницы памяти. Предполагается, что это приблизительный набор страниц, к которым процесс будет обращаться в будущем (скажем, во время следующего ${\displaystyle \tau }$ единиц времени), и, более конкретно, предлагается указывать, какие страницы должны храниться в основной памяти, чтобы обеспечить максимальный прогресс в выполнении этого процесса.

Обоснование

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

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

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

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

Другими словами, стратегия рабочего набора предотвращает взбучка при сохранении максимально возможной степени мультипрограммирования. Таким образом оптимизируется загрузка ЦП и пропускная способность.

Выполнение

Основным препятствием при реализации модели рабочего набора является отслеживание рабочего набора. Окно рабочего набора - это подвижное окно. При каждой ссылке на память на одном конце появляется новая ссылка, а на другом конце самая старая ссылка падает. Страница входит в рабочий набор, если на нее есть ссылка в окне рабочего набора.

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

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

Варианты

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

Аналоги рабочего набора существуют и для других ограниченных ресурсов, в первую очередь процессы. Если набор процессов требует частого взаимодействия между несколькими процессами, тогда он имеет рабочий набор процесса это должно быть запланированный чтобы прогрессировать:^[2]

параллельные программы имеют рабочий набор процесса это должно быть запланированный (запланировано для одновременного выполнения) для выполнения параллельной программы.

Если процессы не планируются одновременно - например, если есть два процесса, но только одно ядро, на котором они выполняются, - тогда процессы могут продвигаться только со скоростью одно взаимодействие за временной интервал.

Другие ресурсы включают файловые ручки или же сетевые розетки - например, копирование одного файла в другой проще всего выполнить с двумя дескрипторами файлов: один для ввода, один для вывода, и, таким образом, размер «рабочего набора дескрипторов файла» равен двум. Если доступен только один дескриптор файла, копирование все еще может быть выполнено, но требует получения дескриптора файла для ввода, чтения из него (скажем, в буфер), освобождения его, затем получения дескриптора файла для вывода, записи в него, отпустить его, затем снова получить дескриптор входного файла и повторить. Точно так же серверу может потребоваться много сокетов, и, если он ограничен, потребуется многократно освобождать и повторно получать сокеты. Эти ресурсы, как правило, требуется для программы, и если она не может получить достаточно ресурсов, она просто терпит неудачу.

Смотрите также

• Местоположение ссылки
• Размер резидентского набора
• Размер рабочего набора

Рекомендации

1. Деннинг, Питер Дж. (1968). «Модель рабочего набора для поведения программы» (PDF). Коммуникации ACM. 11 (5): 323–333. Дои:10.1145/363095.363141.
2. Остерхаут, Дж. К. (1982). «Методы планирования для параллельных систем» (PDF). Труды Третьей Международной конференции по распределенным вычислительным системам: 22–30.

• Таненбаум, Эндрю (2009). Современные операционные системы Третье издание. стр. 209–210
• Деннинг, П.Дж. (1980). Рабочие наборы в прошлом и настоящем. IEEE Transactions по разработке программного обеспечения, 1/1980, том SE-6, стр. 64–84. [1]
• Зильбершац, А., Гальвин, П.Б., и Ганье, Г. (2005). Основные понятия операционной системы, 7-е издание. Палатино: Вайли. С. 346.