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 .

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.

En esta sección se describirán las características que clasifican a los sistemas operativos, básicamente se cubrirán tres clasificaciones: sistemas operativos por su estructura (visión interna), sistemas operativos por los servicios que ofrecen y, finalmente, sistemas operativos por la forma en que ofrecen sus servicios (visión externa).

Sistemas Operativos por su Estructura
Según [Alcal92], se deben observar dos tipos de requisitos cuando se construye un sistema operativo, los cuales son:
Requisitos de usuario: Sistema fácil de usar y de aprender, seguro, rápido y adecuado al uso al que se le quiere destinar.
Requisitos del software: Donde se engloban aspectos como el mantenimiento, forma de operación, restricciones de uso, eficiencia, tolerancia frente a los errores y flexibilidad.
A continuación se describen las distintas estructuras que presentan los actuales sistemas operativos para satisfacer las necesidades que de ellos se quieren obtener.

Estructura monolítica.
Es la estructura de los primeros sistemas operativos constituídos fundamentalmente por un solo programa compuesto de un conjunto de rutinas entrelazadas de tal forma que cada una puede llamar a cualquier otra (Ver Fig. 2). Las características fundamentales de este tipo de estructura son:
Construcción del programa final a base de módulos compilados separadamente que se unen a través del ligador.
Buena definición de parámetros de enlace entre las distintas rutinas existentes, que puede provocar mucho acoplamiento.
Carecen de protecciones y privilegios al entrar a rutinas que manejan diferentes aspectos de los recursos de la computadora, como memoria, disco, etc.
Generalmente están hechos a medida, por lo que son eficientes y rápidos en su ejecución y gestión, pero por lo mismo carecen de flexibilidad para soportar diferentes ambientes de trabajo o tipos de aplicaciones.

Estructura jerárquica.
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.

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).
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).

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.
Sistemas Operativos por Servicios
Esta clasificación es la más comúnmente usada y conocida desde el punto de vista del usuario final. Esta clasificación se comprende fácilmente con el cuadro sinóptico que a continuación se muestra en la Fig. 6.

Monousuarios
Los sistemas operativos monousuarios son aquéllos que soportan a un usuario a la vez, sin importar el número de procesadores que tenga la computadora o el número de procesos o tareas que el usuario pueda ejecutar en un mismo instante de tiempo. Las computadoras personales típicamente se han clasificado en este renglón.

Multiusuarios
Los sistemas operativos multiusuarios son capaces de dar servicio a más de un usuario a la vez, ya sea por medio de varias terminales conectadas a la computadora o por medio de sesiones remotas en una red de comunicaciones. No importa el número de procesadores en la máquina ni el número de procesos que cada usuario puede ejecutar simultáneamente.

Monotareas
Los sistemas monotarea son aquellos que sólo permiten una tarea a la vez por usuario. Puede darse el caso de un sistema multiusuario y monotarea, en el cual se admiten varios usuarios al mismo tiempo pero cada uno de ellos puede estar haciendo solo una tarea a la vez.

Multitareas
Un sistema operativo multitarea es aquél que le permite al usuario estar realizando varias labores al mismo tiempo. Por ejemplo, puede estar editando el código fuente de un programa durante su depuración mientras compila otro programa, a la vez que está recibiendo correo electrónico en un proceso en background. Es común encontrar en ellos interfaces gráficas orientadas al uso de menús y el ratón, lo cual permite un rápido intercambio entre las tareas para el usuario, mejorando su productividad.

Uniproceso
Un sistema operativo uniproceso es aquél que es capaz de manejar solamente un procesador de la computadora, de manera que si la computadora tuviese más de uno le sería inútil. El ejemplo más típico de este tipo de sistemas es el DOS y MacOS.

Multiproceso
Un sistema operativo multiproceso se refiere al número de procesadores del sistema, que es más de uno y éste es capaz de usarlos todos para distribuir su carga de trabajo. Generalmente estos sistemas trabajan de dos formas: simétrica o asimétricamente. Cuando se trabaja de manera asimétrica, el sistema operativo selecciona a uno de los procesadores el cual jugará el papel de procesador maestro y servirá como pivote para distribuir la carga a los demás procesadores, que reciben el nombre de esclavos. Cuando se trabaja de manera simétrica, los procesos o partes de ellos (threads) son enviados indistintamente a cualesquira de los procesadores disponibles, teniendo, teóricamente, una mejor distribución y equilibrio en la carga de trabajo bajo este esquema.

Se dice que un thread es la parte activa en memoria y corriendo de un proceso, lo cual puede consistir de un área de memoria, un conjunto de registros con valores específicos, la pila y otros valores de contexto. Us aspecto importante a considerar en estos sistemas es la forma de crear aplicaciones para aprovechar los varios procesadores. Existen aplicaciones que fueron hechas para correr en sistemas monoproceso que no toman ninguna ventaja a menos que el sistema operativo o el compilador detecte secciones de código paralelizable, los cuales son ejecutados al mismo tiempo en procesadores diferentes. Por otro lado, el programador puede modificar sus algoritmos y aprovechar por sí mismo esta facilidad, pero esta última opción las más de las veces es costosa en horas hombre y muy tediosa, obligando al programador a ocupar tanto o más tiempo a la paralelización que a elaborar el algoritmo inicial.

Sistemas Operativos por la Forma de Ofrecer sus Servicios
Esta clasificación también se refiere a una visión externa, que en este caso se refiere a la del usuario, el cómo accesa los servicios. Bajo esta clasificación se pueden detectar dos tipos principales: sistemas operativos de red y sistemas operativos distribuídos.

