Introduzione ai sistemi operativi

Ehi Habr! Vorrei portare alla vostra attenzione una serie di articoli-traduzioni di una letteratura interessante secondo me - OSTEP. Questo materiale discute in modo abbastanza approfondito il lavoro dei sistemi operativi simili a Unix, vale a dire lavorare con processi, vari programmatori, memoria e altri componenti simili che compongono un sistema operativo moderno. Puoi vedere l'originale di tutti i materiali qui qui. Si prega di notare che la traduzione è stata fatta in modo non professionale (abbastanza liberamente), ma spero di aver mantenuto il significato generale.

Il lavoro di laboratorio su questo argomento può essere trovato qui:

Altre parti:

Puoi anche dare un'occhiata al mio canale su telegramma =)

Introduzione allo schedulatore

L'essenza del problema: come sviluppare una politica di pianificazione
Come dovrebbero essere progettate le strutture sottostanti delle politiche di pianificazione? Quali dovrebbero essere le ipotesi chiave? Quali parametri sono importanti? Quali tecniche di base venivano utilizzate nei primi sistemi informatici?

Presupposti del carico di lavoro

Prima di discutere le possibili politiche, facciamo alcune digressioni semplificatrici sui processi in esecuzione nel sistema, che sono collettivamente chiamati carico di lavoro. La definizione del carico di lavoro è una parte fondamentale della creazione di policy e quanto più si conosce il carico di lavoro, migliore sarà la policy che si potrà scrivere.

Facciamo le seguenti ipotesi sui processi in esecuzione nel sistema, a volte chiamati anche posti di lavoro (compiti). Quasi tutte queste ipotesi non sono realistiche, ma sono necessarie per lo sviluppo del pensiero.

Ogni attività viene eseguita per lo stesso periodo di tempo,
Tutte le attività vengono impostate contemporaneamente,
L'attività assegnata funziona fino al suo completamento,
Tutte le attività utilizzano solo la CPU,
Il tempo di esecuzione di ciascuna attività è noto.

Metriche dello scheduler

Oltre ad alcune ipotesi sul carico, è necessario un altro strumento per confrontare diverse politiche di pianificazione: le metriche dello scheduler. Una metrica è solo una misura di qualcosa. Esistono numerosi parametri che possono essere utilizzati per confrontare gli scheduler.

Ad esempio, utilizzeremo una metrica chiamata tempo di consegna (tempo di consegna). Il tempo di consegna dell'attività è definito come la differenza tra il tempo di completamento dell'attività e l'orario di arrivo dell'attività nel sistema.

Tturnaround=Tcompletamento−arrivo

Poiché abbiamo ipotizzato che tutti i compiti arrivassero nello stesso momento, allora Ta=0 e quindi Tt=Tc. Questo valore cambierà naturalmente quando cambiamo le ipotesi di cui sopra.

Un'altra metrica - equità (correttezza, onestà). Produttività ed equità sono spesso caratteristiche opposte nella pianificazione. Ad esempio, lo scheduler può ottimizzare le prestazioni, ma al costo di attendere l'esecuzione di altre attività, riducendo così l'equità.

PRIMO ENTRATO PRIMO USCITO (FIFO)

L'algoritmo più elementare che possiamo implementare si chiama FIFO o primo arrivato (entra), primo servito (esce). Questo algoritmo presenta diversi vantaggi: è molto semplice da implementare, si adatta a tutte le nostre ipotesi e svolge il lavoro abbastanza bene.

Diamo un'occhiata a un semplice esempio. Diciamo che sono state impostate 3 attività contemporaneamente. Ma supponiamo che l'attività A sia arrivata un po' prima di tutte le altre, quindi apparirà nell'elenco di esecuzione prima delle altre, proprio come B rispetto a C. Assumiamo che ciascuna di esse verrà eseguita per 10 secondi. Quale sarà il tempo medio per completare queste attività in questo caso?

Contando i valori - 10+20+30 e dividendo per 3, otteniamo il tempo medio di esecuzione del programma pari a 20 secondi.
Ora proviamo a cambiare le nostre ipotesi. In particolare, presupposto 1 e quindi non daremo più per scontato che ogni attività richieda la stessa quantità di tempo per essere eseguita. Come si comporterà la FIFO questa volta?

A quanto pare, tempi diversi di esecuzione delle attività hanno un impatto estremamente negativo sulla produttività dell’algoritmo FIFO. Supponiamo che l'attività A impiegherà 100 secondi per essere completata, mentre B e C impiegheranno comunque 10 secondi ciascuna.

Come si vede dalla figura il tempo medio del sistema sarà (100+110+120)/3=110. Questo effetto si chiama effetto convoglio, quando alcuni consumatori a breve termine di una risorsa si mettono in coda dietro a un consumatore pesante. È come la fila al supermercato quando davanti a te c'è un cliente con il carrello pieno. La soluzione migliore al problema è provare a cambiare registratore di cassa oppure rilassarsi e respirare profondamente.

