Gestione dell/I/O

Introduzione
Gestione di un disco
Algoritmi di schedulazione lettura/scrittura
Gestione del clock
Schema generale dell'I/O su Minix
Clock driver in Minix
 
 

Introduzione (Indice )

• Device independence: i programmi devono essere scritti in modo quanto piu' possibile indipendente dallo specifico device che sara' utilizzato.
• Uniform naming: deve essere possibile individuare ciascuna classe di device e ogni singolo device all'interno della classe in modo uniforme e non dipendente dal particolare modello hardware. Il file system deve poter essere strutturato in modo indipendente rispetto ai device di supporto.
• Error handling: la gestione dell'errore deve avvenire il piu' possibile vicino all'hardware. Solo errori non trattabili a basso livello devono filtrare a livelli superiori.

Combinazione della gestione sincrona e asincrona dell'I/O: dal punto di vista dell'utente la gestione dell'OI/O e' un'attivita' sincrona, dal punto di vista del sistema operativo si tratta di una attivita' asincrona (interrupt driven).

Principi generali di hardware per I/O

Abbiamo due livelli:

1. device driver (parte software)
2. device controller (parte elettronica di controllo e parte meccanica o elettromeccanica)

I dispositivi (quasi tutti) possono essere classificati in block device e character device.

Block device: dischi, nastri, floppy, CDROM
E' possibile leggere ciascun blocco in modo indipendente dagli altri. E' caratterizzato dalla dimensione del blocco (128, ..., 1024 byte).

Character device: terminali, stampanti, network interface...
gestiscono l/I/O come una stringa di caratteri.

Esistono anche altri device non classificabili (es. clock)

Struttura di un device

Parte meccanica/  --->   interfaccia        ----->   controller
elettromeccanica         controller device

Controller: e' la parte elettronica che consente di guidare il device fisico vero e proprio, ed e' anche l'interfaccia tra il device ed il software. Si tratta di un componente molte volte assimilabile ad un elaboratore dedicato.

Interfaccia tra il controller e il device

E' di basso livello

ESEMPIO: disco
Il diver produce una sequenza di bit introdotta da un preambolo, seguito dai bit trasmessi, e quindi da un valore di checksum o codice di correzione dell'errore (ECC).
La sequenza di bit (lunga ad esempio 4096 bit per un disco formattato con 8 settori da 512 byte) e' convertita in un blocco dal controller che esegue le eventuali azioni di correzione dell'errore.

Architettura tipo minicomputer a single bus:

Alcuni controller possono essere interfacciati con piu' device dello stesso tipo.

Comunicazione controller-CPU

• avviene attraverso alcuni registri del controller che

• possono far parte dello spazio di indirizzamento di memoria "normale", riferibili con le normali operazioni a particolari indirizzi (es. move).
• possono essere trattati come spazio di indirizzamento riservato e accessibile solo tramite operazioni proivilegiate particolari (es. out).
• puo' beneficiare della possibilita' del controller di lavorare in DMA (Direct Memory Address). E' utilizzato in particolare per gestire device a blocchi
• e' interrupt based.

• La CPU invia comandi al controller  scrivendo il codice del comando ed eventuali parametri nei registri del controller. Per i floppy del PC i comandi sono 15 , del tipo: READ, WRITE, SEEK, FORMAT, RECALIBRATE, ...
• Inviato il comando la CPU puo' continuare il suo lavoro.Quando il controller ha completato il comando provoca un interrupt per ottenere l'attenzione della CPU che legge nei registri del controllre i risultati dell'operazione richiesta.
• Il DMA consente di rendere piu' veloce quest'ultima fase.
• I bit ottenuti dal disco sono memorizzati nel buffer del controller sino a che si e' letto un blocco.
• Il controller accede in modo autonomo alla memoria e trasferisce il contenuto del suo buffer direttamente in memoria senza intervento della CPU. A questo punto la CPU e' risvegliata attraverso un interrupt.
• I registri del controller individuano i parametri dell'operazione. Doppio lavoro del controller: richiede una opportuna organizzazione dei blocchi su disco.

