SISTEMI OPERATIVI

1

CAP 1: INTRODUZIONE AI SISTEMI OPERATIVI Il sistema operativo è il software che gestisce le interazioni tra utente e calcolatore elettronico. Fornisce un ambiente in cui sviluppare ed eseguire codice in maniera comoda ed efficiente. HARDWARE I nsieme delle risorse di calcolo(CPU, memoria...)

PROGRAMMI APPLICATIVI Definiscono i modi in cui le risorse del calcolatore vengano utilizzate per risolvere i problemi degli utenti. Un sistema operativo deve:

- Assegnare le varie risorse disponibili ai vari programmi (tempo di CPU, memoria...)

- Controllare l’esecuzione di programmi - Controllare che il calcolatore sia sempre usato in modo corretto - Avere a sua disposizione una serie di programmi sempre in funzione

(essi rappresentano il KERNEL). 1.1 TIPOLOGIE DI SISTEMI SISTEMI BATCH (LOTTI) Erano dei sistemi controllati tramite consolle, con immissione di dati tramite nastri magnetici. Avevano dei sistemi operativi semplici che gestivano il passaggio da un lavoro all’altro, ed i lavori simili erano raggruppati in lotti. Erano caratterizzati da una bassa efficienza dell’uso della cpu. SISTEMI MULTIPROGRAMMATI Il loro sistema operativo manteneva in memoria contemporaneamente più lavori. SISTEMI MULTITASKING Con questi dispositivi vi era una comunicazione diretta fra sistema operativo e utente, ed il s.o. permetteva di condividere tra più utenti il calcolatore. In questo modo la CPU esegue più lavori ad una frequenta tale da gestire più condivisioni di utenti. SISTEMI DESKTOP Sono dei sistemi a singolo utente, con un sistema operativo orientato a facilitare l’uso del calcolatore agli utenti. SISTEMI PARALLELI ( SIMMETRICI ) Sono dei sistemi che presentano più CPU connessi attraverso un unico bus alle memorie ed ai dispositivi di input/output. In questo modo tutte le CPU hanno lo stesso peso (NO master-slave), aumentando di fatto:

- affidabilità - Aumento del throughput (quantità di dati in uscita) - Economia di scala

2

SISTEMI DISTRIBUITI Con questa tipologia di sistemi i calcoli vengono distribuiti fra diversi processori ( in questo caso però ogni processore ha una propria memoria e dei propri dispositivi di I/O) I vantaggi sono: - condivisione delle risorse - aumento velocità di calcolo - affidabilità Essi però richiedono una infrastruttura di comunicazione (rete). SISTEMI REAL-TIME Sono dei sistemi in cui l’elaborazione deve avvenire entro limiti di tempo precisi ( esempio: processi industriali). Hard Real – Time: sistemi con memoria secondaria (ossia dischi rigidi e lettori) assente o limitata. Soft Real – Time: sistemi che richiedono sistemi operativi specifici con caratteristiche avanzate (esempio realtà virtuale). PDA Sono dei sistemi palmari basati su microprocessori lenti e con poca memoria, essi devono cercare di mediare tra le esigenze dell’utente e le a disposizione. CAP 2: TRASFERIMENTO DATI TRA CPU E DISPOSITIVI DI I/O Esistono essenzialmente due tecniche fondamentali: Busy – Weating: ossia le CPU verifica periodicamente lo stato del dispositivo, eseguendo quando esso è pronto la transazione dei dati. Interrupt: il dispositivo comunica alla CPU quando esso è pronto. Ciò avviene tramite un apposito segnale chiamato segnale di interruzione. Comunque per entrambi i casi ogni dispositivo di I/O dispone di un controllore ( controller ) il quale gestisce il funzionamento del dispositivo. Tali controllori hanno a disposizione un buffer locale dove memorizzare i dati temporaneamente in attesa che essi vengano inviati

la CPU. al 2.1 MECCANISMO DI INTERRUZIONE Il segnale di interruzione trasferisce il controllo al programma dedicato alla gestione dell’interruzione (driver di periferica), tale programma e generalmente indicato dal vettore delle interruzioni che contiene gli indirizzi di partenza di tutti i driver delle periferiche. Inoltre il meccanismo dell’interruzione deve memorizzare l’indirizzo di memoria della successiva istruzione da eseguire alla fine della gestione dell’interruzione, in modo da riprendere il regolare svolgimento del programma. Si definisce eccezione l’interruzione generate tramite software in caso di errore (eccezioni ed interruzioni vengono gestite allo stesso modo). Inoltre il sistema operativo memorizza il contenuto dei registri della CPU prima della gestione dell’interruzione, e del program counter ( salvataggio del contesto). I/O SINCRONO: Per tali dispositivi si ha che il ritorno del processo chiamante avviene solamente alla fine dell’operazione di I/O.

3

In questo modo però si può utilizzare un solo dispositivo per volta rendendo spesso la CPU inattiva. I/O ASINCRONO: Per tali dispositivi il ritorno del processo chiamante avviene appena inizia l’operazione di I/O. In questo modo si possono avere più processi alla volta, utilizzando le TAVOLE DI STATO ed opzionalmente la tecnica del DMA. 2.2 TAVOLE DI STATO Le tavole di stato sono delle aree di memoria in cui il calcolatore elettronico memorizza per ogni periferica di I/O lo stato in cui essa si trova (occupata , inattiva) gestendo di fatto più dispositivi per volta e quindi dando un ordine di priorità tra periferiche. 2.3 DMA Tale meccanismo consente di trasferire i dati dal dispositivo alla memoria senza passare per il processore. In tale tecnica il processore deve però programmare la periferica definendogli:

- L’identità del dispositivo - L’operazione da eseguire - L’indirizzo di memoria di dove copiare i dati - Il numero di byte interessati.

In questo modo vengono trasferiti blocchi di dati ad elevata velocità senza l’intervento della CPU. Viene generata una sola interruzione per blocco di dati trasferiti. Esistono due tipi di DMA: DMA a BURST: viene trasferito il blocco di dati e alla fine del trasferimento viene generato il segnale di interruzione, in questo caso però durante il trasferimento la cpu non è utilizzata in quanto il bus è occupato. DMA bus STEALING: in questo caso il bus viene utilizzato solamente quando viene trasferito effettivamente il dato. 2.4 TIPI DI BUS Bus processore-memoria: alta banda passante (velocità del bus), distanze del bus corte, e su di esso non sono collegate periferiche di I/O. Bus I/O: sono bus per distanze lunghe con molte periferiche che comunicano a diversa velocità (vedi hard disc), e su di esso non sono collegate memorie e processori. Backplane Bus: vecchi tipi di bus in cui sono presenti dispositivi di I/O memorie e processore. 2.5 SISTEMI DI MEMORIZZAZIONE MEMORIA PRINCIPALE: unico mezzo con cui il processore memorizza dati direttamente (sono memorie ad accesso casuale), sono memorie velocissime. MEMORIA SECONDARIA: è un’estensione della memoria principale ed essa è caratterizzata da un’ampia capacità di memoria (vedi hard disc).

4

2.6 GERARCHIE DI MEMORIA All’interno di un calcolatore elettronico si ha una organizzazione della memoria in maniera gerarchica in più livelli di diversa velocità, costo e dimensione: 1 memoria cache: memoria velocissima, molto costosa e generalmente di dimensioni limitate (viene chiamata memoria cassaforte). 2 Memoria principale 3 Memoria secondaria 2.7 PRINCIPI DI LOCALITA’ DEI PROGRAMMI LOCALITA’ SPAZIALE: dati ed istruzioni sono memorizzati ad indirizzi vicini e quindi data la struttura sequenziale dei programmi esse vengono eseguite in tempi ravvicinati. LOCALITA’ TEMPORALE: e il caso in cui un programma tende ad utilizzare in breve tempo sempre lo stesso gruppo di istruzioni, come ad esempio cicli while... Se quindi per esempio tali istruzioni sono presenti all’interno della cache (memoria velocissima) con la presenza di tali principi si ha un accorciamento notevole di accessi in memoria principale, dati che essi sono gia presenti all’interno della cache. Unico “intoppo” è rappresentato dalle dimensioni delle memorie, in quanto passando da un livello inferiore ad un livello superiore la capacità di memorizzazione diminuisce e quindi mi dovrò inventare degli algoritmi adatti che mi ottimizzino il numero gli accessi ad memorie inferiori, che mi comportano un maggior tempo di accesso. Inoltre il sistema di controllo deve far si che il processore deve accedere ai dati nelle versioni più , in modo da non avere la cosiddetta ncoerenza della cache. i

2.8 MODO PROTETTO In ogni sistema operativo si ha la presenza di un duplice modo di funzionamento della CPU: modo utente : utilizzato dagli applicativi modo sistema: utilizzato dal sistema operativo in questo modo posso rendere delle istruzioni privilegiate (istruzioni che potrebbero arrecare danni al calcolatore elettronico) e far si che esse possano essere eseguite solamente in modalità sistema e quindi dal sistema operativo. Con tale tecnica viene dedicato un bit apposito in modo da determinare in ogni istante la modalità in cui si trova la cpu (per esempio bit = 1 modalità utente).

Tutte le istruzioni di I/O sono delle istruzioni privilegiate. Quindi un programma dovrà passare attraverso il sistema operativo le cosiddette chiamate di sistema per eseguire operazioni privilegiate, in questo modo il s.o. controlla va validità della chiamata e passa in

dalità sistema in caso di controllo positivo. mo 2.9 PROTEZIONE DELLA MEMORIA

5

Il sistema operativo deve controllare che sia protetta la parte di memoria in cui risiede il vettore delle interruzioni e le routine di servizio di quest’ultime. Per tale motivo sono tanti introdotti ulteriori due registri per stabilire l’intervallo di memoria che un programma può utilizzare: BASE REGISTER: contiene il primo indirizzo mi memoria accessibile da un determinato programma. LIMIT REGISTER: contiene le dimensioni dell’intervallo. In modalità protetta tutte le zone di memoria sono accessibili. 2.10 PROTEZIONE DELLA CPU Si effettua la protezione della cpu per evitare che un applicativo non restituisca più il controllo di della cpu da parte del sistema operativo. A tale scopo vengono effettuate periodicamente ( con tempo programmabile dal sistema operativo ) delle interruzioni hardware in modo da restituire il controllo al sistema operativo. Nei moderni microprocessori attuali sono previsti modi di funzionamento per avere diversi livelli di protezione. Nei processori INTEL sono presenti quattro livelli di privilegio: livello 0: kernel del sistema operativo livello 1 e livello 2: servizi del sistema operativo livello 3: programmi CAP 3: COMPONENTI DEL SISTEMA OPERATIVO 3.1 GESTIONE DEI PROCESSI Per svolgere i propri compiti, un processo necessita di alcune risorse, tra cui la cpu, la memoria, dispositivi I/O. Queste risorse si possono attribuire al processo al momento della sua creazione, oppure si possono attribuire durante la sua esecuzione. Tutti i processi si possono potenzialmente eseguire in modo concorrente, avvicendandosi l’uso della CPU. Il sistema operativo è responsabile delle seguenti attività connesse alla gestione dei processi:

- creazione o cancellazione di processi - sospensione - ripristino - gestioni delle situazioni critiche (deadlock) - meccanismi di comunicazione

3.2 GESTIONE DELLA MEMORIA PRINCIPALE Per eseguire un processo, il calcolatore necessita di memoria principale dove allocare i dati che deve gestire il processo. Quando un processo termina si dichiara disponibile il suo spazio di memoria; a questo punto si può caricare ed eseguire il processo successivo. Il sistema operativo è responsabile delle seguenti attività :

- tenere sotto controllo le aree di memoria utilizzate da ogni singolo processo

- allocazione delle aree di memoria

6

- scelta dei processi da caricare in memoria 3.3 GESTIONE DEI FILE La gestione dei file è uno dei componenti più visibili del sistema operativo. Il compito chiave del s.o. è quello di fornire all’utente un modo uniforme di gestione la registrazione dei dati su diversi dispositivi di memorizzazione (dischi, nastri…). Un file è una raccolta di informazioni correlate definite dal loro creatore (insieme di dati omogenei). Il sistema operativo deve occuparsi della:

- creazione e cancellazione dei file - creazione e cancellazione delle directory - copiatura dei file su dispositivi di memoria secondari

3.4 GESTIONE DEL SISTEMA I/O Per quanto riguarda la gestione dei dispostivi di I/O il sistema operativo deve preoccuparsi di:

- gestire il trasferimento dati tra memoria principale e i buffer dei dispositivi di I/O

- fornire un’interfaccia generale per i driver dei dispositivi - gestire i driver delle periferiche

3.5 GESTIONE DELLA MEMORIA SECONDARIA La memoria secondaria è generalmente da sostegno alla memoria primaria ed è di dimensioni nell’ordine dei GB composta da dischi magnetici. Il compito principale del sistema operativo sono essenzialmente:

- gestione dello spazio libero - assegnazione dello spazio libero - scheduling del disco

3.6 GESTIONE DELLA RETE Un sistema distribuito è un insieme di unità di elaborazione che non condividono la memoria, i dispositivi periferici o un clock. In tale sistema le unità sono collegate da una rete di comunicazione che può essere configurata in vari modi. I compiti del sistema operativo nei confronti della rete sono: - gestire sessioni di lavoro remote - accedere alle risorse della rete come se fossero locali - trasferire file remoti 3.7 SISTEMI DI PROTEZIONE Se un sistema di calcolo ha più processi che possono essere eseguiti in modo concorrente, se deve avere un sistema che protegga le attività di un determinato processo nei confronti di altri processi. I compiti del sistema operativo:

- distinguere fra uso autorizzato e non autorizzato di un processo

7

- specificare i controlli da effettuare sui processi - provvedere alla gestione delle violazioni

3.8 INTERPRETE DEI COMANDI Uno dei programmi di sistema più importanti di un sistema operativo è l’interprete dei comandi; si tratta dell’interfaccia tra l’utente ed il sistema operativo. Esso mette a disposizione dell’utente una serie di comandi per:

- cancellazione e creazione di un processo - gestione della memoria primaria e secondaria - uso della rete - accesso al file system

Spesso i sistemi operativi si differenziano proprio dal punto di vista dell’interprete dei comandi. Esistono interpreti amichevoli basati sull’utilizzo del mouse per esempio Windows, ed interpreti basati su righe di comando per esempio MS-DOS. 3.9 SERVIZI DEL SISTEMA OPERATIVO Un sistema operativo offre un ambiente in cui eseguire i programmi e fornire servizi ai programmi e ai loro utenti. Per rendere più agevole la programmazione, si offrono i seguenti servizi:

- esecuzione di un programma: il sistema deve poter caricare un programma eseguirlo

- operazioni di I/O: un programma in esecuzione può richiedere un’operazione di I/O che implica l’uso di un file o di un dispositivo di I/O.

- gestione del file system: ossia la possibilità da parte dei programmi di leggere, scrivere creare e cancellare file.

- Comunicazioni: scambio di informazioni fra processi in esecuzione su uno stesso computer attraverso due principali: lo shared memory (copiare grandi quantità di dati) e lo messagge passing (scambio di messaggi tra sistemi operativi).

- Rivelamento degli errori: assicurare la correttezza dei processi gestendo i possibili errori della CPU della memoria e dei dispositivi di I/O.

Esiste anche un’altra serie di funzioni del sistema operativo che non riguarda direttamente gli utenti, ma assicura il funzionamento corretto del sistema stesso: - contabilizzazione delle risorse: il s.o. memorizza quali utenti

utilizzano il calcolatore e quali risorse hanno occupato. Tale informazioni possono essere utilizzate per calcolare il costo da addebitare ad ogni singolo utente (esempio degli internet point).

- Protezione: viene assicurata alla macchina il corretto accesso alle risorse di sistema rispettando i vincoli imposti.

8

3.10 CHIAMATE DI SISTEMA Le chiamate di sistema costituiscono l’interfaccia tra un processo e il sistema operativo. Sono generalmente disponibili sotto forma di istruzioni di linguaggio assemblativo e sono generalmente elencate. Le chiamate di sistema del sistema UNIX ad esempio si possono invocare da un programma scritto in C o in C++. Invece le chiamate di sistema per i moderni sistemi Windows sono disponibili tramite l’API win32. Generalmente una chiamata di sistema viene identificata da un nome ma molto spesso devono anche essere specificati dei parametri. Tali parametri possono essere passati in tre modi differenti:

- utilizzando i registri (quantità di dati limitati) - scritti in una tavola di memoria e poi passata al s.o. l’indirizzo

iniziale di tale dati - uso della memoria gestita a stack (tramite le PUSH e POP).

3.11 TIPOLOGIE DI CHIAMATE DI SISTEMA Controllo dei processi

- end, abort, load, execute, create process, terminate process... 3.12 CONTROLLO DEI PROCESSI Un programma in esecuzione deve potersi arrestare sia normalmente(tramite end), sia anormalmente (tramite Abort). Se per terminare in modo anormale un programma incontra difficoltà, è possibile eseguire un backup della memoria (tramite il dump). Uno specifico programma di ricerca e correzione degli errori, può esaminare tali dati e determinare le cause del problema; sarà successivamente l’interprete dei comandi a comunicare all’utente l’errore ed far effettuare ad esso un’opportuna scelta. In un sistema a lotti, l’interprete dei comandi generalmente termina il lavoro corrente e prosegue con il successivo. Un processo che esegue un programma può richiedere di caricare e di eseguire un altro programma. In questo caso l’interprete dei comandi esegue un programma come se tale richiesta fosse stata impartita ad esempio, da un comando di tale utente. Il controllo dei processi presenta così tanti aspetti e varianti; per esempio il sistema operativo MS-DOS, è un sistema che dispone di un interprete di comandi caricati all’avvio e che esegue un solo programma alla volta, nel seguente modo: il programma viene caricato in memoria, riscrivendo anche la maggior parte della memoria, quindi imposta il PC alla prima istruzione del programma da eseguire. Grande svantaggio di tale architettura è che mentre un programma era attivo, non si poteva interagire con l’interprete dei comandi. Comunque è possibile eseguire processi concorrenti tramite l’uso di programmi TSR, i quali si attivano intercettando segnali di interruzione. Esiste un’altra tipologia per il controllo dei processi utilizzata dai sistemi operativi UNIX. In questo caso, tali sistemi operativi possono, a differenza dell’ MS-DOS, più programmi contemporaneamente. Il sistema esegue un interprete dei comandi(Shell) scelto dall’utente. Per avviare un nuovo processo dei comandi, esegue la chiamata di sistema FORK (che avvia un nuovo processo); si carica il programma selezionato nella memoria e infine si esegue quest’ ultimo. Alla fine dell’esecuzione del processo, viene generato un codice di stato, che permette di capire se il programma è

rminato normalmente o con errori. te

9

3.13 GESTIONE DEI FILE Per la gestione dei file si possono identificare parecchie chiamate di sistema riguardante quest’ultimo. Innanzi tutto è necessario poter creare e cancellare i file. Una volta creato il file è necessario aprirlo e leggerlo, scrivere o riposizionarlo. Si deve infine poter chiudere per indicare che non è più in uso. Le stesse operazioni possono essere necessarie per le stesse directory, nel caso in cui il file system è strutturato in directory. 3.14 GESTIONE DEI DISPOSITIVI Durante l’esecuzione di un processo, è possibile utilizzare i dispositivi: occorre prima richiedere il dispositivo, per assicurare l’esclusiva. Terminato l’uso del dispositivo occorre rilasciarlo; una volta richiesto ed assegnato il dispositivo, è possibile leggervi, scrivervi ed eventualmente procedere ad un riposizionamento. 3.15 COMUNICAZIONE Esistono due modelli molto diffusi di comunicazione. Nel modello a scambio di messaggi, le informazioni si scambiano per mezzo di una funzione di comunicazione messa a disposizione del sistema operativo. Tutti i calcolatori che partecipano alla comunicazione hanno un nome di macchina, ad esempio un IP. Analogamente ogni processo ha un nome di processo, che si converte in un identificatore. Esistono inoltre chiamate di sistema per l’apertura e la chiusura della connessione. Nella maggior parte dei casi i processi che gestiscono la comunicazione sono demoni specifici, cioè programmi di sistema realizzati esplicitamente per questo scopo. Nel modello a memoria condivisa invece per accedere alle aree di memoria possedute da altri processi, i processi usano chiamate del sistema Map Memory. La forma e la posizione dei dati sono determinate esclusivamente da questi processi e non sono sotto il controllo del sistema operativo. I processi sono dunque responsabili del rispetto della condizione di non scrivere contemporaneamente nella stessa posizione. 3.16 PROGRAMMI DI SISTEMA Un’altra caratteristica importante dei sistemi operativi moderni, è quella che riguarda una serie di programmi del sistema. Tali programmi offrono un ambiente più conveniente per lo sviluppo dei programmi. Essi si classificano in:

- gestione dei file: tali programmi cancellano, creano, rinominano ... i file

- informazioni di stato: alcuni programmi richiedono data e ora, spazio libero di memoria, ecc. Le informazioni sono formattate e scritte su schermo, in un altro dispositivo o uno schermo.

- modifica dei file - ambienti di ausilio alla programmazione(compilatori C,C++) - comunicazioni: tali programmi offrono la possibilità di far

dialogare gli utenti attraverso il web, dispositivi remoti, ...

10

