Introduzione ai sistemi operativi

Ciao, Habr! Vorrei presentarvi una serie di articoli tradotti su una libreria che trovo interessante: OSTEP. In questo materiale si analizza in profondità il funzionamento dei sistemi operativi simili a Unix, in particolare la gestione dei processi, vari pianificatori, la memoria e altri componenti simili che costituiscono un moderno sistema operativo. Potete visualizzare l'originale di tutti i materiali qui qui. Si prega di notare che la traduzione non è stata eseguita da un professionista (è abbastanza libera), ma spero di aver mantenuto il significato generale.

Le esercitazioni su questo argomento possono essere trovate qui:

Altre parti:

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

Pianificazione: Coda di Feedback Multi-Livello

In questa lezione discuteremo delle problematiche nello sviluppo di uno degli approcci più noti per
la pianificazione, noto come Coda di Feedback Multi-Livello (MLFQ). Il pianificatore MLFQ è stato descritto per la prima volta nel 1962 da Fernando J. Corbató nel sistema chiamato
Compatible Time-Sharing System (CTSS). Questi lavori (inclusi i successivi contributi su
Multics) sono stati successivamente candidati per il premio Turing. Il pianificatore è stato
poi perfezionato e ha assunto una forma che si può vedere già in
alcuni sistemi moderni.

L'algoritmo MLFQ cerca di risolvere 2 problemi fondamentali che si sovrappongono.
In primo luogo, cerca di ottimizzare il tempo di turnaround, che come abbiamo esaminato nella lezione precedente, è ottimizzato avviando in cima alla coda le
attività più brevi. Tuttavia, il sistema operativo non sa quanto tempo impiegherà un processo, e questa
è una conoscenza necessaria per il funzionamento degli 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 dell'attività) e in tal modo minimizzare il tempo
risposta. Sfortunatamente, algoritmi come RR riducono il tempo di risposta, ma hanno un impatto molto negativo sulla metrica del tempo di turnaround. Da qui il nostro problema: Come progettare
un pianificatore che soddisfi le nostre esigenze e allo stesso tempo non sappia nulla della
natura del processo, in generale? Come può un pianificatore studiare le caratteristiche delle attività che
lancia e quindi prendere decisioni migliori sulla pianificazione?
Il nocciolo della questione: Come pianificare l'assegnazione dei compiti senza una conoscenza perfetta?

Come sviluppare un pianificatore che minimizzi simultaneamente il tempo di risposta
per compiti interattivi e riduca al contempo il tempo di turnaround senza una conoscenza predefinita
del tempo di esecuzione del compito?
Nota: impariamo dagli eventi passati.

La coda MLFQ è un ottimo esempio di un sistema che impara dai

