Teoria di Sistemi operativi

U1B - Hardware

Ciclo di funzionamento di un processore

Un programma è un insieme o una sequenza di istruzioni, le quali saranno caricate da qualche parte a partire da una certa locazione nella memoria centrale. Le nostre istruzioni in linguaggio macchina sono formate così: da una parte c’è il codice dell’operazione (lettura, scrittura ecc...), la seconda parte sono degli operandi, che possono essere valori assoluti (numeri) oppure degli indirizzi.

Accendiamo la macchina, viene settato tutto a 0, inizia a funzionare la CPU.

Fase di fetch

Inizia la la CPU prende il Program Counter (PC), che è 0, lo carica nel Memory Address Register (MAR), tramite il bus indirizzi invia al controller della memoria l’indirizzo, il quale legge il contenuto di quell’indirizzo e lo carica tramite il bus dati nel Memory Data Register (MDR). Dal Memory Data Register questo valore va copiato nell’Instruction Register (IR). L’Unità di Controllo vede che è un’istruzione di load (va a leggere la cella di memoria il cui indirizzo è dato dall’operando e lo carica nel registro accumulatore). Il registro di controllo ha capito che è questa l’istruzione, quindi ricopia l’operando che è 24 dall’Instruction Register nel Memory Address Register, invia al controller della memoria il comando di lettura di quell’indirizzo, e il contenuto viene mandato attraverso il bus dati al Memory Data Register del nostro processore. Da qui verrà copiato nell’accumulatore.

L’istruzione è finita, ma si nota come terminata la fase di decode, il Program Counter sia passato da 0 a 1, e quindi riprende la fase di fetch, prende il contenuto del Program Counter che questa volta è uno e lo carica nel memory address register e così rinizia il tutto.

Organizzazione della memoria

Caching: consiste nel copiare i dati contenuti nella memoria di un certo livello in una memoria di livello superiore (più veloce). Questa serve per tenere i dati che sono stati utilizzati più di recente.

Coerenza della cache

Una cache può essere utilizzata per migliorare le prestazioni di accesso a una data risorsa. Quando ci sono diverse cache per la stessa risorsa, questo può portare a problemi. Per cui la coerenza della cache si riferisce a una serie di modi per assicurarsi che tutte le cache della risorsa abbiano gli stessi dati, e che i dati nelle cache abbiano senso.

Bus Snooping: Ogni cache controller spia il bus per cambiare lo stato dei dati nella sua cache.

Protocolli basati sull’invalidazione: MSI e MESI

Protocolli basati sull’aggiornamento: DRAGON

Gestione richiesta I/O

Nelle architetture più semplici si trovano normalmente 3 tipi di schemi per eseguire le azioni di I/O:

• I/O Programmato con Busy-Waiting (attesa attiva): Ci sono delle istruzioni nel mio programma che chiedono al dispositivo di eseguire delle operazioni, viene definita “attesa attiva” perché il processore ad ogni ciclo di CPU va a chiedere al dispositivo se ha terminato l’operazione oppure no. Il problema è che la velocità di comunicazione di un dispositivo I/O è estremamente più lenta rispetto a quella di un processore, quindi questo approccio non è molto conveniente, inoltre in questo modo si riesce ad avere un solo programma in esecuzione.
• I/O guidato dalle interruzioni (interrupt): Per evitare di tenere bloccata la CPU in un ciclo di controllo in attesa che termini l’operazione richiesta, si può utilizzare quest’altro approccio. Ovvero mentre i dispositivi di I/O lavorano, la CPU potrebbe essere impegnata in compiti più utili (ad esempio eseguire un altro programma). Il controller del dispositivo I/O invia egli stesso un segnale sul bus dati (Interrupt) che arriva alla CPU, la CPU a questo punto legge il registro del controller e copia il contenuto nella memoria centrale.

Problemi

Come mi comporto se ho più I/O che inviano segnali di interrupt? Collego gli I/O in OR e poi tramite il polling o utilizzando la tecnica dell’Interrupt vettorizzato individuo il dispositivo che ha lanciato l’interrupt.

