Algoritmos de direccionamiento

 Vamos a ver 3 algoritmos de direccionamiento: Primer Algoritmo de direccionamiento.  Se define dirección de memoria como el nombre o referencia que tiene cada posición de memoria. Cada dirección está compuesta por una combinación de bits, cuyo numero depende del número de posiciones que se necesite direccionar. Con 1 bit se pueden generar 2 combinaciones ( 0 / 1 ), con 2 bits 4 combinaciones ( 00 / 01 / 10 / 11 ), con 3 bits 8 combinaciones ( 000 / 001 / 010 / 011 / 100 / 101 / 110 / 111), así hasta n bits, lo que equivale a 2 n combinaciones.
 
 Para el ejemplo que estamos desarrollando (370) cada usuario tiene 16 M posiciones virtuales, lo cual implica 16 M referencias distintas. De aquí deducimos:
 
 2 24 = 16 M nombres
 
 Esto significa que para cada posición de memoria de 8 bits, la dirección de memoria correspondiente contiene 24 bits.
 
 Si se decodifica a decimal una dirección virtual se obtiene el número de orden que ocupa cada posición en la secuencia de posiciones del usuario (empezando en la ceaba).
 
 000000000000000000000000  0 ª (ceaba)
 000000000000000000000001  1 ª
 111111111111111111111111  (16 M –1) ª
 
 Cuando el S.O. necesita acceder a una posición de memoria procede del siguiente modo:
 
 • Accede a la Tabla de Usuarios (TU) de dónde obtiene el lugar físico en memoria dónde comienza el espacio virtual que incluye la posición buscada. En la TU se almacena:
 
 • El identificativo del usuario dentro de la instalación.
 • Un puntero con la dirección física de comienzo del espacio de memoria del usuario, es decir, el lugar dónde por 1ª vez el S.O. guardó información para el usuario.
 
 Usuario D P S
 US – 7 5 2 3
 US – 20 4 1 3
 US – 51 4 0 7
 
 • Lee en el Fichero de Direccionamiento (FD) la dirección de memoria correspondiente a la posición buscada. En el FD se almacena (de forma abstracta:
 
 • El identificativo del usuario
 • El nombre del archivo
 • El dato almacenado
 • La dirección virtual asociada al dato
 
 Supongamos la instrucción IF A = 0 del archivo alfa del usuario US – 7:
 
 Usuario Archivo Dato Dirección virtual
 US – 7 ALFA I 000000000000010000000000 1024 ª
 US – 7 ALFA F 000000000000010000000001 1025 ª
 US – 7 ALFA A 000000000000010000000010 1026 ª
 US – 7 ALFA = 000000000000010000000011 1027 ª
 US – 7 ALFA 0 000000000000010000000100 1028 ª
 US – 20 BETA W 000000000000010000000000 1024 ª
 US – 20 BETA H 000000000000010000000001 1025 ª
 US – 7 ZEPO M 000000000000010000000101 1029 ª
 
 La dirección virtual es por usuario, por lo que se pueden repetir para diferentes usuarios.
 
 • Decodifica la dirección de memoria a decimal y obtiene el número de posiciones que tendrá que recorrer (utilizando en su recorrido los punteros) hasta llegar a la posición buscada.
 
 • Sabiendo el lugar de comienzo y el número de desplazamientos realiza la localización física.
 
 Si el número de desplazamientos es pequeño la búsqueda será breve, si no habría que recorrer hasta 16 M posiciones (en el peor de los casos), consumiendo para ello mucho tiempo.
 
 • Tabla de Páginas (2 º algoritmo de direccionamiento)
 
 Surge para solventar el problema que supone las búsquedas excesivamente largas. Los espacios virtuales se subdividen en páginas (cada una de ellas de 4 K ó 4096 posiciones de memoria, para el ejemplo desarrollado). Si se divide el espacio virtual de un usuario (16 M) entre el tamaño de la página (4 K) se obtiene el número de páginas por usuario:
 
 16 M / 4 K = 4 K páginas / usuario (4096 páginas / usuario)
 
 Cada usuario dispone, pues, de 4096 páginas de 4096 posiciones de memoria.
 
 La Tabla de Páginas (TP) es un archivo que se ubica en la Z c y en la que se almacena:
 
 • El número de página
 • Un puntero con la dirección física de memoria dónde comienza la página
 
 Importante: Con este algoritmo, en la TU el puntero de cada registro señala el lugar de comienzo de cada TP. El FA permanece inalterable respecto al algoritmo anterior
 
 Ahora el algoritmo de búsqueda es el siguiente:
 
 1. Accede a la TU de la que obtiene el lugar físico de la memoria dónde comienza la TP del usuario.
 
 2. Del FD obtiene la dirección de memoria de la posición buscada
 
 3. Decodifica los 12 primeros bits (de izquierda a derecha) obteniendo el numero de página, se sitúa en el registro correspondiente y lee el puntero que le indica la dirección física dónde comienza la página.
 
 4. Decodifica los 12 siguientes bits y obtiene el desplazamiento dentro de la página, con lo que ya se puede situar en la posición buscada
 
 Con este algoritmo se reduce enormemente el número de búsquedas (8 K saltos en el peor de los casos) : primero en una TP de 4 K registros y , segundo, en 4 K posiciones de memoria dentro de la página.
 
 • Tabla de Segmentos (3 er algoritmo de direccionamiento)
 
 Se emplea para reducir el tamaño de las TP. Se define segmento como un conjunto o agrupación de páginas. Para el ejemplo que estamos desarrollando el tamaño del segmento es de 64 páginas. Si se divide el número de páginas entre el tamaño del segmento, se obtiene el número de segmentos por usuario:
 
 4 K / 64  4906 / 64  64 segmentos / usuario
 
 De todo esto se deduce que cada usuario dispone de una Tabla de Segmentos (TS) de 64 registros cada una y de 64 TP de 64 registros cada una.
 
 La TS se ubica en la Z c y almacena en cada registro los siguientes datos:
 
 • El número de segmento
 • Un puntero con la dirección física de comienzo de la TP asociada
 
 El algoritmo de búsqueda es el siguiente:
 
 1. Accede a la TU de la que obtiene el lugar físico de la memoria dónde comienza la TS del usuario.
 
 2. Lee en el FD la dirección de memoria correspondiente a la posición buscada.
 
 3. Decodifica los 6 primeros bits (de izquierda a derecha) obteniendo el número de segmento. Con este valor recorre la TS hasta situarse en el registro correspondiente, del que lee el puntero que le indica la dirección física donde comienza la TP.
 
 4. Decodifica los 6 siguientes bits obteniendo el número de página. Con este valor recorre la TP hasta situarse en el registro correspondiente, del que lee el puntero que le indica la dirección física de memoria dónde comienza la página.
 
 5. Decodifica los 12 siguientes bits obteniendo el desplazamiento dentro de la página. Con este valor recorre la página hasta situarse en la posición de memoria buscada.