Особливості виконання потоків
З погляду планування виконання потоку можна зобразити як цикл чергування періодів обчислень (використання процесора) і періодів очікування введення-виведення. Інтервал часу, упродовж якого потік виконує тільки інструкції процесора, називають інтервалом використання процесора (CPU burst), інтервал часу, коли потік очікує введення-виведення, - інтервалом введення-виведення (I/O burst). Найчастіше ці інтервали мають довжину від 2 до 8 мс.
Потоки, які більше часу витрачають на обчислення і менше – на введення-виведення, називають обмеженими можливостями процесора (CPU bound). Вони активно використовують процесор. Основною їхньою характеристикою є час, витрачений на обчислення, інтервали використання процесора для них довші. Потоки, які більшу частину часу перебувають в очікуванні введення-виведення, називають обмеженими можливостями введення-виведення (I/O bound). Такі потоки завантажують процесор значно менше, а середня довжина інтервалу використання процесора для них невелика. Що вища тактова частота процесора, то більше потоків можна віднести до другої категорії.
Механізми і політика планування
Слід розрізняти механізми і політику планування. До механізмів планування належать засоби перемикання контексту, засоби синхронізації потоків тощо, до політики планування – засоби визначення моменту часу, коли необхідно перемкнути контекст. Ту частину системи, яка відповідає за політику планування, називають планувальником (scheduler), а алгоритм, що використовують при цьому, - алгоритмом планування (scheduling algorithm).
|
|
|
Є різні критерії оцінки політики планування, одні з них застосовані для всіх систем, інші – лише для пакетних систем або лише для інтерактивних.
Сьогодні найчастіше використовують три критерії оцінки досягнення мети
· Мінімальний час відгуку. Це найважливіший критерій для інтерактивних систем. Під часом відгуку розуміють час між запуском потоку (або введенням користувачем інтерактивної команди) і отриманням першої відповіді. Для сучасних систем прийнятним часом відгуку вважають 50-150 мс.
· Максимальна пропускна здатність. Це кількість задач, які система може виконувати за одиницю часу (наприклад, за секунду). Такий критерій доцільно застосовувати у пакетних системах; в інтерактивних системах він може бути використаний для фонових задач. Щоб підвищити пропускну здатність, необхідно:
- скорочувати час даремного навантаження (наприклад, час, необхідний для перемикання контексту);
- ефективніше використати ресурси (для того, щоб ані процесор, ані пристрої введення-виведення не простоювали).
· Третім критерієм є справедливість, яка полягає в тому, що процесорний час потокам виділяють відповідно до їхньої важливості. Справедливість забезпечує такий розподіл процесорного часу, що всі потоки просуваються у своєму виконанні, і жоден не простоює. Відзначимо, що реалізація справедливої політики планування не завжди призводить до зменшення середнього часу відгуку. Іноді для цього потрібно зробити систему менш справедливою.
|
|
|
Застосовність принципів планування
Принципи планування потоків застосовні насамперед до багато потокових систем із реалізацією схеми 1:1 (тут плануються винятково потоки ядра), а також до систем з реалізацією моделі процесів. В останньому випадку замість терміна «потік» можна вживати термін «процес», а інформацію, необхідну для планування використовують у багатопотокових системах, для яких кількість потоків користувача не збігається з кількістю потоків ядра (схеми 1:М і М:N). Для них потрібні два планувальники: один для роботи на рівні ядра, інший – у режимі користувача.
Види планування
Довготермінове планування
Засоби довготермінового планування визначають, яку з програм треба завантажити у пам’ять для виконання. Таке планування називають також статичним, оскільки воно не залежить від поточного стану системи. Воно відігравало важливу роль у пакетних системах, коди заздалегідь відомо, які процеси повинні бути виконані і можна скласти розклад виконання задач. В інтерактивних системах (наприклад, у системах з розподілом часу) завантаження процесів у пам’ять здійснюють переважно користувачі, і це плануванню не підлягає; тому в них зазвичай використовують спрощену стратегію довготермінового планування. Система дає можливість створювати процеси і потоки до досягнення деякої максимально можливої межі, після чого подальші спроби створити новий процес або потік спричинятимуть помилку. Така стратегія ґрунтується і на психології користувачів, які, почуваючи себе некомфортно в перевантаженій системі ,можуть переривати роботу з нею, що призводить до зниження навантаження.
|
|
|
Середньотермінове планування
Засоби середньотермінового планування керують переходом потоків із призупиненого стану в стан готовності і назад. Відразу ж зазначимо, що керуючі блоки готових до виконання потоків організується у пам’яті в структуру, яку називають чергою готових потоків ().
Перехід потоку в призупинений стан можуть викликати такі фактори:
|
|
|
· очікування операції введення-виведення;
· очікування закінчення виконання іншого потоку (приєднання);
· блокування потоку через необхідність його синхронізації з іншими потоками.
Зазвичай для коректної організації такого очікування, крім черги готових потоків, реалізують додатковий набір черг. Кожна така черга пов’язана з ресурсом, який може викликати очікування потоку (наприклад, із пристроєм введення-виведення); ці черги ще називають чергами планування (scheduling queues) або чергами очікування (wait queues). Середньотерміновий планувальник керує всіма цими чергами, переміщаючи потоки між ними та чергою готових потоків.
Короткотермінове планування
Короткотермінове планування, або планування процесора (CPU scheduling), є найважливішим видом планування. Воно дає змогу відповісти на два базових запитання.
· Коли перервати виконання потоку?
· Якому потокові з числа готових до виконання потрібно передати процесор у цей момент?
Короткотерміновий планувальник – це підсистема ОС, яка в разі необхідності перериває активний потік і вибирає із черги готових потоків той, що має виконуватися. До його продуктивності ставлять найвищі вимоги, бо він отримує керування дуже часто. Виділяють також диспетчер (dispatcher), який безпосередньо передає керування вибраному потокові (перемикає контекст).
Формат черги готових потоків залежить від реалізації короткотермінового планування. Така черга може бути організована за принципом FIFO, бути чергою із пріоритетами, деревом або невпорядкованим зв’язним списком.
Усі стратегії й алгоритми планування, які ми будемо розглядати далі, належать до короткотермінового планування.
Стратегії планування. Витісняльна і невитісняльна багатозадачність
Перед тим, як розглянути основні стратегії планування, перелічимо варіанти передачі керування від одного потоку до іншого:
· після того, як потік перейшов у стан очікування (наприклад, під час введення-виведення або приєднання);
· після закінчення виконання потоку;
· явно (потік сам віддає процесор іншим потокам на час, поки він не зайнятий корисною роботою)ж
· за перериванням (наприклад, переривання від таймера дає змогу перервати птік, що виконується довше, ніж йому дозволено).
Останній варіант відрізняється від інших тим, що потік не може контролювати, коли настане час передачі керування, за це відповідає планувальник операційної системи. Залежно від підтримки такого варіанта передачі керування розрізняють дві основні стратегії планування потоків – витісняльну і невитісняльну багатозадачність.
При витісняльній багатозадачності (preemptive multitasking) потоки, що логічно мають виконуватися, можуть бути тимчасово перервні планувальником ОС без їхньої участі для передачі керування іншим потокам. Переривання виконання потоку й передачу керування іншому потокові найчастіше здійснюють в обробнику переривання від системного таймера. Така стратегія реалізована в усіх сучасних операційних системах.
При невитісняльній багатозадачності (non-preemptive multitasking) потоки можуть виконуватися упродовж необмеженого часу й не можуть бути перервані ОС. Для невитісняльної багатозадачності передача керування за останнім варіантом не реалізована, і потоки самі повинні віддавати керування ОС для передачі іншим потокам або, принаймні, переходити у стан очікування. Якщо якийсь потік забуде або не зможе це зробити, наприклад займе процесор нескінченим циклом, інші потоки не зможуть продовжувати свою роботу. Таку стратегію було реалізовано в ОС (наприклад, у версії 3.11).
Природно, що реалізація невитісняльної багатозадачності в загальному випадку робить систему досить не стабільною (будь-яке некоректно написане застосування користувача може спричинити «зависання» всієї системи). Практика показує, що невитісняльна багатозадачністьу системах із застосуваннями користувача не може бути реалізована.
Таку стратегію, проте, можна використати в системах, де всі застосування виконуються в режимі ядра і фактично є системними драйверами. Для розробки таких застосувань необхідна висока кваліфікація програмістів вимоги до надійності застосувань можна порівняти з вимогами до самої ОС. При цьому простота реалізації та відсутність зовнішніх переривань потоків від планувальника ОС може підвищувати продуктивність системи для обмеженого кола задач (наприклад, у випадку ОС NetWare це було використання системи як файлового менеджера).
Алгоритми планування
Планування за принципом FIFO
При плануванні за принципом FIFO потоки ставлять на виконання в порядку їхньої появи у системі й виконують до переходу в стан очікування, явної передачі керування або завершення. Чергу готових потоків при цьому організовують за принципом FIFO.
Як тільки в системі створюється новий потік, його керуючий блок додається у хвіст черги. Коли процесор звільняється, його надають потоку з голови черги.
У такого алгоритму багато недоліків:
· він за визначенням є невитісняльним;
· середній час відгуку для нього може бути доволі значним (наприклад, якщо першим надійде потік із довгим інтервалом використання процесора, інші потоки чекатимуть, навіть якщо вони самі використовують тільки короткі інтервали);
· від підлягає ефекту конвою (convoy effect).
Ефект конвою можна пояснити такою ситуацією. Припустимо, що в системі є один потік (Tcpu), обмежений можливостями процесора, і багато потоків (Tio), обмежених можливостями введення-виведення. Рано чи пізно потік Tcpu отримає процесор у своє розпорядження і виконуватиме інструкції з довгим інтервалом використання процесора. За цей час інші потоки Tio завершать введення-виведення, перемістяться в чергу готових потоків і там чекатимуть, при цьому пристрої введення-виведення простоюватимуть. Коли Tcpu нарешті заблокують і відбудеться передача керування, всі потоки Tio швидко виконають інструкції своїх інтервалів використання процесора і знову перейдуть до введення-виведення. Після цього Tcpu знову захопить процесор на тривалий час і т.д.
Кругове планування
Найпростішим для розуміння і найсправедливішим витісняльним алгоритмом є алгоритм кругового планування (round-robin scheduling).
Кожному потокові виділяють інтервал часу, який називають квантом часу (рис. 4.1) і упродовж якого цьому потокові дозволено виконуватися. Коли потік усе ще виконується після вичерпання кванту, його переривають і перемикають процесор на виконання інструкцій іншого потоку .Коли він блокується або закінчує своє виконання до вичерпання кванта часу, процесор теж передають іншому потокові. Довжина кванта часу для всієї системи однакова.
Такий алгоритм реалізувати досить легко. Для цього черга готових потоків має бути циклічним списком. Коли потік вичерпав свій квант часу, його переміщують у кінець списку, туди ж додають і нові потоки. Перевірку вичерпання кванта часу виконують в обробнику переривання від системного таймера.
Рис. 4.1. Кругове планування
Єдиною характеристикою, яка впливає на роботу алгоритму, є довжина кванта часу. Тут слід дотримуватися балансу між часом, що витрачається на перемикання контексту, і необхідністю відповідати на багато одночасних інтерактивних запитів.
Задання надто короткого кванта часу призводить до того, що відбувається дуже багато перемикань контексту, і значний відсоток процесорного часу витрачається не на корисну роботу, а не ці перемикання. З іншого боку, задання надто довгого кванта хоча й заощаджує процесорний час, але спричиняє до зниження часу відгуку на інтерактивні запити, бо якщо десять користувачів одночасно натиснуть клавішу, то десять потоків потраплять у список готових, внаслідок чого останній з них очікуватиме десять довгих квантів часу. У випадку з квантом нескінченої довжини кругове планування зводиться до алгоритму FIFO (усі потоки встигають заблокуватися або закінчитися до вичерпання кванта). На практиці рекомендують встановлювати довжину кванта в 10-100 мс.
Традиційне кругове планування може давати «перекіс» у бік потоків, обмежених можливостями процесора. Такі потоки переважно використовують свій квант повністю, тоді як потоки, обмежені можливостями введення-виведення, часто передають керування до вичерпання кванта, і в результаті їм дістається менше процесорного часу. Для вирішення цієї проблеми можна збільшувати довжину кванта (з огляду на проблеми ,описані раніше) або вводити додаткову чергу потоків, що завершили введення-виведення, яка має перевагу на виконання перед чергою готових потоків.
Планування із пріоритетами
Планування за принципом кругового чергування припускає, що всі потоки однаково важливі. В іншому разі необхідно застосовувати планування із пріоритетами.
Основна ідея проста: кожному потокові надають пріоритет, при цьому на виконання ставитиметься потік із найвищим пріоритетом із черги готових потоків. Пріоритети можуть надаватися потокам статично або динамічно.
Одним із підходів до реалізації планування із пріоритетами є алгоритм багаторівневих черг (multilevel queues). У цьому разі організовують кілька черг для груп потоків із різними пріоритетами (потоки кожної групи звичайно мають різне призначення, можуть бути групи фонових потоків ,інтерактивних тощо).
Рішення про вибір потоку для виконання приймають таким чином:
· якщо в черзі потоків із найвищим пріоритетом є потоки, для них слід використати якийсь простіший алгоритм планування (наприклад, кругове планування), не звертаючи уваги на потоки в інших чергах;
· якщо в черзі немає жодного потоку, переходять до черги потоків з нижчим пріоритетом і т.д.
Розподіл пріоритетів є складним завданням, невдале його розв’язання може призвести до того, що потоки процесів із низьким пріоритетом чекатимуть дуже довго. Таку ситуацію називають голодування (starvation).
Є різні способи розв’язання проблеми голодування. Наприклад, планувальник може поступово зменшувати пріоритет потоку, який виконують (такий процес називають старінням), і коли він стане нижче, ніж у наступного за пріоритетом потоку, перемкнути контекст на цей потік. Можна, навпаки, поступово підвищувати пріоритети потоків, які очікують.
Планування на підставі характеристик подальшого виконання
Важливим класом алгоритмів планування із пріоритетами є алгоритми, в яких рішення про вибір потоку для виконання приймають на підставі знання або оцінку характеристик подальшого його виконання.
Насамперед слід відзначити алгоритм «перший – із найкоротшим часом виконання» (Shortest Time to Completion First, STCF), коли з кожним потоком пов’язують тривалість наступного інтервалу використання ним процесора і для виконання щоразу вибирають потік, у якого цей інтервал найкоротший. У результаті потоки, що захоплюють процесор на коротший час, отримують під час планування перевагу і швидше виходять із системи.
Алгоритм STCF є теоретично оптимальним за критерієм середнього часу відгуку, тобто можна довести, що для вибраної групи потоків середній час відгуку в разі застосування цього алгоритму буде мінімальним порівняно з будь-яким іншим алгоритмом. На жаль, для короткотермінового планування реалізувати його неможливо, тому що ця реалізація потребує передбачення очікуваних характеристик. Для довготермінового планування його використовують досить часто (у цьому разі, ставлячи задачу на виконання, оператор повинен вказати очікуваний момент її завершення, на який система буде зважати під час вибору). Слід зазначити, що оптимальність такого алгоритму невіддільна від його «несправедливості» до потоків із довшими інтервалами використання процесора.
Для короткотермінового планування може бути реалізоване наближення до цього алгоритму, засноване на оцінці довжини чергового інтервалу використання процесора з урахуванням попередніх інтервалів того самого потоку. Для обчислення цієї оцінки можна використати рекурсивну формулу:
Розділ 5
Взаємодія потоків
Дата добавления: 2018-04-05; просмотров: 891; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!