Come mi comporto se ho più interrupt contemporaneamente? La CPU avverte un solo segnale, per cui:

• Se si usa il Polling, l’ordine di scansione determina un ordinamento implicito tra i dispositivi.
• Se si usa l’interrupt vettorizzato, occorre impostare un protocollo di comunicazione tra CPU e dispositivi: quando la CPU ha ricevuto l’interrupt ed è pronta a gestirlo, invia un segnale di Acknowledge (INTA). Quando il controller riceve il segnale invia l’identificatore del dispositivo (vettore di interrupt) sul bus dati. Se il segnale di INTA viene propagato sequenzialmente dai controllori dei dispositivi (collegamento daisy chain) e assorbito dal primo controller che aveva un interrupt pendente, si ha un ordinamento implicito tra i dispositivi determinato dal collegamento in daisy chain degli stessi.

Come mi comporto se arriva un secondo interrupt mentre gestisco un primo interrupt?

Cosa succede quando la CPU riceve un interrupt?

• L’istruzione macchina in corso viene completata.
• Si salva in memoria (registri e program counter) lo stato della computazione interrotta nel descrittore di processo.
• Si determina il tipo di interrupt che è avvenuta (tramite polling o interrupt vettorizzato).
• Si salta ad una posizione in memoria dov’è contenuto l’interrupt handler ovvero il gestore di quel tipo di interruzioni (es. driver) infatti sono segmenti di codice separati.
• Dopo aver gestito l’interrupt, viene ripristinato lo stato del programma interrotto e la sua esecuzione.

Tutto ciò deve essere trasparente rispetto a chi viene interrotto.

I/O con accesso diretto alla memoria (DMA)

Questo approccio viene utilizzato dai dispositivi I/O ad alta velocità in grado di trasferire dati a una velocità vicina a quella della memoria. Il controller del dispositivo trasferisce blocchi di dati dal buffer direttamente alla memoria centrale senza l’intervento della CPU. Viene generato un solo interrupt per blocco piuttosto che un interrupt per byte. Poiché il bus di collegamento tra memoria e il controller DMA è condiviso occorre un arbitro che gestisca i conflitti evitando il furto di cicli (fenomeno del Cycle Stealing, ovvero “furto di cicli (del bus)”).

Interruzioni software (Trap)

Una trap è un’interruzione software, ovvero causato dall’esecuzione di una determinata istruzione del programma in esecuzione. Queste istruzioni possono infatti o presentare degli errori, oppure possono essere istruzioni esplicite che richiedono un servizio del SO tramite una System Call. Le trap vengono trattate in modo del tutto analogo agli interrupt. Ma c’è una differenza: gli interrupt sono asincroni rispetto al programma in esecuzione mentre le trap sono sincrone perché causate dal programma in esecuzione.

System Call

Indica il meccanismo usato da un processo a livello utente, per richiedere un servizio a livello kernel del sistema operativo. Le system call sono realizzate tramite trap. Esistono 3 metodi per il passaggio dei parametri:

• I valori dei parametri vengono memorizzati nei registri.
• I valori dei parametri vengono memorizzati in una tabella in memoria e l’indirizzo della tabella viene memorizzato in un registro.
• I valori dei parametri vengono memorizzati dal programma con una operazione di push nello Stack e letti dal SO con una operazione di pop.

Memoria centrale

La memoria centrale è un supporto di memorizzazione (volatile) che può essere acceduto direttamente dalla CPU. La memoria secondaria è una estensione della memoria centrale, in grado di fornire un supporto di memorizzazione non volatile e di maggiori dimensioni.

Protezioni hardware

Alla base della protezione c’è il cosiddetto funzionamento in Dual-Mode. Infatti quando la CPU esegue le istruzioni può lavorare in due modalità distinte:

• Modalità utente: il sistema sta eseguendo istruzioni per conto di programma utente.
• Modalità kernel: il sistema sta eseguendo istruzioni per conto del SO.

Anche le istruzioni vengono divise in:

• Istruzioni privilegiate: istruzioni macchina eseguibili soltanto dal kernel in grado di causare danni allo stato del sistema.
• Istruzioni non privilegiate: tutte le altre istruzioni eseguibili da tutti i processi.

Quando c’è una interruzione o una trap, l’hardware passa in modalità kernel tramite una system call. In questo modo il sistema passa in modalità kernel. All’istruzione di ritorno da interrupt, viene ripristinata la modalità utente. Per fare ciò all’hardware del computer viene aggiunto un bit di modo per indicare la modalità di funzionamento: kernel (0) o user (1).

U2A - Processi e thread

Diagramma di stato di un processo

La creazione avviene quando chiediamo al SO di mandare in esecuzione un programma. Quindi il programma sta effettuando una chiamata di sistema a una funzione specifica del kernel (quella che richiede l’esecuzione del programma). Questa funzione del kernel viene definita fork, è la modalità attraverso cui un processo crea in memoria una copia di se stesso: la copia prenderà il nome di processo figlio, mentre il processo originale verrà chiamato processo padre.

Va in esecuzione il codice della fork, ma ancora il processo non è in grado di lavorare. Il SO deve creare una struttura per contenere il programma. Appena gli viene assegnata la memoria il programma passa in stato di ready (che è lo stato in cui è pronto per la CPU).

Quando lo scheduler sceglie il processo da mandare in esecuzione, passa il descrittore del processo che ha scelto al dispatcher che assegna il programma alla CPU. In questo modo il processo passa in stato di running.

Da qui ci possono essere 3 possibili situazioni che causano un cambiamento di stato quando il mio programma è in fase di running:

• Interruzione software: Esecuzione di un’interruzione ad es. in seguito a un’operazione di I/O, per cui il processo passa in stato di waiting. Quando viene completata l’operazione passa in stato di ready.
• Interruzione hardware da parte di un altro processo esterno: in questo caso il processo passa in stato di ready.
• Avviene una exit, viene liberata la memoria e il programma termina la sua esecuzione.

Le informazioni relative ad un processo sono contenute in una struttura dati apposita chiamata Process Control Block o descrittore di processo.

Context switch: indica una particolare operazione del SO che conserva lo stato del processo o thread, in modo da poter essere ripreso in un altro momento. Questa attività permette a più processi di condividere la CPU, ed è anche una caratteristica essenziale per i sistemi operativi multitasking.

U2C - Stallo e attesa indefinita

Deadlock (stallo)

Il deadlock (o stallo) è quella situazione in cui due o più processi sono in attesa per un tempo indefinito di un evento che può essere causato solo da un processo a sua volta in attesa. La starvation (o attesa indefinita) è la situazione in cui un processo potrebbe non essere mai rimosso dalla coda di attesa in cui si trova.

Il deadlock si verifica quando sono verificate tutte e quattro le seguenti condizioni (sono quattro condizioni necessarie ma non sufficienti):

• Mutua esclusione: soltanto un processo alla volta può utilizzare una risorsa.
• Possesso e attesa: un processo in possesso di almeno una risorsa è in attesa di acquisire ulteriori risorse possedute da altri processi.
• Senza prelazione: una risorsa può essere rilasciata dal processo che la possiede solo volontariamente.
• Attesa circolare: esiste un insieme {P0, P1, ..., P0} di processi in attesa tale che P0 è in attesa di una risorsa posseduta da P1, P1 è in attesa di una risorsa posseduta da P2, ..., Pn–1 è in attesa di una risorsa posseduta da Pn, e P0 è in attesa di una risorsa posseduta da P0.

Per non finire in una situazione di stallo si possono adottare più approcci:

• Il primo approccio è quello della prevenzione. Per cui bisogna far si che almeno una delle condizioni sopra citate risulti falsa. Questo tuttavia comporta degli effetti collaterali perché i processi rischiano di non ricevere le risorse se non dopo molto tempo. Per cui per prevenire la situazione di stallo si può definire uno stato sicuro (quando è possibile eseguire i processi in una sequenza tale per cui, allocando ad ognuno di essi tutte le risorse che potenzialmente può richiedere, gli si permetta di terminare la propria esecuzione senza stalli). Se uno stato non è sicuro allora c’è la possibilità (non la certezza) di incombere in stalli.
• Permettere lo stallo, ma se si verifica riconoscerlo e ripristinare una situazione corretta.
• Ignorare il problema, presupponendo che lo stallo si verificherà molto raramente.

