Sistemas Operativos

Enviado por samescot2

Partes: 1, 2

Sistemas operativos

Introducción

A través de la historia d la computación se han conocido muchos sistemas operativos y cada vez se ha deseado automatizar más los sistemas operativos y generarlos con más confiabilidad, seguridad y protección para los registros de los usuarios.

Los sistemas operativos se han convertido en una herramienta eficaz dentro del mundo de los negocios y usuario con maquinas personales, los sistemas operativos con la ayuda de un buen soporte de hardware puede ser un patrón importante para el control de sus registros.

La importancia de los sistemas operativos nace históricamente desde los 50's, cuando se hizo evidente que el operar una computadora por medio de tableros enchufables en la primera generación y luego por medio del trabajo en lote en la segunda generación se podía mejorar notoriamente, pues el operador realizaba siempre una secuencia de pasos repetitivos, lo cual es una de las características contempladas en la definición de lo que es un programa. Es decir, se comenzó a ver que las tareas mismas del operador podían plasmarse en un programa, el cual a través del tiempo y por su enorme complejidad se le llamó "Sistema Operativo". Así, tenemos entre los primeros sistemas operativos al Fortran Monitor System ( FMS ) e IBSYS [Tan92].

Posteriormente, en la tercera generación de computadoras nace uno de los primeros sistemas operativos con la filosofía de administrar una familia de computadoras: el OS/360 de IBM. Fue este un proyecto tan novedoso y ambicioso que enfrentó por primera vez una serie de problemas conflictivos debido a que anteriormente las computadoras eran creadas para dos propósitos en general: el comercial y el científico. Así, al tratar de crear un solo sistema operativo para computadoras que podían dedicarse a un propósito, al otro o ambos, puso en evidencia la problemática del trabajo en equipos de análisis, diseño e implantación de sistemas grandes. El resultado fue un sistema del cual uno de sus mismos diseñadores patentizó su opinión en la portada de un libro: una horda de bestias prehistóricas atascadas en un foso de brea.

Surge también en la tercera generación de computadoras el concepto de la multiprogramación, porque debido al alto costo de las computadoras era necesario idear un esquema de trabajo que mantuviese a la unidad central de procesamiento más tiempo ocupada, así como el encolado (spooling ) de trabajos para su lectura hacia los lugares libres de memoria o la escritura de resultados. Sin embargo, se puede afirmar que los sistemas durante la tercera generación siguieron siendo básicamente sistemas de lote.

En la cuarta generación la electrónica avanza hacia la integración a gran escala, pudiendo crear circuitos con miles de transistores en un centímetro cuadrado de silicón y ya es posible hablar de las computadoras personales y las estaciones de trabajo. Surgen los conceptos de interfaces amigables intentando así atraer al público en general al uso de las computadoras como herramientas cotidianas. Se hacen populares el MS-DOS y UNIX en estas máquinas. También es común encontrar clones de computadoras personales y una multitud de empresas pequeñas ensamblándolas por todo el mundo.

Para mediados de los 80's, comienza el auge de las redes de computadoras y la necesidad de sistemas operativos en red y sistemas operativos distribuidos. La red mundial Internet se va haciendo accesible a toda clase de instituciones y se comienzan a dar muchas soluciones ( y problemas ) al querer hacer convivir recursos residentes en computadoras con sistemas operativos diferentes. Para los 90's el paradigma de la programación orientada a objetos cobra auge, así como el manejo de objetos desde los sistemas operativos. Las aplicaciones intentan crearse para ser ejecutadas en una plataforma específica y poder ver sus resultados en la pantalla o monitor de otra diferente (por ejemplo, ejecutar una simulación en una máquina con UNIX y ver los resultados en otra con DOS ). Los niveles de interacción se van haciendo cada vez más profundos.

Capitulo 1

Conceptos arquitectónicos de las computadoras

Estructura y Funcionamiento de la Computadora

La Computadora es una máquina destinada a procesar datos. Este procesamiento involucra dos flujos de información: el de datos y el de instrucciones. Se parte del flujo de datos que han de ser procesados. Este flujo de datos es tratado mediante un flujo de instrucciones de máquina, generado por la ejecución de un programa, y produce el flujo de datos resultado.

La memoria principal se construye con memoria RAM y memoria ROM. En ella han de residir los datos a procesar, el programa máquina a ejecutar y los resultados.

Se denomina programa máquina (o código) al conjunto de instrucciones máquina que tiene por objeto que la computadora realice una determinada función. Los programas escritos en cualquiera de los lenguajes de programación han de convertirse en programa máquina para poder ser ejecutados por la computadora.

La unidad aritmética permite realizar una serie de operaciones aritméticas y lógicas sobre uno o dos operándos.

La unidad de control es la que se encarga de hacer funcionar al conjunto, para lo cual realiza las siguientes funciones:

Lee de memoria las instrucciones máquina que forman el programa.
Interpreta cada instrucción leída.
Lee los datos de memoria referenciados por cada instrucción
Ejecuta cada instrucción
Almacena el resultado de cada instrucción.

Modelo de programación de la computadora.

El modelo de programación a bajo nivel de una computadora se caracteriza por los siguientes aspectos:

Elementos de almacenamiento. en esta sección se consideran aquellos elementos de almacenamiento de la computadora que son visibles a las instrucciones máquina. En esta categoría están incluidos los registros generales, el contador de programa, el puntero de pila, el registro de estado, la memoria principal y el mapa de E/S.
Juego de instrucciones.

Con sus correspondientes modos de direccionamiento. El jugo de instrucciones máquina define las operaciones que es capaz de hacer la computadora. Los modos de direccionamiento determinan la forma en que se especifica la identidad de los elementos de almacenamiento que invierten en las instrucciones maquina.

Secuencia de funcionamiento. Define el modo en que se van ejecutando las instrucciones máquina.

Niveles de ejecución

La mayoría de las computadoras actuales presenta dos o más niveles de ejecución. En el nivel menos permisivo, generalmente llamado nivel de usuario, la computadora ejecuta solamente un subconjunto de las instrucciones máquina, quedando prohibidas las demás.

Además, el acceso a determinados registros, o a partes de esos registros, y a determinadas zonas del mapa de memoria y de E/S también queda prohibido. En el nivel más permisivo, denominado nivel de núcleo, la computadora ejecuta todas sus instrucciones sin ninguna restricción y permite el acceso a todos los registros y mapas de direcciones.

Secuencia de funcionamiento de la computadora.

La unidad de control de la computadora es la que establece el funcionamiento del mismo.

Este funcionamiento está basado en una secuencia sencilla, que se repite a alta velocidad

Esta secuencia consiste en tres pasos:

Lectura de memoria principal de la instrucción máquina apuntada por el contador del programa.
Incremento del contador de programa para que apunte a la siguiente instrucción máquina.
Ejecución de la instrucción.

Registros de control y estado.

Como se ha indicado anteriormente, la unidad de control tiene asociada una serie de registros que denominamos de control y estado. Estos registros dependen de la arquitectura de la computadora y muchos de ellos se refieren a aspectos que se analizarán a lo largo del texto, por lo que no se intentará explicar aquí su función.

Interrupciones.

A nivel físico, una interrupción se solicita activando una señal que llega a la unidad de control. El agente generador o solicitante de la interrupción ha de activar la mencionada señal cuando necesite que se le atienda, es decir, que se ejecute un programa que le atienda.

Ante la solicitud de una interrupción, siempre y cuando esté habilitado ese tipo de interrupción, la unidad de control realiza un ciclo de aceptación de interrupción. Este ciclo se lleva a cabo en cuanto termina la ejecución de la instrucción máquina que se esté ejecutando y consiste en las siguientes operaciones:

Salva algunos registros del procesador, como son el de estado y el contador de programa.
Eleva el nivel de ejecución del procesador, pasándolo a núcleo.
Carga un nuevo valor en el contador de programa, por lo que pasa a ejecutar otro programa.

El reloj.

El término reloj se aplica a las computadoras con tres acepciones diferentes, estas tres acepciones son las siguientes:

Señal que gobierna el ritmo de ejecución de las instrucciones máquina.
Generador de interrupciones periódicas.
Contador de fecha y hora.

Jerarquía de memoria.

A medida que fueron creciendo las necesidades de los usuarios y se perfeccionaron los sistemas, se hizo necesaria una mayor organización del software, del sistema operativo, donde una parte del sistema contenía subpartes y esto organizado en forma de niveles.

Se dividió el sistema operativo en pequeñas partes, de tal forma que cada una de ellas estuviera perfectamente definida y con un claro interface con el resto de elementos.

