Стани процесу

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

Рис. 1.

При виконанні програм на процесорі обчислювальної системи визначають наступні стани

процесора:

 Passive – процес завантаження в пам’ять, але його виконання ще неініційоване.

 Ready – процес готовий до виконання (очікує ресурс центрального процесора).

 Run – процес виконується на центральному процесорі.

 Wait – процес очікує звільнення необхідного ресурсу.

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

 з обмеженням по вводу/виводу (в таких системах найбільший час очікування

витрачається процесом при зверненні до підсистем вводу/виводу);

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

Будь – який процес може знаходитись в одному з перерахованих станів один раз в певний

момент часу.

Умови зміни станів процесу (з Рис.1.)

2 – активізація процесу програмою – диспетчером або ОС;

3 – диспетчеризація процес;

4 – виникнення переривань;

5 – запитом процесом певної системної функції в складі ОС (можливе створення певного

процесу);

6 – запитом процесом певної системної функції (вводу/виводу);

7 – завершення виконання системної функції;

8 – зупинка виконання процесу;

1 – завершення виконання процесу.

17 Властивості процесу. 18 Класифікація процесів.

Процеси

По приналежності до ЦП

1) внутрішні

2) зовнішні

До ОС

1) системні

2) користувацькі

По генеологічному типу

1) породжуючі

2) породжені

По результативності

1) рідні

2) еквівалентні

3) поточні

4) рівні

По динамічному типу

1) послідовні

2) паралельні

3) комбіновані

По зв’язності

1) ізольовані

2) взаємодіючі

3) конкуруючі

4) інформаційно -незалежні

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

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

Породжуючі – це процеси, які можуть породжувати існування інших процесів.

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

Траса – це тривалість і порядок перебування процесу в допустимих станах на інтервалі

існування.

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

Зовнішні процеси – це процеси, розвиток яких проходить під контролем не ЦП, а інших.

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

19 Визначення та властивості ресурсів.

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

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

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

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

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

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

20 Класифікація ресурсів.

Ресурси поділяються на такі категорії:

1) по формі існування:

 фізичні – ресурс, який реально існує і володіє всіма притаманними йому фізичнимихарактеристиками при його розподілі між користувачами,

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

2) по можливості розширення властивостей:

 еластичний – це фізичний ресурс, який допускає віртуалізацію, а також відтворення ірозширення своїх властивостей,

 нееластичний (жорсткий) – це ресурс, який по своїх внутрішніх властивостях недопускає віртуалізації;

3) по ступеню активності:

 активний ресурс – при використанні його він здатний виконувати дії по відношеннюдо інших ресурсів або процесів,

 пасивний ресурс – це ресурси які не володіють активними ресурсами;

4) по часу існування:

 постійний – це ресурс по відношенню до певного процесу, якщо він існує допородження певного процесу і доступний для користувача під час виконання цьогопроцесу,

 тимчасовий – даний ресурс може з’являтися і може знищуватися в системідинамічно під час існування певного процесу (наприклад: буфер обміну);

5) по ступеню важливості:

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

 другорядний – це ресурс, який допускає певне альтернативне виділення іншихресурсів при умові власної недоступності;

6) по структурі:

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

 складний – характеризується деякою структурою, складається з деяких частин і неможе розглядатися як єдине ціле;

7) по характеру використання:

 паралельно використовувані,

 послідовно використовувані;

8) по формі реалізації:

 м’який,

 твердий;

9) по функціональній надлишковості:

 дорогий – може бути використаний для здійснення декількох функцій,

 дешевий – для здійснення однієї функції;

10) по відновлюваності:

 відновлювальні – можуть відновлюватись,

 спожиті – не можуть відновлюватись.

21 Поняття та стратегії планування

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

Стратегії можуть бути наступними:

1) закінчувати обчислення в тому самому порядку, в якому вони були розпочаті;

2) перевагу надавати біль коротким процесам;

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

Розрізняють два типи планування:

 короткострокове планування називається диспетчеризацією;

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

22 Функції та способи реалізації планувальників.

У загальному випадку планувальник здійснює наступні функції:

1)запис копії процесу в пам’ять обчислювальної системи;

2)аналіз атрибутів при виконанні обчислювального процесу та формуваннянабору робочих атрибутів в залежності від характеристик обчислювальноїсистеми;

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

4)періодичний перегляд черги процесів, запис або знищення процесів в черзі увідповідності з часом функціонування процесів.

Структура планувальника.

Системний процес який здійснює планування може бути реалізований двома способами:

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

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

24 Класифікація дисциплін диспетчеризації.

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

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

25 Дисципліни диспетчеризації FIFO, LIFO, FCFS.

Розглянемо деякі дисципліни диспетчеризації:

1) Дисципліна FIFO (first input first output) – є реалізацією безпріоритетної черги. Якщов черзі звільняється елемент і він не останній, то всі після нього посуваютьсявперед і в останній вільний елемент черги записується ім’я нового процесу.Першим з черги вибирається елемент, який стоїть на початку черги.

2) Дисципліна LIFO (last input first output) – першим з черги вибирається елемент, якийприйшов останнім.

