riassunto sistemi operativi

Domande Unifacile sistemi operativi

Paginazione Linux

Guarda domanda 22 (Gestione della memoria fisica in Linux)

Algoritmo buddy-heap

Quando ho delle pagine fisiche contigue le raggruppo insieme formando una regione. Abbiamo che le regioni fisiche possono essere di dimensioni diverse ma prestabilite. Ogni regione ha una dimensione pari a 2ⁿ pagine quindi non hanno dimensioni qualsiasi. La lista dei frame liberi diventa una lista unica per ogni taglio di regione (1 lista per le regioni da una pagina, 1 lista per quelle da due pagine e così via). Ognuna di queste liste può contenere solo regioni di una determinata dimensione, alcune di queste liste possono anche essere vuote. Ad ogni richiesta di memoria (si adotta la strategia best-fit):

• Sia k il numero di pagine richieste (es. k=5).
• Si calcola m pari alla prima potenza di 2 superiore a k (es. m=8).
• Se esiste una regione nella lista delle regioni a dimensione m, viene allocata alla richiesta. Altrimenti si cerca nelle liste delle regioni di dimensioni immediatamente superiori (2m, 4m, ...) fino a trovare una regione libera.
• Una volta individuata una regione, supponendo che sia 2^hm la sua dimensione, essa viene divisa in due buddy per h volte fino ad ottenere una regione della dimensione desiderata.

Vantaggi:

• Allocazione della memoria molto veloce perché usa delle regioni e perché le regioni le conosco a priori.

Svantaggi:

• Abbiamo sia frammentazione interna che esterna.

Esistono due tipi di frammentazioni interna:

1. Ogni pagina può essere occupata parzialmente e questo problema non può essere eliminato.
2. Il secondo tipo di frammentazione si ha a livello di regione. Linux usa un misto tra allocazione contigua a partizione fisse e variabili, qui diciamo che le partizioni fisiche possono avere solo alcune determinate dimensioni (potenze del due) e quindi se ad una regione logica gli si assegna una determinata regione fisica e quella regione fisica è più grande della regione logica, potenzialmente ho interi frame che non utilizzo ma qui possiamo recuperare queste porzioni di regioni fisiche non utilizzate. Se ci sono pagine piccole della stessa dimensione e sono adiacenti costituiscono due buddy e possono essere raggruppati per formare una regione di dimensione maggiore.

Regioni esterne di grandi dimensioni sono rare e quindi la frammentazione esterna si verifica raramente, si ha quando abbiamo regioni logiche di grandi dimensioni ma queste sono rare.

Memoria virtuale

Lo spazio di indirizzamento è costituito da un insieme di regioni. Ogni regione rappresenta un insieme di pagine logicamente contigue, contenenti informazioni omogenee tra loro (codice, dati, ...). Ogni regione è descritta da una struttura dati (vm_area_struct) che contiene tra l'altro:

• Permessi di lettura, scrittura ed esecuzione,
• Proprietà di paginazione,
• Informazioni riguardo i file,
• Numero della prima e dell'ultima pagina appartenente alla regione.

Questo perché l'indirizzo logico che viene generato non contiene il numero di regione, il numero di pagina e lo scostamento, ma in realtà è composto da più numeri di pagina rendendo più veloce la traduzione. Le regioni relative ad uno spazio di indirizzamento sono organizzate in un albero binario bilanciato, per una rapida ricerca della regione corrispondente ad un dato indirizzo virtuale.

L'indirizzo logico è composto da:

• g = numero di pagina esterna
• m = numero di pagina intermedia
• p = numero di pagina interna

Algoritmo di sostituzione

Linux controlla sempre se ci sono delle pagine liberi disponibili (mantiene sempre una certa soglia in modo da cercare di poter far entrare sempre un processo), se si scende al di sotto di una certa soglia inizio a liberare pagine fino a quando non riporta il numero di frame liberi sopra una certa soglia. Esiste un demone chiamato kswapd il cui codice viene eseguito una volta al secondo verifica che ci siano abbastanza pagine libere disponibili, in caso contrario, seleziona una pagina occupata e la rende libera. In questo modo garantisco che quando un processo richiede una pagina che non è in memoria l'unica operazione che deve eseguire è lo swap-in in quanto lo swap-out viene fatto dal kswapd non in quel momento. Riduce quindi i tempi di swap.

Per mappare le pagine ho due alternative. La prima, divido il disco in 2 parti:

