Спін-блокування читання-запису

Іноді у відповідності з метою использовани я блокувань їх можпо розділити два типи – блокування читання (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(&ampmr_rwlock)

І нарешті, показаний нижче код здійснює запис

write_lock(&ampmr_rwlock)

/ * Критичний ділянку (читання і запис) .. * /

write_unlock{&ampmr_rwlock)

Зазвичай зчитування і запис інформації здійснюються в різних ділянках коду, як це показано в даному прикладі

Зауважимо, що блокування, захоплену для читання, не можна підвищувати до блокування, захопленої для запису У наступному коді

read_lock(&ampmr_rwlock)

write_lock(&ampmr_rwlock)

виникне самоблокировки, так як при захопленні блокування на запис буде виконуватися періодична перевірка, поки всі потоки, які захопили блокування для читання, її не звільнять це стосується і поточного потоку Якщо в якому-небудь місці буде необхідна запис, то потрібно відразу ж захоплювати блокування для запису Якщо у вашому коді немає чіткого поділу на код, який здійснює зчитування, і код, який здійснює запис, то немає необхідності використовувати блокування чтеніязапісі У такому випадку оптимальним буде використання звичайних спін-блокувань

Кілька потоків читання безпечно можуть утримувати одну і ту ж блокування читання-запису Насправді один потік також може безпечно рекурсивно захоплювати одну і ту ж блокування для читання Це дозволяє виконати корисну і часто використовувану оптимізацію Якщо в обробниках переривань здійснюється тільки читання і не виконується запис, то можна змішувати використання блокувань із забороною переривань і без заборони Для захисту даних при читанні можна використовувати функцію read_loc k () замість read_lock_irqsav e () При зверненні до даних для запису все одно необхідно забороняти переривання, наприклад використовувати функцію write_lock_irqsav e (), так як в обробнику переривання може виникнути взаімоблокіровка у звязку з очікуванням захоплення блокування на читання при захопленої блокуванні на запис У табл 94 показаний повний список засобів роботи з блокуваннями читання-запису

Ще один факт, який необхідно брати до уваги при роботі з блокуваннями читання-запису в операційній системі Linux, – це те, що блокування на читання завжди має більшу перевагу в порівнянні з блокуванням на запис Якщо блокування захоплена на читання і потік запису очікує на її звільнення, то всі потоки, які намагатимуться захопити блокування на читання, будуть досягати успіху Потік записи, який періодично перевіряє на звільнення блокування, не зможе захопити блокування, поки всі потоки читання цю блокування не звільнять Тому велика кількість потоків читання буде приводити до підвисання очікують потоків запису Це важлива обставина завжди потрібно памятати при розробці схеми блокувань

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

Таблиця 94 Список функцій роботи зі спін-блокуваннями читання-запису

Функція Опис

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

Останній метод використовується для інкремента значення лічильника Якщо чергу очікування семафора не порожня, то одне із завдань цієї черги повертається до виконання і захоплює семафор

Створення та ініціалізація семафорів

Реалізація семафорів залежить від апаратної платформи і визначена у файлі

Структура 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(&ampmr_sem))

/ * Отриманий сигнал і семафор НЕ захоплений * /

/ * Критичний ділянку .. * /

/ * Звільнити семафор * /

up(&ampmr_sem)

Повний список функцій роботи з семафора наведено в табл 95

Таблиця 95Список функцій роботи з семафора

Функція Опис

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 с : Ил – Парал тит англ

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*