Виконується

Призупинення

Призупинений (готовий)

Настання очікваної події

Призупинений (очікує)

Figure: Розширена дiаграма станiв процесу (ОС UNIX)

Сергiй Стасюк Системне програмне забезпечення

Взаємовиключення

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

Такi операцiї як створення i знищення досить складнi (особливо у багатопроцесорнiй системi).

Створення:

Присвоїти номер (ID) процесу; Включити ID в системнi списки; Визначити прiоритет процесу; Завантажити виконуваний код в пам’ять; Сформувати ДП;

Видiлити процесу початковi ресурси; Перевести процес в стан готовностi.

Сергiй Стасюк Системне програмне забезпечення

Взаємовиключення

Операцiї над процесами

Знищення:

Скорегувати системнi структури;

Звiльнити ресурси, якщо процес не звiльнив їх сам;

Розiслати сигнали батькам, нащадкам i пов’язаним процесам.

Якщо знищується процес-батько, можливi два випадки:

1 Знищення усiх синiв;

2 Очiкується завершення процесiв-нащадкiв.

Сергiй Стасюк Системне програмне забезпечення

Взаємовиключення

Паралельнi процеси

Розрiзняють незалежнi процеси (асинхроннi) i взаємодiючi (синхроннi).

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

яку-небудь дiлянку пам’ятi: через змiннi або керуючi структури ОС, через змiннi спiльного використання, через ЗЗП i тому подiбне.

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

Сергiй Стасюк Системне програмне забезпечення

Взаємовиключення

Паралельнi процеси

Приклад: Є декiлька пристроїв, що реєструють подiї одного i того ж типу. Кожним пристроєм керує своя програма i iснує спiльний лiчильник подiй – змiнна спiльного використання.

Програма А

.

.

.

MOV AL, CNT

; обробка CNT

; (перевірка) MOV CNT, AL

.

.

.

Закінчення кванту часу або переривання по настанню події

Програма В

.

.

.

MOV AL, CNT

; обробка CNT MOV CNT, AL

.

.

.

Figure: Приклад необхдностi синхронiзацiї

Сергiй Стасюк Системне програмне забезпечення

Взаємовиключення

Паралельнi процеси

Процес В набуває неправильного значення CNT для обробки, а процес А записує неправильне значення CNT. В результатi втраченi вiдомостi про одну подiю.

Для усунення подiбних проблем кожному процесу необхiдно надати монопольне право доступу до спiльного ресурсу для його модифiкацiї.

Коли один процес модифiкує спiльнi данi, iншим доводиться чекати.

Сергiй Стасюк Системне програмне забезпечення

Взаємовиключення

Критичнi дiлянки

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

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

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

Сергiй Стасюк Системне програмне забезпечення

Взаємовиключення Програмний пiдхiд

Апаратний пiдхiд

Взаємовиключення

Взаємовиключення може бути реалiзоване програмно i апаратно, на рiвнi ОС або на рiвнi застосунку.

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

Сергiй Стасюк Системне програмне забезпечення

Взаємовиключення Програмний пiдхiд

Апаратний пiдхiд

Алгоритм Декера для двох процесiв

Є три спiльнi змiннi, якi встановлюються i аналiзуються двома процесами, що конкурують за ресурс.

початок

П1 (дія першого процесу)

П1_хоче_увійти =І

Обраний процес = другий

2 да

П2_хоче_ увіти = І

2 нет

Аналогично діє П2, тілько змінити номери

П1_хоче_увійти =Х

Критична ділянка 1

Обраний

процес = другий

Обраний процес = другий 2

П1_хоче_увійти =Х

Ця дія дозволяє запобігти

дискримінації

2 нет

П1_хоче_увійти =І

Сергiй Стасюк Системне програмне забезпечення

Взаємовиключення Програмний пiдхiд

Апаратний пiдхiд

Алгоритм Декера для двох процесiв

початок

П1_хоче_увійти = Х П2_хоче_увійти = Х Обраний процес = перший

ініціалізація

П1, П2

кінець

Figure: Запуск двох процесiв, керованих алгоритмом Декера

flag[0]: = false flag[1]: = false turn: = 0 // or 1

Сергiй Стасюк Системне програмне забезпечення

Взаємовиключення Програмний пiдхiд

Апаратний пiдхiд

Алгоритм Декера для двох процесiв

flag[0]: = true

while flag[1] = true { if turn! = 0 {

flag[0]: = false while turn! = 0 {

}

flag[0]: = true

}

}