Sistemas Operativos de Red
Los sistemas operativos de red se definen como aquellos que tiene la capacidad de interactuar con sistemas operativos en otras computadoras por medio de un medio de transmisión con el objeto de intercambiar información, transferir archivos, ejecutar comandos remotos y un sin fin de otras actividades. El punto crucial de estos sistemas es que el usuario debe saber la sintaxis de un cinjunto de comandos o llamadas al sistema para ejecutar estas operaciones, además de la ubicación de los recursos que desee accesar. Por ejemplo, si un usuario en la computadora hidalgo necesita el archivo matriz.pas que se localiza en el directorio /software/codigo en la computadora morelos bajo el sistema operativo UNIX, dicho usuario podría copiarlo a través de la red con los comandos siguientes: hidalgo% hidalgo% rcp morelos:/software/codigo/matriz.pas . hidalgo%. En este caso, el comando rcp que significa "remote copy" trae el archivo indicado de la computadora morelos y lo coloca en el directorio donde se ejecutó el mencionado comando. Lo importante es hacer ver que el usuario puede accesar y compartir muchos recursos.

Sistemas Operativos Distribuídos
Los sistemas operativos distribuídos abarcan los servicios de los de red, logrando integrar recursos ( impresoras, unidades de respaldo, memoria, procesos, unidades centrales de proceso ) en una sola máquina virtual que el usuario accesa en forma transparente. Es decir, ahora el usuario ya no necesita saber la ubicación de los recursos, sino que los conoce por nombre y simplementa los usa como si todos ellos fuesen locales a su lugar de trabajo habitual. Todo lo anterior es el marco teórico de lo que se desearía tener como sistema operativo distribuído, pero en la realidad no se ha conseguido crear uno del todo, por la complejidad que suponen: distribuír los procesos en las varias unidades de procesamiento, reintegrar sub-resultados, resolver problemas de concurrencia y paralelismo, recuperarse de fallas de algunos recursos distribuídos y consolidar la protección y seguridad entre los diferentes componentes del sistema y los usuarios. Los avances tecnológicos en las redes de área local y la creación de microprocesadores de 32 y 64 bits lograron que computadoras mas o menos baratas tuvieran el suficiente poder en forma autónoma para desafiar en cierto grado a los mainframes, y a la vez se dio la posibilidad de intercomunicarlas, sugiriendo la oportunidad de partir procesos muy pesados en cálculo en unidades más pequeñas y distribuirlas en los varios microprocesadores para luego reunir los sub-resultados, creando así una máquina virtual en la red que exceda en poder a un mainframe. El sistema integrador de los microprocesadores que hacer ver a las varias memorias, procesadores, y todos los demás recursos como una sola entidad en forma transparente se le llama sistema operativo distribuído. Las razones para crear o adoptar sistemas distribuídos se dan por dos razones principales: por necesidad ( debido a que los problemas a resolver son inherentemente distribuídos ) o porque se desea tener más confiabilidad y disponibilidad de recursos. En el primer caso tenemos, por ejemplo, el control de los cajeros automáticos en diferentes estados de la república. Ahí no es posible ni eficiente mantener un control centralizado, es más, no existe capacidad de cómputo y de entrada/salida para dar servicio a los millones de operaciones por minuto. En el segundo caso, supóngase que se tienen en una gran empresa varios grupos de trabajo, cada uno necesita almacenar grandes cantidades de información en disco duro con una alta confiabilidad y disponibilidad. La solución puede ser que para cada grupo de trabajo se asigne una partición de disco duro en servidores diferentes, de manera que si uno de los servidores falla, no se deje dar el servicio a todos, sino sólo a unos cuantos y, más aún, se podría tener un sistema con discos en espejo ( mirror ) a través de la red,de manera que si un servidor se cae, el servidor en espejo continúa trabajando y el usuario ni cuenta se da de estas fallas, es decir, obtiene acceso a recursos en forma transparente.

Ventajas de los Sistemas Distribuídos
En general, los sistemas distribuídos (no solamente los sistemas operativos) exhiben algunas ventajas sobre los sistemas centralizados que se describen enseguida.

• Economía: El cociente precio/desempeño de la suma del poder de los procesadores separados contra el poder de uno solo centralizado es mejor cuando están distribuídos.
• Velocidad: Relacionado con el punto anterior, la velocidad sumada es muy superior.
• Confiabilidad: Si una sola máquina falla, el sistema total sigue funcionando.
• Crecimiento: El poder total del sistema puede irse incrementando al añadir pequeños sistemas, lo cual es mucho más difícil en un sistema centralizado y caro.
• Distribución: Algunas aplicaciones requieren de por sí una distribución física.

Por otro lado, los sistemas distribuídos también exhiben algunas ventajas sobre sistemas aislados. Estas ventajas son:

• Compartir datos: Un sistema distribuído permite compartir datos más fácilmente que los sistemas aislados, que tendrian que duplicarlos en cada nodo para lograrlo.
• Compartir dispositivos: Un sistema distribuído permite accesar dispositivos desde cualquier nodo en forma transparente, lo cual es imposible con los sistemas aislados. El sistema distribuído logra un efecto sinergético.
• Comunicaciones: La comunicación persona a persona es factible en los sistemas distribuídos, en los sistemas aislados no. _ Flexibilidad: La distribución de las cargas de trabajo es factible en el sistema distribuídos, se puede incrementar el poder de cómputo.

