Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Паралельні обчислення — це форма обчислень, в яких кілька дій проводяться одночасно. Ефективний розподіл процесу обчислень між багатьма процесорами й забезпечення їхнього рівномірного завантаження - основна складність паралельного програмування, яке справедливо вважається набагато складнішим, ніж послідовне. Паралельні та розподілені архітектури можуть бути найрізноманітнішими. В той час як деякі розподілені архітектури чудово працюють в Web- середовищі, вони практично приречені на невдачу в середовищі реального часу. Наприклад, розподілені архітектури, які розраховані на тривалі часові затримки, цілком прийнятні для Web- середовища і цілковито неприйнятні для багатьох середовищ реального часу. Затримка (час очікування), яка присутня в багатьох поштових Web- системах, була б просто нищівною для таких систем реального часу, як банкомати. Наприклад, методи векторної обробки даних найкраще придатні для рішення певних математичних задач і проблем імітаційного моделювання, але вони абсолютно неефективні в застосування до мультиагентних алгоритмів планування. Поширені архітектури ПЗ, що придатні для паралельного та розподіленого програмування, подано в табл.
Чотири базові моделі, подані в табл. 2, і їх варіанти забезпечують основу для всіх паралельних типів архітектур Вибраний тип архітектури повинен максимально відповідати цьому природному паралелізму. Наприклад, паралелізм в рішенні, можливо, краще описувати за допомогою симетричної моделі, або моделі мережі з рівноправними вузлами (peer-to-peer model)? в якій всі виконавці є рівноправними, на відміну від несиметричної моделі керуючийвиконавчий, в якій існує головний (керуючий) процес, який керує всіма іншими процесами як підлеглими.
|
Таблиця 2. |
Поширені архітектури ПЗ, які використовуються для паралельного і розподіленого програмування |
||
|
Модель |
Архітектура |
Розподілене програмування |
Паралельне програмування |
|
Модель ведучого вузла, інакше кажучи:
|
Головний вузол керує задачами, тобто контролює їх виконання і передає роботу підлеглим задачам |
||
|
Модель рівноправних вузлів |
Всі задачі, в основному, мають однаковий ранг, і робота між ними розподіляється рівномірно |
||
|
Векторна або конвеєрна (потокова) обробка |
Один виконавчий вузол відповідає кожному елементу масиву (вектора) або кроку конвеєра |
18)UML-діаграми для створення багатопоточних паралельних та розподілених програм.
UML — уніфікована мова моделювання, використовується у парадигмі об'єктно-орієнтованого програмування. UML був створений для визначення, візуалізації, проектування й документування в основному програмних систем. Подано сім UML-діаграм, які часто використовуються при створенні багатопоточних, паралельних або розподілених програм.
|
UML-діаграми, які використовуються при створенні багатопоточних, паралельних або розподілених програм |
|
|
UML-діаграми |
Опис |
|
Діаграма (видів) діяльності |
Різновид діаграми станів, в якій більшість станів (або всі) являють види діяльності, а більшість переходів (або всі) активізуються при виконанні деякої дії у вихідних станах |
|
Діаграма взаємодії |
Тип діаграми, що відображає взаємодію між об’єктами. Взаємодія описується у вигляді повідомлень, якими вони обмінюються. До діаграм взаємодії належать діаграми взаємодії, діаграми послідовностей і діаграми (видів) діяльності |
|
Діаграма (паралельних) станів |
Діаграма, яка показує послідовність перетворень об’єкту в процесі його реакції на події. При використанні діаграми паралельних станів дані перетворення можуть відбуватися на протязі одного і того ж інтервалу часу |
|
Діаграма послідовностей |
Діаграма взаємодії, в якій відображено організацію структури об’єктів, які приймають або відправляють повідомлення (акцент на впорядкування подій в часі) |
|
Діаграма співробітництва |
Діаграма взаємодії, в якій відображено організацію структури об’єктів, які приймають або відправляють повідомлення (акцент на структурній організації) |
|
Діаграма розгортання (впровадження) |
Діаграма, яка показує динамічну конфігурацію вузлів обробки, апаратних засобів і програмних компонентів в системі |
|
Діаграма компонентів |
Діаграма взаємодії, в якій відображається організація фізичних модулів програмного коду (пакетів) в системі залежності між ними |
Процес (process) – це деяка частина (одиниця) роботи, що створюється операційною системою.
Розрізняють користувацькі процеси і системні процеси. Процеси, які виконують системний код, називаються системними і застосовуються до системи в цілому. Вони займаються виконанням наступних службових задач, як розподіл пам’яті, обмін сторінками між внутрішнім допоміжним запам’ятовуючим пристроєм, контроль пристроїв та інше. Вони також виконують деякі задачі задорученням користувацьких процесів, наприклад, виконують запити на ввід-вивід даних, виділяють пам'ять та інше. Користувацькі процеси виконують власний код і інколи звертаються до системних функцій. Виконуючи власний код, користувацький мпроцес перебуває в користувацькому режимі (user mode). В користуванькому режимі процес не може виконувати привілейовані машинні команди. Викликаючи системні функції (наприклад read (), write () або open ()) користуванький процес виконує інструкції операційної системи. При цьому користувацький процес утримує процесор до тих пір, доки не буде виконаний системний виклик
Процеси мають характеристики, які використовуються для ідентифікації і визначення їх поведінки. Ядро підтримує необхідні структури даних і надає системні функції, які дають можливість користувачу отримати доступ до цієї інформації. Деякі дані зберігаються у блоках управління процесами (process control block – PCB), або БУП. Дані, які зберігаються в БУП-блоках, описують процес з точки зору потреб операційної системи. За допомогою цієї інформації операційна система може керувати кожним процесом. Коли операційна система переключається з одного процесу на інший, вона зберігає біжучий стан процесу, який виконується і його контекст в області зберігання БУП-блоку, щоб належним чином відновити виконання цього процесу в наступний раз, коли йому знову буде виділений центральний процесор (ЦП). БУП-блок зчитується і оновлюється різними модулями операційної системи. Модулі відповідають контроль продуктивності операційної системи, планування, розподілення ресурсів і доступ до механізму обробки переривань іабо модифікують БУП-блок. БУП-блок містить наступну інформацію:
. Стекові вказівники і вміст регістрів користувача, управління і стану містить інформацію, зв’язану зі станом процесора. При виконанні процесу відповідна інформація розміщується в регістрах ЦП. При перемиканні операційної системи з одного процесу на інший вся інформація з цих регістрів зберігається. Коли процес знову отримує ЦП в тимчасове користування, раніше збережена інформація може бути відновлена.
Адресний простір процесу поділяється на три логічних розділи: текстовий (для коду програми), інформаційний (для даних програми) і стеків (для стеків програми). Текстовий розділ (розміщений в нижній частині адресного простору) містить інструкції що будуть виконуватися, і які називаються програмним кодом. Розділ даних (розміщений над текстовим розділом) містить ініційовані глобальні, зовнішні і стати-
образПРОЦЕСУ
БУП
Стек ядра
Стек користувача
РОЗДІЛ ДАНИХ
РОЗДІЛ КОДУ
ІДЕНТИФІКАЦІЯ ПРОЦЕСУ
ІНФОРМАЦІЯ ПРО СТАН ПРОЦЕСУ
ІНФОРМАЦІЯ ПРО УПРАВЛІННЯ ПРОЦЕСОМ
РОЗДІЛ
СТЕКІВ
чні змінні процесу. Розділ стеків містить локально створювані змінні і параметри, які передаються функціям. Оскільки процес може викликати як системні функції, так і функції, визначені користувачем, в стековому розділі підтримуються два стеки: стек користувача і стек ядра. При виклику функції створюється стеків фрейм функції, якій розміщується в стек користувача або стек ядра в залежності від того, в якому режимі перебуває процес в даний час: в користувацький або привілейований (режим ядра). Стеків розділ має тенденцію рости в напрямі розділу даних. При виході з функції її стеків фрейм виймається з стеку. Розділи коду, даних і стеків, а також блок керування процесом створюють частину того, з чого складається образ процесу (process image).
Адресний простір процесу віртуальний. Застосування віртуальної пам’яті дозволяє відокремити адреси, що використовуються в біжучому процесі, від адрес, реально доступних у внутрішній пам’яті. Тим самим значно збільшується задіяний адресний простір пам’яті у порівнянні з реально доступними адресами. Розділи віртуального адресного простору процесу являють собою суміжні блоки пам’яті. Кожний такий розділ і фізичний адресний простір розділені на ділянки пам’яті, які називаються сторінками.
Пам'ять
Файли
Пристрої
Процеси
Таблиці використання пам’яті
Таблиці файлів
Таблиці пристроїв вводу-виводу
Образ процесу
з PID =19
PID
PPID
STAT
Рис. 3. Структура таблиць процесів операційної системи
ТАБЛИЦІ ПРОЦЕСІВ
|
19 |
6 |
D |
||
|
45 |
90 |
S |
||
|
12 |
15 |
R |
||
|
30 |
9 |
S |
||
|
Вільний елемент таблиці |
||||
|
42 |
30 |
S |
Образ процесу
з PID =45
Образ процесу
з PID =42
2. Стани процесів
Під час виконання процесу його стан змінюється. Під станом процесу розуміють його біжучий режим або статус. В середовищі UNIX процес може перебувати в одному з наступних станів:
Рис. 4. Стани процесів і переходи між ними
ЗУПИНЕНО
ГОТОВИЙ
працездатний
ВИКОНУЄТЬСЯ
ОЧІКУЄ
ЗОМБІ
Сигнал видано
Сигнал видано
Вхід
Вихід
Вивантаження
Завантаження
Кінець кванта часу
Пройшла подія або завершена операція ввід-вивід
Очікування події або завершення операція ввід-вивід
Вихід
Стан процесу змінюється при певних умовах, які створюються існуванням процесу або операційною системою. Під зміною стану, або переходом з одного стану в інший, розуміють обставини, заставляють процес змінити свій стан. На рис. 4 показано діаграму станів для середовища UNIX. Діаграма станів містить вузли та напрямлені ребра, що з’єднують ці вузли. Кожен вузол відображає стан процесу, а напрямлені ребра між вузлами – переходи з одного стану в інший. Можливі зміни стані (з анотацією) описано в табл. 1. На рис. 4 і табл. 1 показано, що між станами дозволені лише певні переходи. Наприклад, між станами готовності і виконання існує перехід (ребро діаграми), а між станами очікування і виконання – немає. Це означає, що можливі обставини, які заставляють процес перейти з стану готовності в стан виконання, але немає обставин, які можуть заставити процес перейти в стан виконання з стану очікування.
Коли процес тільки створюється, від готовий до виконання своїх інструкцій, але повинен очікувати свого часу до тих пір, доки не звільниться процесор. Кожному процесу персонально дозволяється використати процесор в межах дискретного часового інтервалу, який називаємо квант часу (time slice). Процеси, які очікують використання процесора, займають чергу, тобто переміщуються в чергу готових процесів. Тільки з таких черг планувальник вибирає процес, який буде використовувати процесорний час. Процеси, які знаходяться в чергах готових процесів, перебувають в працездатному стані. Коли процесор
|
Переходи процесів з одного стану в інший |
|
|
Переходи між станами |
Опис |
|
ОЧІКУЄ ВИКОНУЄТЬСЯ (завантаження) |
Процес призначається процесору |
|
ВИКОНУЄТЬСЯ ГОТОВИЙ (кінець кванту часу) |
Квант часу процесу, якій призначений процесу закінчився |
|
ВИКОНУЄТЬСЯ ГОТОВИЙ (дострокове вивантаження) |
Процес вивантажується до закінчення його кванту часу. (Це можливе у випадку, якщо став готовим процес з більш високим пріоритетом). Вивантажений процес розміщується знову в чергу процесів |
Якщо готових до виконання процесів більше одного, планувальник повинен визначити, який з них першим призначити процесору. З цією метою планувальник підтримує структуру даних, які дозволяють найбільш ефективним чином розподіляти між процесами процесорний час. Кожен процес отримує клас (тип) пріоритету і розміщується у відповідній йому черзі разом з іншими працездатними процесами того ж пріоритетного класу. Тому істує декілька пріоритетних черг, які відображають різні класи пріоритетів, які використовуються системою. Ці пріоритетні черги впорядковуються і розміщуються в масив розподілу, що називається багаторівневою пріоритетною чергою (multilevel priority queue), зображеній на рис. 5. Кожен елемент цього масиву пов'язаний з конкретною пріоритетною чергою. Для виконання процесором планувальник призначає той процес, який міститься в головній частині не порожньої черги, і має самий високий пріоритет. Пріоритети можуть бути динамічними і статичними
Процесор1
виконується
PID 71
ДИСПЕЧЕР
ПЛАНУВАЛЬНИК
.
.
.
2
1
0
-1
-2
-3
.
.
.
PID 12 PID 17
PID 90 PID 43 PID10 PID 50
PID 12 PID 17
PID 71
рис. 5. Багаторівнева пріоритетна черга
. Стратегія планування
Процеси розміщуються в пріоритетних чергах у відповідності до стратегії планування. В системах UNIX/Linux використовуються дві стратегії планування FIFO (First In First Out – перший прийшов, першим обслужений) і RR (round-robin, тобто циклічна). Схема дії стратегії FIFO подана на рис. 6, а. При використанні стратегії FIFO процеси призначаються процесору у відповідності з часом надходження в чергу. Після закінчення кванту часу процес розміщується на початок (головну частину) своєї пріоритетної черги. Коли процес, який очікує, стає працездатним (працездатним), він розміщується в кінець своєї пріоритетної черги. Процес може викликати системну функцію і відмовитися від процесора на користь іншого процесу з таким же рівнем пріоритету.
ЧЕРГА ГОТОВИХ ПРОЦЕСІВ
PID 35 PID 63
PID 71
Процесор1
виконується
PID 71
Прийшов першим
Прийшов останнім
PID 50
PID 90 PID 43
PID 50
Кінець кванту часу
Запит на операцію ввід-вивід
Операція ввід-вивід завершена
Рис. 6. Схеми дії FIFO- і RR-стратегій планування
ЧЕРГА ГОТОВИХ ПРОЦЕСІВ
PID 35 PID 63
PID 71
Процесор1
виконується
PID 71
Прийшов першим
Прийшов останнім
PID 50
PID 90 PID 43
PID 50
Кінець кванту часу
Запит на операцію ввід-вивід
Операція ввід-вивід завершена
а) FIFO-планування
б) RR -планування
У відповідності з циклічною стратегією планування RR всі процеси вважаються рівноправними (рис. 6, б). RR-планування співпадає з FIFO-плануванням за одним виключенням: після закінчення кванту часу процес розміщується не на початок черги, а в кінець своєї пріоритетної черги, і процесору призначається наступний (по черзі) процес.
Рівень пріоритету процесу можемо змінити за допомогою функції nice (). Кожен пріоритет має фактор поступливості (nice value), який використовується для обчислення рівня пріоритету процесу, який викликає. Процес успадковує пріоритет процесу, який його породив. Щоб понизити пріоритет процесу, необхідно збільшити його фактор поступливості. Лише процеси привілейованих користувачів і ядра системи можуть підвищувати рівні своїх пріоритетів.
Синопсис
# include < unistd.h >
int nice ( int incr );
Чим нижче фактор поступливості, тим вище рівень пріоритету процесу. Параметр incr містить значення, яке добавляється до біжучого фактору поступливості процесу, який викликає. Значення параметру incr може бути від’ємним і додатнім, а фактор поступливості є невід’ємним числом. Додатне значення incr збільшує фактор поступливості, а отже, зменшує рівень пріоритету. Від’ємне значення incr зменшує фактор поступливості, тим самим підвищує рівень пріоритету
Синопсис
# include < sys/resource.h >
int getpriority ( int which, id_t who);
int setpriority ( int which, id_t who, int value);
Функція setpriority () встановлює фактор поступливості для заданого процесу, групи процесів або користувача. Функція getpriority () повертає пріоритет заданого процесу, групи процесів або користувача. Синтаксис використання функцій setpriority () і getpriority () для встановлення і зчитування фактора поступливості біжучого процесу подано в лістінгу 1.
Лістінг 1. Використання функцій setpriority () і getpriority ()
# include < sys/resource.h >
. . .
id_t pid = 0;
int which = PRIO_PROCESS;
int value = 10;
int nice_value;
int ret;
nice_value = getpriority (which, pid);
if (nice_value < value) {
ret = setpriority (which, pid, value);
}
// . . .
В лістінгу 1 повертається та встановлюється пріоритет процесу який викликає. Якщо фактор поступливості процесу, який викликає, стає менше 10, він встановлюється рівним 10. Процес задається значенням, що зберігається в параметрах which і who (синопсис вище). Параметр which може визначати процес, групу процесів або користувача і має наступні значення.
PRIO_PROCESS Означає процес
PRIO_PGRP Означає групу процесів
PRIO_USER Означає користувача
В залежності від значення параметру which параметр who містить ідентифікаційний номер (id) процесу або ефективного користувача. В лістінгу 1 параметру which присвоюється значення PRIO_PROCESS. В лістінгу 1 параметр who встановлюється рівним 0, означаючи тим самим біжучий процес. Параметр value для функції setpriority () визначає нове значення фактора поступливості для заданого процесу, групи процесів або користувача.
Перемикання контексту відбувається в момент, коли процесор перемикається з одного процесу на інший. При перемиканні контексту система зберігає контекст біжучого процесу і встановлює контекст наступного процесу, вибраного для використання процесором. Зберігається та оновлюється вміст регістрів процесора, стан стеку, дані про ідентифікації (про привілеї) користувача та процесу, а також про стратегії планування і облікова інформація.
Система повинна відслідковувати статус пристроїв вводу-виводу процесу та інших ресурсів, а також стан всіх структур даних, пов’язаних з керуванням пам’яттю. Вивантажений (перерваний) процес розміщується у відповідну чергу.
Переривання контексту відбувається у випадках, коли:
Коли вивантажений процес знову обирається для використання процесором, його контекст відновлюється, і виконання продовжується з місця, на якому він був зупинений в попередньому сеансі.