// критична секцiя

...

turn: = 1 flag[0]: = false

// решта коду

flag[1]: = true

while flag[0] = true { if turn! = 1 {

flag[1]: = false while turn! = 1 {

}

flag[1]: = true

}

}

// критична секцiя

...

turn: = 0 flag[1]: = false

// решта коду

Сергiй Стасюк Системне програмне забезпечення

Взаємовиключення Програмний пiдхiд

Апаратний пiдхiд

Алгоритм Декера для двох процесiв

Переваги алгоритму:

На якому б етапi виконання не був перерваний процес, втрати даних або неправильної модифiкацiї не станеться;

Не виникає нескiнченного вiдкладання входу якого-небудь процесу в критичну дiлянку.

Недолiки: наявнiсть циклiв очiкування, в яких процеси, займаючи час ЦП, можуть знаходитися досить довго.

Сергiй Стасюк Системне програмне забезпечення

Взаємовиключення Програмний пiдхiд

Апаратний пiдхiд

Алгоритм Пiтерсона (розв’язок Петерсона)

//interested[2] is boolean; and turn is an integer interested[0] = false;

interested[1] = false; turn;

interested[0] = true; turn = 1;

while (interested[1] == true

& & turn == 1) {

// busy wait

}

// critical section

...

// end of critical section interested[0] = false;

interested[1] = true; turn = 0;

while (interested[0] == true

& & turn == 0) {

// busy wait

}

// critical section

...

// end of critical section interested[1] = false;

Сергiй Стасюк Системне програмне забезпечення

Взаємовиключення Програмний пiдхiд

Апаратний пiдхiд

Взаємовиключення, апаратний пiдхiд

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

1 У разi «зависання» процесу висне i уся машина.

2 Оскiльки машина нiяк не реагує на переривання, неможливий розвиток в системi iнших процесiв.

Сергiй Стасюк Системне програмне забезпечення

TestAndSet

Взаємовиключення Програмний пiдхiд

Апаратний пiдхiд

У систему команд деяких ЕОМ вводяться засоби пiдтримки паралельних обчислень. Приклад – команда test-and-set. TestAndSet(A, B) копiює значення логiчної змiнної B в змiнну A i встановлює значення “iстина” для логiчної змiнної B.

TestAndSet(A, B)

{

A=B;

B=true;

}

Сергiй Стасюк Системне програмне забезпечення

Взаємовиключення Програмний пiдхiд

Апаратний пiдхiд

Взаємовиключення за допомогою TestAndSet

Є глобальна змiнна “активний” i двi локальних змiнних: “П1_заборона_входу” i “П2_заборона_входу”.

Спершу передбачається, що вiдразу в КС входити не можна, i виконується перевiрка: чи знаходиться iнший процес у своїй КС, про що свiдчить встановлена змiнна “активний”. Якщо ця змiнна встановлена, процес не може увiйти до своєї критичної дiлянки i знаходиться в циклi активного очiкування.

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

Сергiй Стасюк Системне програмне забезпечення

Взаємовиключення Програмний пiдхiд

Апаратний пiдхiд

Взаємовиключення за допомогою TestAndSet

початок

початок П1 (дія першого процесу)

Активний=Х

П1, П2

TestAndSet(П1_заборона_входу,

Активний)

к інець

П1_заборона_входу = І

так

ні Критична ділянка 1

Активний = Х

Інші оператори

кінець

Figure: Взаємовиключення за допомогою команди TESTANDSET

Сергiй Стасюк Системне програмне забезпечення

Взаємовиключення Програмний пiдхiд

Апаратний пiдхiд

CompareAndSwap

Машинна iнструкцiя compare-and-swap (CAS) атомарно порiвнює вмiст комiрки пам’ятi з переданим значенням i, тiльки якщо вони однаковi, встановлює вмiст цiєї комiрки в нове передане значення.

Для x86 вона записується як CMPXCHG (для атомарностi з префiксом LOCK).

CompareAndSwap(Mem, OldVal, NewVal)

{

Orig = Mem;

if (Orig == OldVal) Mem = NewVal;

return Orig;

}

Сергiй Стасюк Системне програмне забезпечення

Взаємовиключення Програмний пiдхiд

Апаратний пiдхiд

Питання?

Сергiй Стасюк Системне програмне забезпечення

Семафори Зв’язок мiж процесами

Монiтори

Операцiйнi системи

Сергiй Стасюк

ЧДТУ

3 листопада 2011 р.