I sistemi operativi moderni includono programmi di applicazione che consentono di consultare il web, disegnare, fare calcoli, scrivere file di testo e anche giocare. Il programma più importante è l’interprete dei comandi, che riceve i comandi impartitogli dagli utenti e li esegue, inoltre contiene i codici di esecuzione di alcuni programmi di sistema. L’altro modo usato in LINUX è quello che l’interprete “non conosce” il comando, ma utilizza il codice per identificare un file da caricare nella memoria e per eseguirlo. 3.17 STRUTTURA DEL SISTEMA Affiche un sistema operativo non sia monolitico, ma modificabile, esso deve essere composto da tante componenti ciascuna orientata in modo ben definito, in modo che tali componenti siano ben connesse tra loro. 3.18 STRUTTURA SEMPLICE Molti sistemi commerciali non hanno una struttura ben definita, un esempio è il DOS e UNIX dove occorreva garantire veloce accesso in poco spazio. Lo UNIX e formato da due parti: il nucleo e i programmi di sistema. 3.19 METODO STRATIFICATO Si suddivide il sistema operativo in un certo numero di strati, lo strato più in basso è quello fisico, lo strato più alto è l’interfaccia d’utente. Lo strato di ciascun s.o. è la realizzazione di un oggetto astratto che incapsula i dati e le operazioni che li trattano. Il vantaggio principale è la modularità che garantisce l’uso di funzioni dai soli strati di livello superiore, ciò semplifica notevolmente la messa a punto e la realizzazione del sistema. Con tale gerarchia ogni strato nasconde a quelli inferiori l’esistenza di strutture dati, operazioni ed elementi fisici. Tale sistema può però creare situazioni poco efficienti come ad esempio l’esecuzione di I/O di un utente che invoca una chiamata che è intercettata dallo strato di I/O che a sua volta chiama lo strato di scheduling che passa il tutto al dispositivo di I/O. Tale catena di chiamate è in realtà spreco di tempo. I moderni s.o. per essere rapidi sono molto meno stratificati e ciascuno strato ha, molte più funzioni. Basta vedere l’evoluzione di windows ed in particolare la versione NT con miglioramenti rispetto le precedenti. 3.20 MICRONUCLEO Man mano che UNIX si espandeva con esso lo faceva anche il nucleo fino al punto in cui divenne ingestibile. Verso la metà degli anni 80 alcuni ricercatori introdussero MATCH, un sistema operativo modulare con micronucleo in cui furono ridotte al minimo le operazioni del nucleo riservandogli solo i servizi minimi di gestire processi, della memoria e di comunicazione. Lo scopo principale del micronucleo è fornire funzioni di comunicazione tra i programmi client e i vari servizi, un grande vantaggio è che il s.o. è aggiornabile in quanto i suoi servizi si aggiungono allo spazio

11

utente, inoltre dato che è ridotto, se occorre effettuare modifiche al suo interno, le operazioni da fare sono ben circoscritte. Inoltre il micronucleo offre maggior sicurezza in quanto i servizi li si eseguono in gran parte in modo utente. 3.21 MACCHINE VIRTUALI Un sistema di calcolo è costituito da strati; l’architettura fisica è lo strato più basso che fornisce le istruzioni macchina al nucleo sulla quale si trovano i programmi di sistema che usano i programmi di sistema e le istruzioni di macchina che sebbene accedute diversamente forniscono funzioni complesse, trattando le istruzioni macchina e le chiamate di sistema come se fossero allo stesso livello. I programmi d’applicazione possono considerare quel che si trova al di sotto gerarchicamente come se fosse parte della macchina stessa sebbene i programmi di sistema si trovino a livello superiore. Tale stratificazione conduce al concetto di macchina virtuale. Esempio è il s.o. VM dell’IBM che usa scheduling della CPU creando l’illusione di disporre una propria CPU con una propria memoria (virtuale). La gestione asincrona dell’ I/O e l’esecuzione di più processi, unita a un file system consente di creare lettori di schede e stampanti virtuali. L’unica vera difficoltà è legata alla gestione dei dischi. REALIZZAZIONE: così come nelle macchine fisiche, le macchine virtuali devono avere due modalità: utente e sistema, sebbene sia davvero difficile ottenere la modalità sistema. Se un programma in esecuzione sulla macchina virtuale in modo utente esegue una chiamata del sistema si passa al modo sistema della macchina virtuale all’interno della macchina reale. Quando il sistema della macchina virtuale acquisisce il controllo può modificare il contenuto dei registri e il contatore di programma della macchina virtuale in modo da simulare l’effetto della chiamata di sistema, quindi può riavviare la macchina virtuale che si trova nel modo di sistema virtuale. La differenza consiste nel tempo, l’I/O reale richiede circa 100 ms; quello virtuale richiede di più in quanto l’I/O è simulato da file che si trova sull’hard disc. VANTAGGI: il principale vantaggio della macchina virtuale è la sicurezza per l’harware in quanto non si agisce su esso in modo reale, inoltre grazie a tale sviluppo si è consentito sempre più apportare modifiche ai sistemi operativi dei grandi mainframe. 3.22 JAVA linguaggio orientato agli oggetti che fa uso di una JAVA VIRTUAL MACHINE che fa si che la compilazione delle classi sia interpretata dall’harware. 3.23 PROGETTAZIONE E REALIZZAZIONE DI UN SISTEMA Quando si progetta un s.o. ci si imbatte nel primo problema ossia il suo scopo che in realtà deve soddisfare due scopi: utente e sistema. Gli utenti lo desiderano veloce, efficace, comodo facile, i progettisti lo vogliono senza errori e longevo.

12

CAP 4: GESTIONE DEI PROCESSI Un processo è un programma in esecuzione, che richiede determinate risorse. Ci sono processi di sistema definiti dal s.o. e i processi utente, entrambi vengono eseguiti in contemporanea. Il processo costituisce l’unità di lavoro dei moderni sistemi operativi a partizione del tempo. 4.1 CONCETTO DI PROCESSO Un utente esegue un’operazione alla volta, ma il calcolatore nel gestire la memoria, gestire anche i molti processi che sono in esecuzione. PROCESSO E’ qualcosa di più del codice di un programma, noto come sezione di testo, comprende l’attività corrente, rappresentata dal valore del program counter e dal contenuto dei registri della CPU. Di solito comprende anche un proprio stack e una sezione dati contenenti le variabili globali. Un programma non è un processo in quanto è un entità passiva, un processo è invece un entità attiva. STATO DEL PROCESSO mentre un processo è in esecuzione è soggetto a cambiamenti di stato definiti dalle attività corrente del processo stesso. Gli stati sono:

- nuovo; si crea il processo - esecuzione - attesa; si attende qualche evento - pronto: si attende l’esecuzione da parte della CPU - terminato

DESCRITTORE DEL PROCESSO Ogni processo è rappresentato nel s.o. da un descrittore di processo detto anche blocco di controllo di un processo che contiene molte informazioni:

- stato del processo - contatore di programma - registri di CPU, che comprendono accumulatori registri indice,

stack pointer... quando si verifica un’interruzione della CPU, si salvano le informazioni (contenuti dei registri...) in modo da permettere la corretta esecuzione del processo in seguito. THREAD Un processo è un programma che si esegue seguendo un unico percorso di esecuzione, secondo una singola sequenza di istruzioni, svolgendo un solo compito alla volta.

4.2 SCHEDULING DEI PROCESSI La multiprogrammazione consiste nel disporre contemporaneamente alcuni processi in modo da massimizzare l’utilizzo della CPU. La partizione di tempo punta sulla velocità di commutazione della CPU tra i processi dando all’utente la possibilità di interagire con ciascun programma mentre è in esecuzione.

13

CODE DI SCHEDULING Ogni processo è inserito in una coda di processi di tutti i processi di sistema. I processi presenti in memoria centrale che sono pronti e nell’attesa di essere eseguiti si trovano in una coda di processi pronti, che è una lista concatenata in cui l’intestazione contiene i puntatori del primo e dell’ultimo PCB dell’elenco e ciascun PCB è esteso con un campo puntatore che indica il successivo processo contenuto nella coda dei processi pronti. Il s.o. ha anche altre code, quando si assegna alla CPU un processo, quest’ultimo rimane in esecuzione per un pò di tempo e potrebbe rimanere in attesa per esempio di I/O che è una richiesta diretta ad unità disco, potrebbe capitare che il disco è impegnato per un altro processo e per cui il processo chiamante deve attendere che il disco sia libero. L’elenco dei processi che attendono la disponibilità di un dispositivo di I/O si chiama coda del dispositivo; ogni dispositivo ha la sua coda.

SCHEDULER Nel corso della sua esistenza un processo si trova in varie code di scheduling e il s.o. compie la selezione attraverso un apposito scheduler. Accade spesso che ci siano più lavori di quanti se ne possano svolgere immediatamente, tali lavori vanno in dispositivi di memoria secondaria dove risiedono fino all’esecuzione. Lo scheduler a lungo termine sceglie i lavori da questo insieme e li carica in memoria fisica finché non vengono eseguiti. Lo scheduler a breve termine fa la selezione tra i lavori pronti per essere eseguiti, e assegna la CPU ad uno di essi.

CAMBIO DI CONTESTO Il passaggio alla CPU di un nuovo processo, implica la registrazione dello stato del vecchio processo e il caricamento dello stato precedentemente registrato del nuovo processi. Tale procedura è nota come cambio di contesto e quando avviene, il KERNEL registra il contesto del vecchio processo nel suo PCB e carica il contesto precedente per il nuovo processo

OPERAZIONI SUI PROCESSI I processi di un S.O. si possono eseguire in modo concorrente e si devono creare e cancellare dinamicamente, a tal fine il S.O. deve offrire un meccanismo che permette di creare e terminare il processo

CREAZIONE DI UN PROCESSO Durante la propria esecuzione, un processo può creare numerosi altri processi. Il processo creante si chiama Padre e quello creato Figlio. Il padre dispone di varie risorse ( Cpu,Ram…) e può limitare le risorse del figlio. Quando avviene la creazione vi sono due possibilità:

- Il genitore continua l’esecuzione in parallelo con i figli - Il genitore attende che i processi figli terminino

Ci sono due possibilità anche per lo spazio di indirizzi del nuovo processo:

- Il processo figlio è un duplicato del padre - Nel processo figlio si carica un programma

TERMINAZIONE DI UN PROCESSO Un processo termina quando finisce l’esecuzione della sua ultima istruzione e chiede al sistema operativo la cancellazione attraverso la chiamata Exit.

14

A questo punto il figlio riporta alcuni dati al genitore che li riceve attraverso la chiamata WAIT. Tutte le risorse di un processo sono liberate dal s.o. La terminazione può avvenire anche in altri casi:

- Il genitore ha terminato e il s.o. non consente ai figli di proseguire

- Non è richiesto più il compito assegnato al figlio - Il figlio ha ecceduto le risorse assegnategli

4.3 PROCESSI COOPERANTI Esistono processi indipendenti tra loro che non si influenzano a vicenda e che non condividono dati ed esistono processi dipendenti che interagiscono lavorando in parallelo e condividendo dati. I vantaggi della cooperazione sono: - condivisione di informazione - accelerazione del calcolo - modularità - convenienza: un solo utente può avere la necessità di compiere più

attività insieme. Per i processi cooperanti occorrono meccanismi di comunicazione tra loro e di sincronizzazione. Ciò si può capire attraverso il processo produttore e il processo consumatore; essi devono essere sincronizzati in quanto il consumatore può eseguire solo dopo che il produttore esegue. 4.4 COMUNICAZIONE FRA PROCESSI Come la chat in rete, le funzioni di comunicazione tra processi sono fornite nel migliore dei modi da un sistema a scambio di messaggi. SISTEMI DI SCAMBI DI MESSAGGI Un sistema di IPC fornisce almeno le due operazioni SEND e RECEIVE, i messaggi spediti possono essere di due tipi: a dimensione fissa e a dimensione variabile, l’unica differenza sta nella difficoltà di programmazione. Se i processi P e Q vogliono comunicare con messaggi, occorre un canale di comunicazione realizzabile in molti modi:

- Comunicazione diretta o indiretta - Simmetrica o antisimmetrica - Invio per copiatura o per riferimento - Capacità zero limitata o illimitata - Messaggi di dimensione fissa o variabile

COMUNICAZIONE DIRETTA Ogni processo che intende comunicare deve nominare il ricevente o il trasmittente:

- Send (P, messaggio) - Receive (Q, messaggio)

Caratteristiche del canale:

- Si stabilisce automaticamente un canale e i processi devono conoscere solo la reciproca identità.

- Un canale associato esattamente a due processi - Esiste esattamente un canale tra ciascuna coppia di processi

Tale sistema è simmetrico nell’indirizzamento in quanto il TX e il RX per comunicare devono nominarsi a vicenda.

15

Una variante asimmetrica si definisce: - Send (P, messaggio); invia messaggio al processo P - Receive (ID, messaggio); riceve un messaggio da qualsiasi processo

in cui in ID si specifica il nome del processo. COMUNICAZIONE INDIRETTA I messaggi si inviano a delle porte (Mailbox), che le ricevono. In essi i processi possono introdurre e prelevare i messaggi e sono identificate in modo unico, infatti due processi possono comunicare solo se condividono una porta: - Send (A, messaggio); invia messaggio alla porta A - Receive (A, messaggio); riceve messaggio dalla porta A Caratteristiche del canale:

- C’è il canale solo se i processi condividono la stessa porta - Un canale può essere associato a uno o più processi - Tra ogni coppia di processi comunicanti possono esserci più canali

diversi, ciascuno corrispondente ad una porta. Il s.o. consente ad un processo le seguenti operazioni:

- creare una nuova porta - inviare e ricevere messaggi tramite la porta - rimuovere la porta

SINCRONIZZAZIONE Lo scambio di messaggi può essere sincrono o asincrono:

- Invio sincrono: il processo inviante si blocca nell’attesa che il ricevente riceva

- Invio asincrono: il ricevente si blocca nell’attesa dell’ arrivo di un messaggio.

- Ricezione sincrono: il ricevente si blocca nell’attesa dell’arrivo di un messaggio.

- Ricezione asincrona: il ricevente riceve un messaggio valido oppure un valore nullo.

CODE DI MESSAGGI I messaggi scambiati tra processi comunicanti risiedono in code temporali ed esistono 3 metodi per la realizzazione di tali code. - Capacità 0: la coda è lunga massimo 0, quindi il canale non può avere messaggi di attesa al suo interno - Capacità limitata - Capacità illimitata 4.5 COMUNICAZIONE NEI SISTEMI CLIENT-SERVER Si consideri un utente che deve accedere a dati presenti in un altro server A, tale richiesta è gestita da un server remoto nel sito A che calcola i dati richiesti e invia i risultati all’utente. SOCKET E’ l’estremità di un canale di comunicazione. Una coppia di processi che comunica attraverso una rete usa una coppia di Socket una per ogni processo, e ogni socket identificato con un IP concatenato ad un numero di porta, in generale le socket usano un’architettura client-server. Il sever attende il client stando in ascolto ad una porta specificata, quando il server riceve una richiesta, se accetta la connessione

16

proveniente dalla socket del client, si stabilisce la comunicazione. Quando un processo client richiede una connessione, il calcolatore che lo esegue assegna una porta specifica, che consiste di un numero arbitrario maggiore di 1024, ogni connessione è identificata da una distinta coppia di socket. CHIAMATE DI PROCEDURE REMOTE Un classico esempio è l’RPC in cui i messaggi scambiati per la comunicazione sono strutturati e non semplici come quelli dell’IPC, si indirizzano ad un demone in ascolto sulla porta del sistema remoto e contengono un’identificatore della funzione da eseguire e i parametri da inviare. Se un sistema remoto richiede un servizio (sapere quanti utenti attuali), deve possedere un demone in ascolto a una porta es. 3027 del server che realizzi un RPC in modo che qualsiasi sistema remoto inviando un messaggio RPC alla porta 3027 può sapere tale informazione. La semantica dell’RPC consente ad un client di invocare una procedura che si trova in un sistema remoto come se fosse locale, il sistema RPC nasconde i dettagli necessari che consentono che la comunicazione avvenga, tale sistema ottiene questo risultato assegnando un segmento di codice di riferimento (STUB) alle porte client. Quando il client invoca una procedura remota l’RPC chiama l’appropriato STUB, passando i parametri della procedura remota, lo stub individua la porta del server e struttura i parametri (marshalling) assemblandoli per trasmetterli in rete. Lo stub trasmette al server usando lo scambio di messaggi, un’analogo stub nel server riceve tale messaggio e invoca la procedura nel server. Una questione importante è la differenza nella rappresentazione dei dati nel client e nel server che l’RPC definisce indipendentemente dalla macchina ed è la rappresentazione esterna di dati (XDR). INVOCAZINE DI METODI REMOTI l’RMI è una funzione JAVA simile all’RPC, che permette ad un Head di invocare un metodo di un oggetto remoto, i due differiscono per due motivi fondamentali: l’RPC sono procedurali secondo cui si possono chiamare solo procedure a funzione remota, RMI sono orientate agli oggetti ed invocano metodi di oggetti remoti, poi i parametri per le procedure remote sono normali strutture dati nelle RPC, mentre le RMI si possono passare oggetti come parametri a metodi remoti. Per rendere i metodi trasparenti sia al client sia al server l’RMI realizzano un oggetto remoto usando lo stub nel client e lo scheletro nel server. CAP 5: THREAD 5.1 INTRODUZIONE Un thread, chiamato processo leggero, è l’unità di base dell’uso della c+ e comprende un’identificatore, un contatore di programma, un insieme di registri e uno stack. Condivide con gli altri thread che appartengono allo stesso processo la sezione del codice, i dati e le risorse di sistema. Un processo tradizionale è composto da un solo thread. MOTIVAZIONI Molti programmi per i moderni PC sono predisposti per essere eseguiti da processi multithread. Di solito, un’applicazione si codifica come un processo a se stante comprendente più thread di controllo: un programma

17

di consultazione del web potrebbe avere un thread per la rappresentazione sullo schermo, mentre un altro potrebbe occuparsi del reperimento dei dati nella rete. I thread hanno anche un ruolo primario nei sistemi che impiegano le RPC; si tratta di un sistema che permette la comunicazione tra processi. VANTAGGI I vantaggi della programmazione multithread si possono classificare in: - tempo di risposta: ossia del tempo morto, utilizzato per il cambio di contesto - Condivisione delle risorse: normalmente i thread condividono la memoria e le risorse del processo a cui appartengono - Economia: assegnare memoria e risorse per la creazione di nuovi processi è oneroso; poiché i thread condividono le risorse a cui appartengono, è molto più conveniente creare thread e gestirne i cambiamenti di contesto. - Uso ottimale delle piattaforme multi processore THREAD AL LIVELLO UTENTE E AL LIVELLO DEL NUCLEO LA gestione di thread può avvenire sia a livello d’utente sia al livello del nucleo. I thread al livello d’utente sono gestiti come uno strato separato sopra un nucleo del s.o. e sono realizzati tramite una libreria di funzioni, lo scheduling e la gestione senza alcun intervento diretto del nucleo. I thread al livello del nucleo sono gestiti direttamente al sistema operativo: Il nucleo si occupa della creazione, scheduling e gestione nello spazio d’indirizzi del nucleo. 5.2 MODELLI DI PROGRAMMAZIONE MULTITHREAD La pluralità di sistemi che gestiscono i thread, sia a livello d’utente sia al livello del nucleo, ha portato alla definizione di diversi modelli di programmazione multithread; di seguito analizziamo i più diffusi: MODELLO DA MOLTI A1: fa corrispondere molti thread a livello d’utente a un singolo thread al livello del nucleo. In questo modo si aumenta l’efficienza della gestione dei thread, diminuendo di fatto il tempo necessario per il cambio di contesto. Svantaggio principale di tale modello è che esso non supporta le piattaforme multiprocessore. MODELLO 1 A 1: il modello da 1 a 1, mette in corrispondenza ciascun thread del livello d’utente con un thread del livello del nucleo. Questo modello offre un grado di concorrenza maggiore poiché anche se un thread invoca una chiamata del sistema bloccante (ossia aspetta per esempio un operazione di I/O), è possibile eseguire un alto thread. L’unico svantaggio di questo modello è che la creazione di ogni thread al livello d’utente comporta la creazione di un thread al livello del nucleo, e ciò può compromettere le prestazioni del calcolatore appesantendolo. MODELLO DA MOLTI A MOLTI: il modello da molti a molti mette in corrispondenza più thread del livello d’utente con un numero minore o uguale di thread del livello del nucleo. Nel modello da molti a molti i programmatori possono creare liberamente i thread che ritengono necessari, e i corrispondenti thread del livello del nucleo si possono eseguire in parallelo nelle architetture dotate di più unità di elaborazione.

18

Inoltre, se un thread impiega una chiamata del sistema bloccante, il nucleo può fare in modo che si esegua un altro thread. 5.3 PROGRAMMAZIONE MULTITHREAD In un programma multithread la semantica delle chiamate di sistema fork e exec cambia: se un thread in un programma invoca la chiamata del sistema fork, il nuovo processo, potrebbe, in generale contenere un duplicato di tutti i thread oppure del solo thread invocante. La chiamata del sistema exec di solito restituisce l’intero processo, inclusi tutti i thread. La cancellazione dei thread è l’operazione che permette di terminare un thread prima che completi il suo compito. Ad esempio se più thread stanno facendo una ricerca in una base di dati e un thread riporta un risultato, gli altri possono essere annullati. Un thread da cancellare è spesso chiamato thread bersaglio. La cancellazione di un thread bersaglio può avvenire in due modi diversi:

- cancellazione asincrona: un thread fa immediatamente terminare il thread bersaglio

- cancellazione differita: il thread bersaglio può periodicamente controllare se deve terminare. Questo metodo permette di programmare la verifica in un punto dell’esecuzione in cui il thread può essere cancellato senza problemi. Tali punti sono chiamati punti di cancellazione.

GESTIONE DEI SEGNALI Nei sistemi UNIX si usano segnali per comunicare ai processi il verificarsi di determinati eventi. Un segnale si può ricevere in modo sincrono o in modo asincrono. Un accesso illegale alla memoria o una divisione per zero generano segnali sincroni. I segnali sincroni s’inviano allo stesso processo che ha eseguito l’operazione causa del segnale. Quando un segnale è causato da un evento esterno al processo in esecuzione, tale processo riceve il segnale in modo asincrono. Ogni segnale si può gestire in due modi:

- tramite un gestore predefinito di segnali - tramite un gestore di segnali definito dall’utente

sia i segnali sincroni che quelli asincroni si possono gestire in diversi modi: alcuni si possono semplicemente ignorare (ad esempio il ridimensionamento di una finestra), alti si possono gestire terminando l’esecuzione del programma (ad esempio un accesso illegale alla memoria). In generale esistono le seguenti possibilità:

- inviare il segnale al thread cui il segnale si riferisce - inviare il segnale a ogni thread del processo - inviare thread a specifici thread del processo - definire un thread ricevente

5.4 PTHREAD Con il termine pthread ci si riferisce allo standard POSIX che definisce l’API per la creazione e la sincronizzazione dei thread. Non si tratta di una realizzazione, ma di una definizione del comportamento dei thread; i progettisti di sistemi operativi possono realizzare le API così definite come meglio credono.

19

Tutti i programmi che impiegano la libreria pthread devono includere il file d’intestazione pthread.h. Fra le chiamate più importanti di tale standard vi sono:

- pthread_attr_init() utilizzata per passare gli attributi del thread - pthread_create() per la creazione dei thread

5.5 THREAD NEL SISTEMA WINDOWS 2000 Un’applicazione per ambiente windows si esegue come un processo separato e ogni processo può contenere uno o più thread. Il sistema windows 2000 usa il modello uno a uno. Ogni thread che appartiene a un processo può accedere allo spazio d’indirizzi virtuali di quel processo. I componenti generali di un thread includono:

- un identificatore di thread - un insieme di registri - una pila d’utente (stack) quando il thread è eseguito in modalità

d’utente - un’area di memoria privata, usata dalle librerie DLL

5.6 THREAD NEL SISTEMA LINUX I thread sono stati introdotti nel LINUX nella versione 2.2 del nucleo. Tale sistema operativo offre la chiamata del sistema fork con la funzione di creare un nuovo processo con una copia di tutte le strutture dati del processo stesso è la chiamata di sistema clone per la creazione di un thread: la funzione anziché creare una copia del processo, crea un processo distinto che condivide la memoria del processo chiamante, tale condivisione di memoria può essere totale o parziale. CAP 6: SCHEDULING DELLA CPU 6.1 INTRODUZIONE Lo scheduling della cpu è alla base dei sistemi operativi multiprogrammati attraverso la commutazione del controllo della cpu dei vari processi, il s.o. può rendere più produttivo il calcolatore. L’ obbiettivo della multiprogrammazione è avere sempre processi in esecuzione al fine di massimizzare la cpu. ESEGUZIONE DI UN PROCESSO L’esecuzione di un processo consiste in un ciclo di elaborazioni (svolte dalla cpu) e dall’attesa del completamento delle operazioni di I/O. I processi si alternano tra questi due stadi. L’ esecuzione di un processo comincia con un sequenza di operazioni svolte dalla cpu ( cpu burst), seguita da un sequenza di I/O, e cosi via. SCHEDULER DELLA CPU Ogni qual volta che la cpu passa nello stato di inattività , il s.o. sceglie l’ esecuzione di un processo presente nella coda dei processi pronti. Generalmente gli elementi delle code sono i descrittori dei processi (pcb). Il s.o. interviene per sostituire un processo quando questo ultimo:

- passa dallo stato di esecuzione a quello di attesa - passa dallo stato attesa a quello di pronto

20

- passa dallo stato di esecuzione a quello di pronto - il processo termina

Quando lo scheduling interviene solo nelle condizioni 1,4 si dice che lo schema di scheduling e senza diritto di prelazione (quando si assegna alla cpu un processo, questo rimane in possesso della cpu fino al momento del suo rilascio); altrimenti, lo schema di scheduling è con diritto di prelazione. L’unico inconveniente dello scheduling con diritto di prelazione è che esso non risulta utile quando vi sono processi cooperanti, ossia che condividono la memoria, in quanto risulta difficile gestire l’aggiornamento dei dati. DISPATCHER Un elemento coinvolto nella funzione di scheduling è il dispatcher esso si occupa effettivamente di:

- il cambio di contesto - il passaggio al modo utente - il salto alla giusta posizione del programma per riavviane

l’esecuzione il tempo richiesto per passare da un processo ad un altro è chiamato latenza di dispatch 6.2 CRITERI DI SCHEDULING Esistono diversi algoritmi di scheduling che anno proprietà differenti, essi generalmente vengono suddivisi in :

- utilizzo della cpu, che deve essere più attiva possibile - produttività ossia, in base al numero di processi completati nell’

unita di tempo - tempo di completamento, ossia il tempo necessario per eseguire il

processo - tempo di attesa, cioè la somma degli intervalli d’attesa passati

nella coda dei processi pronti - tempo di risposta, l’ intervallo di tempo che trascorre tra

l’inizio del processo è la “prima” risposta SCHEDULING IN ORDINE DI ARRIVO Il più semplice algoritmo di scheduling della cpu è l’algoritmo di scheduling in ordine di arrivo. Con questo schema la cpu si assegna al processo che la richiede per primo. La realizzazione del criterio fcfs si fonda su una coda fifo, unico inconveniente di quest’ultimo è che il tempo medio di attesa è spesso abbastanza lungo. L’algoritmo di schedulin fcfs è senza prelazione; una volta che la cpu è stata assegnata ad un processo questa la trattiene fino al momento del rilascio SCHEDULING PER BREVITA Un criterio diverso della cpu si può ottenere con l’algoritmo di scheduling per brevità(SJF). Tale algoritmo prevede di assegnare la cpu al processo che a la più breve lunghezza della successiva sequenza di operazioni della cpu, se due processi anno sequenze uguali si applica lo scheduling fcfs. Esistono di tale algoritmo due possibili modelli:

- senza diritto di prelazione : una volta associato alla cpu un processo lo rilascia solo quando ha terminato le sue istruzioni

21

- con diritto di prelazione : se arriva un processo con un tempo di burst minore del tempo di esecuzione rimasto al processo in corso questo viene sostituito.

L’algoritmo SJF è ottimale, nel senso che rende minimo il tempo di attesa medio per un dato insiemi di processi. Unico inconveniente di tale algoritmo è che la cpu non conosce il tempo di durata di una sequenza di istruzioni. Tale tempo viene però calcolata attraverso la media esponenziale delle effettive lunghezze delle precedenti sequenze di operazioni:

tn+1= αtn +(1+α)tn con :

- “ tn+1 “ valore previsto - “ tn “ valore della lunghezza dell’n-esima sequenza di operazioni - “ α “ parametro che vale generalmente ½

SCHEDULING PER PRIORITA’ Tale algoritmo prevede l’assegnamento ad ogni processo di una determinata priorità, generalmente un numero compreso tra l’intervallo dei numeri tra 0 e 4095; i processi con priorità uguali si ordinano secondo lo schema FCFS. Un problema importante relativo agli algoritmi di scheduling per priorità è la cosiddetta attesa indefinita: cioè, può accadere che un processo con bassa priorità non venga mai eseguito dal processore. Per ovviare a ciò generalmente con il passare del tempo di attesa del processo nella coda dei processi pronti, viene incrementata la priorità del processo(processo di AGING) SCHEDULING CIRCOLARE (ROUND ROBIN) Con tale algoritmo ciascun processo riceve una piccola quantità fissata del tempo della CPU, chiamata quanto di tempo, è la coda dei processi pronti è trattata come una coda circolare. Lo scheduler scorre la coda dei processi, assegnando la cpu a ciascun processo per un intervallo di tempo della durata massima di un quanto di tempo. Per tale algoritmo il tempo di attesa medio è spesso abbastanza lungo. Le prestazioni di tale algoritmo dipendono dalla dimensione del quanto di tempo: nel caso in cui è molto lungo il criterio di scheduling (RR)si riduce al criterio FCFS, le caso in cui il quanto di tempo è molto piccolo il processore passa più tempo a effettuare cambi di contesto che all’esecuzione di programmi. SCHEDULING A CODE MULTIPLE È stata creata una classe di algoritmi di scheduling adatta a situazioni in cui i processi si possono classificare facilmente in gruppi diversi. Una distinzione diffusa è ad esempio quella che si fa tra i processi che si eseguono in primo piano, o interattivi , e i processi che si eseguono in sottofondo, o a lotti. Si consideri il seguente algoritmo di scheduling a code multiple

- processi di sistema - processi interattivi - processi di editing - processi in sottofondo - processi degli studenti

ogni coda ha la priorità assoluta; nessun processo della coda di un livello inferiore può essere eseguito prima che una coda di livello superiore sia vuota.

22

SCHEDULING A CODE MULTIPLE CON RETROAZIONE Lo scheduling a code multiple con retroazione è simile a quello con le code multiple ma permette ai processi di spostarsi fra le code. L’idea è quella di separare i processi che hanno caratteristiche diverse nelle sequenze delle operazioni della cpu. Se un processo usa troppo tempo di elaborazione della cpu, viene spostato in una coda con priorità più bassa. Questo schema mantiene i processi con prevalenza di I/O e i processi interattivi nelle code con priorità più elevata. ES: All’ingresso nella coda dei processi pronti, i processi vengono assegnati alla coda 0 che ha un quanto di tempo di 8ms; i processi che non terminano entro tale quanto di tempo, vengono spostati nella coda 1 che ha come quanto di tempo 16 ms, e così via... Generalmente uno scheduler a code multiple con retroazione è caratterizzato da i seguenti parametri:

- numero di code - algoritmi di scheduling per ciascuna coda - metodo per determinare quando spostare un processo da una coda

inferiore a una superiore e viceversa ESEMPI DI SCHEDULING Il sistema operativo Windows compie lo scheduling dei thread servendosi di un algoritmo basato su priorità e prelazione. La porzione del nucleo che si occupa dello scheduling si chiama dispatcher per determinare l’ordine di esecuzione dei thread. Il dispatcher impiega uno schema di priorità a 32 livelli. Il dispatcher adopera una coda per ciascuna priorità di scheduling e percorre l’insieme delle code da quella a priorità più alta a quella con priorità più bassa. In assenza di thread da eseguire, il dispatcher fa eseguire un thread speciale detto IDLE THREAD. CAP 9: GESTIONE DELLA MEMORIA 9.1 INTRODUZIONE I programmi per essere eseguiti devono essere caricati nella memoria principale sottoforma di file binari ed inseriti all’interno di un processo, l’insieme di tutti i processi prende il nome di coda di ingresso. L’algoritmo per il trasferimento da memoria a disco consiste nello sciogliere uno dei processi appartenenti alla coda di ingresso e caricarlo in memoria, quando il processo termina si dichiara disponibile il suo spazio di memoria, inoltre l’occupazione in memoria può essere qualsiasi a partire da qualsiasi indirizzo. È comunque il compilatore ad assegnare gli indirizzi che si dividono in simbolici e rilocabili. L’associazione di istruzioni e dati si può compiere in qualsiasi fase del seguente percorso: - compilazione: se nella fase di compilazione si conosce l’indirizzo di residenza si può generare codice assoluto e se tale indirizzo cambiasse nel tempo occorrerebbe ricompilare il codice (per il dos sono i file .com) - caricamento: se l’indirizzo non si sa nella fase di compilazione il compilatore deve generare codice rilocabile che ritarda l’associazione finale degli indirizzi nella fase del caricamento, se dovesse cambiare l’indirizzo nel tempo è sufficiente ricaricare il codice.

23

- esecuzione: se durante l’esecuzione il processo è spostato da un indirizzo ad un altro l’associazione degli indirizzi va ritardata alla fase di esecuzione. SPAZI DI INDIRIZZI LOGICI E FISICI Un indirizzo generato dalla cpu si chiama indirizzo logico mentre quello caricato nel MAR si chiama indirizzo fisico. I metodi di assegnazione degli indirizzi nella fase di compilazione e caricamento generano indirizzi fisici e logici identici, durante l’esecuzione però gli indirizzi logici non coincidono con quelli fisici, infatti indirizzi logici sono chiamati indirizzi virtuali. L’associazione nella fase di esecuzione degli indirizzi virtuali agli indirizzi fisici è svolta da un dispositivo detto unità di gestione della memoria (MMU) in cui l registro di base e detto registro di rilocazione: quando un processo utente genera un indirizzo prima dell’invio alla unità di memoria si somma a tale indirizzo il valore contenuto nel registro di rilocazione. Il programma utente non considera mai gli indirizzi fisici reali, ma crea un puntatore alla locazione dell’indirizzo logico (cpu), lo memorizza, lo modifica e lo confronta con gli altri indirizzi come se fosse un numero. Il programma utente tratta indirizzi logici e l’architettura del sistema converte tali indirizzi in indirizzi fisici. CARICAMENTO DINAMICO Per migliorare l’utilizzo della memoria si ricorre al caricamento dinamico con cui si carica una procedura solo quando viene richiamata, in questo caso tutte le procedure si tengono su disco in un formato di caricamento rilocabile; si carica il programma principale in ram e durante l’esecuzione se una procedura ne vede chiamare un’altra si controlla per prima cosa che tutto sia stato caricato altrimenti si chiama il caricatore di collegamento rilocabile per caricare in ram la procedura richiesta e aggiornare la tabella degli indirizzi del programma (PCB), solo a questo punto il controllo passa alla procedura neo-caricata. Il vantaggio del caricamento dinamico è che se una procedura non si adopera, non viene caricata. Questo metodo è particolarmente utile nel caricamento di librerie condivise, poiché occorrerebbe avere una copia della libreria per ogni programma. Ogni volta che si fa riferimento ad una procedura di libreria, istruzioni necessarie per localizzare la libreria e come caricarla se non è già presente in memoria. SOVRAPPOSIZIONE DI SEZIONI Per permettere ad un processo di essere maggiore della memoria assegnatagli si usa la sovrapposizione di sezioni che si fonda sulla possibilità di mantenere in memoria solo le istruzioni e i dati che di usano maggiormente, quando sono necessarie altre istruzioni queste prendono il posto nello spazio precedentemente occupato dalle istruzioni che non sono più in uso. 9.2 AVVICENDAMENTO DEI PROCESSI Per essere eseguito un processo si deve trovare in ram ma può essere temporaneamente trasferito su disco per poi poterlo riportare in ram solo al momento dell’esecuzione, tale processo si chiama avvicendamento o scambio (swapping). Contemporaneamente lo scheduler della cpu assegna un quanto di tempo ad un altro processo presente in memoria, quando il suo tempo si esaurisce ciascun processo viene scambiato con un altro. Il

24

gestore della memoria scambia i processi in modo così rapido da far si che alcuni processi siano presenti permanentemente in memoria pronti per essere eseguiti. Una variante di tale algoritmo è quello a criterio di priorità, un processo che è stato scaricato dalla ram si deve ricaricare nello spazio di memoria occupato in precedenza e tale limitazione è dovuta al metodo di assegnazione degli indirizzi. L’avvicendamento dei processi richiede una memoria ausiliaria particolarmente veloce ed ampia poiché il sistema mantiene una coda dei processi pronti le cui immagini di ram si trovano su disco, quando lo scheduler decide di eseguire un processo chiama il dispatcher il quale controlla se il primo processo risiede in memoria se il processo non si trova in memoria perché non c’è spazio libero, il dispatcher scarica un processo dalla memoria e vi carica il processo richiesto dallo scheduler, in questo modo il tempo richiesto per un cambio di contesto è abbastanza elevato, circa 200 millisecondi. Occorre notare che maggior parte del tempo è dato dal tempo di trasferimento che è proporzionale alla quantità di memoria interessata 9.3 ASSEGNAZIONE CONTIGUA DELLA MEMORIA La ram deve contenere sia il sistema operativo che i vari processi per cui è importante assegnare le diverse parti nel modo più efficiente possibile, essa si divide in due porzioni, una per il sistema operativo ed una per i processi. Dato che più processi risiedono contemporaneamente in ram è necessario pensare a come assegnare la memoria disponibile ai processi presenti nella coda di ingresso che attendono di essere caricati, ciò viene fatto attraverso l’assegnazione contigua dove ciascun processo è contenuto in una singola sezione di dimensione prestabilita. PROTEZIONE DELLA MEMORIA Al fine di proteggere i processi utente da alti processi utenti si utilizza un registro di rilocazione con un registro di limite che contiene il valore dell’indirizzo fisico minore e il registro limite contiene l’intervallo degli indirizzi logici quindi ogni indirizzo logico deve essere minore del contenuto del registro limite, a MMU fa corrispondere dinamicamente l’indirizzo fisico all’indirizzo logico sommando a quest’ultimo il valore contenuto nel registro di rilocazione. Quando lo scheduler seleziona un processo il dispatcher durante il cambio di contesto carica il registro di rilocazione e di limite con i valori corretti. ASSEGNAZIONE DELLA MEMORIA Uno dei metodi per l’assegnazione della memoria consiste nel dividerla in partizioni fisse in modo che quando una partizione è libera può essere occupata da un processo in coda che una volta finito libera la partizione per un altro processo, tale metodo è detto MFT e una sua generalizzazione è l’MVT che si usa in sistemi ad elaborazione a lotti, il sistema operativo conserva una tabella nella quale sono indicate le partizioni di memoria disponibili ed occupate, inizialmente tutta la memoria è a disposizione come un grande buco. Quando si carica u processo occorre cercare un buco sufficientemente grande e se esiste si assegna solo la parte di memoria necessaria e la parte rimanente del buco si usa per richieste future. Un problema di importanza rilevante è quello dell’assegnazione dinamica della memoria che consiste nel soddisfare una richiesta di dimensione n data una lista di buchi liberi, i criteri sono i seguenti:

- si assegna il primo buco abbastanza grande (first fit)

25

- si assegna il più piccolo buco in grado di contenere il processo ma per far ciò si deve ricercare nell’intera lista (best fit)

- si assegna il buco più grande, anche in questo caso si deve esaminare tutta la lista (worst fit)

tali processi soffrono di frammentazione esterna ossia quando si caricano e si rimuovono processi dalla memoria si frammenta lo spazio libero in tante piccole parti e ciò potrebbe procurare ingenti spechi di ram. FRAMMENTAZIONE Per risolvere il problema della frammentazione esterna si usa la compattazione che riunisce la memoria libera in un unico grosso blocco generalmente posto dopo l’ultimo blocco utilizzato. 9.4 PAGINAZIONE È un metodo di gestione della memoria che permette che lo spazio degli indirizzi fisici di un processo non sia contiguo. Si suddivide la memoria fisica in blocchi di dimensione fisse (frame) e la memoria logica in blocchi detti pagine. Quando si deve eseguire un processo si caricano le sue pagine nei blocchi di memoria disponibile, prendendole dal disco che è diviso in blocchi fissi uguali a quelli della ram. Ogni indirizzo generato dalla cpu è diviso in due parti: numero di pagina (P) e uno scostamento di pagina (d), il primo serve come indice per la tabella delle pagine contente l’indirizzo di base nella memoria fisica di ogni pagina e il secondo che viene utilizzato insieme al valore dell’indirizzo di base per generare l’effettivo indirizzo fisico della memoria. Ad ogni processo viene associata una singola tabella delle pagine con la quale si identificano in modo esatto i blocchi (frame) utilizzati dal processo stesso. ARCHITETTURA DELLA PAGINAZZIONE Ogni sistema operativo segue metodi propri per memorizzare le tabelle delle pagine,la maggior parte dei sistemi impiega la tabella delle pagine per ciascun processo ed in inoltre l’indirizzo di tale tabella è contenuto all’interno del PCB. Nel caso più semplice le tabelle delle pagine vengono realizzate mediante registri,ma quest’ultima soluzione non è vantaggiosa per tabelle superiori a 256 elementi. La maggior parte dei calcolatori odierni usa infatti tabelle molto grandi, ad esempio di 1 milione di elementi per cui non sono sufficienti i registri per memorizzare le pagine. Per ovviare a ciò le tabelle risiedono in ram ed un registro specifico, il PTBR punta alla tabella stessa. Inconveniente di ciò è che si alzano notevolmente i tempi di accesso alla memoria in quanto bisogna fare più accessi(generalmente 2). Una soluzione ottimale è l’utilizzo di una piccola cache TLB suddivisa in 2 parti: una chiave ed un valore. Quando si presenta un elemento, la memoria la confronta contemporaneamente con tutte le chiavi; se trova una corrispondenza riporta il valore trovato. Il TLB si usa insieme con le tabelle della pagine nel seguente modo: contiene una piccola parte degli elementi delle pagine; quando la cpu genera un indirizzo logico, si presenta il suo numero di pagina al TLB, se tale numero è presente il corrispondente numero di blocco di memoria è immediatamente disponibile, nel caso contrario, si deve consultare la tabella nel modo tradizionale.

26

La percentuale di volte che un numero di pagina si trova nel TLB si chiama tasso di successi. Per calcolare il tempo effettivo di accesso alla memoria occorre usare la seguente formula:

t= (tmem+ttlb)*a+(2*tmem+ttlb)*(1-a) dove: tmem = tempo di accesso alla memoria; ttlb = tempo di accesso alla tlb; a = tasso di successi. PROTEZIONE In un ambiente a paginazione, la protezione della memoria è assicurata dai bit di protezione associati ad ogni blocco di memoria; normalmente tali bit si trovano nella tabella delle pagine. Un bit può determinare per esempio se una pagina si può leggere o scrivere oppure solamente leggere. Di solito si associa un ulteriore bit detto di validità a ciascun elemento della tabella delle pagine. Tale bit impostato a “valido” indica che tale pagina corrispondente è nello spazio di indirizzi logici del processo. Il bit di validità consente di riconoscere gli indirizzi illegali e di notificarne la presenza attraverso un segnale di eccezione. Altre architetture dispongono di registri, detti registri di lunghezza della tabella delle pagine(PTLR),per indicare le dimensioni della tabella. STRUTTURA DELLA TABELLA DELLE PAGINE La maggior parte dei moderni calcolatori dispone di uno spazio di indirizzi logici molto grande, per cui si possono avere tabelle delle pagine eccessivamente grandi, chiaramente sarebbe meglio evitare di collocare tabelle enormi in ram. Una semplice soluzione consiste nel dividere la tabella in parti più piccole; risultato ottenibile in molti modi. Una possibile soluzione è quella di paginare la stessa tabella delle pagine. Paginando la tabella delle pagine viene modificato di fatto l’indirizzo logico, il quale viene suddiviso in tre parti, una prima parte p1 è un indice della tabella di primo livello o esterna e p2 è lo scostamento all’interno della pagina indicata dalla tabella esterna delle pagine e l’ultima parte d è lo scostamento di pagina. TABELLA DELLE PAGINE DI TIPO HASH Altro metodo molto comune per la gestione della tabella è l’impiego di una tabella di tipo hash in cui l’argomento della funzione di hash è il numero della pagina virtuale. Per la gestione delle collisioni ogni elemento della hash contiene una lista concatenata di elementi che la funzione hash fa corrispondere alla stessa locazione. Ciascun elemento è composto da tre campi, un numero di pagine virtuali e l’indirizzo del blocco della memoria fisica, che corrisponde alla pagina virtuale e un untatore al successivo elemento della lista. p TABELLA DELLE PAGINE INVERTITA Si associa una tabella delle pagine a ogni processo e tale tabella contiene un elemento per ogni pagina virtuale che il processo sta utilizzando, ciò è una rappresentazione virtuale poiché i processi fanno riferimento alle pagine tramite gli indirizzi virtuali che il sistema operativo traduce in indirizzi fisici. Poiché tale tabella è ordinata per

