Componenti di un SO

S S I I S S T T E E M M I I O O P P E E R R A A T T I I V V I I

Sistemi operativi Processi 2

Componenti di un sistema operativo 3 Tipologie di un sistema operativo 4 Nucleo di un sistema operativo

Caratteristiche dei processi 7 Stati dei processi 8

Scheduler e Dispatcher 10

Competizione e cooperazione 14 Gestione dell’I/O

Classificazione dei device 22 Gestione dei dischi 24

Gestione della memoria centrale Allocazione contigua 31 Allocazione non contigua 33 Memoria virtuale 34

Gestione del File System Directory 43

Allocazione 48 FAT 52

Glossario

Sistemi Operativi

Un sistema operativo è un complesso insieme di programmi che consente il buon funzionamento di un elaboratore. Il sistema operativo agisce da intermediario fra l’utente e la struttura fisica del calcolatore. Esso ha il compito di gestire e controllare le risorse del sistema (l’hardware ed il software) fornendo un ambiente di lavoro di semplice uso, stabile ed indipendente dall’hardware.

Il sistema operativo deve quindi realizzare politiche di gestione delle risorse hardware al fine di:

1. regolamentare l’impiego delle risorse evitando conflitti di accesso,

2. scegliere i criteri con cui assegnare una risorsa a fronte di più richieste contemporanee, a causa della limitata disponibilità di risorse,

3. nascondere all’utente i dettagli hardware legati al particolare dispositivo.

Processi

L’esecuzione di un programma richiede un flusso di varie operazioni compiute dalla CPU nelle quali, l’esecuzione delle specifiche istruzioni del programma sono solo una parte.

Un processo comprende anche tutte le risorse necessarie per la sua esecuzione (programm counter, stack, dati, device, ecc.)

Molto spesso, l’esecuzione di un programma richiede l’utilizzo di più risorse che vengono attivate per mezzo di altri processi. L’attivazione di questi altri processi viene gestita dal sistema operativo.

Dato che la CPU può eseguire un solo processo per volta, sarà necessario sospendere il processo in corso per attivare il nuovo. Questa commutazione, che è detta cambio di contesto, viene eseguita dal sistema operativo. Il tempo di CPU è quindi in parte dedicato ai processi utente ed in parte ai processi di sistema operativo. Il tempo necessario al cambio di contesto è detto overhead ed essendo tempo sprecato, dovrà essere ridotto al minimo.

Programma (entità statica) e processo (entità dinamica) non sono quindi la stessa cosa.

Tutto il software attivo su un computer è organizzato in un insieme di processi sequenziali attivabili uno per volta. Per poter sospendere e poi riattivare un processo è necessario poter ricordare le condizioni in cui si trovava all’atto della sospensione. Questo insieme di informazioni è chiamato stato del processo ed è costituito da tutte le informazioni necessarie per poter riprendere l’esecuzione dopo una sospensione. Il PCB (Process Control Block) memorizza queste informazioni Thread

Ci sono operazioni che vengono svolte sequenzialmente e che potrebbero essere svolte concorrentemente riducendo così i tempi con la conseguente ottimizzazione delle prestazioni del sistema. L'ideale sarebbe creare processi eseguibili in parallelo e che condividano risorse in comune ma che siano strutturati in modo da rendere i tempi di cambiamento di contesto più brevi.

Si introduce quindi il concetto di thread. Il thread rappresenta l’unità di base di utilizzo della CPU.

Un thread è una parte di un processo che può essere eseguita contemporaneamente ad altri thread riuscendo così ad aumentare lo pseudoparallelismo senza aumentare eccessivamente l’overhead.

Un processo è costituito da almeno un thread che viene creato automaticamente all’avvio del processo. Un thread può creare altri thread e così via.

I thread generalmente condividono tutto il codice del processo e lo spazio dei dati delle variabili, ciò implica che la commutazione tra i thread risulterà molto veloce.

Un processo può creare dei thread ma non viceversa.

Componenti di un SO

Gestore dei processi Il gestore dei processi si occupa di tutte le operazioni che coinvolgono i processi. Un processo è un programma in esecuzione che per svolgere i suoi compiti necessita di alcune risorse (CPU, memoria, file, dispositivi di I/O). Il sistema operativo si occupa di mandare un programma in esecuzione ed allocare le risorse utilizzate. Il sistema operativo quindi:

- crea e cancella i processi utente e di sistema, - sospende e ripristina i processi,

- fornisce meccanismi per la sincronizzazione dei processi, - fornisce meccanismi per la comunicazione tra i processi, - fornisce meccanismi per la gestione dei deadlock.

Gestore degli I/O Il sistema operativo deve nascondere all’utente le caratteristiche degli specifici dispositivi hardware. Solo il driver dello specifico dispositivo fisico conosce le caratteristiche dello stesso. Il sistema operativo realizza un’astrazione dei dispositivi di I/O definendo un’interfaccia comune che sfrutta i servizi dei driver (sottosistema I/O), che è composto da:

- componente per la gestione della memoria di un buffering, latching e spooling,

- un’interfaccia generale per i driver dei dispositivi, - i driver per gli specifici dispositivi.

Gestore della memoria Prima di eseguire un programma deve essergli allocata la memoria: il programma deve essere associato a indirizzi assoluti e caricato in memoria; tali indirizzi vengono generati dalla CPU.

Se ci sono più programmi che richiedono l’elaborazione occorre scegliere quale mandare in esecuzione tenendo conto della memoria totale disponibile e di quella richiesta.

Quando il programma termina il sistema operativo gli revoca la memoria rendendola disponibile per l’esecuzione di altri programmi.

In particolare deve:

- tener traccia della memoria disponibile, - selezionare i processi da caricare in memoria, - assegnare e revocare la memoria ai processi,

- memorizzare per ogni processo la memoria allocata

Gestore del file system I dispositivi di memorizzazione secondaria sono molteplici ed ognuno ha proprie caratteristiche ed una organizzazione fisica diversa. Il sistema operativo si occupa di semplificare i compiti dell’utente e traduce le sue richieste per i dispositivi fisici.

Riguardo alla gestione dei file è responsabile di:

- creare e cancellare file e directory,

- fornire all’utente le funzioni fondamentali per la manipolazione di file e directory,

- creare una associazione tra i file e i corrispondenti dispositivi di memoria secondaria,

- mantenere un back up dei file su dispositivi di memorizzazione stabili, non volatili.

Gestore del networking In un sistema distribuito le unità di elaborazione sono collegate da una rete di comunicazione. I calcolatori che ne fanno parte condividono le risorse.

Quindi il sistema operativo deve gestire l’accesso a queste ultime e gestire la comunicazione con processi remoti. Per far questo è dotato di

un dispositivo di interfaccia con la rete (dispositivi di I/O) e sviluppa la parte dei protocolli di rete nel sistema operativo stesso.

Gestore della sicurezza Se un sistema di calcolo ha più utenti e consente che più processi siano eseguiti in modo concorrente, i diversi processi devono essere protetti dall’attività di altri processi e gli utenti possono accedere solo alle risorse di cui dispongono i permessi.

Per questo motivo esistono meccanismi che assicurano che i file, i segmenti della memoria, la CPU e altre risorse possano essere controllate solo dai processi che hanno ricevuto l’autorizzazione dal sistema operativo. E’ compito del sistema operativo amministrare la sicurezza del sistema nel modo più opportuno.

Interfaccia utenti La UI oppure GUI è l’interfaccia tra il sistema operativo e l’utente trasformando le indicazioni dell’utente in comandi per il sistema operativo senza doverne gestire tutti i dettagli.

Tipologie dei sistemi operativi

batch I sistemi di tipo batch prevedono l’esecuzione di un programma alla volta sempre residente nella memoria: il calcolatore legge un programma, lo carica in memoria e lo esegue fino alla fine o fino ad un errore, poi stampa il risultato. Quindi passa ad un nuovo programma:

lettura, memorizzazione, esecuzione, stampa. E così via per tutti i programmi.

