Как работает Compare и Swap?

Я прочитал довольно некоторые посты, которые говорят, что сравнения и замена гарантирует атомарность, однако я до сих пор не в состоянии получить, как это делает ?? Это общий псевдо-код для сравнения и замены -Как работает Compare и Swap?

int CAS(int *ptr,int oldvalue,int newvalue) 
{ 
    int temp = *ptr; 
    if(*ptr == oldvalue) 
     *ptr = newvalue 
    return temp; 
}

как делает это гарантирует атомарность. Например, если я использую это для реализации семафора,

void lock(int *mutex) 
{ 
    while(!CAS(mutex, 0 , 1)); 
}

как это предотвратить 2 темы от приобретения мьютекса в то же время? Любые указатели будут действительно оценены.

источник

2014-03-12 knuckle_ball

Уверенный: 'ptr',' mutex', 'NULL' ... –

Безопаснее не реализовывать свой собственный мьютекс, а использовать некоторые из системы, такие как' pthread_mutex_lock'/_unlock от glibc (с интерфейсом, определенным в POSIX: http://pubs.opengroup.org/onlinepubs/009695399/functions/pthread_mutex_lock.html) – osgx

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

«общий псевдокод» не является фактическим кодом реализации CAS (сравнение и своп). Специальные аппаратные инструкции используются для активации специального атомного оборудования в ЦП. Например, в x86 можно использовать LOCK CMPXCHG (http://en.wikipedia.org/wiki/Compare-and-swap).

В gcc, например, есть __sync_val_compare_and_swap() встроенный - который реализует аппаратный атомный CAS. Описана эта операция из свежей замечательной книги Павла Маккенни (Is Parallel Programming Hard, And, If So, What Can You Do About It?, 2014), раздел 4.3 «Атомные операции», страницы 31-32.

Если вы хотите узнать больше о построении синхронизации более высокого уровня над атомными операциями и сохранить вашу систему из спин-локов и горящих циклов процессора при активном вращении, вы можете прочитать что-то о механизме futex в Linux. Первая статья о futexes - Futexes are tricky от Ulrich Drepper 2011; другая статья LWN http://lwn.net/Articles/360699/ (и исторический один Fuss, Futexes and Furwocks: Fast Userland Locking in Linux, 2002)

мьютекс замков, описанные Ульриха используют только атомарные операции для «быстрого пути» (если мьютекс не заперт, и наш поток является единственным, кто хочет заблокируйте его), но если мьютекс был заблокирован, поток перейдет в спящий режим с помощью futex (FUTEX_WAIT ...) (и он будет отмечать переменную мьютекса с помощью атомной операции, чтобы сообщить разблокирующему потоку о «есть кто-то, этот мьютекс», так Разблокировка будет знать, что он должен разбудить их, используя futex (FUTEX_WAKE, ...)

источник

2014-03-12 00:20:53 osgx

Как это предотвратить две нити от приобретения замка? Ну, если какой-либо один поток успешно, *mutex будет 1, так что любой другой поток CAS не сработает (потому что он вызывается с ожидаемым значением 0). Блокировка освобождается, сохраняя 0 в *mutex.

Обратите внимание, что это нечетное использование CAS, так как это по существу , требующее нарушение ABA. Как правило, вы бы просто использовать обычный атомный обмен:

while (exchange(mutex, 1) == 1) { /* spin */ } 

// critical section 

*mutex = 0; // atomically

Или, если вы хотите быть немного более сложной и хранить информацию о том, какой нить имеет блокировку, вы можете делать трюки с атомно-выборка и добавление (см., например, код спин-блокировки ядра Linux).

источник

2014-03-12 00:21:01

Как работает Compare и Swap?

ответ

Смежные вопросы