27

indirizzi virtuali, il sistema operativo calcola in che punto della tabella si trova l’elemento dell’indirizzo fisico associato e usa direttamente tale valore. Uno degli inconveniente è quello che la tabella delle pagine può contenere anche milioni di elementi ed occupare grandi quantità di memoria fisica. Per risolvere ciò, si fa uso della tabella delle pagine invertita che ha un solo elemento per ogni pagina reale e tale elemento è costituito dall’indirizzo virtuale della pagina con informazioni sul processo che possiede tale pagina. Nel sistema esiste una sola tabella delle pagine che ha un solo elemento per ciascuna pagina di memoria fisica. PAGINE CONDIVISE Un altro vantaggio della paginazione è quello di condividere codice comune. Si consideri un sistema con 40 utenti, se tale programma è formato da 150 KB di codice e 50 KB di spazio di dati, per gestire i 40 utenti sono necessari 8MB, se però il è rientrante può essere condiviso. Il codice rientrante o puro è un codice che non cambia durante l’esecuzione e due o più processi possono eseguirlo nello stesso momento. Nella memoria fisica è presente una sola copia dell’elaboratore di testi, la tabella delle pagine di ogni utente fa corrispondere gli stessi blocchi di memoria contenenti l’elaboratore di testi; per gestire 40 utenti bastano una copia dell’elaboratore di testi(150KB) e 40 copie di 50 KB per un totale di 2150 KB. Si possono condividere anche altri programmi d’uso frequente come compilatori,interfacce e finestre,librerie… con l’unico vincolo che il codice deve essere rientrante. 9.5 SEGMENTAZIONE Si effettua una separazione tra la visione della memoria dell’utente e l’effettiva memoria fisica, lo spazio “visto” dall’utente non è quello dell’effettiva memoria fisica, ma si fa corrispondere alla memoria fisica. I metodi che stabiliscono questa corrispondenza consentono di separare la memoria logica dalla memoria fisica. METODO DI BASE L’utente può considerare la memoria come un vettore lineare di byte? La tipica struttura di un programma è costituita di una parte principale e di un gruppo di procedure, funzioni o moduli, ciascuno di questi moduli si identifica con un nome: “tabella dei simboli”,”funzione sqrt”,”programma principale”… Ciascuno di questi segmenti ha una lunghezza variabile e gli elementi che si trovano all’interno di un segmento sono identificati dal loro scostamento, misurato dall’inizio del segmento. La segmentazione è uno schema di gestione della memoria che consente di gestire questa visione della memoria da parte dell’utente. Uno spazio d’indirizzi logici è una raccolta di segmenti, ciascuno dei quali ha un nome e una lunghezza; l’utente fornisce ogni indirizzo come una coppia ordinata di valori: un nome di segmento e uno scostamento. Questo schema contrasta con la paginazione nella quale l’utente fornisce un indirizzo singolo che l’architettura di paginazione divide in un numero di pagina e uno scostamento non visibili dal programmatore(protected). ARCHITETTURA DI SEGMENTAZIONE La memoria fisica è una sequenza di byte unidimensionale, per questo motivo occorre tradurre gli indirizzi bidimensionali definiti dall’utente

28

negli indirizzi fisici unidimensionali. Ciò si compie tramite una tabella dei segmenti, in cui ogni suo elemento è una coppia ordinata: la base del segmento e il limite del segmento. La base contiene l’indirizzo fisico iniziale della memoria al quale il segmento risiede e il limite contiene la lunghezza del segmento. Un indirizzo logico è formato da due parti: un numero di segmento s e uno scostamento in tale segmento d. Il numero di segmento si usa come indice per la tabella dei segmenti; lo scostamento d deve essere compreso tra 0 e il limite del segmento, altrimenti s’invia un segnale d’eccezione al sistema operativo. Si somma lo scostamento alla base del segmento per produrre l’indirizzo della memoria fisica a cui si trova il byte desiderato. Quindi la tabella dei segmenti è fondamentalmente un vettore di coppie di registri di base e limite. FRAMMENTAZIONE Lo scheduler a lungo termine deve trovare e assegnare spazio di memoria per tutti i segmenti di un programma utente, tale situazione è analoga alla paginazione, con la differenza che i segmenti a differenza delle pagine hanno lunghezza variabile, per cui l’assegnazione della memoria è un problema di assegnazione dinamica che si complica se tutti i blocchi di memoria libera sono troppo piccoli perché contengano un segmento(frammentazione esterna). La segmentazione è un algoritmo di rilocazione dinamico grazie al quale la memoria si può compattare in qualsiasi momento. 9.6 SEGMENTAZIONE CON PAGINAZIONE(INTEL 80386) Per la gestione della memoria l’80386 adotta la segmentazione con paginazione, il numero massimo di segmenti per processo è di 16KB e ciascun segmento può avere dimensioni fino a 4GB e la dimensione delle pagine è di 4KB. Lo spazio degli indirizzi logici di un processo è diviso in due porzioni: la prima contiene segmenti di dimensioni fino a 8KB riservati al processo e la seconda contiene segmenti di dimensioni fino a 8KB condivisi fra tutti i processi. Le informazioni riguardanti la prima partizione sono contenute nella tabella locale dei descrittori(LTD) quelle relative alla seconda partizione sono memrorizzate nella tabella globale dei descrittori(GDT) Ciascun elemento nella LDT e nella GDT è composto da 8 byte, un indirizzo logico è una coppia selettore,scostamento e il selettore è un numero di 16 bit nella forma:

s---------g--------p 13-------1---------2

Dove s indica il numero del segmento,g indica se il segmento si trova nella GDT o nella LDT e p contiene informazioni relativa alla protezione. Lo scostamento è un numero di 32 bit che indica la posizione del byte all’interno del segmento in questione. Un indirizzo fisico del 386 è lungo 32 bit e si genera come segue: il registro del segmento punta all’elemento appropriato all’interno della LDT o della GDT, le informazioni relative alla base e al limite di tale segmento di usano per generare un indirizzo lineare. Ogni segmento è paginato in pagine di 4 KB e ciò implica la possibilità che ogni processo potrebbe occupare fino a 4 MB di spazio fisico per la sola tabella delle pagine. Il 386 risolve il problema adottando una paginazione a 2 livelli. L’indirizzo lineare è suddiviso in un numero di pagina di 20 bit e uno scostamento di pagina di 12 bit, essendo paginata

29

anche la tabella delle pagine, il numero di pagina è ulteriormente diviso in 2 puntator1 di 10 bit,l’indirizzo logico ha la forma:

n pag--scost p1----p2-----d 10----10----13

CAP 10: MEMORIA VIRTUALE 10.1 INTRODUZIONE La memoria virtuale è una tecnica che permette di eseguire processi che possono non essere completamente contenuti in ram. La memoria virtuale è però difficile da realizzare e, s’è usata scorrettamente, può ridurre di molto le prestazioni del sistema. Il vantaggio principale di tale tecnica è quello di permettere che i programmi siano più grandi della memoria fisica a disposizione. Infatti, molto spesso alcune opzioni e procedure di processi vengono utilizzate raramente, e quindi esse possono anche non essere caricate in ram. La memoria virtuale rappresenta la separazione della memoria logica, vista dall’utente, dalla memoria fisica, vista dal sistema. Essa facilita la programmazione in quanto il programmatore non si deve preoccupare della quantità di memoria fisica a disposizione, ma può concentrarsi sul problema da risolvere. La memoria virtuale generalmente viene realizzata in forma di paginazione su richiesta. 10.2 PAGINAZIONE SU RICHIESTA I processi risiedono nella memoria secondaria, per eseguire un processo, quindi occorre che esso venga caricato in ram. Tuttavia, anziché caricare nella memoria l’intero programma, si può seguire un criterio di avvicendamento pigro; non si carica mai nella ram una pagina se essa non è necessaria. Per cui con l’utilizzo della memoria virtuale si considera un processo come una sequenza di pagine ,invece di un unico ampio spazio di indirizzi contigui. Nell’ambito della paginazione su richiesta, colui che si occupa della gestione delle pagine si chiama paginatore. Con l’avvicendamento di pagine tra ram e memoria secondaria, quindi è necessario che il calcolatore disponga di un qualche meccanismo che consenta di distinguere tra pagine presenti in ram e pagine presenti nei dischi. A tale schema si può utilizzare lo schema basato su bit di validità:

- valid bit = 1 pagina presente in ram - valid bit = 0 pagina presente nei dischi

Se un determinato processo tenta di accedere a una pagina che non è stata caricata in memoria, l’accesso a una pagina contrassegnata come non valida causa un’eccezione di pagina mancante (page fault). La procedura di gestione dell’eccezione di pagina mancante è chiara:

- si controlla nel PCB se il riferimento è valido o si sta tentando di fare un accesso illegale alla memoria

- se il riferimento non è valido viene terminato il processo - se il riferimento è valido, ma non è ancora presente in memoria

viene effettuato l’inserimento

30

- viene dapprima cercato un frame libero, ad esempio prelevandone uno dall’elemento dei blocchi liberi

- viene programmata l’operazione dei dischi per portare il blocco nella zona di memoria appena trovata

- a lettura completata vengono aggiornate le tabelle interne, ad esempio il PCB del processo

- a questo punto il programma può riprendere la normale esecuzione utilizzando la pagina appena caricata in memoria

una volta portata la pagina nella memoria, il processo continua l’esecuzione, subendo assenze di pagine fino a che tutte le pagine necessarie non si trovano effettivamente in memoria. Lo schema descritto è una paginazione su richiesta pura, vale a dire che una pagina non si trasferisce in ram fino a quando essa non è effettivamente richiesta. Molti programmi, però tendono ad avere, una località dei riferimenti, per cui molto spesso oltre alla pagina richiesta vengono caricate in ram anche le pagine contigue a quest’ultima. PRESTAZIONI DELLA PAGINAZIONE SU RICHIESTA La paginazione su richiesta può avere un effetto rilevante sulle prestazioni di un calcolatore. Il motivo si può comprendere calcolando il tempo di accesso effettivo per una memoria con paginazione su richiesta. Attualmente, nella maggior parte dei calcolatori il tempo di accesso alla memoria, denominata “ma” varia tra i 10 e i 200 nanosecondi. Supponendo che “p” sia la probabilità che si verifichi un’assenza di pagina, il tempo di accesso effettivo è dato dalla seguente espressione:

EAT = (1-p)* ma + p * tempo di gestione dell’assenza di pagina Il tempo di gestione dell’assenza di pagina comprende:

- tempo di gestione dell’eccezione - salvataggio del contesto - individuazione di un frame libero - aggiornamento delle strutture dati della memoria virtuale - ripristino del contesto - ripresa dell’interruzione interrotta

vediamo alcuni esempi: consideriamo un tempo medio di servizio dell’eccezione di pagina mancante di 25 millisecondi e un tempo di accesso alla memoria di 100 nanosecondi, il tempo effettivo d’accesso in nanosecondi risulta: EAT = (1-p)*100 + p*25000000 = 100 + 24999900*p 10.3 CREAZIONE DEI PROCESSI Con la paginazione su richiesta vengono offerti numerosi vantaggi per quanto riguarda la creazione dei processi. Infatti nella lettura dei file dai dischi alla memoria, inclusi i file eseguibili in formato binario, viene impiegata la paginazione su richiesta. Questa tecnica permette una creazione dei processi molto rapida e minimizza il numero di pagine che si devono assegnare al nuovo processo. Si ricordi che la chiamata del sistema fork crea un processo figlio come duplicato del genitore. Nella sua versione originale la fork creava per il figlio una copia dello spazio di indirizzi del genitore,

31

duplicando le pagine appartenenti al processo genitore. In alternativa si può impiegare una tecnica nota come copiatura su scrittura, il cui funzionamento si basa sulla condivisione iniziale delle pagine da parte dei processi genitori e dei processi figli. Le pagine condivise si contrassegnano come pagine da copiare su scrittura, a significare che, se un processo scrive su una pagina condivisa, il sistema deve creare una copia di tale pagina. Si consideri l’esempio di un processo figlio che cerca di modificare una pagina che contiene parti dello stack. La tecnica di copiatura su scrittura è piuttosto comune e si usa in diversi sistemi operativi, tra i quali windows 2000, LINUX e Solaris 2. Quando è necessaria la duplicazione di una pagina secondo la tecnica di copiatura su scrittura, è importante capire da dove si attingerà la pagina libera necessaria. Molti sistemi operativi forniscono, per queste richieste, un gruppo di pagine libere (pool). Diverse versioni di UNIX offrono anche una variante della chiamata del sistema fork detta vfork. Con la vfork si sospende il processo genitore e il processo figlio usa lo spazio d’indirizzi del genitore. In questo modo se il processo figlio modifica qualche pagina dello spazio di indirizzi del genitore, le pagine modificate saranno visibili al processo genitore non appena prenderà il controllo. ASSOCIAZIONE DEI FILE ALLA MEMORIA Si consideri un accesso sequenziale per lettura a un file su disco, per mezzo delle normali chiamate di sistema open, read e write. Ogni accesso al file richiede una chiamata e un accesso al disco. In alternativa, si possono usare le tecniche di memoria virtuale, considerando l’I/O relativo a un file come un ordinario accesso alla memoria. Questo metodo si chiama associazione alla memoria di un file e consiste nel permettere che una parte dello spazio degli indirizzi virtuali sia associata logicamente a un file. Questo si realizza facendo corrispondere un blocco di disco (frame) a una pagina della memoria. L’accesso iniziale al file avviene per mezzo dell’ordinario meccanismo di paginazione su richiesta, che determina un’assenza di pagina cui segue, però, il caricamento di una pagina fisica di una porzione di file della dimensione di una pagina, leggendola dal file system. Le successive operazioni di lettura e scrittura avvengono come normali accessi in ram. La chiusura di un file comporta la scrittura su disco secondario di tutte le informazioni presenti i ram e la rimozione del processo dalla memoria virtuale. Alcuni sistemi operativi offrono l’associazione alla memoria soltanto attraverso specifiche chiamate del sistema e gestiscono tutte le altre operazioni di I/O su file attraverso le normali chiamate del sistema. 10.4 SOSTITUZIONE DELLE PAGINE Con l’aumentare del grado di multiprogrammazione, e quindi numerosi processi che girano in contemporanea, è sorto un sostanziale problema di fondo: le dimensioni limitate della memoria principale e la sovrascrittura della memoria. Per tale motivo nei moderni sistemi operativi è utilizzata la tecnica della sostituzione delle pagine. La sostituzione delle pagine segue il seguente criterio: se nessun blocco di memoria è libero, si può liberarne uno attualmente utilizzato. Viene quindi modificata la procedura dell’eccezione di pagina mancante in modo da includere la sostituzione della pagina:

- si individua la locazione su disco richiesta

32

- si cerca un blocco libero, se esiste, lo si usa - altrimenti si impiega un algoritmo di sostituzione delle pagine per

scegliere un blocco di memoria vittima - si scrive la pagina vittima su disco - viene caricata la pagina richiesta dal disco al blocco appena

liberato - si riavvia il processo utente

Occorre notare che se non esiste nessun blocco libero di memoria sono necessari due accessi di memoria. Questo sovraccarico può essere ridotto utilizzando un bit di modifica. Esso viene associata ad ogni pagina, il quale viene impostato a 1 ogni volta che si scrive una parola o un byte su la pagina. Se il bit di modifica non è attivo,significa che la pagina non è stata modificata rispetto a quando era stata letta da disco. Questa tecnica vale anche per le pagine di sola lettura, ad esempio pagine di codice binario. La sostituzione di una pagina è fondamentale al fine della paginazione su richiesta, perché completa la separazione tra la memoria logica e la memoria fisica. Per la realizzazione della paginazione su richiesta è necessario risolvere due problemi principali: occorre sviluppare un algoritmo di assegnazione dei blocchi di memoria e un algoritmo di sostituzione delle pagine. Esistono molti algoritmi di sostituzione delle pagine; probabilmente ogni sistema operativo ha il proprio schema di sostituzione. È quindi necessario stabilire un criterio per selezionare un algoritmo di sostituzione particolare; generalmente si sceglie quello con la minima frequenza delle assenze di pagine. SOSTITUZIONE DELLE PAGINE SECONDO L’ORDINE D’ARRIVO (FIFO) L’algoritmo di sostituzione delle pagine più semplice è un algoritmo fifo. Se si deve sostituire una pagina, si seleziona quella presente nella memoria da più tempo. In questo modo si sostituisce la pagina che si trova nel primo elemento della coda. Quando si carica una pagina nella memoria, la si inserisce nell’ultimo elemento della coda. L’algoritmo fifo di sostituzione delle pagine è facile da capire e da programmare; tuttavia le sue prestazioni non sono sempre buone. La pagina sostituita potrebbe essere un modulo di inizializzazione usato molto tempo prima e che non serve più, ma potrebbe anche contenere una variabile molto usata, inizializzata precedentemente, e ancora in uso. Occorre notare che in alcuni casi il numero delle assenze di pagine per un numero “n” di blocchi è maggiore del numero delle assenze di pagine per “m” blocchi di memoria, con m più piccolo di n. questo inatteso risultato è noto col nome di anomalia di Belady, e riflette il fatto che con alcuni algoritmi di sostituzione delle pagine la frequenza delle assenze di pagine può aumentare con l’aumentare del numero di blocchi di memoria assegnati. SOSTITUZIONE DELLE PAGINE OTTIMALE In seguito alla scoperta dell’anomalia di Belady, la ricerca si è diretta verso un algoritmo ottimale di sostituzione delle pagine. Tale algoritmo è quello tra tutti gli algoritmi presenta la minima frequenza di assenze di pagine e non presenta l’anomalia di Belady. È semplicemente:

- si sostituisce la pagina che non si userà per il periodo di tempo più lungo

l’uso di questo algoritmo di sostituzione assicura la frequenza di assenze più bassa possibile per un numero fissato di blocchi di memoria.

33

Sfortunatamente l’algoritmo ottimale di sostituzione delle pagine è difficile da realizzare, perché richiede la conoscenza futura della successione di riferimenti. Quindi l’algoritmo ottimale si usa solo per studi comparativi. SOSTITUZIONE DELLE PAGINE USATE MENO RECENTEMENTE Se l’algoritmo ottimale non è realizzabile, è forse possibile realizzare un’approssimazione. Usando come approssimazione di un futuro vicino con un passato recente, si sostituisce la pagina che non è stata utilizzata per il periodo di tempo più lungo, ottenendo così l’algoritmo LRU. La sostituzione LRU associa a ogni pagina istante in cui è stata usata per l’ultima volta. Il criterio LRU si usa spesso come algoritmo di sostituzione delle pagine ed è considerato valido. Il problema principale riguarda la realizzazione della sostituzione stessa. Il problema consiste nel determinare un ordine per i blocchi di memoria definito secondo il momento dell’ultimo uso. Si possono realizzare le seguenti soluzioni:

- contatori: nel caso più semplice, a ogni elemento della tabella delle pagine si associa un campo del momento d’uso, e alla cpu si aggiunge un contatore che si incrementa a ogni riferimento di memoria. Ogni volta che si fa riferimento a una pagina, si copia il contenuto del registro contatore nel campo del momento d’uso nella tabella relativa a quella specifica pagina. In questo modo è sempre possibile conoscere il momento in cui è stato fatto l’ultimo riferimento a ogni pagina.

- Pila (Stack): ogni volta che si fa riferimento a una pagina, la si estrae dalla pila e la si colloca in cima a quest’ultima. In questo modo, in cima alla pila si trova sempre la pagina usata per ultima, mentre in fondo si trova la pagina usata meno recentemente.

APPROSSIMAZIONE DELL’ALGORITMO LRU Sono però pochi i sistemi di calcolo che dispongono di un’architettura adatta a una vera sostituzione LRU delle pagine. Molti sistemi, però possono fornire un aiuto: un bit di riferimento. I bit di riferimento sono associati a ciascun elemento della tabella delle pagine. Inizialmente il sistema operativo azzera tutti i bit. Quando inizia l’esecuzione di un processo, l’architettura del sistema imposta a 1 il bit associato a ciascuna pagina cui si fa riferimento. Dopo qualche tempo è possibile stabilire quali pagine sono state usate semplicemente esaminando i bit di riferimento. Non è possibile conoscere l’ordine d’uso. Ulteriori informazioni sull’ordinamento si possono ottenere registrando i bit di riferimento a intervalli regolari. È possibile conservare in una tabella della memoria una serie di bit per ogni pagina (per esempio u registro a scorrimento) i quali vengono aggiornati a intervalli regolari. Se per esempio un registro a scorrimento contiene la successione di bit 00000000, significa che la pagina associata non è stata utilizzata da otto periodi di tempo; a una pagina usata per esempio almeno una volta da 4 periodi di tempo corrisponde la successione 0001XXXX nel registro a scorrimento. Una pagina cui corrisponde la successione 11000100 nel relativo registro,è stata utilizzata più recentemente di quanto non lo sia stata una cui è associata la successione 01110111. ALGORITMO CON SECONDA CHANCE

34

