Контекст i дескриптор процесу

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

Крім цього, операційній системі, для реалізації планування процесів, потрібна додаткова інформація; ідентифікатор процесу, стан процесу, дані про cтупінь привілейованості процесу, місце перебування кодового сегмента й інша інформація. У деяких ОС (наприклад, в ОС UNIX) таку інформацію (що використовують ОС для планування процесів) називають дескриптором процесу.

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

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

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

1. створити інформаційні структури, що описують даний процес, тобто його дескриптор i контекст;

2. включити дескриптор нового процесу в чергу готових процесів;

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

 

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

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

1. визначення моменту часу, з метою зміни виконуваного процесу;

2.вибір процесу на виконання з черги готових процесів;

3. переключения контекстів "старого" i "нового" процесів.

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

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

Відповідно до aлгоритмів, заснованих на квантуванні, зміна активного процесу відбувається, якщо:

· процес завершився i залишив систему;

· наявна помилка;

· процес перейшов у стан ЧЕКАННЯ;

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

Процес, що вичерпав свій квант, переводиться в стан ГОТОВНІСТЬ i очікує, коли йому буде наданий новий квант процесорного часу, а на виконання, відповідно до визначеного правила вибирається новий процес з черги готових. Таким чином, жоден процес не займає процесор надовго. Тому квантування широко використовують у системах поділу часу. Графа станів процесу, зображена на мапюнку 2.1., відповідає алгоритму планування, заснованому на квантуванні.

Кванти, виділені процесом, можуть бути однаковими для всіх процесів. Кванти, виділені одному процесові, є фіксованої величини.Вони можуть змінюватися в piзнi періоди життя процесу. Процеси, що не повністю використали виділений їм квант (наприклад, через відхід на виконання операцій виводу введення-виведення), можуть одержати, чи не одержати, компенсації у видіпривілеїв при наступному обслуговуванні. По-різному може бути організована черга готових процесів.Наприклад, циклічно, за правилом "перший прийшов - перший обслужився" (FIFO) чи за правилом "останній прийшов - перший обслужився" (LIFO).

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

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

В обох випадках вибір процесу на виконання, з черги вже готових, здійснюється однаково: вибирається процес, що має найвищий пріоритет. По-різному вирішується проблема визначення моменту зміни активного процесу. У системах із відносними пріоритетами, активний процес виконується доти, поки він сам не залишить процесор, перейшовши в стан ЧЕКАННЯ (чи ж закрадеться помилка або ж процес завершиться). У системах з абсолютними пріоритетами виконання активного процесу, він переривається ще при одній умові: якщо в черзі готових процесів з'явився процес, пріоритет якого вище пріоритету активного процесу. У цьому випадку перерваний процес переходить у стан готовності. На малюнку 2.2 зображені графи станів процесу для алгоритмів із відносними (a) i абсолютними (б) пріоритетами.

 

Мал. 2.2. Графи станів процесів у системах (а) із відносними пріоритетами; (б)з абсолютними пріоритетами.

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

Існує два основних типи процедур планування процесів: що витісняють (preemptive) i не витісняють (non-preemptive).

Non-preemptive multitasking - не витісняє багатозадачність- це cпociб планування процесів, при якому активний процес виконується доти, поки він сам, за власною ініціативою, не віддасть керування планувальнику операційної системи для того, щоб той вибрав з черги інший, готовий до виконання процес.

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

Поняття preemptive i non-preemptive іноді утотожнюють із поняттями пріоритетних i безпріоритетних дисциплін, що зовсім невірно, а також з поняттями абсолютних i відносних пріоритетів, що частково неправильно. Що витісняє i не витісняє багатозадачність - це ширше поняття, ніж типи пріоритетності. Пріоритети задач можуть як застосовувати, так i не застосовувати. Так, у випадку використання пріоритетів, дисципліна відносних пріоритетів може належати до класу систем, що не витісняють багатозадачність, а дисципліна абсолютних пріоритетів - до класу систем, що витісняють багатозадачність. Безпріоритетна ж дисципліна планування, заснована на виділенні рівних квант часу для вcix задач, належить до алгоритмів, що витісняють.

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

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

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

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

