Почему доступ к порядковым номерам ключей pthread не синхронизирован в реализации NPTL glibc?

Question

В последнее время, когда я смотрю в то, как поток локального хранения осуществляются в glibc, я нашел следующий код, который реализует API pthread_key_create()

int 
__pthread_key_create (key, destr) 
     pthread_key_t *key; 
     void (*destr) (void *); 
{ 
    /* Find a slot in __pthread_kyes which is unused. */ 
    for (size_t cnt = 0; cnt < PTHREAD_KEYS_MAX; ++cnt) 
    { 
     uintptr_t seq = __pthread_keys[cnt].seq; 

     if (KEY_UNUSED (seq) && KEY_USABLE (seq) 
      /* We found an unused slot. Try to allocate it. */ 
      && ! atomic_compare_and_exchange_bool_acq (&__pthread_keys[cnt].seq, 
                 seq + 1, seq)) 
     { 
      /* Remember the destructor. */ 
      __pthread_keys[cnt].destr = destr; 

      /* Return the key to the caller. */ 
      *key = cnt; 

      /* The call succeeded. */ 
      return 0; 
     } 
    } 

    return EAGAIN; 
} 

__pthread_keys является глобальным массивом, доступом всех потоков. Я не понимаю, почему чтение его члена seq не синхронизирован как в следующем примере:

uintptr_t seq = __pthread_keys[cnt].seq; 

хотя syncrhonized когда изменения позднее.

FYI, __pthread_keys представляет собой массив типа struct pthread_key_struct, которая определяется следующим образом:

/* Thread-local data handling. */ 
struct pthread_key_struct 
{ 
    /* Sequence numbers. Even numbers indicated vacant entries. Note 
     that zero is even. We use uintptr_t to not require padding on 
     32- and 64-bit machines. On 64-bit machines it helps to avoid 
     wrapping, too. */ 
    uintptr_t seq; 

    /* Destructor for the data. */ 
    void (*destr) (void *); 
}; 

Заранее спасибо.

Answer 1

В этом случае петля может избежать дорогостоящей фиксации замка. Атомный compare and swap operation, выполненный позже (atomic_compare_and_exchange_bool_acq), гарантирует, что только один поток может успешно увеличить значение последовательности и вернуть ключ вызывающему абоненту. Другие потоки, читающие одно и то же значение на первом шаге, будут продолжать цикл, поскольку CAS может быть успешным только для одного потока.

Это работает, потому что значение последовательности чередуется между четными (пустыми) и нечетными (занятыми). Приращение значения нечетному не позволяет другим нитям приобретать слот.

Простое чтение значения меньше циклов, чем инструкция CAS, как правило, поэтому имеет смысл заглянуть в значение, прежде чем делать CAS.

Существует много wait-free and lock-free algorithms, которые используют инструкцию CAS для достижения низкой скорости накладных расходов.