Алгоритм запобігання тупикових ситуацій.

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

Розглянемо приклад:

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

Представимо фрагмент двох програм:

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

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

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

На малюнку а) зображений деякий стан системи:

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

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

Один з них зветься “Алгоритм Банкіра”.

Кожному процесу поставлено у відповідність ціле число i (1( i (N). Процесу i відповідають його максимальна потреба в пристроях МАКС(i), кількість пристроїв, виділених йому в цей момент ВЫДЕЛУСТР(i), що покладається йому залишок - ЗАЛИШОК(i) і ознака МОЖЕ НЕ ЗАКІНЧИТИ(i).

Системи заводять глобальну змінну ОБЩУТР, що позначає загальне число наявних у системі пристроїв.

На початку роботи невідомо, чи може якийсь процес звкінчитися МОЖЕ НЕ ЗАКІНЧИТИ(i) true для всіх i.

Щораз, коли якийсь ЗАЛИШОК може бути виділений із числа незайнятими пристроїв, що залишаються, передбачається, що відповідний процес працює, поки не закінчиться, а потім його пристрої звільняються.

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

..........

СВОБУСТР:=ОБЩУСТР;

for i:=1 step 1 until N do

 begin

СВОБУСТР:=СВОБУСТР-ВЫДЕЛУСТР(i);

МОЖЕТНЕЗАКОНЧИТЬ(i):=True;

ЗАЛИШОК(i):=МАКС(i)-ВЫДЕЛУСТР(i);

 end;

 ОЗНАКА:=True;

 do while (ОЗНАКА);

ОЗНАКА:=False;

for i:=1 step 1 until N do

Begin

if МОЖЕТНЕЗАКОНЧИТЬ(i) and ЗАЛИШОК(i) <= СВОБУСТР;

СВОБУСТР:=СВОБУСТР+ВЫДЕЛУСТР(i);

ОЗНАКА:=True;

end;end;end;end;

if СВОБУСТР=ОБЩУСТР then Стан системи безпечне

               else Стан системи не безпечне

..........

Розподіл часу процесора.

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

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

Найбільш характерними критеріями ефективності обчислювальних систем є:

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

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

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

Залежно від цього ОС діляться на:

· Системи пакетної обробки;

· Системи поділу часу;

· Системи реального часу.

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

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

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

1. Спеціалізований процесор вводу-виводу.

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

· установити магнітну головку;

· надрукувати рядок і т.д.

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

1. Зовнішні пристрої управляються контролерами.

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

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

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

Системи поділу часу.

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

Системи реального часу .

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

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

Мультипроцесорна обробка.

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

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

Функції підтримки мультипроцесорної обробки даних є в багатьох ОС, у тому числі й такий як Windows NT.

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

· к архітектурі;

· до способу організації обчислювального процесу.

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

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

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

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

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

Ассиметричне мультипроцесування є найбільш простим способом організації. Цей спосіб іноді називають «ведучий - відомий».

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

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

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

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

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

Поняття процесу й потоку

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

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

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

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

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

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

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

При керуванні процесами ОС використовує два основних типи інформаційних структур:

· дескриптор процесу;

· контекст процесу.

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

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

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

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

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

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

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

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

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

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

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

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

· вибір для виконання потоку із черги готових потоків.

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

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

Планування може бути динамічним або статичним.

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

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

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

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

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

Контекст відбиває:

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

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

Диспетчеризація зводиться до наступного :

· збереження контексту поточного потоку, що потрібно перемінити;

· завантаження контексту нового потоку, обраного в результаті планування;

· запуск нового потоку на виконання.

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

· виконання - виконується процесором:

· очікування - чекає здійснення деякої події;

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

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

Граф станів потоку в багатозадачному середовищу можна представити як на малюнку:

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

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

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

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

Невитісняючізасновані на тому, що активному потоку дозволено виконуватися доти, поки він сам не вирішить віддати керування ОС.

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

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

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

Майже всі сучасні ОС, такі як UNIX, Windows NT/2000, OS-2, Windows 95/98 реалізують витісняютчі  алгоритми планування потоків.

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

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

Сміна активного потоку відбувається, якщо:

· потік завершився й покинув систему;

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

· потік перейшов у стан очікування;

· вичерпано квант процесорного часу.

Потік, що вичерпав свій квант, переводиться в стан готовності й очікує в черзі. Граф станів потоку представлений на малюнку:

Кванти для потоків можуть бути однаковими або різними.

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

Відповідний граф станів потоку можна представити як:

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

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

В ОС Windows NT визначено 32 рівня пріоритетів і два класи потоків - потоки реального часу й потоки зі змінними пріоритетами.

Діапазон від 1 до 15 відведений для потоків зі змінними пріоритетами, а від 16 до 32 - для більш критичних вчасно потоків реального часу.

Змішані алгоритми планування.

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

Так зроблено в Windows NT, у ній квантування сполучається з динамічними абсолютними пріоритетами. На виконання вибирається потік з найвищим пріоритетом. Йому виділяється квант часу. Якщо під час виконання в черзі готових з'являється потік з більш високим пріоритетом, то він витісняє виконуваний потік. Витиснутий потік повертається в чергу готових, причому він стає поперед всіх інших потоків, що мають такий же пріоритет.

Планування в системах реального часу.

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

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

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

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

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

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

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

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

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

· зовнішнє апаратне переривання. Воно сигналізує про переклад відповідного поточного завдання в чергу готовності й виконується планувальник;

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

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