Sistemi Operativi

SISTEMI OPERATIVI – I parte

1 di G.Davanzo, A.Matossich, D.Prade

ARCHITETTURA DI UN SISTEMA OPERATIVO: Sistema Operativo: programma che gestisce tutte le risorse di un calcolatore. File system: è una risorsa logica che gestisce i files. Processo: programma in esecuzione. Scheduling: il S.O. deve gestire la CPU e la memoria. S.O. in tempo reale: deve dare una risposta entro un certo periodo detto DEADLINE. S.O. distribuito: è un S.O. di rete (oggetti e risorse sono distribuiti sulla rete). Un sistema operativo va analizzato in base ai diversi punti di vista: utente (vista come una macchina astratta), hardware (insieme di programmi per gestire le risorse hardware), progettista (sistema complesso che deve essere assemblato), applicativo. Strutture interne: La storia dei S.O. inizia nel 1960. La prima impostazione era l’HW controllato dal SW, diviso in livelli. IL nucleo si occupava della gestione dei processi (interrupt). Il livello successivo si occupa della schedulazione del processo, un altro della gestione della memoria, uno della gestione I/O, uno la shell. Alla fine, lo strato più esterno è l’utente. I primi S.O. furono ATLAS e MULTICS, in Inghilterra, e già includevano la memoria virtuale. Nel ’65 fu creato il THE, per analizzare i sistemi concorrenti. 1978: VMS, è il più recente S.O. realizzato a strati, molto sicuro. 1980: MSDOS, è un salto all’indietro perché è molto più primitivo. In realtà il DOS è a struttura monolitica: ogni procedura può interloquire direttamente con tutte le altre, non ha struttura interna  se l’applicazione non ha bugs è più veloce. Però il sistema a strati è più sicuro, ma c’è molto lavoro a carico suo (OVERHEAD, sovraccarico). Poiché dall’85 in poi si è dovuto ridurre l’overhead si optò per i sistemi monolitici. Il migliore all’epoca era UNIX, nato nel ’72  nell’85 si passa da VMS a UNIX. All’inizio UNIX era pensato per segretarie, in particolare per word processor. 1966: la IBM realizza l’OS, creato per essere usato con vari tipi di applicazioni (anche real time, batch, time sharing…). L’OS aveva un nucleo enorme creato in ASM  ogni volta che si risolvevano degli errori ne apparivano altri  si capì che il nucleo deve essere molto ridotto. In seguito un gruppo di programmatori IBM cambiò strada: VM/360: creando un nucleo molto ristretto si possono Macchina Virtuale avere molti utenti che condividono lo stesso HW in timesharing, ognuno dei quali monta il suo S.O.. Un S.O. che funziona in questo modo è detto CLIENT-SERVER. Nucleo HW Unix R4 (descritto da Bach): IPC = Inter Process Communication Utente Interfaccia Gestore FS Gestione processi Buffer Schedulazione Memoria Cache IPC HW Tutti i S.O. sono concorrenti: le applicazioni girano in concorrenza. Vantaggi: utilizzo, efficienza S.O., efficienza applicazioni (se la CPU è libera può essere usata da altre applicazioni). Svantaggi: mutua esclusione… Time Sharing: è un interrupt hardware che svolge la funzione di CONTEXT-SWITCHING, cambiando tra un processo all’altro. (Quanto di Time Sharing ≈ 10/20 ms). Round Robin: se l’ordine di esecuzione della coda dei processi è di tipo FIFO, cioè viene eseguito prima il processo arrivato per primo. Process Control Block (PCB): È una struttura che contiene program-counter, registri CPU, informazioni sulle allocazioni di memoria, info per la schedulazione, info che descrivono le operazioni di I/O (quali files sono aperti), info sui tempi impiegati dai processi, statistiche, variabili d’ambiente… Ogni processo contiene un PCB. IPC: create dal S.O., molto complesse. THREAD: sequenze di esecuzione distinte all’interno dello stesso processo.

2 SISTEMI OPERATIVI – I parte Kernel: Una definizione esatta dipende dal tipo di S.O. In alcuni S.O. il nucleo svolge molte funzioni di gestione dei componenti del S.O. In altri il nucleo e’ molto leggero e svolge solo alcuni servizi, come il passaggio di messaggi o la comunicazione. Sicuramente in tutti i S.O. il nucleo gestisce gli interrupt.

Sistema che gestisce applicazioni concorrenti: Il processo viene creato (FORK) ed istanziato in memoria in una coda d’attesaviene schedulato oppure viene posto su swapdalla memoria viene posto in stato di RUN (di sistema o di utente)può tornare nella coda di attesa (prelazione, in base ad un timer) oppure può fare una richiesta I/O (mediante interrupt I/O; poi viene messo in attesa dell’I/O; e poi viene soddisfatto)l’attesa I/O può essere su swap (swappping area) I processi sono suddivisi in gradi di priorità (alta, media, bassa)sono processati dalla CPU in base alle informazioni contenute nel loro PCB. Lo stato di RUN è in modalità Sistema; posso crearne uno in modalità utente. In UNIX, la chiamata per creare un processo è FORK(). Coefficiente di Utilizzazione=Probabilità che almeno un processo sia in esecuzione=ρ=λ/µ. λ=freq. Arrivo processi. µ=freq. Esecuzione processi. In un S.O. concorrente non è detto che ci sia sempre un processo in esecuzione, perché magari tutti aspettano uno I/O. UNIX System V – Release 3: Struttura monolitica (suddivisa in 3 livelli): • Utente. • Sistema (Kernel): interfaccia, file system (buffer, cache), processi. [gli ultimi due si basano su uno strato driver]. Il buffer e la cache permette un accesso rapido ai dati a cui si è già acceduto. • Hardware: dischi, schede di rete, memoria… LRU (Last Recently Used): i dati in cache e sul disco devono essere allineati (sincronizzati). In LINUX/UNIX il kernel ha solo un centinaio di routines interne al sistema, che vengono chiamate usando degli interrupt software (TRAP). Chiamate di sistema: sono le ≈100 routines del nucleo. I comandi che l’utente dà in console non sono chiamate di sistema, ma richiamano le routines di sistema tramite i TRAPS. Le chiamate di sistema rappresentano un particolare servizio che i programmi utente richiedono al Sistema Operativo. Una chiamata di sistema e’ svolta da una procedura contenuta nel nucleo del S.O. Il software del nucleo esegue in una modalita’ tale che ha accesso a tutte le parti del S.O., mentre i programmi utente girano in una modalita’ tale che solo alcune istruzioni sono eseguibili. Il passaggio tra le due modalita’ e’ realizzato dagli interrupt. Gli interrupt software, in particolare, sono quelli usati dal programma utente per trasferire il controllo al S.O. Risorse: possono essere hardware, software, una procedura… Si dividono in: • SOTTRAIBILI (e non): possono essere tolte in ogni istante dal procedimento. (es: Un file non è sottraibile). • RIUTILIZZABILI (e non): se si consuma con l’uso. (es: una stampa non è riutilizzabile). • CONDIVISIBILI (e non): possono essere usate da più utenti. Codice rientrante: è un codice riutilizzabile e condivisibile che non contiene dati. Anomalie: una risorsa non è usata in modo corretto ed equo (es: Strozzature, Cicli di reazione…). Cicli di reazione: l’uso errato di una risorsa può portare all’uso eccessivo di un’altra risorsa (es: memoria virtuale).

PROGRAMMAZIONE CONCORRENTE: Poiché abbiamo una sola CPU, si tratta di una concorrenza virtuale (“Interleaving”). Ordine di esecuzione: es: P11 P12 P21 P13 P22… (Notazione: P(n°processo)(n°istruzione)) TASK: entità computazionale; es; un’istruzione ASM; dipende da come è strutturato il S.O.. È comodo vedere un programma come una sequenza di Task (che può essere anche una serie di istruzioni). P1=T11T12T13 Ordinamento Totale P2=T21T22T23 Un programma concorrente ha un grafo ad Ordinamento Parziale. La “” realizza una relazione d’ordine di precedenza. T1T2 = T1
}

3 In UNIX, fork e wait sono nel kernel; poi i compilatori usano altri comandi. Es: in C, THREAD-CREATE e THREAD-WAIT richiamano fork e wait tramite una libreria. Interazioni fra Task: • Cooperazioni: dichiarazioni necessarie per il funzionamento del sistema. • Interferenze: problemi, errori di programmazione • Sincronizzazioni: è l’inserimento delle “”. Vita di un task: • Inizio: T = lettura valori, allocazione risorse, inizializzazione. • Task: T • Fine: T = scrive valori, disalloca risorse. Bisogna stare attenti alla scrittura dei valori, perché se scritti nel momento sbagliato possono influenzare il risultato di altri task.

SISTEMI OPERATIVI – I parte