Organizzazione fisica:

• Cilindri: posizione radiale della testina di lettura/scrittura
• Per ogni cilindro abbiamo tante tracce quante testine o superfici di lettura sono presenti
• Ciascuna traccia e' divisa in settori (10-100, 8-32)
• Tutti i settori contengono lo stesso numero di byte (32-1024), quindi i settori piu' esterni hanno dimensione fisica maggiore di quelli interni (si perde un po' di spazio).

Le operazioni di trasferimento partono sempre dall'indirizzo di un settore.
Operazione di seek: posiziona la testina sul cilindro desiderato (seek time circa 5-100 millisec.)

Come Minix vede un floppy per PC-IBM (360K):

Numero di cilindri:               40
Tracce per cilindro:               2
Settori per traccia:               9
Settori per dischetto:           720
Bytes per settore:               512
Byte per dischetto:           368640
Seek time (cilindro adiacente):    6 millisec.
Seek time (caso medio):           77 millisec.
Rotational time:                 200 millisec.
Motor start/stop time:           250 millisec.
Time to transfer 1 sector:        22 millisec.

Il trasferimento avviene quando il primo settore passa sotto la testina (rotational delay <= 20 millisec.).
Il software di Minix usa blocchi da 1K quindi legge/scrive 2 settori consecutivi per volta.

Software per la gestione del disco

Il software per effettuare un'operazione di trasferimento dati da/a disco deve fornire al controller:

• Il cilindro e la superficie per individuare la traccia,
• Il numero del settore dal quale partire,
• Il numero di byte o blocchi da trasferire
• L'indirizzo di memoria al/dal quale trasferire i dati
• Il codice dell'operazione (R/W)

Considerazione: il tempo di lettura/scrittura e' determinato da seek time, rotational delay, actual transfer time.

Il software per lagestione della lettura/scrittura disco puo' accettare anche piu' richieste, che vengono memorizzate su di una tabella, per poi schedularne l'esecuzione, in modo da ottimizzare i tempi.
Il task di Minix per la gestione del disco, invece, accetta una sola richiesta alla volta.

Questi algoritmi considerano le richieste di trasferimento dati facendo riferimento al numero di cilindro indirizzato. (tentativo di minimizzare il seek time medio).
Utilizzano una struttura dati costituita da una tabella indiciata in base al numero del cilindro. Per ogni entry abbiamo una lista di richieste pendenti per quel cilindro.

Esempio

• Disco da 40 cilindri
• Richiesta iniziale per cilindro 11
• Durante il seek time per arrivare al cilindro 11  arrivano nell'ordine le richieste: 1, 36,16, 34, 9, 12.

1. FCFS: nessuna ottimizzazione
2. SSF: puo' essere unfair
3. Elevator: ha un upper bound di 2 * (numero di cilindri)

FCFS First Come First Served
Soddisfa le richieste nell'ordine in cui arrivano. Nell'esempio abbiamo 111 spostamenti unitari. SSF Shortest Seek time First
La prossima richiesta soddisfatta e' quella relativa al cilindro piu' vicino. In genere questo algoritmo tende a mantenere la testina posizionata nel centro del disco  quando ci sono dischi molto carichi e molte richieste, e potrebbe esserci starvation. Nell'esempio 61 spostamenti. Elevator

• Mantiene un bit con valore up oppure down.
• Quando il bit e' up, viene scelto il cilindro piu' vicino, con numero maggiore di quello su cui e' posizionata la testina
• Quando il bit e' down, viene scelto il cilindro piu' vicino, con numero minore di quello su cui e' posizionata la testina
• Se non ci sono richieste con numero di cilindro maggiore o minore (a seconda del valore del bit), si inverte il valore del bit, finche' non sono state soddisfatte tutte le richieste.

Questo algoritmo ha la proprieta' che per qualunque insieme di richieste il numero massimo degli spostamenti e' 2*(numero di cilindri). Nell'esempio 60 spostamenti.
Una variante dell'algoritmo prevede uno scanning circolare della tabella, mantenendo quindi una sola direzione per il bit (che a questo punto non serve piu'). Si evita cosi' che alcune richieste agli estremi del disco siano penalizzate.
 

