Планувальник потоків

Планува́ння викона́ння завда́нь (англ. Scheduling) є однією з ключових концепцій в багатозадачності і багатопроцесорних систем, як в операційних системах загального призначення, так і в операційних системах реального часу. Планування полягає в призначенні пріоритетів процесам в черзі з пріоритетами. Утиліта, що виконує це завдання, називається планувальником (англ. Scheduler).

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

• Використання процесора(-ів) — дати завдання процесору, якщо це можливо.
• Пропускна здатність — кількість процесів, що виконуються за одиницю часу.
• Час на завдання — кількість часу, для повного виконання певного процесу.
• Очікування — кількість часу, який процес очікує в черзі готових.
• Час відповіді — час, який проходить від подання запиту до першої відповіді на запит.
• Справедливість — рівність процесорного часу для кожної ниті

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

Типи планувальників в операційних системах

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

Довготривалий планувальник

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

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

Середньостроковий планувальник

У всіх системах з віртуальною пам'яттю середньостроковий планувальник тимчасово переміщає (вивантажує) процеси з основної пам'яті у вторинну (наприклад, на жорсткий диск), і навпаки. Ці дії називаються підкачуванням або свопінгом (англ. swapping). Середньостроковий планувальник може ухвалити рішення вивантажити процес з основної пам'яті якщо:

• процес був неактивним якийсь час;
• процес має низький пріоритет;
• процес часто викликає помилки сторінок (page fault);
• процес займає велику частку основної пам'яті, а системі потрібна вільна пам'ять для інших цілей (наприклад, щоб задовольнити запит виділення пам'яті для іншого процесу).

Процес буде повернений в основну пам'ять коли буде доступна необхідна кількість вільної пам'яті, або коли процес вийде з режиму очікування (в цьому випадку планувальник вивантажить з основної пам'яті інший процес для звільнення основної пам'яті).

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

Короткостроковий планувальник

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

Реалізації планувальників в операційних системах

Windows

Докладніше: Планування нитей

Системи MS-DOS і ранні Microsoft Windows не були багатозадачними, і відповідно не мали планувальника. Windows 3.1x використовував неупереджувальний планувальник, і тому не могла переривати програми. Система цілком покладається на програму, коли та скаже ОС, що вона вже не потребує процесора (процесорного часу), і тільки тоді система могла виконувати інший процес. Це звичайно називають кооперативною багатозадачністю. Windows 95 представив зародковий упереджувальний планувальник, проте для сумісності зі спадщиною вирішили дати 16-бітним застосункам запускатися в невитісняючому режимі.

Операційні системи на основі Windows NT використовують чергу з багаторівневим відгуком. Визначені 32 рівнів пріоритету, від 0 до 31, де пріоритети від 0 до 15 є «нормальними» пріоритетами, і пріоритети від 16 до 31 є м'якими пріоритетами реального часу, які вимагають привілеїв призначити їх. «0» зарезервований для операційної системи. Користувач може вибрати 5 з цих пріоритетів і призначити їх своїм застосункам з програми Task Manager або за допомогою API управління нитями. Ядро може змінити рівень пріоритету нитки в залежності від його операцій введення-виведення, завантаження процесора і навіть інтерактивно (тобто приймає і реагує на вимогу людини). Планувальник Windows Vista був змінений, щоб задіяти циклічні регістри-лічильники сучасних процесорів відслідковувати скільки точно циклів процесора виконується нить, а не тільки коли інтервал-таймер перериває виконання. Vista використовує також пріоритети планувальника для черги введення-виведення, щоб дефрагментація диску та інші подібні фонові операції не втручалися в роботу основних процедур.

Mac

Mac OS 9 використовував кооперативний планувальник, коли один процес контролює кілька кооперативних ниток. Використовувався простий алгоритм циклічного планування (англ. round-robin) без пріоритетів. Кожен процес мав свою власну копію диспетчера потоків виконання, в той час як ядро, використовуючи алгоритм упереджувального планування, розподіляло поміж всіх наявних задач час процесора.^[]

Mac OS X використовує ниті Mach, і кожна нитка пов'язана з власним окремим процесом. Якщо ниті в певний час кооперативні, тоді тільки одна може працювати одночасно. Нить повинна відмовитися від свого права на процесор, щоб виконувалися інші процеси.

Linux

Починаючи з версії 2.5 ядро Linux використовує з пріоритетами 0-140. 0-99 зарезервовані для задач реального часу, а 100—140 виділені для задач рівня nice. Для завдань реального часу інтервал перемикання процесів становить близько 200 мс(мкс/нс?) і 10 мс для задач nice. Планувальник проходить через всю чергу готових процесів, дозволяючи спочатку пройти найвищим з них і запускаючи їх через зріз часу, а і поміщає їх в чергу закінчених. Потім, коли черга активних задач порожня, черга виконаних знов стає активною, і навпаки. З версії 2.6 до 2.6.23, ядро використовує планувальник O(1). У версії 2.6.23 цей метод було замінено на , який використовує Червоно-чорне дерево замість черги.

Примітки

1. Early Windows. Архів оригіналу за 7 червня 2009. Процитовано 5 червня 2009.
2. Windows NT^{[недоступне посилання з липня 2019]}
3. Inside the Windows Vista Kernel: Part 1, Microsoft Technet
4. Vista Kernel Vista Kernel. Архів оригіналу за 19 лютого 2008. Процитовано 5 червня 2009.
5. Mac OS X
6. Information on CFS. Архів оригіналу за 19 липня 2012. Процитовано 19 липня 2012.

Література

• The Linux scheduler: a decade of wasted cores // Proceedings of the Eleventh European Conference on Computer Systems. — ACM Press, 2016. — 28 листопада. — С. 1–16. — . — DOI:10.1145/2901318.2901326. Процитовано 2016-04-21.