Однак розподіл функцій планувальника міжсистемою i додатками, завжди є недоліком, хоча, за певних умов, може бути i перевагою, оскільки дає можливість розроблювачу додатків самому проектувати алгоритм планування, найбільш придатний для даного фіксованого набору задач. У цьому випадку розроблювач сам визначає у npoгpaмi час віддачі керування, при цьому неможливі нераціональні переривання програм у "незручні” для них моменти часу. Kpiм цього, легко вирішуються проблеми використання даних: задача під час кожної ітерації використовує їх монопольно й упевнено, що не дозволяє нікому протягом цього періоду змінити ці дані. Істотною перевагою non-preemptive систем є висока швидкість переключення з задачі на задачу.

Прикладом ефективного використання, що не витісняє багатозадачності, є файл-сервер NetWare, де, у значній мipi, завдяки цьому, досягнута висока швидкість виконання файлових операцій. Менш вдалим є використання, що не витісняє багтозадачності з операційного середовища Windows 3.x.

Однак, майже всі сучасні операційні системи, орієнтовані на високопродуктивне виконання додатків (UNIX, Windows NT, OS/2 VAX/VMS), спрямовані на витіснена багатозадачності. Останнім часом, дійшла черга i до ОС класу настільних систем, наприклад, OS/2 Warp i Windows 95. Можливо, в зв'язку з цим, ОС, що витісняє багатозадачність, часто називають щирою багатозадачністю.

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

 

 

 

Мал. 2.3. Приклад необхідності синхронізації

 

Недооцінювання питаньми синхронізації процесів, що виконуються в режимі мультипрограмування, може привести до їх неправильної роботи чи, навіть, до краху системи. Розглянемо, як приклад (малюнок 2.3), програму печатки файлів (принт-сервер). Ця програма друкує по черзі yci файли, імена яких, послідовно, за порядком надходження, записують у спеціальний загальнодоступний файл "замовлень" iншi програми. Змінна NEXT, що доступна процесам-клієнтам, містить номер першої вільної, для запису iмeнi файлу, позиції файлу "замовлень". Процеси-клієнти читають цю змiннy, записують у відповідну позицію файлу "замовлень" ім'ясвого файлу i нарощують значения NEXT на одиницю. Уявімо, що в деякий момент, процес R вирішив роздрукувати свій файл. З цією метою він прочитав значення перемінної NEXT, припустимо - 4. Процес запам'ятав це значення, але помістити iм'я файлу не встиг, тому що його виконання було перервано (наприклад, унаслідок вичерпання кванта). Черговий процес S, що бажає роздрукувати файл, прочитав те ж саме значення перемінної NEXT, помістив у четверту позицю ім'ясвого файлу i наростив значення перемінної на одиницю. Коли чергу керування буде передано процесу R, то він, продовжуючи своє виконання, у повній відповідності зi значенням поточно вільної позиції, отриманим під час попередньої ітерації, запише ім'яфайлу також у позицію 4, поверх iмeнi файлу процесу S.

Таким чином, процес S ніколи не побачить свій файл роздрукованим. Складність проблеми синхронізації полягає в нерегулярності виникаючих ситуацій(можна уявити й інший розвиток подій): загублені файли декількох процесів, навпроти, не був загублений жоден файл. У даному випадку ycе визначається взаємними швидкостями процесів i моментами їхнього переривання. Тому налагодження взаємодіючих процесів є складною задачею. Ситуації подібні до тiєї, коли два чи більше процеси обробляють поділювані дані, i кінцевий результат залежить від співвідношення швидкостей процесів, називаються гонками.

Критична секція

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

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

 

 

Мал. 2.4. Реалізація критичних секцій з використанням блокуючих перемінних.

 