DETERMINATEZZA: Il risultato finale è sempre lo stesso per ogni sequenza di istruzioni. Processo MultiThread: Ha un utilizzo ottimale delle risorse, poiché non deve ricorrere alle IPC per comunicare con il kernel. Il modello a memoria comune (multithreaded) può avere problemi ad attuare il principio di determinatezza. Predecessore: Ti , T j ∈ allo stesso percorso. Se • TiTj: Ti è successore di Tj Se j=i+1 allora si parla di Immediato Prec./Succ. f RT RT = Range di T, DT = Dominio di T T realizza f : DT → C=({T1,T2,…,Tn}; <) = collezione di Task con ordinamento parziale. DEF: due task T1,T2 sono mutuamente non interferenti se T1 è successore o predecessore di T2 oppure se ( RT 2 ∩ RT 1 = ∅ )and ( RT 1 ∩ DT 2 = ∅ )and ( RT 2 ∩ DT 1 = ∅ ) DEF: C è mutuamente non interferente se Ti e Tj sono mutuamente non interferenti ∀i, j Teorema di Bernstein: condizione necessaria e sufficiente per la determinatezza è la mutazione non interferente di C. Es: T1 (a=b=c=z=1) crea T2 (a=b+c; z=b) e T3 (z=a; c=a+b)  DT2={b,c}, DT3={a,b}, RT2={a,z}, RT3={c,z}  non è determinato perché DT 3 ∩ RT 2 ≠ ∅ = a

MUTUA ESCLUSIONE: Produttore() {While(true) { el=produci();}} Produttore e consumatore comunicano tra loro tramite un array A di N elementi. L’array ha 2 puntatori IN e OUT. Un esempio di produttore-consumatore è tastiera-monitor. Produttore() Consumatore() {♥ {♣ While(true) { While(true) { el=produci(); DATO=A[OUT]; A[in]=el; OUT=(OUT+1)%N IN=(IN+1)%N ; ; } } } } Ma così non funziona bene, perché Consumatore può leggere anche elementi vuoti. Allora nel punto ♣ inserisco WHILE(IN==OUT) cioè cicla finché non c’è un dato da leggere. Analogamente, non posso scrivere se non ho spazioin ♥ inserisco WHILE((IN+1)%N==OUT). Mutua esclusione: devo proteggere alcune sezioni di codice inserendo dei blocchi di attesa o degli arbitri. E’ un problema legato alle variabili che non possono essere semplicemente condivise (es: IN e OUT con più consumatori).

4 SISTEMI OPERATIVI – I parte COUNTER SWITCH: se per esempio esistono 2 consumatori e non so come decidere a quale dei due far leggere il valore. Ogni processo è formato da un alternarsi di sezioni critiche (SC) e sezioni non critiche (SNC). Un arbitro controlla che non si eseguano in contemporanea due sezioni critiche. Corsa Critica: è un programma che contiene una sezione critica. Per evitare danni in una corsa critica disabilito l’interrupt di COUNTER SWITCH  non si possono avviare altri processi. Ma questo, se fatto male, può bloccare il sistema. Si possono usare Soluzioni Software. Starvation: se un processo deve aspettare troppo a lungo. Deadlock: è lo stallo di un processo (es: due cicli che vanno in loop). PETERSON: è la soluzione software, creata nel 1981. Evita anche la starvation. P1 P2 { { while(1) { while(1) { B1=1; v=1; B2=1; v=0; while((b2==1)and(v==1)) while((b2==1)and(v==0)) ; ; sc1; sc2; b1=0; b2=0; snc1; snc1; } } } } Posso anche usare chiamate di sistema; P1 P2 { { while(1) { while(1) { while(b==0) B2=1; v=0; attesa(); while(b==1) sc1; attesa(); b=0; sveglio(P2); sc2; snc; b=1; sveglio (P1); } snc; } } } Un’altra soluzione al problema è il SEMAFORO: molto semplice e funzionante, richiede meno CPU di quella SW. È una primitiva del nucleo (cioè una system call), una variabile del sistema che non può essere manovrata direttamente dall’utente Le funzioni che ha l’utente di solito sono DOWN(sem) e UP(sem). DOWN(sems) UP(sems) { { if (s>0) s--; if ( ∃ processo in coda d’attesa su s) else metti il metti processo il processo in stato pronto; in coda d’attesa; else s++; } } Sono due procedure atomiche, cioè non possono essere interrotte. P1 P2 P3 DOWN(s); DOWN(s); DOWN(s); SC1; SC2; SC3; UP(s); UP(s); UP(s); C’è un momento all’inizio in cui si inizializza il semaforo a 1. Questi sono i SEMAFORI BINARI. Esiste anche il SEMAFORO CONTATORE, che non si limita a invertire un bit ma cambia i valori di una variabile intera. I sem. bin. Sono fatti per la mutua esclusione  sono detti MUTEX; i semafori contatori invece di solito si usano per la sincronizzazione. Si possono usare i sem. cont. Usando i sem.bin.:

SISTEMI OPERATIVI – I parte

5

MYDOWN(c) MYUP(c) { { DOWN(s1); DOWN(s1); c--; C++; IF(c<0) DOWN(s2); IF(c<=0) UP(s2); UP(s1); ELSE UP(s1); } } Dove C è un intero e all’inizio S1=S2=1, C=4. È un algoritmo potente perché permette di risolvere una vasta gamma di problemi. Esempi di mutua esclusione: Problema del produttore-consumatore: PROD() CONS() { { while(1) { while(1) { el=produci(); DOWN(pieno); DOWN(vuoto); DOWN(mutex); DOWN(mutex) DATO=A[p--]; ; UP(mutex); A[p++]=el; UP(vuoto); UP(mutex); } UP(pieno); } } } Problema del lettore-scrittore: ho una sola risorsa (es: archivio) gestito da una serie di lettori scrittori. Usiamo due sem. bin.: LETTORE(i) SCRTTORE(i) Creatore di thread: { { while(1) { DOWN(s); WHILE(1) { DOWN(mutex); SCRIVI(i); I=0; Nlettori++; UP(s); THREAD_CREATE(*lettore(i)); IF(nlettori==1) DOWN(s); } i++; LEGGI(i); } DOWN(mutex); Nlettori--; IF(nlettori==0) UP(s); UP(mutex); } } Problema dei 5 filosofi a cena: i filosofi a cena pensano o mangiano spaghetti. Esiste un solo piatto di spaghetti e per mangiare ogni filosofo deve usare 2 forchette (ci sono solo 5 forchette). Inserendo un semaforo posso far mangiare un filosofo alla volta (all’inizio s=4). Questo metodo però non garantisce la massima concorrenza. FILOSOFO(i) { WHILE(1) { PENSA(i); AFFAMATO(i); DOWN(s); PRENDISX(i); PRENDIDX(i); MANGIA(i); RILASCIASX(i); RILASCIADX(i); UP(s);

6 }}

SISTEMI OPERATIVI – I parte SCHEDULAZIONE DELLE RISORSE – STALLO:

Stallo: quando tutti i processi richiedono l’accesso a risorse non condivisibili e già assegnate ad altri processi. Stati sicuri: si è in stati sicuri se esiste una schedulazione che fa terminare i processi Condizioni di DeadLock: ci sono più situazioni che possono originare deadlock • tentativo di accesso a risorse non condivisibili • t– di accesso a risorse non sottraibili • t. di accesso a risorse in mutua esclusione • attesa circolare di risorse Grafo di allocazione delle risorse: si indicano i processi con dei cerchi, le risorse con dei quadrati. Quando un processo si aggancia ad una risorsa lo si indica con una freccia che punta al processo, quando un processo richiede una risorsa si usa una freccia che punta alla risorsa. banchiere P(i) Algoritmi: ci sono vari algoritmi che permettono solo passaggi per stati sicuri; {N°risorse – –; do {simula l’andamento del • Algoritmo del banchiere: ho N istanze di una risorsa e conosco il processo che si muove nelle numero massimo di risorse richieste da ogni processo. Lo schedulatore condizioni migliori procede facendo avanzare sempre il processo con il max_alloc minore; }while(!deadlock) or (finerisorse) la soluzioni esiste sempre, basta schedulare nel modo giusto. E’ un } sistema che funziona solo per i sistemi dedicati, cioè per quando conosco le risorse richieste. Un pc, al contrario, usa una allocazione casuale. • Detection and Recovery: W = (w1,…,wm) = vettore delle risorse esistenti; V = (v1,…,vm) = vettore delle risorse disponibili. Pi = (Pi,1,…,Pi,m)vettore delle risorse allocate dal processo Pi ; Qi=(Qi1,…,Qi,m)= vettore delle risorse richieste. P=(P1,…,Pn)T matrice e Q=(Q1,…,Qn)T matrice. Cerco un processo i tale che Qi
SCHEDULAZIONE DEI PROCESSI: Countext Switch: è l’insieme delle operazioni necessarie per passare da un processo all’altro. Ogni schedulazione ottimizza solo una di queste cose: • tempo di attesa media • tourn–around medio: è il tempo media da quando viene eseguito un processo a quando termina. • imparzialità • esecuzione entro la deadline • thruoghput: numeri di processi al secondo Rappresentazione GANTT: è una rappresentazione dei processi in coda, posizionati sull’asse del tempo. Predizione Statistica: ipotizza la durata di un processo; viene effettuata durante il CS e deve durare il meno possibile. tn+1 = f(tn,tn–1,tn–2,…). Una forma molto usata è tn+1 = Σi=0..N aitn–1 con ai = α(1–α)i Tipi di schedulazione: • FIFO o FCFS: First In First Out o First Come First Served; i processi vengono messi in una coda di attesa e sono passati alla cpu secondo l’ordine di arrivo. ai = istante di arrivo, fi = istante di fine del processo. Tempo di attesa medio = t = 1/NΣi=1..N fi – ai • SJF: Shortest Job First, minimizza il tempo d’attesa mettendo in ordine i processi secondo la loro durata, eseguendo prima i più piccoli. Poiché il SO deve conoscere a priori la durata dei processi, va bene solo per applicazioni dedicate, a meno che non si usi la predizione statistica • RR: Round Robin; lavora in time sharing spezzando il processo in varie parti. E’ quella di solito usata nei SO ed è imparziale (non fa preferenze tra i processi)