Tale algoritmo utilizza i reference bit, ed esso è un algoritmo di sostituzione di tipo fifo. Dopo aver selezionato una pagina si controlla il bit di riferimento, se il suo valore è 0, si sostituisce la pagina; se il bit di riferimento è impostato a 1, si da una seconda chance alla pagina e la selezione passa alla successiva pagina fifo. Quando una pagina riceve una seconda chance, si azzera il suo bit di riferimento è si aggiorna il suo istante d’arrivo al momento attuale. In questo modo se una pagina è usata abbastanza spesso, in modo che il suo bit di riferimento sia sempre impostato a 1, non viene mai sostituita. Un metodo per realizzare l’algoritmo con seconda chance,è basato sull’uso di una coda circolare, nella quale un puntatore indica qual è la prima pagina da sostituire. SOSTITUZIONE DELLE PAGINE BASATA SUL CONTEGGIO Esistono molti altri algoritmi che si possono usare per la sostituzione delle pagine. Ad esempio, si potrebbe usare un contatore del numero dei riferimenti che si sono fatti a ciascuna pagina e sviluppare i due seguenti schemi:

- algoritmo di sostituzione delle pagine usate meno frequentemente (LFU): richiede che si sostituisca la pagina con il conteggio più basso. La ragione di questa scelta è che una pagina usata attivamente deve avere un conteggio di riferimento alto.

- Algoritmo di sostituzione delle pagine usate più frequentemente (MFU): è basato sul fatto che, probabilmente, la pagina con il contatore più basso è stata appena inserita e non è stata ancora usata.

10.5 ASSEGNAZIONE DEI BLOCCHI DI MEMORIA A questo punto occorre stabilire un criterio per l’assegnazione della memoria libera ai diversi processi. Il modo più semplice per suddividere m blocchi di memoria tra n processi è quello per cui a ciascun processo si dà una parte uguale, m/n blocchi di memoria. Ad esempio 100 blocchi disponibili in 5 processi, ad ogni processo vengono assegnati 20 blocchi. Questo schema è chiamato assegnazione uniforme. Un’alternativa consiste nel riconoscere che diversi processi hanno bisogno di quantità di memoria diverse. Per risolvere questo problema è possibile ricorrere all’assegnazione proporzionale, secondo cui la memoria disponibile si assegna a ciascun processo secondo la sua dimensione. Si supponga che si sia la dimensione della memoria virtuale del processo pi , e S sia la somma complessiva dei blocchi utilizzati da tutti i processi. Quindi se il numero totale dei blocchi della memoria è “m” al processo pi si assegnano approssivamente:

(si / S)* m Esempio: usando l’assegnazione proporzionale per suddividere 62 blocchi di memoria tra due processi, uno di 10 e uno di 127 pagine, vengono assegnati rispettivamente:

p1 = (10 / 137)* 62 = 4 p2 = (127 / 137)* 62= 57

35

una piccola variante consiste nell’uso di uno schema di assegnazione proporzionale in cui il rapporto dei blocchi di memoria non dipende dalle dimensioni relative ai processi, ma dalle priorità degli stessi oppure da una combinazione di dimensioni e di priorità. ASSEGNAZIONE GLOBALE ED ASSEGNAZONE LOCALE Un altro importante fattore che riguarda il modo in cui si assegnano i blocchi di memoria ai vari processi è la sostituzione delle pagine. Nei casi in cui vi siano in competizione per i blocchi di memoria, gli algoritmi di sostituzione delle pagine si possono dividere in due categorie principali: sostituzione globale e sostituzione locale. La sostituzione globale consente che per un processo si scelga un blocco di memoria per la sostituzione dall’insieme di tutti i blocchi di memoria, anche se un blocco di memoria è correntemente assegnato a qualche altro processo. La sostituzione locale richiede invece che per ogni processo si scelga un blocco di memoria solo dal suo insieme di blocchi di memoria. 10.6 ATTIVITA’ DI PAGINAZIONE DEGENERE (THRASHING) Se un processo non dispone di un numero sufficiente di blocchi di memoria per la sua esecuzione, esso accusa immediatamente un’assenza di pagina. A questo punto si deve sostituire una pagina; ma poiché sono tutte in uso attivo, si deve sostituire una pagina che sarà immediatamente necessaria. Il processo continua a subire assenze di pagine, facendo sostituire pagine che saranno immediatamente trattate come assenti e dovranno essere riprese. Questa intensa e degenere attività di paginazione si verifica quando il calcolatore spende più tempo per la paginazione che per l’esecuzione dei processi. Se inoltre ci si somma il fatto che il sistema operativo vigilando sulla cpu, osserva che il suo utilizzo risulta notevolmente calato di prestazioni, decide di introdurre un nuovo processo, la situazione precipita enormemente, come un cane che si morde la coda. Gli effetti di questa situazione si possono limitare usando un algoritmo di sostituzione locale, o algoritmo di sostituzione per priorità. Con la sostituzione locale, se l’attività di un processo degenera, non si possono sottrarre blocchi di memoria a un altro processo e quindi non si può far degenerare la relativa attività della paginazione. Le pagine si sostituiscono tenendo conto del processo di cui fanno parte. Per evitare il verificarsi di situazioni di degenerazione, occorre fornire al processo tutti i blocchi di memoria di cui necessità. Per cercare di sapere quanti blocchi di memoria “servono” a un processo si impiegano diverse tecniche. Il modello dell’insieme di lavoro, comincia osservando quanti sono i blocchi di memoria che un processo sta effettivamente usando. Questo metodo definisce il modello di località dell’esecuzione di un processo. Una località è un insieme di pagine usate attivamente da un processo per un determinato periodo di tempo. MODELLO DELL’INSIEME DI LAVORO Il modello dell’insieme di lavoro è basato sull’ipotesi di località. Questo modello usa un parametro, D, per definire la finestra dell’insieme di lavoro(WS). L’idea è quella di esaminare i più recenti D riferimenti alle pagine determinando così un insieme di valori: 261577777716……………………………………………………3444343444……………………………… --------- @ T1 ------- @ T2

36

WS={1,2,5,6,7} WS={3,4}

Ad esempio data la successione di riferimenti alla ram mostrata qui sopra, se D = 10 riferimenti alla memoria, l’insieme di lavoro all’istante T1 è {1,2,5,6,7}, mentre all’istante T2 risulta essere {3,4}. Calcolando l’insieme WS per ogni processo del sistema, si può determinare la richiesta totale dei blocchi di memoria in un preciso istante.

S=∑ (WSi) Ogni processo usa attivamente le pagine del proprio insieme di lavoro. Quindi, il processo i necessita di WSi blocchi di memoria. Se la richiesta totale S è maggiore del numero totale di processi liberi, l’attività di paginazione degenera, poiché i processi non dispongono di un numero sufficiente di blocchi di memoria. FREQUENZA DELLE ASSENZE DI PAGINE Un altro buon algoritmo per l’assegnazione del numero delle pagine ai processi e basato sulla frequenza delle assenze di pagine. Il problema specifico è la prevenzione delle situazioni di paginazione degeneri. Se la frequenza delle assenze di pagine è eccessiva per un determinato processo, significa che il processo necessita di più blocchi di memoria. Analogamente, se la frequenza delle assenze di pagine e molto bassa, allora il processo potrebbe disporre di troppi blocchi di memoria. Si può fissare un limite inferiore e superiore per la frequenza desiderata di assenza di pagine, modificabili dal sistema. 10.7 ESEMPI TRA I SISTEMI OPERATIVI Windows NT Il sistema operativo Windows NT realizza la memoria virtuale impiegando la paginazione su richiesta per gruppi di pagine (clustering), ossia si carica in memoria non solo la pagina richiesta, ma anche le pagine adiacenti, sfruttando di fatto la proprietà che se è stata caricata una determinata pagina, vi sono molte probabilità che anche le pagine “vicine” dovranno essere utilizzate in futuro. Alla creazione di ogni processo, il sistema operativo assegna ad ogni processo, un valore minimo ed un valore massimo di insieme di lavoro: il minimo insieme di lavoro sono i frame assegnati sempre e comunque ad un processo. Se un processo adopera tutta la totalità dei suoi frame messi a disposizione dal sistema operativo (valore massimo dell’insieme di valoro), e incomincia a generare page fault, alla ricerca di pagine libere, il sistema operativo inizia a sostituire i frame in base all’algoritmo utilizzato, che varia da piattaforma a piattaforma. 10.8 ALTRE CONSIDERAZIONI In un sistema di paginazione, le decisioni più importanti riguardano l’algoritmo di sostituzione e il criterio di assegnazione. Si devono fare quindi molte altre considerazioni. - PREPAGINAZIONE: Una caratteristica ovvia per un sistema di paginazione su richiesta pura consiste nell’alto numero di assenze di pagine che si verificano all’avvio di un processo. Questa situazione è dovuta al tentativo di portare la località iniziale nella memoria.

37

La prepaginazione consiste nel tentativo di prevenire un livello così alto di paginazione iniziale. La strategia consiste nel portare nella ram in un’unica soluzione tutte le pagine richieste. - DIMENSIONE DELLE PAGINE - PORTATA DEL TLB: un parametro simile al tasso di successi è detto portata del TLB, che esprime la quantità di memoria accessibile dal TLB, ed è dato semplicemente dal numero di elementi del TLB moltiplicato per la dimensione delle pagine - TABELLA DELLE PAGINE INVERTITA - STRUTTURA DEI PROGRAMMI:La paginazione su richiesta deve essere trasparente per il programma utente; l’utente non è neanche a conoscenza della natura paginata della memoria. In altri casi, però le prestazioni del sistema si possono addirittura migliorare se l’utente è consapevole della sottostante presenza della paginazione su richiesta. Un’attenta scelta delle strutture di dati e delle strutture di programmazione può aumentare la località e quindi ridurre la frequenza delle assenze di pagine e il numero di pagine dell’insieme di lavoro. Anche la scelta del linguaggio di programmazione può influire sulla paginazione. Con il linguaggio C e C++, ad esempio, si fanno spesso uso di puntatori, che tendono a distribuire in modo casuale gli accessi in memoria, diminuendo di fatto la località di un processo. - VINCOLI DI I/O: quando si usa la paginazione su richiesta, talvolta occorre permettere che alcune pagine si possano vincolare (rendere disponibili) alla memoria. Una situazione di questo tipo si presenta quando l’I/O si esegue verso o dalla memoria d’utente. Occorre essere certi che non si verifichino la successione di due eventi: un processo emette una richiesta di I/O ed è messo in coda per il relativo dispositivo. Nel frattempo si assegna alla CPU dei processi, che utilizzando opportuni algoritmi di sostituzione vanno a modificare la parte di memoria assegnata in precedenza al dispositivo di I/O. Ciò come si può ben intuire porta alla nascita di numerosi violazioni di memoria. CAP 11: INTERFACCIA DEL FILE SYSTEM 11.1 CONCETTO DI FILE Un file è un insieme di informazioni, correlate e registrate nella memoria secondaria, cui è stato assegnato un nome. Dal punto di vista dell’utente, un file è la più piccola porzione di memoria secondaria logica. Di solito i file rappresentano i programmi, in forma sorgente e oggetto, e dati. In genere un file è formato da una sequenza di bit, byte, righe o record il cui significato è definito dal creatore e dall’utente del file stesso. ATTRIBUTI DEI FILE Per comodità degli utenti umani, ogni file ha un nome che si usa come riferimento. Un nome, di solito, è una sequenza di caratteri come esempio.c. Un file ha altri attributi che possono variare secondo il sistema operativo, ma che tipicamente comprendono i seguenti:

- nome - identificatore: è il nome impiegato dal sistema per il file,

generalmente un numero - tipo - locazione: puntatore al dispositivo e alla locazione del file

38

- dimensione - protezione: se il file si può leggere, scrivere o far eseguire - ora, data dell’ultimo accesso

le informazioni sui file sono conservate nella struttura di directory, che risiede a sua volta nella memoria secondaria. Di solito un elemento di directory consiste di un nome di file e di un identificatore unico, che a sua volta identifica gli altri attributi dei file. OPERAZIONI SUI FILE Un file è un tipo di file astratto. Per definire adeguatamente un file è necessario considerare le operazioni che si possono eseguire su di esso. Il sistema operativo può offrire chiamate di sistema per legger scrivere spostare un file.

- creazione di un file: articolata generalmente nella ricerca di uno spazio libero sul file system

- scrittura di un file - lettura di un file - riposizionamento di un file: si ricerca l’elemento appropriato

nella directory e si assegna un nuovo valore al puntatore alla posizione corrente nel file.

- Cancellazione - Troncamento di un file: quando si vuole cancellare il contenuto di

un file mantenendo però inalterati i suoi attributi. Queste sei operazioni di base comprendono sicuramente l’insieme minimo delle operazioni richieste per i file. La maggior parte delle operazioni richiede una ricerca dell’elemento associato al file specificato nella directory. Per evitare questa continua ricerca, molti sistemi operativi richiedono l’impiego di una chiamata di sistema open la prima volta che si adopera un file in maniera attiva. Il sistema operativo, così mantiene una piccola tabella contenete le informazioni riguardanti tutti i file aperti (detta tabella dei file aperti). Quando si richiede un’operazione su un file, questo viene individuato tramite un indice in tale tabella, in questo modo si evita qualsiasi ricerca. La realizzazione delle operazioni open e close in un ambiente multiutente, come lo UNIX, è più complicata poiché più utenti possono aprire un file completamente. Per tale motivo il sistema operativo introduce due livelli di tabelle interne: una tabella per ciascun processo e una tabella di sistema. La tabella di un processo contiene i riferimenti a tutti i file aperti da quel processo, mentre la tabella di sistema contiene informazioni indipendenti dal processo, come ad esempio la posizione di un file su disco rigido. Ciascun elemento della tabella di sistema è associato, uno o più elementi delle tabelle dei processi (se per esempio un file è usato da più processi). Tipicamente nella tabella di sistema è presente un contatore delle aperture associato a ciascun file; ciascuna chiamata di sistema close decrementa questo contatore, quanto esso ha come valore zero significa che nessun processo sta utilizzando quel file, e quindi esso può essere eliminato da tale tabella. Riassumendo, a ciascun file aperto sono associate diverse informazioni:

- puntatore al file - contatore dei file aperti - posizione nel disco del file

39

- diritti di accesso TIPI DI FILE Nella progettazione di un file system, si deve sempre considerare la possibilità o meno di riconoscere i diversi tipi di file. Una tecnica comune per la realizzazione dei tipi di file consiste nell’includere il tipo nel nome del file. Il nome è suddiviso in due parti, un nome e un’estensione, di solito separate da un punto; in questo modo sia l’utente che il sistema operativo possono risalire al tipo di file semplicemente esaminando il nome. Il sistema usa l’estensione per stabilire il tipo di file e le operazioni possibili su di esso. 11.2 METODI DI ACCESO Esistono molti modi per accedere alle informazioni dei file: alcuni sistemi consentono un solo metodo di accesso ai file, altri invece consentono diversi tipi di accesso. ACCESSO SEQUENZIALE Il più semplice metodo di acceso è l’accesso sequenziale: le informazioni del file si elaborano ordinatamente, un record dopo l’altro; questo metodo di accesso e di gran lunga il più comune, ed è usato, per esempio dagli editor e dai compilatori. L’acceso sequenziale è basato su un modello di file che si rifà al nastro. ACCESSO DIRETTO Un altro metodo è l’acceso diretto. Un file è formato da elementi logici di lunghezza fissa, ciò consente ai programmi di leggere e scrivere rapidamente tali elemento senza un ordine particolare. Il metodo ad acceso diretto si fonda su un modello che si rifà al disco: i dischi permettono, accesso diretto ad ogni blocco del file. Per il metodo ad acceso diretto, si devono modificare le operazioni sui file per inserire il numero del blocco in forma di parametro. Quindi, si hanno read n, dove n è il numero di blocco al posto di read next (dell’accesso sequenziale) e write n invece di write next. ALTRI MODI DI ACCESSO Sulla base di un metodo di accesso diretto se ne possono creare altri, che implicano generalmente la costruzione di un file indice per il file. L’indice contiene puntatori ai vari blocchi; per trovare un elemento del file occorre prima cercare nell’indice, e quindi usare il puntatore per accedere direttamente al file e trovare l’elemento desiderato. Tale tipologia di accesso permette di fare ricerche su file molto lunghi con pochissime operazioni di I/O. 11.3 STRUTTURA DI DIRECTORY Il file system di un calcolatore può essere molto ampio. Per gestire moltissimi dati è necessario che essi siano organizzati; di solito in una o più partizioni e volumi. Tipicamente ciascun disco contiene almeno una partizione, che è una struttura a basso libello nella quale risiedono file e directory. Una directory si può considerare come una tabella di simboli che traduce i nomi dei file negli elementi in essa contenuti. Da questo punto di vista, si capisce che la stessa directory si può organizzare in molti modi viversi: deve essere possibile inserire nuovi elementi, cancellarne

40

esistenti, cercare un elemento ed elencare tutti gli elementi della directory. L’insieme delle operazioni che si possono eseguire su una directory sono:

- ricerca di un file - creazione di un file - cancellazione di u file - elencazione della directory: ossia elencare tutti gli elementi

presenti nella directory - rinominare un file - attraversamento del file system

DIRECTORY A SINGOLO LIVELLO La struttura più semplice per una directory è quella a singolo livello. Tutti i file sono contenuti nella stessa directory, facilmente gestibile e comprensibile. Una directory a singolo livello presenta però limiti notevoli che si manifestano all’aumentare del numero di file in essa contenuti. DIRECTORY A DUE LIVELLI Nella struttura a due livelli ogni utente dispone della propria directory d’utente. Tutte le directory d’utente hanno una struttura simile, ma in ciascuna sono elencati solo i file del proprietario. Quando un utente fa un riferimento a un file particolare, il sistema operativo esegue la ricerca solo nella directory di quel utente. In questo modo utenti diversi possono avere file con lo stesso nome Specificando un nome di utente e un nome di file si definisce un percorso che parte dalla radice ( la directory principale ) e arriva a una specifica foglia ( il file specificato ). Quindi, un nome d’utente e un nome di file definiscono un nome di percorso (path name). Ogni file del sistema ha un nome del percorso. Per attribuire un nome unico a un file, un utente deve conoscere il nome di percorso del file desiderato. Ogni volta che si indica un file da caricare, il sistema operativo lo cerca innanzitutto nella directory d’utente locale, e, se lo trova lo usa; il sistema cerca automaticamente nella speciale directory d’utente che contiene i file di sistema. La sequenza delle directory in cui è stata fatta la ricerca avviata dal riferimento a un file è detta percorso di ricerca (search path). Tale idea si può estendere in modo che il percorso di ricerca contenga un elenco illimitato di directory. DIRECTORY CON STRUTTURA AD ALBERO Questa generalizzazione permette agli utenti di creare proprie sottodirectory e di organizzare i file di conseguenza. L’albero ha una directory radice, e ogni file del sistema ha un unico nome di percorso. Un nome di percorso descrive il percorso che parte dalla radice, passa attraverso tutte le sottodirectory e arriva a un file specifico. Tutte le directory hanno lo stesso formato intero. La distinzione tra file e directory e data da un bit, rispettivamente 0 e 1, di ogni elemento della directory. Normalmente, ogni utente dispone di una directory corrente. La directory corrente deve contenere la maggior parte dei file di interesse corrente. Per cambiare directory corrente si fa uso di una chiamata di sistema che preleva un nome di directory come parametro e lo usa per ridefinire la directory corrente. Quindi, l’utente può cambiare la propria directory corrente. Ogni volta che lo desidera. I nomi del percorso possono essere di due tipi: nomi di percorso assoluti e nomi di percorso relativi. Un nome di percorso assoluto comincia dalla radice dell’albero di una directory e segue un percorso che lo porta fin

41

al file specificato. Un nome di percorso relativo definisce un percorso che parte, invece dalla directory corrente. Una decisione importante relativa alla strutturazione ad albero riguarda la cancellazione di una directory. Alcuni sistemi, come l’MS DOS, non cancellano una directory a meno che non sia vuota; per cancellarla l’utente deve prima cancellare i file in essa contenuti. In alternativa, come nel comando rm dello UNIX, si può avere un’operazione che, alla richiesta di cancellazione di una directory, cancelli anche tutti i file e tutte le sottodirectory in essa contenuti. DIRECTORY CON STRUTTURA A GRAFO ACICLICO La struttura ad albero non ammette la condivisione di file o directory. Un grafo aciclico permette alle directory di avere sottodirectory e file condivisi. Lo stesso file o la stessa sottodirectory possono essere in due directory diverse. Il fatto che un file sia condiviso, o che una directory sia condivisa, non significa che ci siano due copie del file: con due copie ciascun programmatore potrebbe vedere la copia presente nella propria directory e non l’originale. Se invece il file è condiviso esiste un solo file effettivo, perciò tutte le modifiche sono immediatamente visibili. I file e le sottodirectory condivisi si possono realizzare in molti modi. Un metodo diffuso, prevede la creazione di un nuovo elemento di directory, chiamato collegamento. Un collegamento è un puntatore a un altro file o un’altra directory. Quando si fa riferimento a un file, si compie una ricerca nella directory, l’elemento cercato è contrassegnato come collegamento e riporta il nome di percorso del file, o della directory , reale. Un altro comune metodo per la realizzazione dei file condivisi prevede semplicemente la duplicazione di tutte le informazioni relative ai file in entrambe le directory di condivisione, quindi i due file sono identici. Duplicando gli elementi della directory la copia e l’originale sono resi indistinguibili. Un file può avere più nomi di percorso assoluti, quindi nomi diversi possono riferirsi allo stesso file (aliasing). Questa situazione è simile al problema dell’uso degli alias nei linguaggi di programmazione. Un altro problema riguarda la cancellazione, poiché è necessario stabilire in quali casi è possibile rassegnare e riutilizzare lo spazio assegnato a un file condiviso. Una possibilità prevede che ad ogni operazione di cancellazione segua l’immediata rimozione del file, quest’azione può però lasciare puntatori a un file che ormai non esiste più. Sarebbe ancora più grave se i puntatori contenessero gli indirizzi effettivi del disco e lo spazio fosse poi utilizzato per altri file, poiché i puntatori potrebbero puntare in mezzo a questi altri file. Nei moderni sistemi operativi, come windows XP quando si cancella un file, i collegamenti simbolici restano, è l’utente che deve rendersi conto che il file originale è scomparso o è stato sostituito. 11.4 MONTAGGIO DI UN FILE SYSTEM Così come si deve aprire un file per poterlo usare, per essere reso accessibile ai processi di un sistema, un file system deve esser montato. La procedura di montaggio è molto semplice: si fornisce al sistema operativo il nome del dispositivo e la sua locazione (detta punto di montaggio) nella struttura di file e directory alla quale agganciare il file system. Di solito, un punto di montaggio è una directory vuota cui sarà agganciato il file system che deve essere montato.

