Объект очереди

Объект очереди

До сих пор мы связывали с каждым мьютексом только одно событие, но в общем случае могут существовать несколько предикатов переменных условий. Например, в случае очереди, действующей по принципу "первым пришел, первым ушел" (first in first out, FIFO), поток, который пытается удалить элемент из очереди, должен дождаться события, указывающего на то, что очередь не является пустой, а поток, помещающий элемент в очередь, должен дождаться события, указывающего на то, что очередь не является заполненной. Решение заключается в предоставлении двух событий — по одному для каждого условия.

В программе 10.3 представлены необходимые объявления объекта очереди и его функций. В объявлениях намеренно применяется стиль, отличающийся от того, который принят в Windows и который мы использовали до сих пор. Эта программа была получена преобразованием ее первоначального варианта, реализованного в UNIX на основе потоков Pthreads, чем и объясняется происхождение использованного нами стиля. Точно так же и вы можете наследовать тот или иной стиль или определить собственный, который соответствует вашему вкусу или принятым в вашей организации требованиям. В упражнении 10.7 вам предлагается преобразовать приведенный стиль к стилю Windows.

Программы 10.4 и 10.5 представляют функции очереди и программу, которая их использует.

Программа 10.3. SynchObj.h: часть 2 — объявления объекта очереди 

/* Объявления структуры обычной ограниченной синхронизированной очереди.*/

/* Очереди закольцованы и реализованы в виде массивов с индексацией */

/* последнего и первого сообщений. */

/* Кроме того, каждая очередь содержит защитный мьютекс и */

/* переменные условий "очередь не пуста" и "очередь не заполнена". */

/* Наконец, имеется указатель массива сообщений произвольного типа. */

typedef struct queue_tag { /* Универсальная очередь. */

 HANDLE q_guard; /* Защита блока сообщения. */

 HANDLE q_ne; /* Очередь не пуста. Вручную сбрасываемое событие. (Автоматически сбрасываемое событие для "сигнальной модели".) */

 HANDLE q_nf; /* Очередь не заполнена. Вручную сбрасываемое событие. (Автоматически сбрасываемое событие для "сигнальной модели".) */

 volatile DWORD q_size; /* Максимальный размер очереди. */

 volatile DWORD q_first; /* Индекс первого сообщения. */

 volatile DWORD q_last; /* Индекс последнего сообщения. */

 volatile DWORD q_destroyed; /* Получатель сообщений очереди завершил выполнение. */

 PVOID msg_array; /* Массив q_size сообщений. */

} queue_t;

/* Функции управления очередью. */

DWORD q_initialize(queue_t *, DWORD, DWORD);

DWORD q_destroy(queue_t *);

DWORD q_destroyed(queue_t *);

DWORD q_empty(queue_t *);

DWORD q_full(queue_t *);

DWORD q_get(queue_t *, PVOID, DWORD, DWORD);

DWORD q_put(queue_t *, PVOID, DWORD, DWORD);

DWORD q_remove(queue_t *, PVOID, DWORD);

DWORD q_insert(queue_t *, PVOID, DWORD); 

В программе 10.4 представлены такие функции, как q_initialize и q_get, прототипы которых описаны в конце программы 10.3. Обратите внимание, что функции q_get и q_put обеспечивают синхронизацию доступа, а функции q_remove и q_insert, которые вызываются первыми двумя функциями, сами по себе не являются синхронизированными и могут быть использованы в однонитевых программах. В первых двух функциях предусмотрена возможность использования конечных интервалов ожидания, что требует незначительного расширения модели переменных условий.

q_empty и q_full — две другие важные функции, которые используются для реализации предикатов переменных условий.

Данная реализация использует функцию PulseEvent и вручную сбрасываемые события (широковещательная модель), так что все события уведомляются о том, что очередь не пуста или не заполнена.

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

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

Программа 10.4. QueueObj.с: функции управления очередью 

/* Глава 10. QueueObj.c. */

/* Функции очереди */

#include "EvryThng.h"

#include "SynchObj.h"

/* Функции управления конечной ограниченной очередью. */

DWORD q_get(queue_t *q, PVOID msg, DWORD msize, DWORD MaxWait) {

 if (q_destroyed (q)) return 1;

 WaitForSingleObject(q->q_guard, INFINITE);

 while (q_empty(q)) {

  SignalObjectAndWait(q->q_guard, q->q_ne, INFINITE, FALSE);

  WaitForSingleObject(q->q_guard, INFINITE);

 }

 /* Удалить сообщение из очереди. */

 q_remove(q, msg, msize);

 /* Сигнализировать о том, что очередь не заполнена, поскольку мы удалили сообщение. */

 PulseEvent(q->q_nf);

 ReleaseMutex(q->q_guard);

 return 0;

}

DWORD q_put(queue_t *q, PVOID msg, DWORD msize, DWORD MaxWait) {

 if (q_destroyed(q)) return 1;

 WaitForSingleObject(q->q_guard, INFINITE);

 while(q_full(q)) {

  SignalObjectAndWait(q->q_guard, q->q_nf, INFINITE, FALSE);

  WaitForSingleObject(q->q_guard, INFINITE);

 }

 /* Поместить сообщение в очередь. */

 q_insert(q, msg, msize);

 /* Сигнализировать о том, что очередь не пуста; мы вставили сообщение.*/

 PulseEvent (q->q_ne);

 /* Широковещательная модель CV. */

 ReleaseMutex(q->q_guard);

 return 0;

}

