Instituto Tecnológico de la Laguna Departamento de ... Educativa... · 1.3 Relocalización 1.4 Multiples particiones contiguas fijas 1.5 Multiples particiones contiguas variables

Ing. Lamia Hamdán Medina Sistemas Operativos II. 1

Instituto Tecnológico de la Laguna

Departamento de sistemas y Computación

Actualización de apuntes

Sistemas Operativos II

MA Ing. Lamia Hamdán Medina

Agosto del 2004


Sistemas Operativos II Objetivo General “Conocer las técnicas y políticas de la administración de memoria, sistemas de archivos y disco de un sistema operativo; así como sus mecanismos de protección.”


UNIDAD I

AMINISTRACIÓN DE LA MEMORIA Objetivo “El alumno conocerá las diferentes técnicas que ha llevado la administración de memoria desde sus inicios, como base de los sistemas operativos actuales” Temario 1.1 Protección del hardware 1.2 Protección de la memoria 1.3 Relocalización 1.4 Multiples particiones contiguas fijas 1.5 Multiples particiones contiguas variables 1.5.1 Compactación 1.6 ¿cómo administran los virus la memoria? Bibliografía

1. Sistemas Operativos Modernos Autor: Andrew Tanenbaum Editorial: Prentice may Pag 201-211 2. Apuntes de la materia Sistemas Operativos II

Administración de memoria

Introducción

La parte del sistema operativo que se encarga de la memoria se llama administrador de la memoria. Su labor es la de llevar el control de qué partes de la memoria están en uso y cuáles no lo están, asignar memoria a procesos cuando la necesiten y retirárselas cuando terminen, y administrar el intercambio entre la memoria central y el disco cuando la memoria central no baste para contener todos los procesos.


1.1 Protección del hardware

Cuando sucede un error, el hardware es el primero en detectar el error en el sistema operativo. Cuando detecta el error, manda una señal (trampa) mediante interrupciones, con esto, el sistema operativo crea un archivo de vaciado o bien de respaldo, esto sucede muy comúnmente con Microsoft Word®, cuando éste programa no responde, se crea un archivo en donde se recuperan los datos que había en el documento antes de que Word dejará de funcionar. 1.2 Protección de la memoria

El esquema de administración de la memoria más simple posible consiste en tener un solo proceso en la memoria a la vez y en permitir que ese proceso use toda la memoria. El usuario carga toda la memoria en un programa de disco o cinta y se adueña de toda la máquina. Aunque este método fue común hasta el año de 1960, ya no se utiliza. Ahora la memoria física de una computadora es comúnmente dividida en dos áreas, memoria del monitor residente y memoria del usuario. El monitor residente es un programa que automáticamente transfiere el control de un programa, al siguiente proceso, un ejemplo de esto es el Sistema Operativo.

El problema principal de este esquema es el proporcionar una protección eficiente que evite que programas del usuario modifiquen (accidentalmente o intencionalmente) código o datos del monitor residente, ya que esto dejaría fuera de acción al sistema operativo. Existen varias soluciones a este problema, pero el mas común es el de utilizar un registro de límite de dirección comúnmente llamado "registro barrera" (fence register), en el cual se coloca la dirección de la primera posición de memoria que un programa del usuario puede utilizar. Esto se ilustra en la siguiente figura.

En este esquema, cada dirección generada por una instrucción o dato de un programa, es comparada con el contenido del registro barrera. Si la dirección generada es mayor o igual que la barrera, entonces la dirección es válida ya que comprende alguna localidad de la memoria del usuario. En caso contrario, se trata de una referencia ilegal,


por lo que se genera una interrupción al S.O. para que maneje este tipo de error (generalmente imprime un letrero y aborta el programa).

La dirección del registro de barrera puede ser cambiada según las necesidades de memoria, por ejemplo si crece el monitor residente al actualizarlo. Otro problema a considerar es la carga en memoria de los programas del usuario. Aunque la dirección de la memoria de la computadora empieza en 00000, la primera dirección del programa del usuario no puede ser 00000, sino la primera dirección más allá de la barrera.

Una de las formas de corregir esto es al tiempo de compilación, ya que si se conoce la dirección de la barrera, se pueden generar direcciones absolutas que comiencen y se extiendan a partir de la barrera. Sin embargo, si la dirección de la barrera cambia, es necesario recompilar el programa para poder ser corrido nuevamente.

1.3 Relocalizacion

Cuando un programa se enlaza (es decir, el programa central, procedimientos escritos por el usuario y procedimientos de biblioteca se combinan en un solo espacio de dirección), el enlazador debe saber en qué dirección comenzará el programa en la memoria.

Una mejor alternativa al método de direcciones absolutas, consiste en generar direcciones relativas o relocalizables, las cuales no toman en cuenta el valor de la barrera al momento de compilación, sino que la corrección es diferida hasta el tiempo de carga o de ejecución del programa.


En el primer método, al momento de cargar el programa en memoria, el valor de la barrera es sumado a todas las direcciones en que debería cargarse cada instrucción o dato del programa, así como también a las direcciones a las que hace referencia cada instrucción (variables del programa), de tal forma que siempre se tengan direcciones a partir de la barrera. Este método funciona siempre y cuando la barrera no cambie durante la ejecución del programa, sino solamente antes de correr el programa (por ejemplo, entre programa y programa). Debido a esta condición de barrera estática, se dice que se tiene "Relocalización Estática". En muchos casos, los sistemas operativos cuentan con partes transitorias que se pueden eliminar y volver a cargar.

Por ejemplo, en los casos en que algún manejador de dispositivo no se utilice frecuentemente, puede ser quitado para utilizar ese espacio de memoria para programas del usuario, y volver a cargarlo cuando sea requerido por algún programa en ejecución. Este esquema, hace que sea necesario cambiar la dirección de la barrera incluso durante la ejecución de un programa.

Una solución a este problema es cargar el programa en memoria igual que en el método anterior, sumándole el valor de la barrera a todas las direcciones generadas por el compilador, excepto a las direcciones a que hacen referencia las instrucciones del programa (variables); éstas son dejadas tal cual. La corrección es hecha hasta el momento en que al ser ejecuta cada instrucción en el CPU, se genere un intento de accesar a la memoria. En ese momento, a la dirección generada le es sumado el valor de la barrera y luego es enviada a la memoria. Por lo tanto, el usuario siempre trabaja con direcciones lógicas (las generadas por el compilador), y el hardware de relocalización se encarga de generar direcciones físicas. Por ejemplo si la barrera se encuentra en 1700, cualquier intento de accesar a la localidad 0000, será automáticamente relocalizada a 1700. Un acceso a la localidad 515, será relocalizada a la 2215. A este sistema se le llama “Relocalización dinámica” ya que la barrera puede ser cambiada en cualquier momento. El esquema del hardware utilizado es el siguiente.

En este sistema, el registro barrera es ahora llamado registro base.


Por lo tanto, si es necesario cambiar la barrera, solo es necesario cambiar el contenido del registro base, y trasladar el programa del usuario a las nuevas localidades de memoria relativas a la nueva barrera, y continuar con la ejecución del programa.

Los sistemas anteriormente vistos, funcionan bien para sistemas operativos uniprogramados; sin embargo, si cargamos más de un programa en el área del usuario, ya no proporcionan la protección debida, ya que si bien el S. O. queda protegido, los programas de los usuarios no. Considere el siguiente esquema.

Si ejecutamos el programa del usuario1, es posible que éste pueda modificar el código o los datos de los programa 2 y 3. Si movemos la barrera hasta el inicio del programa 2, el programa 1 queda protegido al igual que el monitor; sin embargo, el programa 3 queda aún desprotegido.

Una solución a este problema, es utilizar dos registros para delimitar plenamente la memoria del programa en ejecución. Esto se ilustra en las siguientes figuras.

Los límites se implementan con registros igual que anteriormente. De esta manera, si el programa en ejecución es el 2, el monitor y el programa 1 quedan protegidos por el límite inferior, mientras que el programa 3 queda protegido por el límite superior. Una vez finalizada la ejecución del programa 1, los registros son movidos al programa 2, y así sucesivamente.


Este esquema de cambio de barreras obviamente requiere un sistema de relocalización dinámica. El hardware utilizado para tal efecto es el siguiente.

El registro de límite checa por el límite superior que puede generar un programa antes de ser relocalizado dinámicamente por el registro base mientras que el límite inferior queda definido por la dirección 0000 que generan los compiladores.

Así por, ejemplo en la figura de arriba tenemos como límites 0000 + 1600 = 1600 como límite inferior, y 3000 + 1600 = 4600 como límite superior. Todas las direcciones generadas por el programa del usuario 2 deben de estar en ese rango o se generará un error.

El uso del esquema anterior u otros similares permiten tener más de un usuario residente en memoria simultáneamente, ya que es posible dividir la memoria en múltiples regiones llamadas particiones.

Dos posibles métodos se derivan de este esquema:

• Múltiples particiones contiguas fijas • Múltiples particiones contiguas variables.

1.4 Multiples particiones contiguas fijas

En esta opción, se seleccionan regiones fijas de memoria para crear procesos, por ejemplo una región de 10 K bytes para procesos muy pequeños, regiones de 20 K para procesos de tamaño promedio, y 50 K para procesos grandes.

Es útil tener más de un proceso en la memoria al mismo tiempo. Entonces la pregunta es: ¿Cómo debe organizarse la memoria para lograr este objetivo?. La manera más simple consiste en dividir la memoria en n particiones (posiblemente desiguales). Por ejemplo, esta partición puede ser efectuada en forma manual por el operador cuando el sistema dé inicio.


Cuando un proceso llega del exterior, es puesto en la cola de procesos o spool manejada por el asignador de procesos, cuando le toca su turno (generalmente en forma PEPS), la cantidad de memoria que requiere es tomada en cuenta y es comparada contra las regiones de memoria vacías; si el proceso puede ser cargado en alguna de ellas lo hace, pero si no, entonces busca el siguiente que pueda ser cargado en las regiones disponibles. Para saber que regiones de memoria están disponibles, se implementa una lista llamada "cola de regiones de memoria disponibles", en la cual se anota la cantidad de memoria del hueco libre y la dirección donde inicia. Como en este esquema las particiones son fijas, cualquier espacio que no utilice un trabajo en una partición se pierde.

La desventaja de ordenar los trabajos que llegan en listas de espera separadas se vuelve evidente cuando la lista de espera de una partición grande está vacía pero las de una partición pequeña esta repleta, como sucede en el caso de las particiones 1 y 3 de la figura a. Una organización alternativa consiste en conservar una sola lista de espera (como en la figura b). Siempre que una partición quede libre, el trabajo más próximo al frente de la lista de espera que queda en ella podría cargare en la partición vacía y ejecutarse. Como es indeseable desperdiciar una partición grande con un trabajo pequeño, una estrategia diferente consiste en buscar en toda la lista de espera de entrada siempre que una partición quede libre y tomar el trabajo más grande que quepa en ella.

El asignador de procesos también busca optimizar el desperdicio de memoria; es decir, no cargar programas muy pequeños en regiones muy grandes ya que éstas son fijas. A este desperdicio se le llama fragmentación interna.

Esto se ilustra en la figura.


Como puede observarse, el primer proceso puede ser cargado en la región de 30K con una fragmentación de 5K, el de 12K en la de 15K con fragmentación de 3, el de 15K tendrá que esperar a que se desocupe la región de 15K (o decidir cargarla en la de 40K con gran fragmentación), la de 40K puede ser cargada en la de 50K con un desperdicio de 10K, y las de 50K y 7K tendrán que esperar a que alguna región adecuada se desocupe.

También es posible formar varias colas de procesos, una para cada región de memoria (en este caso 3). Esto se ilustra en la siguiente figura.


En este caso los procesos como van llegando son colocados en la cola que mejor se acomoden según sus requerimientos de memoria.

