Introduzione ai sistemi operativi

Ciao, Habr! Vorrei presentarvi una serie di articoli di traduzione su una letteratura che trovo interessante — OSTEP. In questo materiale vengono esaminati in profondità i funzionamenti dei sistemi operativi Unix-like, in particolare — il lavoro con i processi, diversi scheduler, memoria e altri componenti simili che costituiscono un moderno sistema operativo. Potete vedere l'originale di tutti i materiali qui qui. Si prega di considerare che la traduzione è stata eseguita non professionalmente (abbastanza liberamente), ma spero di aver mantenuto il significato generale.

I lavori di laboratorio su questo argomento possono essere trovati qui:

Altre parti:

E potete anche dare un'occhiata al mio canale su telegram =)

Pianificazione: Coda di Feedback Multi-Livello

In questa lezione parleremo dei problemi nello sviluppo di uno dei più noti approcci alla
pianificazione, chiamato Coda di Feedback Multi-Livello (MLFQ). Per la prima volta, lo scheduler MLFQ è stato descritto nel 1962 da Fernando J. Corbató nel sistema chiamato
Compatible Time-Sharing System (CTSS). Questi lavori (inclusi i successivi lavori su
Multics) sono stati successivamente candidati al premio Turing. Lo scheduler è stato
successivamente migliorato e ha acquisito una forma che può essere trovata già in
alcuni sistemi moderni.

L'algoritmo MLFQ cerca di risolvere 2 problemi fondamentali intersecanti.
Primo, cerca di ottimizzare il tempo di turnaround, che come abbiamo visto nella lezione precedente, è ottimizzato con il metodo di far partire in cima alla coda le
compiti più brevi. Tuttavia, il sistema operativo non sa quanto tempo impiegherà un determinato processo, e questa è
una conoscenza necessaria per gli algoritmi SJF, STCF. In secondo luogo, MLFQ cerca di
rendere il sistema reattivo per gli utenti (ad esempio per coloro che stanno seduti e
fissano lo schermo in attesa del completamento del compito) e in questo modo minimizzare il tempo
di risposta. Sfortunatamente, algoritmi come RR riducono il tempo di risposta, ma hanno un effetto estremamente
negativo sulla metrica del tempo di turnaround. Da qui il nostro problema: Come progettare
uno scheduler che soddisfi le nostre esigenze senza sapere nulla sulla
natura del processo, in generale? Come potrà uno scheduler apprendere le caratteristiche dei compiti,
che esegue e quindi prendere decisioni migliori sulla pianificazione?

Il nodo del problema: Come pianificare l'assegnazione dei compiti senza conoscenza ideale?
Come sviluppare uno scheduler che minimizzi simultaneamente il tempo di risposta
per i compiti interattivi e riduca anche il tempo di turnaround senza una conoscenza predefinita
del tempo di esecuzione del compito?

Nota: apprendiamo dagli eventi precedenti