Іншим способом є використання блокуючих змінних. Із кожним поділюваним ресурсом пов'язується двійкова перемінна, котра приймає значення 1, якщо ресурс вільний (тобто жоден процес не є в даний момент у критичній секції, пов'язаній з даним процесом), i значення 0, якщо ресурс зайнятий. На малюнку 2.4 зображений фрагмент алгоритму, що використовують для реалізації виключення доступу до поділюваного ресурсу D блокуючої перемінни F(D). Перед входом у критичну секцію процес перевіряє чи вільний ресурс D. Якщо він зайнятий, - то перевірка циклічно повторюється, якщо вільний, - то значення перемінної F(D) встановлюється на 0, i тому процес входить у критичну секцію. Після того, як процес виконає всі дії з поділюваним ресурсом D, значення перемінної F(D) знову встановлюється рівним 1.

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

Реалізація критичних секцій з використанням блокуючих перемінних має істотний недолік: протягом часу, коли один процес знаходиться в критичій секції, інший процес, якому потрібен той же ресурс, буде виконувати рутинні дії з опитування блокуючої перемінної, даремно витрачаючи процесорний час. З метою усунення таких ситуацій, може бути використаний так званий апарат подій. За допомогою цього засобу можуть зважуватися не тільки проблеми взаємного виключення, але й більш загальніші задачі синхронізації процесів. У piзниx операційних системах апарат подій реалізується по - своєму, але в будь-якому випадку використовують системні функції аналогічного призначення, що умовно назвемо WAIT(x) i POST(x), де х -ідентифікатор деякої події. На малюнку 2.5 зображений фрагмент алгоритму процесу, що використовує ці функції. Якщо ресурс зайнятий, то процес не виконує циклічне опитування, а викликає системну функцію WAIT(D), тут D позначає подію, що полягає в звільненні ресурсу D. Функція WAІT(D) переводить активний процес у стан ЧЕКАННЯ i робить оцінку в його дескрипторі стосовно того, що процес очікує події D. Процес, що у цей час використовує ресурс D, після виходу з критичної секції виконує системну функцію POST(D), у результаті чого операційна система переглядає чергу процесів, що очікують, i переводить процес, що очікує події D, у стан ГОТОВНІСТЬ.

Узагальнити засіб синхронізації процесів запропонував Дейкстра, що ввів два нових примітиви. В абстрактній формі вони, позначаються Р i V, оперують над цілими ненегативними перемінними, названими семафорами. Нехай S такий семафор. Операції внзначають у такий cпociб:

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

P(S); - зменшення S на 1, якщо це можливо. Якщо S=0, то неможливо зменшити S i залишитися в oблacтi цілих негативних значень, у цьому випадку процес, що викпикає Р-операцію, чекає, поки це зменшення стане можливим. Успішна перевірка i зменшення також є неподільною операцією.

 

Мал. 2.5. Релізація критичної секції, з використанням системних функцій WAIT(D) i POST(D)

 

В окремому випадку, коли семафор S може приймати тільки значення 0 i 1, він перетворюється в блокуючу перемінну. Операція Р містить у coбi потенційну можливість переходу процесу, що її виконує, у стан чекання, у той час як V-операція може, при деяких обставинах, активізувати інший процес, припинений операцією Р (порівняєте ці операції із системними функціями WAIT i POST).

Розглянемо використання семафорів на класичному прикладі взаємодії двох процесів, що виконуються в режимі мультипрограмування, один із яких дано в буферний пул, a інший зчитує його з буферного пула. Нехай буферний пул складається з N буферів, кожнен з яких може містити один запис. Процес '"письменник" повинен припинятися, коли вci буфери є зайнятими, i активізуватися, при звільненні хоча б одного буфера. Навпроти, процес "читач" припиняється, коли всі буфери порожні i активізується з появою хоча б одного запису.

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

 

іnt e = N, f = 0, b=1;

void Writer ()

