:: Sistemi Operativi - Lezione del 20 Maggio 2008 ::
Torna alla pagina di Sistemi Operativi
Lezione 3 - Allocazione dei processi
In questo contesti (Sistemi Distribuiti) allocare processi vuol dire perseguire i seguenti scopi:
- bilanciare il carico tra le varie macchine
- sfruttare bene le risorse delle macchine
- mettere i processi sulle macchine adatte (requisiti HW o SW)
- avere tolleranza ai guasti
Quello che non si fa è di avere uno schedulatore generale per tutto il sistema distribuito: è praticamente impossibile, e si avrebbe un overhead gigantesco.
Invece, si schedula solo all'interno di una stessa macchina, e i processi vengono allocati qua e là a seconda delle esigenze.
Allocazione statica
Si decide su quale macchina allocare un processo all'avvio del processo stesso, in base a qualche parametro. Una volta decisa l'allocazione, il processo non si sposta più da quella macchina fino alla sua morte
L'allocazione statica può essere:
L'allocazione completa si usa quando stabilisco che un processo, tutte le volte che sarà eseguito, sarà sempre allocato sulla stessa macchina. Lo decido una volta per tutte.
Con l'allocazione incrementale, invece, la decisione sull'allocazione viene fatta ad ogni avvio del processo, e quindi è possibile che in 2 vite diverse il processo sia stato attivato su 2 macchine diverse.
Funzione obiettivo
Dicevamo prima che si decide su quale macchina allocare il processo in base a qualche parametro. Questi parametri entrano a far parte di una funzione obiettivo, la quale si prefigge di ottenere - ma no? - un certo obiettivo.
Quali obiettivi? Ce ne sono svariati, ad esempio sfruttare meglio i processori o mettere il processo dove la sua esecuzione sia meno costosa.
Per determinare l'obiettivo, la funzione deve rispettare però dei vincoli, che bene o male abbiamo già capito quali sono:
- dove si trovano i processi stessi
- dove si trovano le risorse che il processo usa
- incompatibilità eventuale con HW o SW
- incompatibilità eventuale con altri processi in esecuzione
Gli algoritmi di allocazione sono quelli che implementano una funzione obiettivo, tenendo presente i vincoli imposti.
Ci sono due tipi di algoritmi di allocazione:
Un algoritmo deterministico in genere ci dà la soluzione ottima. Quello euristico invece la approssima.
Quando uso l'uno e quando l'altro? Un algo deterministico in genere sarà più lungo e pesante, e quindi è meglio se lo si fa girare una volta sola quando prendo le decisioni sull'allocazione statica completa. Al contrario, se ad ogni nascita di processo devo decidere rapidamente dove allocarlo (allocazione incrementale) allora meglio usare un algo euristico, più veloce. Si corre se no il rischio di passare il tempo a decidere dove mettere i processi, invece che eseguirli.
Questi algoritmi possono essere centralizzati o distribuiti. Un algo centralizzato, si sa bene che cosa offre: un single point of failure. Un algo distribuito, a fronte di più complessità, funziona anche se qualche nodo va giù.
Infine, un'altra scelta che ho per questi algo è quella di decidere se eseguirli sulla macchina mittente, o su quella ricevente. E che cosa ciò voglia dire, NON LO SO!:)
Allocazione dinamica
Se ho un'allocazione incrementale, non avrò mai l'ottimo globale, perché l'inserimento di un nuovo proceso avviene a partire da una situazione preesistente, e quindi non si può fare più di tanto.
Se invece volessi raggiungere questo ottimo, dovrei poter essere in grado di spostare i processi dove è meglio: allocazione dinamica.
L'allocazione dinamica è di 2 tipi:
- totale = definisco l'allocazione considerando tutti i processi in giro per il sistema distribuito
- parziale = definisco l'allocazione considerando solo alcuni processi, ad esempio quelli presenti in una sottorete o quello che è
L'algoritmo di allocazione, dicevamo sopra, può essere eseguito più volte. Quando?
- periodicamente: ogni tot tempo lo faccio andare
- reattivamente: quando si verificano certe condizioni nel sistema, eseguo l'algoritmo (eg una macchina è troppo carica)
- volontariamente: è il processo stesso che chiede di essere riallocato altrove, e quindi il sistema provvede a spostare lui e se utile anche gli altri
Come sopra, c'è sempre la funzione obiettivo e i vincoli da rispettare. In aggiunta c'è un altro fattore da tenere in considerazione: il tempo di migrazione. Infatti, non è così indolore spostare un processo da una parte all'altra.
Lezione 4 - Agenti mobili
OCIO: argomento appena accennato e di scarsa rilevanza...
Obiettivo = innalzare il livello di astrazione. Il modello della computazione ad oggetti mi ha già permesso un certo tipo di astrazione, nel senso che incapsulo dati e metodi in un solo oggetto.
Ma ciò che rimane è che l'oggetto è passivo, ed è in attesa che qualcuno lo esegua.
Un agente mobile invece è un'entità autonoma, inserita in un ambiente, pro-attiva e cooperante. Pro-attiva vuol dire che ogni agente è dotato di vita propria. Sa muoversi da solo tra le varie macchine, sa scoprire servizi e risorse.
La progressione in astrazione è: oggetti => agenti => ageni mobili.
Ad ogni modo, occorre un supporto a livello di SO per fare tutte ste cose carine.
Lezione 5 - Coordinamento distribuito tra processi - Parte 1
Devo poter ordinare gli eventi, se voglio coordinare i processi, e per ordinare qualcosa mi occorre una nozione di tempo globale. Ma non posso averla: ogni macchina ha il suo orologio etc. => è impossibile che siano tutte sincronizzate. Vediamo qualche trucco per ovviare a ciò.
Relazione "accaduto prima"
Definiamo la relazione accaduto prima.
- Se A e B sono eventi di uno stesso processo, e A viene prima di B, allora scrivo A -> B
- Se A è l'evento della trasmissione di un messaggio da parte di un processo, e B è l'evento della ricezione dello stesso messaggio da parte di un altro processo, allora A -> B
- Se A -> B, e B -> C, allora A -> C (proprietà transitiva)
Due eventi che non sono in relazione li posso considerare concorrenti, perché non si influenzano. Se invece sono in relazione, vuol dire che possono influenzarsi a vicenda.
Bene, come faccio a realizzare queste relazioni?
Marca di tempo
Posso generare delle marche di tempo da parte di un server centralizzato, e distribuirle ai vari sistemi.
Ma la soluzione migliore è invece questa: ogni macchina mantiene un orologio o contatore privato. Quando riceve un messaggio da un'altra macchina, confronta il timestamp del messaggio in arrivo con il timestamp proprio. Se il timestamp in arrivo è minore del mio timestamp, tutto bene. Al contrario, se il timestamp in arrivo è maggiore del mio, non va bene, perché dicevamo sopra che gli eventi di comunicazione sono in relazione "accaduto prima". Quello che devo fare è prendere quel timestamp in arrivo, aggiungerci uno e a partir da lì ricominciare a contare.
Notiamo che in questo modo NON abbiamo un orologio globale. Abbiamo però una relazione prima - dopo condivisa da tutti.
Mutua esclusione in un sistema distribuito
Bisogna gestire il lock in un sistema distribuito. Ci sono tre vie:
- avere un singolo sistema centralizzato che dà il lock a tutti, e tutti i processi si mettono in coda da lui
- avere un qualche algoritmo distribuito
- uso di token
Nel caso numero 1, avere un solo sistema che fa tutto non è il massimo della vita, in quanto la macchina si intaserebbe alla svelta, e al solito se cade lei gli altri processi non vanno più avanti.
Nel caso numero 2, invece, si usano le marche di tempo. Se un processo P vuole entrare in una sezione critica, genera una marca di tempo e la invia a tutti gli altri.
Gli altri processi (chiamiamolo processo Q per comodità) reagiscono in modo diverso a seconda delle condizioni:
- se Q è già nella sua sezione critica, non risponde a P
- se non intende entrare, risponde subito
- se intende entrare, ma non l'ha ancora fatto, confronta il suo timestamp con quello inviato da P
- se il timestamp di Q è maggiore di quello di Q, deve attendere: risponde quindi a P
- se invece ha timestamp minore, non risponde, perché è lui ad avere la precedenza su P
Anche qui non importa avere un tempo unico per tutti, è sufficiente avere un tempo relativo tra le varie macchine. Questo sistema è tollerante ai guasti, e garantisce l'assenza di starvation e di deadlock.
Per quanto riguarda il passaggio di token, si mettono tutti i processi in un anello logico, e il token gira per l'anello. Il token rappresenta l'autorizzazione a usare una risorsa. Se ho il token, uso la risorsa. Quando ho finito, lascio il token al prossimo processo nell'anello.
Occorre però un sistema per ricreare il token in caso esso si perda nei meandri della rete.
Lezione 5 - Coordinamento parte 2
Adesso vediamo come garantire l'atomicità alle operazioni, usando il concetto di transazione di pierangelica memoria.
L'idea di fondo è dividere la transazione in sottotransazioni, ed usare il protocollo di commit a 2 fasi.
Questo protocollo ha bisogno di un commit globale tra tutte le macchine che sono interessate dalla transazione, ovvero che stanno realizzando almeno una delle sottotransazioni in cui la transazione viene divisa. Devono essere tutte d'accordo, se ce n'è una che fa abort, allora anche tutte le altre devono farlo.
L'idea di dividere la transazione in sottotransazioni dipende dalla volontà di sfruttare per quanto più possibile il parallelismo fisico del nostro sistema distribuito.
Questa situazione, però, genera concorrenza.
Concorrenza
Per gestire la concorrenza, ho diverse strade.
Posso poter decidere di tenere i dati replicati: avendo più copie degli stessi dati, il problema cade alla radice. Ne nasce però un'altro, ovvero quello di mantenere la sincronia tra le diverse copie dei dati.
Posso avere un coordinatore centralizzato, senza i dati replicati. I processi chiedono tutto a lui, e ci pensa a tutto lui. Abbiamo i soliti problemi di performance e di affidabilità.
Posso avere coordinatori multipli, senza dati replicati. Ogni macchina gestisce i lock per le proprie risorse. Nascono difficoltà quando si deve gestire uno stallo, perché occorre sentire tutti i coordinatori. Ma è comunque meglio per prestazioni e tolleranza ai guasti.
Posso avere un coordinatore del lock a maggioranza. Replico tutti i dati, e ogni replica si gestisce i suoi lock. I dati vanno poi però sincronizzati per evitare discrepanze tra le varie copie.
Inoltre, un processo deve ricordarsi di fare richieste di lock a tutte le copie:
- se ottengo la metà più uno di risposte positive, allora la risorsa è mia: ho il lock globale
- se no, attendo
Si vede subito che è abbastanza complicato da gestire.
C'è infine il protocollo polarizzato, che usa ancora i dati replicati, e usa la stessa tecnica del lock a maggioranza. La differenza è che ogni macchina gestisce per conto suo i lock condivisi, mentre si appella ancora alla maggioranza per quanto riguarda i lock esclusivi. Rispetto al lock a maggioranza, è un po' meno pesante.
Se il coordinatore va giù?
Occorre sostituirlo, dato che ce n'è uno centralizzato. A questo scopo, ho due algoritmi disponibili: l'algoritmo del bullo e l'algoritmo dell'anello.
Algoritmo del bullo: quando un processo P si accorge che il coordinatore è morto, allora manda 1 messaggio di inizio elezione a tutti i processi che hanno priorità più alta della sua. Se entro 1 certo timeout non riceve risposta, assume di essere diventato lui il coordinatore, e lo comunica a tutti. Se invece ottiene risposta, attende, in quanto le risposte arriveranno solo da processi con priorità più alta e quindi più "importanti" di lui. Anche qui, se ha ricevuto risposte e si mette in attesa, ma non arriva il messaggio di avvenuta elezione, ricomincia da capo.
OCIO: ROBA MISTERIOSA, CONTROLLARE ALTROVE! - Algoritmo dell'anello: si crea una lista di processi attivi, all'inizio vuota. P attiva l'elezione inviando la lista in giro per l'anello logico dei processi. Se un processo si vede arrivare la lista vuota, si dichiara disponibile e si mette lui stesso nella lista, assiema al processo da cui l'ha ricevuta, e la forwarda al prossimo elemento dell'anello.
Lezione 6 - Deadlock in ambiente distribuito
Qui riprendiamo tutti gli elementi già visti a proposito del deadlock, e li trasportiamo in un ambiente distribuito.
Prevenzione dello stallo
Ecco le mie alternative:
- estendere l'ordinamento globale a tutte le risorse del sistema. L'overhead è basso.
- estendere l'algoritmo del banchiere: molto costoso
- timestamp con rilascio della risorsa: wait-die e wound-wait = ???
Rilevamento dello stallo
Uso un grafo di allocazione delle risorse, ma distribuito, nel senso che riguarda tutte le macchine del mio sistema distribuito.
Ogni macchinina deve avere il proprio grafetto delle risorsine, ma occorre che da qualche parte ci sia l'unione di tutti sti grafetti, perché è possibile che ci siano lock visibili solo dall'unione dei grafetti e non dal singolo grafetto.
C'è però un'altra cosuccia da notare: per realizzare l'unione, si mandano messaggini a chi di dovere. Ma è possibile che nel tempo intercorso tra l'invio del messaggio e la ricostruzione dell'unione dei grafetti, la situazione su di una macchina sia già cambiata in peggio.
Questo vuol dire che l'assenza di cicli nel grafone delle risorsone globale non vuol dire che non ci sono dl in quel momento, bensì non ce n'erano all'invio dei messaggi. Al contrario, se c'è un ciclio nel grafone, allora lo stallo è sicuro.
Nasce dunque la necessità di tenere aggiornato il grafone. Quando una macchina dovrebbe inviare gli aggiornamento che ha fatto in locale al proprio grafetto?
- ad ogni modifica
- oppure dopo un certo numero di cambiamenti al grafetto
Finora abbiamo però supposto che ci fosse una macchina sola che si occupasse di crearsi il grafone a partire dai grafetti. Ma si può avere un algoritmo distribuito.
Ogni macchina si costruisce il proprio grafetto. In presenza di una richesta ad una macchina esterna, nel proprio grafo mette il nodo Pex, ad esempio, ad indicare processo esterno.
Se non ci sono cicli nel mio grafetto, ok. Se invece ci sono cicli, io sono in stallo. Se c'è un ciclo che coinvolge il nodo Pex, allora devo andare a verificare se veramente, all'esterno, c'è un ciclo.
In altre parole, un ciclo che coinvolge il nodo Pex va verificato, perché non è detto che globalmento esso sia un ciclo.
Quindi, comunico con le altre macchine e poi si vede se il ciclo c'è o mica.
Gestione dello stallo
Se trovo un ciclo, devo trovare una vittima e costringerla a fare rollback. Ma non solo: tutti i processi che interagivano con lei dovranno rollbackare.
Il problema è che, a causa dei tempi di trasmissione, si possano rilevare dei falsi cicli, ovveri dei cicli causati da rappresentazioni datate della situazione delle varie macchine. Avrei quindi dei dl falsi, e farei rollbackare inutilmente una vittima.
A questo scopo, occorre avere un timestamp univoco per tutto il sistema distribuito (e che vuol dire?).
Lezione 7 - Comunicazione tra processi in rete
Scambio di messaggi
Trovo un buffer da qualche parte, e lo uso per scambiare i messaggi tra i processi. Le funzioni per interagire con sto buffer saranno implementate tramite RPC.
Da qualche parte vuol dire su una qualsiasi macchina coinvolta, o anche una terza macchina.
Mailbox
Funziona esattamente come per un sistema singolo. Anche qui la mailbox è remota, locale etc.
File
Idem come sopra, con il lock distribuito
Socket
bla bla bla
Insomma, posso fare tutto quello che facevo con i processi su di una singola macchina, ad esclusione della memoria condivisa e delle pipe, per motivi ovvi.
Filesystem distribuiti
Lezione 1 - Struttura e funzioni
Devo accedere ai vari FS nelle varie macchine in modo TRASPARENTEEEEEEEEEEE ed efficiente. Ho due approcci:
- Network File System = NFS (che è anche il nome di un filesytem reale)
- Distributed File System = DFS
NFS = la collezione dei FS delle macchine locali. Monto localmente i FS remoti.
DFS = integrazione di tutti i FS in un unico FS globale: tutte le macchine vedono lo stesso FS
Nome del file:
NFS = il nome è preceduto dall'indicatore della macchina. Quando monto il FS remoto localmente, il percorso per prendere quel file dipenda da DOVE è stato montato.
DFS = il nome è unico per tutto il sistema. Non il nome stesso: intendo dire che c'è un unico percorso, in tutto il sistema, che porta a quel file.
Se la locazione del file è visibile all'utente è NFS. Se è TRASPARENTTTEEE è DFS.
La cosa carina del DFS è che posso spostare fisicamente un file da una macchina all'altra, ma il SO deve fare in modo che la sua posizione logica sia sempre quella. Il SO potrebbe anche pensare di fare copie locali di un file fisicamente remoto, per velocizzare le cose, a patto di sincronizzarne poi le modifiche.
È inoltre possibile migrare il file: il percorso logico è sempre lo stesso, ma fisicamente l'ho spostato dove mi fa più comodo.
Accesso al file
NFS: posso avere:
- chiamate implementate come RPC
- copia del file in locale
DFS: le chiamate locali vengono trasformate in eventuali chiamate remote: il SO pensa a tutto lui, l'utente non si deve accorgere di niente. Ovviamente è un compito pesante per il SO.
Posso anche decidere di avere una cache da qualche parte. Ho diverse possibilità:
- la metto sul server dove il file è presente
- la metto sulla macchina che sta usando il file
- la metto in una macchina accessibile da una sottorete che fa uso frequente di quel file
E quando aggiorno la cache? Le politiche sono più o meno sempre quelle:
- write-through: ogni volta che scrivo in cache, scrivo sincronicamente anche nel file
- delayed-write: scrivo dopo, quando mi fa più comodo
- write-on-close: scrivo quando chiudo il file
La verifica della coerenza tra cache e dati reali può essere iniziata sia dal server che dal client.
Stato del file server
Il concetto di stato del file server rappresenta tutte le informazioni che caratteizzano lo stato di uso di 1 file.
Posso avere un file server senza stato: ogni richiesta ricevuta viene soddisfatta in modo indipendente. Il problema è che il server deve controllare ogni volta dove si trova il file, eventuali condivisioni e così via.
E allora, è meglio anche per i FS distribuiti usare la semantica che già abbiamo visto per i FS locali: usare la open() e la close(). In questo modo, un processo ottiene una volta per tutte le informazioni che gli servono per accedere a quel dannato file, e lo può fare rapidamente senza stare lì ad interpellare il file server per ogni scrittura di byte.
Ecco quindi che i file server con stato implementano la chiamata open() e un identificatore di connessione, per offrire a noialtri più efficienza.
Replica dei file
La replica deve essere T-R-A-S-P-A-R-E-N-T-E.
Si replicano i files per maggiore efficienza, e AL SOLITO devo stare attento a sincronizzare i dati.
E con questo abbiamo FINITO!!!!!!!!!!
Torna alla pagina di Sistemi Operativi
