РЕФЕРАТ

На тему:

Концепція процесу

1. Процеси

Процес — мінімальний програмний об’єкт, що володіє власними системними
ресурсами (запущена програма).

1.1. Класифікація процесів.

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

По генеалогічній ознаці розрізняють процеси, що породжують і породжені.

По результативності розрізняють еквівалентні, тотожні і рівні процеси.

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

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

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

По зв’язності розрізняють процеси:

а) взаємозв’язані, які мають якийсь зв’язок (просторово-часову,
управляючу, інформаційну);

б) ізольовані — слабо зв’язані;

в) незалежні, які використовують сумісні ресурси, але мають власні
інформаційні бази;

г) взаємодіючі — мають інформаційні зв’язки і розділяють загальні
структури даних;

д) взаємозв’язані по ресурсах;

е) конкуруючі.

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

а) передування — один завжди знаходиться в активному стані раніше, ніж
інший;

б) пріоритетності — коли процес може бути переведений в активний стан
тільки в тому випадку, якщо в стані готовності немає процесів з вищим
пріоритетом, або процесор вільний, або на ньому реалізується процес з
меншим пріоритетом;

в) взаємного виключення — в процесі використовується загальний критичний
ресурс, і процеси не можуть розвиватися одночасно: якщо один з них
використовує критичний ресурс, то інший знаходиться в стані очікування.

1. 2.Нитки

Багатозадачність є найважливішою властивістю ОС. Для підтримки цієї
властивості ОС визначає й оформляє для себе ті внутрішні одиниці роботи,
між якими і буде розділятися процесор і інші ресурси комп’ютера. Ці
внутрішні одиниці роботи в різних ОС носять різні назви — задача,
завдання, процес, нитка. У деяких випадках сутності, що позначаються
цими поняттями, принципово відрізняються один від одного.

Говорячи про процеси, ми відзначали, що ОС підтримує їхню
відособленість: у кожного процесу мається свій ВАП, кожному процесу
призначаються свої ресурси — файли, вікна, семафори і т.д. Така
відособленість потрібна для того, щоб захистити один процес від іншого,
оскільки вони, спільно використовуючи всі ресурси машини, конкурують
один з одним. У загальному випадку процеси належать різним користувачам,
що розділяють один комп’ютер, і ОС бере на себе роль арбітра в
суперечках процесів за ресурси.

При мультипрограмуванні підвищується пропускна здатність системи, але
окремий процес ніколи не може бути виконаний швидше, ніж якби він
виконувався в однопрограмному режимі (усякий поділ ресурсів сповільнює
роботу одного з учасників за рахунок додаткових витрат часу на
ОЧІКУВАННЯ звільнення ресурсу). Однак задача, розв’язувана в рамках
одного процесу, може мати внутрішній паралелізм, що у принципі дозволяє
прискорити її рішення. Наприклад, у ході виконання задачі відбувається
звертання до зовнішньому пристрою, і на час цієї операції можна не
блокувати цілком виконання процесу, а продовжити обчислення по іншій
«галузі» процесу.

Для цих цілей сучасні ОС пропонують використовувати порівняно новий
механізм багатониткової обробки (multithreading). При цьому вводиться
нове поняття «нитка» (thread), а поняття «процес» у значній мірі змінює
зміст.

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

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

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

Нитки іноді називають полегшеними процесами чи міні-процесами. Дійсно,
нитки в багатьох відносинах подібні процесам. Кожна нитка виконується
строго послідовно і має свій власний програмний лічильник і стік. Нитки,
як і процеси, можуть, наприклад, породжувати нитки-нащадки, можуть
переходити зі стану в стан. Подібно традиційним процесам (тобто
процесам, що складаються з однієї нитки), нитки можуть знаходиться в
одному з наступних станів: ВИКОНАННЯ, ОЧІКУВАННЯ і ГОТОВНІСТЬ. Поки одна
нитка заблокована, інша нитка того ж процесу може виконуватися. Нитки
розділяють процесор так, як це роблять процеси, відповідно до різних
варіантів планування.

