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


Операції над процесами і пов'язані з ними поняття

Набір операцій

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

· створення процесу – завершення процесу;

· припинення процесу (переклад із стану виконання в стан готовність) – запуск процесу (переклад із стану готовність в стан виконання);

· блокування процесу (переклад із стану виконання в стан очікування) – розблокування процесу (переклад із стану очікування в стан готовність).

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

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

Process Control Block і контекст процесу

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

· стан, в якому знаходиться процес;

· програмний лічильник процесу або, іншими словами, адреса команди, яка має бути виконана для нього наступною;

· вміст регістрів процесора;

· дані, необхідні для планування використання процесора і управління пам'яттю (пріоритет процесу, розмір і розташування адресного простору і т. д.);

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

· відомості про пристрої введення-виводу, пов'язані з процесом (наприклад, які пристрої закріплені за процесом, таблицю відкритихфайлів).

Її склад і будова залежать, звичайно, від конкретної операційної системи. У багатьох операційних системах інформація, що характеризує процес, зберігається не в одній, а в декількох зв'язаних структурах даних. Ці структури можуть мати різні найменування, містити додаткову інформацію або, навпаки, лише частину описаної інформації. Для нас це не має значення. Для нас важливо лише те, що для будь-якого процесу, що знаходиться в обчислювальній системі, вся інформація, необхідна для здійснення операцій над ним, доступна операційній системі. Для простоти викладу вважатимемо, що вона зберігається в одній структурі даних. Ми називатимемо її PCB (Process Control Block) або блоком управління процесом. Блок управління процесом є моделлю процесу для операційної системи. Будь-яка операція, вироблювана операційною системою над процесом, викликає певні зміни в PCB. В рамках прийнятої моделі станів процесів вміст PCB між операціями залишається постійним.

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

Одноразові операції

Складний життєвий шлях процесу в комп'ютері починається з його народження. Будь-яка операційна система, що підтримує концепцію процесів, повинна володіти засобами для їх створення. У дуже простих системах (наприклад, в системах, спроектованих для роботи тільки одного конкретного застосування) всі процеси можуть бути породжені на етапі старту системи. Складніші операційні системи створюють процеси динамічно, в міру необхідності. Ініціатором народження нового процесу після старту операційної системи може виступити або процес користувача, що зробив спеціальний системний виклик, або сама операційна система, тобто, зрештою, теж деякий процес. Процес, що ініціював створення нового процесу, прийнято називати процесом-батьком (parent process), а знов створений процес – процесом-дитиною (child process). Процеси-діти можуть у свою чергу породжувати нових дітей і т. д., утворюючи, в загальному випадку, усередині системи набір генеалогічних дерев процесів – генеалогічний ліс. Приклад генеалогічного лісу зображений на малюнку 2.4. Слід зазначити, що всі призначені для користувача процеси разом з деякими процесами операційної системи належать одному і тому ж дереву лісу. У ряді обчислювальних систем ліс взагалі вироджується в одне таке дерево.

 


Рис. 2.4. Спрощений генеалогічний ліс процесів. Стрілка означає відношення батько–нащадок

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

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

Після наділу процесу-дитини ресурсами необхідно занести в його адресний простір програмний код, значення даних, встановити програмний лічильник. Тут також можливі два рішення. У першому випадку процес-дитина стає дублікатом процесу-батька по регістровому і призначеному для користувача контекстах, при цьому повинен існувати спосіб визначення, хто для кого з процесів-двійників є батьком. У другому випадку процес-дитина завантажується новою програмою з якого-небудь файлу. Операційна система Unix вирішує породження процесу тільки першим способом; для запуску нової програми необхідно спочатку створити копію процесу-батька, а потім процес-дитина повинен замінити свій призначений для користувача контекст за допомогою спеціального системного виклику. Операційна система VAX/VMS допускає тільки друге рішення. У Windows NT можливі обидва варіанти (у різних API).

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

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

Ми детально не зупинятимемося на причинах, які можуть привести до завершення життєвого циклу процесу. Після того, як процес завершив свою роботу, операційна система переводить його в стан закінчив виконання і звільняє всі асоційовані з ним ресурси, роблячи відповідні записи в блоці управління процесом. При цьому сам PCB не знищується, а залишається в системі ще якийсь час. Це пов'язано з тим, що процес-батько після завершення процесу-дитини може запитати операційну систему про причину "смерті" породженого ним процесу і/або статистичну інформацію про його роботу. Подібна інформація зберігається в PCB відпрацьованого процесу до запиту процесу-батька або до кінця його діяльності, після чого всі сліди процесу, що завершився, остаточно зникають з системи. У операційній системі Unix процеси, що знаходяться в змозі закінчив виконання, прийнято називати процесами-зомбі.

