C
4 July 2012

Простой многопоточный тип доступа к данным и атомарные переменные

Автор: Alexander Sandler, оригинал статьи (23 декабря 2008)

Введение


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

В своем первом посте («Нужен ли мьютекс для защиты int») я показал, как легко превратить значение переменной в мусор, изменяя его из двух или более потоков. В своей второй статье («спин-блокировки pthread») я говорил о спин-блокировках (spinlocks — прим. пер.), последнем дополнении в библиотеку pthread. Спин-блокировки действительно могут помочь решить проблему. Однако, они больше подходят для защиты небольших структур данных, чем простых типы данных, таких как int и long. С другой стороны, атомарные переменные идеально подходят для этих задач.

Ключевой момент об атомарных переменных – это то, что как только кто-то начинает их считывать или записывать в них, ничто не может прервать процесс и произойти в середине. То есть, ничто не может разбить процесс доступа к атомарной переменной на две части. Поэтому они так и названы.

С практической стороны, атомарные переменные являются лучшим решением для проблемы одновременного доступа к простой переменной из двух или более потоков.

Как работают атомарные переменные


В действительности, очень просто. Архитектуры процессоров Intel x86 и x86_64 (как и подавляющее большинство других современных архитектур процессоров) имеют инструкции, позволящие заблокировать FSB при какой-либо операции доступа к памяти. FSB расшифровывается как Front Side Bus («передняя шина» — прим. пер.). Это шина, которую использует процессор для связи с RAM. То есть, блокировка FSB будет препятствовать любому другому процессору (ядру) и процессу работающему на этом процессоре в получении доступа к оперативной памяти. И это именно то, что нам нужно для реализации атомарных переменных.

Атомарные переменные широко используется в ядре Linux, но по какой-то причине никто не потрудился их реализовать для человеческого пользовательского режима. До GCC 4.1.2.

Ограничение размера атомарных переменных


Из практических соображений, гуру из Intel не реализовали FSB-блокировки при каждом возможном доступе к памяти. Например, для экономии времени, Intel-процессоры допускают реализации memcpy() и memcmp() одной инструкцией процессора. Но блокировка FSB при копировании большого буфера памяти может оказаться слишком дорогостоящей.

На практике, вы можете заблокировать FSB при доступе к целым числам длиной 1, 2, 4 и 8 байт. GCC позволяет делать атомарные операции почти прозрачно с int, long и long long (и их эквивалентам без знака).

Варианты применения


Увеличение переменной, зная, что никто другой не повредит ее значения — это хорошо, но недостаточно. Рассмотрим следующий фрагмент псевдокода.

decrement_atomic_value();
if (atomic_value() == 0)
    fire_a_gun();

Представим, что значение атомарной переменной — 1. Что произойдет, если два потока попытаются выполнить эту часть псевдо-C одновременно?

Вернемся к нашему моделированию. Вполне возможно, что поток 1 будет выполнять линию 1 и остановится, в то время как поток 2 будет выполнять линию 1 и продолжать выполнение линии 2. Позже поток 1 проснется и выполнит линию 2.



Когда это произойдет, ни один из потоков не запустит процедуру fire_a_gun() (линия 3). Очевидно, что это неправильное поведение, и если бы мы защитили эту часть кода с помощью мьютекса или спин-блокировки — этого бы не произошло.

В случае, если вам интересно, какова вероятность того, что случится что-то подобное, будьте уверены — это весьма вероятно. Когда я впервые начал работать с многопоточным программированием, я был поражен, узнав, что несмотря на то, что наша интуиция подсказывает нам, что сценарий, который я описал ранее маловероятен — это случается чрезвычайно часто.

Как я уже говорил, мы могли бы решить эту проблему путем отказа от атомарных переменных и используя вместо них спин-блокировку или мьютекс. К счастью, мы все еще можем использовать атомарные переменные. GCC разработчики думали о наших потребностях и данной конкретной проблеме и предложили решение. Давайте рассмотрим фактические процедуры, оперирующие атомарными переменными.

В реальности...


Есть несколько простых функций, делающие эту работу. Прежде всего, есть двенадцать (да-да, двенадцать — 12) функций, делающих атомарные добавление, замену и логические атомарные or, and, xor и nand. Есть две функции для каждой операции. Одна, которая возвращает значение переменной до ее изменения и другая, который возвращает значение переменной после изменения.

Вот фактические функции:
type __sync_fetch_and_add (type *ptr, type value);
type __sync_fetch_and_sub (type *ptr, type value);
type __sync_fetch_and_or (type *ptr, type value);
type __sync_fetch_and_and (type *ptr, type value);
type __sync_fetch_and_xor (type *ptr, type value);
type __sync_fetch_and_nand (type *ptr, type value);

