14. Три рівні паралелізму в комп’ютерній програмі.

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

• інструкції;

• підпрограми (функції, процедури);

• об’єктів;

• додатків.

Паралелізм на рівні інструкцій

П аралелізм на рівні інструкцій виникає, якщо декілька частин однієї інс­трукції можуть виконуватися одночасно. На рис. 4. показано приклад декомпо­зиції однієї інструкції з метою досягнення паралелізму окремих операцій. Ми бачимо що компонент (А + В) можемо обчислювати одночасно з компонентом (C + D). Даний вид паралелізму як правило підтримується компіляторами і не підпадає під керування програміста на мовах високого рівня.

Паралелізм на рівні підпрограм

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

Паралелізм на рівні об’єктів

ДЗС-структуру програмного рішення можемо розподілити між об’єкта­ми. Кожен об’єкт можна призначити окремому потоку або процесу. Використо­вуючи стандарт CORBA (Common Object Request Broker Architecture – техноло­гія створення розподілених об’єктних додатків), всі об’єкти можна призначити різним комп’ютерам однієї мережі або різним комп’ютерам різних мереж. Об’є­кти, реалізовані в різних потоки або процесах, можуть виконувати свої ме­тоди паралельно.

Паралелізм на рівні додатків

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

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

15. Проблема зв’язку та синхронізації в паралельному програмуванні.

Для координації задач, які виконуються паралельно, необхідно забезпе­чити зв'язок між ними та синхронізацію їх робіт. При некоректному зв’язку або синхронізації як правило виникають чотири проблеми.

Проблема № 1: гонкі даних

Якщо декілька задач одночасно спробують деяку загальну область да­них, але кінцеве значення даних при цьому буде залежати від того, яка задача звернулася до цієї області першою, виникне ситуація, яку називають станом гонок (race codition). У випадку, коли декілька задач спробує обновити один і той же ресурс даних, такий стан гонок називають гонкою даних (data race). Яка задача в нашій програмі підтримки електронного банку першою отримає доступ до залишку на рахунку, визначається результатом роботи плануваль­ни­ка задач операційної системи, станом процесорів, часом очікування та випадко­вими причинами. В такій ситуації створюється стан гонок. Яке значення в цьо­му випадку повинен повідомити банк в якості реального залишку на рахун­ку?

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

Проблема № 2: нескінченне відтермінування

Таке планування, при якому одна або декілька задач повинні очікувати до тих пір, доки не відбудеться деяка подія або не створяться певні умови, може виявитися доволі не простим. По-перше, очікувана подія або умова повинні ви­різнятися регулярністю. По-друге, між задачами необхідно налагодити зв'язок. Якщо одна або декілька задач очікують сеансу зв’язку до свого виконання, то у випадку, якщо очікуваний сеанс зв’язку не відбудеться, відбудеться надто пізно або не повністю, ці задачі можуть так ніколи і не виконатися. І також, якщо очі­кувана подія або умова, яка (за нашою думкою) повинна відбутися (або насту­пити), але в дійсності не відбулася (або не наступила), то зупинені нами задачі будуть вічно знаходитися в стані очікування. Якщо ми призупинимо одну або декілька задач до настання події (або умови), яка ніколи не відбудеться, вини­к­не ситуація, що називається нескінченне відтермінування (indefinite postpone­ment). Повертаючись до нашого прикладу електронного банку, приймаємо, що, якщо ми встановимо правила, які вказують всім задачам зняття грошей з рахун­ку знаходиться в стані очікування до тих пір, доки не будуть виконані всі задачі вкладання грошей на рахунок, то задачі знаття грошей ризикують стати нескін­ченно відкладеними.

Ви виходили з припущення про гарантоване існування задач вкладання грошей на рахунок. Але якщо один із запитів на поповнення рахунків не надій­де, то що тоді заставить виконатись задачі зняття грошей? І, навпаки, що, якщо будуть нескінченно надходити запити на поповнення одного і того ж рахунку? Тоді не зможе пройти до рахунку ні один запит на зняття грошей. Така ситуація також може викликати нескінчену відтермінування задач зняття грошей.

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

Проблема № 3 : взаємне блокування

