Введение

очереди процессов, ожидающих времени процессора

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

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

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

Первый входит, первый выходит

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

Самый короткий оставшийся срок

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

Превентивное планирование с фиксированным приоритетом

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

Разобновление работы

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

Планирование очереди на нескольких уровнях

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

Сетевые связи

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

Первый в очереди, первый в очереди (FIFO)

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

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

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

Заказчиковая очередь (CQ)

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