загрузка...
загрузка...
На головну

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

  1. F 4. Невротичні, пов'язані зі стресом і соматоформні розлади
  2. F50-F59 Поведінкові синдроми, пов'язані з фізіологічними порушеннями і фізичними факторами
  3. I. Поняття, основні принципи, цілі, завдання та напрями забезпечення безпеки дорожнього руху.
  4. I. Психологічні операції в сучасній війні.
  5. II. Про метод історико-критичної реконструкції поняття знака
  6. II. Від співака до поета. Виділення поняття поезії
  7. II.1. Категоріальний апарат за поняттями

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

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

Операції зручно об'єднати в три пари:

· Народження - завершення процесу

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

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

Далі буде розглянута ще одна операція, яка не має парної: зміна пріоритету процесу.

Операції створення та завершення процесу є одноразовими (тому що застосовуються не більше одного разу).

Всі інші операції, пов'язані зі зміною стану процесів, є багаторазовими.

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

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

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

Кожен з процесів-дітей може в свою чергу породжувати нові процеси. Формується при цьому генеалогічний ліс процесів.

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

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

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

При виникненні процесу-дитини йому потрібні певні ресурси. Є два підходи до їх виділення:

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

2. Процес-дитина може отримати свої ресурси безпосередньо від ОС. При цьому інформація про виділені ресурсах нового процесу заноситься в блок PCB.

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

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

· У другому випадку процес-дитина завантажується новою програмою з будь-якого файлу

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

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

Після того, як процес наділений змістом, в PCB дописується залишилася інформація, і стан нового процесу змінюється на готовність.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

На цьому діяльність заліза (hard ware) по обробці переривання завершується.

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

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

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

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

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

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

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

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

· Створення і завершення процесу

· Припинення і запуск процесу

· Блокування і розблокування процесу

· Зміна пріоритету процесу

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

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

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

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

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

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

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

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

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

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

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

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

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

Здійснюється короткострокове планування не рідше ніж один раз на 100 мілісекунд. Звідси і назва рівня планування: короткострокове.

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

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

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

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

До числа таких цілей можна віднести наступні:

? справедливість (не повинно бути ситуації, коли один процес постійно займає процесор)

? ефективність (ідеально процесор повинен бути зайнятий на 100%, реально - 40-90%)

? скорочення повного часу виконання

? скорочення часу очікування в стані готовність

? скорочення часу відгуку (в інтерактивних системах)

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

· Були передбачуваними (одне і те ж завдання має виконуватися приблизно за один і той же час)

· Були пов'язані з мінімальними накладними витратами (наприклад, при перемиканні контексту)

· Рівномірно завантажували ресурси в ВС (перевагу тим процесам, які буду займати маловикористовувані ресурси)

· Володіли масштабованість (при збільшенні «навантаження» не повинні різко втрачати працездатність)

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

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

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

До статичних параметрів ВС можна віднести граничні значення її ресурсів:

· Розмір ОЗУ

· Максимальна кількість пам'яті на диску для здійснення свопинга

· Кількість підключених пристроїв введення-виведення

Динамічні параметри системи відстежують кількість вільних ресурсів на даний момент.

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

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

? наскільки важливою є поставлена ??задача, тобто який пріоритет її виконання

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

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

? які ресурси ВС (ОЗУ, пристрої введення-виведення, спеціальні бібліотеки та системні програми і т.д.) і в якій кількості необхідні завданням.

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

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

Для середньострокового планування в якості таких характеристик може використовуватися наступна інформація:

? скільки часу пройшло з моменту вивантаження процесу на диск або його завантаження в ОЗУ

? скільки ОЗУ займає процес

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

Для короткострокового планування нам знадобиться ввести ще два динамічних параметра.

Діяльність будь-якого процесу можна представити як послідовність циклів використання процесора (CPU-burst) і очікування завершення операцій введення-виведення (I / O burst).

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

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

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

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

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

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

У випадках 1 та 2 процес, що знаходиться в стані виконання не може далі виконуватися і ОС змушена здійснювати планування, вибираючи новий процес для виконання.

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

Якщо в ОС планування здійснюється тільки у вимушених ситуаціях, кажуть, що має місце невитісняючі планування.

Якщо планувальник приймає і вимушені, і невимушені рішення, говорять про невитісняючі плануванні.

Термін «витісняють планування» виник тому, що що виконується процес може бути витіснений зі стану виконання іншим процесом.

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

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

Алгоритм планування процесів First-Come, First-Served (FCFS)

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

Існують алгоритми, які можна застосовувати на різних рівнях планування.

Далі ми будемо розглядати алгоритми застосовно до короткочасного планування First-Come, First-Served (FCFS).

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

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

Алгоритм легко реалізується, але має багато недоліків.

Розглянемо наступний приклад: є черга з процесів в стані готовність - р0, р1, р2. Нехай відомі часи їх чергових CPU burst. Для спрощення аналізу введемо наступне припущення:

1. Вся діяльність процесів обмежується використанням лише одного проміжку CPU-burst.

2. Процеси не здійснюють операції введення-виведення