Se constituyó una estructura jerárquica o de niveles en los sistemas operativos, el primero de los cuales fue denominado THE (Technische Hogeschool, Eindhoven), de Dijkstra, que se utilizó con fines didácticos (Ver Fig. 3). Se puede pensar también en estos sistemas como si fueran `multicapa'. Multics y Unix caen en esa categoría. [Feld93].

Para ver el gráfico seleccione la opción "Descargar" del menú superior

En la estructura anterior se basan prácticamente la mayoría de los sistemas operativos actuales. Otra forma de ver este tipo de sistema es la denominada de anillos concéntricos o "rings" (Ver Fig. 4).

Para ver el gráfico seleccione la opción "Descargar" del menú superior

En el sistema de anillos, cada uno tiene una apertura, conocida como puerta o trampa (trap), por donde pueden entrar las llamadas de las capas inferiores. De esta forma, las zonas más internas del sistema operativo o núcleo del sistema estarán más protegidas de accesos indeseados desde las capas más externas. Las capas más internas serán, por tanto, más privilegiadas que las externas.

Máquina Virtual.

Se trata de un tipo de sistemas operativos que presentan una interface a cada proceso, mostrando una máquina que parece idéntica a la máquina real subyacente. Estos sistemas operativos separan dos conceptos que suelen estar unidos en el resto de sistemas: la multiprogramación y la máquina extendida. El objetivo de los sistemas operativos de máquina virtual es el de integrar distintos sistemas operativos dando la sensación de ser varias máquinas diferentes.

El núcleo de estos sistemas operativos se denomina monitor virtual y tiene como misión llevar a cabo la multiprogramación, presentando a los niveles superiores tantas máquinas virtuales como se soliciten. Estas máquinas virtuales no son máquinas extendidas, sino una réplica de la máquina real, de manera que en cada una de ellas se pueda ejecutar un sistema operativo diferente, que será el que ofrezca la máquina extendida al usuario (Ver Fig. 5).

Para ver el gráfico seleccione la opción "Descargar" del menú superior

Cliente-servidor (Microkernel)

El tipo más reciente de sistemas operativos es el denominado Cliente-servidor, que puede ser ejecutado en la mayoría de las computadoras, ya sean grandes o pequeñas.

Este sistema sirve para toda clase de aplicaciones por tanto, es de propósito general y cumple con las mismas actividades que los sistemas operativos convencionales.

El núcleo tiene como misión establecer la comunicación entre los clientes y los servidores. Los procesos pueden ser tanto servidores como clientes. Por ejemplo, un programa de aplicación normal es un cliente que llama al servidor correspondiente para acceder a un archivo o realizar una operación de entrada/salida sobre un dispositivo concreto. A su vez, un proceso cliente puede actuar como servidor para otro." [Alcal92]. Este paradigma ofrece gran flexibilidad en cuanto a los servicios posibles en el sistema final, ya que el núcleo provee solamente funciones muy básicas de memoria, entrada/salida, archivos y procesos, dejando a los servidores proveer la mayoría que el usuario final o programador puede usar. Estos servidores deben tener mecanismos de seguridad y protección que, a su vez, serán filtrados por el núcleo que controla el hardware. Actualmente se está trabajando en una versión de UNIX que contempla en su diseño este paradigma.

Capitulo 2

Introducción a los sistemas operativos

2.1. ¿Qué es un sistema operativo?

Un sistema operativo es un programa que tiene encontradas una serie de funciones diferentes cuyo objetivo es simplificar el manejo y la utilización de la computadora, haciéndolo seguro y eficiente.

Maquina desnuda

El término de máquina desnuda se aplica a una computadora carente de sistema operativo, el término es interesante porque resalta el hecho de que una computadora en si misma no hace nada y para realizar una determinada función es necesario que contenga un sistema operativo.

Funciones del sistema operativo

Las funciones clásicas del sistema operativo se pueden agrupar en las tres categorías siguientes:

Gestión de los recursos de la computadora.
Ejecución de servicios para los programas.
Ejecución de los mandatos de los usuarios.

El sistema operativo como gestor de recursos

En una computadora actual suelen coexistir varios programas, del mismo o de varios usuarios, ejecutándose simultáneamente. Estos programas compiten por los recursos de la computadora, siendo el sistema operativo el encargado de arbitrar su asignación y uso. Como complemento a la gestión de recursos, el sistema operativo ha de garantizar la protección de unos programas frente a otros y ha de suministrar información sobre el uso que se hace de los recursos.

El sistema operativo como máquina extendida.

El sistema operativo ofrece a los programas un conjunto de servicios, o llamadas al sistema, que pueden solicitar cuando lo necesiten, proporcionando a los programas una visión de máquina extendida. Los servicios se pueden agrupar en las cuatro clases siguientes:

Ejecución de programas
Operaciones de E/S
Operaciones sobre archivos
Detección de tratamiento de errores.

Concepto de usuario y de grupo de usuario

Un usuario es una persona autorizada para utilizar un sistema informático. El usuario se autentica mediante su nombre de cuenta y su contraseña o password.

2.2. Arranque de la computadora

El arranque de una computadora actual tiene dos fases:

Arranque hardware
Arranque software

Que por el arranque hardware se entiende que es la parte dura es decir el inicio o encendido de todos los componentes de la PC

Ahora el arranque software es el inicio del sistema operativo en una computadora

2.3. Componentes y estructura del sistema operativo

El sistema operativo está formado por una serie de componentes especializados en determinadas funciones. Cada sistema operativo estructura estos componentes de forma distinta. En esta sección se describen en primer lugar los distintos componentes que conforman un sistema operativo.

Componentes del sistema operativo

Un sistema operativo está formado por tres capas:

El núcleo
Los servicios y el intérprete de mandatos o shell.

El núcleo es la parte del sistema operativo que interacciona directamente con el hardware de la máquina. Las funciones básicas de manipulación de menmoria.

Estructura del sistema operativo

Internamente los sistemas operativos estructuralmente de se clasifican según como se hayan organizado internamente en su diseño, por esto la clasificación más común de los sistemas operativos son:

Sistemas monolíticos

En estos sistemas operativos se escriben como un conjunto de procedimientos, cada uno de los cuales puede llamar a cualquiera de los otros siempre que lo necesite. Cuando se emplea esta técnica, cada procedimiento del sistema tiene una interfaz bien definida en términos de parámetros y resultados, y cada una tiene la libertad de llamar a cualquiera otra, si la última ofrece algún cálculo útil que la primera necesite.

Para construir el programa objeto real del sistema operativo cuando se usa este método, se compilan todos los procedimientos individuales a archivos que contienen los procedimientos y después se combinan todos en un solo archivo objeto con el enlazador.

En términos de ocultamiento de información, esencialmente no existe ninguno; todo procedimiento es visible para todos (al contrario de una estructura que contiene módulos o paquetes, en los cuales mucha información es local a un módulo y sólo pueden llamar puntos de registro designados oficialmente del exterior del módulo)

Sistemas operativos estructurados

Se dividió el sistema operativo en pequeñas partes, de tal forma que cada una de ellas estuviera perfectamente definida y con un claro interfase con el resto de elementos

Cliente-servidor

El tipo más reciente de sistemas operativos es el denominado Cliente-servidor, que puede ser ejecutado en la mayoría de las computadoras, ya sean grandes o pequeñas.

Este sistema sirve para toda clase de aplicaciones por tanto, es de propósito general y cumple con las mismas actividades que los sistemas operativos convencionales.

2.4. Gestión de procesos

Uno de los módulos más importantes de un sistema operativo es la de administrar los procesos y tareas del sistema de cómputo. En esta sección se revisarán dos temas que componen o conciernen a este módulo: la planificación del procesador y los problemas de concurrencia.

Planificación del procesador

La planificación del procesador se refiere a la manera o técnicas que se usan para decidir cuánto tiempo de ejecución y cuando se le asignan a cada proceso del sistema. Obviamente, si el sistema es monousuario y monotarea no hay mucho que decidir, pero en el resto de los sistemas esto es crucial para el buen funcionamiento del sistema.

Niveles de planificación

En los sistemas de planificación generalmente se identifican tres niveles: el alto, el medio y el bajo. El nivel alto decide que trabajos (conjunto de procesos) son candidatos a convertirse en procesos compitiendo por los recursos del sistema; el nivel intermedio decide que procesos se suspenden o reanudan para lograr ciertas metas de rendimiento mientras que el planificador de bajo nivel es el que decide que proceso, de los que ya están listos (y que en algún momento paso por los otros dos planificadores) es al que le toca ahora estar ejecutándose en la unidad central de procesamiento. En este trabajo se revisaran principalmente los planificadores de bajo nivel porque son los que finalmente eligen al proceso en ejecución.

2.5. Gestión de memoria

El gestor de memoria es uno de los componentes principales del sistema operativo. Su actividad se centra fundamentalmente en la categoría de gestión de recursos, puesto que tiene por objetivo casi exclusivo la gestión del recurso memoria, en este sentido se encarga de:

Asignar memoria a los procesos para crear su imagen de memoria.
Proporcionar memoria a los procesos cuando la soliciten y liberarla cuando así lo requieran.
Tratar los posibles errores de acceso a memoria, evitando que unos procesos interfieran en la memoria de otros.
Permitir que los procesos puedan compartir memoria entre ellos. De esta forma los procesos podrán comunicarse entre ellos.
Gestionar la jerarquía de memoria y tratar los fallos de página en los sistemas con memoria virtual.

Servicios

El gestor de memoria ofrece una serie de servicios a los procesos. Estos son:

Solicitar memoria
Liberar memoria
Compartir memoria.

2.6. Comunicación y sincronización entre procesos

Los procesos son entes independientes y aislados, puesto que, por razones de seguridad, no deben interferir unos con otros. Sin embargo, cuando se divide un trabajo complejo en varios procesos que cooperan entre sí para realizar ese trabajo, es necesario que se comuniquen para transmitirse datos y ordenes y se sincronicen en la ejecución de sus acciones. Por tanto, el sistema operativo debe incluir servicios de comunicación y sincronización entre procesos que, sin romper los esquemas de seguridad, han de permitir la cooperación entre ellos.

Servicios de comunicación y sincronización.

Como se ha visto anteriormente, existen distintos mecanismos de comunicación y sincronización, cada uno de los cuales se puede utilizar a través de un conjunto de servicios propios. Estos mecanismos son entidades vivas, cuya vida presenta las siguientes fases:

Creación del mecanismo.
Utilización del mecanismo.
Destrucción del mecanismo.

De acuerdo con esto, los servicios básicos de comunicación, que incluyen todos los mecanismos, son los siguientes:

Crear. Permite que el proceso solicite la creación del mecanismo.
Enviar o escribir. Permite que el proceso emisor envíe información a otro.
Recibir o leer. Permite que el proceso receptor reciba información de otro.
Destruir. Permite que el proceso solicite la creación o destrucción del mecanismo.

2.7. Gestión de la E/S

Una de las principales funciones de un sistema operativo es la gestión de los recursos de la computadora y, en concreto, de los dispositivos periféricos. El gestor de E/S debe controlar el funcionamiento de todos los dispositivos de E/S para alcanzar los siguientes objetivos:

Facilitar el manejo de los dispositivos periféricos. Para ello ofrecer una interfaz sencilla, uniforme y fácil de utilizar entre los dispositivos, y gestionar los errores que se pueden producir en el acceso a los mismos.
Ofrecer mecanismos de protección que impidan a los usuarios acceder sin control a los dispositivos periféricos.

El código destinado a manejar la entrada y salida de los diferentes periféricos en un sistema operativo es de una extensión considerable y sumamente complejo. Resuelve las necesidades de sincronizar, atrapar interrupciones y ofrecer llamadas al sistema para los programadores. En esta sección se repasarán los principios más importantes a tomar en cuenta en este módulo del sistema operativo.

Los dispositivos de entrada salida se dividen, en general, en dos tipos: dispositivos orientados a bloques y dispositivos orientados a caracteres. Los dispositivos orientados a bloques tienen la propiedad de que se pueden direccionar, esto es, el programador puede escribir o leer cualquier bloque del dispositivo realizando primero una operación de posicionamiento sobre el dispositivo. Los dispositivos más comunes orientados a bloques son los discos duros, la memoria, discos compactos y, posiblemente, unidades de cinta. Por otro lado, los dispositivos orientados a caracteres son aquellos que trabajan con secuencias de bytes sin importar su longitud ni ninguna agrupación en especial. No son dispositivos direccionables. Ejemplos de estos dispositivos son el teclado, la pantalla o display y las impresoras.

La clasificación anterior no es perfecta, porque existen varios dispositivos que generan entrada o salida que no pueden englobarse en esas categorías. Por ejemplo, un reloj que genera pulsos. Sin embargo, aunque existan algunos periféricos que no se puedan categorizar, todos están administrados por el sistema operativo por medio de una parte electrónica – mecánica y una parte de software.

Controladores de Dispositivos (Terminales y Discos Duros)

Los controladores de dispositivos (también llamados adaptadores de dispositivos) son la parte electrónica de los periféricos, el cual puede tener la forma de una tarjeta o un circuito impreso integrado a la tarjeta maestra de la computadora. Por ejemplo, existen controladores de discos que se venden por separado y que se insertan en una ranura de la computadora, o existen fabricantes de computadoras que integran esa funcionalidad en la misma tarjeta en que viene la unidad central de procesamiento (tarjeta maestra).

Los controladores de dispositivos generalmente trabajan con voltajes de 5 y 12 volts con el dispositivo propiamente, y con la computadora a través de interrupciones. Estas interrupciones viajan por el 'bus' de la computadora y son recibidos por el CPU el cual a su vez pondrá en ejecución algún programa que sabrá qué hacer con esa señal. A ese programa se le llama 'manejador de disposito' (device driver). Algunas veces el mismo controlador contiene un pequeño programa en una memoria de solo lectura o en memoria de acceso aleatoria no volátil y re-escribible que interactúa con el correspondiente manejador en la computadora. En la figura 6.1 se muestra un esquema simple de dispositivos orientados a bloques y otros a caracteres.

Por ejemplo, la terminal (CRT) tiene un 'chip' que se encarga de enviar cadenas de bits por medio de un cable serial que a su vez son recibidos por un controlador de puerto serial en la computadora. Este 'chip' también se encarga de leer secuencias de bits que agrupa para su despiegue en la pantalla o para ejecutar algunas funciones de control. Lo importante en todos estos dispositivos es que se debe ejercer un mecanismo para sincronizar el envío y llegada de datos de manera concurrente.

2.8. Gestión de Archivos y directorios.

El servidor de archivos es la parte del sistema operativo que cubre una de las cuatro clases de funciones que tiene este en su faceta de máquina extendida. Los Objetivos fundamentales del servidor de archivos son los dos siguientes:

Facilitar el manejote los dispositivos periféricos. Para ello ofrece una visión lógica simplificada de los mismos en forma de archivos.
Proteger a los usuarios, poniendo limitaciones a los archivos que es capaz de manipular cada usuario.

Los servicios que se engloban en el servidor de archivos son de dos tipos:

Los servicios dirigidos al manejo de datos, o archivos.
Los dirigidos al manejo de los nombres o directorios.

Un sistema de archivos ( file system ) es una estructura de directorios con algún tipo de organización el cual nos permite almacenar, crear y borrar archivos en diferenctes formatos. En esta sección se revisarán conceptos importantes relacionados a los sistemas de archivos.

Almacenamiento Físico de Datos

En un sistema de cómputo es evidente que existe la necesidad por parte de los usuarios y aplicaciones de almacenar datos en algún medio, a veces por periodos largos y a veces por instantes. cada aplicación y cada usuario debe tener ciertos derechos con sus datos, como son el poder crearlos y borrarlos, o cambialos de lugar; así como tener privacidad contra otros usuarios o aplicaciones. El subsistema de archivos del sistema operativo se debe encargar de estos detalles, además de establecer el formato físico en el cual almacenará los datos en discos duros, cintas o discos flexibles. Debe ser conocido por todos que tradicionalmente la información en los sistemas modernos se almacena en discos duros, flexibles y unidades de disco óptico, y en todos ellos se comparten algunos esquemas básicos para darles formato físico: las superficies de almacenamiento son divididas en círculos concéntricos llamados "pistas" y cada pista se divide en "sectores". A la unión lógica de varias pistas a través de varias superficies "paralelas" de almacenamiento se les llama "cilindros", los cuales son inspeccionados al momento de lectura o escritura de datos por las respectivas unidades fisicas llamadas "cabezas". Las superficies de almacenamiento reciben el nombre de "platos" y generalmente están en movimiento rotatorio para que las cabezas accesen a las pistas que los componen. Los datos se escriben a través de los sectores en las pistas y cilindros modificando las superficies por medio de las cabezas.

El tiempo que una cabeza se tarda en ir de una pista a otra se le llama "tiempo de búsqueda" y dependerá de la distancia entre la posición actual y la distancia a la pista buscada. El tiempo que tarda una cabeza en ir del sector actual al sector deseado se le llama tiempo de latencia y depende de la distancia entre sectores y la velocidad de rotación del disco. El impacto que tiene las lecturas y escrituras sobre el sistema está determinado por la tecnología usada en los platos y cabezas y por la forma de resolver las peticiones de lectura y escritura, es decir, los algoritmos de planificación.

Algoritmos de planificación de peticiones

Los algoritmos de planificación de peticiones de lectura y escritura a discos se encargan de registrar dichas peticiones y de responderlas en un tiempo razonable. Los algoritmos más comunes para esta tarea son:

Primero en llegar, primero en ser servido ( FIFO ): Las peticiones son encoladas de acuerdo al orden en que llegaron y de esa misma forma se van leyendo o escribiendo las mismas. La ventaja de este algoritmo es su simplicidad y no causa sobrecarga, su desventaja principal es que no aprovecha para nada ninguna característica de las peticiones, de manera que es muy factible que el brazo del disco se mueva muy ineficientemente, ya que las peticiones pueden tener direcciones en el disco unas muy alejadas de otras. Por ejemplo, si se están haciendo peticiones a los sectores 6,10,8,21 y 4, las mismas serán resueltas en el mismo orden. _ Primero el más cercano a la posición actual: En este algoritmo las peticiones se ordenan de acuerdo a la posición actual de la cabeza lectora, sirviendo primero a aquellas peticiones más cercanas y reduciendo, así, el movimiento del brazo, lo cual constituye la ventaja principal de este algoritmo. Su desventaja consiste en que puede haber solicitudes que se queden esperando para siempre, en el infortunado caso de que existan peticiones muy alejadas y en todo momento estén entrando peticiones que estén más cercanas. Para las peticiones 6,10,8,21 y 4, las mismas serán resueltas en el orden 4,6,8,10 y 21.
Por exploración ( algoritmo del elevador ): En este algoritmo el brazo se estará moviendo en todo momento desde el perímetro del disco hacia su centro y viceversa, resolviendo las peticiones que existan en la dirección que tenga en turno. En este caso las peticiones 6,10,8,21 y 4 serán resueltas en el orden 6,10,21,8 y 4; es decir, la posición actual es 6 y como va hacia los sectores de mayor numeración (hacia el centro, por ejemplo), en el camino sigue el sector 10, luego el 21 y ese fue el más central, así que ahora el brazo resolverá las peticiones en su camino hacia afuera y la primera que se encuentra es la del sector 8 y luego la 4. La ventaja de este algoritmo es que el brazo se moverá mucho menos que en FIFO y evita la espera indefinida; su desventaja es que no es justo, ya que no sirve las peticiones en el orden en que llegaron, además de que las peticiones en los extremos interior y exterior tendrán un tiempo de respuesta un poco mayor.
Por exploración circular: Es una variación del algoritmo anterior, con la única diferencia que al llegar a la parte central, el brazo regresa al exterior sin resolver ninguna petición, lo cual proveerá un tiempo de respuesta más cercana al promedio para todas las peticiones, sin importar si están cercas del centro o del exterior.

Asignación del espacio de almacenamiento

El subsistema de archivos se debe encargar de localizar espacio libre en los medios de almacenamiento para guardar archivos y para después borrarlos, renombrarlos o agrandarlos. Para ello se vale de localidades especiales que contienen la lista de archivos creados y por cada archivo una serie de direcciones que contienen los datos de los mismos. Esas localidades especiales se llaman directorios. Para asignarle espacio a los archivos existen tres criterios generales que se describen enseguida.

Asignación contigua: Cada directorio contiene la los nombres de archivos y la dirección del bloque inicial de cada archivo, así como el tamaño total de los mismos. Por ejemplo, si un archivo comienza en el sector 17 y mide 10 bloques, cuando el archivo sea accesado, el brazo se moverá inicialmente al bloque 17 y de ahí hasta el 27. Si el archivo es borrado y luego creado otro más pequeño, quedarán huecos inútiles entre archivos útiles, lo cual se llama fragmentación externa.
Asignación encadenada: Con este criterio los directorios contienen los nombres de archivos y por cada uno de ellos la dirección del bloque inicial que compone al archivo. Cuando un archivo es leído, el brazo va a esa dirección inicial y encuentra los datos iniciales junto con la dirección del siguiente bloque y así sucesivamente. Con este criterio no es necesario que los bloques estén contiguos y no existe la fragmentación externa, pero en cada "eslabón" de la cadena se desperdicia espacio con las direcciones mismas. En otras palabras, lo que se crea en el disco es una lista ligada.
Asignación con índices ( indexada ): En este esquema se guarda en el directorio un bloque de índices para cada archivo, con apuntadores hacia todos sus bloques constituyentes, de manera que el acceso directo se agiliza notablemente, a cambio de sacrificar varios bloques para almacenar dichos apuntadores. Cuando se quiere leer un archivo o cualquiera de sus partes, se hacen dos accesos: uno al bloque de índices y otro a la dirección deseada. Este es un esquema excelente para archivos grandes pero no para pequeños, porque la relación entre bloques destinados para índices respecto a los asignados para datos es incosteable.

Métodos de acceso en los sistemas de archivos.

Los métodos de acceso se refieren a las capacidades que el subsistema de archivos provee para accesar datos dentro de los directorios y medios de almacenamiento en general. Se ubican tres formas generales: acceso secuencial, acceso directo y acceso directo indexado.

Acceso secuencial: Es el método más lento y consiste en recorrer los componentes de un archivo uno en uno hasta llegar al registro deseado. Se necesita que el orden lógico de los registros sea igual al orden físico en el medio de almacenamiento. Este tipo de acceso se usa comúnmente en cintas y cartuchos.
Acceso directo: Permite accesar cualquier sector o registro inmediatamente, por medio de llamadas al sistema como la de seek. Este tipo de acceso es rápido y se usa comúnmente en discos duros y discos o archivos manejados en memoria de acceso aleatorio. _ Acceso directo indexado: Este tipo de acceso es útil para grandes volúmenes de información o datos. Consiste en que cada archivo tiene una tabla de apuntadores, donde cada apuntador va a la dirección de un bloque de índices, lo cual permite que el archivo se expanda a través de un espacio enorme. Consume una cantidad importante de recursos en las tablas de índices pero es muy rápido.

Operaciones soportadas por el subsistema de archivos

Independientemente de los algoritmos de asignación de espacio, de los métodos de acceso y de la forma de resolver las peticiones de lectura y escritura, el subsistema de archivos debe proveer un conjunto de llamadas al sistema para operar con los datos y de proveer mecanismos de protección y seguridad. Las operaciones básicas que la mayoría de los sistemas de archivos soportan son:

Crear ( create ) : Permite crear un archivo sin datos, con el propósito de indicar que ese nombre ya está usado y se deben crear las estructuras básicas para soportarlo.
Borrar ( delete ): Eliminar el archivo y liberar los bloques para su uso posterior.
Abrir ( open ): Antes de usar un archivo se debe abrir para que el sistema conozca sus atributos, tales como el dueño, la fecha de modificación, etc. _ Cerrar ( close ): Después de realizar todas las operaciones deseadas, el archivo debe cerrarse para asegurar su integridad y para liberar recursos de su control en la memoria.
Leer o Escribir ( read, write ): Añadir información al archivo o leer el caracter o una cadena de caracteres a partir de la posición actual. _ Concatenar ( append ): Es una forma restringida de la llamada `write', en la cual sólo se permite añadir información al final del archivo. _ Localizar ( seek ): Para los archivos de acceso directo se permite posicionar el apuntador de lectura o escritura en un registro aleatorio, a veces a partir del inicio o final del archivo.
Leer atributos: Permite obtener una estructura con todos los atributos del archivo especificado, tales como permisos de escritura, de borrado, ejecución, etc.
Poner atributos: Permite cambiar los atributos de un archivo, por ejemplo en UNIX, donde todos los dispositivos se manejan como si fueran archivos, es posible cambiar el comportamiento de una terminal con una de estas llamadas.
Renombrar ( rename ): Permite cambiarle el nombre e incluso a veces la posición en la organización de directorios del archivo especificado. Los subsistemas de archivos también proveen un conjunto de llamadas para operar sobre directorios, las más comunes son crear, borrar, abrir, cerrar, renombrar y leer. Sus funcionalidades son obvias, pero existen también otras dos operaciones no tan comunes que son la de `crear una liga' y la de `destruir la liga'. La operación de crear una liga sirve para que desde diferentes puntos de la organización de directorios se pueda accesar un mismo directorio sin necesidad de copiarlo o duplicarlo. La llamada a `destruir la liga' lo que hace es eliminar esas referencias, siendo su efecto la de eliminar las ligas y no el directorio real. El directorio real es eliminado hasta que la llamada a `destruir liga' se realiza sobre él.

Algunas facilidades extras de los sistemas de archivos

Algunos sistemas de archivos proveen herramientas al administrador del sistema para facilitarle la vida. Las más notables es la facilidad de compartir archivos y los sistemas de `cotas'.

