Планування потоків

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

2.1. Стани потоків

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

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

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

2.2. Планування потоків, область конкуренції та пріоритет

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

Зауваження: потоки при моделюванні їх реальної поведінки в додатку повинні мати системну область конкуренції.

Стратегія планування та пріоритет процесу належать основному по­то­ку. Кожен потік (незалежно від основного) може мати власну стратегію пла­нування та пріоритет. Потокам призначаються цілі значення пріоритету, які містяться в межах визначених мінімальним та максимальним значенням. Схема пріоритетів використовується для визначення, послідовності призначення пото­ків процесору: потік з більш високим пріоритетом виконується раніше потоку з більш низьким пріоритетом. Після призначення потокам пріоритетів, задачам, які вимагають миттєвого виконання або відповіді від системи, надається необ­хі­дний процесорний час. В операційній системі з пріоритетами, потік що вико­нується, знімається з процесора, якщо в стан готовності переходить потік з більш високим пріоритетом, і який при цьому володіє тим же рівнем області конкуренції. Наприклад, як показано на рис. 5, потоки з областю конкуренції процесу, змагаються за процесор з потоками того ж процесу, що мають такий же рівень області конкуренції. Процес А має два потоки з пріоритетом 3, і один з них процесору. Як тільки потік з пріоритетом 2 оголосить про свою готов­ність, активний потік буде витіснено, а процесор займе потік з більш високим пріоритетом. Окрім того, в процесі В є два потоки (область конкуренції проце­су) з пріоритетом 1 (пріоритет 1 вище пріоритету 2). Один з цих потоків приз­начається процесору. І хоча інший потік з пріоритетом 1 готовий до виконання, він не витіснить потік з пріоритетом 2 з процесу А, оскільки ці потоки змагаю­ться в межах своїх процесів. Потоки з системної області конкуренції і з більш низьким пріоритетом не витісняються ні одним із потоків з процесів А і В. Вони змагаються за процесорний час тільки з потоками, що мають системну область конкуренції.

Згадаємо, черги готовності організовані у вигляді впорядкованих спис­ків, в яких кожен елемент має свій рівень пріоритету. Під рівнем пріоритету розуміємо чергу потоків з однаковим значенням пріоритету. Всі потоки одного рівня пріоритету призначаються процесору з використанням стратегій планува­ння: FIFO (скор. від First In First Out, тобто перший прийшов, перший обслуже­ний), RR (скор. від round-robin, тобто циклічна) або будь якої іншої. При вико­ристанні стратегії планування FIFO потік, квант процесорного часу якого закін­чився, розміщується в головну частину черги відповідного рівня пріоритету, а процесор надається наступному потоку з черги. Отже, потік буде виконуватися до тих пір, доки він не завершить виконання, не перейде в стан очікування (²за­сне²) або не отримає сигнал зупинитися. Коли потік ²що спить², ²просинаєть­ся², він розміщується в кінець черги відповідного рівня пріоритету. Стратегія планування RR аналогічна FIFO-стратегії, за виключенням того, що по закін­ченню кванта процесорного часу потік розміщується не на початок, а в кінець ²своєї² черги.

Циклічна стратегія планування (RR) вважає всі потоки такими, що воло­діють однаковим пріоритетом і кожному потоку надається процесор тільки на протязі деякого кванту часу. Тому виконання задачі відбувається почергово. Наприклад, програма, яка виконує пошук файлів за заданим ключовими слова­ми, розбивається на два потоки. Один потік (1) знаходить всі файли за заданими ключовими словами і розміщує їх на шлях в контейнер. Другий потік (2) виби­рає імена файлів з контейнера, проглядає кожен файл на наявність в ньому за­даних ключових слів, а потім записує їх імена які містять такі слова. Якщо до цих потоків застосувати циклічну стратегію планування з єдиним процесором, то потік 1 використав би свій квант часу для пошуку файлів і встановлення їх шляхів в контейнер. Потік 2 використав би свій квант часу для виділення імен файлів і пошуку заданих ключових слів. В ідеальному світі потоки 1 і 2 повинні виконуватися почергово. Але в дійсності все може бути інакше. Наприклад, по­тік 2 може виконуватися до потоку 1, коли в контейнері не має жодного файлу, або потік 1 так довго шукати файл, що до закінчення кванту часу не встигне записати його до шляху в контейнер. Така ситуація вимагає синхронізації, що розглянемо пізніше. Стратегія планування FIFO дозволяє кожному потоку ви­ко­натися до завершення. Якщо розглянути той же приклад з використанням FIFO-стратегії, то потік 1 буде мати достатньо часу, щоб знайти всі необхідні файли і встановити їх на шлях до контейнера. Потік 2 в подальшому виділить імена цих файлів та виконає пошук заданих ключових слів. В ідеальному світі завершення виконання потоку 2 буде означати завершення програми в цілому. Але в реальному світі потік 2 може бути призначений процесору до потоку 1, коли контейнер ще не буде містити файлів для пошуку ключових слів. Після ²пустого² виконання потоку 2 процесору буде призначено потік 1, який може вдало знайти необхідні файли та помістити їх шлях до контейнера. Однак по­шук ключових слів ключових слів виконувати вже буде нікому. Тому програма в цілому невдало завершиться. При використанні стратегії FIFO не передбачено перемішування задач. Потік, призначений процесору, займає його до повного завершення своєї задачі. Таку стратегію планування можливо використовувати для додатків, в яких потоки необхідно виконувати дуже швидко. Під іншими стратегіями планування розуміємо вже розглянуті, але з деякими корекціями. Наприклад, FIFO-стратегія може бути змінена таким чином, щоб дозволити розблокування потоків, випадковий вибір.

2.3. Зміна пріоритету потоку

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

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

2.4. Ресурси потоків

Потоки використовують більшу частину своїх ресурсів разом з іншими потоками із цього ж процесу. Власні ресурси потоку визначають його контекст. Так, в контекст потоку входять його ідентифікаційний номер, набір регістрів (включно з вказівником стеку і програмним лічильником) і стек. Інші ресурси (процесор, пам'ять і файлові дескриптори), які необхідні потоку для виконання його задачі, він повинен поділяти з іншими потоками. Дескриптори файлів ви­діляються кожному процесу окремо, тому потоки одного процесу змагаються за доступ доданих дескрипторів. Відносно пам’яті, процесора та інших ресурсів які розподіляються глобально, то за доступ до них потоки конкурують з іншими потоками свого процесу, а також з потоками інших процесів.

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