• Author / Uploaded
• chojinmen

Citation preview

Tema 8. Sistemas Operativos 1.

2.

3.

Introducción.............................................................................................2 1.1. Definición..............................................................................................2 1.2. Funciones de los Sistemas Operativos.....................................................2 1.3. Partes de un sistema operativo...............................................................3 1.4. Evolución Histórica de los Sistemas Operativos........................................4 1.5. Tipos de Sistemas Operativos.................................................................5

2.4.1.

Algoritmos de Planificación.........................................................13

3.1.1. 3.1.2.

Monoprogramación.....................................................................20 Multiprogramación con particiones fijas....................................21

3.2.1. 3.2.2. 3.2.3.

Multiprogramación con particiones variables.............................22 Políticas de asignación de almacenamiento...............................23 Admin. de memoria con mapa de bits y listas enlazadas...........24

3.4.1.

Algoritmos de sustitución de páginas.........................................28

4.2.1. 4.2.2. 4.2.3. 4.2.4. 4.2.5. 4.2.6.

Asignación Adyacente.................................................................32 Asignación en forma de Lista Enlazada.......................................33 Asignación Mediante Lista Enlazada y Un Índice........................33 Nodos-i (Nodos-Índice)...............................................................34 NTFS............................................................................................36 Implantación De Directorios.......................................................36

5.1.1.

Reloj............................................................................................37

2.5. Sincronización y comunicación entre procesos.......................................17 Gestión de Memoria................................................................................19 3.1. Administración de Memoria sin intercambio...........................................20

3.3. 3.4.

5.

Por su estructura interna..............................................................5 Por los modos de explotación.......................................................6 Por los servicios ofrecidos.............................................................7 Por la forma de ofrecer los servicios.............................................8

Gestión de procesos.................................................................................9 2.1. Introducción..........................................................................................9 2.2. Técnicas Hardware utilizadas por un S.O. Interrupciones........................10 2.3. Implementación del modelo de procesos. Estados de un proceso............11 2.4. Planificación de Procesos......................................................................12

3.2.

4.

1.5.1. 1.5.2. 1.5.3. 1.5.4.

Intercambio (Swapping).......................................................................22

Memoria Virtual...................................................................................25 Paginación...........................................................................................26

3.5. Segmentación......................................................................................30 3.6. Segmentación paginada.......................................................................30 Gestión de Archivos................................................................................31 4.1. Directorios y Archivos...........................................................................31 4.2. Implementación del Sistema de Archivos...............................................32

Gestión de Periféricos (Entrada/Salida)................................................37 5.1. Dispositivos De Entrada/Salida..............................................................37

5.2. Controladores de Dispositivo.................................................................38 5.3. Acceso Directo a Memoria (DMA)..........................................................38 5.4. Principios del software de E/S...............................................................38 Anexo sobre FAT16, VFAT, FAT32...........................................................................41

Tema 8 – Sistemas Operativos

1

Introducción. Definición Un Sistema Operativo es un programa (o conj. de programas) de control que tiene por objeto facilitar el uso de la computadora y conseguir que se utilice eficientemente. Se encarga de gestionar y asignar los recursos hardware a los usuarios. Controla los programas de los usuarios y los dispositivos de E/S. Aísla al usuario de las peculiaridades del hardware del ordenador. Podemos ver, pues, el s.o. como un conjunto de programas que gestionan y coordinan el funcionamiento del hardware y software de la máquina.