3. Час перемикання контексту мало, і будемо їм нехтувати

Першим виконується процес р0, який отримує процесор на весь час свого CPU-burst, тобто на 13 одиниць часу. Цей процес перший в черзі. Після його закінчення в стан виконання наводиться процес р1 (він другий в черзі). Займає процесор на 4 одиниці часу, відповідно до його СPU-burst. Після його закінчення на виконання передається останній процес р2, який виконується за одну одиницю часу, відповідно до його СPU-burst.

Час очікування для процесів: р0 - 0 одиниць часу, р1 - 13 одиниць, р2 - 17 одиниць. Середній час очікування процесів дорівнює 10 одиниць.

Повний час виконання для процесу: р0 = 13 одиниць, р1 = 17 одиниць, р2 = 18 одиниць. Середнє повне час виконання всіх процесів дорівнює 16 одиниць.

Змінимо ситуацію в черзі, короткі процеси попереду: р2, р1, р0.

Час очікування для процесів: р0 - 5 одиниць часу, р1 - 1 одиниця, р2 - 0 одиниць. Середній час очікування процесів дорівнює 2 одиниць. Це в 5 разів менше !, ніж в попередньому випадку.

Повний час виконання для процесу: р0 = 18 одиниць, р1 = 5 одиниць, р2 = 1 одиниця. Середнє повне час виконання всіх процесів дорівнює 8 одиниць. Майже в два рази менше, ніж при першій розстановці процесів.

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

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

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

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

Зазначені недоліки усуваються в наступному алгоритмі: Round Robin (RR).

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

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

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

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

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

Розглянемо попередній приклад з порядком процесів p0, p1, p2 і величиною кванта часу рівної 4.

Виконання цих процесів ілюструється таблицею.

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

Стану процесів показані протягом відповідної одиниці часу, т. Е. Колонка з номером 1 відповідає проміжку часу від 0 до 1.

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

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

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

Тепер черга процесів в стані готовність складається з двох процесів, p2 і p0.

Процесор виділяється процесу p2.

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

Час очікування (кількість символів "Г" у відповідному рядку) для процесу:

p0 становить 5 одиниць часу,

p1 становить 4 одиниці часу,

p2 становить 8 одиниць часу.

Середній час очікування виходить рівним

(5 + 4 + 8) / 3 = 5,6 (6) одиниці часу.

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

p0 становить 18 одиниць часу,

p1 становить 8 одиниць часу,

p2 становить 9 одиниць часу.

Середнє повне час виконання виявляється рівним

(18 + 8 + 9) / 3 = 11,6 (12) одиниць часу.

Якщо аналогічним чином розрахувати показники для зворотного порядку процесів - P2, p1, p0, то побачимо

що середній час очікування і середнє повне час виконання не відрізняються від відповідних часів для алгоритму FCFS і складають 2 і 8 одиниць часу відповідно.

На продуктивність алгоритму RR сильно впливає величина кванта часу.

Розглянемо той же самий приклад з порядком процесів p0, p1, p2 для величини кванта часу, рівний 1 (див. Табл.).

Час очікування для процесу

p0 складе 5 одиниць часу,

p1 складе теж 5 одиниць,

p2 складе 2 одиниці.

Середній час очікування виходить рівним

(5 + 5 + 2) / 3 = 4 одиницям часу.

Середнє повне час виконання складе

18 + 9 + 3) / 3 = 10 одиниць часу.

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

при дуже малих величинах створюється ілюзія того, що кожен з n процесів працює на власному віртуальному процесорі з продуктивністю ~ 1 / n від продуктивності реального процесора

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

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

Алгоритм планування процесів Shortest-Job-First (невитісняючі)

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

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

Описаний алгоритм отримав назву "найкоротша робота першої" або Shortest Job First (SJF).

SJF-алгоритм короткострокового планування може бути як витісняє, так і невитісняючі.

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

Розглянемо приклад роботи невитісняючі алгоритму SJF. Нехай в стані готовність знаходяться чотири процесу, p0, p1, p2 і p3, для яких відомі часи їх чергових CPU burst. Ці часи наведені в таблиці.

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

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

Як ми бачимо, середній час очікування для алгоритму SJF становить

(4 + 1 + 9 + 0) / 4 = 3,5 одиниці часу.

Для алгоритму FCFS при порядку процесів p0, p1, p2, p3 середній час очікування буде дорівнювати

(0 + 5 + 8 + 15) / 4 = 7 одиницям часу,

т. е. буде в два рази більше, ніж для алгоритму SJF.

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

Основну складність при реалізації алгоритму SJF представляє неможливість точного знання тривалості чергового CPU burst для виконуються процесів.

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

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

Якщо ж він вкаже меншу кількість часу, завдання може не дорахуватися до кінця.

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

При короткостроковому плануванні ми можемо робити тільки прогноз тривалості наступного CPU burst, виходячи з передісторії роботи процесу

Алгоритм планування процесів Shortest-Job-First (витісняє)

При витісняє SJF-плануванні враховується поява нових процесів в черзі готових до виконання (з числа знову народилися або розблокованих) під час роботи обраного процесу.