Entonces se tienen 3 asignadores de procesos independientes. Cada uno verifica en la cola de regiones de memoria disponibles sí su hueco está libre, y procede a cargar procesos en caso afirmativo.

El problema principal de este sistema es cómo seleccionar los tamaños de las regiones y cuántas de ellas se tendrán, tal que se tenga la menor fragmentación interna posible.

Por lo tanto, el máximo grado de multiprogramación es limitado por el número de regiones que se escojan.

También si se escogen demasiadas regiones, éstas tenderán que ser pequeñas, por lo que se puede sufrir de un problema peor que es la fragmentación externa. Esta se tiene cuando existen regiones de memoria disponibles pero son muy pequeñas para cargar un proceso, por lo que se tendrá que esperar por otro hueco más grande.

1.5 Multiples particiones contiguas variables

Con un sistema de lote, la organización de la memoria en particiones fijas es simple y efectiva. En tanto puedan guardarse suficientes trabajos en la memoria para mantener ocupada a la CPU todo el tiempo, no hay razón para utilizar nada más complicado. Con el tiempo compartido, la situación es diferente: normalmente hay más usuarios que memoria para contener todos sus procesos, tal que es necesario guardar los procesos extra en un disco. El paso de procesos de la memoria central a un disco y de regreso se llama intercambio.

En un principio, un sistema de intercambio pudiera basarse en particiones fijas, Siempre que un proceso se bloqueará, éste podría pasarse al disco y colocarse otro proceso en su partición del disco. En la práctica, las particiones fijas no son atractivas cuando la memoria es escasa porque una parte muy grande de ella es desperdiciada por programas que son menores que sus particiones.

El problema con particiones fijas es determinar los mejores tamaños de regiones para minimizar la fragmentación interna y externa.

Sin embargo, con un conjunto de procesos dinámicos, es poco probable llegar a una condición óptima. La solución a este problema es permitir que las regiones varíen de tamaño dinámicamente. Esta solución es llamada múltiples particiones contiguas variables.

Esta forma de manejo de memoria consiste en tener una cola de regiones de memoria que están disponibles.


La diferencia principal entre las particiones fijas y las particiones variables, es que el número, localidad y amaño de las particiones varían en forma dinámica en el segundo a medida que los procesos vienen y se van, mientras que son fijos en el primero. La flexibilidad de no atarse a un número fijo de particiones que puede ser demasiado grande o demasiado pequeño mejora la utilización de la memoria, más también complica la asignación y desasignación de la memoria, así como su control.

Al inicio se tiene un solo bloque de memoria para programas del usuario que resulta de cargar el Sistema Operativo en la memoria disponible. Esto se ilustra en la figura con una memoria de 256K.

Cuando los procesos llegan, se checa en la cola de regiones de memoria disponibles si se puede cargar el proceso. Si la región es muy grande, solo se asigna la necesaria y el resto es puesto en la cola de regiones de memoria disponibles.


Por ejemplo asuma que los siguientes procesos requieren servicio:

Cola de Procesos

No. de Proceso Memoria requerida

Tiempo ráfaga

1 60 K 10 2 100 K 5 3 30 K 20 4 70 K 8 5 50 K 15

Si el algoritmo usado es del tipo primero en llegar primero en salir, podemos cargar a memoria los 3 primeros procesos:

La cola de regiones de memoria disponible queda con un hueco de 26K; sin embargo, en ese hueco no es posible cargar ya ninguno de los procesos pendientes, por lo que se dice que tenemos una fragmentación externa de 26 K. Al terminar el proceso 2, regresa a la cola de regiones de memoria disponibles un área de 100K en la cual podemos cargar el proceso 4 de 70K, regresando a la cola el área restante de 30K.


La cola de regiones de memoria disponibles queda: 26, 30 con sus respectivas direcciones de inicio. Como el proceso 5 no se puede cargar, nos deja una fragmentación externa de 56K. El siguiente en terminar es el proceso 1, permitiéndonos cargar el proceso 5 en el área de 60K dejado por el proceso 1, y poniendo en la cola de regiones de memoria disponibles el área no usada (10K).

La cola de regiones de memoria nos queda: 26, 30, 10 con sus respectivas direcciones.

Como ya no hay procesos que cargar, no podemos afirmar que se tenga una fragmentación externa de 66K. Esto dependerá de que se pueda cargar o no el siguiente proceso que llegue. En caso negativo, entonces se tiene efectivamente una fragmentación externa de 66K.

El esquema anterior, requiere de una estrategia para asignar los huecos de memoria disponibles. En general se tienen 3 algoritmos: "primero en ajustar" (first-fit), el "mejor en ajustar" (best-fit), y el "peor en ajustar" (worst-fit).


"PRIMERO EN AJUSTAR" (First Fit). Carga el programa en el primer hueco suficientemente grande que encuentra en la lista de regiones de memoria disponibles. Es el algoritmo más rápido.

"MEJOR EN AJUSTAR" (Best Fit). Busca por el hueco de memoria que menos fragmentación produzca. Si la lista de regiones de memoria disponibles es mantenida en orden ascendente, es fácil y rápido encontrar la más adecuada. De otra manera debemos buscar toda la lista.

"PEOR EN AJUSTAR" (Worst Fit). Carga el programa en el hueco más grande que encuentra y deja en la lista de regiones disponibles el tamaño del resto de la memoria no usada. Esta estrategia a veces rinde mejores resultados que la de mejor en caber, ya que produce huecos grandes de fragmentación que pueden ser mejor utilizados que fragmentaciones muy pequeñas.

Es adecuado mantener la lista ordenada de mayor a menor para reducir el tiempo de búsqueda.

El hardware usado para este sistema es exactamente el mismo; es decir, dos registros que delimitan perfectamente el área del programa a ejecutar.

Por ejemplo:

Utilizando una cola circular, los algoritmos de Round Robin y El primero en caber, resolver el siguiente problema de múltiples particiones contiguas variables si se tiene una memoria total de 256 K. El sistema operativo usa 40 K en memoria. Y un cuantum de 2 unidades de tiempo. La siguiente tabla muestra los procesos, su tiempo de llegada, la memoria que requieren, y el tiempo que necesitan para ejecutarse.

Tiempo de Llegada Número de Proceso

Número de Memoria Requerida

Tiempo Ráfaga

0 1 60 K 10 1 2 100 K 5 4 3 30 K 15 5 4 70 K 8 6 5 50 K 15

Por ejemplo:

Utilizando una cola circular, los algoritmos de Round Robin y El primero en caber, resolver el siguiente problema de múltiples particiones contiguas variables si se tiene una memoria total de 6 MB. El sistema operativo usa 500 K en memoria. Y un cuantum de 2 unidades de tiempo. La siguiente tabla muestra los procesos, su tiempo de llegada, la memoria que requieren, y el tiempo que necesitan para ejecutarse.


Tiempo de Llegada

Número de Proceso

Número de Memoria

Requerida

Tiempo Ráfaga

0 1 1500 K 8 1 2 2500 K 6 3 3 2000 K 5 5 4 1200 K 4 6 5 800 K 3

1.5.1 Compactacion

En el ejemplo anterior, se puede apreciar que existe una fragmentación de 66K compuesta por 3 huecos de 10, 30 y 26K, los cuales son más difíciles de usar que si fueran un solo bloque de 66K. Sin embargo, es posible compactar la memoria haciendo que todos los huecos disponibles se junten ya sea en la parte de abajo o del medio de la memoria.

Esto se ilustra en la siguiente figura:

Para efectuar la compactación, es necesario cambiar de localidad los procesos, por lo que este sistema solo es posible si el hardware cuenta con relocalización dinámica; ya que de otra forma, los procesos no podrían trabajar en sus nuevas direcciones.

Como ya se menciono, es posible combinar todas las cavidades (espacios disponibles) en una grande pasando todos los procesos lo más abajo que sea posible. Esta técnica se conoce como comprensión de la memoria. Esto no suele efectuarse porque requiere mucho tiempo de la CPU.


UNIDAD 2

ALMACENAMIENTO VIRTUAL Objetivo El alumno conocerá los antecedentes de la técnica de Memoria virtual y comprenderá su importancia en los Sistemas Computacionales actuales. Temario 2.1 Nacimiento del concepto de almacenamiento virtual 2.2 Concepto de memoria virtual 2.3 Overlay 2.4 Paginación

2.4.1 Hardware de paginación 2.4.2 Tabla de páginas 2.4.3 Demandador de páginas 2.4.4 Algoritmos de reemplazo

2.5 Segmentación 2.5.1 Hardware de segmentación 2.5.2 Tabla de segmentos 2.5.3 Compartimiento de código

2.5.3.1 Código reentrante 2.5.3.2 Compartimiento en página 2.5.3.3 Compartimiento en segmentos

Bibliografía:

Sistemas Operativos Modernos Autor: Andrew Tanenbaum Editorial: Prentice Hall Sistemas Operativos Autor: William Stallings Editorial: Prentice Hall

Almacenamiento virtual


Introducción

En el siguiente capítulo se analizará que la administración de memoria establece una interrelación estrecha y compleja con el hardware del procesador y el software del sistema operativo. Por consiguiente, se verán aspectos de hardware de la memoria virtual, considerando paginación, segmentación y la combinación de ambas. Con esto se consigue abarcar temas del diseño de un servicio de memoria virtual para el sistema operativo.

2.1 Nacimiento del concepto de almacenamiento virtual

En el capítulo de manejo de memoria, se consideró que para que un proceso pueda ser ejecutado, éste debe estar cargado completamente en la memoria principal de la máquina. Esta restricción, parece necesaria y razonable, pero limita el tamaño de los programas a ejecutar al tamaño de la memoria física.

En realidad, examinando programas típicos reales, se llega a la conclusión de que en muchos casos no es necesario cargar el programa completo en memoria. Por ejemplo.

• Algunos programas tienen rutinas para manejar condiciones de error. Dado que estos problemas casi nunca ocurren, el código de esta rutina es rara vez ejecutado.

• Los arreglos, listas y tablas, son generalmente declarados con tamaños mucho mayores al que llegan a necesitar, por lo que se desperdicia memoria.

• Ciertas opciones de algunos programas rara vez son ejecutados.

Aún en el caso en el que el programa entero sea ejecutado, es posible que no sea necesario cargarlo completo a un mismo tiempo. La habilidad de ejecutar un programa que está parcialmente en memoria puede traer muchos beneficios. Por ejemplo.

• Un programa no estaría limitado por la cantidad de memoria RAM disponible. Los usuarios podrían escribir programas con un número de instrucciones muy grande.

• Dado que cada usuario podría tomar menos memoria RAM, más usuarios podrían correr al mismo tiempo, elevando el grado de multiprogramación y por lo tanto mejorando la utilización del CPU.

• Se requerirían menos operaciones de E/S para cargar cada usuario en memoria puesto que los programas serían más cortos.

En general, correr un programa que no está enteramente en memoria, beneficiaría tanto al sistema como al usuario. Existen dos técnicas que permiten realizar esto: Overlays y Memoria Virtual.

2.2 Concepto de memoria virtual

Es la separación de la memoria lógica del usuario de la memoria física. MV es una técnica que permite la ejecución de programas que no pueden estar completamente en memoria.

VENTAJAS

• Los programas pueden ser mayores que la memoria física.


• Abstracción de Memoria Principal es un arreglo de almacenamiento uniforme y extremadamente grande, que separa la memoria lógica, según ve el usuario de la memoria física.

• Libera a los programadores de la preocupación acerca de las limitaciones de almacenamiento de memoria.

DESVENTAJAS

• No es fácil de implementar. • Puede reducir considerablemente el rendimiento.

2.3 Sobreposicion. (overlay)