42

Il passo successivo consiste nella verifica da parte del sistema operativo della validità del file system contenuto nel dispositivo. Infine, il sistema annota nella sua struttura di directory che un certo file system è montato al punto di montaggio specificato. I sistemi operativi impongono una semantica a queste operazioni per rendere più chiare le loro funzioni. Ad esempio, un sistema potrebbe vietare il montaggio in una directory che contiene file, o rendere disponibile il file system montato in tale directory e nascondere i file preesistenti nella directory fino a quando non si smonta il file system. La famiglia dei sistemi operativi Windows mantiene una struttura di directory a due livelli estesa, con una lettera di unità associa a dispositivi e partizioni. Le partizioni hanno una struttura di directory a grafo generale associata a una lettera di unità. Il percorso completo per uno specifico file è quindi della forma lettera_di_unità:\percorso\file. Questi sistemi operativi automatico tutti i dispositivi ed eseguono il montaggio di tutti i file system rilevati in fase di caricamento. 11.5 PROTEZIONE La salvaguardia delle informazioni contenute in un sistema di calcolo e da accessi impropri è fondamentale. La protezione si può ottenere in molti modi. Per un piccolo sistema monoutente, la protezione si ottiene rimovendo fisicamente i dischetti e chiudendoli in un cassetto della scrivania. In un sistema multiutente sono necessari altri metodi. TIPI DI ACCESSO La necessità di proteggere i file deriva direttamente dalla possibilità di accedervi. Il controllo offerto dai meccanismi di protezione si ottiene limitando i possibili tipi di accesso. Si possono controllare diversi tipi di operazioni:

- lettura - scrittura - esecuzione - aggiunta - cancellazione - elencazione

CONTROLLO DEGLI ACCESSI Il problema di protezione comunemente si affronta rendendo l’acceso dipendente dall’identità dell’utente. Più utenti possono richiedere diversi tipi di accesso a un file o una directory. Lo schema più generale per realizzare gli accessi dipendenti dall’identità consiste nell’associare un elenco di controllo degli accessi (Access Control List), in tale elenco sono specificati i nomi degli utenti e i relativi tipi di accesso consentiti. Questo schema ha il vantaggio di permettere complessi metodi di accesso. Per condensare la lunghezza dell’elenco, molti sistemi raggruppano gli utenti di ogni file in tre classi distinte:

- proprietario: utente che ha creato il file - gruppo: o gruppo di lavoro, si tratta di un insieme di utenti che

condividono il file - universo: tutti gli altri utenti

per definire la protezione, data questa più limitata classificazione, occorrono solo tre campi. Ogni campo è formato di un insieme di bit. Nel sistema UNIX, ad esempio, sono definiti tre campi di tre bit ciascuno:

43

RWX, dove r controlla l’accesso per la lettura, w per la lettura e x per esecuzione. Un campo distinto è riservato al proprietario del file, al gruppo proprietario e a tutti gli altri utenti. CAP 12: REALIZZAZIONE DEL FILE SYSTEM 12.1 STRUTTURA DEL FILE SYSTEM IL FILE SYSTEM risiede permanentemente nella memoria secondaria, progettata per contenere in modo permanente grande quantità di dati. Per fornire un efficiente e conveniente accesso al disco, il s.o. fa uso di uno o più file system che consentono di memorizzare, individuare e recuperare facilmente i dati. Un file system è generalmente composto da molti livelli distinti. Ogni livello si serve delle funzioni dei livelli inferiori per creare nuove funzioni che sono impiegate dai livelli superiori. Il livello più basso, il controllo dell’I/O, costituito dei driver dei dispositivi, si occupa del trasferimento dell’informazione tra la memoria centrale e secondaria. Un driver di dispositivo si può pensare come un traduttore che riceve comandi ad alto livello, come ”recupera il blocco 123” ed emette specifiche istruzioni di basso livello per i dispositivi. Altro blocco è il file system di base che deve soltanto inviare dei generici comandi all’appropriato driver di dispositivo per leggere e scrivere i blocchi. Il modulo di organizzazione dei file è a conoscenza dei file e dei loro blocchi logici, può tradurre gli indirizzi dei blocchi logici, negli indirizzi di blocchi fisici. Tale blocco inoltre comprende anche il gestore dello spazio libero. Infine, il file system logico gestisce i metadati e gestisce i cosiddetti blocchi di controllo dei file(file control block)che contengono informazioni sui file. 12.2 REALIZZAZIONE DEL FILE SYSTEM Per realizzare un file system si usano parecchie strutture dati, per esempio nei dischi il file system tiene informazioni su come eseguire l’avviamento di un s.o. memorizzato nei dischi stessi, e il numero totale dei blocchi. Fra le strutture presenti nei dischi ci sono le seguenti:

- il blocco di controllo dell’avviamento, che contiene informazioni dell’avviamento del s.o. da quella partizione; se il disco non contiene un s.o. tale blocco è vuoto

- I blocchi di controllo delle partizioni; ciascuno di essi contiene i dettagli riguardanti la relativa partizione

- Le strutture di directory che si usa per organizzare i file - I descrittori dei file (FCB)

Le informazioni tenute nella memoria sono: - la tabella delle partizioni contenenti informazioni su ciascuna

partizione da montare - la tabella dei file aperti - la tabella dei file aperti per ciascun processo.

Un’applicazione, per creare un nuovo file, fa una chiamata al file system logico, che conosce le strutture di directory, e assegna un nuovo descrittore di file, carica nella memoria la directory appropriata, l’aggiorna con il nuovo nome di file e il relativo descrittore che la descrive nella memoria secondaria. Una volta che un file è stato creato, deve essere aperto. La chiamata del sistema OPEN passa un nome di file ad un file system affinché lo ricerchi. Una volta che il file è stato

44

trovato, si copia il suo descrittore di file nella tabella dei file aperti tenuta in memoria. Successivamente si crea un elemento nella tabella dei file aperti del processo, con un puntatore alla tabella generale dei file aperti. Quando il processo chiude il file, si cancella il relativo elemento nella tabella dei file aperti di un processo e si decrementa il contatore della tabella generale. Se tutti i processi che avevano aperto il file lo hanno chiuso, si riscrive l’informazione aggiornata sul file nei dischi e si cancella il relativo elemento nella tabella generale dei file aperti. FILE SYSTEM VIRTUALI I file system virtuali (VFS) rappresentano un approccio object oriented nell’implementazione di un file system, il VFS permette che un unico interfaccia di chiamate di sistema (API) possa essere usato per pilotare file system diversi. Con tale approccio la realizzazione del file system si articola in tre strati principali: - Interfaccia del file system (read, open, write , close, descrittori) - Interfaccia del VFS - I file system locali o remoti 12.3 REALIZZAZIONI DELLE DIRECTORY LISTA LINEARE Il più semplice metodo di realizzazione di una directory è basato sull’uso di una lista lineare contenente nomi dei file con puntatori ai blocchi dei dati. L’individuazione di un elemento particolare in una lista richiede una ricerca lineare. Questo metodo è di facile programmazione ma la sua esecuzione è onerosa in termini di tempo. Il vero svantaggio dato da una lista lineare è dato dalla ricerca lineare di un file. TABELLA HASH Un’altra struttura di dati per realizzare le directory è la tabella hash. In questo metodo una lista lineare contiene gli elementi di directory. La tabella hash riceve un valore, calcolato attraverso un apposito algoritmo che accetta come parametro il nome del file, e riporta un puntatore al nome del file nella lista lineare. Le maggiori difficoltà legate alla tabella hash sono la sua dimensione e la dipendenza della funzione hash da tale dimensione. 12.4 METODI DI ASSEGNAZIONE Esistono 3 modi principali per l’assegnazione dello spazio di un disco; può essere infatti contigua, incatenata o indicizzata. Ciascuno di questi metodi presenta vantaggi e svantaggi. ASSEGNAZIONE CONTIGUA Per usare il metodo di assegnazione contigua, ogni file deve occupare un insieme di blocchi contigui del disco. Gli indirizzi del disco definiscono un ordinamento lineare del disco stesso. Con questo ordinamento l’accesso, non richiede normalmente alcuno spostamento della testina. L’assegnazione contigua dello spazio per un file è definita dall’indirizzo del primo blocco e dalla lunghezza. L’assegnazione contigua presenta però alcuni problemi; una difficoltà riguarda l’individuazione dello spazio per un nuovo file; il problema generale è

45

quello di soddisfare una richiesta di dimensione N data una lista di buchi liberi. I più comuni criteri di scelta di un buco libero da un’insieme di buchi disponibili sono quelli del primo buco abbastanza grande (first fit) e del più piccolo dei buchi abbastanza grandi (best fit). Simulazioni hanno dimostrato che questi due criteri sono più efficienti di quello di scelta del buco più grande (worst fit). Questi algoritmi però soffrono della frammentazione esterna, ossia lo spazio libero dei dischi viene frammentato in tanti piccoli pezzi. Un altro problema che riguarda l’assegnazione contigua è la determinazione della quantità di spazio necessaria per un file. Esiste il problema di conoscere la dimensione del file da creare; in alcuni casi questa dimensione si può stabilire abbastanza facilmente, in altri casi ciò risulta più complicato. Molti s.o. utilizzano uno schema di assegnazione contigua modificata: inizialmente si assegna una porzione di spazio contiguo, e se questa non è abbastanza grande si aggiunge un’altra porzione di spazio, un estensione. La frammentazione interna può ancora essere un problema se le estensioni sono troppo grandi. ASSEGNAZIONE CONCATENATA Nell’ assegnazione concatenata ogni file è composto da una lista concatenata di blocchi del disco i quali possono essere sparsi in qualsiasi punto del disco stesso. La directory contiene un puntatore al primo e all’ultimo blocco del file, ogni blocco contiene un puntatore al blocco successivo. All’assegnazione concatenata presenta però alcuni svantaggi, il problema principale riguarda il fatto che può essere usata in modo efficiente solo per i file ad accesso sequenziale. Per trovare l’i-esimo blocco di un file occorre partire dall’inizio del file e seguire i puntatori finché non si raggiunge i-esimo richiesto. Un altro problema riguarda l’affidabilità. Poiché i file sono tenuti insieme da puntatori di spazi per tutto il disco, problemi enormi si avrebbero se un puntatore andasse perso o danneggiato. Una variante importante del metodo di assegnazione incatenata consiste nell’uso della tabella di assegnazione di file (FAT). Tale metodo di assegnazione dello spazio è usato nei s.o. MICROSOFT. Si usa essenzialmente una lista concatenata, l’elemento di directory contiene il numero del primo blocco del file. Lo schema di assegnazione basato sulla FAT, può causare un significativo numero di posizionamenti sulla testina. ASSEGNAZIONE INDICIZZATA L’assegnazione concatenata non è in grado di sostenere un efficiente sistema diretto, poiché i puntatori ai blocchi sono sparsi. L’assegnazione indicizzata risolve questo problema, raggruppando tutti i puntatori in una sola locazione: il blocco indice. Ogni file ha il proprio blocco indice: si tratta di un vettore di indirizzi di blocchi del disco. L’i-esimo elemento del blocco indice punta all’i-esimo blocco del file. La directory contiene l’indirizzo del blocco indice. Lo spazio aggiuntivo richiesto ai puntatori del blocco indice è generalmente maggiore dello spazio aggiunto necessario per l’assegnazione concatenata. Un inconveniente nell’assegnazione indicizzata riguarda la dimensione del blocco indice; se infatti il blocco indice è troppo piccolo non si può contenere un numero di puntatori sufficiente per un file di grandi dimensioni. Esistono per tale motivo 3 meccanismi per gestire questa situazione:

- schema concatenato: per permettere la presenza di lunghi file è possibile collegare tra loro parecchi blocchi indice, in questo modo l’ultima parola di un blocco indice potrebbe essere un puntatore ad un altro blocco indice.

46

- Indice a più livelli: una variante della rappresentazione concatenata consiste nell’impiego di un blocco indice di primo livello che punta ad un insieme di blocchi indice di secondo livello che, a loro volta puntano ai blocchi dei file.

- Schema combinato: un’altra possibilità è la soluzione adottata nell’UFS. Consiste nel tenere i primi 15 puntatori del blocco nell’ inode del file. I primi 12 puntano a blocchi diretti, cioè contengono gli indirizzi di blocchi che contengono dati del file. Se la dimensione dei blocchi è 4 Kb, è possibile accedere direttamente fino a 48 Kb dei dati. Gli altri 3 puntatori puntano a blocchi indiretti. Il primo puntatore di blocco indiretto è l’indirizzo di un blocco indiretto singolo; quindi c’è un puntatore di blocco indiretto doppio che contiene l’indirizzo di un blocco che a sua volta contiene gli indirizzi di blocchi contenenti puntatori agli effettivi blocchi. L’ultimo puntatore contiene l’indirizzo di un blocco indiretto triplo.

12.5 GESTIONE DELLO SPAZIO LIBERO Poiché la quantità di spazio dei dischi è limitata, è necessario riutilizzare lo spazio lasciato dai cancellati per scrivere, se possibile, nuovi file. Per tenere traccia dello spazio libero in un disco, il sistema conserva un elenco di blocchi liberi; vi sono registrati tutti i blocchi liberi, cioè non assegnati ad alcun file e directory. VETTORE DI BIT Spesso l’elenco dei blocchi liberi si realizza come una mappa di bit, o vettore di bit. Ogni blocco è rappresentato da un bit; se il blocco è libero è 1, altrimenti vale 0. I vantaggi principali che derivano da questo metodo sono la sua relativa semplicità ed efficienza nel trovare il primo blocco libero o n blocchi liberi consecutivi nel disco. Sfortunatamente, i vettori di bit sono efficienti solo se tutto il vettore è mantenuto nella memoria centrale e viene di tanto in tanto scritto nella memoria secondaria allo scopo di consentire eventuali operazioni di ripristino. LISTA CONCATENATA Un altro metodo di gestione dei blocchi liberi consiste nel collegare tutti i blocchi liberi, tenere un puntatore al primo di questi in una speciale locazione del disco e caricarlo nella memoria. Questo primo blocco contiene un puntatore al successivo blocco libero, e così via. Questo schema non è comunque efficiente: per attraversare la lista occorre leggere ogni blocco, e l’operazione richiede un notevole tempo di I/O. RAGGRUPPAMENTO Una possibile modifica del metodo dell’elenco dei blocchi liberi prevede la memorizzazione degli indirizzi di n blocchi liberi nel primo di questi. I primi n-1 di questi blocchi sono effettivamente liberi; l’ultimo blocco contiene gli indirizzi di altri n blocchi liberi, e così via. CONTEGGIO Un altro orientamento sfrutta il fatto che, generalmente, più blocchi contigui si possono assegnare o liberare contemporaneamente.

47

Quindi anziché tenere un elenco di n indirizzi liberi, è sufficiente tenere l’indirizzo del primo blocco libero e il numero di n blocchi liberi contigui che seguono il primo blocco. 12.6 EFFICIENZA E PRESTAZIONI In questo paragrafo si considerano diverse tecniche utili per migliorare l’efficienza e le prestazioni della memoria secondaria. L’uso efficiente di un disco dipende fortemente dagli algoritmi usati per l’assegnazione del disco e la gestione delle directory. Dopo aver scelto gli algoritmi fondamentali del file system si possono migliorare le prestazioni in diversi modi. Alcuni controllori di unità a disco contengono una quantità di memoria locale sufficiente per la creazione di una cache interna al controllore che può essere sufficientemente grande per memorizzare un’intera traccia del disco alla volta. Alcuni sistemi riservano una sezione separata della memoria centrale come cache del disco, dove tenere i blocchi in previsione di un loro riutilizzo entro breve tempo. Altri sistemi impiegano una cache delle pagine per i file; si tratta di una soluzione che impiega tecniche di memoria virtuale per la gestione dei dati dei file come pagine anziché come blocchi di file system. Diversi sistemi, usano le cache delle pagine sia per le pagine relative ai processi sia per i dati dei file. questo metodo è noto come memoria virtuale unificata. Alcune versioni dello UNIX prevedono la cosiddetta buffer cache unificata, sia per le normali funzioni di I/O sui file, sia per le ordinarie chiamate del sistema read e write. In questo caso, le chiamate del sistema read e write passano attraverso la buffer cache. La chiamata con l’associazione alla memoria ( ossia un file viene gestito con la paginazione ) richiede l’uso di due cache, la cache delle pagine e la buffer cache. L’associazione alla memoria prevede la lettura dei blocchi di disco dal file system e la loro memorizzazione nella buffer cache. Poiché il sistema di memoria virtuale non può interfacciarsi con la buffer cache, si deve copiare nella cache delle pagine il contenuto del file presente nella buffer cache. Alcuni sistemi ottimizzano la cache delle pagine adottando, secondo il tipo d’accesso ai file, differenti algoritmi di sostituzione. Gli accessi sequenziali si potrebbero ottimizzare con tecniche note come rilascio indietro e lettura anticipata. Il rilascio indietro rimuove una pagina dalla memoria di transito non appena si verifica una richiesta della pagina successiva; le pagine precedenti con tutta probabilità non saranno più usate e quindi sprecano spazio nella memoria di transito. Con la lettura anticipata si leggono e si mettono nella cache la pagina richiesta e parecchie pagine successive: è probabile che queste pagine siano richieste una volta terminata l’elaborazione della pagina corrente. Nei PC si adotta comunemente un’altra tecnica per migliorare le prestazioni. Si riserva e si gestisce una sezione della memoria come un disco virtuale o disco ram; in questo caso il driver di un disco RAM accetta tutte le operazioni ordinarie dei dischi, eseguendole però in questa sezione della memoria invece che su disco. La differenza tra un disco RAM e la cache di un disco è che il contento del primo è totalmente controllato dall’utente, mentre quello della cache è sotto il controllo del sistema operativo. CAP 14: MEMORIA SECONDARIA E TERZIARIA 14.1 STRUTTURA DEI DISCHI

48

I dischi sono il principale mezzo di memorizzazione secondaria nei moderni sistemi di calcolo. I nastri magnetici avevano in passato questo ruolo, ma il loro tempo di accesso è molto maggiore di quello dei dischi. Dal punto di vista dell’indirizzamento, i moderni dischi si considerano come un grande vettore monodimensionale di blocchi logici, dove un blocco logico è la minima unità di trasferimento. La dimensione di un blocco è di solito 512 byte, sebbene alcuni dischi si possano formattare a basso livello allo scopo di ottenere una diversa dimensione dei blocchi logici. Il vettore monodimensionale di blocchi logici corrisponde in modo sequenziale ai settori del disco: il settore 0 è il primo settore della prima traccia sul cilindro più esterno; la corrispondenza prosegue ordinatamente lungo la prima traccia, quindi lungo le rimanenti tracce del primo cilindro, e così via di cilindro in cilindro, dall’esterno verso l’interno. SCHEDULING DEL DISCO Una delle responsabilità del sistema operativo è quella di fare un uso efficiente delle risorse fisiche: nel caso delle unità disco, far fronte a queste responsabilità significa garantire tempi di accesso contenuti. Tali tempi si possono scindere in due componenti principali; il tempo di ricerca, cioè il tempo affinché la testina non raggiunga il settore desiderato, e la latenza di rotazione, e cioè il tempo aggiunto necessario perché il disco ruoti finché il settore desiderato si trova sotto la testina. Ogni qualvolta che deve compiere operazioni di I/O con un’unità a disco, un processo impartisce una chiamata di sistema al sistema operativo. La richiesta contiene diverse informazioni:

- tipo di operazione: scrittura lettura - l’indirizzo nel disco da dove iniziare il trasferimento - l’indirizzo della memoria al quale eseguire il trasferimento - il numero di byte da trasferire

SCHEDULING IN ORDINE DI ARRIVO La forma più semplice di scheduling è, naturalmente l’algoritmo di servizio secondo l’ordine di arrivo. Si tratta di un algoritmo intrinsecamente equo, ma che in generale non garantisce la massima velocità del servizio. SCHEDULING PER BREVITA’ Sembra ragionevole servire tutte le richieste vicine alla posizione corrente della testina prima si spostarla in un’altra area lontana per soddisfare altre: questa considerazione è alla base dell’algoritmo di servizio secondo il più breve tempo di ricerca. Esso sceglie la richiesta che dà il minimo tempo di ricerca rispetto alla posizione corrente della testina; poiché questo tempo cresce al crescere della distanza dei cilindri dalla testina, l’algoritmo sceglie le richieste relative ai cilindri più vicini alla posizione della testina. Tale tipo di scheduling è essenzialmente una forma di scheduling per brevità. E al pari di questo, può condurre a situazioni d’attesa indefinita di alcune richieste. SCHEDULING PER SCANSIONE SCAN Secondo l’algoritmo scan il braccio dell’unità a disco parte da un’estremo del disco e si sposta nella sola direzione possibile, servendo le richieste mentre attraversa i cilindri fino a che non raggiunge l’altro estremo del disc: a questo punto, il braccio inverte la marcia e la procedura continua.

49