Сергiй Стасюк Системне програмне забезпечення

Семафори

Семафори Зв’язок мiж процесами

Монiтори

Семафор – це захищена змiнна, значення якої можна визначити або модифiкувати тiльки за допомогою спецiальних операцiй P (закрити) i V (вiдкрити).

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

Використовуючи семафорний механiзм, можна переводити процеси в режим пасивного очiкування.

Сергiй Стасюк Системне програмне забезпечення

Семафори Зв’язок мiж процесами

Монiтори

Розрiзняють бiнарнi (двiйковi) семафори, якi набувають значень 0/1 i семафори з лiчильником, якi можуть набувати будь-яких цiлих значень.

Операцiї P i V виконуються ОС (програмною або мiкропрограмною її частиною) у вiдповiдь на запит, виданий деяким процесом i вмiщаючий iм’я семафора в якостi параметра: P (S), V (S).

P(S) V(S)

ні

S> 0

так

так

ні

S> 0

Помістити процес в чергу очікування до семафору S

S=S-1

Процес продовжує виконання

S=S+1

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

Figure: Схеми операцiй P i V

Сергiй Стасюк Системне програмне забезпечення

Семафори Зв’язок мiж процесами

Монiтори

Це можуть бути бiнарнi семафори, але тодi необхiдно помiняти S = S − 1 на S = 0 i S = S + 1 на S = 1, а iнiцiалiзувати семафор S = 1.

Семафори з лiчильником можуть використовуватися, наприклад, коли є декiлька одиниць ресурсiв одного типу, або до одного ресурсу допускається звернення фiксованої кiлькостi процесiв – вiд n до 0, але не бiльше.

У нашому прикладi виходить, що процес, який отримав керування пiсля зупинки i виконання iншим процесом операцiї V (S), починає виконуватися не з примiтиву P, а з оператора, що йде за ним.

Сергiй Стасюк Системне програмне забезпечення

Семафори Зв’язок мiж процесами

Монiтори

Ще одна можлива схема:

P(S)

V(S)

S=S-1

ні

S< 0

так

нет

да

S< 0

Зупинити процес и помістити його в чергу

S=S+1

Активізувати один з очікуючих процесів

Figure: Операцiї P i V (варiант 2)

Сергiй Стасюк Системне програмне забезпечення

Семафори Зв’язок мiж процесами

Монiтори

Черги процесiв найчастiше органiзовуються за типом FIFO, тодi семафор називають сильним. Слабкий семафор – семафор, порядок вiдновлення процесiв з черги якого не визначений.

Переваги:

унiверсальнiсть (можна реалiзувати синхронiзацiю); очiкуючi процеси не чекають ЦП.

Сергiй Стасюк Системне програмне забезпечення

Семафори Зв’язок мiж процесами

Монiтори

Реалiзацiя взаємовиключення за допомогою семафорiв

Критична дiлянка будь-якого процесу оформлюється таким чином:

P(S)

Критична область

V(S)

Figure: Типове використання семафора

Сергiй Стасюк Системне програмне забезпечення

Семафори Зв’язок мiж процесами

Монiтори

Синхронiзацiя за допомогою семафорiв

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

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

якщо процес-споживач працює швидше, можна прочитати одну i ту ж iнформацiю кiлька разiв;

якщо процес-джерело працює швидше, може бути втрачена iнформацiя.

Сергiй Стасюк Системне програмне забезпечення

Семафори Зв’язок мiж процесами

Монiтори

Приклад синхронiзацiї за допомогою семафорiв

П1 (виробник) початок

P(зчитування) P(взаємовиключення) Записати в буфер

П2 (споживач) початок

P(оновлення) P(взаємовиключення) Читання буфера

V(взаємовиключення)

V(взаємовиключення)

V(зчитування)

V(оновлення)

Використання інформації

кінец

кінець

Figure: Синхронiзацiя пари виробник/споживач

Сергiй Стасюк Системне програмне забезпечення

Семафори Зв’язок мiж процесами

Монiтори

Зв’язок мiж процесами

Для двосторонньої передачi потокiв повiдомлень зазвичай використовують два однонаправленi буфери. Приклад - програмнi канали в UNIX (FIFO).

Сергiй Стасюк Системне програмне забезпечення

Семафори Зв’язок мiж процесами

Монiтори

Синхронiзацiя i взаємовиключення за допомогою монiторiв

