Главная » Ядро Linux » Спин-блокировки чтения-записи

0

Иногда в  соответствии с  целью   использовани я  блокировок их  можпо   разделить  два типа — блокировки чтения (reader  lock)  и  блокировки записи  (writer  lock). Рассмотрим некоторый список,  который может  обновляться и  в котором может  выполняться поиск. Когда  список обновляется (в него  осуществляется запись),  никакой  другой  код  не  может  параллельно осуществлять запись  или чтение  этого  списка. Запись означает исключительный доступ.  С другой  стороны, если  в списке выполняется  поиск (чтение информации), важно  только, чтобы  никто другой  не  выполнял записи в  список.  Работа  со  списком заданий в  системе (как  обсуждалось в  главе  3, "Управление процессами")  аналогична  только   что  описанной  ситуации. Не  удивительно, что список заданий в системе защищен с помощью спин-блокировки чтениязаписи  (reader-writer spin  lock).

Если   работа  со  структурой  данных   может   быть  четко   разделена на  этапы   чтения/записи , как  в только  что  рассмотренном случае, то  имеет  смысл  использовать механизмы блокировок с аналогичной семантикой. Для  таких  ситуаций операционная  система Linux  предоставляет спин-блокировки  чтения-записи.    обеспечивают два  варианта блокировки.  Один  или  больше   потоков выполнения,  которые одновременно выполняют операции считывания,  могут  удерживать  такую  блокировку. Блокировка на  запись,  наоборот,  может  удерживаться в любой  момент времени только  одним  потоком, осуществляющим запись, и  никаких параллельных считываний не  разрешается. Блокировки чтения-записи иногда  также называются  соответственно shared/exclusive (общая/ исключающая) или  concurrent / exclusive   (параллельная/исключающая).

Инициализировать  блокировку для  чтения-записи можно с помощью следующего программного кода.

rwlock_t mr_rwlock = RW_LOCK_UNLOCKED; Следующий код осуществляет считывание. read_lock(&mr_rwlock);

/* критический участок (только для считывания) … */

read unlock(&mr_rwlock);

И наконец, показанный ниже код осуществляет запись.

write_lock(&mr_rwlock);

/* критический участок (чтение и запись) … */

write_unlock{&mr_rwlock);

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

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

read_lock(&mr_rwlock);

write_lock(&mr_rwlock);

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

Несколько  потоков чтения   безопасно  могут  удерживать   одну  и  ту же  блокировку чтения-записи.  На  самом  деле  один  поток  также  может  безопасно  рекурсивно захватывать  одну  и  ту же  блокировку для  чтения.  Это  позволяет выполнить полезную и часто  используемую оптимизацию.  Если  в  обработчиках прерываний  осуществляется  только   чтение  и  не  выполняется запись,  то  можно   "смешивать"  использование блокировок с запрещением прерываний и  без  запрещения. Для  защиты данных  при чтении   можно   использовать функцию  read_loc k ()   вместо   read_lock_irqsav e () . При  обращении к данным для  записи все  равно  необходимо запрещать прерывания, например  использовать  функцию  write_lock_irqsav e  () , так  как  в  обработчике прерывания  может  возникнуть взаимоблокировка в  связи  с  ожиданием захвата  блокировки на  чтение  при  захваченной блокировке на  запись. В табл.  9.4  показан полный  список средств  работы  с блокировками чтения-записи.

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

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

Таблица 9.4. Список функций работы со спин-блокировками чтения-записи

Функция                                       Описание

read_lock ()

read_lock_irq()

read_lock_irqsave()

read_unlock()

read_unlock_irq ()

read_unlock_irqrestore ()

write_lock()

write_lock_irq()

write_lock_irqsave ()

write_unlock ()

write_unlock_irq () write_unlock_irqrestore() write_trylock()

rw_lock_init()

rw  is  locked ()

Захватить указанную блокировку на чтение

Запретить прерывания на локальном процессоре и захватить указанную блокировку на чтение

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

Освободить указанную блокировку, захваченную для чтения

Освободить указанную блокировку, захваченную для чтения, и разрешить прерывания на локальном процессоре

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

Захватить заданную блокировку на запись

Запретить прерывания на локальном процессоре и захватить указанную блокировку на запись

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

Освободить указанную блокировку, захваченную для записи

Освободить указанную блокировку, захваченную для записи, и разрешить прерывания на локальном процессоре

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

Выполнить попытку захватить заданную блокировку на запись и в случае неудачи возвратить  ненулевое значение

Инициализировать объект типа rwlock_ t в заданной области памяти

Возвратить ненулевое значение, если указанная блокировка захвачена, иначе возвратить нуль

Семафоры