Однак різні нитки в рамках одного процесу не настільки незалежні, як
окремі процеси. Усі такі нитки мають той самий адресний простір. Це
означає, що вони розділяють ті самі глобальні змінні. Оскільки кожна
нитка може мати доступ до кожної ВА, одна нитка може використовувати
стек іншої нитки. Між нитками немає повного захисту, тому що, по-перше,
це неможливо, а по-друге, не потрібно. Усі нитки одного процесу завжди
вирішують загальну задачу одного користувача, і апарат ниток
використовується тут для більш швидкого рішення задачі шляхом її
разпаралелювання. При цьому програмісту дуже важливо одержати у своє
розпорядження зручні засоби організації взаємодії частин однієї задачі.
Крім поділу адресного простору, усі нитки розділяють також набір
відкритих файлів, таймерів, сигналів і т.п. Отже, нитки мають власні:
програмний лічильник, стек, регістри, нитки-нащадки, стан. Нитки
розділяють: адресний простір, глобальні змінні, відкриті файли, таймери,
семафори, статистичну інформацію.

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

1.3. Керування процесами

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

Щоб процес міг бути виконаний, ОС повинна призначити йому область ОП, у
якій будуть розміщені коди і дані процесу, а також надати йому необхідну
кількість процесорного часу. Крім того, процесу може знадобитися доступ
до таких ресурсів, як файли і пристрої в/в.

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

У мультипрограмній ОС одночасно може існувати кілька процесів. Частина
процесів породжується з ініціативи користувачів і їхніх додатків, такі
процеси звичайно називають користувальницькими. Інші процеси, називані
системними, ініціалізуються самою ОС для виконання своїх функцій.

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

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

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

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

1.4. Стани процесів

В багатозадачній системі процес може знаходитися в одному з трьох
основних станів:

ВИКОНАННЯ — активний стан процесу, під час якого процес володіє всіма
необхідними ресурсами і безпосередньо виконується процесором;

ОЧІКУВАННЯ — пасивний стан процесу, процес заблокований, він не може
виконуватися по своїх внутрішніх причинах, він чекає виконання деякої
події, наприклад, завершення операції в/в, одержання повідомлення від
іншого процесу, звільнення якого-небудь необхідного йому ресурсу;

ГОТОВНІСТЬ — також пасивний стан процесу, але в цьому випадку процес
заблокований у зв’язку з зовнішніми стосовно нього обставинами: процес
має всі необхідні для нього ресурси, він готовий виконуватися, однак
процесор зайнятий виконанням іншого процесу.

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

У стані ВИКОНАННЯ в однопроцесорній системі може знаходитися тільки один
процес, а в кожному зі станів ОЧІКУВАННЯ і ГОТОВНІСТЬ — кілька процесів,
ці процеси утворять черги відповідно очікуючих і готових процесів.
Життєвий цикл процесу починається зі стану ГОТОВНІСТЬ, коли процес
готовий до виконання і чекає своєї черги. При активізації процес
переходить у стан ВИКОНАННЯ і знаходиться в ньому доти, доки або він сам
звільнить процесор, перейшовши в стан ОЧІКУВАННЯ якої-небудь події, або
буде насильно «витиснутий» із процесора, наприклад, унаслідок вичерпання
відведеного даному процесу кванта процесорного часу. В останньому
випадку процес повертається в стан ГОТОВНІСТЬ. У цей же стан процес
переходить зі стану ОЧІКУВАННЯ, після того, як очікуване подія
відбудеться.

Переривання

Помилка

планувальника

Завершення в/в Очікування в/в Вихід

Мал.6. Граф станів процесу в багатозадачному середовищі

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

• новий (процес тільки що створений);

• виконуваний (команди програми виконуються в ЦП);

• очікуваний (процес чекає завершення деякого випадку, найчастіші
операції в/в);

• готовий (процес чекає звільнення ЦП);

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

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

1.5. Контекст і дескриптор процесу

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

Крім цього, ОС для реалізації планування процесів потрібна додаткова
інформація: ідентифікатор процесу, стан процесу, дані про ступінь
привілейованості процесу, місце перебування кодового сегмента й інша
інформація. У деяких ОС (наприклад, в ОС UNIX) інформацію такого роду,
використовувану ОС для планування процесів, називають дескриптором
процесу. Дескриптор процесу в порівнянні з контекстом містить більш
оперативну інформацію, що повинна бути легко доступна підсистемі
планування процесів. Контекст процесу містить менш актуальну інформацію
і використовується ОС тільки після того, як прийняте рішення про
поновлення перерваного процесу.

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

Програмний код тільки тоді почне виконуватися, коли для нього ОС буде
створений процес. Створити процес — це значить:

створити інформаційні структури, що описують даний процес, тобто його
дескриптор і контекст;

включити дескриптор нового процесу в чергу готових процесів;

завантажити кодовий сегмент процесу в ОП чи в область свопінгу.