3) Дисципліна FCFS (first come first server) – є подібна до FIFO. Ця дисциплінавраховує перебування процесів в станах блокування, наприклад при операціяхвводу/виводу. Ті, які були заблоковані в процесі роботи після переходу в станготовності поступають в чергу готовності перед новими задачами, які ще необслуговувались. При такій дисципліні організовуються дві черги: черга готових дообслуговування процесів і черга нових процесів.

26 Дисципліни диспетчеризації SJN, SRT, RR.

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

1) Дисципліна SJN (short jump next) – згідно з цією дисципліною ОС вимагає, щоб длякожного процесу була відома оцінка по необхідних обчислювальних ресурсах. Дляпостановки задачі в чергу диспетчер оцінює необхідний час виконання задачі іставить задачу перед довшою задачею. При цій дисципліні існує одна черга

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

2) Дисципліна SRT (short remain time) – розроблена з метою забезпечення більшякісного обслуговування коротких завдань. Виконує спочатку ті процеси, часзавершення виконання яких найменший.

3) Дисципліна RR (round robin) – кожна задача отримує порцію часу (квант часу). Післязакінчення цього кванту часу задача знімається з виконання на процесорі і вінпередається наступній задачі. Задача, яка була знята з черги записується в кінецьчерги задач, які готові до виконання. Величина кванту часу, як правило,

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

27Дисципліни диспетчеризації з витісненням та без витісненням.

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

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

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

28Способи забезпечення гарантованого обслуговування процесів.

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

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

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

завершення до певного моменту часу.

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

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

Гарантоване обслуговування може бути досягнуто трьома способами:

1) виділяти мінімальну частину процесорного часу деякому класу процесів, у випадку,

коли хоча б один з них готовий до виконання;

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

він готовий до виконання;

3) виділяти стільки часу певному процесу, щоб він міг виконати своє обчислення в

певний термін.

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

Існують такі критерії порівняння алгоритмів диспетчеризації:

1) використання (завантаження) ЦП – для більшості ПК середня завантаженістьпроцесора не перевищує 3%, однак в моменти складних обчислень завантаженістьпроцесора може досягати 100%. В системах, де ПК виконує багато роботи (сервер),завантаженість – 15-40%, може доходити до 100% при повному завантаженні;

2) пропускна здатність процесора – це кількість процесів, яка виконується процесоромза одиницю часу;

3) час обороту – інтервал часу від моменту появи процесу у вхідній черзі до моментузавершення процесу. Цей час обороту включає в себе час очікування у вхіднійчерзі, час очікування у черзі готовності, час готовності у чергах до периферійнихпристроїв, час виконання на процесорі та час вводу/виводу;

4) час очікування – це сумарний час знаходження процесу в черзі очікування готовихпроцесів;

5) час відповіді – це час від моменту поступлення процесу на вхідну чергу до моментупершого звернення процесу на ввід/вивід даних.

30 Вплив планування на продуктивність обчислювальної системи.

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

В загальному випадку використовують наступні методи підвищення продуктивності системи:

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

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

31 Використання динамічних пріоритетів при плануванні.

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

Операційна система може змінити пріоритет задачі в таких випадках:

1) збільшення пріоритету активної задачі. При завантаженні задачі на виконання їїпріоритет автоматично збільшується. Це знижує час реакції цієї активної задачі на дії користувачівв порівнянні з іншими фоновими задачами;

2) збільшення пріоритету операції вводу/виводу. Після завершення операціївводу/виводу задача отримує найвищий пріоритет в певному класі задач. Це дозволяє більшшвидко закінчити всі незавершені операції вводу/виводу;

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

32 Незалежні та взаємодіючі обчислювальні процеси

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

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

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

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

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

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

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

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

33 Види задач синхронізації паралельних процесів.

Задача “взаємного виключення”.

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

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

 в кожен момент часу тільки один процес може знаходитись в певній критичній

секції;

 ні один процес не може знаходитись в критичній секції в необмежений відрізок часу;

 жоден процес не повинен чекати входження в критичну секцію в нескінченний

проміжок часу;

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

Задача “виробник – споживач”.

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

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

 задача взаємного виключення повинна бути забезпечена по відношенню до спільноїобласті пам’яті;

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

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

Задача “читачів – письменників”.

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

Виділяють два паралельних процеси:

1) процеси “читачі” – вони зчитують одночасно інформацію зі спільного файлу, якщоце допускається при роботі з таким файлом;

2) процеси “письменники” – вони записують інформацію в цей спільний файл, приумові забезпечення задачі взаємного виключення як з процесами “читачами”, так з процесами“письменниками”. Це забезпечується двома шляхами:

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

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

Задача “синхронізації виконання гілок алгоритмів”.

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

34 Синхронізація за допомогою блокування пам'яті.

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

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

Приклад на мові Pascal

var key1, key2: boolean;

begin

key1:=false, key2:=false;

par begin

PR1: white true do

begin key1:=true

while key2 do begin … end {критична секція PR1}

key1:=false

end

and

PR2: white true do

begin key2:=true

while key1 do begin … end {критична секція PR2}

key2:=false

end

par end

При виконанні цього алгоритму можлива ситуація коли два процеси встановлять одночасносвої змінні key 1 і key 2 в true і ввійдуть у безкінечний цикл. Тому для вирішення цієї проблемибув запропонований алгоритм Деккера.