Appunti ragionati di Sistemi Operativi · naming, al bufering ed alla gestione dei malfunzionamenti...

Appunti ragionati di

Sistemi Operativi

Realizzato per l’Università Telematica InternazionaleUNINETTUNO

Studente: Lorenzo L. AncoraDocente: Prof. Claudio Fornaro

VERSIONE WEB

Quest'opera è stata rilasciata con licenza Creative Commons Attribuzione - Condividi allo stesso modo 4.0 Internazionale.

Quest’opera è distribuita con una licenza compatibile con l’iniziativa Free Cultural Works, volta a garantire:

• la libertà di usare l’opera;

• la libertà di studiare l’opera ed utilizzare le nozioni apprese;

• la libertà di creare e distribuire copie, totali o parziali, dell’opera;

• la libertà di modifcare, migliorare e ridistribuire l’opera derivata.

Per leggere una copia della licenza visita il sito web:

http://creativecommons.org/licenses/by-sa/4.0/

Tutti i marchi citati nel testo appartengono ai rispettivi proprietari: devono essere utilizzati con il massimo rispetto e solo a fne didattico.

Questa versione è la controparte digitale della release cartacea.A seconda del file scaricato può contenere solo parte del testo.

METADATI

Titolo: Appunti ragionati di Sistemi OperativiAutore: Lorenzo AncoraRelease: 16/05/18Versione: 1.5.7 - WEBFonte: http://ht.ly/MTyk30jPsQK

STATISTICHE

# pagine: 35# paragrafi: 326# parole: 6659# caratteri: 42781

http://ht.ly/MTyk30jPsQK

http://creativecommons.org/licenses/by-sa/4.0/

Indice generale

1 • Il sottosistema di Input/Output................................................................................81.1 • I driver................................................................................................................... 121.2 • DMA e dischi...................................................................................................... 18

1.2.1 • I dischi........................................................................................................... 181.2.2 • RAID.............................................................................................................. 20

2 • Il flesystem............................................................................................................... 222.1 • Organizzazione del flesystem.....................................................................242.2 • Filesystem UNIX...............................................................................................28

Indice di supporto

Prefazione............................................................................................................................ 5Legenda............................................................................................................................... 6

Appunti ragionati di Sistemi Operativi

4

Prefazione Capitolo

Prefazione

Questo breve compendio raccoglie parte dei miei appunti, scritti per il corso di Sistemi Operativi dell’Università Telematica Internazionale UNINETTUNO. Il testo segue fedelmente le videolezioni dei docenti Maurelio Boari e Paolo Ancilotti, integrandole con esempi, spiegazioni e note ove necessario.

Gli appunti, prima semplici lavagne e fogli, sono stati digitalizzati e rielaborati per consentire sia il ripasso veloce che l’approfondimento da parte di terzi, per cui ho cercato un ragionevole compromesso tra dettaglio e semplicità. Questa trattazione non sostituisce il libro di testo (lettura raccomandata: “Sistemi Operativi” di Ancilotti, Boari, Ciampolini e Lipari) ed è stata concepita come ausilio mnemonico per chi ha già seguito il corso universitario.

Il testo è suddiviso in capitoli, scaricabili e stampabili separatamente: ogni sezione tratta un singolo argomento del corso originale e se serve ricapitola i concetti già visti secondo il punto di vista più opportuno. Il tutor o il docente suggeriranno quali parti studiare ed il metodo di studio più efcace.

Per orientarsi (sono pur sempre gli appunti di uno studente...), il lettore può consultare la legenda e l’indice interattivo dei capitoli. Il testo è dotato anche di alcune appendici, che ho scritto per far risparmiare tempo e fatica a chi desidera approfondire i contenuti.

Spero che questo contributo possa risvegliare la curiosità dello studente verso uno strumento che, troppo spesso, diamo per scontato ma che è indispensabile per l’uso e la programmazione dei moderni computer: il Sistema Operativo.

Lorenzo Ancora

5





Capitolo Prefazione

Legenda

Apparenza Signifcato

Testo in grassettoTerminologia chiave rilevante rispetto al contesto. Termini da tenere a mente.

Testo in corsivoDettaglio che merita attenzione. Frasi da tenere in considerazione quando ci si smarrisce.

Testo comune

Inserto contestuale

Testo comune

Ammodernamenti, suggerimenti e considerazioni personali. Paragrafi che possono essere ignorati da chi non ha bisogno di approfondire.

Testo comune

Inserto letterale

Testo comune

Citazione e/o formula. Paragrafi che devono essere letti preferibilmente in modo letterale ed appuntati se necessario.

• Testo

commento:

▪ Testo annidato

commento annidato;

• Testo;

Lista gerarchica. Gli elementi più annidati dipendono dall’elemento più esterno che li precede. Il commento rientrato si riferisce sempre all’elemento di lista che lo precede.

1. Testo commento;

2. Testo;

Lista gerarchica ordinale. Il commento rientrato si riferisce sempre all’elemento di lista che lo precede. Il numero di lista ha valore semantico rispetto al contesto.

Codice sorgenteListato di codice sorgente o pseudo-codice.

Questa legenda vale per tutti i capitoli degli appunti.

6

Le periferiche Capitolo

Le periferiche

7

Capitolo 1 Il sottosistema di Input/Output

1 • Il sottosistema di Input/Output

Durante alcune porzioni della propria runtime il processo deve utilizzare i device di I/O (Input/Output, Ingresso/Uscita) che vengono allocati come periferiche e quindi, a diferenza di CPU e memoria, senza usare la virtualizzazione.