Desventajas de los Sistemas Distribuídos
Así como los sistemas distribuídos exhiben grandes ventajas, también se pueden identificar algunas desventajas, algunas de ellas tan serias que han frenado la producción comercial de sistemas operativos en la actualidad. El problema más importante en la creación de sistemas distribuídos es el software: los problemas de compartición de datos y recursos es tan complejo que los mecanismos de solución generan mucha sobrecarga al sistema haciéndolo ineficiente. El checar, por ejemplo, quiénes tienen acceso a algunos recursos y quiénes no, el aplicar los mecanismos de protección y registro de permisos consume demasiados recursos. En general, las soluciones presentes para estos problemas están aún en pañales.

Otros problemas de los sistemas operativos distribuídos surgen debido a la concurrencia y al paralelismo. Tradicionalmente las aplicaiones son creadas para computadoras que ejecutan secuencialmente, de manera que el identificar secciones de código `paralelizable' es un trabajo ardúo, pero necesario para dividir un proceso grande en sub-procesos y enviarlos a diferentes unidades de procesamiento para lograr la distribución. Con la concurrencia se deben implantar mecanismos para evitar las condiciones de competencia, las postergaciones indefinidas, el ocupar un recurso y estar esperando otro, las condiciones de espera circulares y , finalmente, los "abrazos mortales" (deadlocks). Estos problemas de por sí se presentan en los sistemas operativos multiusuarios o multitareas, y su tratamiento en los sistemas distribuídos es aún más complejo, y por lo tanto, necesitará de algoritmos más complejos con la inherente sobrecarga esperada.

Por otro lado, en el tema de sistemas distribuídos existen varios conceptos importantes referentes al hadware que no se ven en este trabajo: multicomputadoras, multiprocesadores, sistemas acoplados débil y fuertemente, etc. En páginas 366 - 376 puede encontrarse material relacionado a estos conceptos.

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 mabnera 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 refiere 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 comunmente 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 arcivo 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 comunies 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 nla 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 llmada 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 distribuídos' 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 compartició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 Gygabytes ) 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 distribuídas, y hacia la estandarización que, muchas veces, es `de facto'.

En esta sección se describirán las técnicas más usuales en el manejo de memoria, revisando los conceptos relevantes. Se abarcarán los esquemas de manejo simple de memoria real, la multiprogramación en memoria real con sus variantes, el concepto de `overlays', la multiprogramación con intercambio y los esquemas de manejo de memoria virtual.

Panorama general
Un vistazo al material que se va a cubrir en esta sección se muestra en la figura 4.1. Es una gráfica en donde se especifican, en términos generales, los conceptos más importantes en cuanto a las técnicas empleadas en el manejo de memoria.

Manejo de memoria en sistemas monousuario sin intercambio
Este esquema es aún muy frecuente en México y se usa principalmente en sistemas monousuario y monotarea, como son las computadoras personales con DOS. Bajo este esquema, la memoria real es tomada para almacenar el programa que se esté ejecutando en un momento dado, con la visible desventaja de que si se está limitado a la cantidad de RAM disponible únicamente. La organización física bajo este esquema es muy simple: El sistema operativo se ubica en las localidades superiores o inferiores de la memoria, seguido por algunos manejadores de dispositivos ( `drivers' ). Esto deja un espacio contiguo de memoria disponible que es tomado por los programas del usuario, dejando generalmente la ubicación de la pila (` stack' ) al último, con el objetivo de que ésta pueda crecer hasta el máximo posible. Estas diferentes opciones se pueden ver en la figura 4.2. Como es obvio, bajo estos esquemas no se requieren algoritmos sofisticados para asignar la memoria a los diferentes procesos, ya que éstos son ejecutados secuencialmente conforme van terminando.

Multiprogramación en memoria real
En los 60's, las empresas e instituciones que habían invertido grandes sumas en la compra de equipo de cómputo se dieron cuenta rápidamente que los sistemas en lote invertían una gran cantidad de tiempo en operaciones de entrada y salida, donde la intervención de la unidad central de procesamiento era prácticamente nula, y se comenzaron a preguntar cómo hacer que se mantuviera más tiempo ocupada. Fue así como nació el concepto de multiprogramación, el cual consiste en la idea de poner en la memoria física más de un proceso al mismo tiempo, de manera que si el que se está ejecutando en este momento entraba en un periodo de entrada/salida, se podia tomar otro proceso para que usara la unidad central de procesamiento. De esta forma, la memoria fisica se dividía en secciones de tamaño suficiente para contener a varios programas.