{

while(1)

{

PrepareNexlRecordf); /*пiдготовка нового запису */

P(e); /* Зменшити число вільних буферів, якщо вони є */

/* в іншому випадку - чекати, поки вони звільняться */

P(b); /* Bxiд у критичну секцію */

AddToBuffer(); /* Додати новий запис у буфер */

V(b); /* Вихід iз критичної секції */

V(f); /* Збільшити число зайнятих буферів */

{

{

void Reader ()

{

while(1)

{

P(f); /* Зменшити число зайнятих буферів, якщо вони є */

/* в іншому випадку - чекати, поки вони з'являться

Р(b); /* Bxiд у критичну секцію */

GelFromBufferQ; */ Узяти запис із буфера */

V(b); /* Вихід iз критичної секції */

V(e); /* Збільшити число вільних буферів */

Process Record (); /* Опрацювати запис */

Тупіки

Наведений вище приклад допоможе нам проілюструвати ще одну проблему синхронізації - взаємні блокування, названі також дедлоками(deadlocks),клінчами(clinch)чи тупіками. Якщо переставити місцями операції Р(е) i P(b) у пporpaмi "письменник", то при збігy обставин цідва процеси можуть взаємно заблокувати один одного. Дійсно, нехай "письменник" першим ввійде в критичну секцію i знайде відсутність вільних буферів; він почне чекати, коли "читач" візьме черговий запис із буфера, хоча "читач" не зможе цього зробити, тому що для цього необхідно ввійти в критичну секцію, вхід у яку заблокований процесом "письменником".

Розглянемо ще один приклад тупіка. Нехай двом процесам, що виконуються в режимі мультипрограмування, для виконання їхньої роботи потрібно два ресурси, наприклад, принтер i диск. На малюнку 2.6.(а) показані фрагменти відповідних програм. I нехай після того, як процес А зайняв принтер (установив блокуючу перемінну), він був перерваний. Керування одержав процес У, що спочатку зайняв диск, але при виконанні наступної команди, був заблокований, тому що принтер виявився вже зайнятим процесом А. Керування знову одержав процес А, що у відповідності із своєю програмою, зробив спробу зайняти диск i був заблокований: диск уже зайнятий процесом В. У такому стані процеси А іВ можуть знаходитися як завгодно довго.

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

 

 

Мал. 2.6. (а) фрагменти програм А і В, що розділяють принтер i диск;

(б) взаємне блокування (клінч); (в) черга до поділюваного диска;

(г) незалежне використання pecypciв.

 

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

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

• запобігання утворення тупиків;

• розпізнавання тупіків;

• відновлення системи після тупіків.

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

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

Якщо ж тупікова ситуація все ж таки виникла, то не обов'язково знімати з виконання всі заблоковані процеси. Можна зняти тільки частину з них, при цьому звільняються ресурси, очікувані іншими процесами, можна повернути деякі процеси в область свопінга, можна "відкотити" деякі процеси до так званої контрольної крапки, у якій запам'ятовується вся інформація, необхідна для відновлення виконання програми з даного місця. Контрольні крапки розставляють у пporpaмi в місцях, після яких можливе виникнення тупіка. З усього вищесказаного зрозуміло, що використовувати семафори потрібно дуже обережно, тому що одна незначна помилка може призвести до зупинки системи. Для того, щоб полегшити написания конкретних програм, запропонували високорівневий засіб синхронізації, названий монітором. Moнiтop - це нaбіp процедур, перемінних структур даних. Процеси можуть викликати процедури монітоpa, але не мати доступу до внутрішніх даних монітора. Монітори мають важливу властивість, що робить їx корисними для досягнення взаємного виключення: тільки один процес може бути активним, стосовно монітоpa. Компілятор обробляє виклики процедур монітора особливим образом. Звичайно, коли процес викликає процедуру монітора, то перші кілька інструкцій цієї процедури перевіряють, чи не активний будь-який інший процес, стосовно монітора. Якщо так, то зухвалий процес припиняється, поки інший процес не звільнить монітоp. Таким чином, виключення входу декількох процесів у моніторі реалізується не програмістом, а компілятором, що робить помилки менш ймовірними.

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

Нитки

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

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

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

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

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

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

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

Нитки iноді називають полегшеними процесами чи міні-процесами. Дійсно, нитки в багатьох відношення подібні до процесів. Кожна нитка виконується строго і послідовно i має свій власний програмний лічильник та стік. Нитки, як і процеси, можуть, наприклад, породжувати нитки-нащадки, можуть переходити зі стану в стан. Подібно до традиційних процесів (тобто процесам, що складаються з однієї нитки), вони можуть знаходитися в одному з наступних станів: ВИКОНАННЯ, ЧЕКАННЯ i ГОТОВНІСТЬ. Поки одна нитка заблокована, інша нитка того ж процесу може виконуватися. Нитки розділяють процесор так як це роблять процеси, відповідно до різних варіантів планування.

Однак різні нитки в рамках одного процесу не настільки незалежні, як окремі процеси. Уci вони мають той самий адресний простір. Це означає, що вони розділяють ті caмі глобальні перемінні. Оскільки кожна нитка є доступ до кожної віртуальної адреси, то одна нитка може використовувати стек іншоїнитки. Між нитками немає повного захисту, тому що, по-перше, це неможливо, а по-друге, не потрібно. Уci нитки одного процесу завжди вирішують загальну задачу одного користувача i апарат ниток використовують для більш швидкого рішення задачі, шляхом її розпаралелювання. При цьому, програмісту дуже важливо мати у своєму розпорядженні зручні засоби організації взаємодії частин oднієї задачі. Kpiм поділу адресного простору, yci нитки розділяють також нaбip відкритих файлів, таймерів, сигналів i т.п.

Отже, нитки мають власні:

· програмні лічильники;

· стік;

· регістри;

· нитки-нащадки;

· стани.

Нитки розділяють:

· адресний пpocтip;

· глобальніпepeмінні;

· відкриті файли;

· таймери;

· семафори;

· статистичну інформацію.

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

Широке застосування має багатониткова обробка в розподілених системах. Про це в розділі "Процеси i нитки в розподілених системах".

Деякі приклади задач легше програмувати, використовуючи паралелізм, наприклад, задачі типу "письменник-читач", у яких одна нитка виконує запис у буфер, а інша - зчитує записи з нього. Оскільки вони розділяють загальний буфер, то не потрібно їx робити окремими процесами. Інший приклад використання ниток - це керування сигналами, (наприклад, переривання з клавіатури (del чи break)). Замість обробки сигналу переривання, одна нитка призначається для постійного чекання надходження сигналів. Таким чином, використання ниток може скоротити необхідність у перериваннях користувальницького рівня. У цих прикладах не настільки важливе рівнобіжне виконання, як важлива якість програми.

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

 

 

Керування пам'яттю

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

Типи адрес

Для ідентифікації перемінних i команд використовують символьні імена (мітки), віртуальні i фізичні адреси (малюнок 2.7).

Символьні iмeнa привласнює користувач, при написанні програми алгоритмічною мовою або на ассемблері.

Віртуальні адреси виробляє транслятор, що переводить програму на мову машинни. Оскільки під час трансляції не відомо, у яке місце оперативної пам'яті буде завантажена програма, транслятор привласнює перемінні та віртуальні (умовні) адреси, звичайно, вважаючи за замовчування те, що програма буде розміщена, починаючи з нульової адреси. Сукупність віртуальних адрес процесу називають віртуальним адресним простором. Кожен процес має власний віртуальний адресний пpocтip. Максимальний poзмip віртуального адресного простору обмежується розрядністю адреси, властивій даній apxiтeктypi комп'ютера i, як правило, не збігається з обсягом фізичної пам'яті, що є в комп'ютері.

 

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

 

Мал. 2.7. Типи адрес

 

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