Si tratta di un dispositivo atipico perche' non corrisponde ad uno special file di tipo block o carattere. Distinguiamo subito fra clock hardware e clock sftware:

• clock hardware: genera interrupts ad intervalli di tempo noti.
• clock software: e' generalmente un device driver che realizza funzioni per:
• Mantenere il tempo reale (data...)
• Realizzare il time-slice (quanto di tempo)
• Gestire le system di tipo "alarm" (da processi utente)
• Gestire i time-out di sistema o watchdog
• Fornire informazioni per l'accounting della CPU ed altre statistiche.

Clock semplici: sono collegati alla rete (110-220 Volt) e generano interrupt ad ogni ciclo (50-60 Hz).

Clock programmabili (livello base): sono formati da 3 componenti:

• cristallo di quarzo (oscillatore)
• contatore
• registro

Il cristallo genera un segnale periodico molto preciso (1-100MHz), che e' inviato al contatore, provocandone un decremento.
Quando il contatore arriva a zero, genera un interrupt diretto alla CPU.

• One shot mode: all'avvio del clock il contenuto del registro e' copiato nel contatore, il valore del contatore e' decrementato ad ogni impulso del cristallo. Quando il contatore arriva a zero si genera un interrupt e il clock si ferma fuinche' non viene riavviato via software, provocando la riscrittura del registro (eventualmente modificato nel frattempo) nel counter.
• Square-wave mode: quando il contatore arriva a zero ed e' generato l'interrupt, il contenuto del registro e' copiato nel contatore e quindi si riparte. L'intero procedimento e' ripetuto indefinitamente. Gli interrupt periodici sono chiamati clock tick.

Vantaggi dei clock programmabili
Si puo' controllare via software la frequenza degli interrupt. Con un cristallo a 1 MHz ad esempio, si ha 1 impulso ogni microsecondo. Usando un contatore a 16 bit si possono programmare interrupt ad intervalli da 1 microsecondi a 65536 millisecondi.

Mantenimento della data.

E' importante mantenere la data  in modo che il suo aggiornamento, che deve essere fatto ad ogni tick, sia il piu' veloce possibile. Vediamo il sistema usato da Unix.
Si sceglie una data iniziale di riferimento, ad esempio 01/01/1970 12:00:00.
Quando viene impostata la data odierna, questa viene trasformata nell'equivalente numero di tick a partire dalla data di riferimento. Ad ogni tick il numero e' incrementato.
Il problema e' il possibile overflow nel mantenimento di tale numero. Ad esempio con avendo un clock a 60 Hz e un contatore a 32 bit, c'e' un overflow ogni 2 anni circa.
Si possono trovare diverse soluzioni:

• usare un registro a 64 bit (soluzione hardware) oppure 2 registri a 32 bit, con la possibilita' di usare istruzioni assembler in doppia precisione.
• mantenere un registro di 32 bit con la memorizzazione de secondi, e un altro con la memorizzazione dei tick del secondo attuale. Dura piu' di 136 anni.
• usare non una data di riferimento, ma il tempo di bootstrap in secondi mantenuto in un registro, piu' un altro registro con il numero di tick dal bootstrap.

Realizzazione del time-slice

Ad ogni processo e' associato un contatore in cui e' memorizzato il "quanto" di tempo assegnato al processo stesso in numero di tick. Ad ogni clock interrupt il contatore e' decrementato dal clock driver. Quando il contatore diventa zero, il processo ha esaurito il suo quanto.

Gestione delle system call di tipo "alarm"

