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 =)

Pianificazione: coda di feedback multilivello

In questa conferenza parleremo dei problemi legati allo sviluppo di uno degli approcci più famosi a
pianificazione, che si chiama Coda di feedback multilivello (MLFQ). Lo scheduler MLFQ fu descritto per la prima volta nel 1962 da Fernando J. Corbató in un sistema chiamato
Sistema di condivisione del tempo compatibile (CTSS). Questi lavori (compresi i lavori successivi su
Multics) sono stati successivamente nominati per un Turing Award. Lo schedulatore era
successivamente migliorato e acquisito l'aspetto che si può già trovare in
alcuni sistemi moderni.

L'algoritmo MLFQ tenta di risolvere 2 problemi fondamentali sovrapposti.
In primo luogo, cerca di ottimizzare il tempo di consegna, che, come abbiamo discusso nella lezione precedente, è ottimizzato dal metodo di iniziare in testa alla coda più
compiti brevi. Tuttavia, il sistema operativo non sa per quanto tempo verrà eseguito questo o quel processo e questo
conoscenze necessarie per il funzionamento degli algoritmi SJF, STCF. In secondo luogo, MLFQ ci prova
rendere il sistema responsivo per gli utenti (ad esempio per chi si siede e
fissando lo schermo in attesa che l'attività venga completata) e quindi ridurre al minimo i tempi
risposta. Sfortunatamente, algoritmi come RR riducono i tempi di risposta, ma
hanno un effetto negativo sulla metrica del tempo di consegna. Da qui il nostro problema: come progettare
scheduler che soddisferà le nostre esigenze e allo stesso tempo non ne saprà nulla
la natura del processo, in generale? Come può lo scheduler apprendere le caratteristiche delle attività,
che lancia e quindi prendere decisioni di programmazione migliori?

L'essenza del problema: come pianificare l'impostazione dei compiti senza una conoscenza perfetta?
Come progettare uno scheduler che minimizzi contemporaneamente i tempi di risposta
per attività interattive e allo stesso tempo riduce al minimo i tempi di consegna senza saperlo
conoscenza del tempo di esecuzione dell'attività?

Nota: imparare dagli eventi precedenti

La coda MLFQ è un eccellente esempio di sistema su cui viene effettuato l'addestramento
eventi passati per predire il futuro. Tali approcci sono spesso
trovato nel sistema operativo (e in molti altri rami dell'informatica, inclusi i rami
previsioni hardware e algoritmi di memorizzazione nella cache). Viaggi simili
si innescano quando i compiti hanno fasi comportamentali e sono quindi prevedibili.
Tuttavia, bisogna fare attenzione con questa tecnica, perché le previsioni sono molto facili.
potrebbe rivelarsi sbagliato e portare il sistema a prendere decisioni peggiori di quelle previste
sarebbe del tutto privo di conoscenza.

MLFQ: regole di base

Considera le regole di base dell'algoritmo MLFQ. E sebbene le implementazioni di questo algoritmo
ce ne sono diversi, gli approcci di base sono simili.
Nell'implementazione che prenderemo in considerazione, MLFQ ne avrà diversi
code separate, ciascuna delle quali avrà una priorità diversa. In qualsiasi momento,
l'attività pronta per l'esecuzione è nella stessa coda. MLFQ utilizza le priorità,
per decidere quale attività eseguire per l'esecuzione, ad es. compito con più alto
priorità (un'attività dalla coda con la priorità più alta) verrà avviata per prima
coda.
Naturalmente, in una coda particolare possono esserci più attività
quindi avranno la stessa priorità. In questo caso verrà utilizzato il meccanismo
RR per la pianificazione del lancio tra queste attività.
Arriviamo così a due regole fondamentali per il MLFQ:

Regola 1: se priorità(A) > Priorità(B), l'attività A verrà eseguita (B no)
Regola 2: Se priorità(A) = Priorità(B), A&B vengono avviati utilizzando RR

Sulla base di quanto sopra, gli elementi chiave per pianificare un MLFQ sono:
sono priorità. Invece di dare una priorità fissa a ciascuno
compito, MLFQ cambia la sua priorità a seconda del comportamento osservato.
Ad esempio, se un'attività si chiude costantemente sulla CPU mentre attende l'input da tastiera,
MLFQ manterrà alta la priorità del processo perché è così
il processo interattivo dovrebbe funzionare. Se, al contrario, il compito è costantemente e
richiede un utilizzo intensivo della CPU per un lungo periodo, MLFQ ne eseguirà il downgrade
una priorità. Pertanto, MLFQ studierà il comportamento dei processi nel momento in cui sono in esecuzione.
e utilizzare comportamenti.
Disegniamo un esempio di come potrebbero apparire le code ad un certo punto
tempo e poi ottieni qualcosa del genere:

In questo schema, 2 processi A e B sono in coda con la priorità più alta. Processi
C è da qualche parte nel mezzo e il processo D è alla fine della coda. Secondo quanto sopra
descrizioni dell'algoritmo MLFQ, lo scheduler eseguirà solo le attività con il valore più alto
priorità secondo RR e le attività C, D saranno senza lavoro.
Naturalmente, un’istantanea statica non fornirà un quadro completo di come funziona il MLFQ.
È importante capire esattamente come cambia l'immagine nel tempo.

Tentativo 1: come modificare la priorità

A questo punto, devi decidere come MLFQ cambierà il livello di priorità
attività (e quindi la posizione dell'attività nella coda) durante il suo ciclo di vita. Per
di questo, è necessario tenere presente il flusso di lavoro: una certa quantità
attività interattive con tempi di esecuzione brevi (e quindi rilascio frequente
CPU) e diverse attività lunghe che utilizzano la CPU per tutto il tempo di lavoro, mentre
il tempo di risposta per tali attività non è importante. E così puoi fare il primo tentativo
implementare l'algoritmo MLFQ con le seguenti regole:

Regola 3: quando un'attività entra nel sistema, viene inserita nella coda con la più alta
priorità.
Regola 4a: se un'attività utilizza l'intero intervallo di tempo, allora
la priorità viene abbassata.
Regola 4b: se un task rilascia la CPU prima della scadenza del suo intervallo di tempo, allora
mantiene la stessa priorità.

Esempio 1: singola attività a lunga esecuzione

Come puoi vedere in questo esempio, l'attività all'ammissione è impostata con il massimo
priorità. Dopo una finestra temporale di 10 ms, la priorità del processo viene declassata.
pianificatore. Dopo l'intervallo di tempo successivo, l'attività viene finalmente declassata a
priorità più bassa nel sistema, dove rimane.

Esempio 2: ho scelto un compito breve

Vediamo ora un esempio di come MLFQ cercherà di avvicinarsi a SJF. In ciò
esempio, due attività: A, che è un'attività a esecuzione continua costante
occupando CPU e B, che è un breve compito interattivo. Supponiamo
che A era già in esecuzione da tempo quando è arrivato il compito B.

Questo grafico mostra i risultati dello scenario. L'attività A, come qualsiasi attività,
l'utilizzo della CPU era in fondo. L'attività B arriverà al tempo T=100 e lo farà
inserito nella coda con la priorità più alta. Poiché il tempo di esecuzione è breve,
verrà completato prima di raggiungere l'ultima coda.

Da questo esempio dovresti capire l'obiettivo principale dell'algoritmo: poiché l'algoritmo no
conosce un compito lungo o breve, quindi prima di tutto assume quel compito
breve e gli attribuisce la massima priorità. Se è davvero un compito breve, allora
verrà eseguito rapidamente, altrimenti se si tratta di un compito lungo si muoverà lentamente
in priorità e presto dimostrerà che è davvero un compito lungo che non lo fa
richiede una risposta.

Esempio 3: E l'I/O?

Ora diamo un'occhiata a un esempio di I/O. Come affermato nella regola 4b,
se un processo rilascia il processore senza aver utilizzato completamente il tempo del processore,
quindi rimane allo stesso livello di priorità. Lo scopo di questa regola è piuttosto semplice.
- se il lavoro interattivo esegue molti I/O, ad esempio, in attesa
dalle sequenze di tasti o dal mouse dell'utente, tale attività libererà il processore
prima della finestra assegnata. Non vorremmo tralasciare un compito così prioritario,
e quindi rimarrà allo stesso livello.

Questo esempio mostra come funzionerà l'algoritmo con tali processi: attività interattiva B, che richiede la CPU solo per 1 ms prima dell'esecuzione
Processo di I/O e un lungo lavoro A, che utilizza sempre la CPU.
MLFQ mantiene il processo B alla massima priorità mentre continua a farlo
rilasciare la CPU. Se B è un'attività interattiva, l'algoritmo in questo caso ha raggiunto
il suo scopo è avviare rapidamente attività interattive.

Problemi con l'attuale algoritmo MLFQ

Negli esempi precedenti, abbiamo creato una versione base di MLFQ. E sembra che lui
fa il suo lavoro bene ed equamente, distribuendo equamente il tempo della CPU tra
compiti lunghi e consentire compiti brevi o compiti a cui si accede molto spesso
all'I/O per elaborarli rapidamente. Sfortunatamente, questo approccio ne contiene diversi
problemi seri.
In primo luogo, il problema della fame: se il sistema avrà tanti interattivi
compiti, consumeranno tutto il tempo della CPU e quindi non un solo tempo
il compito non avrà la possibilità di essere eseguito (stanno morendo di fame).

In secondo luogo, gli utenti intelligenti potrebbero scrivere i loro programmi in questo modo
ingannare lo schedulatore. L'inganno sta nel fare qualcosa per forzare
scheduler per dare al processo più tempo di CPU. L'algoritmo che
sopra descritto è abbastanza vulnerabile a tali attacchi: prima che la finestra temporale sia praticamente
finito, è necessario eseguire un'operazione di I/O (per alcuni, non importa quale file)
e quindi liberare la CPU. Tale comportamento ti consentirà di rimanere nello stesso
la coda stessa e ottiene nuovamente una percentuale maggiore di tempo della CPU. Se fatto
questo è corretto (ad esempio esegui il 99% del tempo della finestra prima di rilasciare la CPU),
un compito del genere può semplicemente monopolizzare il processore.

Infine, un programma può modificare il proprio comportamento nel tempo. Quei compiti
che utilizzava la CPU può diventare interattivo. Nel nostro esempio, simile
le attività non riceveranno un trattamento adeguato dallo scheduler, come farebbero altri
compiti interattivi (originali).

Domanda al pubblico: quali attacchi allo scheduler potrebbero essere sferrati nel mondo moderno?

Tentativo 2: aumentare la priorità

Proviamo a cambiare le regole e vediamo se possiamo evitare problemi con
fame. Cosa possiamo fare per garantire che ciò sia correlato
Le attività della CPU avranno il loro tempo (anche se non molto).
Come soluzione semplice al problema, puoi suggerire periodicamente
aumentare la priorità di tutti questi compiti nel sistema. Ci sono molti modi
per raggiungere questo obiettivo, proviamo ad implementare qualcosa di semplice come esempio: tradurre
tutte le attività contemporaneamente alla massima priorità, da qui la nuova regola:

Rule5: Dopo un certo periodo S, trasferisce tutte le attività nel sistema nella coda più alta.

La nostra nuova regola risolve due problemi contemporaneamente. Innanzitutto, i processi
garantito di non morire di fame: le attività nella coda più alta verranno condivise
tempo del processore secondo l'algoritmo RR e quindi tutti i processi riceveranno
tempo del processore. In secondo luogo, se alcuni processi utilizzati in precedenza
solo il processore diventa interattivo, rimarrà in coda con il più alto
priorità dopo aver ricevuto una volta un potenziamento alla priorità più alta.
Considera un esempio. In questo scenario, considera un singolo processo utilizzando

CPU e due brevi processi interattivi. A sinistra nella figura, la figura mostra il comportamento senza aumento di priorità, e quindi l'attività a lunga esecuzione inizia a morire di fame dopo che due attività interattive arrivano sul sistema. Nella figura a destra, ogni 50 ms viene eseguito un aumento di priorità e quindi è garantito che tutti i processi ricevano tempo del processore e verranno avviati periodicamente. In questo caso viene preso come esempio 50 ms, in realtà questo numero è leggermente più alto.
È ovvio che la somma del tempo di salita periodica S porta a
domanda logica: quale valore dovrebbe essere impostato? Uno dei meritati
gli ingegneri di sistema John Ousterhout si riferivano a quantità simili nei sistemi come voo-doo
costante, poiché in qualche modo richiedevano la magia nera per il corretto
esposizione. E, sfortunatamente, S ha un sapore così. Se imposti anche il valore
compiti grandi e lunghi moriranno di fame. E se lo imposti troppo basso,
le attività interattive non riceveranno il tempo CPU adeguato.

Tentativo 3: migliore contabilità

Ora abbiamo un altro problema da risolvere: come non farlo
permettere di imbrogliare il nostro scheduler? I colpevoli di questa possibilità sono
regole 4a, 4b che consentono a un lavoro di mantenere la sua priorità liberando il processore
prima della scadenza del tempo assegnato. Come affrontarlo?
La soluzione in questo caso può essere considerata una migliore contabilizzazione del tempo della CPU su ciascuno
Livello MLFQ. Invece di dimenticare il tempo utilizzato dal programma
processore per l'intervallo assegnato, dovresti tenerne conto e salvarlo. Dopo
il processo ha esaurito il tempo assegnato, dovrebbe essere retrocesso al successivo
livello di priorità. Ora non importa come il processo utilizzerà il suo tempo: come
elaborando costantemente sul processore o come un insieme di chiamate. Così,
la regola 4 dovrebbe essere riscritta come segue:

Rule4: Dopo che un'attività ha esaurito il tempo assegnato nella coda corrente (indipendentemente da quante volte ha liberato la CPU), la priorità di tale attività viene ridotta (si sposta lungo la coda).

Diamo un'occhiata ad un esempio:
»

La figura mostra cosa succede se provi a ingannare lo scheduler
se fosse con le regole precedenti 4a, 4b sarebbe il risultato a sinistra. Con nuovo
la regola è che il risultato è a destra. Prima della protezione, qualsiasi processo poteva chiamare I/O prima del completamento e
dominano così la CPU, dopo aver abilitato la protezione, indipendentemente dal comportamento
I/O, scenderà comunque in coda e quindi non potrà farlo disonestamente
assumere il controllo delle risorse della CPU.

Miglioramento del MLFQ e altre questioni

Con i miglioramenti di cui sopra sorgono nuovi problemi: uno dei principali
domande: come parametrizzare tale scheduler? Quelli. Quanto dovrebbe essere
code? Quale dovrebbe essere la dimensione della finestra del programma all'interno della coda? Come
il programma dovrebbe spesso avere la priorità per evitare la fame e
tenere conto del cambiamento nel comportamento del programma? A queste domande, non c'è niente di semplice
risposta e solo esperimenti con carichi e successiva configurazione
lo scheduler può portare ad un equilibrio soddisfacente.

Ad esempio, la maggior parte delle implementazioni MLFQ consentono di assegnare valori diversi
fasce orarie per le diverse code. Di solito lo sono le code ad alta priorità
brevi intervalli. Queste code consistono in attività interattive,
il passaggio da uno all'altro è abbastanza sensibile e dovrebbe richiedere 10 o meno
SM. Al contrario, le code a bassa priorità sono costituite da attività a lunga esecuzione che utilizzano
PROCESSORE. E in questo caso, intervalli di tempo lunghi si adattano molto bene (100 ms).

In questo esempio, ci sono 2 attività che hanno funzionato nella coda 20 ad alta priorità
ms diviso in finestre da 10ms. 40ms nella coda centrale (finestra di 20ms) e nella coda a bassa priorità
la finestra temporale della coda è diventata 40 ms in cui le attività hanno completato il proprio lavoro.

L'implementazione di MLFQ nel sistema operativo Solaris è una classe di pianificatori time-shared.
Lo scheduler fornirà una serie di tabelle che definiscono esattamente come dovrebbe essere
cambiare la priorità del processo nel corso della sua vita, quale dovrebbe essere la dimensione
finestra da assegnare e la frequenza con cui aumentare le priorità delle attività. Amministratore
il sistema può interagire con questa tabella e far comportare lo scheduler
diversamente. Per impostazione predefinita, questa tabella ha 60 code con un aumento graduale
dimensione della finestra da 20 ms (alta priorità) a diverse centinaia di ms (priorità più bassa) e
anche con il potenziamento di tutte le attività una volta al secondo.

Altri scheduler MLFQ non utilizzano una tabella o qualcosa di specifico
le regole descritte in questo capitolo, al contrario, calcolano le priorità utilizzando
formule matematiche. Ad esempio, lo scheduler di FreeBSD utilizza una formula per
calcolo della priorità dell'attività corrente in base alla durata del processo
utilizzato la CPU. Inoltre, l'utilizzo della CPU diminuisce nel tempo e quindi
Pertanto, l'aumento della priorità è leggermente diverso da quello descritto sopra. Questo è vero
chiamati algoritmi di decadimento. A partire dalla versione 7.1, FreeBSD utilizza lo scheduler ULE.

Infine, molti pianificatori hanno altre funzionalità. Ad esempio, alcuni
gli scheduler riservano livelli più alti per il funzionamento del sistema operativo e quindi
Pertanto, nessun processo utente può ottenere la massima priorità
sistema. Alcuni sistemi ti consentono di dare consigli per aiutare
lo scheduler per stabilire correttamente la priorità. Ad esempio, utilizzando il comando bello
puoi aumentare o diminuire la priorità di un'attività e quindi aumentare o diminuire
ridurre le possibilità del programma per il tempo della CPU.

MLFQ: riepilogo

Abbiamo descritto un approccio di pianificazione chiamato MLFQ. Il suo nome
concluso nel principio di funzionamento: ha diverse code e utilizza il feedback
dare priorità a un compito.
La forma finale delle regole sarà la seguente:

Rule1: Se priorità(A) > Priorità(B), l'attività A verrà eseguita (B no)
Rule2: Se priorità(A) = Priorità(B), A&B vengono avviati utilizzando RR
Rule3: quando un'attività entra nel sistema, viene inserita nella coda con la priorità più alta.
Rule4: Dopo che un'attività ha esaurito il tempo assegnato nella coda corrente (indipendentemente da quante volte ha liberato la CPU), la priorità di tale attività viene ridotta (si sposta lungo la coda).
Rule5: Dopo un certo periodo S, trasferisce tutte le attività nel sistema nella coda più alta.

MLFQ è interessante per il seguente motivo: invece di richiedere conoscenze su
natura del compito in anticipo, l'algoritmo apprende il comportamento passato del compito e lo imposta
priorità di conseguenza. Pertanto, cerca di sedersi su due sedie contemporaneamente: per ottenere prestazioni per compiti piccoli (SJF, STCF) e per eseguire onestamente quelli lunghi,
Lavori di caricamento della CPU. Pertanto, molti sistemi, inclusi BSD e i loro derivati,
Solaris, Windows, Mac utilizzano una qualche forma di algoritmo come pianificatore
MLFQ come riferimento.

Materiali aggiuntivi:

Fonte: habr.com

Sistemi operativi: tre pezzi facili. Parte 5: Pianificazione: coda di feedback multilivello (traduzione)