La facilidad de compartir archivos se refiere a la posibilidad de que los permisos de los archivos o directorios dejen que un grupo de usuarios puedan accesarlos para diferentes operaciones" leer, escribir, borrar, crear, etc. El dueño verdadero es quien decide qué permisos se aplicarán al grupo e, incluso, a otros usuarios que no formen parte de su grupo. La facilidad de `cotas' se refiere a que el sistema de archivos es capaz de llevar un control para que cada usuario pueda usar un máximo de espacio en disco duro. Cuando el usuario excede ese límite, el sistema le envía un mensaje y le niega el permiso de seguir escribiendo, obligándolo a borrar algunos archivos si es que quiere almacenar otros o que crezcan. La versión de UNIX SunOS contiene esa facilidad.

Sistemas de Archivos Aislados

Los sistemas de archivos aislados son aquellos que residen en una sola computadora y no existe la posibilidad de que, aún estando en una red, otros sistemas puedan usar sus directorios y archivos. Por ejemplo, los archivos en discos duros en el sistema MS-DOS clásico se puede ver en esta categoría.

Sistemas de Archivos Compartidos o de Red

Estos sistemas de archivos es factible accesarlos y usarlos desde otros nodos en una red. Generalmente existe un `servidor' que es la computadora en donde reside el sistema de archivos físicamente, y por otro lado están los `clientes', que se valen del servidor para ver sus archivos y directorios de manera como si estuvieran localmente en el cliente. Algunos autores les llaman a estos sistemas de archivos `sistemas de archivos distribuidos' lo cual no se va a discutir en este trabajo.

