Первая страница
Наша команда
Контакты
О нас

    Головна сторінка



“Інформаційні управляючі системи та технології” 080402 “Інформаційні технології проектування” Одеса 2010

“Інформаційні управляючі системи та технології” 080402 “Інформаційні технології проектування” Одеса 2010




Сторінка16/24
Дата конвертації10.03.2017
Розмір1.41 Mb.
1   ...   12   13   14   15   16   17   18   19   ...   24

Розділ 5 Взаємодія потоків


Розглянемо основні принципи взіємодії потоків одного процесу. Основну увагу зосередимо на синхронізації доступу до спільно використовуваних даних таких потоків.

5. 1 Основні принципи взаємодії потоків


Потоки, які виконуються в рамках процесу паралельно, можуть бути незалежними або взаємодіяти між собою.

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

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

Результати виконання незалежного потоку завжди можна повторити, чого не можна сказати про потоки, що взаємодіють.

Дані, яки є загальними для кількох потоків, називають спільно використовуваними (shared data). Це – найважливіша концепція багатопотокового програмування. Усякий потоік може в будь-який момент часу змінити такі дані. Механізми забезпечення коректного доступу до спільно використовуваних даних називають механізмами синхронізації потоків.

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

Проте обійтися без реалізації взаємодії потоків неможливо з кількох причин.


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

  • Коректна реалізація токої взаємодії та використання відповідних алгоритмів можуть значно прискорити обчислювальний процес на багатопроцесорних системах. При цьому задачі розділяють на підзадачі, які виконують паралельно на різних процесорах, а потім їхні результати збирають разом для отримання остаточного розв’язання. Таку технологію називають технологією паралельних обчислень.
    Паралельні обчислення - це форма обчислень, в яких кілька дій проводяться одночасно. Ґрунтуються на тому, що великі задачі можна розділити на кілька менших, кожну з яких можна розв'язати незалежно від інших.


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

  • Подібна організація дає змогу розбивати задачі на окремі виконувані модулі, оформлені як окремі потоки, що при цьому вихід одного модуля може бути входом для іншого, а також підвищується гнучкість системи, оскільки окреми модулі можна міняти, не чіпаючи інші.

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

5. 2 Основні проблеми взаємодії потоків

5. 2. 1 Проблема змагання


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

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

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

total_amount=total_amount new_amount;

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

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


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

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

Розглянемо випадок, коли два користувачі А і В спільно користуються одним і тим самим рахунком. На рахунку є 100 грошових одиниць.
Грошова́ одини́ця - це встановлений у законодавчому порядку грошовий знак. Вона служить для вимірювання цін товарів та послуг. Грошова одиниця встановлюється законодавством країни з урахуванням соціально-економічних та історичних закономірностей її розвитку.
Користувач А збирається покласти на рахунок 1000, користувач В у цей самий час – 100. Потік ТА відповідає користувачу А, потік ТВ – користувачу В. Розглянемо таку послідовність подій (варіант 1).

  1. Потік ТА зчитує значення total_amount, рівне 100.

  2. Потік ТВ зчитує значення total_amount, теж рівне 100.

  3. Потік ТА збільшує зчитане на кроці 1 значення total_amount на 1000, отримує 1100 і зберігає його у глоальній пам’яті.

  4. Потік ТВ збільшує зчитане на кроці 2 значення total_amount на 100, отримує 200 і теж зберігає його у глобальній пам’яті, перезаписуючі те, що зберіг потік ТА.

У результаті внесок користувача А повністю втрачено.

Тепер розглянемо іншу послідовність подій (варіант 2).



  1. Потік ТА зчитує total_amount, збільшує його на 1000 і записує значення 1100 у глобальну пам’ять.

  2. Потік ТВ зчитує total_amount, рівний 1100, збільшує його на 100 і записує значення 1200 у глобальну пам”ять.

У результаті обидва внески зареєстровані успішно.

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

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

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

Ознайомимся із правилами, яких треба дотримуватися, аби створений код відповідав цьому принципу.

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

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

Іноді використання глобальних даних не диктується специфікою задачі.

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

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

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


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

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


Розглянемо використання простішої ідеї для вирішення проблеми змагань.

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

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

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

total_amount=total_amount new_amount;

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

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

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



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

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

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

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

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


Блокування


Раціональнішим розв’язанням є використання блокувань (locks). Блокування – це механізм, який не дозволяє більш як одному потокові виконувати код критичної секції. Використання блокування зводиться до двох дій: запрвадження (заблокування, функція acquire_lock()) і зняття блокування (розблокування, функція release_lock()). У разі заблокування перевіряють, чи не було воно вже зроблено іншим потоком, і якщо це так, цей потік переходить у стан очікування, інакше він запрваджує блокування і входить у критичну секцію. Після виходу із критичної секції потік знімає блокування.

acquire_lock(lock);

//критична секція

release_lock(lock);

Так реалізовують властивість взаємного виключення, звідси походить інша назва для блокування – мютекс (mutex, скорочення від mutual exclusion).

Проблеми із реалізацією блокувань


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

int lock=0;

void aquire_lock(int lock)

{

//якщо блокування не має (lock==0), запровалити його (задати lock=1)



//і вийти – ми ввійшли у критичну секцію

//інакше чекати, поки блокування не знімуть

while(lock!=0); //(1)

lock=1; //(2)

}

void release_lock(int lock)



{

//зняти блокування

lock=0;

}

Головна проблема цієї реалізації полягає в тому, що що перевірка значення змінної блокування (1) та її зміна (2) не є частинами однієї атомарної операції. Коли інший потоік перевірить значення змінної між цима двома операціями і виявить, що вона дорівнює 0, два потоки можуть опинитися у критичній секції одночасно.


1   ...   12   13   14   15   16   17   18   19   ...   24



  • 5. 1 Основні принципи взаємодії потоків
  • 5. 2 Основні проблеми взаємодії потоків
  • 5. 2. 2 Критичні секції та блокування
  • Блокування
  • Проблеми із реалізацією блокувань