Introduzione à i Sistemi Operativi
Ehi Habr! Vogliu portà à a vostra attenzione una seria di articuli-traduzioni di una literatura interessante in u mo parè - OSTEP. Stu materiale discute assai prufonda u travagliu di i sistemi operativi Unix-like, vale à dì, u travagliu cù prucessi, diversi schedulers, memoria, è altri cumpunenti simili chì custituiscenu un OS mudernu. Pudete vede l'uriginale di tutti i materiali quì . Per piacè nutate chì a traduzzione hè stata fatta senza prufessiunali (abbastanza liberamente), ma spergu chì aghju conservatu u significatu generale.
U travagliu di laboratoriu nantu à questu sughjettu pò esse truvatu quì:
Altre parti:
Pudete ancu verificà u mo canale à =)
Introduzione à Scheduler
L'essenza di u prublema: Cumu sviluppà una pulitica di pianificazione
Cumu deve esse designati i quadri di pulitica di pianificazione sottostanti? Chì duveranu esse l'assunzioni chjave? Chì metrica sò impurtanti? Chì tecniche basi sò state aduprate in i primi sistemi informatici?
Assunzioni di carichi di travagliu
Prima di discutiri di e pussibuli pulitiche, facemu prima uni pochi di digressioni simplificanti nantu à i prucessi in esecuzione in u sistema, chì sò chjamati cullettivamente. carica di travagliu. A definizione di a carica di travagliu hè una parte critica di e pulitiche di custruzzione, è più sapete nantu à a carica di travagliu, megliu a pulitica pudete scrive.
Facemu i seguenti supposizioni nantu à i prucessi in esecuzione in u sistema, qualchì volta chjamati ancu Franchisee (i travaglii). Quasi tutti sti supposizioni ùn sò micca realistichi, ma sò necessarii per u sviluppu di u pensamentu.
- Ogni compitu corre per u listessu tempu,
- Tutti i travaglii sò stabiliti simultaneamente,
- U compitu assignatu travaglia finu à a so cumpleta,
- Tutti i travaglii usanu solu CPU,
- U tempu di esecuzione di ogni compitu hè cunnisciutu.
Scheduler Metrics
In più di certi ipotesi nantu à a carica, un altru strumentu per paragunà e diverse pulitiche di pianificazione hè necessariu: metrica di pianificazione. Una metrica hè solu una misura di qualcosa. Ci hè una quantità di metriche chì ponu esse usate per paragunà i pianificatori.
Per esempiu, avemu aduprà una metrica chjamata tempu di turnaround (tempu di turnu). U tempu di turnaround di u travagliu hè definitu cum'è a diffarenza trà u tempu di cumpiimentu di u compitu è u tempu d'arrivu di u travagliu in u sistema.
Tturnaround=Tcumplementu−Arrivu
Puisque on suppose que toutes les tâches arrivent en même temps, alors Ta=0 et donc Tt=Tc. Stu valore cambierà naturalmente quandu cambiamu l'ipotesi sopra.
Un'altra metrica - ghjustizia (equità, onestà). A produtividade è l'equità sò spessu caratteristiche opposte in a pianificazione. Per esempiu, u pianificatore pò ottimisà u rendiment, ma à u costu d'aspittà chì l'altri travaglii currispondenu, riducendu cusì l'equità.
PRIMO ENTRATA, PRIMA uscita (FIFO)
L'algoritmu più basu chì pudemu implementà hè chjamatu FIFO o primu arrivu (entra), primu servitu (esce). Stu algoritmu hà parechji vantaghji: hè assai faciule da implementà è si adatta à tutti i nostri ipotesi è faci u travagliu abbastanza bè.
Fighjemu un esempiu simplice. Diciamu chì 3 cumpetenze sò state stabilite simultaneamente. Ma supponemu chì u compitu A hè ghjuntu un pocu prima di tutti l'altri, cusì appariscerà in a lista d'esekzione prima di l'altri, cum'è B relative à C. Assumimu chì ognuna di elle serà eseguita per 10 seconde. Chì serà u tempu mediu per compie sti travaglii in questu casu?
Cuntendu i valori - 10 + 20 + 30 è dividendu per 3, avemu u tempu mediu di esecuzione di u prugramma uguale à 20 seconde.
Avà pruvemu à cambià i nostri supposizioni. In particulare, l'assunzione 1 è cusì ùn assumeremu più chì ogni attività piglia a listessa quantità di tempu per eseguisce. Cumu serà u FIFO sta volta?
Comu risulta, i tempi di esecuzione di e funzioni differenti anu un impattu estremamente negativu nantu à a produtividade di l'algoritmu FIFO. Assumimu chì u compitu A duverà 100 seconde per compie, mentre chì B è C duverà sempre 10 seconde ognunu.
Comu pò esse vistu da a figura, u tempu mediu per u sistema serà (100 + 110 + 120) / 3 = 110. Stu effettu hè chjamatu effettu convoi, Quandu certi cunsumatori di cortu termine di una risorsa si mette in fila dopu un cunsumadore pisanti. Hè cum'è a linea in a buttrega quandu ci hè un cliente davanti à voi cù un carrettu pienu. A megliu suluzione à u prublema hè di pruvà à cambià a cash register o rilassate è respira profondamente.
U travagliu più breve prima
Hè pussibule di risolve una situazione simile cù prucessi di pesu pesu? Di sicuru. Un altru tipu di pianificazione hè chjamatuU travagliu più breve prima (SJF). U so algoritmu hè ancu abbastanza primitivu - cum'è u nome implica, i travaglii più brevi seranu lanciati prima, unu dopu l'altru.
In questu esempiu, u risultatu di eseguisce i stessi prucessi serà una mellura in u tempu mediu di turnaround di u prugramma è serà uguali à 50 invece di 110, chì hè quasi 2 volte megliu.
Cusì, per l'assunzione data chì tutti i travaglii ghjunghjenu à u stessu tempu, l'algoritmu SJF pare esse l'algoritmu più ottimali. Tuttavia, i nostri supposizioni ùn parenu micca realistichi. Questa volta cambiamu l'assunzione 2 è sta volta imagine chì i travaglii ponu esse prisenti in ogni mumentu, è micca tutti à u stessu tempu. Chì prublemi pò purtà à questu?
Imagine chì u compitu A (100c) ghjunghje prima è principia à esse eseguitu. À t = 10, ghjunghjenu i travaglii B è C, ognuna di e quali duverà 10 seconde. Allora u tempu d'esekzione mediu hè (100+(110-10)+(120-10))3 = 103. Chì puderia fà u pianificatore per migliurà questu?
U Tempu più Cortu di Cumplementu Prima (STCF)
Per migliurà a situazione, omettemu l'assunzione 3 chì u prugramma hè lanciatu è corre finu à a fine. Inoltre, avemu bisognu di supportu hardware è, cum'è pudete guessà, useremu cronometru per interrompe un compitu in esecuzione è cambià di cuntestu. Cusì, u pianificatore pò fà qualcosa quandu i travaglii B, C ghjunghjenu - cessà di eseguisce u compitu A è mette i travaglii B è C in trasfurmazioni, è dopu a so cumpiimentu cuntinueghjanu à eseguisce u prucessu A. Un tali pianificatore hè chjamatu. STCFo Preemptive Job First.
U risultatu di stu pianificatore serà u risultatu seguente: ((120-0)+(20-10)+(30-10))/3=50. Cusì, un tali pianificatore diventa ancu più ottimale per i nostri compiti.
Tempu di risposta metrica
Cusì, se sapemu u tempu di esecuzione di i travaglii è chì questi compiti usanu solu CPU, STCF serà a megliu suluzione. È una volta in i primi tempi, sti algoritmi travagliavanu abbastanza bè. Tuttavia, l'utilizatori passanu avà a maiò parte di u so tempu à u terminal è aspetta una sperienza interattiva produtiva. Cusì hè natu una nova metrica - tempu di risposta (risposta).
U tempu di risposta hè calculatu cusì:
Tresponse=Tfirstrun−Tarrival
Cusì, per l'esempiu precedente, u tempu di risposta serà: A=0, B=0, C=10 (abg=3,33).
È risulta chì l'algoritmu STCF ùn hè micca cusì bonu in una situazione induve 3 compiti ghjunghjenu à u stessu tempu - duverà aspittà finu à chì i picculi compiti sò cumpletamente cumpleti. Allora l'algoritmu hè bonu per a metrica di u tempu di turnaround, ma male per a metrica di interattività. Immaginate s'è vo site à pusà à un terminal chì prova à scrive caratteri in un editore è avè da aspittà più di 10 seconde perchè un altru compitu occupava u CPU. Ùn hè micca assai piacevule.
Allora avemu affruntatu un altru prublema - cumu pudemu custruisce un pianificatore chì hè sensibile à u tempu di risposta?
Round Robins
Un algoritmu hè statu sviluppatu per risolve stu prublema Round Robins (RR). L'idea basica hè abbastanza sèmplice: invece di eseguisce i travaglii finu à ch'elli sò finiti, eseguiremu u compitu per un certu periodu di tempu (chjamatu un pezzu di tempu) è dopu passà à un altru compitu da a fila. L'algoritmu ripete u so travagliu finu à chì tutti i travaglii sò finiti. In questu casu, u tempu di esecuzione di u prugramma deve esse un multiplu di u tempu dopu chì u timer interromperà u prucessu. Per esempiu, se un timer interrompe un prucessu ogni x = 10 ms, allora a dimensione di a finestra di esecuzione di u prucessu deve esse un multiplu di 10 è esse 10,20 o x * 10.
Fighjemu un esempiu: i travaglii ABC ghjunghjenu simultaneamente in u sistema è ognuna di elle vole eseguisce per 5 seconde. L'algoritmu SJF compie ogni compitu prima di inizià un altru. In cuntrastu, l'algoritmu RR cù una finestra di lanciamentu = 1s hà da passà per i travaglii cusì (Fig. 4.3):
(SJF Again (Bad for Response Time)
(Round Robin (Bonu per u tempu di risposta)
U tempu di risposta mediu per l'algoritmu RR hè (0+1+2)/3=1, mentri per l'SJF (0+5+10)/3=5.
Hè logicu di assume chì a finestra di u tempu hè un paràmetru assai impurtante per RR; u più chjucu hè, u più altu u tempu di risposta. Tuttavia, ùn deve micca fà troppu chjucu, postu chì u tempu di cambiamentu di u cuntestu ghjucà ancu un rolu in u rendiment generale. Cusì, l'scelta di u tempu di a finestra di esecuzione hè stabilita da l'architettu di u SO è dipende di i travaglii chì sò previsti per esse eseguiti in questu. U cuntestu di cambiamentu ùn hè micca l'unicu operazione di serviziu chì perde u tempu - u prugramma in esecuzione opera nantu à parechje altre cose, per esempiu, diverse cache, è cù ogni cambiamentu hè necessariu di salvà è restaurà stu ambiente, chì pò ancu piglià assai tempu.
RR hè un grande pianificatore se avemu parlatu solu di a metrica di u tempu di risposta. Ma cumu si cumportarà a metrica di u tempu di turnaround di u travagliu cù questu algoritmu? Cunsiderate l'esempiu sopra, quandu u tempu di funziunamentu di A, B, C = 5s è ghjunghje à u stessu tempu. A Task A finisce à 13, B à 14, C à 15 s è u tempu mediu di turnaround serà 14 s. Cusì, RR hè u peghju algoritmu per a metrica di turnover.
In termini più ginirali, ogni algoritmu di tipu RR hè ghjustu; divide u tempu CPU ugualmente trà tutti i prucessi. È cusì, sti metrichi cunflitti constantemente cù l'altri.
Cusì, avemu parechji algoritmi cuntrastanti è à u stessu tempu ci sò sempre parechje ipotesi - chì u tempu di u travagliu hè cunnisciutu è chì u compitu usa solu u CPU.
Mélange avec I/O
Prima di tuttu, sguassate l'assunzione 4 chì u prucessu usa solu u CPU; naturalmente, questu ùn hè micca u casu è i prucessi ponu accede à altre equipaghji.
U mumentu chì ogni prucessu richiede una operazione I/O, u prucessu entra in u statu bluccatu, aspittendu chì l'I/O finisci. Se l'I / O hè mandatu à u discu duru, una tale operazione pò piglià à parechji ms o più longu, è u processatore serà inattivu in questu mumentu. Duranti stu tempu, u pianificatore pò occupà u processatore cù qualsiasi altru prucessu. A prossima decisione chì u pianificatore duverà fà hè quandu u prucessu compie u so I / O. Quandu succede questu, una interruzzione accade è u SO metterà u prucessu chì chjamava l'I / O in u statu prontu.
Fighjemu un esempiu di parechje attività. Ognunu di elli richiede 50 ms di tempu CPU. Tuttavia, u primu accede à l'I / O ogni 10ms (chì serà ancu eseguitu ogni 10ms). È u prucessu B usa simpricimenti un processore 50ms senza I/O.
In questu esempiu useremu u pianificatore STCF. Cumu si cumportarà u pianificatore se un prucessu cum'è A hè lanciatu nantu à questu? Farà i seguenti: prima hà da travaglià cumpletamente u prucessu A, è dopu u prucessu B.
L'approcciu tradiziunale per risolve stu prublema hè di trattà ogni subtask di 10 ms di u prucessu A cum'è un compitu separatu. Cusì, quandu si principia cù l'algoritmu STJF, a scelta trà un compitu di 50 ms è un compitu di 10 ms hè evidenti. Dopu, quandu u subtask A hè cumpletu, u prucessu B è I / O seranu lanciati. Dopu chì l'I / O cumpleta, serà abitudine di inizià u prucessu 10ms A di novu invece di u prucessu B. In questu modu, hè pussibule implementà a superposizione, induve a CPU hè utilizata da un altru prucessu mentre chì u primu hè aspittatu per u prucessu. I/O. È in u risultatu, u sistema hè megliu utilizatu - in u mumentu chì i prucessi interattivi aspettanu I / O, altri prucessi ponu esse eseguiti nantu à u processatore.
L'Oraculu ùn hè più
Avà, pruvemu di sguassà l'assunzione chì u tempu di esecuzione di u compitu hè cunnisciutu. Questu hè in generale l'assunzione peghju è più irrealisticu di tutta a lista. In fattu, in u SO ordinariu mediu, u SO stessu di solitu sapi pocu di u tempu d'esekzione di i travaglii, allora cumu pudete custruisce un pianificatore senza sapè quantu durarà u compitu per eseguisce? Forsi pudemu usà alcuni principii RR per risolve stu prublema?
U risultatu
Avemu guardatu l'idee basi di a pianificazione di u travagliu è fighjatu à 2 famiglie di pianificatori. U primu principia u travagliu più curtu prima è cusì aumenta u tempu di turnaround, mentre chì u sicondu hè strappatu trà tutti i travaglii ugualmente, aumentendu u tempu di risposta. I dui algoritmi sò cattivi induve l'algoritmi di l'altra famiglia sò boni. Avemu ancu guardatu cumu l'usu parallelu di CPU è I / O pò migliurà u rendiment, ma ùn hà micca risolviu u prublema cù a clarividenza OS. È in a prossima lezione fighjemu un pianificatore chì guarda in u passatu immediata è prova di predichendu u futuru. È hè chjamatu fila di feedback multi-livellu.
Source: www.habr.com