Tema 2 Definiciones y conceptos básicos



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

Tabla 2.15: Asignación de la menor prioridad mediante la rotación de prioridades
Memorias tipo pila

Estas memorias devuelven la información de modo inverso al de su almacenamiento, y por lo tanto, se caracterizan por el hecho de que sólo se puede leer el último dato almacenado en ellas. También se las conoce por el nombre de memorias LIFO (Last In First Out). Desde el punto de vista del acceso a los datos funcionan como memorias de acceso secuencial.. A diferencia de una memoria RAM en la que cualquier dato almacenado puede ser accedido en cualquier momento, a los datos almacenados en una pila sólo se puede acceder a través de una posición concreta. Se pueden ver así como un componente de memoria con un acceso limitado.

Únicamente se puede extraer el dato almacenado en la cumbre de la pila. Cuando se inserta un dato en la pila sustituye al que estaba en la cumbre y toda la información almacenada en la pila desciende un lugar hacia abajo. Deforma recíproca, cuando se extrae de una pila (el dato extraído es el que ocupa la cumbre de la pila) toda la información almacenada en la pila asciende un lugar hacia arriba (ver Figura 2.56). Cuando se diseña una pila de inserción/extracción, desde este punto de vista, la cuestión importante a considerar es que los datos almacenados se desplazan en una posición descendente o ascendente en las operaciones de inserción y extracción respectivamente. Para su implementación hardware se pueden utilizar tanto registros de despla­zamiento como un contador reversible.



Figura 2.56: Operaciones de inserción/extracción en una pila implementada con registros de desplazamiento
La principal desventaja de la realización con registros de desplazamiento es el gran número de ellos que se necesitan cuando se diseña una pila de gran capacidad, lo que encarece su coste. Por esta razón una forma más efectiva de ver las operaciones de inserción/extracción en una pila es la que se muestra en la Figura 2.57 en la que los datos en la pila no modifican sus posiciones y lo que se hace es incrementar o decrementar el valor de la cumbre de pila. La implementación ahora es posible hacerla empleando una memoria RAM. Como las memorias RAM no son capaces de desplazar su contenido, las operaciones de inserción y extracción en estas pilas se realizan de una manera algo diferente: cambiando la posición de la cumbre de la pila. En otras palabras, al insertar datos en la pila, la dirección de la cumbre se incrementará por cada inserción y por el contrario se decrementará en cada extracción.



Figura 2.57: Operaciones de inserción/extracción en una pila que modifica el valor del puntero cumbre de pila
Se analizan a continuación estas dos formas de realizar una memoria tipo pila:

a) Mediante un conjunto de registros convenientemente interconectados.

Es la organización usual de una pila cuando ésta forma parte de la propia CPU (ver Figura 2.58). Cada uno de los registros que constituyen la pila puede copiarse sobre los registros adyacentes. Desde el exterior sólo se pueden hacer operaciones de inserción/extracción sobre el registro R1 (cumbre de la pila).





Figura 2.58: Registros interconectados como memoria pila
En la Figura 2.59 se muestra la realización de una pila con k registros de 1 bit/registro. Cuando la señal R/W = 0 se está en modo de lectura o inserción y el dato de entrada De se carga en el elemento de memoria 1 (que es la cumbre de la pila) y el contenido del elemento de memoria j se transfiere al elemento de memoria j + 1 (j = 1, 2, ..., k), con lo que la información desciende a lo largo del registro de desplazamiento. Cuando la señal R/W = 1 se está en modo de escritura o extracción y el contenido del elemento de memoria 1 se transfiere como dato de salida Ds y el contenido del elemento de memoria j+1 se transfiere al elemento de memoria j (j = 2, ..., k), con lo que la información asciende a lo largo del registro de desplazamiento.



Figura 2.59: Pila con k registros y 1 bit/registro
Se puede construir fácilmente una pila con k registros de m bits/registro interconectando adecuadamente m pilas del tipo anterior (ver Figura 2.60).



Figura 2.60: Pila con k registros y m bits/registro
b) Mediante un conjunto de palabras de la memoria principal.

Para efectuar esta realización de la pila, el procesador dispone de un registro especial que se conoce como puntero de pila o registro SP (Stack Pointer). El procesador posee también un repertorio de instrucciones que le permiten realizar las operaciones básicas de inserción y extracción de un dato en la pila.

El contenido del puntero de pila especifica siempre la posición de memoria donde se ha de almacenar el próximo dato que se introduzca en la pila (ver Figura 2.61).

