Новости из Блогов Синхронизация в коде

Введение
Существует множество примитивов синхронизации, как проработанных теоретически, так и доступных для практического использования в ядре Linux, и их число постоянно растёт. Эта множественность связана, главным образом, с борьбой за эффективность (производительность) выполнения кода, когда для отдельных функциональных требований вводятся новые примитивы синхронизации, более эффективные в отношении этих конкретных задач. Тем не менее, основной принцип работы всех примитивов синхронизации остаётся одинаковым с того момента, как его впервые описал Э. Дейкстрой в своей знаменитой работе 1968г. "Взаимодействие последовательных процессов".

Критические секции кода и защищаемые области данных
Для решения задачи синхронизации в ядре Linux существует множество механизмов синхронизации (сами объекты синхронизации называют примитивами синхронизации) и постоянно появляются новые механизмы, некоторые из которых вводятся для поддержки узкоспециализированных требований. Но условно, по функциональному применению, примитивы синхронизации можно разделить на две группы:

1. примитивы для защиты фрагментов исполняемого кода (критических секций) от одновременного (или псевдо-одновременного) исполнения: мьютексы, блокировки чтения-записи;
2. примитивы для защиты областей данных от несанкционированных изменений: атомарные переменные и операции, счётные семафоры.

Механизмы синхронизации
Обычно все, предусмотренные конкретной версией ядра, примитивы синхронизации становятся доступны после включения заголовочного файла <linux/sched.h> (остальные требуемые определения будут подключены из этого файла). Далее будут рассмотрены только некоторые из механизмов, такие как:

1. переменные, локальные для каждого процессора (per-CPU variables), интерфейс которых описан в файле <linux/percpu.h>;
2. атомарные переменные (описаны в архитектурно-зависимых файлах <atomic*.h>);
3. спин-блокировки (файл <linux/spinlock.h>);
4. сериальные (последовательные) блокировки (<linux/seqlock.h>);
5. семафоры (<linux/semaphore.h>);
6. семафоры чтения и записи (<linux/rwsem.h>);
7. мьютексы реального времени (<linux/rtmutex.h>);
8. механизмы ожидания завершения (<linux/completion.h>);

Мы начнём рассмотрение механизмов синхронизаций в обратном порядке, с механизмов ожидания завершения, потому, что это естественным образом продолжает обсуждение потоков ядра, которое было представлено в предыдущей статье.

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

Условные переменные и ожидание завершения
Естественным сценарием является запуск некоторой задачи в отдельном потоке и последующее ожидание завершения ее выполнения. В ядре нет аналога функции ожидания завершения потока, и вместо нее требуется явно использовать механизмы синхронизации (аналогичные определению барьеров pthread_barrier_t в POSIX 1003.b). Использование для ожидания какого-либо события обычного семафора не рекомендуется так как реализация семафора оптимизирована исходя из предположения, что обычно (основную часть времени жизни) он находится в открытом состоянии. Для этой задачи лучше использовать не семафоры, а специальный механизм ожидания выполнения — completion (в терминологии ядра Linux он называется условной переменной, но разительно отличается от условной переменной, как её понимает стандарт POSIX). Этот механизм (объявленный в файле <linux/completion.h>) позволяет одному или нескольким потокам ожидать наступления какого-то события, например, завершения другого потока. Следующий пример демонстрирует запуск потока и ожидание завершения его выполнения. Полный код примера можно найти в архиве thread.tgz в разделе "Материалы для скачивания".

Листинг 1. Запуск потока и ожидание его завершения (файл mod_thr2.c)

Code:

#include <linux/module.h>
#include <linux/sched.h>
#include <linux/delay.h>  

static int thread( void * data ) {
   struct completion *finished = (struct completion*)data;
   /* current - указатель на дескриптор текущей задачи */
   struct task_struct *curr = current;
   printk( KERN_INFO "child process [%d] is running\n", curr->pid );
   msleep( 10000 );                         /* пауза 10 с. */
   printk( KERN_INFO "child process [%d] is completed\n", curr->pid );
   complete( finished );                    /* отмечаем факт выполнения условия. */
   return 0;
}

