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

From

Sergey Andrianov (2:5020/1507.400)

To

Alexey Krasnov

Date

2002-10-15T22:08:42Z

Area

RU.ALGORITHMS

Здравствуй, Alexey!

Однажды 12-Oct-02  в 16:54   Alexey Krasnov (2:5066/196.96)
написал       All    по поводу
-=-   Сортировка "наоборот"  -=-

AK> Имеется такая задача. Некий сетевой драйвер мастера имеет очередь 
AK> сообщений, которые необходимо разослать ряду устройств в сети и постоянно 
AK> получает задания с верхнего уровня на отправку новых сообщений. Kаждое 
AK> сетевое устройство характеризуется уникальным однобайтовым сетевым 
AK> адресом. Соответственно, каждое сообщение также содержит в себе адрес 
AK> получателя. Необходимо так переупорядочить отправляемые сообщения, чтобы 
AK> не встречалось два последовательно идущих сообщения к одному и тому же 
AK> устройству, так как приняв сообщение, получатель сразу же принимается за 
AK> его обработку и не в состоянии принять следующее (становится "глухим" на 
AK> время обработки запроса), что воспринимается в итоге как ошибка.

AK> Встает вопрос: как в сетевом драйвере реализовать алгоритм быстрого 
AK> переупорядочивания спускаемых сверху запросов ? Что-то похоже на 
AK> сортировку по адресу, но "наоборот", по принципу:

<эр_рфЁхё_0>> <на_адрес_1> <на_адрес_2> <на_адрес_0> <на_адрес_1> ... и т.д.

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

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

                  До свидания,  в  22:03 MSK
                                 Sergey

---
 * Origin: Sergiev Posad (2:5020/1507.400)