Sistemi Operativi PDF - Domenico Siciliani - Ingegneria Informatica PDF

SISTEMI OPERATIVI Autore: Domenico Siciliani ANNO ACCADEMICO 2017/2018 INGEGNERIA INFORMATICA E DELL’AUTOMAZIONE Esame conseguito con voto: 27/30 Teoria dei Sistemi Operativi 1.Sistema operativo: insieme di programmi che gestiscono l’hardware del computer, cioè ricevute richieste di risorse concorrenti tra loro, decide come assegnarle agli applicativi utenti richiedenti. Quindi funge da tramite tra l’utente e l’hardware del computer. È un programma sempre in esecuzione (detto kernel) Sistemi mainframe, per la gestione di applicazioni commerciali e scientifiche, si dividono in: - sistemi a lotti. Gestiti con terminali. L’utente dava all’operatore un job da eseguire sulla macchina (ES. in schede perforate) e quando era pronto il risultato, glielo si consegnava. S.O. passa solo il controllo da un job al successivo. CPU spesso a riposo perché molto più veloce dei dispositivi meccanici di I/O. Job raggruppabili in lotti (batch) con necessità simili, da far eseguire insieme, per velocizzare l’esecuzione; - sistemi multiprogrammati: si mantengono più job in memoria così se quello in esecuzione deve attendere un evento (ES: operazione di I/O), la CPU viene allocata ad un altro job anziché rimanere a riposo. Bisogna sapere quali e quanti job caricare in memoria (job scheduling) e quale tra quelli caricati far eseguire dalla CPU (CPU scheduling); - sistemi time-sharing: Si assegna ad ogni processo utente in memoria una porzione di tempo e allo scadere di tale tempo la CPU viene allocata al processo dell’utente successivo, evitando così la messa in riposo della CPU in caso di attesa di operazioni di I/O. Commutazione tra utenti è rapida, dando all’utente l’impressione che il sistema sia totalmente dedicato ad ognuno di loro. Il S.O. è interattivo poiché c’è uno scambio di informazioni tra utente e processo durante l’esecuzione. Sistemi desktop: devono massimizzare uso CPU, comodità e velocità di risposta. Sono collegati tra loro in reti, quindi va gestita anche la protezione dei file; Sistemi multiprocessore: detti sistemi paralleli o con processori strettamente accoppiati, più processori che comunicano tra loro e che condividono le risorse del computer (ES: memoria), con tre vantaggi: 1) maggiore quantità di elaborazioni eseguibili, che viene ridotta però dalla gestione delle risorse condivise; 2) economia di scala, un computer multiprocessore costa meno di più computer monoprocessore; 3) aumento di affidabilità, il guasto di un processore non blocca il sistema, che diventa fault tolerant Si dividono i due tipi: multiprocessore simmetrico (SMP), in cui ogni processore (paritetici) esegue una copia del S.O. che comunica con le altre copie quando necessario, e multiprocessore asimmetrico, in cui un processore principale (master) organizza e gestisce il lavoro dei processori secondari (slave). Il carico di lavoro va ben ripartito tra le CPU. Sistemi distribuiti: detti sistemi (con processori) lascamente (debolmente) accoppiati, reti di computer ovvero insieme di processori che non condividono memoria e clock. Necessitano di una connessione di rete per funzionare. Si usano protocolli per definire utilizzo, numero di componenti inseribili e per proteggere i dati durante il trasferimento. Si dividono in sistemi client-server, in cui il server fornisce i servizi richiesti dal client (collo di bottiglia è il server), e sistemi peer-to-peer, in cui i nodi del sistema possono agire sia da client che da server, più efficienti perché i servizi possono essere forniti da più nodi (nessun collo di bottiglia). Sistemi cluster: computer collegati tramite rete LAN che condividono la memoria di massa. Affidabili in quanto continuano a erogare il servizio anche se una macchina si guasta. Macchina controllore analizza il comportamento della macchina controllata e la sostituisce se si guasta. Si divide in: cluster simmetrico, in cui le macchine erogano servizi e si controllano a vicenda sfruttando tutto l’hardware disponibile (SAN), cluster asimmetrico, in cui una macchina esegue l’applicazione e l’altra è in stato di attesa a caldo e la controlla, entrando in funzione solo se il server controllato si guasta. Sistemi real-time: usati quando si deve completare le operazioni in tempi prefissati. Si dividono in: hard real-time, che terminano compiti critici in tempi prefissati e usano memorie volatili o di sola lettura per guadagnare velocità, non mischiabile con i S.O. general pourpose perché questi tendono a separare utente e hardware introducendo incertezza sui tempi di esecuzione; soft real-time, in cui si dà priorità massima ai processi critici in modo da terminarle il più velocemente possibile senza imporre un tempo massimo di completamento, mischiabile con S.O. general pourpose. Sistemi palmari: usati in dispositivi di ridotte dimensioni con hardware poco prestante, per non usare batterie troppo ingombranti. S.O. e app non devono penalizzare la CPU (lenta) e devono essere ottimizzati per display piccoli. Collegabili via wireless alla rete o via cavo al PC. Vantaggiosi perché comodi e portabili. Tecnologie web e alte velocità di connessione via Internet permettono accesso remoto ai sistemi. Serve firewall per garantire la sicurezza. Computer embedded usano S.O. real-time e hanno hardware e prestazioni limitate, con interfaccia limitata o inesistente. Dati multimediali, rispetto a quelli tradizionali, vanno trasmessi in modo continuo e con vincoli temporali. 2. Funzionamento del computer: CPU e dispositivi di controllo delle periferiche di I/O concorrono per l’accesso alla memoria. Programma di bootstrap, salvato in una ROM, avvia e inizializza le funzioni del sistema. Carica il kernel del S.O. che esegue il primo processo e attende eventi. I moderni S.O. sono interrupt driven, ovvero gli eventi sono segnalati da un interrupt che può essere hardware, segnale alla CPU generabile in qualsiasi momento, o software, generabile eseguendo una chiamata di sistema. Il vettore degli interrupt contiene gli indirizzi di partenza di tutte le routine di gestione dell’interrupt (interrupt handler), a cui fa riferimento il S.O., in cui sono definite le azioni da eseguire per gestire ogni tipo di interrupt verificabile. Prima di lanciare la routine, va salvato l’indirizzo che ha chiamato l’interrupt, oltre che lo stato della CPU, in modo da poter riprendere l’operazione in corso una volta terminata la routine. Un processo chiede l’intervento del S.O. eseguendo una chiamata di sistema. Polling (scansione degli interrupt): si effettua una scansione dei dispositivi, interrogando ognuno e cercando una conferma su una eventuale richiesta di interrupt inviata. Quando un dispositivo che ha generato un interrupt viene interrogato, invierà una conferma la processore e quest’ultimo avvierà la routine di gestione dell’interrupt relativa a tale dispositivo. Definendo la sequenza di scansione, si definisce anche la priorità di ogni dispositivo. Questa attività spreca molto tempo di CPU rallentando l’intero sistema (CPU in busy waiting: attende il verificarsi di una certa condizione e lo fa verificando periodicamente se è stata soddisfatta). Struttura dell’I/O: ogni controller di un dispositivo I/O mantiene i dati utili in un buffer e registri speciali. CPU per avviare operazione di I/O modifica i registri del relativo controller comunicando che operazione eseguire (R/W). Quando termina l’operazione, il controller per avvisare la CPU gli invia un interrupt. La chiamata I/O può essere: sincrona (bloccante), eseguita con un interrupt software che restituisce il controllo al processo solo al termine dell’operazione di I/O; asincrona (non bloccante), eseguita con un interrupt hardware che restituisce il controllo al processo senza aspettare il completamento dell’operazione. Per implementare l’attesa, alcuni computer hanno l’istruzione wait che mette in attesa la CPU fino al prossimo interrupt, gli altri usano un wait loop realizzato via software con una jump che salta sempre alla stessa posizione, potendo variare lo stato solo al verificarsi di un interrupt. Le chiamate sincrone possono essere eseguite una alla volta quindi il S.O. sa quale dispositivo richiede l’interrupt ma durante l’attesa non è possibile eseguire altre operazioni. Nel caso asincrono la CPU può svolgere altre operazioni durante l’operazione di I/O, quindi si guadagna efficienza, ed eventualmente si esegue una chiamata di sistema per avvisare il processo del completamento dell’operazione di I/O. La Device Status Table indica, per ogni dispositivo, il tipo, l’indirizzo e lo stato attuale. Se all’arrivo di una richiesta il dispositivo è occupato, la si inserisce nella relativa coda d’attesa. Il S.O. gestisce le info nella tabella, elabora in ordine le richieste in coda e restituisce il controllo al processo in attesa al termine dell’operazione oppure all’attività in corso prima dell’interruzione. Molti dispositivi I/O chiedono poco tempo di CPU e tanto per il trasferimento dati, quindi alle operazioni di I/O è data una bassa priorità. Invece, per i dispositivi di I/O ad alta velocità si usa il DMA (Direct Memory Access), con cui si spostano blocchi dati senza l’intervento della CPU, che può eseguire nel frattempo altre operazioni. Così si genera un interrupt a blocco e non a byte. La memoria può trasferire una sola parola per volta quindi il DMA ruba cicli di memoria alla CPU, quindi potrebbe rallentarne l’esecuzione. Struttura della memoria: Oltre alla memoria centrale RAM, in cui risiedono i programmi da far eseguire alla CPU, solitamente i computer sono dotati di una memoria secondaria in cui dati e programmi risiedono in maniera permanente (ES: disco magnetico). I dispositivi di I/O possono trasferire dati dai propri registri alla memoria centrale con istruzioni speciali oppure si usa la struttura I/O memory mapped, in cui blocchi di indirizzi della memoria puntano ai registri del controller del dispositivo, detti porte di I/O. La CPU quando vuole inviare dei byte, ne scrive uno nel registro dei dati e setta il bit nel registro di controllo per avvisare che il byte è disponibile, il dispositivo prende il byte, azzera il bit di controllo segnalando alla CPU che è pronto per il prossimo byte e così via. Col Programmed I/O la CPU interroga ciclicamente il bit di controllo, mentre con il trasferimento I/O interrupt driven, CPU riceve un interrupt quando il dispositivo è disponibile. Disco magnetico: ogni piatto del disco circolare ha un profilo piano e circolare e le due superfici ricoperte da un materiale magnetico. Le informazioni vengono memorizzate registrandole magneticamente sui piatti. Una testina sfiora la superficie di ogni piatto ed è fissata a un braccio del disco che sposta insieme tutte le testine. La superficie di un piatto è divisa logicamente in tracce circolari, a loro volta divise in settori. L’insieme delle tracce che si trovano sotto un braccio formano un cilindro. La velocità del disco dipende dal il tasso di trasferimento (frequenza con coi fluiscono i dati tra il lettore e il computer) e tempo di posizionamento= tempo di seek (per spostare il braccio dalla traccia di partenza a quella di destinazione) + tempo di latenza (per ruotare il disco affinché la testina raggiunga il settore voluto). Caduta della testina: testina tocca la superficie del disco che si danneggia, anche se protetta da un sottile strato protettivo, in genere in maniera irreparabile. Un drive o lettore di dischi viene collegato a un computer tramite cavi chiamati I/O bus (ES: EIDE, ATA, SCSI). Per operare sul disco, il S.O. invia un comando al controller dell’interfaccia, tipicamente con le porte di I/O memory mapped, che invia poi i comandi al controller del disco che li esegue. Coerenza della cache: problema solitamente risolto via hardware, in cui si fa in modo che le cache e i registri delle CPU (in un ambiente multiprocessore) abbiano tutti la stessa versione dei dati contenuti. Protezioni hardware: S.O. multiprogrammati devono assicurarsi che un programma errato non causi il malfunzionamento anche degli altri programmi. Si usano due modalità di funzionamento: utente (bit di modalità=1) e supervisore o controllo (bit di modalità=0). Il caricamento del S.O. all’avvio è eseguito in modalità supervisore, poi si passa alla modalità utente. Ogni volta che il controllo passa al S.O. (ES: per gestire gli interrupt) si passa alla modalità supervisore e prima di dare il controllo all’utente si passa sempre alla modalità utente. Si indicano alcune istruzioni privilegiate, eseguibili solo in modalità supervisore. Un processo chiede al S.O. l’esecuzione di tale istruzioni eseguendo una chiamata di sistema, trattata come un interrupt software. Il S.O., ricevuta la richiesta, verifica che i parametri ricevuti siano corretti e legali, altrimenti l’hardware genera una trap passando il controllo al S.O., come se fosse un interrupt, che genererà un messaggio d’errore. Le operazioni di I/O sono le più pericolose (ES: accesso a locazioni di memoria di altri processi o del S.O.) quindi sono definite con istruzioni privilegiate. Per evitare che un processo non riesca mai a controllare il computer in modalità supervisore, va protetto il vettore degli interrupt in modo che i processi non possano modificare le routine in esso contenute. Inoltre va protetto il S.O. dall’accesso di altri programmi e proteggere i programmi l’uno dall’altro. Si definisce quindi un range di indirizzi legali a cui un programma può accedere, proteggendo lo spazio di memoria degli altri. Si usa un registro base, in cui si inserisce il primo indirizzo legale della memoria fisica, e il registro limite, in cui si inserisce la dimensione del range di indirizzi. Tali indirizzi sono modificabili solo con istruzioni privilegiate. Per evitare che un programma trattenga la CPU per un tempo infinito si usa un timer, decrementato ad ogni colpo del clock dal S.O. e quando arriva a 0 si genera un interrupt, passando il controllo al S.O. che genera un errore o assegna al programma più tempo. Timer usato anche per il time sharing: lo si setta ad un certo quanto di tempo (time slice) che una volta scaduto passa il controllo al S.O. che esegue il cambio di contesto in cui, tra le altre cose, salva l’attuale contenuto dei registri, le variabili e i buffer, somma il time slice al tempo totale di utilizzo della CPU del processo e modifica i parametri per il funzionamento del programma successivo a cui il S.O. provvederà a fornirgli il controllo e che potrà proseguire da dove si era interrotto. Timer usabile anche per calcolare tempo corrente rispetto a un certo valore iniziale. Se il computer è usato da più utenti e può eseguire più processi in contemporanea, va definito un meccanismo di controllo di accesso alle risorse tramite credenziali, che indicano quali risorse fornire per ogni caso. 3. Processo per eseguire le proprie attività necessita di risorse che gli vengono allocate quando è creato o durante l’esecuzione. Può essere a singolo flusso di attività (single-thread), con un solo program counter che indica alla CPU l’istruzione successiva fino al suo termine, oppure a più flussi di esecuzione (multithreaded), ognuno con un proprio program counter che indica l’istruzione successiva. Processi associati allo stesso programma sono trattati come l’esecuzione di codici separati e avranno sezioni dati differenti. Memoria centrale è vista come un vettore di parole a cui possono accedere direttamente CPU e dispositivi di I/O, su cui vanno caricati i programmi da eseguire. File è l’unità logica di memorizzazione delle info, mappati in supporti fisici e organizzati in directory. Per ogni utente va deciso se e come può accedervi. Memoria secondaria (disco) su cui salvare i dati della memoria centrale, usata quindi come sorgente e destinazione dal processo in esecuzione. Interprete dei comandi è un programma del S.O. che funge da interfaccia tra utente e S.O. L’utente impartisce ordini tramite istruzioni di controllo che vengono da esso lette e interpretate, perciò è anche detto interprete delle istruzioni di controllo o shell, che è sempre in attesa del prossimo comando da eseguire. Può essere grafica (user-friendly) o a caratteri (più complessa ma più potente). I comandi possono essere oggetti eseguibili (insieme di operazioni), comandi precostruiti (built-in, azioni semplici) e comandi batch (svolgono azioni in blocco). Chiamate di sistema fungono da interfaccia tra un processo e il S.O., in genere disponibili come istruzioni assembler, eseguibili sia in runtime che in linea. In C e C++ si eseguono direttamente mentre in java si usano metodi nativi (metodi java che chiamano metodi C che eseguono la chiamata). I compilatori forniscono librerie che ne agevolano l’uso. Programma può passare parametri al S.O. nei registri, in un blocco (con indirizzo del blocco in un registro) o in uno stack (memoria provvisoria). Struttura (architettura) del S.O. S.O. sistema complesso, diviso in piccole parti per facilitarne le modifiche. - struttura semplice: minima organizzazione gerarchia per garantire massima funzionalità nel minor spazio. ES: MS-DOS non ben diviso in moduli (applicativi possono accedere direttamente all’hardware), quindi vulnerabile a programmi errati che possono causare blocchi completi; - struttura monolitica: usata in UNIX, in cui il livello dei programmi utente si interfaccia col modulo del S.O. costituito dai programmi di sistema e dal kernel. Quindi è presente un’enorme quantità di funzionalità in un solo livello. - struttura a strati: (OS/2) composta da N livelli modulari. Allo 0 c’è l’hardware, all’N c’è l’interfaccia utente. Ogni strato ha funzioni ben definite. Errori facili da trovare perché S.O. carica uno strato alla volta. Ogni strato è visto dagli altri come una black box che può chiedere servizi solo ai livelli inferiori. Poco efficiente perché per soddisfare una richiesta può essere necessario attraversare più strati, ognuno che modifica i parametri, che ne richiede altri e che quindi allunga il tempo di risposta alla chiamata di sistema. Si cerca di avere pochi strati con più funzionalità per modularizzare il codice ma ridurre il numero di passaggi tra strati. - struttura a microkernel: (SO Mach) kernel modularizzato, detiene solo le componenti indispensabili (ES: gestione processi, della memoria e IPC) e si implementano le altre come programmi di sistema o utente. S.O. più scalabile, sicuro (meno istruzioni privilegiate) e affidabile (mancanza di servizio non compromette S.O.). Soffre di cali di prestazioni dovuti ad un sovraccarico delle funzioni di sistema. - struttura ibrida: (Mac OS X) migliorano performance, sicurezza e affidabilità. Strati superiori includono ambienti applicativi e servizi che forniscono un’interfaccia grafica alle applicazioni. Sotto c’è il kernel diviso in microkernel Mach che gestisce memoria, RPC, IPC e schedulazione thread, e il kernel BSD che fornisce un’interfaccia a riga di comando, supporto a file e rete e implementa librerie multithreading POSIX. - struttura modulare: (Solaris, Linux, Mac OS X, UNIX) si usa programmazione orientata agli oggetti. Kernel costituito da componenti base e si collega dinamicamente a moduli addizionali durante boot ed esecuzione. Struttura simile a quella a strati, con interfacce protette e definite, ma più flessibile perché ogni modulo può richiamare qualsiasi altro modulo. Simile anche al microkernel in quanto il modulo primario ha solo funzioni basilari e comunica con altri moduli ma più efficiente grazie alla comunicazione diretta tra i moduli. Macchina virtuale: definita a partire dal modello a strati, in cui hardware e kernel sono trattati come un blocco hardware puro. Il computer fisico condivide le risorse per generare macchine virtuali: con CPU scheduling fa credere ad un processo di avere un proprio processore, con la memoria virtuale gli dà una propria memoria, con spooling (gestione asincrona delle operazioni di I/O e dei processi) e file system fornisce lettori di schede e stampanti virtuali, con terminale time-sharing fornisce la funzione di console. Il disco fisico viene diviso in minidisk, spazi logici di dimensione variabile in base alle esigenze delle VM. Vengono anche simulate le modalità di esecuzione utente e supervisore che, in caso di chiamate di sistema, switchano come accade nelle macchine fisiche. La differenza sta nel tempi di esecuzioni delle operazioni, che può essere inferiori se lo spooling è ben sfruttato o superiori in quanto va interpretata ogni azione. Vantaggi: protezione delle risorse, con condivisione realizzata via software implementando un minidisk condiviso tra le VM; VM ottimo ambiente per lo sviluppo di S.O. in quanto le ordinarie operazioni del sistema raramente necessitano l’interruzione dello sviluppo del S.O. durante il tempo di sviluppo. Progettazione e implementazione di un S.O. Vanno definiti subito obiettivi e specifiche. Al livello alto si sceglie hardware e tipo di S.O. Al livello basso si considerano gli obiettivi degli utenti (S.O. user-friendly, affidabile, sicuro e veloce) e gli obiettivi del sistema (facile da progettare, implementare, affidabile, senza errori, flessibile ed efficiente). Tali obiettivi richiedono specifiche non soggette a standard implementativi quindi la progettazione di un S.O. rimane fondamentalmente un’operazione creativa. Politica: cosa fare, soggetta a frequenti variazioni. Meccanismo: come fare qualcosa, si cerca di renderlo indipendente dalla politica in modo da dover ridefinire solo alcuni parametri di sistema. Microkernel implementano primitive quasi indipendenti dalla politica così da aggiungere meccanismi e politiche tramite appositi moduli. In Windows politica e meccanismo sono inglobati nel sistema per rafforzare una visione e una sensazione globale. Applicazioni hanno interfaccia simile poiché sviluppata nel kernel. Si preferisce scrivere i S.O. con linguaggi ad alto livello (C e C++) per poter scrivere il codice in maniera più veloce, più compatta e più facile da capire e ottimizzare. I compilatori inoltre migliorano il codice con la compilazione. Infine il S.O. risulta più portabile. Si ha però una ridotta velocità e maggiori esigenze di memoria. In genere si scrive tutto il S.O. con linguaggi ad alto livello e poi si sostituiscono le procedure che fanno da collo di bottiglia con quelle equivalenti in assembler. Le si identifica con programma di analisi dei log, file prodotti da S.O. e che tengono traccia del comportamento del S.O., utili anche per trovare gli errori e analizzare le prestazioni del sistema. Generazione del S.O. SYSGEN, programma che esegue la generazione del sistema: legge informazioni relative all’hardware della macchina, da un file o fornite dall’amministratore, e che configura il S.O. per funzionare correttamente su tale macchina. Le info da determinare sono: CPU, memoria, dispositivi disponibili, opzioni del S.O. desiderate (ES: tipo di algoritmo di CPU scheduling). Si generano così tabelle e moduli da librerie precompilate che contengono i driver di tutti i dispositivi I/O supportati. Si includono così nel S.O. solo quelli necessari. Oppure si può lasciare tutto il codice nel S.O. e la selezione si fa in esecuzione. Così risulta più pesante ma si adatta facilmente a modifiche hardware. Boot: procedura di avvio del computer, in cui si esegue una porzione di codice, nota come bootstrap program o bootstrap loader risiedente in una ROM, che individua il kernel, lo carica in memoria centrale e ne inizia l’esecuzione. I PC usano un processo a due passi in cui un caricatore d’avvio, installato nel MBR (Master Boot Record), recupera dal disco il bootstrap program del S.O. che a sua volta carica il kernel. 4. Processo: programma in esecuzione, unità di lavoro degli attuali sistemi time sharing, comprendente il codice del programma, program counter, contenuto dei registri della CPU, stack di dati temporanei e sezione dati contenente le variabili globali. Durante l’esecuzione un processo passa tra diversi stati, ovvero le modalità di uso della CPU e delle risorse, e sono: new (creato), run (in esecuzione), wait (in attesa di un evento), ready (pronto e in attesa di essere assegnato ad un processore), terminated (esecuzione terminata). Ogni CPU può eseguire solo un processo alla volta ma un processo può essere in esecuzione su più CPU. New si divide in submit, in cui il S.O. identifica le risorse necessarie a soddisfare la richiesta, e in hold, in cui le richieste vengono ordinate per l’esecuzione in base a criteri di priorità dallo Job scheduler che esegue l’operazione di macroscheduling (si definisce l’ordine di ingresso delle richieste). Verificate in ordine le disponibilità delle risorse, il Job scheduler le inserisce nello stato di ready passando il controllo al Process Scheduler che trasforma le richieste in processi, risiedenti in memoria, costituendo per ognuno il relativo PCB (Process Control Block) contenente le info che permettono di gestire il processo nel ciclo di esecuzione e che vengono aggiornate volta per volta. Il Process Scheduler gestisce la coda di ready, usando criteri di priorità, eseguendo l’operazione di microscheduling (si definisce l’ordine con cui i processi saranno eseguiti). Tali processi necessitano solo della CPU per essere eseguiti. Una volta che questa si libera si effettua il context switching della CPU in cui salva il PCB del processo in stato di run e lo passa in stato di ready, e carica il PCB del processo schedulato per l’esecuzione che passa in stato di run. Il tempo di esecuzione del context switching è puro tempo di gestione che va ridotto ed evitato quanto più possibile. Se un processo deve attendere un evento, il S.O. lo porta nella coda di wait. Dopo aver ciclato tra gli stati del ciclo di esecuzione (run, wait e ready), il processo si conclude transitando nello stato complete. Il PCB di un processo contiene: stato attuale, program counter, registri della CPU, info per CPU scheduling (ES: priorità del processo), info per gestione della memoria centrale (ES: PMT), info per l’accounting (ES: tempo di CPU usato), info sullo stato dell’I/O (ES: lista file aperti). Ogni PCB nella coda ha un campo puntatore al prossimo PCB nella lista. Schedulatore a lungo termine (macroschedulatore): controlla il livello di multiprogrammazione (n° processi in memoria). È eseguito con una frequenza dell’ordine dei minuti. Cerca di creare processi allo stesso ritmo con cui terminano. Bilancia in memoria la presenza di processi I/O bound e CPU bound. Schedulatore a breve termine (microschedulatore): sceglie quale processo eseguire e gli alloca la CPU. Eseguito ogni 100ms. Schedulatore a medio termine: riduce il livello di multiprogrammazione per migliorare la distribuzione dei processi tra CPU bound e I/O bound. I processi rimossi saranno ricaricati in memoria e ricominceranno l’esecuzione da dove si sono interrotti (swap). Operazioni sui processi. Un processo può creare un altro processo (padre-figlio) che a sua volta può creare altri processi creando un albero di processi. Un processo figlio può usare le stesse risorse del processo padre, evitando di sovraccaricare il sistema. Il padre può essere eseguito concorrentemente al figlio o attendere il suo termine. Il figlio può condividere lo spazio di indirizzamento del padre o caricare un nuovo programma. Con la chiamata di sistema fork() il padre crea il figlio facendo una copia del proprio spazio di indirizzamento. Si può eseguire una exec() per caricare un nuovo programma nello spazio di memoria di chi lo esegue. Con wait() il padre si può mettere in coda di wait per attendere il termine del figlio. Con exit() un processo chiede al S.O. di essere terminato e seguirà la deallocazione delle risorse. Anche un padre può terminare un figlio se ha ecceduto nell’uso delle risorse a lui allocate, se la sua attività non è più necessaria, se il S.O. usa la terminazione a cascata: se un processo termina, tutti i figli vanno terminati (Windows). Unix fa adottare i processi figli a Init. Processo zombie: risorse deallocate ma va ancora eliminato il PCB dalla tabella degli stati dei processi. Cattiva gestione della memoria se rimangono allocate risorse a un processo terminato: si può usare il java garbage che elimina dalla tabella le risorse allocate ma senza riferimenti, ma riduce le prestazioni della macchina quindi va usato solo se necessario. Processi cooperanti: processi che condividono dati tra loro. Meccanismo che permette la condivisione delle informazioni (su cui va gestito l’accesso concorrente), la velocizzazione della computazione (dividendo il compito in sotto-attività da eseguire in parallelo, hardware permettendo), la modularità (dividendo le funzioni in più processi o thread), e la convenienza (utente può eseguire più attività in parallelo). Produttore-Consumatore: paradigma per processi cooperanti in cui il processo produttore genera info usate dal processo consumatore (server=produttore, client=consumatore). Va usato un buffer per il passaggio di info tra i due che devono essere sincronizzati per sapere se e quando si può operare su di esso. Buffer illimitato: consumatore può attendere oggetti ma produttore può sempre produrne. Buffer limitato: consumatore attende se buffer è vuoto e produttore attende se buffer è pieno. Comunicazione tra processi: meccanismo IPC (Inter Process Communication) fornito dal S.O. con cui i processi possono comunicare senza condividere dati, solitamente scambiandosi messaggi: send(messaggio) e receive(messaggio). Due processi P e Q possono comunicare se c’è un canale di comunicazione, implementabile fisicamente o logicamente. Implementazioni logiche: - comunicazione diretta: schema simmetrico: sia mittente che destinatario devono conoscere il nome dell’altro processo per comunicare. Le primitive sono così definite: send(P, messaggio) e receive(Q, messaggio). Variante asimmetrica: solo il mittente usa il nome del destinatario mentre il destinatario può anche non conoscerlo. In questo caso si ha: send(P, messaggio) e receive(id, messaggio) (variabile id riceve il nome del processo mittente). Svantaggio: limitata modularità, infatti cambiare l’id di un processo causa la redefinizione di tutti gli altri processi (bisogna cambiare tutti i riferimenti al vecchio id col nuovo). - comunicazione indiretta: tramite mailbox o porte, oggetti in cui si depone ed estrae messaggi con ID univoco (=A). Abbiamo: send(A, messaggio), receive (A, messaggio). Va scelto l’approccio da usare nel caso in cui due processi eseguano receive() sulla stessa mailbox: o si associa una connessione a solo due processi, o si fa in modo che un solo processo per volta possa eseguire una receive(), o il S.O. decide a quale processo consegnare il messaggio. Una mailbox può appartenere ad un processo, che è l’unico che può ricevere i messaggi ma se terminato si perde anche la mailbox, o al S.O., che dovrà creare la mailbox, mandare e ricevere messaggi attraverso di essa e poi cancellarla. Le send() e receive() possono essere bloccanti (sincrone) o non bloccanti (asincrone). Con l’invio bloccante il mittente si blocca finché la controparte non riceve il messaggio mentre con l’invio non bloccante appena invia il messaggio riprende l’attività. Con la ricezione bloccante il destinatario si blocca finché il messaggio non è disponibile mentre con la ricezione non bloccante il processo acquisisce un messaggio valido o nullo se nel momento in cui se lo aspetta non lo riceve. Con send() e receive() bloccanti si ha un rendezvous tra mittente e destinatario. Va bufferizzata la coda in cui i messaggi risiedono momentaneamente. Si può usare un buffer a capacità zero, in cui non ci possono essere messaggi in attesa (invio bloccante), a capacità limitata, in cui c’è un massimo di messaggi contenibili, e a capacità illimitata, numero infinito di messaggi contenibili (mittente non si blocca mai). Comunicazione in sistemi client-server: in genere non si usa la strategia precedente, ma altre: - socket (indirizzo IP/porta): estremi di un canale di comunicazione con cui comunicano due processi in una rete, generando una connessione punto-punto. Il server ricevuta una richiesta sul suo socket dal client, accetta la connessione e inizia a comunicare inviando informazioni al socket client. Server usa well-know- ports (0-1023). Indirizzo IP di loopback (127.0.0.1) è usato dal computer per riferirsi a se stesso e permette a un client e a un server su una stessa macchina di comunicare usando il modello TCP/IP. - RPC (Remote Procedure Call): simile all’IPC ma permette di usare chiamate di procedura tra sistemi usando una connessione di rete. Ogni messaggio è inviato a un demone RPC che ascolta su una porta del sistema remoto e che contiene l’ID della funzione da eseguire con i relativi parametri da passare. Eseguita la funzione, il risultato viene inviato alla controparte tramite messaggi. Il sistema RPC fornisce uno stub al client e al server per ogni RPC da eseguire. Quando il client invia una RPC, il sistema RPC chiama il relativo stub e gli passa i relativi parametri. Lo stub esegue il marshalling dei parametri, traducendoli generalmente in formato XDA (External Data Rappresentation, rappresentazione dei dati indipendente dalla macchina) e invia il messaggio al server. Lo stub del server lo riceve, converte i dati da XDA a una rappresentazione dipendente dalla sua architettura, invoca la corretta procedura e invia il valore di ritorno al client usando la stessa tecnica. Problemi di rete possono far fallire le chiamate RPC o duplicarle. Il S.O. decide se eseguire la RPC al più una volta, in cui il server tiene conto dei messaggi elaborati e ignora quelli ricevuti ma già presenti nello storico, o esattamente una volta, in cui il client esegue periodicamente la chiamata RPC finché non riceve l’ack di riscontro dal server. La porta da usare per il collegamento può essere inserita nel processo richiedente oppure può esser definita dinamicamente usando il demone matchmaker con cui il S.O. del server fornisce al client richiedente la porta su cui fare la richiesta RPC. - RMI (Remote Method Invocation): caratteristica java simile alla RPC, che permette a un thread di invocare un metodo su un oggetto remoto che può essere in una JVM sullo stesso o su un computer remoto connesso alla rete. Con RPC si può usare solo programmazione procedurale perché si possono chiamare solo procedure mentre RMI si basa sugli oggetti quindi si può invocare anche metodi su oggetti remoti. In RPC i parametri delle procedure sono strutture dati mentre in RMI possono essere anche oggetti. Nel client risiedono tanti stub, ognuno rappresentante un oggetto remoto, che creano un parcel (pacco) contenente il nome del metodo da invocare sul server e i parametri da passargli su cui è eseguito il marshalling. Quindi il client effettua la chiamata al metodo, lo stub relativo crea il parcel e lo invia al server dove risiede lo skeleton relativo all’oggetto remoto considerato che traduce i parametri e chiama il metodo desiderato, traduce il valore di ritorno e lo passa al client. Oggetti locali sono passati per valore, remoti per riferimento. 5. Thread: unità di base di utilizzo della CPU che comprende un ID, un program counter, un set di registri e uno stack e condivide con gli altri thread del suo stesso processo la sezione di codice, dei dati e altre risorse del S.O. come i file aperti e i segnali. Processo tradizionale ha un solo thread, quindi può compiere una operazione per volta. ES: web server potrebbe rispondere a una sola richiesta per volta e i tempi di attesa dei client sarebbero molto alti. Creare un processo figlio ad ogni richiesta è troppo oneroso, quindi si usano i processi multithread. Server RPC solitamente multithread: ogni messaggio è gestito da un thread diverso quindi si gestiscono più richieste in modo concorrente. Vantaggi programmazione multithread: riduzione del tempo di risposta (processo può continuare la sua esecuzione poiché solo una sua parte è impegnata), condivisione delle risorse (memoria e risorse condivise tra thread che svolgono attività diverse), economia (Tcreazione processo≈ 30 Tcreazione thread e Tcontext switching processo≈ 5 Tcontext switching thread dato che i thread condividono memoria e risorse), utilizzo di architetture multiprocessore (parallelismo reale: thread eseguiti in parallelo su CPU diverse, nei singlecore parallelismo simulato: CPU commuta rapidamente tra i thread simulando un’esecuzione parallela - time sharing). I thread possono essere gestiti a due livelli diversi: - thread livello utente: gestiti tramite una libreria di funzioni per la creazione, lo scheduling e la gestione, senza nessun intervento del kernel, quindi le operazioni richiedono poco tempo; - thread livello kernel: gestiti direttamente dal S.O., quindi è il kernel che li crea, li gestisce e li schedula perciò tali operazioni sono più lente. Modello multithread: come si relazionano i thread di livello utente con quelli di livello kernel. - modello molti a uno: molti thread utente sono riuniti in un unico thread kernel quindi la loro gestione si fa tramite librerie utente perciò è più veloce, ma l’intero processo si blocca se un thread esegue una chiamata bloccante. Un solo thread utente alla volta può accedere al kernel quindi non si può eseguire più thread in parallelo su più processori; - Modello uno a uno: ogni thread è mappato in un thread kernel. Se un thread fa una chiamata bloccante, gli altri possono essere eseguiti e permette l’esecuzione di più thread in parallelo su più processori. Va però creato un thread kernel per ogni thread utente, potendo ridurre di molto le prestazioni del processo; - Modello molti a molti: molti thread mappati a un numero minore o uguale di thread kernel, compromesso in cui si possono creare tutti i thread utente voluti e i relativi thread kernel possono essere eseguiti in parallelo su più processori. Una chiamata bloccante di un thread permette l’esecuzione degli altri. - Modello a due livelli: variante molti a molti in cui è anche possibile fare associazioni uno a uno. Problematiche relative ai thread. Nei programmi multithread, con una fork() il processo creato può duplicare tutti i thread o solo quello che ha invocato la fork() mentre la exec() funziona come nei processi monothread. In UNIX c’è una fork() che genera un processo monothread, utile quando si fa una exec() perché sarà subito sostituito, e una fork() che duplica tutti i thread, utile se non si usa la exec() dopo. Un thread può essere terminato prima del completamento eseguendo una cancellazione asincrona (un thread termina immediatamente il thread target, rischiando di non riuscire a liberare risorse o lasciare dati in una situazione di inconsistenza) o una cancellazione differita (thread target controlla periodicamente un flag il cui valore gli dice se deve terminare, in modo da farlo in un istante sicuro). In UNIX i processi vengono avvertiti del verificarsi di un evento inviandogli un segnale che vanno poi gestiti. Un segnale può essere sincrono, se consegnato allo stesso processo che ha causato l’evento, o asincrono, se generato da un evento esterno al processo a cui viene consegnato. Un segnale può essere gestito dal gestore di segnali di default (posseduto da ogni segnale ed eseguito dal kernel) o dal gestore di segnali definito dall’utente (funzione definita dall’utente che sostituisce quello di default). In un programma monothread il segnale è sempre consegnato al processo mentre in un multithread va capito a quale thread consegnarlo. Uno sincrono va consegnato solo al thread che lo ha generato. Uno asincrono può essere inviato a tutti i thread (nel caso di terminazione del processo) o ad alcuni o a uno predefinito che si occupa di ricevere tutti i segnali del processo. UNIX permette di definire per ogni thread quali segnali ignorare e quali accettare. I segnali vanno gestiti una sola volta quindi verrà consegnato solo a primo che non lo blocca. Windows non supporta i segnali che possono essere emulati con le APC (Asynchronous Procedure Calls) che permettono a un thread utente di scegliere una funzione da chiamare quando riceve la notifica di un evento. Se un server multithread generasse un thread ad ogni richiesta si spenderebbe tempo per preparare il thread che deve servire la richiesta, poi ogni thread andrebbe terminato una volta soddisfatta la richiesta. Inoltre si potrebbe generare un numero troppo alto di thread che esaurirebbe le risorse del sistema. Si risolve usando un pool di thread creati all’avvio del processo e messi in attesa. Quando il server riceve una richiesta, un thread dal pool viene svegliato, serve la richiesta e poi torna in attesa nel pool. Se non ci sono thread disponibili, la richiesta attende finché se ne libera uno. Il numero di thread nel pool si può scegliere considerando il numero di CPU nel sistema o la memoria fisica disponibile o il numero atteso di richieste concorrenti. Alcune architetture regolano dinamicamente tale numero, riducendolo quando possibile e quindi abbassando il carico sul sistema. Molti sistemi, per decidere quanti thread kernel usare dato un certo numero di thread utente, usano una struttura dati intermedia chiamata LWP (lightweight process) che funge per la libreria dei thread utente come un processore virtuale con cui il processo può schedulare l’esecuzione dei thread utente (schema di comunicazione tra libreria thread utente e kernel noto come attivazione dello schedulatore). In genere si assegna un LWP a thread kernel ma potrebbero servire di più in caso di un uso intenso di chiamate bloccanti. Upcall è la procedura con cui si alloca LWP ad un thread utente, gestita dalla libreria dei thread col gestore di upcall. Il kernel fa una upcall quando il thread sta per bloccarsi, liberando il LWP relativo e potendo così schedulare un altro thread da eseguire su di esso. Il kernel fa poi un’altra upcall quando il thread si sbocca e si rimette in attesa di essere schedulato. Pthread si basano sullo standard POSIX ed è una specifica per il comportamento dei thread, in cui sono definite API per la loro creazione e sincronizzazione, implementabile dai progettisti come desiderano. Sono considerate librerie di thread a livello utente poiché non c’è relazione fra un thread creato usando le API di Pthread e un thread del kernel associato. Usato in Linux, Solaris, UNIX, MacOS X e Windows. 6. L’esecuzione di un processo si alterna tra picci di CPU e picchi di I/O. Processo I/O bound ha molti picchi CPU brevi mentre uno CPU bound ne ha pochi ma lunghi. Terminato il picco di CPU del processo in esecuzione, la CPU si libera e lo schedulatore a breve termine (CPU scheduler) sceglie un processo dalla coda di ready e gli alloca la CPU. Schedulazione è nonpreemptive o volontaria se porta lo stato del processo da run a wait (ES: richiesta I/O) o da run a terminated quindi il processo a cui è stata allocata la CPU la tiene finché non termina o passa in stat di wait. Mentre è preemptive o non volontaria se porta lo stato da run a ready (ES: arriva un interrupt) o da wait a ready (termina I/O) quindi la CPU può essere rilasciata prima del termine di un’operazione in corso, potendo lasciare eventuali dati condivisi in uno stato di inconsistenza. Inoltre il kernel potrebbe essere occupato nello svolgere un’operazione per un processo che sta modificando la struttura stessa del kernel, quindi se il processo venisse terminato ci sarebbe una inconsistenza nel codice del kernel, creando il caos. Per risolvere il problema, molte versioni di UNIX fanno terminare la chiamata o l’operazione di I/O prima di eseguire il cambio di contesto ma così è difficile implementare il modello real-time e elaborare più processi in parallelo. Oppure si può evitare di condividere porzioni di codice soggette ad interrupt. Dispatcher: componente che da il controllo della CPU al processo schedulato, quindi esegue il cambio di contesto, passa alla modalità utente e salta alla corretta locazione del programma per riprenderne l’esecuzione da dove si era fermato. Il tempo per fermare un processo e iniziarne un altro è detto latenza del dispatcher. Criteri di schedulazione: usati per comparare gli algoritmi di schedulazione della CPU - Utilizzo della CPU (sistema a basso carico la usa al 40%, uno ad alto carico al 90%); - throughput (frequenza di completamento, n° processi completati per unità di tempo); - turnaround time (tempo di completamento che va dall’immissione del processo nel sistema alla sua fine); - tempo di attesa (tempo totale che un proceso passa nella coda di ready); - tempo di risposta (tempo che passa dalla richiesta dell’output all’istante in cui il processo inizia a rispondere). Algoritmi di schedulazione: per decidere a quale processo nella coda di ready deve essere allocata la CPU. - FCFS (First Come First Served): il processo che chiede la CPU per primo, la ottiene per primo. Quando un processo entra nella coda dei processi pronti, il suo PCB viene inserito alla fine della coda. È non preemptive, quindi il processo tiene la CPU finché termina o effettua una richiesta di I/O. Il tempo di attesa medio è molto lungo e varia molto cambiando l’ordine di arrivo dei processi. Non usabile nei sistemi time- sharing in cui ogni utente deve avere una porzione di tempo di CPU ad intervalli regolari. Effetto convoglio: ritardo a catena che i processi subiscono dovendo attendere che quello più lungo rilasci la CPU, risolvibile se fosse possibile far eseguire prima i processi più brevi (SJF) o rendendo l’algoritmo preemptive (RR); - SJF (Shortest Job First): appena la CPU si libera, viene assegnata al processo con il più breve picco futuro di CPU. Se più picchi sono uguali si sceglie con FCFS. Può essere sia preemptive (shortest-remaining-time-first, processo in esecuzione viene fermato se arriva nella coda di ready un processo che richiede un tempo di picco di CPU più breve) che nonpreemptive (si lascia terminare il picco del processo in esecuzione). Ottimale perché fornisce il tempo di attesa medio minimo ma non implementabile poichè non si può conoscere la lunghezza del prossimo picco di CPU. Si può approssimare la schedulazione stimando il prossimo picco con una media esponenziale delle lunghezze dei picchi misurati precedentemente: 𝜏𝑛+1 = 𝛼𝑡𝑛 + (1 − 𝛼)𝜏𝑛 , con tn lunghezza ultimo picco registrato, τn storia passata e α parametro tale che 0≤α≤1 che in genere viene posto a ½ per far pesare ugualmente storia passata e ultimo picco. Il valore iniziale τ 0 può essere definito come una costante o considerando le prestazioni del sistema in media. Sviluppando: 𝜏𝑛 = 𝛼𝑡𝑛−1 + (1 − 𝛼)𝜏𝑛−1 e 𝜏𝑛−1 = 𝛼𝑡𝑛−2 + (1 − 𝛼)𝜏𝑛−2 => - schedulazione a priorità: la CPU viene allocata al processo che risulta avere la priorità più alta, se uguale allora si usa FCFS. SJF è un algoritmo con priorità dove la priorità è l’inverso del prossimo picco di CPU previsto: più grande è il picco, più piccola è la priorità e viceversa. Le priorità possono essere definite internamente (considerando ES: numero di file aperti) o esternamente (ES: l’importanza del processo). Può essere sia preemptive che nonpreemptive. È soggetta a starvation: processi a bassa priorità potrebbero attendere per un tempo indefinito. Si può risolvere con l’ageing: si aumenta periodicamente la priorità. - Round-Robin (schedulazione circolare): progettato per sistemi time sharing, è un FCFS con preemption per alternare i processi. Si definisce un quanto di tempo q, tra 10 e 100 ms, che è la durata massima che un processo può tenere la CPU prima che lo schedulatore la allochi al processo successivo in coda che quindi è trattata come una coda circolare. Il tempo di attesa medio è solitamente più lungo di quello del SJF ma si ha un minor tempo di risposta, cosa utile nei sistemi interattivi. Con N processi, ognuno otterrà 1/N del tempo della CPU che sarà lungo al più q. Ogni processo attende al più (N-1)*q unità di tempo prima del suo prossimo quanto. Se q è grande RR degenera in FCFS, se è piccolo viene chiamato processor sharing e da l’impressione ad ogni processo di avere un prcessore con 1/N della velocità di quello reale. Per non ridurre troppo le prestazioni, q deve essere grande rispetto al tempo di context switching (in genere F(Ri). Witness (testimone): software che effettua tale verifica e avvisa se le risorse sono acquisite fuori ordine e quindi il deadlock diventa possibile. Deadlock avoidance: si evita che si possano formare deadlock. La soluzione più semplice è che ogni processo dichiari il numero massimo di risorse di ogni tipo di cui può avere bisogno e si crea una procedura che esamina dinamicamente lo stato di allocazione delle risorse (numero di risorse di disponibili, assegnate e richiedibili dai processi) per accertarsi che la condizione di attesa circolare non si verifichi mai. Il sistema è in uno stato sicuro se esiste una sequenza sicura, ovvero se si possono soddisfare le richieste di ogni processo seguendo un certo ordine che permette di evitare ancora il deadlock. La sequenza di processi è sicura se per ogni i, le richieste che Pi può fare sono soddisfabili dalle risorse attualmente disponibili + le risorse tenute da tutti i processi Pj con jm si verifica il thrashing, perché alcuni processi non avranno abbastanza frame per coprire il proprio working set e il S.O. deve selezionare e sospendere un processo. La finestra mobile usata dal working set è difficile da implementare. Si può approssimare usando un timer che genera interrupt periodicamente e un bit di riferimento. Ricevuto l’interrupt, si copiano i valori del reference bit di ogni pagina, che poi vengono azzerati. Quando si verifica un page fault si esamina l’attuale reference bit e gli n bit tenuti in memoria per pagina. Se almeno 1 è posto a 1 allora la pagina è nel working set. Non è possibile conoscere esattamente quando è stata referenziata la pagina. L’incertezza si riduce aumentando il numero di bit immagazzinabili in memoria e la frequenza degli interrupt, causando però un costo maggiore da sostenere. Un’altra strategia per prevenire il thrashing cosnidera la frequenza dei page fault: superato un valore di soglia, il processo necessita di più frame quindi gliene vengono allocati altri, al di sotto di tale valore gliene vengono tolti. Superata la soglia e in assenza di frame liberi, il processo viene sospeso. Prepaginazione: si carica in memoria centrale tutte le pagine necessarie a un processo. Ottenibile salvando il working set di un processo prima di sospenderlo e quando va ripreso, lo si riporta in memoria. Ci sono diversi fattori da considerare per definire la dimensione delle pagine. Riducendola, aumentano le entry nella PMT e quindi la sua dimensione quindi andrebbero usate pagine grandi. Ma con pagine grandi aumenta la frammentazione interna. Inoltre con pagine piccole si riesce ad aumentare la risoluzione, ovvero a soddisfare con più precisione la località del programma, occupando solo la memoria realmente necessaria. Inoltre si riduce il tempo da usare per le chiamate di I/O avendo in memoria solo i dati necessari. Però pagine piccole potrebbero causare più page fault consecutivi per caricare in memoria tutti i dati necessari. Lo sviluppo storico è verso dimensioni di pagina più grandi. L’hit ratio aumenta all’aumentare delle entry nella TLB che però è una memoria costosa e consuma energia. Hit radio dipende quindi dall’estensione della TLB=n°entry*dim pagina. Dimensione ottimale della TLB consente di contenere il working set di un processo. A parità di entry, l’estensione della TLB si può aumentare aumentando la dimensione della pagina. Si possono usare dimensione di pagina differenti, che soddisfano meglio le necessità dei processi senza aumentare la frammentazione. Si aggiunge quindi in ogni entry della TLB un campo che indica la dimensione della pagina. La gestione della TLB via software ha un costo in termini di prestazioni, compensato però dall’aumento dell’hit ratio e dell’estensione della TLB. I programmatori possono migliorare le prestazioni del sistema se costruiscono codici che tengono conto di come avviene la richiesta di paginazione, anche se questa è progettata per essere trasparente agli applicativi, cercando di operare su parole di una stessa pagina prima di passare a quella successiva. Può essere utile, usando la richiesta di paginazione, bloccare alcune pagine in memoria, ad esempio la pagina contenente un buffer di un processo coinvolto in un’operazione di I/O. Si evita quindi di usare il double buffering che raddoppia il numero di accessi a memoria. Per farlo si associa un bit di blocco a frame che se settato a 1 impedisce ai processi di sceglierlo come vittima per la sostizione, usabile anche per bloccare in memoria pagine del kernel del S.O. se necessario. Utile anche per evitare che una pagina venga sostituita quando è appena stata caricata in memoria e ancora non usata. L’uso del bit di blocco è pericoloso perché può capitare che venga acceso e mai più spento, rendendo il frame bloccato inutilizzabile. Richiesta di segmentazione: usabile se l’hardware è insufficiente per implementare la richiesta di paginazione, in cui la memoria viene allocata in segmenti di cui si tiene traccia attraverso i descrittori dei segmenti, ognuno contenente un validity bit per indicare se il segmento è in memoria e perciò accessibile. 11. File System: fornisce il supporto per la memorizzazione dei dati e dei programmi, composto da due parti: i file, in cui sono memorizzati dati e programmi, e una struttura della directory che organizza l’accesso ai file di tutto il sistema e fornisce informazioni su di essi. File: unità logica di memorizzazione, usata dal S.O. per astrarre le prorietà fisiche del dispositivo e per fornire una visione logica e uniforme della memorizzazione delle informazioni. Solitamente sono mappati in dispositivi fisici non volatili. I dati contenuti possono essere di qualsiasi tipo, possono avere un formato libero (ES: testo) o rigido. In genere un file è una sequenza di byte e record il cui significato è dato dal suo creatore. Struttura: dipende dal tipo di file, definibile dal dal S.O. o dal programma generatore. Nel primo caso il S.O. deve contenere il codice per supportare tali strutture, appesantendosi anche molto. Nel secondo caso il S.O. supporta solo le strutture di base (ES: file eseguibili) e le restanti vengono definite dai programmatori nei programmi che risiedono nel sistema. Al file viene dato un nome per semplificare l’identificazione da parte dell’utente, diventando così indipendente dal processo, dall’utente e dal S.O. che lo ha creato. Tipici attributi di un file: nome (unico in forma leggibile dall’uomo), identificatore (che lo identifica nel file system), tipo, locazione (puntatore alla locazione fisica del file), dimensione corrente, protezione (permessi d’accesso al file), tempo, data e identificativo dell’utente (utili a protezione, sicurezza e controllo ES: data e ora ultimo accesso e modifica). Tali informazioni sono tenute nelle directory che, come i file, risiedono nella memoria secondaria e caricate a pezzi di memoria in base alla necessità. Operazioni su file: eseguibili effettuando chiamate di sistema fornite dal S.O.. Le fondamentali sono: - creazione: S.O. trova spazio nel file system, crea un descrittore nella directory contenente le varie info; - scrittura: utente specifica nome file e info da scrivere. S.O. cerca nella directory del file quello col nome dato e mantiene un puntatore che definisce la posizione (che aggiorna) in cui eseguire la prossima scrittura; - lettura: utente specifica nome file e posizione del record dal leggere. S.O. trova il descrittore associato e maniente un puntatore di lettura che definisce la posizione (che aggiorna) su cui eseguire la prossima lettura; - riposizionamento: S.O. trova il file interessato nella directory e modifica il valore del puntatore alla posizione corrente del file, senza accedere alle info in esso contenute; - cancellazione: S.O. trova il file nella directory col nome passato dall’utente, fa rilasciare tutto il suo spazio usabile poi da altri file e cancella il descrittore della directory relativa a tale file; - troncamento: utente chiede di cancellare il contenuto del file mantenendone gli attributi. S.O. azzera la dimensione del file e rilascia lo spazio da questo occupato in memoria secondaria; Per non eseguire la ricerca del file ad ogni accesso, molti S.O. chiedono che sia effettuata prima la chiamata di sistema open(), con cui prende il nome del file e lo cerca nella directory, e poi salva nella tabella dei file aperti i descrittori dei file attualmente aperti che da allora saranno da lì reperibili senza accedere al disco. Con la open() va definita anche la modalità d’accesso al file (r/w) che verrà aperto solo se tale modalità è permessa. Quando non si vuole più usare il file, questo viene chiuso con la chiamata close() e il S.O. cancella il relativo descrittore dalla tabella dei file aperti. In un ambiente multiutente più utenti potrebbero voler aprire il file nello stesso momento, per questo vengono usate la tabella (dei file aperti) di processo e la tabella di sistema. Quando un file viene aperto, viene caricato il relativo descrittore nella tabella di sistema. Ogni processo che esegue una open() su tale file, aggiunge un nuovo descrittore nella propria tabella di processo che punta al descrittore di tale file nella tabella di sistema che in genere ha anche un contatore di apertura per ogni file, che tiene conto di quanti processi hanno aperto quel file. Ogni close() decrementa tale contatore e quando arriva a 0, il descrittore del file viene eliminato in quanto non più in uso. Molti S.O. riconosco diversi tipi di file, assumendo un comportamento diverso per ognuno. Solitamente il tipo viene incluso nel nome del file sotto forma di estensione. Abbiamo quindi “nome.tipo”. I record del file possono essere di dimensione fissa o variabile e sono solitamente impacchettati in un certo numero di record logici e salvati nei blocchi fisici necessari, ottimizzando così l’impiego della memoria. Metodi di accesso alle informazioni del file: - accesso sequenziale: semplice, le info vengono elaborate in ordine, operando su una porzione di file e facendo avanzare il puntatore alla locazione che contiene la porzione subito successiva. Rewind: riporta il puntatore all’inizio del file. Le chiamate read() e write() non prendono in input il puntatore in quanto la posizione d’accesso è definita dall’operazione precedente. (ES: per file di testo, che hanno record logici di lunghezza variabile); - accesso diretto: usabile per file con record logici di lunghezza fissa. Il file viene visto come una sequenza di blocchi numerati e il programma può accedervi senza seguire un ordine. Usato dai database per leggere il blocco richiesto da un’interrogazione giunta al sistema. Read() e write() vogliono in input l’identificativo del blocco su cui operare. L’utente usa numeri di blocchi relativi che partono da 0 anche se i vari indirizzi assoluti non sono contigui. Questo permette al S.O. di decidere dove allocare il file e ad evitare accessi illegali alla memoria. Accesso sequenziale simulabile in un file ad accesso diretto usando una variabile cp che definisce la posizione corrente, a cui viene sommato 1 quando si vuole operare sul blocco successivo. Simulare l’accesso diretto su un file ad accesso sequenziale invece è estremamente inefficiente. Altri metodi d’accesso basati su quello diretto usano un file indice che contiene i puntatori ai vari blocchi fisici. Per cercare il blocco fisico voluto in tale file si usa in genere un algoritmo di ricerca binaria. È così possibile eseguire una ricerca in un file grande usando poche chiamate di I/O. Per file molto grandi si può creare un file indice primario che contiene i puntatori a più file indice secondari che punteranno ai dati effettivi. Struttura della directory. Partizione: struttura a basso livello con cui si divide un disco e contiene i file e le directory. Si può usare una partizione per separe aree di memoria di un disco, ognuna vista come un dispositivo diverso, oppure per raggruppare più dischi in una sola unità logica. Directory del dispositivo: dove risiedono tutte le informazioni dei file in una partizione, utile al file system per organizzare i file. Operazioni eseguibili su una directory: ricerca, creazione, rinomina e cancellazione di un file e relativo descrittore; elencare i file e i relativi descrittori, presenti in una directory; attraversamento del file system, potendo accedere ad ogni directory e a ogni file in una directory. La directory è organizzata logicamente per fornire efficienza (collocazione più rapida dei file), rinomina (gli utenti possono dare lo stesso nome a file diversi o dare più nomi allo stesso file) e raggruppamento logico (in base alle loro prorietà); Directory a singolo livello: tutti i file sono contenuti in un’unica directory, nessun raggruppamento. Univocità dei nomi difficile da rispettare nel caso multiutente e ricerca lunga e inefficiente. Directory a due livelli: ogni utente ha la propria directory, ognuna che contiene solo i file di un singolo utente quindi migliora l’efficienza delle ricerche. Quando un utente fa riferimento ad un file, questo viene cercato solo nella propria directory quindi più utenti possono avere file diversi con lo stesso nome. È uno svantaggio se più utenti vogliono cooperare in una attività e condividere i file ad essa relativi. Nome del percorso: necessario in tale struttura per identificare univocamente un file, contenente la partizione in cui è presente la directory dell’utente, nome dell’utente(=nome directory) e nome file. Ancora problemi di raggruppamento per l’utente. Directory con struttura ad albero: gli utenti possono creare delle sottodirectory e organizzare i file in essi. L’albero ha la sua directory radice e ogni file ha un percorso univoco che va da essa al file stesso. Le directory quindi sono dei file con funzioni diverse, che vengono identificate come tali usando un bit nel loro descrittore e che vengono gestite con particolari chiamate di sistema. Per cambiare directory corrente è usata una chiamata di sistema che prende come parametro il nome della directory e lo usa per ridefinire la directory corrente. Percorso assoluto: comincia dalla radice e segue il percorso verso il file specificato. Percorso relativo: definisce il percorso a partire dalla directory corrente. Quindi con tale struttura un utente può accedere sia ai propri file che a quelli degli altri utenti. Directory a grafo aciclico: le directory possono condividere sottodirectory e file, quindi un file o una sottodirectory possono trovarsi in due directory differenti e modificandone una, si modificano anche tutte le altre. In UNIX si crea un descrittore chiamato link che è un puntatore ad un file o directory. Questo può semplicemente far seguire il percorso per raggiungere il file reale (soft link) oppure essere lui stesso un descrittore del file reale (hard link), rendendo l’originale indistinguibile dalla copia. Quindi un file può avere più percorsi assoluti, perciò nomi diversi possono riferirsi allo stesso file. Se si effettua la cancellazione rimuovendo il file, i link rimarrebbero appesi e se tale spazio venisse allocato da un altro file, il puntatore porterebbe a tale file. Cancellando un soft link, il file non viene toccato. Cancellando invece un hard link, i suoi collegamenti rimangono pendenti. Si può decidere di eliminarli tutti ma è molto dispendioso oppure si può lasciarli pendenti finché non si prova ad aprirli e allora comunicare che tale file non esiste più e quindi dovrà essere l’utente a cancellarlo. UNIX invece conserva i file finché ci sono hard link riferiti ad esso. Usa quindi un contatore di riferimenti che viene incrementato se viene creato un nuovo hard link e decrementato se ne viene cancellato uno. Quando arriva a 0, il file viene cancellato. Il contatore è tenuto nel blocco delle informazioni del file, detto inode. Directory a grafo generale: grafo aciclico è facile da attraversare (non essendoci cicli) e determinare quando non ci sono più riferimenti a un file. Qui si possono formare cicli per cui si vuole evitare di cercare lo stesso file due volte, ovver entrare in un ciclo. Le directory possono autoreferenziarsi, quindi in caso di cicli il contatore di riferimento piò essere diverso da zero anche se non ci sono più riferimenti a tale file. Garbage collector: percorre tutto il file system e marca ciò che si può raggiungere, cancellando tutto il resto. Tecnica molto dispendiosa, per questo conviene usare un grafo aciclico, ottenibile permettendo di creare link ai soli file e non alle directory. Oppure si usano algoritmi di rilevazione dei cicli, molto costosi computazionalmente. Un algoritmo semplice consiste nell’escludere i collegamenti durante l’attraversamento di tale struttura, evitando quindi di imbattersi in cicli e risparmiando il relativo overhad. Montaggio del file system: operazione da eseguire per renderlo disponibile per i processi nel sistema. Per farlo va fornito al S.O. il nome del dispositivo da montare e il punto di montaggio, cioè una locazione nell’attuale file system a cui quello da montare deve agganciarsi. Tipicamente è una directory vuota. Poi il S.O. verifica che il dispositivo abbia un file system valido e annota nella propria struttura della directory che un nuovo file system è stato montato nel punto specificato ed è possibile così navigare indifferentemente tra i file system contenuti nelle diverse partizioni così collegate. Condivisione dei file: implementabile dal S.O. conservando più attributi per ogni file e directory del caso di un sistema monoutente. S.O. definisce permessi di accesso di default oppure richiede ad ogni utente che definiscano l’accesso ai loro file. Quasi tutti i S.O. usano il concetto di proprietario di file/directory e di gruppi. Nei sistemi distribuiti i file vengono condivisi tramite la rete. Network File System (NFS): protocollo di condivisione presente in UNIX che permette relazioni molti a molti tra server e clienti. Protezione: meccanismi che permettono l’accesso controllato limitando i tipi di accesso ai file seguendo criteri definiti dal proprietario del file, tra cui il tipo di accesso richiesto. Controllabili operazioni di lettura, scrittura, esecuzione, appending, cancellazione ed elenco. In genere si fa dipendere l’accesso dall’identità dell’utente assegnando ad ogni file una ACL (Access Control List) controllata dal S.O. ad ogni tentativo di accesso e l’accesso viene consentito solo se l’utente è autorizzato a effettuare l’operazione voluta. Per ridurre la lunghezza della lista degli ACL si dividono gli utenti in tre tipi: proprietario (che ha creato il file e può cambiarne i permessi di accesso), gruppo (insieme di utenti che condivide l’accesso al file e necessita dello stesso tipo di accesso) e universo (tutti gli altri utenti del sistema). Quindi servono tre campi per definire la protezioni di un file. In UNIX sono definiti 3 campi da 3 bit ciascuno: rwx, per un totale di 9 bit per registrare le informazioni di protezione del file. 12. Struttura del file system. Caratteristiche che rendono un mezzo adatto alla memorizzazione di un file sono: possibilità di riscrivere i file nello stesso posto e possibilità di accedere direttamente a qualsiasi blocco di informazioni sul disco. Per migliorare l’efficienza dell’I/O, i trasferimenti fra memoria e disco sono effettuati in unità di blocchi di settori. Livelli del file system: dispositivi, controller I/O (driver dei dispositivi – dati in input ordini di alto livello fornisce in uscita comandi comprensibili dal dispositivo - , gestori delle interruzioni per trasferire info tra memoria centrale e dispositivi), file system di base (fornisce al controller I/O i riferimenti ai blocchi fisici su cui eseguire le operazioni), modulo di organizzazione dei file (mapping degli indirizzi logici in fisici da trasferire al file system di base), file system logico (gestisce i metadati senza considerare le info contenute nei file, riceve il nome del file e fornisce al livello inferiore le info necessarie per operare. Conserva la struttura di ogni file tramite il FCB (File Control Block) che contiene info sul file considerato come proprietario, permessi e locazione dei blocchi di dati), e programmi applicativi. Realizzazione dei file system. UNIX e altri S.O. trattano le directory come file, con campo tipo che la definisce come tale. La open() passa un nome di un file al file system, si copia il FCB nella tabella dei file aperti del sistema (che contiene il contatore per tener conto del numero di processi che hanno quel file aperto), nella tabella dei file aperti del processo viene creato un puntatore al relativo elemento nella tabella dei file aperti del sistema. Tutte le operazioni sono fatte tramite questo puntatore, detto in UNIX descrittore del file. Quando tutti i processi lo chiudono, viene aggiornata la struttura della directory sul disco con tutte le modifiche ad esso apportate e il relativo elemento nella tabella di sistema viene eliminato. Virtual File System (VLS): interfaccia che permette ad un S.O. di integrare diversi file system, attraverso cui gli utenti possono navigare in modo invisibile. Nasconde le implementazioni dei diversi file system, permettendo di gestirli con un’unica interfaccia. Si interpone tra l’interfaccia di sistema, usata dall’utente per navigare tra i diversi file system e basata sulle chiamate open, read, write e close e sui descrittori dei file, e i vari file system locali e/o remoti. Più realizzazioni di VLS possono coesistere in un S.O., permettendo di accedere in maniera trasparente ai diversi file system montati localmente. Realizzazione della directory. Diversi algoritmi di allocazione e gestione delle directory: - Lista dei nomi dei file che contengono ai relativi blocchi dati, semplice da programmare ma va eseguita una ricerca sequenziale per trovare un file, rallentandone l’accesso; - hash table che prende un valore calcolato a partire dal nome del file ricevuto e restituisce il puntatore al file, riducendo molto i tempi di ricerca nella directory. Vanno gestite situazioni di collisione in cui nomi diversi danno in uscita alla funzione di hash un puntatore allo stesso file, inoltre la gestione di tale tabella si complica a causa della sua dimensione generalmente fissa. Metodi di allocazione: come allocare i blocchi del disco ai file creati e indicizzati dalle directory. - allocazione contigua: caricare file su blocchi contigui sul disco. Allocazione definita con indirizzo blocco di partenza e numero di blocchi allocati. Per accessi sequenziali, il file system ricorda l’ultimo blocco referenziato, partendo quindi dal successivo. Per accessi diretti, per accedere al blocco i del file che comincia dal blocco b, si accede direttamente al blocco b+i. Si usa first-fit e best-fit per scegliere un hole libero, quindi tale metodo soffre di frammentazione esterna. Va anche definita la quantità di memoria da allocare al file, infatti uno spazio troppo piccolo potrebbe impedire al file di essere ampliato ulteriormenti poiché non potrebbero esserci ulteriori blocchi contigui disponibili. In tal caso si interrompe il programma e l’utente deve allocare al file più spazio o bisogna trovare un hole più grande in cui copiarlo. Per migliorare la situazione alcuni S.O. usano uno schema di allocazione contigua modificato, in cui, se lo spazio attuale non riesce più a contenere il file, si aggiunge un altro pezzo di spazio contiguo ovvero un’estensione. Quindi la posizione di un file viene registrata come posizione iniziale e numero di blocchi più un collegamento al blocco dell’estensione successiva. VFS (Veritas File System) usa tale approccio che migliora di molto le prestazioni rispetto all’UFS standard; - Allocazione collegata: ogni file è una lista collegata di blocchi sparpagliati sul disco. La directory contiene un puntatore al primo e all’ultimo blocco del file ed ogni blocco contiene un puntatore a quello successivo. Una scrittura su file causa la ricerca di un qualsiasi blocco libero che verrà allocato e collegato alla fine del file. Per la lettura si legge il file passando di blocco in blocco. Non c’è frammentazione esterna e il file può crescere finché ci sono blocchi liberi. Accesso al file efficiente solo se sequenziale, in quanto per arrivare all’i-esimo blocco bisogna seguire tutti i puntatori fino a raggiugnere quello voluto. Inoltre una porzione di ogni blocco va sprecata per salvare il puntatore al blocco successivo quindi un file pesa più del dovuto. FAT (File Allocation Table): usata in una variante di tale metodo, tabella che viene salvata in una sezione del disco all’inizio di ogni partizione e che contiene un elemento per ogni blocco del disco ed è indicizzata dal numero del blocco. La directory contiene solo il numero del primo blocco, che poi contiene quello del blocco successivo, fino a raggiungere l’ultimo che contiene il valore nil (end of file). I blocchi non usati sono indicati con 0 nella tabella quindi per allocare un blocco basta trovare il primo elemento della tabella con valore 0, sostituire il nil dell’ultimo blocco col l’indirizzo del nuovo blocco finale e sostituire lo 0 in tabella col nil. Per trovare i blocchi del file, la testina del disco si muove all’inizio della partizione, trova la locazione del blocco dovuto nella FAT e poi va sul blocco stesso. Nel caso peggiore di 1 blocco a file sono necessari entrambi i movimenti per ogni blocco a cui accedere. Il vantaggio è la riduzione del tempo di accesso diretto in quanto la testina può trovare la locazione di qualsiasi blocco leggendo la relativo info nella FAT; - Allocazione indicizzata: ogni file ha un index block, un array di indirizzi dei blocchi occupati sul disco da tale file. Per leggere l’i-esimo blocco, si usa un puntatore all’i-esimo elemento dell’index block che punta a tale blocco. La directory contiene l’indirizzo del blocco indice. Creato un file, tutti gli elementi dell’index block sono posti a nil. Quando bisogna scrivere l’i-esimo blocco, il gestore dello spazio libero fornisce un blocco e il suo indirizzo viene scritto nell’i-esimo elemento del blocco indice. Rapido accesso diretto e non c’è frammentazione esterna. Lo svantaggio è che un intero blocco va usato come indice, quindi c’è un maggiore spreco rispetto all’allocazione collegata. 3 metodi per scegliere la grandezza del blocco indice: - schema collegato: index block è un blocco su disco su cui poter leggere e scrivere direttamente. In caso di grandi file si può usare più blocchi indice, usando l’ultimo indirizzo di uno come riferimento al successivo; - indice multi-livello: si usa un blocco indice di primo livello per puntare a un insieme di index block di secondo livello, che puntano a un insieme di blocchi del file. Ci possono essere anche tre o ancora più livelli, in base alla dimensione massima desiderata del file; - schema combinato: usato in UNIX. Si mantengono, ad esempio, i primi 16 puntatori dell’index block nell’inode del file. Di questi, i primi 13 indirizzano a blocchi diretti, ovvero contengono indirizzi che puntano direttamente a blocchi conteneti i dati del file. I restanti 3 puntano a blocchi indiretti. In particolare il primo contiene l’indirizzo al blocco di prima indirezione, che è un blocco che contiene 16 indirizzi, ognuno che punta a un cluster di 16 blocchi dati, quindi indirizza un totale di 256 blocchi dati allocabili a gruppi di 16. Il secondo contiene l’indirizzo al blocco di seconda indirezione, che è un blocco che contiene 16 indirizzi, ognuno che punta a un blocco contenente 16 indirizzi di blocchi di prima indirezione, dove ogni blocco di prima indirezione contiene 16 indirizzi a cluster da 16 blocchi dati. Analogamente il terzo contiene l’indirizzo al blocco di terza indirezione, che è un blocco contenente 16 indirizzi, ognuno che punta un blocco contenente 16 indirizzi di blocchi di seconda indirezione. Ci sono un totale di 13+256+2562+2563 blocchi dati allocabili. Gestione dello spazio libero. Lista dello spazio libero: sono registrati tutti i blocchi non allocati del disco. Per creare un nuovo file, si cerca nell’elenco dello spazio libero la quantità di spazio richiesta e si alloca tale spazio al nuovo file. Quando si cancella un file, il suo spazio su disco viene riaggiunto alla lista degli spazi liberi. Tale lista è implementabile come: - vettore di bit: ogni blocco è rappresentato da un bit. Un blocco libero ha il rispettivo bit settato a 1, se è occupato a 0. Semplice ed efficiente trovare 1 o n blocchi liberi sul disco. Molti computer hanno istruzioni che restituiscono lo spiazzamento del primo bit con valore 1 all’interno di una parola. Si controlla quindi sequenzialmente ogni parola nel vettore finché non si trova una che abbia un bit settato a 1, corrispondente al primo blocco libero. Il numero di blocco si ottiene come (n° bit per parola)*(n° parole con tutti bit=0)+ spiazzamento nella parola del primo bit=1. Tecnica inefficiente se il vettore non è presente tutto in memoria centrale e se il disco è molto grande perché il vettore sarebbe molto ingombrante. Si allunga anche il tempo di scrittura dei blocchi perché il vettore va aggiornato ad ogni modifica del disco; - lista collegata: si inserisce in ogni blocco libero il puntatore al blocco libero successivo. Puntatore al primo blocco salvato in una locazione speciale del disco. Inefficiente perché per attraversare la lista va letto ogni blocco, aumentando molto il tempo di I/O; - clustering: si memorizza gli indirizzi di n blocchi liberi nel primo blocco libero, con n-1 blocci realmente liberi mentre n-esimo indirizzo porta a un blocco contenente ulteriori n indirizzi di blocchi liberi, ecc. Tutti i blocchi di un cluster vanno allocati insieme quindi potrebbe esserci frammentazione interna; - conteggio: si conserva l’indirizzo del primo blocco libero e il numero degli n blocchi liberi contigui rispetto a quello indirizzato. Quindi ogni elemento della lista è costituito da un indirizzo del disco e da un contatore. Utile perché spesso si assegnano e si liberano più blocchi contigui, soprattutto se si usa un algoritmo di allocazione contigua o un raggruppamento in cluster. Efficienza e prestazioni: l’efficienza dipende dall’algoritmo di allocazione dei file e delle directory e dai tipi di dati conservati nell’inode di un file. Ad esempio ogni volta che si accede a un file va aggioranta data e ora di ultimo accesso nel relativo descrittore (inode) nella directory. Cache del disco: memoria usata, dopo aver scritto quella centrale, per salvare i settori di una traccia a partire da dove si posiziona la testina una volta finita la ricerca. I blocchi rimangono così in memoria nell’ipotesi che saranno riutilizzati. Solitamente è riservata una porzione di memoria centrale a tale scopo oppure si usa una cache delle pagine, che usa la memoria virtuale per salvare i dati del file come pagine invece che come blocchi. Per accedere a un file si può usare le chiamate read e write, che passano attraverso la buffer cache, oppure la mappatura della memoria, che copia il contenuto dei file nella cache della pagine che poi si riversa sulla buffer cache per interfacciarsi col file system. Situazione nota come double caching, che causa perdite di cicli di CPU e I/O dovute al passaggio di dati da una cache all’altra. Alcune versioni di UNIX usano invece una cache unificata, così che entrambi i metodi riversano i dati sulla stessa cache di pagina e permettendo alla memoria virtuale di gestire i dati del file system. I processi effettuano scritture asincrone sulla cache che poi il S.O. provvederà a riversare sul disco quando opportuno. Le scritture sincrone (ES: metadati) scrivono direttamente sul disco perché devono mantenere l’ordine delle richieste. La cache di pagina viene ottimizzata in base all’algoritmo di sostituzione usato. Tecniche usabili: free-behind, in cui si rimuove una pagina dal buffer appena viene chiesta la successiva in quanto si suppone che non verranno riutilizzate fino alla richiesta della pagina successiva, e read-ahead, in cui si inserisce nella cache anche pagine successive oltre a quella richiesta così da risparmiare tempo recuperando con una procedura più dati dal disco. Disco RAM: metodo per migliorare le prestazioni, in cui si definisce una porzione di memoria centrale in cui sono eseguibili tutte le operazioni eseguibili su disco. Ovviamente la memorizzazione dei dati è temporanea. Recupero dei file system. In caso di crash del sistema, la tabella dei file aperti risiedente nella memoria centrale, viene persa come anche le modifiche apportate ai file aperti, lasciando il file system in uno stato incoerente rispetto a quello descritto nella struttura della directory. Controllore della coerenza: si attiva durante il bootstrap e confronta i dati nella struttura della directory con i blocchi dati sul disco, cercando di riparare eventuali incoerenze. Una incoerenza è difficile da recuperare nei sistemi ad allocazione indicizzata in quanto i blocchi dati non hanno conoscenza l’uno dell’altro per questo UNIX usa la cache solo per leggere mentre operazioni di scrittura che allocano spazio su disco o che modificano i metadati sono eseguite in modo sincrono. Si possono usare programmi di sistema per effettuare un backup dei dati dal disco fisso a un supporto esterno. Per recuperare i file persi basta quindi ripristinare i dati salvati sul supporto di backup. File system basati sulla registrazione delle attività o orientati alle transazioni basate sui log: anziché usare scritture sincrone, usano file log in cui si registra ogni operazione eseguita sul file system come una transazione. Infatti il controllore della coerenza può non essere in grado di recuperare le strutture. Si può invece scrivere i cambiamenti da eseguire sul file log e far tornare il controllo al processo utente che potrà continuare la sua esecuzione. Intanto le voci sul file log sono replicate nelle strutture dati attuali del file system. Quando una transazione viene completata, viene rimossa dal file log. Se il sistema si blocca, al riavvio vanno eseguite le transazioni ancora presenti in tale file. Le modifiche eseguite da transazioni interrotte da crash vengono annullate in modo da conservare la coerenza del file system. Così le operazioni sincrone di aggiornamento dei metadati sono trasformate in scritture sequenziali sincrone nell’area di log, molto meno costose, che verranno poi scritte in modo asincrono nel file system, migliorando le prestazioni. 14. Struttura dei dischi. Sono i principali sistemi di archiviazione secondaria. Sono indirizzati come grandi array monodimensionali di blocchi logici, unità di trasferimento dati in lettura e scrittura. Il vettore dei blocchi logici è mappato nei settori del disco in modo sequenziale. Viene mappato come settore 0 il primo settore della prima traccia sul cilindro più esterno e si procede nell’ordine lungo quella traccia, poi sul resto delle tracce del cilindro, mappando così tutti i cilindri dal più esterno al più interno. Si può così convertire un numero di blocco logico in un indirizzo fisico del disco, costituito da: n° cilindro, n° traccia e n°settore. Schedulazione degli accessi al disco. S.O. deve avere un basso tempo di accesso e una buona largezza di banda per usare in maniera efficiente il disco. Con tempo di accesso = tempo di seek (o di ricerca, che impiega il braccio a muovere la testina fino al cilindro contenente il settore desiderato) + latenza di rotazione (tempo che il disco impiega per far ruotare il settore desiderato fino alla testina). La larghezza di banda è il numero totale di byte trasferiti diviso il tempo che intercorre tra la richiesta e il completamento dell’ultimo trasferimento. Quando un processo effettua una richiesta di una operazione di I/O, se il disco è libero viene subito soddisfatta altrimenti viene messa in fondo a una coda d’attesa, per cui va deciso un algoritmo di schedulazione degli accessi su disco per scegliere l’ordine di esecuzione delle operazioni richieste. L’obiettivo è ridurre il tempo d’accesso e lo si fa minimizzando il tempo di ricerca, in quanto quello di rotazione risulta trascurabile. Gli algoritmi lo fanno minimizzando il percorso che la testina deve compiere per soddifare una sequenza di richieste d’accesso ricevute. I diversi algoritmi sono: - FCFS: più semplice, richieste soddisfatte in ordine di arrivo. La testina compie ampie oscillazioni che allungano il percorso seguito, rendendo perciò l’algoritmo inefficiente; - SSTF (Shortest Seek Time First): viene soddisfatta prima la richiesta col minimo tempo di ricerca per la posizione corrente della testina. A parità di vettore di richieste, segue un percorso che è un terzo della lunghezza di quello definito dal FCFS, migliorando quindi notevolmente le prestazioni. È una schedulazione di tipo SJF quindi può causare la starvation di alcune richieste. Non è ottimale, migliorabile eliminando le oscillazioni compiute dalla testina; - SCAN: il braccio del disco parte da un estremo e si muove verso l’altro servendo le richieste man mano che raggiunge ogni cilindro. Raggiunto l’altro estremo del disco, inverte la direzione e continua a servire le richieste. Va definita la direzione di movimento della testina per conoscre l’ordine con cui soddisfare le richieste. Detto anche algoritmo dell’ascensore proprio perché il braccio serve tutte le richieste seguendo una direzione, poi torna indietro per servire le richieste nell’altra direzione; - C-SCAN (Circular Scan): variante dello SCAN che fornisce un tempo di attesa più uniforme. Quando la testina raggiunge l’altro capo, torna direttamente all’inizio del disco senza servire alcuna richiesta durante il ritorno, quindi i cilindri vengono trattati come una lista circolare; - LOOK e C-LOOK: varianti rispettivamente di SCAN e C-SCAN, in cui il braccio arriva fino alla richiesta finale per ogni direzione, poi inverte subito la direzione, senza raggiungere l’estremità del disco. SSTF è la scelta più frequente perché aumenta molto le prestazioni rispetto al FCFS. Per sistemi che generano un elevato numero di richieste d’accesso al disco conviene usare SCAN e C-SCAN, evitando così problemi di starvation. L’algoritmo migliore cambia in base alla sequenza di richieste data, che varia molto anche in base al metodo di allocazione dei file usato. Un’allocazione contigua genera richieste di cilindri vicini tra loro quindi c’è un movimento ridotto della testina, mentre un’allocazione collegata o indicizzata, che ha i blocchi dei file sparsi sul disco, causano un maggiore movimento della testina. Per questo la procedura di schedulazione del disco viene scritta su un modulo post programmabile separato dal S.O. e la si cambia in base alle proprie esigienze. Nei computer general pourpose di default si trova SSTF o LOOK. Amministrazione del disco. Prima di poter memorizzare i dati sul disco, si esegue una formattazione a basso livello o fisica, in cui il disco viene diviso in settori che il controller può leggere e scrivere. Poi, per memorizzare i file su disco, il S.O. deve registrarci sopra le sue strutture dati partizionando il disco in uno o più gruppi di cilindri. Infine si esegue la formattazione logica, con cui viene creato un file system nella partizione considerata. Si può avere un solo file system a partizione, ma più file system sullo stesso disco, uno a partizione. Per far funzionare un calcolatore, durante l’avvio viene eseguito un programma di inizializzazione (bootstrap) che recupera il kernel del S.O. dal disco, lo carica in memoria centrale e salta a un indirizzo iniziale per cominciare l’esecuzione del S.O. stesso. Il bootstrap solitamente è immagazzinato in una ROM che, essendo una memoria di sola lettura, non può essere infettata da virus. Dovendo modificare i circuiti per cambiare il codice della ROM, solitamente al suo interno si memorizza solo un piccolo programma caricatore che prende e fa eseguire un programma di avvio completo dal disco che può essere facilmente modificato. Tale programma di bootstrap è salvato in una posizione fissa su disco. Disco di boot o disco di sistema: disco che ha una partizione per il caricamento del S.O.. I dischi eseguono movimenti meccanici, quindi sono soggetti a guasti. A volte per un solo guasto va sostituito l’intero disco, più spesso invece solo alcuni settori risultano difettosi. In genere un malfunzionamento del disco può essere logico (riparabile ripartizionando il disco o eseguendo di nuovo una formattazione logica della partizione soggetta a problemi) o fisico (danneggiamento che riguarda la formattazione fisica del disco, quindi difficilmente risolvibile). Nei dischi SCSI il controller mantiene una lista dei blocchi difettosi sul disco stesso, che viene inizializzata con la formattazione fisica in fabbrica e viene aggiornata durante la vita del disco. La formattazione fisica inoltre predispone settori aggiuntivi, non visibili al S.O., usati per sostituire quelli guasti. Si ordina quindi al controller di sostituire logicamente un settore guasto con di scorta. Schema noto come ricambio dei settori guasti (sector sparing o forwarding). La sostituzione di un blocco spesso richiede un intervento manuale per riparare il file che stava usando il blocco difettoso da sostituire. Gestione dello spazio di swap. Ricavabile come file all’interno del file system o come partizione separata del disco. Nel primo caso lo si genera con una normale procedura del file system, nel secondo non c’è un file system nella partizione quindi si usa un gestore separato dello spazio di swap per allocare e deallocare i blocchi. In BSD viene creato uno spazio di swap per ogni processo che si avvia, con una dimensione sufficiente a memorizzare l’intero programma. Con questa preallocazione si impedisce a un processo di esaurire lo spazio di swap durante l’esecuzione. Mappe di swap: ne sono usate due a processo dal kernel, per tracciare l’uso dello spazio di swap. Windows crea un unico file di swap per tutti i processi in esecuzione. Solaris 2 assegna uno spazio di swap solo quando una pagina viene scaricata dalla memoria fisica, piuttosto che quando la pagina virtuale viene creata in memoria per la prima volta. Collegamento dei dischi. I computer accedono alla memorizzazione su disco tramite le porte di I/O ovvero mediante la memorizzazione con collegamento all’host (host-attached storage), oppure tramite un host remoto mediante il NFS (Network File System), file system distribuito usato in UNIX che permette la memorizzazione con collegamento di rete (NAS, Network Attached Storage). In quest’ultimo caso si parla di SAN (Storage Area Network), ovvero una rete costituita da soli dischi, ognuno dei quali accessibile da remoto, solitamente da client sprovvisti o con scarso spazio di archiviazione, che si connetto alla SAN con un collegamento ad alta velocità. Così facendo tutti i computer di una LAN possono condividere un gruppo di periferiche di archiviazione con la stessa semplicità di assegnazione di nomi e accessi garantita da un collegamento ad un host locale. Quindi una SAN è una rete privata fra i server e le unità di memorizzazione, separata da una LAN o WAN che collega i server ai client. A una SAN possono collegarsi più host e più gruppi di memorizzazione, risultando molto flessibile e permettendo di assegnare dinamicamente la capacità di memorizzazione agli host. Ad esempio, se un host ha carenza di spazio su disco, la SAN può essere configurata in modo da assegnare più spazio di archiviazione a quell’host. Linux LINUX è un clone di UNIX, S.O. Multiutente, Multitasking, Multipiattaforma, che aveva come limitazione il fatto di non essere open source né un software free. Più precisamente è il kernel del S.O GNU/Linux (Gnu is Not Unix). I numeri di versione di Linux sono due, uno riferito alla distribuzione e uno al kernel, quindi il c’è un versioning differente per kernel e distro. Una distribuzione è un pacchetto completo comprendente: LINUX (vale a dire il kernel) Applicativi Una distribuzione è sviluppata da una comunità indipendente dalle altre. Si ricorda che il kernel è l’insieme delle routine di basso livello del S.O e dipendente in maniera debole dalla distribuzione. Il versioning del kernel si è evoluto negli anni. Lo scherma di riferimento attuale consiste di quattro cifre: A.B.C[.D] (es. 2.6.12.3) A: versione del kernel. Viene modificato molto raramente la più recente è la versione 4; B: revisione maggiore del kernel. Prima della serie 2.6.x, i numeri pari indicano un ramo stabile mentre i numeri dispari (come 1.1 oppure 2.5) indicano rami di sviluppo. Nei kernel stable si tende a fare maintenance ed a implementare solo le feature strettamente necessarie. Nel kernel development invece si aggiunge lo sviluppo di nuove funzionalità. A partire dalla serie 2.6.x, il versioning diventa di tipo time-based e lo sviluppo di nuove caratteristiche avviene all'interno dello stesso ramo. Il sistema di numerazione diventa del tipo 2.6.x.y incrementando la terza cifra; C: revisione minore del kernel. Nel modello a tre cifre questo numero viene incrementato in caso di aggiornamenti riguardanti la sicurezza, correzioni di alcuni errori, nuove caratteristiche, o nuovi driver. Invece nel modello a quattro cifre viene cambiato solo quando vengono introdotti nuovi driver o funzionalità aggiuntive, in quanto le correzioni minori sono conteggiate da D; D: patch number. Serve a conteggiare correzioni e patch di sicurezza. Nel 2011 si passa direttamente dalla versione 2.6.39 alla 3.0, in cui viene mantenuto l’approccio time-based ma è la seconda cifra ad essere incrementata ad ogni rilascio (3.1, 3.2, ecc.) mentre la terza cifra viene usata per rappresentare il patch number. Infine, dalla versione 3.19 si è passati direttamente alla 4.0. Fuzionalità: Multiuser: più utenti possono interagire in contemporanea (da terminali differenti). Ognuno è identificato da un username (nome logico di un utente) e sono divisi in gruppi. L’utente root è l’amministratore di sistema; Multitasking: esecuzione di più processi gestiti a divisione di tempo, su di un’unica CPU in contemporanea Multithreading: esecuzione di più parti di uno stesso programma in contemporanea Multiprocessing: supporta più processori in parallelo Compatibilità con molte architetture di CPU, diversi file system, la maggioranza degli standard UNIX. Permette un controllo diretto dei job in esecuzione. È dotato di una console virtuale per la modalità testuale e può Coesistere con altri S.O. Copyright: Nel 1985 Richard Stallman, ex ricercatore del MIT, fonda la Free Software Foundation (FSF), finanziata per donazioni, alla cui base c'era il progetto del S.O. GNU. L’obiettivo infatti è la realizzazione di un sistema operativo free, nel senso più esteso del termine. Un software free (libero), rilasciato con la GNU General Public Licence (GPL), implica: Libertà di eseguire il programma come si desidera, per qualsiasi scopo Libertà di modificare il programma in modo da adattarlo alle proprie necessità Libertà di ridistribuire copie (anche a pagamento) Libertà di migliorare il programma e distribuirne pubblicamente i miglioramenti Un software libero non è detto che sia gratuito: free ≠ gratis. Il kernel LINUX è rilasciato con licenza GNU GPL quindi i sorgenti sono liberamente modificabili e non esistono limitazioni ai diritti di distribuzione. La licenza GPL si estende ai sorgenti modificati, quindi le modifiche al kernel producono il cosidetto “worked derived”, ovvero in fase di distribuzione si è obbligati a rilasciare il codice sorgente con tutte le modifiche apportate utilizzando la stessa licenza GPL. Nonostante ciò la diffusione può essere gratuita o a pagamento. Alle aziende venditrici è consentito pubblicare i sorgenti del software anche in un secondo momento ma sono stabilite dei limiti ai possibili servizi a pagamento post-vendita che si possono fornire (ES: solo costo del supporto). L’obiettivi della licenza GPL è quello di incrementare la qualità del software in circolazione senza trarne profitto. La shell è un programma che permette ad un utente di interagire con un sistema operativo leggendo ed interpretando i comandi che vengono inseriti dall'utente. La shell tipica dei sistemi Unix e Unix-like (GNU/Linux) deriva dalla shell di Bourne: la shell BASH (Bourne Again SHell). Una shell Unix svolge, di base, i compiti seguenti: Prompt per inserimento dei comandi; Interprete del comando inserito dall'utente; Esegue le sostituzioni, in base ai caratteri jolly e alle variabili di ambiente; Mette a disposizione alcuni comandi interni o programmi esterni; Gestisce la ridirezione dell'input e dell'output; É in grado di interpretare ed eseguire dei file script in linguaggio di shell; Permette il controllo dei processi. La shell può essere ampiamente personalizzata modificando le informazioni fornite da prompt, i colori, definizione statica degli alias e altro. Ogni utente di un sistema Linux ha un file di configurazione (nascosto) per questo scopo: “.bashrc” oppure “.bash_profile”, a seconda della distribuzione utilizzata. Questi file non sono altro che script di configurazione, contengono cioè una serie di comandi che verranno eseguiti al login, settando le preferenze specificate dall’utente. Modificando questo file è possibile quindi adattare il più possibile la shell alle proprie esigenze, riutilizzando il file di configurazione su altri sistemi. Nella home- directory di ogni utente è presente un file (nascosto «.») che contiene la cronologia dei comandi immessi: “.bash_history”. Un terminale, in Unix, è un'interfaccia, testuale o grafica, tramite la quale gli utenti possono interagire col sistema. I primi terminali erano telescriventi (TTY), ovvero apparecchiature che stampavano i risultati dell'elaborazione su carta. I terminali virtuali nei sistemi Unix e derivati vengono tutt'ora identificati con l'acronimo TTY seguito dal numero del terminale (es. tty3). Normalmente una distribuzione Linux per sistemi desktop avvia sette terminali di cui i primi sei sono shell testuali, mentre il settimo è dedicato al terminale che ospita la sessione grafica. Quando si avviano più sessioni grafiche, queste risiederanno nei terminali grafici successivi al settimo. Nella sess

Sistemi Operativi PDF - Domenico Siciliani - Ingegneria Informatica PDF

Document Details

Tags

Related

Summary

Full Transcript