SCHEDULING PER SCANSIONE CIRCOLARE C-SCAN L’algoritmo scan circolare è una versione dello scheduling SCAN concepita per garantire un tempo di attesa meno variabile. Anche l’algoritmo C-SCAN, sposta la testina da un estremo all’altro del disco, servendo le richieste lungo il percorso; tuttavia, quando la testina giunge all’altro estremo del disco, ritorna immediatamente all’inizio del disco stesso, senza servire altre richieste durante il viaggio di ritorno. SCHEDULING LOOK Secondo la descrizione appena fatta, sia l’algoritmo SCAN sia il C-SCAN spostano il braccio dell’unità attraverso tutta l’ampiezza del disco: all’atto pratico, il braccio si sposta solo finché ci sono altre richieste da servire in quella direzione, dopo di che cambia immediatamente direzione. Queste versioni dello SCAN e del C-SCAN sono dette LOOK e C-LOOK perché guardano se ci sono altre richieste in quella direzione. 14.3 GESTIONE DELL’UNITA’ A DISCO FORMATTAZIONE DEL DISCO Un disco magnetico nuovo è tabula rasa: un insieme di uno o più piatti sovrapposti ricoperti di materiale magnetico; prima che possa memorizzare dati, deve essere diviso in settori che possano essere letti o scritti dal controllore. Questo processo si chiama formattazione di basso livello, o formattazione fisica. La formattazione di basso livello riempie il disco con una speciale struttura di dati per ogni settore, tipicamente consistente di un’intestazione, un’area per i dati e una coda. L’intestazione e la coda contengono informazioni usate dal controllore del disco, ad esempio il numero del settore e un codice per la correzione degli errori (ECC). La formattazione fisica dei dischi è seguita nella maggior parte dei casi dal costruttore come parte del processo produttivo; ciò permette al costruttore di provare il disco, e di instaurare la corrispondenza fra blocchi logici e settori correttamente funzionanti del disco. Per usare un disco come contenitore di informazioni, il sistema operativo deve ancora registrare le proprie strutture dati nel disco, cosa che fa in due passi. Il primo consiste nel suddividere il disco in uno o più gruppi di cilindri, detti partizioni, il secondo la suddivisione delle partizioni con la formattazione logica, cioè la creazione di un file system. BLOCCO D’AVVIAMENO Affinché un calcolatore possa entrare in funzione, è necessario che esegua un programma iniziale; di solito, questo programma d’avviamento iniziale è piuttosto semplice. Per la maggior parte dei calcolatori, il programma d’avviamento è memorizzato in una memoria a sola lettura, il che è conveniente perché la ROM non richiede inizializzazione, e ha un indirizzo iniziale fisso dal quale la CPU può cominciare l’esecuzione ogniqualvolta si accende o si riavvia la macchina. Il programma di avviamento completo è registrato in una partizione del disco denominata blocchi di avviamento, posta in una locazione fissa del disco; un disco contenente una tale partizione si chiama disco d’avviamento o disco di sistema. Il codice contenuto nella ROM d’avviamento istruisce innanzi tutto il controllore del disco affinché trasferisca il contenuto dei blocchi d’avviamento nella memoria, quindi comincia a eseguire il codice.

50

BLOCCHI DIFETTOSI Le unità a disco sono strutturalmente portate ai malfunzionamento perché sono costituite da parti mobili a bassa tolleranza; in effetti, la maggior parte dei dischi messi in commercio contiene già blocchi difettosi. Essi sono trattati in diversi modi secondo il controllore e l’unità a disco presenti nel sistema. Nel caso dei dischi semplici, gestiti dal controllo IDE i blocchi difettosi vengono gestiti manualmente. Ad esempio, il comando format dell’MS DOS esegue una formattazione logica, e come parte del processo esamina il disco per rilevare la presenza di blocchi difettosi: se ne trova qualcuno, scrive un valore speciale nel corrispondente elemento della FAT al fine di segnalare alle procedure di assegnazione di non usare il blocco in questione. Unità a disco più complesse (per esempio i dischi SCSI), hanno strategie di recupero dei blocchi difettosi più raffinate. La formattazione fisica mette da parte dei settori di riserva non visibili al sistema operativo, in modo tale che se il controllore trova un blocco difettoso, esso sarà rimpiazzato da uno conservato come scorta. Questa strategia è nota come accantonamento di settori. Un alternativa all’accantonamento dei settori è data da quei controllori capaci di sostituire i settori difettosi tramite la tecnica della traslazione dei settori, ossia traslato tutti i settori di una posizione baypassando quindi quello danneggiato. 14.4 GESTIONE DELL’AREA DI AVVICENDAMENTO La gestione dell’area di avvicendamento è un altro compito di basso livello del sistema operativo. L’area di avvicendamento è usata in modi diversi da sistemi operativi diversi. I sistemi che adottano l’avvicendamento dei processi, possono usare l’area d’avvicendamento per mantenere l’intera immagine del processo, inclusi i segmenti dei dati e del codice; i sistemi a paginazione, invece, possono semplicemente memorizzarvi pagine contenute nella memoria centrale. COLLOCAZIONE DELL’AREA DI AVVICENDAMENTO Ci sono due possibili collocazioni per un’area d’avvicendamento: all’interno del normale file system, o in una partizione del disco a sé stante. Se l’area d’avvicendamento è semplicemente un grande file all’interno del file system, si possono usare le ordinarie funzioni del file system per crearla, assegnargli un nome, e assegnare spazio per essa. In alternativa, l’area d’avvicendamento si può creare in una partizione del disco distinta: in essa non è presente alcuna struttura relativa al file system e alle directory, ma si usa uno speciale gestore dell’area d’avvicendamento per assegnare e rimuovere i blocchi. GESTIONE DELL’AREA DI AVVICENDAMENTO: UNIX Nei sistemi operativi UNIX si assegna l’area di avvicendamento a un processo quando esso è avviato: si riserva spazio sufficiente per il segmento testo , dove è contenuto il programma, e per il segmento dati. Questa forma di assegnazione preventiva in genere impedisce che il processo esaurisca il suo spazio di avvicendamento durante l’esecuzione. Quando comincia l’esecuzione di un processo, si carica il suo testo nella memoria prelevandolo dal file system, in questo modo, si consulta il file system una sola volta per ciascuna pagina di testo. La mappa di avvicendamento dei dati è più complicata, perché il segmento dei dati può crescere nel tempo. La dimensione della mappa è fissa, ma contiene indirizzi relativi a blocchi dell’area d’avvicendamento di dimensione

51

variabile. Per ogni indice i il blocco puntato dall’i-esimo della mappa è 2ix16Kb, fino a un massimo di 2Mb. 14.4 STRUTTURE RAID L’evoluzione tecnologica ha reso le unità a disco progressivamente più piccole e meno costose. La presenza di più dischi, qualora si possano usare in parallelo, rende possibile l’aumento della frequenza alla quale i dati si possono leggere o scrivere. Inoltre, una configurazione di questo tipo permette di migliorare l’affidabilità. Ci sono varie tecniche, note col nome comune di batterie ridondanti di dischi (RAID), che hanno lo scopo di affrontare i problemi di affidabilità e di prestazioni. MIGLIORAMENTO DELL’AFFIDABILITA’ TRAMITE RIDONDANZA La soluzione del problema dell’affidabilità sta nell’introdurre una certa ridondanza, cioè nel memorizzare informazioni che non sono necessarie. Il metodo più semplice, ma anche più costoso, di introduzione di ridondanza è quello della copia speculare; ogni disco logico consiste di due dischi fisici e ogni scrittura si effettua su entrambi i dischi. Se uno dei dischi si guasta, i dati si possono leggere dall’altro. I dati si perdono solo se il secondo disco si guasta prima della sostituzione del disco guasto. MIGLIORAMENTO DELLE PRESTAZIONI TRAMITE IL PARALLELISMO L’accesso in parallelo a più dischi può portare a vari vantaggi. Con la copiatura speculare dei dischi, la frequenza con la quale si possono gestire le richieste di lettura raddoppia, poiché ciascuna richiesta si può inviare indifferentemente a uno dei due dischi. Attraverso l’uso di più dischi è possibile anche migliorare la capacità di trasferimento distribuendo i dati in sezioni di dischi. Nella sua forma più semplice questa distribuzione, chiamata sezionamento dei dati, consiste nel distribuire i bit di ciascun byte su più dischi; in questo caso si parla di sezionamento a livello di bit. LIVELLI RAID La tecnica di copiatura speculare offre un’alta affidabilità ma è costosa, per tali motivi sono stati proposti numerosi schemi per fornire ridondanza usando l’idea del sezionamento combinata con i bit di parità. Questi schemi realizzano diversi compromessi tra costi e prestazioni e sono stati classificati in livelli chiamati RAID:

- Livello 0: si riferisce a batterie di dischi con sezionamento a livello di blocchi, ma senza ridondanza

- Livello 1: si riferisce alla tecnica della copiatura speculare - Livello 2: tale livello è anche noto come organizzazione con codici

per la correzione degli errori. Da molto tempo i sistemi di memorizzazione impiegano tecniche di riconoscimento degli errori basate sui bit di parità. Gli schemi di correzione degli errori memorizzano due o più bit supplementari e possono ricostruire i dati nel caso di un singolo bit danneggiato. La stessa idea alla base dell’ECC si può usare immediatamente nelle batterie di dischi eseguendo il sezionamento dei byte presenti nei dischi

- Livello 0+1: tale livello consiste in una combinazione dei livelli RAID 0 e 1. il livello 0 fornisce le prestazioni, mentre il livello 1 l’affidabilità

52

CAP 7: SINCRONIZZAZIONE DEI PROCESSI 7.1 INTRODUZIONE Un processo cooperante è un processo che può influenzare un altro processo in esecuzione nel sistema o anche subirne l’influenza. I processi cooperanti possono condividere uno spazio logico di indirizzi oppure possono condividere dati soltanto attraverso i file. La soluzione del problema per due soli processi, con memoria limitata, consente la presenza contemporanea nel vettore di DIM_VETTORE-1 elementi. Una possibilità consiste nell’aggiungere una variabile intera, contatore, che si incrementa ognivalvolta si inserisce un nuovo elemento e si decrementa quando esso viene prelevato. Il codice per il processo produttore è il seguente: /* produce un elemento in appena_prodotto */ ... while (contatore == DIM_VETTORE); /* non fa niente */ vettore[inserisci] = appena_prodotto; inserisci = (inserisci + 1) % DIM_VETTORE ; contatore++ ; ... E per il processo consumatore: ... while (contatore == 0); /* non fa niente: nessun dato prodotto */ da_consumare = vettore[preleva] ; preleva = (preleva + 1) % DIM_VETTORE ; contatore-- ; ... /* consuma un elemento in da_consumare */ Sebbene siano corrette se si considerano separatamente, le procedure del produttore e del consumatore possono non funzionare altrettanto correttamente se si eseguono in modo concorrente. Si può dimostrare che il valore di contatore può essere scorretto: produttore: registro1 = registro1 + 1 (registro1 = 6) consumatore: registro2 = contatore (registro2 = 5) consumatore: registro2 = registro2 – 1 (registro2 = 4) produttore: contatore = registro1 (contatore = 6) consumatore: contatore = registro2 (contatore = 4) Il valore di contatore alla fine sarà 4, invece di 5. Per evitare le situazioni di questo tipo, occorre assicurare che un solo processo alla volta possa modificare la variabile contatore. 7.2 PROBLEMA DELLA SEZIONE CRITICA Si consideri un sistema composto di n processi; ciascun avente un segmento di codice, chiamato sezione critica, nel quale il processo può modificare variabili comuni, aggiornare una tabella, scrivere un file e così via. Il problema della sezione critica si affronta progettando un protocollo che i processi possano usare per cooperare. Ogni processo deve chiedere il permesso per entrare nella propria sezione critica. La sezione di codice che realizza questa richiesta è la sezione di ingresso. La sezione

53

critica può essere seguita da una sezione di uscita, e la restante parte del codice e detta sezione non critica. Una soluzione al problema della sezione critica deve soddisfare i tre seguenti requisiti:

- mutua esclusione: se il proceso P è in esecuzione, nessun altro processo può essere in esecuzione in contemporanea

- progresso: se nessun altro processo è in esecuzione nella sua sezione critica, e qualche processo desidera entrare nella sezione critica, deve poterlo fare

- attesa limitata: se un processo ha già richiesto l’ingresso nella sua sezione critica, esiste un limite al numero di volte che si consente al altri processi di entrare nelle rispettive sezioni critiche

SOLUZIONE PER DUE PROCESSI ALGORITMO 1 Il primo tentativo di soluzione consiste nel far condividere ai processi una variabile intera turno. Se turno==i si permette al processo Pi si permette di entrare nella propria sezione critica: ... while (turno != i); /* finché non è il turno di Pi non fa niente */ <sezione critica> turno = j; /* abilita il turno dell’altro processo */ ... ALGORITMO 2 L’algoritmo 1 non possiede informazioni sufficienti sullo stato di ogni processo; ricorda solo il processo cui si permette l’ingresso nella sezione critica. Per rimediare a questo problema si può sostituire la variabile turno con il seguente vettore:

boolean pronto[2]; gli elementi del vettore si inizializzano a false. Se il valore di pronto[i], significa che Pi è pronto ad entrare nella sua regione critica. ... pronto[i] = true;/* dico Pi è pronto per entrare nella sezione critica */ while (pronto[j]);<sezione critica>

/* fa nulla se un altro processo è in sez. critica */

pronto[i] = false; <sezione non critica> ... Tale meccanismo assicura la mutua esclusione ma non il progresso. ALGORITMO 3 Combinando i concetti chiave dell’algoritmo 1 e dell’algoritmo 2 si può ottenere una soluzione corretta del problema della sezione critica: ... pronto[i] = true; turno = j; while (pronto[j] &<sezione critica>

& turno == j);

pronto[i] = false; <sezione non critica> ... SOLUZIONE PER PIU’ PROCESSI

54

In questo paragrafo si descrive un algoritmo che ha lo scopo di risolvere il problema della sezione critica per n processi. Tale algoritmo, noto come algoritmo del fornaio, è basato su uno schema di servizio comunemente usato nelle panetterie. Al suo ingresso nel negozio, ogni cliente riceve un numero; si serve, progressivamente, il cliente con il numero più basso. Le strutture dati comuni sono:

boolean scelta[n] int numero[n]

ecco una possibile implementazione: ... scelta[i] = true; numero[i] = max(numero[0], numero[1], …, numero [n – 1])+1; scelta[i] = false; for (j = 0; j < n; j++){ while (scelta[j]) ; while ((numero[j] != 0) && (numero[j,j] < numero[i,i])) ; } <sezione critica> numero[i] = 0; <sezione non critica> ... 7.3 ARCHITETTURE DI SINCRONIZZAZIONE In questo paragrafo si descrivono alcune semplici istruzioni, disponibili in molte altre unità d’elaborazione, e si dimostra come si possono impiegare efficacemente per risolvere il problema della sezione critica. In un sistema dotato di singola CPU tale problema si potrebbe risolvere semplicemente se si potessero interdire le istruzioni mentre si modificano le variabili condivise. Sfortunatamente questa soluzione non è sempre praticabile; la disabilitazione delle interruzioni nei sistemi a partizione del tempo può comportare sprechi di tempo. Per questo motivo molte architetture offrono particolari istruzioni che permettono di controllare il contenuto di una parola di memoria, oppure di scambiare il contenuto di due parole di memoria, in modo atomico. Se si dispone dell’istruzione TestAndSet, si può realizzare la mutua esclusione, dichiarando una variabile booleana globale blocco, inizializzata a false. L’istruzione Swap, agisce sul contenuto di due parole di memoria; come l’istruzione TestAndSet, è anch’essa eseguita in modo atomico. Definizione TestAndSet: boolean TestAndSet(boolean &obiettivo) { boolean valore = obiettivo; obiettivo = true; return valore; } Ecco come si realizza la mutua esclusione: ... /*la variabile blocco inizializzata con il valore false*/ while (TestAndSet(<sezione critica>

blocco));

55

blocco = false; <sezione non critica> Definizione swap: void Swap(boolean &a, boolean &b) { boolean temp = a; a = b; b = temp; } E con swap: /* la variabile blocco inizializzata con il valore false */ chiave = true; while (chiave = true) Swap(blocco,chiave); <sezione critica> blocco = false; <sezione non critica> Per dimostrare che l’algoritmo soddisfa il requisito di mutua esclusione, si considera che il processo Pi può entrare nella propria sezione critica solo se attesa[i]==false oppure chiave==false. Il valore di chiave può diventare false solo se si esegue TestAndSet. Il primo processo che esegue TestAndSet trova chiave==false; tutti gli altri devono attendere. La variabile attesa[i] può diventare false solo se un altro processo esce dalla propria sezione critica; solo una variabile attesa[i] vale false, il che consente di rispettare il requisito di mutua esclusione. attesa[i] = true chiave = true; while (attesa[i] && chiave) chiave = TestAndSet(blocco); attesa[i] = false <sezione critica> j = (i + 1) % n; while (( j != i ) && !attesa[i]) j = (i + 1) % n; if (j == i) blocco = false; else attesa[j] = false; <sezione non critica> 7.4 SEMAFORI Un semaforo S è una variabile intera cui si può accedere, escludendo l’inizializzazione, solo tramite due operazioni atomiche predefinite: wait e signal. La definizione classica di wait in pseudocodice è la seguente: wait(S){ while(S <= 0); /*non fa nulla: rimane a ciclare qui dentro…*/ S--; }

56

La definizione classica di signal in pseudocodice è la seguente: signal(S){ S++; } USO DEI SEMAFORI I semafori si possono usare per risolvere il problema della sezione critica con n processi. Gli n processi condividono un semaforo comune, mutex, inizializzato a 1. ogni processo e strutturato come segue: wait(mutex); <sezione critica> signal(mutex); <sezione non critica> I semafori si possono usare anche per risolvere diversi problemi di sincronizzazione. Si considerino, ad esempio, due processi in esecuzione concorrente: P1 con un’istruzione s1 e P2 con un’istruzione s2, si supponga di voler eseguire s2 solo dopo che s1 termina. Questo schema si può prontamente realizzare facendo condividere a P1 e P2 un semaforo, sincronizzazione, inizializzato a 0: nel processo P1 le istruzioni ... s1; signal(sincronizzazione) ... E nel processo P2 le istruzioni ... Wait(sincronizzazione) S2; ... REALIZZAZIONE Mentre un processo si trova nella propria sezione critica, qualsiasi altro processo che tenti di entrare nella sezione critica si trova sempre nel ciclo del codice della sezione di ingresso. Tale situazione costituisce un problema per un sistema a multiprogrammazione, in quanto tale condizione di attesa spreca cicli della CPU che un altro processo potrebbe sfruttare in modo più produttivo. Per evitare il problema della perdita di cicli di CPU, si può definire il semaforo come una struttura del linguaggio C: typedef struct{ int valore; struct processo *L; } semaforo; a ogni semaforo sono associati un valore intero e una lista di processi. L’operazione wait del semaforo si può definire come segue: void wait(semaforo S) { S.valore--; if (S.valore < 0 ) { /* aggiungi questo processo alla coda dei processi in attesa */ block(); }

57

} L’operazione signal del semaforo si può definire come segue: void signal(semaforo S) { S.valore++; if (S.valore <= 0 ) { /* togli questo processo alla coda dei processi in attesa */ wakeup(P); } } L’operazione block sospende il processo che lo invoca; l’operazione wakeup(P) pone in stato di pronto per l’esecuzione un processo P bloccato. Queste due operazioni sono fornite dal sistema operativo come chiamate del sistema di base. STALLO E ATTESA INDEFINITA La realizzazione di un semaforo con coda d’attesa può condurre a situazioni in cui ciascun processo di un insieme di processi attende indefinitamente un evento. Quando si verifica una situazione di questo tipo si dice che i processi sono in stallo. Per illustrare questo processo si consideri un insieme di due processi, P0 e P1, ciascuno dei quali ha accesso a due semafori, S e Q, impostati al valore 1. P0 P1 Wait(S) Wait(Q) Wait(Q) Wait(S) ... ... ... ... Signal(S) Signal(Q) Signal(Q) Signal(S) Si supponga che P0 esegua wait(S), e quindi P1 esegua wait(Q); eseguita wait(Q), P0 deve attendere che P1 esegua signal(Q); analogamente, quando P1 esegue wait(S), deve attendere che P0 esegua signal(S). Poiché queste operazioni signal non si possono eseguire, P0 e P1 sono in stallo. Un insieme di processi è in stallo se ciascun processo dell’insieme attende un evento che può essere causato solo da un altro processo dell’insieme. 7.5 PROBLEMI TIPICI DI SINCRONIZZAZIONE PRODUTTORI E CONSUMATORI CON MEMORIA LIMITATA Si supponga di disporre di una certa quantità di memoria rappresentata nel vettore con n posizioni, ciascuna capace di contenere un elemento. Il semaforo mutex garantisce la mutua esclusione degli accessi al vettore ed è inizializzato al valore 1. I semafori vuote e piene conteggiano rispettivamente il numero di posizioni vuote e il numero di posizioni piene nel vettore. Il semaforo vuote si inizializza al valore n; il semaforo piene si inizializza al valore 0. Codice del produttore: ... /* produce un elemento in appena_prodotto */ wait(vuote);

58

wait(mutex); /* inserisci in vettore appena_prodotto */ signal(mutex); signal(piene); ... Codice del consumatore: ... wait(piene); wait(mutex); /* rimuovi un elemento da vettore e mettilo in da_consumare */ signal(mutex); signal(vuote); /* consuma l’elemento in da_consumare */ ... PROBLEMA DEI LETTORI E DEI SCRITTORI Si consideri un insieme di dati, ad esempio un file, che si deve condividere tra numerosi processi concorrenti. Tutti i processi si possono suddividere in due grandi categorie: lettori, quelli che si interessano solo della lettura, e scrittori, che si interessano della scrittura. Naturalmente se due lettori accedono nello stesso momento all’insieme dei dati condiviso, non si ha nessun effetto negativo; viceversa, se uno scrittore e un altro processo accedono contemporaneamente allo stesso insieme di dati, si possono creare incoerenze. Questo problema di sincronizzazione si chiama problema dei lettori e dei scrittori. Variabili condivise int numlettori = 0 Semaforo scrittura,mutex Inizializzazione scrittura=1 mutex=1 per il processo Scrittore: ... wait(scrittura); /* esegui l’operazione di scrittura */ signal(scrittura); ... Per il processo Lettore: ... wait(mutex); numlettori++; if (numlettori == 1) wait(scrittura); signal(mutex); /* esegui l’operazione di lettura */ wait(mutex); numlettori--; if (numlettori == 0) wait(scrittura); signal(mutex);