Es una técnica que permite a un programa ser más grande que la cantidad de memoria otorgada a él, sobreponiendo en una misma área de memoria dos o más subprogramas que no se usan al mismo tiempo, ni se llaman entre sí. Cuando se escribe un programa con overlays, el lenguaje que se use debe tener esa capacidad, tal es el caso de algunos pascales como el turbo pascal 3.0. Ejemplo:

Considere dos subprogramas escritos en pascal: Procedure uno y procedure dos, los cuales son llamados por un programa principal cuyo nombre es prueba. El programa completo nos queda:

PROGRAM PRUEBA;

VAR (*Variables del programa prueba*)

-

-

PROCEDURE UNO;

BEGIN

-

-

END;

PROCEDURE DOS;


BEGIN

-

-

END;

BEGIN (*Programa prueba*)

-

-

-

END. (*Programa prueba*)

El archivo compilado queda formado como se ilustra en la siguiente figura.

ARCHIVO prueba.com

Si por ejemplo, el código del programa principal (prueba) ocupa 100 K y los procedimientos uno y dos ocupan 30 y 50 K respectivamente, y la memoria asignada al usuario es de solo 150 K, es obvio que el programa no podrá ser corrido.

Sin embargo, si los procedimientos uno y dos no se llaman entre ellos, se puede cargar solo uno de ellos a la vez junto con el programa principal. Esto se haría de la siguiente manera:


PROGRAM PRUEBA;

VAR

(*Variables del programa prueba*)

-

-

-

OVERLAY PROCEDURE UNO;

BEGIN

-

-

-

END;

OVERLAY PROCEDURE DOS;

BEGIN

-

-

-

END;

BEGIN (*Programa prueba*)

-

-

END. (*Programa prueba*)

Lo anterior crea el mismo archivo prueba pero sin el código de los dos subprogramas y un archivo más llamado prueba.000 (archivo de overlay) con el contenido de ambos subprogramas.


El programa es cargado a memoria colocando el código del archivo prueba, y dejando un hueco reservado para cargar el código de un subprograma u otro contenido en el archivo de overlay. Esto se ilustra en la siguiente figura.

El área de overlay es del tamaño del más grande de los overlays. Por lo tanto, al correr el programa, sólo el código de uno de los subprogramas es cargado a la vez en la misma área de memoria, permitiendo correr el programa como si estuviera cargado en memoria totalmente. Tiene la desventaja que el programa corre un poco más lento por tener que ir a disco (principalmente si es disquete).

A continuación se presenta un programa ejemplo de overlay.

PROGRAM MEMOVIRT; OVERLAY procedure UNO; begin GotoXY(8, 2); write('CORRIENDO PROCEDIMIENTO UNO'); readln; end; OVERLAY procedure DOS; begin GotoXY(8, 6); write('CORRIENDO PROCEDIMIENTO DOS'); readln; end; BEGIN ClrScr; GotoXY(1, 0); write('CORRIENDO PROGRAMA PRINCIPAL'); readln; UNO; GotoXY(1, 4); write('CORRIENDO PROGRAMA PRINCIPAL'); readln; DOS; write('FIN DEL PROGRAMA PRINCIPAL'); readln; END.


2.4 Paginación

El sistema de particiones variables sufre del problema de fragmentación externa ya que un proceso debe ser cargado en memoria contigua. Este problema puede ser resuelto por compactación o por paginación.

La Paginación permite que un programa sea cargado en memoria no contigua; es decir, en varios fragmentos fijos no contiguos.

2.4.1 Hardware de paginación

El hardware utilizado en paginación se ilustra en la siguiente figura.


La memoria física es dividida en bloques de tamaño físico llamados "frames" o cuadros. La memoria lógica (direcciones generadas por el compilador), es también dividida en bloques del mismo tamaño llamados páginas. Cuando un programa va a ser ejecutado, sus páginas son cargadas en los cuadros disponibles, y la tabla de páginas es definida para traducir de páginas del usuario a cuadros de memoria. Cada dirección lógica generada por un programa en el CPU, es dividida en dos partes: un número de página (p) y un desplazamiento de página (d).

El número de página es usado como índice de la tabla de páginas donde se encuentra la dirección del cuadro que le corresponde en la memoria física.

Esa dirección es combinada con el desplazamiento de página para definir la dirección exacta que se anda buscando. La combinación es como sigue:

Dirección física = (no. de cuadro x no. de palabras por página + desplazamiento de página)

Por ejemplo, considere una memoria usando un tamaño de página de 4 palabras y una memoria física de 28 palabras (7 cuadros). En la siguiente figura se muestra cómo la memoria desde el punto de vista del usuario es mapeada en memoria física.


Por ejemplo, la dirección lógica 4 está en página 1 y un desplazamiento de 0. De acuerdo a la tabla de páginas ésta es mapeada en el cuadro 2, y la dirección exacta de la dirección lógica 4 es: (2 * 4 + 0)= 8.

La dirección lógica 13 corresponde a (1 * 4 + 1)= 5

La dirección lógica 3 corresponde a (6 * 4 + 3)=27

La dirección lógica 0 corresponde a (6 * 4 + 0)=24

Es importante notar que paginación es por sí misma una forma de relocalización dinámica.

Un aspecto importante de paginación es la clara separación entre la memoria desde el punto de vista del usuario y la memoria física actual. El usuario ve la memoria como un espacio contiguo, conteniendo solo su programa. En realidad, el programa del usuario esta disperso a través de toda la memoria física, la cual también contiene otros programas. La traducción entre ambas memorias es realizada por la tabla de páginas que es manejada por el sistema operativo.

La Paginación viene a ser un esquema de múltiples particiones fijas no contiguas.

2.4.2 Tabla de páginas

El mecanismo básico de lectura de una palabra de memoria supone la traducción por medio de la tabla de páginas de una dirección virtual o lógica, formada por un número de página y un desplazamiento, a una dirección física que está formada por un número de marco y un desplazamiento. Puesto que la tabla de páginas es de longitud variable, en función del tamaño del proceso, no es posible suponer que quepa en los registros. En su lugar, debe estar en memoria principal para ser accesible. La siguiente figura, sugiere una implementación en hardware de este esquema. Cuando se está ejecutando un proceso en particular, la dirección de comienzo de la tabla de páginas para este proceso se mantiene en un registro. El número de página de la dirección virtual se emplea como índice en esta tabla para buscar el número de marco correspondiente. Este se combina con la parte de desplazamiento de la dirección virtual para generar la dirección real deseada.


Asignación de memoria en paginación.

En el sistema de paginación, cuando un proceso nuevo llega al dispositivo de spool, es seleccionado por el asignador de procesos para ser cargado a memoria. Primero comprueba su requerimiento de memoria en páginas. En seguida busca en la lista de cuadros de memoria disponibles para ver si es posible cargar el proceso. Cada página requiere un cuadro, por lo que si el proceso consta de n páginas, deberá haber n cuadros de la memoria física para pode r cargarlo. Esto se ilustra en la figura anterior.

El sistema de paginación está exento de fragmentación externa, ya que todos los cuadros pueden ser otorgados a cualquier proceso que lo necesite. Sin embargo, es posible tener fragmentación interna ya que los cuadros son de tamaño fijo y sí un programa no logra llenar la página completa, se tendrá un desperdicio. El peor caso es cuando un programa requiere de n páginas más una palabra, ya que casi toda la página quedará vacía.

Paginas compartidas.


Una de las ventajas de paginación, es poder compartir código común. Esta característica es particularmente importante en sistemas operativos del tiempo compartido.

Considere un sistema el cual soporta 40 usuarios, cada uno de los cuales ejecuta un intérprete BASIC. Si el intérprete consiste de 60K de código y 40K de espacio para el programa y datos del usuario, se requerirían 40 x 100= 4000 K para soportar a los 40 usuarios.

Si el código es reentrante (no modificable a sí mismo), éste puede ser compartido por todos los usuarios, por lo que sólo se requeriría una copia del intérprete (60K) para todos, más 40K de código de datos para cada uno de los procesos. Esto nos da un requerimiento de 60K + 40(40 k) = 1660 K, un ahorro considerable frente a los 4000 K. En la siguiente figura se ilustra un ejemplo similar con un intérprete BASIC de 3 páginas compartido por 3 procesos.

COMPARTIMIENTO DE CÓDIGO EN AMBIENTE DE PAGINACIÓN

2.4.3 Demandador de páginas

Memoria virtual en paginación

Es una técnica que permite ejecutar programas que no están enteramente cargados en memoria, dando al usuario la impresión de que tiene una memoria mucho mayor a la memoria física de la máquina, por lo que puede escribir programas muy extensos. La memoria virtual en paginación está constituida por dos subsistemas: El demandador de páginas y el algoritmo de reemplazo de página.

En el demandador de páginas, en lugar de cargar en memoria todas las páginas que componen el programa, como se hacía en el esquema de paginación visto anteriormente,


las páginas se van cargando según lo vaya requiriendo la ejecución de éste; es decir, que una página nunca será cargada a memoria a menos que sea necesaria.

Sin embargo, cuando el CPU trata de usar una página que no ha sido traída a memoria, traduce una dirección de usuario en una dirección física utilizando la tabla de páginas, pero como esta dirección no tiene un cuadro asociado, entonces la dirección es inválida y se genera un error abortando el programa.

Para evitar este problema, el hardware de paginación es modificado agregando un bit de validación. De esta manera, si una página no ha sido traída a memoria, el bit es puesto a 1 ó inválido. Esto se ilustra en la figura.


De esta manera, cuando se accesa la tabla de páginas, es posible saber si la página está en memoria ó no. Si la página no está cargada en memoria, en lugar de producir una interrupción al sistema operativo del tipo de dirección de memoria ilegal, la cual abortaría el programa, ahora se genera una interrupción de otro tipo indicando que la página no está en memoria. El manejador de esta interrupción procederá a cargar la página faltante y proseguirá la ejecución del programa. Esto se ilustra en la siguiente figura.


El procedimiento se resume en los siguientes puntos.

1.- Primero checamos la tabla interna mantenida en el bloque de control de proceso, para determinar si la referencia es un acceso a memoria válido o inválido. Si fue inválido, abortar el programa.

2.- Si fue una referencia válida pero aún no hemos traído la página, debemos traerla ahora.

3.- Encontrar un cuadro libre (buscando en la lista de cuadros disponibles), y determinar en qué lugar en disco se encuentra la página faltante.

4.- Hacer una operación de lectura para traer la página deseada al cuadro nuevo asignado.

5.- Cuando la lectura se haya completado, modificar la tabla interna y la tabla de páginas para reflejar que la página está ahora en memoria.

6.- Restablecer la instrucción que fue interrumpida por la página faltante. El proceso puede ahora accesar a la página como si siempre hubiera estado en memoria.


Hay que hacer notar que al generarse la interrupción, es necesario guardar el estado del proceso interrumpido (registros, código de condiciones, contador del programa) en su PCB correspondiente, de tal manera que el proceso pueda ser restablecido después de haber traído la página faltante.

En el caso extremo, nosotros podemos empezar la ejecución de un programa con cero páginas en memoria. El proceso inmediatamente generará una petición de página con la primera instrucción. Después de que esta página sea traída, el programa continuará ejecutándose y generando peticiones de páginas (como sea necesario) hasta que cada página que sea necesaria esté en memoria. En este punto, el programa puede ejecutarse sin interrupciones de falta de páginas, o bien la frecuencia de falta de páginas puede mantenerse en un nivel razonablemente bajo. Se estima que este nivel debe ser del orden de un acceso de memoria en 100000. De no ser así, la ejecución de los programas se alenta dramáticamente debido al tiempo total transcurrido desde que se genera la interrupción, se checa si es una página faltante, determina la posición de la página en disco, se lee y escribe en un cuadro libre, actualiza la tabla y se restablece la instrucción interrumpida. Este tiempo en promedio es del orden de 10 milisegundos.