De esta manera, si un sistema gastaba en promedio 60% de su tiempo en entrada/salida por proceso, se podía aprovechar más el CPU. Anterior a esto, el CPU se mantenía ese mismo porcentaje ocioso; con la nueva técnica, el tiempo promedio ocioso disminuye de la siguiente forma. Llámese al tiempo promedio que el CPU está ocupado `grado de multiprogramación'. Si el sistema tuviese un solo proceso siempre, y éste gastara 60% en entrada/salida, el grado de multiprogramación sería 1 - 60% = 40% = 0.4. Con dos procesos, para que el CPU esté ocioso se necesita que ambos procesos necesiten estar haciendo entrada/salida, es decir, suponiendo que son independientes, la probabilidad de que ambos estén en entrada/salida es el producto de sus probabilidades, es decir, 0.6x0.6 = 0.36. Ahora, el grado de multiprogramación es 1 - (probabilidad de que ambos procesos estén haciendo entrada/salida) = 1 - 0.36 = 0.64.

Como se ve, el sistema mejora su uso de CPU en un 24% al aumentar de uno a dos procesos. Para tres procesos el grado de multiprogramación es 1 - (0.6) 3 = 0.784, es decir, el sistema está ocupado el 78.4% del tiempo. La fórmula del grado de multiprogramación, aunque es muy idealista, pudo servir de guía para planear un posible crecimiento con la compra de memoria real, es decir, para obtener el punto en que la adición de procesos a RAM ya no incrementa el uso de CPU.

Dentro del esquema de multiprogramación en memoria real surgieron dos problemas interesantes: la protección y la relocalización.

El problema de la relocalización
Este problema no es exclusivo de la multiprogramación en memoria real, sino que se presentó aquí pero se sigue presentando en los esquemas de memoria virtual también. Este problema consiste en que los programas que necesitan cargarse a memoria real ya están compilados y ligados, de manera que internamente contienen una serie de referencias a direcciones de instrucciones, rutinas y procedimientos que ya no son válidas en el espacio de direcciones de memoria real de la sección en la que se carga el programa. Esto es, cuando se compiló el programa se definieron o resolvieron las direcciones de memoria de acuerdo a la sección de ese momento, pero si el programa se carga en otro dia en una sección diferente, las direcciones reales ya no coinciden. En este caso, el manejador de memoria puede solucionar el problema de dos maneras: de manera `estática' o de manera `dinámica'. La solución `estática' consiste en que todas las direcciones del programa se vuelvan a recalcular al momento en que el programa se carga a memoria, esto es, prácticamente se vuelve a recompilar el programa. La solución `dinámica' consiste en tener un registro que guarde la dirección base de la sección que va a contener al programa. Cada vez que el programa haga una referencia a una dirección de memoria, se le suma el registro base para encontrar la dirección real. Por ejemplo, suponga que el programa es cargado en una sección que comienza en la dirección 100. El programa hará referencias a las direcciones 50,52,54. Pero el contenido de esas direcciones no es el deseado, sino las direcciones 150, 152 y 154, ya que ahí comienza el programa. La suma de 100 + 50, ...,etcétera se hacen al tiempo de ejecución. La primera solución vale más la pena que la segunda si el programa contiene ciclos y es largo, ya que consumirá menos tiempo en la resolución inicial que la segunda solución en las resoluciones en línea.

El problema de la protección
Este problema se refiere a que, una vez que un programa ha sido caragado a memoria en algún segmento en particular, nada le impide al programador que intente direccionar ( por error o deliberadamente ) localidades de memoria menores que el límite inferior de su programa o superiores a la dirección mayor; es decir, quiere referenciar localidades fuera de su espacio de direcciones. Obviamente, este es un problema de protección, ya que no es legal leer o escribir en áreas de otros programas.

La solución a este problema también puede ser el uso de un registro base y un registro límite. El registro base contiene la dirección del comienzo de la sección que contiene al programa, mientras que el límite contiene la dirección donde termina. Cada vez que el programa hace una referencia a memoria se checa si cae en el rango de los registros y si no es así se envía un mensaje de error y se aborta el programa.

Particiones fijas o particiones variables
En el esquema de la multiprogramación en memroia real se manejan dos alternativas para asignarle a cada programa su partición correspondiente: particiones de tamaño fijo o particiones de tamaño variable. La alternativa más simple son las particiones fijas. Dichas particiones se crean cuando se enciende el equipo y permanecerán con los tamaños iniciales hasta que el equipo se apague. Es una alternativa muy vieja, quien hacía la división de particiones era el operador analizando los tamaños estimados de los trabajos de todo el día. Por ejemplo, si el sistema tenía 512 kilobytes de RAM, podia asignar 64 k para el sistema operativo, una partición más de 64 k, otra de 128k y una mayor de 256 k. Esto era muy simple, pero inflexible, ya que si surgían trabajos urgentes, por ejemplo, de 400k, tenían que esperar a otro día o reparticionar, inicializando el equipo desde cero. La otra alternativa, que surgió después y como necesidad de mejorar la alternativa anterior, era crear particiones contiguas de tamaño variable. Para esto, el sistema tenía que mantener ya una estructura de datos suficiente para saber en dónde habían huecos disponibles de RAM y de dónde a dónde habían particiones ocupadas por programas en ejecución. Así, cuando un programa requería ser cargado a RAM, el sistema analizaba los huecos para saber si había alguno de tamaño suficiente para el programa que queria entrar, si era así, le asignaba el espacio. Si no, intentaba relocalizar los programas existentes con el propósito de hacer contiguo todo el espacio ocupado, así como todo el espacio libre y así obtener un hueco de tamaño suficiente. Si aún así el programa no cabía, entonces lo bloqueaba y tomaba otro. El proceso con el cual se juntan los huecos o los espacios ocupados se le llama `compactación'. El lector se habrá dado cuenta ya de que surgen varios problemas con los esquemas de particiones fijas y particiones variables: ø En base a qué criterio se elige el mejor tamaño de partición para un programa ? Por ejemplo, si el sistema tiene dos huecos, uno de 18k y otro de 24 k para un proceso que desea 20 k, ø Cual se le asigna ? Existen varios algoritmos para darle respuesta a la pregunta anterior, los cuales se ennumeran y describen enseguida.

• Primer Ajuste: Se asigna el primer hueco que sea mayor al tamaño deseado.
• Mejor Ajuste: Se asigna el hueco cuyo tamaño exceda en la menor cantidad al tamaño deseado. Requiere de una búsqueda exhaustiva.
• Peor Ajuste: Se asigna el hueco cuyo tamaño exceda en la mayor cantidad al tamaño deseado. Requiere también de una búsqueda exhaustiva.
• El Siguiente Ajuste: Es igual que el `primer ajuste' con la diferencia que se deja un apuntador al lugar en donde se asignó el último hueco para realizar la siguiente búsqueda a partir de él.
• Ajuste Rápido: Se mantienen listas ligadas separadas de acuerdo a los tamaños de los huecos, para así buscarle a los procesos un hueco más rápido en la cola correspondiente.