En consecuencia, será necesario para la realización de una pila en memoria, que la CPU disponga de instrucciones que de forma automática incremente o decremente el contenido del registro SP, cada vez que se realiza un acceso a la pila.





Figura 2.61: Zona de la memoria principal utilizada como pila
En la Tabla 2.16 se resumen las ventajas y desventajas de las dos formas de realizar una pila.




Pila realizada como conjunto de registros

Pila formada por una zona de la memoria principal

Ventajas

• Velocidad alta

Utiliza la memoria principal

• Coste bajo

• Gran capacidad


Desventajas

• Hardware propio en la CPU

• Coste alto

• Capacidad limitada


• Velocidad baja

Tabla 2.16: Comparación de las dos formas de realizar una pila
A veces se suelen dar realizaciones de carácter mixto, en las que las primeras posiciones de la pila están soportadas por un conjunto de registros del procesador y el resto de la información sobre posiciones de memoria.
2.7.1 Aplicaciones de las memorias tipo pila

Entre las aplicaciones más clásicas de este tipo de memorias se pueden mencionar las siguientes:

a) En el salto a subrutinas, para almacenar la dirección de retorno. El empleo de una pila facilita el tratamiento de los saltos anidados.

En la Figura 2.62 se muestra de forma esquemática la utilización de una memoria tipo pila en la construcción de instrucciones de salto a subrutina con varios saltos concatenados, en cuyo caso se utiliza la pila para almacenar las direcciones de ruptura de secuencia.





Figura 2.62: Utilización de una pila en el salto a subprogramas

b) En el tratamiento de interrupciones, para guardar el estado de los registros del procesador antes de la interrupción. También simplifica el tratamiento de interrupciones anidadas (ver apartado 3-4.4).

c) En la compilación de expresiones aritméticas.

El siguiente ejemplo ilustra la evaluación de la expresión (A + B) x (C - D) en un computador hipotético que se basa en la utilización de una pila. Se supone que la instrucción PUSH inserta el contenido del registro D0 en la pila. Las instrucciones SUM, RES y MUL todas ellas extraen los dos operandos que necesitan de la parte superior de la pila, realizan la operación indicada e insertan el resultado otra vez en la cumbre de la pila. Finalmente POP extrae el contenido de la posición de memoria referenciada por la cumbre de la pila y lo almacena en el registro D0.


1 MOVE A, D0 Copia el contenido de A en D0

2 PUSH Inserta el contenido de D0 en la pila

3 MOVE B, D0 Inserta el contenido de B en D0

4 PUSH Inserta el contenido de D0 en la pila

5 ADD Suma los dos operandos en cumbre y deja resultado en cumbre de pila

6 MOVE C, D0 Copia el contenido de C en D0

7 PUSH Inserta el contenido de D0 en la pila

8 MOVE D, D0 Copia el contenido de D en D0

9 PUSH Inserta el contenido de D0 en la pila

10 SUB Resta los dos operandos en cumbre y deja resultado en cumbre de pila

11 MUL Multiplica los dos operandos en cumbre y deja resultado en cumbre de pila

12 POP Extrae el resultado de la cumbre de pila y lo almacena en D0


La Figura 2.63 representa el estado de la pila en diferentes etapas de la ejecución del segmento de programa anterior. Los números debajo de cada diagrama se corresponden con el número de línea del programa.



Figura 2.63: Estado de la pila en la evaluación de la expresión (A + B) x (C   D)
Discos magnéticos

Los discos son el principal soporte (y en muchos sistemas el único) para la memoria secundaria y el sistema de archivos, por ello en esta sección se estudiarán las características funcionales y la organización de la información en estos periféricos.


2.8.1 Estructura física

El medio físico de almacenamiento de los datos es una película de óxido magnético que recubre a un disco que se parece a los de grabación fonográfica. Estos platos de grabación pueden ser extraíbles o fijos, dependiendo de si pueden ser extraídos o no de la unidad. Una unidad también puede disponer de varios platos. En la Figura 2.64 se muestra la configuración mecánica básica de una unidad de disco.





