LINUX.ORG.RU

посоветуйте реализацию очереди сообщений для задачи с критичным временем реакции.


0

0

тоесть надо чтобы следующая последовательность 
 1) уложилась в 10 мс (максимум 20мс) на ядре 2.4
 2) чтобы сообщения могли посылатся несколькими процессами (вычитывающий процесс всегда один)
========================================
процесс 1:
 - установка блокировки на очередь 1
 - добавление сообщения в очередь 1
 - снятие блокировки с очереди 1
процесс 2:
 - установка блокировки на очередь 1
 - чтение сообщения с очереди 1
 - снятие блокировки с очереди 1

 - обработка сообщения(<1mc)

 - установка блокировки на очередь 2
 - добавление сообщения в очередь 2
 - снятие блокировки с очереди 2
процесс 1:
 - установка блокировки на очередь 2
 - чтение сообщения с очереди 2
 - снятие блокировки с очереди 2
========================================



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

у меня пока что наиболее жизнеспособная идея - реализовать очередь на posix shared memory а в роли блокировки пользовать fcntl()

может у кого ещё какие-то идеи есть??
★★★★★

Re: посоветуйте реализацию очереди сообщений для задачи с критичным временем реакции.

или такое быстродействие можно получить только на тредах??

cvv ★★★★★ ()

Re: посоветуйте реализацию очереди сообщений для задачи с критичным временем реакции.

А каким образом планируется использовать fcntl?

По поводу идей. 1. Linux - не realtime OS, и задача не решаема в принципе. 2. Использование нитей кажется разумным, особенно если обмен является существенной частью всей деятельости процессов. 3. Насколько я знаю, в современных Linux'ах вполне возможно размещать в shared memory все примитивы синхронизации (напр. mutex'ы).

anonymous ()

Re: посоветуйте реализацию очереди сообщений для задачи с критичным временем реакции.

>А каким образом планируется использовать fcntl?

на дескрипторе шаренной памяти

>1. Linux - не realtime OS, и задача не решаема в принципе.

тоесть получить требуемое быстродействие - проблематично?

а то что время реакции будет плавать в пределах +-10мс это не смертельно. здесь более важным является мат-ожидание

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

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

>3. Насколько я знаю, в современных Linux'ах вполне возможно размещать в shared memory все примитивы синхронизации (напр. mutex'ы).

теоретически да, на практике местами разложены грабли

так есть ли всётаки альтернативы шаренной памяти??

cvv ★★★★★ ()

Re: посоветуйте реализацию очереди сообщений для задачи с критичным временем реакции.

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

yuriy123 ()

Re: посоветуйте реализацию очереди сообщений для задачи с критичным временем реакции.

anonymous (*) (03.02.2006 12:23:26):

> ...в современных Linux'ах вполне возможно размещать в shared memory все примитивы синхронизации (напр. mutex'ы).

Если ядро 2.4, то с ним стандартно шла linux threads, а там это не так.

Die-Hard ★★★★★ ()

Re: посоветуйте реализацию очереди сообщений для задачи с критичным временем реакции.

2cvv:

Первое -- если читатель только один, то зачем тебе блокировки при чтении? Чисто алгоритмически, можно организовать очередь так, чтобы избежать блокировок при чтении.

> у меня пока что наиболее жизнеспособная идея - реализовать очередь на posix shared memory а в роли блокировки пользовать fcntl()

А насколько быстр fcntl()? Он, все же, с файловой системой взаимодействует...

Я б расшарил память через anonymous mmap, а синхронизовался спинлоками. Или, если нужна портабильность (спинлоки не сделать портабельными), то на SySV семафорах.

Die-Hard ★★★★★ ()

Re: посоветуйте реализацию очереди сообщений для задачи с критичным временем реакции.

>Первое -- если читатель только один, то зачем тебе блокировки при чтении? Чисто алгоритмически, можно организовать очередь так, чтобы избежать блокировок при чтении.

если на пайпах или сокетах то я согласен, а если на шаренной памяти то неуверен что это реализуемо

>> у меня пока что наиболее жизнеспособная идея - реализовать очередь на posix shared memory а в роли блокировки пользовать fcntl()

>А насколько быстр fcntl()? Он, все же, с файловой системой взаимодействует...

а не знаю. знал бы - не спрашивал

>Я б расшарил память через anonymous mmap, а синхронизовался спинлоками. Или, если нужна портабильность (спинлоки не сделать портабельными), то на SySV семафорах.

спинлоки из юзер-спейса? мне почемуто-казалось что это kernel-space only

cvv ★★★★★ ()

Re: посоветуйте реализацию очереди сообщений для задачи с критичным временем реакции.

> ...если на пайпах или сокетах то я согласен, а если на шаренной памяти то неуверен что это реализуемо

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

> спинлоки из юзер-спейса? мне почемуто-казалось что это kernel-space only