7 Prioritaria: si dividono i processi in tre categorie in base al loro funzionamento: I/O bounded se la maggior parte del processo implica accessi I/O, CPU bounded se hanno un uso preponderante della CPU e misti nel caso di parità. Si creano così tre code separate; è un compromesso con il RR che cerca di minimizzare il tempo di attesa medio e l’imparzialità RR Prioritaria: di solito P=1/tn+1 (v.predizione stat.) ed ottimizza il tempo di attesa medio. E’ il sistema usato da unix: più code con priorità diverse, in modo da agevolare i processi che terminano prima. Selfish RR: ho due code, una RR e una FIFO. Prendiamo un piano cartesiano con il tempo sulle x e la priorità su y: ad ogni processo è assegnata una retta passante per l’asse t nel momento in cui entra il processo. In to entra un processo gli assegniamo una retta passante per to a pendenza α; ai processi successivi si assegnano rette con pendenza β>α. Un processo viene messo nella coda RR quando la sua curva interseca la retta a pendenza α: in questo modo non appesantisco subito la coda RR. Multilevel Feedback: se un processo termina entro una certa dead–line (es: due quanti di time sharing) viene eseguito nella prima coda (è un processo breve), altrimenti (processo lungo) viene spostato in una coda successiva. Ho quindi due livelli di priorità: quello interno di coda e quello tra le varie code. Problema: starvation di schedulazione prioritaria: i processi più lenti vanno a finire sempre più in la nelle code e rischiano di non essere eseguiti. Soluzione: aging, è un sistema che alza temporaneamente la priorità dei processi che sono da molto tempo nella coda più lunga.

SISTEMI OPERATIVI – I parte

•

• •

•

SCHEDULAZIONE IN S.O. DEDICATI: Dead line: limite temporale entro il quale un processo deve terminare = d Nelle schedulazioni in tempo reale ho un tempo massimo entro il quale un task deve finireil RR non è applicabile e devo eliminare tutte le fonti di imprevedibilità quali: • memoria cache: contiene i dati di uso recente, ma il cache hit/miss è un evento imprevedibile (prob. cache hit = 99)  non viene usata • memoria virtuale: prob.VM = 90%  si usa memoria contigua • interrupt: nel tempo reale non viene servito subito Lateness: sia s l’istante in cui arriva un processo, f l’istante in cui finisce. 0
GESTIONE MEMORIA: C’è una coda in cui vengono messi i processi che richiedono l’accesso alla memoria; questa coda viene organizzata da un gestore della memoria che passa i dati alla memoria fisica. α = indirizzo virtuale, β = α+base = indirizzo fisico. Esiste un test di controllo che in caso di errore apre un interrupt: if(β>limite) then fault Tipi di partizioni: esistono due modi per dividere la memoria; • basi fisse: a priori stabilisco le dimensioni delle partizioni. Il gestore di memoria prende il processo e vede in che zona di memoria può essere caricato, dunque lo mette in memoria. Problema: si crea una frammentazione della memoria, perché resta inutilizzata in molti punti.

8

SISTEMI OPERATIVI – I parte

• basi variabili: le dimensioni delle partizioni sono variabili. Compattazione della memoria a basi variabili: sia V la velocità con cui cresce la memoria occupata [parole/sec], f = memoria libera / memoria totale = percentuale di memoria occupata, M la memoria totale. Allora f⋅ M = memoria libera e (1–f)⋅ M = memoria occupata; TR = tempo di riempimento = f⋅ M/V. Il compattamento richiede del tempo: se si libera una word in basso bisogna leggere e scrivere tutta la memoria per compattarla nuovamente. Tc=(1–f)M⋅ 2 (⋅ 2 perché devo leggere e scrivere); è un’operazione critica perché durante il suo svolgimento la memoria è bloccata. Costo di compattamento=Tc / (TR+TC)= 2(1–f)V/(f+2(1–f)v); la curva dipende da V e si azzera in (0,1) e (1,0) con f sulle ascisse e Tc/(Tr+Tc) sulle ordinate. Stazionarietà: sono in questa condizione se la memoria non è mai tutta piena o tutta vuota Considerazioni basi fisse: sia na il numero di partizioni che se liberate lasciano inalterato il numero di partizioni libere, nb quelle che se liberate ne decrementa il numero, nc quelle che se liberate lo aumentano. N° partizioni occupate = na+nb+nc; si può usare una formula approssimata per calcolare la partizioni libere: N° partizioni libere = ½(na+2nb) (±1). Se è stazionario, nb=nc Considerazioni basi variabili: se si è in regime stazionario, vale che N° partizioni libere = N° partizioni occupate/2; Se n=dimensione media del processo, m=dimensione media di una partizione libera f=(Nlib⋅ m)/ (Nocc⋅ n + Nlib⋅ m)=m/(2n+m) Liste Concatenate: è il metodo della gestione fisica; ogni elemento della lista contiene l’indirizzo della base, la dimensione e un indicatore di memoria libera/occupata. Un’alternativa è il creare due liste: una per le zone occupate e una per le zone liberelo scorrimento è più veloce. Possono essere ordinate per: • indirizzo: scorro le liste finché non trovo una partizione libera ≥ della richiesta trovo le first fit • dimensione crescente: la prima partizione libera che può contenere il processo è la partizione ottimabest fit. Problema: crea molta deframmentazione • dimensione decrescente: la prima partizione che trovo è la peggiore  worst fit Problema: crea grossi buchi

MEMORIA VIRTUALE: l'idea che sta alla base della memoria virtuale è che le dimensioni combinate del programma, dei dati e dello stack possono oltrepassare la quant di mem fisicamente disp. il so mantiene in mem le parti del prog attualmente in uso mentre il resto rimane su disco. Memoria virtuale: formata da pagine di dimensioni fisse (Dim C[byte], es 512, 1024, 4096,…). Memoria fisica anche divisa in pagine stessa dim. Spazio di indirizzamento: insieme delle pagine. Lo spazio complessivo deve essere multiplo di C, altrimenti spazio inutilizzato. Pagine più piccole implicano meno frammentazione. Mem Virt = {0…m} Mem Fis = {0…n} di solito m>=n>=0 indirizzamento virtuale α = x*c + w (x num pag virt, w offset), indirizzamento fisico β = f(x)*c + w (f(x) effettua traduzione indirizzi (f(x) = y se risiede in β , f(x) = 0 altrimenti. Alla ricezione di una demand paging il SO effettua: fetch: individua pagina da copiare; placement: individua spazio in mem fisica dove mettere pag, se ha spazio ok, altrimenti rimpiazza pag vecchia; replacement:: deve capire quale pag rimpiazzare. Alternativa: pre-fetch: maggior parte dei prog è sequenziale (se chiede pag x, molto prob che chieda pag x+1). Replacement: prob di page fault PF = #pagefault / #riferimenti, Td temp accesso al disco, Tn temp accesso memoria; T temp effettivo di accesso medio alla mem M = PF(Td+Tm)+(1-PF)Tm Distanza Backward (elimino la pagina usata più tempo indietro) - Forward (elimino la pagina che verrà usata più tempo avanti); Algoritmi usati: LRU o Least Recently Used (massimizza la dist backward), Belady (massimizza la dist forward), FIFO (rimpiazza la pag rimasta in mem fis più a lungo), NRU o Not Recently Used. Problema tabella da inizializza: meglio inizializzarla riga per riga (non colonna per colonna, cioè for(x=0;…) for(y=0;…) a[x][y]=0, non a[y][x]) evito così di creare molti più page-fault. Aumento mem fisica migliore? In generale aumentando le pag di mem fis la PF nuova è <= la PF vecchia. FIFO e anomalie: in questo proc non occorre riordinare perché non serve sapere quanto tempo prima una pag è stata mem. Di solito FIFO è più lungo, anche se velocità di calc sembra maggiore. E’ un algoritmo anomalo, non è detto che l’aumento di mem fis diminuisca il page fault. PMT Page Map Table: ogni task può avere al max 2^20 pag di mem virt in un SO con indirizzamento a 32 bit [20 indirizzamento pag; 12 offset]; tramite i 20 bit si ricerca la pag virt nella tabella