Слід відмітити, що у ряді операційних систем (наприклад, в VAX/VMS) загибель процесу-батька приводить до завершення роботи всіх його "дітей". У інших операційних системах (наприклад, в Unix) процеси-діти продовжують своє існування і після закінчення роботи процесу-батька. При цьому виникає необхідність зміни інформації в PCB процесів-дітей про породжувач їх процесі для того, щоб генеалогічний ліс процесів залишався цілісним. Розглянемо наступний приклад. Хай процес з номером 2515 був породжений процесом з номером 2001 і після завершення його роботи залишається в обчислювальній системі необмежено довго. Тоді не виключено, що номер 2001 буде використаний операційною системою повторно для зовсім іншого процесу. Якщо не змінити інформацію про процес-батько для процесу 2515, то генеалогічний ліс процесів виявиться некоректним – процес 2515 вважатиме за свого батька новий процес 2001, а процес 2001 відхрещуватиметься від нежданого нащадка. Як правило, що "усиротіли" процеси "усиновляються" одним з системних процесів, який породжується при старті операційної системи і функціонує весь час, поки вона працює.

Багаторазові операції

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

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

Запуск процесу. З числа процесів, що знаходяться в змозі готовність, операційна система вибирає один процес для подальшого виконання. Критерії і алгоритми такого вибору будуть детально розглянуті в лекції 3 – "Планування процесів". Для вибраного процесу операційна система забезпечує наявність в оперативній пам'яті інформації, необхідної для його подальшого виконання. То, як вона це робить, буде в деталях описано в лекціях 8-10. Далі стан процесу змінюється на виконання, відновлюються значення регістрів для даного процесу і управління передається команді, на яку указує лічильник команд процесу. Всі дані, необхідні для відновлення контексту, витягуються з PCB процесу, над яким здійснюється операція.

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

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

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

Перемикання контексту

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

Давайте для прикладу спрощено розглянемо, як в реальності може протікати операція розблокування процесу, чекаючого введення-виводу (див. мал. 2.5). При виконання процесором деякого процесу (на малюнку – процес 1) виникає переривання від пристрою введення-виводу, що сигналізує про закінчення операцій на пристрої. Над процесом, що виконується, проводиться операція припинення. Далі операційна система розблоковує процес, що ініціював запит на уведення-виведення (на малюнку – процес 2) і здійснює запуск припиненого або нового процесу, вибраного при виконанні планування (на малюнку був вибраний розблокований процес). Як ми бачимо, в результаті обробки інформації про закінчення операції введення-виводу можлива зміна процесу, що знаходиться в змозі виконання.

 


Рис. 2.5. Виконання операції розблокування процесу. Використання терміну "код користувача" не обмежує рисунок тільки процесами користувача

Для коректного перемикання процесора з одного процесу на іншій необхідно зберегти контекст процесу, що виконувався, і відновити контекст процесу, на який буде перемкнутий процесор. Така процедура збереження/відновлення працездатності процесів називається перемиканням контексту. Час, витрачений на перемикання контексту, не використовується обчислювальною системою для здійснення корисної роботи і є накладними витратами, що знижують продуктивність системи. Воно міняється від машини до машини і зазвичай коливається в діапазоні від 1 до 1000 мікросекунд. Істотно скоротити накладні витрати в сучасних операційних системах дозволяє розширена модель процесів, що включає поняття threads of execution (нитки виконання або просто нитки).

Висновок

Поняття процесу характеризує деяку сукупність набору команд, що виконуються, асоціюються з ним ресурсів і теперішнього моменту його виконання, що знаходиться під управлінням операційної системи. У будь-який момент процес повністю описується своїм контекстом, що складається з регістрової, системної і призначеної для користувача частин. У операційній системі процеси представляються певною структурою даних – PCB, що відображає зміст регістрового і системного контекстів. Процеси можуть знаходитися в п'яти основних станах: народження, готовність, виконання, очікування, закінчив виконання. Із стану в стан процес переводиться операційною системою в результаті виконання над ним операцій. Операційна система може виконувати над процесами наступні операції: створення процесу, завершення процесу, припинення процесу, запуск процесу, блокування процесу, розблокування процесу, зміна пріоритету процесу. Між операціями вміст PCB не змінюється. Діяльність мультипрограмної операційної системи складається з ланцюжків перерахованих операцій, що виконуються над різними процесами, і супроводиться процедурами збереження/відновлення працездатності процесів, тобто перемиканням контексту. Перемикання контексту не має відношення до корисної роботи, що виконується процесами, і час, витрачений на нього, скорочує корисний час роботи процесора.

 

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

