algortimos-discos

Vista previa del material en texto

Sistemas OperativosSistemas Operativos
INF - 151INF 151
MODULO IV. ENTRADA Y SALIDA
4 1 Algoritmos4.1 Algoritmos
Continuación…………………….
Resumen preparado por Miguel Cotaña
Algoritmos para calendarizar el brazo del discoAlgoritmos para calendarizar el brazo del disco
Consideraremos el tiempo que toma leer
Algoritmos para calendarizar el brazo del discoAlgoritmos para calendarizar el brazo del disco
o escribir un bloque de disco. El tiempo
requerido está determinado por 3q p
factores:
1 Tiempo de desplazamiento (seek time:1. Tiempo de desplazamiento (seek time:
el tiempo que tarda el movimiento del
brazo hasta el cilindro correcto)brazo hasta el cilindro correcto)
2. Retrazo rotacional (el tiempo que
tarda el sector correcto en girar hasta
colocarse bajo la cabeza)
23. Tiempo real de transferencia de datos
Si el controlador de disco acepta
solicitudes una por una y las ejecuta en
ese orden es decir primera que llegaese orden, es decir, primera que llega,
primera que se atiende (FCFS; first-
fi t d) dcome, first-served), poco puede
hacerse para optimizar el tiempo de
desplazamiento. Sin embargo, si el disco
está sometido a una carga intensa,está sometido a una carga intensa,
podría utilizase otra estrategia.
3
Es muy probable que mientras el brazo
se está desplazando para atender una
solicitud otros procesos generen otrassolicitud, otros procesos generen otras
solicitudes de disco.
M h j d d di tiMuchos manejadores de disco mantienen
una tabla, indizada por número de
cilindro, con todas las solicitudes
pendientes para cada cilindro,pendientes para cada cilindro,
encadenadas en una lista enlazada
b d l t d d l t bl
4
encabezada por las entradas de la tabla.
Dado este tipo de estructura de datos,
podemos mejorar el algoritmo dep j g
calendarización de primera que llega,
primera que se atiendeprimera que se atiende.
Considerar un disco imaginario con 40
cilindros. Llega una solicitud para leer un
bloque en el cilindro 11.q
Mientras el brazo se está desplazando al
cilindro 11 llegan nuevas solicitudes paracilindro 11, llegan nuevas solicitudes para
los cilindros 1, 36, 16, 34 9 y 12, en ese
5orden
Estas solicitudes se colocan en la tabla de
solicitudes pendientes, con una lista
enlazada distinta para cada cilindroenlazada distinta para cada cilindro.
Cuando termina la solicitud actual (que
pidió el cilindro 11), el controlador de
disco puede escoger cuál solicitudp g
atenderá a continuación.
Si usa FCFS se dirigirá ahora al cilindroSi usa FCFS, se dirigirá ahora al cilindro
1, luego al 36, y así sucesivamente.
Requeriría movimientos del brazo de 10,
35, 20, 18, 25 y 3, para un total de 111
6
, , , y , p
cilindros
DISCOS (Planificación del brazo: FCFS)
¡ C l d ti i
• Ejemplo: Posición actual: cilindro 11
Llegan peticiones: 1, 36, 16, 34, 9 ,12
¡ Colas de peticiones 
pendientes por 
cilindro !
0 1 9 11 12 16 34 36
X XX XX X
10
3535
20
1818
25
3
7¡ En total se atraviesan 111 cilindros !
Como alternativa, el controlador de,
dispositivo podría atender siempre a
continuación la solicitud más cercanacontinuación la solicitud más cercana,
para así minimizar el tiempo de
desplazamiento.
Dadas las solicitudes del gráfico anterior,g ,
la sucesión será 12, 9, 16, 1, 34 y 36,
como indica el zigzagcomo indica el zigzag.
8
Con esta sucesión, los movimientos del,
brazo son de 1, 3, 7, 15, 33 y 2, para un
total de 61 cilindrostotal de 61 cilindros.
Este algoritmo, desplazamiento más
corto primero (SSF; Shortest Seek
First), recorta el movimiento total del),
brazo casi a la mitad, en comparación
con FCFScon FCFS.
9
DISCOS (Planificación del brazo: SSF “Shortest Seek First”)
• • • • •
0 1 9 11 12 16 34 36
X X X X X X
0 1 9 11 12 16 34 36
posición actual
(1)
(3)
(7)
(15)
( )(33)
(2)
¡ En total se atraviesan 61 cilindros !
10INJUSTICIA + INANICIÓN
Lamentablemente SSF tiene un
bl S i d iproblema. Suponiendo que siguen
llegando más solicitudes mientras se
están procesando las solicitudes. Por
ejemplo, si después de desplazarse alejemplo, si después de desplazarse al
cilindro 16 hay una nueva solicitud para
el cilind o 8 esta solicit d tend áel cilindro 8, esta solicitud tendrá
prioridad respecto al cilindro 1. Si luego
llega una solicitud para el cilindro 13, el
brazo se dirigirá al 13, no al 1.
11
brazo se dirigirá al 13, no al 1.
Si el disco está sometido a una carga
d l b t d ápesada, el brazo tenderá a permanecer
en la parte media del disco casi todo el
tiempo, y las solicitudes para ambos
extremos tendrán que esperar hasta queextremos tendrán que esperar hasta que
una fluctuación estadística en la carga
ocasione q e no ha a ning na solicit docasione que no haya ninguna solicitud
cerca de la parte media.
Las solicitudes alejadas de la parte media
podrían recibir mal servicio.
12
podrían recibir mal servicio.
Se debe reducir al mínimo el tiempo de
respuesta y de ser equitativos.
El problema de calendarizar un elevadorEl problema de calendarizar un elevador
de un edificio es similar al de calendarizar
l b d diel brazo de un disco.
Contínuamente llegan solitudes que
llaman al elevador a los pisos (cilindros)
al azar El ordenador que controla elal azar. El ordenador que controla el
elevador podría llevar fácilmente un
i t d l d l li tregistro del orden en que los clientes
oprimieron el botón de llamada y
13atenderlos FCFS, también SSF.
Pero, los elevadores utilizan un algoritmo
di i ili ldistinto para conciliar las metas opuestas
de eficiencia y equitatividad.
El elevador continúa avanzando en la
misma dirección hasta que no hayamisma dirección hasta que no haya
solicitudes pendientes en esa dirección.
E t bi d di ióEn ese momento, cambia de dirección.
Este algoritmo es conocido como el
algoritmo del elevador.
14
Este algoritmo, requiere que el software
mantenga un bit: el bit de direcciónmantenga un bit: el bit de dirección
actual, SUBE o BAJA.
C d t i d t dCuando termina de atenderse una
solicitud, el controlador del disco o del
elevador lee el bit. Si es SUBE, el brazo o
la cabina se desplaza hasta la siguientela cabina se desplaza hasta la siguiente
solicitud pendiente más alta.
Si h li it d di tSi no hay solicitudes pendientes en
posiciones más altas, se invierte el bit de
15dirección
Empleando las mismas 7 solicitudes del
primer gráfico suponiendo que en unprimer gráfico, suponiendo que en un
principio que el bit de dirección era SUBE.
El d ti d l ili dEl orden en que se atienden los cilindros
es 12, 16, 34, 36, 9 y 1, lo cual implica
movimientos del brazo de 1, 4, 18, 2, 27
y 8 para un total de 60 cilindrosy 8, para un total de 60 cilindros.
En este caso el algoritmo del elevador es
j SSFun poco mejor que SSF.
16
DISCOS (Planificación del brazo: Elevador )( )
• Idea de sentido: (Sube – Baja) *
• • • • •X X X X X X
 0 1 9 11 12 16 34 36
