Почему доступ к порядковому номеру ключей 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;

хотя он синхронизируется при изменении позже.

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

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

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

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

Существует много алгоритмов без ожидания и без блокировки, которые используют инструкцию CAS для достижения синхронизации с минимальными издержками.