Разновидности очередей

Интересной разновидностью очередей являются многопоточные очереди. Элементы в нее, как обычно, добавляются в хвост, но очередь имеет несколько потоков или голов.

В общем случае многопоточные очереди более эффективны, чем несколько однопоточных очередей.

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

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

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

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

Некоторые операционные системы использую приоритетные очереди для планирования заданий. В операционной системе UNIX все процессы имеют разные приоритеты. Когда процессор освобождается, выбирается готовый к исполнению процесс с наивысшим приоритетом. Процессы с более низким приоритетом должны ждать завершения или блокировки процессов с более высокими приоритетами.

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

Алгоритмы приоритетного обслуживания очень популярны во многих областях вычислительной техники, в частности в операционных системах, когда одним приложениям нужно отдать предпочтение перед другими при их обработке в мультипрограммной смеси. Весь трафик разбивается на небольшое количество классов, каждому из которых присваивается приоритет. Приоритетное обслуживание обычно применяется для класса трафика, чувствительного к задержкам, имеющего небольшую интенсивность. Тогда обслуживание этого класса не слишком ущемляет остальные классы. Например, голосовой трафик (чувствителен, но его интенсивность обычно не превышает 8-16 Кбит/c).

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