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

Недавно, когда я изучал, как локальное хранилище потока реализовано в 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;

хотя он синхронизируется при более поздних изменениях.

К вашему сведению, __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 *);
};

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


person spockwang    schedule 21.04.2013    source источник


Ответы (1)


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

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

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

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

person jspcal    schedule 21.04.2013
comment
Проблема в том, что чтение seq может привести к промежуточному значению, потому что тип uintptr_t seq не гарантирует, что он читается атомарно (т. е. в одном командном цикле). - person spockwang; 21.04.2013
comment
Если seq несовместимо, поток перейдет к следующему элементу, потому что сравнение в атомарной операции CAS завершится ошибкой. Чтение находит слот-кандидат (который в конечном итоге может оказаться непригодным для использования), а CAS обеспечивает гарантию синхронизации. - person jspcal; 21.04.2013
comment
Я обнаружил, что pthread_key_delete() также использует этот трюк. Он полагается на CAS, обеспечивающий гарантию синхронизации, чтобы убедиться, что он не удалит недействительный ключ. Но он может забыть удалить действительный ключ, ошибочно приняв его за недопустимый ключ. - person spockwang; 21.04.2013