Il sistema operativo utilizzato è molto semplice: non c’è interazione tra programma e utente, non si devono prendere decisioni su come allocare le risorse, né scegliere il successivo programma da eseguire.

Questi sistemi sono poco efficienti e la CPU è spesso inattiva.

single user single task Prevede un unico utente ed una sola attività in esecuzione.

single user multi tasking Prevede un unico utente ma la possibilità di eseguire più attività

“contemporaneamente”, sono anche detti multiprogrammati.

La multiprogrammazione consente di aumentare l’utilizzo della CPU organizzando i lavori in modo tale da mantenerla in continua attività.

In questi sistemi sono presenti contemporaneamente in memoria centrale diversi programmi, uno dei quali viene selezionato e mandato in esecuzione. Il processo creato mantiene il controllo della CPU finché non si arresta perché termina o perché in attesa di qualche evento come il completamento di una operazione di I/O. A questo punto la CPU invece di rimanere inattiva viene assegnata ad un altro processo presente in memoria. Se il primo processo non era terminato, quando torna pronto riprende il controllo della CPU continuando la sua esecuzione.

La multiprogrammazione ottimizza l’utilizzo delle risorse, in particolare della CPU che viene commutata tra i processi in esecuzione per ridurre i tempi morti

multi user Una variante dei sistemi multiprogrammati è rappresentata dai sistemi interattivi (multi user) in cui la CPU viene commutata più velocemente per permettere all’utente di interagire con il programma.

Per fare questo (e per dare all’utente l’impressione che l’esecuzione dei programmi sia parallela) si introduce il meccanismo del timesharing (ripartizione del tempo) secondo il quale si commuta la CPU tra i diversi programmi per un quanto di tempo T. Ogni programma viene quindi

eseguito per un tempo minore o uguale a T. Se non ci sono errori che sospendono l’esecuzione prima che sia trascorso il tempo T, il programma viene bloccato ed il controllo della CPU passa ad un altro programma, mentre il precedente viene accodato in una apposita lista.

Il tempo impiegato dal sistema operativo per trasferire il controllo da un programma ad un altro è detto overhead e deve essere limitato il più possibile. La scelta dell’intervallo di tempo T dipende dal numero di programmi che devono essere eseguiti: maggiore è il numero di programmi, minore è T. Se T è sufficientemente piccolo l’utente non si accorge del cambiamento di esecuzione.

paralleli I sistemi paralleli sono dotati di più unità di elaborazione, per questo sono chiamati anche sistemi multiprocesso.

I processori che compongono questo tipo di sistemi sono strettamente accoppiati: condividono risorse hardware e tipicamente hanno lo spazio di memoria in comune. Le operazioni sono eseguite in parallelo su più processi; quindi se una solita operazione deve essere eseguita su dati diversi, sfruttando la presenza di più CPU, vengono mandati in esecuzione contemporaneamente processi diversi.

Offrono maggiore efficienze e maggiore affidabilità.

reti di calcolatori In una rete di calcolatori il sistema è costituito da più processori come accade nei sistemi paralleli, ma a differenza di questi ultimi, i processori sono dislocati a distanze elevate uno dall’altro. Inoltre nei sistemi paralleli lo spazio di memoria è generalmente in comune (in realtà dipende dalla struttura del sistema) , quindi i diversi processori non sono completamente autonomi. Nelle reti invece i nodi sono indipendenti e possono lavorare da soli.

SISTEMI DI RETE: il sistema operativo è supportato da moduli per il networking e da programmi per la comunicazione in rete con altri calcolatori simili. L’utente ha visione di tutte le risorse disponibili, può quindi accedere a macchine remote e copiare file da una macchina all’altra. Ogni macchina ha il proprio sistema operativo locale.

SISTEMI DISTRIBUITI: il sistema operativo così organizzato fa apparire la rete come un unico sistema monoprocessore: l’utente manda in esecuzione un programma su una macchina; sarà poi il sistema operativo a decidere su quale macchina verrà realmente eseguito (di solito sceglie il processore meno occupato), quindi l’utente non sa quali risorse vengono utilizzate. Risultano più complessi.

cluster I sistemi cluster hanno alcune caratteristiche simili ai sistemi paralleli e altre simili alle reti: sono composti da più nodi autonomi che condividono le risorse (per esempio condividono dispositivi di memoria secondaria – dischi). Questi sistemi sono utilizzati per garantire affidabilità e disponibilità: devono produrre grosse prestazione o essere sempre disponibili (server web). Le richieste vengono gestite da un controllore e smistate ai nodi. Le richieste di uno stesso utente possono essere gestite tutte da uno stesso nodo o da nodi diversi a seconda della politica scelta dal controllore.

real time I sistemi di elaborazione in tempo reale si usano quando è necessario fissare rigidi vincoli temporali per le operazioni della CPU o per il flusso di dati. In questi sistemi tutte le elaborazioni devono essere eseguite entro un limite massimo temporale, altrimenti i risultati non risultano più attendibili.

HARD REAL-TIME: i compiti critici devono essere completati in un dato intervallo di tempo; il mancato rispetto del vincolo temporale produce effetti catastrofici (la definizione di effetti catastrofici è relativa).

SOFT REAL-TIME: il mancato rispetto del vincolo temporale non ha conseguenze disastrose (per es. sistemi multimediali, realtà virtuale).

embedded I sistemi embedded vengono eseguiti su calcolatori che controllano dispositivi che non sono generalmente veri e propri sistemi di elaborazione (per esempio televisori, lavatrici, forni a microonde, telefoni cellulari). Il sistema in questo caso è ottimizzato per la specifica applicazione, per questo è in contraddizione con i general purpuse i quali sono progettati per svolgere funzioni diverse.

Il sistema operativo risulta quindi semplice: si limita ad interpretare i comandi, gestire la memorizzazione dei dati sui file e attivare i programmi applicativi. I sistemi embedded spesso hanno esigenze di real-time, ma hanno anche problemi di limitazioni di memoria (non c’è la virtualizzazione delle risorse) e di alimentazione

mobile I sistemi mobili comprendono palmari, notebook, cellulari che possono connettersi alle reti.

La dimensione ridotta di questi dispositivi rende il sistema che li realizza particolare:

Per ridurre al minimo le dimensioni dei portatili si utilizzano risorse hardware inferiori ai normali pc.

La memoria disponibile è limitata ed a volte non è realizzata la virtualizzazione della memoria; il sistema operativo deve quindi gestire la memoria in modo efficiente.

L’unità di elaborazione è lenta, perché una maggiore frequenza della CPU comporta un maggior consumo. Quindi il sistema risulta avere una minor potenza di calcolo.

Perché questi dispositivi siano portatili le batterie devono essere leggere e non alimentate da rete.

Tutte le risorse sono progettate in modo da consumare il meno possibile e utilizzate nel modo più efficiente, compatibilmente al minor consumo.

transaction processing Per transazione si intende una operazione le cui varie fasi devono avvenire tutte con successo altrimenti l’operazione stessa deve essere annullata in tutte le sue fasi. Un esempio sono le transazioni bancarie.

Si evidenzia il fatto che, la classificazione ora proposta non definisce le tipologie in modo mutuamente esclusivo in quanto possono esistere sistemi operativi le cui caratteristiche soddisfano contemporaneamente più di una delle tipologie esposte.

Caratteristiche dei processi

Uno degli aspetti più apprezzati di un processo è la velocità di accesso al codice eseguibile e la relativa disponibilità dello stesso nei vari livelli di memoria.

Il concetto di locality si riferisce alla possibilità di prevedere il futuro punto di accesso in memoria.

Spatial Locality: se un programma accede ad una particolare locazione di memoria, la probabilità che acceda, in un prossimo futuro, a locazioni vicine è molto elevata. Ciò è giustificato dall’esecuzione sequenziale e dall’utilizzo di strutture dati di tipo vettoriale.

Temporal Locality: se un programma accede ad una particolare locazione di memoria, è probabile che vi acceda nuovamente in un prossimo futuro. Ciò è giustificato dall’uso frequente nei programmi di tecniche iterative

