Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Особливості виконання потоків

Читайте также:
  1. I.3.Особливості політичного становища гетьманів у 1648-1667 роках.
  2. Алгоритм виконання курсової роботи
  3. Алгоритм виконання практичного навику №10
  4. Алгоритм виконання практичного навику №4
  5. Алгоритм виконання практичної навички
  6. Алгоритм виконання практичної навички
  7. Алгоритм виконання практичної навички
  8. Аналіз виконання договірних зобов’язань
  9. Аналіз виконання договірних зобов’язань
  10. Аналіз виконання договірних зобов’язань

З погляду планування виконання потоку можна зобразити як цикл чергування
періодів обчислень (використання процесора) і періодів очікування введення-виведення. Інтервал часу, упродовж якого потік виконує тільки інструкції процесора,
називають інтервалом використання процесора (CPU burst), інтервал часу, коли
потік очікує введення-виведення, — інтервалом введення-виведення (I/O burst).
Найчастіше ці інтервали мають довжину від 2 до 8 мс.

Потоки, які більше часу витрачають на обчислення і менше — на введення-виведення, називають обмеженими можливостями процесора (CPU bound). Вони активно використовують процесор. Основною їхньою характеристикою є час, витрачений на обчислення, інтервали використання процесора для них довші. Потоки, які більшу частину часу перебувають в очікуванні введення-виведення, називають обмеженими можливостями введення-виведення (I/O bound). Такі потоки
завантажують процесор значно менше, а середня довжина інтервалу використання процесора для них невелика. Що вища тактова частота процесора, то більше
потоків можна віднести до другої категорії.

Потік, обмежений процесором (перемножування матриць)

Потік, обмежений введенням-виведєнням (текстовий редактор)

4.1.2. Механізми і політика планування введення-виведення (I/O burst)

Інтервал використання процесора (CPU burst)
Рис. 4.1. Класифікація потоків з погляду планування

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

Є різні критерії оцінки політики планування, одні з них застосовні для всіх
систем, інші — лише для пакетних систем або лише для інтерактивних.

Сьогодні найчастіше використовують три критерії оцінки досягнення мети.

♦ Мінімальний час відгуку. Це найважливіший критерій для інтерактивних систем. Під часом відгуку розуміють час між запуском потоку (або введенням користувачем інтерактивної команди) і отриманням першої відповіді. Для сучасних систем прийнятним часом відгуку вважають 50-150 мс.

♦ Максимальна пропускна здатність. Це кількість задач, які система може виконувати за одиницю часу (наприклад, за секунду). Такий критерій доцільно застосовувати у пакетних системах; в інтерактивних системах він може
бути використаний для фонових задач. Щоб підвищити пропускну здатність,
необхідно:

♦ скорочувати час даремного навантаження (наприклад, час, необхідний для
перемикання контексту);

♦ ефективніше використати ресурси (для того, щоб ані процесор, ані пристрої введення-виведення не простоювали).

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

4.1.3. Застосовність принципів планування

Принципи планування потоків застосовні насамперед до багатопотокових систем
із реалізацією схеми 1:1 (тут плануються винятково потоки ядра), а також до систем з реалізацією моделі процесів. В останньому випадку замість терміна «потік»
можна вживати термін «процес», а інформацію, необхідну для планування, зберігати в структурах даних процесів. Складніші принципи планування використовують у багатопотокових системах, для яких кількість потоків користувача не
збігається з кількістю потоків ядра (схеми 1 :М і M:N). Для них потрібні два планувальники: один для роботи на рівні ядра, інший - у режимі користувача.

4.2. Види планування

Розрізняють планування довготермінове (long-term scheduling), середньотермінове (medium-term scheduling) і короткотермінове (short-term scheduling).

4.2.1. Довготермінове планування

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

4.2.2. Середньотермінове планування

Засоби середньотермінового планування керують переходом потоків із призупиненого стану в стан готовності й назад. Відразу ж зазначимо, що керуючі блоки готових до виконання потоків організуються у пам’яті в структуру, яку називають чергою готових потоків (ready queue). Докладніше розглянемо цю чергу під час вивчення короткотермінового планування.Перехід потоку в призупинений стан можуть викликати такі фактори:

♦ очікування операції введення-виведення;

♦ очікування закінчення виконання іншого потоку (приєднання);

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

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

 

Рис. 4.2. Організація черг готових потоків і планування
Особливості планування операцій введення-виведення розлянемо в розділі 15.

 

 

 

 

4.2.3. Короткотермінове планування

Короткотермінове планування, або планування процесора (CPU scheduling), є найважливішим видом планування. Воно дає змогу відповісти на два базових запитання.

♦ Коли перервати виконання потоку?

