Атомарные операции над переменной

инкремент/декремент sig_atomic_t на i386 всегда атомарный.

>но где-то в гугле прочитал, что инкремент и декремент могут не быть атомарными. Это так?

на многопроцесорных системах. например NUMA

2cvv

> инкремент/декремент sig_atomic_t на i386 всегда атомарный.

Нет.

_Доступ_ к sig_atomic_t атомарный. Доступ, а не инкремент/декремент.

> Есть ли в POSIX тип, который гарантирует атомарность некторых операций над собой? Нужно сравнение, инкремент и декремент.

Разумеется, нет!

Более того, насколько мне известно, атомарных операций тоже нет.

А какой самый лучший обходной путь предложите? Окружить переменную мьютексами? или заменить ее на семафор?

Есть какой-нибудь опыт в этом деле?

>2cvv

>> инкремент/декремент sig_atomic_t на i386 всегда атомарный.

>Нет.

>_Доступ_ к sig_atomic_t атомарный. Доступ, а не инкремент/декремент.

Я доселе считал что ето может быть только в случае крайней кривизны кода сгенерированного компилером. Ведь в принципе любое атомарное действие можно сделать неатомарным.

Обьясни, пожайлуста.

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

На gcc -- выдрать соответствующую ассемблерную вставку из кода libc.

На icc есть интринсики.

> Есть какой-нибудь опыт в этом деле? 

Портабильного нет.

На ia64 меня интересует только icc, там я пользуюсь
интринсиками. Например,

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

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*/ 

Еще интринсики:

int _InterlockedIncrement(volatile int *addend )
int _InterlockedDecrement(volatile int *addend )


> заменить ее на семафор? 

Ни в коем случае! Очень тормозить будет. 
Тут нужен не семафор, а спинлок. Но для реализации спинлока
потребуется как раз эта самая атомарная операция :(

Если все же нужен POSIX, то придется прикрывать операцию мьютексом -- 
будет сильно тормозить...

>> заменить ее на семафор?

>Ни в коем случае! Очень тормозить будет. >Тут нужен не семафор, а спинлок. Но для реализации спинлока >потребуется как раз эта самая атомарная операция :(

>Если все же нужен POSIX, то придется прикрывать операцию мьютексом >-- >будет сильно тормозить...

Вот-вот.. Я тоже так думаю.. Ассемблерные вставки не катят. Нуждна переносимость. идеал - позикс.

Кстати а как с переносимостью у макросов в файле /usr/include/asm/atomic.h? Там как раз то что нужно. Я почти уверен что их может не быть на других системах. Но может я неправ? =)

В моей ситуации выход - пересмотреть алгоритм, чтобы это было не нужно =)

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

2cvv:

> Обьясни, пожайлуста.

Без блокировки шины инкремент/декремент в принципе не может быть атомарным. Тип данных тут не при чем. Тем более, sig_atomic_t всего лишь int:

/usr/include/bits/sigset.h:typedef int __sig_atomic_t;

Не знаю, как на одноглавом компутере -- ни разу сам не наблюдал райсов при инкременте -- но на двухпроцессорной архитектуре мгновенно воспроизводится:

i=0;/*first thread:*/i++;/*second thread:*/i++;/*main thread:*/if(i==1)printf("1+1=1!\n");

> Кстати а как с переносимостью у макросов в файле /usr/include/asm/atomic.h? Там как раз то что нужно. Я почти уверен что их может не быть на других системах. Но может я неправ? =)