Se ha dicho que uno de los principales beneficios de no cargar completamente los programas, es que nos queda más memoria disponible y por lo tanto más usuarios pueden ser cargados al mismo tiempo, aumentando el grado de multiprogramación. Por ejemplo si tenemos 40 cuadros de memoria física y un programa que tiene 10 páginas pero solo usa realmente 5, podríamos cargar hasta 8 programas similares en lugar de 4 si no tuviéramos memoria virtual. Sin embargo, sí repentinamente los ocho programas requirieran usar las 10 páginas completas se tendría una demanda de 80 cuadros cuando solamente se tienen 40. Aunque esta situación es poco probable, ésta llega a ser muy factible cuando aumentamos el grado de multiprogramación, al punto en que la memoria promedio de uso, se aproxima a la memoria física disponible.

Cuando esta situación se presenta, el sistema operativo tiene varias opciones:

1.- Abortar el programa en cuestión. Sin embargo dado que la idea de usar memoria virtual es beneficiar tanto al usuario como al sistema, es obvio que ésta no es la mejor opción.

2.- Reducir el grado de multiprogramación, pasando a disco a uno de los usuarios (swapping) y liberando así todos sus cuadros de memoria que ocupaba. Esta es una buena solución más no la mejor.

3.- La mejor opción, es utilizar un algoritmo llamado reemplazo de página (page replacement).


2.4.4 Algoritmos de reemplazo de página

La política de reemplazo de página trata de seleccionar una página a reemplazar en memoria principal cuando se debe de cargar una nueva página. Esto resulta dificil de explicar ya que se involucran varios conceptos interrelacionados, tales como:

• El número de marcos de página a asignar a cada proceso activo • Si el conjunto de páginas candidatas para el reeemplazo debe limitarse a las del

proceso que provocó el fallo de página o abarcará a todos los marcos de página situados en memoria principal.

• De entre el conjunto de páginas candidatas, la página que debe elegirse en particular para el reemplazo.

Existe una regla que debe tenerse en cuenta es que cuanto más elaborada y sofisticada es la política de reemplazo, mayor es la sobrecarga de hardware y software necesaria para implementarla.

Cabe mencionar que existe una restricción en la política de reemplazo:

Algunos marcos de memoria principal pueden estar bloqueados. Cuando un marco está bloqueado, la página cargada actualmente en este marco no puede ser reemplazada. La mayoría del núcleo del sistema operativo, así como las estructuras clave de control, se albergan en marcos bloqueados. Además, los buffers de E/S y otras áreas críticas en tiempo pueden bloquearse en marcos de memoria. El bloqueo se onsigue asociando un bit de bloqueo a cada marco. Este bit puede guardarse en una tabla de marcos o estar incluído en la tabla de páginas actual.

El funcionamiento en forma muy básica de un algoritmo de reemplazo de página es el siguiente:

Si no hay un cuadro libre, encontrar uno que no se esté usando y desocuparlo escribiendo su contenido a disco, y reflejando el cambio en la tabla de páginas para indicar que esa página no está más en memoria.

El cuadro libre puede ahora ser utilizado para cargar la página faltante. Esto se ilustra en la siguiente figura.


Al introducir el algoritmo de reemplazo de página, la rutina del sistema operativo que sirve la interrupción de una página faltante queda como sigue:

1.- Encontrar la localización en disco de la página deseada.

2.- Encontrar un cuadro libre

Si hay un cuadro, entonces: usarlo

Sino: Usar un algoritmo de reemplazo de página para encontrar un cuadro

Víctima.

Escribir la página víctima al disco.

Actualizar la tabla de páginas para reflejar el cambio.

[Fin del condicional]

3.- Leer la página faltante y escribirla en el cuadro libre.

Cambiar la tabla de páginas.

4.- Restablecer la ejecución del programa.

Note que dos intercambios (swappings) son requeridos si no hay cuadros libres. Esta situación dobla el tiempo de servicio de una página faltante. Si esto es muy frecuente, el funcionamiento del sistema puede no ser muy eficiente, por tanto el grado de multiprogramación debe ser escogido adecuadamente.


La combinación del demandador de páginas con el reemplazador de páginas, es la manera en que comúnmente se implementa la memoria virtual, la cual constituye una separación de la memoria lógica de la memoria física. La memoria virtual puede ser mucho más grande que la memoria física.

Existen varios algoritmos básicos que se emplean para la selección de una página a reemplazar, entre lo que se encuentran:

• Óptima • Usada hace más tiempo (LRU, Least Recently Used) • Primera en entrar, primera en salir (FIFO, First-In First-Out) • De reloj

2.5 Segmentación

Segmentación es otro método de administración de memoria, el cual permite cargar un programa en memoria no contigua.

Este método es más natural ya que generalmente un programa está constituido por un programa principal y varios subprogramas separados, por lo que cada una de estas entidades puede ser guardada en un segmento de memoria individual de tamaño exacto según lo requiera cada uno.

Lo anterior indica que los segmentos deben de ser de longitud variable, en contraste con paginación en donde las páginas son de longitud fija.

2.5.1 Hardware de segmentación

El uso de la tabla de segmentos es ilustrado en la siguiente figurar.

Cada segmento tiene un nombre o número y una longitud. El usuario por esto especifica cada dirección por dos cantidades: un nombre de segmento y un desplazamiento.

Dado que ahora una dirección dentro de un programa del usuario (dirección lógica), debe especificarse como una dirección de 2 dimensiones, y dado que la memoria física es aún un arreglo de una sola dimensión, es necesario implementar un dispositivo que mapee o convierta una dirección de dos dimensiones en otra de una sola dimensión. Esto se hace por medio de la tabla de segmentos.


Memoria virtual en segmentación:

La memoria virtual también puede ser implementada en sistemas de segmentación; sin embargo requiere de algoritmos de reemplazo más complejos.

Resulta más fácil implementar memoria virtual segmentada a través de sistemas de segmentación paginada; es decir, los segmentos divididos en páginas. De esta forma, el usuario ve un sistema segmentado, pero el sistema operativo ve un sistema paginado, por lo que puede utilizar el algoritmo de reemplazo de página.

2.5.2 Tabla de segmentos

Una dirección lógica consiste de dos partes: un número de segmento "s" y un desplazamiento "d" dentro del segmento. El número de segmento es usado como índice en la tabla de segmentos.

El renglón apuntado por ese índice, tiene la dirección donde empieza el segmento (llamada base del segmento), y un límite que indica el número de palabras de que consta ese segmento. El desplazamiento "d" de la dirección lógica, debe estar entre 0 y el límite del segmento: sí no, entonces se tiene un error de dirección, por lo que se manda una interrupción al sistema operativo.

Si el desplazamiento es legal, entonces es sumado a la base del segmento, para producir la dirección de la palabra deseada en la memoria física. Considere el ejemplo mostrado en la siguiente figura:


Tenemos cinco segmentos numerados del 0 al 4. Los segmentos son almacenados en la memoria física tal como se muestra en la figura. La tabla de segmentos tiene un renglón separado para cada segmento que nos da la dirección de inicio de cada segmento (base), y la longitud de ese segmento (límite). Por ejemplo, el segmento 2 comienza en la dirección 4300 y tiene 400 palabras de longitud.

Por lo tanto, una referencia a la palabra 53 del segmento 2 es mapeada en la localidad 4300 + 53 = 4353.

Una referencia a la palabra 1222 del segmento cero resultaría en un error y por lo tanto interrupción al sistema operativo, ya que el desplazamiento 1222 excede el límite del segmento cero que es de 1000.

2.5.3 Compartimiento de código 2.5.3.1 Código reentrante Un código reentrante es aquel que no se modifica a sí mismo. 2.5.3.2 Compartimiento en página Fragmentación en paginación.

El asignador de procesos debe encontrar y cargar en memoria todos los segmentos de un programa del usuario. Esta situación es similar a paginación excepto que los segmentos son de longitud variable, (las páginas son todas del mismo tamaño), por lo que la


fragmentación interna puede ser despreciable. Sin embargo, se puede tener fragmentación externa cuando todos los segmentos disponibles son demasiado pequeños para cargar cierto programa.

Segmentación viene a ser un esquema de múltiples particiones no contiguas variables.

2.5.3.3 Compartimiento en segmentos

Segmentos compartidos

Una ventaja de segmentación es que pueden compartirse segmentos de código común a varios procesos: por ejemplo compartir entre dos usuarios una subrutina escrita en FORTRAN, o un editor de textos. Esto se ilustra en la siguiente figura:


UNIDAD 3. SISTEMA DE ARCHIVOS

Objetivo : Conocer los elementos básicos de la Administración de Archivos como parte

del Sistema Operativo.

TEMARIO 3.1 ORGANIZACIÓN LÓGICA Y FÍSICA 3.2 MECANISMOS DE ACCESO 3.3 OPERACIONES DE ARCHIVO 3.4 DIRECTORIOS 3.5 SEGURIDAD

3.5.1 PRINCIPIOS DE DISEÑO PARA LA SEGURIDAD 3.5.2 AUTENTIFICACIÓN DE USUARIOS

3.6 MECANISMOS DE PROTECCIÓN 3.6.1 DOMINIOS DE PROTECCIÓN 3.6.2 LISTAS DE CONTROL DE ACCESO 3.6.3 MODELOS DE PROTECIÓN

BIBLIOGRAFÍA:

1. Apuntes de Sistemas Operativos II

Sistemas de Archivos

Administración de archivos En la mayoría de las aplicaciones, el archivo es el elemento central. Los archivos tienen una vida fuera de cualquier aplicación individual que los utilice para Entrada y Salida. Los usuarios desean:

• Acceder a los archivos • Guardar y mantener la integridad de su contenido.

Sistemas de administración de archivos (S. A. A) Proporciona a los usuarios y aplicaciones servicios relativos al empleo de los archivos. Normalmente la única forma en que un usuario o aplicación puede acceder a los archivos es mediante S. A. A. Objetivos de la administración de archivos

1. Cumplir con los necesidades de archivos de datos y requisitos del usuario. 2. Garantizar a medida de lo posible, que los datos de los archivos sean válidos. 3. Optimizar el rendimiento. 4. Ofrecer soporte de Entrada – Salida para la variedad de tipos de dispositivo de

almacenamiento.


5. Minimizar o eliminar la posibilidad de pérdida o destrucción de datos. 6. Ofrecer un conjunto estándar de rutina de interfaz de Entrada – Salida. 7. Proporcionar soporte de Entrada – Salida para múltiples usuarios.

El S. A consta de 2 partes distintas:

1. Colección de Archivos, cada uno para el almacenamiento de Datos. 2. Estructura de Directorios, organiza y proporciona información acerca de los

archivos en el sistema.


3.1 Organización lógica y física

Para facilidad de uso de un sistema de cómputo, los sistemas operativos proporcionan un medio abstracto que permite manejar los dispositivos de almacenamiento del sistema, sin necesidad de conocer las propiedades físicas de éstos. Esto se hace mediante la definición de una unidad de almacenamiento lógico en lugar de una unidad de almacenamiento físico.

Esta unidad de almacenamiento lógico es el archivo.

Un archivo es una colección de información relacionada definida por su creador. Regularmente los archivos representan programas y/o datos.

En general un archivo es una secuencia de registros lógicos.

Los registros lógicos están constituidos por bytes o grupos de bytes que pueden significar para el usuario diferentes tipos de datos (por ejemplo valores numéricos o cadenas de caracteres).

Los registros lógicos pueden ser definidos de varios tamaños de anchura: sin embargo, si ésta no es la misma que la del registro físico (disco), crea el problema de desperdicio de espacio si es menor, o de no poder escribirlo si es mayor.

Este problema es solucionado en el S.O. mediante el uso del factor de bloqueo.

En este método, los registros lógicos son agrupados o empacados según su tamaño para luego ser almacenados en el registro físico.

Por ejemplo: Si la anchura del registro físico es de 256 bytes, y el registro lógico fue definido de 128 bytes, entonces tendremos un agrupamiento de dos registros lógicos por cada registro físico.

