Tassonomia di Flynn
 Tassonomia del software
       Topologie di connessione LAN
 Generalita' sui Sistemi Distribuiti (LAN)
Sistemi di indirizzamento
Primitive di comunicazione: caratteristiche
Implementazione dei server nei sistemi distribuiti

E' in realta' un argomento che include tipi anche estremamente diversi di architetture hardware e di conseguenza software, anche a causa del continuo sviluppo del settore. Una delle prime tassonomie proposte e' quella di Flynn, oggi ancora utilizzata:

• SISD Single Instruction stream Single Data (Architettura di Von Neuman)
• SIMD Single Instruction stream Multiple Data (Connection Machine, Nasa MPP...)
• MISD Multiple Instruction stream Single Data (nessuna)
• MIMD Multiple Instruction stream Multiple Data (Cray X/MP, ipercubo...)

Tassonomia delle macchine MIMD in base alla velocita' di trasmissione:

A. Multiprocessori a bus

Ogni accesso alla memoria condivisa avviene tramite bus, quindi con accesso serializzato.
Ogni processore mantiene allora una copia della memoria comune in una cache privata.
Problema: mancanza di coerenza.
Possibile soluzione: write-to-cache:

1. operazioni di letture fatte localmente
2. le scritture sono eseguite sulla memoria comune
3. tutte le CPU controllano il bus. Quando passa un dato in write questo viene ricopiato nelle memorie cache mantenendole sincronizzate (snoopy cache).

Da 32 a 64 CPU sullo stesso bus, che e' parallelo per dati, indirizzi e segnali di controllo. Accesso diretto da CPU a memoria (con 1 hop) ma gli accessi vanno serializzati (il tempo necessario dipende dal carico).

B. Multiprocessori a commutazione
 

I sistemi crossbar consentono il collegamento di un numero maggiore di CPU (>1000).
Se 2 CPU vogliono accedere alla stessa memoria, 1 viene sospesa.
Per n CPU occorrono O(n**2) cross point.
Elevato numero di loop, e costo hardware alto (esistono anche diverse topologie di connessione).

C. Multicalcolatore a bus

Minore volume di dati su bus seriale (trasmissione di messaggi). Da 10 a 100 Mbps.

D. Multicalcolatori a commutazione

Il numero di hop per la comunicazione e' proporzionale alla radice quadrata del numero di CPU.

Ipercubo a 4 dimensioni (4 link per processore)

Cubo a n dimensioni: ogni nodo ha n connessioni con altre CPU. Il numero di hop e' proporzionale a log2(n). Esistono ipercubi fina 16384 CPU.

Sistemi Operativi per CPU multiple:

• Accoppiamento lasco: consente l'evoluzione di processi in modo indipendente con interazioni limitate.
• Accoppiamento stretto: esecuizione di un accoppiamento stretto: esecuzione di un unico programma distribuito (o parallelo).

Poche interazioni a basse velocita'. Esempi:

• login remoto (rlogin, telnet)
• Trasferimento file (rpc, ftp)

Ogni workstation ha un suo sistema operativo, con programmi che gestiscono lo comunicazione.

Caso piu' complesso:

• S.O. per ogni W.S.
• S.O. di rete che consente la visione di un file system

Primo esempio: ARPANET (1968),
Link tipici: lenee telefoniche, canali satellitari.
Comunicazioni mantenute con special purpose computer: Paket Switching Exchange(PSEs) e Interface Message Processor (IMPs).
store and forward

I PSE sono responsabili del routing dei messaggi. I tempi di operazione sono lunghi: 2 <= Frequenza Trasmissione <= 100 kbps.
In piu' occorre aggiunhgere il tempo per decidere il routing (almeno millisecondi). U messaggio corto puo' richiedere circa 100/200 msec. per la trasmissione, mentre per quelli su satellite si arriva a 500 msec.
Uso:  electronic mail, collegamento terminali remoti per esecuzione di job batch.

A partire dal 1970. Le W.S. sono situate a pochi Km. di distanza (al massimo). I messaggi sono comunicati direttamente, senza PSE. Tutti gli host sono responsabili del collegamento. Componenti hardware:

• Workstation
• File server
• Cavi di collegamento
• Hub (concentratore)
• NIC (Network Interface Card)

Il File Server e' un computer ad alta velocita' e dotato di grande spazio disco che funziona come un file repository centrale (con funzioni di security). Ogni W.S. ha una NIC (anche il File Server) per la connessione in rete. Lo HUB consente il collegamento delle molte W.S. con il F.S.

Componenti software:

• Nework Operating System. Software che risiede sul F.S. Controlla e gestisce l'accesso multiuser.
• W.S. Operating System
• Network Shell. Creato dal Network O.S. ma allocato su ogni W.S. Determina se una richiesta al S.O. e' locale o di network.

Modo di programmazione: Distributed Processing.

LAN omogenee:

• AFP  Apple Talk File Protocol
• NFS  Sun Microsystem
• Unix-based Network File System
• DecNet  Digital Eq.

LAN eterogenee:

• Novell   Netware Operating System
• Microsoft LAN Manager

Connessione di Network

• Internet

Per ogni topologia di connessione bisogna considerare:

• il costo di base per la costruzione dei link (cavi, hub, bus...)
• il costo in tempo per la comunicazione
• la reliability della comunicazione (capacita' di autonomia relativamente a possibili guasti).

Consideriamo 3 topologie point-to-point (una W.S. e' connessa ad un altra W.S. con un cavo dedicato): tree, star e ring, e una topologia a bus: branching bus (la struttura a bus puo' anche essere a ring).

Costo della comunicazione

• Tree: basso costo (logaritmico sul numero dei nodi)
• Star: molto basso (2 hop per comunicazione, ma possibilita' di bottleneck)
• Ring: medio-lungo
• Bus: basso se non c'e' molto traffico, altrimenti e' un bottleneck.

Nelle LAN gli utenti sanno che stanno lavorando su un sistema distribuito. Su multicalcolatori si pouo' istallare un S.O. distribuito che fa in modo di dare l'impressione di usare un singolo calcolatore.

• Uguali meccanismi di comunicazione su tutte le macchine
• Meccanismi di protezione d'accesso globale
• Gestione dei processi unica.

Unico insieme di chiamate di sistema che possono operare sia localmente che su altri nodi. Lo scheduler e' unico per tutte le CPU, mentre altre funzionalita' (pafinazione e swapping) rimangono gestite localmente. Ancora in fase di prototipi.
 
 

Esempio: sistemi Encore e Sequent. Usano Unix timesharing con piu' di 1 CPU. caratteristica: unica coda di eseguibili.

Evoluzione futura per i S.O. distribuiti

• Possibilita' di usare connessioni veloci anche in modelli tipo LAN, considerati ad architettura lasca (es. uso di cabvi a fibbre ottiche, nuovi protocolli di comunicazione ATM...)
• Utilizzo di librerie di comunicazione (scambio di messaggi, creazione di processi remoti...) per scrivere programmi paralleli che girano su sistemi distribuiti eterogenei (PVM, MPI,...)
• Quindi sistemi distribuiti multicomputer possono essere usati come macchine parallele ad accoppiamento stretto.

Nel seguito ci riferiremo ad applicazioni di tipo LAN.

• Condivisione delle risorse, senza necessita' di replicarle su tutti gli utenti (printer, dischi, data base, array processor).
• Guadagno in tempo dovuto alla possibilita' di esecuzione parallela, o di usare un host meno carico o con particolari caratteristiche (floating point...)
• Reliability: se il sistema e' ridondante si puo' continuare a lavorare (ridondanza hardware, software, dati). Occorre in questo caso rilevare il fallimento di un nodo e trasferirne le funzioni ad un altro. Infine si reintegra il nodo, dopo averlo aggiustato.
• Possibilita' di comunicazione fra utenti diversi: ìì, ad esempio per posta elettronica. Funziona come un ufficio postale, con un mailbox in cui si mandano mail con un indirizzo.

Caratteristiche dei sistemi distribuiti
Nell'ANSI Reference Manual (1987) si parla di  separazione e trasparenza come di caratteristiche importanti dei sistemi deistribuiti. Purtoppo sono concetti in constrasto fra loro.

• Separazione: si richiede comunicazione e integrazione. Consente:
• esecuzione di programmi e processi in parallelo
• recovery dai guasti senza distruzione del sistema
• crescita o contrazione incrementale del sistema.
• Trasparenza: occultamento della separazione. Il sistema e' percepito come un tutt'unico. Ci sono varie forme di trasparenza:
• di accesso ai file remoti come se fossero locali
• di locazione degli oggetti che possono essere usati senza sapere dove risiedono effettivamente
• di replicazione, per cui copie multiple di files, dati o processi sono replicati per aumentare la reliability o la performance, senza diretta conoscenza da parte dell'utente
• del fallimento, per nascondere possibili guasti
• di migrazione, per consentire movimenti degli oggetti, senza l'esplicito controllo dell'utente.

Ne puo' guadagnare:

• la  performance: il sistema puo' riconfigurarsi automaticamente
• lo scaling: sono possibili espansioni dell'architettura senza modifiche ai sistemi e agli algoritmi utente.

Nota: influenza sull'architettura del kernel:

• kernel convenzionale o monolitico: contiene incapsulati servizi di scheduler, creazione dei processi, funzioni di I/O. Le strutture dati e le Tavole del kernel devono essere accessibili a tutti i processi che implementano i servizi.
• kernel distribuito: deve dare la possibilita' di modificare o estendere i servizi. Modello client-server con scambio di messaggi. Spazi di indirizzamento separati, accesso controllato a dati condivisi.

Standard e protocolli per il Network
Lo scopo del network e' incorporare hardware e software di diversi componenti. bisogna accordarsi per seguire protocolli di comunicazione (cioe' regole di comunicazione, principalmente per la trasmissione di dati, compreso il loro formato).

Comunicazioni

• Design strategies: quali sono le relazioni fra la comunicazione e le applicazioni?
• Routing strategies: su quali link deve essere inoltrato il messaggio?
• Connection strategies: com'e' inviato il messaggio?
• Contention: come si risolvono i conflitti d'accesso su bus?
• Security: come si fa a mantenere segreto un messaggio?

Standard Organizations

Esistono diverse organizzazioni internazionali per la definizione di protocolli standard.

• CCITT (Consultative Committee on International Telegraphy and Telephony). Organizzazioni con sede a Ginevra che ha sviluppato standard per diversi aspetti della trasmissione e della comunicazione di dati telefonica. Gli standard piu' noti sono X.25, X.400, X.500 e X.29. Questi standard hanno maggiore impatto sulle WAN che sulle LAN.
• ISO (International Standard Organization). Sede in Ginevra. Ha sviluppato un modello di riferimento per computer networking noto come OSI (Open Systems Interconnect). Molti degli standard attualmente esistenti sono basati su di esso.
• IEEE (Institute of Electrical and Electronic Engineers). Organizzazione degli U.S. per standard su LAN che ha avuto molto seguito per le LAN. Parte importante e' contenuta nel Progetto 802.

Il lavoro dell'ISO e del CCITT fornisce una base per l'evoluzione del networking standard, in particolare da quando anche il CCITT ha adottato il modello ISO/OSI. IEEE Project 802 e' piu' specializzato ed e' responsabile di molti degli standard e architetture esistenti oggi.

Il modello ISO/OSI e' discusso nella sezione ISO/OSI

Sistemi di indirizzamento (Indice)

Il client, per spedire un messaggio al server, ha bisogno di conoscerne l'indirizzo. Abbiamo diversi metodi:

1. Indirizzamento di tipo Internet. Formato da:
   Identificatore di rete + identificatore dell'host,
   Identificatore locale (all'interno dell'host) scelto in modo casuale.
   Problemi:
• mancanza di trasparenza,
• non fault tolerant (se l'host fallisce, si potrebbe voler attivare il servizio su di un altro host: problema della migrazione).
2. Identificatore unico su tutta la rete, indipendente dall'host.
   Problema: occorre una componente centralizzata che distribuisce gli identificatori, che devono essere unici sulla rete. Questo potrebbe costituire un bottleneck, che e' sempre meglio evitare.
   Si puo' allora consentire ai server di scegliersi in modo casuale (in un ampio rango) il proprio identificatore. In questo caso si restringe il rischio di omonimia.
   Nasce pero' un'altro problema: come si fa a sapere su quale macchina si trova veramente il server, in modo da mandare fisicamente il messaggio? Soluzioni possibili:
1. Se esiste la possibilita' di mandare facilmente un messaggio in broadcast, si manda a tutti gli host un pacchetto di localizzazione per un certo indirizzo simbolico. Se il server legge il proprio indirizzo simbolico, risponde inviando l'indirizzo fisico. Questo indirizzo e' memorizzato dal kernel del cliente per evitare il broadcast la volta successiva in cui ce n'e' necessita' (soluzione distribuita). Vedere indirizzamento ethernet.
2. Si utilizza un name server che opera su una macchina particolare e nota, che risponde alle richieste di localizzazionew inviate dai client (soluzione centralizzata. Vedere DNS.
3. Uso di hardware specializzato. Nei chip di interfaccia con la rete fisica si possono memorizzare gli identificatori dei processi operanti su quell'host. I frame usano direttamente l'identificatore del processo, che viene riconosciuto piu' velocemente.

Caratteristiche delle primitive di comunicazione (Indice)

1. Primitive bloccanti e non bloccanti

Attenzione: si possono trovare terminologie diverse.

Funzione send

1. Operazioni bloccanti e non bloccanti. Vediamo cosa succede ad un processo che invia un messaggio. In un caso rimane bloccato finche' il kernel non ha instradato il messaggio sulla rete fisica.



Si tratta quindi di una primitiva bloccante (questo non vuol dire che il client rimane bloccato finche' il server ha ricevuto il messaggio, ma semplicemente finche' il kernel l'ha instradato).
Altrimenti si puo' avere una primitiva non bloccante:



L'attesa del processo client e' inferiore, ma c'e' un problema: come fa il client, se vuole fare un'altra spedizione, a sapere che il buffer di send e' vuoto, e che quindi puo' soprascriverlo senza perdere il messaggio precedente, non ancora completamente inviato?

1. buffer multipli: il kernel mette a disposizione piu' di un buffer. Questo implica che nella zona A il kernel ricopia il messaggio in un altro suo buffer, per liberare subito quello di partenza.
2. interruzione di fine spedizione: e' un segnale generato dal kernel quando il buffer si libera, e puo' quindi essere riutilizzato dal client per un'altra spedizione. Non e' necessario il ricopiamento, ma e' molto scomodo per il client (difficile programmazione).

Nota: la frase "spedizione del messaggio" significa anche ricopiare il buffer nell'area delle spedizione fisica.

Funzione receive

Anche in questo caso abbiamo funzioni di vario tipo:

1. Operazione non bloccante: il server avverte il kernel che e' in attesa di un messaggio su di un certo buffer. Poi ricevere una interruzione quando arriva il messaggio, come nel caso della send.
2. Receive condizionale o probe: il server controlla se c'e' un messaggio da ricevere (polling) altrimenti si va avanti. Si causa un rallemento, dovuto alla forma di busy waiting.

Sia sulla send che sulla receive bloccanti si puo' mettere un time-out per evitare attese eterne.

2. Primitive di receive bufferizzate e non

Se una receive e' chiamata prima dell'arrivo di un messaggio, si puo' scegliere se bloccare o no il processo ricevente. Problema: cosa succede se un messaggio arriva e il ricevente non ha richiesto nessuna receive?

1. Si scarta il messaggio,
2. Si memorizza, almeno per un po' di tempo. Si definisce una mailbox in cui il ricevente ripesca il messaggio quando lo vuole ricevere. Anche qui abbiamo un problema: quanto va grande la mailbox?
3. Si sospende il mittente finche' il receiver non ha effettivamente ricevuto il messaggio (e' richiesto un ack).

3. Primitive affidabili e non

Come fa il mittente a sapere che il messaggio che ha inviato e' arrivato a destinazione?

1. Si ignora il problema. Chi invia un messaggio deve anche effettuare i controlli per conto suo. Eventualmente si mette un time-out.
2. Si richiede un messaggio di acknowledge.
3. Se la comunicazione e' del tipo client-server, il client puo' prendere come ack del server la risposta che egli riinvia.

Per avere una buona efficienza, occorre eviatare gli overhead. Ad esempio, nelle operazioni di send e receive bufferizzate e' necessario effettuare diverse volte la ricopiatura del messaggio. D'altra parte sipossono avere difficolta' con lo swapping se si limita il numero delle copie. Bisogna trovare un giusto compremesso.

C'e' un overhead peraltro anche solo per preparare un messaggio: invocazione del kernel, salvataggio dello stato del processo corrente, identificazione del processo destinatario, update di tavole, controllo dei permessi di accesso...

Le funzionalita' del kernel possono essere viste come servizi forniti da server. Questo consente di ottenere kernel piu' piccoli ed efficienti.

Struttura di un server

La piu' semplice e' un thread di controllo sequenziale, come gia' visto in MINIX:

   main loop:    while TRUE do begin
                    GetRequest
                    CarryOutRequest
                    SendReply
                 end;

Problema: Quando esegue CarryOutRequest non si possono accettare altre richieste. Il file server, ad esempio, lo potrebbe, mentre aspetta che sia eseguita una lettura da disco.

Prima soluzione: se il server deve passare in stato blocked, copia invece il suo stato su una tavola e torna al main loop per vedere se ci sono altre richieste da parte di altri processi, o se e' stata sbloccata una situazione precedentemente blocked. In pratica, effettua un auto schedulazione. Questa architettura e' molto complessa e poco pratica.

Seconda soluzione : si attiva un cluster di task. Il server diventa una collezione di task (in questo caso si tratta di thread) che condividono il codice e i dati globali, pur avendo anche un'area dati e stack locale.

Organizzazione:

Il dispatcher accetta ed esgue lui stesso la richiesta solo se e' non blocking (es. lettura di un file presente nella cache). Se e' di tipo blocking (esempio accesso al disco) la passa ad un suo worker. Quando questo si blocca, il dispatcher o un altro worker puo' essere schedulato. Si utilizza cioe' la schedulazione gia' implementata nel Sistema Operativo.

Nel caso in figura 9.13, il numero di worker e' fissato a priori, ma possono anche essere attivati dinamicamente in caso di bisogno. Tutti inizialmente sono in attesa di ricevere una richiesta di servizio. Il kernel sceglie in modo random quale worker attivare.

Poiche' l'area globale e' condivisa, sono necessari meccanismi di lock e unlock per accedere ai dati condivisi. Si puo' in alternativa avvertire lo scheduler di non fare context-switching finche' il processo non diventa blocked.

Il numero di worker potrebbe anche non essere prefissato. Quando e' necessario il dispatcher attiva un thread per il servizio. In questo modo si risparmia spazio di memoria, e numero di processi nella Proc Table, ma e' necessario un tempo un po' piu' lungo per attivare il thread (vedere funzione Unix accept).

Server tipici di un S.O. distribuito (e non)

• File Server
• Printer Server
• Terminal Server
• Process server: attiva nuovi processi. Unix ha la funzione fork. In altri sistemi si puo' richiedere uno spazio di memoria e metterci dentro dati, codice, stack ecc. e poi attivare un processo che esegue su quell'immagine., sia localmente che in remoto (ad esempio il S.O. Amoeba).
• Time Server. Si puo' chiedere che tempo e' localmente o su di una macchina remota. Il time server puo' anche mantenere un tempo sincrono, a meno di un errore di grandezza inferiore ad un valore piccolo ma diverso da zero.
• Boot Server. Fa partire il sistema da power-on o quando c'e' un problema interno grave non risolvibile. Richiede un meccanismo hardware per l'inizializzazione (interrupt reset). Esegue ogni tanto un polling sui server per vedere se sono ancora vivi.
• Gateway server. Converte messaggi da un protocollo ad un altro (o cambia semplicemente gli indirizzi) per passare da un protocollo della rete locale al protocollo della rete esterna, e viceversa.