Los sistemas de archivos compartidos en red más populares son los provistos por Netware, el Remote Filke Sharing ( RFS en UNIX ), Network File System ( NFS de Sun Microsystems ) y el Andrew File System ( AFS ). En general, lo que proveen los servidores es un medio de que los clientes, localmente, realicen peticiones de operaciones sobre archivos los cuales con `atrapadas' por un `driver' o un `módulo' en el núcleo del sistema operativo, el cual se comunica con el servidor a través de la red y la operación se ejecuta en el servidor. Existen servidores de tipo "stateless y no-stateless". Un servidor "stateless" no registra el estado de las operaciones sobre los archivos, de manera que el cliente se encarga de todo ese trabajo. La ventaja de este esquema es que si el servidor falla, el cliente no perderá información ya que ésta se guarda en memoria localmente, de manera que cuando el servidor reanude su servicio el cliente proseguirá como si nada hubiese sucedido. Con un servidor "no-stateless", esto no es posible.

La protección sobre las operaciones se lleva a cabo tanto el los clientes como en el servidor: si el usuario quiere ejecutar una operación indebida sobre un archivo, recibirá un mensaje de error y posiblemente se envíe un registro al subsistema de `seguridad' para informar al administrador del sistema de dicho intento de violación.

En la práctica, el conjunto de permisos que cada usuario tiene sobre el total de archivos se almacena en estructuras llamadas `listas de acceso' ( access lists ).

Tendencias actuales

Con el gran auge de las redes de comunicaciones y su incremento en el ancho de banda, la proliferación de paquetes que ofrecen la comparición de archivos es común. Los esquemas más solicitados en la industria es el poder accesar los grandes volúmenes de información que residen en grandes servidores desde las computadoras personales y desde otros servidores también. Es una realidad que la solución más socorrida en las empresas pequeñas es usar Novell Netware en un servidor 486 o superior y accesar los archivos desde máquinas similares.

A veces se requieren soluciones más complejas con ambientes heterogéneos:

diferentes sistemas operativos y diferentes arquitecturas. Uno de los sistemas de archivos más expandidos en estaciones de trabajo es el NFS, y prácticamente todas las versiones de UNIX traen instalado un cliente y hasta un servidor de este servicio. Es posible así que una gran cantidad de computadoras personales (de 10 a 80 ) accesen grandes volúmenes de información o paquetería (desde 1 a 8 Giga bites ) desde una sola estación de trabajo, e incluso tener la flexibilidad de usar al mismo tiempo servidores de Novell y NFS. Soluciones similares se dan con algunos otros paquetes comerciales, pero basta ya de `goles'. Lo importante aquí es observar que el mundo se va moviendo poco a poco hacia soluciones distribuidas, y hacia la estandarización que, muchas veces, es `de facto'.

2.9. Seguridad y protección

La seguridad reviste dos aspectos, uno es garantizar la identidad de los usuarios y otro es definir lo que puede hacer cada uno de ellos. El primer aspecto se trata bajo el término de autenticación, mientras que el segundo se hace mediante los privilegios. La seguridad es una de las funciones del sistema operativo que, para llevarla a cabo, se ha de basar en los mecanismos de protección que le proporciona el hardware.

Autenticación.

El objetivo de la autenticación es determinar que un usuario( persona, servicio o computadora) es quien dice ser.

Privilegios.

Los privilegios especifican los recursos que puede acceder cada usuario. Para simplificar la información de privilegi9os es corriente organizar a los usuarios en grupos, asignando determinados privilegios a cada grupo.

2.10. Activación del sistema operativo.

Una vez presentadas las funciones y principales componentes del sistema operativo, es importante describir cuáles son las acciones que activan la ejecución del mismo, el sistema operativo es un servidor que está a la espera de que se encargue trabajo.

2.11. Interfaz del programador.

2.13. Historia de los sistemas operativos

Los Sistemas Operativos, al igual que el Hardware de los computadores, han sufrido una serie de cambios revolucionarios llamados generaciones. En el caso del Hardware, las generaciones han sido marcadas por grandes avances en los componentes utilizados, pasando de válvulas ( primera generación ) a transistores ( segunda generación ), a circuitos integrados ( tercera generación), a circuitos integrados de gran y muy gran escala (cuarta generación). Cada generación Sucesiva de hardware ha ido acompañada de reducciones substanciales en los costos, tamaño, emisión de calor y consumo de energía, y por incrementos notables en velocidad y capacidad.

Generación Cero (década de 1940)

Los primeros sistemas computacionales no poseían sistemas operativos. Los usuarios tenían completo acceso al lenguaje de la maquina. Todas las instrucciones eran codificadas a mano.

Primera Generación (década de 1950)