Взаємне блокування – це ще одна проблема, пов’язана з очікуванням. Для демонстрації взаємного блокування в важитимемо, що в нашій програмі підтримку електронного банку три задачі працюють не з одним, а з двома раху­нками. Згадаємо, що задача А отримує запит від задачі В на знімання грошей з рахунку, А від задачі С – запити на вкладання грошей на депозит. Задачі А, В і С можуть виконуватися паралельно. Однак задачі В і С можуть оновлювати од­ночасно тільки один рахунок. Задача А надає доступ задач В і С до необхідного рахунку за правилом першим прийшов – перший пішов. Вважаємо, що задача В має монопольний доступ до рахунку 1, а задача С – монопольний доступ до рахунку – 2. При цьому задачі В для виконання відповідної обробки також нео­бхідний доступ до рахунку 2 і задачі С – доступ до рахунку 1. Задача В утримує рахунок 1, очікуючи, доки задача С не звільнить рахунок 1. Тим самим задачі В і С ризикують попасти в безвихідну ситуацію, яку в даному випадку можемо назвати взаємним блокуванням (deadlock). Ситуація взаємного блокування між задачами В і С схематично подано на рис. 3.

Форма взаємного блокування в даному випадку пояснюється наявністю задач, що виконуються паралельно, мають загальний доступ до даних, що вико­ристовуються спільно, і які їм дозволено оновлювати. Тут можлива ситуація, коли кожна із задач буде очікувати до тих пір, доки друга не звільнить доступ ло загальних даних (Загальними даними тут є рахунок 1 і рахунок 2). Обидві задачі мають доступ до двох рахунків. Може статися так, що замість отримання доступу однієї задачі до двох рахунків, кожна задача отримає доступ до одного з рахунків. Оскільки задача В не може звільнити рахунок 1, доки не отримає доступу до рахунку 2, а задача С не може звільнити рахунок 2, доки не отримає доступу до рахунку 1, програма обслуговування рахунків електронного банку буде залишатися заблокованою. Зверніть увагу, що задачі В і С можуть ввести в стан нескінченого відтермінування і інші задачі (якщо такі є в системі). Якщо інші задачі очікують доступу до рахунків 1 або 2, а задачі В і С зв’язані взаєм­ним блокуванням. При координації задач, які виконуються паралельно необхід­но пам’ятати, що взаємне блокування і нескінченне відтермінування – це самі н ебезпечні перепони, які необхідно передбачити і уникнути.

Проблема № 4: труднощі організації зв’язку

Багато поширених паралельних середовищ (наприклад, кластери) в біль­шості випадків складаються з гетерогенних комп’ютерних мереж. Гетерогенні комп’ютерні мережі – це системи, які складаються з комп’ютерів різних типів, що працюють в загальному випадку під керуванням різних операційних систем і використовуються різні мережеві протоколи. Їх процесори можуть мати різну архітектуру, опрацьовувати слова різної довжини і використовувати різні ма­ши­нні мови. Окрім різних операційних систем, комп’ютери можуть відрізня­ти­ся стратегіями планування і системами пріоритетів. Гірше всього, всі системи можуть розрізнятися параметрами передачі даних. Це робить обробку помилок та виключних ситуацій (виключень) особливо складною. Неоднорідність сис­теми може ускладнюватись і іншими причинами. Наприклад, може виникнути необхідність в організації спільного використання даних програм, написаних на різних мовах, або розроблених з використанням різних моделей ПЗ. Адже за­га­льне системне рішення може бути реалізовано по частинах, написаних на мовах Ада, С++ і Java. Це вносить проблеми міжмовного зв’язку. І навіть, якщо розпо­ділена або паралельна система не є гетерогенною, залишається проблема взає­модії між декількома процесами або потоками. Оскільки кожен процес має вла­сний адресний простір, то для спільного використання змінних , параметрів та значень, які повертаються функціям, необхідно застосувати технологію між процесорної взаємодії (interprocess communication - IPC), або МПВ- технологію. І хоча реалізація МПВ- методів необов’язково є самою складною частиною роз­робки системи ПЗ, тим не менше вони створюють додатковий рівень проекту­вання, тестування і налагодження в створенні системи.