Figura 2.64: Configuración mecánica de una unidad de disco
Sea el disco extraíble o fijo, una vez situado en la unidad el funcionamiento es similar. Los discos giran a una velocidad constante (superior a las 3.000 rpm, aunque la velocidad de giro de los discos extraíbles es menor). El número de discos varía entre 1 (para los disquetes) y 20 en los discos de gran capacidad. Los datos se leen y escriben mediante cabezas de lectura/escritura montadas de forma que contacten con la parte del disco que contiene los datos. Cada disco tiene dos superficies (o caras) por lo que hay dos cabezas de lectura y escritura para cada disco. Los datos se almacenan en las superficies magnéticas del disco en forma de círculos concéntricos llamados pistas. Se llama cilindro al conjunto de pistas de todas las superficies que están a la misma distancia del eje del disco. Las pistas se dividen en sectores y cada sector contiene varios centenares de bytes:
Conviene advertir que, como la velocidad de giro, el número de sectores por pista y el número de bytes por sector son constantes pero las pistas tienen distinto radio, la densidad de grabación en las pistas internas será mayor que en las externas. Es posible optimizar la superficie magnética del disco (aumentando así su capacidad) si el número de sectores por pista es menor cuanto más interna sea ésta. Normalmente no se considera esta posibilidad ya que complica el diseño del controlador asociado y de su software. Sin embargo, es previsible que en el futuro inmediato comiencen a aparecer en el mercado unidades de discos con estas características cuando se generalice el uso de controladores basados en la norma SCSI.

Dependiendo del número de cabezas, los discos pueden ser de cabeza fija o de cabeza móvil. Los de cabeza fija tienen generalmente una cabeza de lectura/escritura por cada pista, de forma que a un sector se accede activando la cabeza sobre la pista apropiada cuando el sector pasa bajo ella. El tiempo necesario para acceder al sector deseado se denomina latencia rotacional (o tiempo de espera) y en promedio es igual a la mitad del tiempo de revolución del disco. La velocidad típica de giro de los discos suele ser de 3600 rpm que equivale a dar una revolución cada 16,7 mseg. Así el retardo medio rotacional será de 8,3 mseg. Los disquetes giran sin embargo mucho más lentamente, entre 300 y 600 rpm, por lo que el tiempo medio de latencia estará comprendido entre 100 y 200 mseg.



Los discos de cabeza móvil tienen una cabeza o unas pocas cabezas de lectura/escritura por superficie. En este caso, la lectura de un sector requiere que el montaje de las cabezas sea desplazado hasta el cilindro correspondiente, tras de lo cual se activa la cabeza cuando el sector deseado pasa bajo ella. En este caso el tiempo de acceso (ta) está compuesto por el tiempo de posicionamiento de la cabeza o tiempo de búsqueda (tb) y el tiempo de latencia rotacional (tr). Debido a estas dos componentes en el tiempo de acceso hay una gran variabilidad de unos discos a otros. Pero una vez alcanzado el sector, la velocidad de transferencia de datos de los discos actuales suele ser del orden de 5 Mb/seg. Debido a estas velocidades elevadas, lo normal es usar técnicas de acceso por DMA para la transferencia de datos entre los discos y la memoria principal. En la Tabla 2.17 se muestran el rango de los parámetros de los discos actuales.

Número de superficies

2 ≤ S ≤ 40

Número de cilindros

40 ≤ C ≤ 2000

Número de sectores por pista

10 ≤ S ≤ 100

Número de bytes por sector

256, 512 o 1024

Capacidad del disco

360 KB ≤ M ≤ 10 GB

Tasa de transferencia

60 KB/s ≤ N ≤ 4 MB/s

Tiempo medio de búsqueda

1 mseg ≤ tbm ≤ 50 mseg

Tiempo de búsqueda (cilindros contiguos)

0.1 mseg ≤ tbc ≤ 5mseg

Tiempo medio de espera

10 mseg ≤ te ≤ 200 mseg

Tiempo de transferencia de un sector

0.1 mseg ≤tt ≤ 20 mseg

Tiempo de encendido/apagado del motor

10 mseg ≤ te ≤ 200 mseg

Tabla 2.17: Parámetros típicos de los discos
En resumen, el tiempo que se precisa para que los datos se transfieran desde el disco a la memoria principal del computador se compone de los tres tiempos siguientes (ver Figura 2.65):

1) Tiempo de búsqueda (tb): Es el tiempo necesario para que las cabezas se desplacen al cilindro adecuado. Consta de dos componentes claves: el tiempo de arranque inicial (ti) y el tiempo que se tarda en recorrer todos los cilindros que hay entre la pista inicial y la final. Desgraciadamente no es una función lineal del número de pistas que tiene el disco. Se suele aproximar con la fórmula siguiente:

tb = m × n + ti

donde

m = cte que depende de la unidad del disco