Якщо CPU burst нового процесу менше, ніж залишок CPU burst у що виконується, то що виконується процес витісняється новим.

Для розгляду прикладу витісняє SJF планування ми візьмемо ряд процесів p0, p1, p2 та p3 з різними часом CPU burst і різними моментами їх появи в черзі процесів, готових до виконання (див. Табл)

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

Після 2 одиниць часу в систему надходить процес p1. Час його CPU burst менше, ніж залишок CPU burst у процесу p3, який витісняється зі стану виконання і переводиться в стан готовність.

Після ще 2 одиниць часу процес p1 завершується, і для виконання знову вибирається процес p3.

У момент часу t = 6 в черзі процесів, готових до виконання, з'являється процес p2, але оскільки йому для роботи потрібно 7 одиниць часу, а процесу p3 залишилося працювати всього 1 одиницю часу, то процес p3 залишається в стані виконання.

Після його завершення в момент часу t = 7 в черзі знаходяться процеси p0 і p2, з яких вибирається процес p0. Нарешті, останнім отримає можливість виконуватися процес p2.

Пріоритетне планування процесів (невитісняючі і витісняє варіант)

пріоритетне планування

Алгоритм SJF є окреме питання пріоритетного планування.

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

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

Для алгоритму SJF як такого пріоритету виступає оцінка тривалості наступного CPU burst. Чим менше значення цієї оцінки, тим вищий пріоритет має процес

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

До внутрішніх параметрів належать різні кількісні та якісні характеристики процесу такі як: обмеження за часом використання процесора, вимоги до розміру пам'яті, число відкритих файлів і використовуваних пристроїв введення-виведення, ставлення середніх тривалостей I / O burst до CPU burst і т. Д.

Алгоритм SJF використовує внутрішні параметри.

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

Високий зовнішній пріоритет може бути присвоєно завданню лектора або того, хто заплатив $ 100 за роботу протягом однієї години.

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

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

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

Давайте розглянемо приклади використання різних режимів пріоритетного планування

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

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

Щоб уникнути плутанини, у всіх наших прикладах ми будемо припускати, що більше значення відповідає меншому пріоритету, т. Е. Найбільш пріоритетним в нашому прикладі є процес p3, а найменш пріоритетним - процес p0.

Як поводитимуться процеси при використанні невитісняючі пріоритетного планування?

Першим для виконання в момент часу t = 0 вибирається процес p3, як володіє найвищим пріоритетом.

Після його завершення в момент часу t = 5 в черзі процесів, готових до виконання, виявляться два процеси p0 і p1.

Більший пріоритет з них у процесу p1, він і почне виконуватися (див. Табл.). Потім в момент часу t = 8 для виконання буде обраний процес p2, і лише потім - процес p0.

Іншим буде надання процесора процесам в разі витісняє пріоритетного планування (див. Табл.).

Першим, як і в попередньому випадку, почне виконуватися процес p3, а по його закінченні - процес p1. Однак в момент часу t = 6 він буде витіснений процесом p2 і продовжить своє виконання тільки в момент часу t = 13. Останнім, як і раніше, буде виконуватися процес p0.

У розглянутому вище прикладі пріоритети процесів з плином часу не змінювалися. Такі пріоритети прийнято називати статичними.

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

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

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

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

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

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

Прикладами алгоритмів з динамічними пріоритетами є алгоритм SJF і алгоритм гарантованого планування.

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

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

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

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

Або обчислювальну систему доводиться вимикати, і вони губляться (при зупинці IBM 7094 в Массачусетському технологічному інституті в 1973 році були знайдені процеси, запущені в 1967 році і жодного разу з тих пір не виконувалися).

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

Нехай спочатку процесам присвоюються пріоритети від 128 до 255. Кожен раз після закінчення певного проміжку часу значення пріоритетів готових процесів зменшуються на 1.

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

Багаторівневі черги в плануванні процесів (без зворотного зв'язку і зі зворотним зв'язком)

(Multilevel Queue)

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

Цим чергам приписуються фіксовані пріоритети.

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

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

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

Усередині цих черг для планування можуть застосовуватися найрізноманітніші алгоритми.

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

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

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

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

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

Для простоти розглянемо ситуацію, коли процеси в стані готовність організовані в 4 черги, як на малюнку

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

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

Процеси в черзі 1 не можуть виконуватися, якщо в черзі 0 є хоча б один процес.

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

І нарешті, процес в черзі 3 може отримати процесор в своє розпорядження тільки тоді, коли черги 0, 1 і 2 порожні.

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

Планування процесів всередині черг 0-2 здійснюється з використанням алгоритму RR, планування процесів в черзі 3 ґрунтується на алгоритмі FCFS.

Народжений процес надходить в чергу 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.

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

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

Вони найбільш важкі в реалізації, але в той же час володіють найбільшою гнучкістю.

Зрозуміло, що існує багато інших різновидів такого способу планування, крім варіанту, приведеного вище. Для повного опису їх конкретного втілення необхідно вказати:

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

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

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

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

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

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

 




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

загрузка...
© um.co.ua - учбові матеріали та реферати