Рівні планування процесів. Критерії планування і вимоги до алгоритмів

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

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

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

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

Критерії планування і вимоги до алгоритмів

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

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

· Ефективність – постаратися зайняти процесор на все 100% робочого часу, не дозволяючи йому простоювати в очікуванні процесів, готових до виконання. У реальних обчислювальних системах завантаження процесора коливається від 40 до 90%.

· Скорочення повного часу виконання (turnaround time) – забезпечити мінімальний час між стартом процесу або постановкою завдання в чергу для завантаження і його завершенням.

· Скорочення часу очікування (waiting time) – скоротити час, який проводять процеси в змозі готовність і завдання в черзі для завантаження.

· Скорочення часу відгуку (response time) – мінімізувати час, який потрібний процесу в інтерактивних системах для відповіді на запит користувача.

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

· Були передбаченими. Одне і те ж завдання повинне виконуватися приблизно за один і той же час. Застосування алгоритму планування не повинне приводити, наприклад, до витягання кореня квадратного з 4 за соті долі секунди при одному запуску і за декілька діб – при другому запуску.

· Були пов'язані з мінімальними накладними витратами. Якщо на кожних 100 мілісекунд, виділені процесу для використання процесора, доводитиметься 200 мілісекунд на визначення того, який саме процес отримає процесор в своє розпорядження, і на перемикання контексту, то такий алгоритм, очевидно, застосовувати не варто.

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

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

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

Параметри планування

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

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

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

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

· Яким користувачем запущений процес або сформовано завдання.

· Наскільки важливим є поставлене завдання, тобто який пріоритет її виконання.

· Скільки процесорного часу запитано користувачем для вирішення завдання.

· Яке співвідношення процесорного часу і часу, необхідного для здійснення операцій введення-виводу.

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

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

· скільки часу пройшло з моменту вивантаження процесу на диск або його завантаження в оперативну пам'ять;

· скільки оперативної пам'яті займає процес;

· скільки процесорного часу вже надано процесу.

 


Рис. 3.1. Фрагмент діяльності процесу з виділенням проміжків безперервного використання процесора і очікування введення-виводу

Для короткострокового планування нам знадобиться ввести ще два динамічні параметри. Діяльність будь-якого процесу можна представити як послідовність циклів використання процесора і очікування завершення операцій введення-виводу. Проміжок часу безперервного використання процесора носить назва CPU burst, а проміжок часу безперервного очікування введення-виводу – I/O burst. На мал. 3.1 показаний фрагмент діяльності деякого процесу на псевдомові програмування з виділенням вказаних проміжків. Скорочено ми використовуватимемо терміни CPU burst і I/O burst без перекладу. Значення тривалості останніх і чергових CPU burst і I/O burst є важливими динамічними параметрами процесу.

Витісняюче і невитісняюче планування

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

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

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

3. Коли процес переводиться із стану виконання в стан готовність (наприклад, після переривання від таймера).

4. Коли процес переводиться із стану очікування в стан готовність (завершилася операція введення-виводу або відбулася інша подія). Детально процедура такого перекладу розглядалася в лекції 2 (розділ "Перемикання контексту"), де ми показали, чому при цьому виникає можливість зміни процесу, що знаходиться в змозі виконання.

У випадках 1 і 2 процес, що знаходився в змозі виконання, не може далі виконуватися, і операційна система вимушена здійснювати планування вибираючи новий процес для виконання. У випадках 3 і 4 планування може як проводитися, так і не проводитися, планувальник не вимушений обов'язково ухвалювати рішення про вибір процесу для виконання, процес, що знаходився в змозі виконання може просто продовжити свою роботу. Якщо в операційній системі планування здійснюється тільки у вимушених ситуаціях, говорять, що має місце невитісняюче (nonpreemptive) планування. Якщо планувальник приймає і вимушені, і невимушені рішення, говорять про витісняюче (preemptive) планування. Термін "витісняюче планування" виник тому, що процес, що виконується, окрім своєї волі може бути витиснений із стану виконання іншим процесом.

Невитісняюче планування використовується, наприклад, в MS Windows 3.1 і ОС Apple Macintosh. При такому режимі планування процес займає стільки процесорного часу, скільки йому необхідно. При цьому перемикання процесів виникає тільки процесу, що за бажання самого виконується, передати управління (для очікування завершення операції введення-виводу або після закінчення роботи). Цей метод планування відносно просто реалізовується і достатньо ефективний, оскільки дозволяє виділити велику частину процесорного часу для роботи самих процесів і до мінімуму скоротити витрати на перемикання контексту. Проте при невитісняючому плануванні виникає проблема можливості повного захоплення процесора одним процесом, який унаслідок яких-небудь причин (наприклад, із-за помилки в програмі) зациклюється і не може передати управління іншому процесу. У такій ситуації рятує тільки перезавантаження всієї обчислювальної системи.

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

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