Se dice que se tiene un factor de bloqueo de dos.

Si el registro lógico se define de 80 bytes y el registro físico es de 256 bytes, el S.O. adopta un factor de bloqueo de 3.


Sin embargo en este tamaño de registro lógico se desperdicia algo de espacio.

También se puede dar el caso de que el registro lógico exceda en tamaño al registro físico. En este caso, un registro lógico es colocado en más de un registro físico. Por ejemplo si un registro lógico es de 500 bytes y el físico de 256, nos queda:

En la mayoría de los S.O., el usuario puede escoger el factor de bloqueo que considere más adecuado. El registro físico no puede ser modificado dado que es una característica física de la unidad de disco.

El S.O. también provee la facilidad de tener registros de longitud variable, aunque esto es más común en cintas que en discos. Las cintas, dadas sus características físicas que solo permiten acceso secuencial, son utilizadas solo para respaldos de información.

3.2 Mecanismos de acceso

Secuencial

Los registros lógicos se escriben uno detrás de otro por medio de un apuntador que se mueve automáticamente. El usuario no tiene control sobre el apuntador. Es difícil insertar una componente en medio de otras; así como eliminar una componente dada. Su uso de espacio es eficiente.


Directo

Se puede especificar en qué registro posicionar el apuntador y escribir o leer en él. Si no se tiene cuidado se puede desperdiciar mucho espacio.

Archivos con llaves de busqueda

Aunque el acceso directo es el más rápido, si no se sabe en que registro está la información que buscamos no es posible llegar a ella. Para poder hacer una buena organización y acceso rápido a la información se utilizan los archivos con llaves de búsqueda. A continuación se revisan varias técnicas.

Archivos con índices. Constan de un archivo de datos y uno o más archivos de índices.

Indexado puro (no secuencial). Desarrollado con índices densos (un apuntador por cada registro del archivo de datos). El archivo de datos se mantiene en orden cronológico (como se dio de alta), mientras que el de índices se mantiene ordenado por la llave de búsqueda. Se pueden tener varias llaves de búsqueda alternas. Ocupa más espacio y es más lento que el indexado secuencial. Es fácil agregar nuevos registros, pero se requiere reordenar el archivo de índices cada vez que se haga ésto.

Indexado secuencial. Desarrollado generalmente con índices escasos (aunque también pueden desarrollarse con índices densos). El archivo de datos se ordena físicamente de acuerdo a la llave de búsqueda y después se generan los archivos de índices. En el nivel de índices más alto se hace una búsqueda binaria que nos posiciona en otro nivel, y así sucesivamente hasta llevarnos al archivo de datos; una vez ahí, se busca secuencialmente ya que el archivo está ordenado físicamente. No se pueden tener llaves de búsqueda alternas. Si se necesita insertar nuevos registros se generan áreas de desborde (listas encadenadas). Ocupa menor espacio en disco y tiene un tiempo de acceso más rápido que los indexados puros. Se recomienda para mantener grandes volúmenes de información que no cambia con mucha frecuencia y que requiere tiempos de acceso rápidos.

Árboles. Se basan en la versatilidad que proporciona el tener índices que se expanden o encogen dinámicamente. El archivo de datos se mantiene en forma cronológica. Sus algoritmos para buscar, insertar y eliminar registros son más complejos que los de ambos tipos de indexados, pero tienen la ventaja sobre éstos que sus archivos casi no necesitan ser reorganizados. Existen varios tipos de archivos con árboles, como los Search Trees , los Balanceados B y B+, los Binarios Balanceados (AVL), y Binarios No-balanceados. Los más usados son los B y B+.

Árboles B+. Cualquier camino desde la raíz a una hoja tiene la misma longitud. Permiten tener llaves de búsqueda repetidas (por ejemplo, varios nombres homónimos). Impone un gasto extra durante la inserción o eliminación de nodos, además de requerir espacio extra. Su estructura es más sencilla que los B. Usa


varios niveles de índices: los internos y los de hoja. El apuntador al archivo de datos se almacena siempre en los nodos hoja. Árboles B. Similares a los B+ pero elimina el almacenamiento de valores de llave

de búsqueda repetidos, por lo que requiere menos nodos para almacenar los índices. Su estructura es más compleja debido a que sus ramas son más largas y por lo tanto la eliminación de un nodo resulta más complicada que en un B+. Su acceso es ligeramente más rápido que los B+. Usa varios niveles de índices: los internos y los de hoja. El apuntador al archivo de datos se puede almacenar en cualquier nivel. Puede requerir más niveles que los B+.

Hashing. Utiliza funciones que convierten las llaves de búsqueda a números enteros entre 0 y el número máximo de entradas en el archivo de datos. No existen archivos de índices; por esta razón, este método es el más rápido. Sin embargo, tiene el problema de que dos o más llaves pueden generar el mismo número de registro ocasionando colisiones. También tiene el problema de que si el archivo alcanza el número máximo de entradas ya no pueden insertarse nuevos registros. Existen varios métodos para manejar colisiones.

Memoria abierta. Si al tratar de insertar un nuevo registro, su llave genera una colisión, el registro se coloca en la posición más cercana al lugar que le correspondía. Por lo tanto, cuando una llave nos lleva a un registro en el archivo de datos y éste no es el que buscamos, se hace una búsqueda secuencial hasta encontrar el registro deseado.

Encadenamiento de colisiones. Se genera una lista encadenada por cada registro que genera colisiones. Cuando se llega a un registro y éste no es el que buscamos, entonces realizamos una búsqueda secuencial en la lista encadenada hasta encontrar el registro deseado. Doble hashing. Cuando una llave genera una colisión, se pasa por una segunda

función de hashing (diferente a la primera), dando oportunidad de que la posibilidad de generar una colisión disminuya. Si aún así colisiona, se usa cualquiera de los otros dos métodos.

3.3 Operaciones de archivos

Es deseable que un S.O. permita crear archivos, escribir en ellos, leerlos y eliminarlos cuando no se necesiten más. También es deseable poder editar y modificar un archivo, copiarlo a otro dispositivo por ejemplo a la impresora, y renombrarlo.

1. Crear un archivo Se debe encontrar espacio para éste en el S. A Se debe hacer una entrada en el directorio para el nuevo archivo. La entrada en el directorio registra el nombre del archivo y su ubicación en el S. A.

2. Escribir un archivo

Para escribir un archivo, hacemos una llamada al sistema especificando tanto el nombre del archivo como la información que se va escribir en él. Dado el nombre del archivo el sistema busca en el directorio para encontrarle una ubicación. El


sistema debe mantener un apuntador de escritura a la ubicación en el archivo donde va a tener lugar la siguiente escritura. El apuntador de escritura debe actualizarse siempre que ocurra una escritura.

3. Leer un archivo

Para leer un archivo empleamos una llamada al sistema que especifica el nombre del archivo y el lugar (en la memoria) donde deberá colocarse el siguiente bloque del mismo. Nuevamente, se busca en el directorio la entrada asociada, y el sistema mantiene un apuntador de lectura a la ubicación en el archivo en donde va a tener lugar la siguiente lectura. Una vez que se ha realizado la operación el apuntador de lectura se actualiza. Debido a que en general un archivo se está leyendo o escribiendo, la mayoría de los sistemas mantienen sólo un apuntador de la posición actual en el archivo. Tanto en la operación de lectura como la de escritura emplean este mismo apuntador, reduciendo la complejidad del sistema y ahorrando espacio.

4. Reposicionarse dentro de un archivo

Se busca en el directorio la entrada apropiada y se asigna un valor dado a la posición actual del archivo. El reposicionamiento dentro de un archivo no necesita incluir una operación real de entrada – salida. Esta operación sobre el archivo se conoce como Búsqueda en el archivo.

5. Borrar un archivo

Para borrar un archivo buscamos en el directorio el archivo designado. Una vez que se ha encontrado la entrada asociada, liberamos todo el espacio del archivo (para que pueda ser utilizado por otros archivos) y borramos la entrada del directorio.

6. Truncar un archivo

Hay ocasiones en que el usuario desea que los atributos de un archivo permanezcan iguales, pero quiere borrar el contenido del archivo. En lugar de obligar al usuario a borrar el archivo y después volverlo a crear, está función permite que todos los atributos permanezcan sin modificación (excepto la longitud del archivo) pero restableciendo el archivo a una longitud cero.

7. Tipos de Archivo

Un aspecto importante en el diseño de sistemas de archivos (SA) y de todo el sistema operativo es si el sistema operativo deberá reconocer y soportar tipos de archivo. Una técnica común para implementar tipos de archivo consiste en incluir el tipo como parte del nombre del archivo. El nombre se divide en 2 partes: nombre y extensión, separados normalmente por un punto. El sistema utiliza la extensión para indicar el tipo de archivo y el tipo de operaciones que pueden realizarse sobre dicho archivo.

3.4 Directorios


Cada dispositivo de almacenamiento, mantiene una tabla de contenido, en la cual se especifica el nombre, dirección y tamaño de cada uno de los archivos existentes en esa unidad. Esta tabla es conocida como directorio.

La información contenida en un directorio es comúnmente la siguiente:

Nombre de archivo. Tipo de archivo (por ejemplo binario o ASCII). Localización, dispositivo y dirección donde se encuentra el archivo. Tamaño en bytes, palabras o bloques. Máximo tamaño disponible. Protección de acceso para lectura, escritura, ejecución, etc. Fecha de creación o última modificación. Otros.

Estructura de un directorio

Existen muchas formas y métodos de implementar un directorio. Algunas de las más comunes son las siguientes.

Directorio de un nivel

Es el más simple de todos. En este tipo de directorio se agrupan todos los archivos del sistema en una sola lista o tabla, por lo que si se tiene más de un usuario, es necesario que los nombres sean únicos. Es recomendable para sistemas de un solo usuario. Se puede implementar en forma lineal o con "hashing".

CAT BO A PRUEBA DATOS CORREO Directorios

Archivos

Directorio lineal.

Está constituido por una lista lineal encadenada. Es fácil de implementar pero es lenta en acceso ya que para saber si un archivo existe en el directorio hay que hacer una búsqueda secuencial. Sin embargo, si la lista se ordena alfabéticamente, es posible ejecutar búsquedas binarias que reducen notablemente el tiempo de búsqueda. La desventaja es que al dar de alta o de baja nuevos archivos, es necesario reordenar la lista.

Directorio con tabla hash.


Este tipo de algoritmo mejora notablemente el tiempo de búsqueda y tanto las inserciones como las eliminaciones son muy directas.

Este algoritmo convierte los nombres de archivos a números enteros entre cero y el máximo tamaño asignado a la tabla Hash. Por ejemplo una tabla de 256 registros, generará números entre 0 y 255. Obviamente si la tabla se llena, no se podrá agregar otro más ya que habría que modificar el algoritmo. Además un directorio con tabla Hash debe proveer un sistema de manejo de colisiones ya que dos o más archivos con nombres similares pueden producir el mismo número de registro.

Directorio de dos niveles

La principal desventaja de un directorio de un solo nivel, es la confusión de nombres de archivos entre diferentes usuarios. La solución es crear un directorio propio para cada usuario. Esto se hace por medio de un árbol de dos niveles como se ilustra en la siguiente figura.

En este tipo de sistema, cuando un usuario se da de alta, el directorio maestro es buscado hasta encontrar el directorio del usuario correspondiente (generalmente a través de un número de cuenta). Cuando ese usuario lista el directorio, sólo los archivos contenidos en su directorio son mostrados. Esto permite tener nombres repetidos en otros directorios de otros usuarios, sin peligro de borrar o modificar el archivo equivocado, ya que cada usuario solo tiene acceso a los archivos de su propio directorio.

Esto último puede representar un problema cuando dos o más usuarios requieren trabajar en equipo y compartir archivos.