Working set: è la generalizzazione del concetto di locality in ambito di gestione della memoria. Il working set è l’insieme delle pagine di memoria utilizzate nelle ultime unità temporali di lavoro.

Boundless

Un processo che fa uso frequente di I/O si dice I/O bound.

Un processo che fa molta computazione e poco I/O si dice CPU bound.

La fase di utilizzo della CPU si dice CPU burst e quella di I/O invece I/O burst.

Un processo si dice che è in fase di I/O bound se esegue una operazione di I/O in un tempo uguale o inferiore a 10 unità di tempo.

Un processo si dice in fase di CPU bound se esegue 100 o più istruzioni senza operazioni di I/O.

Un processo è in fase neutrale se non rientra nelle due precedenti.

La conoscenza della tipologia di bound è importante nei sistemi multiprocesso per poter assegnare la CPU o l’I/O ai diversi processi in modo da migliorare l’impiego delle risorse e l’efficienza.

Registri e memoria

L’accesso ai dati per l’esecuzione delle istruzioni può essere effettuato dai registri o dalla memoria RAM. Nel caso dei registri la velocità di elaborazione è massima.

Un processo si dice che è in fase di register intensive se esegue 100 o più istruzioni senza accedere alla RAM mentre è in fase RAM intensive se accede intensivamente alla RAM

Foreground/background

I processi foreground sono gestiti e quindi interagiscono con gli utenti mentre i processi background sono in stato di sospensione pronti però ad attivarsi per fornire servizi.

Stati dei processi

In un sistema operativo, un processo è rappresentato da una struttura dati detta Process Control Block (PCB) o descrittore del processo.

Il PCB contiene le seguenti informazioni:

program counter

area di stack per il salvataggio dei registri di stato e general purpuse stato di avanzamento del processo

identificatore del processo puntatori ai processi dipendenti livello di priorità

informazioni per il memory management informazioni per lo scheduling del processo informazioni sull’accounting del processo informazioni sull’I/O del processo

Il PCB è quindi la struttura dati mediante la quale il sistema operativo gestisce un processo e ne rappresenta lo stato globale.

Stati di un processo

Lo stato di un processo consiste in tutte le informazioni necessarie per riprendere l’esecuzione dopo una temporanea sospensione.

Un processo si evolve attraverso una serie di stati di avanzamento discreti:

• Stato iniziale: NEW. Quando si manda in esecuzione un programma si crea un processo ed il relativo descrittore. Il programma creato si trova nello stato new. I campi del PCB vengono inizializzati con dei valori iniziali appropriati e il processo viene inserito in una coda. Si crea anche un identificatore (PID) che serve al sistema operativo per identificare quel processo. Il processo creato non ha ancora la memoria a sua disposizione, quindi non è ancora in esecuzione. Esistono più processi in stato new raggruppati in una lista da cui verranno scelti in base alla politica dello schedulatore. Il programma verrà poi selezionato per l’assegnazione della memoria.

• Stato READY. Quando un processo che si trova nello stato iniziale viene scelto dallo schedulatore, gli viene associata la memoria e passa nello stato ready, in attesa di essere assegnato ad una unità di elaborazione (il processo viene inserito nella lista dei processi pronti). Oltre a modificare opportunamente il campo stato, operazione che avviene ad ogni cambiamento di stato, nel descrittore si inseriscono anche le informazioni sulla memoria allocata. Il processo è pronto per essere mandato in esecuzione e possiede tutte le risorse necessarie tranne la CPU.

• Stato RUNNING. Il passaggio dallo stato ready allo stato running avviene quando l’unità di elaborazione è libera. Un processo passa dallo stato ready allo stato running quando un’unità di elaborazione esegue le istruzioni del relativo programma. Poiché esistono più di un processo nello stato ready, la selezione del processo da mandare in esecuzione avviene in base alla politica adottata dal sistema. Una componente del sistema operativo (dispatcher) commuta il contesto: copia i valori attuali della CPU nel descrittore del processo uscente e carica i registri della CPU con i nuovi valori prelevati dal descrittore del processo entrante. Il processo uscente viene inserito nella lista dei processi pronti. Da questo stato si può tornare allo stato ready per effetto di una interruzione (per esempio nei sistema timesharing trascorso il quanto temporale a disposizione di un processo si ha un cambiamento di contesto), oppure se il processo richiede operazioni di I/O si passa allo stato di waiting, infine se il processo è terminato passa nello stato terminate.

puntatore stack del processo

contatore di programma numero del processo

. . . elenco dei file aperti

limiti di memoria registri

• Stato WAITING. Quando i processi richiedono operazioni che non coinvolgono l’utilizzo della CPU (per esempio una operazione di I/O) vengono messi nello stato waiting in attesa che l’operazione termini (intanto la CPU passa ad eseguire un altro processo); quindi torna in READY in attesa che sia di nuovo il suo turno. Un processo può andare in stato WAITING anche per problemi diversi dalle chiamate di I/O, per esempio per attese di particolari eventi.

• Stato TERMINATE. Il processo può terminare in modo anomalo, mentre è in stato RUNNING, o normale. Il processore aggiunge alla fine del programma una chiamata di sistema che lo fa terminare. Tutte le risorse vengono liberate, eventuali file aperti vengono chiusi dal sistema operativo, la memoria allocata torna libera e tutte le risorse revocate. Il descrittore di processo viene liberato e messo in una coda in attesa di essere allocato per un altro processo.

Operazioni sui processi

CREATE I principali eventi che possono determinare la creazione di un processo sono:

avviamento ed inizializzazione del sistema

un processo in esecuzione invoca una system call creation un utente richiede la creazione di un nuovo processo

FORK Un processo può creare un nuovo processo per mezzo della procedura fork.

Il processo creatore viene detto parent mentre quello creato è detto child. In questa gerarchia, un parent può avere più child ma un child può avere un solo parent.

JOIN La join è usata per unificare due sequenze di codice sdoppiate da una fork. E’ utile al processo parent per potersi sincronizzare con il processo child.

ABORT Determina la terminazione forzata di un processo ed è usata per rimuovere un processo malfunzionante. Crea anche delle informazioni sui motivi del malfunzionamento.

SUSPEND Un processo può sospendere se stesso o un altro processo secondo le priorità.

RESUME Riattiva un processo sospeso

DELAY Gestisce i time out cioè il tempo di attesa di un certo evento, scaduto il quale, il processo riprende il controllo.

TERMINATE Rappresenta la conclusione di un processo. Questo può avvenire in più modi:

Normal exit: quando il processo si conclude regolarmente Error exit: quando si verifica un errore parametrico

Fatal error: quando si verifica un grave errore che impedisce la prosecuzione Killed: quando un altro processo ne chiede la conclusione

new

ready running

waiting

terminate ammesso

interruzione

completamento di un I/O o verificarsi di un

evento

dispatch

attesa di un I/O o di un evento uscita

Thread

Si è già detto che un thread rappresenta l’unità di base di utilizzo della CPU che viene individuato e schedulato per l’esecuzione da parte della CPU.

Un thread è caratterizzato dal Program Counter, un insieme di registri ed una area di stack.

Il thread è quindi più leggero da gestire rispetto ai normali processi, in particolare riduce l’overhead.

Nella programmazione multithread, ogni processo è composto da singoli thread in esecuzione per ogni attività concorrente e che condividono codice, dati e file. Ogni singolo thread contiene i registri e lo stack che definiscono l'attività caratteristica di quel thread. Con l’utilizzo della programmazione a multithread i tempi di commutazione di contesto si riducono notevolmente.

Quando si commuta il contesto, il salvataggio dello stato del vecchio thread ed il caricamento dello stato del nuovo thread (all’interno di uno stesso processo) riguarda solo i registri e lo stack dato gli altri dati sono in comune. I vantaggi della programmazione multithread sono:

• Tempi di risposta più brevi. Un programma può continuare la sua elaborazione anche quando un thread che lo compone è bloccato o sta eseguendo una operazione particolarmente lunga.