Otro problema que se vislumbra desde aquí es que, una vez asignado un hueco, por ejemplo, con "el peor ajuste", puede ser que el proceso requiriera 12 kilobytes y que el hueco asignado fuera de 64 kilobytes, por lo cual el proceso va a desperdiciar una gran cantidad de memoria dentro de su partición, lo cual se le llama `fragmentación interna'.

Por otro lado, conforme el sistema va avanzando en el día, finalizando procesos y comenzando otros, la memoria se va configurando como una secuencia contigua de huecos y de lugares asignados, provocando que existan huecos, por ejemplo, de 12 k, 28k y 30 k, que sumados dan 70k, pero que si en ese momento llega un proceso pidiéndolos, no se le pueden asignar ya que no son localidades contiguas de memoria ( a menos que se realice la compactación ). Al hecho de que aparezcan huecos no contiguos de memoria se le llama `fragmentación externa'.

De cualquier manera, la multiprogramación fue un avance significativo para el mejor aprovechamiento de la unidad central de procesamiento y de la memoria misma, así como dio pie para que surgieran los problemas de asignación de memoria, protección y relocalización, entre otros.

Los overlays
Una vez que surgió la multiprogramación, los usuarios comenzaron a explorar la forma de ejecutar grandes cantidades de código en áreas de memoria muy pequeñas, auxiliados por algunas llamadas al sistema operativo. Es así como nacen los `overlays'.

Esta técnica consiste en que el programador divide lógicamente un programa muy grande en secciones que puedan almacenarse el las particiones de RAM. Al final de cada sección del programa ( o en otros lugares necesarios ) el programador insertaba una o varias llamadas al sistema con el fin de descargar la sección presente de RAM y cargar otra, que en ese momento residía en disco duro u otro medio de almacenamiento secundario. Aunque esta técnica era eficaz ( porque resolvía el problema ) no era eficiente ( ya que no lo resolvía de la mejor manera ). Esta solución requería que el programador tuviera un conocimiento muy profundo del equipo de cómputo y de las llamadas al sistema operativo. Otra desventaja era la portabilidad de un sistema a otro: las llamadas cambiaban, los tamaños de particiones también. Resumiendo, con esta técnica se podían ejecutar programas más grandes que las particiones de RAM, donde la división del código corría a cuenta del programador y el control a cuenta del sistema operativo.

Multiprogramación en memoria virtual
La necesidad cada vez más imperiosa de ejecutar programas grandes y el crecimiento en poder de las unidades centrales de procesamiento empujaron a los diseñadores de los sistemas operativos a implantar un mecanismo para ejecutar automáticamente programas más grandes que la memoria real disponible, esto es, de ofrecer `memoria virtual'.

La memoria virtual se llama así porque el programador ve una cantidad de memoria mucho mayor que la real, y en realidad se trata de la suma de la memoria de almacenamiento primario y una cantidad determinada de almacenamiento secundario. El sistema operativo, en su módulo de manejo de memoria, se encarga de intercambiar programas enteros, segmentos o páginas entre la memoria real y el medio de almacenamiento secundario. Si lo que se intercambia son procesos enteros, se habla entonces de multiprogramación en memoria real, pero si lo que se intercambian son segmentos o páginas, se puede hablar de multiprogramación con memoria virtual.

La memoria virtual se apoya en varias técnicas interesantes para lograr su objetivo. Una de las teorias más fuertes es la del `conjunto de trabajo', la cual se refiere a que un programa o proceso no está usando todo su espacio de direcciones en todo momento, sino que existen un conjunto de localidades activas que conforman el `conjunto de trabajo'. Si se logra que las páginas o segmentos que contienen al conjunto de trabajo estén siempre en RAM, entonces el programa se desempeñará muy bien.