Прав :(

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

Увы!

Если нужен Посикс, то только мьютексы или семафоры.

Но ассемблерные вставки будут работать _почти_ везде. Может, не нужен уж _очень_ строгий Посикс?

Кстати, я не совсем правильно тебя понял -- конечно, тебе надо просто семафор использовать в качестве счетчика, не будет сильно тормозить (я думал, ты инкремент хочешь семафором прикрывать). Тормозить будет _разблокировка_, которой у тебя не будет.

Вдогонку -- в случае использования семафора, обрати внимание на трудности со сравнением. Инкремент получишь без труда, на декременте рискуешь уснуть, а со сравнением -- надо думать...

Проблема будет еще одна. Буфероф будет много.. То есть семафоров может быть одновременно пара сотен. Это наверное не особо хорошо с точки зрения экономии памяти.

по-видимому товаришч спарашивает про аналог
InterlockedIncrement, InterlockedDecrement etc.

Вот как это реализовано в wine:
http://cvs.winehq.com/cvsweb/wine/libs/port/interlocked.c?rev=1.3

++
http://cvs.winehq.org/cvsweb/~checkout~/wine/dlls/kernel/sync.c?rev=1.77&...

Да... Это тол что нужно.. Но асм пихать не хочется совсем...

Хм.. хм.. А не знаешь где-нибудь пример примитвного буфера со счетчиком ссылок?

Кстати, сейчас сравнил SySV семафоры с заспинлоченным инкрементом/декрементом 
волатильной переменной (что, очевидно, _дольше_, чем
 InterlockedIncrement/InterlockedDecrement):

#define MAXI 12800000

int semPost(int sem)
{
struct sembuf sem_op;
   sem_op.sem_num = 0;
   sem_op.sem_op =1;
   sem_op.sem_flg = 0;
   return semop(sem,&sem_op, 1);
}

int semWait(int sem)
{
struct sembuf sem_op;
   sem_op.sem_num = 0;
   sem_op.sem_op =-1;
   sem_op.sem_flg = 0;
   return semop(sem,&sem_op, 1);
}

static volatile int spl=0;

int incr(int *i)
{
   spinlock(&spl);
   (*i)++;
   spl=0;
   return *i;
}
int decr(int *i)
{
   spinlock(&spl);
   (*i)--;
   spl=0;
   return *i;
}

. . .

volatile int vol=0;
. . .

    ts=clock();
    for(i=0; i<MAXI;i++){
              semPost(sems);
              semWait(sems);
    }

    fprintf(stderr,"Sems: %.2f\n",(double)(clock()-ts)/CLOCKS_PER_SEC);

    ts=clock();
    for(i=0; i<MAXI;i++){
              incr(&vol);
              decr(&vol);
    }

    fprintf(stderr,"Vol: %.2f\n",(double)(clock()-ts)/CLOCKS_PER_SEC);

. . . 

(код spinlock() я приводил выше)

Результат:
Sems: 11.21
Vol: 0.43

Тормозит, однако!

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

Вдогонку -- исправил int incr(int *i) на  int incr(volatile int *i)
(аналогично с decr) -- чуть притормозило, но до семафоров пока далеко:

Sems: 11.26
Vol: 0.59

> Что и следовало ожидать..

если честно, то я не ождал, что так все машинно_зависимо

>чуть притормозило, но до семафоров пока далеко:

А если использовать не ipc семафоры, а posix, 
или вместо
    spinlock(&spl)
использовать 
    pthread_mutex_lock()
какие будут скорости?

2mky :

> А если использовать не ipc семафоры, а posix

Счас спробую. По моим наблюдениям, ipc семафоры _очень_ быстрЫ, но я прикидывал это, в основном, на тему пробуждения спящих процессов.

> или вместо spinlock(&spl) использовать pthread_mutex_lock()

Очевидно, мьютекс будет на _порядки_ медленнее спинлока: во-первых, мьютексы должны проходить через ядро; во вторых, в начале любого мьютекса идет спинлок.

2idle:

Ты где? Приди и все объясни, как обычно!:-)

А кстати.. попробуй еще futex потестировать.

2OxiD :

> попробуй еще futex потестировать.

Увы :(

Моя проблема в том, что у меня 2.4 ядро... Знал бы ты, как я с Нумой извращаюсь!:)