Il sottosistema di I/O deve nascondere agli sviluppatori i dettagli specifci della gestione di ciascun dispositivo (come le periferiche) ed al contempo gestire i malfunzionamenti hardware, tutto nel modo più trasparente ed automatico possibile. In particolare deve saper gestire diferenti tipi di difetti, che possono essere umani (svista o incomprensione nell'uso del dispositivo da parte dell'utente), transitori (come ad esempio le interferenze EM) o permanenti (tipicamente danni meccanici). Non sempre gli errori di I/O sono gestibili senza l'intervento dei livelli applicativi più alti o dell'utente.

Il sottosistema deve ricercare l'omogeneità dei nomi (naming) e garantire la sincronizzazione tra periferiche e processi, poiché la CPU è quasi sempre più veloce dei device.

UNIX ed i suoi derivati come GNU/Linux eccellono nel naming, grazie alla loro capacità di uniformare l'accesso usando i device fles, posti nel flesystem tramite astrazioni del eernel.

Le istruzioni di I/O (istruzioni a livello macchina) fanno riferimento ai registri del controllore di ciascun device, che si frappongono nel bus tra la CPU ed il device stesso. I controllori variano in base al device connesso che si classifca come:

• a caratteri

come mouse, tastiere o stampanti, ovvero dispositivi che inviano/ricevono un fusso di byte dal dominio ben noto;

8

Il sottosistema di Input/Output Capitolo 1

• a blocchi

come le memorie di massa, che inviano/ricevono blocchi di dati dal dominio non necessariamente noto a priori;

• speciali

come i timer e tutti quei dispositivi che si limitano a cadenzare interruzioni, producendo informazioni potenzialmente utili senza però trasferire dati;

Esistono altri modi di classifcare i dispositivi, in base al ruolo (es. collegamento remoto), ai possibili errori, ai malfunzionamenti fsici o ancora in base alla velocità espressa come ordine di grandezza dei dati trasferibili.

I guasti transitori si rilevano tramite Controlli di Ridondanza Ciclica (CRC) o con metodi più specifci per le verifche in lettura ed, in genere, basta ripetere l'operazione fnché il disturbo alla radice dell'errore non scompare.

Lo sviluppatore utilizza l'I/O API per operare sui dispositivi di I/O tramite nomi simbolici, eventualmente presenti come fle speciali sul flesystem.

I trasferimenti da e verso questi device possono essere:

• sincroni

bloccanti per il processo richiedente;

• asincroni

non bloccanti per il processo richiedente.

Tutti i trasferimenti possono essere mediati e facilitati tramite la tecnica del bufering.

9


Il bufering viene fatto dal livello di I/O device-independent ed usa più bufer di sistema per accumulare i dati in ingresso o in uscita dal SO. Questi dati vengono accodati a ciascun bufer libero fnché non si riempie o si raggiunge la quantità di dati richiesta dal programma e nel frattempo i bufer che si sono svuotati vengono riempiti, permettendo di fare altro I/O (vd. "read ahead" e doppi bufer). In realtà il bufering ha anche tante altre applicazioni, come ad esempio il fare caching per le memorie di massa riducendo gli accessi duplicati.

L'I/O API è il livello più alto, basato sulla parte del sistema di I/O indipendente dai device, fondata a sua volta sull'interfaccia di livello inferiore indipendente dai dispositivi fsici e così via fno a giungere all'interfaccia dipendente dai dispositivi fsici ("device-dependent"). Quest'ultima interfaccia implementa i driver, ovvero quei programmi altamente specializzati nel gestire i dettagli di ciascun dispositivo connesso. La parte device-dependent con la sua interfaccia specializzata implementa anche i gestori delle interruzioni hardware (interrupt handlers) tramite i driver. La parte indipendente dai device si limita in realtà al naming, al bufering ed alla gestione dei malfunzionamenti più gravi, ma solo dopo aver allocato i device ai processi in modo appropriato, rispettando ad esempio la necessità di alcune periferiche (come le stampanti) di ricevere direttive e fussi di dati in mutua esclusione.

Le interruzioni hardware delle architetture più comuni sono gestite con la tecnica IRQ (Interrupt ReQuest) e sono fsicamente implementate utilizzando i controllori PIC (Programmable Interrupt Controller) o APIC (Advanced Programmable Interrupt Controller).

Il bufering è richiesto quando un device è molto più lento della CPU, considerazione valida anche per i dispositivi a blocchi di uso quotidiano. Il bufering funziona accumulando i dati letti dal device in un bufer riservato nella memoria principale dal SO, che sarà poi ricopiato volta per volta nel bufer utente (nominato anche come "u-buf", o user bufer) allocato dal processo. Se il SO ha almeno due bufer dedicati all'I/O (cosa comune a tutti i

10


sistemi moderni), essi possono essere commutati vicendevolmente per velocizzare il trasferimento: il bufering aumenta la performance scambiando il bufer di sistema designato per la scrittura con l'altro, che nel frattempo è stato svuotato, ogni qual volta è pronto per essere ricopiato nel bufer utente.Con questa tecnica il device non rimane mai inattivo durante i trasferimenti perché, fnché un processo attende il suo OUTPUT, è sempre in corso un trasferimento in lettura verso uno dei bufer di sistema e questo comporta una migliore efcienza di calcolo ed un maggior risparmio energetico a lungo termine, tutto questo in modo quasi del tutto trasparente alle applicazioni.

11


1.1 • I driver