В операционной системе  Linux семафоры (semaphore) — это блокировки, которые  переводят процессы в состояние ожидания. Когда  задание пытается захватить семафор, который уже удерживается, семафор помещает это задание в очередь  ожидания  (wait queue)  и переводит это задание в состояние ожидания (sleep).  Когда  процессы3, которые удерживают семафор, освобождают блокировку, одно  из заданий очереди  ожидания возвращается к выполнению и может  захватить  семафор.

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

3   Как будет показано дальше, несколько процессо в могут пр и необходимости одновременн о удерживать один семафор.

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

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

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

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

• Так как поток  выполнения во время  конфликта при  захвате  блокировки находится  в состоянии ожидания, то семафоры можно  захватывать  только  в  контексте  процесса. Контекст прерывания планировщиком не управляется.

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

• При  захвате  семафора нельзя  удерживать  спин-блокировку, поскольку процесс  может  переходить  в состояние ожидания, ожидая  на освобождение  семафора,

а при удержании спин-блокировки  в состояние ожидания переходить  нельзя.

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

Средства синхронизации в ядре191

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

Последняя полезная функция семафоров — это  то, что  они  позволяют иметь  любое  количество потоков,  которые одновременно удерживают семафор.  В  то  время как  спин-блокировки   позволяют удерживать блокировку только   одному   заданию  в любой   момент   времени,  количество заданий,  которым разрешено одновременно удерживать семафор,  может  быть  задано  при  декларации семафора. Это  значение называется счетчиком использования (usage count) или просто счетчиком (count). Наиболее часто  встречается ситуация,  когда  разрешенное  количество  потоков,  которые  одновременно могут  удерживать семафор,  равно   одному,  как  и  для  спин-блокировок. В таком  случае  счетчик использования равен  единице и семафоры называются  бинарными семафорами (binary  semaphore)  (потому что он может удерживаться только одним заданием или  совсем  никем  не  удерживаться)  или   взаимоисключающими блокировками (mutex,  мьютекс)   (потому  что  он  гарантирует взаимоисключающий  доступ  —mutual  exclusion).   Кроме того, счетчику  при  инициализации может  быть  присвоено значение, большее   единицы.  В  этом   случае  семафор  называется  счетным  семафором  (counting semaphore,  семафор-счетчик), и  он  допускает количество потоков,  которые одновременно удерживают блокировку,  не  большее   чем  значение  счетчика использования. Семафоры-счетчики  не  используются для  обеспечения  взаимоисключающего  доступа, так как  они  позволяют нескольким потокам выполнения одновременно находиться  в  критическом участке.   Вместо  этого  они  используются для  установки лимитов в определенном коде.   В ядре  они  используются мало.  Если  вы  используете семафор, то, скорее  всего, вы  используете взаимоисключающую блокировку (семафор со  счетчиком, равным единице).

Семафоры  были   формализован ы  Эдсгером  Вайбом   Дейкстрой 4     (Edsger   Wybe Dijkstra)   в  1968  году  как  обобщенный механизм блокировок.  Семафор поддерживает две  атомарные операции  Р ()   и V () , название которых  происходит от голландских слов Proben (тестировать) и  Verhogen (выполнить инкремент). Позже  эти  операции начали  называть down  ()  и  up ()  соответственно.

В операционной системе  Linux  они  имеют  такое  же  название.  Операция down  () используется для  того,  чтобы  захватить   семафор путем  уменьшения его  счетчика на единицу.  Если  значение этого  счетчика больше   или  равно  нулю, то  блокировка захватывается успешно  и  задание может  входить  в  критический участок.   Если  значение  счетчика меньше нуля,  то  задание помещается  в  очередь   ожидания и  процессор  переходит   к  выполнению каких-либо других  операций.  Об  использовании  этой функции говорят  в форме   глагола—  семафор  опускается  (down)  для  того,  чтобы  его захватить. Метод  up ()   используется для  того, чтобы  освободить семафор после  завершения  выполнения  критического  участка.   Эту  операцию  называют  поднятием (upping)  семафора.

4   Доктор  Дейкстр а (1930-2002 г.)  один  из  самых талантливых  ученых за всю  (конечно,  не очен ь долгую)  истори ю  существования  вычислительно й  техник и  как  области  науки.  Его  многочисленны е труды включают  работы  но  проектировани ю операционны х систем  и по  теори и  алгоритмов,  сюда же  входит  концепци я  семафоров .  Он  родился  в  городе  Роттердам ,  Нидерланды ,  и  преподавал  в университете   штата  Техас  в течени е  15  лет.  Тем  не  менее,   он  был  бы  не  очен ь доволен  большим количеством директи в  GOTO в ядре  Linux.

i

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

Создание и инициализация семафоров

