Operating systems / Sistemi Operativi by Andrea Mantoni Ultima modifica: %%mtime(%d %B %Y) = Introduzione = Il *SO = Sistema Operativo* è una _interfaccia_ / mediatore tra le applicazioni utente / user applications e l'hardware. L'OS è un *resource manager* = gestisce le risorse di sistema: - processore - memoria - I/O devices mediante: - processi - file system evoluzione storica: - *monoprogrammazione / elaborazione seriale* PROBLEMI: - scheduling inefficiente - setup time manuale - *monoprogrammazione batch* -> consente di eliminare le _pause di inattività_ mediante 1 *monitor* (forma primitiva di OS) = 1 programma _sempre residente in memoria_ -> in caso di errore il controllo ritorna al monitor che: - gestisce dei *jobs* "a lotti" mediante un *JCL = Job Control Language* - fornisce i seguenti servizi: - *memory protection* = l'area di memoria del monitor non può essere alterata - *timer* = interrompe un job dopo un certo tempo - *istruzioni privilegiate* = impedisce l'uso di certe istruzioni al job -> supervisor mode/user mode - *multiprogrammazione / multitasking* sempre per massimizzare l'efficienza, si caricano in memoria + jobs/programmi contemporaneamente e si mandano in esecuzione contemporaneamente con l'ausilio delle interruzioni. Ciò richiede: > memoria per tenere tutti i jobs - meccanismo di _gestione della memoria_ e schedulazione dei jobs - interruzioni di I/O (per riprendere un job quando un dispositivo di I/O ha finito) PROBLEMA: memory protection tra jobs - *multiuser / time-sharing* consente a più utenti di _interagire contemporaneamente_ con lo stesso elaboratore. Mediante un _timer_ si assegna un _quanto di tempo CPU_ a ciascun utente. Allo scadere del quanto, il controllo passa ad un altro utente e, se necessario, i dati dell'utente precedente vengono scritti su disco/nastro -> swapping PROBLEMI: - gestione accesso concorrente all'I/O - gestione accesso concorrente al file system caratteristiche OS moderni: - architettura: - *kernel monolitico* = 1 unico "processo" in _kernel mode_ = 1 unico address space - *microkernel* + servers = "processi di sistema" / services _in user space_ = tanti address spaces distinti - multitasking può essere: - PMT = Pre-emptive MultiTasking - CMT = Co-operative MultiTasking / not-preemptive - multiuser (già visto) - multithreading = in un processo vi sono più flussi d'esecuzione/threads distinti. PROs: - maggiore immunità agli errori ... OS overview (code): *--------------------------------------* process -> | service calls handler \ | \ | |-> dispatcher | -> process I/O ----> | interrupt handler / | *--------------------------------------* *service calls handler* = gestisce le chiamate a syscalls effettuate dai processi / user applications. *interrupt handler* = gestisce le interruzioni provenienti dalle periferiche di I/O e (a volte in caso di errore) dai processi. *dispatcher* = seleziona il prossimo processo (di sistema o utente) a cui assegnare la CPU OS overview (data): - processes - system resources - opened files - memory bitmap (RAM and HD) - system users (for security) Il SO a runtime gestisce _diverse tabelle_ nel suo address space. [...] = I processi / task / job = Un processo rappresenta una istanza di un programma in esecuzione. Possono esistere più istanze dello stesso programma in esecuzione contemporanamente. Una user application può essere costituita da più processi. Un processo è costituito da 3 componenti: - il codice eseguibile (statico) - i dati associati al programma (variabili) - il contesto d'esecuzione -> contiene il *PCB = Process Control Block* process image: - *execution context* - *data* (variable) - *code* (static) PCB contents: - PID -> ogni processo è identificato da un ID - *stato d'esecuzione / process state* (READY/RUNNING/etc.) - CPU registers -> necessari per il context switch Il PCB è utilizzato dal SO per la gestione dei processi (scheduling, context switch, etc.) stati d'esecuzione: - RUNNING = in esecuzione. OSS.: con una sola CPU ci può essere al più 1 processo in esecuzione in un dato istante. - READY = not running. Sarà preso in esame dallo scheduler alla prossima invocazione. - BLOCKED = in attesa di I/O interrupt - NEW = processo nuovo, non ancora accettato dal SO - EXIT = processo terminato, non ancora rimosso - SUSPENDED = swappato su disco process states models: - 2-state process model (READY/RUNNING) - 5-state process model (NEW/READY/RUNNING/BLOCKED/EXIT) - 7-state process model (NEW/READY/RUNNING/BLOCKED/BLOCKED-SUSPENDED/READY-SUSPENDED/EXIT) == Scheduling == scheduling dei processi: - long-term scheduling (NEW->READY) - medium-term scheduling (SWAPPED->READY) - short-term scheduling (READY->RUNNING) -> *dispatcher* Influenzano il livello di multiprogrammazione di un OS. algoritmi short-term scheduling: - *FIFO / FCFS = First Come First Served* (non-preemptive) -> favorisce i processi lunghi - *RR = Round Robin* (preemptive con _quanto di tempo_) -> poco bilanciato CPU-bound/I/O - *SPN = Shortest Process Next* (non-preemptive) \ - richiedono che sia noto il service time in anticipo - *SRT = Shortest Remaining Time* (preemptive all'arrivo) / - rischio starvation per processi lunghi criteri di scelta: - Turnaround Time = tempo di completamento - Response Time = tempo di reazione (per processi interattivi) - Throughput = n° di processi completati - Priorità == Concorrenza == { multiprogrammazione (+ processi su 1 CPU) \ tutti questi temi != | presentano il multiprocessing (+ processi su + CPU) | problema della != | concorrenza processi distribuiti (in rete) / tra processi problema della concorrenza tra processi: L'output di un processo deve essere _indipendente_ dal suo _contesto d'esecuzione_ (gli altri processi, etc.) Il SO deve garantire che non si verifichino _interferenze_ con: - protezione della memoria - accesso in mutua esclusione alle risorse condivise interazione tra processi: - competizione - cooperazione - indiretta (tramite condivisione) - diretta (tramite comunicazione) classificazione dei processi in base al livello di conoscenza reciproco: - p. indipendenti = che non si vedono tra loro - p. che cooperano indirettamente = condividono l'uso di qualche risorsa - p. che cooperano direttamente = condividono delle risorse e si scambiano dei messaggi } Ad ogni processo sono associate diverse _risorse condivise_ dal SO: - processor time - memory - files - I/O devices ciò comporta il *problema della concorrenza*. sottoproblemi: - race conditions - dead-locks - live-locks / starvation soluzione: - definizione di *critical sections* nei programmi - accesso in *mutua esclusione* alle risorse condivise: - via hardware support - interrupt disable - special CPU instructions - via software -> busy waiting - algoritmo di Dekker - algoritmo di Peterson - via software support (OS, programming language) - semaphores - monitors - message passing *MUTEX = MUTual EXclusion = mutua esclusione* = protocollo di accesso alle risorse condivise -> implementazioni sw e hw primitive: - entra_critica() - esci_critica() != sincronizzazione = ordinamento dell'esecuzione -> semafori Per la gestione delle concorrenza si possono seguire diverse strategie, tutte equivalenti: - condivisione risorse + mutua esclusione - condivisione risorse + sincronizzazione - message passing Sono tutti equivalenti, infatti ognuno può essere implementato con un altro. { tecniche di ???: - variabili condivise + mutex (valori arbitrari) - semafori generici (incremento/decremento unitari) - array di semafori binari indicizzato } == Semafori == *semaforo* = 1 struttura dati contenente: - 1 *contatore* rappresenta: se > 0 -> il n° di risorse disponibli se <= 0 -> il n°di processi in attesa - 1 *coda di processi* in attesa Ha associate 3 operazioni primitive: - init( sem, value ) = inizializza \ - wait( sem ) = decrementa | il contatore - signal( sem ) = incrementa / La "wait" è eseguita da un processo che vuole richiedere l'uso di una risorsa. Se il semaforo è >1 gli viene concessa, altrimenti il processi è bloccato ed è messo in coda. -> NO busy waiting La "signal" è eseguita per rilasciare le risorse usate. Sblocca 1 dei processi in attesa sulla coda. classificazioni: - a seconda del tipo di contatore: - binari - generici / a contatore - a seconda di come viene gestita la coda: - *strong semaphore* = FIFO -> default - *weak semaphores = random -> PROBLEM: starvation Protocollo d'uso: global init( s, 1 ) process { wait( s ) // sezione critica signal( s ) } possibili usi semafori: - accesso un mutua esclusione alle risorse / variabili condivise (wait = entra_critica, signal = esci_critica) - sincronizzazione / signaling / serializzazione delle azioni (wait = attende/dorme, signal = segnala/risveglia) -> rendezvous == Message passing / comunicazione == Si basa su 2 primitive: - send( dst, msg ) - receive( src, msg ) possono essere: - bloccanti - non-bloccanti sono possibili varie combinazioni: - la send bloccante di solito è affidabile = assicura che il messaggio non sia andato perso - send bloccante + receive bloccante = rendezvous -> sincronizzazione stretta tra processi - send non bloccante + receive bloccante -> combinazione più comune formato msg: - HEADER - BODY - TRAILER indirizzamento: - diretto (ad es. mediante PID) - indiretto -> il SO gestisce delle *mailbox* = delle code che contengono temporaneamente i messaggi == Problemi tipici == Problema produttore/consumatore Problema lettori/scrittori Problema del barbiere Problema dei filosofi a cena == Deadlock == *stallo/deadlock* = blocco permanente di un insieme di processi che competono tra loro. dipende da: - scheduling dell'esecuzione -> non possiamo fare assunzioni su di esso - implementazione dell'applicazione -> in particolare, quali ed in quale ordine sono richieste e rilasciate le risorse condizioni di stallo, affinchè lo stallo sia possibile: 1. *mutua esclusione* per l'accesso ad un insieme di risorse 2. *possesso + attesa* = un processo può mantenere il possesso delle risorse mentre è in attesa di ottenerne altre 3. *assenza di prerilascio* = un processo non può essere forzato dall'esterno a rilasciare una risorsa posseduta Affinchè si verifichi una stallo (CNES) deve essere verificata anche: 4. *attesa circolare* = il grafo che connette i processi con le risorse richieste/possedute contiene un ciclo gestione dello stallo: - i processi sono bloccati: - prevenzione ----------> - prima di partire \ + conservative - esclusione -----------> - _prima_ della richiesta | - rilevamento ----------> - _dopo_ la richiesta / + liberali Ogni strategia ha i suoi pro e i suoi contro. Non esistono soluzioni assolutamente efficienti per la gestione dello stallo. Di solito si applicano strategie diverse per classi di risorse diverse. Prevenzione = impedisce "a priori" il verificarsi di una stallo prevenendo le condizioni CNES viste prima: - indiretta = impedisce 1, 2, 3 - diretta = impedisce 4 Esclusione 2 approcci: 1. rifiuto permesso di esecuzione (NEW->READY) = il processo non viene ammesso nel sistema se non è possibile soddisfare la somma delle sue richieste di risorse e quella dei processi in esecuzione (espresse sottoforma di matrici) -> bisogna conoscere in anticipo le richieste 2. _rifiuto di allocare le risorse_ se queste fanno transitare il SO in uno _stato non sicuro_ = non esiste una schedulazione dei processi che gli consenta di completare senza il verificarsi di uno stallo -> può essere verificato con l'*algoritmo del banchiere* Lo stato del SO può essere descritto mediante 2 vettori: - Risorse (statico) = n° _totale_ di unità di risorse disponibili - Disponibili = unità di risorse _non assegnate_ attualmente e 2 matrici: - Richieste (statico) = mette in relazione i processi con il n° di risorse che saranno richieste durante la loro esecuzione - Assegnazione = mette in relazione le risorse con i processi a cui sono state assegnate attualmente Quando un processo richiede nuove risorse: - si controlla che la sua richiesta sia compatibile con la _dichiarazione iniziale_ del processo - si valuta se la sua richiesta è compatibile con le risorse attualemente disponibili -> attraverso il vettore "Disponibili" - se non lo è, il processo è sospeso - se lo è, si calcola in anticipo il _nuovo stato_ in cui transiterebbe il sistema concedendo le risorse richieste -> accedendo ad "Assegnazione" e "Disponibili" - infine, si determina con l'algorimo del banchiere se il nuovo stato è sicuro: - se lo è le risorse vengono concesse - altrimenti il processo viene sospeso algoritmo del banchiere: [...] Rilevamento = non si interviene nell'assegnamento delle risorse, ma si controlla periodicamente "a posteriori" il verificarsi dello stallo -> i processi in stallo vengono ripristinati il ripristino può essere fatto con diversi approcci: - aborting totale o parziale (+ usato) - ripristino ad un checkpoint (memorizzato in precedenza) - prerilascio di alcune risorse contese = Memory management = La gestione della memoria { Si occupa di dividere / allocare la parte "utente" della memoria (non occupata dal SO) tra i vari processi. } { Si occupa di _allocare_ la memoria ai processi. La memoria non occupata dal SO viene suddivisa in tante aree / *address spaces*, ognuna assegnata ad un processo distinto. } Inoltre, fornisce funzionalità di: - protezione - condivisione - rilocazione - memoria virtuale (mediante swapping) tecniche di allocazione: - continua -> aree contigue di memoria - partizionamento / partitioning - *partizionamento fisso* = dimensioni di tutte partizioni prefissate -> PROBLEMI: n° di processi attivi limitato, frammentazione interna - equal size partitions - unequal/variable size partitions VARIANTE: *buddy system* - *partizionamento dinamico* = dimensioni di ogni partizione stabilite a runtime -> PROBLEMA: frammentazione esterna -> SOL.: deframmentazione/compaction -> PROBLEMA: richiede tempo CPU serve un algoritmo di allocazione: - best fit - first fit (migliore) - next fit (si fà una scansione delle aree vuote di memoria) - discontinua - *paginazione* = mapping ( process pages <-> memory frames ) + page table - *segmentazione* = process segments + segments table - mista con memoria virtuale == Buddy system == Un "compromesso" per risolvere i problemi del partizionamento è il *buddy system*. La memoria è trattata a _blocchi di 2^K bytes_ (gestiti ad es. con un albero binario), con L < K < U dove "L" ed "U" variano a runtime in modo da formare i blocchi delle dimensioni appropriate per contenere i processi: 2^U = blocco allocato di dimensione max 2^L = blocco allocato di dimensione min funzionamento: - Quando arriva un processo di dimensione "S" da allocare, SE 2^U-1 < S < 2^U, allora gli è assegnato l'intero blocco; ALTRIMENTI il blocco è diviso in 2 "buddies" da 2^U-1 bytes ciascuno. E così via, fino alla dimensione minima. - Quando un processo è rimosso, i "compagni" contigui vengono riuniti in 1 singolo blocco == Rilocazione, linking e loading dei processi == Un programma può essere caricato ogni volta in posizioni diverse della memoria. Il SO deve gestire i _riferimenti alla memoria_ in esso contenuti mappando/traducendo di volta in volta: indirizzi logici/relativi (di solito all'indirizzo base del processo) <-> fisici/assoluti Per fare questo ci si serve del supporto della CPU, che carica: - nel base register : indirizzo iniziale del processo - nel bound register : indirizzo della fine del processo Quindi a runtime, per ottenere gli indirizzi fisici, somma ogni indirizzo relativo al base register, e controlla che siano entro i limiti del processo. *Loading* = caricamento di un programma in memoria (una volta che lo scheduler ha assegnato un'area di memoria al processo) può essere: - assoluto (statico) - rilocabile (one shot) = il calcolo di un indirizzo assoluto è effettuato quando il processo è caricato in memoria - dinamico a runtime = il calcolo di un indirizzo assoluto è effettuato solo quando è necessario e non quando il processo è caricato -> l'unico che consente la rilocazione dei processi Il *linking* consiste nella fusione di più *moduli oggetto* e nella creazione di un *modulo di caricamento / eseguibile*. Per fare questo devono essere risolti i *riferimenti* ai moduli esterni in riferimenti a locazioni all'interno del modulo di caricamento. Ciò può essere fatto in vari modi: - *linking statico* (con linkage editor) - *linking dinamico* (a runtime) -> facilita la condivisione di memoria == Paginazione == La memoria è divisa in frames \ _tutti di dimensioni_ I processi sono divisi in pagine / _uguali (piccole)_ _Le pagine di un processo vengono allocate in frames anche non contigui._ Per tenere traccia della mappatura delle pagine nei frames di memoria ci si serve di una *page table* per ogni processo. Gli indirizzi logici vengono espressi con _n° di pagina + offset_ e gestiti sempre con l'ausilio della CPU (che accede direttamente alla page table del processo corrente). Inoltre il SO mantiene una *lista dei frames liberi*. La _dimensione delle pagine_ deve essere _bilanciata_ in modo da limitare: - la frammentazione interna, - la dimensione della page table - il n° di page faults == Segmentazione == Un processo è diviso in *segmenti / spazi di indirizzamento* di _dimensioni dinamiche_ non necessariamente contigui. Ci si serve di una *tabella dei segmenti* per ogni processo e una *lista di blocchi liberi*. Ogni entry della tabella contiene l'indirizzo di memoria base del segmento e la sua lunghezza. Gli indirizzi logici sono costruiti da _n° di segmento + offset_ e gestiti sempre con l'ausilio di appositi registri della CPU. PROBLEMI: - il programmatore deve curarsi della _dimensione max_ dei segmenti. - non c'è alcuna relazione semplice tra indirizzo logico -> indirizzo fisico === x86 memory model === x86 memory modes: - *real mode* (from i086) 20-bit segmented memory address space giving exactly 1 MiB of addressable memory 384KB above was reserved for system use and optional devices 640 KB was for applications use -> *640 KB barrier* unlimited direct software access to all memory, I/O addresses and peripheral hardware no support for memory protection, multitasking, or code privilege levels all x86 CPUs start in real mode when reset - *protected (virtual address) mode* (from i286) 32-bits segmented memory address space -> *4 GB limit* features such as virtual memory, paging and safe multi-tasking privilege levels *virtual x86 mode* (since i386) = real mode emulation (not 100% compatible) ... L'x86 supportava inizialmente solo il real mode. Per superare il limite dei 640KB, sono state sviluppate varie tecniche: - *(LIM) EMS = (Lotus Software, Intel, and Microsoft) Expanded Memory Specification* initially req. an ISA expansion card with bank-switched memory modules in seguito emulato via software nella memoria estesa -> "EMM386.EXE" in MS-DOS - *XMS = eXtended Memory Specification* based on swapping memory between conventional and extended memory areas -> fornito da "HIMEM.SYS" in MS-DOS In seguito, sono stati realizzati vari *DOS extender* per consentire alle applicazioni di andare in protected mode ed accedere direttamente a tutta la memoria disponibile (secondo le specifiche *DPMI=DOS Protected Mode Interface*): - DOS/4G and DOS/4GW and DOS/16M - CWSDPMI - HX DOS Extender - PMODE and PMODE/W ... DOS memory management: - conventional / base memory (0-640KB) -> direcly addressable in real mode by apps - UMA = Upper Memory Area (640KB-1MB = 384 KB) -> reserved by the OS for I/O device drivers, TSRs=Terminate and Stay Resident - extended memory (4GB-1MB) - i 64KB più bassi sono riservati per la *HMA=high memory area* -> usata per ?? == Virtual memory == Le tecniche di paginazione e segmentazione con il loading dinamico consentono l'uso della *memoria virtuale* con *swapping* dei processi su disco. Per poter essere eseguibile, è sufficiente che solo un "pezzo" (pagina o segmento) del processo sia in memoria principale (il *resident set*). VANTAGGI: - più processi in memoria ready -> miglior uso della CPU - non tutto il processo deve essere contenuto in memoria -> aumento della memoria disponibile funzionamento: Quando un processo tenta di accedere ad una locazione fuori dal suo resident set si genera una interruzione (ad es. "page fault") e il processo diventa "blocked". Finchè non viene caricata la pagina/segmento dall'I/O, si genera un altro interrupt, e il processo torna "ready". OSS.: per il *principio di località* ciò non avviene molto spesso! === Paginazione con memoria virtuale === Occorre aggiungere alla page table _alcuni flags_ per indicare: p = la presenza di una pagina in memoria principale m = la modifica di una pagina in memoria principale -> è necessario riscriverla su disco [...] Poichè la dimensione della page table può essere notevole, si può paginare anch'essa. (Per poter essere eseguibile almeno una entry della page table del processo deve essere in memoria principale) Alcune CPU usano uno "schema a 2 livelli" per la tabella delle pagine: 1 directory + page tables Per ridurre il n° di accessi alla memoria virtuale per recuperare le entries della page table si utilizza una cache hardware detta *TLB = Translation Lookaside Buffer* che mantiene le entries usate più di recente. Il TLB di solito usa una _mappa associativa_ per le entries: n° di pagina <-> N° di frame != _mappa diretta/indicizzazione_ usata per la page table === Segmentazione con memoria virtuale === Anche in questo caso di aggiungono dei flags nella segment table. Di solito la segment table è mantenuta in memoria principale. VANTAGGI: - ottimo per strutture dati dinamiche - facilita la protezione e condivisone, il linking dinamico === Paginazione e segmentazione con memoria virtuale === Per avere i vantaggi di entrambe le tecniche, è possibile _combinare paginazione e segmentazione_ dividendo i processi in segmenti a loro volta suddivisi in pagine. Gli indirizzi virtuali conterranno quindi: n° di segmento + n° di pagina + offset Cmq resta il fatto che _paginazione e segmentazione richiedono il supporto dell'hardware_. Per la gestione della memoria virtuale occorrono diversi algoritmi: - fetching (delle pagine) - paginazione a richiesta = 1 pagina è caricata solo quando richiesto - prepaginazine = si prova a caricare le pagine attigue in anticipo - posizionamento (dei segmenti) - best fit - first fit - next fit - sostituzione (delle pagine) -> PROBLEMA: bisogna evitare il *thrashing* - *LRU = Least Recently Used* (con uno stack) -> PROBLEMA: implementazione onerosa - *FIFO = First In First Out* -> PROBLEMA: poco efficiente funzionamento: Il SO gestisce i frames allocati come un _buffer circolare_. - *Page buffering* = FIFO + 1 buffer in cui vengono mantenute le pagine da sostituire per un po' prima di essere effettivamente sovrascritte - *Clock* (use bit, circular buffer) funzionamento: - Ad ogni frame è associato un *use bit*. Questo è settato ad "1" ogni volta che il processo vi accede. - Inoltre ci si serve di un *next frame pointer* = un puntatore che scorre circolarmente tutti i frames. Questo punta sempre al frame seguente dell'ultima sostituzione. - Per trovare il prossimo frame, il puntatore scorre circolarmente trasformando gli "1" che incontra in "0" e si ferma quando incontra uno "0" = I/O devices = caratteristiche: - generalità (astrazione) -> rappresentazione gerarchica per layers/caratteristiche -> HAL = Hardware Abstraction Layer - efficienza -> software buffering/caching, scheduling Una operazione di I/O _non_ può avvenire se l'area di memoria sorgente/destinazione del trasferimento è _bloccata_. PROBLEMA: Ciò impedirebbe lo swapping totale di un processo bloccato SOL.: si fà uso di un *buffer di I/O* nell'area di memoria del SO, condiviso tra i processi. PROBLEMA2: il SO deve mappare le assegnazioni delle aree del buffer ai processi. tipi di buffering: - *single buffer with read-ahead* = lettura anticipata del prossimo blocco/byte - *double buffer with swap* = uno riempito dal processo, l'altro usato dal SO per l'I/O - *circular buffer* -> viene gestito con degli algoritmi ~ procuttore/consumatore == Disk scheduling & caching == Le richieste di I/O su disco dei processi vengono gestite dal SO in una coda. Per minimizzare il seek time occorre un'apposita _politica di scheduling_ per la selezione delle richieste dalla coda. - secondo il richiedente: - RSS (casuale) -> la peggiore - FIFO \ traggono qualche vantaggio - LIFO / dal principio di località -> PROBLEMA: starvation - per priorità -> PROBLEMA: starvation - secondo l'elemento richiesto: - *SSTF = Shortest Service Time First* = si sceglie sempre la richiesta con seek-time minore. -> PROBLEMA: bisogna conoscere la _posizione attuale_ della testina e calcolare i tempi - *SCAN* = la testina esegue una scansione delle traccie del disco soddisfacendo _tutte_ le richieste in coda problemi: - non si avvantaggia del principio di località - i processi che richiedono l'accesso alle traccie agli estremi sono avvantaggiati varianti di SCAN: - *C-SCAN* = il soddisfacimento delle richieste avviene _solo in una direzione_ della scansione, e non entrambe - *N-step SCAN* - *FSCAN* - *LOOK* / elevator algorithm = la scansione si ferma subito se non ci sono nuove richeste Per ottimizzare ulteriormente l'accesso al disco è possibile usare una *cache del disco* gestita dal SO in memoria principale. Richiede un algoritmo di sostituzione: - *LRU = Least Recently Used* = la cache è gestita come uno _stack di puntatori_, ogni volta che un blocco è richiesto lo si sposta in cima allo stack - *LFU = Least Recently Used* = ad ogni blocco nella cache è associato un _contatore delle richieste_ -> PROBLEMA: può non sfruttare adeguatamente il principio di località - *Frequency-based replacement* -> il migliore funzionamento: - la cache è gestita come uno stack di puntatori come nell'LRU. - lo stack è diviso in _sezioni (nuova, intermedia, vecchia)_. - quando si ha una richiesta di un blocco già presente nella cache esso viene posto in cima allo stack ed il suo contatore incrementato sse si trovava nella sezione vecchia Le performance della cache dipendono da: - algoritmo di sostituzione -> max *hit ratio* - dimensione della cache == Hard disk e partizioni == L'hard disk è un dispositivo *block-oriented* = l'unità minima di trasferimento è 1 blocco / 1 settore (di una traccia). La dimensione tipica di un blocco è 512 bytes (for magnetic disks) or 2048 bytes (for optical discs). Di solito il SO utilizza una *unità di allocazione >= unità minima di trasferimento*. Ad es. su Widows, 1 *cluster* da 4KB = 8 blocchi da 512 bytes. allocation unit / cluster size smaller vs bigger: - smaller = slower, more storage, more fragmentation - bigger = faster, less storage (more "slack"), less fragmentation Il primo blocco del disco è il *MBR = Master Boot Record*. contiene: - *MPT = Master Partition Table* -> top level partitions definitions - *bootstrap code* = instructions to identify the configured bootable partition, then load and execute its *Volume Boot Record (VBR)* as a chain loader. - 32-bit disk timestamp (optional) - 32-bit disk signature (optional) tipi di partizioni e restrizioni: - top-level (max 4): - *primary partitions* (bootable) (max 3/4 - if more than 1 you must tell the computer which primary partition is to boot from = you must set an "active" partition) - *extended partition* (not-bootable) (max 1) - *logical / secondary partitions* (not bootable) (unlimited number) Le partizioni top-level sono definite nel MBR. Le partizioni logiche sono definite con tanti *EBR = Extended Boot Record* linkati tra loro. "Unlike primary partitions, which are all described by a single partition table within the MBR, and thus limited in number, each EBR precedes the logical partition it describes." NOTE: - non è possibile unire/fondere 2 partizioni di tipo diverso (primaria+estesa); - è sempre possibile estendere/ingrandire una partizione verso destra; - non è sempre possibile shrinkare/ridurre una partizione verso sinistra. === Formattazione === Comunemente con il termine "formattazione" si intende l'inizializzazione di un file system in una partizione. La formattazione definisce: - tipo di file system - dimensione dell'unità di allocazione - etichetta e altri metadati associati al volume (criptazione trasparente, etc.) NOTA: una volta effettuata la formattazione non è possibile modificare questi parametri! Più precisamente, questo tipo di formattazione è la *HLF = High-Level Formatting* = set up an empty file system on the disk, and install a boot sector. Sometimes it searches and marks bad sectors. effettuata con: Windows' foot DOS/Windows' "format" console command Linux' "mkfs..." console command (altri tool di 3e parti) Esistono anche altri tipi di "formattazione": - *LLF = Low-Level Formatting* = used to define HDD geometry (setup boundaries of positions of the tracks and sectors on the hard disk). effettuata con: HDD manufacturer proprietary tool - disk reinitialization / zero-fill (sometimes also referred as "LLF") = sovrascrittura di tutti i settori del disco, per ragioni di sicurezza effettuata con: dd if=/dev/zero of=/dev/hda1 (altri tool di 3e parti) == FS = File System == Il file system è un *database*, strutturato secondo una *gerarchia di dati*: - file - record - campi A livello logico un *file* è costituito da un insieme di *record* ed è identificato da un *nome simbolico* univoco. I file possono essere organizzati in una *directory* che contiene tutte le info necessarie al SO per la loro gestione: - nome \ - tipo/contenuto / info di base - dispositivo di memorizzazione \ - indirizzo fisico di partenza | info per indirizzamento - bytes usati e allocati / - utente proprietario \ - azioni permesse / info per controllo accessi - data creazione, ultimo \ accesso/modifica | info d'uso - _uso corrente_ / Un file è identificato univocamente dal *pathname* (ad es. "C:\WIDOWS\system.ini"). struttura della directory: - a 2 livelli = dir principale + dirs utenti - gerarchica / ad albero = ogni dir (compresa la root) può contenere subdirs e files A livello hardware, i file sono memorizzati in blocchi su memoria secondaria. Un file può essere _allocato_ -> *pre-allocazione != allocazione dinamica* in una o più *porzioni* contigue, gestite mediante una *FAT = File Allocation Table*. Le porzioni possono essere: - grandi, variabili, continue -> migliore performance nell'accesso sequenziale, ma con frammentazione esterna - picocle, fisse, discontinue (blocchi) -> facilita la riallocazione La struttura della FAT dipende dal metodo di allocazione: - *a. continua* = il fle occupa una porzione contigua. PROs: buon accesso casuale, FAT compatta CONs: solo per preallocazione, frammentazione esterna - *a. a catena* = ogni blocco contiene un puntatore al blocco allocato seguente. Ogni entry della FAT contiene un puntatore al 1° blocco e la dimensione del file. PROs: buon accesso sequenziale, FAT compatta CONs: cattivo accesso casuale - *a. indicizzata* = la FAT contiene solo un puntatore all'_indice del file_ che a sua volta contiene i puntatori a tutte l porzioni allocate del file Tutte le tecniche precedenti richiedono anche una *tabella di allocazione del disco* per sapere quali blocchi del disco sono used/unused. tecniche di gestione: - *bitmap/tabella di bit* = si associa un flag ad ogni blocco del disco PRO: accesso random come un array CON: la tabella deve essere tenuta in memoria principale - *porzioni libere a catena* = ogni porzione è collegata a quella seguente da un puntatore ed un valore della lunghezza della stessa PRO: tabella minimale CON: peggiora le performance delle operazioni sui files - *indicizzazione* = ogni entry della tabella contiene un puntatore ad una area libera su disco e la sua dimensione Anche la directory dei files e le info di controllo devono essere memorizzate su disco, solitamente in una area apposita, separata dai file stessi. Per motivi di efficienza i *metadati* associati ad un file _non_ vengono di solito aggiornati in maniera sincrona sul disco e sulla (loro copia in) memoria. PROBLEMA: perdita della _consistenza_ del file system se l'aggiornamento su disco viene perso per qualche motivo. SOL.: *ripristino della consistenza* con appositi tool (ad es. "scandisk") forniti dal SO. SOL.(2): alcuni file systems utilizzano il *journaling* ed un modello transazionale per garantire la consistenza. === FAT = File Allocation Table === Il file system FAT fu introdotto alla fine degli anni '70 per i floppy disk. In seguito divenne il file system più usato anche per gli hard disk dei PC con SO Microsoft (DOS e Windows). Attualmente anche se il suo uso è scosigliato per gli hard disk, è ancora il file system più usato per le memorie flash (SD, etc.). nomenclatura strutture fisiche-logiche: - *volume* = 1 partizione logica su disco contenente un file system indipendente - *settore* (~blocco) = unità di allocazione fisica minima - *cluster* (uno o più settori contigui) = unità di allocazione logica minima OSS.: Il n° di settori per cluster varia a seconda della dimensione del volume. I cluster forniscono così una astrazione sulla dimensione fisica dei settori. struttura: *----------*--------*--------*----------*----------------------------------* | reserved | FAT #1 | FAT #2 | root dir | user data | *----------*--------*--------*----------*----------------------------------* - reserved sectors (include il boot sector, BPB=BIOS Parameter Block, ...) - FAT #1 (dimensione = FAT entries size * number of disk clusters) - FAT #2 (copia ridondante di sicurezza) - root dir (FAT12 and FAT16-only) (fixed size of 512 entries on a hard disk and the size on a floppy disk depends) - user data region Le entries della FAT hanno dimensione fissa. Si distinguono varie versioni a seconda delle loro dimensioni: FAT12 = 12 bit -> up to 4096 clusters per volume FAT16 = 16 bit FAT32 = 32 bit Ogni entry della FAT fa riferimento ad un cluster del disco e può contenere: - 0 = cluster libero - !0 = cluster usato: - un puntatore all'indice del cluster seguente del file -> _allocazione concatenata a blocchi_ - tutti 1 = fine del file / ultimo cluster usato dal file - bad cluster marker Le *directory tables* sono memorizzate come files nell'area "utente", e contengono tutte le info di controllo per la gestione dei files stessi: - filename (8.3 | LFN = Long File Names) - attributi (archive, directory, hidden, read-only, system and volume) - timestamps - dimensione in bytes - indice del primo cluster PROBLEMI: - nessun supporto per la gestione degli accessi ed il ripristino della consistenza del file system - frammentazione dei files - scarse performaces (peggiorano ulteriormente al crescere della FAT -> non può essere mantenuta in memoria principale) === NTFS = (Windows) NT File System === Introdotto con Windows NT, è attualmente il principale file system utilizzato su Windows. features: - nomi file a 255*16-bits (case insensitive) - supporto volumi e file molto grandi (16 exabytes max) - allocazione mediante bitmap - *USN = Update Sequence Number Journal* - supporto a diversi tipi di *reparse points*: - hard links (UNIX-like) = link to a file MFT entry; - symbolic links (UNIX-like), local or remote, relative or absolute SMB file or path; - *junction points/directory junctions*, only local absolute directory path; - *volume mount points* (UNIX-like with limitations) = consentono di montare un volume in una directory vuota - forks / *ADS = Alternate Data Streams*, using the filename format "filename:streamname" - *sparse files* = allocazione effettiva solo dei blocchi con dati reali / non nulli - compressione e crittografia trasparenti (EFS = Encrypting File System) - VSS = Volume Shadow Copy Service - TxF = Transactional NTFS - disk quotas - possibilità indicizzazione file per contenuto struttura: *-------*----------*-----------------*-----------*-----------------* | MFT > MFT zone | file area | metafiles | file area | *-------*----------*-----------------*-----------*-----------------* - *MFT = Master File Table* (growing to the right), una tabella con record a lunghezza variabile (include il jornal, la allocation bitmap, e altri metadati) - *MFT Zone* = MFT-preallocated space (default size: 12.5% of volume) (will be allocated to files if the unreserved space on the disk is full) - metafiles backup = the first 16 MFT records (system files) internals: - Tutti i metadati sono rappresentati come files ($MFT, $Volume, $Bitmap, $Boot, etc.). - *MFT = Master File Table*, una tabella con record a lunghezza variabile, descrive tutti i file nel volume. - Ogni entry della MFT rappresenta un file e contiene: - *resident data* = l'inizio (header) del file - *non-resident data references* = una serie di puntatori ai blocchi allocati nella file area - tutti gli *attributi* del file (nome, timestamps, etc.) "In NTFS, files are collections of attributes" An NTFS directory pretty much stores only information about the directory itself, not about the files within the directory. (!= FAT) Everything within NTFS is considered a file, and that applies to directories as well. Each directory has an entry in the Master File Table, which serves as the main repository of information for the directory. To improve performance, NTFS directories use a special data management structure called a B-tree. affidabilità: - journaling delle operazioni / logging -> facilmente reversibili - mantiene doppia copia della MFT sicurezza: NTFS usa un modello "discrezionale" più flessibile di quello standard in Unix. Ad ogni file è associata una *ACL = Access Control List*. Ogni ACL contiene più *ACE = Access Control Entries*, che indica un utente ed un azione (definisce esplicitamente "chi può fare cosa"). NTFS default cluster size / allocation unit size: 512 - Windows default for volumes <512MB 1K - Windows default for volumes 512MB-1GB 2K - Windows default for volumes 1GB-2GB 4K - Windows default for volumes >2GB, = memory page size 8K - do not support transparent compression 16K - do not support transparent compression 32K - do not support transparent compression === Unix file systems, caratteristiche comuni === Unix "vede" i file come semplici stream di bytes (non distingue binary/text files), la struttura logica interna è curata dalle applicazioni. I file possono essere di diversi tipi: - normali / ordinari (indicated by a dash '-') - speciali - d = directories - l = *symbolic links* = riferimento simbolico ad un file (mediante il suo path) - c/b = device files -> distinzione tra char/block devices - p = named pipes \ - s = sockets / meccanismi di IPC NOTA: a volte si indicano come "special files" solo i device files. Tutte le info _sui files ordinari_ sono contenute nella *i-node table* (memorizzata su disco). Gli i-node sono di dimensione fissa e vegnono caricati in memoria principale all'apertura del file. Ad un singolo i-node possono essere associati più *hard links* = nome alternativo di un file (!= symbolic links), anche in diverse directories. { Anche se un file può avere più hardlinks in diverse locazioni, ad ogni file sempre è associato un unico i-node. } Ogni i-node contiene nell'ordine: - tipo di file (normal/dir/special) - no di hard links - UID del proprietario - GID del proprietario - permessi di accesso - dimensione in bytes - tabella indirizzi dei blocchi dati - timestamps OSS.: NON contiene il filename! tutte queste info possono essere lette ad es. con il comando "ls -lis": 72670 8 -rwxr--r-- 1 penguin birds 213 Oct 2 00:12 prova.txt [indice inode] [no blocchi usati] [permission bits] [hardlink counter] [user and group owners] [dimensione in byte] [data ultima modifica] [nome del file] Le directories sono sequenze di bytes come i files ordinari. Ogni directory entry associa: - filename / nome del file (case sensitive) - *i-number* = riferimento ad un i-node OSS.: oltre a questa associazione, le directories non contengono nient'altro! { L'i-node contiene tutte le info per l'indirizzamento e la protezione del file. In particolare, contiene 1 campo con 10 indirizzi diretti ai primi 10 blocchi del file ed 1 puntatore ad 1 blocco indiretto singolo, 1 doppio, e 1 triplo. I "blocchi indiretti" sono dei blocchi che contengono degli indici. Possono essere a pià livelli. L'allocazione dei file è: - dinamica - basata su blocchi - con indicizzazione } = Fonti = Stallings - Sistemi Operativi (3e) (Jackson Libri) (2000)