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 à =)
Pianificazione: Coda di Feedback Multi-Level
In sta cunferenza, avemu da parlà di i prublemi di sviluppà unu di l'approcciu più famosu
pianificazione, chì hè chjamatu Coda di feedback multi-livellu (MLFQ). U MLFQ scheduler hè statu scrittu prima in 1962 da Fernando J. Corbató in un sistema chjamatu
Sistema di Time-Sharing Compatibile (CTSS). Questi travaglii (cumpresi i travaglii più tardi
Multics) sò stati successivamente nominati per un Premiu Turing. U pianificatore era
successivamente migliuratu è acquistatu l'aspettu chì pò esse truvatu digià in
certi sistemi muderni.
L'algoritmu MLFQ prova di risolve 2 prublemi fundamentali di sovrapposizione.
Prima, prova à ottimisà u tempu di turnaround, chì, cum'è avemu discututu in a lettura precedente, hè ottimizatu da u metudu di principià à u capu di a fila più.
compiti brevi. Tuttavia, u SO ùn sà micca quantu durarà questu o quellu prucessu, è questu
cunniscenza necessaria per u funziunamentu di l'algoritmi SJF, STCF. Siconda, MLFQ prova
rende u sistema responsive per l'utilizatori (per esempiu, per quelli chì si sentenu è
fighjendu u screnu mentre aspittendu chì u compitu finisci) è cusì minimizzà u tempu
risposta. Sfurtunatamente, algoritmi cum'è RR riduce u tempu di risposta, ma
avè un male effettu nantu à a metrica di u tempu di turnaround. Da quì u nostru prublema: Cumu cuncepisce
scheduler chì risponde à i nostri bisogni è à u stessu tempu ùn sapi nunda
a natura di u prucessu, in generale? Cumu u pianificatore pò amparà e caratteristiche di i travaglii,
chì lancia è cusì piglià megliu decisioni di pianificazione ?
L'essenza di u prublema: Cumu pianificà u stabilimentu di i travaglii senza cunniscenza perfetta?
Cumu cuncepisce un pianificatore chì minimizza simultaneamente u tempu di risposta
per i travaglii interattivi è à u stessu tempu minimizza u tempu di turnaround senza sapè
cunniscenza di u tempu di esecuzione di u travagliu?
Nota: amparà da avvenimenti precedenti
A fila MLFQ hè un esempiu eccellente di un sistema chì hè furmatu
avvenimenti passati per predichendu u futuru. Tali approcci sò spessu
trovu in u OS (È assai altri rami in l'informatica, cumprese i rami
previsioni di hardware è algoritmi di cache). Escursioni simili
trigger quandu i travaglii anu fasi di cumportamentu è sò cusì prevedibili.
Tuttavia, unu deve esse attentu à sta tecnica, perchè e previsioni sò assai faciuli.
pò turnà à esse sbagliatu è guidà u sistema à piglià decisioni peggiu chè
saria senza cunniscenza.
MLFQ: Reguli di basa
Cunsiderate i reguli basi di l'algoritmu MLFQ. E ancu chì l'implementazioni di stu algoritmu
ci sò parechji, l'avvicinamenti basi sò simili.
In l'implementazione chì avemu da cunsiderà, MLFQ averà parechje
fila separata, ognuna di quali avarà una priorità sfarente. In ogni mumentu,
u compitu prontu per l'esecuzione hè in a stessa fila. MLFQ usa priorità,
per decide quale compitu da eseguisce per l'esecuzione, i.e. compitu cù più altu
priorità (un compitu da a fila cù a più alta priorità) serà lanciatu à u primu
fila.
Di sicuru, ci pò esse più di un compitu in una fila particulare, cusì
cusì avaranu a listessa priorità. In questu casu, u mecanismu serà utilizatu
RR per a pianificazione di u lanciu trà queste attività.
Cusì ghjunghjemu à dui reguli basi per MLFQ:
- Regola 1: Se a priorità (A) > Priorità (B), u compitu A currirà (B ùn serà micca)
- Rule2: Se priorità (A) = Priorità (B), A & B sò cuminciati cù RR
Basatu nantu à ciò chì sopra, l'elementi chjave per a pianificazione di un MLFQ sò
sò priorità. Invece di dà una priorità fissa à ognunu
compitu, MLFQ cambia a so priorità secondu u cumpurtamentu osservatu.
Per esempiu, se un compitu smette constantemente in u CPU mentre aspetta l'input di u teclatu,
MLFQ mantene a priorità di u prucessu alta perchè hè cusì
u prucessu interattivu deve travaglià. Sì, à u cuntrariu, u compitu hè constantemente è
hè CPU intensiva per un longu periodu, MLFQ u downgraderà
una priorità. Cusì, MLFQ studiarà u cumpurtamentu di i prucessi à u mumentu chì sò in esecuzione.
è aduprà cumpurtamenti.
Fighjemu un esempiu di ciò chì e file di fila puderanu esse in un certu puntu
tempu è poi avete qualcosa cum'è questu:
In questu schema, 2 prucessi A è B sò in a fila cù a più alta priorità. Prucessu
C hè in qualchì locu à mezu, è u prucessu D hè à a fine di a fila. Sicondu u sopra
Descrizzione di l'algoritmu MLFQ, u pianificatore eseguirà solu i travaglii cù u più altu
priurità sicondu RR, è i travaglii C, D seranu fora di travagliu.
Naturalmente, una snapshot statica ùn darà micca una stampa cumpleta di cumu funziona MLFQ.
Hè impurtante di capisce esattamente cumu a stampa cambia cù u tempu.
Attempt 1: Cumu cambià a priorità
À questu puntu, avete bisognu di decide cumu MLFQ cambierà u livellu di priorità
compitu (è cusì a pusizione di u compitu in a fila) durante u so ciclu di vita. Per
di questu, avete bisognu di mantene in mente u flussu di travagliu: una certa quantità
compiti interattivi cù tempi di esecuzione brevi (è dunque liberazione frequente
CPU) è parechji travaglii longu chì utilizanu u CPU tuttu u so tempu di travagliu, mentri
U tempu di risposta per tali compiti ùn hè micca impurtante. È cusì pudete fà u primu tentativu
implementà l'algoritmu MLFQ cù e regule seguenti:
- Rule3: Quandu un compitu entra in u sistema, hè postu in a fila cù u più altu
- priurità.
- Rule4a: Se un compitu usa tutta a so finestra di tempu, allora
- a priorità hè calata.
- Rule4b: Se una Task libera u CPU prima chì a so finestra di tempu scade, allora
- ferma cù a stessa priorità.
Esempiu 1: Unicu travagliu longu
Comu pudete vede in questu esempiu, u compitu à l'admission hè stabilitu cù u più altu
priurità. Dopu à una finestra di tempu 10ms, u prucessu hè downgraded in priorità.
pianificatore. Dopu à a prossima finestra di u tempu, u compitu hè infine downgraded à
a priorità più bassa in u sistema, induve ferma.
Esempiu 2: Pigliatu un travagliu curtu
Avà vedemu un esempiu di cumu MLFQ pruvà à avvicinà SJF. In questu
esempiu, dui compiti: A, chì hè un compitu longu in permanenza
occupendu CPU è B, chì hè un cortu compitu interattivu. Suppone
chì A era digià in esecuzione da qualchì tempu à u tempu chì u compitu B hè ghjuntu.
Stu graficu mostra i risultati di u scenariu. Task A, cum'è ogni compitu,
l'usu di u CPU era in fondu. A Task B ghjunghjerà à l'ora T = 100 è serà
pusatu in a fila di a più alta priorità. Siccomu u tempu di corsa hè breve,
si compie prima ch'ellu ghjunghje à l'ultima fila.
Da questu esempiu, avete da capisce u scopu principale di l'algoritmu: postu chì l'algoritmu ùn hè micca
cunnosce un compitu longu o cortu, po prima di tuttu assume chì u compitu
cortu è dà a più alta priorità. S'ellu hè veramente un compitu cortu, allora
eseguirà rapidamente, altrimenti s'ellu hè un compitu longu si move lentamente
in priurità falà è prestu pruvucarà ch'ella hè veramente un travagliu longu chì ùn hè micca
richiede una risposta.
Esempiu 3: E I/O?
Avà fighjemu un esempiu I/O. Cum'è dichjaratu in a regula 4b,
se un prucessu libera u processatore senza avè utilizatu cumplettamente u so tempu di processatore,
tandu ferma à u listessu livellu di priorità. U scopu di sta regula hè abbastanza sèmplice.
- se u travagliu interattivu eseguisce assai I / O, per esempiu, aspittendu
da i tasti di l'utilizatori o di u mouse, un tali compitu liberarà u processatore
davanti à a finestra attribuita. Ùn vulemu micca omette un compitu cusì priurità,
è cusì ferma à u listessu livellu.
Questu esempiu mostra cumu l'algoritmu travaglià cù tali prucessi - task interattivu B, chì solu bisognu di u CPU per 1ms prima di eseguisce.
I / O prucessu è un travagliu longu A, chì usa u CPU tuttu u tempu.
MLFQ mantene u prucessu B à a più alta priorità mentre cuntinueghja
liberate u CPU. Se B hè un compitu interattivu, allura l'algoritmu in questu casu hà righjuntu
u so scopu hè di lanciari rapidamente attività interattive.
Prublemi cù l'algoritmu MLFQ attuale
In l'esempi precedenti, avemu custruitu una versione basica di MLFQ. È pare chì ellu
face u so travagliu bè è ghjustu, distribuzendu u tempu di CPU abbastanza trà
travaglii longu è chì permettenu e travaglii brevi o travaglii chì sò assai accessu
à I/O per processà rapidamente. Sfurtunatamente, stu approcciu cuntene parechji
prublemi seri.
Prima, u prublema di a fami: se u sistema avarà parechji interattivi
compiti, cunsumanu tuttu u tempu di CPU è cusì micca una sola longa
u compitu ùn hà micca a pussibilità di esse eseguitu (sò affamati).
Siconda, l'utilizatori intelligenti puderanu scrive i so prugrammi per quessa
ingannà u pianificatore. U ingannu si trova à fà qualcosa per forza
scheduler per dà u prucessu più tempu CPU. L'algoritmu chì
descrittu sopra hè abbastanza vulnerabile à tali attacchi: prima di a finestra di u tempu hè praticamenti
sopra, avete bisognu di fà una operazione I / O (per alcuni, ùn importa micca u schedariu)
è cusì liberate u CPU. Un tali cumpurtamentu vi permetterà di stà in u listessu
a fila stessu è torna un percentinu più grande di u tempu di CPU. Sè fattu
questu hè currettu (per esempiu, eseguite 99% di u tempu di a finestra prima di liberà u CPU),
un tali compitu pò simpricimenti monopolize lu prucissuri.
Infine, un prugramma pò cambià u so cumpurtamentu cù u tempu. Quelli compiti
chì hà utilizatu u CPU pò diventà interattivu. In u nostru esempiu, simili
i travaglii ùn riceveranu micca trattamentu propiu da u pianificatore, cum'è altri
(urigginali) compiti interattivi.
Quistione à l'audienza: chì attacchi à u pianificatore puderia esse fattu in u mondu mudernu?
Tentativu 2: Aumentà a priorità
Pruvemu di cambià e regule è vede s'ellu pudemu evità prublemi
a fame. Chì pudemu fà per assicurà chì hè in relazione
I travaglii di CPU utteneranu u so tempu (ancu s'ellu ùn hè micca longu).
Comu solu suluzione simplice à u prublema, pudete suggerisce periodicamente
aumentà a priorità di tutti questi compiti in u sistema. Ci sò parechje manere
per ottene questu, pruvemu à implementà qualcosa simplice cum'è un esempiu: traduce
tutti i travaglii à una volta à a più alta priorità, da quì a nova regula:
- Regula 5: Dopu qualchì periodu S, trasfiriri tutti i travaglii in u sistema à a fila più alta.
A nostra nova regula risolve dui prublemi à una volta. Prima, i prucessi
guarantisci micca a fame: i travaglii in a fila più alta sparteranu
u tempu di u processatore secondu l'algoritmu RR è cusì tutti i prucessi riceveranu
tempu di prucissuri. Siconda, s'è qualchi prucessu chì nanzu usatu
solu u processatore diventa interattivu, ferma in a fila cù u più altu
priorità dopu avè ricivutu un impulso à a più alta priorità una volta.
Cunsiderate un esempiu. In questu scenariu, cunzidira un solu prucessu cù l'usu
CPU è dui prucessi interattivi è brevi. À a manca in a figura, a figura mostra u cumpurtamentu senza spinta di priorità, è cusì u travagliu longu cumencia à mori di fame dopu chì duie attività interattive arrivanu in u sistema. In a figura à a diritta, ogni 50ms un aumentu di priorità hè realizatu è cusì tutti i prucessi sò guarantiti per riceve u tempu di processore è seranu periodicamente iniziati. 50ms in questu casu hè pigliatu cum'è un esempiu, in realtà stu numeru hè un pocu più altu.
Hè evidenti chì l'aghjunzione di u tempu di salita periodica S porta à
quistione logica: chì valore deve esse stabilitu? Unu di i meritati
l'ingegneri di sistemi John Ousterhout anu riferitu à quantità simili in i sistemi cum'è voo-doo
custanti, postu ch'elli in qualchì modu necessitanu magia negra per u currettu
espusizioni. E, sfurtunatamenti, S hà un tali gustu. Sè ancu stabilisce u valore
grandi - i travaglii longu moriranu di fame. È s'ellu si mette troppu bassu,
I travaglii interattivi ùn riceveranu micca u tempu CPU propiu.
Tentativu 3: Contabilità megliu
Avà avemu un altru prublema per risolve: cumu micca
permette di ingannà u nostru pianificatore? I culpiti di sta pussibilità sò
regule 4a, 4b chì permettenu à un travagliu di mantene a so priorità per liberà u processatore
prima di a scadenza di u tempu attribuitu. Cumu trattà cun ella?
A suluzione in questu casu pò esse cunsiderata cum'è una cuntabilità megliu di u tempu CPU nantu à ognunu
Livellu MLFQ. Invece di scurdà di u tempu u prugramma utilizatu
processore per l'intervallu attribuitu, duvete piglià in contu è salvà. Dopu
u prucessu hà usatu u so tempu attribuitu, deve esse demoted à u prossimu
livellu di priorità. Avà ùn importa micca cumu u prucessu aduprà u so tempu - cumu
computing constantemente nantu à u processatore o cum'è un gruppu di chjama. Cusì,
A regula 4 deve esse riscritta cum'è seguente:
- Regula 4: Dopu chì un compitu hà utilizatu u so tempu assignatu in a fila attuale (indipendente da quante volte hà liberatu u CPU), a priorità di una tale attività hè ridutta (si move in a fila).
Fighjemu un esempiu:
»
A figura mostra ciò chì succede se pruvate à ingannà u pianificatore cum'è
s'ellu era cù e regule precedente 4a, 4b seria u risultatu à manca. Cù novu
a regula hè chì u risultatu hè à a diritta. Prima di prutezzione, ogni prucessu puderia chjamà I / O prima di cumpiimentu è
cusì domina u CPU, dopu avè attivatu a prutezzione, indipendentemente da u cumpurtamentu
I/O, hà da sempre falà in a fila è cusì ùn puderà micca disonestamente
ripiglià e risorse di CPU.
Migliurà MLFQ è altri prublemi
Cù i migliuramentu di sopra, i prublemi novi nascenu: unu di i principali
dumande - cumu parameterizà un tali pianificatore? Quelli. Quantu deve esse
fila ? Chì deve esse a dimensione di a finestra di u prugramma in a fila? Cumu
prugramma deve esse spessu priurità per evità a fame è
per piglià in contu u cambiamentu in u cumpurtamentu di u prugramma? À queste dumande, ùn ci hè micca simplice
risposta è solu esperimenti cù carichi è cunfigurazione sussegwenti
scheduler pò purtà à qualchì equilibriu satisfacente.
Per esempiu, a maiò parte di l'implementazioni MLFQ permettenu di assignà diverse
intervalli di tempu per diverse file. Fila di alta priorità sò generalmente
intervalli brevi. Queste file sò custituiti da attività interattive,
cambià trà quale hè abbastanza sensibile è deve piglià 10 o menu
ms. In cuntrastu, e file di priorità bassa sò custituiti da travaglii longu chì utilizanu
CPU. È in questu casu, intervalli longu di tempu si adattanu assai bè (100 ms).
In questu esempiu, ci sò 2 attività chì anu travagliatu in a fila di alta priorità 20
ms divisu in Windows 10ms. 40 ms in a fila media (finestra di 20 ms) è in a fila di priorità bassa
A finestra di u tempu di fila hè diventata 40 ms induve i travaglii anu finitu u so travagliu.
L'implementazione di MLFQ in u SO Solaris hè una classa di pianificatori di tempu spartutu.
U pianificatore furnisce un inseme di tavule chì definiscenu esattamente cumu si deve
cambià a priorità di u prucessu nantu à u corsu di a so vita, ciò chì deve esse a taglia
finestra per esse attribuita è quantu spessu suscitarà e priorità di u travagliu. Amministratore
u sistema pò interagisce cù sta tavula è fà cumportà u scheduler
diversamente. Per automaticamente, sta tavola hà 60 file cù un aumentu graduali
dimensione di a finestra da 20ms (priurità alta) à parechji centu ms (priurità più bassa), è
ancu cù u boost di tutti i travaglii una volta à seconda.
L'altri pianificatori MLFQ ùn utilizanu micca una tavola o alcuna specifica
i reguli chì sò discrittu in stu capitulu, à u cuntrariu, calculanu priurità utilizendu
formule matematiche. Per esempiu, u pianificatore in FreeBSD usa una formula per
calculà a priorità di u travagliu attuale basatu nantu à quantu u prucessu
usatu u CPU. Inoltre, l'usu di CPU rots in u tempu, è cusì
Cusì, l'aumentu di priorità hè un pocu sfarente di ciò chì hè descrittu sopra. Questu hè veru
chjamati algoritmi di decadenza. Da a versione 7.1, FreeBSD usa u pianificatore ULE.
Infine, parechji pianificatori anu altre caratteristiche. Per esempiu, certi
i pianificatori riservanu livelli più alti per u funziunamentu di u sistema operatore è cusì
Cusì, nisun prucessu d'utilizatore pò uttene a più alta priorità
sistema. Certi sistemi permettenu di dà cunsiglii per aiutà
u pianificatore per dà priorità currettamente. Per esempiu, usendu u cumandamentu piacevule
pudete aumentà o diminuite a priorità di un compitu è cusì cresce o diminuite
riduce e probabilità di u prugramma per u tempu di CPU.
MLFQ: Riassuntu
Avemu descrittu un approcciu di pianificazione chjamatu MLFQ. U so nome
cunclusu in u principiu di funziunamentu - hà parechje fila è usa feedback
per dà priorità à un compitu.
A forma finale di e regule serà a seguente:
- Regula 1: Se priorità (A) > Priorità (B), l'attività A serà eseguita (B ùn serà micca)
- Regula 2: Se priorità (A) = Priorità (B), A & B sò cuminciati cù RR
- Regula 3: Quandu un compitu entra in u sistema, hè piazzatu in a fila di priorità più alta.
- Regula 4: Dopu chì un compitu hà utilizatu u so tempu assignatu in a fila attuale (indipendente da quante volte hà liberatu u CPU), a priorità di una tale attività hè ridutta (si move in a fila).
- Regula 5: Dopu qualchì periodu S, trasfiriri tutti i travaglii in u sistema à a fila più alta.
MLFQ hè interessante per i seguenti mutivi - invece di dumandà a cunniscenza
natura di u compitu in anticipu, l'algoritmu ampara u cumpurtamentu passatu di u compitu è mette
priorità in cunseguenza. Cusì, prova à pusà nantu à duie sedie à una volta - per ottene u rendiment per i picculi compiti (SJF, STCF) è onestamente curriri longu,
I travagli di carica di CPU. Dunque, parechji sistemi, cumpresi BSD è i so derivati,
Solaris, Windows, Mac utilizanu una forma di algoritmu cum'è pianificatore
MLFQ cum'è una basa.
Materiali supplementari:
- (informatica)
Source: www.habr.com