А не все ли равно спинлоку-то?

Разумеется, "официальных" спинлоков в libc нету, надо самому делать. Для этого нужна будет какая-либо нетривиальная атомарная операция, которой в libc тоже нет, поэтому я и сказал про проблемы с портабильностью.

Die-Hard ★★★★★ ()

Re: посоветуйте реализацию очереди сообщений для задачи с критичным временем реакции.

>> спинлоки из юзер-спейса? мне почемуто-казалось что это kernel-space only

>А не все ли равно спинлоку-то?

а вот кабы я знал

>Разумеется, "официальных" спинлоков в libc нету, надо самому делать.

а позаимстовать реализацию с ядра можно?

или вы под одним именем понимаете две совершенно различные сущности?

cvv ★★★★★ ()

Re: посоветуйте реализацию очереди сообщений для задачи с критичным временем реакции.

Спинлок - это некий механизм, который может быть реализован по-разному

http://en.wikipedia.org/wiki/Spinlock

Предполагается, что немного покрутить цикл будет меньшей бедой, чем переключаться в режим ядра и использовать какой-нибудь mutex. Для того, чтобы эта конструкция была реализуема, нужен как минимум Atomic Exchange, который, как было справедливо указано, непортабелен, но кикакой проблемы в его реализации нет.

Прежде чем вести ученый диспут, я бы убедился, что при использовании самых очевидных и незатейливых механизмов проблема возникает. Очень может быть, что с семафорами все будет замечательно работать.

anonymous ()

Re: посоветуйте реализацию очереди сообщений для задачи с критичным временем реакции.

2cvv:

Вот кусочек кода для icc для ia64 (тама icc ассемблер не поддерживает,
поэтому интринсик пришлось юзать)

#ifdef __INTEL_COMPILER
/*Use intrinsic _InterlockedExchange*/
#include <ia64intrin.h>
#define tands(lock,val) _InterlockedExchange((volatile int *)(lock),(val))
#endif

/*
Spinlock is the inline function void spinlock(int *target), it
waits until *target becomes zero and sets it to 1.
It uses the atomic operation tands (Test And Set):*/
static inline void spinlock(volatile int *target)
{
   while(  tands(target,1)!= 0 ){/*Conflict!*/
      /*Wait until a competitor finishes*/
        /* To avoid a memory HotSpot:*/
        do{}while(*target!=0);
   }
   /*Now *target is 1, and it is set definitely by this function!*/
}/*spinlock*/

Важно, флажок, на который spinlock вешается, должен быть волатильным.

Die-Hard ★★★★★ ()

Re: посоветуйте реализацию очереди сообщений для задачи с критичным временем реакции.

anonymous (*) (03.02.2006 16:26:40)Ж

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

А всякие мутексы все равно со спинлока начинаются.

> Очень может быть, что с семафорами все будет замечательно работать.

Они тормозят. К тому же, SySV семафоры довольно плохо портабельны (семантика semctl() различается на разных системах), а posix семафоры в linux threads не работают между процессами. Да и проще спинлоки.

Другое дело, что, если очередь ограничена, то все равно придется писателей усыплять, если очередь переполнилась. Да и с читателем надо что-то делать, когда очередь пуста. Так что без какого-либо подобия семафора/мутекса все равно вряд ли обойтись.

Die-Hard ★★★★★ ()

Re: посоветуйте реализацию очереди сообщений для задачи с критичным временем реакции.

>> Очень может быть, что с семафорами все будет замечательно работать.

>Они тормозят

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

anonymous ()

Re: посоветуйте реализацию очереди сообщений для задачи с критичным временем реакции.

спасибо

никогда не думал что за словом spinlock такая карусель прячется :)

а не раскажите как засыпание на семафорах реализуют? Для общего развития, довольно интересно

cvv ★★★★★ ()

Re: посоветуйте реализацию очереди сообщений для задачи с критичным временем реакции.

2cvv

> а не раскажите как засыпание на семафорах реализуют?

Ну, это надо idle спрашивать :) Я в ядре никогда не копался.

Когда-то я делал юзерспейсовские семафоры на спинлоках и sigsuspend. Разумеется, они были не совсем юзерспейсовские, поскольку спали в ядре на sigsuspend. Но они тормозили по сравнению SySV семафорами -- не в разы, но на проценты -- и я переключился на SySV. Конечно, пришлось с ними возиться -- ifdef'ы на разные системы, демон-гард, который их подчищает в случае несанкционированной смерти вызывающего, и т.п.

Die-Hard ★★★★★ ()

Re: посоветуйте реализацию очереди сообщений для задачи с критичным временем реакции.

>а не раскажите как засыпание на семафорах реализуют? Для общего развития, довольно интересно

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

На концептуальном уровне все очень просто ;)

anonymous ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.