int test_thread( void ) {
   DECLARE_COMPLETION( finished );
   struct task_struct *curr = current;
   printk( KERN_INFO "main process [%d] is running\n", curr->pid );
   pid_t pid = kernel_thread( thread, &finished, CLONE_FS ); /* запускаем новый поток */
   msleep( 5000 );                                           /* пауза 5 с. */
   wait_for_completion( &finished );         /* ожидаем выполнения условия */
   printk( KERN_INFO "main process [%d] is completed\n", curr->pid );
   return -1;
}

module_init( test_thread );

Результаты запуска этого примера разительно отличаются от результатов модуля mod_thr1 из предыдущей статьи (обратите внимание на временные метки сообщений!):

Code:

$ sudo insmod ./mod_thr2.ko
insmod: error inserting './mod_thr2.ko': -1 Operation not permitted
$ sudo cat /var/log/messages | tail -n4
Apr 17 21:20:23 notebook kernel: main process [12406] is running
Apr 17 21:20:23 notebook kernel: child process [12407] is running
Apr 17 21:20:33 notebook kernel: child process [12407] is completed
Apr 17 21:20:33 notebook kernel: main process [12406] is completed
$ ps -A | grep 12406
$ ps -A | grep 12407
$  

Переменные типа struct completion могут определяться либо статически макросом, как в показанном примере, или инициализироваться динамически:

Code:

DECLARE_COMPLETION( name );                  // статический подход
void init_completion( struct completion * ); // динамический подход

Примечание: Всё разнообразие потоков ядра (kernel_thread()), параллельных процессов (fork()) и потоков пространства пользователя (pthread_create()) в Linux обеспечивается тем, что потоки и процессы в этой системе не разделены принципиально, а создаются единым системным вызовом clone(). Все различия создания определяются набором флагов вида CLONE_* для создаваемой задачи (последний параметр kernel_thread() в листинге 1).

Атомарные переменные и операции
Атомарные переменные — это наименее ресурсоёмкие средства обеспечения атомарного выполнения операций (там, где их минимальных возможностей будет достаточно). Они реализуются в платформенно-зависимой части кода ядра. К важным качествам атомарных переменных и операций можно отнести то, что:

1. компилятор (по ошибке, пытаясь повысить эффективность кода) не будет оптимизировать операции обращения к атомарным переменным;
2. атомарные операции скрывают различия между реализациями для различных аппаратных платформ.

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

1. атомарные операции, устанавливающие новые значения;
2. атомарные операции, которые обновляют существующие значения, при этом возвращая предыдущее значение (обычно это функции вида test_and_*()).

С другой стороны, по представлению данных, с которыми они оперируют, атомарные операции также делятся на две группы, но уже по типу объекта:

1. оперирующие с целочисленными значениями (арифметические);
2. оперирующие с последовательным набором бит.

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

Битовые атомарные операции
Эти операции определены в файле <asm-generic/bitops.h> и в отдельном каталоге описаний <asm-generic/bitops/*.h>. Битовые атомарные операции выполняют действия над обычными операндами типа unsigned long, первым операндом вызова является номер бита (0 — младший, ограничения на старший номер не вводится, для 32-бит процессоров это 31, для 64-бит процессоров 63):

Code:

void set_bit( int n, void *addr ) — установить n-й бит;
    void clear_bit( int n, void *addr ) — очистить n-й бит;
    void change_bit( int n, void *addr ) — инвертировать n-й бит;
    int test_and_set_bit( int n, void *addr ) — установить n-й бит и возвратить предыдущее значение этого бита;
    int test_and_clear_bit( int n, void *addr ) — очистить n-й бит и возвратить предыдущее значение этого бита;
    int test_and_change_bit( int n, void *addr ) — инвертировать n-й бит и возвратить предыдущее значение этого бита;
    int test_bit( int n, void *addr ) — возвратить значение n-го бита;

Пример использования битовых атомарных переменных:

Code:

unsigned long word = 0; 
set_bit( l, &word );    /* атомарно устанавливается бит 1 */
clear_bit( 1, &word );  /* атомарно очищается бит 1 */
change_bit( 1, &word ); /* атомарно инвертируется бит 1, теперь он опять установлен */
// очищается бит 1, возвращается прежнее значение этого бита 1 : 
if( test_and_clear_bit( 1, &word ) ) {
   /* в таком виде условие выполнится */
} 

