Алгоритм выборки

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

Алгоритм аналогичен рассмотренному выше алгоритму исключения, однако модификация указателя на голову списка не выполняется.

Процедура Прочитать(Уаг у)

  • 1. Если Пусто(). Выход.
  • 2. y=Q(P,).

Определение числа элементов в очереди

Число элементов в очереди состоит в вычислении разности указателей с учетом кольцевой природы очереди.

Функция Количество()

  • 1. Если Пусто(), то Количество = 0. Выход.
  • 2. Если Pi = Р2, то Количество = 1. Выход.
  • 3. Если Pi < Р2, то Количество = Р2- Pi + 1.
  • 4. Иначе (Pi > Р2) Количество = Р2 + (n- Pi) + 1.

Рассмотрим несколько примеров использования очередей в вычислительных системах.

Буфер клавиатуры

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

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

Совместное использование ресурсов системы

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

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

LIFO-очереди (стеки) обычно используются операционными системами для учета свободных ресурсов.

Взаимодействие между параллельными задачами

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

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

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

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

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

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

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

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ   След >