• Ottimizzazione della condivisione delle risorse. Un’applicazione può avere molti thread di attività diverse, tutti nello stesso spazio di indirizzamento, grazie alla condivisione del codice.

• Aumento del grado di parallelismo nei sistemi con più unità di elaborazione. Nelle architetture a singola CPU i thread si scambiano il controllo della CPU molto velocemente, creando l’illusione di una esecuzione parallela, in realtà si esegue un thread alla volta.

• Tempi più brevi derivanti dalla condivisione delle risorse dei thread. Nei thread, i tempi di cambio di contesto sono inferiori rispetto alla creazione ed allocazione della memoria ai processi. Quindi è conveniente creare un solo processo composto da tanti thread invece di creare tanti processi indipendenti.

Scheduler e Dispatcher

Si intende per scheduling il criterio di individuazione, di uno tra più richiedenti, al quale assegnare l’esecuzione di un sevizio.

Il concetto di scheduling risulta essere alquanto ampio e pertanto ne vengono definiti tre livelli:

Long Term Scheduling (LTS): Regola l’accesso dei programmi al sistema per la loro esecuzione e quindi controlla il grado di multiprogrammazione per cercare di massimizzarlo. Suddivide i processi in gruppi bilanciati nell’uso di CPU ed I/O per poi sottoporli all’STS.

Medium Term Scheduling (MTS): Riguarda solo una parte dei processi che vengono mantenuti in memoria mentre i rimanenti sono trasferiti su disco. Vengono rimossi i processi che sono rimasti in memoria un tempo sufficientemente lungo per caricare un nuovo insieme di processi dal disco. Si tratta di un livello connesso alla gestione della memoria virtuale.

Short Term Scheduling (STS): è il normale scheduler di CPU dei processi residenti in memoria ed è quello che sarà in seguito preso in considerazione.

Scheduler

Il compito dello scheduler è quello di stabilire quale sarà il successivo processo al quale assegnare la CPU per l’esecuzione. La scelta avviene per mezzo di opportuni algoritmi di schedulazione.

L’effettiva assegnazione della CPU al processo prescelto è effettuata dal dispatcher . Scheduler e dispatcher operano sulle code di attesa dei processi.

Dispatcher

Il dispatcher è un modulo del sistema operativo che passa effettivamente il controllo della CPU ai processi scelti dallo scheduler. Il dispatcher effettua il cambio di contesto (context switch) assegnando la CPU ad un processo di un utente precedentemente sospeso e riprendendone l’esecuzione dal punto dove era stato sospeso.

Il tempo necessario per sospendere un processo ed avviare il successivo è detto tempo di latenza.

Context switch

Per assicurare ad ogni processo un equo utilizzo della CPU, il sistema operativo usa un Real Time Clock hardware che genera periodicamente un interrupt consentendo una regolare schedulazione dei processi presenti in memoria.

Quando la CPU viene assegnata ad un nuovo processo si ha un context switching.

I valori dei registri sono salvati nel PCB del processo che viene sospeso ed i registri sono caricati con i valori del nuovo processo. Queste operazioni richiedono un tempo non trascurabile mentre per i thread questa operazione è molto più veloce in quanto è relativa ad una minore quantità di informazioni da commutare.

Sistema Operativo

in esecuzione

Salva stato in PCB0

scheduler inattivo

Ripristina stato da PCB1

inattivo in esecuzione

Salva stato in PCB1

scheduler

Ripristina stato da PCB0 inattivo

in esecuzione

Processo P₀ Processo P₁

interruzione o chiamata del sistema

interruzione o chiamata del sistema

Criteri di scheduling

L’obbiettivo dello scheduling è quello di ottimizzare le prestazioni dell’intero sistema ed in modo particolare quello della CPU. Si definiscono quindi alcuni indici di prestazione in base ai quali si determina il comportamento di un sistema.

• Fairness: lo scheduler deve essere imparziale. Ogni processo deve ricevere la sua equa parte di tempo di CPU e nessun processo deve attendere indefinitamente. Equità però non vuol dire uguaglianza ma assegnazione di tempo proporzionale all’importanza ed alla priorità.

• Policy Enforcement: lo scheduler deve assicurare che le politiche del sistema siano sempre garantite e cioè che i processi ad alta priorità siano sempre eseguiti.

• Efficiency: lo scheduler deve sempre mantenere le risorse del sistema impegnate al 100%.

• Response time: è il tempo che intercorre tra l’istante in cui viene generata una richiesta e l’istante di inizio dell’asservimento. Il suo valore deve essere il più piccolo possibile.

• Tempo di attesa: rappresenta la somma dei tempi che i processi passano in coda.

• Throughput: numero dei processi elaborati per unità di tempo.

• Overhead: percentuale di tempo di CPU usata dallo scheduler e dal dispatcher.

Scheduling preemptive e non preemptive

Gli algoritmi di schedulazione possono essere divisi in due categorie: preemptive e non preemptive (con prerilascio e senza prerilascio oppure interrompente e non interrompente).

Lo scheduling si dice non preemptive se, una volta assegnata la CPU ad processo, questa non può essere tolta al processo in base ad eventi esterni al processo stesso. In questo caso, il context switch si potrà attivate solo se il processo termina o si blocca.

Lo scheduling si dice preemptive quando è possibile togliere la CPU ad un processo in relazione ad eventi esterni al processo stesso e cioè può essere sospeso anche se dispone di tutte la risorse necessarie, per es. l’arrivo di un processo con priorità più elevata.

Algoritmi di schedulazione

First Come First Served (FCFS)

Viene anche detto FIFO (First In First Out) ed utilizza la politica secondo la quale il primo arrivato è il primo servito per cui la coda dei processi viene riempita secondo il tempo di arrivo.

Questo algoritmo è il più utilizzato, soprattutto per la sua semplicità realizzativa.

E’ un algoritmo non premptive per cui un processo al quale viene assegnata la CPU sarà eseguito fino al suo completamento.

Si tratta di un algoritmo solo teoricamente equo in quanto un processo lungo e poco importante potrebbe far attendere molto un processo breve ma importante.

I cambiamenti di contesto risultano molto veloci, ma i tempi medi di attesa in coda sono elevati.

Si consideri questo esempio:

I tempi di attesa in coda risultano:

TP1 = 0; TP2 = 24; TP3 = 27;

Quindi il tempo medio di attesa sarà:

(TP1 + TP2 + TP3 )/3 = 17

Il valore ottenuto è elevato: l’algoritmo FCFS non fornisce grandi prestazioni dal punto di vista dell’attesa dei processi in coda. Risulta quindi evidente che questo algoritmo non può essere utilizzato nei sistemi real-time nei quali i processi richiedono risposte in tempi brevi.

Shortest Process Next First (SPNF)

Viene anche detto SJF (Shortest Job First) ed utilizza la politica secondo la quale il primo processo ad essere eseguito è quello con minor tempo di esecuzione, cioè quello con CPU burst più breve. Se nella coda dei processi pronti ci sono più processi con lo stesso CPU burst, tra questi si sceglie secondo il criterio FCFS.

E’ un algoritmo non premptive per cui un processo al quale viene assegnata la CPU sarà eseguito fino al suo completamento.

Processo Burst Time

P1 24

P2 3 P3 7

La coda dei processi pronti è più complicata rispetto al caso precedente: non è organizzata più in modalità FIFO, ma ordinata in base alla durata della successiva sequenza di operazioni di CPU.

L’estrazione risulta quindi immediata (se la coda è ordinata in modo decrescente si estrae il primo), mentre l’inserimento è più complesso.

Con questo algoritmo si riducono i tempi medi di attesa dei processi in coda.

Considerando l’esempio precedente si ha che:

I tempi di attesa in coda risultano:

TP1 = 10; TP2 = 0; TP3 = 3;

Quindi il tempo medio di attesa sarà:

(TP1 + TP2 + TP3 )/3 = 4.5

