|
| Суббота, 21.06.2025, 17:25 |
| Приветствую Вас Гость | RSS |
|
|
паралельні та розподілені обчислення
| |
| Ellcrys | Дата: Вторник, 21.06.2011, 14:06 | Сообщение # 1 |
|
Любопытный соф
Группа: Администраторы
Сообщений: 56
Статус: Offline
| 5. Паралельні і розподілені обчислення
5. Паралельні і розподілені обчислення 1
1. Розширені мережі Петрі. Типи розширень. Модифіковані правила активізації і ввімкнення переходів. 2
2. Конвеєрна обробка. Пікова та реальна продуктивність. Графік залежності продуктивності конвеєрного пристрою від довжини вхідного набору даних. 3
3. Ступінь деталізації декомпозиції, ступінь паралелізму паралельного алгоритму. Граф залежності задач. 4
4. Взаємодія задач при паралельній обробці. Граф взаємодії задач. 5
5. Вартість операції, завантаженість пристрою, прискорення системи. 1-й закон Амдала. 6
6. Другий та третій закони Амдала. 7
7. Потоки і багатозадачність. Потік, процес, програма, багатопотоковість. Типи потоків, види багатозадачності. Правила використання потоків. 8
8. Організація обчислень в машинах потоків даних. 9
9. Декомпозиція задач за вхідними даними. 10
10. Декомпозиція задач за вихідними даними. 11
11. Дослідницька декомпозиція задач. 12
12. Декомпозиція задач за проміжними даними. 13
13. Граф машин потоків даних (МПД) і його основні елементи. 14
14. Способи взаємодії ниток при багато потоковому програмуванні: семафори, події, взаємне виключення. 15
15. Рекурсивна декомпозиція. Приклад швидкого сортування масиву чисел. 16
1. Розширені мережі Петрі. Типи розширень. Модифіковані правила активізації і ввімкнення переходів.
Мережа Петрі – це дводольний орієнтований граф з мітками. Кожна мережа Петрі є графом, в якому є два типи вершин:
1.Вузли (стан)
2.Переходи – (дія)
Між вузлами та переходами можуть міститися ребра, але два вузли або два переходи не можуть бути зв’язані ребрами. Вузли можуть бути вільними або зайнятими (маркованими).
Три типи розширень мереж Петрі:
Багаторазове маркування (невід’ємне)
Активізація. Перехід активізований тоді, коли кількість маркувань всіх його вхідних вузлів 1.
Ввімкнення. Активізований перехід вмикається, при цьому число маркувань його вхідних вузлів зменшуються на 1, а вихідних збільшується на 1.
Дуги-заперечення
Не мають дугової ваги, завжди направлені тільки від деякого вузла до деякого переходу. Всі дуги, що не є дугами заперечення, називаються позитивними.
Активізація. Перехід є активізованим, якщо кількість маркувань вузлів вхідних позитивних дуг , а дуг-заперечень =0.
Ввімкнення. Якщо активізований перехід вмикається, то кількість маркувань вхідних вузлів позитивних дуг зменшується на 1, а дуг заперечення залишається незмінною.
Вага дуг
Кожна дуга, що не є дугою заперечення може мати постійну вагу .
Активізація. Перехід є активізованим, якщо кількість маркувань всіх його вхідних вузлів вагам відповідних дуг.
Ввімкнення. Якщо активізований перехід вмикається, то кількість маркувань вхідних вузлів зменшується на вагу відповідної дуги, а вихідних вузлів збільшується на вагу вихідних дуг.
2. Конвеєрна обробка. Пікова та реальна продуктивність. Графік залежності продуктивності конвеєрного пристрою від довжини вхідного набору даних.
Під терміном паралельні обчислення розуміють сукупність питань, що відноситься до створення ресурсів паралелізму в процесах вирішення задачі з метою досягнення більшої ефективності використання обчислювальної техніки.
Направлений на збільшення ефективності роботи комп’ютерної системи.
Удосконалення комп’ютерів призводить до збільшення їх продуктивності, тобто до збільшення можливості виконання більшої кількості операцій за 1 часу. Продуктивність вимірюється у MIPS (мільйон ітерацій з плаваючою комою за секунду).
Реальна продуктивність обчислювальної системи визначається як продуктивність, якої сягає обчислювальна система при виконанні конкретної задачі.
Пікова продуктивність – сумарна продуктивність АЛП.
Ефективність системи – відношення реальної продуктивності до пікової. Якщо продуктивність системи <0.5 , то система працює незадовільно.
Способи паралельної обробки:
1.Чистий паралелізм .
2.Конвеєризація.
Чистий паралелізм характеризується повторним використанням однакових елементів, об’єктів, модулів і дає прямо пропорційне зростання використаним елементам продуктивності.
Конвеєризація. Якщо кожну мікро операцію задачі виділити в окремий пристрій і розташувати їх у порядку виконання, причому вхід п–нного мікропристрою пов'язаний з виходом n-1 , то такий спосіб організації обчислень носить назву конвеєрної обробки. Кожен мікро пристрій називається кроком конвеєра , а загальне число кроків визначає довжину конвеєра.
Якщо конвеєр кроків містить n кроків і кожен з них спрацьовує за 1 часу, то час обробки n незалежних операцій складе Всі операції бувають двох типів: векторні і скалярні.
Якщо хоча б один елемент команди є вектором, то команда називається векторною. Тоді кількість операцій визначається: L+n-1+, де - час ініціалізації вектора. Векторні операції ефективні тоді, коли n>>, в протилежному випадку вектори перетворюються в скаляри, тобто, оскільки ні , ні L не залежать від n, то із збільшенням довжини вхідних векторів, ефективність конвеєрної обробки зростає.
Формула ефективності:
E = n/t = n /( + L + n - 1) = 1 /((/n) + (L/n) + - (/n)) = 1 / + (( + L – 1)/n)
При n E 1/
3. Ступінь деталізації декомпозиції, ступінь паралелізму паралельного алгоритму. Граф залежності задач.
Для формування паралельного алгоритму необхідно:
1.ідентифікувати частини роботи, які можуть бути виконані одночасно
2.відобразити зазначені частини на множину одночасно застосовуваних процесорів
3.розподілити вхідні, вихідні і проміжні дані між процесами відповідно до поставленої задачі
4.керувати доступом до спільно використовуваних даних
5.синхронізувати процеси на різних стадіях виконання програми
Процес розподілу обчислень на менші частини, деякі або всі з яких можуть бути виконані паралельно, називається декомпозицією.
Задачі – це визначені програмістом модулі обчислень, на які поділяється основне завдання за допомогою декомпозиції. Задачі можуть мати довільний розмір, але, визначені один раз, вони розцінюються як неподільні.
Частіше за все декомпозиція розбиває завдання на множину взаємозалежних задач. Абстракція, яка відображає зв’язок між задачами і власний порядок їх виконання називається ГЗЗ. ГЗЗ – це направлений, ациклічний граф, вузли якого є виконуваними задачами, а дуги вказують на залежність між ними. Якщо задачі є незалежними, то ГЗЗ буде незв’язаним.
Число і розмір задач визначає ступінь деталізації паралельного алгоритму. Декомпозицію на велику кількість малих задач називають мілкомодульною, а на велику кількість крупних задач - крупномодульною. Поняття, пов’язане із ступенем деталізації – ступінь паралелізму. Максимальне число задач, які в паралельній програмі можуть бути виконані одночасно, носять назву максимальний ступінь паралелізму.
В більшості випадків максимальний ступінь паралелізму є меншим за загальну кількість задач через взаємодію задач.
Середній ступінь паралелізму – це відношення загальної кількості задач до висоти паралельної форми алгоритму (кількості тактів).
Ступінь паралелізму також залежить від форми ГЗЗ. Одна і та сама ступінь деталізації не визначає один і той самий ступінь паралелізму.
4. Взаємодія задач при паралельній обробці. Граф взаємодії задач.
Задачі – це визначені програмістом модулі обчислень, на які поділяється основне завдання за допомогою декомпозиції. Задачі можуть мати довільний розмір, але, визначені один раз, вони розцінюються як неподільні.
Число і розмір задач визначає ступінь деталізації паралельного алгоритму. Декомпозицію на велику кількість малих задач називають мілкомодульною, а на велику кількість крупних задач - крупномодульною. Поняття, пов’язане із ступенем деталізації – ступінь паралелізму. Максимальне число задач, які в паралельній програмі можуть бути виконані одночасно, носять назву максимальний ступінь паралелізму.
В більшості випадків максимальний ступінь паралелізму є меншим за загальну кількість задач через взаємодію задач.
Середній ступінь паралелізму – це відношення загальної кількості задач до висоти паралельної форми алгоритму (кількості тактів).
Крім зернистості і ступеня паралелізму є ще один чинник, який не дає отримати максимальне прискорення від застосування паралельного алгоритму, а саме взаємодія між задачами, що виконуються на різних процесорах. Модель взаємодії задач характеризується ГВЗ. Вершинам і ребрам ГВЗ можуть бути представлені ваги, відповідно до кількості обчислень і числа взаємодій, що передаються вздовж ребра. Ребра в ГВЗ частіше за все неорієнтовані, але вони можуть вказувати на напрям, якщо потік даних однонаправлений. Масив ребер ГВЗ зазвичай надмножина масиву ребер ГЗЗ.
|
| |
| |
| Ellcrys | Дата: Вторник, 21.06.2011, 14:07 | Сообщение # 2 |
|
Любопытный соф
Группа: Администраторы
Сообщений: 56
Статус: Offline
| 5. Вартість операції, завантаженість пристрою, прискорення системи. 1-й закон Амдала.
Будь-яка ОС є сукупністю функціональних пристроїв (ФП), що працюють в часі. Оцінимо якість роботи ОС за допомогою спеціальних характеристик. Для цього введемо ряд понять:
Назвемо ФП простим, якщо жодна наступна операція не може почати виконуватись раніше, ніж закінчиться попередня. Основна риса такого пристрою – монопольне вик. свого обладнання для виконання кожної окремої операції. На відміну від простого ФП, конвеєрний ФП розподіляє своє обладнання для одночасної реалізації декількох операцій. Простий ФП завжди можна вважати конвеєрним з довжиною конвеєра, рівною 1.
Назвемо вартістю операції час її реалізації, а вартістю роботи — суму вартостей всіх виконаних операцій. Тобто, вартість роботи — це час послідовної реалізації всіх даних операцій на простих ФП з аналогічними періодами спрацьовувань. Завантаженістю пристрою на даному відрізку часу називатимемо відношення вартості реально виконаної роботи до максимально можливої вартості. Ясно, що завантаженість р завжди задовольняє умовам 0 ≤ р ≤ 1. Має місце також очевидне
ТВЕРДЖЕННЯ 1
Максимальна вартість роботи, яку можна виконати за час Т, рівна Т для простого ФП і nТ для конвейєрного ФП довжини n.
Називатимемо реальною продуктивністю системи пристроїв кількість операцій, реально виконаних в середньому за одиницю часу. Піковою продуктивністю називатимемо максимальну кількість операцій, яка може бути виконана тією ж системою за одиницю часу за відсутності зв'язків між ФП. З визначень витікає, що як реальна, так і пікова продуктивності системи є сумами відповідно реальних і пікових продуктивностей всіх складових системи пристроїв.
ТВЕРДЖЕННЯ 2
Хай система складається з s пристроїв, в загальному випадку простих або конвеєрних. Якщо пристрої мають пікові продуктивності π1,...πs і працюють із завантаженостями р1,...,рs, то реальна продуктивність системи виражається формулою
Введемо поняття "прискорення":
Хай алгоритм реалізується за час Т на обчислювальній системі з s пристроїв, що мають пікові продуктивності 1,....,s, які зв’язані співвідношенням 1≤2≤....≤s. Прискоренням реалізації алгоритму на даній ОС або просто прискоренням R будемо називати відношення R=r/s. Беручи до уваги (1), маємо
Розглянемо систему з s пристроїв. Оскільки будь-який конвеєрний ФП завжди можна представити як лінійний ланцюжок простих пристроїв, то вважатимемо всі пристрої простими. Допустимо, що між пристроями встановлені направлені зв'язки, і вони не міняються в процесі функціонування системи. Побудуємо орієнтований мультиграф, в якому вершини символізують пристрої, а дуги — зв'язки між ними. Назвемо цей мультиграф графом системи.
Дослідимо максимальну продуктивність системи, тобто її максимально можливу реальну продуктивність при достатньо великому часі функціонування.
ТВЕРДЖЕННЯ 3
Хай система складається з s простих пристроїв з піковими продуктивностями 1,....,s. Якщо граф системи зв'язний, то максимальна продуктивність rmax системи виражається формулою
Майже дослівне повторенням твердження 3 носить назву:
НАСЛІДОК (1-ИЙ ЗАКОН АМДАЛА)
Продуктивність обчислювальної системи, що складається із зв'язаних між собою пристроїв, в загальному випадку визначається найнепродуктивнішим її пристроєм.
Припустимо, що всі пристрої, до того ж, прості і універсальні, тобто на них можна виконувати різні операції. Хай на такій системі реалізується деякий алгоритм, а сама реалізація відповідає якійсь його паралельній формі. Допустимо, що висота паралельної форми рівна m, ширина рівна q і всього в алгоритмі виконується N операцій.
6. Другий та третій закони Амдала.
Мінімальне число пристроїв системи, при якому може бути досягнуто максимально можливе прискорення, рівне ширині алгоритму.
Припустимо, що з яких-небудь причин n операцій з N ми вимушені виконувати послідовно. Причини можуть бути різними. Наприклад, операції можуть бути послідовно зв'язані інформаційно. І тоді без зміни алгоритму їх не можна реалізувати інакше. Відношення = n/N назвемо часткою послідовних обчислень.
НАСЛІДОК (2-Й ЗАКОН АМДАЛА)
Хай система складається з s однакових простих універсальних пристроїв. Припустимо, що при виконанні паралельної частини алгоритму всі s пристроїв завантажені повністю. Тоді максимально можливе прискорення рівне
Позначимо через пікову продуктивність окремого ФП. Оскільки якщо система складається з s пристроїв однакової пікової продуктивності, то прискорення системи дорівнює сумі завантаженості всіх пристроїв:
Якщо всього виконується N операцій, то серед них N операцій виконується послідовно і (1 - )N паралельно на s пристроях по (1 - )N/s операцій на кожному. Можна вважати, що всі послідовні операції виконуються на першому ФП. Всього алгоритм реалізується за час
На паралельній частині алгоритму працюють як перший, так і вся решта пристроїв, витрачаючи на це час:
для 2 ≤ і ≤ n. Тому p1 = 1 і
Отже
НАСЛІДОК (3-Й ЗАКОН АМДАЛА)
Хай система складається з простих однакових універсальних пристроїв. При будь-якому режимі роботи її прискорення не може перевершити зворотню величину частки послідовних обчислень.
7. Потоки і багатозадачність. Потік, процес, програма, багатопотоковість. Типи потоків, види багатозадачності. Правила використання потоків.
Потоки – це об'єкти, які отримують час процесора. Час звичайно виділяється квантами. Квант часу – це інтервал, що є у розпорядженні потоку до тих пір, поки час не буде у нього відібрано і передано в розпорядження іншого потоку. Потрібно мати на увазі, що кванти виділяються не програмам або процесам, а породженим ними потокам. Як мінімум, кожен процес має хоча б один потік, але Windows 95 і Windows NT дозволяють запустити в рамках процесу скільки завгодно потоків.
Два головні типи потоків — асиметричні і симетричні. Частіше всього на персональних комп'ютерах використовують асиметричні потоки. Асиметричні потоки (Asymmetric threads) — це потоки, що вирішують різні задачі і, як правило, не розділяють ресурси. Один з таких потоків відповідає за друк; інший обробляє повідомлення від клавіатури і миші; третій завідує автоматичним збереженням документа користувача. Симетричні потоки (Symmetric threads) виконують одну і ту ж роботу, розділяють одні ресурси і виконують один код.
Пріоритет потоків. Операційна система планує час процесора відповідно до пріоритету потоків. Коли потік створюється, йому призначається пріоритет, відповідний пріоритету його процесу, що породив. У свою чергу, процеси можуть мати наступні класи пріоритетів:
- Реального часу (Real time) - Високий (High) - Нормальний (Normal) - Фоновий (Idle)
Пріоритети мають значення від 0 до 31. Процес, що породив потік, може згодом змінити його пріоритет; у цій ситуації програміст має нагоду управляти швидкістю відгуку кожного потоку.
Процес – це виконання програми. Компоненти процесу – це програма , що виконується, її дані , її ресурси (пам’ять), стан виконання. Процес володіє своїм адресним простором, і його стан характеризується наступною інформацією: таблиці сторінок, дескриптори файлів, замовлення на ввід/вивід інформації, регістри. Процеси або нитки можуть взаємодіяти:
1.Через розподілення пам’яті (ОП, зовн.)
2.Завдяки передачі повідомлень
При взаємодії процесів через спільну пам'ять необхідна синхронізація їх виконання.
Розрізняють 2 види синхронізації:
1.Взаємне виключення критичних інтервалів
2.Координація процесів
Очевидно, що при програмуванні для однопотокового середовища в будь - який момент часу звертається до об’єкту лише 1 потік, то є гарантія що кожний метод завершиться до виклику наступного. Це значить, що об’єкт для своїх клієнтів знаходиться в дійсному стані. А при багатопотоковому програмуванні трапляються ситуації, коли потоки звертаються до об’єкту, що знаходяться в недійсному стані. Результат виконання не передбачено.
Термін безпека потоків означає підтримку об’єктів в дійсному стані при одночасному звертанні до них декількох потоків. Стандартний засіб уникнення непередбачених ситуацій – це синхронізація. Синхронізація дозволяє задавати критичні секції. Критичні секції коду – в кожен окремий момент часу може входити 1 потік, гарантуючи, що будь-які тимчасові недійсні стани об’єкту будуть невидимі його клієнтам.
Дві типові проблеми, з якими програміст може зіткнутися при роботі з потоками :
1.Гонки (Race conditions) 2. Тупіки(Deadlocks).
Правила використання потоків
1.Для досягнення підвищеного паралелізму.
Дуже часто додаткам вимагається виконувати декілька задач одночасно.
2.З метою спрощення конструкції.
Популярний спосіб спрощення структури складних систем – використання черг і асинхронної обробки. Щоб задіяти таку конструкцію вам доведеться підготувати черги для обробки подій, що відбуваються у вашій системі. Замість прямого виклику методів створюються об’єкти і поміщаються в черги , в яких відбувається їх обробка. На іншому кінці цих черг працює багато потокові серверні програми, налаштовані на відстежування повідомлень , що приходять в ці черги. Перевага спрощених конструкцій цього типу – надійність, стійкість і розширюваність заснованих на них систем.
3.Для ефективного використання процесорного часу.
Часто ваш додаток реально не виконує ніякої роботи, в той же час продовжуючи використовувати свій квант. Прикладом може служити очікування виводу документів на друк або закінчення операцій введення-виведення жорсткого диску CD-ROM. У кожному з цих випадків процесорний час не використовується. Ці випадки є кандидатами на перевід в потоки, що працюють у фоновому режимі.
8. Організація обчислень в машинах потоків даних.
Такі машини анулюють дві риси машин Фон-Неймана, а саме:
1.лічильник команд
2.традиційна пам'ять
Принцип роботи таких систем базується на використанні правила запалювання: команда оголошується готовою до виконання, як тільки обчислені всі операнди, що необхідні для її виконання. Команда, для якої ця умова виконана, називається командою, що спрацювала. У відповідності до описаного вище правила, дана модель є асинхронною. Оскільки доступність обчислених операндів дозволяє одночасне виконання декількох операторів, то паралельність дії є внутрішньою властивістю схем потоків даних.
Обчислення в МПД
Програма в МПД може бути представлена як орієнтований граф. Дуги в ньому бувають двох типів:
1.неперервні (такі дуги переносять числову та строкову інформацію) – зв’язки даних
2.перервані (переносять булеві змінні) – зв’язки керування
Вершинами такого графу є актори, які бувають 5 типів:
розмножувачі
блоки виконання операцій
блоки прийняття рішень
змішувачі
клапани або вентилі
9. Декомпозиція задач за вхідними даними.
Процес розподілу обчислень на менші частини, деякі або всі з яких можуть бути виконані паралельно, називається декомпозицією.
Застосовується до даних, які оперують великими масивами чисел. Проводиться в два етапи:
1)розділення даних
2)використання для розподілу основного завдання на окремі задачі цього розділення
Секціонування здійснюється різними способами, буває різних типів:
1.секціонування за вихідними даними
2.секціонування за вхідними даними
3.секціонування за вхідними і вихідними даними
4.секціонування за проміжними даними
Правило власника обчислень – кожне секціонування має виконувати обчислення над всіма даними, якими володіє.
Секціонування за вхідними даними застосовується у випадку, коли кожен вихідний елемент обчислюється як функція входу, але секціонування за вихідними даними неможливе
Приклад: визначення мінімуму або максимуму з набору чисел
10. Декомпозиція задач за вихідними даними.
Процес розподілу обчислень на менші частини, деякі або всі з яких можуть бути виконані паралельно, називається декомпозицією.
Застосовується до даних, які оперують великими масивами чисел. Проводиться в два етапи:
2)розділення даних
3)використання для розподілу основного завдання на окремі задачі цього розділення
Секціонування здійснюється різними способами, буває різних типів:
1.секціонування за вихідними даними
2.секціонування за вхідними даними
3.секціонування за вхідними і вихідними даними
4.секціонування за проміжними даними
Правило власника обчислень – кожне секціонування має виконувати обчислення над всіма даними, якими володіє.
Секціонування за вихідними даними – такий тип секціонування можливий, коли вихідні дані не залежать один від одного і кожен вихідний елемент є лише функцією входу
Приклад: матричне множення. Обчислення кожного вихідного елементу виділяється в окрему задачу.
11. Дослідницька декомпозиція задач.
Процес розподілу обчислень на менші частини, деякі або всі з яких можуть бути виконані паралельно, називається декомпозицією.
Даний тип декомпозиції використовується, коли існує декілька шляхів розв’язку однієї задачі, тобто існує простір для вибору рішень.
При такому способі ми розбиваємо область пошуку на менші частини і аналізуємо кожну з них одночасно з метою знайти вірний розв’язок.
Приклад: пятнашка
Дана задача розв’язується типово, використовуючи методи пошуку дерева. Вихідна конфігурація може мати 2, 3 або 4 на ступні конфігурації. Набір просторових конфігурацій можна розглядати як граф, кожен вузол – це конфігурація, а кожне ребро сполучає дві послідовні конфігурації, які утворюються одна з одної лише рухом однієї складової.
12. Декомпозиція задач за проміжними даними.
Процес розподілу обчислень на менші частини, деякі або всі з яких можуть бути виконані паралельно, називається декомпозицією.
Застосовується до даних, які оперують великими масивами чисел. Проводиться в два етапи:
3)розділення даних
4)використання для розподілу основного завдання на окремі задачі цього розділення
Секціонування здійснюється різними способами, буває різних типів:
1.секціонування за вихідними даними
2.секціонування за вхідними даними
3.секціонування за вхідними і вихідними даними
4.секціонування за проміжними даними
Правило власника обчислень – кожне секціонування має виконувати обчислення над всіма даними, якими володіє.
Секціонування за проміжними даними – зазвичай проміжні дані явно не існують, необхідно реструктурувати первинний алгоритм.
Приклад: матричне множення. Максимальний ступінь паралелізму дорівнює 4. Можна збільшити ступінь паралелізму, ввівши проміжні дані. На цій додатковій стадії обчислення додаються субматриці, а результат зберігається у проміжній тривимірній субматриці D.
Реструктуризація первинного алгоритму дала змогу отримати вищий ступінь паралелізму програми, але це прискорення було досягнуто за рахунок використання додаткового об’єму пам’яті.
13. Граф машин потоків даних (МПД) і його основні елементи.
Схема МПД може бути представлена сукупністю процесорних елементів. Кожен вузол визначає операцію для виконання і адреси всіх вузлів, які очікують на обчислення даного операнду. В дійсності процесор МПД працює як простий круговий конвеєр. Токени - дані, що надходять з мережі. Складаються з даних і адреси призначення або тега. Актори – дії, операції, що виконуються над токенами.
У вузлі відповідності тег порівнюється з тегами, наявними у сховищі токенів. Якщо такі присутні, то вони обираються разом з операцією, яку над ними необхідно виконати. Потім вони разом подаються до модуля виконання. Отриманий результат відправляється за тими адресами, де на нього очікують. Якщо ж не всі токени для операції готові, то даний токен розміщується у сховищі токенів і очікує своєї черги на виконання.
14. Способи взаємодії ниток при багато потоковому програмуванні: семафори, події, взаємне виключення.
Дві типові проблеми, з якими програміст може зіткнутися при роботі з потоками :
Гонки (Race conditions) Тупіки(Deadlocks).
Тупіки. Тупік має місце тоді, коли потік чекає ресурс, який в даний момент належить іншому потоку. Розглянемо приклад: Потік 1 захоплює об'єкт А і, для того, щоб продовжувати роботу, чекає можливості захопити об'єкт Б. В той же час Потік 2 захоплює Об'єкт Б і чекає можливості захопити Об'єкт А. Розвиток цього сценарію заблокує обидва потоки; жоден з них не виконуватиметься.
В ролі ресурсів виступають довільні спільно використовувані об’єкти, а саме файли, масиви в пам’яті.
Гонки. Ситуація гонок виникає, коли два або більш потоків намагаються дістати доступ до загального ресурсу і змінити його стан. Розглянемо наступний приклад. Хай Потік 1 дістав доступ до ресурсу і змінив його в своїх інтересах; потім активізувався Потік 2 і модифікував цей же ресурс до завершення Потоку 1. Потік 1 вважає, що ресурс залишився в тому ж стані, що і був до перемикання. Залежно від того, коли саме був змінений ресурс, результати можуть варіюватися — іноді код виконуватиметься нормально, іноді - ні.
Ситуації гонок і тупіків можна уникнути, якщо використовувати такі прийоми:
1.Взаємне виключення. Дозволяє тільки одному потоку за один раз володіти об’єктом.
Характеризується:
тільки 1 процес знаходиться в середині критичного інтервалу
якщо жоден процес не знаходиться в критичному інтервалі то довільний інший процес, яки бажає отримати доступ до об’єкту повинне отримати дозвіл без жодної затримки
не повинно існувати жодних домовленостей про швидкість процесу
2.Семафори. Семафор (semaphore) подібний взаємному виключенню. Різниця між ними у тому, що семафор може управляти кількістю потоків, які мають до нього доступ.
Семафор встановлюється на граничне число потоків, яким доступ дозволений. Коли це число досягнуте, подальші потоки будуть припинені, поки один або більш потоків не від'єднаються від семафора і не звільнять доступ. Семафор – невід’ємна ціла змінна, яка може змінюватись і перевірятись лише двома функціями:
P(s): [|знач.|><звільнити>]
V(s): [|знач.|><зайняти>]
Блокування процесу і перемикання на інший не ефективно, коли семафор захоплюється на дуже короткий час. Очікування звільнення таких семафорів може бути реалізовано в ОС завдяки циклічним опитуванням значень семафору. Недоліки такого «активного очікування» - не продуктивна витрата часу, навантаження на загальну пам'ять і можливість практично заблокувати роботу процесу, що знаходиться в критичному інтервалі. Тобто, якщо об’єкт використовується великою кількістю потоків, використання семафорів не доцільне.
3.Подія – змінна, яка показує що відбулася певна подія.
Для об’явлення події використовується оператор: Post(ім’я змінної) , для очікування : Wait(ім’я змінної). Для очищення (привласнення 0 значення): clear(ім’я змінної).
4.Критична секція. Критичні секції подібні взаємним виключенням по суті, проте між ними існують дві головні відмінності:
взаємні виключення можуть бути спільно використані потоками в різних процесах, а критичні секції — ні;
якщо критична секція належить іншому потоку, чекаючий потік блокується аж до звільнення критичної секції. На відміну від цього, взаємне виключення дозволяє продовження після закінчення тайм-ауту.
5.Обмін повідомленнями. «Взаємодія паралельних процесів».1978р., Хоар.
Мета: позбутись проблему розподілу пам’яті і запропонувати модель взаємодії процесів у розподілених системах.
Використовуються основні функції:
1.Send (destination, message, size) 2. Receive (source, message, size)
Адресатом виступає процес, відправник не специфікується , в його ролі виступає довільний об’єкт.
Механізм семафорів та взаємодії процесів семантично взаємо заміняються . Тому на мультипроцесорах використовується один через інший.
15. Рекурсивна декомпозиція. Приклад швидкого сортування масиву чисел.
Процес розподілу обчислень на менші частини, деякі або всі з яких можуть бути виконані паралельно, називається декомпозицією.
При цьому способі основне завдання розподіляється певним способом на невелику кількість незалежних задач. На наступному кроці отримані задачі знову декомпозуються, рекурсивно застосовуючи вищезазначений спосіб і т.д.
Цей спосіб призводить до виявлення природного паралелізму системи.
Приклад. Швидке сортування набору чисел : 5 12 11 1 10 6 8 2 7 4 9 3
Вибирається основний елемент Х і основна послідовність А розбивається на дві послідовності А0 і А1, такі що всі елементи послідовності А0 є меншими за Х, а всі елементи А1 є більшими за Х і т.д.
|
| |
| |
|
|
|
