Tema 2 Definiciones y conceptos básicos



Descargar 424.76 Kb.
Página8/8
Fecha de conversión12.11.2017
Tamaño424.76 Kb.
1   2   3   4   5   6   7   8

2.8.4 Planificación del disco

El tiempo de lectura/escritura de un sector del disco depende de tres factores: a) el tiempo de búsqueda del cilindro, b) el retardo rotacional y c) el tiempo de transferencia (ver Figura 2.65). De todos ellos, el único que se puede optimizar desde el programa gestor del disco es el primero, ya que los otros dos dependen de las características propias del disco y del bus de transmisión. Esto se observa claramente si se analizan los resultados del Ejemplo 2.8.2. El motivo de la diferencia de rendimiento entre los accesos secuencial y aleatorio está en el tiempo de búsqueda. Si las peticiones de acceso a los sectores del disco se realizan seleccionando las pistas de forma aleatoria, entonces la velocidad de las operaciones de E/S entre el disco y la memoria principal es muy baja. Una forma de mejorar los resultados consiste en reducir el tiempo medio empleado en las búsquedas. Cuando un programa requiere una operación de E/S del disco, envía la correspondiente llamada al sistema operativo especificándole las siguientes informaciones:

a) Tipo de operación (si se trata de una entrada o de una salida)

b) Dirección en el disco (unidad, cilindro, superficie, bloque)

c) Dirección en memoria

d) Cantidad de información que se va a transferir (número de bytes)

Si está disponible, es posible atender de forma inmediata la petición. No obstante, si la unidad o el controlador del disco se encuentran sirviendo una solicitud anterior, será preciso poner en una cola todas las peticiones que vayan llegando (generalmente provienen de otros programas). En los sistemas con multiprogramación, la mayoría de las veces la cola del disco no estará vacía, de manera que al acabar una petición habrá que elegir una de las que están pendientes de ser servidas.
Planificación FCFS: primero en llegar, primero en ser servido

Este método es la forma más sencilla de gestionar la búsqueda del sector. Se realiza directamente ya que las solicitudes de acceso se van almacenando en una memoria tipo FIFO, de forma que la primera petición que llega es la primera que se sirve; es el algoritmo FCFS (First Come, First Served). Este algoritmo es sencillo de programar y se puede considerar que es inherentemente justo, pero es muy probable que no ofrezca en promedio el mejor tiempo de servicio. Sea, por ejemplo, un disco con 200 pistas para el que se dispone de una cola ordenada en la que se han almacenado las siguientes peticiones de pistas:

22, 124, 105, 181, 142, 36, 5, 59, 115

la posición inicial de la cabeza de lectura/escritura está en la pista 95. En la Tabla 2.18 se resumen los resultados de la estrategia de planificación FCFS. En un principio la cabeza se moverá de la pista 95 a la 22, luego a la 124 y así sucesivamente, atendiendo por el orden de llegada todas las peticiones que se encuentran en la cola.



Próxima pista a la que se accede

22

124

105

181

142

36

5

59

115




Número de pistas que se atraviesan

73

102

19

76

39

106

31

54

56

LMB = 61,8

Tabla 2.18: Algoritmo FCFS de planificación del disco
La longitud media de búsqueda (LMB) es de 61,8. El problema con el algoritmo FCFS está en los movimientos bruscos de vaivén a los que se ve sometida la cabeza de lectura/escritura (por ejemplo ir de la pista 142 a la 36). Si se pudieran atender juntas las peticiones de las pistas 22, 36, 5 y 59 antes o después de las solicitudes de las pistas 124, 105, 181 y 115 disminuiría enormemente el movimiento de la cabeza y el tiempo para servir cada solicitud.
Planificación SSTF: primero la de menor tiempo de posicionamiento

La estrategia SSTF (shortest service time first) consiste en atender la petición que requiere el menor movimiento de la cabeza de lectura/escritura desde su posición actual. De esta forma se elige la opción que incurre en el menor tiempo de búsqueda. Esto sin embargo no garantiza que el tiempo medio de búsqueda a lo largo de un número de movimientos sea mínimo. Como la cabeza se puede mover en las dos direcciones es posible emplear un algoritmo de "tirar la moneda" para resolver los casos de distancias iguales.

En el ejemplo de la cola de solicitudes anterior, la pista más próxima a la posición inicial (95) es la pista 105. Una vez situados en esta pista, la siguiente petición más próxima es la de la 115 y así sucesivamente tal como se muestra en la Tabla 6-7. Este método de planificación da como resultado una longitud media de búsqueda de 29,1, lo que representa una mejora de más del 50% respecto al caso anterior.


Próxima pista a la que se accede