Il risultato ottenuto è decisamente migliore di quello trovato con l’algoritmo FCFS.

Questo algoritmo è ottimale nel senso che rende minimo il tempo di attesa medio per un dato insieme di processi in coda, ma non è realizzabile poiché non è nota a priori la durata della successiva richiesta della CPU da parte di ogni singolo processo.

Questo algoritmo non è adeguato per ambienti time sharing al contrario per quelli batch.

Round Robin (RR)

I processi vengono eseguiti per un intervallo di tempo definito dal sistema (time slice).

Dopo tale intervallo il processo viene inserito in fondo alla coda dei processi pronti e la CPU viene assegnata al prossimo processo prelevato dalla testa della coda. Se l’esecuzione del processo termina prima dell’intervallo che gli è stato concesso, il processo stesso rilascia volontariamente la CPU e lo scheduler seleziona il primo processo nella coda dei processi pronti. Quindi l’esecuzione di ogni processo ha una durata massima definita dal quanto di tempo.

Questo algoritmo è di tipo preemptive e quindi adatto ai sistemi time sharing.

Questo tipo di scheduling è implementato tramite una coda circolare gestita in modalità FIFO e garantisce che tutti i processi vadano in esecuzione, eliminando il problema della starvation (blocco all’infinito).

Ogni volta che lo scheduler seleziona un processo dalla coda dei processi pronti (il primo) oltre ad attivare il dispatcher per l’effettiva esecuzione del processo, imposta un timer inizializzato al quanto di tempo specificato dal sistema operativo. Allo scadere del timer il sistema invia un segnare di interruzione che blocca il processo attualmente in esecuzione, per assegnare la CPU ad un altro processo.

La scelta del quanto di tempo da dedicare ad ogni processo è fondamentale: se il sistema sceglie un intervallo troppo grande, l’algoritmo degenera nell’FCFS; se l’intervallo è troppo piccolo (al limite 0) degenera nel processor sharing, algoritmo a condivisione di processore, non realizzabile, nel quale i diversi processi hanno l’impressione che ci siano n processori reali ognuno dei quali esegue un processo diverso.

Il sistema operativo deve quindi scegliere un intervallo di tempo abbastanza piccolo da garantire l’interattività, cioè deve fare in modo che i processi brevi vengano eseguiti velocemente, ma abbastanza grande in modo da limitare l’overhead. Infatti se il quanto temporale è troppo piccolo il sistema è rallentato dai numerosi cambi di contesto. Quindi l’intervallo deve essere molto maggiore della latenza di dispatcher.

Shortest Remaining Time (SRT)

Questo algoritmo è la versione preemptive di SPNF ed è quindi idoneo al time sharing.

L’algoritmo prevede che il successivo processo sia quello con minor tempo stimato per il completamento. Con questo algoritmo si ha un overhead maggiore di SPNF in quanto è necessario determinare ed aggiornare il tempo restante e gestire il preemptive.

Priority Scheduling

Questo algoritmo assegna ad ogni processo una priorità e viene mandato in esecuzione il processo a priorità maggiore. Nel caso di processi con uguale priorità si opera con FCFS.

La priorità può essere assegnata dal sistema operativo o dal programmatore.

Nel primo caso si devono individuare delle proprietà misurabili mentre nel secondo caso la priorità del processo è generalmente funzione dell’importanza del processo.

Il priority scheduling può essere sia preemptive che non preemptive.

Il problema fondamentale di questo algoritmo è la starvation (causato dalla priorità statica): l’attesa di un processo in coda è indefinita poiché dipende dalla priorità di ogni singolo processo. In particolare, l’esecuzione dei processi con bassa priorità può essere impedita da un flusso costante di processi con priorità maggiore.

Poiché non c’è garanzia che un processo venga eseguito, si introduce il concetto di aging (si introduce la priorità dinamica): periodicamente il sistema aumenta le priorità dei processi che sono da molto tempo nella coda. In questo modo i processi con CPU burst brevi vengono eseguiti molto più velocemente. Questo concetto è utilizzato in particolare nei sistemi interattivi.

Multilevel Queue Scheduling

L’algoritmo multilevel queue suddivide la coda in diverse code ognuna delle quali ha uno specifico livello di priorità. I processi vengono assegnati staticamente ad una certa coda in base ad una specifica tipologia di priorità. Ogni coda potrà poi avere un proprio algoritmo di schedulazione.

Naturalmente sarà poi necessario effettuare lo scheduling tra le varie code.

Competizione e cooperazione

I processi gestiti dal sistema operativo possono essere indipendenti o cooperanti.

I processi indipendenti non scambiano informazioni e l’esecuzione di tali processi non è condiziona dall’esecuzione degli altri. Al contrario, due processi cooperanti si scambiano dati e le esecuzioni sono influenzate l’una dall’altra.

La cooperazione è una caratteristica utile per diverse ragioni, in particolare:

• Consente la condivisione delle informazioni tra i processi cooperanti: per esempio se due utenti devono condividere codice o dati, i processi devono cooperare.

• Aumenta il grado di parallelismo: esistono attività non sequenziali ma costituite da sottoattività che possono essere svolte concorrentemente (per esempio scrittura, stampa e compilazione) e per questo devono cooperare e sincronizzarsi.

• Modularizza il sistema: l’organizzazione a moduli semplifica il sistema. Ogni modulo può corrispondere ad un processo o un thread, l’insieme dei quali costituisce un unico programma.

Per permettere ai processi di cooperare il sistema operativo deve fornire dei meccanismi che implementino la comunicazione e la sincronizzazione delle attività dei processi.

In un sistema in cui è ammessa la cooperazione, un processo può influenzare un altro processo in esecuzione causando situazioni incoerenti o dati in uscita non attendibili.

I processi cooperanti possono condividere direttamente uno spazio logico di indirizzi, quindi il sistema operativo deve implementare dei meccanismi che assicurino una ordinata esecuzione dei processi stessi.

In ambiente multiprocesso i processi possono accedere a risorse condivise, se questi accessi non sono opportunamente controllati si può determinare la contaminazione di dati o conflitti sulle periferiche. E’ quindi necessario impedire che più di un processo possa, simultaneamente, leggere o scrivere stessi dati o usare stesse periferiche.

Si parla di race condition quando più processi accedono e manipolano gli stessi dati concorrentemente e l’esito varia a seconda dell’ordine con il quale sono avvenuti gli accessi. Per evitare questa situazione occorre assicurare che un solo processo alla volta possa modificare la variabile condivisa, condizione realizzabile tramite la sincronizzazione dei processi.

Per evitare il problema del race condition, i dati e le risorse condivise da più processi devono essere usate e manipolate da un solo processo alla volta.

Ogni processo può quindi avere nel suo codice una sezione critica, cioè una parte di programma con la quale può accedere a risorse comuni o modificare dati comuni ad altri processi. Ad un solo processo per volta è consentito eseguire la propria sezione critica: l’esecuzione delle sezioni critiche da parte dei processi deve essere mutuamente esclusiva nel tempo, cioè, quando un processo sta eseguendo una parte di codice a sezione critica, nessun altro processo può fare altrettanto.

L’esecuzione delle sezioni critiche deve essere soggetta ad alcune regole:

Mutua esclusione: Se un processo sta eseguendo la sua sezione critica, nessun altro processo può eseguire la sua sezione critica.

Progresso: Se un processo è nella sua sezione critica ed esiste un processo che vuole entrare nella sua sezione critica, l’esecuzione di quest’ultimo processo non può essere rimandata all’infinito.

Attesa limitata: Se un processo ha chiesto di entrare nella sua sezione critica, il numero di volte che si può rinviare questo accesso per concederlo ad altri processi deve essere limitato.

E’ quindi evidente che, il primo processo che entra in sezione critica obbligherà tutti gli altri a mettersi in coda di attesa. Esistono diversi metodi per attuare la mutua esclusione.

• Un primo metodo prevede la disabilitazione delle interruzioni quando un processo entra in sezione critica e la riabilitazione quando ne esce. Può però essere pericoloso consentire ad un processo utente la gestione delle interruzioni.