9 delle pag ottenendo così l’indirizzo fisico che viene sostituito all’indirizzo virt e affiancato all’offset formando l’indirizzo definitivo che viene mandato alla mem. PMT multilivello: due tavole PMT e indirizzi composti diversamente [10bit per la PMT1, 10bit per la PMT2, 12bit offset]; tramite le PMT multiliv la ricerca di un dato è più facile è veloce. TLB Translation Lookaside Buffer: tabella conentente il numero di pag virt e il num di pag fis. Piccola cache in cui sono salvati i dati usati più di recente. Alla traduzione dell’indirizzo prima si guarda la TLB, se non si trova il dato si guarda la PMT; molto vantaggiose, 99% hit-rate, molto veloce. Un elemento della TLB [dim comune di 32bit quasi sempre] è formato da indirizzo di pag fis [numero di frame di pagina], bit presente/assente, bit di protezione [due soluzioni: 1bit [0 lettura/scrittura; 1 solo lettura]; 3bit [lettura/scrittura/esecuzione], bit modificato, bit riferito. Algoritmi di rimpiazzamento pagine: NRU: vengono associati due bit di stato ad ogni pagina per effettuare statistiche sulle pagine in uso [bit R messo a 1 quando pag riferita, bit M quando pag modificata]. All’avvio di un processo tutti i bit vengono messi a zero; quando avviene un page fault bit R ad 1; se pagina scritta bit M messo a 1; periodicamente bit R azzerato per trovare pag riferite di recente o meno. Tramite questi due bit l’algoritmo rimuove una pag che non è stata riferita recentemente piuttosto che una pag non modificata ma in uso; FIFO: il SO mantiene una lista contentente tutte le pag in memoria, dove pag in testa è più vecchia, pag in coda più recente. Con page fault pag in testa rimossa e nuova pag messa in coda. Raramente usato; Second Chance: variante algoritmo FIFO, evita di buttare pagina molto usata, esamina bit R della pag più vecchia; se bit è 0 pag vecchia e inutilizzata, immediatamente rimpiazzata; se 1 bit azzerato, pag messa in fondo alla lista, suo tempo di caricamento aggiornato come appena messo in mem. LRU: lista contenente tutte pag presenti in memoria, dove pag usata più di recente in testa, pag meno frequente in fondo, lista aggiornata ad ogni riferimento in memoria; trovare pag in lista, rimuoverla e quindi spostarla richiede molto tempo; NFU: soluzione software della LRU; si associa un contatore software ad ogni pagina inizialmente posto a zero; ogni colpo di clock tutte le pag in memoria sono scandite, per ogni pag il bit R viene addizionato al contatore; quando si ha un page fault la pag con contatore minimo viene rimpiazzata. Working set: insieme delle pagine riferite in una finestra temporale T; ws più usato working set con LRU. Implementazione del ws-LRU: si introduce un parametro PFF = 1/(ta-tPF) con ta tempo virtuale e tPF tempo ultimo page fault; ha senso calcolarlo solo se ho PF. Implementazione pratica: if PFF>0 then (aggiungi la pag che ha causato PF al WS) else (il WS resta invariato).

SISTEMI OPERATIVI – I parte

MEMORIA CACHE: Memoria cache: velocità ormai quasi uguale alle memorie normali, vantaggio nel non occupare il buffer. h: hit rate; tc: tempo accesso cache; tm: tempo accesso memoria. Tempo accesso effettivo = h*tc+(1-h)*(tc+tm) = h*tc-h*(tc+tm)+(tm+tc) = -h*tm+tm+tc. Essendo tm>>tc, se h->0, Teff-> tm; se h->1, Teff->tc. In genere piccole variazioni di h influenzano molto le prestazioni. Dimensioni di pagina: α = x*c+w [x indirizzo, c dim pagina, w offset]. Mediamente la mem non utilizata è f = c/2; s spazio di indirizzamento, s/c num pag virt; es. con riga PMT di 8 byte; dimensioni tot PMT = 8*c/s; fattore di costo F = f*dim PMT = c/2+8*s/c facendo derivata otteniamo c ottimo: dF/dc = ½+8s/c^2 >> ½ = 8s/c^2 >> c^2=16s >> c=4sqrt(s).

GESTIONE DISCHI: Gestione dischi: HD collo di bottigliadei calcolatori; tlettura = tseek+tlantenza+ttrasferimento [ultimi due dipendono dalla vel di rotazione]. Tseek: dipende dal braccio che regge le testine, di solito circa 10ms, composto da più operazioni tra cui center time [tempo richiesto per centrare l’obiettivo una volta in zona]. HD sistema dedicato, composto da SO in tempo reale. Sistemi di gestione HD: FCFS – First Come First Served; SSTF – Shortest Seek Time First: scelta della richiesta con minor tempo di seek (ottimizzazione), soggetto a starvation perché può darsi che una zona sia servita più spesso; SCAN: testina si muove continuamente dal max al min e serve le richieste quando è in zona; CSCAN: come scan ma dopo aver servito qualcuno torno al punto di inizio, funziona a scatti, HD con potenza di calcolo non molto alta; CLOOK: quando torna indietro serve la richiesta che incontra.

RETI DI TELECOMUNICAZIONI – II parte

1

di Giorgio DAVANZO, Andrea MATOSSICH e Davide PRADE

THREADS: Processi: Nei sistemi concorrenti (multiprogrammati), il termine processo denota la singola attività eseguita in modo indipendente e separato rispetto alle altre. Tipicamente, un programma è eseguito da un processo, anche se più processi possono eseguire lo stesso programma. Facendo un paragone con Classi e Oggetti, un programma agisce come una classe, il processo rappresenta una istanza in esecuzione del programma. Un processo: • è del tutto autonomo e indipendente dagli altri processi • ha un proprio spazio di indirizzamento riservato (porzione di memoria RAM) e non condivide memoria con altri processi: • significa che anche le variabili globali sono private al processo • ha un proprio stack riservato (quindi anche le variabili locale sono private al processo). I processi servono ad avere attività (task) in esecuzione concorrente ma indipendente, minimizzando le possibilità di interazione e quindi di disturbo reciproco, e con un proprio ciclo di vita (es. five state model, vedi figura a fianco). Comunicazione tra processi: non può quindi avvenire in modo “diretto” (per condivisione di variabili), ma deve sfruttare appositi meccanismi di sistema (IPC, per esempio file o socket). Threads: sono delle sotto-attività di un processo che possono essere eseguite tutte in “parallelo” e risultano meno onerose da gestire per il S.O. (storicamente si usava il termine LWP “Light Weight Processes”). Nascono dalla necessità di ottimizzare al meglio il tempo di esecuzione di un processo nel caso di programmi in cui non vi è solo una attività in esecuzione, ma in cui diverse attività in concorrenza eseguono (motivi di efficienza dell'esecuzione). In questo caso, vi è può l'esigenza forte di fare interagire le diverse attività in esecuzione. Carattersitche: • è un’attività autonoma che “vive” all’interno di un processo (e quindi, tipicamente, la stessa istanza in esecuzione di un programma, corrispondente a un processo, ospita al suo interno dei sotto-flussi di esecuzione concorrente, corrispondenti ai thread) • non ha uno spazio di indirizzamento riservato: tutti i thread appartenenti allo stesso processo condividono il medesimo spazio di indirizzamento (le variabili globali in RAM). • ha un proprio stack riservato (e quindi le sue variabili locali di una procedura sono private e non condivise da altri thread) • l’oggetto che crea il thread non si blocca aspettandone la fine, ma prosegue la sua esecuzione in contemporanea. Comunicazione tra threads: può avvenire in modo molto più semplice, tramite lo spazio di memoria condiviso. Quindi, se ci sono variabili globali o riferimenti a aree di memoria od oggetti comuni diversi threads possono interagire. Occorre però disciplinare l’accesso a tale area comune → necessità di opportuni meccanismi di sincronizzazione In un liguaggio ad oggetti come Java, ovviamente, il concetto di variabile globale non ha senso. Però più threads possono condividere riferimenti allo stesso oggetto, interagendo tramite tale oggetto. Differenza tra processi e threads: I processi si caratterizzano come “Collezione organizzata di insiemi di risorse”, e queste risorse in esecuzione si dicono Thread. I thread sono quindi delle unità minime di schedulazione per l’esecuzione da parte della CPU, in buona misura indipendenti gli uni dagli altri Multithreading: è la proprietà che caratterizza quei SO in grado di garantire la gestione di più threads all’interno di un processo; infatti, i SO possono gestire: • un solo thread (es.: MS-DOS) • un processo con più thread • più processi utente ma un solo thread per processo (es: UNIX) • thread multipli (es: Windows 2000, Solaris, Linux, Mach, OS/2) SO Multithreading: Un S.O.M. è caratterizzato da due componenti di esecuzione: processi e thread; - ai processi sono associati: • un unico spazio di indirizzi che contiene l’immagine del processo (testo, dati, stack)

RETI DI TELECOMUNICAZIONI – II parte

2

• meccanismi di protezione da e verso altri processi • risorse: file e I/O - ai thread sono associati: N.B.: non vi è un meccanismo di protezione per i thread. • uno stato (running, ready, ecc.) • un contesto (opportunamente salvato quando il thread non è in esecuzione) • uno stack (pila) per l’esecuzione delle procedure • uno stack per la memorizzazione di variabili locali • accessi alle risorse del processo al quale il thread appartiene: memoria, file e periferiche Gestione dei Thread: sono gestiti in modo analogo a come sono gestiti i processi in un sistema multiprogrammato; un processo comincia l’esecuzione con un thread che procede creandone altri mediante chiamate di libreria. Ogni thread ha diversi stati, diversi da ogni SO. Es.: Modello Linux a Processi/thread: un thread è in esecuzione solo se il suo processo è in running state. Comparazione multi / single thread: • single thread process mode: ci sono un Process Control Block, un User Address Space, uno User Stack ed un Kernel Stack • multi thread process mode: ci sono un Process Control Block, un User Address Space, molti thread formati da Thread Control Block, User Stack ed Kernel Stack Vantaggi nell’uso dei thread: • creare/terminare un thread sono operazioni più veloci delle corrispondenti operazioni sui processi • non ci sono risorse associate ai thread • il context switch tra thread è un’operazione più veloce del context switch tra processi • la comunicazione tra thread è un’operazione più veloce della comunicazione tra processi • l’esecuzione con thread multipli migliora le prestazioni: o Quando I/O e calcolo possono essere sovrapposti o In presenza di CPU multiple (SMP, Symmetric MultiProcessing) SMP: Il Kernel è in esecuzione su ciascun processore; ogni processore schedula ed esegue processi o thread scelti tra un pool di attività disponibili Remote Procedure Calls e Threads: le RPC sono procedure richieste da un client ad un server. • sistema non multi–thread: le richieste sono serializzate • sistema multi–thread: le chiamate al server sono contemporanee. Es.: Apache 2.0 (non multi–thread ma multi–process): il server assegna ad ogni richiesta un processo separato  alla fine si hanno N processi in memoria  poco efficiente. Con il multi–thread: supponiamo di avere più richieste alla stessa pagina; il web server ha un processo solo con un thread ed un dispacherche genera worker threads: se è una richiesta nuova non cambia niente, altrimenti il nuovo thread troverà già la pagine richiesta caricata nello spazio di memoria condiviso. User mode threads: La gestione dei thread è completamente svolta a livello applicazione (es: JVM), il kernel ignora l’esistenza dei thread  all’interno del processo ci deve essere un motore che gestisce i thread, il Runtime System, che: • mantiene le informazioni necessarie per ciascun thread (tabella dei thread) • decide lo scheduling dei thread • implementa le funzioni di libreria thread_create, thread_wait, thread_exit, thread_yield, ecc Vantaggi: • Portabilità • Efficienza di switching e scheduling • non è necessario eseguire un trap (interruzione software) al kernel per ciascuno switch tra thread di uno stesso processo

RETI DI TELECOMUNICAZIONI – II parte

3

• Scheduling personnalizzato Svantaggi: • Un’operazione bloccante di un thread blocca l’intero processo • il kernel ignora l’esistenza di thread liberi di quel processo • Il page fault di un thread blocca l’intero processo • Non può essere sfruttato il multiprocessing Kernel Level Threads: tutta la gestione affidata al run-time è svolta dal kernel, di conseguenza lo scheduling viene effettuato sulla base dei thread. Es.: win2k, linux, OS/2. Vantaggi: Pieno sfruttamento delle risorse hardware del sistema Svantaggi: La gestione dei thread è più lenta di quella User Level poiché richiede l’intermediazione del kernel Oggetto thread in Windows: basta sapere che i thread hanno due macrostadi: runnable e non runnable. Approccio ibrido – Solaris: I thread sono creati a livello user sopra thread di livello kernel; gran parte delle operazioni di scheduling e sincronizzazione tra thread sono svolte a livello utente, mentre il kernel dà un accesso rapido alle risorse. Problemi sui threads: • Conflitti su variabili condivise • File condivisi: può accadere che un thread chiuda un file mentre un altro thread lo sta leggendo • Fork: quando viene clonato un processo, il processo figlio eredita tutti i thread del genitore? • Gestione degli interrupt: più thread appartenenti allo stesso processo possono essere in attesa dello stesso tipo di evento

INTER PROCESS COMMUNICATION (IPC): Sono meccanismi per scambiare informazioni di vario tipo; alcuni di essi sono: • signal: generati automaticamente dal sistema o inviati su richiesta di un processo o di una periferica • pipe: per scambio stream caratteri tra processi padre/figlio: uno produce un output stream e uno lo usa • FIFO (o named pipe): per scambio stream caratteri tra processi residenti sulla stessa macchina • socket: per scambio dati tra processi residenti anche su macchine diverse • shared memory, (un)lock per file condivisi Segnali: sono interrupt software inviati al processo dal SO o da user process che possono essere ricevuti in modo asincrono o meno; questo segnale deve essere trattato dal processo ricevente, che può ignorarlo o catturarlo. Se lo cattura il P. deve gestire il segnale attraverso una funzione detta handler oppure, se questa non è specificata, si usa una funzione definita dal SO come default. Attesa di un segnale: in unix la primitiva è pid_t wait (int *stat_loc); è una funzione bloccante. Alla terminazione del processo figlio, il SO invia sigchild al padre, che ne ricorda lo stato in stat_loc. Se il padre non cattura la terminazione si parla di figlio zombie, mentre se il padre termina prima del figlio questi diventa discendente di init. Signal Posix: in posix ci sono vari segnali, alcuni definiti dal sistema (es: sigill = l’utente ha premuto del) e due definibili per le applicazioni. Costruzione di un handler: si usa la procedura signal, che consente di specificare un handler per il segnale sig: void(*signal(int sig, void (*func)(int)))(int). Ritorna 0 se ha successo, –1 altrimenti. Ci sono altre funzioni a disposizione: • sigaction: e' una variante di signal • sigreturn: ritorna da handler e ripulisce stack da esso • sigprocmask: cambia l'insieme di segnali da bloccare • sigpending: consente di esaminare segnali bloccati • sigsuspend: aggiorna mask e sospende proc. in attesa signal Terminazione su segnali: si invia un segnale ad un processo, usando la funzione int kill(pid_t pid, int sig): invia il segnale sig ad il processo indicato da pid. Se pid = 0, va a tutti i processi nel gruppo sender; se pid= –1 va a tutti i processi con UID uguale al UID e EUID del sender. Ritorna 0 se ha successo, –1 altrimenti. Alarm: serve a risvegliare ciclicamente un processo dormiente: unsigned int alarm(unsigned int sec). Dopo sec secondi genera il segnale SIGALARM; se sec=0 annulla le precedenti chiamate ad alarm(), ritorna –1 per errori o il numero di secondi mancanti all’allarme precedente. Pause: manda in stato di wait un processo finchè questo non riceve una alarm.

RETI DI TELECOMUNICAZIONI – II parte

4

Pipe: int pipe(int fildes[2]). E’ un flusso di comunicazione unidirezionale, in cui fildes[0] è usato per leggere e fildes[1] è usato per scrivere. Va creata prima della fork, torna 0 se ha successo, –1 altrimenti. Es.: int canale[2]; pipe(canale); per scrivere: write(canale[1],buffer,counter). per leggere: read(canale[0],buffer,1). Fifo: è simile alla Pipe, consentono la comunicazione tra processi residenti sulla stessa macchina ma non imparentati: il file è noto ad entrambi, un processo scrive e l’altro legge. Shared Memory: semafori per mutex, sincronizzazione. Usa le funzioni shmget, shmctl, … File Locking: è il modo più pesante e meno efficiente, usa le funzioni lockf e flock Socket: i due processi comunicano attraversto la rete (IP e UDP/TCP) e attraverso una porta speciale.

RETI: •

Client/Server:

•

Reti Broadcast: o Broadcasting o Unicast o Multicast

Rete punto-punto: Routing (instradamento)

•

Reti Geografiche (WAN):

Routing tra 2 subnet: una subnet basata su questo principio si chiama: • punto a punto; • store and forward; • a commutazione di pacchetto (packet switched). Molte topologie di interconnessione possono essere impiegate fra i router: • a stella (ridondanza zero); • ad anello (ridondanza zero); • ad albero (ridondanza zero); • magliata (ridondanza media); • completamente connessa (ridondanza massima). Gateway (internetworking): Protocolli/Interfacce:

Flusso informazioni in rete:

SISTEMI OPERATIVI – II parte Tipologie di servizio: • Connection-oriented: (tutti i pacchetti seguono la stessa connessione); • Connection-less: (i pacchetti possono seguire una connessione diversa dalla precedente). Primitive del servizio: • request(): si chiede al servizio di fare qualcosa; • indication(): si viene avvertiti dal servizio di qualche evento; • response(): si vuole ripondere ad un evento; • confirm(): la risposta che si attendeva è arrivata. Servizi vs. protocolli:

Modello OSI:

Flusso OSI via router:

Differenza OSI e TCP/IP: OSI Tcp/Ip Applicaton Applicaton Presentation Session Transport Transport Network Internet Data Link Host-to-Network Fisico Architettura di rete TCP/IP: Ftp

Telnet

Transport Internet Host-to-Network

Tcp Udp IP Vari standard per LAN, WAN e MAN

Netware (Novell): Application File Server, etc. Transport NCP, SPX, Tcp Network IPX

Smtp

Http

Nnt p

Application

…

5

6 Data Link Fisico SNA (IBM): Livelli OSI 7 6 5 4 3 2 1

SISTEMI OPERATIVI – II parte Ethernet, Token Ring, etc. Ethernet, Token Ring, etc. Livelli SNA Transaction service Presentation service Data Flow Management service Transmiss. control Virtual route Explicit route Trasmission group Liv. Data Link Liv. Fisico

Internet (IP, RFC791): ci sono una US Backbone e una Europe Backbone collegate fra di loro. A quella americana è collegata una rete regionale, mentre a quella europea una rete nazionale, alle quali sono collegate le LAN.

SISTEMI DISTRIBUITI: A metà degli anni quaranta inizia l’era dei calcolatori moderni: grandi, costosi e capaci di eseguire decine di istruzioni al secondo. A partire dalla metà degli anni ottanta il sviluppo tecnologico su microprocessori e reti fa abbassare enormemente i prezzi. Sistemi distribuiti: sistemi ottenuti dall’aggregazione di singole CPU, sistemi di memorizzazione e periferiche, oppure, un sistema distribuito è una collezione di computer indipendenti che appaiono all’utente come un singolo sistema coerente. Il fatto che i computer siano indipendenti significa che sono autonomi. L’apparire come un singolo sistema è una caratteristica del software. Nulla è detto relativamente alla locazione fisica dei singoli computer. Hanno bisogno di software di sistema completamente diverso rispetto al passato. Esempi: • Un pool di PC nel laboratorio studenti non assegnati ad utenti, ma dinamicamente allocati secondo le esigenze di calcolo. • Un insieme di robot, singolarmente controllati da computer, che cooperano in una produzione industriale e alla risoluzione di problemi nella produzione. • Una banca con centinaia di filiali distribuite nel mondo che gestisce le operazioni dei clienti in maniera trasparente rispetto a dove si trovi il loro conto corrente. Vantaggi sui sistemi centralizzati: • I sistemi distribuiti hanno un miglior rapporto costo/ prestazione. • Possono fornire prestazioni assolute maggiori di qualsiasi sistema centralizzato. • Alcune applicazioni sono intrinsecamente distribuite (es: approvvigionamento in catene di supermercati; allineamento di sequenze; giochi, …). • Affidabilità: se ad ogni istante il 5% delle risorse di un sistema distribuito è guasto, si ha un degrado delle prestazioni del 5%. • Crescita incrementale: se i bisogni di una azienda crescono, un nuovo sistema centralizzato più grande è necessario… Vantaggi sui Sistemi Indipendenti: • Se si utilizzano i singoli sistemi indipendentemente il risultato non è sempre la “somma” dei singoli risultati (es: un sistema di prenotazioni non può essere costituito da stazioni indipendenti). • La condivisione delle risorse può riguardare strumenti costosi o unici (es: telescopi, microscopi, periferiche…). • Connettendo insieme un gruppo di calcolatori isolati in un sistema distribuito si migliora la comunicazione interpersonale (es: sistemi P2P per file sharing). • Singoli sistemi non cooperanti saranno sempre più rari. Svantaggi: • Disegno e implementazione del software: gestione dell’eterogeneità e trasparenza, allocazione delle risorse, scheduling, memorizzazione…

7 • Affidabilità: le risorse possono appartenere ad organizzazioni differenti; la rete di comunicazione può perdere messaggi o saturarsi. • Protezione e privacy: la condivisione di informazioni non sempre è vantaggiosa. Organizzazione Hardware: Tutti i sistemi distribuiti sono costituiti da più CPU; la maniera in cui queste sono connesse e comunicano conduce a diverse organizzazioni. Diverse classificazioni sono state proposte negli anni, ma nessuna è stata ampiamente adottata. Tra queste la più famosa è la tassonomia di Flynn (1972). Le caratteristiche essenziali per Flynn sono i flussi (stream) di dati e istruzioni: • Single Instruction Single Data (SISD) tutti i monoprocessori • Single Instruction Multiple Data (SIMD) processori vettoriali • Multiple Instruction Single Data (MISD) nessun computer • Multiple Instruction Multiple Data (MIMD) tutti i sistemi distribuiti: i sistemi MIMD che condividono la memoria sono detti multiprocessori, gli altri multicomputer.

SISTEMI OPERATIVI – II parte

Se la comunicazione avviene su reti di sistema, si parla di accoppiamento stretto, altrimenti di accoppiamento debole. Multiprocessori basati su bus: Per bus si intende che esiste una rete, backplane, bus, cavo o altro mezzo che connette tutte le macchine. Per diminuire il traffico sul bus, si aggiunge una cache tra CPU e bus. Il numero massimo di processori è 16-32. Multiprocessori basati su switch: Per collegare più di 64 CPU si può dividere la memoria in moduli e collegarla alle CPU mediante switch. Per mantenere limitato il numero degli switch si possono utilizzare tipologie di connessione particolari. Multicomputer basati su bus: Memoria locale

Memoria locale

Memoria locale

CPU

CPU

CPU

Multicomputer basati su switch: • Griglia • Ipercubo Software: Sistema NOS (Network Operating System) DOS (Distributed Operatine System) Middleware

Descrizione Scopo principale Sistema operativo debolmente accoppiato per Offre servizi locali a multicomputer eterogenei (LAN e WAN) client remoti Sistema operativo strettamente accoppiato per Nasconde e gestisce multicomputer e multiprocessori omogenei risorse hardware Strato di software posto sopra un NOS per implementare Fornisce trasparenza servizi general-purpose per multicomputer eterogenei alla distribuzione Sistemi Operativi di Rete: offre un ambiente nel quale gli utenti possono accedere alle risorse remote e condividere file. Esempi di servizi messi a disposizione sono: accesso alle risorse con telnet o rlogin, autenticazione centralizzata, condivisione dei file, esecuzione remota mediante chiamate a procedura remota.

8 SISTEMI OPERATIVI – II parte In un tale ambiente un sistema operativo gestisce le singole risorse e le comunicazioni tra di esse. Il sistema operativo dei singoli computer può essere o meno lo stesso. Sistemi Operativi Distribuiti: il trasferimento di dati e processi è sotto il controllo del sistema operativo. La comunicazione interprocesso avviene mediante lo stesso meccanismo sia localmente, sia in remoto. Sono presenti meccanismi globali di protezione, gestione dei processi, accesso alla memoria secondaria. Gestiscono sia multicomputer, sia multiprocessori: • In un sistema operativo per multiprocessori tutte le strutture dati necessarie alla gestione dell’hardware si trovano nella memoria condivisa e vanno protette da accessi concorrenti. • Nei sistemi operativi per multicomputer tali strutture dati non sono facilmente condivisibili e l’unico mezzo di comunicazione è lo scambio dei messaggi. Un utente accede alle risorse remote così come accade per quelle locali. Alternative per bloccaggio e buffering nello scambio di messaggi:

Relazione tra comunicazioni bloccanti, bufferizzate e affidabili: Punto di sincronizzazione Send Affidabilità buffer Blocca sender fino a quando buffer non è pieno Si Non necessariamente Blocca sender fino a quanto il messaggio è spedito No Non necessariamente Blocca sender fino a quanto il messaggio è ricevuto No Necessariamente Blocca sender fino a quanto il messaggio è recapitato No Necessariamente Middleware: Né i sistemi operativi di rete, né quelli distribuiti soddisfano la definizione di sistema distribuito. In questi approcci o si perde l’indipendenza o la visione di un unico sistema coerente. Per ovviare a questo problema si utilizza il middleware, un ulteriore strato di software tra il sistema operativo e le applicazioni. Modelli di middleware: Per sviluppare ed integrare applicazioni distribuite si definiscono dei modelli (paradigmi) atti a descrivere la distribuzione e la comunicazione. La maniera più semplice è descrivere tutto tramite file, come accade in UNIX; la comunicazione avviene tramite la condivisione dei file (Plan 9). Nei file system distribuiti la trasparenza si applica solo ai file regolari e spesso l’esecuzione di un processo su una determinata macchina è esplicita (AFS). Nella chiamata a procedura remota, un processo può chiamare una procedura la cui implementazione si trova su un server remoto (RPC). Nel paradigma ad oggetti distribuiti, quando un processo invoca un metodo, tale richiesta viene tradotta in un messaggio inviato all’oggetto, che esegue la richiesta e ritorna il risultato (CORBA). Middleware e Apertura: Un sistema operativo distribuito aperto è caratterizzato in termini di specifica delle interfacce. Un’interfaccia è completa se nella specifica sono presenti tutti i dettagli necessari per implementarla. Può accadere che due implementazioni dello stesso standard siano incompatibili, nel senso che non possono cooperare. In un sistema distribuito basato su middleware aperto, i protocolli usati da ciascun livello del middleware devono essere gli stessi, così come le interfacce alle applicazioni.

SISTEMI OPERATIVI – II parte

9

Forme differenti di trasparenza in un sistema distribuito: Trasparenza Descrizione Accesso Nascondere le differenze nella rappresentazione dei dati e nell’accesso alle risorse Locazione Nascondere dove le risorse siano fisicamente collocate Migrazione Nascondere che le risorse possono migrare verso altri posti Rilocazione Nascondere che le risorse possono migrare verso un altro posto durante il loro uso Replicazione Nascondere la condivisione delle risorse tra diversi utenti in competizione Concorrenza Nascondere che una risorsa possa essere condivisa tra diversi utenti in competizione Guasto Nascondere il guasto ed il ripristino di una risorsa Parallelismo Nascondere il fatto che una risorsa sia un sistema parallelo Affidabilità di un Sistema Distribuito: Uno degli scopi originari nella realizzazione dei sistemi distribuiti era di renderli più affidabili rispetto ai sistemi monoprocessori. L’affidabilità può essere intesa come disponibilità, vale a dire come percentuale di tempo in cui il sistema è utilizzabile. La sicurezza nei sistemi distribuiti è un elemento critico: quando un server riceve una richiesta di un servizio, bisogna stabilire da chi proviene. Un sistema distribuito deve essere in grado di tollerare i guasti: la sua funzionalità globale non può derivare da quella sui singoli componenti. Prestazioni di un Sistema Distribuito: Per misurare le prestazioni di un sistema distribuito si utilizzano delle metriche; ciascuna mette in risalto un aspetto del comportamento del sistema distribuito (es: tempo di risposta, throughput, utilizzazione del sistema, percentuale di banda utilizzata…). Le misure vengono effettuate tramite benchmark, i cui test possono dare risultati molto differenti a seconda di quello che fanno. La misura può variare a causa della dinamicità del sistema. Scalabilità di un Sistema Distribuito: Come sarebbe Internet se… • i servizi di posta elettronica fossero gestiti da un unico server (componenti centralizzati)? • la risoluzione dei nomi dei domini (DNS) fosse fatta mediante un’unica tabella centralizzata (tabelle centralizzate)? • l’ instradamento (routing) avvenisse mediante informazioni complete (algoritmi centralizzati)? In un sistema distribuito: nessuna macchina possiede informazioni complete sullo stato del sistema; ciascun componente decide con le informazioni che possiede; il guasto di un sistema non pregiudica l’intero sistema; non esiste nessun meccanismo globale di misurazione del tempo. Confronto tra Sistemi: Caratteristica DOS NOS Middleware Grado di trasparenza alto basso alto Stesso SO sui nodi si no no Copie del SO N N N Comunicazione messaggi file dipende Gestione delle Risorse globale, distribuita per nodo per nodo Scalabilità moderata si alta Apertura chiuso aperto aperto

IL FILE SYSTEM: Gestione dello spazio libero: risolta in svariati modi. • Il modo basilare è avere una bitmap, in cui ogni bit corrisponde a un blocco (1=libero, 0=occupato). Problema: con un disco da 1Gb con blocchi da 1Kb avrebbe una bitmap da 1Mbittroppo grande per essere interna al sistema operativo. • Si passò a liste linkate di blocchi, che si riferiscono a gruppi di blocchi (clusterizzazione). Allocazione dello spazio: • Contigua: vengono assegnati gruppi di blocchi ad un file se trovo un gruppo di blocchi contigui abbastanza grandi a contenere il file. (con first fit (il primo che trovo) o best fit (il più piccolo di essi))  necessaria deframmentazione frequente

10

SISTEMI OPERATIVI – II parte •

Concatenata: il file è allocato in blocchi sparsi tenendo però traccia dei blocchi allocati in una tabella (FAT). Nella directory sono scritti i blocchi iniziale e finale, e ogni blocco intermedio è collegato tramite puntatore al successivo, fino a EOF.  si spreca poco spazio. Ma se c’è un crash perdo il file o posso avere delle allocazioni incrociate (cross-link). o Variante indicizzata: c’è un blocco che è più importante degli altri, l’Index-Block, che contiene le info su tutti i blocchi allocati per quel file. Ma se perdo l’Index-Block il file è perso. o I-Node: struttura dati Unix. A metà fra concatenata e indicizzata: gli indici sono multipli. In un indice è possibile di solito allocare 1024 blocchi  max.filesize sarebbe 4Mb. Allora si crea una gerarchia di indici: il master-index collega più indici, e ogni indice può allocare 1024 blocchi  In totale avrei una max.filesize elevatissima, anche troppo, e inoltre avrei un grande spreco di blocchi: 1025 indici per un file anche piccolo. La struttura I-Node risolve: contiene un contatore del numero di blocchi allocati, e 4 tipi di puntatori: direct(direttamente a blocchi dati), single indirect(a blocchi indice che puntano direttamente a blocchi dati), double indirect e triple indirect. E’ un’allocazione dinamica e molto efficiente. Se perdo I-Node è molto dolorosa la sua ricostruzione. Gli I-Nodes sono contenuti all’interno di superblocchi, creati all’atto della formattazione. La diversità consente di gestirli in modo differenziato e più accurato. Directory: in Unix sono gestite esattamente come i files (hanno solo un bit flag che le contraddistingue). In altri sistemi sono trattate con schemi di allocazione diversi e hanno una struttura separata. • La struttura basilare è la lista lineare: i tempi di ricerca di un file potrebbero essere molto lunghi se un sottoalbero è molto pieno. • Tabelle Hash: c’è un meccanismo di mapping molto più rapido in esecuzione.

FILE SYSTEM DISTRIBUITI: File System Distribuito (DFS) – implementazione distribuita classico modello time-sharing di file system, più utenti condividono file e risorse di memorizzazione. DFS gestisce insieme strumenti memorizzazione distribuiti. Spazio per memorizzazione gestito da DSF è composto da spazi più piccoli, distinti e remoti. Di solito c’è corrispondenza tra spazi di memorizzazione e insiemi di file. Struttura dei DFS Servizio – entità software che funziona su un o più calcolatori che fornisce funzionalità a client non noti a priori. Server – servizio software in esecuzione su singola macchina. Client – processo che richiede servizio mediante insieme di operazioni (interfaccia client; un i.c. per un servizio di file consiste in insieme di operazioni primitive su file (creazione, cancellazione, lettura, scrittura). Un interfaccia client di un DFS non dovrebbe fare distinzione tra file locali e remoti. Nominazione e trasparenza Nominazione – corrispondenza tra oggetti logici e fisici. Mapping multilivello – astrazione di un file che nasconde informazioni su come e dove è memorizzato lo stesso file. DFS trasparente – nasconde collocazione fisica nella rete dove il file è memorizzato. Per un file replicato in più siti la corrispondenza ritorna un insieme di locazioni delle copie (esistenza delle copie e loro locazione rimane nascosta). Strutture di nominazione Trasparenza della locazione – nome del file non rileva la locazione fisica. - nome del file determina uno specifico e nascosto insieme di blocchi su dischi fisici; - utile strumento per condividere dati; - rileva corrispondenza tra componenti e computer. Indipendenza della locazione – nome del file non deve cambiare quando muta la sua locazione fisica. - migliore astrazione del file; - promuove condivisione di spazio fisico di memorizzazione; - separa gerarchie di nominazione da quelle degli strumenti di memorizzazione. Schemi di nominazione – tre approcci principali - nomi dei file scelti in funzione di una combinazione del nome host su cui risiedono e nome locale del file; garantisce nome unico in tutto il sistema; - directory remote attaccate a quelle locali in modo da avere l’apparenza di un albero coerente di directory; accesso trasparente possibile solamente a directory remote montate precedentemente; - integrazione totale dei file system componenti:

SISTEMI OPERATIVI – II parte

11

o singola struttura dei nomi trasversale rispetto a tutti i file nel sistema; o se un server non è disponibile un insieme arbitrario di directory su macchine differenti diventa di conseguenza non disponibile. Accesso a file remoti Riduzione di traffico in rete mediante memorizzazione in cache locale di blocchi di disco usati recentemente in modo che accessi ripetuti alla stessa informazione sono gestiti localmente; - se dati richiesti non presenti in cache, una copia viene mandata dal server all’utente; - accessi avvengono su una copia in cache; - file identificati da copia master sul server, e copie (parti) del file distribuite su cache differenti; - problema del cache – consistency: mantenere consistenti le copie con il file master. Locazione della cache-disco vs. memoria principale Vantaggi cache su disco: - più affidabile; - dati contenuti in cache su disco non persi durante operazioni di ripristino. Vantaggi cache in memoria centrale: - implementabile su computer senza disco; - accesso più veloce ai dati; - aumento prestazioni per grandi memorie; - cache su server (usate per velocizzare I/O su disco) in memoria centrale, indipendentemente dalla collocazione cache utente; permette di usare singolo meccanismo di caching per server e utenti. Politica di aggiornamento cache Scrittura diretta: scrittura diretta dei dati su disco non appena modificati in cache; molto affidabile, ma scarse prestazioni. Scrittura ritardata: modifiche scritte in cache e più tardi sul server. Accessi in scrittura completati rapidamente; dati possono essere sovrascritti prima di essere scritti. - poco affidabile, dati non scritti persi ogni volta che macchina utente si guasta; - variante – esaminare cache regolarmente e scrivere blocchi modificati dall’ultimo esame; - variante – scrittura su chiusura: scrivere dati sul server quando server viene chiuso; vantaggioso per file aperti a lungo e modificati spesso. Coerenza Copia dati in cache coerente con copia master? Approccio iniziato dal client: client inizia controllo validità; server controlla se dati locali coerenti con master. Approccio iniziato dal server: server registra per ciascun client parti del file sottoposto a caching; quando individua incoerenza reagisce. Confronto tra caching e servizi remoti Numero alto di accessi remoto può essere gestito dalla cache locale; maggior parte di accessi remoti gestita velocemente quanto accessi locali. Server contattati occasionalmente nel caching (invece che ad ogni accesso): riduzione carico del server e traffico di rete; aumento potenziale di scalabilità. Metodo di servizio remoto gestisce ogni accesso remoto attraverso la rete (penalizzati traffico di rete, carico server e prestazioni). Overhead totale di rete legato a trasmissioni di grandi quantità di dati (caching) è inferiori a serie di risposte a specifiche richieste (servizio remoto). Quando scritture non continue caching superiore. Per scritture frequenti considerevole overhead per superare problema della coerenza. Per usufruire benefici caching esecuzione deve essere su dischi locali o grandi memorie centrali. Accesso remoto a macchine senza dischi, con memoria ridotta dovrebbe avvenire mediante metodo di servizio remoto. Interfaccia tra macchine differente da interfaccia utente. Nel servizio remoto interfaccia tra macchine uguale interfaccia tra utente e file system. Servizio con informazioni di stato Meccanismo: client apre file; server preleva dal disco info su file, registra in propria memoria fisica, da al client identificativo di connessione, unico per client e file aperto; identificativo utilizzato per accessi futuri, fino al termine sessione; server reclama spazi di memoria utilizzati dai client che non sono più attivi. Maggiori performance: minor accesso al disco; server con info di stato sa se file è aperto per accesso sequenziale e può leggere blocchi successivi. Servizio senza informazioni di stato Evita informazione di stato rendendo ogni richiesta autosufficiente; ogni richiesta identifica file e posizione nel file, per accessi in lettura e scrittura; non server stabilire apertura e chiusura connessione per operazioni di apertura e chiusura.

12 SISTEMI OPERATIVI – II parte Distinzioni tra servizi con/senza informazioni Ripristino dai guasti: in caso di guasto, server con info di stato perde tutto il suo stato (è volatile). Recupero mediante protocollo di ripristino basato su dialogo tra client, oppure mediante terminazione in abort delle operazioni in corso. Server deve essere informato dei guasti dei client per poter reclamare spazio allocato e registrare stato dei processi dei client guasti (rilevamento ed eliminazione degli orfani). Nei server senza info di stato gli effetti di un guasto passano inosservati. Un server appena ripristinato risponde alle richieste del client senza difficoltà. Penalità con uso di servizio senza stato robusto: messaggi più lunghi, elaborazione richieste più lenta, ulteriori vincoli al progetto del DFS. Alcuni ambienti chiedono servizi con info di stato: server che utilizzano validazione cache (conserva record di quali file sono in cache in quali client). UNIX usa descrittori file e offset impliciti intrinsecamente con info di stato; server devono conservare tabelle con corrispondenze tra descrittori e inodes, e memorizzare offset corrente del file. Replicazione file Repliche dello stesso file sono su macchine i cui guasti sono indipendenti. Migliora disponibilità, riduce tempi di servizio. Schema di nominazione fa corrispondere nome replicato a particolare replica (esistenza di repliche invisibile a livelli superiori, repliche differenziate da nomi di livello inferiori differenti). Aggiornamenti: repliche di un file indicano stessa entità logica, aggiornamento di una deve riflettersi sulle altre. Replicazione su richiesta: lettura di una replica non locale causa caching locale, generando nuova replica non primaria. Esempio NFS – Network File System Sviluppato da SUN anni ’80 (RFC1094), permette mount di file system su rete TCP/IP, permettendo condivisione di risorse in reti locali eterogenee; protocollo stateless, ogni transazione è un’unità completa in sé (come http). Tre componenti fondamentali: TCP/IP, computer servente deve esportare sottoalbero in /etc/exports, computer client deve importare sottoalbero esportato in /etc/fastab al boot oppure con mount. Distinzione tra hard e soft mount. NFS – implementazione - il S.O. fa parsing path e scopre se file locale o remoto; - se remoto chiede file handle a server (mount / lookup); - file handle contiene #device, #inode, access bit relativi a file system server dove si trova il file; - read: da file handle server apre file: usa lseek per posizionarsi a offset; legge caratteri desiderati e li rende al client; - read ahead: lato client chiede nuova read a terminazione precedente; se codice processo ne ha bisogno dati disponibili subito. Esempio – CORBA - CORBA (Common Object Request Broker Architecture) offrre un approccio basato su oggetti alla costruzione di sistemi distribuiti, come anche Microsoft DCOM e diversamente dal DCE. - Permette a oggetti presenti su un computer locale di richiamare i metodi di oggetti che si trovano su computer remoti. - Diversamente da DCOM, CORBA è uno standard aperto. - CORBA utilizza oggetti accessibili attraverso ORB (Object Request Broker), i quali sono utilizzati per collegare oggetti tra loro in rete. - L’interfaccia del client verso ORB è uno stub scritto in IDL (Interface Definition Language), il quale agisce come un proxy dell’oggetto remoto. - L’interfaccia del server verso ORB è un IDL model (ossia un meccanismo indipendente dal linguaggio per accedere all’oggetto remoto) - Vantaggio: IDL indipendente dal linguaggio di sviluppo. Esempio – ANDREW - Ambiente di calcolo distribuito in fase di sviluppo dal 1983 presso la Carnegie-Mellon University. - Andrew è altamente scalabile; il sistema è progettato per comprendere più di 5000 workstation. - Andrew distingue tra client (workstation) e server dedicati. I server e i client utilizzano lo UNIX BSD e sono collegati mediante LAN. - I client vengono presentati con uno spazio dei nomi partizionato: uno spazio dei nomi locali ed uno dei nomi condivisi.

13 I server dedicati, detti Vice, presentano lo spazio dei nomi condivisi ai client come una gerarchia di file omogenea e indipendente dalla locazione. Lo spazio dei nomi locali è la radice del file system della workstation da cui discende lo spazio dei nomi condivisi. Le workstation utilizzano il protocollo Virtue per comunicare con i Vice e devono possedere dischi locali per memorizzare lo spazio dei nomi locali. L’insieme dei server è responsabile della memorizzazione e gestione dello spazio dei nomi condivisi. Client e server sono strutturati in cluster interconnessi da una LAN. Un cluster consiste di una collezione di workstation e un cluster server è connesso alla WAN tramite un router. Un meccanismo chiave scelto per le operazioni su file remoti è il caching completo dei file. L’apertura di un file causa il suo caching completo sul disco locale. I volumi di Andrew sono unità componenti associate con i file su un singolo client. Un fid identifica un file o una directory del Vice. Un fid è lungo 96 bit ed è costituito da tre elementi della stessa lunghezza: o Numero di volume o Numero di vnode– indice in un array contenente gli inode dei file in un singolo volume. o Unicizzatore– permette il riuso dei valori di vnode, mantenendo le strutture compatte. I Fid sono trasparenti alla locazione, quindi gli spostamenti di un file da server a server non invalidano il contenuto della directory che si trova nella cache. Le informazioni sulla locazione sono mantenute in termini di volumi e l’informazione replicata su ciascun server. Andrew effettua il caching degli interi file dal server. Un client interagisce con i Vice solo all’atto dell’apertura e della chiusura dei file. Venus – effettua il caching dei file dai Vice quando sono aperti e memorizza le copie modificate dei file quando vengono chiusi. Lettura e scrittura dei byte del file sono effettuate dal kernel senza intervento di Venus sulla copia cache. Venus effettua il caching del contenuto delle directory e dei link simbolici, per la traduzione percorsonome. Eccezioni alla politica di caching sono le modifiche alle directory che sono fatte direttamente sul server responsabile per quella directory. I processi client si interfacciano al kernel di UNIX mediante le chiamate di sistema standard. Venus esegue la traduzione percorso-nome componente per componente. Il file system di UNIX viene usato come un sistema di memorizzazione a basso livello sia dai server, sia dai client. La cache del client è una directory locale sul disco della workstation. Sia i processi di Venus, sia quelli del server accedono al file system UNIX attraverso gli inode per evitare le costose routine di traduzione percorso-inode. Venus gestisce due cache separate: o Una per lo stato o Una per i dati Algoritmo LRU utilizzato per mantenere limitata la grandezza di entrambe. La cache dello stato viene mantenuta nella memoria virtuale, per permettere un rapido servizio delle operazioni di stat (stato del file). La cache dei dati è residente sui dischi locali, ma il buffering dell’I/O di UNIX effettua un caching dei blocchi del disco in memoria in maniera trasparente per Venus.

SISTEMI OPERATIVI – II parte

-

-

-

Università degli Studi di Trieste Piazzale Europa 1, 34100 Trieste Facoltà di INGEGNERIA Corso di Laurea in INGEGNERIA INFORMATICA Anno Accademico 2005/2006

Sistemi Operativi

Studente: Giorgio Davanzo [email protected]

Docente: Prof. Enzo Mumolo