Критичні ділянки та стан конкуренції за ресурси – ЧАСТИНА 1

Гілки коду, які отримують доступ до спільно використовуваними даними і маніпулюють ними, називаються критичними ділянками(Critical region) Зазвичай небезпечно декільком потокам виконання одночасно звертатися до одного і того ж ресурсу Для запобігання конкурентного доступу під час виконання критичних ділянок програміст, тобто Ви, повинен гарантувати, що код виконується атомарне без перерв, так якби весь критичний ділянка була однією неподільною машинної інструкцією Якщо два потоку виконання одночасно перебувають у критичному ділянці, то це-помилка в програмі Якщо таке раптом трапляється, то така ситуація називається станом, конкуренції за ресурс (Стан гонок, race condition) Назва повязана з тим, що потоки як би змагаються один з одним за доступ до ресурсу Слід звернути увагу на те, наскільки рідко така ситуація може виникати, – тому виявлення станів конкуренції за ресурси при налагодженні програм часто дуже складне завдання, тому що подібну ситуацію дуже важко відтворити Забезпечення гарантії того, що конкуренції не буде і, отже, що станів конкуренції за ресурси виникнути не може, називається синхронізацією

Навіщо потрібен захист

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

Як перший приклад розглянемо ситуацію з реального життя банкомат

(Який ще називають ATM, Automated Teller Machine, або кеш-машиною)

Одне з найбільш часто зустрічаються дій, які доводиться виконувати за допомогою банкомату-це зняття грошей з персонального банківського рахунку фізичної особи Людина підходить до банкомату, вставляє картку, вводить PINкод, проходить аутентифікацію, вибирає пункт меню Зняття готівки, вводить необхідну суму, натискає ОК, забирає гроші і відправляє їх автору цієї книги

Після того як користувач ввів необхідну суму, банкомат повинен перевірити, що така сума дійсно є на рахунку Якщо такі гроші є, то необ-

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

int total = get_total_from_account () / * Загальна кількість грошей на рахунку * /

int withdrawal = get_withdrawal_amount () / * Кількість грошей, які хочуть зняти * /

/ * Перевірити, чи є у користувача гроші на рахунку * /

if (total &lt withdrawal)

error (У Вас немає таких грошей”)

/ * Так, у користувача достатньо грошей: відняти знімається суму із загальної кількості грошей на рахунку * /

total -= withdrawal

update_total_funds(total)

/ * Видати користувачеві гроші * /

spit_out_money(withdrawal)

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

Обидві системи, які знімають гроші з рахунку, виконують код, аналогічний щойно розглянутому: перевіряється, що зняття грошей можливо, після цього обчислюється нова сума грошей на рахунку і, нарешті, гроші знімаються фізично Тепер розглянемо деякі чисельні значення Припустимо, що перша снимаемая сума дорівнює $ 100, а другий – $ 10, наприклад, за те, що користувач зайшов в банк (що не вітається: необхідно використовувати банкомат, так як у банках людей не хочуть бачити) Припустимо також, що у користувача на рахунку є сума, рівна

$ 105 Очевидно, що одна з цих двох транзакцій не може завершитися успішно без отримання мінусів на рахунку

Можна очікувати, що вийде щось на кшталт такого: перша завершиться транзакція по зняттю плати за вхід в банк Десять доларів – це менше ніж

$ 105, тому, якщо від $ 105 відняти $ 10, на рахунку залишиться $ 95, а $ 10 запрацює банк Далі почне пиполняться зняття грошей через банкомат, але воно завершиться невдало, так як $ 95 – це менше ніж $ 100

Проте життя може виявитися значно цікавіше, ніж очікувалося Припустимо, що дві зазначені вище транзакції починаються майже в один і той же момент часу Обидві транзакції переконуються, що на рахунку достатньо грошей: $ 105 – це більше $ 100 і більше $ 10 Після цього процес зняття грошей з банкомату відніме

$ 100 з $ 105 і вийде $ 5 В цей же час процес зняття плати за вхід зробить те ж саме і відніме $ 10 з $ 105, і вийде $ 95 Далі процес зняття грошей оновить стан рахунку користувача: на рахунку виявиться сума $ 5 Наприкінці транзакція зняття плати за вхід також оновить стан рахунку, і на рахунку виявиться $ 95 Отримуємо гроші в подарунок

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

Загальна змінна

Тепер розглянемо приклад, повязаний з компютерами Нехай у нас є дуже простий спільно використовуваний ресурс: одна глобальна целочисленная змінна і дуже простий критичний ділянку – операція инкремента значення цієї змінної:

i++

Це вираз можна перевести в інструкції процесора таким чином Завантажити поточне значення змінної i з памяті в регістр

Додати одиницю до значення, яке знаходиться в регістрі

Записати нове значення змінної i назад в память

Тепер припустимо, що є два потоку, які одночасно виконують цей критичний ділянку, і початкове значення змінної i одно 7 Результат виконання буде приблизно таким (кожна рядок відповідає одному інтервалу часу)

Потік 1 Потік 2

отримати значення i з памяті (7)

збільшити i на 1 <7 -> 8)

записати значення i в память (8)

отримати значення i з памяті (8)

збільшити i на 1 (8 -> 9)

записати значення i в память (9)

Як і очікувалося, значення змінної ±, рівне 7, було збільшено на одиницю два рази і стало одно 9 Проте можливий і інший варіант

Потік 1 Потік 2

отримати значення i з памяті (7)

збільшити i на 1 (7 -> 8)

записати значення i в память (8)

отримати значення i з памяті (7)

збільшити i на 1 (7 -> 8)

записати значення i в память (8)

Якщо обидва потоку виконання прочитають початкове значення змінної i перед тим, як воно було збільшено на 1, то обидва потоку збільшать його на одиницю і запишуть в память одне і те ж значення В результаті змінна i буде містити значення 8, тоді як вона повинна містити значення 9 Це один з найпростіших прикладів критичних ділянок На щастя, рішення цієї проблеми просте – необхідно просто забезпечити можливість виконання всіх розглянутих операцій за один неподільний крок Для більшості процесорів є машинна інструкція, яка дозволяє атомарне вважати дані з памяті, збільшити їх значення на 1

і записати назад в память, виділену для змінної Використання такої інструкції дозволяє вирішити проблему Можливо тільки два варіанти правильного виконання цього коду – наступний

Потік 1 Потік 2\

збільшити i на 1 (7 -> 8)

Або таким чином

збільшити i на 1 (8 -> 9)

Потік 1 Потік 2

збільшити i на 1 (7 -> 8)

збільшити i на 1 (8 -> 9)

Дві атомарні операції ніколи не можуть перекриватися Процесор на фізичному рівні гарантує це Використання такої інструкції вирішує проблему Ядро надає кілька інтерфейсів, які дозволяють реалізувати атомарні операції Ці інтерфейси будуть розглянуті в наступному розділі

Блокування

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

Джерело: Лав, Роберт Розробка ядра 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>

*

*