семафоры

POSIX семафоры. По крайней мере из соображений переносимости.

В рамках POSIX есть только POSIX семафоры...

Серьезно, про все остальное забудь. И подумай, нужны ли они (семафоры) тебе вообще.

Если все ж тебе нужны именно семафоры, то Sytem V семафоры в ядерном контексте самые шустрые, но идеологически "неправильные"...

>В рамках POSIX есть только POSIX семафоры...
Позволю не согласиться:
Семафоры SysV в POSIX "легализованы" по крайней мере в версии стандарта от 2004 года. Так что сейчас они входят и в POSIX.
А что касается данного вопроса то, если семафоры используются в рамках одного процесса, разумно будет использовать POSIX семафоры или, 
если требуется только синхронизация потоков, то лучше рассмотреть 
вариант с мьютексами.

romanSA(*) (30.04.2006 1:22:35):

Собственно, я о том и говорю...

Семафоры нужны, поскольку осущуствляется работа со структрутой ограниченного размера, один тип потоков ее напонляет, второй - опустошает. По-моему, это классический случай для семафоров, но если вы подскажете как здесь можно обойтись без них - я буду только рад :)

Ну если ВСЕ типы потоков изменяют вашу структуру, то можно просто 
использовать мьютексы для ограничения доступа к структуре:
  
   pthread_mutex_lock (&mutex);

   /* 
    * здесь читаем и изменяем структуру 
    */

   pthread_mutex_unlock (&mutex);

По мьютексам нужно смотреть кроме вышеперечисленного:
pthread_mutex_init(), pthread_mutex_destroy()

Если же нужно чтобы несколько потоков могли читать структуру 
одновременно (конечно не тогда, когда в нее пишут), то советую
использовать блокировки чтения/записи (смотреть 
pthread_rwlock_init() ).
Ну а для оповещения потоков о том, что структура изменилась можно 
использовать pthread_cond_signal().

P.S. Рекомендую почитать UNIX Network Programming Стивенса 
(во втором томе там все очень хорошо про это написано), тем более,
что есть неплохой перевод издательсва Питер (http://www.piter.com/).

Мне нужно немного не так. В последнем посте я вроде понятно написал. Структура ограниченного размера. Одни потоки ее наполняют - другие опустошают. Семафор показывает, сколько еще мона записать в струтктуру. Когда он 0 - пишущие блокируются

Я бы все-таки использовал мьютексы условные переменные и проверял бы значение счетчика в структуре. Для меня это нагляднее.

Для пишущего потока:

  pthread_mutex_lock (&mutex);

  while (data.count >= data.max_count)
    pthread_cond_wait (&write_cond, &mutex);

  if (data.count < data.max_count)
    add_data ();

  pthread_cond_signal (&read_cond);

  pthread_mutex_unlock (&mutex);

Для читающего потока:

  pthread_mutex_lock (&mutex);

  while (data.count == 0)
    pthread_cond_wait (&read_cond, &mutex);

  if (data.count > 0)
    extract_data ();

  pthread_cond_signal (&write_cond);

  pthread_mutex_unlock (&mutex);


Если все же нужно использовать семафоры, то для этой задачи лучше 
подойдут именно SysV, так как там проще контролировать значение
семафора. В POSIX же версии прийдется его "вычислять", так как там 
нет возможности получить это значение напрямую.
Однако следует помнить, что SysV семафор - это объект ядра, который
не удаляется автоматически при завершении приложения.

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

>В POSIX же версии прийдется его "вычислять", так как там нет возможности получить это значение напрямую.

Хм, а что тогда делает int sem_getvalue(sem_t * sem, int * sval); ?

!sem_getvalue! stores in the location pointed to by |sval| the current count of the semaphore |sem|.

Что странно, она работает...

2roy:

Если _один_ пишет, а другой (но тоже _один_) читает в ФИФО, то ни семафоры, ни мьютексы _не_нужны_ вообще! Достаточно атомарности присваивания указателю, а она присутствует во всех реализациях Це.

Для стека, или если читателей/писателей больше одного, увы.

2 roy:
Ну насчет sem_getvalue() стандарт говорит:
  The sem_getvalue() function is part of the Semaphores option and
  need not be available on all implementations.

А я привык писать "портабельный" код. Но если у Вас нет необходимости 
переносить приложение под другие *nix, то нет проблем.
Впрочем остается одна загвоздка (не по данной задаче): значение SysV
семафора задать можно любое, а у POSIX кроме sem_wait() и sem_post() 
и воспользоваться-то нечем.

По поводу замены предложенного мной кода на POSIX семафоры: 
кто Вам сказал, что связка sem_getvalue() + sem_post() или 
sem_getvalue() + sem_wait() атомарна? По большому счету Вам все-равно 
потребуется использовать какие-либо механизмы синхронизации.

2 Die-Hard:
Насчет FIFO почти согласен, но что делать, если читающий поток 
работает значительно медленнее пишущего (т.е. возможно 
"переполнение FIFO")? 

romanSA (*) (30.04.2006 23:59:35):

> что делать, если читающий поток работает значительно медленнее пишущего (т.е. возможно "переполнение FIFO")?

Дык, в чем проблемы - то? Писатель ведет счетчик, и если он слишком большой, засыпает. Читатель его будит, когда прочитает порцайку. Максимум ошибки будет в одну позицию (когда читатель уже прочитал ячейку, но еще не уменьшил счетчик), что обычно принебрежимо.

Конечно, для этого нужен атомарный инкремент, который, вообще говоря, в Це отсутствует. Но его всегда можно сделать.

Альтернатива -- каждый раз пересчитывать писателем количество ячеек. Если их всего несколько штук, то оверхэд будет меньше путешествия в ядро и обратно, как на SySV семафорах, например.

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

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

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

2 romanSA:

> "запись слова в память" есть операция атомарная.

только если слово выровнено по границе слова.

>о поводу замены предложенного мной кода на POSIX семафоры: кто Вам сказал, что связка sem_getvalue() + sem_post() или sem_getvalue() + sem_wait() атомарна? По большому счету Вам все-равно потребуется использовать какие-либо механизмы синхронизации.

Semaphores are counters for resources shared between threads. The basic operations on semaphores are: increment the counter atomically, and wait until the counter is non-null and decrement it atomically.

Спасибо всем за ткое внимание к треду, но то что я хотел - я узнал, и уже написал, и все работает. Без семафоров никак - и читателей и писаталеей переменное число.

По поводу переносимости - не является целью проекта, тем более уже и так есть функции, доступные как я понял только в GNU LIBC.

>>Если _один_ пишет, а другой (но тоже _один_) читает в ФИФО, то ни >>семафоры, ни мьютексы _не_нужны_ вообще! Достаточно атомарности >>присваивания указателю, а она присутствует во всех реализациях Це.

Присвоение указателей действиельно атомарно, и это в POSIX прописано. Но на SMP это может не сработать:

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

Motl :

> ... действиельно атомарно, ... Но на SMP это может не сработать...

1. Атомарность никак от барьеров не зависит;

2. Ну да, говорят, барьер нужно делать явно. Но, вообще говоря, как я понимаю, достаточно будет volatile: компилятор тогда сам барьер сделает, если надо. Недавно долго тут обсуждали -- у меня сложилось впечатление, что volatile будет достаточно (хотя idle утверждает, что, вообще говоря, нет).

Как будет время, попробую разобраться с этим плотнее.

Я гонял довольно интенсивные тесты на Оптеронах и Итаниках, там волатильности указателя было достаточно.

> Хм, а что тогда делает int sem_getvalue(sem_t * sem, int * sval); ?

как только я встречаю аппеляцию к sem_getvalue(), у меня почему-то сразу возникает стойкое ощущение большой проблемы и неверной архитектуры системы :)