Funciones de los Sistemas Operativos Vamos a ver unos ejemplos que introducen muy bien la utilidad de un s.o.: Ejemplo 1.1: un programador que diseña un programa de ordenación de datos, desde un fichero de entrada a otro de salida. Si no existe s.o., entre otras cosas se tendría que ocupar de: Saber donde está físicamente el fichero en memoria secundaria (MS: Cilindro, pista, Sector. (Gestión de Archivos) Gestionar la transferencia de datos de MS a memoria principal(MP) (Gestión de E/S). Gestionar el espacio en la MP de los datos traídos de MS (Gestión de Memoria). Ordenar los datos en MP (lo único que realmente tenía que hacer) Dar un lugar exacto para grabar la información del fichero de salida (Gestión de E/S). Liberar el espacio en MP (Gestión de Memoria). Ejemplo 1.2: Un programa tiene una serie de instrucciones (I1, I2, I3, …In) , una de las cuales es imprimir un documento de 1000 hojas. (Gestión de CPU: Procesos) P1: I1,I2,…Impresion100Hojas,… In, P2: I1, I2 P3:I1, I2, I3 La impresión de las 1000 hojas bloquearía al resto de programas del ordenador (P2 y P3), con un proceso que seguramente se puede hacer de forma independiente de la CPU. Nota: Como se vera más adelante, un proceso es un programa en ejecución.

Ejemplo 1.3: Tenemos una memoria RAM de 256 MB, y 4 procesos en memoria, cada uno de los cuales ocupa 200 MB ¿Cómo se gestiona y particiona la memoria para dar servicio a todos? (Gestión de Memoria)    

Por tanto el sistema operativo gestiona principalmente: Procesos Memoria Entrada/Salida Archivos

Los sistemas Operativos llevan a cabo fundamentalmente dos funciones que, en esencia, no tienen nada que ver entre sí. Según estas funciones se puede ver el Sistema Operativo desde dos puntos de vista:

Tema 8 – Sistemas Operativos

2

Sistema Operativo como máquina virtual: la arquitectura a nivel de lenguaje máquina de la mayoría de los ordenadores es primitivo y difícil de programar, particularmente en la E/S. El programa que oculta la cruda realidad acerca del hardware al programador y presenta una agradable y sencilla visión de los archivos es el sistema operativo. “la función del S.O. es presentar al usuario el equivalente de una máquina extendida o máquina virtual que sea más fácil de programar”. Sistema Operativo como controlador de recursos: un punto de vista alternativo de arriba hacia abajo, sostiene que el S.O. está ahí para controlar todas las piezas de un complejo sistema. Desde este punto de vista, la labor del sistema operativo es la de proporcionar una asignación ordenada y controlada de los procesadores, memorias y dispositivos de entrada/salida.

Partes de un sistema operativo Los módulos más importes de los que consta un Sistema Operativo son los siguientes:  

   

Cargador inicial: programa cargador, que pasa de memoria masiva a RAM los distintos módulos del Sistema Operativo. Núcleo (kernel): es la parte central del sistema operativo y entre otras tiene las siguientes funciones: o Planificación o asignación de la CPU. o Gestión de las interrupciones. o Comunicación y sincronización entre procesos. Administración de la Memoria Principal. Se encarga de gestionar la asignación de la memoria a los programas. Administración de los periféricos de E/S. Administración de archivos. Intérprete de las órdenes del lenguaje de control. Es el proceso que se encarga de realizar el dialogo con los usuarios (realmente no forma parte del sistema operativo como tal).

Como podemos observar, nuevamente, hablamos de la gestión de procesos, de memoria, de la E/S y de la gestión de archivos.

Tema 8 – Sistemas Operativos

3

Evolución Histórica de los Sistemas Operativos Generación Cero (década de 1940)

Los primeros computadores no disponían de sistemas operativos, se trabajaba siempre en lenguaje máquina y todas las instrucciones debían codificarse a mano.

Primera Generación (década de 1950)

Posteriormente, en la década de los cincuenta, se diseñaron nuevos sistemas operativos con el fin de hacer más fluida la transición entre trabajos, ya que se perdía demasiado tiempo entre la finalización de un trabajo y el comienzo de otro. Al principio, cuando el trabajo estaba en ejecución, éste tenía control total sobre la máquina. Al finalizar el trabajo, el control era devuelto al sistema operativo, que se encargaba de mostrar los resultados y comenzar el trabajo siguiente. Este proceso se mejoró con la introducción de las tarjetas perforadas (que servían para introducir los programas de lenguaje máquina), puesto que ya no había necesidad de utilizar los tableros enchufables. Además el laboratorio de investigación de General Motors implementó el primer sistema operativo para los ordenadores IBM 701. Estos sistemas 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 solo flujo, ya que los programas y los datos eran sometidos en grupos o lotes. La introducción del transistor a mediados de esta década cambió la imagen radicalmente. Se crearon máquinas suficientemente confiables, las cuales se instalaban en lugares especialmente acondicionados, aunque únicamente las grandes universidades, las grandes corporaciones o las oficinas del gobierno podían disponer de ellas.

Segunda Generación (hasta la mitad de la década de los sesenta)

A principio de los sesenta surgieron los sistemas operativos multiprogramados y los principios del multiprocesamiento. El sistema operativo se encargaba de seleccionar uno de los trabajos preparados y lo ejecutaba; en algún momento ese trabajo tendría que esperar porque la CPU debería procesar otro trabajo, y así sucesivamente. En los sistemas de multiprogramación, varios programas de usuario se encuentran al mismo tiempo en el almacenamiento principal y el procesadores cambia rápidamente de un trabajo a otro. En los sistemas de multiprocesamiento se utilizan varios procesadores en un único sistema computacional, con la finalidad de incrementar el poder de procesamiento de la máquina. La independencia de los dispositivos aparecerá después. Un usuario que deseara escribir datos en una cinta en sistemas de primera generación tenía que hacer referencia específica a una unidad de cinta particular. En la Segunda generación el programa del usuario especificaba tan sólo que un archivo iba a ser escrito en una unidad de cinta con cierto número de pistas y cierta densidad. Se desarrollaron sistemas compartidos, en los 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.

Tema 8 – Sistemas Operativos

4

Tercera Generación (desde la mitad de la década de los sesenta hasta la mitad de la década de los setenta)

Esta generación se inicia en 1964, con la introducción de la familia de computadores S/360 de IBM. Los computadores de esta generación fueren 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 en tiempo real y multiprocesamiento. Eran grandes y costosos; nunca antes se había construido algo similar y muchos de los esfuerzos de desarrollo terminaros 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 (desde la mitad de la década de los setenta en adelante)

Los sistemas de la cuarta generación constituyen el estado actual de la tecnología. Muchos diseñadores y usuarios se sienten aún 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 ordenadores y del procesamiento distribuido, los usuarios obtienen acceso a equipos alejados geográficamente a través de varios tipos de elementos de comunicación. Los sistemas de seguridad has pasado a tener mucha importancia, ya que la información pasa a través de varios tipos vulnerables de líneas de comunicación. Ha sido necesario codificar los datos personales o de gran intimidad para que, aun cuando puedan ser accedidos sin permiso, no sean de utilidad a nadie más que a los receptores adecuados.

Tipos de Sistemas Operativos Según la perspectiva con la que se observen los sistemas operativos, pueden realizarse múltiples clasificaciones. Entre ellas se pueden incluir las siguientes:

.1

Por su estructura interna

Esta clasificación tiene en cuenta cómo se diseñan los sistemas a la hora de ser creados. Hay que tener en cuenta que, en la mayoría de los casos estas concepciones de diseño no se aplican aisladas, sino que puede haber interrelación entre ellas. 



Monolítica. Es la estructura utilizada en los primeros sistemas operativos en la que todas las funciones se implementaban en el Kernel. Puede decirse que su estructura consiste en que no existe una estructura como tal. El sistema operativo está constituido por un único programa compuesto de multitud de rutinas interrelacionas entre sí, de forma que cada una de ellas pueda llamar a cualquier otra. Por capas. A medida que los sistemas operativos fueron creciendo, fue siendo necesaria una mayor estructuración. Este diseño se corresponde con una estructura jerárquica que se divide en distintos niveles, cada uno de ellos encargado de realizar distintas funciones principales del sistema operativo. Cada uno de los niveles se comunica con el

Tema 8 – Sistemas Operativos

5

inmediatamente inferior y superior coordinando sus funciones, se pueden distinguir cinco que son: o Nivel 1: Gestión del Procesador. En este nivel se encuentra la parte del sistema operativo encargada de la gestión de la CPU. En los sistemas operativos multiproceso, este nivel se encarga de compartir la CPU entre los distintos procesos realizando funciones de sincronización, conmutación de la CPU y gestión de interrupciones. o Nivel 2: Gestión de Memoria. Encargado de repartir la memoria disponible entre los procesos. Se realizan funciones de asignación y liberación de memoria, y el control de violación de acceso a zonas de la memoria no permitidas. o Nivel 3: Gestión de Procesos. Encargado de la creación y destrucción de procesos, intercambio, detección y arranque de mensajes. o Nivel 4: Gestión de Dispositivos. Aquí se realiza la gestión de las entradas/salidas (E/S) en función de los dispositivos existentes. Entre otras se encarga de las funciones de creación de procesos de E/S, asignación y liberación de dispositivos de E/S y planificación de la E/S. o Nivel 5: Gestión de la Información. El objetivo de este nivel es el de gestionar el espacio de nombres lógicos y la protección de la información realizando funciones de creación y destrucción de ficheros y directorios, apertura y cierre de ficheros, lectura y escritura de ficheros y protección de acceso. 

.2

Máquina virtual. Se trata de un tipo de sistemas operativos que presentan una interfaz 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 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. La principal ventaja de esta estructura reside en que permite implementar varios tipos de sistemas operativos sobre cada máquina virtual. No obstante, presentan el problema de que los sistemas operativos implementados son disjuntos, lo cual complica enormemente la interacción, comunicación y compartición que necesitan los sistemas operativos actuales.

Por los modos de explotación

Los modos de explotación se corresponden con las distintas maneras en que puede funcionar un sistema operativo. Dentro de ellas se encuentran las siguientes: 

Procesamiento por lotes. Se caracteriza por la agrupación en bloques de los trabajos similares. El rasgo más característico de este tipo de sistema operativo es la ausencia de interacción entre el usuario y el proceso mientras éste se ejecuta.



Multiprogramación. El sistema operativo se encarga de distribuir la carga computacional entre los procesadores existentes (monoprocesador o multiprocesador), con el fin de incrementar el poder de procesamiento de la máquina. Dentro de los sistemas operativos multiprogramados cabe diferenciar:

Tema 8 – Sistemas Operativos

6

.3

o

Tiempo compartido. Son los sistemas operativos más extendidos y a los que se refiere este tema. Utilizan las distintas técnicas de planificación de CPU para que se atiendan todos los procesos en espera de ser ejecutados. Este proceso ocurre tan rápidamente que el usuario no lo percibe. Entre este tipo de sistemas operativos se encuentra: UNIX, Windows (95, 98, Millenium, XP, NT, 2000), MAC-OS y OS/2.

o

Tiempo Real. En este tipo de sistemas, los resultados son correctos no sólo si la computación es correcta, sino que también ha de serlo el tiempo en el cual se producen los resultados. Basta imaginar un sistema de defensa de un navío militar que, al detectar un misil acercándose, lanza otro para destruirlo en el aire. No es suficiente con que el sistema de detección obtenga los datos y dé la órdenes correctas, también debe hacerlo en un intervalo de tiempo determinado; si no, esos resultados no valen de nada. Si no se cumplen las restricciones de tiempo, se dice que se ha producido un fallo en el sistema. Para ejecutar un conjunto de tareas concurrentes con un único procesador, hace falta multiplexar el uso entre todas las tareas activas en un momento dado. Utilizar algoritmos de planificación equitativos no permite garantizar el tiempo de respuesta de las tareas. Para solucionar este problema, se utiliza planificación basada en prioridades. Los sistemas operativos en tiempo real son sistemas muy complejos que suelen diseñarse a medida para ciertas aplicaciones, después de mucho tiempo de estudio de todas las opciones y problemas que pudieran surgir.

o

Híbrido. Intentan ser una mezcla de los dos anteriores, buscando combinar las ventajas de los sistemas en tiempo compartido y en tiempo real. No se han obtenido aún sistemas realmente eficientes.

Por los servicios ofrecidos En esta clasificación se tiene en cuenta la visión del usuario final y puede ser:

Por el número de usuarios 

Monousuario. Sólo soportan a un usuario a la vez, sin importar el número de procesadores o el número de tareas o procesos que el usuario pueda ejecutar al mismo tiempo. Entre este tipo de sistemas operativos se encuentra MS-Dos, DR-Dos, W95, W98, W Me, W XP, W2000 Profesional.



Multiusuario. Son capaces de dar servicio a más de un usuario a la vez, ya sea por medio de varios terminales conectados a la computadora o por sesiones remotas en una red de comunicaciones. Entre este tipo de sistemas operativos se encuentra W NT, W2000 Server, Linux, Unix, Novell Netware

Por el número de tareas 

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

Tema 8 – Sistemas Operativos

7



Multitarea. Es aquel que permite al usuario estar ejecutando varios programas al mismo tiempo. Entre este tipo de sistemas operativos se encuentra W9X, W XP, W Me, W2000, W NT, Linux, Unix.

Por el número de procesadores 

Monoprocesador. Es aquel que sólo es capaz de manejar un procesador. Sin embargo, permiten simular la multitarea haciendo que el sistema realice una tarea rotatoria con intercambio muy rápido. Entre este tipo de sistemas operativos se encuentra MS-Dos, DR-Dos, W95, W98, W Me, W XP.



Multiprocesador. Puede usar más de un procesador y, por tanto, son capacer de ejecutar varias tareas al mismo tiempo redistribuyendo la carga entre cada uno de ellos. Entre este tipo de sistemas operativos se encuentra W NT, W2000, Linux, Unix. Dentro de los sistemas multiprocesador, se encuentran los sistemas: o Asimétrico: Donde se agota toda la potencia de un procesador antes de consumir potencia de otros. o Simétrico: Donde se va consumiendo la potencia de los diferentes procesadores que tiene el ordenador de una forma equilibrada.

.4

Por la forma de ofrecer los servicios En esta clasificación se encuentran: 

Sistemas centralizados. Hasta que los computadores personales no tuvieron un precio accesible y suficiente potencia, la mayoría de los sistemas (UNIX) utilizaban el modelo de proceso centralizado. Con este tipo de modelo los computadores mainframe se encargaban de todo el procesamiento y los usuarios manejaban únicamente terminales “tontos” (es decir, no disponían de memoria, ni procesador). Actualmente se siguen utilizando los sistemas centralizados (como los Terminal Services de Microsoft), pero los terminales dejan de ser tontos y pueden realizar otras muchas tareas por sí mismos. Los principales SO centralizados en el mercado son z/OS, OS/390, Linux, TPF, VSE y ESA.



Sistemas de red. Sistemas que mantienen a dos o más computadoras unidas a través de algún medio de comunicación (físico o no), con el objetivo primordial de poder compartir los diferentes recursos y la información del sistema. En este entorno, cada computador mantiene su propio sistema operativo y su propio sistema de archivos local. El primer sistema operativo de red estaba enfocado a equipos con un procesador Motorota 6800, pasando posteriormente a procesadores Intel como Novell NetWare. Los sistemas operativos de red usados más ampliamente son Novell NetWare, Personal NetWare, LAN Manager, Windows NT Server, Windows 200 Server, UNIX, LANtastic, etc.



Sistemas distribuidos. Sistemas cuasi independientes que permiten distribuir los trabajos, tareas o procesos entre un conjunto de procesadores. Puede ocurrir que este conjunto de procesadores se encuentre en el mismo equipo o en equipos distintos (siendo, en este caso, transparente para el usuario). Existen dos esquemas básicos:

Tema 8 – Sistemas Operativos

8

o

Un sistema fuertemente acoplado es aquél que comparte la memoria y un reloj global, cuyos tiempos de acceso son similares para todos los procesadores.

o

Un sistema débilmente acoplado es aquél en el que los procesadores no comparten ni memoria ni reloj, ya que cada uno de ellos cuenta con su memoria local.

Las principales ventajas de los sistemas distribuidos son: o Compartición de recursos. o Aceleración de los cálculos. o Fiabilidad. o Comunicación. o Sistemas no heterogéneos. Los sistemas operativos distribuidos más extendidos son los siguientes: Sprite, Solaris-MC, Mach, Chotus, Spring, Amoeba, Taos, etc.

Gestión de procesos. Introducción Uno de los módulos más importantes de un sistema operativo es el que se encarga de administrar los procesos y tareas del sistema de cómputo. La parte del sistema operativo encargada de la gestión de los procesos es el kernel o núcleo. Las formas de explotación de un sistema operativo responden a la forma en la que el usuario utiliza los recursos hardware y software que componen el sistema informático. De esta forma, el usuario podrá obtener determinadas respuestas de sus peticiones ante el ordenador. La manera de obtener estas respuestas es lo que denominamos explotación de un sistema informático. Para ello vamos a ver una introducción de gestión y administración del tiempo de la CPU. En primer lugar definiremos proceso como un programa o rutina en ejecución. Un programa por sí es un ente “pasivo”, mientras que un proceso es un ente “activo”. Cada proceso, dentro de su información, tiene el código del programa, el área de datos, registros e información adicional. El sistema operativo debe poder crear un proceso, destruirlo, suspenderlo, retomarlo, debe tener un mecanismo para retomar un proceso y para sincronizalos, y mecanismos de concurrencia. En un sistema monoprogramación o serie, hasta que no termina la ejecución del programa del usuario no empieza a ejecutarse otro. La multiprogramación es una técnica que aprovecha los tiempos muertos de la CPU. Consiste en cargar en la memoria principal varios procesos. El SO, y más concretamente un módulo perteneciente al kernel denominado despachador (“dispatcher”), va dando turno de ejecución a cada uno de los procesos almacenados en memoria. Para hacer esto el despachador provoca sucesivas interrupciones.

Tema 8 – Sistemas Operativos

9

El tiempo asignado a cada proceso (quantum) depende del tipo de multiprogramación utilizado, en cualquier caso los programas se van ejecutando a lo largo del tiempo a trozos, dando la sensación a los usuarios de que todos los trabajos en memoria se ejecutan simultáneamente. En realidad no es así ya que la CPU solo puede en un instante dado estar dedicada a un programa. Sólo un s.o. que cuenta con varios procesadores es multitarea real.   

Un s.o. con un solo procesador: Carga en memoria más de un proceso Sólo se puede ejecutar un proceso cada vez Se va conmutando entre los procesos de forma que parece que realiza más de una tarea a la vez.

Se necesita una planificación para optimizar los recursos del sistema. Ejemplo 2.1: Un cocinero está trabajando y tiene 2 recetas a elaborar: una para hacer una paella y otra para un pastel. En este caso tenemos que: Procesador=Cocinero Receta Paella= Programa1 Receta Pastel= Programa2 Proceso 1= Haciendo la paella Proceso 2=Haciendo el pastel El cocinero puede estar elaborando las 2 recetas a la vez, aunque en cada instante tiene las manos en una sola cosa (proceso). Por ejemplo mientras bate los huevos del pastel, puede haber dejado el arroz reposando en la paellera. Si por ejemplo viene un compañero de cocina (llorando mucho) vociferando que se ha quemado, el cocinero dejará lo que tenga entre manos (proceso actual) y dará prioridad al compañero maltrecho. Buscará las instrucciones de cómo atender una quemadura (nuevo programa) y lo aplicará sobre el compañero (nuevo proceso P3). En cuanto haya terminado de atender al compañero, retornará el proceso que estaba llevando a cabo antes de la interrupción (el proceso 1 o el 2).

Técnicas Hardware utilizadas por un S.O. Interrupciones. Una interrupción consiste en detener momentáneamente la ejecución de un programa, para pasar a ejecutar otro. Posteriormente la CPU continúa con el programa interrumpido. Para dar servicio a los distintos procesos en ejecución, la CPU gestionará continuamente las interrupciones entre procesos. Ejemplo 2.2: Un proceso que controla el teclado, cuando se pulse una tecla, generará una interrupción sobre el programa que esté en ejecución en ese momento que desencadenará todo el proceso siguiente.   

Los pasos que se siguen en la gestión de una interrupción son los siguientes: Petición o demanda de interrupción. La petición se realiza por medio de una señal hardware o software enviada a la CPU. La CPU no atiende inmediatamente la petición de interrupción, sino que acaba antes de ejecutar la instrucción en curso. El tratamiento de la interrupción por parte de la CPU suele comenzar con una rutina o programa de servicio de inicio de la interrupción. esta rutina analiza la

Tema 8 – Sistemas Operativos

10

 

causa de la interrupción, salva en memoria el contenido de los acumuladores/registros de la CPU y pasa el control al programa preferente. Se ejecuta la rutina o módulo preferente, atendiéndose por tanto el requerimiento de la interrupción. Se ejecuta la rutina de servicio de fin de interrupción. Restaura el contenido de acumuladores/registros del programa que se interrumpió.

Un programa que interrumpe a otro puede a su vez ser interrumpido por otro, y así sucesivamente. Reconocimiento interrupción

Programa en Ejecución (PE)

de

la

Salvar contenidos asociados a PE Petición de interrupción

Determinación del origen de IR Inicio de la Interrupción

Instrucciones

Servicio de requerimiento realizado

PROGRAMA PREFERENTE

Fin de la Interrupción

Restaurar contenidos de PE

Regreso a PE

Implementación del modelo de procesos. Estados de un proceso.     

El SO utiliza una tabla de procesos. Por cada proceso almacena: Estado del proceso, que puede ser: En ejecución, Bloqueado, Listo. Contador de programa. Puntero de pila. Memoria asignada. Información relativa a su aplicación.

Esta información es necesaria para cuando pasa de estado de En ejecución a Bloqueado o Listo, para que en cuanto se reanude la ejecución lo haga como si no hubiera sucedido nada. En cada cambio de procesos, CAMBIO DE CONTEXTO, hay que salvar estos valores.

Estados de un proceso: Un proceso, desde el punto de vista de su ejecución, puede estar en una de las siguientes situaciones o estados:  

Estado listo: un proceso se encuentra en este estado cuando se encuentra en memoria principal, sin operaciones de e/s pendientes, y listo para entrar en ejecución Estado de ejecución: es cuando el proceso está siendo atendido por la CPU.

Tema 8 – Sistemas Operativos

11



Estado bloqueado: en este caso el proceso se encuentra esperando la realización de una operación de e/s o a la espera de un recurso no disponible.

Transiciones entre estados:

a

En ejecución

b c

Bloqueado

d

Listo

a=Un proceso activo se encuentra en el estado de ejecución y se inicia una operación de e/s, o solicita un recurso no disponible para él en ese momento. Pasa entonces a la situación de bloqueado. b=Un proceso activo se encuentra en el estado de ejecución y se le acaba su turno o quantum, o se interrumpe por cualquier motivo, pero sin haber terminado de realizar todas sus operaciones. Pasa entonces al estado de listo. c=Cuando al proceso, que está preparado, le llega su turno de CPU d=Cuando el proceso recibe el recurso esperado (señal, dato,…) o acaba la operación de e/s pendiente, entonces pasará a listo (y de ahí a ejecución cuando le toque su turno).

Planificación de Procesos. En un momento dado puede haber varios procesos listos para ejecutarse. 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 asigna el procesador a cada proceso del sistema. La parte del S.O. que decide cual ejecutar se llama planificador y el algoritmo que utiliza para tomar la decisión se llama algoritmo de planificación. Obviamente, si el sistema es monousuario y monotarea no hay mucho que decidir, pero en el resto de sistemas esto es crucial para el buen funcionamiento del sistema.

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 del propio planificador. Por tanto, un planificador intenta conseguir diversas metas como: 1. Equidad: Se asigna el procesador a cada proceso de forma equitativa. 2. Eficiencia: El procesador debería estar ocupado el 100% del tiempo. 3. Tiempo de respuesta: Minimizar el tiempo de respuesta para los procesos interactivos. 4. Tiempo de regreso: Minimizar el tiempo que han de esperar los usuarios de trabajos por lotes para obtener su salida 5. Tiempo de espera: es el tiempo que pasa un proceso en la cola de procesos listos esperando a que se le conceda la CPU. 6. Rendimiento: Maximizar el nº de trabajos procesados por unidad de tiempo.

Tema 8 – Sistemas Operativos

12

Algunos criterios pueden ser contradictorios, como el 3 y el 4, ya que si se favorece a los trabajos por lotes, se perjudica a los interactivos. Además, cualquier algoritmo que favorezca un tipo de trabajos perjudicará a otros. Principalmente, un planificador puede adoptar dos estrategias de funcionamiento:  Una estrategia que permite suspender a procesos ejecutables para ejecutar otros procesos: Planificación Apropiativa.  Otra estrategia que permite a un proceso ejecutarse hasta terminar o cambiar a estado de bloqueado: Planificación no apropiativa o de ejecución hasta no terminar. El éxito de la planificación de la CPU depende de la siguiente propiedad de los procesos: “La ejecución de un proceso consiste en un ciclo de ejecución de la CPU (ráfaga de CPU) y un ciclo de espera de E/S (ráfaga de E/S) y los procesos alternan entre estos 2 estados, comenzando y terminando por una ráfaga de CPU” Es decir, la ejecución del proceso es: Ráfaga de CPURáfaga de E/SRáfaga de CPURáfaga de E/S...Ráfaga de CPU Esta propiedad hace posible la existencia de la multiprogramación, ya que mientras unos procesos están en ráfagas de E/S, otro puede estar en una ráfaga de CPU. Esto hace que la CPU no se desperdicie consiguiendo también una reducción del tiempo total de ejecución de todos los procesos.

.1

Algoritmos de Planificación

Algunos de los algoritmos más importantes para asignar el turno de ejecución son los siguientes: Planificación FCFS (Primero en llegar, primero en ser servido) En este esquema, los procesos se ejecutan según el orden de llegada (primero en entrar primero en ser servido) Este algoritmo es el más sencillo pero quizás también el más ineficaz. Es el típico algoritmo de spool de impresoras. La ventaja de este algoritmo es que es justo y no provoca aplazamientos indefinidos. La desventaja es que no aprovecha ninguna de las características de los procesos y no sirve para procesos en tiempo real. En esta política el tiempo promedio de respuesta puede ser bastante largo. Este algoritmo en NO APROPIATIVO Ejemplo 2.3: Se lanzan los procesos A, B,C, llegando en ese mismo orden, con las siguientes ráfagas de CPU Proceso A: 7 Ciclos Proceso B: 5 Ciclos Proceso C: 8 Ciclos a 1

a 2

A 3

a 4

a 5

a 6

a 7

b 8

b 9

b 10

Tema 8 – Sistemas Operativos

b 11

b 12

c 13

c 14

c 15

c 16

c 17

c 18

c 19

c 20

13

En este caso, el tiempo medio de respuesta es de (7+12+20)/3 =13, y el tiempo medio de espera es de (0+7+12)/3 = 6.33 Planificación SJF (Primero el trabajo más corto) En este algoritmo, se busca que el promedio de espera de los trabajos sea el menor posible. Consiste en coger, de entre todos los trabajos listos, aquel que menos tiempo tarda en ejecutarse en total (aunque también se puede coger aquel con la siguiente menor ráfaga de CPU). Es difícil 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 tanto, especialmente indicado para sistemas por lotes, en los que se conoce de antemano el tiempo de ejecución. No aplicable en procesos interactivos, ya que en estos no se puede estimar la duración. Es óptimo cuando todos los trabajos están disponibles a la vez. Ejemplo 2.4: Tenemos 4 procesos en los que el tiempo estimado de ejecución en ciclos es el siguiente: Proceso Proceso Proceso Proceso

A = 8 ciclos. B = 4 ciclos. C = 4 ciclos. D = 4 ciclos.

Si lo ejecutamos en ese orden: A, B, C, D: a 1

a 2

a 3

a 4

a 5

a 6

a 7

a 8

b 9

b 10

b 11

b 12

c 13

c 14

c 15

c 16

d 17

D 18

d 19

d 20

El proceso D necesita 20 ciclos para poder terminar, el C necesita 16, el B necesita 12 y A necesita los 8 suyos solamente. El tiempo medio de regreso es de (20+16+12+8)/4 = 14 ciclos. El tiempo medio de espera es de (0+8+12+16)/4 = 9 ciclos. Si ahora ejecutamos primero los procesos más cortos, tendremos que: b 1

b 2

b 3

b 4

c 5

C 6

c 7

c 8

d 9

d 10

d 11

d 12

a 13

a 14

A 15

a 16

a 17

a 18

a 19

a 20

El proceso A necesita 20 ciclos, el D necesita 12, el C necesita 8 y el B 4. El tiempo medio de regreso queda como: (20+4+8+12)/4= 11 Ciclos. Y el tiempo medio de espera es de (12+0+4+8)/4 = 6 ciclos. Formalizándolo, si los procesos se ejecutan en tiempos a, b, c, d, tenemos que: El El El El

1º 2º 3º 4º

acaba en tiempo a en tiempo a+b en tiempo a+b+c en tiempo a+b+c+d

Tema 8 – Sistemas Operativos

14

El promedio sería: (4a + 3b + 2c + d)/4 Por tanto el que más contribuye a la media es el tiempo a, luego b,…con lo que queda claro que primero debemos ejecutar los procesos con tiempos más cortos para que su contribución a la media tenga menor peso. El algoritmo SJF puede ser apropiativo o no apropiativo(descrito hasta ahora). Será apropiativo cuando se quita la CPU a un proceso para dársela a otro proceso listo con ráfaga de CPU menor que lo que resta del proceso que se está ejecutando. A la SJF apropiativa se le llama Planificación SRTF (primero el que tenga menor tiempo restante). Aquí se calcula 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. La desventaja es que provoca más sobrecarga porque el algoritmo es más complejo. Planificación RR, Round Robin o circular. La asignación de tiempos de ejecución a los diferentes procesos es la misma y de forma rotativa. A cada proceso se le asigna el mismo quantum (intervalo de tiempo de ejecución). Un Quantum, y esto en general es aplicable para cualquier algoritmo: a. Muy alto: Deja a los procesos interactivos con respuestas demasiado largas. b. Muy corto: Hace que se pierda mucho tiempo en los cambios de contexto. La ventaja de este método es su simplicidad, es justo y no provoca aplazamientos indefinidos. Ejemplo 2.5: Tres procesos A, B, C, con una estimación de tiempos de ejecución, medida en ciclos como la siguiente: Proceso A: 7 Ciclos Proceso B: 5 Ciclos Proceso C: 8 Ciclos Con un quantum= 1 ciclo, la traza de ejecución sería: a 1

b 2

c 3

a 4

b 5

C 6

a 7

b 8

c 9

a 10

b 11

c 12

a 13

b 14

c 15

a 16

c 17

a 18

c 19

c 20

c 16

c 17

a 18

c 19

c 20

El tiempo medio de respuesta sería (18+14+20)/3 = 17.33 Y el tiempo medio de espera sería (11+9+12)/3=10.66 Con un quantum= 2 ciclos, la traza de ejecución sería: a 1

a 2

b 3

b 4

c 5

C 6

a 7

a 8

b 9

b 10

c 11

c 12

a 13

A 14

b 15

En este caso, el tiempo medio de respuesta sería (18+15+20)/3 = 17.66 Y el tiempo medio de espera sería (11+10+12)/3=11

Tema 8 – Sistemas Operativos

15

Por Prioridad. A cada proceso se le asigna una prioridad determinada. Los procesos de mayor prioridad se ejecutan primero. No se ejecutan procesos de prioridad inferior hasta que se hayan ejecutado todos los de prioridades superiores. Normalmente, la prioridad es un número donde un número alto representa una mayor prioridad. Dentro de cada prioridad, la ejecución se lleva a cabo de forma rotatoria. 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 prioridad baja. Ejemplo 2.6: Tenemos 2 procesos A y C con prioridad alta, y uno B con prioridad baja: Alta: A ; C Baja: B Proceso A: 7 Ciclos Proceso B: 5 Ciclos Proceso C: 8 Ciclos Suponiendo que los procesos A y B se lanzan en el primer ciclo y el proceso C en el tercer ciclo, tenemos que la traza de ejecución sería: a 1

a 2

a 3

a 4

a 5

a 6

a 7

c 8

c 9

c 10

c 11

c 12

c 13

c 14

c 15

b 16

b 17

b 18

b 19

b 20

El tiempo medio de respuesta sería (7+20+12)/3 = 13 Y el tiempo medio de espera sería (0+15+4)/3=6.33 El algoritmo por prioridad puede ser apropiativo o no apropiativo (que tomaremos por defecto). En el caso de que sea un algoritmo apropiativo, cuando llega un proceso y solicita el uso de la CPU, si este proceso es de mayor prioridad que el que se está ejecutando, el planificador automáticamente le asigna a este nuevo proceso (“más importante”) el uso de la CPU, y el otro pasará a la lista de espera. Multinivel Es la planificación más general de todas, pero también la más compleja. Podemos tener varias colas de distintos niveles de prioridad. Cada proceso se asigna a una cola y otra según ciertos criterios, como son: tipo de proceso (interactivo o proceso por lotes, que tienen requisitos de tiempo de respuesta bastante diferentes), importancia del proceso (de sistema o de usuario), etc. Cada una de las colas tiene su propio algoritmo de planificación, que se debe elegir en función del tipo de procesos de esa cola. Entre las distintas colas también debe existir una planificación que puede ser planificación apropiativa por prioridad o repartir el tiempo de CPU entre las colas y que cada una lo administre a su manera.

Tema 8 – Sistemas Operativos

16

Sincronización y comunicación entre procesos. Comunicación entre procesos.

Cuando se ejecutan varios procesos a la vez, es posible que éstos compartan uno o varios recursos del sistema (monitor, memoria...). El objetivo del Sistema Operativo es permitir que varios procesos compartan recursos sin que se produzcan problemas. Hay dos tipos de procesos: los independientes que no afectan ni pueden ser afectados por ningún otro proceso y los cooperantes que afectan y pueden ser afectados por algún otro proceso del sistema operativo. Los procesos con frecuencia precisan comunicarse entre sí. Situaciones donde dos o más procesos leen o escriben algunos datos compartidos y el resultado final depende de cual se ejecuta en un momento preciso se denomina Condiciones de concurso. Lo que se necesita es exclusión mutua (que es un mecanismo por el que se asegura que sólo una persona o proceso está haciendo algo en un instante determinado y los otros están excluidos, como por ejemplo, dos procesos que comparten una sección de memoria). La parte del programa que accede a la memoria compartida (entre distintos procesos) se le llama sección crítica. Para tener una solución adecuada los procesos deben cumplir estos cuatro puntos: 1. Nunca dos procesos pueden encontrarse simultáneamente en sus secciones críticas. 2. No se hacen suposiciones acerca de las velocidades relativas de los procesos o del número de CPU. 3. Ningún proceso suspendido fuera de la sección crítica debe bloquear a otros procesos. 4. Nunca un proceso debe querer entrar de forma arbitraria en su sección crítica.

Algoritmos de solución al problema de la sección crítica Deshabilitación de Interrupciones La solución más simple es que cada proceso desactive todas las interrupciones justo después de entrar en su sección crítica y las vuelva a activar antes de salir de ella. Con las interrupciones deshabitadas no pueden ocurrir interrupciones al reloj por lo cual no se cambiara a otro proceso. Este método no es muy atractivo ya que no es muy prudente dar a los procesos del usuario el poder de desactivar las interrupciones. Si un usuario lo hiciera y nunca las volviera a activar sería el fin del sistema. Además si fuera un sistema con más de una CPU la desactivación de interrupciones solo afectaría una de ellas y las otras podrían acceder a la memoria compartida. Algoritmo de Variables de Cierre Este algoritmo utiliza un flag. Al entrar a la sección crítica se fija si es uno o cero; si es cero lo pone en uno y entra a la sección crítica; si es uno espera hasta que valga cero. Antes de salir de la sección crítica iguala el flag a cero. Repeat If (flag = 0) then { Flag:=1 Seccion crítica

Tema 8 – Sistemas Operativos

17

Flag:=0 Seccion no crítica} Until flag = 1 Este algoritmo sin embargo no resuelve el problema de la sección crítica porque si hubiera una interrupción justo después de comprobar el estado del flag y se accediera a la memoria compartida antes de cambiar el flag, otro proceso podría acceder a la memoria compartida, cambiar el flag a uno y habría dos procesos accediendo a la memoria compartida. Algoritmo de alternación Estricta En este algoritmo dos procesos comparten una variable flag, pero en vez de utilizar el mismo código se usa distinto código para cada proceso. Proceso 1 Repeat While (flag=1) do no_op Seccion crítica Flag=1 Seccion no crítica Until 0=1

Proceso 2 Repeat While (flag=0) do no_op Seccion crítica Flag=0 Seccion no crítica Until 0=1

El problema aquí radica en que si un proceso tiene una sección no crítica muy larga el otro tendrá que esperar para entrar en su sección crítica a pesar que no se esté ejecutando nada que la afecte. Explicación: Cuando el proceso 1 sale de su sección critica hace que flag sea 1, lo que le permite que el proceso 2 entre en su sección critica; el P1 entra en su sección no crítica, pero si la sección crítica de P2 tarda menos tiempo que la no crítica de P1 hay tiempo desperdiciado para P2 que no puede coger el control hasta que P1 termine su sección crítica y la crítica.

Sincronización de procesos Los Semáforos son una de las herramientas que se utilizan para la sincronización de procesos. Es una variable protegida que solo puede ser modificada por la rutina de inicialización y por otras dos operaciones atómicas: Se realizan dos operaciones sobre los semáforos: 



Down. Sobre semáforo verifica si el valor es mayor que 0. Si es así, disminuye el valor y simplemente prosigue. Si el valor es 0, el proceso se bloquea. La verificación del valor, su alteración y posiblemente su bloqueo se realizan en una única acción atómica e indivisible. Up. Incrementa el valor del semáforo. Si uno o más procesos están bloqueados en ese semáforo, el sistema elige uno y le permite completar su operación Down; el semáforo seguirá siendo 0 pero habrá un proceso bloqueado menos en él.

Bloqueos La mayoría de los recursos que existen en cualquier computador sólo pueden utilizarse por un proceso a la vez. Basta pensar, por ejemplo, en una impresora; no es

Tema 8 – Sistemas Operativos

18

posible que dos procesos hagan uso al mismo tiempo de este dispositivo, el resultado sería catastrófico. Sin embargo, en un sistema operativo multiprogramado, la situación anterior puede darse en multitud de ocasiones y el sistema operativo debe encargarse de que esto no ocurra, otorgando acceso exclusivo a los recursos del sistema susceptibles de ser accedidos por más de un proceso al mismo tiempo. No obstante, la apropiación de un dispositivo de E/S para uso exclusivo puede provocar, a su vez, problemas graves que el sistema operativo también debe encargarse de resolver. Imagínese dos procesos que desean imprimir un gran archivo situado en una cinta al mismo tiempo. El proceso A solicita en uso exclusivo la impresora, mientras que el proceso B solicita el uso exclusivo de la cinta. El proceso A no puede comenzar la impresión porque no tiene acceso a la cinta, pero no libera la impresora. Mientras tanto, el proceso B no inicia la impresión ya que no tiene acceso a la impresora, pero no libera la apropiación de la cinta. Se dice que los procesos se han bloqueado y permanecerán así para siempre si el sistema operativo no se encarga de solucionarlo. El bloqueo de un conjunto de procesos se produce cuando un proceso espera un evento que sólo puede ser provocado por otro proceso del conjunto. Los procesos permanecerán esperando; ninguno de ellos realizará ninguna acción hasta que otro libere algún recurso, por lo que se entra en un bucle de espera infinito. El bloqueo se denomina también como abrazo mortal. Los sistemas operativos emplean distintas técnicas para enfrentarse al problema de los bloqueos. 1. Algoritmo del avestruz, es decir, meter la cabeza bajo la tierra e ignorar el problema. Si después de estudiar la probabilidad de bloqueos en el sistema, se llega a la conclusión de que ésta es muy baja (por ejemplo, un bloqueo cada seis años), es posible que los programadores decidan no perder el tiempo en implementar técnicas de detección y corrección de bloqueos. UNIX funciona con este “algoritmo”. 2. Evitarlos: mediante un estudio cuidadoso de la asignación de recursos, el sistema operativo puede conseguir que nunca se produzcan bloqueos. 3. Detección y recuperación: los bloqueos se producen, pero el sistema operativo se encarga de detectarlos y recuperarse del bloqueo.

Gestión de Memoria Un programa máquina es un conjunto ordenado de instrucciones en código máquina. Estas instrucciones, en el momento de ejecutarse “encajan” en palabras de memoria que pueden numerarse correlativamente de la 0 a la n-1. Estas direcciones se denominan direcciones lógicas. El programa al ser cargado en memoria, ocupará determinadas posiciones de la misma (en total n); si se cargan a partir de la dirección N, quedará ubicado de la dirección N a la N-1. A N se denomina dirección base y a las direcciones f en que realmente se almacenan las instrucciones se les denominan direcciones físicas. f = N + i; para todo 0 p7 p3 -> p5 -> p6

s.o.

Otra posibilidad es tener una única cola compartida por todas las particiones. Cuando se libera una partición se busca la primera tarea de la cola que quepa en dicha partición. Como esto puede hacer que una tarea pequeña desperdicie una partición grande…  buscar en la cola el trabajo más grande que quepa  se discrimina a tareas pequeñas que podrían ser tareas interactivas que requieren un mejor trato. Una solución: tener una partición pequeña. Otra

Tema 8 – Sistemas Operativos

21

solución: establecer un límite k. Si una tarea se excluye más de k veces, ya no se excluye más. Partición 4 Partición 3

7 MB 6 MB

Partición 2

4 MB

Partición 1

2 MB

p2-p4-p1-p7...

s.o.

Claramente, aquí el grado de multiprogramación se ve limitado por el número de particiones.

Fragmentación

La fragmentación se produce cuando en la memoria hay áreas ocupadas intercaladas con áreas libres, es decir, no hay una única área ocupada ni una única área libre. Se presenta en todos los sistemas de cómputo sea cual sea la organización de almacenamiento. En los sistemas de multiprogramación con particiones fijas surge porque los trabajos no llenan por completo las particiones designadas (fragmentación interna) o porque una partición se queda sin utilizar por ser demasiado pequeña para contener un trabajo que espera (fragmentación externa).

Intercambio (Swapping) Las particiones fijas son válidas para sistemas por lotes, mientras haya trabajos para mantener ocupada la CPU, pero en procesamiento con tiempo compartido la cosa cambia Hay más usuarios que MP para contener todos sus procesos, y estos entran/salen continuamente. Por tanto en el Swapping la memoria se va asignando dinámicamente a los procesos. El paso de MP a MS (y viceversa) se llama intercambio.

.1

Multiprogramación con particiones variables

En la multiprogramación con Particiones fijas pueden servir para un sistema de intercambio, pero una parte grande de ellas es desperdiciada por procesos que son menores que sus particiones. Solución: Particiones variables donde el nº, posición y tamaño de las particiones varían dinámicamente en tiempo de ejecución.

Tema 8 – Sistemas Operativos

22

Proceso A

Proceso C

Proceso C

Proceso C

Proceso B

Proceso B

Proceso B

Proceso B

Proceso A

Proceso A Proceso D

Sistema Oper.

Sistema Oper.

Sistema Oper.

Sistema Oper.

Sistema Oper.

+A

+B

+C

-A

+D

Al no estar condicionados por particiones fijas que pueden ser demasiado grandes o pequeñas, mejora la utilización de la MP, pero complica la asignación/desasignación de ésta. Si un proceso tiene un tamaño fijo se asigna exactamente lo que necesita, pero el proceso puede crecer asignándole memoria dinámica:  Si al lado del proceso hay hueco no se presenta ningún problema: se le asigna este hueco.  Si hay un proceso a su lado, entonces hay que moverlo a otro hueco.  Si no hay hueco suficiente, hay que esperar o eliminar el proceso. Solución: Reservar memoria extra para los procesos, reduciendo así estos inconvenientes. Compactación de la MP: Combinar todos los huecos en uno más grande, pasando todos los procesos a la parte inferior (o superior) de la memoria. Solo se usa en casos extremos, porque requiere de mucho tiempo de CPU.

.2

Políticas de asignación de almacenamiento.

Cuando hay que asignar memoria a un nuevo proceso se debe buscar un hueco. Hay distintas formas de buscar ese hueco libre y eso es lo que vamos a ver ahora. Políticas:  Primero en ajustarse: El administrador de memoria busca el primer hueco lo suficientemente grande para que quepa el proceso. El hueco se divide en 2 partes, una para el proceso y otra que pasa a ser un hueco libre (si es que no cabe de forma exacta). Este algoritmo es rápido pues busca lo menos posible. Una variante es el siguiente en ajustarse. El funcionamiento es el mismo sólo que empieza a buscar desde donde se quedó la última vez, en vez de empezar siempre desde el principio.  Mejor en ajustarse: Busca entre todos los huecos el más pequeño en el que quepa el proceso y que menos hueco creará. Es lento ya que debe buscarse en toda la lista y genera multitud de pequeños huecos casi inservibles. 

Peor en ajustarse: Lo contrario de lo anterior. Busca el que genera mayor hueco, para que luego sea útil. Es lento ya que debe buscarse en toda la lista. Funciona bastante bien.

Tema 8 – Sistemas Operativos

23

.3

Admin. de memoria con mapa de bits y listas enlazadas.

Hemos visto distintas formas de asignar memoria a los distintos procesos sin preocuparnos de llevar un registro de la memoria libre y de la ocupada. Veamos dos formas utilizadas por los sistemas operativos para llevar un registro del uso de la memoria.

Mapa de bits

La memoria principal se divide en unidades de asignación, todas del mismo tamaño. Por cada unidad de asignación hay un bit en el mapa de bits, que tomará el valor: 0  Unidad libre. 1  Unidad ocupada.

Proceso A

Proceso B

El tamaño de la unidad de asignación es importante:  Una unidad de asignación (u.a.) pequeña, hace que se desperdicie poco por hueco no utilizado (en la última u.a. que tiene el proceso), pero a cambio genera un mapa de bits grande.  Una u.a. grande hace que se desperdicie mucho por hueco no utilizado, pero a cambio el mapa de bits es menos complejo. Ejemplo 3.1.: Tamaño de u.a. de 4 bytes= 32 bits, en una memoria de 64 MB. 64 * 1.048.576 Bytes / 4 Bytes = 16.777.216 entradas (bits) necesarias en el mapa de bits, donde cada bit indica un bloque. El total de memoria ‘desperdiciada’ en tareas de administración sería: 16.777.216 / (64* 1.048.576 * 8) = 0.0312  3.12 % de la memoria se utiliza en gestionarla. Cuando se trae un proceso que tiene ‘k’ unidades de asignación de tamaño, hay que recorrer el mapa buscando un hueco de al menos ‘k’ u.a. Este proceso no es muy rápido, por eso no se utiliza demasiado.

Listas enlazadas

Tenemos una lista enlazada de segmentos de memoria asignados o libres. Cada segmento es un proceso (es decir, una zona ocupada) o un hueco entre 2 procesos (2 huecos seguidos no puede haber, puesto que formarían un único hueco) Ejemplo 3.2: Supongamos que tenemos 2 procesos, uno de tamaño 5 (empieza en 0) y otro de tamaño 6 (empezando en la posición 8). En medio hay un hueco de tamaño 3 (empezando en el 5) P1 0

5

 H

5

3

 P4 8

6

Cuando termina un proceso rodeado de huecos se puede unificar tanto por delante como por detrás.

Tema 8 – Sistemas Operativos

24

Ejemplo 3.3: Si entra un proceso P7, de tamaño 2, el hueco que teníamos se reduce a 1 P1 0

5

 P7 5

2

 H

7

1  P4

8 6

Si el proceso P4 acabara: P1 0

5

 P7 5

2

 H

Para la búsqueda de huecos a los procesos algoritmos vistos en el apartado 3.2.2.

7

7

podemos hacer uso de los

Memoria Virtual Se guardan en la memoria parte de los programas (parte de los procesos), pero no necesariamente procesos completos como en el Intercambio. Se utiliza un mecanismo de traducción de direcciones virtuales a direcciones físicas en MP (reales). Dirección Virtual (en el proceso)  Dirección Física (en MP) La memoria que ocuparía el proceso se ‘virtualiza’: Se divide el proceso en bloques en MS, para que se puedan mover estos bloques de forma independiente a MP, sin tener que mover el proceso completo. El mecanismo de traducción dinámica debe mantener las correspondencias entre las direcciones virtuales del proceso y las direcciones reales que efectivamente ocupan. La MP se organiza en bloques que tendrá el mismo tamaño en memoria virtual, y en el área de intercambio de MS.  Si el tamaño del bloque es grande: menor es el espacio ocupado para guardar las correspondencias, pero también se tarda más en transferir de MS a MP y además el nº de procesos que pueden compartir la MP es menor. Si todos los bloques son iguales hablamos de PÁGINAS. Si los bloques son de diferentes tamaños se les denomina SEGMENTOS. Los sistemas actuales combinan ambos métodos, utilizando por ejemplo segmentos de tamaño variable, compuesto de páginas de tamaño fijo. Las direcciones de memoria virtual son al menos bidimensionales (ya sea con segmentación, paginación o una combinación de ambas): Don Virtual= (b,d), b = Es el nº de bloque d = Es el desplazamiento dentro del bloque.

Tema 8 – Sistemas Operativos

25

… … b’

↑d

..

Tema 8 – Sistemas Operativos

26

REGISTRO a Registro de CPU con dirección de tabla de asignación

T:

Tamaño de cada entrada en la tabla de bloques

a+ (b*t) +

a

b

D

Nº bloque

Desplazamiento

Tabla asignación bloques proceso

t v1 v2 b’

b

….

Dirección Virtual: (del proceso) V=b+d

de de del

+ Dirección Física: (en MP) F=b’+d

v1, v2… : Son los bits de acceso, modificaciones,…. b' : es la dirección del bloque en el almacenamiento físico d: Es el desplazamiento dentro del bloque Este esquema es válido para segmentación, combinados como segmentación/paginación.

paginación

y esquemas

Cada proceso tiene su propia tabla de asignación de bloques, que el sistema aloja en una zona de MP que nunca se virtualiza. En cada cambio de contexto se carga en el registro ‘a’ la dirección de la tabla de asignación del proceso. En MP están las tablas de asignación de todos los procesos que hay en MP, y en ‘a’ apuntamos a la tabla del proceso que ha entrado en la CPU. Este rgtro ‘a’ se llama CR3 en algunos micros de Intel x86, o PDR en los procesadores Alpha. Las tablas de asignación de bloques de los procesos se almacenan en un espacio contiguo de direcciones de MP llamado ‘directorio de bloques’.

Paginación Utilizado, junto a otros esquemas también, en UNIX, Linux, Windows NT.

Tema 8 – Sistemas Operativos

27

CPU

Memoria Principal

MMU

Controlador de E/S Disco

MS

La CPU trabaja con direcciones virtuales. La MMU (Memory Manager Unit) traduce las direcciones virtuales a direcciones físicas. La MMU puede estar en el chipset o en el microprocesador. Los bloques de memoria virtual se denominan ‘páginas’ y los de memoria física (en MP) ‘Marcos de página’ y tienen el mismo tamaño. Este tamaño puede ir de 512 bytes hasta unas 8KB. En algunos x86 tiene un tamaño de 4KB, en los Alpha de 8KB. Ejemplo 3.4.: Si tenemos un espacio virtual de 64 KB (de un proceso) y la memoria física es de 32 KB (MP), con un tamaño de página de 4 KB, tenemos que (64 KB / 4 KB) = 16 páginas virtuales (el proceso se divide en 16 páginas) (32 KB / 4 KB) = 8 marcos de página (la memoria se divide en 8 marcos de página) Las direcciones virtuales son de 16 bits, ya que 2 16 = 64 KB: 4 bits con el nº de página (24 = 16 páginas en que se divide el proceso) 12 bits con el desplazamiento dentro de la página, 2 12=4096 B Las 16 páginas virtuales deberán caber en 8 marcos de página en MP. Esto es, si sólo estuviera este proceso, la mitad de sus páginas no cabrían en MP. Si hay más procesos aparte de éste, que es lo lógico, entonces tendremos aún más páginas virtuales a colocar sólo en 8 marcos de página. Si tenemos ‘m’ páginas virtuales y ‘n’ marcos de página y m>n, al menos hay m-n páginas que no están en MP. Tenemos que llevar control de qué páginas están en MP y cuales no. En cada una de las líneas de la tabla de asignación de bloques del proceso: V

…

R

M

nº de marco de página / D on en Disco

Donde: V = Página presente/ausente en un marco de página R = Bit de página referenciada M = Bit de página modificada. nº de marco de página = Es donde se encuentra la página. Sino se encuentra en MP, este campo nos índica donde se encuentra la página en memoria secundaria.

Tema 8 – Sistemas Operativos

28

Si la CPU hace referencia a una página que no está en ningún marco, la MMU (Memory Management Unit) hace que la CPU envíe una señal de “fallo de página” al sistema operativo.

.1

Algoritmos de sustitución de páginas

Cuando ocurre un fallo de página, el SO tiene que elegir que página sacar de MP para cargar la de disco. Si la página a sacar se ha modificado, habrá que escribirla en disco para actualizarla. Deberíamos elegir una página poco usada para su sustitución. Si se quita una página muy utilizada, probablemente tendrá que volver a cargarse de forma inmediata. Principio de “optimalidad”: El mejor algoritmo es aquel que elimina la página que tardará más tiempo en ser referenciada. Pero el sistema operativo no tiene forma de saber cual va a ser la futura referencia. Todas las técnicas que se aproximan a este óptimo serían las más adecuadas.

Algoritmo de reemplazo de páginas Óptimo

De todas las páginas que hay en memoria y que se pueden eliminar, se elimina aquella para la que pasará más tiempo antes de que sea utilizada. Este algoritmo es irrealizable ya que el SO no tiene forma de saber qué página se referenciará más tarde. Sin embargo, es útil ya que, mediante simulación, se puede estudiar lo bueno o malo que son otros algoritmos realizables.

Algoritmo NRU (no usada recientemente)

En cada entrada de la tabla de págnas existe un bit referenciado (bit R) utilizado para saber si una página se ha referenciado o no (tanto para lectura como para escritura) y un bit modificado (bit M) para saber si una página se ha modificado o no (y saber si se debe escribir en el disco cuando es eliminada de memoria). Cuando un proceso se inicia, pone los 2 bits a 0. Una vez activado cada uno de estos 2 bits por el hardware, permanece en ese estado hasta que el SO lo desactiva por software. Para distinguir las páginas no referenciadas recientemente de las que si, cada cierto tiempo se pone el bit R=0. El sistema operativo divide las páginas en 4 categorías: Clase 0 1 2 3

R 0 0 1 1

M 0 1 0 1

Tema 8 – Sistemas Operativos

29

La existencia de las páginas de clase 1 (con R=0 y M=1), se produce cuando en una página de clase 3 una interrupción de reloj limpia su bit R (indica que son páginas que han sido modificadas pero no referenciadas recientemente). El algoritmo NRU elimina una página elegida de forma aleatoria de la primera clase no vacía de número más pequeño. Este algoritmo es sencillo, de implementación eficiente y con un rendimiento adecuado muchas veces.

Algoritmo FIFO (primero en entrar, primero en salir)

Tenemos una lista (de todas las páginas que sen encuentran en la memoria) ordenada por antigüedad: Cabeza Lista= La más antigua que entró Final Lista= La más moderna que entró. En un fallo de página se elimina la página de la cabeza de la lista. Este algoritmo es sencillo de entender y de implementar, así como de bajo coste. El problema de este algoritmo es que no tiene en cuenta ningún dato adicional, como la frecuencia de uso de una página, lo que hace que muchas veces produzca demasiados fallos.

Algoritmo de la segunda Oportunidad:

Es una modificación del algoritmo FIFO que evita deshacerse de una página de uso frecuente. El algoritmo sería como sigue: Elemento= Cabeza Repetir Si elemento Є grupo 0 entonces Eliminar Elemento Sino Si elemento Є Grupo 1 entonces Eliminar Elemento Sino Si R=1 entonces R=0 (cambia de grupo) Pasar al siguiente elemento de la lista Mientras NoEliminemos Si el bit R de todas las páginas es 1, este algoritmo deriva en un simple FIFO, lo que asegura que siempre termina.

Algoritmo del reloj

Aunque el algoritmo de la segunda oportunidad es razonable, es ineficiente puesto que desplaza constantemente las páginas en una lista. Un mejor enfoque es mantener las páginas en una lista circular donde una “manecilla” apunta a la página más antigua. Al ocurrir un fallo de página, se inspecciona la página a la que apunta la manecilla. Si su bit R=0, la página se retira de la memoria, se inserta la nueva página

Tema 8 – Sistemas Operativos

30

en su lugar en el reloj y la manecilla avanza una posición. Si R=1, este bit se pone a 0 y la manecilla avanza a la página siguiente. Este algoritmo difiere del anterior sólo en la implementación.

Algoritmo LRU (menos usada recientemente).

Se basa en el principio de localidad: Las páginas usadas últimamente lo seguirán siendo en las siguientes instrucciones. Es por tanto, una buena aproximación al algoritmo óptimo, ya que se basa en una idea que se aproxima a la del óptimo. Al ocurrir un fallo de página, se saca de memoria la página que no ha sido usada durante hace más tiempo. Este algoritmo es caro en lo que respecta al tiempo, ya que es necesario mantener una lista ligada de todas las páginas en la memoria, donde la página usada más recientemente está al principio de la lista y la que se utilizó hace más tiempo está al final. El problema radica en que la lista debe actualizarse en cada referencia a memoria: la página que se acaba de utilizar debe buscarse en la lista, eliminarla de su posición y trasladarla al frente. Una implementación vía hardware (que reduciría el coste temporal), utilizaría un contador “C” de n bits. Este contador se incrementa en cada ciclo de reloj. Al referenciar una página se copia “C” a un campo “Contador” de la página. El que tenga menor valor en su campo “Contador” es la usada menos recientemente y es la que se sustituye.

Segmentación En la segmentación, el espacio de direcciones lógicas se compone de un conjunto de segmentos, cada uno de los cuales tiene una posición y un tamaño, y además con información general a un aspecto: Código, datos, pila, …. La dirección se conforma con dos valores (s, d): s: nº de segmento d: desplazamiento dentro del segmento Para hacer corresponder las direcciones bidimensionales del usuario (segmento, desplazamiento) con las direcciones físicas unidimensionales, se usa una tabla de segmentos. Cada entrada de la tabla de segmentos tiene una base (dirección de comienzo del segmento) y un límite (tamaño del segmento). La segmentación está estrechamente relacionada con los modelos de administración de memoria de multiprogramación con particiones variables y como en ellos, se produce fragmentación externa.

Segmentación paginada. Combina ambos esquemas. Los segmentos contienen páginas, es decir, los segmentos se dividen en un número determinado de páginas. Esto hace que desaparezca la fragmentación externa (ya que se pueden utilizar todos los marcos), aunque no la interna. El tamaño del segmento es por tanto múltiplo del tamaño de página. No todas las páginas de un proceso tienen que estar presentes en MP. Ni siquiera páginas contiguas en memoria virtual tienen porqué serlo en MP. Tema 8 – Sistemas Operativos

31

Una dirección virtual se compone ahora, por tanto, de 3 elementos (s, p, d), donde: s: Nº de segmento p: Nº de página d: desplazamiento dentro de la página Los esquemas utilizados en algunos microprocesadores comerciales son: Segmentación: 8088, 8086, 80186, 80286 Segmentación/Paginada: IBM/370, GE-645, 80386, 80486, Pentium.

Gestión de Archivos Todas Tenemos tres plazo: o o o

las aplicaciones necesitan almacenar y recuperar la información. condiciones esenciales para el almacenamiento de la información a largo Debe ser capaz de almacenar gran cantidad de información. La información debe sobrevivir a la conclusión del proceso que la utiliza. Debe ser posible que varios procesos tengan acceso concurrente a la información.

La solución es el almacenamiento de la información en discos y otros medios externos, en unidades llamadas archivos. Un archivo es un conjunto de información del mismo tipo, tratada como una unidad de almacenamiento. Un archivo debe desaparecer sólo en caso de su eliminación explícita por parte del usuario. Los archivos son administrados por el sistema operativo. Su estructura, nombre, forma de acceso, uso, protección e implementación son temas fundamentales en el diseño de un sistema operativo. Para poder almacenar los datos en un disco, éstos se han de guardar respetando una serie de normas y restricciones. Estas normas y restricciones vienen impuestas por el sistema de archivos implementado. El sistema de archivos determinará esa estructura, nombre, forma de acceso, uso y protección de los archivos que se guardarán en el disco. Cada sistema operativo dispone de su propio sistema de archivos diferente, pero el objetivo y función de todos ellos es el mismo: permitir al usuario un manejo fácil y lógico de sus archivos abstrayéndose de las particularidades de los dispositivos físicos empleados.

Directorios y Archivos En un sistema de archivos hay dos tipos fundamentales de objetos: los directorios y los archivos. Los archivos son los objetos encargados de contener los datos, mientras que los directorios son los objetos cuya misión principal es permitir una mayor organización de los archivos dentro del disco. Un directorio es un contenedor que puede contener archivos y, a su vez, otros directorios dentro de él. De esta forma, se puede llegar a crear una jerarquía en forma de árbol que simplifica enormemente la tarea de

Tema 8 – Sistemas Operativos

32

organizar y estructurar los archivos dentro de un disco. En realidad, lo que un directorio contiene no son otros directorios ni otros archivos tal cual, sino la información necesaria sobre dichos archivos o directorios, generalmente la posición del sector del disco en el que comienzan, que permitirá al sistema operativo recuperar su contenido del disco. En todo sistema de archivos hay un directorio especial llamado raíz o root que es el directorio que contiene todos los demás directorios y archivos. Desde este directorio es desde el que se parte cuando se busca un archivo mediante una ruta de acceso absoluta. Cuando se usa una ruta de acceso relativa, el archivo se busca partiendo del directorio en el que se está trabajando o directorio activo. Muchos sistemas operativos que implementan un sistema jerárquico de directorios tienen dos entradas en cada uno de sus directorios, “.” y “..”, que hacen referencia respectivamente al directorio activo y a su padre, es decir, al propio directorio y al directorio de nivel superior que contiene a éste. Estas entradas permiten navegar de una forma más cómoda por el árbol de directorios.

Implementación del Sistema de Archivos Tenemos distintas estrategias de almacenamiento de un fichero de N bytes: Se almacenan como N bytes consecutivos de espacio del disco. Si el archivo crece habrá que cambiarlo de sitio, ya que al delimitar seguramente con otro fichero (u otro tipo de información) sobrescribiría estos datos. Otra posibilidad, es dividir los N bytes en varios bloques, contiguos o no. Un bloque está compuesto por un determinado número de sectores que se asocian a un único archivo. Un archivo, por tanto, se almacena en uno o más bloques. Esta opción aporta mayor flexibilidad. A estos bloques los podemos llamar también clusters. Tendríamos que analizar cuales pueden ser los tamaños de bloque adecuados: Un tamaño de bloque grande hace que se desperdicie mucho espacio por la parte no utilizada. Por ejemplo, un bloque de 4KB, con un archivo de 96 bytes, desperdicia 4000 bytes. Un tamaño de bloque pequeño implica que cada archivo usará muchos bloques, lo que aumentará la complejidad (por ejemplo, en una lectura del archivo al tener que localizar todos los bloques que componen dicho archivo). Para manejar los bloques asociados a cada archivo, se pueden utilizar varias técnicas:

.1

Asignación Adyacente

Se almacenan los archivos mediante bloques adyacentes en el disco (así en el directorio sólo se tendrá que guardar la dirección en la que comienza el primer bloque, ya que los demás están a continuación). Esta técnica es fácil de implementar, pero es necesario conocer con anterioridad el número de bloques que ocupará el fichero y esto, en general, no ocurre (el archivo no podría crecer más allá de los bloques con que cuenta inicialmente). Además genera una gran fragmentación del disco que produce una pérdida de espacio.

Tema 8 – Sistemas Operativos

33

.2

Asignación en forma de Lista Enlazada.

El directorio contiene la dirección del primer bloque y cada bloque contiene la dirección del siguiente bloque o el valor null (0) en el caso de que sea el último bloque del fichero (la primera palabra de cada bloque se utiliza como puntero al siguiente y el resto del bloque contiene los datos). Con esta técnica se consigue aprovechar todos y cada uno de los bloques del disco y se evita perder capacidad por la fragmentación.

0 Bloque de archivo 0

Bloque de archivo 1

Bloque Físico: 4 7 14

0

Bloque de archivo 2

Bloque de archivo 3

Bloque de archivo 4

2

10

12

Bloque de archivo 0

Bloque de archivo 1

6

3

Bloque de archivo 2

11

Desventajas: o El retardo que se produce ya que se tienen que leer los bloques secuencialmente para poder llegar a un bloque intermedio. Y además estas operaciones se hacen en disco. o Cada bloque pierde parte de su capacidad (ya que se ha de reservar un espacio para contener la dirección del siguiente bloque).

.3

Asignación Mediante Lista Enlazada y Un Índice.

Se intenta eliminar los defectos de la anterior. Se toma la palabra del puntero de cada bloque del disco y se le coloca en una tabla o índice de memoria. En el directorio se asocia el número de bloque en el que comienza dicho archivo; con este dato y mediante la tabla se puede averiguar la dirección de todos los bloques que componen dicho archivo únicamente siguiendo la lista enlazada. Esta tabla se encuentra en memoria, con lo que las consultas son muy rápidas y no es necesario acceder a disco. Con esta organización, todo el bloque está disponible para los datos. Nº de bloque 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Siguiente bloque

10 11 7 3 2

El Archivo A comienza aqui El Archivo B comienza aqui

12 14 0 0

Tema 8 – Sistemas Operativos

34

Bloque de archivo 3

Mediante esta organización el acceso aleatorio es más sencillo. La principal desventaja es que toda la tabla de registros debe estar en la memoria principal permanentemente, con lo que la memoria consumida para almacenar la tabla no está disponible para ser usada por otros procesos Esto llega a ser un gran problema en el supuesto de discos con un gran número de bloques, ya que la tabla de registros puede llegar a ocupar gran parte de la memoria principal del ordenador o, incluso, desbordarla. MS-DOS utiliza este método. En este caso a la tabla de registros se le denomina FAT (File Allocation Table o Tabla de localización de ficheros) y se puede encontrar en distintas versiones: FAT12, FAT16, FAT32 (se diferencian en el tamaño de palabra del apuntador: 12 bits, 16 bits, etc. En FAT32 se aprovecha mucho más el espacio de memoria. VFAT=parche sobre FAT que permite los nombres largos). Ejemplo 4.1: Una FAT32 de W9x, con un disco de 8GB y bloques de 4KB, requiere unas 8MB de RAM únicamente para mantener toda la tabla en memoria. Ejemplo 4.2: Tenemos 3 archivos, el A con 4 bloques y el B y el C con 3 bloques. La FAT sería como la siguiente: x 0

x 1

EOF 2

13 3

2 4

9 5

8 6

7

4 8

12 9

3 10

11

EOF 12

EOF 13

14

15

Los espacios marcados con ‘x’ se reservarían para almacenar parámetros como el tamaño del disco, etc… Archivo A 6

→ 8

→ 4

Archivo B 5

→ 9

→ 12

Archivo C 10 → 3

→ 13

→ 2

En asociación con cada disco hay una tabla llamada FAT=File Allocation Table, de asignación de archivos:  Hay una entrada por cada bloque de disco  La entrada del directorio de cada archivo da el nº del primer bloque del archivo. FAT12 se utiliza actualmente en disquetes, FAT16 en tarjetas de memorias y llaves USB. FAT32 está destinado a discos que ya tengan cierta capacidad de almacenamiento para aprovechar su capacidad.

.4

Nodos-i (Nodos-Índice)

Entre los problemas que presenta la FAT es que los punteros de todos los archivos se combinan en la misma tabla al azar. Por tanto, se requiere, en potencia, toda la FAT aunque sólo se abra un archivo. Solución: Conservar las listas de bloques de diferentes archivos en lugares distintos. Con cada archivo existe una pequeña tabla llamada nodo-i. En cada nodo-i se guarda la

Tema 8 – Sistemas Operativos

35

información de los bloques que conforman el archivo, los permisos, contabilidad de uso…. Una aproximación gráfica a la estructura de un i-nodo sería: Tipo de fichero y permisos Numero de enlaces del fichero Información del propietario y grupo Tamaño del fichero en bytes Fechas (acceso, modificación, etc) Bloque directo 1 Bloque directo 2 ................. ................. Bloque directo 12 Bloque de indirección simple 13 Bloque de indirección doble 14 Bloque de indirección triple 15

Las últimas entradas del i-nodo se reservan para cuando el archivo ocupa más bloques de los que el i-nodo es capaz de almacenar y pueden contener la dirección de otro bloque en el que se guardan las demás direcciones de los bloques del archivo. A este bloque se le llama bloque indirecto. En el caso de que con este bloque extra no haya suficiente espacio para guardar todas las direcciones de los bloques del archivo, existe la posibilidad de utilizar un bloque doblemente indirecto e, incluso, un tercer bloque triplemente indirecto. UNIX utiliza este sistema. Ejemplo 4.3.: Si el tamaño de un bloque fuera de 1KB, si el archivo ocupa más de 10 KB (10 bloques directos), se busca un bloque libre, y ahí se almacenan los apuntadores a bloques que no caben en el directo. En el “Indirecto Individual” sólo se almacena la dirección de ese bloque libre. Si como hemos dicho anteriormente el bloque fuera de 1 KB, y la direcciones fueran de 32 bits, entonces el “Indirecto Individual” almacena 256 direcciones de bloques : 1 KB= 1024*8= 8192 bits, 8192/32 bits = 256 Direcciones Total: 10 directos + 256 Indirectos = 266 KB Si el archivo ocupa mas de 266 bloques (con bloques de 1 KB=266 KB), entonces se utiliza el “Indirecto Doble”. El bloque apuntado apunta a más bloques con punteros: 2562 = 65536 nuevos bloques (unas 64 MB) Total: 10 Directos + 256 Indirectos Indiv. + 65536 Indirectos Dobles=65802 Bloques ≈ 64.2 MB Para más de 65802 bloques utilizamos el Indirecto Triple, 256 3 = 16 GB, Total= 16 GB + 64 MB + 256 KB = 16.6 GB

Tema 8 – Sistemas Operativos

36

32 bits

Apuntadores a bloques de datos

Nodo-i

Guarda

10 Bloques Directos

la

dirección de un bloque

Indirecto Individual Indirecto Doble Indirecto Triple

.5

Este bloque almacena 256 apuntadores a bloques

NTFS Basado en parte en la filosofía de UNIX/Linux, pero más complejo aún.

Permite nombres de archivo de hasta 256 caracteres, ordenación de directorios, atributos de acceso a archivos, reparto de unidades en varios discos duros y registro de actividades. En Windows 2000 Server incluye mejoras que permiten utilizar el Directorio Activo, dominios, cuotas en disco para cada usuario, encriptación de archivos, almacenamiento remoto, una herramienta de desfragmentación y utilización de enlaces de archivos similares a los realizados en UNIX. Los bloques tienen un tamaño de 512 bytes - 4 KB El tamaño máximo de un archivo es de 16 Exabytes (2 60 = 1 Exabyte, 1000 Millones de GB), o bien estará limitado al tamaño del volumen.

.6

Implantación De Directorios

Antes de poder leer un archivo, éste debe ser abierto. Al abrir un archivo, el sistema operativo utiliza el nombre de la ruta de acceso dado por el usuario para localizar el dato en el directorio. El dato del directorio contiene la información necesaria

Tema 8 – Sistemas Operativos

37

para encontrar los bloques en el disco. Según el sistema, esta información podría ser la dirección en disco de todo el archivo, el número del primer bloque o el número del inodo. En todos los casos, la principal función del sistema de directorios es asociar el nombre ASCII del archivo con la información necesaria para localizar los datos. Bytes

8

3

1

10

2

2

2

4

Nombre del archivo

Extensión

Atributos

Reservado

Hora

Fecha

Nº del primer bloque

Tamaño

Directorio en MS-DOS Bytes

2 Nº de inodo Directorio en Unix-Linux

14 Nombre del archivo

Gestión de Periféricos (Entrada/Salida) 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. Este código resuelve las necesidades de sincronizar, atrapar interrupciones y ofrecer llamadas al sistema para los programadores.

Dispositivos De Entrada/Salida Los dispositivos de entrada/salida se dividen, en general en dos tipos: orientados a bloques y orientados a caracteres. Los 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 son: discos duros, la memoria, etc. Los orientados a caracteres son aquellos que trabajan con secuencias de bytes sin importar su longitud ni ninguna agrupación en especial. Ejemplos de estos dispositivos son el teclado, la impresora, monitor, etc. 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 o interrupciones periódicas. Sin embargo, todos están administrados por el sistema operativo por medio de una parte electrónica – mecánica y por una parte software.

.1

Reloj

Los relojes son esenciales para el buen funcionamiento de cualquier sistema porque juegan un papel decisivo en la sincronización de procesos, en la calendarización de trabajos por lote y para la asignación de turnos de ejecución entre otras tareas relevantes. Generalmente se cuenta con dos relojes en el sistema: uno que lleva la hora y fecha del mismo y que oscila entre 50 y 60 veces por segundo y el reloj que oscila entre 5 y 100 millones de veces por segundo y que se encarga de enviar Tema 8 – Sistemas Operativos

38

interrupciones a la CPU de manera periódica. El reloj de mayor frecuencia sirve para controlar el tiempo de ejecución de los procesos.

Controladores de Dispositivo Los controladores de dispositivo (también llamados adaptadores de dispositivos) son la parte electrónica de los periféricos, el cual puede tener forma de una tarjeta o un circuito impreso a la tarjeta maestra (placa base ) del ordenador. Los controladores de dispositivos generalmente trabajan con voltajes de 5 y 12 voltios con el dispositivo propiamente, y con el ordenador a través de interrupciones. Estas interrupciones viajan por un “bus” del ordenador y son recibidos por la CPU la 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 dispositivo” (device driver). Para intercambiar datos o señales entre el ordenador y los controladores, muchas veces se usan registros o secciones predefinidas de la memoria del ordenador. A este esquema se le llama “manejo de entrada/salida mapeado por memoria”

Acceso Directo a Memoria (DMA) Existen ciertas unidades de control que descargan a la CPU de las gestiones rutinarias asociadas a los periféricos o al control minucioso de las transferencias de información entre periféricos, o entre periféricos y la memoria principal. El controlador DMA sirve para transferir información de dispositivos rápidos de memoria masiva a la memoria principal y viceversa. La CPU carga en el controlador de DMA: o una instrucción indicando el sentido de la transferencia o el código del periférico involucrado o las posiciones de memoria principal y disco donde deben iniciarse las transferencias una vez hecho esto, la CPU genera una señal de control para indicar al DMA que actúe. Cuando el procesador DMA acaba la tarea encomendada por la CPU, envía a ésta una señal de petición de interrupción indicando con ello que está libre.

Principios del software de E/S El sistema operativo contiene los módulos software que comunican los programas con los controladores físicos que generan las señales de control para los periféricos. Objetivos del software de E/S del s.o.: .1 Lograr que los periféricos se utilicen con eficiencia. El s.o. gestiona los dispositivos de E/S, considerándolos de una de las dos siguientes formas:  Dispositivos de uso exclusivo: Asignar ciertos dispositivos (teclado, ratón, pantalla, impresora…) a un solo proceso durante la ejecución de éste.  Dispositivos compartidos: Dispositivos que pueden ser compartidos por varios procesos. El s.o. debe evitar los conflictos. Tema 8 – Sistemas Operativos

39

.2 Conseguir “independencia del dispositivo”: Desde el punto de vista del usuario y de las aplicaciones, las operaciones de E/S deben ser lo más generales posibles. Permite diseñar programas que utilicen archivos y dispositivos de forma abstracta, sin particularizar para un dispositivo concreto. Ejemplo 5.1: En Unix, Linux, NT, los dispositivos se referencian como si fueran archivos especiales: Numero=read(descriptorArchivo, zona, numB) Donde los campos tienen el siguiente significado: Numero: es el nº real de bytes leídos, descriptorArchivo: es el nombre simbólico que se le ha dado al periférico. Zona: Donde se guardan los datos en MP. numB: nº de bytes (teóricos) que pretendemos leer del dispositivo. Los objetivos se logran estructurando el software de E/S en niveles:

5. Programas de usuario 

Llamadas al sistema

Peticiones Satisfechas



4. Sw de E/S independiente del dispositivo 

Peticiones de E/S

Peticiones Satisfechas



3. Organización física 

Peticiones de E/S

Peticiones Satisfechas



2. Controlador/Gestor SW del dispositivo Instrucciones al controlador

Petic. De interrupción



1. Hw (controlador Hw y dispositivos de E/S)

En el nivel 5 (software para usuarios): Parte del Software que el usuario tiene cierto control sobre los dispositivos, como por ejemplo la sentencia printf en lenguaje C. En el nivel 4 (software de E/S independiente del dispositivo): La función básica consiste en ejecutar las funciones de E/S que son comunes a todos los dispositivos o por lo menos a grupos de ellos (abrir, cerrar, leer, escribir) y proporcionar una interfaz uniforme al software a nivel de usuario. En NT, Unix, Linux, se utilizan los dispositivos como archivos especiales. En el nivel 3(manejadores de dispositivo): El sistema debe proveer los drivers necesarios para los periféricos que necesite controlar, así como ocultar las peculiaridades del manejo interno de cada uno de ellos, tales como el formato de la información, los medios mecánicos, los niveles de voltaje y otros. Se puede decir que todo el código del dispositivo está en los drivers.

Tema 8 – Sistemas Operativos

40

Se tiene en cuenta ya a los dispositivos de forma específica: impresora, teclado, ratón… Se forman bloques físicos de información (en el nivel 4 se veían como un flujo continuo). Gestiona el almacenamiento intermedio de la RAM: caché de E/S en UNIX, caché de archivos en NT. Convierte las referencias lógicas (del nivel superior) en direcciones físicas, teniendo en cuenta la estructura física del dispositivo de E/S. En el nivel 2 (manejador de interrupciones): El primer objetivo referente a los manejadores de interrupciones consiste en que el programador o el usuario no deben darse cuenta de los mecanismos de bajo nivel para los casos en que el dispositivo está ocupado y se debe suspender el proceso o sincronizar algunas tareas. Desde el punto de vista del proceso o usuario, el sistema simplemente tardó más o menos tiempo en responder a su petición. En este nivel nos encontramos con las siguientes funciones: Planificación y control Generación de instrucciones de E/S para el Hw. Atención a las interrupciones

Tema 8 – Sistemas Operativos

41

Anexo sobre FAT16, VFAT, FAT32 Todo dispositivo para el almacenamiento de datos debe ser formateado antes de su uso; es decir, que se le debe dar un cierto formato lógico que indique cómo será almacenada la información: el tamaño de los paquetes, la forma en que se distribuyen, los atributos posibles de los archivos (nombre, tipo, fecha...) y otras características que definirán un tipo de sistema de archivo concreto. En el mundo PC el sistema de archivo más extendido es el FAT16 de las versiones de DOS superiores a la 3 y del Windows 95 original, usado en los disquetes y la mayoría de los discos duros. La VFAT (FAT Virtual) de Windows 95 que permite nombres largos no es más que un parche sobre este sistema de archivo, no un sistema de archivos en sí. El otro sistema en rápida extensión es el FAT32 de Windows 98, ME y de la versión OSR-2 de Windows 95 (la "4.00.950B", como se identifica a sí misma en el icono de Sistema del Panel de control). Las ventajas de este sistema de archivo frente al anterior radican en que es de 32 bits y tiene un tamaño de cluster muy pequeño, lo que le hace capaz de admitir grandes discos duros y aprovecharlos muy bien, además de no necesitar artificios como VFAT para usar nombres largos de archivo. Vayamos por partes; primero, los clusters; son como "cajones" en que el disco duro está dividido, en los cuales se guardan los archivos. Se da la peculiaridad de que un cluster no puede ser compartido por dos archivos distintos, por lo que si tenemos un tamaño de cluster de 16 Kb y queremos guardar un archivo que ocupa 17 Kb, se repartirá en dos clusters, ocupando uno entero y sólo 1 Kb del otro; el resto (15 Kb) se desperdiciará. Sí, ha leído bien; ¡tiraremos el 47% del espacio!! . Y esto no es nada, ya verá. Lo mismo ocurre si queremos almacenar un archivo que ocupa sólo 1 byte; si el cluster es de 16 Kb (16.384 bytes), se desperdiciarán totalmente 16.383 bytes, ¡el 99,99% del espacio!! Como comprenderá, en estas condiciones resulta muy importante mantener el tamaño del cluster lo menor posible para minimizar las pérdidas que ocasionan estos archivos, especialmente los muy pequeños. Observe la tabla a continuación que relaciona el tamaño de las particiones (a continuación explicaremos qué son) con el tamaño del cluster en FAT16 y en FAT32: Tamaño de la partición FAT16 Hasta 2 GB Menos de 1 GB Menos de 512 MB Menos de 256 MB Menos de 128 MB FAT32 A partir de 8 GB Menos de 8 GB

Tamaño del cluster 32 Kb 16 Kb 8 Kb 4 Kb 2 Kb 8 Kb 4 Kb

En cuanto al tamaño de los discos, no es difícil de entender; si el sistema de archivo da direcciones de archivo de 16 bits, esto nos da 2 elevado a 16 = 65.536

Tema 8 – Sistemas Operativos

42

direcciones, que a un máximo de 32 Kb por cluster son 2.097.152 Kb, es decir, 2 GB como máximo para FAT16. ¿Quiere esto decir que no podemos usar discos de más de 2 GB? No, afortunadamente; pero implica que deberemos dividirlos en varias particiones, que son cada una de las divisiones lógicas (que no físicas) de un disco, las cuales se manejan como si fueran discos duros separados (con su propia letra de unidad e incluso con diferentes tipos de sistema de archivo si lo deseamos). Por ejemplo, un disco de 3,5 GB debe dividirse al menos en dos particiones de 2 GB o menos cada una para usarlo con FAT16. Para FAT32 el cálculo es similar, aunque no se usan los 32 bits, sino "sólo" 28, lo que da un máximo de ¡¡2.048 GB por partición!! (2 Terabytes) usando clusters de 8 Kb. Sin duda no necesitaremos hacer más de una partición al disco... Observe que para mantener el mismo tamaño de cluster de 4 Kb en un disco de 2 GB, en FAT16 necesitaríamos al menos 8 particiones de como mucho 255,9 MB, mientras que en FAT32 nos bastaría con una. Indudablemente, aunque no podamos instalar FAT32 resulta preferible perder algo de espacio a tener que manejar un disco subdividido en unidades "C", "D", "E", "F"... y así hasta "J". Para terminar, tres consideraciones: Primero, la ganancia de espacio al pasar de FAT16 a FAT32 es enorme, varios cientos de MB en un disco de un par de GB, y en mi opinión ésta es la mejor (y casi única) ventaja de Windows 98 frente a Windows 95 (no frente a la versión OSR-2, que ya tiene soporte para FAT32). Segundo, ambos sistemas son incompatibles a nivel de utilidades de disco. Léase las Norton, las utilidades de defragmentación (por cierto, defragmentar es organizar un poco todos esos trozos de archivo que andan dispersos en decenas de clusters separados en el disco duro), los compresores de disco y demás. Si instala FAT32, deshágase de su software antiguo para estos menesteres o el follón puede ser enorme. Y tercero, no son los únicos sistemas de archivo, ni mucho menos los mejores. En el caso de la FAT16 supongo que ya se lo esperaba, pero es que la FAT32 tampoco es una maravilla; por ejemplo, carece de características de seguridad implícitas en el sistema de archivo (como acceso restringido a determinados usuarios) o bien auto-compresión de los archivos, características que sí tienen sistemas más avanzados como los de Unix y Linux, el de 32 bits de OS/2 (HPFS) y el de 32 bits del mismísimo Windows NT (NTFS). ¿Por qué Microsoft inventó el FAT32 teniendo ya el muy eficiente NTFS? Misterios de la vida, amigos...

Tema 8 – Sistemas Operativos

43