fatti trascorsi per prevedere il futuro. Approcci simili si trovano spesso nei sistemi operativi
(e in molti altri settori dell'informatica, comprese le ramificazioni
di previsione nell'hardware e gli algoritmi di caching). Tali metodi
funzionano quando le attività hanno fasi comportamentali e sono quindi prevedibili.
si attivano quando i compiti hanno fasi comportamentali rendendoli così prevedibili.
Tuttavia, con questa tecnica è importante essere cauti, poiché le previsioni possono facilmente
risultare errate e portare il sistema a prendere decisioni peggiori di quelle
che sarebbero state senza alcuna conoscenza.

MLFQ: Regole di base

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

Regola1: Se priorità(A) > Priorità(B), verrà avviato il compito A (B non verrà avviato)
Regola 2: Se priorità(A) = priorità(B), A e B vengono avviati utilizzando RR

Sulla base di quanto sopra, 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 della CPU in attesa di input da tastiera,
MLFQ manterrà la priorità del processo alta, poiché è questo che
deve fare un processo interattivo. D'altra parte, se un compito utilizza costantemente e
intensamente la CPU per un lungo periodo, MLFQ abbasserà la sua
priorità. In questo modo, MLFQ imparerà il comportamento dei processi mentre vengono eseguiti
e utilizzerà questi comportamenti.
Disegniamo un esempio di come potrebbero apparire le code in un certo momento
e quindi otterremo qualcosa del genere:

In questo schema, 2 processi A e B si trovano in coda con la massima priorità. Il processo
C è a metà strada, mentre il processo D si trova alla fine della coda. Secondo le descrizioni fornite
dell'algoritmo MLFQ, il pianificatore eseguirà solo i compiti con la massima priorità.
la priorità secondo RR, mentre i task C e D saranno trascurati.
Naturalmente, uno snapshot statico non fornisce un quadro completo di come funziona MLFQ.
È importante comprendere come cambia la situazione nel tempo.

Tentativo 1: Come modificare la priorità

In questo momento è necessario decidere come MLFQ cambierà il livello di priorità
dei task (e quindi la posizione del task nella coda) durante il loro ciclo di vita. Per
questo è necessario tenere a mente il flusso di lavoro: un certo numero di
task interattivi con brevi tempi di esecuzione (e quindi frequenti rilasci di
CPU) e alcuni task lunghi, che utilizzano la CPU per tutto il loro tempo di lavoro, dando
una scarsa importanza al tempo di risposta per tali task. E così si può fare il primo tentativo
di implementare l'algoritmo MLFQ con le seguenti regole:

Rule3: Quando un task entra nel sistema, viene collocato nella coda con la priorità più alta.
priorità.
Rule4a: Se un task utilizza completamente il tempo assegnato, allora la sua
priorità viene ridotta.
Rule4b: Se il task rilascia la CPU prima della scadenza del suo tempo assegnato, allora rimane
con la stessa priorità.

Esempio 1: Un singolo task a lungo termine

Come si può vedere in questo esempio, il compito viene assegnato con la massima priorità
. Dopo una finestra temporale di 10 ms, il processo viene retrocesso in priorità
dal pianificatore. Dopo la successiva finestra temporale, il compito viene infine retrocesso a
una priorità inferiore nel sistema, dove rimane.

Esempio 2: Un compito breve è stato presentato

Ora vediamo un esempio di come MLFQ cercherà di avvicinarsi a SJF. In questo
esempio ci sono due compiti: A, che è un compito a lunga durata che utilizza costantemente la CPU, e B, che è un compito interattivo breve. Supponiamo
che A abbia già lavorato per un certo periodo quando è arrivato il compito B.
Nel grafico sono visibili i risultati dello scenario. Il compito A, come qualsiasi compito

che utilizza la CPU, si trova in fondo. Il compito B arriverà a T=100 e sarà
posta nella coda con la priorità più alta. Poiché il suo tempo di esecuzione è breve,
terminerà prima di raggiungere l'ultima coda.
Da questo esempio si può comprendere l'obiettivo principale dell'algoritmo: poiché l'algoritmo non

sa se un compito è lungo o breve, assume innanzitutto che il compito
sa se un compito è lungo o corto, quindi in primo luogo si presume che il compito
breve e le dà la massima priorità. Se si tratta veramente di un compito breve,
si completerà rapidamente; altrimenti, se è un compito lungo, procederà lentamente
nella priorità verso il basso e dimostrerà presto di essere effettivamente un compito lungo che non
richiede una risposta.

Esempio 3: E per quanto riguarda l'input-output?

Ora diamo un'occhiata a un esempio di input-output. Come affermato nella regola 4b,
se un processo libera la CPU senza utilizzare completamente il suo tempo di CPU,
allora rimane al suo livello di priorità attuale. Le intenzioni di questa regola sono abbastanza semplici:
se un compito interattivo esegue molte operazioni di input-output, ad esempio, in attesa
di input da parte dell'utente, come tasti o mouse, tale compito libererà la CPU
prima della finestra prevista. Non vorremmo abbassare la priorità di tale compito,
e quindi rimarrà al suo livello attuale.

Questo esempio mostra come il algoritmo funzionerà con tali processi: il compito interattivo B, che necessita di CPU solo per 1 ms prima di eseguire
il processo di input-output e il compito lungo A, che utilizza tutta la sua CPU.
MLFQ gestisce i processi con la massima priorità, poiché continua a liberare CPU nel frattempo.
Se B è un compito interattivo, l'algoritmo in questo caso ha raggiunto
il suo obiettivo di avviare i compiti interattivi rapidamente.

Problemi con l'algoritmo MLFQ attuale

Negli esempi precedenti abbiamo costruito una variante base di MLFQ. Sembra che
stia svolgendo il suo lavoro bene e in modo equo, distribuendo il tempo di CPU equamente tra
compiti lunghi e consentendo ai compiti brevi o quelli ad alta intensità di I/O di completarsi rapidamente. Sfortunatamente, questo approccio presenta diversi
serî problemi.
, problema di starvation: se nel sistema ci sono molti compiti interattivi,
In primo luogoquesti consumeranno tutto il tempo di CPU e di conseguenza nessun compito lungo
avrà l'opportunità di essere eseguito (starverà).
, utenti astuti potrebbero scrivere i loro programmi in modo tale da

In secondo luogoingannare il piano di scheduling. L'inganno consiste nel fare qualcosa che costringa
il piano di scheduling a dare al processo più tempo di CPU. L'algoritmo che
lo scheduler assegna più tempo di CPU al processo. L'algoritmo che
come descritto sopra, è vulnerabile a questi attacchi: prima che la finestra di tempo sia praticamente
scaduta, è necessario eseguire un'operazione di input/output (su un file casuale, non importa quale)
e in questo modo liberare la CPU. Questo comportamento consentirà di rimanere nella stessa
coda e ottenere di nuovo una percentuale maggiore di tempo di CPU. Se fatto
correttamente (ad esempio, eseguendosi il 99% del tempo della finestra prima di liberare la CPU),
questo compito può semplicemente monopolizzare il processore.

Infine, un programma può modificare il proprio comportamento nel tempo. I compiti
che usavano la CPU possono diventare interattivi. Nel nostro esempio, tali
compiti non riceveranno il giusto trattamento dal pianificatore, come riceverebbero altri
(iniziali) compiti interattivi.

Domanda al pubblico: quali attacchi al pianificatore potrebbero essere effettuati nel mondo moderno?

Tentativo 2: Aumento della priorità

Proviamo a cambiare le regole e vediamo se riusciamo ad evitare i problemi di
starvation. Cosa possiamo fare per garantire che i compiti legati alla
CPU ricevano il loro tempo (anche se non per molto).
Come soluzione semplice al problema, si può proporre di aumentare periodicamente
la priorità di tutte queste attività nel sistema. Esistono numerosi modi
per raggiungere questo obiettivo; proviamo a realizzare come esempio qualcosa di semplice: tradurre
subito tutte le attività alla massima priorità, da qui la nuova regola:

Rule5: Dopo un certo periodo S, trasferire tutte le attività nel sistema alla massima coda.

La nostra nuova regola risolve immediatamente due problemi. In primo luogo, i processi
non soffrono mai di starvation: le attività nella coda prioritaria superiore condivideranno
il tempo della CPU secondo l'algoritmo RR e in questo modo tutti i processi riceveranno
tempo della CPU. In secondo luogo, se un processo, che in precedenza utilizzava
solo la CPU, diventa interattivo, rimarrà nella coda con priorità superiore dopo aver ricevuto
una volta l'upgrade della priorità alla massima.
Consideriamo un esempio. In questo scenario consideriamo un processo che utilizza

CPU e due processi interattivi, brevi. A sinistra, l'immagine mostra il comportamento senza elevazione di priorità, e così un compito lungo inizia a soffrire di fame dopo l'arrivo nel sistema di due compiti interattivi. A destra, ogni 50 ms viene eseguita un'elevazione di priorità, garantendo così che tutti i processi ricevano tempo di CPU e vengano eseguiti periodicamente. I 50 ms in questo caso sono stati scelti come esempio; in realtà, questo numero è leggermente più alto.
È evidente che l'aggiunta di un tempo di elevazione periodica S porta a
una questione inevitabile: quale valore dovrebbe essere impostato? Uno degli ingegneri di sistema più rispettati, John Ousterhout, definiva simili grandezze nei sistemi come voodoo
costante, poiché in un certo senso richiedevano una sorta di magia nera per essere impostate correttamente.
E, sfortunatamente, S ha quell'aria. Se si imposta un valore troppo
alto, i compiti lunghi inizieranno 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

Tentativo 3: Miglior conteggio

Adesso abbiamo un altro problema da risolvere: come evitare
che il nostro pianificatore venga ingannato? I colpevoli di questa possibilità sono
le regole 4a e 4b, che permettono a un compito di mantenere la priorità, liberando il processore
fino alla scadenza del tempo assegnato. Come possiamo affrontare questo?
Una possibile soluzione è una migliore contabilizzazione del tempo CPU a ciascun
livello MLFQ. Invece di dimenticare il tempo che un programma ha utilizzato
il processore durante il proprio intervallo, si dovrebbe tenere conto e conservarlo. Dopo che
il processo ha consumato il suo tempo assegnato, il suo livello di priorità deve essere abbassato
al livello successivo. Ora non importa come il processo utilizzerà il suo tempo: sia
come un calcolo continuo sul processore o come molteplici chiamate. In questo modo,
dobbiamo riscrivere la regola 4 nella forma seguente:

Rule4: Dopo che un compito ha consumato il tempo a disposizione nella coda attuale (indipendentemente da quante volte ha liberato la CPU), la priorità di quel compito viene abbassata (si muove verso il basso nella coda).

Vediamo un esempio:
»

La figura mostra cosa succede se si cerca di ingannare lo scheduler, come
se avessimo usato le precedenti regole 4a, 4b si otterrebbe il risultato a sinistra. Con la nuova
regola — il risultato è a destra. Prima della protezione, qualsiasi processo poteva causare I/O fino al termine e
pertanto dominare la CPU, dopo l'attivazione della protezione, indipendentemente dal comportamento
dell'I/O, verrà comunque messo in coda in basso e quindi non potrà appropriatamente
sottrarre risorse alla CPU.

Miglioriamo MLFQ e altri problemi

Con i miglioramenti sopra menzionati sorgono nuovi problemi: una delle principali
questioni è come parametrare uno scheduler simile? Cioè, quante dovrebbero essere
le code? Qual è la dimensione della finestra di lavoro del programma all'interno della coda? Quanto
spesso dovrebbe essere aumentato il prioritario del programma per evitare l'starvation e
considerare il cambiamento del comportamento del programma? Non c'è una risposta semplice a queste domande e solo esperimenti con carichi di lavoro e la successiva configurazione
dello scheduler possono portare a un certo equilibrio soddisfacente.
Ad esempio, la maggior parte delle implementazioni di MLFQ consentono di assegnare diversi

Ad esempio, la maggior parte delle implementazioni MLFQ consente di assegnare diversi
intervalli di tempo per varie code. Le code ad alta priorità di solito
ricevono intervalli brevi. Queste code consistono in compiti interattivi,
la cui commutazione è piuttosto sensibile e dovrebbe richiedere 10 millisecondi o meno.
In contrapposizione, le code a bassa priorità consistono in compiti lunghi che utilizzano
la CPU. E in questo caso, lunghi intervalli di tempo sono molto adatti (100 ms).

In questo esempio ci sono 2 compiti che hanno operato in una 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à
l'intervallo temporale è diventato 40 ms, dove i compiti hanno completato il loro lavoro.

L'implementazione di MLFQ nel sistema operativo Solaris è una classe di pianificatori che dividono il tempo.
Il pianificatore fornisce un insieme di tabelle che definiscono esattamente come deve
cambiare la priorità di un processo nel corso della sua vita, quale dovrebbe essere la dimensione
della finestra allocata e con quale frequenza devono essere aumentate le priorità dei compiti. L'amministratore
di sistema può interagire con questa tabella e forzare il pianificatore a comportarsi.
diversamente. Per impostazione predefinita, in questa tabella ci sono 60 code con un aumento graduale
della dimensione della finestra da 20 ms (alta priorità) fino a diverse centinaia di ms (bassa priorità), e
anche con un potenziamento di tutte le attività ogni secondo.

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

Infine, molti pianificatori hanno altre caratteristiche. Ad esempio, alcuni
pianificatori riservano i livelli superiori per il funzionamento del sistema operativo e in questo
modo, nessun processo utente potrà ottenere la massima priorità nel
sistema. Alcuni sistemi consentono di fornire suggerimenti per aiutare
è possibile impostare correttamente le priorità. Ad esempio, con il comando nicely
si può aumentare o diminuire la priorità di un'attività, aumentando o
diminuiendo le probabilità che il programma ottenga tempo di CPU.

MLFQ: Conclusioni

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

Regola1: Se priorità(A) > priorità(B), verrà avviata l'attività A (B non verrà avviata)
Regola2: Se priorità(A) = priorità(B), A e B vengono avviate utilizzando RR
Regola3: Quando un'attività entra nel sistema, viene collocata nella coda con la priorità più alta.
Rule4: Dopo che un compito ha consumato il tempo a disposizione nella coda attuale (indipendentemente da quante volte ha liberato la CPU), la priorità di quel compito viene abbassata (si muove verso il basso nella coda).
Rule5: Dopo un certo periodo S, trasferire tutte le attività nel sistema alla massima coda.

MLFQ è interessante per il seguente motivo: invece di richiedere conoscenze sulla
natura dell'attività in anticipo, l'algoritmo studia il comportamento passato dell'attività e imposta
le priorità di conseguenza. In questo modo cerca di sedere su due seggi contemporaneamente: ottenere prestazioni per le piccole attività (SJF, STCF) e avviare equamente le lunghe
attività che caricano la CPU. Perciò molti sistemi, inclusi BSD e le loro derivate,
Solaris, Windows e Mac utilizzano una forma di algoritmo come pianificatore
MLFQ come base fondamentale.