Modulo 10: Gestione dei dispositivi di...

Sistemi Operativi Laface 200110.1

Modulo 10: Gestione dei dispositivi di I/O

• Complessità del sottosistema di I/O

• Livello HW

• Gestione interrupt

• Buffering

• Politiche di Scheduling del disco


Complessità del sottosistema di I/O

• Grande varietà di dispositivi:– Interfacce diverse– Velocità d’accesso e di trasferimento– Modo d’accesso a stream di byte o a blocchi– Complessità di gestione (lp - disco)– Modalità di gestione (file system - swap)– Frequenza di interruzione– Frequenza degli errori e dei guasti


Gestione a due livelli

• Gestione logica: – offre un’interfaccia semplice mediante un numero

limitato di operazioni effettuabili sul periferico come, ad esempio, open, read, write, close.

• Gestione fisica:– le system call devono essere implementate:

o impartendo gli opportuni comandi al controller del dispositivo.

o generando i segnali di controllo del dispositivo stesso.


Il Sottosistema di I/O – livello HW

• I/O gestito in interrupt

• I/O gestito in Direct Memory Access (DMA)

• Elaboratore di Canale di I/O– La CPU ha il compito di preparare in memoria centrale un

programma di I/O– L’elaboratore di canale esegue tale programma ed

interrompe la CPU solamente alla sua conclusione.

• Processore di canale di I/O– si fa carico di tutte le problematiche inerenti la gestione dei

dispositivi fornendo all'elaboratore centrale insiemi di dati già formattati e preprocessati.


Architettura di I/O

I/OController

I/OController

I/OController

SelectorChannel

I/O Bus

DA C

System Bus

DA C

I/OController

I/OController

I/OController

I/OController

MultiplexorChannel

(a) - Selector Channel

(b) - Multiplexor Channel


(a) - User Process

...(* Output section *)Prepare MSG (BUF, LEN, SEMUSER)send( MSG, TOQ);wait( SEMUSER );......

Gestione interrupt – Processo driver

(b) - Output Driver

while (1) {receive( MSG, TOQ);(* Decode MSG *)Start I/O;wait( SEMDTO );signal( SEMUSER );

}


Gestione interrupt – interrupt handler

if (ultimo carattere in output){signal( SEMDTO );End I/O;

}else

Return from interrupt


I/O Buffering

User Process

UserData Area

SystemBuffer

Move

(b) - Single Buffering

I/O Device

Transfer

Operating System

UserData Area

SystemBuffer #1 System

Buffer #2

SystemBuffer #n

Move

User Process

(d) - Circular Buffering

I/O Device

Transfer

Operating System


I/O Buffering

T

C

BL1

BL1

BL2

BL2

BL3

BL3

BL4

BL4

BL1

BL1

BL2T

C

BL3

BL2

BL4 BL5 BL6

BL3 BL4 BL5

BL7

BL1

BL1

BL2T

C BL2 BL3 BL4 BL5

BL3 BL4BU1 BU1BU2 BU2

BL5 BL6 BL7 BL8BU1 BU1BU2 BU2

BL1

BL1

BL2T

C BL2 BL3 BL4 BL5

BL3 BL4BU1 BU2

BL5 BL6BU3 BU1 BU2

BL7BU1

BL8 BL9BU2 BU3

NoBuffering

SingleBuffering

DoubleBuffering

CircularBuffering(3 buffer)

(C) Elaborazione > Trasferimento T

C

T

C

NoBuffering

SingleBuffering

BL4

BL1

BL1

BL2

BL2

BL3

BL3

BL4

BL1 BL2

BL1 BL2

BL3

BL3

BL4

BL4

BL5

BL5

BL6

(C) Elaborazione< Trasferimento


Buffering per trasferimento blocchi del disco

SEEK TIME

ROTATIONAL LATENCY

TRANSFER TIMEHEAD ARM


I/O Buffering

(C) - Elaborazione < Trasferimento

T

C