Реализация  семафоров зависит  от  аппаратной платформы и  определена в  файле

<asm/semaphore.h> .  Структура   struc t     semaphor e  представляет  объекты   типа  семафор.  Статическое определение семафоров  выполняется  следующим образом.

static DECLARE_SEMAPHORE_GENERIC(name, count);

где name  — имя  переменной семефора, a coun t — счетчик семафора. Более  короткая запись  для  создания взаимоисключающей блокировки  (mutex),  которая используются  наиболее часто, имеет  следующий вид.

static DECLARE_MUTEX(name);

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

sema_init(sem, count);

где  sem— это указатель, a coun t — счетчик использования  семафора. Аналогично для инициализации  динамически  создаваемой взаимоисключающей блокировки можно использовать функцию

init_MUTEX(sem);

Неизвестно,  почему  слово  "mutex"  в  имени функции  init_MUTEX( )  выделено большими буквами  и  почему  слово  "init"  идет  перед  ним, в то  время  как  имя  функции   sema_ini t  ()   таких  особенностей не  имеет.  Тем  не  менее  ясно, что  это  выглядит  не  логично,  и  я  приношу свои  извинения за  это  несоответствие.  Надеюсь,  что после  прочтения главы  7 ни  у кого  уже не  будет  вызывать удивление то, какие  имена придумывают  символам  ядра.

Использование семафоров

Функция  down_interruptibl e  ()  выполняет попытку захватить  данный семафор. Если  эта  попытка неудачна, то  задание переводится в состояние ожидания с  флагом TASK_INTERRUPTIBLE. Из  материала главы  3 следует  вспомнить, что  такое  состояние процесса означает,  что  задание может  быть  возвращено к  выполнению  с  помощью сигнала  и  что  такая  возможность обычно   очень  ценная. Если  сигнал  приходит в тот момент,  когда  задание ожидает   на  освобождение  семафора,  то  задание возвращается  к выполнению, а функция  down_interruptibl e ()   возвращает значение -EINTR. Альтернативой рассмотренной  функции  выступает   функция down  () ,  которая переводит  задание в состояние ожидания с флагом  TASK_UNINTERRUPTIBLE. В большинстве  случаев  это  нежелательно,  так  как  процесс,  который ожидает  на  освобождение семафора, не  будет отвечать  на  сигналы.  Поэтому функция   down_interruptibl e  () используется значительно более  широко, чем  функция down () . Да, имена  этих  функций, конечно, далеки  от идеала.

Функция   down_tryloc k   ()   используется для  неблокирующего  захвата  указанного семафора.  Если  семафор   уже  захвачен,   то  функция  немедленно  возвращает ненулевое  значение.  В  случае  успеха  по  захвату  блокировки  возвращается  нулевое  значение и  захватывается   блокировка.

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

/* объявление и описание семафора с именем mr_sem и первоначальным значением счетчика, равным 1 */

static DECLARE_MUTEX(mr_sem);

if (down_interruptible(&mr_sem))

/* получен сигнал и семафор не захвачен */

/* критический участок … */

/* освободить семафор */

up(&mr_sem);

Полный список   функций работы  с  семафорами приведен   в табл.  9.5.

Таблица 9.5.  Список функций  работы  с семафорами

Функция                                                                          Описание

sema_init(struc t    semaphore   *,   int )

init_MUTEX(struct  semaphore *) init_MUTEX_LOCKED (struct semaphore *) down_interruptible(struc t   semaphore    *)

down(struct semaphore  *)

down_trylock(struct semaphore *)

up(struc t   semaphore    *)

Инициализация динамически созданного семафора и установка  для него указанного значения счетчика  использования

Инициализация динамически созданного семафора и установка  его счетчика  использования в значение  1

Инициализация динамически созданного семафора и установка его счетчика  использования в значение 0 (т.е.  семафор  изначально  заблокирован)

Выполнить  попытку  захватить  семафор  и перейти в прерываемое состояние ожидания,  если семафор  находится  в состоянии конфликта  при захвате  (contended)

Выполнить  попытку захватить  семафор  и перейти в непрерываемое состояние ожидания,  если семафор  находится  в состоянии конфликта  при захвате (contended)

Выполнить  попытку  захватить  семафор  и немедленно  возвратить  ненулевое  значение,  если семафор находится  в состоянии конфликта  при захвате (contended)

Освободить  указанный  семафор  и возвратить  к выполнению  ожидающее  задание,  если такое есть

Источник: Лав,  Роберт. Разработка ядра  Linux, 2-е  издание. : Пер.  с англ.  — М.  : ООО  «И.Д.  Вильяме» 2006. — 448 с. : ил. — Парал. тит. англ.

По теме:

  • Комментарии