Монiтор – це примiтив синхронiзацiї бiльш високого рiвня, нiж семафор. Це набiр процедур, змiнних i структур даних, зiбраних в один пакет. Будь-яка процедура з монiтора може бути викликана будь-яким процесом у будь-який час. Внутрiшнi структури даних в монiторi не можуть бути використанi процедурами, описаними поза монiтором.

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

Сергiй Стасюк Системне програмне забезпечення

Семафори Зв’язок мiж процесами

Монiтори

Приклад опису:

Monitor prod_cons Integer i; Condition c;

Procedure producer(x)

...

end;

Procedure consumer(x)

...

end;

end monitor;

Сергiй Стасюк Системне програмне забезпечення

Семафори Зв’язок мiж процесами

Монiтори

По сутi, монiтор - це конструкцiя мови програмування i, отже, реалiзується засобами компiлятора (i можливо, ОС).

Взаємовиключення зазвичай реалiзоване всерединi монiтора за допомогою бiнарного семафора. Над змiнними стану можуть виконуватися двi операцiї: wait i signal. Якщо процедура в монiторi не може бути виконана до кiнця з якоїсь причини (наприклад, заповнений буфер), то вона виконує операцiю wait над якоюсь змiнною, i викликаючий процес призупиняється.

Операцiя signal має бути виконана як остання у будь-якiй процедурi монiтора.

Змiннi стану умови не є лiчильниками, тому якщо немає процесiв, очiкуючих подiї пов’язаної з цiєю змiнною, сигнал втрачається.

Сергiй Стасюк Системне програмне забезпечення

Семафори Зв’язок мiж процесами

Монiтори

Монiтори Хоара

Figure: Монiтор Хоара з двома змiнними стану умови

Сергiй Стасюк Системне програмне забезпечення

Семафори Зв’язок мiж процесами

Монiтори

Монiтори Mesa

Figure: Монiтор в стилi Mesa з двома змiнними стану умови

Сергiй Стасюк Системне програмне забезпечення

Монiтори Java

Семафори Зв’язок мiж процесами

Монiтори

Figure: Монiтор в стилi Java

Сергiй Стасюк Системне програмне забезпечення

Семафори Зв’язок мiж процесами

Монiтори

Питання?

Сергiй Стасюк Системне програмне забезпечення

Тупиковi ситуацiї

Операцiйнi системи

Сергiй Стасюк

ЧДТУ

8 листопада 2011 р.

Сергiй Стасюк Системне програмне забезпечення

Тупиковi ситуацiї

Тупиковi ситуацiї (deadlocks)

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

Приклад. Нехай iснують два процеси: П1 i П2, якi використовують два ресурси Р1 i Р2. З ресурсами пов’язанi семафори S1 i S2 вiдповiдно. Нехай процеси розвиваються по наступному алгоритму (семафори iнiцiалiзуються 1):

Сергiй Стасюк Системне програмне забезпечення

Тупиковi ситуацiї

Тупиковi ситуацiї (deadlocks)

П1 П2

початок

початок

P(S1) 1

P(S2) 5

P(S2) 2

P(S1) 6

V(S1) 3

V(S1) 7

V(S2) 4

V(S2) 8

кінець

кінець

Figure: Приклад виникнення тупикової ситуацiї

Сергiй Стасюк Системне програмне забезпечення

Тупиковi ситуацiї

Тупиковi ситуацiї (deadlocks)

Виконання П2

Завершився П2

Завершилися обидва

Р2 Р1

Завершився П1

Виконання П1

1 2 3 4

Р1 Р2

Figure: Приклад виникнення тупикової ситуацiї

Сергiй Стасюк Системне програмне забезпечення

Тупиковi ситуацiї

Умови виникнення тупикових ситуацiй

1 Умова взаємовиключення – процеси вимагають монопольного доступу до ресурсiв.

2 Умова очiкування ресурсiв – процеси утримують видiленi їм ресурси пiд час очiкування видiлення їм додаткових ресурсiв.

3 Умова вiдсутностi перерозподiлу – ресурси не можна вiдiбрати у процесiв, що зайняли їх, поки вони самi не звiльнять їх.

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

Сергiй Стасюк Системне програмне забезпечення

Тупиковi ситуацiї

Вирiшення проблеми тупикiв

Розглянемо три класичнi стратегiї вирiшення проблеми тупикiв:

1 Запобiгання deadlock-ам (виключення будь-якої з умов виникнення тупику);

2 Обхiд deadlock-iв – заборона на вхiд системи в небезпечнi стани;