Algoritmo del banchiere

È un algoritmo utilizzato per evitare deadlock nell'allocazione delle risorse. In particolare questo algoritmo può indicare se un sistema si ritroverebbe in uno stato sicuro o meno nel caso assegnasse una risorsa ad uno dei processi richiedenti. 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 credito presso la banca (fino ad un certo limite individuale) e le risorse allocabili sono viste come il denaro. È 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).

Per cui entrando nello specifico, quando si presenta un nuovo processo, questo deve dichiarare il numero massimo di istanze di cui necessita per ogni tipo di risorsa. A questo punto bisogna controllare se lascia il sistema in uno stato sicuro, altrimenti deve attendere. Quando un processo ottiene le risorse le deve rilasciare in un tempo finito.

Per procedere con questo algoritmo, bisogna definire delle strutture dati: Siano n i processi e m i tipi di risorse.

• Available: vettore di lunghezza m. Se Available [ j ] = k, ci sono k istanze ancora disponibili della risorsa di tipo Rj.
• Max: matrice n x m. Se Max [ i, j ] = k, allora il processo Pi può richiedere al massimo k istanze della risorsa Rj.
• Allocation: matrice n x m. Se Allocation[ i, j ] = k allora a Pi sono attualmente allocate k istanze di Rj.
• 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.

Ovviamente si ha che Need [ i, j ] = Max[ i, j ] – Allocation [ i, j ].

Verifica dello stato sicuro (Check State)

1. Inizializzazione
   • Work = Available
   • Finish [ i ] = false per i = 1,2, ..., n.
2. Trovare un indice i tale che:
   • Finish [ i ] = false
   • Need[ i ] <= Work
3. Se non esiste un indice i che soddisfa le richieste del punto 2, passare al punto 4
   • Work = Work + Allocation[ i ]
   • Finish[ i ] = true
   • Vai al punto 2.
4. Se Finish[ i ] == true per ogni i
   • Il sistema è in uno stato sicuro
   • Altrimenti il sistema è in uno stato non sicuro.

Richiesta delle risorse

Sia Request[ i ] il vettore delle richieste per il processo Pi. Quindi se Request[ j ] = k allora il processo Pi vuole k istanze della risorsa di tipo Rj.

1. Se Request[ i ] <= Need[ i ] proseguo al punto 2, altrimenti scatta l’errore
2. Se Request[ i ] <= Available prosegui al punto 3, altrimenti Pi deve aspettare perché le risorse non sono disponibili
3. Simula di allocare le risorse richieste a Pi
   • Available = Available - Requesti
   • Allocationi = Allocationi + Requesti
   • Needi = Needi - Requesti
4. Check State
   • Se il sistema è in uno stato sicuro, le risorse vengono allocate a Pi.
   • Altrimenti se il sistema è in uno stato non sicuro, Pi deve aspettare, e viene ripristinata l’allocazione.

Attesa indefinita (o Starvation)

È il posticipo indefinito dell’assegnazione delle risorse richieste da un processo quando le risorse, sebbene disponibili per l’allocazione, non vengono mai assegnate a questo processo. Ci sono varie cause:

• Le decisioni sull’assegnazione delle risorse vengono prese localmente
• Le priorità dei processi
• La selezione casuale
• Non ci sono abbastanza risorse

Possibili rimedi:

• Ci deve essere un manager indipendente per ogni risorsa che gestisca in modo “fair” la risorsa.
• Non dovrebbero essere applicate le priorità in modo rigido, ad esempio aumentando la priorità di un processo al crescere del tempo di attesa (invecchiamento o aging).
• Evita selezioni casuali, concorrenza incontrollata, ecc.