en un disco con tecnología Winchester1 de bajo coste para computadores personales m  0.3 mseg y ti  20 mseg, mientras que para discos más caros son m  0.1 mseg y ti  3 mseg
2) Retardo rotacional (tr): Es el tiempo medio que tarda el sector en estar debajo de la cabeza de lectura/escritura. Si f es la velocidad de rotación en revoluciones por segundo, tr se puede expresar por:



3) Tiempo de transferencia (tt): Es el tiempo que se tarda en transferir los datos. Depende del tamaño del sector y es el menor de los tres. Si b es el número de bytes que se desean transferir y P el número de bytes que hay en una pista, tt se puede expresar como:





Figura 2.65: Temporización de la transferencia de E/S del disco
En algunos supercomputadores, con el fin de mejorar el rendimiento de la transferencia de datos entre el disco y la memoria principal, se suele emplear una técnica conocida como sensor de posición rotacional. La forma en la que opera es la siguiente: cuando se emite una orden de "búsqueda de un sector" se libera el canal para manejar las operaciones de E/S. Al finalizar esta orden, el dispositivo determina en que momento el sector pasará por encima de la cabeza y cuando se va aproximando intenta restablecer de nuevo la comunicación. En el caso de que la unidad de control del computador o el canal estén ocupados atendiendo a otra operación de E/S fallará el intento de reconexión y el dispositivo deberá girar una vuelta completa antes de volver a intentarlo otra vez.
2.8.2 Ejemplo: Tiempo de acceso a un archivo de acceso secuencial y aleatorio

Es preciso tener presente que uno de los factores dominantes a la hora de medir la velocidad de las operaciones de E/S entre el disco y la memoria principal es la forma como está organizado el archivo que se va a transferir. Para poner esto de manifiesto se supone que se desea leer un archivo que tiene un tamaño de 256K. El disco utilizado tiene los siguientes parámetros

tiempo medio de búsqueda = 25 mseg

velocidad de transferencia = 800 Kb/s

tamaño del sector = 256 bytes

número de sectores por pista = 64

Se van a considerar dos situaciones extremas en cuanto a la organización del archivo en el disco

1) Acceso secuencial. El archivo está almacenado de la forma más compacta posible ocupando 1024 sectores localizados en 16 pistas contiguas

2) Acceso aleatorio. El archivo está almacenado de forma que los sectores están distribuidos aleatoriamente por su superficie

En la Figura 2.66 se muestra el tiempo total empleado en la lectura del archivo en los dos casos. En el acceso secuencial se ha supuesto que una vez leída la primera pista, en las restantes el tiempo de búsqueda es despreciable al estar ya posicionada correctamente la cabeza de lectura. Resulta claro, de este ejemplo, que el orden en el que se leen los sectores del disco tiene un efecto muy importante sobre su rendimiento.


2.8.3 Controlador del disco

Las señales típicas entre el controlador del disco y la unidad propiamente dicha están indicadas en la Figura 2.67. Puesto que un controlador puede manejar varias unidades de características similares, se necesitan algunas líneas de control para seleccionar la unidad, son las marcadas como líneas de selección de unidad. Análogamente, las líneas de .selección de cabeza se utilizan para activar la cabeza de lectura/escritura de la unidad adecuada. Después vienen las líneas de dirección, paso, leer ,y escribir, la primera de ellas indicarán como se desplazará la cabeza desde la situación actual (hacia dentro o hacia fuera), la segunda proporciona una secuencia de impulsos, y la tercera y cuarta se usa para activar la cabeza seleccionada. Las líneas de entrada y salida de datos transportan los bits leídos del disco o los que hay que grabar en el mismo según sea la operación de lectura o de escritura. Después vienen una serie de entradas como las de reinicializar, indicación de fallo, etc.




Figura 2.66: Lectura de un archivo mediante acceso secuencial y acceso aleatorio



Figura 2.67: Señales entre el controlador y la unidad de disco
Las funciones y estructura del controlador del disco se verá en el tema 3 cuando se estudien los controladores de E/S. El control de errores es necesario para detectar los errores transitorios provocados por ruidos e interferencias electromagnéticas y para manejar los defectos del medio de almacenamiento. Cada vez que se escribe un dato en el disco, el controlador calcula los bits de verificación y los añade a la información que se transmite. Como los errores de disco ocurren en secuencias y producen errores en cadenas de bits sucesivos, los controladores suelen utilizar mecanismos de detección capaces de tratarlos, como los códigos de redundancia crítica. Dependiendo de la causa, un error puede ser transitorio o permanente. Los primeros se corrigen leyendo varias veces el sector correspondiente. Si después de unas cuantas lecturas (que dependen de un parámetro denominado contador de reintentos) el error persiste, éste se trata como permanente. En este caso el bloque queda marcado como defectuoso, de forma que se impide su utilización. La misión de evitar el uso de los bloques defectuosos corresponde generalmente a una capa de bajo nivel del sistema de control de archivos. Los bloques defectuosos pueden ser detectados durante la fase de inicialización del disco.

