Планува́ння викона́ння завда́нь (англ. 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 цей метод було замінено на , який використовує Червоно-чорне дерево замість черги.
Примітки
- . Архів оригіналу за 7 червня 2009. Процитовано 5 червня 2009.
- Windows NT[недоступне посилання з липня 2019]
- Inside the Windows Vista Kernel: Part 1, Microsoft Technet
- . Архів оригіналу за 19 лютого 2008. Процитовано 5 червня 2009.
- Mac OS X
- 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. — 2 червня. — С. 1–16. — . — DOI: . Процитовано 2016-04-21.
Це незавершена стаття про операційні системи. Ви можете проєкту, виправивши або дописавши її. |
Це незавершена стаття з інформатики. Ви можете проєкту, виправивши або дописавши її. |
Ця стаття не містить . (травень 2016) |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Planuva nnya vikona nnya zavda n angl Scheduling ye odniyeyu z klyuchovih koncepcij v bagatozadachnosti i bagatoprocesornih sistem yak v operacijnih sistemah zagalnogo priznachennya tak i v operacijnih sistemah realnogo chasu Planuvannya polyagaye v priznachenni prioritetiv procesam v cherzi z prioritetami Utilita sho vikonuye ce zavdannya nazivayetsya planuvalnikom angl Scheduler Najvazhlivishoyu metoyu planuvannya zavdan ye yaknajpovnishe zavantazhennya dostupnih resursiv Dlya zabezpechennya zagalnoyi produktivnosti sistemi planuvalnik maye opiratisya na Vikoristannya procesora iv dati zavdannya procesoru yaksho ce mozhlivo Propuskna zdatnist kilkist procesiv sho vikonuyutsya za odinicyu chasu Chas na zavdannya kilkist chasu dlya povnogo vikonannya pevnogo procesu Ochikuvannya kilkist chasu yakij proces ochikuye v cherzi gotovih Chas vidpovidi chas yakij prohodit vid podannya zapitu do pershoyi vidpovidi na zapit Spravedlivist rivnist procesornogo chasu dlya kozhnoyi niti U seredovishah obchislen realnogo chasu napriklad na pristroyah priznachenih dlya avtomatichnogo upravlinnya v promislovosti napriklad robototehnika planuvalnik zavdan povinen zabezpechiti vikonannya procesiv v perebigu zadanih chasovih promizhkiv chas vidguku ce kritichno dlya pidtrimki korektnoyi roboti sistemi realnogo chasu Tipi planuvalnikiv v operacijnih sistemahOperacijni sistemi mozhut vklyuchati do troh riznih tipiv planuvalnikiv dovgotrivalij planuvalnik abo planuvalnik dozvolu vikonannya serednostrokovij planuvalnik i korotkostrokovij planuvalnik takozh vidomij yak dispetcher Sami nazvi vzhe opisuyut vidnosnu chastotu z yakoyu planuvalnik vikonuye svoyi funkciyi Dovgotrivalij planuvalnik Dovgotrivalij planuvalnik virishuye yaki zavdannya abo procesi budut dodani v chergu procesiv gotovih do vikonannya tobto koli provoditsya sproba zapusku procesu dovgotrivalij planuvalnik abo dodaye novij proces v chergu gotovih procesiv dopuskaye do vikonannya abo vidkladaye cyu diyu Takim chinom dovgotrivalij planuvalnik virishuye yaki procesi vikonuvatimutsya odnochasno tim samim kontrolyuyuchi stupin paralelizmu i proporciyu mizh procesami sho intensivno vikonuyut vvedennya vivedennya i procesami sho intensivno vikoristovuyut procesor Zazvichaj v nastilnih komp yuterah ne zastosovuyetsya dovgotrivalij planuvalnik i novi procesi dopuskayutsya do vikonannya avtomatichno Ale cej planuvalnik duzhe vazhlivij dlya sistem realnogo chasu oskilki pri nadmirnomu navantazhenni sistemi procesami sho paralelno vikonuyutsya chas vidguku sistemi mozhe stati bilshe potribnogo sho nepripustimo Serednostrokovij planuvalnik U vsih sistemah z virtualnoyu pam yattyu serednostrokovij planuvalnik timchasovo peremishaye vivantazhuye procesi z osnovnoyi pam yati u vtorinnu napriklad na zhorstkij disk i navpaki Ci diyi nazivayutsya pidkachuvannyam abo svopingom angl swapping Serednostrokovij planuvalnik mozhe uhvaliti rishennya vivantazhiti proces z osnovnoyi pam yati yaksho proces buv neaktivnim yakijs chas proces maye nizkij prioritet proces chasto viklikaye pomilki storinok page fault proces zajmaye veliku chastku osnovnoyi pam yati a sistemi potribna vilna pam yat dlya inshih cilej napriklad shob zadovolniti zapit vidilennya pam yati dlya inshogo procesu Proces bude povernenij v osnovnu pam yat koli bude dostupna neobhidna kilkist vilnoyi pam yati abo koli proces vijde z rezhimu ochikuvannya v comu vipadku planuvalnik vivantazhit z osnovnoyi pam yati inshij proces dlya zvilnennya osnovnoyi pam yati U bagatoh suchasnih sistemah sho pidtrimuyut vidobrazhennya virtualnogo adresnogo prostoru na vtorinnu pam yat vidminnu vid fajlu pidkachuvannya serednostrokovij planuvalnik mozhe odnochasno grati rol i dovgotrivalogo planuvalnika rozglyadayuchi novi procesi yak procesi yaki buli vivantazheni z osnovnoyi pam yati Takim chinom sistema mozhe pidvantazhuvati v osnovnu pam yat programnij kod tilki todi koli vin znadobitsya procesu dlya vikonannya ce nazivayetsya zavantazhennyam na vimogu abo ledachim zavantazhennyam dzherelo Korotkostrokovij planuvalnik Korotkostrokovij planuvalnik takozh vidomij yak dispetcher abo sheduler virishuye yaki z gotovih procesiv u pam yati mayut buti vikonani viddanni na vikonannya CP za nastupnim pererivannyam godinnika pererivannyam vvedennya vivedennya sistemnim viklikom abo vid inshoyi formi signalu Takim chinom korotkostrokovij planuvalnik robit planuvannya rishen nabagato chastishe nizh dovgostrokovi i serednostrokovi planuvalniki shonajmenshe odne rishennya maye buti zroblene pislya kozhnogo chasu kvantuvannya procesu a ce duzhe korotkij promizhok Ce planuvalnik mozhe uperedzhuvalnij abo vitisnyayuchij mayetsya na uvazi sho vin zdatnij primusovo vidaliti procesi z procesora yaksho vin virishit peredati procesor inshomu procesu abo ne uperedzhuvalnij takozh vidome yak dobrovilnij abo kooperativnij v yakomu planuvalnik ne v sili viluchiti proces vid procesora Realizaciyi planuvalnikiv v operacijnih sistemah Windows Dokladnishe Planuvannya nitej Sistemi MS DOS i ranni Microsoft Windows ne buli bagatozadachnimi i vidpovidno ne mali planuvalnika Windows 3 1x vikoristovuvav neuperedzhuvalnij planuvalnik i tomu ne mogla pererivati programi Sistema cilkom pokladayetsya na programu koli ta skazhe OS sho vona vzhe ne potrebuye procesora procesornogo chasu i tilki todi sistema mogla vikonuvati inshij proces Ce zvichajno nazivayut kooperativnoyu bagatozadachnistyu Windows 95 predstaviv zarodkovij uperedzhuvalnij planuvalnik prote dlya sumisnosti zi spadshinoyu virishili dati 16 bitnim zastosunkam zapuskatisya v nevitisnyayuchomu rezhimi Operacijni sistemi na osnovi Windows NT vikoristovuyut chergu z bagatorivnevim vidgukom Viznacheni 32 rivniv prioritetu vid 0 do 31 de prioriteti vid 0 do 15 ye normalnimi prioritetami i prioriteti vid 16 do 31 ye m yakimi prioritetami realnogo chasu yaki vimagayut privileyiv priznachiti yih 0 zarezervovanij dlya operacijnoyi sistemi Koristuvach mozhe vibrati 5 z cih prioritetiv i priznachiti yih svoyim zastosunkam z programi Task Manager abo za dopomogoyu API upravlinnya nityami Yadro mozhe zminiti riven prioritetu nitki v zalezhnosti vid jogo operacij vvedennya vivedennya zavantazhennya procesora i navit interaktivno tobto prijmaye i reaguye na vimogu lyudini Planuvalnik Windows Vista buv zminenij shob zadiyati ciklichni registri lichilniki suchasnih procesoriv vidslidkovuvati skilki tochno cikliv procesora vikonuyetsya nit a ne tilki koli interval tajmer pererivaye vikonannya Vista vikoristovuye takozh prioriteti planuvalnika dlya chergi vvedennya vivedennya shob defragmentaciya disku ta inshi podibni fonovi operaciyi ne vtruchalisya v robotu osnovnih procedur Mac Mac OS 9 vikoristovuvav kooperativnij planuvalnik koli odin proces kontrolyuye kilka kooperativnih nitok Vikoristovuvavsya prostij algoritm ciklichnogo planuvannya angl round robin bez prioritetiv Kozhen proces mav svoyu vlasnu kopiyu dispetchera potokiv vikonannya v toj chas yak yadro vikoristovuyuchi algoritm uperedzhuvalnogo planuvannya rozpodilyalo pomizh vsih nayavnih zadach chas procesora dzherelo Mac OS X vikoristovuye niti Mach i kozhna nitka pov yazana z vlasnim okremim procesom Yaksho niti v pevnij chas kooperativni todi tilki odna mozhe pracyuvati odnochasno Nit povinna vidmovitisya vid svogo prava na procesor shob vikonuvalisya inshi procesi Linux Pochinayuchi z versiyi 2 5 yadro Linux vikoristovuye z prioritetami 0 140 0 99 zarezervovani dlya zadach realnogo chasu a 100 140 vidileni dlya zadach rivnya nice Dlya zavdan realnogo chasu interval peremikannya procesiv stanovit blizko 200 ms mks ns i 10 ms dlya zadach nice Planuvalnik prohodit cherez vsyu chergu gotovih procesiv dozvolyayuchi spochatku projti najvishim z nih i zapuskayuchi yih cherez zriz chasu a i pomishaye yih v chergu zakinchenih Potim koli cherga aktivnih zadach porozhnya cherga vikonanih znov staye aktivnoyu i navpaki Z versiyi 2 6 do 2 6 23 yadro vikoristovuye planuvalnik O 1 U versiyi 2 6 23 cej metod bulo zamineno na yakij vikoristovuye Chervono chorne derevo zamist chergi Primitki Arhiv originalu za 7 chervnya 2009 Procitovano 5 chervnya 2009 Windows NT nedostupne posilannya z lipnya 2019 Inside the Windows Vista Kernel Part 1 Microsoft Technet Arhiv originalu za 19 lyutogo 2008 Procitovano 5 chervnya 2009 Mac OS X Information on CFS Arhiv originalu za 19 lipnya 2012 Procitovano 19 lipnya 2012 LiteraturaThe Linux scheduler a decade of wasted cores Proceedings of the Eleventh European Conference on Computer Systems ACM Press 2016 2 chervnya S 1 16 ISBN 978 1 4503 4240 7 DOI 10 1145 2901318 2901326 Procitovano 2016 04 21 Ce nezavershena stattya pro operacijni sistemi Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi Ce nezavershena stattya z informatiki Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi Cya stattya ne mistit posilan na dzherela Vi mozhete dopomogti polipshiti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Material bez dzherel mozhe buti piddano sumnivu ta vilucheno traven 2016