:: 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:
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.
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.
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:
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!:)
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:
L'algoritmo di allocazione, dicevamo sopra, può essere eseguito più volte. Quando?
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ò.
Definiamo la relazione accaduto prima.
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?
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.
Bisogna gestire il lock in un sistema distribuito. Ci sono tre vie:
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:
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.
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:
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.
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.
Ecco le mie alternative:
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?
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.
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
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.
Funziona esattamente come per un sistema singolo. Anche qui la mailbox è remota, locale etc.
Idem come sopra, con il lock distribuito
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:
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
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.
NFS: posso avere:
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à:
E quando aggiorno la cache? Le politiche sono più o meno sempre quelle:
La verifica della coerenza tra cache e dati reali può essere iniziata sia dal server che dal client.
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.
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!!!!!!!!!!