Queste system call sono utilizzabili dai programmi utente per ricervere un "warning" (in Unix ha la forma di un signal) dopo un certo intervallo di tempo. In presenza di piu' richieste di questo tipo, il problema che si pone e' quello di simulare piu' clock virtuali con un unico clock fisico, nel modo piu' "veloce" possibile.
Possibile soluzione (usata da Minix): si utilizza una lista di elementi, uno per ogni processo che ha un alarm pendente, ordinata in base ai tempi succesivi di scadenza dell'allarme. Ogni elemento contiene un numero che indica dopo quanti tick di tempo va emesso un signal (a quel processo) dopo che quell'elemento e' diventato il primo della lista. Il numero dell'elemento al top viene decrementato ad ogni tick, il signal e' emesso quando il numero si annulla, e l'elemento e' cancellato dalla lista.

Esempio:

La lista corrisponde ad un elenco di processi che richiedono rispettivamente un signal agli istanti di tempo:  4203  4207  4213  4215  4216.

Realizzazione del watchdog

Il meccanismo utilizzato e' simile a quello per gli allarmi. In questo caso il clock software, anziche' inviare un signal al processo richiedente, attiva una procedura che gli e' stata fornita dal processo chiamante. Un esempio e' l'arresto del motore per il floppy.

Accounting della CPU

Per avere una accurata misurazione e' meglio usare un supporto hardware. Solitamente nei clock chip ci sono piu' di un timer. Si utilizza allora un secondo timer che si fa partire quando si avvia il processo e si ferma quando il processo termina.
Metodo meno accurato: Si associa un contatore software al processo.
 
 

• User Process: effettuazione dell'I/O call, formattazione dell'I/O, spooling.
• Device independent software: Naming, protection, blocking, buffering, allocation,error reporting.
• Device drivers: setup device registers, state control.
• Interrupt handlers: risveglia il driver quando l'operazione di I/O e' completata.
• Hardware: esegue le operazioni di I/O

Il Device independent software trasforma nomi simbolici di device in riferimenti al driver corrispondente.

Esempio

/dev/fd0
Nell'entry fd0 del file directory /dev viene identificato l'i-node di un file speciale che contiene il major e minor device number.
Il major DN identifica il driver, il minor DN e' un parametro passato al driver, che serve ad identificare eventuali diverse unita' dello stesso tipo.
Usi possibili:
mknod   /dev/fd0   b   2   0
mount   /dev/fd0   user
mkfs   /dev/fd0   360

Per ogni classe di device di I/O esiste uno specifico task di I/O (device driver).
Tale driver e' eseguito come processo.

I task di Minix comunicano con gli altri processi esclusivamente attraverso scambio di messaggi. I processi utente non possono comunicare direttamente con i task, ma possono utilizzarli tramite il server File System (FS).

1. Richiesta di servizio
3. Messaggio richiesta servizio al task per I/O
2. Risposta del task
4. Esito operazione

Esempio di struttura di un messaggio di richiesta di servizio per un device a blocchi (disco)

  m.m_type (INT)        --> tipo di operazione
  m.m_device *(INT)     --> minor device number
  m.position (LONG)     --> posizione all'interno del device
  m.PROC_NR (INT)       --> identificatore processo utente chiamante
                            (indice nella proc. table)
  m.m_source            --> identificatore server chiamante
  m.address (CHAR)      --> indirizzo all'interno del task
  m.count (INT)         --> dimensione di trasferimento

Messaggio di Risposta:

  m.m_type (INT)        --> sempre "TASK_REPLY"
  m.REP_PROC_NR (INT)   --> come proc_nr in chianata
  m.REP_STATUS (INT)    --> bytes trasferiti o codice di errore.

Struttura tipica di un task di I/O

message msg       /* buffer per il messaggio */

io_task ()
{
......
int  r, caller, proc_nr
initialize ();      /* eseguito solo allo startup */
while (TRUE)  
   {
   receive (ANY, &msg);   /* attende una richiesta */
   caller = msg.m_source  /* server dal quale arriva la richiesta */
   proc_nr = msg.PROC_NR  /* proc. utente richiedente */
   ......
   switch (msg.m_type)
      {
      case READ:  r = do_read(); break;
      case WRITE: r = do_write(); break;
      case OTHER: r = do_other(); break;
      default:    r = ERROR
      }
   msg.m_type = TASK_REPLY;
   msg.REP_STATUS = r;    /* return code */
   send (caller, &msg);    /* send reply back */
   }
}

