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

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

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

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

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

У такого алгоритму багато недоліків:

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

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

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

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

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

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

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

Рис. 4.1. Кругове планування

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

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

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

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

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

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

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

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

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

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

Розподіл пріоритетів є складним завданням, невдале його розв’язання може призвести до того, що потоки процесів із низьким пріоритетом чекатимуть дуже довго. Таку ситуацію називають голодування (starvation).

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

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

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

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

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

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

Розділ 5

Взаємодія потоків

5.1. Основні принципи взаємодії потоків

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

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

Усі інші потоки є такими, що взаємодіють. Ці потоки мають дані, спільні з іншими потоками. Їх виконання залежить не тільки від вхідних даних, але й від виконання інших потоків, тобто є недетермінованими.

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

Дані, які є загальними для кількох потоків, називають спільно використовуваними даними (shared data). Це – найважливіша концепція багато потокового програмування. Усякий потік може в будь-який момент часу змінити такі дані. Механізми забезпечення коректного доступу до спільно використовуваних даних називають механізмами синхронізації потоків.

Обійтися без реалізації взаємодії потоків неможливо з кількох причин.

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

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

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

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

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

5.2. Основні проблеми взаємодії потоків

Дата добавления: 2014-01-05