105

115

124

142

181

59

36

22

5




Número de pistas que se atraviesan

10

10

9

18

39

122

23

14

17

LMB = 29,1

Tabla 2.19: Algoritmo SSTF de planificación del disco
Un problema potencial que se puede presentar con el algoritmo SSTF es el bloqueo indefinido (cierre) de algunas peticiones. Conviene observar, que en un sistema real las solicitudes pueden llegar en cualquier momento. Por ejemplo, supóngase que se tiene en la cola dos peticiones, una para la pista 5 y otra para la 181. Si mientras se está atendiendo a la petición de la pista 5 llega la de otra que está próxima a ella, ésta será la siguiente en servirse, por lo que la solicitud de la 181 deberá esperar. Este argumento podría repetirse de forma indefinida con otras pistas cercanas entre si, lo que ocasionaría que la solicitud de la pista 181 espere indefinidamente.
Planificación SCAN

El algoritmo SCAN (rastreo) evita el bloqueo indefinido que se puede producir con la planificación SSTF. La estrategia es ir recorriendo todas las pistas en una dirección y satisfaciendo todas las peticiones que se encuentra en el camino, hasta que alcanza la última pista o no hay más solicitudes en esa dirección. En este punto se invierte el sentido del recorrido y la búsqueda prosigue de la misma forma. También se le conoce como algoritmo del ascensor, por su analogía a como se atienden las llamadas de servicio para desplazarse de un piso a otro en un edificio. En la Tabla 2.20 se ilustra la estrategia SCAN para el ejemplo que se viene tratando (se ha supuesto que el movimiento de la cabeza, desde la posición inicial, era en la dirección de las pistas decrecientes).



Próxima pista a la que se accede

59

36

22

5

105

115

124

142

181




Número de pistas que se atraviesan

36

23

14

17

100

10

9

18

39

LMB = 29,5

Tabla 2.20: Algoritmo SCAN de planificación del disco



Figura 2.69: Comparación de los algoritmos de planificación del disco

Si llega una petición a la cola justo delante de la cabeza se atenderá inmediatamente, mientras que si corresponde a una posición que está por detrás deberá esperar a que se llegue a un extremo del disco y se invierta la dirección de movimiento. Esta consideración muestra que el algoritmo SCAN no explota la localidad de las peticiones al contrario que el algoritmo SSTF. No es difícil ver también que es un algoritmo de planificación, que proporciona ventajas a los procesos cuyas peticiones son a pistas que están localizadas en los cilindros más internos y externos del disco. Este problema se puede subsanar con la planificación C-SCAN.



Planificación C-SCAN

Esta estrategia restringe el rastreo a una única dirección. Así, cuando se ha visitado la última pista en una dirección, la cabeza vuelve al extremo opuesto del disco y comienza otra vez la exploración. De esta forma se consigue reducir el retardo máximo que experimentan las nuevas peticiones. En la Tabla 2.21 se muestra la conducta del algoritmo C-SCAN para el ejemplo propuesto.



Próxima pista a la que se accede

59

36

22

5

181

142

124

115

105




Número de pistas que se atraviesan

36

23

14

17

176

39

18

9

10

LMB = 38,0

Tabla 2.21: Algoritmo C SCAN de planificación del disco
Básicamente, la planificación C-SCAN considera al disco como si fuera circular, con la última pista adyacente a la primera. En la Figura 2.69 se muestra una comparación de los movimientos de la cabeza de lectura/escritura para las cuatro estrategias de planificación analizadas: FCFS, SSTF, SCAN y C-SCAN.
Planificación LOOK y C-LOOK

Tal como se han presentado, las estrategias SCAN y C-SCAN mueven siempre la cabeza desde un extremo del disco al otro. En realidad ninguno de los dos algoritmos se implementan de esta manera, sino que es usual que la cabeza se mueva hasta la última petición en cada dirección. Si no hay peticiones pendientes en la dirección actual, se cambia el sentido del movimiento. A estas variantes de SCAN y C-SCAN se las denomina planificación LOOK (mirar) y C-LOOK, puesto que miran hacia adelante para ver si existe o no una solicitud antes de moverse en esa dirección.


Conclusiones
La memoria es el elemento del computador encargado del almacenamiento y subsiguiente recuperación de datos e instrucciones. La unidad de memoria de un computador presenta un espectro muy amplio de tipos, tecnologías, organización y coste. Un computador típico está equipado con una jerarquía de subsistemas de memoria, unos internos (directamente accesibles por la CPU) y otros externos (accesibles a la CPU a través de módulos de E/S). En el tema 2 se han analizado, en primer lugar, los conceptos fundamentales y las características de los diferentes tipos de memoria. El interés del tema se ha centrado en estudiar la utilización de la memoria como elemento de un computador. De toda la jerarquía de memorias, el tema se ha dedicado fundamentalmente a la memoria interna del computador y en concreto se estudian los siguientes tipos:

1) Memorias de semiconductor

2) Memorias caché

3) Memorias asociativas

4) Memorias compartidas

5) Memorias tipo pila

Por su relevancia práctica las memorias tipo semiconductor han sido tratadas con mayor amplitud. Haciendo un énfasis especial en su organización interna y en el diseño de módulos de memoria de mayor capacidad y longitud de palabra a partir de un módulo básico.

Las memorias caché tienen como principal objetivo acelerar la ejecución de los programas y se sitúan entre la CPU y la memoria principal del computador. Se han analizado los diferentes modos de organización de una memoria caché, las políticas de reemplazamiento de bloques, las estrategias de escritura para mantener la consistencia de la información que almacena y un análisis elemental de su rendimiento.

Las memorias asociativas son memorias direccionables por su contenido y se utilizan cuando se desea recuperar, con gran velocidad, información asociada a determinadas claves. La operación básica de recuperación de información en una memoria asociativa consiste en seleccionar las palabras de memoria que contienen una cierta información denominada clave y extraer la información asociada a dicha clave en las palabras seleccionadas. Se ha analizado brevemente el concepto de memoria compartida, que se emplean cuando más de un recurso de cálculo (por ejemplo 2 CPU's) intentan acceder a la misma unidad de memoria. Se han estudiado las memorias tipo pila que se caracterizan porque devuelven la información en sentido inverso al de su almacenamiento.

Finalmente como sistema de memoria externa se ha analizado su dispositivo más importante: el disco magnético que es la base de este tipo de memorias en casi todos los computadores.


Problemas

1) Representar un sistema digital que está constituido por una CPU, 4 memorias ROM de 1 K x 8 bits y un bus que contiene 12 líneas de dirección y 8 líneas de datos. Añadir la lógica necesaria que seleccione uno de los 4 módulos ROM para cada una de las 4K direcciones.


2) Se dispone de un circuito integrado de memoria RAM de 128 x 8 bits.

a) ¿Cuántos módulos se necesitan para proporcionar una capacidad de memoria de 4.096 bytes?

b) ¿Cuántas líneas del bus de dirección se deben utilizar para acceder a los 4.096 bytes de memoria?. ¿Cuántas de estas líneas son comunes a todos los módulos?

c) ¿Cuántas líneas deben decodificarse para seleccionar cada módulo? Especifíquese el tamaño de los decodificadores.


3) La Mp de un computador utiliza un circuito integrado de memoria RAM de 256K x 1 bits de capacidad.

a) ¿Cuántos módulos se necesitan, y como se deben conectar sus líneas de dirección para proporcionar una capacidad de memoria de 256K x 8 bits?

b) Lo mismo que en el apartado a) para un capacidad de memoria de 1M x 8 bits. c) Lo mismo que en el apartado a) para un capacidad de memoria de 4M x 16 bits.
4) Se dispone de circuitos integrados de memoria RAM de 1024 x 4bits. Estos chips disponen de dos señales de control, CS (selección del chip) y R/W (lectura o escritura). Diseñar con ellos un sistema de memoria de 2K x 8 bits. La memoria debe responder sólo a las direcciones 0400H a 0BFFH y se comunica con el procesador central mediante las líneas de direcciones A15-A0, de datos D7-D0, y las líneas de control MEMR y MEMW. Para decodificar las direcciones utilizar un PLA indicando los términos producto y términos suma que debe incorporar.
5) Un pequeño computador con una longitud de palabra de 8 bits, tiene un bus de dirección de 12 bits. Las primeras 11 líneas de la dirección se utilizan para acceder a un banco de memoria de 2K bytes. El bit más significativo de la dirección se emplea para seleccionar un registro que recibe el contenido del bus de datos. Explíquese como se puede usar esta configuración para extender la capacidad de memoria del sistema aun total de 16K bytes.

6) Un computador de 8 bits de longitud de palabra, necesita 512 bytes de memoria RAM y 512 bytes de memoria ROM. Los circuitos integrados de tipo RAM y ROM que se utilizan se muestran en la Figura 2.70 (las entradas de Selección 2 que están complementadas se activan con un 0).





Figura 2.70: Diagrama de bloque de los módulos RAM y ROM
En la Figura 2.22 se da el mapa de direcciones de memoria que se desea. Efectuar el diseño y mostrar la conexión con la CPU.

Componente

Dirección hexadecimal

RAM 1