Prima il lavoro più breve

È possibile in qualche modo risolvere una situazione simile con processi pesanti? Certamente. Un altro tipo di pianificazione è chiamatoPrima il lavoro più breve (SJF). Anche il suo algoritmo è piuttosto primitivo: come suggerisce il nome, le attività più brevi verranno avviate per prime, una dopo l'altra.

In questo esempio, il risultato dell'esecuzione degli stessi processi sarà un miglioramento del tempo medio di consegna del programma e sarà pari a 50 invece di 110, che è quasi 2 volte migliore.

Pertanto, partendo dal presupposto che tutte le attività arrivino nello stesso momento, l'algoritmo SJF sembra essere l'algoritmo più ottimale. Tuttavia, le nostre ipotesi non sembrano ancora realistiche. Questa volta cambiamo l'ipotesi 2 e questa volta immaginiamo che i compiti possano essere presenti in qualsiasi momento e non tutti contemporaneamente. A quali problemi può portare questo?

Immaginiamo che il compito A (100c) arrivi per primo e inizi ad essere eseguito. A t=10 arrivano le attività B e C, ciascuna delle quali richiederà 10 secondi. Quindi il tempo di esecuzione medio è (100+(110-10)+(120-10))3 = 103. Cosa potrebbe fare lo scheduler per migliorarlo?

Prima il tempo di completamento più breve (STCF)

Per migliorare la situazione, omettiamo l'ipotesi 3 secondo cui il programma viene avviato e prosegue fino al completamento. Inoltre, avremo bisogno del supporto hardware e, come puoi immaginare, lo utilizzeremo timer per interrompere un'attività in esecuzione e cambio di contesto. Pertanto, lo scheduler può fare qualcosa nel momento in cui arrivano i compiti B, C: interrompere l'esecuzione del compito A e mettere in elaborazione i compiti B e C e, dopo il loro completamento, continuare l'esecuzione del processo A. Tale pianificatore è chiamato STCFo Prima il lavoro preventivo.

Il risultato di questo pianificatore sarà il seguente risultato: ((120-0)+(20-10)+(30-10))/3=50. Pertanto, un tale pianificatore diventa ancora più ottimale per i nostri compiti.

Tempo di risposta metrico

Pertanto, se conosciamo il tempo di esecuzione delle attività e che queste utilizzano solo la CPU, STCF sarà la soluzione migliore. E una volta, nei primi tempi, questi algoritmi funzionavano abbastanza bene. Tuttavia, l'utente ora trascorre la maggior parte del tempo al terminale e si aspetta un'esperienza interattiva produttiva. Così è nata una nuova metrica: tempo di risposta (risposta).

Il tempo di risposta viene calcolato come segue:

Tresponse=Tfirstrun−Tarrival

Pertanto, per l'esempio precedente, il tempo di risposta sarà: A=0, B=0, C=10 (abg=3,33).

E si scopre che l'algoritmo STCF non è così buono in una situazione in cui arrivano 3 attività contemporaneamente: dovrà attendere fino al completamento delle piccole attività. Quindi l'algoritmo è positivo per la metrica del tempo di consegna, ma negativo per la metrica dell'interattività. Immagina di essere seduto a un terminale e provare a digitare caratteri in un editor e di dover attendere più di 10 secondi perché qualche altra attività occupa la CPU. Non è molto piacevole.

Quindi ci troviamo di fronte a un altro problema: come possiamo costruire uno scheduler sensibile al tempo di risposta?

Round Robin

È stato sviluppato un algoritmo per risolvere questo problema Round Robin (RR). L'idea di base è abbastanza semplice: invece di eseguire attività fino al loro completamento, eseguiremo l'attività per un certo periodo di tempo (chiamato intervallo di tempo) e poi passeremo a un'altra attività dalla coda. L'algoritmo ripete il suo lavoro fino al completamento di tutte le attività. In questo caso il tempo di esecuzione del programma deve essere un multiplo del tempo trascorso il quale il timer interromperà il processo. Ad esempio, se un timer interrompe un processo ogni x=10 ms, la dimensione della finestra di esecuzione del processo dovrebbe essere un multiplo di 10 ed essere 10,20 o x*10.

Consideriamo un esempio: le attività ABC arrivano simultaneamente nel sistema e ciascuna di esse deve essere eseguita per 5 secondi. L'algoritmo SJF completerà ogni attività prima di iniziarne un'altra. Al contrario, l’algoritmo RR con una finestra di lancio = 1s svolgerà i compiti come segue (Fig. 4.3):