Это функции, которые возвращают значение переменной перед изменением. Следующие функции, с другой стороны, возвращают значение переменной после ее изменения.
type __sync_add_and_fetch (type *ptr, type value);
type __sync_sub_and_fetch (type *ptr, type value);
type __sync_or_and_fetch (type *ptr, type value);
type __sync_and_and_fetch (type *ptr, type value);
type __sync_xor_and_fetch (type *ptr, type value);
type __sync_nand_and_fetch (type *ptr, type value);

тип в каждом из выражений может быть одним из следующих:
int 
unsigned int 
long 
unsigned long 
long long 
unsigned long long 

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

Пора увидеть это в деле


Возвращаясь к примеру, начатому мной в первом посте, который упоминался ранее.
Напомню, что это небольшая программа открывающая несколько потоков. Количество потоков равно количеству процессоров в компьютере. Затем она привязывает каждый из потоков к одному из процессоров. Наконец, каждый поток запускает цикл и увеличивает глобальное целое число один миллион раз.

Исходник
#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
#include <stdlib.h>
#include <sched.h>
#include <linux/unistd.h>
#include <sys/syscall.h>
#include <errno.h>

#define INC_TO 1000000 // один миллион...

int global_int = 0;

pid_t gettid( void )
{
        return syscall( __NR_gettid );
}

void *thread_routine( void *arg )
{
        int i;
        int proc_num = (int)(long)arg;
        cpu_set_t set;

        CPU_ZERO( &set );
        CPU_SET( proc_num, &set );

        if (sched_setaffinity( gettid(), sizeof( cpu_set_t ), &set ))
        {
                perror( "sched_setaffinity" );
                return NULL;
        }

        for (i = 0; i < INC_TO; i++)
        {
//              global_int++;
                __sync_fetch_and_add( &global_int, 1 );
        }

        return NULL;
}

int main()
{
        int procs = 0;
        int i;
        pthread_t *thrs;

        // Получаем число процессоров
        procs = (int)sysconf( _SC_NPROCESSORS_ONLN );
        if (procs < 0)
        {
                perror( "sysconf" );
                return -1;
        }

        thrs = malloc( sizeof( pthread_t ) * procs );
        if (thrs == NULL)
        {
                perror( "malloc" );
                return -1;
        }

        printf( "Starting %d threads...\n", procs );

        for (i = 0; i < procs; i++)
        {
                if (pthread_create( &thrs[i], NULL, thread_routine,
                        (void *)(long)i ))
                {
                        perror( "pthread_create" );
                        procs = i;
                        break;
                }
        }

        for (i = 0; i < procs; i++)
                pthread_join( thrs[i], NULL );

        free( thrs );

        printf( "После всех вычислений, значение global_int value равно: %d\n",
                global_int );
        printf( "Ожидаемое значение равно: %d\n", INC_TO * procs );

        return 0;
}


Обратите внимание на строки 36 и 37. Вместо того, чтобы просто увеличить переменную, я использую встроенную функцию __ sync_fetch_and_add(). Выполнение этого кода, очевидно, дает ожидаемые результаты — то есть значение global_int — это 4 000 000, как и ожидалось (число процессоров в машине, умноженных на один миллион — в моем случае это четырехъядерная машина). Помните, когда я запустил этот фрагмент кода, оставив строку 36 как есть, результатом было 1 908 090, а не 4 000 000, как мы ожидали.

Предосторожности


При использовании атомарных переменных должны быть приняты некоторые дополнительные меры предосторожности. Одной из серьезных проблем с реализацией атомарной переменной в GCC является то, что она позволяет делать атомарные операции на обычных переменных. То есть нет четкого различия между атомарными переменными и обычными. Ничто не мешает вам увеличить значение атомарной переменной с помощью __ sync_fetch_and_add(), как я только что продемонстрировал, а затем в коде сделать то же самое обычным оператором ++.
Очевидно, что это может стать серьезной проблемой. Вещи, как правило, имеют тенденцию к забыванию и это лишь вопрос времени, пока кто-то из вашего проекта или даже вы сами начнете изменять значение переменной с помощью обычных операторов, вместо атомарных функций, предоставляемых GCC.
Для решения этой проблемы, настоятельно рекомендую обернуть атомные функций и переменные либо с помощью ADT (Abstract Data Type — прим. пер.) в C, либо с помощью класса C++.

Заключение


Эта статья завершает серию статей и постов, где проводится исследование и изучение новейших технологий в мире многопоточного программирования для Linux. Надеюсь, вы найдете эти сообщения и посты полезными. Как обычно, в случае, если у вас есть дополнительные вопросы, пожалуйста, не стесняйтесь, напишите мне на e-mail (указан в оригинале — прим. пер.)

Примечание переводчика

Данная и другие статьи автора не претендуют на полноту охвата материала по теме, но у них хороший вводный стиль изложения.

Отмечу, что на данный момент атомарные переменные:


+16
15.2k 76
Comments 2