La coda MLFQ è un ottimo esempio di un sistema che apprende dagli
eventi passati per prevedere il futuro. Approcci simili si trovano spesso nei sistemi operativi (e in molti altri settori dell'informatica, comprese le branche
delle previsioni nell'hardware e gli algoritmi di caching). Approcci simili
previsioni nell'hardware e algoritmi di caching). Escursioni simili
scattano quando i compiti hanno fasi comportamentali e sono quindi prevedibili.
Tuttavia, con questa tecnica bisogna fare attenzione, perché le previsioni possono
rivelarsi molto facilmente errate e portare il sistema a prendere decisioni peggiori di
quelle che sarebbero senza alcuna conoscenza.

MLFQ: Regole di Base

Esaminiamo le regole di base dell'algoritmo MLFQ. Anche se esistono diverse
implementazioni di questo algoritmo, gli approcci fondamentali sono simili.
Nell'implementazione che stiamo considerando, in MLFQ ci saranno diverse
code separate, ognuna delle quali avrà una priorità diversa. In qualsiasi momento,
il compito pronto per l'esecuzione si trova in una coda. MLFQ utilizza le priorità
per decidere quale compito eseguire, ovvero il compito con una priorità più alta
(compito dalla coda con la priorità più alta) verrà eseguito per primo.
Senza dubbio, in una specifica coda possono esserci più di un compito, e in tal
modo avranno la stessa priorità. In questo caso, verrà utilizzato il meccanismo
RR per pianificare l'esecuzione tra questi compiti.
Pertanto, arriviamo a due regole fondamentali per MLFQ:
Regola 1: Se priorità(A) > Priorità(B), verrà eseguito il compito A (B non verrà)

Regola 2: Se priorità(A) = Priorità(B), A e B vengono eseguiti utilizzando RR
Secondo quanto esposto, gli elementi chiave per la pianificazione MLFQ

sono le priorità. Invece di assegnare una priorità fissa a ciascun
compito, MLFQ modifica la sua priorità in base al comportamento osservato.
Ad esempio, se un compito continua a interrompere il lavoro sulla CPU in attesa di input dalla tastiera,
MLFQ manterrà alta la priorità del processo, poiché è così che dovrebbe
funzionare un processo interattivo. Se invece un compito utilizza costantemente e
intensamente la CPU per un lungo periodo, MLFQ ne abbasserà la
priorità. In questo modo, MLFQ studierà il comportamento dei processi mentre lavorano
e utilizzerà i comportamenti.
Facciamo un esempio di come potrebbero apparire le code in un certo momento
e allora avremmo qualcosa del genere:
In questo schema ci sono 2 processi A e B nella coda con la priorità più alta. Il processo

C è da qualche parte nel mezzo, mentre il processo D è alla fine della coda. Secondo quanto detto sopra
Con un po' a metà, mentre il processo D è alla fine della coda. Secondo quanto sopra
Il descrizione dell'algoritmo MLFQ farà eseguire le attività solo con la massima
priorità secondo il RR, mentre le attività C e D non saranno considerate.
È ovvio che uno snapshot statico non fornisce un quadro completo di come funziona MLFQ.
È importante capire come la situazione cambia nel tempo.

Tentativo 1: Come cambiare la priorità

In questo momento è necessario decidere come MLFQ cambierà il livello di priorità
delle attività (e quindi la posizione dell'attività nella coda) nel corso del suo ciclo di vita. Per
questo è necessario tenere a mente il flusso di lavoro: un certo numero di
attività interattive con tempi di esecuzione brevi (e quindi frequenti liberazioni
del CPU) e alcune attività lunghe, che utilizzano il CPU per tutto il loro tempo di lavoro, in questo
momento il tempo di risposta per tali attività non è importante. E così si può fare il primo tentativo
di implementare l'algoritmo MLFQ con le seguenti regole:

Regola 3: Quando un'attività entra nel sistema, viene inserita nella coda con la massima
priorità.
priorità.
Regola 4a: Se un'attività utilizza interamente la finestra temporale a essa assegnata, la sua
priorità viene abbassata.
Regola 4b: Se un'attività libera il CPU prima della scadenza della sua finestra temporale, allora

rimane con la stessa priorità.

Esempio 1: Un'unica attività a lungo termine
Come si può vedere in questo esempio, l'attività al momento dell'ingresso viene assegnata con la massima
priorità. Dopo una finestra temporale di 10 ms, il processo viene abbassato nella priorità
dal pianificatore. Dopo la successiva finestra temporale, l'attività viene finalmente abbassata a

la priorità più bassa nel sistema, dove rimane.

Esempio 2: Arrivo di un'attività breve
Ora guardiamo un esempio di come MLFQ cercherà di avvicinarsi a SJF. In questo
esempio ci sono due attività: A, che è un'attività a lungo termine che occupa costantemente
il CPU e B, che è un'attività interattiva breve. Supponiamo che

A avesse già lavorato per un certo periodo di tempo al momento in cui è arrivata l'attività B.
Nel grafico sono visibili i risultati dello scenario. L'attività A, come qualsiasi attività,
utilizzando il CPU è finita in fondo. L'attività B arriverà al tempo T=100 e verrà
inserita nella coda con la massima priorità. Poiché il suo tempo di lavoro è breve, quindi

terminerà prima di raggiungere l'ultima coda.
sa che un compito è lungo o breve, prima di tutto presume che il compito
sia breve e gli assegna la massima priorità. Se si tratta davvero di un compito breve, allora
verrà completato rapidamente, altrimenti, se è un compito lungo, si muoverà lentamente
nel gradino di priorità e presto dimostrerà che è davvero un compito lungo che non
richiede una risposta.

Esempio 3: E riguardo all'input/output?

Ora diamo un'occhiata a un esempio con input/output. Come affermato nella regola 4b,
se un processo libera la CPU, senza utilizzare completamente il suo tempo di CPU,
allora rimane al livello di priorità precedente. Le intenzioni di questa regola sono piuttosto semplici
— se un'attività interattiva esegue molte operazioni di input/output, per esempio, aspettando
le pressioni dei tasti o del mouse da parte dell'utente, tale attività libererà la CPU
prima della finestra di tempo allocata. Non vorremmo abbassare la priorità di tale attività,
pertanto rimarrà al livello precedente.

Questo esempio mostra come funzionerà l'algoritmo con tali processi: l'attività interattiva B, che ha bisogno della CPU solo per 1 ms prima di eseguire
il processo di input/output e l'attività lunga A, che utilizza tutta la sua volta la CPU.
MLFQ mantiene il processo B con la massima priorità, poiché continua sempre a
liberare la CPU. Se B è un'attività interattiva, allora l'algoritmo ha così raggiunto
il suo obiettivo di eseguire rapidamente le attività interattive.

Problemi con l'attuale algoritmo MLFQ

Negli esempi precedenti abbiamo costruito una versione base di MLFQ. E sembra che
faccia il suo lavoro bene e in modo equo, distribuendo il tempo di CPU in modo giusto tra
compiti lunghi e consentendo ai compiti brevi o ad alta intensità di input/output di essere eseguiti rapidamente. Sfortunatamente, questo approccio presenta diversi
problemi gravi.
, il problema della fame: se nel sistema ci sono molte attività interattive,
Primoesse consumeranno tutto il tempo di CPU e quindi nessun compito lungo
avrà la possibilità di essere eseguito (essi stanno sofferendo la fame).
, utenti esperti potrebbero scrivere i loro programmi in modo da

In secondo luogoingannare lo scheduler. L'inganno consiste nel fare qualcosa che costringa
lo scheduler a fornire più tempo di CPU al processo. L'algoritmo che
il pianificatore può assegnare più tempo di CPU al processo. L'algoritmo che
descritto sopra è abbastanza vulnerabile a tali attacchi: prima che la finestra di tempo scada praticamente
è necessario eseguire un'operazione di input-output (a un file, non importa quale)
e in questo modo liberare la CPU. Tale comportamento consentirà di rimanere nella stessa
coda e di ottenere nuovamente una maggiore percentuale di tempo della CPU. Se fatto
correttamente (ad esempio, eseguendosi per il 99% del tempo della finestra prima di liberare la CPU),
tale attività potrebbe semplicemente monopolizzare il processore.

Infine, il programma può cambiare il suo comportamento nel tempo. Le attività che
utilizzavano la CPU possono diventare interattive. Nel nostro esempio, tali
attività non riceveranno il giusto trattamento dallo scheduler, poiché riceverebbero altre
(iniziali) attività interattive.

Domanda al pubblico: quali attacchi allo scheduler si potrebbero effettuare nel mondo moderno?

Tentativo 2: Aumento della priorità

Proviamo a cambiare le regole e vediamo se riusciamo a evitare i problemi di
stenti. Cosa potremmo fare per garantire che le attività legate alla CPU ricevano il loro tempo (anche se non a lungo).
Come semplice soluzione al problema, si potrebbe proporre di aumentare periodicamente
la priorità di tutte queste attività nel sistema. Esistono molteplici modi
per ottenere questo, proviamo a realizzare come esempio qualcosa di semplice: trasferire
immediatamente tutte le attività alla massima priorità, da qui una nuova regola:
Rule5

: Dopo un certo periodo S, trasferire tutte le attività nel sistema nella massima coda.La nostra nuova regola risolve due problemi contemporaneamente. In primo luogo, i processi

non soffrono di stenti: le attività nella coda più alta condivideranno
il tempo della CPU secondo l'algoritmo RR e in questo modo tutti i processi riceveranno
tempo della CPU. In secondo luogo, se qualche processo, che in precedenza utilizzava
solo la CPU, diventa interattivo, rimarrà in coda con priorità più alta dopo aver una volta ricevuto un aumento della priorità al massimo.
Consideriamo un esempio. In questo scenario consideriamo un processo che utilizza
ha la priorità dopo aver ricevuto un aumento di priorità fino al massimo.
Consideriamo un esempio. In questo scenario, consideriamo un processo che utilizza

CPU e due processi interattivi e brevi. A sinistra, l'immagine mostra il comportamento senza l'innalzamento della priorità, e così un compito lungo inizia a soffrire di fame dopo l'arrivo nel sistema di due compiti interattivi. Nell'immagine a destra, ogni 50 ms avviene un innalzamento della priorità e in questo modo tutti i processi ricevono garantito del tempo di CPU e verranno eseguiti periodicamente. 50 ms è preso qui come esempio, in realtà questo numero è leggermente superiore.
È evidente che l'aggiunta del tempo di innalzamento periodico S porta a
una domanda legittima: quale valore dovrebbe essere impostato? Uno dei noti
ingegneri di sistema John Ousterhout chiamava tali grandezze nei sistemi voo-doo
costante, poiché richiedevano in un certo senso magia nera per una corretta
impostazione. E, sfortunatamente, S ha quel 'profumo'. Se si imposta un valore troppo
alto, i compiti lunghi iniziano a soffrire di fame. E se si imposta un valore troppo basso,
i compiti interattivi non riceveranno il giusto tempo di CPU.

Tentativo 3: Migliore gestione del tempo

Ora abbiamo un'altra questione da risolvere: come evitare di
ingannare il nostro pianificatore? I colpevoli di questa possibilità sono
le regole 4a, 4b, che consentono a un compito di mantenere la priorità liberando la CPU
fino alla scadenza del tempo assegnato. Come gestire questa situazione?
La soluzione in questo caso può essere considerata una migliore registrazione del tempo CPU a ogni
livello MLFQ. Invece di dimenticare il tempo che il programma ha utilizzato
la CPU nell'intervallo assegnato, dovremmo tenerne traccia e conservarlo. Dopo che
il processo ha esaurito il tempo assegnato, dovrebbe essere ridotto al successivo
livello di priorità. Ora non importa come il processo utilizzerà il suo tempo — come
un calcolo costante sulla CPU o come molteplici chiamate. In questo modo,
dovremmo riscrivere la regola 4 nella seguente forma:

Regola4: Dopo che un compito ha esaurito il tempo a lui assegnato nella coda attuale (indipendentemente da quante volte ha liberato la CPU), la priorità di tale compito viene abbassata (si sposta verso il basso nella coda).

Diamo un'occhiata a un esempio:
»

Nell'immagine si mostra cosa succede se si prova a ingannare il pianificatore, come
se ci fossero state le precedenti regole 4a, 4b, il risultato sarebbe a sinistra. Con la nuova
regola — il risultato è a destra. Prima della protezione, qualsiasi processo poteva generare I/O fino al completamento e
così dominare la CPU, dopo l'attivazione della protezione, indipendentemente dal comportamento
I/O, esso finirà comunque per scendere in coda e pertanto non potrà appropriarsi in modo sleale
delle risorse della CPU.

Miglioriamo MLFQ e altri problemi

Con i miglioramenti di cui sopra sorgono nuovi problemi: una delle principali
domande è come parametrizzare un pianificatore simile? Cioè, Quante dovrebbero essere
le code? Qual è la dimensione della finestra di lavoro di un programma all'interno della coda? Quanto
spesso dovrebbe essere aumentata la priorità del programma per evitare la starvation e
tenere conto del cambiamento del comportamento del programma? A queste domande, non c'è una risposta semplice
e solo esperimenti con carichi e la successiva configurazione
del pianificatore possono portare a un certo equilibrio soddisfacente.

Ad esempio, la maggior parte delle implementazioni MLFQ permette di assegnare intervalli di tempo diversi a
code diverse. Le code ad alta priorità di solito
ricevono intervalli brevi. Queste code sono composte da attività interattive,
il passaggio tra le quali è piuttosto sensibile e dovrebbe richiedere 10 ms o meno.
Al contrario, le code a bassa priorità sono composte da attività lunghe che utilizzano
la CPU. E in questo caso, intervalli di tempo lunghi funzionano molto bene (100 ms).

In questo esempio ci sono 2 attività, che hanno lavorato nella coda ad alta priorità per 20
ms, suddivisi in finestre di 10 ms. 40 ms nella coda media (finestra di 20 ms) e nella coda a bassa priorità
la finestra temporale è diventata 40 ms, dove le attività hanno completato il loro lavoro.

L'implementazione di MLFQ nel sistema operativo Solaris è una classe di pianificatori che dividono per tempo.
Il pianificatore fornisce un insieme di tabelle, che definiscono esattamente come dovrebbe
cambiare la priorità di un processo nel corso della sua vita, quale dovrebbe essere la dimensione
della finestra assegnata e quanto spesso devono essere elevate le priorità delle attività. L'amministratore
di sistema può interagire con questa tabella e costringere il pianificatore a comportarsi
in modo diverso. Per impostazione predefinita, in questa tabella ci sono 60 code con un aumento graduale
della dimensione della finestra da 20 ms (alta priorità) a diverse centinaia di ms (bassa priorità), e
anche con un boost di tutte le attività ogni secondo.

Altri pianificatori MLFQ non utilizzano tabelle o regole specifiche
come quelle descritte in questa lezione, ma calcolano le priorità utilizzando
formule matematiche. Ad esempio, il pianificatore in FreeBSD utilizza una formula per
calcolare la priorità attuale di un'attività, basandosi su quanto processo
ha utilizzato la CPU. Inoltre, l'uso della CPU nel tempo diminuisce, e in questo
modo l'aumento della priorità avviene in un modo leggermente diverso da quanto descritto sopra. Questi sono i
cosiddetti algoritmi di decadimento. Dalla versione 7.1 FreeBSD utilizza il pianificatore ULE.

Infine, molti pianificatori hanno altre caratteristiche. Ad esempio, alcuni
pianificatori riservano i livelli superiori per il funzionamento del sistema operativo e così
nessun processo utente potrà ottenere la massima priorità nel
sistema. Alcuni sistemi consentono di dare suggerimenti per aiutare
il pianificatore a impostare correttamente le priorità. Ad esempio, tramite il comando nice
è possibile aumentare o diminuire la priorità di un'attività e in questo modo aumentare o
ridurre le possibilità del programma di ottenere tempo CPU.

MLFQ: Riepilogo

Abbiamo descritto un approccio alla pianificazione chiamato MLFQ. Il suo nome
si basa sul suo principio di funzionamento: ha più code e utilizza il feedback
per determinare la priorità di un'attività.
La forma finale delle regole sarà la seguente:

Regola1: Se priorità(A) > Priorità(B), verrà avviata l'attività A (B non sarà avviata)
Regola2: Se priorità(A) = Priorità(B), A e B vengono avviati utilizando RR
Regola3: Quando un'attività entra nel sistema, viene collocata nella coda con la massima priorità.
Regola4: Dopo che un compito ha esaurito il tempo a lui assegnato nella coda attuale (indipendentemente da quante volte ha liberato la CPU), la priorità di tale compito viene abbassata (si sposta verso il basso nella coda).
: Dopo un certo periodo S, trasferire tutte le attività nel sistema nella massima coda.La nostra nuova regola risolve due problemi contemporaneamente. In primo luogo, i processi

MLFQ è interessante per il seguente motivo: invece di richiedere una conoscenza
della natura dell'attività in anticipo, l'algoritmo studia il comportamento passato dell'attività e assegna
le priorità di conseguenza. In questo modo cerca di bilanciare simultaneamente le due esigenze: raggiungere prestazioni elevate per le piccole attività (SJF, STCF) e lanciare onestamente compiti lunghi e
intensivi per la CPU. Pertanto molti sistemi, inclusi BSD e i loro derivati,
Solaris, Windows, Mac utilizzano come pianificatore una qualche forma dell'algoritmo
MLFQ come base fondamentale.