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

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

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

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

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

Деки

Дек (от англ. deq – double ended queue, т.е. очередь с двумя концами) – особый вид очереди в котором включение и исключение элементов может осуществляться с любого из двух концов списка. Частный случай – дек с ограниченным входом и дек с ограниченным выходом. Логическая и физическая структуры деки аналогичны структурам кольцевой FIFO-очереди.

Операции над деком заключаются в определении размера, очистки, включение/исключение элемента справа/слева. На рис. 5.2 в качестве примера показана последовательность состояний дека при включении и удалении пяти элементов. На каждом этапе стрелка указывает, с какого конца дека (левого или правого) осуществляется включение или исключение элемента. Элементы соответственно обозначены буквами A, B, C, D, E.

Рис. 5.2. Состояния дека в процессе изменения.