• Alcuni sistemi operativi hanno la possibilità di commutare dal modo multiprocesso al modo single processing eliminando così la condizione di race condition. Anche in questo caso può essere pericoloso consentire ad un processo utente la gestione di questa commutazione.

• Un altro metodo è il test and set che consiste nell’utilizzo di una variabile condivisa detta lock la quale assume valore 1 quando c’è un processo in sezione critica altrimenti vale 0. Se un processo vuole entrare in sezione critica testa la variabile lock: se vale 0 entra in sezione critica e la pone ad 1 altrimenti continua a fare il test finché non la trova a 0. L’inefficienza di questo metodo risiede nel fatto che il processo in coda spenderà molto tempo in un loop di test della variabile lock.

• Per risolvere il problema della sezione critica si usa uno strumento di sincronizzazione chiamato semaforo. Un semaforo è una variabile intera il cui accesso può avvenire solo tramite due operazioni atomiche standard, wait e signal, (atomico si riferisce al fatto che il flusso di esecuzione delle due operazioni è indivisibile).

Inizialmente ogni semaforo viene inizializzato a 1. Quando un processo P1 vuole entrare nella propria sezione critica, esegue la wait sul semaforo. Se nessun altro processo si trova nella propria sezione critica, P1 continua la sua esecuzione dopo aver decrementato il valore del semaforo. Se invece un altro processo P2 sta già eseguendo la sezione critica, P1 viene sospeso.

Quando il processo P2 esce dalla sua sezione critica esegue la signal che sblocca il processo P1. Tutte queste operazioni devono essere fatte in un’unica indivisibile azione atomica in modo da garantire che, una volta che un’operazione su un semaforo è cominciata, nessun altro processo possa accedere al semaforo fino a che l’operazione non è completata. L’atomicità è assolutamente essenziale per risolvere i problemi di sincronizzazione.

Il problema dello stallo

Si intende per sincronizzazione, quell’insieme di meccanismi che consentono ad un programma di sospendersi in attesa di un segnale da parte di un altro processo che gli consenta di riprendere l’avanzamento. Questo problema può essere risolto con l’uso dei semafori.

Un insieme di processi si trova in stato di stallo (deadlock) quando ognuno di essi è in attesa di un evento generato da un altro processo che a sua volta si trova nella stessa condizione.

Nessuno dei processi può avanzare, nessuno può rilasciare le risorse e nessuno può essere posto nello stato di ready.

In sintesi, il sistema è in deadlock poiché ogni processo dispone di una risorsa richiesta da un altro e che non può rilasciare.

Anche le risorse possono essere preemptive e non preemptive:

una risorsa preemptive può essere sottratta al processo senza conseguenze

una risorsa non preemptive non può essere tolta al processo senza conseguenze negative, solo il processo che la detiene può rilasciarla.

La riallocazione delle risorse potrebbe evitare il deadlock se le risorse fossero premptive.

Si definiscono quattro condizioni il cui simultaneo verificarsi determina un deadlock:

• Mutua esclusione: le risorse coinvolte non sono condivisibili, cioè solo un processo può usare la risorsa e quindi si accede per mutua esclusione.

• Hold and wait: un processo richiede risorse ed è in attesa di altre risorse.

• Non preemptive: le risorse già allocate non sono preemptive (sia dal kernel che dal processo).

• Condizione di attesa circolare.

I processi del sistema formano quindi una lista circolare nella quale ogni processo è in attesa di una risorsa posseduta dal successivo processo in lista.

Naturalmente il deadlock si può verificare solo in presenza di almeno due processi.

Esistono diversi modi per gestire il deadlock:

Rilevare e recuperare il deadlock: si usa un monitor che rileva l’esistenza di un deadlock ed identifica i processi e le risorse coinvolti. Si disallocano temporaneamente le risorse dei processi

in deadlock, si riportano questi processi in uno stato precedente al deadlock e si concludono alcuni processi fino a rimuovere il deadlock. Si tratta però di una tecnica molto onerosa.

Evitare il deadlock mediante una oculata schedulazione delle risorse. L’algoritmo più noto è quello del Banchiere così chiamato perché simile alla procedura che utilizzano i banchieri per decidere se un prestito può essere o meno concesso senza rischi.

L’algoritmo si evolve quindi valutando se il soddisfacimento di una richiesta può condurre in una stato sicuro o in deadlock ed in quest’ultimo caso ritarda la concessione della richiesta.

Prevenzione del deadlock: consiste nello schedulare le risorse in modo da evitare almeno una delle quattro condizioni citate in precedenza.

Infine si può cercare di evitare la condizione di coda circolare forzando i processi a richiedere le risorse in base ad un ordine crescente o decrescente. In questo modo il grafo di allocazione delle risorse non potrà mai essere circolare.

La comunicazione

Spesso i processi hanno bisogno di comunicare tra loro. Nasce quindi la necessità che l’interazione tra i processi avvenga in modo ben strutturato, mantenendo alta l’efficienza del sistema.

Per realizzare la comunicazione il sistema operativo deve implementare dei meccanismi che consentano a un processo di passare informazioni ad un altro processo in modo sequenzialmente corretto.

I processi concorrenti in esecuzione sotto il controllo del sistema operativo, possono essere indipendenti o cooperanti. I processi indipendenti non scambiano informazioni e la loro esecuzione non è condiziona dall’esecuzione degli altri. Due processi cooperanti al contrario si scambiano dati e le esecuzioni sono influenzate l’una dall’altra.

Come già detto, la cooperazione è una caratteristica utile per diverse ragioni, in particolare:

• Consente la condivisione delle informazioni tra i processi cooperanti; per esempio se due utenti devono condividere codice o dati i processi devono cooperare.

• Aumenta il grado di parallelismo; esistono attività non sequenziali ma costituite da sottoattività che possono essere svolte concorrentemente e per questo devono cooperare e sincronizzarsi.

• Modularizza il sistema; l’organizzazione a moduli semplifica il sistema.

Per permettere ai processi di cooperare il sistema operativo deve fornire dei meccanismi che implementino la comunicazione e la sincronizzazione delle attività dei processi. Esistono due tecniche diverse per lo scambio di dati tra processi:

Modello a memoria comune: i due processi condividono una area di memoria comune tramite la quale cooperano. Un processo scrive i dati nell’area comune, l’altro li legge.

Modello a scambio di messaggi: modello basato sullo scambio di messaggi tra processi. Il sistema operativo provvede a recapitare i messaggi al destinatario implementando funzioni apposite a questo scopo.

Per illustrare il modello a memoria comune si consideri il problema del produttore e del consumatore che è un classico paradigma per processi cooperanti.

Un processo produttore produce informazioni che sono consumate da un processo consumatore.

Per permettere un’esecuzione concorrente dei processi, occorre disporre di un vettore (buffer) in cui il produttore può inserire un elemento mentre il consumatore ne sta prelevando un altro, facendo attenzione alla capacità del vettore.

Nascono quindi due problemi:

Sincronizzazione tra i processi consumatore e produttore: il prelievo di un dato da parte del consumatore deve avvenire dopo che il produttore lo ha inserito nel buffer.

Grandezza dell’area di memoria comune: se la memoria è illimitata, non ci sono limiti alla grandezza del buffer e il produttore può sempre produrre dati; se la memoria è limitata il buffer avrà una lunghezza massima e il produttore prima di inserire un dato nel buffer deve controllare che non sia pieno. In entrambe le situazioni il consumatore, prima di prelevare un dato, deve sempre controllare che il buffer non sia vuoto.

Un metodo alternativo con cui il sistema operativo può ottenere gli stessi risultati ottenuti con il modello a memoria comune consiste nel fornire gli strumenti per la comunicazione tra processi, realizzando ciò che comunemente prende il nome di sistema di comunicazione tra processi (IPC:

Inter Processing Communication).

Il modello IPC è particolarmente utile in un ambiente distribuito dove i processi comunicanti possono risiedere in diversi calcolatori connessi da una rete.