3 Виявлення deadlock-iв з подальшим вiдновленням системи.

Сергiй Стасюк Системне програмне забезпечення

Тупиковi ситуацiї

Запобiгання тупиковим ситуацiям

Дисциплiни, якi реалiзують цю стратегiю повиннi гарантувати, що хоч би одну з 4-х необхiдних умов виникнення тупику буде порушено.

Умову взаємовиключення можна усунути введенням необмеженого роздiлення ресурсiв. Проте є ресурси, якi не допускають спiльного використання: принтери, змiннi диски i тому подiбне. Тобто по-справжньому спiльними можуть бути тiльки програми i немодифiкованi данi.

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

Сергiй Стасюк Системне програмне забезпечення

Тупиковi ситуацiї

Запобiгання тупиковим ситуацiям

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

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

Сергiй Стасюк Системне програмне забезпечення

Тупиковi ситуацiї

Обхiд тупикових ситуацiй

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

Розглянемо так званий алгоритм банкiра, запропонований Дейкстрою.

Сергiй Стасюк Системне програмне забезпечення

Тупиковi ситуацiї

Алгоритм банкiра

Нехай є фiксоване число клiєнтiв, кожен з яких з яких заздалегiдь повiдомляє банкiровi максимальну суму, яка може йому знадобитися. Клiєнт може позичати цю суму по частинах i немає нiяких гарантiй, що вiн поверне хоч би частину грошей до того, як зробить усю позику. Але з ймовiрнiстю 100% вiн поверне грошi в кiнцевий термiн часу пiсля отримання їм повної суми. Капiтал банкiра зазвичай менше, нiж сумарнi вимоги клiєнтiв.

Сергiй Стасюк Системне програмне забезпечення

Тупиковi ситуацiї

Алгоритм банкiра

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

Iнакше можлива тупикова ситуацiя: кожен просить дати йому суму, яку йому бракує до максимуму, i тiльки пiсля цього обiцяє повернути грошi.

Сергiй Стасюк Системне програмне забезпечення

Тупиковi ситуацiї

Застосування алгоритму банкiра

А тепер уявимо собi, що банкiр – це система, а клiєнти – процеси. Нехай є t однотипних одиниць ресурсу i n процесiв. Кожен процес заздалегiдь вказує максимальне число ресурсiв, яке йому може знадобитися.

M – максимальна потреба системи;

mi – максимальна потреба у ресурсах i -го процесу, mi< = t, 1 < = i < = n;

li – поточна кiлькiсть ресурсiв, видiлених i -му процесу;

ci = mi− li – поточна потреба в ресурсах i -го процесу. Поточний стан обчислювальної системи називається надiйним, якщо ОС може забезпечити усiм процесам завершення впродовж кiнцевого часу.

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

Сергiй Стасюк Системне програмне забезпечення

Тупиковi ситуацiї

Приклади станiв системи процесiв

Приклад: t = 12

l 1= 1 m 1= 4

Надiйний стан

l 2= 4 m 2= 6

l 3= 5 m 3= 8

n

Залишок z = t − ∑ ︀ l (i) = 2

i =1

l 1= 7 m 1= 10

Ненадiйний стан

Залишок z = 1

l 2= 2 m 2= 5

l 3= 2 m 3= 4

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

Сергiй Стасюк Системне програмне забезпечення

Тупиковi ситуацiї

Приклади станiв системи процесiв

З надiйного стану запросто можна потрапити в ненадiйний: Якщо система знаходиться у ненадiйному станi, черговий запит може поставити її у тупик (ресурси запитуються i звiльняються

l 1= 1 m 1= 4

по одному)

l 2= 4 m 2= 6

l 3= 6 m 3= 8

Залишок z = 1

Сергiй Стасюк Системне програмне забезпечення

Тупиковi ситуацiї

Виявлення й усунення тупикiв

За допомогою спецiального алгоритму система перевiряє, чи не є граф запитiв i розподiлу ресурсiв вiдображенням тупикової ситуацiї.

Р1 Р1

Figure: Пошук тупикових ситуацiй за допомогою графа запитiв i розподiлу ресурсiв

Сергiй Стасюк Системне програмне забезпечення

Тупиковi ситуацiї

Виявлення й усунення тупикiв

Перiодичнiсть виконання цього алгоритму:

кожного разу, коли запит ресурсу вiдхиляється; через рiвнi промiжки часу (1 хвилина).

Сергiй Стасюк Системне програмне забезпечення

Тупиковi ситуацiї

