Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



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

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

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

 

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

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

 

 

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

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

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

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

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

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

 

 

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

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

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

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

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

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

 


Читайте також:

  1. Абстрактна модель оптимального планування виробництва
  2. Алгоритм планування податкових платежів. Вибір оптимального варіанту оподаткування та сплати податків.
  3. Аналіз та планування витрат організації на професійне навчання персоналу
  4. Бар’єри стратегічного планування та заходи щодо їх подолання
  5. Бізнес-план як один із головних інструментів редакційного планування
  6. Бізнес-планування
  7. Бізнес-планування інвестиційного проекту. Розробка планів фінансового проекту
  8. Бізнес-планування, його суть та призначення
  9. Бюджетне планування
  10. Бюджетне планування та прогнозування.
  11. Бюджетне планування.
  12. Бюджетне фінансове планування.




Переглядів: 2044

<== попередня сторінка | наступна сторінка ==>
Стратегії планування. Витісняльна і невитісняльна багатозадачність. | Подальшого виконання

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

  

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.003 сек.