Урок № 92

(згідно навчальної робочої програми)

Тема: «Стратегії планування»

Питання:

1. Витісняльна і невитісняльна багатозадачність.

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

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

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

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

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

7. Багаторівневі черги зі зворотним зв’язком.

8. Лотерейне планування.

Витісняльна і невитісняльна багатозадачність

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

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

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

• явно;

• за перериванням.

Залежно від підтримки такого варіанта передачі керування роз­різняють дві основні стратегії планування потоків — витісняльну і невитісняльнубагатозадачність.

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

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

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

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

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

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

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

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

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

Найпростішим для розуміння і найсправедливішим витісняльним алгоритмом є алгоритм кругового планування(round-robin scheduling).

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

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

Рисунок 4 – Кругове планування

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

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

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

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

Одним із підходів до реалізації планування із пріоритетами є алгоритм бага­торівневих черг (multilevel queues). У цьому разі організовують кілька черг для груп потоків із різними пріоритетами.

Рішення про вибір потоку для виконання приймають таким чином:

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

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

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

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

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

Алгоритм STCF є теоретично оптимальним за критерієм середнього часу від­гуку, тобто можна довести, що для вибраної групи потоків середній час відгуку в разі застосування цього алгоритму буде мінімальним порівняно з будь-яким іншим алгоритмом.

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

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

Багаторівневі черги зі зворотним зв’язком

Алгоритм багаторівневих черг зі зворотним зв’язком (multilevel feedback queues) є найуніверсальнішим алгоритмом плануванн, але при цьому одним із найскладніших у реалізації.

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

Відмінності між двома алгоритмами полягають у тому, що:

• потокам дозволено переходити з рівня на рівень (із черги в чергу);

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

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

Лотерейне планування

Ідея лотерейного планування полягає у тому, що:

• потік отримує деяку кількість лотерейних квитків, кожен з яких дає право ко­ристуватися процесором упродовж часу Т;

• планувальник через проміжок часу Т вибирає випадково один лотерейнийквиток;

• потік, «що виграв», дістає керування до наступного розіграшу.

Лотерейне планування дає змогу:

• емулювати кругове планування, видавши кожному потокові однакову кіль­кість квитків;

• емулювати планування із пріоритетами, розподіляючи квитки відповідно до пріоритетів потоків;

• емулювати SRTCF— давати коротким потокам більше квитків, ніж довгим (якщо потік отримав хоча б один квиток, він не голодуватиме);

• забезпечити розподіл процесорного часу між потоками — дати кожному пото­кові кількість квитків, пропорційну до частки процесорного часу, який пот­рібно йому виділити (наприклад, якщо є три потоки, і треба, щоб потік А зай­мав 50 % процесора, а потоки В і С — по 25 %, можна дати потоку А два квитки, а потокам В і С — по одному);

• динамічно міняти пріоритети, відбираючи і додаючи квитки по ходу.

Контрольні питання:

1. Що таке витісняльна і невитісняльна багатозадачність?

2. Які існують алгоритми планування?

3. В чому суть планування за принципом FIFO?

4. В чому суть кругового планування?

5. В чому суть планування із пріоритетами?

6. В чому суть планування на підставі характеристик подальшого В чому суть виконання?

7. Як працюють багаторівневі черги зі зворотним зв’язком?

8. В чому суть лотерейне планування?

Література: Шеховцов В.А. Операційні системи. – К.: Видавнича група BHV, 2005. – 576 с.: іл., стор. 93-99.