2. Планування процесів.

Розподіл процесів між ресурсами називається плануванням процесів.

Вхідна черга розміщується у зовнішній пам’яті. У вхідній черзі процеси
очікують звільнення ресурсів – адресного простору основної пам’яті.
Готові до виконання процеси розміщуються в основній пам’яті і зв’язані
чергою готових прцесів. Процеси в цій черзі очікують звільнення ресурсу
процесорного часу. Процес в стані очікування завершення операції в/в
знаходиться в одній із черг до обладнання в/в. При проходженні через
комп’ютер процес мігрує між різними чергами під управлінням програми,
яка називається планувальник. ОС, яка забезпечує режим
мультипрограмування зазвичай включає два планувальники: довгостроковий і
короткостроковий. Наприклад в OS/360 довгостроковий планувальник
називається планувальником завдань, а короткостроковий – супервізором
задач. На рівень довгострокового планування виноситься рідкісні системні
дії, які потребують більших затрат системних ресурсів. На рівень
короткострокового планування – часті і більш короткі процеси. На кожному
рівні існує свій об’єкт і власні засоби управління ним.

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

3. Алгоритми планування процесів

Планування процесів містить у собі рішення наступних задач:

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

вибір процесу на виконання з черги готових процесів;

переключення контекстів «старого» і «нового» процесів.

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

відбулася помилка,

процес завершився і залишив систему,

процес перейшов у стан ОЧІКУВАННЯ,

вичерпано квант процесорного часу, відведений даному процесу.

Процес, що вичерпав свій квант, переводиться в стан ГОТОВНІСТЬ і очікує,
коли йому буде наданий новий квант процесорного часу, а на виконання
відповідно до визначеного правила вибирається новий процес з черги
готових. Таким чином, жоден процес не займає процесор надовго, тому
квантування широке використовується в системах поділу часу. Граф станів
процесу, зображений на малюнку 6, відповідає алгоритму планування,
заснованому на квантуванні.

Кванти, виділювані процесам, можуть бути однаковими для всіх процесів чи
різними. Кванти, виділені одному процесу, можуть бути фіксованої
величини чи змінюватися в різні періоди життя процесу. Процеси, що не
цілком використовували виділений їм квант (наприклад, через відхід на
виконання операцій в/в), можуть одержати чи не одержати компенсацію у
виді привілеїв при наступному обслуговуванні. По різному може бути
організована черга готових процесів: циклічно, за правилом «перший
прийшов — перший пішов» (FIFO) чи за правилом «останній прийшов — перший
пішов» (LIFO).

Інша група алгоритмів використовує поняття «пріоритет» процесу.

Пріоритет — це число, що характеризує ступінь привілейованості процесу
при використанні ресурсів обчислювальної машини, зокрема, процесорного
часу: чим вище пріоритет, тим вище привілею.

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

Існує два різновиди пріоритетних алгоритмів: алгоритми, що
використовують відносні пріоритети, і алгоритми, що використовують
абсолютні пріоритети.

В обох випадках вибір процесу на виконання з черги готових
здійснюється однаково: вибирається процес, що має найвищий пріоритет. По
різному зважується проблема визначення моменту зміни активного процесу.
У системах з відносними пріоритетами активний процес виконується доти,
поки він сам не залишить процесор, перейшовши в стан ОЧІКУВАННЯ (чи ж
відбудеться помилка, чи процес завершиться). У системах з абсолютними
пріоритетами виконання активного процесу переривається ще при одній
умові: якщо в черзі готових процесів з’явився процес, пріоритет якого
вище пріоритету активного процесу. У цьому випадку перерваний процес
переходить у стан готовності. На малюнку 7 показані графи станів процесу
для алгоритмів з відносними (а) і абсолютними (б) пріоритетами.

Рис. 7. Графи станів процесів у системах

(а) з відносними пріоритетами; (б)з абсолютними пріоритетами.

3.1. Алгоритми планування, засновані на квантуванні.

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

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

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

Кванти, виділені одному потоку, можуть бути фіксованої величини, а
можуть і змінюватися в різні періоди життя потоку. Нехай, наприклад,
спочатку кожному потоку призначається досить великий квант, а величина
кожного наступного кванта зменшується до деякої заздалегідь заданої
величини. У такому випадку перевагу одержують короткі задачі, які
встигають виконуватися протягом першого кванта, а тривалі обчислення
будуть проводитися у фоновому режимі. Можна уявити собі алгоритм
планування, у якому кожен наступний квант, визначений конкретному
потоку, більше попереднього. Такий підхід дозволяє зменшити накладні
витрати на переключення задач у тому випадку, коли відразу декілька
задач виконують тривалі обчислення.