Otro factor importante es si los programas exhiben un fenómeno llamado `localidad', lo cual quiere decir que algunos programas tienden a usar mucho las instrucciones que están cercanas a la localidad de la instrucción que se está ejecutando actualmente.

Paginación pura
La paginación pura en el majejo de memoria consiste en que el sistema operativo divide dinámicamente los programas en unidades de tamaño fijo ( generalmente múltiplos de 1 kilobyte ) los cuales va a manipular de RAM a disco y viceversa. Al proceso de intercambiar páginas, segmentos o programas completos entre RAM y disco se le conoce como `intercambio' o `swapping'. En la paginación, se debe cuidar el tamño de las páginas, ya que si éstas son muy pequeñas el control por parte del sistema operativo para saber cuáles están en RAM y cuales en disco, sus direcciones reales, etc; crece y provoca mucha `sobrecarga' (overhead). Por otro lado, si las páginas son muy grandes, el overhead disminuye pero entonces puede ocurrir que se desperdicie memoria en procesos pequeños. Debe haber un equilibrio.

Uno de los aspectos más importantes de la paginación, asi como de cualquier esquema de memoria virtual, es la forma de traducir una dirección virtual a dirección real. Para explicarlo, obsérvese la figura

Como se observa, una dirección virtual `v' = ( b,d) está formada por un número de página virtual `b' y un desplazamiento `d'. Por ejemplo, si el sistema ofrece un espacio de direcciones virtuales de 64 kilobytes, con páginas de 4 kilobytes y la RAM sólo es de 32 kilobytes, entonces tenemos 16 páginas virtuales y 8 reales. La tabla de direcciones virtuales contiene 16 entradas, una por cada página virtual. En cada entrada, o registro de la tabla de direcciones virtuales se almacenan varios datos: si la página está en disco o en memoria, quién es el dueño de la página, si la página ha sido modificada o es de lectura nada mas, etc. Pero el dato que nos interesa ahora es el número de página real que le corresponde a la página virtual. Obviamente, de las 16 virtuales, sólo ocho tendrán un valor de control que dice que la página está cargada en RAM, así como la dirección real de la página, denotada en la figura 4.3 como b' . Por ejemplo, supóngase que para la página virtual número 14 la tabla dice que, efectivamente está cargada y es la página real 2 ( dirección de memoria 8192 ). Una vez encontrada la página real, se le suma el desplazamiento, que es la dirección que deseamos dentro de la página buscada ( b' + d ).

La tabla de direcciones virtuales a veces está ubicada en la misma meoria RAM, por lo cual se necesita saber en qué dirección comienza, en este caso, existe un registro con la dirección base denotada por la letra `a' en la figura 4.3.

