42. Планування процесорів за принципом fifo
Найпростіший невитісняльний алгоритм, у якому потоки ставлять на виконання в порядку їхньої появи у системі й виконують до переходу в стан очікування, явної передачі керування або завершення. Чергу готових потоків при цьому організовують за принципом FIFO, тому алгоритм називають алгоритмом FIFO.
Як тільки в системі створюється новий потік, його керуючий блок додається у хвіст черги. Коли процесор звільняється, його надають потоку з голови черги.
У такого алгоритму багато недоліків:
• він за визначенням є невитісняльним;
• середній час відгуку для нього може бути доволі значним (наприклад, якщо першим надійде потік із довгим інтервалом використання процесора, інші потоки чекатимуть, навіть якщо вони самі використовують тільки короткі інтервали);
• він підлягає ефекту конвою (convoy effect).
Ефект конвою можна пояснити такою ситуацією. Припустимо, що в системі є один потік (назвемо його Tсри), обмежений можливостями процесора, і багато потоків Тіо, обмежених можливостями введення-виведення. Рано чи пізно потік Tсри отримає процесор у своє розпорядження і виконуватиме інструкції з довгим інтервалом використання процесора. За цей час інші потоки Tіо завершать введення-виведення, перемістяться в чергу готових потоків і там чекатимуть, при цьому пристрої введення-виведення простоюватимуть. КолиTсрц нарешті заблокують і відбудеться передача керування, всі потоки Тіошвидко виконають інструкції своїх інтервалів використання процесора (у них, як ми знаємо, такі інтервали короткі) і знову перейдуть до введення-виведення. Після цього Тсризнову захопить процесор на тривалий час і т. д.
Планування за принципом FIFO
Це дисципліна планування без переключення, при якій процесам надається ЦП у відповідності з часом їх надходження у список готових до виконання.
Таке планування найчастіше застосовується в системах пакетної обробки, але воно не дозволяє гарантувати можливий (допустимий) час відповіді для інтерактивних користувачів.
43. Циклічне планування завантаження процесорів
Найпростішим для розуміння і найсправедливішим витісняльним алгоритмом є алгоритм кругового планування (round-robinscheduling). У середні віки терміном (roundrobin) називали петиції, де підписи йдуть по колу, щоб не можна було дізнатися, хто підписався першим (ця назва свідчить, що для такого алгоритму всі потоки рівні).
Кожному потокові виділяють інтервал часу, який називають квантом часу (timequantum, timeslice) і упродовж якого цьому потокові дозволено виконуватися. Коли потік усе ще виконується після вичерпання кванта часу, його переривають і перемикають процесор на виконання інструкцій іншого потоку. Коли вінблокується або закінчує своє виконання до вичерпання кванта часу, процесор тежпередають іншому потокові. Довжина кванта часу для всієї системи однакова.
Такий алгоритм реалізувати досить легко. Для цього черга готових потоків має бути циклічним списком. Коли потік вичерпав свій квант часу, його переміщують у кінець списку, туди ж додають і нові потоки (рис. 4.3). Перевірку вичерпання кванта часу виконують в обробнику переривання від системного таймера.
Рис. 4.3. Кругове планування
Єдиною характеристикою, яка впливає на роботу алгоритму, є довжина кванта часу. Тут слід дотримуватися балансу між часом, що витрачається на перемикання контексту, і необхідністю відповідати на багато одночасних інтерактивних запитів.
Задання надто короткого кванта часу призводить до того, що відбувається дуже багато перемикань контексту, і значний відсоток процесорного часу витрачається не на корисну роботу, а на ці перемикання. З іншого боку, задання надто довгого кванта хоча й заощаджує процесорний час, але спричиняє до зниження часу відгуку на інтерактивні запити, бо якщо десять користувачів одночасно натиснуть клавішу, то десять потоків потраплять у список готових, внаслідок чого останній з них очікуватиме десять довгих квантів часу. У випадку з квантом нескінченної довжини кругове планування зводиться до алгоритму FIFO (усі потоки встигають заблокуватися або закінчитися до вичерпання кванта). На практиці рекомендують встановлювати довжину кванта в 10-100 мс.
Зазначимо, що традиційне кругове планування може давати «перекіс» у бік потоків, обмежених можливостями процесора. Такі потоки переважно використовують свій квант повністю, тоді як потоки, обмежені можливостями введення-виведення, часто передають керування до вичерпання кванта, і в результаті їм дістається менше процесорного часу. Для вирішення цієї проблеми можна збільшувати довжину кванта (з огляду на проблеми, описані раніше) або вводити додаткову чергу потоків, що завершили введення-виведення, яка має перевагу на виконання перед чергою готових потоків.
Циклічне планування (RR)
Циклічне, або кругове (roundrobin, RR). Диспетчеризація виконується за принципом FIFO, але кожний раз процесу надається обмежена кількість часу ЦП, що називається квантом. Процес, у якого був перехоплений ЦП, переходить в кінець списку готових до виконання процесів. Така дисципліна (RR) ефективна для роботи з розподілом часу, коли система повинна гарантувати можливий час відповіді для всіх інтерактивних користувачів.
Визначення оптимального розміру кванту – складна задача. Як правило, його вибирають настільки великим, що більшість тривіальних пересічних запитів можна було б повністю обслужити в рамках одного кванту.