Виявлення й усунення тупикiв

Можливi дiї для вiдновлення нормальної роботи:

Примусове завершення усiх процесiв i перезапуск ОС - занадто радикально;

Примусове завершення усiх процесiв, що знаходяться в deadlock;

Завершення процесiв, що знаходяться в deadlock по одному з перевiркою стану системи на предмет усунення тупика;

Сергiй Стасюк Системне програмне забезпечення

Тупиковi ситуацiї

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

Перерозподiлити (видiлити) усi необхiднi ресурси одному з процесiв з надiєю, що виконавшись вiн дасть можливiсть виконатися iншим;

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

Сергiй Стасюк Системне програмне забезпечення

Тупиковi ситуацiї

Питання?

Сергiй Стасюк Системне програмне забезпечення

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

Операцiйнi системи

Сергiй Стасюк

ЧДТУ

8 листопада 2011 р.

Сергiй Стасюк Системне програмне забезпечення

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

Керування процесором (процесорним часом)

Час ЦП в мультизадачних системах – це деякий перерозподiльний ресурс. Розподiлом часу в системi займається планувальник (диспетчер). Планувальник верхнього рiвня визначає, якi процеси допущенi до виконання на ЦП. А планувальник нижнього рiвня (диспетчер) визначає який процес з черги процесiв готових до виконання отримає черговий квант ЦП i на який час.

Усi дисциплiни планування ЦП подiляються на два види – з перемиканням завдань мiж собою (з витiсненням) i без перемикання (виконання завдань вiд початку до кiнця, без витiснення).

Сергiй Стасюк Системне програмне забезпечення

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

Дисциплiни планування з однiєю чергою

Дисциплiна планування FIFO (First In First Out) – без перемикання, завдання ставляться в чергу за принципом FIFO. Дисциплiна планування RR (Round Robin) – аналогiчна попереднiй, але з перемиканням завдань, не виконане до кiнця завдання повертається в кiнець черзi.

Дисциплiна планування SJF (Shortest Jobs First) – найкоротшi завдання виконуються першими, перемикання не передбачено. Мiсце завдання в черзi на запуск визначається її очiкуванним часом виконання.

Сергiй Стасюк Системне програмне забезпечення

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

Дисциплiни планування з однiєю чергою

Дисциплiна планування SRT (Shortest Remaining Time) – по найменшому залишившимуся до завершення часу. Ця дисциплiна припускає перемикання завдань. Залишившийся час - це рiзниця мiж очiкуваним часом виконання завдання i часом впродовж якого це завдання вже знаходиться в роботi. Порiвняно довгi завдання матимуть навiть бiльший час очiкування, чим у випадку SJF. Це вiдбувається через те, що реалiзацiя дисциплiни SRT характеризується великими накладними витратами.

Сергiй Стасюк Системне програмне забезпечення

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

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

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

Сергiй Стасюк Системне програмне забезпечення

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

Дисциплiни планування з однiєю чергою

Дисциплiна планування HRN (Highest Response ratio Next) - вибiр мiсця процесу в черзi по найбiльшому вiдносному часу вiдповiдi. Перемикання не вiдбувається, тобто кожне завдання виконується вiд початку i до кiнця. Ця дисциплiна компенсує деякi недолiки SJF: дискримiнацiю по вiдношенню до довгих завдань i надмiрну прихильнiсть до коротких нових завдань.

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

Сергiй Стасюк Системне програмне забезпечення

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

Дисциплiни планування з однiєю чергою

1 � – динамiчний прiорiтет;

2 � – час вiдповiдi системи;

3 � – час очiкування;

4 � – час обслуговування.

� + �

� =

�

� + � = �

Сергiй Стасюк Системне програмне забезпечення

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

Дисциплiни планування з однiєю чергою

Динамiчний прiорiтет = час очiкування + час обслуговування

час обслуговування

Час очiкування + час обслуговування = час вiдповiдi системи

Сергiй Стасюк Системне програмне забезпечення

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

Дисциплiни з декiлькома чергами

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

надавати перевагу коротким завданням;

надавати перевагу завданням, що часто виконують ввiд/вивiд, щоб забезпечити хороший коефiцiєнт використання ПВВ;

якнайшвидше визначати характер процесу i вiдповiдним чином планувати його виконання.

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

Сергiй Стасюк Системне програмне забезпечення

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

Дисциплiни з декiлькома чергами

Рівень 1

Рівень 2

FIFO

Виконання

Закінчення кванту часу

Виконання