Я "живу" на Альтиксах. Они переползают с Красной Шапки на СуСЮ, но у меня аккурат кончилась поддержка. Предлагают за "смешную" сумму в $30 000 продлить поддержку на год -- я на хрен их послал. Конечно, деньги не мои, но за $30K я могу себе новый 2-brick Альтикс попросить (правда, без поддержки).

Главная проблема в том, что мне не так просто проводить single user эксперименты: production задачи на компьютере крутятся месяцами. К счастью, купили новый Альтикс на 8 процессоров -- пока что только для меня. К сожалению, моя лафа недолга -- мне дают с ним поиграться только с полгода. Через полгода я должен гарантировать, что он заработает в кооперации с большим; типа, NUMA роутер прикупят. Потом обещают для меня 8 процессоров держать свободными, но сейчас я не могу обновить Линух на большой машине, поскольку она считает...

Спробовал Позикс семафоры.

Ближе, но все равно от спинлоков далеко:

Sems: 11.32
Vol: 0.59
psem: 6.34

Кстати, насколько мне помнится (завтра потестирую), Позикс семафоры
были сильны именно в смысле "тупых" операций +/-, поскольку половина в юзерспейсе выполнялось;
но вот для пробуждения процесса они используют rt сигналы, что _гораздо_
дольше ipc семафоров.

Код (только про Посикс семафоры, остальное раньше постил):


#include <semaphore.h>

. . .
sem_t psem;
. . .

if(sem_init(&psem,0,0)){
     perror("CreateSemaphore");
     exit(0);
}

. . .

    ts=clock();
           for(i=0; i<MAXI;i++){
              sem_post(&psem);
              sem_wait(&psem);
           }

    fprintf(stderr,"psem: %.2f\n",(double)(clock()-ts)/CLOCKS_PER_SEC);

Да, для полноты ощущений:

2.4.21-sgi303r2 #1 SMP Mon Nov 29 15:29:38 PST 2004 ia64

cat /etc/sgi-release:

SGI ProPack 3SP3 for Linux, Build 303r6-0411291521

>> Обьясни, пожайлуста.

>Без блокировки шины инкремент/декремент в принципе не может быть атомарным. Тип данных тут не при чем. Тем более, sig_atomic_t всего лишь int:

>/usr/include/bits/sigset.h:typedef int __sig_atomic_t;

>Не знаю, как на одноглавом компутере -- ни разу сам не наблюдал райсов при инкременте -- но на двухпроцессорной архитектуре мгновенно воспроизводится:

>i=0;/*first thread:*/i++;/*second thread:*/i++;/*main thread:*/if(i==1)printf("1+1=1!\n");

я имел ввиду только одноглавые компутеры

cvv:

> я имел ввиду только одноглавые компутеры

А там треды -- давить!

>> я имел ввиду только одноглавые компутеры

>А там треды -- давить!

Зачем???

кстати а насколько портабельны спинлоки???

я немножко запутался в этом топике.

конечно, для атомарного изменения переменной нужны
специальные примитивы, и эти примитивы зависят от
архитектуры. но ведь они есть в include/atoimic.h?
или проблема в том, что они не стандартны? в таком
случае я удивлен, стандартов я не знаю, но ведь это
очевидно необходимая вещь, неужели нету?

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

> > или вместо spinlock(&spl) использовать pthread_mutex_lock()
>
> Очевидно, мьютекс будет на _порядки_ медленнее спинлока: во-первых, мьютексы должны проходить через ядро; во вторых, в
> начале любого мьютекса идет спинлок.

вообще-то, это не факт. я сам не пользовался всем
этим, поэтому могу обмануть. но по идее, если семафоры
реализованы через futex (а вроде так и есть в nptl),
то должны они работать быстро, причем в uncontended
случае даже без входа в ядро.

я не 100% уверен, но в http://people.redhat.com/drepper/futex.pdf
что-то есть про это.