Арифметические атомарные операции
Эти операции реализуются в машинно-зависимом коде и описаны в следующих файлах:

Code:

$ ls /lib/modules/`uname -r`/build/include/asm-generic/atomic*
/lib/modules/2.6.32.9-70.fc12.i686.PAE/build/include/asm-generic/atomic64.h
/lib/modules/2.6.32.9-70.fc12.i686.PAE/build/include/asm-generic/atomic.h
/lib/modules/2.6.32.9-70.fc12.i686.PAE/build/include/asm-generic/atomic-long.h

Эта группа атомарных операций работает над операндами специального типа atomic_t, atomic64_t, atomic_long_t (в отличие от битовых операций). Ниже перечислены только некоторые из них

Code:

    ATOMIC_INIT( int i ) — объявление и инициализация в значение i переменной типа atomic_t;
    int atomic_read( atomic_t *v ) — считывание значения в целочисленную переменную;
    void atomic_set( atomic_t *v, int i ) — установить переменную v в значение i;
    void atomic_add ( int i, atomic_t *v ) — прибавить значение i к переменной v;
    void atomic_sub( int i, atomic_t *v ) — вычесть значение i из переменной v;
    void atomic_inc( atomic_t *v ) — инкремент v;
    void atomic_dec( atomic_t *v ) — декремент v;

Объявление атомарных переменных и запись атомарных операций не вызывает сложностей и аналогично работе с обычными переменными:

Code:

atomic_t v = ATOMIC_INIT( 111 ); /* определение переменной и инициализация ее значения */
atomic_add( 2, &v ) ;            / * v = v + 2  */
atomic_inc( &v );                / * v++ */

В поздних версиях ядра набор атомарных переменных существенно расширен такими 64-х битными типами, как:

Code:

typedef struct {
   long long counter;
} atomic64_t;
typedef atomic64_t atomic_long_t;

И соответствующими для них операциями:
ATOMIC64_INIT( long long ) ;
long long atomic64_add_return( long long a, atomic64_t *v );
long long atomic64_xchg( atomic64_t *v, long long new );

Code:

...
ATOMIC_LONG_INIT( long )
void atomic_long_set( atomic_long_t *l, long i );
long atomic_long_add_return( long i, atomic_long_t *l );
int atomic_long_sub_and_test( long i, atomic_long_t *l );
...

Локальные переменные процессора
Это переменные, закреплённые за процессором (per-CPU data) и определенные в файле <linux/percpu.h>. Основное их достоинство состоит в том, что если некоторую функциональность можно разумно распределить между такими переменными, то они не потребуют взаимных блокировок доступа от разных процессоров в SMP. API, предоставляемые для работы с локальными данными процессора, на время работы с такими переменными запрещают вытеснение в режиме ядра.

Вторым свойством локальных переменных процессора является то, что они позволяют существенно уменьшить недостоверность данных, хранящихся в кэше. Это происходит потому, что процессоры поддерживают свои кэши в синхронизированном состоянии. Если один процессор начинает работать с данными, которые находятся в кэше другого процессора, то первый процессор должен обновить содержимое своего кэша. Постоянное аннулирование данных, находящихся в кэше процессора, именуемое перегрузкой кэша (cash thrashing), существенно снижает производительность системы (в 3 — 4 раза). Использование данных, связанных с процессорами, позволяет приблизить эффективность работы с кэшем к максимально возможной, потому что в идеале каждый процессор работает только со своими данными.