Le due operazioni fondamentali che costituiscono il modello IPC e che permettono ai processi di comunicare e sincronizzarsi senza condividere dati sono due:

- operazione send(message), - operazione receive(message).

I processi che vogliono comunicare con il modello a scambio di messaggi possono farlo grazie alla presenza di un canale di comunicazione, realizzabile in molti modi sia logicamente che fisicamente.

Per comunicare i processi devono disporre di un modo con cui riferirsi agli altri processi.

A secondo di come si implementa questa caratteristica si distinguono due differenti sistemi:

1. Comunicazione diretta.

Con la comunicazione diretta, ogni processo che intenda comunicare deve nominare esplicitamente il ricevente o il trasmittente della comunicazione.

Nella comunicazione diretta il canale ha le seguenti caratteristiche:

• i canali sono creati automaticamente;

• tra ogni coppia di processi esiste un canale

• i processi per comunicare devono conoscere solo la reciproca identità;

• un canale è associato esattamente a due processi;

• il canale può essere unidirezionale o, più spesso, bidirezionale.

2. Comunicazione indiretta.

I messaggi vengono inviati a delle mailbox (chiamati anche porte) e da essi ricevuti. La mailbox è un oggetto in cui i processi possono introdurre e da cui possono prelevare i messaggi.

Nella comunicazione indiretta due processi possono comunicare solo se hanno una mailbox in comune.

In questo schema le primitive send e receive hanno il seguente formato:

send(A, message); invia il messaggio alla mailbox A;

receive(A, message); riceve un messaggio dalla mailbox A.

Il canale di comunicazione ha le seguenti caratteristiche:

• tra una coppia di processi si stabilisce un canale solo se entrambi i processi della coppia condividono una mailbox;

• un canale può essere associato a più di due processi;

• tra ogni coppia di processi comunicanti possono esserci più canali diversi, ciascuno corrispondente a una porta.

Gestione dell’I/O

Il sistema operativo si deve occupare della gestione dell’I/O eseguendo i comandi destinati ai dispositivi fisici, rimuovendo le condizioni di errore e risolvendo i problemi dovuti alla diversità delle caratteristiche dei vari dispositivi. A tale scopo fornisce una interfaccia comune a tutti i dispositivi, diposta tra i dispositivi fisici e il resto del sistema.

Con la sigla I/O si identificano delle unità fisiche che possono essere:

• Dispositivi fisici di ingresso uscita (device)

• Unità di controllo dei device in grado di gestire polling, interrupt o DMA con registri di I/O e buffer (I/O controller)

• Processori di I/O in grado di alleggerire il lavoro della CPU

I compiti che un sistema operativo deve eseguire nella gestione dell’I/O sono:

• Stabilire a quale processo assegnare un device e per quanto tempo

• Mantenere traccia dello stato del device

• Allocare fisicamente il device al processo

• Deallocare il device dal processo

Sono infine necessari dei componenti software detti device driver i quali sono specifici per ogni device ed operano da interfaccia software tra il sistema operativo ed il device vero e proprio gestendo le operazioni di I/O, le interruzioni e gli errori.

I device di I/O sono generalmente costituiti da parti elettromeccaniche con un funzionamento spesso asincrono rispetto alla CPU rendendo così più complessa la loro gestione.

L’hardware di I/O è costituito dai dispositivi di I/O e dai relativi controllori.

I dispositivi possono differire sotto molti aspetti. Per quanto riguarda il trasferimento dei dati si distinguono:

• Trasferimenti a blocchi di dati o a stringhe di caratteri. I dispositivi a blocchi memorizzano le informazioni in blocchi di lunghezza fissa, ognuno dei quali ha un proprio indirizzo ed ogni blocco può essere indirizzato in maniera indipendente dagli altri. I dispositivi a caratteri operano invece su flussi di caratteri.

• Trasferimenti seriali o paralleli. I dispositivi seriali inviano o ricevono un bit alla volta, i dispositivi paralleli trasferiscono più bit contemporaneamente.

• Trasferimenti sincroni, che hanno tempi di risposta prevedibili, o asincroni, in cui i tempi di risposta non sono prevedibili.

• Dispositivi che consentono solo la lettura, solo la scrittura o entrambe le operazioni. Le operazioni di lettura e scrittura vengono eseguite su un blocco o su un carattere a seconda del tipo di dispositivo.

La modalità di accesso al dispositivo può essere sequenziale se il trasferimento avviene secondo un ordine fisso, oppure casuale, se si accede direttamente ad una qualunque locazione di memoria.

Inoltre si distinguono i dispositivi condivisi, utilizzati da più utenti simultaneamente, da quelli dedicati ai quali può accedere un utente alla volta.

La velocità di funzionamento è generalmente diversa per ogni dispositivo.

Il software deve garantire buone prestazioni su sequenze di dati di diversi ordini di grandezza.

La gestione dell’I/O viene suddivisa in tre livelli:

• Il primo livello consiste nella definizione delle operazioni di sincronizzazione e trasferimento delle informazioni tra device e processi. Le funzioni di questo livello rendono trasparenti all’utente i meccanismi hardware e software usati.

Il trasferimento delle informazioni può avvenire per mezzo dei registri del processore o per mezzo del gestore del DMA.

• Il secondo livello consente l’interfacciamento tra i processi ed i device in modo indipendente dalle caratteristiche del device stesso. Tutto ciò avviene per mezzo dello specifico driver del device il quale traduce i comandi provenienti dal software di sistema in comandi e segnali interpretabili dall’hardware del device.

• Il terzo livello (detto Virtual File System) realizza una interfaccia uniforme per i processi utenti che potranno così utilizzare un unico sistema di nomi per i device con uno schema di accesso simile a quello dei file. Questo livello comprende anche le politiche mediante le quali il sistema operativo ottimizza le prestazioni dell’utilizzo dei device.

Il sistema operativo permette l’aggiunta di nuovi dispositivi e la modifica delle caratteristiche di quelli preesistenti. Poiché ogni dispositivo ha caratteristiche diverse, il sistema astrae dai dettagli dei dispositivi individuando alcuni tipi generali per ognuno dei quali definisce una interfaccia. Le effettive differenze tra i vari dispositivi saranno poi gestite dai driver specifici.

Inoltre la parte del sistema operativo che si occupa dell’I/O deve:

• Garantire l’indipendenza del sistema dai dispositivi. Il codice del programma dal quale si accede ad un dispositivo deve essere indipendente dal tipo di dispositivo, ovvero il codice per essere eseguito su dispositivi diversi non deve essere modificato.

• Gestire una denominazione uniforme dei dispositivi. Un dispositivo deve avere il solito nome (file system o cdrom, o dischetti…). Tutti i file e i dispositivi sono indirizzati nello stesso modo, utilizzando uno specifico path name.

• Gestire il trattamento degli errori. La maggior parte degli errori sono temporanei e non si ripresentano se l’operazioni viene ripetuta, quindi possono essere gestiti dal driver di dispositivo, se non riesce il controllore, semplicemente rieseguendo il comando. In ogni caso è preferibile che l’utente finale non si accorga degli errori, quindi devono essere gestiti al livello più basso, più vicino all’hardware. Solo se i livelli più bassi non sono in grado di gestire l’errore vengono avvertiti i livelli alti.

• Gestire il trasferimento delle informazioni. Si distingue in trasferimento sincrono (a controllo di programma) e trasferimento asincrono (a controllo di interruzioni o DMA). La maggior parte dell’I/O è asincrono, ma i programmi utenti sono più semplici se le operazioni di I/O sono sincrone. Il sistema deve mascherare all’utente il vero aspetto delle operazioni facendole apparire sincrone.

Un’altra funzione del sottosistema di I/O è il buffering: esiste una area della memoria in cui vengono memorizzati i dati trasferiti tra due dispositivi, o tra un’applicazione e un dispositivo.

Questa zona è chiamata buffer.

