Timpul de execu\u021bie al fiec\u0103rei sarcini este cunoscut.<\/li>\n<\/ol>\nMetricile Planificatorului<\/h3>\n \n Pe l\u00e2ng\u0103 unele presupuneri despre sarcin\u0103, este nevoie de un instrument de comparare a diferitelor politici de planificare: metricile planificatorului. O metric\u0103 este pur \u0219i simplu o m\u0103sur\u0103 a ceva. Exist\u0103 un anumit num\u0103r de metrici care pot fi folosite pentru compararea planificatorilor.<\/p>\n
Ca exemplu, vom folosi o metric\u0103 numit\u0103 timp de rota\u021bie<\/b> (turnaround time). Timpul de rota\u021bie al unei sarcini este definit ca diferen\u021ba dintre timpul finaliz\u0103rii sarcinii \u0219i timpul la care sarcina a fost introdus\u0103 \u00een sistem.<\/p>\n
Tturnaround=Tfinalizare\u2212Tintrare<\/u><\/p>\n
Deoarece am presupus c\u0103 toate sarcinile au fost introduse \u00een acela\u0219i timp, atunci Ta=0 \u0219i astfel Tt=Tc. Aceast\u0103 valoare se va schimba natural atunci c\u00e2nd vom modifica presupunerile men\u021bionate anterior.<\/p>\n
O alt\u0103 metric\u0103 \u2014 fairness<\/b> (fairness, echitate). Performan\u021ba \u0219i echitatea sunt adesea caracteristici opuse \u00een planificare. De exemplu, un planificator poate optimiza performan\u021ba, dar \u00een detrimentul a\u0219tept\u0103rii ini\u021bierii altor sarcini, reduc\u00e2nd astfel echitatea.<\/p>\nFIRST IN FIRST OUT (FIFO)<\/h3>\n
\n Cel mai de baz\u0103 algoritm pe care \u00eel putem implementa se nume\u0219te FIFO sau first come (in), first served (out)<\/b>. Acest algoritm are c\u00e2teva avantaje: este foarte simplu de implementat \u0219i se potrive\u0219te cu toate ipotezele noastre, realiz\u00e2nd sarcina destul de bine.<\/p>\n
S\u0103 lu\u0103m un exemplu simplu. S\u0103 presupunem c\u0103 3 sarcini au fost atribuite simultan. Dar s\u0103 presupunem c\u0103 sarcina A a sosit pu\u021bin mai devreme dec\u00e2t celelalte, a\u0219a c\u0103 va ap\u0103rea mai devreme \u00een lista de execu\u021bie, la fel cum B se va afla rela\u021bionat cu V. S\u0103 presupunem c\u0103 fiecare dintre ele va fi executat\u0103 timp de 10 secunde. Care va fi astfel timpul mediu de execu\u021bie pentru aceste sarcini?<\/p>\n
Se dovede\u0219te c\u0103 timpii de execu\u021bie diferite ale sarcinilor au un impact extrem de negativ asupra productivit\u0103\u021bii algoritmului FIFO. S\u0103 presupunem c\u0103 sarcina A se va executa timp de 100 de secunde, \u00een timp ce B \u0219i V vor continua s\u0103 dureze c\u00e2te 10 fiecare.<\/p>\n
efectul convoiului<\/b>, atunci c\u00e2nd anumi\u021bi consumatori de scurt\u0103 durat\u0103 ai unei resurse vor sta \u00een a\u0219teptare \u00een spatele unui consumator greu. Este asem\u0103n\u0103tor cu o coad\u0103 la magazinul alimentar, c\u00e2nd \u00eenaintea ta se afl\u0103 un cump\u0103r\u0103tor cu un c\u0103rucior plin. Cea mai bun\u0103 solu\u021bie pentru problem\u0103 este s\u0103 \u00eencerci s\u0103 schimbi casa de marcat sau s\u0103 te relaxezi \u0219i s\u0103 respiri ad\u00e2nc.<\/p>\nShortest Job First<\/h3>\n
\n Se poate solu\u021biona cumva o astfel de situa\u021bie cu procese greoaie? Desigur. Un alt tip de planificare se nume\u0219teShortest Job First<\/b> (SJF). Algoritmul s\u0103u este, de asemenea, destul de primitiv \u2014 dup\u0103 cum sugereaz\u0103 \u0219i numele, sarcinile cele mai scurte vor fi executate prima dat\u0103, una dup\u0103 alta.<\/p>\n
50 \u00een loc de 110<\/b>, ceea ce este practic de 2 ori mai bine.<\/p>\n
Astfel, conform presupunerii c\u0103 toate sarcinile sosesc \u00een acela\u0219i timp, algoritmul SJF pare a fi cel mai optim algoritm. Totu\u0219i, presupunerile noastre \u00eenc\u0103 nu par realiste. De data aceasta, vom schimba presupunerea 2 \u0219i vom considera c\u0103 sarcinile pot sosi \u00een orice moment, nu toate simultan. Ce probleme poate cauza acest lucru?<\/p>\n
Shortest Time-to-Completion First (STCF)<\/h3>\n \n Pentru a \u00eembun\u0103t\u0103\u021bi situa\u021bia, vom renun\u021ba la presupunerea 3 conform c\u0103reia programul este lansat \u0219i ruleaz\u0103 p\u00e2n\u0103 la final. De asemenea, vom avea nevoie de suport hardware \u0219i, dup\u0103 cum probabil a\u021bi ghicit, vom folosi un temporizator<\/b> pentru a \u00eentrerupe sarcina \u00een execu\u021bie \u0219i a schimba contexte<\/b>. Astfel, programatorul poate \u00eentreprinde ceva \u00een momentul sosirii sarcinilor B \u0219i C \u2014 s\u0103 opreasc\u0103 execu\u021bia sarcinii A \u0219i s\u0103 proceseze sarcinile B \u0219i C, iar dup\u0103 finalizarea acestora, s\u0103 continue execu\u021bia procesului A. Acest tip de programator se nume\u0219te STCF<\/b>sau Preemptive Job First<\/b>.<\/p>\n
Metrica Timp de r\u0103spuns (Response Time)<\/h3>\n \n Astfel, dac\u0103 \u0219tim timpul de execu\u021bie al sarcinilor \u0219i faptul c\u0103 aceste sarcini folosesc doar CPU, STCF va fi cea mai bun\u0103 solu\u021bie. \u0218i \u00een vremurile de mult uitate, aceste algoritmi au func\u021bionat destul de bine. Totu\u0219i, acum utilizatorul \u00ee\u0219i petrece cea mai mare parte a timpului la terminal \u0219i a\u0219teapt\u0103 interac\u021biuni interactive eficiente. A\u0219a a ap\u0103rut o nou\u0103 metric\u0103 \u2014 timp de r\u0103spuns<\/b> (response).<\/p>\n
Timpul de r\u0103spuns se calculeaz\u0103 astfel:<\/p>\n
Tresponse=Tfirstrun\u2212Tarrival<\/u><\/p>\n
Astfel, pentru exemplul anterior, timpul de r\u0103spuns va fi: A=0, B=0, C=10 (abg=3,33).<\/p>\n
Se pare c\u0103 algoritmul STCF nu este at\u00e2t de bun \u00een situa\u021bia \u00een care 3 sarcini sosesc simultan \u2014 va trebui s\u0103 a\u0219tepte p\u00e2n\u0103 c\u00e2nd sarcinile mici se finalizeaz\u0103 complet. Astfel, algoritmul este bun pentru metrica timpului de rota\u021bie, dar slab pentru metrica interactivit\u0103\u021bii. Imagina\u021bi-v\u0103 c\u0103, a\u0219ezat la un terminal, \u00eencerc\u00e2nd s\u0103 tasta\u021bi caractere \u00eentr-un editor, trebuie s\u0103 a\u0219tepta\u021bi mai mult de 10 secunde deoarece o alt\u0103 sarcin\u0103 ocup\u0103 procesorul. Nu este deloc pl\u0103cut.<\/p>\n
Round Robin<\/h3>\n \n Pentru a rezolva aceast\u0103 problem\u0103, a fost dezvoltat un algoritm Round Robin<\/b> (RR). Ideea de baz\u0103 este destul de simpl\u0103: \u00een loc s\u0103 lans\u0103m sarcinile p\u00e2n\u0103 la completarea lor, vom rula o sarcin\u0103 pentru un anumit interval de timp (numit cuant\u0103 de timp) \u0219i apoi vom comuta la o alt\u0103 sarcin\u0103 din coad\u0103. Algoritmul repet\u0103 aceast\u0103 procedur\u0103 p\u00e2n\u0103 c\u00e2nd toate sarcinile sunt terminate. Timpul de execu\u021bie al programului trebuie s\u0103 fie multiplu al intervalului de timp \u00een care temporizatorul va \u00eentrerupe procesul. De exemplu, dac\u0103 temporizatorul \u00eentrerupe procesul la fiecare x=10ms, atunci dimensiunea ferestrei de execu\u021bie a procesului trebuie s\u0103 fie multiplu de 10 \u0219i s\u0103 fie 10, 20 sau x*10.<\/p>\n
S\u0103 lu\u0103m un exemplu: Sarcinile A, B, C sosesc simultan \u00een sistem \u0219i fiecare dintre ele dore\u0219te s\u0103 ruleze 5 secunde. Algoritmul SJF va executa fiecare sarcin\u0103 p\u00e2n\u0103 la finalizare \u00eenainte de a lansa o alta. Spre deosebire de algoritmul RR cu fereastra de execu\u021bie=1s, va parcurge sarcinile \u00een urm\u0103torul mod (fig. 4.3):<\/p>\n
Timpul mediu de r\u0103spuns pentru algoritmul RR (0+1+2)\/3=1, \u00een timp ce pentru SJF (0+5+10)\/3=5.<\/p>\n
Este logic s\u0103 presupunem c\u0103 fereastra de timp este un parametru foarte important pentru RR; cu c\u00e2t este mai mic\u0103, cu at\u00e2t timpul de r\u0103spuns este mai mare. Totu\u0219i, nu trebuie s\u0103 fie prea mic\u0103, deoarece timpul de schimbare a contextului va juca, de asemenea, un rol \u00een performan\u021ba general\u0103. Astfel, alegerea timpului de fereastr\u0103 de execu\u021bie este stabilit\u0103 de arhitectul sistemului de operare \u0219i depinde de sarcinile care sunt planificate a fi executate. Schimbarea contextului nu este singura opera\u021bie de serviciu care consum\u0103 timp - programul \u00een execu\u021bie opereaz\u0103 \u0219i cu diverse cache-uri, iar la fiecare schimbare este necesar\u0103 salvarea \u0219i restaurarea acestui mediu, ceea ce poate necesita, de asemenea, mult timp.<\/p>\n
RR este un planificator excelent, dac\u0103 ne g\u00e2ndim doar la metricile timpului de r\u0103spuns. Dar cum se va comporta metrica timpului de \u00eentoarcere a sarcinii \u00een acest algoritm? S\u0103 lu\u0103m exemplul de mai sus, c\u00e2nd timpul de execu\u021bie pentru A, B, C este de 5s \u0219i ajung \u00een acela\u0219i timp. Sarcina A se va finaliza la 13s, B la 14s, C la 15s, iar timpul mediu de \u00eentoarcere va fi de 14s. Astfel, RR este cel mai slab algoritm pentru metricile de \u00eentoarcere.<\/p>\n
\u00cen termeni mai generali, orice algoritm de tip RR este corect, \u00eemp\u0103r\u021bind timpul de lucru pe CPU \u00een mod egal \u00eentre toate procesele. Astfel, aceste metrici intr\u0103 constant \u00een conflict \u00eentre ele.<\/p>\n
Prin urmare, avem mai multe algoritmi opu\u0219i \u0219i, \u00een acela\u0219i timp, \u00eenc\u0103 mai r\u0103m\u00e2n c\u00e2teva presupuneri - c\u0103 timpul sarcinii este cunoscut \u0219i c\u0103 sarcina utilizeaz\u0103 doar CPU.<\/p>\n
Amestecarea cu I\/O<\/h3>\n \n \u00cen primul r\u00e2nd, s\u0103 elimin\u0103m presupunerea 4, c\u0103 procesul utilizeaz\u0103 doar CPU; desigur, nu este a\u0219a, iar procesele pot accesa \u0219i alte echipamente.<\/p>\n
\u00cen momentul \u00een care un proces solicit\u0103 o opera\u021bie de intrare-ie\u0219ire, acesta trece \u00een starea blocat\u0103, a\u0219tept\u00e2nd finalizarea I\/O. Dac\u0103 I\/O este trimis c\u0103tre hard disk, aceast\u0103 opera\u021bie poate dura p\u00e2n\u0103 la c\u00e2teva ms sau mai mult, iar procesorul va fi inactiv \u00een acest moment. \u00cen acest timp, planificatorul poate ocupa procesorul cu un alt proces. Urm\u0103toarea decizie pe care va trebui s\u0103 o ia planificatorul este c\u00e2nd procesul va finaliza I\/O. C\u00e2nd se \u00eent\u00e2mpl\u0103 asta, va avea loc o \u00eentrerupere \u0219i sistemul de operare va schimba procesul care a solicitat I\/O \u00een starea de preg\u0103tire.<\/p>\n
S\u0103 lu\u0103m un exemplu din mai multe sarcini. Fiecare dintre ele necesit\u0103 50ms de timp de procesor. Totu\u0219i, prima va accesa I\/O la fiecare 10ms (care va fi de asemenea executat la fiecare 10ms). Procesul B, pe de alt\u0103 parte, folose\u0219te pur \u0219i simplu 50ms de procesor f\u0103r\u0103 I\/O.<\/p>\n
Oracolul nu mai exist\u0103<\/h3>\n \n Acum s\u0103 \u00eencerc\u0103m s\u0103 sc\u0103p\u0103m de presupunerea c\u0103 timpul de execu\u021bie al sarcinii este cunoscut. Aceasta este, \u00een general, cea mai proast\u0103 \u0219i nerealist\u0103 presupunere din \u00eentreaga list\u0103. De fapt, \u00een sistemele de operare medii, OS-ul \u00eensu\u0219i \u0219tie foarte pu\u021bin despre timpul de execu\u021bie al sarcinilor, cum atunci s\u0103 construim un programator f\u0103r\u0103 a \u0219ti c\u00e2t timp va dura execu\u021bia unei sarcini? Poate am putea folosi unele principii RR pentru a rezolva aceast\u0103 problem\u0103?<\/p>\n
Rezultatul<\/h3>\n \n Am examinat conceptele de baz\u0103 ale program\u0103rii sarcinilor \u0219i am analizat dou\u0103 familii de programatori. Primul ruleaz\u0103 sarcina cea mai scurt\u0103 la \u00eenceput, astfel cre\u0219te timpul de rota\u021bie, iar al doilea se \u00eemparte uniform \u00eentre toate sarcinile, sporind timpul de r\u0103spuns. Ambele algoritmi sunt slabi \u00een domeniile \u00een care sunt buni algoritmii celeilalte familii. De asemenea, am v\u0103zut cum utilizarea paralel\u0103 a CPU \u0219i I\/O poate \u00eembun\u0103t\u0103\u021bi performan\u021ba, dar nu am rezolvat problema viziunii sistemului de operare. \u00cen urm\u0103toarea lec\u021bie, vom analiza un programator care se uit\u0103 \u00een trecutul apropiat \u0219i \u00eencearc\u0103 s\u0103 prezic\u0103 viitorul. Acesta se nume\u0219te coada de feedback multi-nivel.habr.com<\/a><\/p>","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"excerpt":{"rendered":"\u0412\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0432 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u043e\u043d\u043d\u044b\u0435 \u0441\u0438\u0441\u0442\u0435\u043c\u044b \u041f\u0440\u0438\u0432\u0435\u0442, \u0425\u0430\u0431\u0440! \u0425\u043e\u0447\u0443 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0432\u0430\u0448\u0435\u043c\u0443 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u044e \u0441\u0435\u0440\u0438\u044e \u0441\u0442\u0430\u0442\u0435\u0439-\u043f\u0435\u0440\u0435\u0432\u043e\u0434\u043e\u0432 \u043e\u0434\u043d\u043e\u0439 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e\u0439 \u043d\u0430 \u043c\u043e\u0439 \u0432\u0437\u0433\u043b\u044f\u0434 \u043b\u0438\u0442\u0435\u0440\u0430\u0442\u0443\u0440\u044b \u2014 OSTEP. \u0412 \u044d\u0442\u043e\u043c \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b\u0435 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0433\u043b\u0443\u0431\u043e\u043a\u043e \u0440\u0430\u0431\u043e\u0442\u0430 unix-\u043f\u043e\u0434\u043e\u0431\u043d\u044b\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u043e\u043d\u043d\u044b\u0445 \u0441\u0438\u0441\u0442\u0435\u043c, \u0430 \u0438\u043c\u0435\u043d\u043d\u043e \u2014 \u0440\u0430\u0431\u043e\u0442\u0430 \u0441 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0430\u043c\u0438, \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u043c\u0438 \u043f\u043b\u0430\u043d\u0438\u0440\u043e\u0432\u0449\u0438\u043a\u0430\u043c\u0438, \u043f\u0430\u043c\u044f\u0442\u044c\u044e \u0438 \u043f\u0440\u043e\u0447\u0438\u0438\u043c\u0438 \u043f\u043e\u0434\u043e\u0431\u043d\u044b\u043c\u0438 \u043a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442\u0430\u043c\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u044e\u0442 \u0441\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u0443\u044e \u041e\u0421. \u041e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0432\u0441\u0435\u0445 \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b\u043e\u0432 \u0432\u044b \u043c\u043e\u0436\u0435\u0442\u0435 \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u0432\u043e\u0442 \u0442\u0443\u0442. […]<\/p>\n","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"author":1,"featured_media":23990,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[688],"tags":[],"class_list":["post-32158","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-administrirovanie"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t