Cuando se está buscando una página cualquiera y ésta no está cargada, surge lo que se llama un `fallo de página' (page fault ). Esto es caro para el manejador de memoria, ya que tiene que realizar una serie de pasos extra para poder resolver la dirección deseada y darle su contenido a quien lo pide. Primero, se detecta que la página no está presente y entonces se busca en la tabla la dirección de esta página en disco. Una vez localizada en disco se intenta cargar en alguna página libre de RAM. Si no hay páginas libres se tiene que escoger alguna para enviarla hacia el disco. Una vez escogida y enviada a disco, se marca su valor de control en la tabla de direcciones virtuales para indicar que ya no está en RAM, mientras que la página deseada se carga en RAM y se marca su valor para indicar que ahora ya está en RAM. Todo este procedimiento es caro, ya que se sabe que los accesos a disco duro son del orden de decenas de veces más lentos que en RAM. En el ejemplo anterior se mencionó que cuando se necesita descargar una página de RAM hacia disco se debe de hacer una elección. Para realizar esta elección existen varios algoritmos, los cuales se describen enseguida. _ La primera en entrar, primera en salir: Se escoge la página que haya entrado primero y esté cargada en RAM. Se necesita que en los valores de control se guarde un dato de tiempo. No es eficiente porque no aprovecha ninguna característica de ningún sistema. Es justa e imparcial. _ La no usada recientemente: Se escoge la página que no haya sido usada (referenciada) en el ciclo anterior. Pretende aprovechar el hecho de la localidad en el conjunto de trabajo.

• La usada menos recientemente: Es parecida a la anterior, pero escoge la página que se usó hace más tiempo, pretendiendo que como ya tiene mucho sin usarse es muy probable que siga sin usarse en los próximos ciclos. Necesita de una búsqueda exhaustiva.
• La no usada frecuentemente: Este algoritmo toma en cuenta no tanto el tiempo, sino el número de referencias. En este caso cualquier página que se use muy poco, menos veces que alguna otra.
• La menos frecuentemente usada: Es parecida a la anterior, pero aquí se busca en forma exhaustiva aquella página que se ha usado menos que todas las demás.
• En forma aleatoria: Elige cualquier página sin aprovechar nada. Es justa e imparcial, pero ineficiente.

Otro dato interesante de la paginación es que ya no se requiere que los programas estén ubicados en zonas de memoria adyacente, ya que las páginas pueden estar ubicadas en cualquier lugar de la memoria RAM.

Segmentación pura
La segmentación se aprovecha del hecho de que los programas se dividen en partes lógicas, como son las partes de datos, de código y de pila (stack). La segmentación asigna particiones de memoria a cada segmento de un programa y busca como objetivos el hacer fácil el compartir segmentos ( por ejemplo librerías compartidas ) y el intercambio entre memoria y los medios de almacenamiento secundario.

Por ejemplo, en la versión de UNIX SunOS 3.5, no existían librerías compartidas para algunas herramientas, por ejemplo, para los editores de texto orientados al ratón y menús. Cada vez que un usuario invocaba a un editor, se tenía que reservar 1 megabyte de memoria. Como los editores son una herramienta muy solicitada y frecuentemente usada, se dividió en segmentos para le versión 4.x ( que a su vez se dividen en páginas ), pero lo importante es que la mayor parte del editor es común para todos los usuarios, de manera que la primera vez que cualquier usuario lo invocaba, se reservaba un megabyte de memoria como antes, pero para el segundo, tercero y resto de usuarios, cada editor extra sólo consumía 20 kilobytes de memoria. El ahorro es impresionante. Obsérvese que en la segmentación pura las particiones de memoria son de tamaño variable, en contraste con páginas de tamaño fijo en la paginación pura. También se puede decir que la segmentación pura tiene una granularidad menor que la paginación por el tamanó de segmentos versus tamaño de páginas. Nuevamente, para comprender mejor la segmentación, se debe dar un repaso a la forma en que las direcciones virtuales son traducidas a direcciones reales, y para ellos se usa la figura 4.4. Prácticamente la traducción es igual que la llevada a cabo en la paginación pura, tomando en consideracióñ que el tamaño de los bloques a controlar por la tabla de traducción son variables, por lo cual, cada entrada en dicha tabla debe contener la longitud de cada segmento a controlar. Otra vez se cuenta con un registro base que contiene la dirección del comienzo de la tabla de segmentos. La dirección virtual se compone de un número de segmento (s) y un desplazamiento ( d ) para ubicar un byte (o palabra ) dentro de dicho segmento. Es importante que el desplazamiento no sea mayor que el tamaño del segmento, lo cual se controla simplemente checando que ese valor sea mayor que la dirección del inicio del segmento y menor que el inicio sumado al tamaño.

Una ves dada una dirección virtual v=( s,d ), se realiza la operación b + s para hallar el registro (o entrada de la tabla de segmentos ) que contiene la dirección de inicio del segmento en la memoria real, denotado por s'. Ya conociendo la dirección de inicio en memoria real s' sólo resta encontrar el byte o palabra deseada, lo cual se hace sumándole a s' el valor del desplazamiento, de modo que la dirección real ® r = s'+ d.

Cada entrada en la tabla de segmentos tiene un formato similar al mostrado en la figura 4.5. Se tienen campos que indican la longitud, los permisos, la presencia o ausencia y dirección de inicio en memoria real del segmento.

Según amplios experimentos [Deitel93] sugieren que un tamaño de páginas de 1024 bytes generalmente ofrece un desempeño muy aceptable. Intuitivamente parecería que el tener páginas del mayor tamaño posible haría que el desempeño fuera óptimo pero no es así, a menos que la página fuera del tamaño del proceso total. No es así con tamaños grandes de página menores que el proceso, ya que cuando se trae a memoria principal una página por motivo de un solo byte o palabra, se están trayendo muchísimos más bytes de los deseados. La dependencia entre el número de fallas respecto al tamaño de las páginas se muestra en la figura 4.6.

Un hecho notable en los sistemas que manejan paginación es que cuando el proceso comienza a ejecutarse ocurren un gran número de fallos de página, porque es cuando está referenciando muchas direcciones nuevas por vez primera, después el sistema se estabiliza, conforme el número de marcos asignados se acerca al tamaño del conjunto de trabajo.

El la figura 4.7 se muestra la relación entre el tiempo promedio entre fallas de página y el número de marcos de página asignados a un proceso. Allí se ve que el tiempo entre fallas decrece conforme se le asignan más páginas al proceso. La gráfica se curva en un punto, el cual corresponde a que el proceso tiene un número de páginas asignado igual al que necesita para almacenar su conjunto de trabajo. Después de eso, el asignarle a un proceso más páginas que las de su conjunto de trabajo ya no conviene, ya que el tiempo promedio entre fallas permanece sin mucha mejora. Un aspecto curioso de aumentar el número de páginas a un proceso cuando el algoritmo de selección de páginas candidatas a irse a disco es la primera en entrar primera en salir es la llamada `anomalía FIFO' a `anomalía de Belady'. Belady encontró ejemplos en los que un sistema con un número de páginas igual a tres tenía menos fallas de páginas que un sistema con cuatro páginas. El ejemplo descrito en [Tanxx] es injusto. Si se mira con cuidado, obviamente si se compara un sistema con 10 páginas contra otro de 5, ya de inicio el primer sistema tendrá 5 fallos de página más que el de 5, porque se necesitan diez fallos para cargarlo. A esto debería llamársele `anomalía de Belady con corrección.

Sistemas combinados
La paginación y la segmentación puras son métodos de manejo de memoria bastante efectivos, aunque la mayoría de los sistemas operativos modernos implantan esquemas combinados, es decir, combinan la paginación y la segmentación. La idea de combinar estos esquemas se debe a que de esta forma se aprovechan los conceptos de la división lógica de los programas (segmentos) con la granularidad de las páginas. De esta forma, un proceso estará repartido en la memoria real en pequeñas unidades (páginas) cuya liga son los segmentos. También es factible así el compartir segmentos a medida que las partes necesitadas de los mismos se van referenciando (páginas). Para comprender este esquema, nuevamente se verá cómo se traduce una dirección virtual en una localidad de memoria real. Para la paginación y segmentacíon puras se puede decir que el direccionamiento es `bidimensional' porque se necesitan dos valores para hallar la dirección real. Para el caso combinado, se puede decir que se tiene un direccionamiento `tridimensional'. En la figura 4.8 [ Deitel93] se muestran las partes relevantes para lograr la traducción de direcciones. El sistema debe contar con una tabla de procesos (TP). Por cada renglón de esa tabla se tiene un número de proceso y una dirección a una tabla de segmentos. Es decir, cada proceso tiene una tabla de segmentos. Cuando un proceso hace alguna referencia a memoria, se consulta TP para encontrar la tabla de segmentos de ese proceso. En cada tabla de segmentos de proceso (TSP) se tienen los números de los segmentos que componen a ese proceso. Por cada segmento se tiene una dirección a una tabla de páginas. Cada tabla de páginas tiene las direcciones de las páginas que componen a un solo segmento. Por ejemplo, el segmento `A' puede estar formado por las páginas reales `a','b','c','p' y `x'. El segmento `B' puede estar compuesto de las páginas `f','g','j','w' y `z'.