posición actualp
(1) (4)
(18)
(2)(2)
(27)
(8)
Total cilindros atravesados 60
( )
17
Total cilindros atravesados = 60
Una ligera modificación de este algoritmo
que tiene menor varianza en los tiemposque tiene menor varianza en los tiempos
de respuesta consiste en siempre
l l i di ió Uexplorar en la misma dirección. Una vez
que se ha atendido el cilindro de número
más alto que tenia una solicitud
pendiente el brazo se dirige al cilindro dependiente, el brazo se dirige al cilindro de
número más bajo que tenga una solicitud
di t l ti ú ié dpendiente y luego continúa moviéndose
hacia arriba.
18
DISCOS (Planificación del brazo: Elevador mejorado CSCAN )
• • • • •
 0 1 9 11 12 16 34 36
X X X X X X
posición actual
(1) (4)(1) (4)
(18)
(2)( )
(35)
(8)
19Total cilindros atravesados = 68
Manejo de erroresManejo de errores
ó
jj
Los defectos de fabricaciónintroducen sectores
defectuosos, es decir, sectores que no
devuelven de manera correcta el valor que se
acaba de escribir en ellos. Si el defecto es muyy
pequeño, digamos en unos cuantos bits, es
posible usar el sector defectuoso y tan sóloposible usar el sector defectuoso y tan sólo
dejar que el ECC corrija los errores en cada uso.
Si el defecto es mayor no podrá disfrazarse elSi el defecto es mayor, no podrá disfrazarse el
error.
20
Existe dos enfoques para manejar los
bloques defectuosos:q
Ocuparse de ellos en la
controladora ócontroladora, ó
Hacerlo en el SO.
Con el primer enfoque, antes de que el
disco salga de la fábrica se le prueba y sedisco salga de la fábrica se le prueba y se
escribe en el disco una lista de sectores
defectuosos. Cada uno de ellos se
sustituye por un sector de repuesto.
21
y p p
También pueden surgir errores durante el
funcionamiento normal después de quefuncionamiento normal después de que
se ha instalado la unidad de disco. La
i lí d d f l tprimera línea de defensa al presentarse
un error que el ECC no pueda manejar es
simplemente reintentar la operación.
Algunos errores de lectura sonAlgunos errores de lectura son
transitorios, es decir, son causados por
tí l d l b j l bpartículas de polvo bajo la cabeza y
desaparcen en el nuevo intento.
22
Si la controladora nota que estáSi la controladora nota que está
obteniendo errores repetidos en cierto
ásector, podrá cambiar a un sector de
repuesto antes de que el sector quedep q q
inutilizado por completo.
Por lo regular es necesario utilizar elPor lo regular es necesario utilizar el
método de sustitución del sector
d f ddefectuoso por uno de repuesto.
23
En un segundo enfoque, si la
controladora no puede ajustar de formacontroladora no puede ajustar de forma
transparente la correspondencia entre
t fí i ú d tsectores físicos y números de sector
como hemos visto, el SO deberá hacerlo
en software.
Esto implica que primero deberáEsto implica que primero deberá
conseguir una lista de sectores
d f t l é d l d l didefectuosos, sea leyéndola del disco o
tan solo probando él mismo todo el disco.
24
Si el SO se está encargando del ajuste de
correspondencia deberá asegurarse decorrespondencia deberá asegurarse de
que no haya sectores defectuosos en los
hi t l li t darchivos y tampoco en la lista o mapa de
bits de sectores libres. Una forma de
hacerlo es crear un archivo secreto
integrado por todos los sectoresintegrado por todos los sectores
defectuosos. Si este archivo no se
i l i t d hi lincorpora al sistema de archivos, los
usuarios no podrán leerlo
25accidentalmente
Sin embargo, todavía queda un
problema: los respaldos.
Si un disco se respalda archivo porp p
archivo, es importante que el programa
de respaldo no trate de copiar el archivode respaldo no trate de copiar el archivo
de bloques defectuosos. Para evitarlo, el
SO tiene que ocultar dicho archivo, para
que ni siquiera un programa de respaldoq q p g p
pueda hallarlo.
26
Los sectores defectuosos no son la única
fuente de errores. También pueden
presentarse errores de: desplazamientop p
del brazo causados por problemas
mecánicos La controladora se mantienemecánicos. La controladora se mantiene
al tanto de la posición del brazo.
Para realizar un deplazamiento, la
controladora envía una serie de pulsos alp
motor del brazo, un pulso por cilindro, a
fin de trasladar el brazo al nuevo cilindro
27
fin de trasladar el brazo al nuevo cilindro
Una vez que el brazo llega a su destino,
la controladora lee el número de cilindro
real en el preámbulo del siguiente sector.p g
Si el brazo no está en el lugar correcto,
se habrá presentado un error dese habrá presentado un error de
desplazamiento.
Casi todas las controladoras de disco
duro corrigen errores de desplazamientog p
en forma automática
28
Por lo que la controladora es unaPor lo que, la controladora es una
pequeña computadora especializada,
úcompleta con software, variables, búferes
y, de vez en cuando, bugs (errores)y, , g ( )
La recalibración de un disco produce un
ruido raro pero por lo demás no causaruido raro pero por lo demás no causa
problemas en condiciones normales.
29
Almacenamiento estableAlmacenamiento estable
Utiliza un par de disco idénticos en el que los
bloques correspondientes colaboran para formar
un bloque sin errores. En ausencia de errores,un bloque sin errores. En ausencia de errores,
los bloques correspondientes en ambas
unidades son iguales Es posible leer cualquieraunidades son iguales. Es posible leer cualquiera
de ellos y obtener el mismo resultado. Para
l l t d fi 3 ilograr la meta, se define 3 operaciones:
Escrituras estables
Lecturas estables
Recuparación después de caidas.
30
RelojesRelojesRelojesRelojes
Los relojes (temporizadores) son
indispensables para el funcionamiento deindispensables para el funcionamiento de
cualquier sistema multiprogramado
(mantienen la hora del día y evitan que
un proceso monopolice la CPU).un proceso monopolice la CPU).
El estudio de los relojes se basa en el
hardware y en el softwarehardware y en el software.
31
Hardware de relojHardware de reloj
Se construye con 3 componentes:
jj
Un cristal oscilador
Un contadorUn contador
Un registro de retención
Cuando un cristal de cuarzo se corta de manera
adecuada y se monta sometido a tensión, puede
hacerse que genere una señal periódica de gran
precisión, por lo regular del orden de variosp , p g
cientos de megahertz, dependiendo del cristal
escogido
32
escogido
Utilizando circuitos electrónicos estaUtilizando circuitos electrónicos, esta
señal base puede multiplicarse por un
entero pequeño para obtener frecuencias
de hasta 1000 MHz. Todo ordenador
contiene al menos un circuito de este
tipo el cual alimenta una señaltipo, el cual alimenta una señal
sincronizadora a los demás circuitos de la
ámáquina
33
Los relojes programables suelen tenerLos relojes programables suelen tener
varios modos de operación:
úModo de disparo único
Modo de onda cuadrada
Cuando el contador llega a cero y causa
la interrupción entonces estala interrupción, entonces esta
interrupciones periódicas se llaman tics
de reloj
34
Software de relojSoftware de reloj
Lo único que hace el hardware de reloj es
jj
generar interrupciones a intervalos
conocidos. Todo lo demás relacionado con elconocidos. Todo lo demás relacionado con el
tiempo debe efectuarse en software. Las
tareas son:tareas son:
1. Mantener la hora al día
2 E it j t l2. Evitar que se ejecuten los procesos
durante más tiempo del debido
3. Contabilizar el consumo de CPU
4. Procesar la llamada al sistema alarm
35emitida por procesos de usuario
5. Proporcionar temporizadores de
vigilancia a ciertas partes delg p
sistema
6 Realizar perfiles supervisión y6. Realizar perfiles, supervisión y
recolección de datos estadísiticos
36
La primera función del reloj mantener laLa primera función del reloj, mantener la
hora del día (tiempo real). Sólo requiere
incrementar un contador en cada tic del
reloj. Lo único que hay que cuidar es elj q y q
número de bits en el contador de la hora
del día Con una tasa de reloj de 60 Hzdel día. Con una tasa de reloj de 60 Hz,
un contador de 32 bits se desbordará en
á ñpoco más de 2 años.
37
Para resolver este problema puede
adaptarse 3 enfoques:p q
Utilizar un contador de 64 bits
Mantener la hora del día enMantener la hora del día en
segundos, no en tics.
Contar en tics, pero hacerlo con
relación al momento en que se pusoq p
en marcha el sistema
38
Temporizadores de SoftwareTemporizadores de Software
Casi todas las computadoras tienen un segundo
pp
reloj programable que puede ajustarse de
modo que cause interrupciones con lamodo que cause interrupciones con la
frecuencia que las necesite un programa. Este
temporizador es adicional al temporizadortemporizador es adicional al temporizador
principal del sistema.
Mi t l f i d l i t iMientras la frecuencia de las interrupciones sea
baja, no habrá problema si este segundo
temporizador se utiliza con fines específicos
para una aplicacióndada.
39
El problema surge cuando la frecuencia
del temporizador específico para la
aplicación es muy altaaplicación es muy alta.
Los temporizadores de software evitan
i t i C d l k linterrupciones. Cada vez que el kernel se
ejecuta por algún otro motivo, justo
antes de volver al modo de usuario
examina el reloj de tiempo real para verexamina el reloj de tiempo real para ver
si ha expirado un temporizador de
ft
40
software
Si es así, se ejecuta el suceso
calendarizado sin necesidad de cambiar
al modo del kernel porque el sistema yaal modo del kernel porque el sistema ya
está allí. Una vez efectuado el trabajo, el
t i d d ft t bltemporizador de software se restablece
para que vuelva a dispararse. Lo único
que hay que hacer es copiar el valor
actual del reloj en el temporizador yactual del reloj en el temporizador y
sumarle el intervalo de tiempo fuera.
41
El funcionamiento de los temporizadores
de software depende de la frecuencia con
que se ingrese al kernel por otrosque se ingrese al kernel por otros
motivos, que pueden ser:
Ll d l i tLlamadas al sistema
Fallos de TLB
Fallos de página
Interrupciones de E/SInterrupciones de E/S
La CPU se queda sin trabajo
42