I guasti e gli eventi anomali permanenti vengono sollevati come eccezioni verso i livelli superiori del SO, che provano a gestirli senza l'interazione dei processi utente. I problemi semantici (ovvero quelli derivanti dall’utente o da cattive implementazioni) sono considerati come errori permanenti e la loro gestione è delegata ai processi tramite un errore (i processi potrebbero essere costretti a richiedere l'interazione dell'utente).

Un tipico esempio è il tentare di scrivere su una memoria esterna (come un foppy o una memoria fash) dopo aver attivato il blocco hardware per la scrittura: la semantica dell’operazione è errata, perché la richiesta di scrivere su un dispositivo read-only è priva di senso. In questo caso le applicazioni devono mostrare un errore e delegare la risoluzione all’utente.

I dispositivi possono essere condivisi in mutua esclusione o tramite IPC con un processo server: lo spooling consente, tramite appositi fle di spool (tipicamente uno per processo), di delegare la gestione ad un singolo processo server.Il processo server riordina, fltra e processa ciascun fle di spool accettato come INPUT, rappresentando quindi l'implementazione ideale delle code di stampa e di funzionalità afni.

Una tipica funzione dell'interfaccia device-dependent dei SO più difusi è nella forma:

int read( dispositivo, sysbuffer, nbytes );

ove:

• dispositivo

nome unico del device a cui inviare la richiesta di lettura, prodotto del naming;

12


• sysbufer

un bufer allocato dal SO appositamente per la lettura;

• nbytes

numero di bytes che il programma desidera leggere, non necessariamente corrispondenti al numero di quelli che saranno poi efettivamente letti;

Ciascun controllore, a prescindere dalla periferica che gestisce e media, ha almeno 3 registri accessibili dal SO:

• Registro di controllo (contiene anche i bit “i” ed “a”)

sola scrittura. Confgura la modalità di funzionamento del dispositivo;

• Registro di stato

sola lettura. Rappresenta lo stato di svolgimento del compito assegnato al dispositivo;

• Registro dati

area di transito per i dati di I/O da e verso il SO. Qui viene memorizzato il payload dei compiti dopo che il loro stato di svolgimento è diventato favorevole;

I dispositivi più complessi possono avere un numero variabile di questi registri che conservano tali valori semantici, con variazioni a seconda del protocollo di trasferimento. D'ora in avanti - per semplicità - li considererò unici.

Il bit del registro di controllo "i", nell'istante della propria attivazione, abilita il dispositivo ad inviare interruzioni al completamento del compito assegnatogli; il

13


bit del registro di controllo "a", in seguito alla propria attivazione, abilita il dispositivo allo svolgimento di ulteriori compiti.

Nel registro di stato sono contenuti dei bit di errore ed un bit fag, che indica il completamento delle operazioni che costituiscono il compito.

Ciascun dispositivo connesso all'elaboratore può essere idealizzato come una CPU special-purpose, capace di eseguire una sequenza di operazioni dal dominio ben noto, che darà vita ad una sequenza di azioni predefnita da parte del dispositivo. Chiamiamo questa sequenza "processo esterno", in quanto viene eseguita in parallelo ai processi della CPU. Un tipico processo esterno si compone di alcuni passi:

1. attesa di "a" (vd. registro di controllo)

attende il bit di start, rimanendo in stand-by fnché è disattivato;

2. esecuzione del compito richiesto dalla CPU;

3. attivazione del bit di fag (vd. registro di stato)

segnala la fne del comando attivando il bit di fag;

4. stand-by.

Può anche essere esemplifcato come:

/* Pseudo-codice in linguaggio C. * Rappresentazione del processo esterno. */while(true) { // Runtime predicibile.

do { // Attesa dell'attivazione.[...]

} while(a == false);// [Esegui compito della CPU.]

}

Il processo utente prepara il comando e lo invia al processo esterno che inizia a svolgere il compito assegnatogli, mentre il processo che lo ha richiesto fa l'attesa attiva del payload.

14


Può anche essere esemplifcato come:

/* Pseudo-codice in linguaggio C. * Rappresentazione del processo interno con attesa attiva. * Pattern: controllo di programma. */// [Invia comando al device.]do { // Attesa attiva

[...]} while(flag == false);// [Verifica l'esito.]// [Reagisci e ripeti.]

Questo pattern è detto "a controllo di programma" e non usa le interruzioni, per cui mal si adatta ai sistemi multiprogrammati. La soluzione è il pattern "a interruzione di programma" ove ciascun device ha riservato un semaforo, il cui compito è indicare la disponibilità dei dati partendo dallo stato che è inizialmente azzerato. Quando il bit "i" del registro di controllo viene preventivamente attivato, il device può avvertire il processo tramite un nuovo interrupt. In questo modo i processi utente possono subire il cambio di contesto durante l'attesa dell'I/O, con enormi vantaggi prestazionali!

Il pattern a interruzione di programma necessita di specifci gestori delle interruzioni (interrupt handlers), implementati dai driver.

Ogni driver fa I/O sui registri del controllore per consentire alla CPU di comandare il device: la CPU memorizza i comandi nel registro di controllo e, in seguito all'attivazione del suo bit di start, il controllore li trasforma in segnali che il device può interpretare; quando il dispositivo completa il tase assegnatogli dalla CPU esso aggiorna almeno due fag nel registro di stato, rispettivamente per segnalare eventuali errori e per indicare la fne dell'operazione. In realtà il processo è molto più complesso ed il driver si occupa di gestirne tutte le peculiarità strettamente dipendenti dal device.

15


Per implementare la virtualizzazione ciascun device driver include per il proprio dispositivo un descrittore che contiene:

• indirizzo del registro di controllo;

• indirizzo del registro di stato;

• indirizzo del registro dati;

• semaforo "dato disponibile";

• contatore dei dati da trasferire;

• puntatore al bufer del SO

posto nella memoria principale per accogliere i dati trasferiti durante l'I/O;

• campo "esito del trasferimento".

La funzione virtualizzata per la lettura deve anch'essa subire alcune variazioni, proprio perché appartiene al livello device-dependent:

int read( int dispositivo, char* sysbuffer, int nbytescont );

ove:

• dispositivo

nome unico del device a cui inviare la richiesta di lettura, prodotto del naming;

• sysbufer

indirizzo nel descrittore. Un bufer allocato dal SO appositamente per la lettura;

• nbytescont

parte del descrittore. Numero di bytes che il programma desidera leggere, non necessariamente corrispondenti al numero di quelli che saranno poi efettivamente letti;

In questo esempio è stato palesato il tipo degli argomenti che però può subire variazioni in base al tipo di dispositivo.

16


Il bufer ed il numero di dati da leggere vengono salvati nel descrittore, il device viene attivato e si attende l'esito con la chiamata di sistema "wait" sul bit di disponibilità del descrittore. Alla fne sia le funzioni a basso livello che l'interrupt handler gestiscono parte degli errori e lo sviluppatore ha maggiori probabilità di ottenere un payload utile dal dispositivo.

17


1.2 • DMA e dischi

I dispositivi DMA possono rubare cicli alla CPU ("cycle stealing" mode) per copiare in memoria i registri del controllore usando un canale apposito.Il DMA usa due campi simili al contatore ed al bufer del descrittore operando in modo simile al pattern "a gestione di programma" e - dal punto di vista dei processi - l'unica cosa che cambia è il numero di interruzioni che si riduce ad uno, senza che le applicazioni utente debbano subire modifche: i processi utente accedono soltanto allo strato device-independent più elevato del sottosistema di I/O usando chiamate di sistema, ovvero invocazioni che generano interruzioni e ricevono come argomento sia il bufer utente che la sua dimensione.Questo bufer è indipendente da quello del SO e viene riempito alla fne di ciascun trasferimento: il bufer di sistema diferisce in dimensione da quello utente, che riceve solo la quantità di dati desiderata dallo sviluppatore.

Queste funzioni di sistema invocano tradizionalmente le loro omonime di più basso livello (ad esempio "read" invocherà "_read").

1.2.1 • I dischi

I primi dischi (dischi foppy) erano supporti di memorizzazione plastici su cui veniva depositato del materiale magnetico. Questo materiale magnetico permetteva l'I/O ed era suddiviso in tracce circolari concentriche, ulteriormente separate in settori tramite minuscoli spazi ben defniti detti "gap" (termine generico per indicare uno spazio libero, qui termine tecnico). Alcuni dischi erano a doppia faccia e quindi usavano coordinate ternarie.

I moderni dischi rigidi sono in genere di alluminio ed usano sofsticate cache, ma comunque le nozioni elencate continuano ad essere valide.Le memorie a stato solido (SSD) richiedono una trattazione a parte.

Se i dischi sono più di uno si dice che sono organizzati in "pacchi" e le tracce sullo stesso asse si dicono cilindri e costituiscono un'ulteriore coordinata (es. su

18


un piano cartesiano con centro sulla faccia esterna del primo disco del pacco, sarebbero allineati sull'asse Z).

Il tempo di seek (da "seeking", ovvero ricerca della locazione fsica) è nell'ordine dei millisecondi, a causa del vincolo puramente meccanico, aggravato anche dal tempo di rotazione del disco: è imperativo ridurre il tempo di posizionamento e rotazione!

Chiarimento in formule:

TF = TA + TT

TA = ST + RL

ove:

• TF è il tempo medio di I/O sul dispositivo

composto da:

• TT, che è il tempo di efettivo I/O;

• TA, che è il tempo medio di accesso.

TA è a sua volta composto dai tempi puramente meccanici:

• ST, che è il seek time

tempo di posizionamento;

• RL, che è la rotation latency

latenza causata dalla rotazione del disco.

Da questo possiamo dedurre che avremmo grossi vantaggi accedendo ai dati tra loro fsicamente prossimi ed allineati!

Questa ottimizzazione si attua tramite particolari algoritmi di scheduling, implementati in un unico processo server che gestisce le richieste di lettura e scrittura tramite una coda ben gestita. L'algoritmo migliore è quello che riduce il tempo medio di accesso ai dati desiderati da ciascuna richiesta pendente, usando una politica tendenzialmente FIFO (quindi non troppo pesante per la CPU) capace di evitare la starvation delle richieste di I/O. Tuttavia un algoritmo

19


puramente FIFO non predilige gli accessi su dati allineati e non è in grado di ridurre il movimento meccanico... esistono alternative migliori!

L'algoritmo Short Seee Time First (SSTF) riordina le richieste in ordine di prossimità fsica, riducendo gli spostamenti ma senza prevenire la starvation delle richieste più lontane.

L'algoritmo dell'ascensore (SCAN) è uguale a SSTF ma aggiunge il vincolo fondamentale di seguire un solo senso di spostamento alla volta, cambiando senso solo quando non ci sono più richieste nell'attuale direzione fsica di lettura. Con questa semplice ma geniale accortezza l'algoritmo SCAN previene la starvation, migliorando notevolmente la performance media, risparmiando energia e riducendo lo stress meccanico.

1.2.2 • RAID