BL1

BL1

LNo

Buffering

T

C

BL1L

BL2

BL1 BL2

SingleBuffering

TL

BL1 BL2 BL3 BL4

BL1 BL2 BL3BU1 BU1BU2 BU2

BL4BU1 BU1BU2 BU2BL5 BL7 BL8BL6

BL5 BL7 BL8BL6

BL2

BL2

BL3

BL3

BL4

BL4

BL4

BL3 BL4

BL4BL3

BL5

BL5

BL6

BL6

BU1 BU1BU2BL9 BL10 BL11

TL

BL1 BL2 BL3

BL1 BL2 BL3BU1 BU2

BL4

DoubleBuffering

CircularBuffering(3 buffer) BU3 BU1 BU2 BU3

BL5 BL6

BL4 BL5 BL6BU1 BU2 BU3 BU1 BU2 BU3BL7 BL8 BL9 BL10 BL11

BL7 BL8

BL9

BL9

BL12

BL10

TL

NoBuffering

C

C

C

BL1

BL1

TL

SingleBuffering

C

BL1

BL1

BL2

BL2

BL3 BL4

BL4BL3

BL3

BL3

BL2

BL2

(C) -Elaborazione > Trasferimento

L - Latenza


• Il numero di buffer da utilizzare deve essere soddisfare la seguente relazione:

N * tempo di elaborazione > tempo di rotazione +

tempo di trasferimento

Infatti, nel tempo di rotazione e di trasferimento si liberano

questo numero di buffer

Numero di buffer da utilizzare

tempo di rotazione + tempo di trasferimento

tempo di elaborazione


Politiche di Scheduling del disco

• Tempo di Posizionamento

• Latenza Rotazionale

• Tempo di Trasferimento

• Tempo di Completamento dell’I/O


Tempo di Posizionamento

Ts = m ⋅ n + s [msec]

Ts è i tempo di posizionamento stimato.

n è il numero di tracce attraversate durante lo spostamento.

m è il tempo medio di spostamento della testina da una traccia ad una adiacente (track-to-track seek time).

s è il tempo necessario alla testina per accelerare da una velocità nulla alla velocità di crociera.

Per uno spostamento di 100 tracce:

Ts = 0.1 x 100 + 3 = 13 msec.


Latenza Rotazionale

• Hard disk con una velocità di rotazione di 6000 rpm.

• A 6000 rpm, r = 0.1 msec-1 (giri al millisecondo)

• per compiere una rotazione il disco impiega 10 msec.

• la latenza rotazionale vale Dr = 5 msec.

Drr =

12

[msec]


Tempo di Trasferimento

• T è il tempo di trasferimento.

• b è il numero di blocchi (settori) interessati dal trasferimento

• N è il numero di settori per traccia

• r è la velocità di rotazione del disco in giri al millisecondo.

T br N

=⋅

[msec]


Tempo di Completamento dell’I/O

TI/O = t ⋅ (Ts + Dr + T) [msec]

• t è il numero di tracce interessate dall'operazione di trasferimento.

• leggere un file di 256 KByte da un disco caratterizzato da settori da 1 Kbyte e 32 settori per traccia.

• l'operazione di lettura interessa 256 settori ovvero t = 8 tracce.

• Con Ts = 15 ms e velocità di rotazione di 6000 rpm

(Dr = 5 msec e T = 10 ms).

Si ottiene un tempo totale di lettura pari a:

TI/O = 8 ⋅ ( 15 + 5 +10) = 240 msec.


Tempo di Completamento dell’I/O

• Se le tracce sono adiacenti

TI/O = (15 + 5 + 10) + 7⋅(0.1 + 5 + 10) = 135.7 msec.

• Se i settori che compongono il file sono memorizzati sul disco inmodo assolutamente casuale, la lettura di ogni settore prende:

15 + 5 + 10/32 = 20.3 msec

Per leggere l'intero file, dal momento che è costituito da 256 settori occorrerà un tempo pari a:

TI/O = 256 ⋅ 20.3 = 5197 msec = 5.2 sec


Strategie di Scheduling del Disco

• Strategia FIFO

• Strategia Shortest Seek Time Next

• Strategia SCAN

• Strategia C-SCAN


Strategia FIFO

• Numero di tracce del disco: 200.

• Traccia attualmente servita :100.

• Sequenza di richieste di I/O per le tracce:

55, 58, 39, 18, 90, 160, 150, 38, 184• Vantaggi:

• Semplice

• Equa

• No starvation

• Svantaggi

• Pessimo comportamento dovuto

ai seek random

(a) - FIFO

0

20

40

60

80

100

120

140

160

180

200

0 3 6 9

Accesso #

Trac

cia

#


Strategia Shortest Seek Time Next

• Si seleziona dalla coda delle richieste di I/O su disco la richiestache implica lo spostamento minimo della testina rispetto alla posizione corrente.

(b) - SSTN

0

20

40

60

80

100

120

140

160

180

200

0 3 6 9

Accesso #

55, 58, 39, 18, 90, 160, 150, 38, 184

• Vantaggi:

• Minimizza (localmente) iltempo di posizionamento

• Svantaggi:

• Favorisce le tracce centrali

• Starvation


Strategia SCAN

• È simile alla strategia di un ascensore a prenotazione

• Impone che la testina si sposti in una sola direzione servendo ordinatamente tutte le richieste che riguardano tracce attraversate durante tale spostamento.

• Quando la testina raggiunge l'ultima traccia del disco in quella direzione, oppure non vi sono ulteriori richieste da soddisfare, la direzione del moto si inverte e vengano servite in ordine tutte le richieste che si sono accodate durante il ciclo di servizio precedente


Strategia SCAN

55, 58, 39, 18, 90, 160, 150, 38, 184

• Vantaggi:

• Tempo di posizionamento simile a SSTN

• Svantaggi:

• Favorisce le tracce periferiche

• Starvation

(c) - SCAN

0

20

40

60

80

100

120

140

160

180

200

0 3 6 9

Accesso #

Trac

cia

#


Strategia C-SCAN

• Impone che la testina si sposti in una sola direzione, ad esempio per numeri di traccia crescenti, servendo ordinatamente tutte le richieste che riguardano tracce attraversate durante tale spostamento.

• Quando la testina raggiunge l'ultima traccia del disco oppure non vi sono ulteriori richieste da soddisfare, essa ritorna alla traccia iniziale ove inizia un nuovo ciclo di servizio.


Strategia C-SCAN

55, 58, 39, 18, 90, 160, 150, 38, 184

• Vantaggi:

• Tempo di posizionamento simile a SSTN

• Elimina la polarizzazione del servizio verso

tracce periferiche

• Svantaggi:

• Starvation

(d) - C-SCAN

0

20

40

60

80

100

120

140

160

180

200

0 3 6 9

Accesso #

Trac

cia

#

La starvation, dovuta a richieste per settori nella stessa traccia, può essere eliminata usando alternativamente due code: alla seconda si accodano le richieste durante il servizio di quelle della prima.


Confronto delle strategie

(a) - FIFO

0

20

40

60

80

100

120

140

160

180

200

0 3 6 9

Accesso #

Trac

cia

#

(b) - SSTN

0

20

40

60

80

100

120

140

160

180

200

0 3 6 9

Accesso #

Trac

cia

#

(c) - SCAN

0

20

40

60

80

100

120

140

160

180

200

0 3 6 9

Accesso #

Trac

cia

#

(d) - C-SCAN

0

20

40

60

80

100

120

140

160

180

200

0 3 6 9

Accesso #

Trac

cia

#

55.3 27.6 27.8 35.8

55, 58, 39, 18, 90, 160, 150, 38, 184

Modulo 10: Gestione dei dispositivi di...

Documents

Transcript of Modulo 10: Gestione dei dispositivi di...