DWORD q_initialize(queue_t *q, DWORD msize, DWORD nmsgs) {

 /* Инициализация очереди, включая ее мьютекс и события. */

 /* Выделить память для всех сообщений. */

 q->q_first = q->q_last = 0;

 q->q_size = nmsgs;

 q->q_destroyed = 0;

 q->q_guard = CreateMutex(NULL, FALSE, NULL); 

 q->q_ne = CreateEvent(NULL, TRUE, FALSE, NULL);

 q->q_nf = CreateEvent(NULL, TRUE, FALSE, NULL);

 if ((q->msg_array = calloc(nmsgs, msize)) == NULL) return 1;

 return 0; /* Ошибки отсутствуют. */

}

DWORD q_destroy(queue_t *q) {

 if (q_destroyed(q)) return 1;

 /* Освободить все ресурсы, созданные вызовом q_initialize. */

 WaitForSingleObject(q->q_guard, INFINITE);

 q->q_destroyed = 1;

 free(q->msg_array);

 CloseHandle(q->q_ne);

 CloseHandle(q->q_nf);

 ReleaseMutex(q->q_guard);

 CloseHandle(q->q_guard);

 return 0;

}

DWORD q_destroyed(queue_t *q) {

 return (q->q_destroyed);

}

DWORD q_empty(queue_t *q) {

 return (q->q_first == q->q_last);

}

DWORD q_full(queue_t *q) {

 return ((q->q_last – q->q_first) == 1 || (q->q_first == q->q_size-l && q->q_last == 0));

}

DWORD q_remove(queue_t *q, PVOID msg, DWORD msize) {

 char *pm;

 pm = (char *)q->msg_array;

 /* Удалить наиболее давнее ("первое") сообщение. */

 memcpy(msg, pm + (q->q_first * msize), msize);

 q->q_first = ((q->q_first + 1) % q->q_size);

 return 0; /* Ошибки отсутствуют. */

}

DWORD q_insert(queue_t *q, PVOID msg, DWORD msize) {

 char *pm;

 pm = (char *)q->msg_array;

 /* Добавить новое ("последнее") сообщение. */

 if (q_full(q)) return 1; /* Ошибка – очередь заполнена. */

 memcpy(pm + (q->q_last * msize), msg, msize);

 q->q_last = ((q->q_last + 1) % q->q_size);

 return 0;

} 

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг

3. Очереди

Из книги Информатика и информационные технологии: конспект лекций автора Цветкова А В


19. Очереди

Из книги Информатика и информационные технологии автора Цветкова А В


У6.10 Очереди

Из книги Основы объектно-ориентированного программирования автора Мейер Бертран

У6.10 Очереди Описать в виде АТД очереди (первым пришел - первым ушел) в том же стиле, что и стеки. Обратите внимание на общие и отличительные черты этих АТД. (Указание: аксиомы для item и remove должны отличаться, при описании put (s,x) рассмотрите случаи, когда очередь s пуста и


9.2. Стеки и очереди

Из книги Программирование на языке Ruby [Идеология языка, теория и практика применения] автора Фултон Хэл

9.2. Стеки и очереди Стеки и очереди — это первые из встретившихся нам структур, которые, строго говоря, не встроены в Ruby. Иными словами, в Ruby нет классов Stack и Queue, в отличие от Array и Hash (впрочем, класс Queue есть в библиотеке thread.rb, которую мы еще будем рассматривать).И все же в


26.5. Очереди сообщений

Из книги Linux: Полное руководство автора Колисниченко Денис Николаевич

26.5. Очереди сообщений 26.5.1. Основные структуры ядра для работы с очередями Очередь сообщений — это связный список, находящийся в адресном пространстве ядра. Каждая очередь имеет свой уникальный идентификатор IPC.Структура ядра msgbuf (описана в файле /usr/src/linux/include/linux/msg.h)


26.5.4. Получение сообщений очереди

Из книги Linux программирование в примерах автора Роббинс Арнольд

26.5.4. Получение сообщений очереди Для получения сообщения используется системный вызов msgrcv():int msgrcv(int msqid, struct msgbuf *msgp, int msgsz, long mtype, int msgflg);Первый аргумент определяет очередь, из которой нужно получить сообщение. Второй аргумент — это адрес буфера, в который будет записано


Очереди

Из книги Русский справочник по Win32 API автора Сорока Тарас


9.3.2. Очереди FIFO

Из книги UNIX: разработка сетевых приложений автора Стивенс Уильям Ричард


Сообщения и очереди сообщений

Из книги Разработка ядра Linux автора Лав Роберт

Сообщения и очереди сообщений GetQueueStatus Функция GetQueueStatus возвращает флаги, которые показывают тип сообщений, обнаруженных в очереди сообщений вызывающего потока. DWORD GetQueueStatus ( UINT flags // флаги состояния очереди ); Параметры flags - определяет флаги состояния очереди, указывая


Диспетчер очереди печати

Из книги автора

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


Очереди выполнения

Из книги автора

Очереди выполнения Основная структура данных планировщика — это очередь выполнения (runqueue). Очередь выполнения определена в файле kernel/sched.c[21] в виде структуры struct runqueue. Она представляет собой список готовых к выполнению процессов для данного процессора.Для каждого


Очереди отложенных действий

Из книги автора

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


Очереди запросов

Из книги автора

Очереди запросов Для блочных устройств поддерживаются очереди запросов (request queue), в которых хранятся ожидающие запросы на выполнение операций блочного ввода-вывода. Очередь запросов представляется с помощью структуры request_queue, которая определена в файле <linux/blkdev.h>.