Содержание


Инструменты программирования в ядре: Часть 74. Параллелизм и синхронизация. Блокировки. Часть 2

Comments

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

Сериальные (последовательные) блокировки

Хотя данные тип блокировок и является одним из механизмов синхронизации, но по сути своей сериальные блокировки таковыми (в полной мере) не являются. Этот подвид блокировок чтения-записи был специально добавлен для создания реализаций, обладающих повышенной эффективностью. Подобные примитивы синхронизации описаны в файле <linux/seqlock.h>, а для их представления вводится тип seqlock_t:

typedef struct {
   unsigned sequence;
   spinlock_t lock;
} seqlock_t;

Данная блокировка может создаваться и инициализироваться статически:

seqlock_t lock = SEQLOCK_UNLOCKED;

Или динамически:

seqlock_t lock;
seqlock_init( &lock );

Чтобы получить доступ на чтение, на входе в защищаемую критическую секцию следует запросить целочисленную безнаковую последовательность (ключ). На выходе из секции это значение сравнивается с его текущей величиной на момент завершения; и если возникает несоответствие, то это значит, что секция за это время подверглась операциям записи, и проделанное считывание следует повторить. В результате, на стороне читателя используется подобный код:

seqlock_t lock = SEQLOCK_UNLOCKED;
unsigned int seq;
do {
   seq = read_seqbegin( &lock );
   /* ... */
} while read_seqretry( &lock, seq );

Блокировка по записи реализуется через спин-блокировку. Чтобы войти в критическую секцию, защищаемую последовательной блокировкой, необходимо получить эксклюзивную спин-блокировку с помощью вызова следующей функции:

static inline void write_seqlock( seqlock_t *sl ) {
   spin_lock(&sl->lock);
   ++sl->sequence;
   smp_wmb();
}

Снятие блокировки записи выполняет другая функция:

static inline void write_sequnlock( seqlock_t *sl ) {
   smp_wmb();
   sl->sequence++;
   spin_unlock(&sl->lock);
}

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

static __always_inline unsigned read_seqbegin( const seqlock_t *sl ) {
   unsigned ret;
repeat:
   ret = sl->sequence;
   smp_rmb();
   if( unlikely( ret & 1 ) ) {
      cpu_relax();
      goto repeat;
   }
   return ret;
}

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

Существует также вариант write_tryseqlock(), который возвращает ненулевое значение, если получить блокировку не удалось.

Если механизмы последовательной блокировки применяются в обработчике прерываний, то следует использовать специальные (безопасные) версии API всех показанных выше вызовов (макросы):

unsigned int read_seqbegin_irqsave( seqlock_t* lock, unsigned long flags );
int read_seqretry_irqrestore( seqlock_t *lock, unsigned int seq, unsigned long flags );
void write_seqlock_irqsave( seqlock_t *lock, unsigned long flags );
void write_seqlock_irq( seqlock_t *lock );
void write_sequnlock_irqrestore( seqlock_t *lock, unsigned long flags );
void write_sequnlock_irq( seqlock_t *lock );

где flags— просто заранее зарезервированная область сохранения IRQ флагов.

Мьютексы реального времени

Кроме обычных мьютексов (как бинарного подвида семафоров), в ядре был создан новый интерфейс для мьютексов реального времени (rt_mutex). Это механизм появился не так давно и его рассмотрение мы будем проводить на ядре версии 2.6.37.3.

Структура мьютекса реального времени находится в файле <linux/rtmutex.h>, и если исключить из рассмотрения её отладочную часть, то можно выделить следующие ключевые атрибуты:

struct rt_mutex {                 // структура для определения мьютекса реального времени
   raw_spinlock_t      wait_lock; // спин-блокировка для защиты структуры
   struct plist_head   wait_list; // список для размещения процессов,
                                  // ожидающих данных мьютекс, в порядке приоритета
   struct task_struct *owner;     // владелец мьютекса
...
};

Характерно присутствие поля owner, обязательного для любых мьютексов POSIX (в отличии от семафоров), что уже обсуждалось ранее. В этом же файле находится весь API для работы с этим примитивом:

#define DEFINE_RT_MUTEX( mutexname )
void __rt_mutex_init( struct rt_mutex *lock,
                      const char *name ); // name используется в отладочной части
void rt_mutex_destroy( struct rt_mutex *lock );
void rt_mutex_lock( struct rt_mutex *lock );
int rt_mutex_trylock( struct rt_mutex *lock );
void rt_mutex_unlock( struct rt_mutex *lock );

Признак захвата мьютекса определяется следующим образом:

inline int rt_mutex_is_locked( struct rt_mutex *lock ) {
   return lock->owner != NULL;
}

Инверсия и наследование приоритетов

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

# cat /boot/config-2.6.32.9-70.fc12.i686.PAE | grep RT_MUTEX
CONFIG_RT_MUTEXES=y
# CONFIG_DEBUG_RT_MUTEXES is not set
# CONFIG_RT_MUTEX_TESTER is not set

В отличие от обычных, мьютексы реального времени обеспечивают наследование приоритетов (priority inheritance, PI) — один из нескольких (немногих) известных способов, препятствующих возникновению инверсии приоритетов (priority inversion). Если мьютекс реального времени был захвачен процессом A, и его пытается захватить процесс B c более высоким приоритетом, то:

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

Это позволяет избежать потенциальной инверсии приоритетов.

Эти действия затрагивают самый нижний уровень управления процессами, и для этого в <linux/sched.h> определяется специальный вызов:

void rt_mutex_setprio( struct task_struct *p, int prio );

И парный ему макрос:

static inline int rt_mutex_getprio( struct task_struct *p ) {
   return p->normal_prio;
}

Из этой inline реализации хорошо видно, что в основной структуре описания процесса:

struct task_struct {
...
   int prio, static_prio, normal_prio;
...
}

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

Множественное блокирование

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

DEFINE_SPINLOCK( lock1, lock2 );
...
spin_lock ( &lock1 ); /* 1-й фрагмент кода */
spin_lock ( &lock2 );
...
spin_lock ( &lock2 ); /* где-то в совсем другом месте кода... */
spin_lock ( &lock1 );

В подобном примере, в конечном итоге, когда-то обязательно возникнет бесконечное блокирование (dead lock). Поэтому если необходимо выполнить захват нескольких блокировок, то правильным будет:

  • использовать один и тот порядок захвата и освобождения блокировок в обоих фрагментах;
  • порядок освобождения должен быть обратным порядку захвата в обоих фрагментах.

Поэтому предыдущий пример следует переписать так:

spin_lock ( &lock1 ); /* так должно быть везде, где использованы lock1 и lock2 */
spin_lock ( &lock2 );
/* ... здесь выполняется действие */
spin_unlock ( &lock2 );
spin_unlock ( &lock1 );

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

Уровень блокирования

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

static DECLARE_MUTEX( sema );
down( &sema ); 
for( int i = 0; i < n; i++ ) {
   // здесь делается нечто монопольное за время T
}
up( &sema );

Этот же фрагмент представить и по-другому, но функционально эквивалентно:

static DECLARE_MUTEX( sema );
for( int i = 0; i < n; i++ ) {
   down( &sema ); 
   // здесь делается нечто монопольное за время T
   up( &sema );
}

Во втором случае потенциальное блокирование любых других потоков, попробовавших захватить семафор, будет представляться как n раздельных интервалов длительностью T, а в первом, как один сплошной интервал протяжённостью n*T.

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

Рассмотрим пример модуля mlock (который можно найти в архиве mlock.tgz в разделе "Материалы для скачивания"), который позволяет очень тонко прочувствовать, как происходит синхронизация потоков, и как эта синхронизация может выполняться на самых различных уровнях:

Листинг 1. Различные варианты использования примитивов синхронизации (файл mlock.c)
#include <linux/delay.h>
#include <linux/kthread.h>
#include <linux/jiffies.h>
#include <linux/semaphore.h>
 
#include "../prefix.c"
 
static int num = 2; // num - число рабочих потоков
module_param( num, int, 0 );
static int rep = 100; // rep - число повторений (объём работы)
module_param( rep, int, 0 );
static int sync = -1; // sync - уровень на котором синхронизация
module_param( sync, int, 0 );
static int max_level = 2; // max_level - уровень глубины вложенности
module_param( max_level, int, 0 );
 
static DECLARE_MUTEX( sema );
static long locked = 0;
static long loop_func( int lvl ) {
   long n = 0;
   if( lvl == sync ) { down( &sema ); locked++; }
   if( 0 == lvl ) {
      const int tick = 1;
      msleep( tick ); // выполняемая работа потока
      n = 1;
   }
   else {
      int i;
      for( i = 0; i < rep; i++ ) {
         n += loop_func( lvl - 1 );
      }
   }
   if( lvl == sync ) up( &sema );
   return n;
}

struct param { // параметр потока
   int    num;
   struct completion finished;
};