♦ Якому потокові з числа готових до виконання потрібно передати процесор
у цей момент?

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

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

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

4.3. Стратегії планування. Витісняльна
і невитісняльна багатозадачність

Перед тим як розглянути основні стратегії планування, перелічимо варіанти пе-
редачі керування від одного потоку до іншого:

♦ після того, як потік перейшов у стан очікування (наприклад, під час введення-виведення або приєднання);

♦ після закінчення виконання потоку;

♦ явно (потік сам віддає процесор іншим потокам на час, поки він не зайнятий
корисною роботою);

♦ за перериванням (наприклад, переривання від таймера дає змогу перервати
потік, що виконується довше, ніж йому дозволено).

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

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

При невитісняльній багатозадачності (non-preemptive multitasking) потоки
можуть виконуватися упродовж необмеженого часу й не можуть бути перервані
ОС. Для невитісняльної багатозадачності передача керування за останнім варіантом не реалізована, і потоки самі повинні віддавати керування ОС для передачі
іншим потокам або, принаймні, переходити у стан очікування. Якщо якийсь потік
забуде або не зможе це зробити, наприклад займе процесор нескінченним циклом,
інші потоки не зможуть продовжувати свою роботу. Таку стратегію було реалізовано в ОС Novell NetWare (наприклад, у версії 3.11, яку широко використовували в 90-х роках XX ст).

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

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

4.4. Алгоритми планування

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

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

Планування за принципом FIFO

Розглянемо найпростіший («наївний») невитісняльний алгоритм, у якому потоки ставлять на виконання в порядку їхньої появи у системі й виконують до переходу в стан очікування, явної передачі керування або завершення. Чергу готових
потоків при цьому організовують за принципом FIFO, тому алгоритм називають
алгоритмом FIFO.

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

♦ він за визначенням є невитісняльним;

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

♦ він підлягає ефекту конвою (convoy effect).

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

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

Кругове планування

Найпростішим для розуміння і найсправедливішим витісняльним алгоритмом
є алгоритм кругового планування (round-robin scheduling). У середні віки терміном «round robin» називали петиції, де підписи йдуть по колу, щоб не можна було
дізнатися, хто підписався першим (ця назва свідчить, що для такого алгоритму
всі потоки рівні).

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

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

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

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

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

Планування із пріоритетами

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

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

Одним із підходів до реалізації планування із пріоритетами є алгоритм багаторівневих черг (multilevel queues). У цьому разі організовують кілька черг для
груп потоків із різними пріоритетами (потоки кожної групи звичайно мають різне призначення, можуть бути групи фонових потоків, інтерактивних тощо).
Рішення про вибір потоку для виконання приймають таким чином:

♦ якщо в черзі потоків із найвищим пріоритетом є потоки, для них слід використати якийсь простіший алгоритм планування (наприклад, кругового планування), не звертаючи уваги на потоки в інших чергах;

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

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

Розподіл пріоритетів є складним завданням, невдале його розв'язання може
призвести до того, що потоки процесів із низьким пріоритетом чекатимуть дуже
довго. Наприклад, у 1973 році в Массачусетському технологічному інституті була
зупинена машина, на якій знайшли процес із низьким пріоритетом — він був
поставлений у чергу на виконання в 1967 році і з того часу так і не зміг запуститися. Таку ситуацію називають голодуванням (starvation).

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

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

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

Насамперед слід відзначити алгоритм «перший — із найкоротшим часом виконання» (Shortest Time to Completion First, STCF), коли з кожним потоком пов'язують тривалість наступного інтервалу використання ним процесора і для виконання щоразу вибирають той потік, у якого цей інтервал найкоротший. У результаті
потоки, що захоплюють процесор на коротший час, отримують під час планування перевагу і швидше виходять із системи.

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

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

tn +1=а Тn + (1 - а) tn , 0 < а < 1, t0 = T0,

де tn +1 — оцінка довжини інтервалу; tn — оцінка довжини попереднього інтерва-
лу; Тn — справжня довжина попереднього інтервалу. Найчастіше використовують
значення а = 0,5, у цьому разі для перерахування оцінки достатньо обчислити се-
реднє між попередньою оцінкою і реальним значенням інтервалу.

Витісняльним аналогом STCF є алгоритм перший — із найкоротшим часом
виконання, що залишився» (Shortest Remaining Time to Completion First, SRTCF).
Його відмінність від SCTF полягає в тому, що, коли в чергу готових потоків додають новий, у якого наступний інтервал використання процесора коротший, ніж
час, що залишився до завершення виконання поточного потоку, поточний потік
переривається, і на його місце стає новий потік.


Дата добавления: 2014-12-20; просмотров: 43 | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2021 год. (0.029 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав