Очереди в вычислительных системах

Очереди с приоритетами

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

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

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

Типичным примером кольцевой очереди в вычислительной системе является буфер клавиатуры BIOS (Базовой Системы Ввода-Вывода) IBM PC. Буфер клавиатуры занимает последовательность байтов памяти по адресам от 40:1E до 40:2D включительно. По адресам 40:1A и 40:1C располагаются указатели на начало и конец очереди соответственно. При нажатии на любую клавишу генерируется прерывание 9.

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

Очередь является одним из ключевых понятий в многозадачных операционных системах (Windows NT, Unix, OS/2 и др.). Ресурсы вычислительной системы (процессор, оперативная память, внешние устройства и т.п.) используются всеми задачами, одновременно выполняемыми в среде. Поскольку многие виды ресурсов не допускают одновременного использования разными задачами, такие ресурсы предоставляются задачам поочередно.

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

Дата добавления: 2014-01-07