RAID (Redundand Array of Independent Dises) è una tecnica sofsticata di virtualizzazione dei dischi che, se supportata da hardware professionale co erente, è capace di migliorare la performance ed al contempo rendere il sistema totalmente ridondante. Il disco virtuale, fatto da più dischi fsici indipendenti, può leggere in parallelo due settori su due dischi diferenti usando il DMA. Tramite la tecnica del mirroring la rottura di un disco su un sistema basato su RAID non causa la perdita di dati che, fnanche nei casi più gravi, possono essere recuperati in poche ore con l'aiuto di un professionista.

Esistono ben 7 standard che ci permettono di perfezionare un sistema con RAID e, nonostante siano tutti molto complessi, ormai anche le piccole aziende italiane possono adattare i sistemi esistenti alle versioni di RAID che prevedono la ridondanza con un budget minimo. D'altronde è sempre meno costoso tutelarsi contro la perdita di informazioni prima che avvenga, perché l'errore umano o un fallimento meccanico prima o poi potrebbero originare dei danni!

20

Il flesystem Capitolo

Il flesystem

21

Capitolo 2 Il flesystem

2 • Il flesystem

Il disco magnetico è una memoria di massa poiché può memorizzare grossi archivi di dati in modo persistente. Per farlo in modo agevole per l'utente fnale, il SO fornisce supporto ad uno o più flesystem, con lo scopo di fornire un sistema di archiviazione ordinato ed indipendente dalle strutture fsiche dei blocchi di dati, in modo che l'utente possa reperire i propri fle con comodità.

La "comodità" consiste nel poter strutturare le informazioni in gerarchie, per consentire la ricerca in base a dati e metadati su specifche collezioni di fles. Se l'utente fnale è ordinato e conosce le features del proprio flesystem, potrà ritrovare tutte le informazioni velocemente anche senza l'ausilio di un motore di ricerca locale.

Un fle è un contenitore di dati (detto anche "archivio", pur non essendo necessariamente compresso), tipicamente informazioni utili all'utente, dati temporanei dei software o enti logici più avanzati. Il fle è composto da informazioni tra di loro correlate e poste sulla memoria di massa, che possono essere in vari formati: eseguibili, sorgenti, grafci, musicali, vari tipi di fle oggetto etc. Il tipo del fle ne defnisce la struttura interna e deve essere ben noto e signifcativo per il programma che, tramite un processo, lo ha creato ed eventualmente riempito. Ad esempio un fle di codice oggetto è una sequenza di byte organizzati in blocchi, strutturati per essere interpretati dal lineer; un fle di tipo codice sorgente è - a seconda del linguaggio di programmazione in cui è stato scritto - un insieme di prototipi, funzioni, dichiarazioni di variabili etc.

L'utente può accedere e ritrovare un fle usando il suo nome simbolico, che lo collega ai blocchi di cui è composto sulla memoria secondaria, ai suoi altri attributi (ad esempio l'ora di creazione o di modifca) ed alle informazioni di protezione, fondamentali nei SO multiutente.

22

Il flesystem Capitolo 2

Sui sistemi DOS e superiori il fle deve essere dotato del corretto sufsso, detto estensione. Le estensioni sono superfue su UNIX e derivati perché il SO fornisce utilità e politiche per individuare il tipo corretto dei fle tramite i primi bytes, detti "magic number", o tramite deduzione strutturale.

Le variazioni sul tema sono tante: ad esempio in certi sistemi la dimensione dei fle è espressa direttamente con il numero di blocchi fsici allocati o fra gli attributi fgura il gruppo del creatore assieme ai diritti di accesso. Il fle è però un'entità dal profondo valore semantico, che rimane co erente negli anni e mantiene le caratteristiche qui elencate.

Le strutture dati che contengono gli attributi e gli altri metadati si chiamano descrittori di fle e risiedono sullo stesso supporto del fle, essendo oggetti persistenti (in gergo tecnico "long-lived") come il fle stesso, che sopravvive anche senza alimentazione grazie alle caratteristiche peculiari del supporto fsico magnetico o ottico.

Due classici per la ricerca di fles su GNU/Linux sono i comandi "fnd" (ricerche tramite descrittori) ed "rgrep" (full-text search ricorsivo), ma pochi sanno che nel sistema è installato un manuale della GNU Foundation che illustra le tecniche di ricerca più rafnate. Per visionarlo basta eseguire in una shell il comando "info Finding Files".

Il flesystem fornisce gli strumenti per creare, cancellare (non necessariamente in modo permanente o immediato), leggere, scrivere o eseguire un fle (se è un binario compatibile); inoltre controlla la correttezza degli accessi in quanto a sicurezza di processi e dati condivisi fra più processi nei sistemi multiprogrammati. Il flesystem deve consentire la strutturazione delle informazioni in formati più complessi della sequenza di byte (byte stream), consentendo il naming del fle in modo analogo ai device, ponendosi come il

23


livello più alto, idealmente inferiore a quello applicativo ed accessibile all'utente tramite i tool di sistema.

Il flesystem è nella pratica una collezione di fle, gestita da un sistema di catalogazione a cartelle ("directory structure", su UNIX e derivati è bene usare sempre il termine directory al posto di cartella) che si palesa all'utente fnale come un insieme di cataloghi navigabili: su Windows ogni catalogo parte da un'unità; su GNU/Linux - che in questo frangente rimane sempre molto più avanzato e fessibile - esistono standard per nominare le directory più importanti della gerarchia (che è puramente logica, ogni directory può essere un mount point, ovvero un punto di accesso, per una diferente partizione e flesystem), partendo sempre dalla directory radice, “/”, che - in casi davvero particolari, attualmente non standard - può anche essere fttizia (es. tramite il tool amministrativo "chroot").

