Координація паралельних обчислень

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

Задача А отримує запити від задачі В на виконання операції знімання грошей з рахунку. Задача А також отримує запити від задачі С покласти гроші на депозит. Задача А приймає запити і опрацьовує їх за правилом ²першм прий­шов – перший опрацьований². Приймаємо, на рахунку маємо 1000 дол., при цьому задача С вимагає покласти на рахунок 100 дол., а задача В хоче зняти з

рахунку 1100 дол. Що відбудеться, якщо дві задачі В і С спробують оновити

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

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

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

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

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

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

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

POSIX- специфікація підтримує п’ять базових механізмів, які викорис­то­вуються для реалізації взаємодії між процесами:

· файли з засобами блокування та розблокування;

· канали (неіменовані, іменовані і черги FIFO);

· загальна пам'ять і повідомлення;

· сокети;

· семафори.

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

В табл.1 зверніть увагу на те, що існують конфігурації, в яких парале­лізм досягається за рахунок використання декількох комп’ютерів. В такому ви­падку ефективніше скористатися бібліотеками PVM. І також існують конфігу­ра­ції, в яких розподілене програмування може бути реалізоване лише на одно­му комп’ютері за рахунок розподілу логіки ПЗ на декілька процесів або пото­ків. Власне факт використання множини процесів або потоків говорить про те, що робота програми являє ²розподілений² характер. Комбінації паралельного і розподіленого програмування, подані в табл.1, показують, що проблеми конфі­гурації, за звичай характерні розподіленому програмуванню, можуть виникну­ти в ситуаціях, обумовлених паралельним програмування, і, навпаки, проблеми конфігурації, за звичай пов’язані з паралельним програмуванням, можуть ви­ни­­кати в ситуаціях, обумовлених розподіленим програмуванням.

Таблиця 1.	Комбінації паралельного і розподіленого програмування з різними конфігураціями апаратного забезпечення
	Один комп’ютер	Багато комп’ютерів
Паралельне програму­­­­- вання	Мітить багато процесорів. Ви­ко­­ристовує логічне розділен­ня на декілька потоків або про­це­сів. Потоки або процеси можуть виконуватися на різних проце­со­рах. Для координації задач не­обхідно МПВ- технології	Використовує такі бібліотеки, як PVM. Потребує організації взаємодії за допомогою передачі повідомлень, що як правило характерно для розподіленого програмування.
Розподілене програму-вання	Наявність декількох процесорів не є обов’язковим. Логіка ПЗ мо­же бути розділена на декіль­ка процесів або потоків	Реалізується за допомогою со­кетів і таких компонентів, як CORBA ORB (Object Request Broker – брокер об’єктних за­питів). Ми можемо використо­вувати тип взаємодії, який як правило пов'язаний з парале­льним програмуванням

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

Вибір архітектури

Існує багато архітектурних рішень, які підтримують паралелізм. Архіте­ктурне рішення можемо вважати коректним, якщо воно відповідає декомпозиції робіт (work breakdown – WBR) програмного забезпечення (ДР ПЗ). Паралельні та розподілені архітектури можуть бути найрізноманітнішими. В той час як де­які розподілені архітектури чудово працюють в Web- середовищі, вони прак­ти­ч­но приречені на невдачу в середовищі реального часу. Наприклад, розподілені архітектури, які розраховані на тривалі часові затримки, цілком прийнятні для Web- середовища і цілковито неприйнятні для багатьох середовищ реального часу. Достатньо порівняти розподілену обробку даних на Web- орієнтованій системі функціонування електронної пошти з розподіленою обробкою даних в банкоматах, або автоматичних касових машинах (automated teller machine – ATM). Затримка (час очікування), яка присутня в багатьох поштових Web- сис­темах, була б просто нищівною для таких систем реального часу, як банко­мати. Одні розподілені архітектури (власне, деякі асинхронні моделі) справляю­ться з часовими затримками краще, ніж інші. Крім того, необхідно самим серйозним чином підходити до вибору відповідних архітектур паралельної обробки даних. Наприклад, методи векторної обробки даних найкраще придатні для рішення певних математичних задач і проблем імітаційного моделювання, але вони аб­солютно неефективні в застосування до мультиагентних алгоритмів плануван­ня. Поширені архітектури ПЗ, що придатні для паралельного та розподіленого програмування, подано в табл. 2.

Чотири базові моделі, подані в табл. 2, і їх варіанти забезпечують основу для всіх паралельних типів архітектур (тобто обєктно-орієнтованого, агентно-орієнтованого і ²класної дошки²), які будемо розглядати в лекціях. Розробни­кам ПЗ необхідно докладно ознайомитися з кожною з даних моделей і їх засто­суванням до паралельного і розподіленого програмування. В лекційному курсі надано початковий опис цих моделей і бібліографічна інформація по матеріа­лам, які дозволять знайти про них більш ґрунтовну інформацію. В кожній робо­ті або при вирішенні проблеми краще всього шукати природній або властивий їм паралелізм, а вибраний тип архітектури повинен максимально відповідати цьому природному паралелізму. Наприклад, паралелізм в рішенні, можливо, краще описувати за допомогою симетричної моделі, або моделі мережі з рівно­правними вузлами (peer-to-peer model)? в якій всі виконавці є рівноправними, на відміну від несиметричної моделі ²керуючий/виконавчий², в якій існує го­ловний (керуючий) процес, який керує всіма іншими процесами як підлеглими.