Los sistemas operativos de los años cincuenta fueron diseñados para hacer mas fluida la transición entre trabajos. Antes de que los sistemas fueran diseñados, se perdía un tiempo considerable entre la terminación de un trabajo y el inicio del siguiente. Este fue el comienzo de los sistemas de procesamiento por lotes, donde los trabajos se reunían por grupos o lotes. Cuando el trabajo estaba en ejecución, este tenia control total de la maquina. Al terminar cada trabajo, el control era devuelto al sistema operativo, el cual limpiaba y leía e iniciaba el trabajo siguiente.

Al inicio de los 50's esto había mejorado un poco con la introducción de tarjetas perforadas (las cuales servían para introducir los programas de lenguajes de máquina), puesto que ya no había necesidad de utilizar los tableros enchufables.

Además el laboratorio de investigación General Motors implementó el primer sistema operativo para la IBM 701. Los sistemas de los 50's generalmente ejecutaban una sola tarea, y la transición entre tareas se suavizaba para lograr la máxima utilización del sistema. Esto se conoce como sistemas de procesamiento por lotes de un sólo flujo, ya que los programas y los datos eran sometidos en grupos o lotes.

La introducción del transistor a mediados de los 50's cambió la imagen radicalmente.

Se crearon máquinas suficientemente confiables las cuales se instalaban en lugares especialmente acondicionados, aunque sólo las grandes universidades y las grandes corporaciones o bien las oficinas del gobierno se podían dar el lujo de tenerlas.

Para poder correr un trabajo (programa), tenían que escribirlo en papel (en Fortran o en lenguaje ensamblador) y después se perforaría en tarjetas. Enseguida se llevaría la pila de tarjetas al cuarto de introducción al sistema y la entregaría a uno de los operadores. Cuando la computadora terminara el trabajo, un operador se dirigiría a la impresora y desprendería la salida y la llevaría al cuarto de salida, para que la recogiera el programador.

Segunda Generación (a mitad de la década de 1960)

La característica de los sistemas operativos fue el desarrollo de los sistemas compartidos con multiprogramación, y los principios del multiprocesamiento. En los sistemas de multiprogramación, varios programas de usuario se encuentran al mismo tiempo en el almacenamiento principal, y el procesador se cambia rápidamente de un trabajo a otro. En los sistemas de multiprocesamiento se utilizan varios procesadores en un solo sistema computacional, con la finalidad de incrementar el poder de procesamiento de la maquina.

La independencia de dispositivos aparece después. Un usuario que desea escribir datos en una cinta en sistemas de la primera generación tenia que hacer referencia especifica a una unidad de cinta particular. En la segunda generación, el programa del usuario especificaba tan solo que un archivo iba a ser escrito en una unidad de cinta con cierto número de pistas y cierta densidad.

Se desarrollo sistemas compartidos, en la que los usuarios podían acoplarse directamente con el computador a través de terminales. Surgieron sistemas de tiempo real, en que los computadores fueron utilizados en el control de procesos industriales. Los sistemas de tiempo real se caracterizan por proveer una respuesta inmediata.

Tercera Generación (mitad de década 1960 a mitad década de 1970)

Se inicia en 1964, con la introducción de la familia de computadores Sistema/360 de IBM. Los computadores de esta generación fueron diseñados como sistemas para usos generales . Casi siempre eran sistemas grandes, voluminosos, con el propósito de serlo todo para toda la gente. Eran sistemas de modos múltiples, algunos de ellos soportaban simultáneamente procesos por lotes, tiempo compartido, procesamiento de tiempo real y multiprocesamiento. Eran grandes y costosos, nunca antes se había construido algo similar, y muchos de los esfuerzos de desarrollo terminaron muy por arriba del presupuesto y mucho después de lo que el planificador marcaba como fecha de terminación.

Estos sistemas introdujeron mayor complejidad a los ambientes computacionales; una complejidad a la cual, en un principio, no estaban acostumbrados los usuarios.

Cuarta Generación (mitad de década de 1970 en adelante)

Los sistemas de la cuarta generación constituyen el estado actual de la tecnología. Muchos diseñadores y usuarios se sienten aun incómodos, después de sus experiencias con los sistemas operativos de la tercera generación.

Con la ampliación del uso de redes de computadores y del procesamiento en línea los usuarios obtienen acceso a computadores alejados geográficamente a través de varios tipos de terminales.

Los sistemas de seguridad se ha incrementado mucho ahora que la información pasa a través de varios tipos vulnerables de líneas de comunicación. La clave de cifrado esta recibiendo mucha atención; han sido necesario codificar los datos personales o de gran intimidad para que; aun si los datos son expuestos, no sean de utilidad a nadie mas que a los receptores adecuados.

El porcentaje de la población que tiene acceso a un computador en la década de los ochenta es mucho mayor que nunca y aumenta rápidamente.

El concepto de maquinas virtuales es utilizado. El usuario ya no se encuentra interesado en los detalles físicos de; sistema de computación que esta siendo accedida. En su lugar, el usuario ve un panorama llamado maquina virtual creado por el sistema operativo.

Los sistemas de bases de datos han adquirido gran importancia. Nuestro mundo es una sociedad orientada hacia la información, y el trabajo de las bases de datos es hacer que esta información sea conveniente accesible de una manera controlada para aquellos que tienen derechos de acceso.

Capitulo 3

Procesos

Planificación del procesador

Niveles de planificación

En los sistemas de planificación generalmente se identifican tres niveles: el alto, em medio y el bajo. El nivel alto decide que trabajos (conjunto de procesos) son candidatos a convertirse en procesos compitiendo por los recursos del sistema; el nivel intermedio decide que procesos se suspenden o reanudan para lograr ciertas metas de rendimiento mientras que el planificador de bajo nivel es el que decide que proceso, de los que ya están listos (y que en algún momento paso por los otros dos planificadores) es al que le toca ahora estar ejecutándose en la unidad central de procesamiento. En este trabajo se revisaran principalmente los planificadores de bajo nivel porque son los que finalmente eligen al proceso en ejecución.

Objetivos de la planificación

Una estrategia de planificación debe buscar que los procesos obtengan sus turnos de ejecución apropiadamente, conjuntamente con un buen rendimiento y minimización de la sobrecarga (overhead) del planificador mismo. En general, se buscan cinco objetivos principales:

Justicia o Imparcialidad: Todos los procesos son tratados de la misma forma, y en algún momento obtienen su turno de ejecución o intervalos de tiempo de ejecución hasta su terminación exitosa.
Maximizar la Producción: El sistema debe de finalizar el mayor numero de procesos en por unidad de tiempo.
Maximizar el Tiempo de Respuesta: Cada usuario o proceso debe observar que el sistema les responde consistentemente a sus requerimientos.
Evitar el aplazamiento indefinido: Los procesos deben terminar en un plazo finito de tiempo.
El sistema debe ser predecible: Ante cargas de trabajo ligeras el sistema debe responder rápido y con cargas pesadas debe ir degradándose paulatinamente. Otro punto de vista de esto es que si se ejecuta el mismo proceso en cargas similares de todo el sistema, la respuesta en todos los casos debe ser similar.

Características a considerar de los procesos

No todos los equipos de cómputo procesan el mismo tipo de trabajos, y un algoritmo de planificación que en un sistema funciona excelente puede dar un rendimiento pésimo en otro cuyos procesos tienen características diferentes. Estas características pueden ser:

Cantidad de Entrada/Salida: Existen procesos que realizan una gran cantidad de operaciones de entrada y salida (aplicaciones de bases de datos, por ejemplo).
Cantidad de Uso de CPU: Existen procesos que no realizan muchas operaciones de entrada y salida, sino que usan intensivamente la unidad central de procesamiento. Por ejemplo, operaciones con matrices.
Procesos de Lote o Interactivos: Un proceso de lote es más eficiente en cuanto a la lectura de datos, ya que generalmente lo hace de archivos, mientras que un programa interactivo espera mucho tiempo (no es lo mismo el tiempo de lectura de un archivo que la velocidad en que una persona teclea datos) por las respuestas de los usuarios.
Procesos en Tiempo Real: Si los procesos deben dar respuesta en tiempo real se requiere que tengan prioridad para los turnos de ejecución.
Longevidad de los Procesos: Existen procesos que tipicamente requeriran varias horas para finalizar su labor, mientras que existen otros que solonecesitan algunos segundos.

Planificación apropiativa o no apropiativa (preemptive or not preemptive)

La planificación apropiativa es aquella en la cual, una vez que a un proceso le toca su turno de ejecución ya no puede ser suspendido, ya no se le puede arrebatar la unidad central de procesamiento. Este esquema puede ser peligroso, ya que si el proceso contiene accidental o deliberadamente ciclos infinitos, el resto de los procesos pueden quedar aplazados indefinidamente. Una planificación no apropiativa es aquella en que existe un reloj que lanza interrupciones periodicas en las cuales el planificador toma el control y se decide si el mismo proceso seguirá ejecutándose o se le da su turno a otro proceso. Este mismo reloj puede servir para lanzar procesos manejados por el reloj del sistema. Por ejemplo en los sistemas UNIX existen los 'cronjobs' y 'atjobs', los cuales se programan en base a la hora, minuto, día del mes, día de la semana y día del año.

En una planificación no apropiativa, un trabajo muy grande aplaza mucho a uno pequeño, y si entra un proceso de alta prioridad esté también debe esperar a que termine el proceso actual en ejecución.

Asignación del turno de ejecución

Los algoritmos de la capa baja para asignar el turno de ejecución se describen a continuación:

Por prioridad: Los procesos de mayor prioridad se ejecutan primero. Si existen varios procesos de mayor prioridad que otros, pero entre ellos con la misma prioridad, pueden ejecutarse estos de acuerdo a su orden de llegada o por 'round robin'. La ventaja de este algoritmo es que es flexible en cuanto a permitir que ciertos procesos se ejecuten primero e, incluso, por más tiempo. Su desventaja es que puede provocar aplazamiento indefinido en los procesos de baja prioridad. Por ejemplo, suponga que existen procesos de prioridad 20 y procesos de prioridad 10. Si durante todo el día terminan procesos de prioridad 20 al mismo ritmo que entran otros con esa prioridad, el efecto es que los de prioridad 10 estarán esperando por siempre. También provoca que el sistema sea impredecible para los procesos de baja prioridad.
El trabajo más corto primero: Es dificil de llevar a cabo porque se requiere saber o tener una estimación de cuánto tiempo necesita el proceso para terminar. Pero si se sabe, se ejecutan primero aquellos trabajos que necesitan menos tiempo y de esta manera se obtiene el mejor tiempo de respuesta promedio para todos los procesos. Por ejemplo, si llegan 5 procesos A,B,C,D y E cuyos tiempos de CPU son 26, 18, 24, 12 y 4 unidades de tiempo, se observa que el orden de ejecución será E,D,B,C y A (4,12,18, 24 y 26 unidades de tiempo respectivamente). En la tabla siguiente se muestra en que unidad de tiempo comienza a ejecutarse cada proceso y como todos comenzaron a esperar desde la unidad cero, se obtiene el tiempo promedio de espera.