59

... PROBLEMA DEI CINQUE FILOSOFI Si considerino cinque filosofi che passano la vita pensando e mangiando. I filosofi condividono un tavolo rotondo circondato da cinque sedie, una per ciascun filosofo. Il problema dei cinque filosofi è considerato un classico problema di sincronizzazione, perchè rappresenta una vasta serie di problemi di controllo della coerenza, in particolare i problemi caratterizzati dalla necessità di assegnare varie risorse a vari tipi di processi, evitando lo stallo. Una semplice soluzione potrebbe essere la seguente: Variabili condivise Semaforo bacchette[5]; inizializzate ad 1 per ogni processo Filosofo-iesimo ... wait(bacchetta[i]); wait(bacc<mangia>

hetta[ (i+1) % 5]);

signal(bacchetta[i]); signal(bacchetta[ (i+1) % 5]); <pensa> ... Questa soluzione garantisce che due vicini non mangiano contemporaneamente, ma è insufficiente poiché non esclude la possibilità che si abbia una situazione di stallo. Si supponga che tutti 5 abbiano fame contemporaneamente e che ciascuno tenti di afferrare la bacchetta di sinistra; tutti gli elementi bacchetta, diventano uguali a zero, perciò ogni filosofo che tenta di afferrare la bacchetta di destra entra in stallo. 7.6 REGIONI CRITICHE Se bene i semafori siano un meccanismo utile ed efficace, se si usano in modo scorretto possono produrre errori di sincronizzazione. Si supponga che un processo scambi l’ordine di esecuzione delle operazioni Wait e Signal sul semaforo mutex; avrebbe l’esecuzione seguente: signal(mutex); ... Sezione critica ... Wait(mutex); che potrebbe causare l’esecuzione contemporanea di più processi nelle rispettive sezioni critiche, violando così il requisito di mutua esclusione. Si supponga che un processo sostituisca signal(mutex) con wait(mutex), avrebbe l’esecuzione seguente: wait(mutex);

60

... Sezione critica ... Wait(mutex); e si avrebbe uno stallo. Per evitare l’insieme degli errori appena presentai, i ricercatori hanno inventato diversi costrutti, per esempio la regione critica. Il costrutto di sincronizzazione ad alto livelli, detto regione critica, richiede che una variabile V di tipo T che deve essere condivisa tra tanti processi, sia dichiarata come seguito: V: shared T Alla variabile V si accede solo all’interno di un’istruzione region della forma Region V when (B) do S; Significa che mentre si esegue l’istruzione S, nessun altro processo può accedere alla variabile V. Quando un processo vuole accedere alla variabile condivisa V, si valuta l’espressione booleana B; se risulta vera si esegue l’espressione S altrimenti il processo rilascia la mutua esclusione ed è ritardato fino a che B diventa vera e nessun altro

ocesso si trova nella regione associata a V. pr APPENDICE A: SYSTEM CALL PER UNIX Le chiamate di sistema a disposizione in UNIX sono scritte nel linguaggio C. Generalmente esse restituiscono il valore 0 se la funzione è stata eseguita correttamente, -1 se ha trovato qualche errore. A.1 GESTIONE DEI FILE Nel sistemi operativi di stampo UNIX il kernel di sistema associa ad ogni processo aperto una tabella dei file aperti, ed assegna ad ogni file un intero chiamato identificatore di file, diverso per ogni file. Ogni elemento della tabella dei file aperti contiene un puntatore utilizzato per le operazioni di lettura\scrittura denominato file pointer. CREAZIONE DEI FILE: creat() int creat(char *nome_file, int mode) *nome_file: string che contiene nome file da creare mode : specifica modi di accesso per la lettura\scrittura\esecuzione NOTE: essa restituisce il numero di identificatore di file se tutto ok, altrimenti -1 se fallisce. Restituisce errore se:

- file già creato da altri processi - file_pointer è nullo - raggiunto numero massimo di file aperti

Esempio: ... Int fid;

61

... Fid=creat(“pippo”,0777); ... GESTIONE DEI FILE: open() int open(char *nome_file,int flag_option[int mode]) flag_option : specifica la modalità di aperture mode : specifica modi di accesso per la lettura scrittura ed esecuzione NOTE: ritorna il numero di descrittore di file se tutto ok, -1 altrimenti. Tramite i flag definiti in fcntl.h si può specificare: - O_RDONLY apertura in sola lettura - O_WRONLY apertura in sola scrittura - O_RDWR apertura in lettura e scrittura - O_APPEND mette il puntatore alla fine del file - O_CREAT crea il file usando le modalità specificate - O_TRUNC elimina il contenuto del file se esiste - O_EXCL garantisce che il file sia stato creato dal programma che effettua la chiamata open() Restituisce errore se:

- se si vuole accedere ad una directory che non esiste - file_pointer è nullo - raggiunto numero massimo di file aperti

Esempio: ... Int fid; ... Fid=open(“pippo”,O_RDWR|O_TRUNC); ... GESTIONE DEI FILE: close() int close(int ds_file) ds_file : descrittore di file associate al file Esempio: #include <fcntl.h> ... int fid; ... fid = open(“pippo”, O_RDWR|O_TRUNC); ... close(fid); ... GESTIONE DEI FILE: read() int read(int ds_file, char *buffer_pointer, unsigned dim_trasferimento) ds_file : descrittore di file associate al file *buffer_pointer : punta area di memoria dove memorizzare i dati letti

62

dim_trasferimento : quanti bytes devono essere trasferiti NOTE: ritorna un intero pari al numero di bytes letti se tutto ok, -1 altrimenti. Esempio: ... Int fid; char buffer[1024]; ... Fid=open(“pippo”,O_RDWR|O_TRUNC); ... read(fid,buffer,100); printf(“ho letto %s :”, buffer); GESTIONE DEI FILE: write() int write(int ds_file, char *buffer_pointer, unsigned dim_trasferimento) ds_file : descrittore di file associate al file *buffer_pointer : punta area di memoria dove memorizzare i dati scritti dim_trasferimento : quanti bytes devono essere trasferiti NOTE: ritorna un intero pari al numero di caratteri affettivamente scritti, -1 se ha fallito. Esempio: #include <fcntl.h> ... int fid; char buffer[10]; ... scanf(“%s”,buffer); ... write(fid, buffer, 10); ... close(fid); GESTIONE DEI FILE: lseek() Serve a posizionare il file pointer all’interno di un file. int lseek(int ds_file,long spostamento, int option) ds_file : descrittore di file associate al file spostamento : offset del puntatore option : specifica il punto di inizio dello spostamento NOTE: ritorna il nuovo valore del file pointer in termini di numero di caratteri dall’inizio del file, -1 se fallisce. I valori di option possono essere: - SEEK_CUR si sposta a partire dalla posizione corrente file pointer, si può usare per avere la posizione corrente - SEEK_SET la posizione iniziale è l’inizio del file - SEEK_END la posizione finale è la fine del file

63

Esempio: #include <unistd.h> ... /* apro un file e metto in fid l’identificatore di file */ ... lseek(fid, 10, SEEK_CUR); /* parto da posizione corrente */ ... lseek(fid, 20, SEEK_SET); /* parto dall’inizio dl file */ ... lseek(fid, -10,SEEK_END); /* parto da fine file */ GESTIONE DEI FILE: link() e unlink() Dato che in UNIX si può gestire l’aliasing dei file (stesso file con più nomi e percorsi path) esistono tali funzioni. int link(char *percorso,char *nome_alias) int unlink(char *nome_alias) *percorso : punta al file in questione (può contenere percorso assoluto) *nome_alias : punta alla stringa contenente il nome da assegnare al file NOTE: esse ritornano rispettivamente 0 se tutto ok, -1 se la funzione ha fallito. Con la chiamata unlink() se il link rimosso era l’ultimo anche il file viene rimosso (hard link). Esempio: #include <fcntl.h> ... int fid; fid =...; link(“c:\...\nomi”, “nomi2”); ... unlink(“nomi”); ... close(fid); ... GESTIONE DEI FILE: dup()e dup2() Tali funzioni servono a duplicare il descrittore di file. int dup(int old_fd) int dup2(int old_fd, int new_fd) old_fd : descrittore di file da duplicare Esempio: int fid; fid = …;dup(fd);

GESTIONE DEI FILE: truncate() e ftruncate() Servono per troncare il contenuto di un file.

64

int truncate(char *path, int offset) int ftruncate(int fd, int offset) *path : è il puntatore al nome del file fd : e il descrittore di file associato offset : è la posizione a partire da dove si deve troncare il file Esempio: #include <fcntl.h> ... int fid; ... fid = open(“nomi”, O_RDWR|O_TRUNC); ... ftruncate(fid,5); /* truncate(“nomi”,5); */ ... GESTIONE DEI FILE: access() Serve a verificare la modalità di accesso ad un file. int access(char *path, int mode) *path : è il puntatore al nome del file mode : p R_OK verifica accesso in lettura

uò avere come valori

W_OK verifica accesso in scrittura X_OK verifica la possibilità di eseguire il file F_OK verifica l’esistenza Esempio: ... if ( access(“nomi”,R_OK) == -1) printf(“ il file non può essere aperto in lettura \n ”); ... GESTIONE DEI FILE: chmod() e fchmod() Servono per cambiare i bit di protezione di un file. int chmod(const char *path, mode_t mode) int fchmod(int fd, mode_t mode) *path : puntatore al nome del file fd : descrittore di file mode : specifica i bit protezione - Seconda cifra si riferisce al proprietario - Terza cifra al gruppo di appartenenza - Quarta cifra a tutti gli altri utenti Esempio: ... fid = creat(“pippo”,0664); ... fchmod(fid,0600); ... chmod(“pippo”,0660); ...

65

A.2 CODE DI MESSAGGI La coda di messaggi è una struttura che mantiene memorizzato un messaggio Inviato da un processo fino a quando un altro processo non decida di estrarlo dalla coda. Ad ogni coda corrisponde un identificativo numerico unico chiamato “chiave”, così come per i file esistono chiamate di sistema per creare, aprire e distruggere code. CODE DI MESSAGGI: msgget() Serve a creare una coda di messaggi. int msgget(int key, int flag) key : intero positivo che identifica la coda di messaggi flag : specifica la modalità di creazione - IPC_CREAT specifica che si vuole creare la coda n. key - IPC_EXCL specifica che si vuole generare errore in caso si tenti di creare una coda già esistente NOTE: ritorna identificatore numerico per l’accesso alla coda se OK , -1 se fallisce. Esempio: ... int dc; key_t chiave = 20; ... dc = msgget(chiave, IPC_CREAT|0600); if (dc == -1) printf(“errore …..msgget()\n”); ... CODE DI MESSAGGI: msgctl() Tale funzione serve per modificare, acquisire statistiche su una coda di messaggi. int msgctl(int ds_coda, int cmd, struct msquid_ds *buff) - ds_coda : descrittore di coda - cmd : specifica il comando invocato - IPC_STAT

- IPC_RMID

- IPC_SET - *buff : punta una struttura dove vengono memorizzate le informazioni richieste con il comando Esempio: #include <sys/icp.h> #include <sys/msg.h> ... int dc; key_t chiave = 20; ... dc = msgget(chiave, IPC_CREAT|0600); ... msgctl(dc, IPC_RMID,NULL); ...

66

CODE DI MESSAGGI: msgsnd() e msgrcv() Servono rispettivamente per inviare e ricevere un messaggio. int msgsnd(int ds_coda, void *ptr, size_t nbyte, int flag) int msgrcv(int ds_coda, void *ptr, size_t nbyte, int flag) ds_coda : descrittore di coda da cui voglio inviare/estrarre il messaggio *ptr : punta alla zona dove prelevare/registrare il messaggio nbyte : dimensione del messaggio flag : specifica se la spedizione/ricezione è di tipo bloccante (IPC_NOWAIT) Esempio: #inc...

lude ...

typedef struct { long mtype; char mtext[1024]; } msg; ... msg messaggio; int dc, ris; key_t chiave = 20; dc = msgget(chiave, IPC_CREAT|0666); ... messaggio.mtype = 1; s trcopy(messaggio.mtext,”saluti”);

ris = msgsnd(dc, &messaggio, 7, IPC_NOWAIT) ... ris = msgrcv(dc, &messaggio, 7, IPC_NOWAIT); A.3 MEMORIA CONDIVISA La memoria condivisa è un area di memoria accessibile a più processi. Ad ogni area di memoria condivisa corrisponde un identificativo numerico unico chiamato “chiave”. Così come per i file esistono chiamate di sistema per creare , aprire e rimuovere aree di memoria. MEMORIA CONDIVISA: shmget() Tale funzione serve per creare un’area di memoria condivisa.

int shmget(int key, int size, int flag) key : intero positivo che identifica l’area di memoria size : specifica la dimensione (bytes) flag : specifica la modalità di creazione IPC_CREAT IPC_EXCL Esempio:

67

#include... int dm; int chiave = 20; ... dm = shmget(chiave,256,IPC_CREAT); ... MEMORIA CONDIVISA: shmctl() Tale funzione serve per distruggere, modificare i permessi o acquisire statistiche su una coda di messaggi. int shmctl(int ds_shm, int cmd, struct shmid_ds *buff) ds_shm : descrittore dell’area di memoria cmd : specifica il comando invocato IPC_RMID IPC_STAT IPC_SET *buff : punta una struttura dove vengono memorizzate le informazioni richieste con il comando Esempio: #include... ... int dm, ris; key_...

t chiave = 20;

ris = shmctl(dm, IPC_RMID, NULL); if (ris == -1 ) printf(“errore … shmctl ”); MEMORIA CONDIVISA: shmat() e shmdt() Tali funzioni servono rispettivamente per attaccare e staccare delle aree di memoria dai processi. int shmat(int ds_shm, void *addr, int flag ) int shmdt(const void *addr) ds_shm : descrittore dell’area di memoria flag : specifica le modalità di accesso SHM_R SHM_W SHM_RW *addr : indirizzo di memoria a cui si collega/scollega l’area di memoria condivisa. Esempio: #include... int dm, ris; in chiave = 20; void *addr ; ... dc = shmget(chiave, 256, IPC_CREAT); ... addr = shmat(dc, addr, SHM_RW);

68

... shmdt(addr); PIPE e FIFO: pipe() e mkfifo() PIPE e FIFO sono meccanismi per comunicazione fra processi. Una PIPE è un canale di comunicazione fra processi che può essere condiviso con i processi figli, per crearlo si usa la chiamata pipe() int pipe(int fd[2] ) In fd[0] viene restituito un descrittore che si usa per scrivere mentre fd[1] restituisce un descrittore che si usa per leggere. Per accedere i pipe si usano le normali chiamate read(), write(),close(). Una FIFO è simile alla PIPE ma è una struttura permanente ed indipendente dal processo che la crea, per crearla si usa la chiamata mkfifo(). Per accedere le FIFO si usano le normali chiamate read(), write(), close(). int mkfifo(char *fifo_name, int mode ) *fifo_name : punta il nome della FIFO da creare mode : specifica la modalità di creazione ed i permessi di accesso. A.4 SEMAFORI Un semaforo corrisponde ad una variabile contenente un intero non negativo utilizzata come contatore per controllare l’accesso a risorse condivise fra più processi. Ogni semaforo ha un nome unico all’interno del sistema costituito da un i ntero positivo chiamato “chiave”.

SEMAFORI: semget() Tale funzione serve per creare un semaforo. int semget(key_t key, int number, int flag) key : identificatore del semaforo number : numero di elementi del semaforo(generalmente 1) flag : specifica le modalità di creazione del semaforo IPC_CREAT IPC_EXCL Esempio: ... semget(chiave, numero, IPC_CREAT | 0660); ... SEMAFORI: semctl() Tale funzione serve per assegnare il valore iniziale, prelevare o modificare i permessi di un semaforo. int semctl(int ds_sem, int sem_num, int cmd, senum arg) ds_sem : descrittore del semaforo sem_num : elemento del semaforo su cui operare cmd : specifica il comando invocato - IPC_RMID - GETALL, SETALL

69

- GETVAL, SETVAL arg : specifica gli argomenti del comando SEMAFORI: semop() Tale funzione serve per incrementare o decrementare il valore di un semaforo. int semop(int ds_sem, struct sembuf oper[], int number) ds_sem : descrittore del semaforo *oper : puntatore ad un buffer contenente la specifica dell’operazione da eseguire number : numero di elementi del buffer STRUTTURA DEL SEMAFORO struct sembuf { short sem_num; /* elemento del semaforo su cui operare */ short sem_op; /* valore positivo o negativo da sommare */ short sem_flg; /* opzioni default 0 */ } A.5 SEGNALI I segnali permettono di notificare un evento ad un processo, nella maggior parte dei casi è il kernel che genera segnali in occasione di eventi eccezionali. Fra i segnali più comuni vi sono: -SIGHUP : chiusura terminale associato al processo -SIGINT : CTRL-C -SIGQUIT : genera un core dump -SIGILL : istruzione illegale -SIGKILL kill : modo più sicuro per terminare un processo -SIGSEGV : violazione di segmento -SIGTERM : richiesta di terminazione che può essere ignorata -SIGALARM : inviato allo scadere del conteggio del time SEGNALI: kill(), alarm() e signal() Per inviare un segnale ad un processo si usa la chiamata kill(). int kill(int pid, int segnale) pid : identificatore del processo segnale : specifica il segnale da inviare Per autoinviarsi il SIGALRM dopo un certo periodo di tempo si usa la chiamata alarm(). unsigned alarm(unsigned time) time : specifica il periodo di tempo in secondi Per associare ad un segnale una funzione da eseguire al momento del suo arrivo si usa la chiamata signal()

70

void (*signal(int sig, void (*ptr)(int)))(int) sig : specifica il segnale da gestire ptr : specifica la modalità di gestione APPENDICE B: LINUX B.1 COMANDI FONDAMENTALI man <comando> : spiega cosa fa <comando>; per terminare premere Q stty –a : informazioni generiche sul terminale echo <frase> : scrive sullo schermo <frase> ls : elenca le directory e file della cartella corrente mkdir <cartella> : crea directory <cartella> cd <pippo> : va alla cartella pippo cd.. : torna indietro pwd : restituisce percorso della directory corrente echo $PATH : visualizza percorso della PATH PATH = $PATH:<percorso> : aggiunge <percorso> al PATH echo $TERN : restituisce il tipo di terminale echo $HOME : restituisce la home directory echo $HOSTNAME : restituisce host name del calcolatore echo $SHELL : restituisce tipo di shell usata echo $OSTYPE : restituisce il tipo di sistema operativo echo $LOGNAME : restituisce il tipo di utente corrente ls –lat : restituisce info sui metodi di lettura/scrittura sui file contenuti nella directory corrente chmod 777 <file> : abilita in scrittura/lettura/esecuzione per tutti gli utenti ./ <file> : specifica che <file> e da cercare nella directory corrente date : restituisce la data who : restituisce gli utenti correnti whoami : restituisce informazioni sull’utente corrente <comando> > <file> : ridireziona l’output di <comando> sul file sovrascrivendo il contenuto di <file>

71

<comando> >> <file> : ridireziona l’output di <comando> sul file appendendo il contenuto di <file> (<com1>;<com2>) > <file> : esegue contemporaneamente <com1> e <com2> mandando l’output di tali comandi sul <file> more <file> : visualizza <file> sullo schermo ps : restituisce i processi in esecuzione more < <file> : stampa sullo schermo il contenuto di <file> ps –aux|more : simile a dir/p per l’MS DOS. <comando1>|<comando2> : valore restituito da <comando1> va in input a <comando2> History|more : elenca ultimi comandi eseguiti !! : esegue l’ultimo comando !10 : esegue il 10 comando della lista history !<lettera> : esegue ultimo comando eseguito che inizia con la lettera <lettera> wc <file> : restituisce righe, parole e byte di <file> find / -name *<estensione> –print & : cerca a partire dalla route tutti i file che hanno come estensione .<estensione> e restituisce il prompt, eseguendo il comando in background ls –lat <lettera> : elenca tutti i file che iniziano con lettera <lettera> ls –lat [<lettera1><lettera2><lettera3>]* : elenca i file che iniziano per <lettera1>,<lettera2> e <letter3>. ls –lat [<lettera1> - <lettera2>] : elenca i file compresi tra le lettere <lettera1> e <lettera2> <comando1> & <comando2> : esegue <comando1> e <comando2> simultaneamente <comando1> && <comando2> : se è verificato <comando1> si esegue <comando2> B.2 ESEMPI DI APPLICAZIONI SHELL #! /bin/bash DIR = $HOME/esempishell/ciclofor

72

test –d $DIR || mkdir $DIRFOR for I in $1 $2 $3 do cp File$I $DIRFOR done NOTE: test –d $DIR || ... vede se esiste la directory che ha come percorso DIR e se si esegue il comando mkdir $1,$2,$3,... per richiamare rispettivamente il parametro 1,2,3,... passato in input $# contiene il numero di parametri passati in ingresso /****************************************************************/ #! /bin/bash case $1 in A|a) X=alpha;; B|b) X=beta;; G|g) X=Giorgio;; esac echo $X /****************************************************************/ #! /bin/bash If [ $# = 0 ] then echo devi fornire 1 argomento else echo $* fi NOTE: echo $* stampa sullo schermo tutti i parametric passati in ingresso, equivale a fare echo $@ /****************************************************************/ #! /bin/bash while : do if who|grep $1 > res then echo $1 è loggato else sleep 30 fi

73

done NOTE: who|grep S1 > res elenca tutti gli utenti che hanno nome $1 all’interno del file res sleep 30 aspetta 30 sewhile :

condi

e come fare while(1) in C++ /****************************************************************/ #! /bin/bash until who|grep $1 > res do sleep 30 done echo $1 è loggato /****************************************************************/

74