Рабочий набор

Рабочий набор — это концепция в информатике , которая определяет объем памяти, необходимый процессу в заданный интервал времени. ^[1]

Определение

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

Обоснование

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

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

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

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

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

Выполнение

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

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

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

Варианты

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

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

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

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

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

См. также

Ссылки

^ Деннинг, Питер Дж. (2 февраля 2021 г.). «Аналитика рабочего набора». Обзоры вычислительной техники ACM . 53 (6). Ассоциация вычислительной техники (ACM): 1–36. дои : 10.1145/3399709 . ISSN 0360-0300 .
^ Деннинг, Питер Дж. (1968). «Модель рабочего набора поведения программы» (PDF) . Коммуникации АКМ . 11 (5): 323–333. дои : 10.1145/363095.363141 . S2CID 207669410 .
^ Оустерхаут, Дж. К. (1982). «Методы планирования для параллельных систем» (PDF) . Материалы Третьей международной конференции по распределенным вычислительным системам : 22–30.

Дальнейшее чтение

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

[denning-1] Деннинг, Питер Дж. (2 февраля 2021 г.). «Аналитика рабочего набора». Обзоры вычислительной техники ACM . 53 (6). Ассоциация вычислительной техники (ACM): 1–36. дои : 10.1145/3399709 . ISSN 0360-0300 .

[2] Деннинг, Питер Дж. (1968). «Модель рабочего набора поведения программы» (PDF) . Коммуникации АКМ . 11 (5): 323–333. дои : 10.1145/363095.363141 . S2CID 207669410 .

[3] Оустерхаут, Дж. К. (1982). «Методы планирования для параллельных систем» (PDF) . Материалы Третьей международной конференции по распределенным вычислительным системам : 22–30.

[1]

[2]

[3]