Proceso Espera desde Termina Tiempo de Espera

A 0 4 4

B 0 16 16

C 0 34 34

D 0 58 58

E 0 84 84

Tiempo promedio = (4 + 16 + 34 + 58 + 84 )/5 = 39 unidades.

El primero en llegar, primero en ejecutarse: Es muy simple, los procesos reciben su turno conforme llegan. La ventaja de este algoritmo es que es justo y no provoca aplazamiento indefinido. La desventaja es que no aprovecha ninguna característica de los procesos y puede no servir para unproceso de tiempo real. Por ejemplo, el tiempo promedio de respuesta puede ser muy malo comparado con el logrado por el del trabajo más corto primero. Retomando el mismo ejemplo que en el algoritmo anterior, obtenemos un tiempo de respuesta promedio (26+44+68+80+84)/5 = 60 unidades, el cual es muy superior a las 39 unidades que es el mejor tiempo posible.
Round Robin: También llamada por turno, consiste en darle a cada proceso un intervalo de tiempo de ejecución (llamado time slice), y cada vez que se vence ese intervalo se copia el contexto del proceso a un lugar seguro y se le da su turno a otro proceso. Los procesos están ordenados en una cola circular. Por ejemplo, si existen tres procesos, el A,B y C, dos repasadas del planificador darían sus turnos a los procesos en el orden A,B,C,A,B,C. La ventaja de este algoritmo es su simplicidad, es justo y no provoca aplazamiento indefinido.
El tiempo restante más corto: Es parecido al del trabajo más corto primero, pero aquií se está calculando en todo momento cuánto tiempo le resta para terminar a todos los procesos, incluyendo los nuevos, y aquel que le quede menos tiempo para finalizar es escogido para ejecutarse. La ventaja es que es muy útil para sistemas de tiempo compartido porque se acerca mucho al mejor tiempo de respuesta, además de responder dinámicamente a la longevidad de los procesos; su desventaja es que provoca más sobrecarga porque el algoritmo es más complejo.
La tasa de respuesta más alta: Este algoritmo concede el truno de ejecución al proceso que produzca el valor mayor de la siguiente formula:

tiempo que ha esperado + tiempo total para terminar

valor = ___________________________________________

tiempo total para terminar.

Es decir, que dinámicamente el valor se va modificando y mejora un poco las deficiciencias del algoritmo del trabajo más corto primero.

Por politica: Una forma de asignar el turno de ejecución es por politica, en la cual se establece algún reglamento específico que el planificador debe obedecer. Por ejemplo, una politica podría ser que todos los procesos reciban el mismo tiempo de uso de CPU en cualquier momento. Esto sig- nifica, por ejemplo, que si existen 2 procesos y han recibido 20 unidades de tiempo cada uno (tiempo acumulado en time slices de 5 unidades) y en este momento entra un tercer proceso, el planificador le dara inmediatamente el turno de ejecución por 20 unidades de tiempo. Una vez que todos los procesos están 'parejos' en uso de CPU, se les aplica 'round robin'.

Capitulo 4

Gestión de Memoria

La memoria es uno de los principales recursos de la computadora, la cual debe de administrarse con mucho cuidado. Aunque actualmente la mayoría de los sistemas de cómputo cuentan con una alta capacidad de memoria, de igual manera las aplicaciones actuales tienen también altos requerimientos de memoria, lo que sigue generando escasez de memoria en los sistemas multitarea y/o multiusuario.

La parte del sistema operativo que administra la memoria se llama administrador de memoria y su labor consiste en llevar un registro de las partes de memoria que se estén utilizando y aquellas que no, con el fin de asignar espacio en memoria a los procesos cuando éstos la necesiten y liberándola cuando terminen, así como administrar el intercambio entre la memoria principal y el disco en los casos en los que la memoria principal no le pueda dar capacidad a todos los procesos que tienen necesidad de ella.

Los sistemas de administración de memoria se pueden clasificar en dos tipos: los que desplazan los procesos de la memoria principal al disco y viceversa durante la ejecución y los que no.

El propósito principal de una computadora es el de ejecutar programas, estos programas, junto con la información que accesan deben de estar en la memoria principal (al menos parcialmente) durante la ejecución.

Para optimizar el uso del CPU y de la memoria, el sistema operativo debe de tener varios procesos a la vez en la memoria principal, para lo cual dispone de varias opciones de administración tanto del procesador como de la memoria. La selección de uno de ellos depende principalmente del diseño del hardware para el sistema. A continuación se observarán los puntos correspondientes a la administración de la memoria.

Memoria real

La memoria real o principal es en donde son ejecutados los programas y procesos de una computadora y es el espacio real que existe en memoria para que se ejecuten los procesos. Por lo general esta memoria es de mayor costo que la memoria secundaria, pero el acceso a la información contenida en ella es de más rápido acceso. Solo la memoria cache es más rápida que la principal, pero su costo es a su vez mayor.

Sin intercambio

Monoprogramación sin intercambio o paginación

Cuando solo se tiene un proceso que ocupe la memoria a la vez, el esquema de la administración de la memoria es el más sencillo que hay. Sin embargo, éste método ya no tiene aplicación en la actualidad, ya que era visto en las computadoras con sistemas operativos de un solo usuario y una sola tarea. El usuario introducía su disco a la computadora (por lo general, la máquina no contaba con disco duro) y ejecutaba su aplicación, la cual acaparaba toda la máquina.

Para ver el gráfico seleccione la opción ¨Bajar trabajo¨ del menú superior

Fig.1. Ejemplos de distribución de la memoria principal con un sistema operativo y un solo proceso de usuario

La figura 1 muestra la organización de la memoria usando este sistema. La memoria se divide entre el sistema operativo y el proceso de un solo usuario. La más conocida es la que muestra el inciso c, que es la usada por las PC’ de IBM. Los controladores de dispositivo los almacena en memoria ROM, en un bloque de 8K de la parte superior del espacio de direcciones de 1M.

El ejemplo más claro de este esquema es el que podemos ver en el sistema operativo MS-DOS, en que el usuario escribe un comando al sistema y al ejecutarse el sistema operativo lo carga a memoria desde el disco y realiza sus funciones. Cuando el proceso termina la memoria es liberada y le muestra al usuario el indicador de comandos (prompt) en la pantalla.

Multiprogramación y uso de memoria

Esta organización facilita la programación de una aplicación al dividirla en dos o más procesos. Además ofrece la capacidad de tener más de un proceso a la vez en memoria así puede ofrecer servicios a varios usuarios a la vez.

El esquema de multiprogramación incrementa el aprovechamiento del CPU, dado que a diferencia de la monoprogramación en donde solo un proceso reside en memoria a la vez limitando el uso del procesador a las llamadas que requiera dicho proceso, desperdiciando un promedio del 80% del tiempo del procesador. En cambio la multiprogramación, al tener varios procesos en la memoria principal y dividiéndose el tiempo de uso del procesador, logra reducir drásticamente el desperdicio del procesador.

Multiprogramación con particiones fijas

Para poder implementar la multiprogramación, se puede hacer uso de particiones fijas o variables en la memoria. En el caso de las particiones fijas, la memoria se puede organizar dividiéndose en diversas partes, las cuales pueden variar en tamaño. Esta partición la puede hacer el usuario en forma manual, al iniciar una sesión con la máquina.

Una vez implementada la partición, hay dos maneras de asignar los procesos a ella. La primera es mediante el uso de una cola única (figura 2a) que asigna los procesos a los espacios disponibles de la memoria conforme se vayan desocupando. El tamaño del hueco de memoria disponible es usado para localizar en la cola el primer proceso que quepa en él. Otra forma de asignación es buscar en la cola el proceso de tamaño mayor que se ajuste al hueco, sin embargo hay que tomar en cuenta que tal método discrimina a los procesos más pequeños. Dicho problema podría tener solución si se asigna una partición pequeña en la memoria al momento de hacer la partición inicial, el cual sería exclusivo para procesos pequeños.

Para ver el gráfico seleccione la opción "Descargar" del menú superior

Fig. 2. (a) Particiones fijas en memoria con una cola única de entrada. (b) Particiones fijas en memoria con colas exclusivas para cada tamaño diferente de la partición. El espacio asignado a la partición 2 está en desuso.

Esta idea nos lleva a la implementación de otro método para particiones fijas, que es el uso de diferentes colas independientes (figura 2b) exclusivas para cierto rango en el tamaño de los procesos. De esta manera al llegar un proceso, éste sería asignado a la cola de tamaño más pequeño que la pueda aceptar. La desventaja en esta organización es que si una de las colas tiene una larga lista de procesos en espera, mientras otra cola esta vacía, el sector de memoria asignado para ese tamaño de procesos estaría desperdiciándose.

Con intercambio

Multiprogramación con particiones variables

Este esquema fue originalmente usado por el sistema operativo IBM OS/360 (llamado MFT), el cual ya no está en uso.

El sistema operativo lleva una tabla indicando cuáles partes de la memoria están disponibles y cuáles están ocupadas. Inicialmente, toda la memoria está disponible para los procesos de usuario y es considerado como un gran bloque o hueco único de memoria. Cuando llega un proceso que necesita memoria, buscamos un hueco lo suficientemente grande para el proceso. Si encontramos uno, se asigna únicamente el espacio requerido, manteniendo el resto disponible para futuros procesos que requieran de espacio.

