Входная очередь

В информатике очередь ввода — это совокупность процессов в хранилище , ожидающих загрузки в память для запуска программы. Очереди ввода в основном используются в планировании операционной системы, которое представляет собой метод распределения ресурсов между процессами. Очереди ввода применимы не только к операционным системам (ОС), но также могут применяться для планирования внутри сетевых устройств. Цель планирования — обеспечить справедливое и эффективное распределение ресурсов; следовательно, это улучшает производительность системы.

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

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

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

Операционная система

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

Первый пришел, первый ушел

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

Кратчайшее оставшееся время

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

Упреждающее планирование с фиксированным приоритетом

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

Круговое планирование

Метод циклического планирования дает одинаковое количество времени для каждого процесса и циклического их прохождения. Этот метод в значительной степени основан на том, что каждый процесс занимает много времени. Слишком короткое время приведет к фрагментации процессов, а слишком большое увеличит время ожидания выполнения каждого процесса. Правильный выбор времени является основой этого метода. ^{[ нужны разъяснения ]}

Многоуровневое планирование очередей

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

сеть

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

Очередь «первым пришел — первым ушел» (FIFO)

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

Взвешенная справедливая очередь (WFQ)

Взвешенная справедливая очередь использует алгоритм min-max-fair-share для распределения пакетов. Минимальное справедливое распределение означает, что сетевая ОС будет распределять одинаково минимальный ресурс для каждого типа пакета. Максимальное справедливое распределение означает, что сетевая ОС предоставит больше ресурсов для пакетов, которым необходимо передать большой объем данных в данный момент, но заберет ресурс обратно после передачи. «Взвешенный» означает, что планировщик назначит вес каждому типу пакета. В зависимости от веса он определит, как поместить пакет в очередь и обслуживать его. Обычно каждый пакет будет взвешиваться на основе поля IP Precedence из IP-заголовка каждого пакета.

Справедливое распределение = (емкость ресурса – уже выделенный ресурс) / количество пакетов.

Приоритетная очередь (PQ)

Очередь приоритетов разделена на 4 подочереди с разными приоритетами. Данные в каждой очереди обслуживаются только тогда, когда очереди с более высоким приоритетом пусты. Если данные поступают в пустую очередь с более высоким приоритетом, в то время как сетевая ОС передает данные очереди с более низким приоритетом, сетевая ОС будет хранить данные очереди с более низким приоритетом и сначала обрабатывать данные в очереди с более высоким приоритетом. Сетевую ОС не волнует, как долго очереди с более низким приоритетом должны ждать своей очереди, поскольку она всегда сначала завершает каждую очередь от самого высокого до самого низкого приоритета, прежде чем переходить к следующей очереди. Внутри каждой очереди пакеты пересылаются по принципу «первым пришел — первым обслужен».

Пользовательская очередь (CQ)

Пользовательская очередь разделена на 17 различных подочередей. Первая очередь, очередь 0, зарезервирована для сетевой ОС для передачи системных пакетов, остальные 16 очередей предназначены для пакетов, определяемых пользователем. Пользователь может определить различные важные пакеты и назначить их в каждую очередь. Каждая очередь имеет ограниченный размер, и если она достигнет этого предела, она будет отбрасывать все поступающие пакеты. Каждая очередь обслуживается в зависимости от количества пакетов, обслуживаемых в каждой очереди. Если этот предел соблюден, сетевая ОС будет удерживать пакеты текущей очереди и обслуживать следующую очередь до тех пор, пока эта очередь не станет пустой или не достигнет своего лимита пакетов. Если одна очередь пуста, сетевая ОС пропустит эту очередь и обслужит следующую очередь.

См. также

Очередь сообщений

Ссылки

Столлингс, Уильям (2003). Практические исследования CCIE, том II . Сиско Пресс. ISBN 1-58705-072-2 .
Планирование операционной системы
Операционная система — планирование
Планирование и буферизация ОС