Esto se puede solucionar permitiendo que los usuarios tengan la capacidad de compartir algunos archivos. Por ejemplo, colocar los archivos más comúnmente usados (editores, compiladores, etc.) en un directorio público al cual se puede tener un acceso limitado.

Directorios de multiples niveles. (estructura de árbol)

Cuando un usuario tiene diferentes aplicaciones en un mismo directorio, por ejemplo, programas de COBOL, BASIC y PASCAL, es deseable poder tener cada grupo de programas en directorios separados, pero bajo el control del mismo usuario. Esto se logra por medio de la creación de subdirectorios o directorios de múltiples niveles. Ejemplo:

El S.O. MSDOS, permite al usuario organizar su directorio en forma de árbol, por ejemplo como el del usuario 1 de la figura anterior. El S.O. Unix usa una estructura de árbol. El árbol tiene una raíz. Cada archivo tiene un nombre de trayectoria único. Un nombre de trayectoria, es el camino desde la raíz hasta el archivo pasando a través de los subdirectorios.

Directorio de grafos aciclicos

Son una generalización de los directorios del tipo de árbol. Un directorio de árbol generalmente prohibe el compartir archivos o directorios. Un grafo acíclico sí permite compartir tanto archivos como subdirectorios completos. Esto se ilustra en la siguiente figura.


Note que no se generan ciclos de retorno a través de los mismos archivos y subdirectorios; de ahí su nombre acíclico.

Este tipo de directorios es recomendable en situaciones en que un grupo de usuarios trabajan como equipo. En este caso, todos los archivos a compartir se colocan en un directorio.

Los directorios individuales de cada miembro del equipo, contendrán el directorio de archivos a compartir como un subdirectorio del suyo, por lo que cada uno puede listarlos y utilizarlos.

La búsqueda y eliminación de archivos es complicada debido a que puede existir más de una trayectoria a un mismo archivo, cosa que no sucede en los directorios de árboles (múltiples niveles).

Directorio de grafo general

El directorio de grafo general permite una flexibilidad total para compartir archivos al permitir que haya trayectorias cíclicas a través de todo el directorio. Esto se ilustra en la siguiente figura.


Dado que es permitido tener trayectorias cíclicas, se puede caer en el problema de pasar por la misma trayectoria más de una vez al buscar un archivo, o incluso caer en un lazo infinito. Por lo anterior, se requieren algoritmos muy complicados para mantener este tipo de directorios.

3.5 Seguridad

a. Amenazas a la Seguridad

Para comprender los diversos tipos de amenazas a la seguridad, hace falta primero definir los requisitos de seguridad:

1. Confidenciabilidad 2. Integridad 3. Disponibilidad

b. Tipos de Amenaza

• Interrupción (Amenaza de Disponibilidad) - Destrucción: DD, SA, HW.


• Intercepción (Amenaza a la Confidenciabilidad) - Conexiones Telefónicas - Copia Ilícita

• Modificación (a la Integridad)

- Modificación de Mensajes - Modificación a valores de un archivo

• Invención (a la Integridad)

- Inserción de Mensajes Falsos - Adición de Registros


TTAABBLLAA DDEE AAMMEENNAAZZAASS DDEE SSEEGGUURRIIDDAADD YY EELLEEMMEENNTTOOSS DDEE UUNN SSIISSTTEEMMAA DDEE CCOOMMPPUUTTAADDOORRAASS ELEMENTO DISPONIBILIDAD CONFIDENCIABILIDAD INTEGRIDAD

HW Robo o inutilización de equipo, robando el servicio.

SW Eliminación de programas, denegando el acceso a los usuarios.

Realización de copias no autorizadas del SW

Alteración de un programa en funcionamiento haciendo hallar durante la ejecución o haciendo que realice una tarea no pretendida.

Dato Eliminación de archivos, denegando el acceso a los usuarios.

Lectura de Datos No Autorizados.

Modificación de archivos existentes o invención.

Líneas de comunicación

Destrucción o eliminación de Mensajes, las líneas de comunicación se hacen no accesibles.

Lectura de Mensajes. Observación del tráfico de Mensajes.

Mensajes Modificados retardados, reordenados o duplicados. Invención de Mensajes.

3.5.1 Principios de diseño de medidad de seguridad.

1. Mínimo Privilegio. 2. Ahorro de Mecanismos. 3. Aceptación. 4. Medición Total. 5. Diseño Abierto.

3.6 Proteccion de archivos

La necesidad de proteger los archivos es un resultado directo de la habilidad de compartir archivos. En un sistema que no permite compartir archivos, no es necesario un mecanismo de protección.

Los mecanismos de protección permiten compartir archivos en una forma controlada, limitando el tipo de acceso que se puede tener a un archivo.

Los tipos de acceso son los siguientes:

Lectura de un archivo. Escritura o reescritura de un archivo. Carga en memoria de un archivo y ejecución. Agregar nueva información al final del archivo. Eliminación de un archivo y liberación de su espacio para re usarse.

Otras operaciones que pueden ser controladas son: renombrar, copiar, o editar un archivo, y listar un directorio.


3.6.1 Dominios de protección

Dominio es un conjunto de parejas (objetos, derechos) cada pareja especifica un objeto y un conjunto de operaciones que se pueden efectuar con él.

Derecho significa autorización para ejecutar una de las operaciones.

DOMINIO 1 DOMINIO 2 DOMINIO 3 A1[R] A3[R] A6[RWX]

A2[RW] A4[RWX] PLOTTER2[W] A5[RW] PRINTER1[W]

3.6.2 Listas con control de acceso

Consiste en asociar con cada objeto una lista (ordenada) que contenga todos los dominios que puedan acceder al objeto y que indique como hacerlo.

A0: (JUAN, *, RWX) A1: (JUAN, SSTEMA, RWX) A2: (JUAN, *, RW-) (ELSA, PERSONAL, R- -)(MARTHA, *, R - -) A3: (*, ESTUDIANTE, R - -) A4: (LUIS, *, - - -) (*, ESTUDIANTE, R - -)

3.6.3 Modelos de protección de achivos

Los siguientes son algunos de los esquemas de protección más utilizados por la mayoría de sistemas operativos

1. No permitir listar los archivos de otro usuario. De esta manera, si no se conoce le nombre de un archivo, será muy difícil lograr el acceso ya que se tendría que recurrir a tratar de adivinar el nombre, cosa muy poco probable.

2. Sistema de "passwords" o palabras de pase para cada archivo. Este sistema es eficiente mientras se escojan los passwords al azar y se cambien frecuentemente. La protección se puede redondear utilizando otro password para el acceso del usuario al sistema (número de cuenta).

3. Hacer que el acceso al sistema sea dependiente de la identidad del usuario. Existen varias maneras de implementar esto. Dos de las más comunes son las siguientes:

Asociar una lista de acceso a cada archivo y a cada directorio, en la cual se especifican los nombres de los usuarios y tipo de acceso que tiene cada uno de ellos a ese archivo o directorio. De esta manera, cuando un usuario solicita usar un determinado archivo, el S.O. checa primero la lista de acceso de ese archivo. Si ese usuario esta listado para ese tipo de acceso (por ejemplo escribir), entonces le permite el acceso; si no, un mensaje de error es mostrado al usuario. Una desventaja de este método, es que si la lista de usuarios es grande, es tardado leer toda la lista para determinar si el acceso es válido o no.


Para condensar la lista de acceso, muchos sistemas reconocen tres clasificaciones de usuarios: "creador", "grupo" y "cualquier otro" (ANY). Cada archivo tiene un creador, el usuario que lo generó. Adicionalmente, el creador puede pertenecer a un grupo de usuarios que están compartiendo el archivo y necesitan un acceso similar (por ejemplo los miembros de un equipo de programadores que están desarrollando un sistema, o los miembros de una clase que requieren compartir un graficador). Finalmente todos los demás usuarios que ni crearon el archivo ni pertenecen a ese grupo, forman la clasificación "cualquier otro". Con esta clasificación, combinada con los tipos de acceso se puede generar una plantilla o matriz de protección. Ejemplo:

ARCHIVO: TAREA1 ARCHIVO: GRAF ARCHIVO: FTN

PROTECCION: R W X PROTECCION: R W X PROTECCION: R W X

G G A C C G C C A

El S.O. Unix utiliza el método arriba descrito, usa 3 bits para almacenar los valores C, G, A, y otros 6 bits para almacenar el nombre del creador y usuarios del grupo al que pertenece el archivo. Así, 9 bits son suficientes para proporcionar protección al archivo.

Los sistemas HP-3000 utilizan un esquema similar, sólo que además de los campos R W X, existen otros como A (Append) agregar, y S (Save) guardar.


UNIDAD IV: ADMINISTRADOR DE DISCO

Objetivo: El alumno conocerá las alternativas de asignación de archivos en memoria secundaria y la administración del espacio libre

Temario

4.1. Caracteristicas fisicas de los discos 4.2. Planificacion de disco 4.3. Optimizacion de busqueda. 4.4. Optimizacion rotacional 4.5. Metodos de asignacion de archivos

Bibliografía

7. Sistemas operativos,conceptos fundamentales Silberschatz Editorial : Addison Wesley

INTRODUCCIÓN

Existen dos tareas principales de la Administración de Almacenamiento Secundario:

1.- Debe asignar el espacio de memoria secundaria a los archivos. 2.- Es necesario guardar constancia del espacio disponible para asignar. El almacenamiento de archivos tiene una característica general: Direccionar y Transmitir datos por bloques .La diferencia con la memora principal es que esta Direcciona y transmite Palabras


6.1 CARACTERISTICAS FISICAS DE LOS DISCOS

Cada unidad de disco, puede tener varios platos de aluminio rígido con ambas superficies recubiertas de material magnético (similar al de las cintas).

Los discos son impulsados por un solo motor a una velocidad de alrededor de 3600 RPMS.

Existe una cabeza de lectura/escritura muy cercana a cada superficie de cada plato (del orden de micrones).

Cada disco se divide en pistas concéntricas y éstas a su vez en bloques llamados sectores.

La información es grabada magnéticamente sobre la pista que esté bajo la cabeza de lectura/escritura.

Existen unidades de discos de cabezas fijas y de cabezas móviles.

Una unidad de cabezas fijas, tiene una cabeza por cada pista (de cada lado de cada disco). Esto permite a la computadora cambiar de pista a pista rápidamente; sin embargo, es muy costosa por requerir gran número de cabezas.

Las unidades de cabezas móviles, tienen una sola cabeza por cada superficie de los discos. Se requiere hardware para mover las cabezas pero resulta en una unidad de más bajo costo aunque más lenta que las de cabezas fijas.

Todas las pistas de una unidad que pueden ser accesadas sin mover las cabezas son llamadas cilindros. Básicamente un cilindro está constituido por la misma pista de todas las


superficies de los platos. Por ejemplo, cilindro cero puede ser todas las pistas cero de todas las superficies. (Normalmente, todas las cabezas se mueven al mismo tiempo y a la misma posición).

El tiempo de acceso requerido para dar servicio a una lectura/escritura es la suma de los siguientes tres tiempos:

TIEMPO DE BÚSQUEDA (Seek time). Es el tiempo requerido para que la cabeza se posicione en la pista o cilindro apropiado. En las unidades de cabezas fijas, este tiempo se considera cero. Algunos tiempos de discos típicos para PC’s andan alrededor de 40 a 10 mili segundos.

TIEMPO DE LATENCIA o TARDANZA (Latency time). Una vez posicionada la cabeza en la pista o cilindro correcto, debe esperarse hasta que el bloque deseado rote bajo la cabeza de lectura/escritura. Es del orden de 5 mili segundos.

TIEMPO DE TRANSFERENCIA (Transfer time). Es el tiempo que se requiere para transferir la información entre el disco y la memoria. Es del orden de 1 mili segundos.

Ta=Tbusq+Tlaten+Ttransf