Consideremos el ejemplo de la figura 3, en donde se cuenta un espacio reservado para el sistema operativo en la memoria baja de 400K y un espacio disponible para procesos de usuario de 2160K, siendo un total de memoria del sistema de 2560K. Dada la secuencia de procesos de la figura y usando un algoritmo de First Come – First Served (FCFS) se puede asignar de inmediato memoria a los procesos P1, P2 y P3, creando el mapa de memoria de la figura 4(a) en el cual queda un hueco de 260K que ya no puede ser utilizado por el siguiente proceso dado que no es suficiente para abarcarlo.

Para ver el gráfico seleccione la opción "Descargar" del menú superior

Fig. 3. Ejemplo de una división inicial de memoria y una lista de trabajos.

Para ver el gráfico seleccione la opción "Descargar" del menú superior

Fig. 4. Ejemplo de asignación de procesos en la memoria principal.

Usando un proceso de asignación Round-Robin con un quantum de 1 unidad de tiempo, el proceso P2 terminaría en la unidad de tiempo 14, liberando esa cantidad de memoria, como se muestra en la figura 4(b). Entonces el sistema operativo checa la lista de trabajos y asigna el siguiente proceso que quepa en el espacio de memoria liberado. El proceso P4 produce el mapa de memoria que se muestra en la figura 4(c). El proceso P1 terminará en la unidad de tiempo 28 para producir el mapa de la figura 4(d) y entonces se asigna el proceso P5 generando el mapa de la figura 4(e).

Cuando a un proceso se le asigna un espacio y es cargado a la memoria principal, puede entonces competir para el uso del CPU.

Compactación de memoria

Cuando un proceso llega y necesita memoria, el sistema operativo busca en la tabla de huecos alguno lo suficientemente grande para el proceso. Si el hueco es muy grande, lo parte en dos. Una parte es asignada al proceso y la otra se identifica como hueco. Cuando el proceso termina y la memoria es liberada, el espacio es identificado como un hueco más en la tabla y si el nuevo hueco es adyacente con otro, ambos huecos se unen formando un solo hueco más grande. En ese momento se debe de checar si no existen procesos a los que este nuevo hueco pueda darles cabida.

Para ver el gráfico seleccione la opción "Descargar" del menú superior

Fig. 5. Ejemplo de compactación de huecos no adyacentes.

En la figura 5 se muestra como se modifica el mapa de la memoria después de compactar huecos no adyacentes generados después de intercambios realizados en el ejemplo de la figura 4.

Asignación dinámica

El proceso de compactación del punto anterior es una instancia particular del problema de asignación de memoria dinámica, el cual es el cómo satisfacer una necesidad de tamaño n con una lista de huecos libres. Existen muchas soluciones para el problema. El conjunto de huecos es analizado para determinar cuál hueco es el más indicado para asignarse. Las estrategias más comunes para asignar algún hueco de la tabla son:

Primer ajuste: Consiste en asignar el primer hueco con capacidad suficiente. La búsqueda puede iniciar ya sea al inicio o al final del conjunto de huecos o en donde terminó la última búsqueda. La búsqueda termina al encontrar un hueco lo suficientemente grande.
Mejor ajuste: Busca asignar el espacio más pequeño de los espacios con capacidad suficiente. La búsqueda se debe de realizar en toda la tabla, a menos que la tabla esté ordenada por tamaño. Esta estrategia produce el menor desperdicio de memoria posible.
Peor ajuste: Asigna el hueco más grande. Una vez más, se debe de buscar en toda la tabla de huecos a menos que esté organizada por tamaño. Esta estrategia produce los huecos de sobra más grandes, los cuales pudieran ser de más uso si llegan procesos de tamaño mediano que quepan en ellos.

Se ha demostrado mediante simulacros que tanto el primer y el mejor ajuste son mejores que el peor ajuste en cuanto a minimizar tanto el tiempo del almacenamiento. Ni el primer o el mejor ajuste es claramente el mejor en términos de uso de espacio, pero por lo general el primer ajuste es más rápido.

Administración de la memoria con mapas de bits

Este tipo de administración divide la memoria en unidades de asignación, las cuales pueden ser tan pequeñas como unas cuantas palabras o tan grandes como varios kilobytes. A cada unidad de asignación le corresponde un bit en el mapa de bits, el cual toma el valor de 0 si la unidad está libre y 1 si está ocupada (o viceversa). La figura 6 muestra una parte de la memoria y su correspondiente mapa de bits.

Para ver el gráfico seleccione la opción "Descargar" del menú superior

Fig. 6. Ejemplo de un mapa de bits para la administración de la memoria.

Un mapa de bits es una forma sencilla para llevar un registro de las palabras de la memoria en una cantidad fija de memoria, puesto que el tamaño del mapa sólo depende del tamaño de la memoria y el tamaño de la unidad de asignación.

Administración de la memoria con listas ligadas

Otra forma de mantener un registro de la memoria es mediante una lista ligada de los segmentos de memoria asignados o libres, en donde un segmento puede ser un proceso o un hueco entre dos procesos. La memoria de la figura 7(a) está mostrada como una lista ligada de segmentos en la figura 7(b). Cada entrada de la lista especifica un hueco (H) o un proceso (P), la dirección donde comienza, su longitud y un apuntador a la siguiente entrada.

Para ver el gráfico seleccione la opción "Descargar" del menú superior

Fig. 7. Ejemplo de listas ligadas.

En este ejemplo, la lista de segmentos está ordenada por direcciones, lo que da la ventaja de que al terminar o intercambiar un proceso, la actualización de la lista es directa.

Asignación del hueco de intercambio

En algunos sistemas, cuando el proceso se encuentra en la memoria, no hay un hueco en el disco asignado a él. Cuando deba intercambiarse, se deberá asignar un hueco para él en el área de intercambio del disco. Los algoritmos para la administración del hueco de intercambio son los mismos que se utilizan para la administración de la memoria principal.

En otros sistemas, al caerse un proceso, se le asigna un hueco de intercambio en el disco. Cuando el proceso sea intercambiado, siempre pasará al hueco asignado, en vez de ir a otro lugar cada vez. Cuando el proceso concluya, se libera el hueco de intercambio. La única diferencia es que el hueco en disco necesario para un proceso debe representarse como un número entero de bloques del disco. Por ejemplo, un proceso de 13.5 K debe utilizar 14K (usando bloques de 1K).

Fragmentación

La fragmentación es la memoria que queda desperdiciada al usar los métodos de gestión de memoria que se vieron en los métodos anteriores. Tanto el primer ajuste, como el mejor y el peor producen fragmentación externa.

La fragmentación es generada cuando durante el reemplazo de procesos quedan huecos entre dos o más procesos de manera no contigua y cada hueco no es capaz de soportar ningún proceso de la lista de espera. Tal vez en conjunto si sea espacio suficiente, pero se requeriría de un proceso de defragmentación de memoria o compactación para lograrlo. Esta fragmentación se denomina fragmentación externa.

Existe otro tipo de fragmentación conocida como fragmentación interna, la cual es generada cuando se reserva más memoria de la que el proceso va realmente a usar. Sin embargo a diferencia de la externa, estos huecos no se pueden compactar para ser utilizados. Se debe de esperar a la finalización del proceso para que se libere el bloque completo de la memoria.

Memoria virtual

Paginación

Hasta ahora, los métodos que hemos visto de la administración de la memoria principal, nos han dejado con un problema: fragmentación, (huecos en la memoria que no pueden usarse debido a lo pequeño de su espacio) lo que nos provoca un desperdicio de memoria principal.

Una posible solución para la fragmentación externa es permitir que espacio de direcciones lógicas lleve a cabo un proceso en direcciones no contiguas, así permitiendo al proceso ubicarse en cualquier espacio de memoria física que esté disponible, aunque esté dividida. Una forma de implementar esta solución es a través del uso de un esquema de paginación. La paginación evita el considerable problema de ajustar los pedazos de memoria de tamaños variables que han sufrido los esquemas de manejo de memoria anteriores. Dado a sus ventajas sobre los métodos previos, la paginación, en sus diversas formas, es usada en muchos sistemas operativos.

Al utilizar la memoria virtual, las direcciones no pasan en forma directa al bus de memoria, sino que van a una unidad administradora de la memoria (MMU –Memory Management Unit). Estas direcciones generadas por los programas se llaman direcciones virtuales y conforman el hueco de direcciones virtuales. Este hueco se divide en unidades llamadas páginas. Las unidades correspondientes en la memoria física se llaman marcos para página o frames. Las páginas y los frames tienen siempre el mismo tamaño.

Tablas de páginas

Cada página tiene un número que se utiliza como índice en la tabla de páginas, lo que da por resultado el número del marco correspondiente a esa página virtual. Si el bit presente / ausente es 0, se provoca un señalamiento (trap) hacia el sistema operativo. Si el bit es 1, el número de marco que aparece en la tabla de páginas se copia en los bits de mayor orden del registro de salida, junto con el ajuste (offset) de 12 bits, el cual se copia sin modificaciones de la dirección virtual de entrada. Juntos forman una dirección física de 15 bits. El registro de salida se coloca entonces en el bus de la memoria como la dirección en la memoria física.

En teoría, la asociación de las direcciones virtuales con las físicas se efectúa según lo descrito. El número de página virtual se divide en un número de página virtual (los bits superiores)y un ajuste (los bits inferiores). El número de página virtual se utiliza como un índice en la tabla de páginas para encontrar la entrada de esa página virtual. El número de marco (si existe) se determina a partir de la tabla de páginas. El número de marco se asocia al extremo superior del ajuste y reemplaza al número de página virtual para formar una dirección física que se puede enviar a la memoria.

La finalidad de la tabla de páginas es asociar las páginas virtuales con los marcos. En términos matemáticos, la tabla de páginas es una función, cuyo argumento es el número de página virtual y como resultado el número del marco físico. Mediante el resultado de esta función, se puede reemplazar el campo de la página virtual de una dirección virtual por un campo de marco, lo que produce una dirección en la memoria física. Sin embargo hay que enfrentar dos aspectos fundamentales:

La tabla de páginas puede ser demasiado grande.
La asociación debe ser rápida.

El primer punto proviene del hecho de que las computadoras modernas utilizan direcciones virtuales de al menos 32 bits. Por ejemplo, si el tamaño de página es de 4K, un hueco de direcciones de 32 bits tiene un millón de páginas; en el caso de un hueco de direcciones de 64 bits, se tendría más información de la que uno quisiera contemplar.