Para traducir una dirección virtual v=(s,p,d) donde `s' es el segmento, `p' es la página y `d' el desplazamiento en la página se hace lo siguiente. Primero se ubica de qué proceso es el segmento y se localiza la tabla de segmentos de ese proceso en la TP. Con `s' como índice se encuentra un renglón ( registro) en la tabla de segmentos de ese proceso y en ese renglón está la dirección de la tabla de páginas que componen al segmento. Una vez en la tabla de páginas se usa el valor `p' como índice para encontrar la dirección de la página en memoria real. Una vez en esa dirección de memoria real se encuentra el byte (o palabra) requerido por medio del valor de `d'.

Ahora, en este esquema pueden haber dos tipos de fallos: por fallo de página y por fallo de segmento. Cuando se hace referencia a una dirección y el segmento que la contiene no está en RAM ( aunque sea parcialmente ), se provoca un fallo por falta de segmento y lo que se hace es traerlo del medio de almacenamiento secundario y crearle una tabla de páginas. Una vez caragado el segmento se necesita localizar la página correspondiente, pero ésta no existe en RAM, por lo cual se provoca un fallo de página y se carga de disco y finalmente se puede ya traer la dirección deseada por medio del desplazamiento de la dirección virtual.

La eficiencia de la traducción de direcciones tanto en paginación pura, segmentación pura y esquemas combinados se mejora usando memorias asociativas para las tablas de páginas y segmentos, así como memorias cache para guardar los mapeos más solicitados.

Otro aspecto importante es la estrategia para cargar páginas ( o segmentos ) a la memoria RAM. Se usan más comunmente dos estrategias: cargado de páginas por demanda y cargado de páginas anticipada. La estrategia de caragdo por demanda consiste en que las páginas solamente son llevadas a RAM si fueron solicitadas, es decir, si se hizo referencia a una dirección que cae dentro de ellas. La carga anticipada consiste en tratar de adivinar qué páginas serán solicitadas en el futuro inmediato y cargarlas de antemano, para que cuando se pidan ya no ocurran fallos de página. Ese `adivinar' puede ser que se aproveche el fenómeno de localidad y que las páginas que se cargan por anticipado sean aquellas que contienen direcciones contiguas a la dirección que se acaba de refenciar. De hecho, el sistema operativo VMS usa un esquema combinado para cargar páginas: cuando se hace referencia a una dirección cuya página no está en RAM, se provoca un fallo de página y se carga esa página junto con algunas páginas adyacentes. En este caso la página solicitada se cargó por demanda y las adyacentes se cargaron por anticipación.

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 nohay 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, 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'.

Problemas de Concurrencia
En los sistemas de tiempo compartido (aquellos con varios usuarios, procesos, tareas, trabajos que reparten el uso de CPU entre estos) se presentan muchos problemas debido a que los procesos compiten por los recursos del sistema. Imagine que un proceso está escribiendo en la unidad de cinta y se le termina su turno de ejecución e inmediatamente después el proceso elegido para ejecutarse comienza a escribir sobre la misma cinta. El resultado es una cinta cuyo contenido es un desastre de datos mezclados. Así como la cinta, existen una multitud de recursos cuyo acceso debe der controlado para evitar los problemas de la concurrencia.

El sistema operativo debe ofrecer mecanismos para sincronizar la ejecución de procesos: semáforos, envío de mensajes, 'pipes', etc. Los semáforos son rutinas de software (que en su nivel más interno se auxilian del hardware) para lograr exclusión mutua en el uso de recursos. Para entender este y otros mecanismos es importante entender los problemas generales de concurrencia, los cuales se describen enseguida.

• Condiciones de Carrera o Competencia: La condición de carrera (race condition) ocurre cuando dos o más procesos accesan un recurso compartido sin control, de manera que el resultado combinado de este acceso depende del orden de llegada. Suponga, por ejemplo, que dos clientes de un banco realizan cada uno una operación en cajeros diferentes al mismo tiempo.
• El usuario A quiere hacer un depósito. El B un retiro. El usuario A comienza la transacción y lee su saldo que es 1000. En ese momento pierde su turno de ejecución (y su saldo queda como 1000) y el usuario B inicia el retiro: lee el saldo que es 1000, retira 200 y almacena el nuevo saldo que es 800 y termina. El turno de ejecución regresa al usuario A el cual hace su depósito de 100, quedando saldo = saldo + 100 = 1000 + 100 = 1100. Como se ve, el retiro se perdió y eso le encanta al usuario A y B, pero al banquero no le convino esta transacción. El error pudo ser al revés, quedando el saldo final en 800.
• Postergación o Aplazamiento Indefinido(a): Esto se mencionó en el apartado anterior y consiste en el hecho de que uno o varios procesos nunca reciban el suficiente tiempo de ejecución para terminar su tarea. Por ejemplo, que un proceso ocupe un recurso y lo marque como 'ocupado' y que termine sin marcarlo como 'desocupado'. Si algún otro proceso pide ese recurso, lo verá 'ocupado' y esperará indefinidamente a que se 'desocupe'.
• Condición de Espera Circular: Esto ocurre cuando dos o más procesos forman una cadena de espera que los involucra a todos. Por ejemplo, suponga que el proceso A tiene asignado el recurso 'cinta' y el proceso B tiene asignado el recurso 'disco'. En ese momento al proceso A se le ocurre pedir el recurso 'disco' y al proceso B el recurso 'cinta'. Ahi se forma una espera circular entre esos dos procesos que se puede evitar quitándole a la fuerza un recurso a cualquiera de los dos procesos.
• Condición de No Apropiació