Nota: i task hanno una struttura strettamente sequenziale, come i server. Possono cioe' accogliere una sola richesta alla volta. Un task di I/O, dopo aver effettuato una richiesta di I/O all'hardware, si sospendeattendendone la risposta (sotto forma di interrupt), ad esempio in do_read(). Ogni altra richiesta e' sospesa finche' il servizio attuale non e' completato (principio del rendez-vous). I server hanno una struttura analoga.

Ciascuna procedura do_xxx soddisfa una richiesta specifica e restituisce uno status code che dice cosa e' accaduto durante lo svolgimento dell'operazione. Questo codice e' restituito al server chiamante.

Maggiori informazioni sulla struttura del device per disco fisso di Minix si trovano sul file minix_device.html
 

Il driver del clock di Minixe' contenuto nel file clock.c nel la directory kernel. La struttura generale e' quella del task descritto precedentemente.
Il clock task inizializza il clock (i8253) utilizzando la procedura init_clock.
Esegue quindi un loop senza fine nel quale provvede a ricevere i messaggi ed eseguire i servizi richiesti.

Possibili richieste:

• set_alarm (process#, procedure to call, delay)
• get_time
• set_time  (new time in sec.)
• clock_tick  (e' la procedura eseguita all'interrupt del clock)

Variabili utilizzate

realtime: contatore incrementato ad ogni tick
boot_time: con realtime consente di avere il tempo attuale
next_alarm: tempo al quale attivare il prossimo allarme.
sched_ticks: numero di tick alla prossima chiamata dello scheduler.
watch_dog: array che memorizza la procedura indicata dai task
lost_ticks: numero di tick persi (aggiornata ad ogni interrupt)

E' permesso avere un solo allarme pendente per processo. Viene infatti riservata una sola word nella tavola dei processi per memorizzare l'allarme.

Procedure importanti

set_alarm e' gestita dalla procedura do_setalarm. I messaggi arrivano dal MM su richiesta di un processo utente, oppure dagli I/O task per settare dei time-out. In quest'ultimo caso il task chiamante specifica anche la procedura da eseguire allo scadere del tempo. La procedura setta i parametri di allarme e poi scandisce la lista dei processi per individuare il primo allarme in scadenza. Il valore piu' basso trovato e' caricato in "next alarm" (non e' cioe' mantenuta una lista ordinata).

get_time: procedura do_get_time. Restituisce il tempo calcolato da "boot time" + realtime.

set_time: procedura do_set_time. Assegna il tempo di boot come new_time - realtime. Nota: i tempi vanno intesi come colpi di clock da 01/01/1970.

clock_tick: e' gestito da do_clock_tick. Il messaggio in questo caso e' generato dall'interrupt di click (proviene dal finto processo HARDWARE).

• La procedura aggiorna il conteggio dei colpi di clock non serviti e memorizzati in lost_ticks. Ricordare che quando arriva un interrupt da clock, la procedura interrupt , se non trova il clock task in attesa di un messaggio (perche' e' gia' impegnato a fare altro) aggiunge 1 alla variabile lost_ticks.
• Si controllano poi gli allarmi scaduti. Se il primo allarme e' scaduto allora anche piu' di uno puo' esserlo.
• A fronte di un allarme scaduto si effettua la segnalazione con un messaggio a MM per processi utente, o attivazione della procedura di time-out per i task di I/O.
• Chiamata della procedura di accounting che addebita un colpo di clock allo user time o al system time del processo sotto accounting (individuato dalla variabile bill_ptr).
• Eventuale chiamata allo scheduler.

Negli aa. 1996/97 e 1998/99 sono state svolte due esercitazioni relative all'implementazione di driver per scheda grafica e mouse. E' possibile consultare la documentazione relativa, con la descrizione di questo tipo di driver.

Prima Esercitazione 1996/97.

Prima Esercitazione 1998/99.