Потоки одержують для виконання квант часу, але деякі з них
використовують його не цілком, наприклад через необхідність виконати
ввід або вивід даних. У результаті виникає ситуація, коли потоки з
інтенсивними звертаннями до в/в використовують тільки невелику частину
виділеного їм процесорного часу. Алгоритм планування може виправити цю
«несправедливість». Як компенсацію за невикористані цілком кванти
потоки одержують привілеї при наступному обслуговуванні. Для цього
планувальник створює дві черги готових потоків Черга 1 утворена
потоками, що прийшли в стан готовності в результаті вичерпання кванта
часу, а черга 2 — потоками, яких завершилася операція в/в. При виборі
потоку для виконання насамперед проглядається друга черга, і тільки якщо
квант виділяється потоку з першої черги.

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

3. 2. Алгоритми планування, засновані на пріоритетах

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

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

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

У багатьох ОС передбачається можливість зміни пріоритетів в продовж
життя потоку. Зміна пріоритету можуть відбуватися по ініціатив самого
потоку, коли він звертається з відповідним викликом до OC, чи з
ініціативи користувача, коли він виконує відповідну команду. Крім того,
ОС сама може змінювати пріоритети потоків в залежності від ситуації, що
складається в системі. В останньому випадку приорітети називаються
динамічними на відміну від незмінних, фіксованих пріоритетів.

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

3.3. Витісняючі і невитісняючі алгоритми планування

Існує два основних типи процедур планування процесів — витісняючі
(preemptive) і невитісняючі (non-preemptive).

Non-preemptive multitasking — невитісняюча багатозадачність — це спосіб
планування процесів, при якому активний процес виконується доти, поки
він сам, за власною ініціативою, не віддасть керування планувальнику ОС
для того, щоб той вибрав з черги інший, готовий до виконання процес.

Preemptive multitasking — витісняюча багатозадачність — це такий
спосіб, при якому рішення про переключення процесора з виконання одного
процесу на виконання іншого процесу приймається планувальником ОС, а не
самою активною задачею.

Поняття preemptive і non-preemptive іноді ототожнюються з поняттями
пріоритетних і безприорітетних дисциплін, що зовсім невірно, а також з
поняттями абсолютних і відносних пріоритетів, що невірно. Невитісняюча і
витісняюча багатозадачність — це більш широкі поняття, чим типи
пріоритетності. Пріоритети задач можуть як використовуватися, так і не
використовуватися і при витісняючіх, і при невитисняючих способах
планування. Так, у випадку використання пріоритетів дисципліна відносних
пріоритетів може бути віднесена до класу систем із не витісняючої
багатозадачності, а дисципліна абсолютних пріоритетів — до класу систем
із витісняючої багатозадачності. А безпріорітетна дисципліна планування,
заснована на виділенні рівних квантів часу для всіх задач, відноситься
до витісняючих алгоритмів.

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

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

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

Однак розподіл функцій планувальника між системою і додатками не завжди
є недоліком, а за певних умов може бути і перевагою, тому що дає
можливість розроблювачу додатків самому проектувати алгоритм планування,
найбільш придатний для даного фіксованого набору задач. Тому що
розроблювач сам визначає в програмі момент часу віддачі керування, то
при цьому виключаються нераціональні переривання програм у «незручні»
для них моменти часу. Крім того, легко дозволяються проблеми спільного
використання даних: задача під час кожної ітерації використовує їхній
монопольно й упевнена, що протягом цього періоду ніхто іншої не змінить
ці дані. Істотною перевагою non-preemptive систем є більш висока
швидкість переключення з задачі на задачу.

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

Однак майже у всіх сучасних ОС, орієнтованих на високопродуктивне
виконання додатків (UNIX, Windows NT, OS/2, VAX/VMS), реалізована
витісняюча багатозадачність. Останнім часом дійшла черга і до ОС класу
настільних систем, наприклад, OS/2 Warp і Windows 95. Можливо в зв’язку
з цим що витісняє багатозадачність часто називають щирою
багатозадачністю.

Взаємодія процесів. Транспортери, сигнали, семафори, черги.

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

Буфер має фіксовані розміри, тому процеси можуть знаходитись в стані
очікування, коли:

буфер заповнений – очікує процес виробник;