другое дело, что вроде бы не имеет смысла в данном
случае использовать семафоры (т.е. блокировки, которые
работают усыпляя процесс), бльше подходит spinlock,
т.е. busy-wait.

но все равно это будет медленнее, spinlock ведь сам
реализован с помощью (фактически) atomic_dec_and_test,
хотя это тоже от архитектуры зависит.

так что я мало что могу добавить к тому, что уже
сказал Die-Hard.

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

2idle:

> ...но ведь они есть в include/atoimic.h? или проблема в том, что они не стандартны?

Увы, не в include/atoimic.h, а в include/asm/atomic.h. Они, действительно, не стандартны...

> по идее, если семафоры реализованы через futex (а вроде так и есть в nptl), то должны они работать быстро, причем в uncontended случае даже без входа в ядро.

Все равно дольше спинлоков.

А мне вдруг интересно стало -- как без входа в ядро определить, uncontented случай, или нет?

cvv:

>> ...треды -- давить!

> Зачем???

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

> кстати а насколько портабельны спинлоки???

Увы:( Вообще не портабильны.

> Увы, не в include/atoimic.h, а в include/asm/atomic.h

все равно не понимаю. то есть, я не могу просто
сказать #include <asm/atoimic.h> ?

я имею в виду, что есть платформы, которые POSIX,
но не имеют там реализации atomic_... ?

> > по идее, если семафоры реализованы через futex (а вроде
> > так и есть в nptl), то должны они работать быстро,
>
> Все равно дольше спинлоков.

конечно! и даже не потому, что они медленнее, они "должны"
работать приблизительно с одинаковой скоростью если семафор
или spinlock свободен. а потому, что когда он занят, spinlock
просто подождет несколько нан (инкремент-то быстро работает), 
а в случае futex процесс пойдет в кернел и заснет, обладатель
семафора должен будет его будить при освобождении семафора,
это опять в ядро, ну и так далее.

> А мне вдруг интересно стало -- как без входа в ядро определить,
> uncontented случай, или нет?

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

user level nptl code - очень грубо говоря - пытается захватить
семафор как spinlock. если не получилось (contended случай),
только тогда он вызывает ядерный futex_wait().

при освобождении вызов futex_wake() происходит только, если
кто-то этого семафора ждет в ядре.

например (это совсем не так реализовано, все гораздо хитрее,
и этот код просто непраильный, только для иллюстрации идеи)

lock(int *futex)
{
again:
      val = ++*futext;

      if (val == 1)
           return; // семафор захвачен

      // спать, пока значение по адр futex не поменяется
      futex_wait(futex, val);
      goto again;
}

unlock(int *futex)
{
      if (--*futex == 0)
            return; // некого будить.

      // разбудить тех, кто ждет изменения *futex
      futex_wake(futex);
}

повторяю, приведенный "код" никакого отношения к реальности
не имеет.

2idle:

> очень грубо говоря - пытается захватить семафор как spinlock. если не получилось (contended случай), только тогда он вызывает ядерный futex_wait().

Да, конечно, прошу прощения, ступил -- я и сам точно так же делаю :)

В POSIX нет, но: Linux: asm/atomic.h, FreeBSD: src/sys/i386/include/atomic.h, Windows: семейство Interlocked функций, SunOS: sys/atomic.h. Над всем этим обёртка в виде С++ класса делается на раз. Можно работать как с простой переменной. У меня это реализовано через шаблонный класс Atomic. Работает так: Threading::Atomic< Long > val; ...

>> я имел ввиду только одноглавые компутеры >А там треды -- давить!

Не согласен. Хоть на однопроцессорной машине выигрыша производительности не будет (как бы не наоборот), но имхо многие вещи написать гораздо проще используя потоки. С точки зрения алгоритма.

посмотрел "asm/atomic.h", не понял, как это делается под linux
(uname -a
Linux pcroot4.cern.ch 2.4.18-3smp #1 SMP Thu Apr 18 07:27:31 EDT 2002 i686 unknown
)