(SJF Again (Cattivo per il tempo di risposta)

(Round Robin (buono per il tempo di risposta)

Il tempo di risposta medio per l'algoritmo RR è (0+1+2)/3=1, mentre per l'SJF (0+5+10)/3=5.

È logico supporre che la finestra temporale sia un parametro molto importante per RR; quanto più piccola è, tanto maggiore è il tempo di risposta. Tuttavia, non dovresti renderlo troppo piccolo, poiché anche il tempo di cambio del contesto avrà un ruolo nelle prestazioni complessive. Pertanto, la scelta del tempo della finestra di esecuzione viene impostata dall'architetto del sistema operativo e dipende dalle attività che si prevede di eseguire in essa. Il cambio di contesto non è l'unica operazione di servizio che fa perdere tempo: il programma in esecuzione opera su molte altre cose, ad esempio varie cache, e con ogni cambio è necessario salvare e ripristinare questo ambiente, il che può anche richiedere molto tempo tempo.

RR è un ottimo pianificatore se parlassimo solo della metrica del tempo di risposta. Ma come si comporterà la metrica del tempo di consegna delle attività con questo algoritmo? Consideriamo l'esempio sopra, quando il tempo di funzionamento di A, B, C = 5 s e arrivano allo stesso tempo. L'attività A terminerà alle 13, B alle 14, C alle 15 e il tempo medio di consegna sarà di 14 secondi. Pertanto, RR è il peggiore algoritmo per la metrica del fatturato.

In termini più generali, qualsiasi algoritmo di tipo RR è equo; divide equamente il tempo della CPU tra tutti i processi. E quindi, queste metriche sono costantemente in conflitto tra loro.

Pertanto, abbiamo diversi algoritmi contrastanti e allo stesso tempo rimangono ancora diverse ipotesi: che il tempo dell'attività sia noto e che l'attività utilizzi solo la CPU.

Miscelazione con I/O

Innanzitutto eliminiamo l’assunto 4 secondo cui il processo utilizza solo la CPU; naturalmente non è così e i processi possono accedere ad altre apparecchiature.

Nel momento in cui un processo richiede un'operazione di I/O, il processo entra nello stato bloccato, in attesa del completamento dell'I/O. Se l'I/O viene inviato al disco rigido, tale operazione può richiedere diversi ms o più e il processore sarà inattivo in questo momento. Durante questo periodo, lo scheduler può occupare il processore con qualsiasi altro processo. La prossima decisione che lo scheduler dovrà prendere sarà quando il processo completerà il suo I/O. Quando ciò accade, si verificherà un'interruzione e il sistema operativo metterà il processo che ha chiamato l'I/O nello stato pronto.

Diamo un'occhiata ad un esempio di diverse attività. Ognuno di essi richiede 50 ms di tempo CPU. Tuttavia, il primo accederà all'I/O ogni 10 ms (che verrà eseguito anch'esso ogni 10 ms). E il processo B utilizza semplicemente un processore da 50 ms senza I/O.

In questo esempio utilizzeremo lo scheduler STCF. Come si comporterà lo scheduler se su di esso viene lanciato un processo come A? Farà quanto segue: prima elaborerà completamente il processo A, quindi il processo B.

L'approccio tradizionale per risolvere questo problema consiste nel trattare ogni sottoattività da 10 ms del processo A come un'attività separata. Pertanto, quando si inizia con l'algoritmo STJF, la scelta tra un compito da 50 ms e uno da 10 ms è ovvia. Quindi, una volta completata la sottoattività A, verranno avviati il processo B e l'I/O. Una volta completato l'I/O, sarà consuetudine riavviare il processo A da 10 ms anziché il processo B. In questo modo, è possibile implementare la sovrapposizione, in cui la CPU viene utilizzata da un altro processo mentre il primo è in attesa del I/O. Di conseguenza, il sistema viene utilizzato meglio: nel momento in cui i processi interattivi attendono I/O, altri processi possono essere eseguiti sul processore.

L'Oracolo non c'è più

Ora proviamo a sbarazzarci del presupposto che il tempo di esecuzione dell'attività sia noto. Questo è generalmente il presupposto peggiore e più irrealistico dell’intero elenco. In effetti, nel sistema operativo ordinario medio, il sistema operativo stesso di solito sa molto poco sul tempo di esecuzione delle attività, quindi come è possibile creare uno scheduler senza sapere quanto tempo richiederà l'esecuzione dell'attività? Forse potremmo usare alcuni principi RR per risolvere questo problema?

risultato

Abbiamo esaminato le idee di base della pianificazione delle attività e abbiamo esaminato 2 famiglie di pianificatori. Il primo avvia per primo l'attività più breve e quindi aumenta il tempo di consegna, mentre il secondo viene diviso tra tutte le attività equamente, aumentando il tempo di risposta. Entrambi gli algoritmi sono cattivi mentre gli algoritmi dell'altra famiglia sono buoni. Abbiamo anche esaminato come l'uso parallelo di CPU e I/O possa migliorare le prestazioni, ma non abbiamo risolto il problema con la chiaroveggenza del sistema operativo. E nella prossima lezione vedremo un pianificatore che guarda al passato immediato e cerca di predire il futuro. E si chiama coda di feedback multilivello.

Fonte: habr.com

Sistemi operativi: tre pezzi facili. Parte 4: Introduzione allo scheduler (traduzione)