DISKETTES

Los discos floppy o diskettes, son diferentes en construcción respecto a los discos rígidos. En un floppy, la superficie es recubierta con un material magnético duro, tal que la cabeza de lectura/escritura pueda estar siempre haciendo contacto con la superficie sin destruir la información. El diskette es mucho más barato pero después de mucho uso, el recubierto de la superficie y la cabeza se desgastan y deben ser reemplazados. Su tiempo de acceso es mayor que el de los discos rígidos, ya que no pueden rotar a velocidades muy altas por la fricción entre la cabeza y el disco.

Su capacidad de almacenamiento va de 100K a 1.2Mbytes o más.

Mientras que los discos rígidos van de 5 Mbytes a varios Gigabytes. Sus tamaños varían de 8, 5 1/4 y 3 1/2 pulgadas.

Pueden ser de uno o ambos lados, y de simple, doble o cuádruple densidad de escritura.

TAMAÑOS TÏPICOS DE DISKETTES

� 5 ¼ 2S2D Baja Densidad - 360 Kb., 40 pistas, 9 sectores.

� 5 ¼ 2SHD Alta Densidad - 1.2 Mb., 80 pistas, 15 sectores.

� 3 ½ 2S2D Baja Densidad - 720 Kb., 80 pistas, 9 sectores.

� 3 ½ 2SHD Alta Densidad - 1.44 Mb., 80 pistas, 21 sectores.


PASOS PARA FORMATEAR UN DISCO DURO en MSDOS / Windows.

1.- Recabar la información correspondiente a la geometría del disco, por ejemplo, número de cabezas (platos), cilindros, sectores, capacidad total, etc. Esto puede hacerse en la carátula del disco o en su manual correspondiente.

2.- Instalarlo físicamente (cable de control y datos, cable de fuentes, tornillos, etc.).

Si el disco no es un maestro sino un esclavo, hay que modificar los “jumpers” del disco (o en algunos casos de ambos) para indicar que se trata de un esclavo.

3.- Dar de alta el disco en el set-up de la computadora utilizando la información recabada en el paso 1. Si el disco tiene auto-identificación, ponerlo en auto.

4.- Formatear el disco a bajo nivel. Este paso se omite en discos duros nuevos, y solamente se da para discos con algún tipo de problema, tal como sector de arranque dañado, demasiados sectores dañados, etc. que no puedan ser reparados con alguna utilería de disco. El formato a bajo nivel se hace con utilerías como el diskmanager o algunas que vienen integradas en el set-up de la máquina. Antes de dar el formato a bajo nivel se deben especificar algunos parámetros como el interleave (distribución de los sectores; contiguos, 1:1; terciados, 1:3; etc.), los sectores dañados (Cyl, Hd, BFI), y otros parámetros opcionales tales como bytes /sectores, etc. Con esta información se procede a formatear el disco, creando los sectores del disco , numerándolos y verificando su integridad.

Nota.- Debe tenerse cuidado de que la geometría escogida en el set-up sea exactamente la marcada en la carátula o manual del disco, pues si se escoge una geometría de emulación (misma capacidad pero con diferente número de cabezas, cilindros y sectores) el disco puede dañarse.

5.- Crear las particiones del disco duro y su tabla de particiones. Se utiliza el comando del sistema operativo Fdisk o la utilería diskmanager. En esta etapa se especifica si el disco duro se dividirá en varias particiones lógicas (por ejemplo una parte para C:, otra para D:, otra para E:, etc., o incluso una parte para instalar otro tipo de sistema operativo). Por omisión se toma todo el espacio disponible del disco duro para una sola partición, a la cual se le asigna la letra C:. A la partición C: se le denomina “primaria” y debe especificarse como activa (para arranque). Para crear particiones lógicas D:, E:, etc., primero hay que crear una partición extendida con el espacio sobrante de la partición primaria, y después crear cada una de las particiones lógicas, especificando el espacio que se destinará a cada una de ellas. Las particiones lógicas (D:, E:, etc.), son tomadas por el sistema de archivos como si fueran discos duros físicos independientes.

6.- Formatear el disco a alto nivel. Esto se hace con el comando del sistema operativo Format C: /S /V para la partición primaria, o Format Drive: /V en caso de que sea una partición adicional; donde “drive” corresponde a la letra asignada en el paso anterior (D:, E:, etc.). Este procedimiento crea la FAT (tabla de asignación de archivos) y la estructura


del directorio. Para el caso de la partición primaria (C:) también copia el sistema operativo y lo hace “arrancable”.

6.2 PLANIFICACION DE DISCO

En los sistemas multiprogramados, los procesos generan peticiones de lectura o escritura mucho más rápido de lo que pueden ser atendidas por los dispositivos de almacenamiento de disco. Por esta razón, es necesario generar colas de espera o servicio para cada dispositivo.

Muchos sistemas atienden estas peticiones en la forma "primero en llegar, primero en ser servido" o FCFS (first comes, firt served). Este sistema da buenos resultados cuando las peticiones no alcanzan un volumen muy grande, además de ser una forma justa de prestar servicio. Sin embargo, cuando el volumen de peticiones se sobrecarga, el método FCFS puede dar como resultado tiempos de espera muy largos. Esto es debido a que varias peticiones sucesivas pueden requerir búsquedas de cilindros no contiguos o incluso opuestos, por ejemplo ir de un cilindro interior a uno exterior, ocasionando búsquedas muy largas en discos de cabezas móviles.

Cuando se tienen altos volúmenes de peticiones, es conveniente tratar de reducir los tiempos de acceso tal que pueda prestarse un servicio más eficiente. Para esto, es necesario reordenar la cola de servicio de acuerdo a parámetros diferentes que a los del FCFS. A estas técnicas se les llama "planificación de disco.

Un planificador de disco, examina las direcciones de los sectores que tiene cada petición pendiente en la cola de servicio, y las reordena de tal manera que éstas puedan ser servidas con un mínimo de movimientos mecánicos.

La planificación de disco, debe intentar maximizar el número de peticiones servidas por unidad de tiempo, y minimizar el tiempo de respuesta promedio, eliminando desperdicios de tiempo al efectuar largas búsquedas.

Los dos tipos más comunes de planificación de disco son la optimización de búsqueda y la optimización rotacional.

Debido a que los tiempos de búsqueda son mayores que los tiempos de latencia, la mayoría de los algoritmos de planificación se centran en optimizar el tiempo de búsqueda. La optimización rotacional solo se utiliza bajo condiciones de carga muy pesada, y puede ser aplicada tanto en discos de cabezas móviles como de cabezas fijas.

6.3 OPTIMIZACION DE BUSQUEDA.

A continuación se describen los principales algoritmos utilizados en la optimización de búsqueda:

PRIMERO EN LLEGAR, PRIMERO EN SER SERVIDO. (First comes first served). FCFS. La primera petición que llega es la primera en ser servida. Una petición no puede ser desplazada por la llegada de otra petición con prioridad más alta.


Este algoritmo da un patrón de búsqueda al azar si las peticiones se encuentran uniformemente distribuidas en el disco.

FCFS produce tiempos de respuesta aceptables cuando se tiene una carga de peticiones ligera; es decir, que la cola de servicio no es muy larga. Sin embargo, cuando la cola aumenta considerablemente, el dispositivo se satura y el brazo del disco tiende a viajar frenéticamente de un extremo al otro, dando como resultado tiempos de respuesta largos.

MENOR TIEMPO DE BUSQUEDA PRIMERO. (Shortestseek time first). SSTF. Este algoritmo sirve la petición que produzca el menor tiempo de búsqueda; es decir, aquella petición que da por resultado el movimiento del brazo más corto con respecto a la posición actual del mismo. Por lo tanto, el orden en que llegan no es respetado.

Este tipo de algoritmo presenta un patrón de búsqueda muy concentrado en una sola región, principalmente las pistas medias; por lo que las pistas internas y externas reciben una atención pobre.

Tiene la ventaja de que da un buen número de peticiones servidas por unidad de tiempo, y una media de tiempo de respuesta baja para cargas moderadas, por lo que es muy recomendable para procesamiento por lotes (batch).

Sin embargo, para sistemas de tiempo compartido no es recomendable debido a que causa tiempo de respuestas largos para las peticiones que están en las pistas de los extremos.

BARRIDO (SCAN). En este algoritmo, la cabeza empieza en uno de los extremos del disco (por ejemplo el exterior), y empieza a moverse hacia el extremo opuesto (el interior), dando servicio a las peticiones que se encuentran en cada pista que va encontrando en su camino. Al llegar el extremo opuesto, la cabeza invierte el sentido de dirección y emprende el viaje de regreso, sirviendo todas las peticiones que se encuentran en esa trayectoria. Así por ejemplo, si una petición llega a la cola de servicio en el instante en que la cabeza pasa delante de la pista requerida por esa petición, será servida casi inmediatamente; mientras que si la petición llega justo detrás de la cabeza, entonces tendrá que esperar hasta que la cabeza emprenda el viaje de retorno y pase por la pista solicitada. El viaje de regreso puede ser iniciado no solamente cuando se alcanza el extremo del disco, sino también cuando ya no haya más peticiones en esa dirección.

Este algoritmo produce un buen número de peticiones servidas por unidad de tiempo, así como una buena medida de tiempos de respuesta.

Su característica principal es que evita las discriminaciones que se tienen en el algoritmo SSTF, por lo que sí es recomendable para sistemas de tiempo compartido. Tiene la desventaja de que los cilindros de los extremos son visitados con menos frecuencia, pero esto no es tan notorio como en el algoritmo SSTF.


BARRIDO DE N PASOS. (N STEP SCAN). Es una variante del algoritmo anterior. La diferencia estriba en que solamente se sirven las peticiones que hayan llegado hasta el momento en que el brazo inicia el movimiento hacia alguno de los extremos, por lo que las peticiones que llegan después y que aún podrían ser servidas por encontrarse en la trayectoria, son diferidas para el viaje de retorno.

Este algoritmo disminuye aún más la discriminación a ciertas peticiones.

BARRIDO CIRCULAR. (CIRCULAR SCAN). C-SCAN. Este algoritmo es otra variante más del algoritmo SCAN. C-SCAN mueve el brazo de un extremo a otro igual que SCAN, sirviendo las peticiones que encuentra en su trayectoria. Al llegar al extremo opuesto, el brazo regresa rápidamente al extremo del que partió, sin servir ninguna petición en su regreso. Por lo tanto C-SCAN trata el disco como si éste fuera circular; es decir, con la última pista adyacente a la primera.

C-SCAN elimina completamente la discriminación de los cilindros de los extremos, y proporciona un tiempo de respuesta más parejo para todas las peticiones.

Una variante de este algoritmo es el C-LOOK, el cual se comporta igual que el C-SCAN excepto que al irse moviendo hacia el extremo opuesto, si ya no hay más peticiones que servir en el resto de las pistas, entonces emprende el regreso.

En general, la planificación de disco mejora mucho la eficiencia del sistema; sin embargo, existen ciertos casos particulares en los que es más adecuado aplicar simplemente un algoritmo FCFS. Por ejemplo cuando no se tienen distribuciones uniformes como en los casos de archivos secuenciales muy largos, ya que los registros están todos contiguos y agrupados en una cierta zona del disco. Esto hace innecesario el algoritmo, ya que sólo existe una sola petición a través de un gran número de cilindros contiguos.

Otro caso problemático para aplicar la planificación de disco son los archivos secuenciales indexados tales como KSAM o ISAM, ya que el archivo de datos puede estar almacenado en cilindros diferentes a los de los índices. Esto hace que se tengan que realizar búsquedas de un extremo a otro, rompiendo con el algoritmo de planificación. Una solución para evitar romper con la planificación de disco es diferir el acceso al archivo de datos hasta que se pase por los cilindros correspondientes.

6.4 OPTIMIZACION ROTACIONAL