Eseguire “cat /etc/mtab” per visionare tutti i mount point attivi, “info flesystem” per visionare la lista di flesystem nativamente supportati e “pwd” per vedere la directory corrente a partire dalla root.

Pensiamo al disco come ad un array di blocchi fsici indicizzabili per traccia e settore. Nei sistemi moderni, l'organizzazione fsica dei fle si fonda sul concetto di dispositivo virtuale, che è un'astrazione sulle periferiche. I device virtuali sono le partizioni (dette anche "volumi" o sui sistemi più esotici "minidischi") che suddividono i dischi fsici o li uniscono per simulare un supporto unico. Con queste astrazioni un singolo disco può contenere diversi flesytem e SO!

2.1 • Organizzazione del flesystem

Il livello fsico defnisce l'astrazione del fle allocando i dati in blocchi. Ciascuna partizione è suddivisa nella tabella dei contenuti (posta in loco predefnito e di dimensione nota a priori) e nella sequenza di blocchi di dati che costituiscono i fle. La tabella dei contenuti riunisce la tabella dei descrittori dei fle allocati sulla sua partizione e la lista dei blocchi liberi, che può essere un vettore di

24


bit, una lista concatenata o una lista di gruppi e viene creata alla formattazione con il comando "format".

Se l'allocazione dei blocchi è contigua, basta che il descrittore contenga l'indice del primo blocco del proprio fle di riferimento. Per evitare la frammentazione si può usare l'allocazione concatenata, che genera una lista concatenata di descrittori per ciascun fle, sacrifcando la velocità di accesso.

Una tecnica perfezionata è quella dell'allocazione tramite indice, ove il primo blocco del fle (puntato dal descrittore) indicizza, puntandoli, tutti i blocchi del fle, imponendo però un limite al numero massimo di blocchi per ciascun fle. UNIX e derivati superano questa limitazione, potendo puntare altri blocchi indicizzanti a partire dal primo.

Il livello dei metodi di accesso defnisce le modalità con cui ciascun processo può accedere ai fle, in base a criteri di sicurezza e modalità di accesso: sequenziale, diretta (che in gergo i programmatori chiamano "random" o "ad accesso casuale") o con chiave. Il fle può essere visto, infatti, come un vettore o un dizionario di record.

La modalità ad accesso diretto consente, appunto, di accedere direttamente a qualsiasi record del fle, senza dover leggere i precedenti ma con la necessità di conoscere l'ofset su memoria secondaria, con base all'inizio del fle richiesto; l'accesso con chiave è l'accesso diretto tramite chiave già nota, ove bisogna ricercare la chiave per poi avere accesso diretto all'informazione, con il vantaggio di non dover sapere dove essa sia fsicamente posta o in che ordine sia stata scritta; l'accesso sequenziale è il più primitivo (quindi sempre garantito ed implementato da tutti i sistemi) e, a diferenza dei precedenti, non necessita ovviamente di conoscere l'indice del record, perché il record viene riconosciuto durante la lettura dell'intero fle.

25


Il meccanismo di protezione, implementato proprio in questo livello, vale per tutti i tipi di risorse e ne gestisce le politiche ed i meccanismi di controllo delle politiche (ovvero la loro imposizione ai processi), in base al dominio di protezione. Il dominio è una coppia "<risorsa logica, diritti di accesso>", ove la risorsa è in genere un fle ed i diritti imponibili sono perlomeno "lettura", "scrittura" ed "esecuzione".

Ogni processo viene eseguito con uno specifco dominio e si può accedere quindi a ciascun fle - in base al processo che ne richiede l'handle al SO - con diversi diritti, creando di fatto una matrice sparsa fle-dominio. L'implementazione in base alla colonna dei fle si chiama "Access Control List" (ACL) ed è usata in UNIX; quella basata sulle righe dei domini è la "Capability List" (C-List), che defnisce per ciascun processo i diritti di accesso per ogni fle.

Alcuni sistemi (vd. Multics, SO storicamente rilevante) usano tutte e due le tecniche, richiedono l'uso sia dei diritti che delle capacità.

La struttura logica del flesystem è defnita dalla directory (sinonimo più corretto di "cartella"), tipo speciale di fle ricorsivo che può raggruppare fle e altre directory ed è quindi basato sull'accesso con chiave. Ogni record della directory rappresenta un fle, il cui nome è chiave e i cui attributi sono il contenuto del record associato alla chiave. In UNIX questo contenuto punta alla entry nella tabella dei descrittori, per consentire la condivisione delle directory nei sistemi multiutente.

I sistemi moderni supportano i links, trasformando la classica struttura ad albero delle directory in un vero e proprio grafo: un fle diventa accessibile comodamente da più posizioni.

Nel caso di GNU/Linux i line/collegamenti possono essere simbolici o “hard” (fsici). Un fle viene efettivamente cancellato solo se tutti gli hard line sono stati eliminati. A seconda del flesystem ove il collegamento risiede, non è sempre possibile creare line verso le directory ed i diritti dei line simbolici sono irrilevanti.

26


Per motivi di performance le applicazioni devono utilizzare le syscall "open" e "close", che rispettivamente aggiungono e tolgono il descrittore dalla memoria principale ed impongono un limite ai fle aperti. Nella memoria principale il SO mantiene un'unica tabella dei descrittori in uso, sfruttando un contatore di riferimenti al descrittore, incrementato ad ogni invocazione di "open" e decrementato ad ogni invocazione di "close": il contatore varia simmetricamente in base al numero di riferimenti al fle descriptor e, quando si azzera, il SO considera il fle come superfuo e ne rimuove i riferimenti dalla memoria primaria.