Простим алгоритмом планування є алгоритм, який прийнято позначати абревіатурою FCFS по перших буквах його англійської назви, – First-Come, First-Served (першим прийшов, першим обслужений). Уявимо собі, що процеси, що знаходяться в змозі готовність, збудовані в чергу. Коли процес переходить в стан готовність, він, а точніше, посилання на його PCB поміщається в кінець цієї черги. Вибір нового процесу для виконання здійснюється з початку черги з видаленням звідти посилання на його PCB. Черга подібного типу має в програмуванні спеціальне найменування – FIFO1), скорочення від First In, First Out (першим увійшов, першим вийшов).

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

Таблиця 3.1.
Процес p0 p1 p2
Тривалість чергового CPU burst

Перевагою алгоритму FCFS є легкість його реалізації, але в той же час він має і багато недоліків. Розглянемо наступний приклад. Хай в змозі готовність знаходяться три процеси p0, p1 і p2, для яких відомі часи їх чергових CPU burst. Ці часи приведені в таблиця 3.1 в деяких умовних одиницях. Для простоти вважатимемо, що вся діяльність процесів обмежується використанням тільки одного проміжку CPU burst, що процеси не здійснюють операцій введення-виводу і що час перемикання контексту так мало, що їм можна нехтувати.

Якщо процеси розташовані в черзі процесів, готових до виконання, в порядку p0, p1, p2, то картина їх виконання виглядає так, як показано на мал. 3.2. Першим для виконання вибирається процес p0, який отримує процесор на весь час свого CPU burst, тобто на 13 одиниць часу. Після його закінчення в стан виконання переводиться процес p1, він займає процесор на 4 одиниці часу. І, нарешті, можливість працювати отримує процес p2. Час очікування для процесу p0 складає 0 одиниць часу, для процесу p1 – 13 одиниць, для процесу p2 – 13 + 4 = 17 одиниць. Таким чином, середній час очікування в цьому випадку – (0 + 13 + 17) /3 = 10 одиниць часу. Повний час виконання для процесу p0 складає 13 одиниць часу, для процесу p1 – 13 + 4 = 17 одиниць, для процесу p2 – 13 + 4 + 1 = 18 одиниць. Середній повний час виконання виявляється рівним (13 + 17 + 18) /3 = 16 одиницям часу.

 

 


Рис. 3.2. Виконання процесів при порядку p0,p1,p2

Якщо ті ж самі процеси розташовані в порядку p2, p1, p0, то картина їх виконання відповідатиме мал. 3.3. Час очікування для процесу p0 дорівнює 5 одиницям часу, для процесу p1 – 1 одиниці, для процесу p2 – 0 одиниць. Середній час очікування складе (5 + 1 + 0) /3 = 2 одиниці часу. Це в 5 (!) разів менше, ніж у попередньому випадку. Повний час виконання для процесу p0 виходить рівним 18 одиницям часу, для процесу p1 – 5 одиницям, для процесу p2 – 1 одиниці. Середній повний час виконання складає (18 + 5 + 1) /3 = 8 одиниць часу, що майже в 2 рази менше, ніж при першій розстановці процесів.

 


Рис. 3.3. Виконання процесів при порядку p2, p1, p0

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

Алгоритм планування Round Robin (RR)

Модифікацією алгоритму FCFS є алгоритм, що отримав назву Round Robin (Round Robin – це вид дитячої каруселі в США) або скорочено RR. По суті справи, це той же самий алгоритм, тільки реалізований в режимі витісняючого планування. Можна уявити собі всю безліч готових процесів організованою циклічно – процеси сидять на каруселі. Карусель обертається так, що кожен процес знаходиться біля процесора невеликий фіксований квант часу, звичайні 10 – 100 мілісекунд (див. мал. 3.4). Поки процес знаходиться поряд з процесором, він отримує процесор в своє розпорядження і може виконуватися.


Рис. 3.4. Процеси на каруселі

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

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

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

Розглянемо попередній приклад з порядком процесів p0, p1, p2 і величиною кванта часу рівної 4. Виконання цих процесів ілюструється таблиця 3.2. Позначення "В" використовується в ній для процесу, що знаходиться в змозі виконання, позначення "Г" – для процесів в змозі готовність, порожні осередки відповідають процесам, що завершилися. С

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