0000 - 007F

RAM 2

0080 - 00FF

RAM 3

0100 - 017F

RAM 4

0180 - 0lFF

ROM

0200 - 03FF

Tabla 2.22: Mapa de direcciones de memoria
7) Una memoria caché con una organización asociativa por conjuntos consta de 64 bloques divididos en 4 bloques/conjunto. La memoria principal contiene 4K bloques de 128 palabras/bloque. Definir el formato de dirección de la memoria principal.
8) Un computador tiene una memoria principal de 32K palabras de 16 bits. También tiene una memoria caché de 4K palabras dividida en 4 bloques/conjunto con 64 palabras/bloque. Se supone que inicialmente la memoria caché está vacía. La CPU lee de forma consecutiva el contenido de las posiciones 0,1,2, ...., 4.351. A continuación repite 9 veces más esta secuencia de lectura. La memoria caché es 10 veces más rápida que la memoria principal. Estimar la mejora que se obtiene por la utilización de la memoria caché. Para el reemplazamiento de bloques en la memoria caché se emplea una estrategia LRU.
9) Sea una jerarquía de memoria de dos niveles Mca (caché) y Mp (principal) en un computador, tal como se muestra en la Figura 2.71. Cc y Cp son los costes por bit, Sc y Sp los tamaños, Tc y Tp los tiempos de acceso y h la tasa de aciertos del sistema de memoria.

a) ¿Cuál es el coste por bit del sistema de almacenamiento?

b) ¿Bajo qué condiciones el coste se aproxima a Cp?

c) ¿Cuál es el tiempo medio de acceso, Ta, para el sistema de memoria?

d) Sea r =Tp/Tc la razón de velocidades de las dos memorias y E = Tc/Ta la eficiencia de acceso del sistema. Expresar E en función de r y h, y dibujar esta relación para r = 1, 2 y 10.



Figura 2.71: Jerarquía de memoria de un computador
10) Una memoria caché asociativa por conjuntos dispone de 2 conjuntos y utiliza bloques de 4 palabras. La memoria caché puede contener un total de 2.048 palabras de la memoria principal que tiene un tamaño de 128K x 32 bits.

a) Dar toda la información necesaria para construir la memoria caché.

b) ¿Cuál es el tamaño de la memoria caché?
11) Un computador tiene una unidad de memoria de 64K x 16 bits y una memoria caché de 1 K. La memoria caché utiliza correspondencia directa, con un tamaño de bloque de 4 palabras.

a) ¿Cuántos bits hay en los diferentes campos del formato de dirección?

b) ¿Cuántos bits hay en cada palabra de la memoria caché, y cómo se dividen según su función?

c) ¿Cuántos bloques puede contener la memoria caché?


12) Obtener la función lógica del circuito de coincidencia de una palabra, en una memoria asociativa que tiene un bit de etiqueta que indica si la palabra está activa o inactiva.
13) ¿Qué lógica adicional se necesita para dar un resultado de no coincidencia, en una palabra de una memoria asociativa, cuando todos los bits del registro de máscara M son ceros?
14) En una memoria asociativa dibujar los siguientes diagramas lógicos:

a) Todas las celdas de una palabra, incluyendo la lógica de lectura/escritura de la Figura 2.52 y la lógica de coincidencia de la Figura 2.53.

b) Todas las celdas de una columna. Incluir una línea de salida común para todos los bits que pertenecen a la misma columna.

c) A partir de los diagramas obtenidos en a) y b), mostrar que si se conecta la salida Mi a la línea de "lectura" de la misma palabra, ésta se leerá a condición de que sólo se produzca una coincidencia con el contenido del registro argumento (una vez enmascarado).


15) Obtener la estructura lógica de una celda y de una palabra completa en una memoria asociativa que tiene una salida que indica si el contenido del registro argumento sin enmascarar es mayor que (pero no igual a) la palabra en la memoria asociativa.


1 En la mayoría de las unidades de "disco duro" el disco no está accesible ya que se encuentra en un compartimento estanco. Esta tecnología se conoce como "tecnología Winchester". Su ventaja está en aislar a la unidad de las partículas de polvo del aire lo que permite que las cabezas estén más próximas a la superficie magnética y que las pistas sean más estrechas, aumentando así su capacidad y reduciendo su tamaño y su peso. El nombre proviene de la unidad de disco de IBM 3030 que almacenaba 30 MB en cada lado de una única superficie. El número del modelo es una reminiscencia del famoso rifle Win­chester 3030.


Compartir con tus amigos:
1   2   3   4   5   6   7   8


La base de datos está protegida por derechos de autor ©composi.info 2017
enviar mensaje

    Página principal