27


2.2 • Filesystem UNIX

Per UNIX tutti i fle sono byte streams (il tipo efettivo viene dedotto dai processi) e la struttura gerarchica è un directory system con supporto agli ACL (matrice per colonna); i fle speciali sono le pipe (implementate come mailboxes) ed i device virtuali.

Il flesystem logico può essere rappresentato come un grafo aciclico orientato, fatto da directories e fles. Il descrittore di fle è chiamato i-node e vi si accede tramite l'i-number, indice della i-list, ovvero della tabella dei descrittori.

Secondo Dennis Ritchie, l’inventore del linguaggio C che ha contribuito allo sviluppo di UNIX, questi termini si possono scrivere anche senza il trattino.

La “i” nel nome sta per “index”: l’inumber è l’indice che individua un particolare inode nella ilist, che può essere rappresentata come un array.

Le directories sono i-node indicizzanti che associano gli i-number ai nomi simbolici dei fle. Le directory entry UNIX consumano 16 bytes, di cui solo due dedicati all'i-number e il resto per il nome simbolico.

Il "pathname" è il percorso assoluto del fle (ovvero il percorso completo a partire dalla radice) che può essere abbreviato nel pathname relativo conoscendo la working directory dell'utente, ulteriormente abbreviabile sostituendola con il simbolo del punto ASCII. Il punto nel pathname rappresenta la directory corrente, mentre due punti ASCII consecutivi rappresentano la directory superiore rispetto alla directory corrente, ovvero il padre del nodo indicizzante attuale.

Ogni partizione UNIX è suddivisa in due parti:

• la tabella dei contenuti;

• i blocchi di dati dei fle.

28


La tabella dei contenuti è salvata nella zona fsica iniziale della partizione ed è formata da 3 parti predefnite in quanto a posizione e dimensione massima:

• l'area di bootstrap

fondamentale per poter eseguire la macchina estesa, contiene il primo software del SO, avviato dopo il frmware del sistema;

• il superblocco

descrive con precisione la struttura del volume;

• i-list1

creata alla formattazione e di dimensione vincolante per il numero di fle allocabili.

Il superblocco contiene:

• il numero di blocchi della partizione

determina la dimensione della partizione stessa;

• i dati per gestire i blocchi

come, ad esempio, la free-block list;1 L’Illustrazione 1 mostra la stretta relazione tra directories e i-nodes in un flesystem UNIX.

29


• la dimensione della i-list

che, come detto prima, deve essere nota a priori e ben defnita;

• i dati per gestire gli i-node

come, ad esempio, la free i-node list;

• il bit di modifca del superblocco

se è attivo il superblocco ha subito modifche e deve essere fsicamente aggiornato.

La free-block list è una lista concatenata di blocchi liberi, basata sui fle.

Ogni i-node contiene:

• dati identifcativi del creatore

almeno:

▪ UID dell'account del proprietario;

▪ GID del gruppo dell'account del proprietario.

• permessi di accesso

relativi al creatore, al suo gruppo e agli altri;

30

f

f Blocco del fle tracciato

Blocco di un fle qualsiasi Blocco libero

free-block list


• tipo del fle

in quanto byte stream, può solo essere "ordinario", "directory" o "speciale". Altre deduzioni semantiche sono lasciate ai processi;

• timestamps (data ed ora dalla UNIX epoch)

possono essere commutati con “mount”, di vario tipo:

▪ di accesso

opzionale e poco afdabile;

Su GNU/Linux alcuni flesystem (come ext4) la supportano ma i tools di sistema non sono ancora in grado di mostrarla o la ignorano, anche perché alcuni amministratori la disabilitano per ridurre l'overhead di accesso, specialmente su dischi a stato solido (SSD).

▪ di modifca

necessaria, non disabilitare;

Su GNU/Linux disabilitarla può causare malfunzionamenti insidiosi, specialmente se la partizione è temporanea (allocata nella memoria principale tramite astrazioni del eernel).

▪ di modifca dell'i-node.

• dimensione in byte;

• tabella degli indirizzi

indicizza i blocchi di dati che compongono il fle.

I permessi di accesso richiedono 9 bit, composti da 3 gruppi:

{User, user’s Group, Others}

...ciascuno con i valori booleani di:

{Readable, Writable, eXecutable}.

31


La tabella dei blocchi dati punta direttamente ai primi 10 blocchi del fle e poi riserva 3 campi per il puntamento multi-indirezione (ovvero la risoluzione ricorsiva degli handle).

Questo rimuove le limitazioni sul contenuto ma l'accesso è più lento verso la fne dei fle...

Nella memoria principale, l'i-node table - unica - contiene una entry per fle aperto, fatta da:

• contatore delle referenze (“ref-counter”)

detto "reference counter";

• i-number ed afni;

• i-node.

Quando il ref-counter diventa 0 - e quindi tutti i processi hanno chiuso il fle e non lo vogliono più utilizzare - l'inode viene scritto sulla memoria secondaria e scaricato dalla memoria principale (vd. funzione "close").

32

55 f.d.

88 f.d.

read

write

f

i-node

2

count

...

...

...

...

i-node table

fle table

...

...

...

...

...

fle descriptor table di P2

fle descriptor table di P1

...

...

Apertura del fle “f”


