|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrew Ezhguroff 2:5020/400 13 Oct 2002 03:03:03
To : Oleg Khovayko
Subject : Re: Сортировка "наобо рот"
--------------------------------------------------------------------------------
Привет! "Oleg Khovayko" <olegh@hotpop.com> сообщил(а):
>> Hапример, лучше использовать не массив, а список (циклический?)
>> актуальных
>> очередей.
OK> И обслуживать в нем две специальные ситуации "список пуст" и
OK> "в списке только одина очередь".
В ействительности ситуация только одна - "список пуст", при которой должна
производиться приостановка процесса.
Ситуация "только одна очередь" для циклического списка означает, что
последовательно будут обрабатываться элементы этой самой единственной
очереди (что, правда, будет вызывать ситуацию "слишком маленький промежуток
времени").
>> При этом пустая очередь исключается из списка
OK> И куда девается? Отдается на растерзание free() или переносится в
OK> некий другой "список свободных очередей"? Оба способа имеют свои
OK> недостатки...
Если не ограничивать максимальное число необработанных сообщений в очереди,
то без free() все равно не обойтись. :-)
Этот самый кольцевой список я предложил для того, чтобы исключить просмотр
заведомо пустых очередей. И Проще всего это реализовать с помощью вектора из
256 (или сколько их там будет) заголовков очередей.
Кстати, в случае именно кольцевого списка обработанную непустую очередь
перемещать не нужно - она уже находится в конце. :-)
Когда обработчик получает сообщение для устройства номер N:
1. Добавляем сообщение в очередь номер N.
2. Если до этого очередь N была пуста - добавляем указатель на заголовок
очереди номер N (либо просто N - если использовать не указатели, а индексы)
в кольцевой список ПЕРЕД текущим элементом списка.
OK> Ага. То есть циклический список должен быть двусвязным?
OK> или же для каждой перестановки его придется несколько раз обежать по
OK> кругу.
Проще сделать двухсвязным. И, кстати, указатели на следующую/предыдущую
очередь в списке можно разместить в заголовках очередей.
OK> Еще потенциальная проблема - если рассматриваемый нами
OK> процесс-диспетчер очередь лихо будет переставлять очередь по памяти,
OK> то он сможет создать проблемы для процесса-наполнителя очереди.
В действительноси, перестановок в памяти не будет.
OK> Можно, конечно, решить проблему путем хранения в кольцевом списке
OK> указателей на очереди, но тогда будут проблемы с удалением/созданием
OK> очередей в контексте процесса-наполнителя.
Какие проблемы? Заголовки очередей существуют постоянно... И, разумеется,
должны быть критические участки - чтобы, исключить модификацию списка
очередей одновременно процедурами вставки и удаления сообщений.
Т.е. получаем что-то вроде:
typedef struct _List_Msg{ // Список сообщений - собственно очередь
_List_Msg *Next_Msg; // Следующее сообщение в очереди
_Message Val_Msg ; // Собственно сообщение
};
typedef struct _Queue{ // Заголовок очереди
_Queue *Prev_Queue; // Предыдущая очередь в списке
_Queue *Next_Queue; // Следующая очередь в списке
long Time_Msg ; // Время отправки последнего сообщения
_List_Msg *Beg_Msg ; // Первое сообщение в очереди
_List_Msg *End_Msg ; // Последнее сообщение в очереди
};
_Queue Tab_Queue[256]; // Вектор заголовков очередей
_Queue *Cur_Queue; // Указатель на текущую очередь
Соотвественно, динамическими являются только списки сообщений, а спиок
очередей реализуется статическими структурами.
OK> Я вот свой "почти рабочий" вариант, с одной единственной
OK> очередью, привел. Есть против него возражения?
> for( ; ; ) {
> message MSG = Q.get();
> cur_addr = MSG.address();
> if(cur_addr == last_addr) {
> if(reput >= Q.length()) {
> sleep(TIME_OUT);
> } else {
> Q.put(MSG);
> reput++;
> continue;
> }
> }
> send_to_recepient(MSG, cur_addr);
> reput = 0;
> last_addr = cur_addr;
> }
Разумеется, есть...
1. Твой алгоритм меняет порядок сообщений одному устройству:
Предположим, у нас в очереди три сообщения устройству <3> и одно устройству
<5>: {<3>[1], <3>[2], <5>[1], <3>[3]}. Hасколько я понимаю, они будут
переданы в порядке: <3>[1], <5>[1], <3>[3], <pause>, <3>[2].
2. Он работает только в том случае, если время, за которое устройство
"приходит в себя" меньше, или равно времени передачи одного сообщения.
С уважением, Андрей.
--
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
* Origin: Talk.Mail.Ru (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