Otros errores, denominados errores de búsqueda, pueden deberse a problemas mecánicos en las cabezas. Un ejemplo de esta clase puede ser que el brazo de la cabeza de lectura/escritura no se posiciona correctamente. Algunos controladores corrigen automáticamente los errores de búsqueda, pero otros sólo activan un bit de error y pasan el resto del problema al manejador, que se encarga del error enviando una orden de recalibración.

Un aspecto que conviene considerar es la necesidad de que el controlador disponga de un buffer interno para el almacenamiento temporal de los datos. La razón es que una vez se ha iniciado una operación de E/S desde el disco, los datos se transfieren a velocidad constante, independientemente de que el controlador esté preparado o no para recibirlos. Si el controlador pretende transferirlos directamente a la memoria es preciso que utilice el bus del sistema, que sin embargo podría estar ocupado por otro dispositivo. La utilización de un buffer interno hace innecesario el bus del sistema hasta que comienza el acceso por DMA (lo que facilita el diseño del controlador ya que la transferencia a memoria mediante DMA no impone limitaciones de tiempo) y tiene consecuencias importantes en la gestión del sistema de E/S. Cuando el controlador o la propia CPU están transfiriendo los datos a la memoria (operación de salida), el siguiente sector estará pasando por debajo de las cabezas de lectura de manera que la información correspondiente estará llegando al controlador (operación de entrada). Si éste tiene un diseño sencillo no permite realizar de forma simultánea la entrada y la salida de datos por lo que durante la transferencia a memoria no hay posibilidad de leer el siguiente sector.

Como resultado del argumento anterior se deduce que este tipo de controladores no es capaz de leer bloques contiguos de información (que están en sectores adyacentes). Así, la lectura de una pista completa requiere al menos dos rotaciones, una para los sectores pares y otra para los impares (ya que si el tiempo de transferencia de los bloques desde el controlador a la memoria fuese mayor que el empleado en leerlos desde el disco, podría ser necesario leer un bloque y seguidamente saltar dos o más). Esta técnica de saltar bloques, para dar un margen de tiempo suficiente para que el controlador transmita los dato a la memoria, se llama entrelazado. Por esta razón cuando se formatean los discos, los sectores se numeran teniendo en cuenta el factor de entrelazado. En la Figura 2.68 se muestra un disco con 16 sectores por pista formateado con distintos factores de entrelazado.

Hay pues una gran variedad de controladores de discos, aunque cada vez son más "inteligentes", encargándose de muchas de las funciones que anteriormente se hacían por software, como son el formateo o inicialización de los discos, el almacenamiento en buffers o la agrupación de los datos en bloques.
Las funciones que se tienen que hacer en un disco se pueden describir mediante una típica rutina de disco, que básicamente permita la lectura y escritura de sectores especificados por medio de direcciones físicas de la forma siguiente:

Las órdenes elementales al nivel de la rutina son buscar, leer y escribir. En algunas implementaciones las peticiones de leer y escribir tienen que venir precedidas por órdenes de búsqueda.





Figura 2.68: Entrelazado de bloques
Como las transferencias de datos entre el disco y la memoria se hace mediante DMA, la rutina de disco no devuelve datos explícitos a sus invocadores, excepto la información referente al resultado de la operación. Cuando se detecta una excepción, como por ejemplo un error de lectura o un fallo de la unidad, la rutina del disco indica el número real de bytes transferidos correctamente antes del error. Otras órdenes de la rutina pueden incluir algunos modos de manejo de la unidad de almacenamiento, como el de formatear una pista o marcar un bloque como defectuoso.

Algunas rutinas y controladores son capaces de transferir múltiples sectores o incluso pistas, en respuesta a una sola orden. Esto presenta la ventaja de que las cabezas sólo se tienen que posicionar una vez, lo que reduce el tiempo medio de acceso para muchos sectores. Estas operaciones requieren que los datos ocupen direcciones consecutivas de disco.



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