Re: Сортировка "наобо рот"

From

Oleg Khovayko ()

To

Andrew Ezhguroff

Date

2002-10-13T00:12:12Z

Area

RU.ALGORITHMS

From: Oleg Khovayko <olegh@hotpop.com>

Andrew Ezhguroff wrote:

>  OK> В этому случае твой алгоритм
> 
> Это не алгоритм, а голая идея. :-)

После данного пояснения - понял и проникся.
До этого же данный тезис был неочевиден.

> Это означает, что все сообщения предназначены единственному устройству.

Ну дык! И я о том же.

> Подобную ситуацию придется решать в любом алгоритме 

Да.

 > и простейшее лобовое
> решение - для каждой очереди хранить время отправки последнего сообщения.

Можно и так делать...

> Еще раз - это не алгоритм, а идея. Понятно, что запускать подобный
> бесконечный цикл в драйвере абсурдно.

Вот и я о том же. Что твое предыдущее письмо никак нельзя рассматривать 
как руководство к действию. А рассматривать его можно разве что как 
рассуждения общего порядка - "куда думать".

> 
> Например, лучше использовать не массив, а список (циклический?) 
 > актуальных
 > очередей.

И обслуживать в нем две специальные ситуации "список пуст" и
"в списке только одина очередь".

 > При этом пустая очередь исключается из списка

И куда девается? Отдается на растерзание free() или переносится в
некий другой "список свободных очередей"? Оба способа имеют свои 
недостатки...

, а очередь,
> сообщение из которой отправляется, перемещается в конец списка. 

Ага. То есть циклический список должен быть двусвязным?
или же для каждой перестановки его придется несколько раз обежать по кругу.

> Очередь,
> ставшая непустой (в результате появления нового сообщения)

Еще потенциальная проблема - если рассматриваемый нами
процесс-диспетчер очередь лихо будет переставлять очередь по памяти,
то он сможет создать проблемы для процесса-наполнителя очереди.

Можно, конечно, решить проблему путем хранения в кольцевом списке
указателей на очереди, но тогда будут проблемы с удалением/созданием 
очередей в контексте процесса-наполнителя.

, добавляется
> также в конец списка. При исчерпании списка процесс приостанавливается до
> появления нового сообщения. Если время после отправки предыдущего сообщения
> из текущей очереди слишком мало, то процесс приостанавливается на
> достаточное время.

Но несмотря на описаные выше тонкие места, это уже похоже на работающий 
вариант. Теперь осталось только закодировать. ;)

Я вот свой "почти рабочий" вариант, с одной единственной
очередью, привел. Есть против него возражения?

> ИМХО, скорее всего будет с точностью до наоборот - в RT-11SJ драйверы
> работать может и будут, а вот приложение - нет. 

Да, здесь ты прав. Поправка принимается.

> А вот в "нормальной"
> многозадачной среде если бесконечный цикл работает не на максимальном
> приоритете, то система все же будет функционировать.

Да. Но хреново.

.
--- ifmail v.2.15dev5
 * Origin: Demos online service (2:5020/400)