Александр Терентьев (aterentiev) wrote,
Александр Терентьев
aterentiev

Categories:

Множественная очередь

Второй день ломаю голову и все никак не могу придумать элегантное решение. Программизм зашкаливает. Может, кто подскажет умным советом?

Представим себе набор (массив) эдаких сенсоров разных типов, массив размера Х (т.е. теоретически там может находиться от 0 до Х сенсоров от 0 до Х разных типов, крайние случаи - а) массив нулевой, т.е. ни одного сенсора нет и б) массив заполнен Х разными сенсорами).

В общем случае в массиве "натыкано" К сенсоров N разных типов. Например, так:

[1,1,1,_,_,3,1,2,2,_,_,1,3,_,_,2,2,2,3,_]

В данном примере-массиве Х=20 мест, занятых К=13 сенсорами, 7 мест пустые, 3 разных типов.

Эти сенсоры нужно в циклически вызываемой функции опрашивать. За один вызов можно запустить на опрос только один сенсор. Сенсор отвечает асинхронно, может ответить сразу данными, а может сказать "я занят, приходите позже". При таком ответе, т.е. начав опрос такого сенсора, надо продолжать его опрашивать наряду с другими пока не ответит данными (или не стукнет таймаут, что, впрочем, пока неинтересно).

Если б это было всей задачей, я бы тупо опрашивал все подряд. Но есть вот это:

Каждого типа (из N) можно одновременно начать опрос не более M << K штук. То есть, система, стоящая внутри, не позволяет послать опрос более чем М штукам каждого типа. Например, возьмем М=4.

В данном примере алгоритм должен быть какой-то такой. Смотрим по порядку. Ставим указатель на начало:

[1,1,1,_,_,3,1,1,2,_,_,2,3,_,_,2,2,2,3,_]
^

Пока что не запушено опросов ни одного сенсора.
Смотрим на элемент #1. Типа 1. Запоминаем, запускаем опрос. Отвечает "жди".
Смотрим на элемент #2. Типа 1. Запоминаем, запускаем опрос. Отвечает "жди".
Смотрим на элемент #3. Типа 1. Запоминаем, запускаем опрос. Отвечает "жди". На данный момент запущено 3 опроса #1.
Смотрим на элемент #4. Пусто. Пропускаем.
Смотрим на элемент #5. Пусто. Пропускаем.
Смотрим на элемент #6. Типа 3. Запоминаем, запускаем опрос. Отвечает "жди".
Смотрим на элемент #7. Типа 1. Запоминаем, запускаем опрос. Отвечает "жди".
Смотрим на элемент #8. Типа 1. Больше #1 запускать нельзя, пропускаем. Но помним, что #1,#2,#3 и #7 были уже опрошены, но сказали "приходи позже".
Смотрим на элемент #9. Типа 2. Запоминаем, запускаем опрос. Отвечает "жди".
...
дойдя до конца массива мы пробовали опрашивать выделенные сенсоры, но все ответили "жди":

[1,1,1,_,_,3,1,1,2,_,_,2,3,_,_,2,2,2,3,_]

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

Но вот один из сенсоров очнулся и отдал данные, скажем, этом был #1 типа 1. Продолжаем опрос по маркированным сенсорам, но встретив следующий немаркированный сенсор типа 1, запускаем и маркируем его. Получаем что-то такое:

[1,1,1,_,_,3,1,1,2,_,_,2,3,_,_,2,2,2,3,_]

При этом, нужно достичь того, чтобы #1 встал в конец очереди, то есть, при прочих равных условиях, его, как только что ответившего, можно в следующий раз опросить только после того, как все сенсоры этого типа как минимум раз будут опрошены. То есть, просто по кругу ходить уже нельзя, ибо можно попасть на ситуацию, когда некоторые сенсоры не будут опрошены никогда (дурацкий тайминг)...

В общем, множественная очередь. Ситуация осложняется тем, что принимать решение в каждом вызове приходится индивидуально, а сенсоры чувах снаружи может на лету поменять.

Куда хотя бы копать, подскажите, все мысли повыдумывал уже! :):):)

Приоризированная множественная очередь, млин.
Tags: Программизмы, Работа, Размышления
Subscribe

  • Вот и зима...

    ...наступила. Сегодня утром отскребал карябалкой лед с лобового стекла авто. Потом вспомнил-таки, что у меня есть размораживающий спрей и дело…

  • Для тех, кто в теме :-)

    Расово-правильный номер :)

  • Новая пташка

    Вот, теперь я такой...

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 23 comments

  • Вот и зима...

    ...наступила. Сегодня утром отскребал карябалкой лед с лобового стекла авто. Потом вспомнил-таки, что у меня есть размораживающий спрей и дело…

  • Для тех, кто в теме :-)

    Расово-правильный номер :)

  • Новая пташка

    Вот, теперь я такой...