1 administración de i/o y scheduling de disco capítulo 11
TRANSCRIPT
![Page 1: 1 Administración de I/O y Scheduling de disco Capítulo 11](https://reader035.vdocumento.com/reader035/viewer/2022081520/5665b4361a28abb57c900b3a/html5/thumbnails/1.jpg)
1
Administración de I/O y Scheduling de disco
Capítulo 11
![Page 2: 1 Administración de I/O y Scheduling de disco Capítulo 11](https://reader035.vdocumento.com/reader035/viewer/2022081520/5665b4361a28abb57c900b3a/html5/thumbnails/2.jpg)
2
Categorías de dispositivos de I/O
• Leíbles por humanos– Usados para comunicación con el usuario
– Impresoras, teclados, terminales, etc
• Leíbles por máquinas– Usados para comunicación con equipos electrónicos
– Discos, floppies, sensores, etc
• De comunicación – Usados para comunicación con dispositivos remotos
– Modems, tarjeta de red, etc
![Page 3: 1 Administración de I/O y Scheduling de disco Capítulo 11](https://reader035.vdocumento.com/reader035/viewer/2022081520/5665b4361a28abb57c900b3a/html5/thumbnails/3.jpg)
3
Diferencias entre dispositivos de I/O
• Tasa de transferencia de datos– Puede existir varios órdenes de magnitud de diferencia
![Page 4: 1 Administración de I/O y Scheduling de disco Capítulo 11](https://reader035.vdocumento.com/reader035/viewer/2022081520/5665b4361a28abb57c900b3a/html5/thumbnails/4.jpg)
4
Diferencias (cont)
• Aplicación– Un disco usado para almacenar los archivos de los usuarios requiere del sistemas
de archivos
– Un disco usado para almacenar páginas de memoria virtual y realizar swap-in y swap-out requiere hardware y software apropiado
• Complejidad de control
• Unidad de transferencia– flujo de caracteres o bloques
• Representación de datos; esquemas de codificación
• Condiciones de error
La diversidad de dispositivos de I/O y sus diferencias hacen difícil la tarea de proveer una solución uniforme y consistente
![Page 5: 1 Administración de I/O y Scheduling de disco Capítulo 11](https://reader035.vdocumento.com/reader035/viewer/2022081520/5665b4361a28abb57c900b3a/html5/thumbnails/5.jpg)
5
Tres formas básicas de realizar I/O• I/O Programado
– El procesador emite el comando de I/O, en favor de un proceso, al módulo de de I/O
– luego el proceso espera (busy waiting) hasta que la operación de I/O termine
• I/O basado en interrupciones– El procesador emite el comando de I/O al igual que I/O programado– Luego el procesador continua ejecutando instrucciones del mismo u otro proceso– Cuando la operación de I/O termina, el módulo de I/O envía una interrupción al
procesador para que éste avise al proceso
• Acceso Directo a Memoria (DMA)– El procesador instruye al módulo de DMA que transfiera uno o más bloques de
datos – El módulo de DMA controla completamente la transferencia de datos entre el
dispositivo de I/O y la memoria principal, sin intervención del procesador– Finalmente, el módulo DMA interrumpe al procesador cuando la transferencia está
lista
![Page 6: 1 Administración de I/O y Scheduling de disco Capítulo 11](https://reader035.vdocumento.com/reader035/viewer/2022081520/5665b4361a28abb57c900b3a/html5/thumbnails/6.jpg)
6
Relaciones entre las técnicas
![Page 7: 1 Administración de I/O y Scheduling de disco Capítulo 11](https://reader035.vdocumento.com/reader035/viewer/2022081520/5665b4361a28abb57c900b3a/html5/thumbnails/7.jpg)
7
Evolución de la función de I/O• Procesador controla directamente al dispositivo• Controlador o módulo de I/O
– Procesador usa I/O programado sin interrupciones– Procesador no maneja los detalles de los dispositivos externos
• Controlador o módulo I/O con interrupciones– Procesador no necesita esperar en busy-waiting hasta que la operación termine
• DMA– Se transfieren bloques de datos entre dispositivo y memoria sin involucrar al
procesador– El procesador se involucra sólo al principio y al final de la trasnferencia
• Módulo I/O es un procesador separado (I/O channel)– Ejecuta instrucciones en memoria principal– Permite manejar una secuencia de operaciones de I/O sin la intervención del
procesador
• Procesador I/O (I/O processor)– Módulo I/O tiene memoria local y es en realidad un computador
![Page 8: 1 Administración de I/O y Scheduling de disco Capítulo 11](https://reader035.vdocumento.com/reader035/viewer/2022081520/5665b4361a28abb57c900b3a/html5/thumbnails/8.jpg)
8
DMA
• Procesador delega las operaciones de I/O al módulo de DMA
• Módulo DMA transfiere bloques de datos directamente desde o hacia la memoria principal
• Cuando la transferencia termina, envía una interrupción al procesador
![Page 9: 1 Administración de I/O y Scheduling de disco Capítulo 11](https://reader035.vdocumento.com/reader035/viewer/2022081520/5665b4361a28abb57c900b3a/html5/thumbnails/9.jpg)
9
Configuraciones DMA
![Page 10: 1 Administración de I/O y Scheduling de disco Capítulo 11](https://reader035.vdocumento.com/reader035/viewer/2022081520/5665b4361a28abb57c900b3a/html5/thumbnails/10.jpg)
10
Configuraciones DMA
![Page 11: 1 Administración de I/O y Scheduling de disco Capítulo 11](https://reader035.vdocumento.com/reader035/viewer/2022081520/5665b4361a28abb57c900b3a/html5/thumbnails/11.jpg)
11
Buffering de I/O
• Considere el siguiente escenario– Un proceso requiere leer un bloque de datos y almacenarlos en su espacio de
direcciones (por ejemplo, un arreglo)
– ¿Qué pasa si el SO decide suspender el proceso mientras se realiza la operación de lectura?
– Es necesario que ciertas páginas permanezcan lock incluso si el proceso es suspendido
– Note que también seria posible que ocurriera deadlock
• I/O buffering consiste en realizar lectura de datos anticipadamente y realizar operaciones de escritura no inmediatamente después del requerimiento mismo.
![Page 12: 1 Administración de I/O y Scheduling de disco Capítulo 11](https://reader035.vdocumento.com/reader035/viewer/2022081520/5665b4361a28abb57c900b3a/html5/thumbnails/12.jpg)
12
Tipos de dispositivos de I/O• Orientado al bloque
– Información es almacenada en bloques de tamaño fijo– La transferencia es de un bloque a la vez
• Orientado al flujo (Stream)– Transfiere información como un flujo de bytes– Usado por impresoras, terminales, puertos de comunicación, etc
![Page 13: 1 Administración de I/O y Scheduling de disco Capítulo 11](https://reader035.vdocumento.com/reader035/viewer/2022081520/5665b4361a28abb57c900b3a/html5/thumbnails/13.jpg)
13
Buffer simple
• SO asigna un buffer en memoria principal (un área de memoria) para un requerimiento de I/O
• Buffering orientado al bloque– Transferencia se realiza a un buffer del sistema
– Luego, el bloque es movido al espacio de direcciones del proceso
– Otro bloque es leído inmediatamente en el buffer del sistema; read ahead
• Note que el proceso puede suspenderse o bloquearse porque la transferencia se hace en memoria del sistema y no espacio del usuario
• El SO administra los buffers asignados a los procesos
• T: tiempo para leer un bloque• C: tiempo de cómputo entre lecturas• M: tiempo para mover datos desde memoria del sistema a memoria usuario
• T+C versus max{C,T} + M
![Page 14: 1 Administración de I/O y Scheduling de disco Capítulo 11](https://reader035.vdocumento.com/reader035/viewer/2022081520/5665b4361a28abb57c900b3a/html5/thumbnails/14.jpg)
14
Buffer doble• Se utilizan dos buffers de sistema
• Mientras se transfiere data desde o hacia uno de los buffers, el SO transfiere datos desde o hacia el otro buffer
• En este caso tiempo de ejecucion es max{C, T]
![Page 15: 1 Administración de I/O y Scheduling de disco Capítulo 11](https://reader035.vdocumento.com/reader035/viewer/2022081520/5665b4361a28abb57c900b3a/html5/thumbnails/15.jpg)
15
Buffer circular• Se utilizan más de dos buffers
• Cada buffer es una unidad en un buffer circular
• Es útil cuando el proceso realiza muchas y continuas operaciones de I/O
![Page 16: 1 Administración de I/O y Scheduling de disco Capítulo 11](https://reader035.vdocumento.com/reader035/viewer/2022081520/5665b4361a28abb57c900b3a/html5/thumbnails/16.jpg)
16
Scheduling de discoParámetros de rendimiento
• Para leer o escribir, la cabeza lectora del disco debe estar posicionada en la pista deseada y al comienzo del sector apropiado
• Seek time (tiempo de búsqueda)– Tiempo necesario para posicionar la cabeza en la pista deseada
• Latencia rotacional (o demora rotacional)– Tiempo que demora hasta que la cabeza se posiciona en el sector deseado
• Tiempo de acceso– suma seek time y latencia rotacional; tiempo total antes de comenzar a leer o
escribir
• La transferencia de datos ocurre a medida que el sector se mueve debajo de la cabeza
![Page 17: 1 Administración de I/O y Scheduling de disco Capítulo 11](https://reader035.vdocumento.com/reader035/viewer/2022081520/5665b4361a28abb57c900b3a/html5/thumbnails/17.jpg)
17
Parámetros (cont)
• Demora rotacional– Tiempos típicos velocidad rotacional entre 3600 rpm hasta 15000 rpm.
– En discos con 15000 rpm, tenemos una revolución por 4 ms
– En promedio, demora rotacional será 2 ms
– En floppies, la demora promedio es entre 100 y 50 ms
• Tiempo de transferencia– T = b/ (r N)
– b: número de bytes a transferir
– N: número de bytes en la pista
– r: velocidad rotacional, en revoluciones por segundo
– Tiempo total de acceso = Ts + 1/(2r) + b/(rN)
– Ts, seek time
![Page 18: 1 Administración de I/O y Scheduling de disco Capítulo 11](https://reader035.vdocumento.com/reader035/viewer/2022081520/5665b4361a28abb57c900b3a/html5/thumbnails/18.jpg)
18
Ejemplo comparativo
• Considere un disco con los siguientes parámetros– Tiempo seek promedio 4ms
– Velocidad rotacional 7500 rpm
– Sectores de 512 bytes, y 500 sectores por pista
• Suponga que se desea transferir 2500 sectores, es decir 1.28 Mbytes
• Primero suponga que el archivo ocupa todos los sectores en 5 pistas consecutivas (organización secuencial).
• Entonces, el tiempo para leer la primera pista– Seek promedio = 4 ms
– Demora rotacional promedio = 4 ms
– Lectura de 500 sectores = 8 ms
– Total 16 ms
• Las otras pistas se leen sin seek time, es deir 4 + 8
• Tiempo total = 16 + 4*12 = 64 ms = 0.064 segundos
![Page 19: 1 Administración de I/O y Scheduling de disco Capítulo 11](https://reader035.vdocumento.com/reader035/viewer/2022081520/5665b4361a28abb57c900b3a/html5/thumbnails/19.jpg)
19
Ejemplo (cont)
• Ahora asuma acceso random– Tiempo seek = 4 ms
– Demora rotacional = 4 ms
– Lectura de 1 sector = 0.016 ms
– Lectura de 2500 sectores = 2500*8.016 = 20.04 segundos
![Page 20: 1 Administración de I/O y Scheduling de disco Capítulo 11](https://reader035.vdocumento.com/reader035/viewer/2022081520/5665b4361a28abb57c900b3a/html5/thumbnails/20.jpg)
20
Scheduling de discoPolíticas
• Tiempo seek es la razón principal del rendimiento pobre en el ejemplo anterior
• Recordar que para cada unidad de I/O, el SO mantiene una cola de requerimientos de I/O (de distintos procesos)
• En el caso de discos, estos requerimientos vienen con el número de pista(s) que se necesitan leer.
• Si las pistas se visitan aleatoreamente, el rendimiento será el peor
• Para las siguentes políticas, asumiremos la siguiente cola de disco:– 55, 58, 39, 18, 90, 160, 150, 38, 184
• Y la cabeza lectora está inicialmente sobre la pista 100
![Page 21: 1 Administración de I/O y Scheduling de disco Capítulo 11](https://reader035.vdocumento.com/reader035/viewer/2022081520/5665b4361a28abb57c900b3a/html5/thumbnails/21.jpg)
21
FIFO• Los requerimientos se sirven en el orden de llegada (secuencialmente)
• Dependiendo de los requerimientos encolados, FIFO puede comportarse como una lectura random
• 55, 58, 39, 18, 90, 160, 150, 38, 184
![Page 22: 1 Administración de I/O y Scheduling de disco Capítulo 11](https://reader035.vdocumento.com/reader035/viewer/2022081520/5665b4361a28abb57c900b3a/html5/thumbnails/22.jpg)
22
Prioridad
• La meta no es optimizar uso de disco
• Lecturas pequeñas podrían tener más prioridad que lecturas masivas
• Esto significaría un buen tiempo de respuesta a aplicaciones interactivas
• No es una política recomendada para sistemas de base de datos
![Page 23: 1 Administración de I/O y Scheduling de disco Capítulo 11](https://reader035.vdocumento.com/reader035/viewer/2022081520/5665b4361a28abb57c900b3a/html5/thumbnails/23.jpg)
23
Tiempo servicio más corto primero (SSTF)• Selecciona el requerimiento de disco que requiere el menor movimiento del brazo
desde su posición actual
• Es decir, minimiza el tiempo seek
• Note que este algoritmo no garantiza que el tiempo promedio de seek sobre un conjunto de operaciones de I/O sea mínimo
• 55, 58, 39, 18, 90, 160, 150, 38, 184
![Page 24: 1 Administración de I/O y Scheduling de disco Capítulo 11](https://reader035.vdocumento.com/reader035/viewer/2022081520/5665b4361a28abb57c900b3a/html5/thumbnails/24.jpg)
24
SCAN• El brazo se mueve sólo en una dirección, satisfaciendo todos los requerimientos de
acuerdo al movimiento hasta llegar a la última pista
• Luego, el brazo barre el disco en la otra dirección
• ¿Cuáles pistas se favorecen?
• 55, 58, 39, 18, 90, 160, 150, 38, 184
![Page 25: 1 Administración de I/O y Scheduling de disco Capítulo 11](https://reader035.vdocumento.com/reader035/viewer/2022081520/5665b4361a28abb57c900b3a/html5/thumbnails/25.jpg)
25
C-SCAN (scan circular)• Restringe el barrido sólo en una dirección, sin revertir cuando se llega al final
• Cuando se llega al final, el brazo retorna al principio y comienza nuevamente su barrido
• 55, 58, 39, 18, 90, 160, 150, 38, 184
![Page 26: 1 Administración de I/O y Scheduling de disco Capítulo 11](https://reader035.vdocumento.com/reader035/viewer/2022081520/5665b4361a28abb57c900b3a/html5/thumbnails/26.jpg)
26
Comparación
![Page 27: 1 Administración de I/O y Scheduling de disco Capítulo 11](https://reader035.vdocumento.com/reader035/viewer/2022081520/5665b4361a28abb57c900b3a/html5/thumbnails/27.jpg)
27
Comparación
![Page 28: 1 Administración de I/O y Scheduling de disco Capítulo 11](https://reader035.vdocumento.com/reader035/viewer/2022081520/5665b4361a28abb57c900b3a/html5/thumbnails/28.jpg)
28
RAID
• Redundant Array of Independent Disks
• Un conjunto de discos físicos es visto por el SO como un sólo disco lógico
• Los datos se almacenan en forma distribuida en el arreglo de discos lo cual permite lectura paralela de distintos discos
• Además, se utiliza la capacidad redundante para almacenar información de paridad, la cual garantiza la recuperación de información en caso de falla de uno de los discos
• Existen 7 niveles RAID, de 0 a 6
![Page 29: 1 Administración de I/O y Scheduling de disco Capítulo 11](https://reader035.vdocumento.com/reader035/viewer/2022081520/5665b4361a28abb57c900b3a/html5/thumbnails/29.jpg)
29
RAID 0 (sin redundancia)
• Los datos estan organizados en los discos en strips, los cuales se distribuyen round-robin en los discos físicos
• El disco lógico también está dividido en strips
• Suponga que tenemos n discos físicos, luego los primeros n strips se mapean consecutivamente en los n discos. Este conjunto de strips forma un stripe
• Provee la transferencia más alta, pero no es tolerante a fallos
![Page 30: 1 Administración de I/O y Scheduling de disco Capítulo 11](https://reader035.vdocumento.com/reader035/viewer/2022081520/5665b4361a28abb57c900b3a/html5/thumbnails/30.jpg)
30
RAID 1 (espejo)
• Se provee tolerancia a fallos mediante la simple replicación de los datos
• Cada disco físico tiene su disco espejo que replica los datos
• Note que cada vez que se requiere agregar un disco para aumentar la capacidad de almacenamiento, se necesita de otro disco para la duplicación
• Muy costoso para sistemas muy grandes (mucha información)
![Page 31: 1 Administración de I/O y Scheduling de disco Capítulo 11](https://reader035.vdocumento.com/reader035/viewer/2022081520/5665b4361a28abb57c900b3a/html5/thumbnails/31.jpg)
31
RAID 2 (redundancia mediante código de Hamming)
• Típicamente, la información se distribuye al nivel de bits o bytes.
• Por ejemplo, 32 discos serían necesarios para un sistema cuya palabra es de 32 bits. En este caso, cada strip es de 1 bit
• Se usa el código detector y corrector de Hamming para calcular un código de error, el cual se almacena en discos adicionales.
• Cuando se lee una palabra, se calcula su código y se compara con el almacenado; si hay una diferencia de un bit, entonces se puede corregir.
• Si hay diferencias en más de un bit, se puede detectar
• RAID 2 no se usa en la práctica
![Page 32: 1 Administración de I/O y Scheduling de disco Capítulo 11](https://reader035.vdocumento.com/reader035/viewer/2022081520/5665b4361a28abb57c900b3a/html5/thumbnails/32.jpg)
32
RAID 3 (bit de paridad)
• Similar a RAID 2, pero utiliza un bit de paridad y no un código de error.
• Luego, en caso que un disco falle, se lee el disco de paridad y se regenera el dato
• Por ejemplo, si hay 4 discos de datos (0, 1, 2, 3), el bit de paridad se calcula
• Luego si falla la unidad 1, recuperamos la información sumando
• A cada lado de la ecuación anterior
)(0)(1)(2)(3)(4 iXiXiXiXiX
)(1)(4 iXiX
)(0)(2)(3)(4)(1 iXiXiXiXiX
![Page 33: 1 Administración de I/O y Scheduling de disco Capítulo 11](https://reader035.vdocumento.com/reader035/viewer/2022081520/5665b4361a28abb57c900b3a/html5/thumbnails/33.jpg)
33
RAID 4 (bloque de paridad)
• En RAID 4 los strips son relativamente grandes (no bits como en RAID 2 y 3) y se usa un bloque de paridad bit a bit del mismo tamaño que los strips
• Además, las unidades se operan independientemente, con lo que pueden atender varias solicitudes de I/O en paralelo
• RAID 4 involucra un penalty cuando la solicitud es pequeña
• Suponga que el requerimiento de escritura es sólo para el strip en disco 1. Se puede demostrar que
• Donde el símbolo prima significa el strip después de la escritura. Por lo tanto, una escritura de un strip, requiere dos lecturas (en paralelo) y una escritura
• Si la solicitud involucra todos los strips, entonces se requiere solo una escritura en paralelo
)´(1)(1)(4)´(4 iXiXiXiX
![Page 34: 1 Administración de I/O y Scheduling de disco Capítulo 11](https://reader035.vdocumento.com/reader035/viewer/2022081520/5665b4361a28abb57c900b3a/html5/thumbnails/34.jpg)
34
RAID 5 (bloque de paridad distribuido)
• La única diferencia con RAID 4, es que en RAID 5, el bloque de paridad se distribuye en todos los disco, por ejemplo en forma round-robin
• Note que:– Los datos también están distribuidos en round-robin
– Aún necesitamos de un disco adicional al de la necesaria para almacenar los datos
![Page 35: 1 Administración de I/O y Scheduling de disco Capítulo 11](https://reader035.vdocumento.com/reader035/viewer/2022081520/5665b4361a28abb57c900b3a/html5/thumbnails/35.jpg)
35
RAID 6 (dual redundancy)
• Se utilizan dos algoritmos de cálculo de paridad: uno calcula los bits con el algoritmo del OR exclusivo, y el otro es uno provisto por el proveedor.
• Luego, se mantienen dos bloques de paridad (distribuidos como en RAID 5)
• Esto permite que se puedan recuperar los datos aun cuando fallen dos unidades
• Un arreglo RAID 6 de N discos de datos requiere N+2 discos en total