#define IDENT "mlock_thread_%d"
static int thread_func( void* data ) {
   long n = 0;
   struct param *parent = (struct param*)data;
   int num = parent->num - 1; // порядковый номер потока (локальный!)
   struct task_struct *t1 = NULL;
   struct param parm;
   printk( "! %s is running\n", st( num ) );
   if( num > 0 ) {
      init_completion( &parm.finished );
      parm.num = num;
      t1 = kthread_run( thread_func, (void*)&parm, IDENT, num );
   }
   n = loop_func( max_level ); // рекурсивный вызов вложенных циклов
   if( t1 != NULL )
      wait_for_completion( &parm.finished );
   complete( &parent->finished );
   printk( "! %s do %ld units\n", st( num ), n );
   return 0;
} 

static int test_mlock( void ) {
   struct task_struct *t1;
   struct param parm;
   unsigned j1 = jiffies, j2;
   if( sync > max_level ) sync = -1; // без синхронизации
   printk( "! repeat %d times in %d levels; synch. in level %d\n",
           rep, max_level, sync );
   init_completion( &parm.finished );
   parm.num = num;
   t1 = kthread_run( thread_func, (void*)&parm, IDENT, num );
   wait_for_completion( &parm.finished );
   printk( "! %s is finished\n", st( num ) );
   j2 = jiffies - j1;
   printk( "!! working time was %d.%1d seconds, locked %ld times\n",
           j2 / HZ, ( j2 * 10 ) / HZ % 10, locked );
   return -1;
}

module_init( test_mlock );
MODULE_LICENSE( "GPL" );

Так как представленная логика довольно сложна, то дополним код некоторыми комментариями:

  • включаемый файл определяет функцию st() для форматирования диагностики о потоке (с меткой времени jiffies), которую мы уже видели ранее;
  • потоки (числом num— параметр запуска модуля) запускают друг друга последовательно и завершаются в обратном порядке: каждый поток ожидает завершения им порождённого;
  • "работа" потока состоит в неоднократном циклическом (параметр rep) выполнении рекурсивной функции loop_func();
  • хотя применение рекурсии в модулях ядра довольно рискованно из-за ограниченности и фиксированного размера стека ядра, но в данном случае это допускается, так как
    1. это демонстрационная задача, заодно показывающая возможность рекурсии в коде ядра;
    2. функция сознательно имеет минимальное число локальных (стековых) переменных;
    3. и самая важная причина состоит в том, что рекурсия позволяет создать структуру вложенных циклов переменной и произвольно большой глубины вложенности, так (параметр max_level модуля), вызов loop_func( N ) эквивалентен:
      for( j1; ... )
              for( j2; ... )
                 for( j3; ... )
                 ...
                    for( jN; ... )
  • варьируя параметр модуля sync, можно определять, на какой глубине вложенных циклов потоки станут пытаться синхронизироваться захватом семафора sema:
    • sync=0— на самом глубоком уровне имитации "работы" потока;
    • sync=1— уровнем выше;
    • sync=max_level— на максимально возможном верхнем уровне охватывающего цикла;
    • sync<0 или sync>max_level— вообще не синхронизироваться и не пытаться получить доступ к семафору sema;
  • модуль выполнен как пользовательская задача, ничего не устанавливающая в ядре, но выполняющаяся в режиме защиты супервизора.

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

$ sudo insmod mlock.ko rep=10 num=2 max_level=2 sync=-1
insmod: error inserting 'mlock.ko': -1 Operation not permitted
$ dmesg | tail -n 30 | grep !
! repeat 10 times in 2 levels; synch. in level -1
! 02094515 : kthread [05336:1] is running
! 02094515 : kthread [05337:0] is running
! 02094716 : kthread [05337:0] do 100 units
! 02094716 : kthread [05336:1] do 100 units
! 02094716 : kthread [05335:2] is finished
!! working time was 0.2 seconds, locked 0 times
$ sudo insmod mlock.ko rep=10 num=2 max_level=4 sync=-1
insmod: error inserting 'mlock.ko': -1 Operation not permitted
$ dmesg | tail -n 30 | grep !
! repeat 10 times in 4 levels; synch. in level -1
! 01915560 : kthread [05275:1] is running
! 01915560 : kthread [05276:0] is running
! 01935606 : kthread [05276:0] do 10000 units
! 01935608 : kthread [05275:1] do 10000 units
! 01935608 : kthread [05274:2] is finished 
!! working time was 20.0 seconds, locked 0 times

А вот различия времени выполнения (в num=5 раз!) в зависимости от синхронизации потоков или её отсутствия:

$ sudo insmod mlock.ko rep=10 num=5 max_level=3 sync=-1 
insmod: error inserting 'mlock.ko': -1 Operation not permitted 
$ dmesg | tail -n 30 | grep '!!' 
!! working time was 2.0 seconds, locked 0 times 
$ sudo insmod mlock.ko rep=10 num=5 max_level=3 sync=0 
insmod: error inserting 'mlock.ko': -1 Operation not permitted 
$ dmesg | tail -n 30 | grep '!!' 
!! working time was 10.0 seconds, locked 5000 times 
$ sudo insmod mlock.ko rep=10 num=5 max_level=3 sync=1 
insmod: error inserting 'mlock.ko': -1 Operation not permitted 
$ dmesg | tail -n 30 | grep '!!' 
!! working time was 10.0 seconds, locked 500 times 
$ sudo insmod mlock.ko rep=10 num=5 max_level=3 sync=2 
insmod: error inserting 'mlock.ko': -1 Operation not permitted 
$ dmesg | tail -n 30 | grep '!!' 
!! working time was 10.0 seconds, locked 50 times 
$ sudo insmod mlock.ko rep=10 num=5 max_level=3 sync=3 
insmod: error inserting 'mlock.ko': -1 Operation not permitted 
$ dmesg | tail -n 30 | grep '!!' 
!! working time was 10.0 seconds, locked 5 times

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

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

Предписания порядка выполнения

Механизмы, предписывающие порядок выполнения кода, не относятся напрямую к синхронизирующим механизмам, но рассматриваются всегда вместе с ними, так как их роднит единственное сходство: и те и другие могут влиять на порядок выполнения операторов, и изменять его в "плавном" последовательном выполнении операторов кода.

Аннотация ветвлений

Одним из таких механизмов являются определённые в файле <linux/compiler.h> макросы likely() и unlikely(), иногда называемые аннотацией ветвлений:

if( unlikely() ) {
   /* сделать нечто редкостное */
};

Или

if( likely() ) {
   /* обычное прохождение вычислений */
}
else {
   /* что-то нетрадиционное */
};

Если вы помните в минимальном объёме специфику выполнения процессорной инструкции jmp, то наверняка знаете, что при её выполнении происходит разгрузка (и перезагрузка) конвейера уже частично декодированных последующих команд. Кроме того, необходимо учесть и кеш памяти, который может потребовать перезагрузки в дальнюю jmp область (а это разница в скорости обычно в 2-4 раза). Поэтому если это так, и во всяком ветвлении (условном переходе) одна из ветвей обязательно должна выполнять jmp, то можно дать указание компилятору компилировать код так, чтобы веткой с jmp оказалась ветка с наименьшей вероятностью выполнения. Таким образом, аннотации ветвления нужны только для повышения производительности выполнения кода (иногда заметно ощутимой). Кроме того, такие предписания делают код более читабельным, но допускаются только в ядре, так не определены в пространстве пользовательского кода.

Применение подобных оптимизаций стало актуальными с появлением в процессорах конвейерных вычислений с предсказыванием. На других платформах, отличных от Intel x86, предоставляемые ими преимущества могут быть на сегодня и не столь ощутимыми (это нужно уточнить в процессе детального изучения архитектуры перед началом разработки).

Барьеры

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

a = 1;
b = 2;

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

a = 1;
b = a + 1;

Она гарантирует отсутствие перестановок в процессе оптимизации, так как компилятор "видит" операции в едином контексте (фрагменте кода). Но в других случаях, когда операции выполняются из разных фрагментов кода нужно гарантировать, что они не будут перенесены через определённые барьеры. Операции (макросы) с барьерами объявлены в файле </asm-generic/system.h>, и на сегодня все они (rmb(), wmb(), mb() и др.) определены одинаково:

#define   mb()  asm volatile ("": : :"memory")

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

Ещё один макрос, объявленный в <linux/compiler.h>, препятствует компилятору при оптимизации переставлять операторы до вызова и после вызова:

void barrier( void );

Заключение

На этом завершается беглый обзор средств синхронизаций выполнения параллельных ветвей в ядре (модулях ядра). Причём, рассмотрены средства синхронизации «в широком смысле»: не только синхронизация как техника препятствующая неконтролируемому совместному выполнению, но и приёмы управления последовательностью выполнения участков кода. Обзор этот назван беглым, поскольку синхронизация — очень обширный предмет с многими нюансами, а, кроме того, с развитием кода ядра в нём добавляются всё новые и новые механизмы, «заточенные» на разрешение каких-то частных задач.


Ресурсы для скачивания


Похожие темы


Комментарии

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

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Linux, Open source
ArticleID=940889
ArticleTitle=Инструменты программирования в ядре: Часть 74. Параллелизм и синхронизация. Блокировки. Часть 2
publish-date=08142013