буфер вільний – очікує процес користувач.

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

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

Черги. Ці механізми можуть забезпечувати передачу або використання
спільних даних без переміщення даних, а з передачею елемента черги, який
містить вказівник даних і об’єм масиву даних. Черга використовується
разом з механізмом загальної пам’яті. Елемент черги може бути зчитаний
із знищенням або без знищення цього елемента. Зчитування елемента черги
може здійснюватися у відповідності з механізмом черги або стека.
Зчитування елементів черги здійснює тільки створюючий черги процес.
Створюючий процес може виконувати слідуючі дії над чергою:

Створення черги;

Зчитування черги;

Перегляд черги;

Закриття черги.

Записуючий процес виконує слідуючи дії:

Відкрити чергу;

Записати в чергу;

Закрити чергу;

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

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

Установки семафора з метою сигналізації;

Очікування викликаючим потоком поки семафор не буде виключений;

Очікування потоку виключення одного із декількох семафорів.

Для роботи з семафорами вводять два значення, позначені P i V. Нехай
деяка S представляє собою семафор. Тоді дії P(S) i V(S) визначаються
наступним чином:

Дія V(S). Деяка S збільшується на одиницю єдиною дією. Збільшення та
запам”ятовування не можуть бути перерваними. До деякої S немає доступу
другим потокам під час виконання даної операції.

Дія P(S). Відбувається зменшення S на одиницю, якщо це можливо. Якщо
S=0, тобто неможливо зменшити S, залишаючись в області цілих невід”ємних
значень, то в цілому випадку потік викликаючий операцію Р, чекає поки це
зменшення стане дійсним.

Успішна перевірка і зменшення також являються нероздільною операцією.

В цілому випадку, якщо семафор S може приймати 0 і 1, він перетворюється
в блокуючу змінну, яку по цій причині часто називають подвійним
семафором.

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

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

Введемо два семафори: е – число порожніх буферів, f – число заповнених
буферів, при чому у вихідному стані e=N, а f=0. Тоді робота потоків з
загальним буферним пулом може бути описана наступним чином:

Використання семафорів для синхронізації потоків.

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

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

4.1. Методи і засоби синхронізації

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

У багатьох ОС ці засоби називаються засобами міжпроцесорного взаємодії —
Intel Process Communications (IРС), що відбиває історичну первинність
поняття «процес» стосовно поняття «потік». Звичайно до засобів ІРС
відносять не тільки засоби міжпроцесорної синхронізації, але і засоби
міжпроцесорного обміну даними.

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

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

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

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

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

4. 2. Проблема тупіків.

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

При розгляді проблеми тупіків доцільно поняття ресурсів систем
розділити на два класи — повторно використовувані (чи системні) ресурси
(типу RR чи SR) і споживані (ті що витрачаються) ресурси (типу CR).

Повторно використовуваний ресурс (SR) є кінцева безліч ідентичних
одиниць з наступними властивостями :

число одиниць ресурсу постійно;

кожна одиниця ресурсу, доступна чи розподілена одному і тільки одному
процесу.

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

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

Ресурс, що витрачається (CR) відрізняється від ресурсу типу SR у
декількох відносинах :

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

— процес „користувач” зменшує число одиниць ресурсу, спочатку
запрошуючи, а потім здобуваючи (споживаючи) одну чи більше одиниць.
Одиниці ресурсу, що придбані, у загальному випадку не повертаються
ресурсу, а споживаються (витрачаються).

Методи боротьби з тупіками.

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

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

Запобігання тупіків

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

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

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

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

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

Обхід тупіків.

Обхід тупіків можна представити як заборону входу в небезпечний стан.
Якщо жодна з 4-ох умов не виключено, то вхід в небезпечний стан можна
передбачити при наявності в систёмі інформації про послідовність
запитів, зв’язаних з кожним рівнобіжним процесом. Доведено, що якщо
обчислення знаходяться в будь-якому небезпечному стані, то існує
принаймні одна послідовність станів, що обходить небезпечне. Отже,
досить перевірити, чи не приведе виділення необхідного ресурсу відразу ж
до небезпечного стану. Якщо так, то запит відходить. Якщо ні, то можна
його виконати. Визначення того, чи є стан небезпечним чи ні, вимагає
аналізу послідовних запитів процесів.

4.3. Критична секція

Важливим поняттям синхронізації потоків є поняття «критичної секції»
програми.

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

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

Новий

Виконуючий

Готовий

Очікуваний

Завершений

Похожие записи