Senza la bufferizzazione delle informazioni, un processo viene bloccato in attesa che venga portata a termine una operazione di I/O. Viene sbloccato ogni volta che arriva un dato, quindi torna nello stato bloccato dopo il suo trasferimento.

La bufferizzazione viene fatta dal sistema operativo per conto del processo: i dati da trasferire al processo vengono mantenuti in un buffer e solo quando l’operazione di I/O è terminata il processo viene sbloccato e i dati trasferiti tutti in una volta dal buffer al processo stesso.

La bufferizzazione può essere utile anche per gestire la differenza di velocità di trasferimento dei dati tra processi (per esempio nel caso di processo produttore e processo consumatore).

Infine il sottosistema di I/O deve rendere possibile la condivisione delle risorse. Le risorse condivisibili, per esempio il disco, non causano problemi. Esistono però risorse non condivisibili a cui pervengono contemporaneamente più richieste. In questa situazione non è conveniente che la gestione del dispositivo venga svolta dal processo, ma è il sistema operativo che, tramite lo scheduling di I/O, stabilisce un ordine di esecuzione efficace delle richieste di I/O.

Per ogni dispositivo esiste una coda delle richieste (device queue); quando una applicazione esegue una system call di I/O bloccante, la richiesta è aggiunta nella coda relativa al dispositivo appropriato. Lo scheduler di I/O riorganizza la coda per migliorare le prestazioni, offrendo una migliore efficienza globale del sistema e una diminuzione del tempo di attesa delle applicazioni.

Classificazione dei device

I device possono essere classificati per tipo di funzione, tempo di accesso, tipo di accesso, velocità di trasferimento, codifica dei dati, tipologia dei comandi e condizione di errore.

In base alla funzione si ha:

• Human readable: usati per comunicare con gli utenti (terminali, tastiere, mouse, stampanti, ecc.)

• Machine readable: usati per la comunicazione tra altri sistemi elettronici (sensori, attuatori, ecc.)

• Communication: usati per comunicare con dispositivi remoti

• Memory device: usati per la memorizzazione delle informazioni

Il tempo di accesso è definito come l’intervallo di tempo che intercorre tra l’istante di richiesta dell’informazione e l’istante in cui questa è disponibile.

In base al tipo di accesso si ha:

• Accesso sequenziale: sono device per i quali il tempo di accesso dipende dalla posizione del dato e presenta quindi grandi oscillazioni del suo valore.

• Accesso casuale: sono device per i quali il tempo di accesso è costante.

• Accesso quasi casuale: sono device per i quali il tempo di accesso presenta una lieve dipendenza dalla posizione del dato.

Un’altra classificazione riguarda l’impacchettamento dei dati trasferiti che possono essere a blocchi (hard disk, CD ROM, stampanti) o a carattere (terminali, modem).

Per quel che riguarda le velocità di trasferimento, queste possono avere grandi differenze.

Struttura del software di I/O

Il software di I/O è organizzato in quattro livelli:

Livello utente SW I/O LIVELLO UTENTE

⇓

SW I/O INDIPENDENTE DAI DISPOSITIVI

⇓

DRIVER DEI DISPOSITIVI

⇓ SW di I/O

Livello kernel

DRIVER DELLE INTERRUZIONI

HW di I/O HARDWARE

• La gestione delle interruzioni creata nell’hardware di I/O è completata dal driver delle interruzioni. La gestione delle interruzioni non è semplice perché comporta l’esecuzione di una serie di operazioni eseguite via software dal driver delle interruzioni, dopo che l’interruzione hardware è stata avviata (nel livello hardware di I/O).

• Il driver di un dispositivo comanda l’operazione richiesta (read o write) poi si blocca perché l’operazione di I/O richiede del tempo. Il driver viene bloccato da una interruzione provocata dal driver delle interruzioni.

Indipendentemente dall’algoritmo di scheduling scelto si può verificare che, durante l’intervallo di tempo in cui il driver è bloccato, un processo si sblocchi. Al termine dell’operazione di I/O il processo che va in esecuzione è quello con priorità maggiore, mentre l’altro processo viene inserito in una coda di attesa.

• Il livello del driver dei dispositivi gestisce la diversità delle caratteristiche dei dispositivi fisici e rende indipendente il livello superiore dai particolari dispositivi. E’ costituito da un insieme di driver, uno per ogni dispositivo presente o uno per una classe di dispositivi con caratteristiche simili. In fase di installazione del dispositivo fisico il sistema operativo carica anche il corrispondente driver. Se il sistema operativo implementasse un unico driver per rappresentare tutti i dispositivi, tale driver dovrebbe raggruppare tutte le diverse caratteristiche che può assumere un dispositivo ed avrebbe dimensioni enormi.

Per rendere trasparenti le caratteristiche dei dispositivi, il sistema operativo definisce una interfaccia tra il livello del driver di dispositivo e il livello del software di I/O indipendente dai dispositivi. Tale interfaccia permette ai diversi driver dei dispositivi di fornire al livello superiore un numero limitato di funzioni, del tipo:

- “write / read un carattere”, se il dispositivo trasferisce caratteri;

- “write / read un blocco”, se il dispositivo trasferisce blocchi.

Queste procedure possono essere chiamate dal resto del sistema per interagire con il driver del dispositivo.

• L’interfaccia definita a livello utente è generale, composta da funzioni limitate e tutte dello stesso tipo per tutti i dispositivi: il livello del software di I/O indipendente dai dispositivi invia le funzioni al livello del driver di dispositivo che ha il compito gestirle opportunamente.

Il driver accetta e traduce il comando di carattere generale in una sequenza di comandi relativi ad un dispositivo, in un linguaggio di più basso livello, adatti per il controllore che il driver gestisce.

A questo punto il controllore insieme al driver cominciano ad eseguire l’operazione richiesta: in alcuni casi questa fase risulta veloce, altre volte il completamento delle operazioni comporta una perdita di tempo non trascurabile per il driver di dispositivo che è in attesa attiva. In questa situazione il driver di dispositivo controlla lo stato del dispositivo:

• Dispositivo occupato: inserisce la richiesta in attesa in una coda (coda delle richieste pendenti);

quando il dispositivo si libera, la scelta della richiesta da servire viene fatta secondo un algoritmo di scheduling.

• Dispositivo libero: il driver traduce l’istruzione e invia al dispositivo di I/O il comando, poi si blocca in attesa dell’istruzione di ritorno eseguita dal dispositivo di I/O.

Gestione dei dischi

Gli hard disk rappresentano la più importante tra le unità di I/O di un sistema di elaborazione in primo luogo per la grande quantità di dati che possono conservare e per l’importanza che questi dati possono avere. La parte principale è rappresentata dai file del sistema operativo che vengono movimentati per la gestione di tutti i vari servizi offerti dal sistema operativo stesso.

Gli hard disk sono costituiti da un insieme di dischi rotanti sullo stesso asse (7200 giri/min) e ricoperti di materiale magnetico. Ogni faccia del disco contiene un insieme di tracce circolari concentriche. Le tracce corrispondenti delle diverse facce costituiscono un cilindro. I dischi vengono letti o scritti da un insieme di testine magnetiche che volano ad una microscopica distanza dalla superfice del disco e sono movimentate da un braccio ad altissima precisione.

Le tracce sono suddivise in settori di capacità fissa (da 512 a 4096 byte), i settori consecutivi sono separati da piccoli intervalli non magnetizzati detti gap.

I settori del disco rappresentano la minima unità di trasferimento hardware.

Via software è possibile definire una nuova unità minima di trasferimento multipla intera del settore che viene denominata cluster.

Ogni settore è diviso in tre parti:

• Preambolo: contiene le informazioni di controllo (numero della traccia, numero del settore…).

• Dati: contiene i dati.

• ECC (Error Correcting Code): contiene il codice a correzione di errore. Contiene sufficienti informazioni affinché il controllore possa identificare i bit danneggiati e ricalcolare il loro corretto valore.

Preambolo Dati ECC

Testina

Braccio

Motore Disco

Cilindro Traccia

Traccia

Settore Gap