#ifndef __ARCH_I386_ATOMIC__
#define __ARCH_I386_ATOMIC__

#include <linux/config.h>

/*
* Atomic operations that C can't guarantee us. Useful for
* resource counting etc..
*/

/*
* Make sure gcc doesn't try to be clever and move things around
* on us. We need to use _exactly_ the address the user gave us,
* not some alias that contains the same information.
*/
typedef struct { volatile int counter; } atomic_t;

#define ATOMIC_INIT(i) { (i) }

/**
* atomic_read - read atomic variable
* @v: pointer of type atomic_t
*
* Atomically reads the value of @v. Note that the guaranteed
* useful range of an atomic_t is only 24 bits.
*/
#define atomic_read(v) ((v)->counter)

/**
* atomic_set - set atomic variable
* @v: pointer of type atomic_t
* @i: required value
*
* Atomically sets the value of @v to @i. Note that the guaranteed
* useful range of an atomic_t is only 24 bits.
*/
#define atomic_set(v,i) (((v)->counter) = (i))


#warning Using kernel header in userland program. BAD!
#endif

#ifndef __ARCH_I386_ATOMIC__ #define __ARCH_I386_ATOMIC__

#include <linux/config.h>

/* * Atomic operations that C can't guarantee us. Useful for * resource counting etc.. */

#ifdef CONFIG_SMP #define LOCK "lock ; " #else #define LOCK "" #endif

/* * Make sure gcc doesn't try to be clever and move things around * on us. We need to use _exactly_ the address the user gave us, * not some alias that contains the same information. */ typedef struct { volatile int counter; } atomic_t;

#define ATOMIC_INIT(i) { (i) }

/** * atomic_read - read atomic variable * @v: pointer of type atomic_t * * Atomically reads the value of @v. */ #define atomic_read(v) ((v)->counter)

/** * atomic_set - set atomic variable * @v: pointer of type atomic_t * @i: required value * * Atomically sets the value of @v to @i. */ #define atomic_set(v,i) (((v)->counter) = (i))

/** * atomic_add - add integer to atomic variable * @i: integer value to add * @v: pointer of type atomic_t * * Atomically adds @i to @v. */ static __inline__ void atomic_add(int i, atomic_t *v) { __asm__ __volatile__( LOCK "addl %1,%0" :"=m" (v->counter) :"ir" (i), "m" (v->counter)); }

/** * atomic_sub - subtract the atomic variable * @i: integer value to subtract * @v: pointer of type atomic_t * * Atomically subtracts @i from @v. */ static __inline__ void atomic_sub(int i, atomic_t *v) { __asm__ __volatile__( LOCK "subl %1,%0" :"=m" (v->counter) :"ir" (i), "m" (v->counter)); }

/** * atomic_sub_and_test - subtract value from variable and test result * @i: integer value to subtract * @v: pointer of type atomic_t * * Atomically subtracts @i from @v and returns * true if the result is zero, or false for all * other cases. */ static __inline__ int atomic_sub_and_test(int i, atomic_t *v) { unsigned char c;

__asm__ __volatile__( LOCK "subl %2,%0; sete %1" :"=m" (v->counter), "=qm" (c) :"ir" (i), "m" (v->counter) : "memory"); return c; }

/** * atomic_inc - increment atomic variable * @v: pointer of type atomic_t * * Atomically increments @v by 1. */ static __inline__ void atomic_inc(atomic_t *v) { __asm__ __volatile__( LOCK "incl %0" :"=m" (v->counter) :"m" (v->counter)); }

/** * atomic_dec - decrement atomic variable * @v: pointer of type atomic_t * * Atomically decrements @v by 1. */ static __inline__ void atomic_dec(atomic_t *v) { __asm__ __volatile__( LOCK "decl %0" :"=m" (v->counter) :"m" (v->counter)); }