// wbr

> (хотя idle утверждает, что, вообще говоря, нет).

точно недостаточно

> компилятор тогда сам барьер сделает, если надо.

сомневаюсь, это дорогая операция (на тех архитектурах,
где wbm() не пустышка).

пример.

    whaterver_t data, *ptr_to_data;

писатель:

    data = ....;
    wmb();
    ptr_to_data = &data;

volatile - не достаточно, это барьер только для компилятора.
ptr_to_data должен быть выровнен, тогда запись в него атомарна.

а теперь сюрприз. вот такой код для читателя

    copy_of_data = *ptr_to_data;

вообще говоря не работает. это странно, но процессор может
прочитать '*ptr' _перед_ 'ptr'. правда, такое может быть
только при очень weak memory model (alpha).

поэтому код для читателя:

    my_ptr = ptr_to_data;        // 1
    read_barrier_depends();
    copy_of_data = *my_ptr;      // 2

опять-таки, volatile нам не поможет никак, компилятор и без
него не может переставить 1 и 2.

А как такое организовать в программе ? Т.е. что использовать в качестве функции read_barrier_depends(); ?

> что использовать в качестве функции read_barrier_depends(); ?

еще раз: из тех архитектур, на которых работает linux,
только alpha требует read_barrier_depends(), и он
реализован как mb(). хотя - я уверен - достаточно было
бы rmb(). на остальных это 'do ; while (0)'.

2idle:

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

Глупость какая. Это ж просто баг!

> ptr_to_data должен быть выровнен, тогда запись в него атомарна.

А как он _может_ быть не выровнен? Все мои знакомые компиляторы, вроде, выравнивают все целые типы.

>> правда, такое может быть >> только при очень weak memory model (alpha).

Если посмотреть реализацию атомиков в glib (2.10), там memory barrier используются помимо alpha для powerpc, для sparc итп. Короче, почти для всего, кроме x86-64.

Как раз Opteron не показатель в данном случае.

На нем не будет out-of-order execution.

> Глупость какая. Это ж просто баг!

не согласен, и не согласен сильно.

с моей точки зрения, volatile вообще никакого отношения
к барьерам не имеет - это самое главное, и во-первых.

во-вторых, барьеры действительно дороги, должны быть под
контролем программиста.

и наконец, компилятор не может знать, какой барьер нам нужен.
к примеру, запись в pci регистр происходит через volatile *reg.
барьеры памяти здесь вообще не при чем, нам нужен mmiowb().
в то же время, нам нужен volatile, иначе компилятор может
"оптимизировать"

    *reg = CMD_ВЫПУСТИТЬ_ШАССИ;
    *reg = CMD_ПРИЗЕМЛЯЦЦА;

> > только при очень weak memory model (alpha).
>
> там memory barrier используются помимо alpha для powerpc,
> для sparc итп. Короче, почти для всего, кроме x86-64.

вы не поняли, посмотрите внимательнее, о чем я говорил.

речь идет об очень специфичном барьере: read_barrier_depends()
не нужен он на ppc:

include/asm-powerpc/system.h:
    #define read_barrier_depends()  do { } while(0)

> На нем не будет out-of-order execution.

дело не только и не столько в o-o-o-e.