La fle table è anch'essa unica e contiene una entry per ogni modalità di apertura di ogni fle aperto. Ogni entry contiene:

• il ref-counter;

• l'indice dell'ultimo byte acceduto

fondamentale per il seeeing dei processi, perché determina il prossimo byte da leggere o scrivere;

• la modalità di apertura

ad esempio Read & Write (rw, troncante/generatrice);

• l'indice nell i-node table

vista prima.

Ogni processo ha una fle descriptor table, contenente puntatori verso la fle table, che a sua volta punta all'i-node table (le ultime due, ricordiamo, uniche nel SO).

Quando un fle viene aperto, il suo i-node viene copiato nella memoria principale e le strutture inerenti vengono riempite. Afnché ciò avvenga, però, il processo deve esplicitamente aprire il fle, dichiarando quindi di possederne una referenza:

/* Esempio in pseudo-codice C: apertura di un file. * Se il file non può essere aperto restituisce -1, * valore che il programmatore deve sempre gestire. */filedescriptor = open(pathname, flags, ...);

...localizza il fle nel flesystem usando il pathname (ovvero seguendo la scia di i-node). Se il fle non è ancora stato aperto da altri processi, il SO crea e popola in ordine le relative entry nella i-node table, nella fle table e nella fle descriptor table del processo, per poi restituire l'indice della entry nella fle descriptor table, che il linguaggio di programmazione può astrarre con un tipo opaco (in questo caso il tipo opaco è buona prassi, per favorire la compatibilità).

33


I primi 3 elementi della fle descriptor table di ciascun processo devono sempre essere in ordine (standard-) input, (standard-) output e (standard-) error, fle virtuali standard che non necessitano dell’apertura esplicita e consentono l'I/O sugli stream standard del terminale.

Gli stream standard possono essere rediretti dal processo padre, dalla shell o da tools afni, quindi la loro afdabilità dipende dalla volontà dell'utente corrente. I programmi dovrebbero dedurre se l'ambiente di esecuzione è interattivo (shell interattiva, se il programma usa solo la CLI) oppure è puramente batch e se ha associato un TTY (device fle che rappresenta la shell) valido usando le variabili d'ambiente, prima di produrre messaggi dedicati all'utente umano.

Per chiudere un fle:

/* Esempio in pseudo-codice C: chiusura di un file. * Se il file non può essere chiuso restituisce -1, * valore che il programmatore talvolta deve gestire. */status = close(filedescriptor);

...dealloca la entry della fle descriptor table e se il ref-count della entry è maggiore di 1 lo decrementa e termina; se invece è 0, dealloca la entry anche dalla fle table e, se la corrispondente entry della i-node table è maggiore di 1, lo decrementa e termina; se invece è 0 allora nessun processo sta più usando il fle: scrive l'i-node nella memoria secondaria e dealloca la entry della i-node table, per poi terminare.

Per leggere un fle:

/* Esempio in pseudo-codice C: lettura di alcuni dati da un file. * Quando la lettura non può proseguire restituisce -1, * valore che il programmatore deve necessariamente gestire. */nbyteletti = read(filedescriptor, buffer, nbytes);

...accede al fle descriptor (usandolo come indice della fle descriptor table) e controlla la modalità ed i permessi di accesso. Se va tutto bene, tramite la fle table accede alla i-node table e tramite la tabella inerente rintraccia gli indirizzi dei blocchi, trova il primo byte del fle, legge i blocchi di dati richiesti - salvo

34


casi particolari - per mezzo della bufer cache del SO e copia da qui solo (e mai di più) la quantità di nbytes richiesti nel bufer utente. Alla fne aggiorna l'i-node e l'ofset nella entry della fle table, per tenere traccia del punto di seee. Restituisce il numero di bytes efettivamente letti.

Miscelare chiamate di sistema da API vecchie e nuove può introdurre errori nella memorizzazione del punto di seee, difcilissimi da individuare. Prima di miscelare le chiamate di sistema GNU/Linux che prevedono diversi tipi di accesso al fle è bene consultare con diligenza la documentazione di un singolo standard POSIX, specialmente quando si tratta di dover leggere vettori.

Una pipe è in realtà una mailbox limitata e gestita come una FIFO: se è piena, i processi si bloccano in attesa della lettura/scrittura. Grazie a questa sincronizzazione (che non dispensa lo sviluppatore dall'uso delle primitive di sincronizzazione) è considerato come un tipo di fle speciale, che possiamo immaginare come avente la stessa eleganza di una coda circolare.Per creare una pipe anonima:

/* Esempio in C: creazione di una nuova pipe. * Documentazione: $ man 2 pipe * Ritorna -1 in caso di errore; non trascurare la lettura di 'errno'. */int pipe(int filedescriptors[2]); // passare nuovo array di file descriptor

...assegna ordinatamente i due estremi della pipe: il primo elemento [0] è l'estremo aperto in lettura, mentre il secondo [1] è l'estremo opposto, aperto in scrittura. La fle table subirà quindi l'aggiunta di 2 nuove entry che puntano però alla stessa entry dell'i-node table, dotata nell'immediato di un ref-count di 2 e che punta all'i-node della pipe. Un processo “foreato” potrà usare elegantemente, grazie alla memoria condivisa, il fle descriptor della pipe per l'IPC interna al programma.

35

Appunti ragionati di Sistemi Operativi · naming, al bufering ed alla gestione dei malfunzionamenti...

Documents

Transcript of Appunti ragionati di Sistemi Operativi · naming, al bufering ed alla gestione dei malfunzionamenti...