El segundo punto es consecuencia del hecho de que la asociación virtual – física debe hacerse en cada referencia a la memoria. Una instrucción común tiene una palabra de instrucción y también un operando de memoria. Entonces es necesario hacer una, dos o más referencias a la tabla de páginas por cada instrucción.

Algoritmos de reemplazo de páginas

Con el uso del método de paginación se puede llegar a saturar la memoria si se incrementa demasiado el nivel de multiprogramación. Por ejemplo, si se corren seis procesos, cada uno con un tamaño de diez páginas de las cuales en realidad sólo utiliza cinco, se tiene un mayor uso del CPU y con marcos de sobra. Pero pudiera suceder que cada uno de esos procesos quiera usar las diez páginas resultando en una necesidad de 60 marcos, cuando solo hay 40 disponibles.

Esto provoca sobre-asignación y mientras un proceso de usuario se está ejecutando, ocurre un fallo de página. El hardware se bloquea con el sistema operativo, el cual checa en sus tablas internas y se da cuenta que es un fallo de página y no un acceso ilegal de memoria. El sistema operativo determina si la página está residiendo en disco, pero también determina que no hay marcos de memoria disponibles en la lista de marcos libres.

Al ocurrir el fallo de página, el sistema operativo debe elegir una página para retirarla de la memoria y usar el espacio para la página que se necesita para desbloquear el sistema y que el hardware pueda seguir trabajando. Si la página por eliminar de la memoria fue modificada, se debe volver a escribir al disco para mantener la información actualizada; de lo contrario, si la página no fue modificada no es necesario rescribir la información a disco y la página que se carga simplemente se escribe sobre la página a borrar en memoria. La figura 8 muestra gráficamente un intercambio de páginas entre la memoria principal y el disco (memoria secundaria).

Para ver el gráfico seleccione la opción "Descargar" del menú superior

Fig. 8. Se elimina de la memoria principal una página que no esté en uso y se reemplaza por una página de la cual el sistema operativo tiene necesidad de uso.

Algoritmo aleatorio

Este algoritmo consiste simplemente en reemplazar aleatoriamente cualquier página de la memoria principal, sin hacer ningún esfuerzo de predicción.

Es el algoritmo más sencillo dado que no requiere tener ninguna información, sin embargo, por no hacer uso de dicha información sobre el comportamiento del proceso, no puede lograr un buen desempeño.

Algoritmo de reemplazo de páginas óptimo

Este algoritmo debe de tener el menor índice de fallos de página de todos los algoritmos. En teoría, este algoritmo debe de reemplazar la página que no va a ser usada por el periodo más largo de tiempo.

Desafortunadamente, el algoritmo de reemplazo óptimo es fácil en teoría, pero prácticamente imposible de implementar, dado que requiere conocer a futuro las necesidades del sistema.

Tal algoritmo existe y ha sido llamado OPT o MIN, pero se usa únicamente para estudios de comparaciones. Por ejemplo, puede resultar muy útil saber que aunque algún nuevo algoritmo no sea óptimo, está entre el 12.3% del óptimo y entre el 4.7% en promedio.

Algoritmo de reemplazo de páginas según el uso no tan reciente

Este algoritmo hace uso de los dos bits de estado que están asociados a cada página. Estos bits son: R, el cual se activa cuando se hace referencia (lectura / escritura) a la página asociada; y M, que se activa cuando la página asociada es modificada (escritura). Estos bits deben de ser actualizado cada vez que se haga referencia a la memoria, por esto es de suma importancia que sean activados por el hardware. Una vez activado el bit, permanece en ese estado hasta que el sistema operativo, mediante software, modifica su estado.

Estos bits pueden ser utilizados para desarrollar un algoritmo de reemplazo que cuando inicie el proceso, el sistema operativo asigne un valor de 0 a ambos bits en todas las páginas. En cada interrupción de reloj, limpie el bit R para distinguir cuáles páginas tuvieron referencia y cuáles no.

Cuando ocurre un fallo de página, el sistema operativo revisa ambos bits en todas las páginas y las clasifica de la siguiente manera:

Clase 0: La página no ha sido referenciada, ni modificada.

Clase 1: La página no ha sido referenciada, pero ha sido modificada.

Clase 2: La página ha sido referenciada, pero no ha sido modificada.

Clase 3: La página ha sido referenciada y también modificada.

Una vez obtenida la clasificación, elimina una página de manera aleatoria de la primera clase no vacía con el número más pequeño. Esto porque para el algoritmo es mejor eliminar una página modificada sin referencias en al menos un intervalo de reloj, que una página en blanco de uso frecuente.

A pesar de que este algoritmo no es el óptimo, es fácil de implementar y de comprender y con mucha frecuencia es el más adecuado.

Algoritmo de reemplazo "Primero en entrar, primero en salir" (FIFO)

El algoritmo más sencillo para remplazo de páginas es el FIFO (First In – First Out). Este algoritmo asocia a cada página el momento en que ésta fue traída a memoria. Cuando una página debe ser reemplazada se selecciona a la más antigua.

No es estrictamente necesario registrar el momento de entrada de la página a memoria, sino que se puede crear una cola en la que se van agregando las páginas conforme van llegando a la memoria. Cuando se debe eliminar una página, se selecciona la que está al frente de la lista (o sea, la más antigua de la lista). Cuando llega una página nueva, se inserta en la parte trasera de la cola. En la figura 9 se representa el funcionamiento de éste algoritmo.

Para ver el gráfico seleccione la opción "Descargar" del menú superior

Fig. 9. Reemplazo de páginas mediante el algoritmo FIFO.

Al igual que el algoritmo aleatorio, este algoritmo es fácil de comprender y de programar. Sin embargo, su desempeño no siempre es del todo bueno. La página reemplazada puede ser un módulo de inicialización que fue usado hace mucho tiempo y ya no se tiene necesidad de él. Por otro lado, puede contener una variable de uso muy frecuente que fue inicializada de manera temprana y está en uso constante.

Algoritmo de reemplazo de páginas de la segunda oportunidad

Este algoritmo es una modificación del FIFO. El algoritmo hace uso del bit de referencia de la página. Cuando una página ha sido seleccionada para reemplazo, se revisa el bit de referencia. Si tiene valor de 0, se procede a reemplazar la página. Si por el contrario, el bit de referencia es 1 se le da a la página una segunda oportunidad.

Para ver el gráfico seleccione la opción "Descargar" del menú superior

Fig. 10. Algoritmo de la segunda oportunidad.

Cuando esto sucede, se le cambia el bit de referencia a 0 y se actualiza su tiempo de llegada al tiempo actual para que la página se colocada al final de la cola. De esta manera, la página espera todo un ciclo completo de páginas para ser entonces reemplazada.

Si la página tiene un uso muy frecuente, el bit de referencia se mantendría constantemente en 1 y la página no sería reemplazada. En la figura 10 se puede apreciar el funcionamiento del algoritmo.

Algoritmo de reemplazo de páginas del reloj

Modificando el algoritmo de la segunda oportunidad (que a su vez es una modificación de FIFO) obtenemos el algoritmo aumentado de la segunda oportunidad o algoritmo del reloj. Usamos la misma clasificación vista en el algoritmo de uso no tan reciente (sección 2.1.2.3.).

Este algoritmo organiza las páginas en una lista circular como se muestra en la figura 11 y se usa un apuntador (o manecilla) que señala a la página más antigua.

Para ver el gráfico seleccione la opción "Descargar" del menú superior

Fig. 11. Algoritmo de reloj.

Cuando se presenta un fallo de página, el algoritmo revisa la página a la que está apuntando la manecilla. Si el bit de referencia es 0, la página es reemplazada con la nueva y la manecilla avanza una posición. Si el bit es 1, entonces se limpia (cambia a 0) y la manecilla avanza a la siguiente página y así sucesivamente hasta encontrar una con bit 0.

Algoritmo de reemplazo de páginas "la de menor uso reciente" (LRU)

Este algoritmo es una buena aproximación al óptimo y se basa en al observación de que las páginas de uso frecuente en las últimas instrucciones se utilizan con cierta probabilidad en las siguientes. De la misma manera, es probable que las páginas que no hayan sido utilizadas durante mucho tiempo permanezcan sin uso por bastante tiempo. Implementando el algoritmo con esta base, al ocurrir un fallo de página, se elimina la página que no haya sido utilizada durante el tiempo más grande. De ahí su denominación: menor uso reciente (LRU – Least Recent Use).

A diferencia de los algoritmos anteriores, el LRU tiene un mejor rendimiento en cuanto al tiempo de aprovechamiento del CPU y del uso de la memoria. Sin embargo, el problema con este algoritmo es que su implementación es muy cara, ya que requiere de una asistencia considerable de hardware. Otro problema es el de determinar un orden para los marcos definido por el tiempo de menor uso. Para éste último hay dos posibles implementaciones:

Contadores: En el caso más sencillo, se asocia cada entrada tabla-página un campo de tiempo-de-uso y se le agrega al CPU un reloj lógico o contador. Este reloj es incrementado en cada referencia de memoria. Siempre que se hace referencia a una página, el contenido del registro del reloj es copiado al campo de tiempo-de-uso en la tabla de páginas para esa página. De esta forma, siempre se dispone del "tiempo" de la última referencia a cada página. La página que se reemplaza es la del menor valor de tiempo. Este esquema requiere de una búsqueda en toda la tabla de páginas para encontrar la página LRU, y una escritura en memoria al campo de tiempo-de-uso en la tabla de páginas por cada acceso a memoria. Los tiempos también se deben de mantener cuando las tablas de páginas son alteradas (debido a organización del CPU). Se debe considerar la posibilidad de sobrecarga en el reloj.
Pilas: Otra aproximación para implementar el reemplazo LRU es la de tener una pila con los números de páginas. Siempre que se hace referencia a una página, se quita de la pila y se pone en la parte superior. De esta manera, la parte superior de la pila es la página de uso más reciente y la de abajo es la LRU, tal como se muestra en la figura 12.

Para ver el gráfico seleccione la opción "Descargar" del menú superior

Fig. 12. Uso de pilas en el algoritmo LRU

Partes: 1, 2

Página siguiente