/** * atomic_dec_and_test - decrement and test * @v: pointer of type atomic_t * * Atomically decrements @v by 1 and * returns true if the result is 0, or false for all other * cases. */ static __inline__ int atomic_dec_and_test(atomic_t *v) { unsigned char c;

__asm__ __volatile__( LOCK "decl %0; sete %1" :"=m" (v->counter), "=qm" (c) :"m" (v->counter) : "memory"); return c != 0; }

/** * atomic_inc_and_test - increment and test * @v: pointer of type atomic_t * * Atomically increments @v by 1 * and returns true if the result is zero, or false for all * other cases. */ static __inline__ int atomic_inc_and_test(atomic_t *v) { unsigned char c;

__asm__ __volatile__( LOCK "incl %0; sete %1" :"=m" (v->counter), "=qm" (c) :"m" (v->counter) : "memory"); return c != 0; }

/** * atomic_add_negative - add and test if negative * @v: pointer of type atomic_t * @i: integer value to add * * Atomically adds @i to @v and returns true * if the result is negative, or false when * result is greater than or equal to zero. */ static __inline__ int atomic_add_negative(int i, atomic_t *v) { unsigned char c;

__asm__ __volatile__( LOCK "addl %2,%0; sets %1" :"=m" (v->counter), "=qm" (c) :"ir" (i), "m" (v->counter) : "memory"); return c; }

по-видимому у меня старинный linux (??)

В linux 2.0.40 тоже самое.

#ifndef __ARCH_I386_ATOMIC__
#define __ARCH_I386_ATOMIC__

/*
* Atomic operations that C can't guarantee us. Useful for
* resource counting etc..
*/

#ifdef __SMP__
#define LOCK "lock ; "
#else
#define LOCK ""
#endif

/*
* Make sure gcc doesn't try to be clever and move things around
* on us. We need to use _exactly_ the address the user gave us,
* not some alias that contains the same information.
*/
#define __atomic_fool_gcc(x) (*(struct { int a[100]; } *)x)

typedef int atomic_t;

static __inline__ void atomic_add(atomic_t i, atomic_t *v)
{
__asm__ __volatile__(
LOCK "addl %1,%0"
:"=m" (__atomic_fool_gcc(v))
:"ir" (i), "m" (__atomic_fool_gcc(v)));
}

static __inline__ void atomic_sub(atomic_t i, atomic_t *v)
{
__asm__ __volatile__(
LOCK "subl %1,%0"
:"=m" (__atomic_fool_gcc(v))
:"ir" (i), "m" (__atomic_fool_gcc(v)));
}

static __inline__ void atomic_inc(atomic_t *v)
{
__asm__ __volatile__(
LOCK "incl %0"
:"=m" (__atomic_fool_gcc(v))
:"m" (__atomic_fool_gcc(v)));
}

static __inline__ void atomic_dec(atomic_t *v)
{
__asm__ __volatile__(
LOCK "decl %0"
:"=m" (__atomic_fool_gcc(v))
:"m" (__atomic_fool_gcc(v)));
}

static __inline__ int atomic_dec_and_test(atomic_t *v)
{
unsigned char c;

__asm__ __volatile__(
LOCK "decl %0; sete %1"
:"=m" (__atomic_fool_gcc(v)), "=qm" (c)
:"m" (__atomic_fool_gcc(v)));
return c != 0;
}

#endif

тогда я совсем ничего не понимаю ...
я смотрю на /usr/include/asm/atomic.h

> тогда я совсем ничего не понимаю ...

а что непонятно ?

> я смотрю на /usr/include/asm/atomic.h

это реализация kernel-level, у вас, судя по всему,
/usr/include/asm - symlink. не надо этого делать.

ls -ls /usr/include/
4 drwxr-xr-x 2 root root 4096 Aug 23 2002 asm

2OxiD:

> ...многие вещи написать гораздо проще используя потоки. С точки зрения алгоритма.

Не согласен. Но спорить не буду:)