Cuando se tienen condiciones de carga muy pesada, la cola de servicio se hace muy larga, por lo que es necesario considerar la optimización rotacional para que junto con la optimización de búsqueda puedan manejar adecuadamente las peticiones.

La optimización rotacional se basa en el hecho de que bajo condiciones de carga muy pesada, la probabilidad de que ocurran referencias al mismo cilindro aumentan, por lo que se puede utilizar un algoritmo que optimice esas peticiones.

ALGORITMO TIEMPO DE TARDANZA MAS CORTO PRIMERO. Shortest latency time first). SLTF. En este algoritmo cuando el brazo llega a un cilindro en particular


(usando cualquier algoritmo de optimización de búsqueda), se examinan todas las peticiones pendientes para ese cilindro y se sirve primero aquella que tiene el tiempo de tardanza más pequeño. Esta estrategia se ha usado por muchos años en discos de cabezas fijas ya que estos tienen un tiempo de búsqueda despreciable. Además es fácil de implementar.

En resumen, en base a experiencias obtenidas, se puede decir que la mejor política de planificación de discos se puede manejar en tres etapas: para carga baja, la planificación SCAN es la mejor; mientras que para cargas medias y pesadas C-SCAN produce los mejores resultados. Para cargas muy pesadas, el algoritmo C-SCAN con optimización rotacional produce resultados efectivos.

6.5 METODOS DE ASIGNACION DE ARCHIVOS

Desde el punto de vista del usuario, un archivo es un tipo de dato abstracto. Puede ser creado, abierto, escrito, cerrado, etc., sin preocuparse por su implementación. Esto es trabajo del sistema operativo.

El problema principal es cómo asignar espacio a los archivos tal que el espacio del disco sea eficientemente utilizado y los archivos sean accesados rápidamente.

Existen 3 métodos de asignación de espacio que son los más usados: asignación contigua, asignación encadenada y asignación indexada. Cada método tiene sus ventajas y desventajas.

MANEJO DE ESPACIO LIBRE.

Antes de proceder a revisar estos métodos, veremos cómo se maneja el espacio disponible en un disco. Durante la operación de un sistema de cómputo, los archivos son creados y eliminados con frecuencia. Dado que el espacio en disco es limitado, es necesario reusarlo para colocar nuevos archivos.

Para mantener la huella del espacio libre en disco, el sistema de archivos mantiene una estructura de datos llamada "Lista de espacio libre", en la cual se almacena el número de los sectores del disco que están disponibles.

Cuando se desea crear un archivo, se recorre esta lista en busca de la cantidad requerida y se le otorga al nuevo archivo.

El espacio es entonces removido de la lista de espacio libre.

Esta lista es muy importante y existen varias maneras de implementarlas: una de ellas es por medio de un vector que contiene un bit por cada sector del disco. Si el sector correspondiente está disponible el bit se pone a cero; si no, se pone a uno. Como ejemplo, considere un disco donde los sectores 2,3,4,5,8,9,10,11,12,13,17,18,25,26 y 27 están libres. Entonces el vector que compone la lista de espacio libre nos queda:

110000110000001110011111100011111....


Otro método es encadenar todos los sectores libres del disco, manteniendo un apuntador al primer sector libre. Este sector tiene un apuntador al siguiente sector libre, y así sucesivamente. Ejemplo.

Este sistema no es muy rápido ya que para saber si habrá espacio suficiente, hay que recorrer la lista y leer cada sector.

Una modificación a este método consiste en encadenar bloques de sectores libres; por ejemplo si se tienen n sectores libres, en el primer sector se escriben todas las direcciones del resto de las n-1 sectores libres. En el último sector se escribe la dirección de otro sector que contiene las direcciones de otro bloque de n sectores libres.

La importancia de este método, es que se puede saber inmediatamente cuántos sectores libres se tienen en un bloque y si serán suficientes para almacenar un cierto archivo.

Otro método consiste en mantener la dirección del primer sector libre y el número de sectores contiguos libres que siguen a ese sector. Por lo tanto, en este caso la lista de espacio libre consiste de una dirección del disco y una cuenta.

ASIGNACION CONTIGUA

El método de asignación contigua, requiere que cada archivo ocupe un conjunto de direcciones contiguas en el disco. (Las direcciones en el disco generalmente están ordenadas en una forma lineal). Típicamente, las direcciones se incrementan a través de todos los sectores en una pista, después a través de todas las pistas de un cilindro, y


finalmente del cilindro cero al cilindro m (donde m es el número de cilindros en el disco). En un floppy sería igual, sólo que cada cilindro tiene únicamente dos pistas.

Este tipo de asignación puede soportar tanto acceso secuencial como directo.

La dificultad con la asignación contigua, es encontrar espacio para la creación de un archivo. Una vez que la lista de espacio libre ha sido definida, podemos definir cómo encontrar espacio para una asignación contigua. Si el archivo a ser creado es de n sectores de longitud, debemos buscar en la "lista de espacio libre" n sectores contiguos.

En una lista de espacio libre del tipo vector, necesitamos encontrar n bits en cero en fila. En una "lista de espacio libre" del tipo de direcciones y cuentas, necesitamos una cuenta de al menos n sectores.

Para el tipo de asignación contigua, se tienen dos algoritmos:

"PRIMERO EN AJUSTAR" (first fit). Busca el primer hueco de sectores contiguos en el que pueda caber el archivo.

"MEJOR EN AJUSTAR" (best fit). Busca el hueco de sectores contiguos más pequen~o en el que pueda caber el archivo.

Actualmente no se sabe cuál es mejor, pero el algoritmo primero en ajustar es el más rápido.

Ambos algoritmos sufren de fragmentación externa, la cual sucede cuando después de asignar y desasignar archivos exhaustivamente, el espacio en disco queda reducido a muchos pedazos pequeños que no son contiguos por lo que llega el momento en que un archivo no puede ser colocado en ninguno de ellos. Una solución al problema de fragmentación externa es aplicar técnicas de compactación (por ejemplo, mensualmente reempacar el disco).

Otro problema con asignación contigua es que cuando se crea un archivo, puede no saberse el tamaño de éste, una solución es que el usuario lo estime o el sistema le de un "default", pero si esta estimación resulta ser muy grande, se desperdiciará espacio.

Por oto lado, si resulta muy baja, no se podrá agregar más registros cuando se llegue al límite, por lo que habría que abortar la operación para que el usuario genere en archivo mayor, o bien el S.O. puede buscar un hueco mayor a donde trasladar todo el archivo.

Ejemplo de asignación contigua.


ASIGNACION ENCADENADA

En el método de asignación encadenada, los archivos no tienen la restricción de que deban ocupar sectores contiguos. En este método, cada archivo es formado por una lista encadenada de sectores del disco.

El directorio tiene un apuntador al primero y último sector del archivo. A su vez, cada sector contiene un apuntador al siguiente sector. Por ejemplo, un archivo de 5 sectores de longitud, puede comenzar en el sector 9, y continuar en el sector 16, después en el sector 1, sector 10 y finalmente sector 25. El archivo queda disperso por todo el disco. Los apuntadores no están accesibles al usuario. Esto se ilustra en la siguiente figura.


Si cada sector es de 512 palabras, y el apuntador requiere de dos palabras para almacenar una dirección del disco, entonces desde el punto de vista del usuario, los sectores quedan de 510 palabras.

Crear archivos es fácil en este método. Inicialmente se da de alta el nombre del archivo en el directorio, y se le asigna un sector de inicio. Este sector se inicializa a nil o nulo para indicar un archivo vacío.

Cuando se hace una operación de escritura, se remueve un sector de la "lista de sectores libres" y se escribe en él. En seguida ese sector es encadenado al final del archivo y el apuntador de final es actualizado en el directorio.

Una operación de lectura de este archivo consiste simplemente en leer los sectores siguiendo los apuntadores en cada sector.

No existe fragmentación externa en este método, ya que cualquier sector en la lista de sectores libres puede ser usado para encadenarlo a un archivo.

Note también que no es necesario declarar el tamaño del archivo cuando éste es creado. Su longitud puede continuar creciendo mientras haya sectores disponibles en la lista de sectores libres. Por lo tanto, nunca se requiere compactar el disco.

Sin embargo, la asignación encadenada también tiene desventajas. La mayor de ellas es que solo puede ser usada con eficiencia con archivos de acceso secuencial; ya que para posicionar el apuntador de archivo en cierta posición requeriría viajar secuencialmente a través de los sectores encadenados del archivo leyendo cada uno de ellos hasta encontrar el buscado.

Como consecuencia, algunos sistemas soportan acceso directo utilizando asignación contigua y acceso secuencial con asignación encadenada. Esto obliga a declarar inicialmente el tipo de acceso.

Un archivo declarado inicialmente como secuencial, no podrá ser utilizado en forma directa pues habrá sido encadenado; mientras que un archivo declarado inicialmente como directo, sí podrá ser utilizado en ambos tipos de acceso ya que habrá sido colocado en asignación contigua.

Una manera de convertir de un tipo de asignación a otro sería copiar un archivo de forma secuencial a otro definido como de acceso directo.

Otras desventajas son el espacio que ocupan los apuntadores, y la posibilidad de la pérdida de un apuntador al momento de leer, lo cual resultaría en una lectura a un archivo equivocado.

Esto último puede resolverse con un doble encadenamiento, pero requeriría un apuntador más y por lo tanto deja menos espacio útil.


ASIGNACION INDEXADA

La asignación encadenada resuelve los problemas de fragmentación externa y declaración de tamaño en la asignación contigua. Sin embargo, la asignación encadenada no soporta acceso directo debido a que sus bloques y más importante sus apuntadores, están dispersos por todo el disco.

La asignación indexada resuelve este problema, colocando todos los apuntadores juntos en un solo bloque, el bloque de índices.

Cada archivo tiene su propio bloque de índices, el cual es un arreglo de direcciones de sectores del disco. El primer apuntador del bloque de índices, apunta al primer sector del archivo, el segundo apuntador al segundo sector, y así sucesivamente. En general, el i-ésimo apuntador del bloque de índices apunta al i-ésimo sector del archivo. (Así, cuando deseamos leer la i-ésima componente, utilizamos el i-ésimo apuntador). Esto se ilustra en la siguiente figura.

Cuando el archivo es inicialmente creado, todos los apuntadores son puestos a nil ó nulo (en este caso -1). Cuando una escritura es requerida, un sector es removido de la lista de sectores libres y la información es escrita en él. A continuación su dirección por ejemplo la 9 es escrita en el bloque de índices; en este caso en la primera posición ya que es el primer bloque del archivo. El proceso se repite para cada nuevo bloque del archivo.

La asignación indexada soporta acceso directo sin sufrir de fragmentación externa. Cualquier sector libre en cualquier lugar del disco puede ser usado para satisfacer una nueva escritura.


Sin embargo, la asignación indexada sufre de pérdida de espacio ya que requiere de todo un bloque (un sector) por archivo para almacenar los apuntadores, aún cuando el archivo sea pequeño.

Normalmente el bloque de índices es de un sector, lo cual es suficiente para archivos de tamaño medio.

Para archivos de gran tamaño, varios bloques de índices pueden ser encadenados. En este caso, el último apuntador del primer bloque de índices apunta al segundo bloque de índices y así sucesivamente. Nótese que esta representación utiliza asignación encadenada para los bloques de índices. Otra variante de este método es usar un índice de bloques en el cual cada apuntador apunta a un índice de bloques que a su vez apunta a los sectores que componen el archivo.

Este método se puede llevar hasta un nivel de 4, pero generalmente es suficiente dos niveles. Tiene la desventaja de requerir varias lecturas según el número de niveles.

Documents

Instituto Tecnológico de la Laguna Departamento de ... Educativa... · 1.3 Relocalización 1.4 Multiples particiones contiguas fijas 1.5 Multiples particiones contiguas variables