Проблема змагання

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

total_amount = total_amount + new_amount;

Виникає запитання: чи можна дати гарантію, що внаслідок роботи із вкладом потік, який відповідає кожному користувачу, буде здатний збільшити значення total_amount на потрібну величину?

Насправді цей найпростіший оператор зводиться до послідовності таких дій:

· отримання поточного значення total_amount із глобальної пам’яті;

· збільшення його на new_amount і збереження результату в глобальній пам’яті.

Результат виконання коду залежить від послідовності виконання потоків у системі. Це спричиняє до такого: в одній ситуації код може працювати, в іншій – ні, і передбачити появу помилки в загальному випадку неможливо. Таку ситуацію називають станом гонок або змаганням (race condition), що є однією з найбільш важко вловлюваних помилок, з якими зіштовхуються програмісти. Вона практично не піддається традиційному налагодженню (оскільки нереально перебрати у налагоджувані всі можливі комбінації послідовностей виконання потоків, особливо якщо їх багато).

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

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

Розглянемо основні підходи до розв’язання проблеми змагань.

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

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

У всіх інших випадках потрібно забезпечувати захист змін від впливу інших потоків. Це і є основним завданням синхронізації.

5.2.2. Критичні секції та блокування.

Поняття критичної секції

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

Звідси випливає, що розв’язанням проблеми змагання є перетворення фрагмента коду, який спричиняє проблему, в атомарну операцію, тобто в таку, котра гарантовано виконуватиметься цілковито без втручання інших потоків. Такий фрагмент коду називають критичною секцією (critical section):

//початок критичної секції

total_amount = total_amount + new_amount;

//кінець критичної секції

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

Розглянемо властивості, які повинна мати критична секція.

· Взаємного виключення (mutual exclusion): у конкретний момент часу код критичної секції може виконувати тільки один потік.

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

· Обмеженості очікування: процес, що намагається ввійти у критичну секцію, рано чи пізно обов’язково в неї ввійде.

Залишається відповісти на далеко не просте запитання: «Як нам змусити систему сприймати кілька операцій як одну атомарну операцію?»

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

Дата добавления: 2014-01-05