Предыдущая модель
Эта модель существует с версии ядра 2.4, но остаётся столь же функциональной и широко используется и сейчас. В этой модели локальные данные процессора представляются как массив (любой структурной сложности элементов), индексируемый номером процессора (начиная с 0 и далее...), а работа этой модели базируется на вызовах:

1. int get_cpu() — получить номер текущего процессора и запретить вытеснение в режиме ядра;
2. put_cpu() — разрешить вытеснение в режиме ядра.

Пример работы в этой модели:

Code:

int data_percpu[] = { 0, 0, 0, 0 };
int cpu = get_cpu();
data_percpu[ cpu ]++;
put_cpu();

Так как запрет вытеснения в режиме ядра является принципиально важным условием, то код, работающий с локальными переменными процессора, не должен переходить в блокированное состояние (по собственной инициативе). Почему код, работающий с локальными переменными процессора не должен вытесняться?:

1. если выполняющийся код будет вытеснен и позже восстановится для выполнения на другом процессоре, то значение переменной cpu больше не будет актуальным, потому что эта переменная будет содержать номер другого процессоpa.
2. если некоторый другой код вытеснит текущий, то он может параллельно обратиться к переменной data_percpu[] на том же процессоре, что приведёт к состоянию "гонки за ресурсы".

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

Статические определения (на этапе компиляции):

Code:

DEFINE_PER_CPU( type, name );

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

Code:

DECLARE_PER_CPU( type, name );

Для работы с экземплярами этих переменных используются макросы:

1. get_cpu_var( name ) — вызов возвращает L-value экземпляра указанной переменной на текущем процессоре, при этом запрещается вытеснение кода в режиме ядра;
2. put_cpu_var( name ) — разрешает вытеснение.

Ещё один вызов возвращает L-value экземпляра локальной переменной другого процессора:

• per_cpu( name, int cpu ) — этот вызов не запрещает вытеснение кода в режиме ядра и не обеспечивает никаких блокировок, поэтому для его использования необходимы внешние блокировки в коде.

Пример статически определённой переменной:

Code:

DECLARE_PER_CPU( long long, xxx ); 
get_cpu_var( xxx )++;
put_cpu_var( xxx );

Динамические определения (на этапе выполнения) — это другая группа API, в которой динамически выделяются области фиксированного размера, закреплённые за процессором:

Code:

void *alloc_percpu( type );
void *__alloc_percpu( size_t size, size_t align );
void free_percpu( const void *data );

Функции размещения возвращают указатель на экземпляр области данных, а для работы с таким указателем вводятся вызовы, аналогичные случаю статического распределения:

1. get_cpu_ptr( ptr ) — вызов возвращает указатель (типа void*) на экземпляра указанной переменной на текущем процессоре, при этом запрещается вытеснение кода в режиме ядра.
2. put_cpu_ptr( ptr ) — разрешает вытеснение;
3. per_cpu_ptr( ptr, int cpu ) — возвращает указатель на экземпляра указанной переменной на другом процессоре;

Пример динамически определённой переменной:

Code:

long long *xxx = (long long*)alloc_percpu( long long );
++*get_cpu_ptr( xxx );
put_cpu_var( xxx );

Требование неблокируемости кода, работающего с локальными данными процесса, остаётся актуальным и в этом случае.
Как легко заметить, что новая модель (будь это группа API, работающая с самими переменными, или с указателями на них) не так уж значительно отличается от предыдущей: устранена необходимость явного индексирования массива экземпляров по номеру процессора, так как это делается внутренними скрытыми механизмами, и окончательно возвращается уже индексированный экземпляр, связанный с текущим процессором.

Заключение
В этой части рассмотрены некоторые из механизмов синхронизации выполняющихся кодов в ядре. Особенно актуальными такие механизмы становятся после реализации вытеснения потоков в ядре Linux (после версий 2.5 ядра), и с ростом числа процессоров в SMP системах. Рассмотрение других способов синхронизации будет продолжено в последующих частях.

Пример реализации синхронизации потоков: скачать

Автор: Олег Иванович Цилюрик
Дата: 13.08.2013
http://www.ibm.com/developerworks/ru/library/l-linux_kernel_72/​