• File, i dati che mi servono.
• Area di swap, è l'area in cui vengono memorizzate le pagine. Quindi serve solo per contenere lo spazio logico dei processi.

Esiste però un'altra alternativa in cui lavoro solo con il file system cioè gestisco soltanto i file della MM (Memoria Virtuale), quindi anche i miei processi vengono mappati su disco come dei file. Quindi ogni volta che faccio lo swap out, chiedo al file system di scrivere su un file tutto lo spazio degli indirizzi (windows).

In linux i dati vengono swappati sull'area di swap il che risulta più efficiente e il codice sta sul file eseguibile.

Algoritmo di selezione

Questo algoritmo di selezione è globale e non locale. È lo swapper che decide quale pagine togliere e a chi. L'algoritmo è piuttosto complesso, riportiamo una versione semplificata:

• Si cerca il processo che ha più pagine in memoria
• Si analizzano tutte le sue regioni (a partire dall'ultima regione analizzata nella ricerca precedente) e se ne seleziona una (non vengono considerate le pagine condivise, utilizzate dai canali DMA, locked, assenti dalla memoria).
• Selezionata la regione si deve selezionare la pagina e per far questo si adotta l'algoritmo dell'orologio a doppia scansione. Cioè si utilizzano due bit per ogni pagina: 1 bit di attività, mi dice se la mia pagina sta nella lista delle pagine attive oppure non attive quindi abbiamo che:
  • 1 — è nella lista delle pagine attive
  • 0 — è nella lista delle pagine inattive
• 1 bit di riferimento:
  • 1 — è stata usata di recente
  • 0 — non è stata usata di recente

All'atto di caricamento della pagina ho tutti e due bit a zero, ogni volta che uso una pagina metto il bit di riferimento a 1 come avevamo visto in passato. Il kswapd periodicamente cerca di osservare per ogni pagina se il bit di riferimento è a 1, qualora lo fosse, il bit di riferimento viene posto a 0 mentre quello di attività viene messo a 1, è una pagina attiva. Se invece tale pagina ha il bit di riferimento a 0 e quello di attività a 1 mette quello di attività a zero. Dà quindi un'opportunità in più avendo un bit in più. La pagina vittima è quella con entrambi i bit a zero.

Vantaggio:

• Utilizzando 2 bit abbiamo un'informazione più ricca quindi ho più precisione, riesco a distinguere più casi.

Creazione di un nuovo spazio di indirizzamento virtuale in Linux

Linux crea un nuovo spazio di indirizzamento virtuale quando:

• Viene eseguita una exec
  • Viene creato uno spazio di indirizzi completamente vuoto.
  • È compito del caricatore popolare lo spazio con regioni di memoria virtuale.
• Viene eseguita una fork
  • Viene creata una copia dello spazio di indirizzamento del task genitore.
  • Il kernel copia tutti i vm area struct del genitore. Copia quindi tutti gli indirizzi del genitore inizialmente. Puntano quindi le stesse regioni all'inizio.
  • Crea un nuovo insieme di tabelle delle pagine per il figlio.
• Il contenuto delle tabelle delle pagine del genitore è copiato nelle tabelle del figlio.
• Dopo la fork, genitore e figlio condividono le stesse pagine fisiche (anche quelle private del genitore).
  • La pagina di una regione privata viene duplicata solo in fase di esecuzione, quando uno dei due task chiede di modificarla.
• Così le copie delle pagine si creano solo quando è necessario, cioè, quando il task figlio fa riferimento ad una regione che però non è condivisa (solo in questa situazione).

Linux adotta per i programmi eseguibili due formati differenti:

• Il formato a.out (comune ai vecchi sistemi unix)
• Il formato ELF (specifico di Linux).

Inizialmente il programma eseguibile viene mappato nello spazio di indirizzamento virtuale, ma le pagine non vengono caricate:

• Solo quando il task chiede di accedere ad una data pagina, ci sarà un page fault e di conseguenza la pagina verrà caricata (swapped in) nella memoria fisica.
• Il compito del caricatore è quello di instaurare le associazioni iniziali per permettere l'avvio dell'esecuzione del programma.

L'area di memoria di un task è divisa in questo modo:

Linux permette due tipi di collegamento alle librerie di sistema:

• Il collegamento statico
• Il collegamento dinamico (occupa meno spazio sia in memoria centrale sia su disco)

Algoritmo del banchiere

L'Algoritmo del banchiere è utilizzato per evitare i deadlock nell'allocazione delle risorse. In particolare questo algoritmo può indicare se un sistema (in particolare un sistema operativo) si venga a trovare in uno stato sicuro o meno nel caso assegnasse una risorsa ad uno dei processi richiedenti. La complessità computazionale di questo algoritmo è O(n²m), dove n è il numero di processi e m il numero di tipi di risorse (per ogni tipo possono essere disponibili più risorse - per esempio, due stampanti equivalenti, porte di comunicazione, ecc.).

Concetto alla base dell’algoritmo:

Un sistema, nell'allocare le risorse che vengono richieste, deve procedere come farebbe una banca. I processi sono visti come dei clienti che possono richiedere del credito presso la banca (fino ad un certo limite individuale) e le risorse allocabili sono viste come i soldi. È chiaro che il sistema, come la banca, non può permettere a tutti i clienti di raggiungere il loro limite di credito contemporaneamente, poiché in tal caso la banca fallirebbe (e il sistema non potrebbe allocare risorse a sufficienza, causando un deadlock).

Lo stato sicuro quindi è uno stato in cui è possibile allocare tutte le risorse richieste da un processo senza che quest'ultimo comporti un deadlock con un altro processo. Il fatto che il sistema si trovi in uno stato sicuro non implica che tutte le allocazioni di risorse avverranno con successo, ma solo che esiste almeno un modo sicuro per allocare tutte le risorse. Se il sistema si trova in uno stato sicuro il deadlock può essere evitato, ma ovviamente uno stato non sicuro non implica necessariamente un deadlock. Il sistema infatti può dunque evitare del tutto gli stalli se ad ogni richiesta di una risorsa da parte di un processo, effettua una verifica dello stato in cui si troverebbe allocando la risorsa. Se lo stato futuro è sicuro, allora la risorsa può essere tranquillamente allocata. A tal fine si può utilizzare l'algoritmo del banchiere.

Questo concetto è difficilmente attuabile sui sistemi moderni, sia perché non è possibile prevedere in modo deterministico l'allocazione delle risorse, come richiesto dall'algoritmo del banchiere, sia perché sarebbe troppo costoso in termini economici. La maggior parte dei sistemi operativi, a partire dallo Unix, non considera il problema di eventuali deadlock in quanto esso infatti è un evento molto raro, data l'abbondanza delle risorse a disposizione. Inoltre è doveroso aggiungere che oggigiorno la gestione dei deadlock è sicuramente più critica nei database che non nei sistemi operativi.

Appunti: L’idea è quella delle banche: prima di soddisfare un prelievo, la banca deve essere sicura che ci siano soldi. Nel nostro caso possiamo dire che il sistema operativo, prima di concedere una risorsa, va a vedere se rimangono un numero di risorse che riescono a far progredire il sistema. Lavorare con il grafo adesso, visto che abbiamo risorse a istanza multipla, non serve più, in quanto le quattro proprietà non sono più condizione necessaria e sufficiente.

N numero di processi.

M tipi di risorse.

Abbiamo una serie di strutture dati:

• Available: vettore di lunghezza m. Se Available[j] = k, ci sono k istanze ancora disponibili della risorsa di tipo Rj. Questo mi dice il numero di istanze libere per quella risorsa.
• Max: matrice n x m. Se Max[i,j] = k, allora il processo Pi può richiedere al massimo k istanze alla risorsa Rj, cioè rappresenta quante istanze può richiedere quel processo Pj.
• Allocation: matrice n x m. Se Allocation[i,j] = k allora a Pi sono attualmente allocate k istanze di Rj. Questa mi serve per vedere quali sono le istanze allocate al processo.
• Need: matrice n x m. Se Need[i,j] = k, allora Pi può aver bisogno ancora di altre k istanze di Rj per completare il suo compito.

Il cuore dell’algoritmo è andare a vedere se siamo in uno stato sicuro oppure no, e lo fa in quattro passi:

1. Supponiamo che Work e Finish siano due vettori di lunghezza m (tipi di risorse) e n (numero di processi), rispettivamente. Inizializziamo: Work = Available & Finish[i] = false per i = 1,2, … , n. Cioè tale vettore non è finito.
2. Si cerca un indice i per cui valgano A e B, ovvero si cerca un processo che non abbia ancora terminato e tale per cui il suo vettore di necessità sia più piccolo delle risorse disponibili (ossia si può soddisfare la richiesta di necessità del processo Pi):
   • (A) Finish[i] = false, ovvero Pi non ha ancora terminato il suo compito.
   • (B) L’i-esima riga di Need <= Work, cioè il numero di risorse di cui il processo Pi può ancora aver bisogno per completare il suo compito deve essere minore di quelle ancora disponibili ==> se vale il punto A e se le risorse di cui ho bisogno sono minori delle risorse disponibili per completare il suo lavoro allora passo al punto 3, altrimenti vado al punto 4.
3. Work = Work + (i-esima riga di Allocation), il processo Pi termina e libera le sue risorse, cioè somma alle attuali risorse disponibili il vettore che indica il numero di risorse allocate al processo Pi prima di terminare; Finish[i] = true, ovvero il processo i-esimo ha terminato; torna al punto 2.
4. Se Finish[i] == true per ogni i, allora lo stato è sicuro.

Se alla fine dell’algoritmo il vettore di finish è tutto a true, allora sono in uno stato sicuro, perché significa che tutti i processi hanno terminato. Questo algoritmo quindi ci serve per osservare se uno stato è sicuro oppure no.

Ora analizziamo l’algoritmo che gestisce le richieste:

Request = vettore di richiesta per il processo Pi. Se Request[j] = k allora il processo Pi vuole K istanze dalla risorsa Rj. Request è quindi un vettore che ci indica le istanze richieste.

1. Se l’i-esima riga di Request <= i-esima riga di Need allora vai al punto 2. Se questa condizione non è verificata significa che all’inizio il processo aveva bisogno di certe risorse e poi durante l’esecuzione le ha eccedute, che è una condizione di errore.
2. Se l’i-esima riga di Request <= Available, vai al punto 3. Altrimenti Pi deve aspettare, finché le risorse non diventano disponibili.
3. Fingiamo di allocare le risorse richieste a Pi modificando lo stato come segue:
   • Available = Available - l’i-esima riga di Request, cioè allochiamo le risorse al processo Pi e conseguentemente diminuiamo le risorse disponibili;
   • L’i-esima riga di Allocation = L’i-esima riga di Allocation + L’i-esima riga di Request, cioè le risorse allocate aumentano in numero pari a quelle che ha appena richiesto;
   • L’i-esima riga di Need = L’i-esima riga di Need - L’i-esima riga di Request, cioè il processo Pi abbassa le sue pretese in quanto ha appena ricevuto delle risorse e sicuramente in futuro dovrebbe aver bisogno di meno risorse;
4. Se siamo in uno stato sicuro ==> le risorse sono allocate a Pi. Se siamo in uno stato non sicuro ==> Pi deve aspettare, e il vecchio stato è ripristinato (?). Non è soddisfatta l’attesa limitata.

Esempio da vedere su dispensa.

Scheduling Processi Linux

Dalle varie versioni di Linux ci sono stati differenti algoritmi di scheduling. Dalla versione 2.2 del kernel sono stati introdotti degli elementi di tipo real-time (soft real-time). Dalla versione 2.4 è stata introdotta una versione complessa di scheduling che si basava sul concetto di crediti che venivano assegnati ai processi, però lo scheduler aveva complessità del tipo O(n), il che era molto vantaggioso. Siccome lo scheduler viene invocato ad ogni context switch, anche O(n) ha un certo peso in termini di tempo, quindi si cercò di migliorare lo scheduler. Dalla versione 2.6 lo scheduler aveva complessità costante O(1), però ciò non implica che sia basso il tempo di scheduling ma solo che esso è indipendente dal numero dei task. Dalla versione 2.6.23 in poi è stato introdotto un altro algoritmo che va sotto il nome di completely fair scheduler la cui complessità è O(log n). Tale complessità, al contrario degli algoritmi precedenti, si ha non quando viene selezionato un task, infatti in quel caso è costante, ma quando viene aggiunto un task in coda e quindi le prestazioni sono molto buone.

Linux adotta un’elaborazione dei processi in modo simmetrico (SMP) e con code multiple. Ogni volta che creo un nuovo task, non solo bisogna decidere quanta memoria assegnare a quel task, ma anche in che processore assegnarlo. Esistono quindi degli algoritmi di ribilanciamento dei task sulle code. Quando dobbiamo spostare dei task da una coda ad un’altra, queste due code si devono bloccare, per evitare problemi di coerenza e/o corsa critica c’è un semaforo per ogni coda, e quando c’è una migrazione le code si bloccano.

Esistono due tipi di task:

• Real-time, devono terminare prima il loro lavoro
• Time-sharing, sono tutti gli altri task quelli che hanno minore priorità, come quelli int...