ВІКІСТОРІНКА
Навигация:
Інформатика
Історія
Автоматизація
Адміністрування
Антропологія
Архітектура
Біологія
Будівництво
Бухгалтерія
Військова наука
Виробництво
Географія
Геологія
Господарство
Демографія
Екологія
Економіка
Електроніка
Енергетика
Журналістика
Кінематографія
Комп'ютеризація
Креслення
Кулінарія
Культура
Культура
Лінгвістика
Література
Лексикологія
Логіка
Маркетинг
Математика
Медицина
Менеджмент
Металургія
Метрологія
Мистецтво
Музика
Наукознавство
Освіта
Охорона Праці
Підприємництво
Педагогіка
Поліграфія
Право
Приладобудування
Програмування
Психологія
Радіозв'язок
Релігія
Риторика
Соціологія
Спорт
Стандартизація
Статистика
Технології
Торгівля
Транспорт
Фізіологія
Фізика
Філософія
Фінанси
Фармакологія


Багаторівневі черги (Multilevel Queue)

Для систем, в яких процеси можуть бути легко розсортовані по різних групах, був розроблений інший клас алгоритмів планування. Для кожної групи процесів створюється своя черга процесів, що знаходяться в змозі готовність (див. мал. 3.5). Цим чергам приписуються фіксовані пріоритети. Наприклад, пріоритет черги системних процесів встановлюється вище, ніж пріоритет черг призначених для користувача процесів. А пріоритет черги процесів, запущених студентами, нижче, ніж для черги процесів, запущених викладачами. Це означає, що жоден призначений для користувача процес не буде вибраний для виконання, поки є хоч один готовий системний процес, і жоден студентський процес не отримає в своє розпорядження процесор, якщо є процеси викладачів, готові до виконання. Усередині цих черг для планування можуть застосовуватися самі різні алгоритми. Так, наприклад, для великих рахункових процесів, що не вимагають взаємодії з користувачем (фонових процесів), може використовуватися алгоритм FCFS, а для інтерактивних процесів – алгоритм RR. Подібний підхід, що отримав назву багаторівневих черг, підвищує гнучкість планування: для процесів з різними характеристиками застосовується найбільш відповідний ним алгоритм.


Рис. 3.5. Декілька черг планування

Багаторівневі черги із зворотним зв'язком (Multilevel Feedback Queue)

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

Для простоти розглянемо ситуацію, коли процеси в змозі готовність організовані в 4 черги, як на мал. 3.6. Планування процесів між чергами здійснюється на основі витісняючого пріоритетного механізму. Чим вище на малюнку розташовується черга, тим вище її пріоритет. Процеси в черзі 1 не можуть виконуватися, якщо в черзі 0 є хоч би один процес. Процеси в черзі 2 не будуть вибрані для виконання, поки є хоч один процес в чергах 0 і 1. І нарешті, процес в черзі 3 може отримати процесор в своє розпорядження тільки тоді, коли черги 0, 1 і 2 порожні. Якщо при роботі процесу з'являється інший процес в якій-небудь пріоритетнішій черзі, процес, що виконується, витісняється новим. Планування процесів усередині черг 0–2 здійснюється з використанням алгоритму RR, планування процесів в черзі 3 грунтується на алгоритмі FCFS.


Рис. 3.6. Схема міграції процесів в багаторівневих чергах планування із зворотним зв'язком. Витіснення процесів пріоритетнішими процесами і завершення процесів на схемі не показане

Процес, що народився, поступає в чергу 0. При виборі на виконання він отримує в своє розпорядження квант часу розміром 8 одиниць. Якщо тривалість його CPU burst менше цього кванта часу, процес залишається в черзі 0. Інакше він переходить в чергу 1. Для процесів з черги 1 квант часу має величину 16. Якщо процес не укладається в цей час, він переходить в чергу 2. Якщо укладається – залишається в черзі 1. У черзі 2 величина кванта часу складає 32 одиниці. Якщо для безперервної роботи процесу і цього мало, процес поступає в чергу 3, для якої квантування часу не застосовується і, за відсутності готових процесів в інших чергах, може виконуватися до закінчення свого CPU burst. Чим більше значення тривалості CPU burst, тим в менш пріоритетну чергу потрапляє процес, але тим на більший процесорний час він може розраховувати. Таким чином, через деякий час всі процеси, що вимагають малого часу роботи процесора, виявляться розміщеними у високопріоритетних чергах, а всі процеси, що вимагають великого рахунку і з низькими запитами до часу відгуку, – в низькопріоритетних.

Міграція процесів у зворотному напрямі може здійснюватися по різних принципах. Наприклад, після завершення очікування введення з клавіатури процеси з черг 1, 2 і 3 можуть поміщатися в чергу 0, після завершення дискових операцій введення-виводу процеси з черг 2 і 3 можуть поміщатися в чергу 1, а після завершення очікування всіх інших подій – з черги 3 в чергу 2. Переміщення процесів з черг з низькими пріоритетами в черзі з високими пріоритетами дозволяє більш повно враховувати зміну поведінки процесів з часом.

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

· Кількість черг для процесів, що знаходяться в змозі готовність.

· Алгоритм планування, що діє між чергами.

· Алгоритми планування, що діють усередині черг.

· Правила приміщення процесу, що народився, в одну з черг.

· Правила перекладу процесів з однієї черги в іншу.

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

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

Висновок

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

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

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

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

Взаємодіючі процеси. Категорії засобів обміну інформацією.

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

Для чого процесам потрібно займатися спільною діяльністю? Які існують причини для їх кооперації?

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

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

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

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

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

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

© 2013 wikipage.com.ua - Дякуємо за посилання на wikipage.com.ua | Контакти