Процеси або нитки можуть взаємодіяти:

1. Через розподілення пам'яті (ОП, зовн.)

2. Завдяки передачі повідомлень

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

Розрізняють 2 види синхронізації:

1. Взаємне виключення критичних інтервалів

2. Координація процесів

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

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

Дві типові проблеми, з якими програміст може зіткнутися при роботі з потоками :

1. Гонки (Race conditions)

2. Тупіки(Deadlocks).

Правила використання потоків

Потоки необхідно використовувати:

1. Для досягнення підвищеного паралелізму.

Дуже часто додаткам вимагається виконувати декілька задач одночасно.

2. З метою спрощення конструкції.

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

3. Для ефективного використання процесорного часу.

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

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

Застосовується до даних, які оперують великими масивами чисел. Проводиться в два етапи:

1) розділення даних

2) використання для розподілу основного завдання на окремі задачі цього розділення

Секціонування здійснюється різними способами, буває різних типів:

1. секціонування за вихідними даними

2. секціонування за вхідними даними

3. секціонування за вхідними і вихідними даними

4. секціонування за проміжними даними

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

Секціонування за вхідними даними застосовується у випадку, коли кожен вихідний елемент обчислюється як функція входу, але секціонування за вихідними даними неможливе

Приклад: визначення мінімуму або максимуму з набору чисел

2. Декомпозиція послідовних програм за вихідними даними

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

Застосовується до даних, які оперують великими масивами чисел. Проводиться в два етапи:

1) розділення даних

2) використання для розподілу основного завдання на окремі задачі цього розділення

Секціонування здійснюється різними способами, буває різних типів:

1. секціонування за вихідними даними

2. секціонування за вхідними даними

3. секціонування за вхідними і вихідними даними

4. секціонування за проміжними даними

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

Секціонування за вихідними даними - такий тип секціонування можливий, коли вихідні дані не залежать один від одного і кожен вихідний елемент є лише функцією входу

Приклад: матричне множення. Обчислення кожного вихідного елементу виділяється в окрему задачу.

3. Дослідницька декомпозиція послідовних програм

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

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

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

Приклад: пятнашка

Дана задача розв'язується типово, використовуючи методи пошуку дерева. Вихідна конфігурація може мати 2, 3 або 4 на ступні конфігурації. Набір просторових конфігурацій можна розглядати як граф, кожен вузол - це конфігурація, а кожне ребро сполучає дві послідовні конфігурації, які утворюються одна з одної лише рухом однієї складової.

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

Застосовується до даних, які оперують великими масивами чисел. Проводиться в два етапи:

3) розділення даних

4) використання для розподілу основного завдання на окремі задачі цього розділення

Секціонування здійснюється різними способами, буває різних типів:

1. секціонування за вихідними даними

2. секціонування за вхідними даними

3. секціонування за вхідними і вихідними даними

4. секціонування за проміжними даними

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

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

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

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

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

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

Дві типові проблеми, з якими програміст може зіткнутися при роботі з потоками :

3. Гонки (Race conditions)

4. Тупіки(Deadlocks).

Тупіки. Тупік має місце тоді, коли потік чекає ресурс, який в даний момент належить іншому потоку. Розглянемо приклад: Потік 1 захоплює об'єкт А і, для того, щоб продовжувати роботу, чекає можливості захопити об'єкт Б. В той же час Потік 2 захоплює Об'єкт Б і чекає можливості захопити Об'єкт А. Розвиток цього сценарію заблокує обидва потоки; жоден з них не виконуватиметься.

В ролі ресурсів виступають довільні спільно використовувані об'єкти, а саме файли, масиви в пам'яті.

Гонки. Ситуація гонок виникає, коли два або більш потоків намагаються дістати доступ до загального ресурсу і змінити його стан. Розглянемо наступний приклад. Хай Потік 1 дістав доступ до ресурсу і змінив його в своїх інтересах; потім активізувався Потік 2 і модифікував цей же ресурс до завершення Потоку 1. Потік 1 вважає, що ресурс залишився в тому ж стані, що і був до перемикання. Залежно від того, коли саме був змінений ресурс, результати можуть варіюватися -- іноді код виконуватиметься нормально, іноді - ні.

Ситуації гонок і тупіків можна уникнути, якщо використовувати такі прийоми:

1. Взаємне виключення. Дозволяє тільки одному потоку за один раз володіти об'єктом.

Характеризується:

- тільки 1 процес знаходиться в середині критичного інтервалу

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

- не повинно існувати жодних домовленостей про швидкість процесу

2. Семафори. Семафор (semaphore) подібний взаємному виключенню. Різниця між ними у тому, що семафор може управляти кількістю потоків, які мають до нього доступ.

Семафор встановлюється на граничне число потоків, яким доступ дозволений. Коли це число досягнуте, подальші потоки будуть припинені, поки один або більш потоків не від'єднаються від семафора і не звільнять доступ. Семафор - невід'ємна ціла змінна, яка може змінюватись і перевірятись лише двома функціями:

P(s): [<if<умова>|знач.|><звільнити><s:=s-1>]

V(s): [<if<умова>|знач.|><зайняти><s:=s+1>]

Блокування процесу і перемикання на інший не ефективно, коли семафор захоплюється на дуже короткий час. Очікування звільнення таких семафорів може бути реалізовано в ОС завдяки циклічним опитуванням значень семафору. Недоліки такого «активного очікування» - не продуктивна витрата часу, навантаження на загальну пам'ять і можливість практично заблокувати роботу процесу, що знаходиться в критичному інтервалі. Тобто, якщо об'єкт використовується великою кількістю потоків, використання семафорів не доцільне.

3. Подія - змінна, яка показує що відбулася певна подія.

Для об'явлення події використовується оператор: Post(ім'я змінної) , для очікування : Wait(ім'я змінної). Для очищення (привласнення 0 значення): clear(ім'я змінної).

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

· взаємні виключення можуть бути спільно використані потоками в різних процесах, а критичні секції -- ні;

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

5. Обмін повідомленнями. «Взаємодія паралельних процесів».1978р., Хоар.

Мета: позбутись проблему розподілу пам'яті і запропонувати модель взаємодії процесів у розподілених системах.

Використовуються основні функції:

1. Send (destination, message, size)

2. Receive (source, message, size)

Адресатом виступає процес, відправник не специфікується , в його ролі виступає довільний об'єкт.

Механізм семафорів та взаємодії процесів семантично взаємо заміняються . Тому на мультипроцесорах використовується один через інший.

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

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

Цей спосіб призводить до виявлення природного паралелізму системи.

Приклад. Швидке сортування набору чисел : 5 12 11 1 10 6 8 2 7 4 9 3

Вибирається основний елемент Х і основна послідовність А розбивається на дві послідовності А0 і А1, такі що всі елементи послідовності А0 є меншими за Х, а всі елементи А1 є більшими за Х і т.д.

Страницы: 1, 2