Управління процесами
Найважливішою частиною операційної системи, що безпосередньо впливає на функціонування обчислювальної машини, є підсистема керування процесами. Процес (або по-іншому, завдання) - абстракція, що описує, які виконуються. Для операційної системи процес являє собою одиницю роботи, заявку на споживання системних ресурсів. Підсистема управління процесами планує виконання процесів, тобто розподіляє процесорний час між декількома одночасно існуючими в системі процесами, а також займається створенням і знищенням процесів, забезпечує процеси необхідними системними ресурсами, підтримує взаємодію між процесами.
Стан процесів
У багатозадачній (багатопроцесорний) системі процес може знаходитися в одному з трьох основних станів:
ВИКОНАННЯ - активний стан процесу, під час якого процес володіє всіма необхідними ресурсами і безпосередньо виконується процесором;
ОЧІКУВАННЯ - пасивний стан процесу, процес заблокований, він не може виконуватися по своїх внутрішніх причин, він чекає здійснення деякої події, наприклад, завершення операції введення-виведення, одержання повідомлення від іншого процесу, звільнення якого-небудь необхідного йому ресурсу;
ГОТОВНІСТЬ - також пасивний стан процесу, але в цьому випадку процес заблокований у зв'язку з зовнішніми по відношенню до нього обставинами: процес має всі необхідні для нього ресурси, він готовий виконуватися, однак процесор зайнятий виконанням іншого процесу.
У ході життєвого циклу кожен процес переходить з одного стану в інший відповідно до алгоритму планування процесів, реалізованим у даній операційній системі. Типовий граф станів процесу показаний на малюнку 2.1.
У стані ВИКОНАННЯ у однопроцесорній системі може знаходитися тільки один процес, а в кожному зі станів ОЧІКУВАННЯ і ГОТОВНІСТЬ - кілька процесів, ці процеси утворюють черги відповідно очікують і готових процесів. Життєвий цикл процесу починається зі стану ГОТОВНІСТЬ, коли процес готовий до виконання і чекає своєї черги. При активізації процес переходить у стан ВИКОНАННЯ і знаходиться в ньому до тих пір, поки або він сам звільнить процесор, перейшовши в стан ОЧІКУВАННЯ якої-небудь події, або буде насильно "витиснутий" із процесора, наприклад, внаслідок вичерпання відведеного даному процесу кванта процесорного часу . В останньому випадку процес повертається в стан ГОТОВНІСТЬ. У цей же стан процес переходить зі стану ОЧІКУВАННЯ, після того, як очікуване подія відбудеться.
Рис. 2.1. Граф станів процесу в багатозадачному середовищі
Контекст і дескриптор процесу
Протягом існування процесу його виконання може бути багаторазово перерване і продовжене. Для того, щоб відновити виконання процесу, необхідно відновити стан його операційного середовища. Стан операційного середовища відображається станом регістрів і програмного лічильника, режимом роботи процесора, покажчиками на відкриті файли, інформацією про незавершені операції введення-виведення, кодами помилок виконуваних даним процесом системних викликів і т.д. Ця інформація називається контекстом процесу.
Крім цього, операційної системи для реалізації планування процесів потрібна додаткова інформація: ідентифікатор процесу, стан процесу, дані про ступінь привілейованості процесу, місце знаходження кодового сегмента й інша інформація. У деяких ОС (наприклад, в ОС UNIX) інформацію такого роду, використовувану ОС для планування процесів, називають дескриптором процесу.
Дескриптор процесу в порівнянні з контекстом містить більш оперативну інформацію, яка повинна бути легко доступна підсистемі планування процесів. Контекст процесу містить менш актуальну інформацію і використовується операційною системою тільки після того, як прийнято рішення про відновлення перерваного процесу.
Черги процесів являють собою дескриптори окремих процесів, об'єднані в списки. Таким чином, кожен дескриптор, крім всього іншого, містить принаймні один покажчик на інший дескриптор, що є сусідами з ним в черзі. Така організація черг дозволяє легко їх переупорядочівать, включати і виключати процеси, переводити процеси з одного стану в інший.
Програмний код тільки тоді почне виконуватися, коли для нього операційною системою буде створений процес.
Створити процес - це значить:
створити інформаційні структури, що описують даний процес, тобто його дескриптор і контекст;
включити дескриптор нового процесу в чергу готових процесів;
завантажити кодовий сегмент процесу в оперативну пам'ять або в область свопінгу.
Алгоритми планування процесів
Планування процесів містить у собі рішення наступних завдань:
визначення моменту часу для зміни виконуваного процесу;
вибір процесу на виконання з черги готових процесів;
перемикання контекстів "старого" і "нового" процесів.
Перші два завдання вирішуються програмними засобами, а остання значною мірою апаратно (див. розділ 2.3. "Засоби апаратної підтримки управління пам'яттю і багатозадачного середовища в мікропроцесорах Intel 80386, 80486 і Pentium").
Існує безліч різних алгоритмів планування процесів, по різному вирішують перераховані вище завдання, переслідують різні цілі і забезпечують різну якість мультипрограмування. Серед цієї безлічі алгоритмів розглянемо докладніше дві групи найбільш часто зустрічаються алгоритмів: алгоритми, засновані на квантуванні, і алгоритми, засновані на пріоритетах.
Відповідно з алгоритмами, заснованими на квантуванні, зміна активного процесу відбувається, якщо:
процес завершився і залишив систему,
сталася помилка,
процес перейшов у стан ОЧІКУВАННЯ,
вичерпаний квант процесорного часу, відведений даному процесу.
Процес, який вичерпав свій квант, переводиться в стан ГОТОВНІСТЬ і чекає, коли йому буде наданий новий квант процесорного часу, а на виконання відповідно до певним правилом вибирається новий процес з черги готових. Таким чином, жоден процес не займає процесор надовго, тому квантування широко використовується в системах поділу часу. Граф станів процесу, зображений на малюнку 2.1, відповідає алгоритму планування, заснованому на квантуванні.
Кванти, виділювані процесам, можуть бути однаковими для всіх процесів чи різними. Кванти, виділювані одному процесу, можуть бути фіксованої величини або змінюватися в різні періоди життя процесу. Процеси, які не повністю використали виділений їм квант (наприклад, через відхід на виконання операцій введення-виведення), можуть отримати або не отримати компенсацію у вигляді привілеїв при наступному обслуговуванні. По різному може бути організована чергу готових процесів: циклічно, за правилом "перший прийшов - першим обслужений" (FIFO) чи за правилом "останній прийшов - перший обслужити" (LIFO). Інша група алгоритмів використовує поняття "пріоритет" процесу. Пріоритет - це число, що характеризує ступінь привілейованості процесу при використанні ресурсів обчислювальної машини, зокрема, процесорного часу: чим вищий пріоритет, тим вище привілеї. Пріоритет може виражатися цілими чи дробовими, позитивним чи негативним значенням. Чим вище привілеї процесу, тим менше часу він буде проводити в чергах. Пріоритет може призначатися директивно адміністратором системи в залежності від важливості роботи або внесеної плати, або обчислюватися самою ОС за визначеними правилами, він може залишатися фіксованим протягом усього життя процесу або змінюватися в часі відповідно до деякого закону. В останньому випадку пріоритети називаються динамічними. Існує два різновиди пріоритетних алгоритмів: алгоритми, що використовують відносні пріоритети, і алгоритми, які використовують абсолютні пріоритети. В обох випадках вибір процесу на виконання з черги готових здійснюється однаково: вибирається процес, що має найвищий пріоритет. По різному вирішується проблема визначення моменту зміни активного процесу. У системах з відносними пріоритетами активний процес виконується до тих пір, поки він сам не покине процесор, перейшовши в стан ОЧІКУВАННЯ (чи ж станеться помилка, чи процес завершиться). У системах з абсолютними пріоритетами виконання активного процесу переривається ще при одній умові: якщо в черзі готових процесів з'явився процес, пріоритет якого вище пріоритету активного процесу. У цьому випадку перерваний процес переходить у стан готовності. На малюнку 2.2 показані графи станів процесу для алгоритмів з відносними (а) і абсолютними (б) пріоритетами.
Рис. 2.2. Графи станів процесів у системах (а) з відносними пріоритетами; (б) з абсолютними пріоритетами
У багатьох операційних системах алгоритми планування побудовані з використанням як квантування, так і пріоритетів. Наприклад, в основі планування лежить квантування, але величина кванта і / або порядок вибору процесу з черги готових визначається пріоритетами процесів.
Витісняють і невитесняющая алгоритми планування
Існує два основних типи процедур планування процесів - витісняють (divemptive) і не витісняє (non-divemptive).
Non-divemptive multitasking - невитесняющая багатозадачність - це спосіб планування процесів, при якому активний процес виконується до тих пір, поки він сам, з власної ініціативи, не віддасть управління планувальником операційної системи для того, щоб той вибрав з черги інший, готовий до виконання процес .
Preemptive multitasking - витісняє багатозадачність - це такий спосіб, при якому рішення про переключення процесора з виконання одного процесу на виконання іншого процесу приймається планувальником ОС, а не найактивнішою завданням.
Поняття divemptive і non-divemptive іноді ототожнюються з поняттями пріоритетних і беспріорітетних дисциплін, що зовсім невірно, а також з поняттями абсолютних і відносних пріоритетів, що невірно частково. Витісняюча і невитесняющая багатозадачність - це більш широкі поняття, ніж типи пріоритетності. Пріоритети задач можуть як використовуватися, так і не використовуватися і при витісняють, і при витісняє способах планування. Так у випадку використання пріоритетів дисципліна відносних пріоритетів може бути віднесена до класу систем з невитискаючої багатозадачністю, а дисципліна абсолютних пріоритетів - до класу систем з витісняючою багатозадачністю. А беспріорітетная дисципліна планування, заснована на виділенні рівних квантів часу для всіх задач, відноситься до витісняючим алгоритмам.
Основною відмінністю між divemptive і non-divemptive варіантами багатозадачності є ступінь централізації механізму планування задач. При витісняючої багатозадачності механізм планування задач цілком зосереджений в операційній системі, і програміст пише свій додаток, не піклуючись про те, що воно буде виконуватися паралельно з іншими завданнями. При цьому операційна система виконує такі функції: визначає момент зняття з виконання активної задачі, запам'ятовує її контекст, вибирає з черги готових задач наступну і запускає її на виконання, завантажуючи її контекст.
При невитискаючої багатозадачності механізм планування розподілений між системою і прикладними програмами. Прикладна програма, отримавши управління від операційної системи, сама визначає момент завершення своєї чергової ітерації і передає керування ОС за допомогою якого-небудь системного виклику, а ОС формує черги задач і вибирає відповідно до деякого алгоритмом (наприклад, з урахуванням пріоритетів) наступну задачу на виконання. Такий механізм створює проблеми як для користувачів, так і для розробників. Для користувачів це означає, що управління системою губиться на довільний період часу, який визначається додатком (а не користувачем). Якщо програма витрачає занадто багато часу на виконання якої-небудь роботи, наприклад, на форматування диска, користувач не може переключитися з цього завдання на інше завдання, наприклад, на текстовий редактор, в той час як форматування тривало б у фоновому режимі. Ця ситуація небажана, оскільки користувачі зазвичай не хочуть довго чекати, коли машина завершить своє завдання. Тому розробники додатків для non-divemptive операційного середовища, покладаючи на себе функції планувальника, повинні створювати додатки так, щоб вони виконували свої завдання невеликими частинами. Наприклад, програма форматування може відформатувати одну доріжку дискети і повернути управління системі. Після виконання інших завдань система поверне управління програмі форматування, щоб та відформатована наступну доріжку. Подібний метод поділу часу між завданнями працює, але він істотно ускладнює розробку програм і висуває підвищені вимоги до кваліфікації програміста. Програміст повинен забезпечити "дружнє" ставлення своєї програми до інших виконуваних одночасно з нею програмами, досить часто віддаючи їм керування. Крайнім проявом "недружній" додатка є його зависання, яке призводить до загального краху системи. У системах з витісняючою багатозадачністю такі ситуації, як правило, виключені, так як центральний планує механізм зніме завислу завдання з виконання. Однак розподіл функцій планувальника між системою і додатками не завжди є недоліком, а за певних умов може бути і перевагою, тому що дає можливість розробнику додатків самому проектувати алгоритм планування, найбільш підходящий для даного фіксованого набору задач. Так як розробник сам визначає в програмі момент часу віддачі керування, то при цьому виключаються нераціональні переривання програм у "незручні" для них моменти часу. Крім того, легко дозволяються проблеми спільного використання даних: задача під час кожної ітерації використовує їх монопольно і впевнена, що протягом цього періоду ніхто іншої не змінить ці дані. Істотною перевагою non-divemptive систем є більш висока швидкість переключення з задачі на задачу. Прикладом ефективного використання невитискаючої багатозадачності є файл-сервер NetWare, у якому, в значній мірі завдяки цьому, досягнута висока швидкість виконання файлових операцій. Менш вдалим виявилося використання невитискаючої багатозадачності в операційному середовищі Windows 3.х. Однак майже у всіх сучасних операційних системах, орієнтованих на високопродуктивне виконання додатків (UNIX, Windows NT, OS / 2, VAX / VMS), реалізована витісняє багатозадачність. Останнім часом дійшла черга і до ОС класу настільних систем, наприклад, OS / 2 Warp і Windows 95. Можливо в зв'язку з цим витісняючу багатозадачність часто називають істинної мно
Засоби синхронізації та взаємодії процесів. Проблема синхронізації
Процесам часто потрібно взаємодіяти один з одним, наприклад, один процес може передавати дані іншому процесу, або декілька процесів можуть обробляти дані із загального файлу. У всіх цих випадках виникає проблема синхронізації процесів, яка може вирішуватися призупиненням і активізацією процесів, організацією черг, блокуванням та звільненням ресурсів.
Рис. 2.3. Приклад необхідності синхронізації
Нехтування питаннями синхронізації процесів, що виконуються в режимі мультипрограмування, може призвести до їх неправильної роботі або навіть до краху системи. Розглянемо, наприклад (малюнок 2.3), програму друку файлів (принт-сервер). Ця програма друкує по черзі всі файли, імена яких послідовно в порядку надходження записують у спеціальний загальнодоступний файл "замовлень" інші програми. Особлива мінлива NEXT, також доступна всім процесам-клієнтам, містить номер першої вільної для запису імені файлу позиції файлу "замовлень". Процеси-клієнти читають цю змінну, записують у відповідну позицію файлу "замовлень" ім'я свого файла і нарощують значення NEXT на одиницю. Припустимо, що в деякий момент процес R вирішив роздрукувати свій файл, для цього він прочитав значення змінної NEXT, значення якої для визначеності припустимо рівним 4. Процес запам'ятав це значення, але помістити ім'я файлу не встиг, оскільки його виконання було перервано (наприклад, в наслідок вичерпання кванта). Черговий процес S, бажаючий роздрукувати файл, прочитав те ж саме значення змінної NEXT, помістив у четверту позицію ім'я свого файлу і наростив значення змінної на одиницю. Коли в черговий раз управління буде передано процесу R, то він, продовжуючи своє виконання, у повній відповідності зі значенням поточної вільної позиції, отриманим під час попередньої ітерації, запише ім'я файлу також в позицію 4, поверх імені файлу процесу S.
Найважливішою частиною операційної системи, що безпосередньо впливає на функціонування обчислювальної машини, є підсистема керування процесами. Процес (або по-іншому, завдання) - абстракція, що описує, які виконуються. Для операційної системи процес являє собою одиницю роботи, заявку на споживання системних ресурсів. Підсистема управління процесами планує виконання процесів, тобто розподіляє процесорний час між декількома одночасно існуючими в системі процесами, а також займається створенням і знищенням процесів, забезпечує процеси необхідними системними ресурсами, підтримує взаємодію між процесами.
Стан процесів
У багатозадачній (багатопроцесорний) системі процес може знаходитися в одному з трьох основних станів:
ВИКОНАННЯ - активний стан процесу, під час якого процес володіє всіма необхідними ресурсами і безпосередньо виконується процесором;
ОЧІКУВАННЯ - пасивний стан процесу, процес заблокований, він не може виконуватися по своїх внутрішніх причин, він чекає здійснення деякої події, наприклад, завершення операції введення-виведення, одержання повідомлення від іншого процесу, звільнення якого-небудь необхідного йому ресурсу;
ГОТОВНІСТЬ - також пасивний стан процесу, але в цьому випадку процес заблокований у зв'язку з зовнішніми по відношенню до нього обставинами: процес має всі необхідні для нього ресурси, він готовий виконуватися, однак процесор зайнятий виконанням іншого процесу.
У ході життєвого циклу кожен процес переходить з одного стану в інший відповідно до алгоритму планування процесів, реалізованим у даній операційній системі. Типовий граф станів процесу показаний на малюнку 2.1.
У стані ВИКОНАННЯ у однопроцесорній системі може знаходитися тільки один процес, а в кожному зі станів ОЧІКУВАННЯ і ГОТОВНІСТЬ - кілька процесів, ці процеси утворюють черги відповідно очікують і готових процесів. Життєвий цикл процесу починається зі стану ГОТОВНІСТЬ, коли процес готовий до виконання і чекає своєї черги. При активізації процес переходить у стан ВИКОНАННЯ і знаходиться в ньому до тих пір, поки або він сам звільнить процесор, перейшовши в стан ОЧІКУВАННЯ якої-небудь події, або буде насильно "витиснутий" із процесора, наприклад, внаслідок вичерпання відведеного даному процесу кванта процесорного часу . В останньому випадку процес повертається в стан ГОТОВНІСТЬ. У цей же стан процес переходить зі стану ОЧІКУВАННЯ, після того, як очікуване подія відбудеться.
Рис. 2.1. Граф станів процесу в багатозадачному середовищі
Контекст і дескриптор процесу
Протягом існування процесу його виконання може бути багаторазово перерване і продовжене. Для того, щоб відновити виконання процесу, необхідно відновити стан його операційного середовища. Стан операційного середовища відображається станом регістрів і програмного лічильника, режимом роботи процесора, покажчиками на відкриті файли, інформацією про незавершені операції введення-виведення, кодами помилок виконуваних даним процесом системних викликів і т.д. Ця інформація називається контекстом процесу.
Крім цього, операційної системи для реалізації планування процесів потрібна додаткова інформація: ідентифікатор процесу, стан процесу, дані про ступінь привілейованості процесу, місце знаходження кодового сегмента й інша інформація. У деяких ОС (наприклад, в ОС UNIX) інформацію такого роду, використовувану ОС для планування процесів, називають дескриптором процесу.
Дескриптор процесу в порівнянні з контекстом містить більш оперативну інформацію, яка повинна бути легко доступна підсистемі планування процесів. Контекст процесу містить менш актуальну інформацію і використовується операційною системою тільки після того, як прийнято рішення про відновлення перерваного процесу.
Черги процесів являють собою дескриптори окремих процесів, об'єднані в списки. Таким чином, кожен дескриптор, крім всього іншого, містить принаймні один покажчик на інший дескриптор, що є сусідами з ним в черзі. Така організація черг дозволяє легко їх переупорядочівать, включати і виключати процеси, переводити процеси з одного стану в інший.
Програмний код тільки тоді почне виконуватися, коли для нього операційною системою буде створений процес.
Створити процес - це значить:
створити інформаційні структури, що описують даний процес, тобто його дескриптор і контекст;
включити дескриптор нового процесу в чергу готових процесів;
завантажити кодовий сегмент процесу в оперативну пам'ять або в область свопінгу.
Алгоритми планування процесів
Планування процесів містить у собі рішення наступних завдань:
визначення моменту часу для зміни виконуваного процесу;
вибір процесу на виконання з черги готових процесів;
перемикання контекстів "старого" і "нового" процесів.
Перші два завдання вирішуються програмними засобами, а остання значною мірою апаратно (див. розділ 2.3. "Засоби апаратної підтримки управління пам'яттю і багатозадачного середовища в мікропроцесорах Intel 80386, 80486 і Pentium").
Існує безліч різних алгоритмів планування процесів, по різному вирішують перераховані вище завдання, переслідують різні цілі і забезпечують різну якість мультипрограмування. Серед цієї безлічі алгоритмів розглянемо докладніше дві групи найбільш часто зустрічаються алгоритмів: алгоритми, засновані на квантуванні, і алгоритми, засновані на пріоритетах.
Відповідно з алгоритмами, заснованими на квантуванні, зміна активного процесу відбувається, якщо:
процес завершився і залишив систему,
сталася помилка,
процес перейшов у стан ОЧІКУВАННЯ,
вичерпаний квант процесорного часу, відведений даному процесу.
Процес, який вичерпав свій квант, переводиться в стан ГОТОВНІСТЬ і чекає, коли йому буде наданий новий квант процесорного часу, а на виконання відповідно до певним правилом вибирається новий процес з черги готових. Таким чином, жоден процес не займає процесор надовго, тому квантування широко використовується в системах поділу часу. Граф станів процесу, зображений на малюнку 2.1, відповідає алгоритму планування, заснованому на квантуванні.
Кванти, виділювані процесам, можуть бути однаковими для всіх процесів чи різними. Кванти, виділювані одному процесу, можуть бути фіксованої величини або змінюватися в різні періоди життя процесу. Процеси, які не повністю використали виділений їм квант (наприклад, через відхід на виконання операцій введення-виведення), можуть отримати або не отримати компенсацію у вигляді привілеїв при наступному обслуговуванні. По різному може бути організована чергу готових процесів: циклічно, за правилом "перший прийшов - першим обслужений" (FIFO) чи за правилом "останній прийшов - перший обслужити" (LIFO). Інша група алгоритмів використовує поняття "пріоритет" процесу. Пріоритет - це число, що характеризує ступінь привілейованості процесу при використанні ресурсів обчислювальної машини, зокрема, процесорного часу: чим вищий пріоритет, тим вище привілеї. Пріоритет може виражатися цілими чи дробовими, позитивним чи негативним значенням. Чим вище привілеї процесу, тим менше часу він буде проводити в чергах. Пріоритет може призначатися директивно адміністратором системи в залежності від важливості роботи або внесеної плати, або обчислюватися самою ОС за визначеними правилами, він може залишатися фіксованим протягом усього життя процесу або змінюватися в часі відповідно до деякого закону. В останньому випадку пріоритети називаються динамічними. Існує два різновиди пріоритетних алгоритмів: алгоритми, що використовують відносні пріоритети, і алгоритми, які використовують абсолютні пріоритети. В обох випадках вибір процесу на виконання з черги готових здійснюється однаково: вибирається процес, що має найвищий пріоритет. По різному вирішується проблема визначення моменту зміни активного процесу. У системах з відносними пріоритетами активний процес виконується до тих пір, поки він сам не покине процесор, перейшовши в стан ОЧІКУВАННЯ (чи ж станеться помилка, чи процес завершиться). У системах з абсолютними пріоритетами виконання активного процесу переривається ще при одній умові: якщо в черзі готових процесів з'явився процес, пріоритет якого вище пріоритету активного процесу. У цьому випадку перерваний процес переходить у стан готовності. На малюнку 2.2 показані графи станів процесу для алгоритмів з відносними (а) і абсолютними (б) пріоритетами.
Рис. 2.2. Графи станів процесів у системах (а) з відносними пріоритетами; (б) з абсолютними пріоритетами
У багатьох операційних системах алгоритми планування побудовані з використанням як квантування, так і пріоритетів. Наприклад, в основі планування лежить квантування, але величина кванта і / або порядок вибору процесу з черги готових визначається пріоритетами процесів.
Витісняють і невитесняющая алгоритми планування
Існує два основних типи процедур планування процесів - витісняють (divemptive) і не витісняє (non-divemptive).
Non-divemptive multitasking - невитесняющая багатозадачність - це спосіб планування процесів, при якому активний процес виконується до тих пір, поки він сам, з власної ініціативи, не віддасть управління планувальником операційної системи для того, щоб той вибрав з черги інший, готовий до виконання процес .
Preemptive multitasking - витісняє багатозадачність - це такий спосіб, при якому рішення про переключення процесора з виконання одного процесу на виконання іншого процесу приймається планувальником ОС, а не найактивнішою завданням.
Поняття divemptive і non-divemptive іноді ототожнюються з поняттями пріоритетних і беспріорітетних дисциплін, що зовсім невірно, а також з поняттями абсолютних і відносних пріоритетів, що невірно частково. Витісняюча і невитесняющая багатозадачність - це більш широкі поняття, ніж типи пріоритетності. Пріоритети задач можуть як використовуватися, так і не використовуватися і при витісняють, і при витісняє способах планування. Так у випадку використання пріоритетів дисципліна відносних пріоритетів може бути віднесена до класу систем з невитискаючої багатозадачністю, а дисципліна абсолютних пріоритетів - до класу систем з витісняючою багатозадачністю. А беспріорітетная дисципліна планування, заснована на виділенні рівних квантів часу для всіх задач, відноситься до витісняючим алгоритмам.
Основною відмінністю між divemptive і non-divemptive варіантами багатозадачності є ступінь централізації механізму планування задач. При витісняючої багатозадачності механізм планування задач цілком зосереджений в операційній системі, і програміст пише свій додаток, не піклуючись про те, що воно буде виконуватися паралельно з іншими завданнями. При цьому операційна система виконує такі функції: визначає момент зняття з виконання активної задачі, запам'ятовує її контекст, вибирає з черги готових задач наступну і запускає її на виконання, завантажуючи її контекст.
При невитискаючої багатозадачності механізм планування розподілений між системою і прикладними програмами. Прикладна програма, отримавши управління від операційної системи, сама визначає момент завершення своєї чергової ітерації і передає керування ОС за допомогою якого-небудь системного виклику, а ОС формує черги задач і вибирає відповідно до деякого алгоритмом (наприклад, з урахуванням пріоритетів) наступну задачу на виконання. Такий механізм створює проблеми як для користувачів, так і для розробників. Для користувачів це означає, що управління системою губиться на довільний період часу, який визначається додатком (а не користувачем). Якщо програма витрачає занадто багато часу на виконання якої-небудь роботи, наприклад, на форматування диска, користувач не може переключитися з цього завдання на інше завдання, наприклад, на текстовий редактор, в той час як форматування тривало б у фоновому режимі. Ця ситуація небажана, оскільки користувачі зазвичай не хочуть довго чекати, коли машина завершить своє завдання. Тому розробники додатків для non-divemptive операційного середовища, покладаючи на себе функції планувальника, повинні створювати додатки так, щоб вони виконували свої завдання невеликими частинами. Наприклад, програма форматування може відформатувати одну доріжку дискети і повернути управління системі. Після виконання інших завдань система поверне управління програмі форматування, щоб та відформатована наступну доріжку. Подібний метод поділу часу між завданнями працює, але він істотно ускладнює розробку програм і висуває підвищені вимоги до кваліфікації програміста. Програміст повинен забезпечити "дружнє" ставлення своєї програми до інших виконуваних одночасно з нею програмами, досить часто віддаючи їм керування. Крайнім проявом "недружній" додатка є його зависання, яке призводить до загального краху системи. У системах з витісняючою багатозадачністю такі ситуації, як правило, виключені, так як центральний планує механізм зніме завислу завдання з виконання. Однак розподіл функцій планувальника між системою і додатками не завжди є недоліком, а за певних умов може бути і перевагою, тому що дає можливість розробнику додатків самому проектувати алгоритм планування, найбільш підходящий для даного фіксованого набору задач. Так як розробник сам визначає в програмі момент часу віддачі керування, то при цьому виключаються нераціональні переривання програм у "незручні" для них моменти часу. Крім того, легко дозволяються проблеми спільного використання даних: задача під час кожної ітерації використовує їх монопольно і впевнена, що протягом цього періоду ніхто іншої не змінить ці дані. Істотною перевагою non-divemptive систем є більш висока швидкість переключення з задачі на задачу. Прикладом ефективного використання невитискаючої багатозадачності є файл-сервер NetWare, у якому, в значній мірі завдяки цьому, досягнута висока швидкість виконання файлових операцій. Менш вдалим виявилося використання невитискаючої багатозадачності в операційному середовищі Windows 3.х. Однак майже у всіх сучасних операційних системах, орієнтованих на високопродуктивне виконання додатків (UNIX, Windows NT, OS / 2, VAX / VMS), реалізована витісняє багатозадачність. Останнім часом дійшла черга і до ОС класу настільних систем, наприклад, OS / 2 Warp і Windows 95. Можливо в зв'язку з цим витісняючу багатозадачність часто називають істинної мно
Засоби синхронізації та взаємодії процесів. Проблема синхронізації
Процесам часто потрібно взаємодіяти один з одним, наприклад, один процес може передавати дані іншому процесу, або декілька процесів можуть обробляти дані із загального файлу. У всіх цих випадках виникає проблема синхронізації процесів, яка може вирішуватися призупиненням і активізацією процесів, організацією черг, блокуванням та звільненням ресурсів.
Рис. 2.3. Приклад необхідності синхронізації
Нехтування питаннями синхронізації процесів, що виконуються в режимі мультипрограмування, може призвести до їх неправильної роботі або навіть до краху системи. Розглянемо, наприклад (малюнок 2.3), програму друку файлів (принт-сервер). Ця програма друкує по черзі всі файли, імена яких послідовно в порядку надходження записують у спеціальний загальнодоступний файл "замовлень" інші програми. Особлива мінлива NEXT, також доступна всім процесам-клієнтам, містить номер першої вільної для запису імені файлу позиції файлу "замовлень". Процеси-клієнти читають цю змінну, записують у відповідну позицію файлу "замовлень" ім'я свого файла і нарощують значення NEXT на одиницю. Припустимо, що в деякий момент процес R вирішив роздрукувати свій файл, для цього він прочитав значення змінної NEXT, значення якої для визначеності припустимо рівним 4. Процес запам'ятав це значення, але помістити ім'я файлу не встиг, оскільки його виконання було перервано (наприклад, в наслідок вичерпання кванта). Черговий процес S, бажаючий роздрукувати файл, прочитав те ж саме значення змінної NEXT, помістив у четверту позицію ім'я свого файлу і наростив значення змінної на одиницю. Коли в черговий раз управління буде передано процесу R, то він, продовжуючи своє виконання, у повній відповідності зі значенням поточної вільної позиції, отриманим під час попередньої ітерації, запише ім'я файлу також в позицію 4, поверх імені файлу процесу S.
Таким чином, процес S ніколи не побачить свій файл роздрукованим. Складність проблеми синхронізації полягає в нерегулярності ситуацій, що виникають: у попередньому прикладі можна уявити й інший розвиток подій: були втрачені файли декількох процесів або, навпаки, не був втрачений жоден файл. У даному випадку все визначається взаємними швидкостями процесів і моментами їх переривання. Тому налагодження взаємодіючих процесів є складним завданням. Ситуації подібні тій, коли два або більше процесів обробляють колективні дані, і кінцевий результат залежить від співвідношення швидкостей процесів, називаються гонками.
Критична секція
Важливим поняттям синхронізації процесів є поняття "критична секція" програми. Критична секція - це частина програми, в якій здійснюється доступ до даних, що розділяються. Щоб виключити ефект гонок по відношенню до деякого ресурсу, необхідно забезпечити, щоб у кожен момент в критичній секції, зв'язаної з цим ресурсом, перебував максимум один процес. Цей прийом називають взаємним виключенням.
Найпростіший спосіб забезпечити взаємне виключення - дозволити процесу, що знаходиться в критичній секції, забороняти все переривання. Однак цей спосіб не годиться, тому що небезпечно довіряти управління системою для користувача процесу, він може надовго зайняти процесор, а при краху процесу в критичній області крах потерпить вся система, тому що переривання ніколи не будуть дозволені.
Іншим способом є використання блокуючих змінних. З кожним ресурсом зв'язується двійкова змінна, яка приймає значення 1, якщо ресурс вільний (тобто ні один процес не знаходиться в даний момент в критичній секції, пов'язаною з цим процесом), і значення 0, якщо ресурс зайнятий. На малюнку 2.4 показаний фрагмент алгоритму процесу, що використовує для реалізації взаємного виключення доступу до ресурсу D блокує змінну F (D). Перед входом в критичну секцію процес перевіряє, чи вільний ресурс D. Якщо він зайнятий, то перевірка циклічно повторюється, якщо вільний, то значення змінної F (D) встановлюється в 0, і процес входить в критичну секцію. Після того, як процес виконає всі дії з ресурсом D, значення змінної F (D) знову встановлюється рівним 1.
Рис. 2.4. Реалізація критичних секцій з використанням блокуючих змінних
Якщо всі процеси написані з використанням вищеописаних угод, то взаємне виключення гарантується. Слід зауважити, що операція перевірки та встановлення блокує змінної повинна бути неподільною. Пояснимо це. Нехай у результаті перевірки змінної процес визначив, що ресурс вільний, але відразу після цього, не встигнувши встановити змінну в 0, був перерваний. За час його призупинення інший процес зайняв ресурс, увійшов у свою критичну секцію, але також був перерваний, не завершивши роботи з ресурсом. Коли управління було повернуто перший процесу, він, вважаючи ресурс вільним, встановив ознака зайнятості і почав виконувати свою критичну секцію. Таким чином був порушений принцип взаємного виключення, що потенційно може призвести до небажаних наслідків. Щоб уникнути таких ситуацій у системі команд машини бажано мати єдину команду "перевірка-установка", або ж реалізовувати системними засобами відповідні програмні примітиви, які б забороняли переривання протягом всієї операції перевірки та встановлення.
Реалізація критичних секцій з використанням блокуючих змінних має істотний недолік: протягом часу, коли один процес знаходиться в критичній секції, інший процес, якому потрібен той же ресурс, буде виконувати рутинні дії за опитуванням блокує змінної, марно витрачаючи процесорний час. Для усунення таких ситуацій може бути використаний так званий апарат подій. За допомогою цього засобу можуть вирішуватися не тільки проблеми взаємного виключення, але й більш загальні завдання синхронізації процесів. У різних операційних системах апарат подій реалізується по своєму, але в будь-якому випадку використовуються системні функції аналогічного призначення, які умовно назвемо WAIT (x) і POST (x), де x - ідентифікатор деякої події. На малюнку 2.5 показаний фрагмент алгоритму процесу, що використовує ці функції. Якщо ресурс зайнятий, то процес не виконує циклічний опитування, а викликає системну функцію WAIT (D), тут D позначає подія, що полягає у звільненні ресурсу D. Функція WAIT (D) переводить активний процес в стан ОЧІКУВАННЯ і робить відмітку в його дескрипторі про те, що процес чекає події D. Процес, який в цей час використовує ресурс D, після виходу з критичної секції виконує системну функцію POST (D), в результаті чого операційна система переглядає чергу очікують процесів і переводить процес, що очікує події D, в стан ГОТОВНІСТЬ.
Узагальнююче засіб синхронізації процесів запропонував Дейкстра, який ввів два нових примітиву. В абстрактній формі ці примітиви, що позначаються P і V, оперують над цілими невід'ємними змінними, званими семафорами. Нехай S такий семафор. Операції визначаються наступним чином:
V (S): мінлива S збільшується на 1 одним неподільним дією; вибірка, інкремент та запам'ятовування не можуть бути перервані, і до S немає доступу іншим процесам під час виконання цієї операції.
P (S): зменшення S на 1, якщо це можливо. Якщо S = 0, то неможливо зменшити S і залишитися в області цілих невід'ємних значень, в цьому випадку процес, що викликає P-операцію, чекає, поки це зменшення стане можливим. Успішна перевірка і зменшення також є неподільною операцією.
Рис. 2.5. Реалізація критичної секції з використанням системних функцій WAIT (D) і POST (D)
В окремому випадку, коли семафор S може приймати тільки значення 0 і 1, він перетворюється на блокуючу змінну. Операція P містить в собі потенційну можливість переходу процесу, який її виконує, в стан очікування, в той час як V-операція може за деяких обставин активізувати інший процес, призупинений операцією P (порівняйте ці операції з системними функціями WAIT і POST).
Розглянемо використання семафорів на класичному прикладі взаємодії двох процесів, що виконуються в режимі мультипрограмування, один з яких пише дані в буферний пул, а інший зчитує їх з буферного пула. Нехай буферний пул складається з N буферів, кожний з яких може містити один запис. Процес "письменник" повинен припинятися, коли всі буфери опиняються зайнятими, і активізуватися при звільненні хоча б одного буфера. Навпаки, процес "читач" припиняється, коли всі буфери порожні, і активізується при появі хоч би одного запису.
Введемо два семафора: e - число порожніх буферів і f - число заповнених буферів. Припустимо, що запис у буфер і зчитування з буфера є критичними секціями (як у прикладі з принт-сервером на початку цього розділу). Введемо також двійковий семафор b, який використовується для забезпечення взаємного виключення. Тоді процеси можуть бути описані в такий спосіб:
/ / Глобальні змінні
# Define N 256
int e = N, f = 0, b = 1;
void Writer ()
while (1)
PrepareNextRecord (); / * підготовка нового запису * /
P (e) / * Зменшити число вільних буферів, якщо вони є * /
/ * У противному випадку - чекати, поки вони звільняться * /
P (b) / * Вхід в критичну секцію * /
AddToBuffer (); / * Додати новий запис у буфер * /
V (b) / * Вихід з критичної секції * /
V (f) / * Збільшити число зайнятих буферів * /
void Reader ()
while (1)
P (f) / * Зменшити число зайнятих буферів, якщо вони є * /
/ * У противному разі чекати, поки вони з'являться * /
P (b) / * Вхід в критичну секцію * /
GetFromBuffer (); / * Взяти запис з буфера * /
V (b) / * Вихід з критичної секції * /
V (e) / * Збільшити число вільних буферів * /
ProcessRecord (); / * Опрацювати запис * /
Тупики
Наведений вище приклад допоможе нам проілюструвати ще одну проблему синхронізації - взаємні блокування, звані також дедлок (deadlocks), клінчами (clinch) або тупиками. Якщо переставити місцями операції P (e) і P (b) у програмі "письменника", то при деякому збігу обставин ці два процеси можуть взаємно заблокувати один одного. Дійсно, нехай "письменник" першим увійде в критичну секцію та виявить відсутність вільних буферів; він почне чекати, коли "читач" візьме чергову запис з буфера, але "читач" не зможе цього зробити, тому що для цього необхідно увійти в критичну секцію, вхід до якої заблоковано процесом "письменником".
Розглянемо ще один приклад глухого кута. Нехай двох процесів, що виконується в режимі мультипрограмування, для виконання їхньої роботи потрібно два ресурси, наприклад, принтер і диск. На малюнку 2.6, а показані фрагменти відповідних програм. І нехай після того, як процес А зайняв принтер (встановив блокує змінну), він був перерваний. Управління отримав процес В, який спочатку зайняв диск, але при виконанні наступної команди був заблокований, так як принтер виявився вже зайнятим процесом А. Управління знову отримав процес А, який у відповідності зі своєю програмою зробив спробу зайняти диск і був заблокований: диск вже розподілено процесу В. У такому положенні процеси А і В можуть знаходитися як завгодно довго.
У залежності від співвідношення швидкостей процесів, вони можуть або цілком незалежно використовувати колективні ресурси (г), або утворювати черги до ресурсів (в), або взаємно блокувати один одного (б). Тупикові ситуації треба відрізняти від простих черг, хоча і ті й інші виникають при спільному використанні ресурсів і зовні виглядають схоже: процес призупиняється і чекає звільнення ресурсу. Однак чергу - це нормальне явище, невід'ємною ознакою високого коефіцієнта використання ресурсів при випадковому надходженні запитів. Вона виникає тоді, коли ресурс недоступний в даний момент, але через деякий час він звільняється, і процес продовжує своє виконання. Тупик ж, що видно з його назви, є до певної міри нерозв'язною ситуацією.
У розглянутих прикладах глухий кут був утворений двома процесами, але взаємно блокувати один одного можуть і більше число процесів.
Проблема тупиків включає в себе наступні завдання:
- Запобігання тупиків,
- Розпізнавання тупиків,
- Відновлення системи після тупиків.
Рис. 2.6. (A) фрагменти програм А і В, які поділяють принтер і диск; (б) взаємне блокування (клінч); (в) чергу до разделяемому диску; (г) незалежне використання ресурсів
Тупики можуть бути запобігти на стадії написання програм, тобто програми повинні бути написані таким чином, щоб глухий кут не міг виникнути ні при якому співвідношенні взаємних швидкостей процесів. Так, якщо б у попередньому прикладі процес А і процес У запитували ресурси в однаковій послідовності, то глухий кут був би в принципі неможливий. Другий підхід до запобігання тупиків називається динамічним і полягає у використанні певних правил при призначенні ресурсів процесам, наприклад, ресурси можуть виділятися в певній послідовності, загальною для всіх процесів.
У деяких випадках, коли тупикова ситуація утворена багатьма процесами, що використовують багато ресурсів, розпізнавання глухого кута є нетривіальним завданням. Існують формальні, програмно-реалізовані методи розпізнавання тупиків, засновані на веденні таблиць розподілу ресурсів і таблиць запитів до зайнятих ресурсів. Аналіз цих таблиць дозволяє виявити взаємні блокування.
Якщо ж тупикова ситуація виникла, то не обов'язково знімати з виконання всі заблоковані процеси. Можна зняти тільки частину з них, при цьому звільняються ресурси, очікувані іншими процесами, можна повернути деякі процеси в область свопінгу, можна зробити "відкат" деяких процесів до так званої контрольної точки, в якій запам'ятовується вся інформація, необхідна для відновлення виконання програми з даного місця. Контрольні точки розставляються в програмі в місцях, після яких можливе виникнення безвиході.
З усього вищесказаного ясно, що використовувати семафори потрібно дуже обережно, тому що одна незначна помилка може призвести до зупинки системи. Для того, щоб полегшити написання коректних програм, було запропоновано високорівневий засіб синхронізації, зване монітором. Монітор - це набір процедур, змінних і структур даних. Процеси можуть викликати процедури монітора, але не мають доступу до внутрішніх даних монітора. Монітори мають важливе властивість, яка робить їх корисними для досягнення взаємного виключення: тільки один процес може бути активним по відношенню до монітора. Компілятор обробляє виклики процедур монітора особливим чином. Зазвичай, коли процес викликає процедуру монітора, то перші кілька інструкцій цієї процедури перевіряють, не активний може який-небудь інший процес по відношенню до цього монітора. Якщо так, то зухвалий процес припиняється, поки інший процес не звільнить монітор. Таким чином, виключення входу декількох процесів в монітор реалізується не програмістом, а компілятором, що робить помилки менш імовірними.
У розподілених системах, що складаються з декількох процесорів, кожний з яких має власну оперативну пам'ять, семафори та монітори виявляються непридатними. У таких системах синхронізація може бути реалізована тільки за допомогою обміну повідомленнями. Докладніше про це дивіться у розділі "Синхронізація в розподілених системах".
Нитки
Багатозадачність є найважливішою властивістю ОС. Для підтримки цієї властивості ОС визначає й оформляє для себе ті внутрішні одиниці роботи, між якими і буде розділятися процесор і інші ресурси комп'ютера. Ці внутрішні одиниці роботи в різних ОС носять різні назви - задача, завдання, процес, нитка. У деяких випадках сутності, що позначаються цими поняттями, принципово відрізняються один від одного.
Говорячи про процеси, ми відзначали, що операційна система підтримує їх відособленість: у кожного процесу є своє віртуальний адресний простір, кожному процесу призначаються свої ресурси - файли, вікна, семафори і т.д. Така відособленість потрібна для того, щоб захистити один процес від іншого, оскільки вони, спільно використовуючи всі ресурси машини, конкурують один з одним. У загальному випадку процеси належать різним користувачам, що розділяють один комп'ютер, і ОС бере на себе роль арбітра в суперечках процесів за ресурси.
При мультипрограмування підвищується пропускна здатність системи, але окремий процес ніколи не може бути виконаний швидше, ніж якщо б він виконувався в однопрограмних режимі (всяке поділ ресурсів сповільнює роботу одного з учасників за рахунок додаткових витрат часу на очікування звільнення ресурсу). Проте завдання, яке вирішується в рамках одного процесу, може мати внутрішнім паралелізмом, який в принципі дозволяє прискорити її розв'язання. Наприклад, в ході виконання задачі відбувається звертання до зовнішньому пристрою, і на час цієї операції можна не блокувати повністю виконання процесу, а продовжити обчислення по іншій "гілки" процесу.
Для цих цілей сучасні ОС пропонують використовувати порівняно новий механізм багатонитковою обробки (multithreading). При цьому вводиться нове поняття "нитка" (thread), а поняття "процес" у значній мірі змінює зміст.
Мультипрограмування тепер реалізується на рівні ниток, і задача, оформлена у вигляді декількох ниток в рамках одного процесу, може бути виконана швидше за рахунок псевдопаралельною (або паралельного в мультипроцессорной системі) виконання її окремих частин. Наприклад, якщо електронна таблиця була розроблена з урахуванням можливостей багатонитковою обробки, то користувач може запросити перерахунок свого робочого листа й одночасно продовжувати заповнювати таблицю. Особливо ефективно можна використовувати багатонитковою для виконання розподілених додатків, наприклад, багатонитковою сервер може паралельно виконувати запити відразу декількох клієнтів.
Нитки, що відносяться до одного процесу, не настільки ізольовані один від одного, як процеси в традиційній багатозадачного системі, між ними легко організувати тісну взаємодію. Дійсно, на відміну від процесів, які належать різним, взагалі кажучи, конкуруючим додаткам, усі нитки одного процесу завжди належать одному додатку, тому програміст, що пише це додаток, може заздалегідь продумати роботу безлічі ниток процесу таким чином, щоб вони могли взаємодіяти, а не боротися за ресурси.
У традиційних ОС поняття "нитка" тотожно поняттю "процес". У дійсності часто буває бажано мати кілька ниток, що розділяють єдиний адресний простір, але виконуються квазіпараллельно, завдяки чому нитки стають подібними процесам (за винятком поділюваного адресного простору).
Нитки іноді називають полегшеними процесами чи міні-процесами. Дійсно, нитки в багатьох відносинах подібні процесам. Кожна нитка виконується строго послідовно і має свій власний програмний лічильник і стік. Нитки, як і процеси, можуть, наприклад, породжувати нитки-нащадки, можуть переходити зі стану в стан. Подібно традиційним процесам (тобто процесів, що складається з однієї нитки), нитки можуть знаходиться в одному з наступних станів: ВИКОНАННЯ, ОЧІКУВАННЯ і ГОТОВНІСТЬ. Поки одна нитка заблокована, інша нитка того ж процесу може виконуватися. Нитки розділяють процесор так, як це роблять процеси, у відповідності з різними варіантами планування.
Однак різні нитки в рамках одного процесу не настільки незалежні, як окремі процеси. Всі такі нитки мають одне і те ж адресний простір. Це означає, що вони поділяють одні й ті ж глобальні змінні. Оскільки кожна нитка може мати доступ до кожного віртуального адресою, одна нитка може використовувати стек іншої нитки. Між нитками немає повного захисту, тому що, по-перше, це неможливо, а по-друге, не потрібно. Усі нитки одного процесу завжди вирішують загальну задачу одного користувача, і апарат ниток використовується тут для більш швидкого рішення задачі шляхом її розпаралелювання. При цьому програмісту дуже важливо одержати у своє розпорядження зручні засоби організації взаємодії частин однієї задачі. Крім поділу адресного простору, всі нитки розділяють також набір відкритих файлів, таймерів, сигналів і т.п.
Отже, нитки мають власні:
- Програмний лічильник,
- Стік,
- Регістри,
- Нитки-нащадки,
- Стан.
- Нитки розділяють:
- Адресний простір,
- Глобальні змінні,
- Відкриті файли,
- Таймери,
- Семафори,
- Статистичну інформацію.
Багатонитковою обробка підвищує ефективність роботи системи в порівнянні з багатозадачною обробкою. Наприклад, у багатозадачному середовищі Windows можна одночасно працювати з електронною таблицею і текстовим редактором. Однак, якщо користувач запитує перерахування свого робочого листа, електронна таблиця блокується до тих пір, поки ця операція не завершиться, що може зажадати значного часу. У багатонитковою середовищу у випадку, якщо електронна таблиця була розроблена з урахуванням можливостей багатонитковою обробки, що надаються програмісту, цієї проблеми не виникає, і користувач завжди має доступ до електронної таблиці.
Широке застосування знаходить багатонитковою обробка в розподілених системах. Дивіться про це у розділі "Процеси і нитки в розподілених системах".
Деякі прикладні завдання легше програмувати, використовуючи паралелізм, наприклад задачі типу "письменник-читач", в яких одна нитка виконує запис у буфер, а інша зчитує записи з нього. Оскільки вони поділяють спільний буфер, не варто їх робити окремими процесами. Інший приклад використання ниток - це управління сигналами, такими як переривання з клавіатури (del або break). Замість обробки сигналу переривання, одна нитка призначається для постійного очікування надходження сигналів. Таким чином, використання ниток може скоротити необхідність в перериваннях користувацького рівня. У цих прикладах не настільки важливо паралельне виконання, наскільки важлива ясність програми.
Нарешті, в мультипроцесорних системах для ниток з одного адресного простору є можливість виконуватися паралельно на різних процесорах. Це дійсно один з головних шляхів реалізації поділу ресурсів у таких системах. З іншого боку, правильно сконструйовані програми, які використовують нитки, повинні працювати однаково добре як на однопроцесорній машині в режимі поділу часу між нитками, так і на справжньому мультипроцесорі.
Критична секція
Важливим поняттям синхронізації процесів є поняття "критична секція" програми. Критична секція - це частина програми, в якій здійснюється доступ до даних, що розділяються. Щоб виключити ефект гонок по відношенню до деякого ресурсу, необхідно забезпечити, щоб у кожен момент в критичній секції, зв'язаної з цим ресурсом, перебував максимум один процес. Цей прийом називають взаємним виключенням.
Найпростіший спосіб забезпечити взаємне виключення - дозволити процесу, що знаходиться в критичній секції, забороняти все переривання. Однак цей спосіб не годиться, тому що небезпечно довіряти управління системою для користувача процесу, він може надовго зайняти процесор, а при краху процесу в критичній області крах потерпить вся система, тому що переривання ніколи не будуть дозволені.
Іншим способом є використання блокуючих змінних. З кожним ресурсом зв'язується двійкова змінна, яка приймає значення 1, якщо ресурс вільний (тобто ні один процес не знаходиться в даний момент в критичній секції, пов'язаною з цим процесом), і значення 0, якщо ресурс зайнятий. На малюнку 2.4 показаний фрагмент алгоритму процесу, що використовує для реалізації взаємного виключення доступу до ресурсу D блокує змінну F (D). Перед входом в критичну секцію процес перевіряє, чи вільний ресурс D. Якщо він зайнятий, то перевірка циклічно повторюється, якщо вільний, то значення змінної F (D) встановлюється в 0, і процес входить в критичну секцію. Після того, як процес виконає всі дії з ресурсом D, значення змінної F (D) знову встановлюється рівним 1.
Рис. 2.4. Реалізація критичних секцій з використанням блокуючих змінних
Якщо всі процеси написані з використанням вищеописаних угод, то взаємне виключення гарантується. Слід зауважити, що операція перевірки та встановлення блокує змінної повинна бути неподільною. Пояснимо це. Нехай у результаті перевірки змінної процес визначив, що ресурс вільний, але відразу після цього, не встигнувши встановити змінну в 0, був перерваний. За час його призупинення інший процес зайняв ресурс, увійшов у свою критичну секцію, але також був перерваний, не завершивши роботи з ресурсом. Коли управління було повернуто перший процесу, він, вважаючи ресурс вільним, встановив ознака зайнятості і почав виконувати свою критичну секцію. Таким чином був порушений принцип взаємного виключення, що потенційно може призвести до небажаних наслідків. Щоб уникнути таких ситуацій у системі команд машини бажано мати єдину команду "перевірка-установка", або ж реалізовувати системними засобами відповідні програмні примітиви, які б забороняли переривання протягом всієї операції перевірки та встановлення.
Реалізація критичних секцій з використанням блокуючих змінних має істотний недолік: протягом часу, коли один процес знаходиться в критичній секції, інший процес, якому потрібен той же ресурс, буде виконувати рутинні дії за опитуванням блокує змінної, марно витрачаючи процесорний час. Для усунення таких ситуацій може бути використаний так званий апарат подій. За допомогою цього засобу можуть вирішуватися не тільки проблеми взаємного виключення, але й більш загальні завдання синхронізації процесів. У різних операційних системах апарат подій реалізується по своєму, але в будь-якому випадку використовуються системні функції аналогічного призначення, які умовно назвемо WAIT (x) і POST (x), де x - ідентифікатор деякої події. На малюнку 2.5 показаний фрагмент алгоритму процесу, що використовує ці функції. Якщо ресурс зайнятий, то процес не виконує циклічний опитування, а викликає системну функцію WAIT (D), тут D позначає подія, що полягає у звільненні ресурсу D. Функція WAIT (D) переводить активний процес в стан ОЧІКУВАННЯ і робить відмітку в його дескрипторі про те, що процес чекає події D. Процес, який в цей час використовує ресурс D, після виходу з критичної секції виконує системну функцію POST (D), в результаті чого операційна система переглядає чергу очікують процесів і переводить процес, що очікує події D, в стан ГОТОВНІСТЬ.
Узагальнююче засіб синхронізації процесів запропонував Дейкстра, який ввів два нових примітиву. В абстрактній формі ці примітиви, що позначаються P і V, оперують над цілими невід'ємними змінними, званими семафорами. Нехай S такий семафор. Операції визначаються наступним чином:
V (S): мінлива S збільшується на 1 одним неподільним дією; вибірка, інкремент та запам'ятовування не можуть бути перервані, і до S немає доступу іншим процесам під час виконання цієї операції.
P (S): зменшення S на 1, якщо це можливо. Якщо S = 0, то неможливо зменшити S і залишитися в області цілих невід'ємних значень, в цьому випадку процес, що викликає P-операцію, чекає, поки це зменшення стане можливим. Успішна перевірка і зменшення також є неподільною операцією.
Рис. 2.5. Реалізація критичної секції з використанням системних функцій WAIT (D) і POST (D)
В окремому випадку, коли семафор S може приймати тільки значення 0 і 1, він перетворюється на блокуючу змінну. Операція P містить в собі потенційну можливість переходу процесу, який її виконує, в стан очікування, в той час як V-операція може за деяких обставин активізувати інший процес, призупинений операцією P (порівняйте ці операції з системними функціями WAIT і POST).
Розглянемо використання семафорів на класичному прикладі взаємодії двох процесів, що виконуються в режимі мультипрограмування, один з яких пише дані в буферний пул, а інший зчитує їх з буферного пула. Нехай буферний пул складається з N буферів, кожний з яких може містити один запис. Процес "письменник" повинен припинятися, коли всі буфери опиняються зайнятими, і активізуватися при звільненні хоча б одного буфера. Навпаки, процес "читач" припиняється, коли всі буфери порожні, і активізується при появі хоч би одного запису.
Введемо два семафора: e - число порожніх буферів і f - число заповнених буферів. Припустимо, що запис у буфер і зчитування з буфера є критичними секціями (як у прикладі з принт-сервером на початку цього розділу). Введемо також двійковий семафор b, який використовується для забезпечення взаємного виключення. Тоді процеси можуть бути описані в такий спосіб:
/ / Глобальні змінні
# Define N 256
int e = N, f = 0, b = 1;
void Writer ()
while (1)
PrepareNextRecord (); / * підготовка нового запису * /
P (e) / * Зменшити число вільних буферів, якщо вони є * /
/ * У противному випадку - чекати, поки вони звільняться * /
P (b) / * Вхід в критичну секцію * /
AddToBuffer (); / * Додати новий запис у буфер * /
V (b) / * Вихід з критичної секції * /
V (f) / * Збільшити число зайнятих буферів * /
void Reader ()
while (1)
P (f) / * Зменшити число зайнятих буферів, якщо вони є * /
/ * У противному разі чекати, поки вони з'являться * /
P (b) / * Вхід в критичну секцію * /
GetFromBuffer (); / * Взяти запис з буфера * /
V (b) / * Вихід з критичної секції * /
V (e) / * Збільшити число вільних буферів * /
ProcessRecord (); / * Опрацювати запис * /
Тупики
Наведений вище приклад допоможе нам проілюструвати ще одну проблему синхронізації - взаємні блокування, звані також дедлок (deadlocks), клінчами (clinch) або тупиками. Якщо переставити місцями операції P (e) і P (b) у програмі "письменника", то при деякому збігу обставин ці два процеси можуть взаємно заблокувати один одного. Дійсно, нехай "письменник" першим увійде в критичну секцію та виявить відсутність вільних буферів; він почне чекати, коли "читач" візьме чергову запис з буфера, але "читач" не зможе цього зробити, тому що для цього необхідно увійти в критичну секцію, вхід до якої заблоковано процесом "письменником".
Розглянемо ще один приклад глухого кута. Нехай двох процесів, що виконується в режимі мультипрограмування, для виконання їхньої роботи потрібно два ресурси, наприклад, принтер і диск. На малюнку 2.6, а показані фрагменти відповідних програм. І нехай після того, як процес А зайняв принтер (встановив блокує змінну), він був перерваний. Управління отримав процес В, який спочатку зайняв диск, але при виконанні наступної команди був заблокований, так як принтер виявився вже зайнятим процесом А. Управління знову отримав процес А, який у відповідності зі своєю програмою зробив спробу зайняти диск і був заблокований: диск вже розподілено процесу В. У такому положенні процеси А і В можуть знаходитися як завгодно довго.
У залежності від співвідношення швидкостей процесів, вони можуть або цілком незалежно використовувати колективні ресурси (г), або утворювати черги до ресурсів (в), або взаємно блокувати один одного (б). Тупикові ситуації треба відрізняти від простих черг, хоча і ті й інші виникають при спільному використанні ресурсів і зовні виглядають схоже: процес призупиняється і чекає звільнення ресурсу. Однак чергу - це нормальне явище, невід'ємною ознакою високого коефіцієнта використання ресурсів при випадковому надходженні запитів. Вона виникає тоді, коли ресурс недоступний в даний момент, але через деякий час він звільняється, і процес продовжує своє виконання. Тупик ж, що видно з його назви, є до певної міри нерозв'язною ситуацією.
У розглянутих прикладах глухий кут був утворений двома процесами, але взаємно блокувати один одного можуть і більше число процесів.
Проблема тупиків включає в себе наступні завдання:
- Запобігання тупиків,
- Розпізнавання тупиків,
- Відновлення системи після тупиків.
Рис. 2.6. (A) фрагменти програм А і В, які поділяють принтер і диск; (б) взаємне блокування (клінч); (в) чергу до разделяемому диску; (г) незалежне використання ресурсів
Тупики можуть бути запобігти на стадії написання програм, тобто програми повинні бути написані таким чином, щоб глухий кут не міг виникнути ні при якому співвідношенні взаємних швидкостей процесів. Так, якщо б у попередньому прикладі процес А і процес У запитували ресурси в однаковій послідовності, то глухий кут був би в принципі неможливий. Другий підхід до запобігання тупиків називається динамічним і полягає у використанні певних правил при призначенні ресурсів процесам, наприклад, ресурси можуть виділятися в певній послідовності, загальною для всіх процесів.
У деяких випадках, коли тупикова ситуація утворена багатьма процесами, що використовують багато ресурсів, розпізнавання глухого кута є нетривіальним завданням. Існують формальні, програмно-реалізовані методи розпізнавання тупиків, засновані на веденні таблиць розподілу ресурсів і таблиць запитів до зайнятих ресурсів. Аналіз цих таблиць дозволяє виявити взаємні блокування.
Якщо ж тупикова ситуація виникла, то не обов'язково знімати з виконання всі заблоковані процеси. Можна зняти тільки частину з них, при цьому звільняються ресурси, очікувані іншими процесами, можна повернути деякі процеси в область свопінгу, можна зробити "відкат" деяких процесів до так званої контрольної точки, в якій запам'ятовується вся інформація, необхідна для відновлення виконання програми з даного місця. Контрольні точки розставляються в програмі в місцях, після яких можливе виникнення безвиході.
З усього вищесказаного ясно, що використовувати семафори потрібно дуже обережно, тому що одна незначна помилка може призвести до зупинки системи. Для того, щоб полегшити написання коректних програм, було запропоновано високорівневий засіб синхронізації, зване монітором. Монітор - це набір процедур, змінних і структур даних. Процеси можуть викликати процедури монітора, але не мають доступу до внутрішніх даних монітора. Монітори мають важливе властивість, яка робить їх корисними для досягнення взаємного виключення: тільки один процес може бути активним по відношенню до монітора. Компілятор обробляє виклики процедур монітора особливим чином. Зазвичай, коли процес викликає процедуру монітора, то перші кілька інструкцій цієї процедури перевіряють, не активний може який-небудь інший процес по відношенню до цього монітора. Якщо так, то зухвалий процес припиняється, поки інший процес не звільнить монітор. Таким чином, виключення входу декількох процесів в монітор реалізується не програмістом, а компілятором, що робить помилки менш імовірними.
У розподілених системах, що складаються з декількох процесорів, кожний з яких має власну оперативну пам'ять, семафори та монітори виявляються непридатними. У таких системах синхронізація може бути реалізована тільки за допомогою обміну повідомленнями. Докладніше про це дивіться у розділі "Синхронізація в розподілених системах".
Нитки
Багатозадачність є найважливішою властивістю ОС. Для підтримки цієї властивості ОС визначає й оформляє для себе ті внутрішні одиниці роботи, між якими і буде розділятися процесор і інші ресурси комп'ютера. Ці внутрішні одиниці роботи в різних ОС носять різні назви - задача, завдання, процес, нитка. У деяких випадках сутності, що позначаються цими поняттями, принципово відрізняються один від одного.
Говорячи про процеси, ми відзначали, що операційна система підтримує їх відособленість: у кожного процесу є своє віртуальний адресний простір, кожному процесу призначаються свої ресурси - файли, вікна, семафори і т.д. Така відособленість потрібна для того, щоб захистити один процес від іншого, оскільки вони, спільно використовуючи всі ресурси машини, конкурують один з одним. У загальному випадку процеси належать різним користувачам, що розділяють один комп'ютер, і ОС бере на себе роль арбітра в суперечках процесів за ресурси.
При мультипрограмування підвищується пропускна здатність системи, але окремий процес ніколи не може бути виконаний швидше, ніж якщо б він виконувався в однопрограмних режимі (всяке поділ ресурсів сповільнює роботу одного з учасників за рахунок додаткових витрат часу на очікування звільнення ресурсу). Проте завдання, яке вирішується в рамках одного процесу, може мати внутрішнім паралелізмом, який в принципі дозволяє прискорити її розв'язання. Наприклад, в ході виконання задачі відбувається звертання до зовнішньому пристрою, і на час цієї операції можна не блокувати повністю виконання процесу, а продовжити обчислення по іншій "гілки" процесу.
Для цих цілей сучасні ОС пропонують використовувати порівняно новий механізм багатонитковою обробки (multithreading). При цьому вводиться нове поняття "нитка" (thread), а поняття "процес" у значній мірі змінює зміст.
Мультипрограмування тепер реалізується на рівні ниток, і задача, оформлена у вигляді декількох ниток в рамках одного процесу, може бути виконана швидше за рахунок псевдопаралельною (або паралельного в мультипроцессорной системі) виконання її окремих частин. Наприклад, якщо електронна таблиця була розроблена з урахуванням можливостей багатонитковою обробки, то користувач може запросити перерахунок свого робочого листа й одночасно продовжувати заповнювати таблицю. Особливо ефективно можна використовувати багатонитковою для виконання розподілених додатків, наприклад, багатонитковою сервер може паралельно виконувати запити відразу декількох клієнтів.
Нитки, що відносяться до одного процесу, не настільки ізольовані один від одного, як процеси в традиційній багатозадачного системі, між ними легко організувати тісну взаємодію. Дійсно, на відміну від процесів, які належать різним, взагалі кажучи, конкуруючим додаткам, усі нитки одного процесу завжди належать одному додатку, тому програміст, що пише це додаток, може заздалегідь продумати роботу безлічі ниток процесу таким чином, щоб вони могли взаємодіяти, а не боротися за ресурси.
У традиційних ОС поняття "нитка" тотожно поняттю "процес". У дійсності часто буває бажано мати кілька ниток, що розділяють єдиний адресний простір, але виконуються квазіпараллельно, завдяки чому нитки стають подібними процесам (за винятком поділюваного адресного простору).
Нитки іноді називають полегшеними процесами чи міні-процесами. Дійсно, нитки в багатьох відносинах подібні процесам. Кожна нитка виконується строго послідовно і має свій власний програмний лічильник і стік. Нитки, як і процеси, можуть, наприклад, породжувати нитки-нащадки, можуть переходити зі стану в стан. Подібно традиційним процесам (тобто процесів, що складається з однієї нитки), нитки можуть знаходиться в одному з наступних станів: ВИКОНАННЯ, ОЧІКУВАННЯ і ГОТОВНІСТЬ. Поки одна нитка заблокована, інша нитка того ж процесу може виконуватися. Нитки розділяють процесор так, як це роблять процеси, у відповідності з різними варіантами планування.
Однак різні нитки в рамках одного процесу не настільки незалежні, як окремі процеси. Всі такі нитки мають одне і те ж адресний простір. Це означає, що вони поділяють одні й ті ж глобальні змінні. Оскільки кожна нитка може мати доступ до кожного віртуального адресою, одна нитка може використовувати стек іншої нитки. Між нитками немає повного захисту, тому що, по-перше, це неможливо, а по-друге, не потрібно. Усі нитки одного процесу завжди вирішують загальну задачу одного користувача, і апарат ниток використовується тут для більш швидкого рішення задачі шляхом її розпаралелювання. При цьому програмісту дуже важливо одержати у своє розпорядження зручні засоби організації взаємодії частин однієї задачі. Крім поділу адресного простору, всі нитки розділяють також набір відкритих файлів, таймерів, сигналів і т.п.
Отже, нитки мають власні:
- Програмний лічильник,
- Стік,
- Регістри,
- Нитки-нащадки,
- Стан.
- Нитки розділяють:
- Адресний простір,
- Глобальні змінні,
- Відкриті файли,
- Таймери,
- Семафори,
- Статистичну інформацію.
Багатонитковою обробка підвищує ефективність роботи системи в порівнянні з багатозадачною обробкою. Наприклад, у багатозадачному середовищі Windows можна одночасно працювати з електронною таблицею і текстовим редактором. Однак, якщо користувач запитує перерахування свого робочого листа, електронна таблиця блокується до тих пір, поки ця операція не завершиться, що може зажадати значного часу. У багатонитковою середовищу у випадку, якщо електронна таблиця була розроблена з урахуванням можливостей багатонитковою обробки, що надаються програмісту, цієї проблеми не виникає, і користувач завжди має доступ до електронної таблиці.
Широке застосування знаходить багатонитковою обробка в розподілених системах. Дивіться про це у розділі "Процеси і нитки в розподілених системах".
Деякі прикладні завдання легше програмувати, використовуючи паралелізм, наприклад задачі типу "письменник-читач", в яких одна нитка виконує запис у буфер, а інша зчитує записи з нього. Оскільки вони поділяють спільний буфер, не варто їх робити окремими процесами. Інший приклад використання ниток - це управління сигналами, такими як переривання з клавіатури (del або break). Замість обробки сигналу переривання, одна нитка призначається для постійного очікування надходження сигналів. Таким чином, використання ниток може скоротити необхідність в перериваннях користувацького рівня. У цих прикладах не настільки важливо паралельне виконання, наскільки важлива ясність програми.
Нарешті, в мультипроцесорних системах для ниток з одного адресного простору є можливість виконуватися паралельно на різних процесорах. Це дійсно один з головних шляхів реалізації поділу ресурсів у таких системах. З іншого боку, правильно сконструйовані програми, які використовують нитки, повинні працювати однаково добре як на однопроцесорній машині в режимі поділу часу між нитками, так і на справжньому мультипроцесорі.