EL SISTEMA OPERATIVO UNIX

CONTENIDOS:

1. Introducción.

2. Estructura del Sistema.

3. La visión del usuario.

4. Estructura general del núcleo.

5. El Subsistema de Ficheros UNIX.

5.1. Descripción general del Subsistema de Ficheros.

5.2. Inode.

5.3. Estructuración de la información en ficheros.

5.4. Los directorios UNIX.

5.5. Asignación del espacio en disco.

5.6.Llamadas al Sistema.

6. El Subsistema de Control de procesos.

6.1. Descripción general de un proceso.

6.2. Estructura de los procesos UNIX.

6.3. Manejo de Memoria.

6.4. Planificación de procesos.

6.3. Llamadas al Sistema para el control de procesos.

7. El Subsistema de Entrada/Salida.

7.1. Interfases de manejadores de dispositivos.

7.2. Configuración del Sistema.

7.3. Llamadas al Sistema.

1. Introducción.

El sistema operativo UNIX proporciona un entorno adecuado y común de operación a sus usuarios. Su gran popularidad se debe, entre otras causas, a su capacibilidad de funcionamiento tanto en pequeños ordenadores (microordenadores) como en poderosos sistemas de computación. El sistema UNIX posee dos partes bien diferenciadas: la parte "visible" a los usuarios constituida por una serie de programas y servicios (compiladores, procesadores de texto, etc) y una segunda parte formada por el sistema operativo que soporta a estos programas y servicios. Estas dos partes funcionan como un todo, resultando al final un sistema cuyas características las podríamos resumir en:

- Sistema construido en un lenguaje de alto nivel; debido a ello es fácil su comprensión, posibles cambios y traslado a otras máquinas.

- Ofrece primitivas que facilitan la construcción de aplicaciones complejas.

- Sistema de ficheros eficiente y de fácil manejo.

- Uniformidad en el tratamiento de ficheros; tratándolos como cadenas de bytes.

- Interfase simple y coherente con los dispositivos de E/S.

- Proporciona un entorno multiusuario y multiprogramación.

2. Estructura del sistema.

La figura 1 muestra la arquitectura de alto nivel de UNIX. El hardware, que está en el centro de la figura, proporciona los servicios básicos al sistema operativo. A continuación nos encontramos con el núcleo del sistema operativo que aisla las especificidades hardware del usuario; esto hace que los programas bajo UNIX puedan moverse entre máquinas distintas. Seguidamente aparecen las capas más externas que se comunican con el núcleo a través de las llamadas al sistema; en estas capas estarán por un lado los comandos del sistema y por otro lado los programas de aplicación diseñados por los usuarios.

Como resumen podemos decir que bajo el nombre de UNIX se engloba a un conjunto de subsistemas y programas que utilizan los servicios que el núcleo les proporciona a través de las llamadas al sistema. En este sentido cabe decir que el sistema operativo UNIX contempla 64 llamadas al sistema estándares que deben ser soportadas en cualquier versión, por ejemplo: Solaris para estaciones sun, SCO UNIX para PCs , HP-UX para equipos Hewlett Packard, AIX para IBM, etc.

3. La visión del usuario.

En esta sección se describen brevemente los rasgos de alto nivel de UNIX, concretamente se pasa revista al sistema de ficheros y al entorno de procesos. El sistema de ficheros de UNIX se organiza en forma de árbol, tal y como se representa en la figura.

Existe una única raiz, root, que se denota por "/", cada nodo no hoja es un directorio de ficheros, los nodos hojas pueden ser directorios, ficheros normales o ficheros especiales. El nombre de un fichero viene dado por su path_name que especifica como localizar el fichero en la estructura jerárquica.

Los programas bajo UNIX deben interpretar los datos contenidos en los ficheros. La sintaxis de acceso a los datos de un fichero es la misma para todo programa y es definida por el sistema, en cambio, la semántica de los datos es soportada por los programas.

Los directorios son ficheros cuya información especifica los nombres de los ficheros contenidos en ellos, en este sentido, éstos son ficheros normales cuya particularidad es que sus datos sólo pueden ser accedidos por un conjunto de primitivas para el manejo de directorios.

En cuanto a los ficheros especiales, los más importantes son los ficheros asociados a dispositivos, ya que UNIX de cara a los usuarios, trata a los dispositivos como si fuesen ficheros. Debido a ello, los usuarios podrán acceder a los dispositivos utilizando la misma sintaxis que se emplea para el acceso a los ficheros de datos corrientes. En cuanto a los usuarios se contemplan tres categorias: el propietario, el grupo y demás usarios. Cada fichero tendrá asociado unos permisos de acceso para cada categoría de usuario. Finalmente se resumen algunas de las características relevantes del sistema de ficheros UNIX:

- Estructura jerárquica.

- Tratamiento coherente de los ficheros.

- Capacidad de crear y borrar ficheros.

- Crecimiento dinámico de los ficheros.

- Protección de ficheros.

- Tratamiento de los dispositivos periféricos como ficheros.

En cuanto al entorno de procesos, el sistema operativo UNIX permite la multitarea. Para UNIX un proceso es simplemente un programa en ejecución siendo un programa un fichero ejecutable. UNIX dispone de varias llamadas al sistema para la creación, sincronización y finalización procesos, así como para el control de la respuestas a eventos. Seguidamente se describen algunas de estas llamadas al sistema:

fork: Crea un nuevo proceso. Al proceso creador se le llama "padre" y el proceso creado es llamado "hijo".

exit: Finaliza un proceso. Todo proceso debe acabar su ejecución con una llamada a este servicio.

wait: Suspende la ejecución del proceso llamador hasta que finalice un determinado proceso. Este servicio es típico en la sincronización de procesos.

Un ejemplo de proceso padre es el shell, intérprete de comandos de UNIX, su misión es interpretar la primera palabra de una línea de comando como una orden; de forma que el resto de las palabras de la línea de comando son tratadas como argumentos. Para ejecutar dicha orden se crea un proceso hijo que se encargará de la ejecución del comando. El shell reconoce tres tipos de comandos:

- Internos, intrínsecos o residentes: Contenidos en el própio código del shell.

- Externos, extrínsecos o trasintorios: Sus códigos están contenidos en ficheros ejecutables que se han de cargar en memoria cada vez que se invoquen.

- Ficheros batch: Ficheros que contienen una secuencia de líneas con comandos de cualquier tipo.

UNIX distingue dos tipos de modo de ejecución durante la vida de cualquier proceso:

Modo usuario: Los procesos en modo usuario sólo pueden acceder a sus própios datos y direcciones. Un proceso en modo usuario podrá pasar a modo sistema si ejecuta una instrucción privilegiada a trarvés de una llamada al sistema.

Modo sistema: Los proceso en modo sistema pueden acceder a sus datos y direcciones tanto suyas como de cualquier otro proceso.

El núcleo proporciona una serie de servicios. Aparte de los ya mencionados, destacan:

- Control de la ejecución de procesos permitiendo la creación suspensión y comunicación.

- Servicios para la correcta planificación de los procesos. El recurso de CPU es compartido por los procesos mediante un esquema de tiempo compartido.

- Asignación de memoria principal para la ejecución de un proceso. Se permite la compartición de memoria por parte de varios procesos bajo ciertas condiciones.

- Control del acceso a los periféricos por parte de los procesos.

4. Estructura general del núcleo.

El modelo de sistema UNIX se fundamenta en base a dos conceptos: fichero y proceso. La siguiente figura muestra una visión lógica del núcleo con sus módulos y las relaciones existentes entre ellos.

Se pueden distinguir tres niveles: nivel de usuario, nivel de núcleo y nivel hardware. La interfase entre el nivel de usuario y el núcleo se realiza mediante las llamadas al sistema y las librerías del sistema. El conjunto de llamadas al sistema se dividen en dos grupos: las que interaccionan con el subsistema de ficheros y las que lo hacen con el subsistema de control de procesos.

El subsistema de ficheros es el responsable de:

- Manejo de ficheros.

- Control de acceso a los ficheros.

- Gestión del espacio libre.

- Administración de los datos.

Los procesos interaccionan con este subsistema haciendo uso de llamadas al sistema tales como: open, close, read, write, chmod, chown, etc. El subsistema de ficheros accede a los datos usando la técnica de buffering, que regula el flujo de datos entre el núcleo y los dispositivos de almacenamiento secundario. El mecanismo de buffering interactúa a su vez con los manejadores de dispositivos de E/S cada vez que se realiza una transferencia de datos. Sin embargo, existe la posibilidad de que el subsistema de ficheros opere directamente con los manejadores de dispositivos evitando así el uso de los buffers; para ello se utilizan las cola de E/S y una serie de servicios de bajo nivel.

El subsistema de control de procesos es responsable de la sincronización y comunicación entre procesos y el manejo y la gestión de la memoria. El subsistema de ficheros interactúa con este subsistema cada vez que un fichero ejecutable es cargado en memoria para su ejecución. Algunas de las llamadas al sistema para control de procesos son: fork, exec, exit, wait, signal, brk, etc.

El módulo de manejo de memoria controla el espacio de memoria haciendo uso de la técnica swapping, soportando generalmente memoria virtual. En cuanto al módulo gestionador de CPU (planificador), éste gestiona el uso de la CPU por parte de los procesos; la política de planificación de CPU consiste en desasignar la CPU a un proceso cuando éste pida otro recurso, o bien, cuando a éste se le cumpla su rodaja de tiempo de uso de CPU, entonces el gestionador elige al proceso de mayor prioridad para su ejecución. La comunicación entre procesos es posible a través de diferentes mecanismos: semáforos, señales, mensajes, memoria compartida y pipes.

Finalmente el módulo de control del hardware es responsable del manejo de las interrupciones y de la comunicación con la máquina. Dispositivos tales como terminales o discos pueden interrumpir a la CPU mientras un proceso es ejecutado. Si es así, el núcleo puede reanudar la ejecución del proceso interrumpido una vez atendida la interrupción. El tratamiento de las interrupciones se lleva a cabo por medio de funciones especiales del núcleo (no por procesos especiales).

5. El subsistema de ficheros UNIX:

5.1. Descripción del subsistema de ficheros:

Cada fichero en UNIX tiene asociado una estructura de control llamada inode que contiene la descripción del fichero: localización en el disco, permisos de accesos, propietarios y tiempos de acceso. Cuando un proceso hace referencia a un fichero por su nombre, el núcleo localiza su inode asociado y comprueba los permisios de acceso. La creación de un inode lleva consigo la asignación de un inode no usado. Los inodes se localizan en memoria secundaria, siendo transferidos por parte del núcleo a memoria principal; concretamente a una tabla llamada tabla de inodes.

El núcleo utiliza otras dos tablas: la tabla de ficheros y la tabla de descriptores de ficheros de usuario. La tabla de descriptores de ficheros de usuario se asocia a cada proceso y tiene por finalidad identificar los ficheros abiertos por un proceso. En cuanto a la tabla de ficheros, ésta contiene la siguiente información: desplazamiento en bytes y los permisos de acceso asociados. La siguiente figura muestra muestra las tablas descritas y la relación existente entre ellas.

Cuando se producen llamadas al sistema para abrir o crear un fichero, el núcleo devuelve un descriptor de fichero el cual es un índice dentro de la tabla de descritores de ficheros de usuario. Cuando se producen lecturas o escrituras, el núcleo utiliza la tabla de descriptores de ficheros para obtener el puntero que permita acceder a la tabla de ficheros y a la tabla de inodes donde se encuentra el inode asociado al fichero en cuestión, a partir de su información se podrán localizar los datos a acceder. UNIX, debido a la diferencia de tiempos de acceso entre las cintas y discos, utiliza estos últimos como memoria secundaria sobre los cuales construye sus sistemas de ficheros. Una instalación bajo UNIX puede soportar varias unidades físicas de disco, conteniendo cada una de ellas uno o varios sistemas de ficheros, siendo uno de ellos el sistema de ficheros root (de arranque). Cada sistema de ficheros se denomina dispositivo lógico y la conversión entre dispositivo lógico y físico es responsabilidad del manejador de dispositivo que forma parte del núcleo.

Internamente un sistema de ficheros consiste en una secuencia de bloques de bytes; cada uno de 512, 1024, 2048 o cualquier múltiplo de 512 dependiendo del tamaño elegido en el momento de la creación del sistema. El tamaño de los bloques lógicos es el mismo para cada sistema de ficheros, en cambio puede ser distinto para sistemas de ficheros diferentes. Cada sistema de ficheros posee la siguiente estructura:

- Si es de tipo root (de arranque), comenzará con un bloque "boot" que ocupa el principio del sistema de ficheros, normalmente el primer sector, que puede contener el código de bootstrap.

- El super-bloque que describe el estado del sistema de ficheros, ésto es: tamaño, espacio libre, etc.

- Lista de inodes cuyo tamaño es especificado por el administardor del sistema cuando se crea el sistema de ficheros.

- Los bloques de datos que empieza despues de la lista de inodes.

5.2. Inode.

Como ya se mencionó anteriormente, UNIX asigna para cada fichero un único inode. Esta estructura de control almacena la información necesaria para que los procesos puedan acceder a la información a través del núcleo. La informción contenida en inode se estructura de la siguiente forma:

- Identificador de propietario.

- Tipo de fichero: Regulares, Directorio, Especiales de caracter, Especiales de bloque y Pipes.

- Número de Links asociados.

- Direcciones de los bloques de datos en disco.

- Tamaño del fichero. Se define como el mayor offset que puede soportar más uno.

Cuando el inode ha sido transferido de disco a memoria, el núcleo le añade la siguiente información:

- Estado del inode:

* El inode está bloqueado.

* Un proceso está esperando a que se desbloquee.

* El inode se ha actualizado modificando algún campo suyo.

* El inode se ha actualizado debido a una actualización de los datos del fichero asociado.

- El número lógico de dispositivo que contiene al sistema de ficheros.

- Número de inodes en la lista de inodes de disco.

- Puntero a otro inode en memoria.

- Número de veces que el fichero asociado se ha abierto.

5.3. Estructuración de la información en ficheros.

Como ya se dijo anteriormente cada inode asociado a un fichero UNIX posee una tabla de direcciones de los bloques de disco que contiene los datos del fichero. Por defecto todo inode contiene una tabla de 13 entradas y cada entrada puede ser: directa, indirecta, doble indirecta o triple indirecta. Una entrada directa contiene la dirección de un bloque de datos del fichero. Una entrada indirecta contiene la dirección de un bloque de disco que contiene una tabla directa. Una entrada doble indirecta contiene la dirección de un bloque de disco que contiene una tabla indirecta. Por último, una entrada triple indirecta contiene la dirección de un bloque de disco que contiene una tabla doble indirecta.

Debido al compromiso existente entre flexibilidad en el crecimiento de ficheros y el tiempo de acceso a la información, las distintas implementaciones de UNIX fijan el número máximo de entradas no directas que un fichero puede tener, así por ejemplo:

* AT&T UNIX ver. 6:

En un inode hay 8 entradas:

Ficheros pequeños (Small Files): 8 entradas directas.

Ficheros grandes (Large Files): 7 entradas indirectas y una doble indirecta.

* AT&T UNIX ver. 7:

Bloques de 512 bytes.

En un inode hay 13 direcciones de bloque.

10 entradas directas.

1 entrada indirecta.

1 entrada doble indirecta.

1 entrada triple indirecta.

* AT&T UNIX system V:

Bloques de 1 Kbytes.

Mismo esquema de direccionamiento que el anterior.

5.4. Los directorios UNIX.

Un directorio UNIX es un fichero que proporciona estructura jerárquica al sistema de ficheros, a través de ellos se transforman los nombres de los ficheros dados por los usuarios, en el número de inode asociado. Cada directorio está constituido por una secuencia de entradas conteniendo cada una de ellas:

- Número de inode asociado (2 bytes) .

- Nombre del fichero (máximo 14 caracteres).

La siguiente figura ilustra la estructura interna de un directorio.

5.5. Asignación del espacio en disco.

Para entender como se gestiona el espacio en disco en UNIX hay que tener presente la estructura interna del super-bloque, característico de cada sistema de ficheros, construido en UNIX con el comando mkfs. Un super-bloque en UNIX posee la siguiente información:

- Tamaño del sistema de ficheros.

- Número de bloques libres en el sistema de ficheros.

- Lista de bloques libres en el sistema de fichero.

- Un indice a esta lista para asignar el próximo bloque.

- Tamaño de la lista de inodes.

- Número de inodes libres en el sistema de ficheros.

- Lista de inodes libres en el sistema de ficheros.

- Indice del próximo inode libre a asignar.

- Campos de bloqueo de acceso a la lista de bloques libres y de inodes.

- Un flag que indica que el super-bloque ha sido cambiado.

Cuando el comando mkfs crea un sistema de ficheros, éste construye en el super-bloque una lista de bloques libres de forma que cada entrada contiene la dirección de un bloque de disco disponible. La última entrada contiene la direccón de un bloque de disco que posee otra lista de bloques libres cuya organización es la misma que la anterior. Así pues, cuando se necesita espacio en disco, el núcleo acude a la copia del super-bloque en memoria (cuando se monta un sistema de ficheros, mount, su super-bloque se transfiere a memoria principal) para tomar el siguiente bloque disponible. En el caso de que éste sea el último de la lista de bloques libres; entonces no es considerado como un bloque libre de datos, sino que es tomado como un bloque que contiene otra lista de bloques libres. Cuando ocurre lo anterior, el núcleo procede a transferir dicha lista a la zona del super-bloque en memoria destinada a contener dicha lista.

5.6. Llamadas al sistema del subsistema de ficheros.

En la siguiente figura se ilustra el conjunto de algoritmos y llamadas al sistema del subsistema de ficheros:

- I	Llamadas que retornan un descriptor de fichero.

- II	Llamadas que usan namei.

- III	Llamadas que necesitan inode libres; ialloc y ifree.

- IV	Llamadas para asignar o cambiar atributos.

- V	Llamadas de E/S; alloc, free y algoritmos de buffers.

- VI	Llamadas que cambianla estructura del sistema de ficheros.

- VII	Llamadas que cambian la organización de los ficheros.

Algoritmos de bajo nivel del subsistema de ficheros.

En este apartado vamos a describir de forma algoritmica algunas de las tareas más básicas del subsistema de ficheros UNIX.

Obtención del inode asociado al nombre de un fichero:

El algoritmo que realiza esta acción es namei, antes de pasar a estudiar este algoritmo se debe tener en cuenta como estan estructurados internamente los ficheros directorios.

Algoritmo:	namei

Entrada:	Path name del fichero

Salida:	inode bloqueado

"Si" (path name comienza desde la raíz) "Entonces"

inode de trabajo = inode de la raíz ;

"Si no"

inode de trabajo = inode del directorio actual ;

Fin si"

"Mientras" (Existan componentes en el path name) "Hacer"

Extraer siguiente componente del path name ;

Verificar que el inode de trabajo es de un directorio ;

Verificar accesos ;

"Si" (inode de trabajo es del root y la componente es "..") "Entonces" continue ;

Leer directorio asociado al inode de trabajo ;

Buscar la componente actual en dicho fichero ;

"Si" (Exito en la búsqueda) "Entonces"

Extraer número de inode asociado ;

Liberar inode de trabajo ;

inode de trabajo = inode buscado ;

"Si no"

return(no inode) ;

"Fin si"

"Fin mientras"

Return (inode de trabajo) ;

Obtener dirección de los datos asociados al offset de un fichero:

Esta tarea se implementa a través del algoritmo bmap. Antes de pasar a leer dicho algoritmo se debe recordar la organización de los datos en un fichero UNIX.

Algoritmo:	bmap

Entrada:	(1) inode

(2) Offset en bytes

Salida:	(1) Número de bloque del sistema de fichero

(2) Offset en bytes dentro del bloque

(3) bytes de E/S dentro del bloque

(4) flag de indirección

Calcular número de bloque lógico del fichero ;

Calcular Offset dentro del bloque lógico ; /* salida 2 */

Calcular bytes de E/S en el bloque ; /* salida 3 */

Comprobar si existe indexación de bloques ; /* salida 4 */

Determinar nivel de indexación ;

"Mientras" (no final de indexación) "Hacer"

Calcular índice dentro del inode o del bloque indirecto ;

Obtener número del bloque de disco a acceder ;

Liberar buffer de la lectura previa ;

"Si" (final de indexación) "Entonces" return(número de bloque); /* salida 4

Leer bloque indirecto de disco ;

Ajustar número de bloque lógico según nuevo nivel ;

"Fin mientras"

Asignación de un In_core inode a un inode del sis. de ficheros:

Esta labor se realiza a través de la implementación del algoritmo iget. Antes de pasar a leer este algoritmo repase los conceptos de inode del sistema de ficheros y de In_core inode.

Algoritmo:	iget

Entrada:	número de inode del sistema de ficheros

Salida:	inode bloqueado

"Mientras" ( ) "hacer"

"Si" (inode ya es In_core inode) "Entonces"

"Si" (inode bloqueado) "Entonces"

sleep (evento: inode no bloqueado) ;

continue ;

"Fin si"

"Si" (inode en lista de inodes libres) "Entonces"

borrarlo de la lista de inodes libres ;

"Fin si"

Incrementar número de referencias del inode ;

return(inode) ;

"Fin si"

"Si" (lista de inodes libres vacía) "Entonces" return(error) ;

Extraer entrada de la lista de inodes libres ;

Colocar inode el la tabla de inodes del sistema ;

Leer inode desde disco ;

Inicializar inode ;

return(inode) ;

"Fin mientras"

Liberamos un In_core inode:

Esta tarea se realiza a través del algoritmo iput.

Algoritmo:	iput

Entrada	puntero a un In_core inode

Salida:	ninguna

Bloquear inode si aún no está bloqueado ;

Decrementar las referencias del inode ;

"Si" (referencias = 0) "Entonces"

"Si" (contador de link del inode = 0) "Entonces"

Liberar bloques de disco del fichero ;

Poner el tipo de fichero a cero ;

Liberar inode ;

"Fin si"

"Si" (fichero accedido o inode alterado) "Entonces" Actualizar inode en disco Poner inode en la lista de inodes libres ;

"Fin si"

desbloquear el inode ;

Asignación de un inode del sistema de ficheros a un fichero:

Esta tarea se realiza a través de la implementación del algoritmo ialloc. Para entender este algoritmo es conveniente tener claro como se organizan los inodes en el super_bloque de disco y diferenciarlos de los In_core inodes. También hay que tener presente que cuando un sistema de ficheros se monta se crea una lista inodes libres en memoria. Esta lista proviene de la lista de inodes libres del superbloque de disco y es más pequeña que esta; de ahí que cuando en la lista de inodes libres de un superbloque en memoria está vacía se desencadena un proceso de búsqueda de inodes libres de la lista de inodes libres del superloque en disco. Este proceso de búsqueda tiene la particularidad que se empieza en un inode marcado como inode de referencia que no es otro que aquel de mayor número, de esta manera se reduce considerablemente el tiempo de búsqueda de inodes libres.

Algoritmo:	ialloc

Entrada:	sistema de ficheros

Salida:	inode bloqueado

"Mientras" ( ) "Hacer"

"Si" (super_bloque bloqueado) "Entonces"

sleep (evento: superbloque no bloqueado) ;

continue ;

"Fin si"

"Si" (Lista de inodes del superbloque vacía) "Entonces"

bloquear superbloque ;

Obtener inode marcado para búsqueda de inodes libres;

Buscar inodes libres de disco hasta llenar la lista ;

Desbloquear el superbloque ;

wake up (evento: superbloque no bloqueado)

"Si" (no se encontraron inodes libres) "Entonces" return(no inode) ;

Obtener el inode de referencia para busquedas ;

"Fin si"

Obtener número de inode de la lista de inodes libres ;

Asignarle un In_core inode (iget) ;

"Si" (inode no disponible) "Entonces"

Escribir inode en disco ;

Liberar inode (iput) ;

continue ;

"Fin si"

Inicializar inode ;

Escribir inode en disco ;

Decrementar inodes libres del sistema de ficheros ;

return(inode) ;

"Fin mientras"

Liberamos un inode del sistema de ficheros:

Esta tarea se realiza a través del algoritmo ifree.

Algoritmo:	ifree

Entrada:	número de inode del sistema de ficheros

Salida:	ninguna

Incrementar número de inodes libres del sistema de ficheros;

"Si" (superbloque bloqueado) "Entonces" return ;

"Si" (lista de inodes libres llena) "Entonces"

"Si" (número de inode < marca de búsqueda) "Entonces"

marca de búsqueda = número de inode ;

"Si no"

Almacenar número de inode en la lista de inodes

libres ;

"Fin si"

return ;

"Fin si"

Asignación de un bloque de datos del sistema de ficheros:

Esta tarea se realiza a través del algoritmo alloc. Para pasar a la descripción de este algoritmo es necesario recordar como estaban organizados los bloques libres en un sistema de ficheros y como se accedían a ellos a través del superbloque del sistema de ficheros.

Algoritmo:	alloc

Entrada:	número de sistema de ficheros

Salida:	buffer para el nuevo bloque

"Mientras" (superbloque bloqueado) "Hacer"

sleep (evento: superbloque no bloqueado) ;

"Fin mientras"

Extraer un bloque libre de la lista de bloques libres ;

"Si" (es el último bloque de la lista) "Entonces"

bloquear superbloque ;

Leer el bloque ;

Copiar números de bloques en el superbloque ;

Desasignar buffer del bloque ;

desbloquear superbloque ;

wake up (evento: superbloque no bloqueado) ;

"Fin si"

Obtener buffer para el bloque extraido de la lista ;

Decrementar número total de bloques libres ;

Marcar superbloque como modificado ;

return buffer ;

Llamadas al sistema:

En esta sección se describirán las llamadas al sistema de UNIX del subsistema de ficheros. En algunas se presentarán sus algoritmos asociados y en otras nos limitaremos a describir su sintaxis y acciones que realizan.

* open:

La llamada al sistema open debe ser invocada simpre que un proceso quiera hacer uso de un fichero. Retornará un valor entero (descriptor de fichero) que es un índice en la tabla de descriptores de ficehros de ususario del proceso invocador.

int open(pathname,flags,modo)

pathname:	nombre del fichero

flags:	modo de apertura del fichero

modo:	permisos de acceso

Convertir pathname a inode (namei) ;

"Si" (fichero no existe o acceso denegado) "Entonces" return(error) ;

Asignarle una entrada en la tabla de ficheros del sistema ;

Asignar una entrada en al tabla de descriptores del proceso;

"Si" (apertura de truncamiento) "Entonces"

Liberar todos los bloques del fichero (free)

unlock(inode) /* bloqueado préviamente por namei */

return(descriptor de fichero) ;

* read:

La llamada al sistema read lee bytes de información de un fichero especificado por su descriptor asociado. Retornará el número de bytes leidos que siempre será menor o igual que el número especificado en la llamada.

int read(fd,buffer,count)

fd:	descriptor de fichero

buffer:	destino de la información leida

count:	número de bytes a leer

Extraer información de la tabla de descriptores;

Chequear permisos de acceso ;

Ubicar parámetros de la llamada en la U_area del proceso ;

Obtener inode de la tabla de ficheros del sistema ;

Bloquear inode ;

Poner el offset del fichero en al U área ;

"Mientras" (cuenta no satisfecha) "hacer"

Convertir Offset a dirección de bloque (bmap) ;

Calcular offset dentro del bloque ;

Número de bytes a leer;

"Si" (número de bytes a leer = 0 ) "Entonces" break ;

Leer bloque ;

Copiar bytes en el buffer de usuario ;

Actualizar parámetros de la llamada en la U área ;

Liberar buffer del sistema de transferencia ;

"Fin mientras"

Desbloquear inode ;

Actualizar Offset del fichero en la tabla de ficheros ;

return(número de bytes leidos) ;

* write:

La llamada al sistema write efectua la escritura desde memoria de usuario a un fichero. Tanto la sintaxis como el algoritmo de esta llamada son análogos a los de la llamada read.

int write(fd,buffer,count)

fd:	descriptor de fichero

buffer:	destino de la información leida

count:	número de bytes a escribir

* lseek:

Las llamadas read y write realizan accesos secuenciales a un fichero, pero para aquellos casos en los que se requieran accesos aleatorios a un fichero por parte de un proceso, UNIX dispone de la llamada lseek. El retorno de esta función es el desplazamiento del próximo byte a acceder en el fichero.

long lseek(fd,offset,referencia)

fd:	descriptor del fichero

offset:	desplazaminento en bytes requerido

referencia:	principio, final o posición actual.

Lseek simplemente actualiza un nuevo valor de offset en la tabla de ficheros del sistema, no origina operaciones se "seek" en disco.

* close:

La llamada al sistema close realiza el cierre de un fichero. El núcleo para ello accede a la tabla de decriptores de ficheros del proceso que invocó a esta llamada y a las tablas del sistema de ficheros y de inodes y las actualiza. Si el contador de referencias en la tabla de ficheros del sistema es mayor que uno, debido a llamadas fork o dup, entonces simplemente se decrementa dicho contador. En cambio si el contador de referencias es uno entonces se procede a la liberación de la entrada en la tabla de inodes asociada al fichero sólo si el contador de referencias del inode en memoria es uno, en caso contrario simplemente se decrementará dicho contador; ya que existen otros procesos que quieren acceder al fichero.

int close(fd)

fd:	descriptor de fichero

* creat:

La llamada al sistema creat crea un nuevo fichero en el sistema. Retorna un descriptor de fichero.

int creat(pathname,modos)

pathname:	nombre del fichero

modos:	permisos de acceso del fichero

Obtener el inode del fichero (namei)

"Si" (fichero ya existe) "Entonces"

"Si" (permiso de acceso denegado) "Entonces"

Liberar inode (iput) ;

return(error) ;

"Fin si"

"Si no"

Asignar un inode libre del sistema de ficheros ;

Crear una nueva entrada en el directorio padre ;

"Fin si"

Asignar una entrada libre en la tabla de ficheros ;

"Si" (fichero ya existía) "Entonces" Liberar bloques del fichero (free) ;

unlock(inode) ;

return(descriptor de fichero de usuario) ;

* mknod:

La llamada mknod construye un fichero nuevo de tipo especial, ésto es: pipe, fichero de dispositivo o directorio. La sintaxis es:

int mknod(pathname,tipo y permisos,dev)

pathname:	nombre del fichero

tipo y permisos:	tipo del fichero y accesos permitidos

dev:	número mayor y memor del dispositivo ;

"Si" (No pipe y no es super_usr) "Entonces" return(error) ;

Acceder al inode del padre del nuevo fichero (namei) ;

"Si" (ya existía inode a crear) "Entonces"

Liberar inode del padre (iput) ;

return(error) ;

"Fin si"

Tomar un inode libre del sist. de ficheros (ialloc) ;

Crear una nueva entrada en el directorio padre ;

Liberar inode del padre ;

"Si" (inode de dispositivo) "Entonces" Escribir número mayor y menor ;

Liberar inode creado (iput) ;

6. El subsitema de control de procesos.

6.1. Descripción general de un proceso.

Un proceso es un programa en ejecución. Bajo UNIX se pueden ejecutar múltiples procesos simultáneamente según el núcleo los seleccione, cuando un proceso se ejecuta sigue un orden que él mismo se impone y no puede hacer referencia a otros procesos. La comunicación entre procesos se realizará mediante llamadas al sistema. Todo proceso bajo UNIX es una entidad creada por la función fork, la cual fue invocada por otro proceso al que se le llama proceso padre. Cada proceso posee un identificador numérico único. Todo fichero ejecutable posee la siguiente estructura:

- Cabecera, describiendo atributos del fichero.

- Instrucciones del programa.

- Representación de aquellos datos que se deben inicializar al comienzo de la ejecución.

- Tabla de símbolos.

Todo fichero ejecutable, que consiste en una cadena de bytes que la CPU interpretará como instrucciones o datos, se carga en memoria a través de la llamada al sistema exec. Lógicamente todo proceso UNIX está dividido en tres partes o regiones: Texto (instrucciones), Datos y Pila. Las regiones de texto y datos provienen del fichero ejecutable, en cambio, la región de pila se crea automáticamente y su tamaño se ajusta dinámicamente por el núcleo en tiempo de ejecución. Debido a que todo proceso se puede ejecutar en dos modos diferentes (usuario y sistema), UNIX emplea dos pilas separadas para cada uno de estos modos, de forma que:

- La pila en modo usuario se usa para la ejecución en modo usuario.

- La pila en modo sistema se usa para la ejecución en dicho modo.

Existe un matiz importante entre la ejecución en modo usuario y en modo sistema. Este consiste en que la ejecución en modo sistema es "non-preentive", es decir, un proceso en modo sistema cede la CPU de forma voluntaria (parada voluntaria o retorno a modo usuario), en cambio, en modo usuario la ejecución es "preentive".

6.2. Estructura de los procesos UNIX.

En la sección anterior se dió una descripción muy general del concepto de proceso y de algunos aspectos relacionados con ellos. En esta sección vamos a profundizar aún más; concretamente vamos a describir las estructuras de control relacionadas con ellos, disposición en memoria, contexto de un proceso y finalmente como se manipula el espacio de direcciones de un proceso.

Estructuras de control relacionadas con un proceso:

Existen dos estructuras de datos del sistema que describen el estado de un proceso: la tabla de procesos y el U área. La tabla de procesos es accedida por el sistema en todo momento, en cambio, al U área sólo se accede cuando los procesos se ejecutan. A continuación se muestra el contenido de cada entrada en la tabla de procesos:

- Estado del proceso.

- Información que indica la localización del proceso y de su U área en memoria principal o secundaria, así como su longitud.

- Identificador del propietario que determina los privilegios del proceso.

- Flag de indicación de proceso en reposo.

- Parámetros de scheduling.

- Información acerca de las señales que se han enviado y que aún no han sido tratadas.

- Contadores que dan el tiempo de ejecución del proceso.

Todo proceso posee su U área, la información que posee esta estructura de control es:

- Puntero a la tabla de procesos.

- Identificadores de usuario que determinan los privilegios del proceso.

- Contadores que se decrementan a medida que el proceso se ejecuta en modo usuario o sistema.

- Una tabla que inidica qué debe hacer el proceo cuando reciba una señal determinada.

- Identificador del terminal asociado al proceso.

- Campo de error para las llamadas al sistema.

- Campo de resultados para las llamadas al sistema.

- Parámetros de E/S: Cantidad, destino , etc.

- Directorio actual.

- Tabla de descriptores de ficheros abiertos.

- Límites del proceso.

- Campo de permisos de acceso que tendrán asociados los ficheros que el proceso cree.

Descripción de la disposición en memoria:

Como ya se mencionó todo proceso UNIX está dividido en tres partes lógicas o regiones: TEXT, DATA y STACK. La sección TEXT está constituida por las instrucciones ejecutables del proceso y se direcciona a sí misma y a cualquiera de las otras dos secciones. Las secciones DATA y STACK se constituyen a partir de los datos y pila respectivamente.

Cuando se compila un programa, el compilador genera direcciones virtuales que son traducidas a direcciones reales mediante el subsistema de memoria. Este subsistema de memoria está constituido por una parte lógica y otra física (hardware de direccionamiento). Este esquema permite que un proceso pueda ser ubicado en diferentes zonas de memoria durante la vida del mismo (reubicación dinámica).

Regiones: El espacio direccionable virtual de un proceso se estructura en regiones lógicas. Una región es un conjunto de direcciones virtuales contiguas de un mismo proceso que puede ser tratada como una unidad diferenciada del resto de las regiones del proceso en cuanto a protección y compartición. Normalmente TEXT, DATA y STACK se construyen en regiones separadas en un proceso. Así por ejemplo, varios procesos que provienen de un mismo programa pueden ejecutarse compartiendo la misma región TEXT. Todo proceso posee una estructura de control, llamada tabla de regiones, cuya finalidad es describir cada región del proceso. Cada entrada en esta tabla está asociada una región y su estructura es:

- Dirección de la tabla de páginas (si es una sistema paginado).

- Inode del fichero de donde proviene la región.

- Tamaño , estado y tipo.

- Contador de referencia.

Páginas: En sistemas paginados se relacionan las direcciones virtuales de cada región con las direcciones reales asociando los números de páginas lógicas de cada región con los números de páginas físicas a través de una tabla de páginas. Esta tabla contiene en cada una de sus entradas información referente al número de página física y se entra en ella a través del número de página lógico. Cada entrada en la tabla de regiones del sistema posee un puntero a una tabla de páginas.

Disposición del núcleo: El núcleo del sistema se trata de la misma forma que los procesos, solo que cuando el sistema es cargado se produce un mapeo de memoria virtual a memoria física del sistema. El código y los datos del núcleo residen de forma permanente en el sistema y son compartidos por todos los procesos. Por lo tanto, hay que distinguir entre memoria del sistema y de procesos. Por último hay que decir, que toda U área de un proceso es accesible sólo cuando el proceso se está ejecutando en modo sistema. Dicha área se almacena en una posición fija de memoria virtual, esto es debido a que el compilador asigna direcciones fijas virtuales a las variables globales de un programa, y también a que el núcleo almacena el U área de un proceso en una variable cuando quiere acceder a dicha área.

El contexto de un proceso:

El contexto de un proceso consiste en el contenido de su espacio de direcciones, y el contenido de las estructuras de control del núcleo asociadas a dicho proceso. Podemos distinguir tres partes bien diferenciadas:

El contexto de nivel de usuario: Se compone del programa y los datos, en definitiva se trata de las regiones TEXT, DATA y STACK.

El contexto de registros: Se compone del contenido de los registros, es decir:

- Contador de programa.

- El registro de estado del proceso.

- Registros de stack.

- Registros de propósito general de la CPU.

El contexto a nivel de sistema: Se compone de una parte estática que es constante, en cuanto a tamaño, durante la vida de un proceso y otra parte dinámica:

- Parte estática: Formada por las entradas en la tabla de procesos, U área, tabla de regiones.

- Parte dinámica: Formada por una pila donde el núcleo almacena los diferentes niveles de contexto en los que el proceso se ha ejecutado.

El contexto de un proceso se salva cuando alguno de los siguientes eventos ocurre:

- Interrupción.

- Excepción.

- Llamada al sistema.

Cuando se produce una interrupción el núcleo procede de la siguiente manera:

1. Salva el contexto de registros del proceso.

2. Determina la causa de la interrupción.

3. Se llama a la subrutina de tratamiento.

4. Cuando finaliza la rutina se restaura el contexto a través de instrucciones máquina específicas.

Cuando lo que se produce es una llamada al sistema entoces se procede de la siguiente manera:

1. Se identifica la llamada al sistema asociandole un índice

2. Con este índice se entra en la tabla donde se localiza la subrutina de tratamiento y los parámetros correpondientes.

3. Se toman los parámetros en la pila de usuario.

4. Se copian en la U área.

5. Se ejecuta la subrutina de tratamiento.

6. Una vez terminado el tratamiento se chequean los parámetros de error devolviendo los resultados en la U área.

7. Se retorna a modo usuario.

6.3. Manejo de memoria:

En todo sistema el recurso de la memoria principal es vital ya que para poder ejecutar un proceso éste debe estar, al menos parcialmente, en memoria principal. El subsistema de manejo de memoria es el responsable de:

- Gestionar el espacio virtual de direcciones.

- Gestionar la memoria principal.

Históricamente UNIX gestionaba la memoria mediante transferencia de procesos enteros entre memoria principal y el dispositivo de swap, tal técnica llamada swapping sólamente permitía transferir parcialmente un proceso, cuando ésta consistía en bloques compartidos. Actualmente los sistemas UNIX soportan el concepto de memoria virtual, utilizando la técnica de gestión de memoria por demanda de página en la que la memoria se gestiona mediante bloques de tamaño fijo llamados páginas. Bajo estas condiciones los procesos no tienen por qué residir totalmente en memoria principal para su ejecución. Comparando estas dos filosofías de manejo de memoria principal podemos llegar a las siguientes conclusiones:

- La demanda de página proporciona una mayor flexibilidad en la transformación entre memoria física y virtual. Proporcionando un mayor grado de multiprogramación.

- Swapping es más fácil de implementar y posee un menor coste de implementación.

Un detalle a tener en cuenta es que la utilización de la técnica de demanda de página implica la utilización de Swapping.

Swapping:

Seguidamente vamos a realizar una descripción de los tres aspectos sobre los que se fundamenta esta técnica:

* El dispositivo de swap.

* Proceso de Swapping out de un proceso.

* Proceso de Swapping in de un proceso.

Swap device: El dispositivo de swap (swap device) está formado por el conjunto de registros físicos de disco. El núcleo asigna dicho espacio de forma diferente a como asigna los registros físicos que forman un sistema de ficheros. Mientras que para los ficheros del sistema de ficheros la asignación del espacio de disco se realiza a través de bloques individuales, la asignación de espacio en el dispositivo swap se realiza por bloques contíguos. La razón para llevar a cabo la asignación de esta manera es que de esta forma las operaciones de E/S serán más rápidas.

Debido a esta diferencia, la estructuras de datos que utiliza el núcleo para gestionar el dispositivo swap difieren de las empleadas para controlar el espacio en disco del sistema de ficheros. El núcleo utiliza una lista encadenada para el sistema de ficheros, en cambio para el dispositivo swap utiliza una tabla llamada map.

La tabla map es un vector cuyas entradas constan de dos campos: el primero es de dirección del registro y el segundo contiene el número de registros consecutivos a partir de esta dirección que pueden ser utilizados. A medida que los procesos van siendo transferidos del dispositivo swap a memoria principal y viceversa la tabla map va siendo actualizada por el núcleo. Seguidamente para ilustrar este proceso de actualización se muestra el algoritmo de asignación de espacio mediante la tabla map y un ejemplo de como actúa dicho algoritmo. Supongamos un estado inicial

Dirección	Unidad

1	10000

Entonces la gestión del espacio de swap se haría, en lo que a peticiones de bloques, según el algoritmo de la función malloc (función para pedir memoria dinámicamente).

Algoritmo:	malloc /* algoritmo de ubicación en Swap dev. */

Entrada:	(1) tabla map

(2) número de unidades requeridas

Salida:	dirección en Swap device, si hay disponible

0, si no hay disponible

"Para" (cada entrada en la tabla map) "hacer"

"Si" (tamaño asociado >= petición) "Entonces"

"Si" (petición = tamaño asociado) "Entonces"

borrar entrada en la tabla ;

"si no"

ajustar dirección de comienzo de la entrada ;

"Fin si"

return(dirección original de la tabla) ;

"Fin si"

"Fin para"

return(0) ;

Dirección	Unidad	Dirección	Unidad

1	10000	asignación de 100 blk	101	9900

Dirección	Unidad	Dirección	Unidad

101	9900	asiganción de 50 blk	151	9850

Cuando de lo que se trata es de liberar espacio del dispositivo swap, el núcleo localiza la entrada correspondiente en la tabla map mediante el campo dirección. Existen tres casos posibles:

1. Los recursos liberados llenan completamente un hueco de la tabla map y son contiguos a las entradas cuyas direcciones le preceden y seguen en la tabla, entonces el núcleo crea una única entrada en la tabla map fusionando las tres anteriores.

2. Los recursos liberados llenan parcialmente un hueco del map y la dirección de los recursos liberados es contígua con una entrada en el map que le precede o con la que le sigue, pero no con ambas, entonces el núcleo adopta la direccón de la entrada apropida para justificar los recursos liberados; en este caso, el número de entradas en la tabla map no se modifica.

3. Los recursos liberados llenan parcialmente un hueco pero no son contíguos con los recursos del map, entonces se creará una nueva entrada.

Swap out:

En núcleo realiza una tarea de swap out, o de desalojo de la memoria principal, sobre un proceso cuando necesita memoria principal debido a:

- Realización de una llamada al sistema fork.

- Realización de una llamada al sistema brk.

- Obtener memoria para procesos que préviamente habían sido desalojados de memoria principal.

Cuando el núcleo selecciona un proceso para el swapping desde memoria principal, decrementa en uno el número de referencias de cada área del proceso y realiza un swap out cuando éste es cero.

Cuando se realiza una llamada al sistema fork y no hay memoria suficiente para el proceso hijo, el sistema libera memoria asignada a otros procesos que no sean el proceso padre. Mientras esto ocurre, el proceso hijo se encuentra en el dispositivo swap y es el proceso padre quién pone al hijo en estado ready. Sólo en este estado el proceso hijo será ubicado en memoria.

Cuando un proceso necesita más memoria de la que se le asignó o de la que está disponible, en el dispositivo swap se reservará espacio suficiente para contener el espacio de memoria del proceso, incluyendo el espacio más recientemente solicitado. Luego se ajusta el mapa de traducción de direcciones del proceso, y por último se desaloja el proceso.

swap in:

Este proceso consiste en ubicar procesos en memoria principal, esta tarea se aplicará a aquellos procesos que estén en el dispositivo swap de forma que se eligirá aquel que más tiempo lleve esperando. Si existe suficiente espacio en memoria principal el proceso se realiza invirtiendo los pasos del swap out, esto es: Asignar memoria física, leer el proceso del dispositivo swap, y liberar espacio del dispositivo swap. Cuando no existe memoria suficiente, se intenta relaizar un swap out y cuando éste finaliza se intenta realizar de nuevo un swap in.

Demanda de páginas:

Los técnica de demanda de páginas se pueden implementar sólo en aquellas máquinas que posean:

- Una arquitectura de memoria basada en páginas.

- CPU que posean instrucciones específicas de RESTAR para situaciones de "fallo de página".

La gestión de memoria por demanda de página es transparente a los procesos; de forma que permite liberar a estos de las limitaciones del tamaño de memoria principal. La única limitación que se impone en cuanto al tamaño de los programas de usuario la define la dimensión de la memoria virtual.

La razón por la que en estos sistemas paginados se obtienen buenos resultados se debe fundamentalmente al cumplimiento, por parte de los procesos, del llamado principio de localización de Denning que establece que las referencias a direcciones de un proceso se localizan en pequeñas porciones de su espacio de direcciones. Este principio se acentúa a medida que los programas se construyen de forma más modular. Desde un punto de vista más formal, Denning formuló su principio a través del concepto de conjunto de trabajo de un proceso (working set) que se define como el número de páginas de memoria que el proceso ha referenciado en las últimas n referencias, al número n se le denomina ventana de trabajo. Debido a que el conjunto de trabajo representa una porción de un proceso, entoces se tendrán más procesos en memoria principal (grado de multiprogramación) cuando ésta sea ocupada por los conjuntos de trabajo de los procesos y no por los procesos enteros, esto ocurría en un sistema de swapping. Cuando un proceso referencia a una página que no está en memoria se produce un fallo de página; implicando la parada del proceso y la transferencia de dicha página a memoria principal para el posterior reinicio del proceso.

Estructuras de control utilizadas por la demanda de páginas:

Existen cuatro estructuras de control básicas sobre las que se fundamenta la demanda de páginas, éstas son:

- Tabla de páginas.

- Descriptores de bloque de disco.

- Tabla de franjas de páginas (pfdata).

- Tabla de swap.

Cuando el sistema es paginado, cada región contendrá una tabla de páginas. Cada entrada en esta tabla contendrá:

- Dirección física de la página.

- Bits de protección.

- Bit de validez.

- Bit de referencia.

- Bit de modificación.

- Bit de copiado de escritura.

- Bits de edad.

El bit de validez es utilizado por el núcleo para indicar cuando contiene una página "legal". El bit de referencia indica si la página ha sido referenciada recientemente. El bit de modificación indica si el contenido de la página ha sido alterado. El bit de copiado de escritura indica si el núcleo debe crear una nueva copia en caso de modificar su contenido, este bit se utiliza con la llamada al sistema fork. Por último, los bits de edad indican cuanto tiempo hace que la página forma parte del conjunto de trabajo del proceso.

Cada entrada en la tabla de páginas tiene asociada un descriptor de bloque de disco, que posee información acerca de la copia virtual de la página. De esta manera, procesos que comparten una región compartirán la tabla de páginas de dicha región y los respectivos descriptores de bloques de disco. El contenido de la página virtual podrá estar en un dispositivo swap o en un fichero ejecutable. Cuando se encuentra en un dispositivo swap el descriptor de bloque de disco contiene el número de dispositivo lógico y el número de bloque que contiene dicha página. Si la página está en un fichero ejecutable el descriptor de bloque de disco contendrá el número de bloque lógico que contiene la página.

La tabla pfdata contiene en cada una de sus entradas una descripción de cada página en memoria física. Los campos de cada entrada son:

- El estado de la página

* En dispositivo swap.

* En fichero ejecutable.

* En transferencia de DMA.

* Disponible.

- Dispositivo lógico y bloque que contiene una copia de la página.

- Número de procesos que referencian a la página.

- Puntero a otras entradas de la tabla pfdata, dando lugar a una lista.

La tabla de uso de swap contiene una entrada por cada página que esté en un dispositivo swap. La información que cada entrada contiene es:

- Contador de referencia (número de entradas en la tabla de página le apuntan).

- Número de página.

- Número de bloque.

En cuanto al descriptor de bloque de disco; existe uno por entrada en la tabla de páginas (puede ser visto como una extensión de ésta), cada descriptor contiene:

- Dispositivo swap (número lógico de dispositivo).

- Número de bloque.

- Tipo de página (en Swap, en Fichero, demanda "fill", demanda "Zero")..

6.4. Planificación de procesos.

El planificador de procesos de UNIX se basa en la política conocida de Round-Robin con colas realimentadas multinivel, básicamente esta política consiste en asignar una rodaja de tiempo a cada proceso que se ejecuta, de forma que cuando ésta se acaba se acaba, el proceso es introducido en una de las colas y se asigna la CPU a otro proceso que esté en una de las colas.

Prioridades entre procesos:

La prioridad de un proceso puede tomar una serie de valores, dichos valores se dividen en dos: valores de prioridad de modo núcleo (prioridade altas) y valores de prioridad de modo usuario. Los valores de prioridad de modo usuario se definen en función del uso reciente de la CPU; de forma que procesos con prioridad baja se corresponden con aquellos que usarón la CPU recientemente. Los valores de prioridad en modo núcleo, a su vez, se dividen en dos clases: prioridades que dan lugar a ejecuciones sin interrupción y prioridades que dan lugar a ejecuciones que pueden ser interrumpidas. En la siguiente figura se ilustra este esquema de prioridades.

La asignación de prioridades de modo núcleo es función de la causas que hacen que un proceso pueda pasar a estado de espera, en cambio, no se contemplan aspectos tales como ciclos de E/S , ciclos de CPU. A la hora de asignar prioridades se tiene en cuenta el fenómeno de cuello de botella que se produce en ciertos recursos del sistema; así por ejemplo, a los procesos que esperan por la finalización de una E/S de disco se les asignará una prioridad mayor que a los procesos que esperan por un buffer disponible, en este caso varias son las razones para obrar así: la primera de ellas consiste en que un proceso que espera por la finalización de un E/S ya posee al menos un buffer, y por lo tanto, cuando ésta finalice puede liberar algún buffer, consiguientemente habrán más recursos disponibles por lo que la posibilidad de detener la ejecución de un proceso por falta de buffer disminuye, con lo que el flujo total del sistema aumenta. La segunda razón radica en que pudiera darse el caso de que el buffer que necesita el proceso bloqueado ya estubiese asignado a un proceso que está a la espera de finalizar una E/S de disco, entonces cuando ésta finalice ambos procesos podrían reanudarse, de forma que si el que se reanuda es el proceso peticionario del buffer en uso por la transferencia de datos, se producirá un nueva detención de dicho proceso hasta que la transferencia finalice. Pór último, y en cuanto a prioridades, hay que comentar que se pueden variar las prioridades en las siguientes situaciones:

- El proceso realiza una llamada al sistema sleep.

- El proceso retorna de modo núcleo a modo usuario.

- El manejador del temporizador ajusta las prioridades por uso de CPU.

La planificación de la CPU se lleva a cabo cada vez que ocurre una interrupción asociada al temporizador del sistema (típicamente entre 50 y 100 veces por segundo). Existen otros eventos que producen un reasignación de la CPU, éstos son:

- Terminación del proceso.

- El proceso necesita más memoria para seguir ejecutándose.

- El proceso se bloquea.

- Por apropiación de la CPU por un proceso de mayor prioridad.

6.5. Llamadas al Sistema para el control de procesos.

En esta sección vamos a describir las llamadas al sistema de control de procesos usadas más frecuentemente. Concretamente nos referimos a las llamadas al sistema para crear procesos, fork, terminación de un proceso, exit, sincronizar procesos, wait, controlar eventos, signal, y por último terminar la ejecución exit.

Creación de procesos:

La creación de procesos en UNIX se realiza a través de la llamada al sistema fork. el proceso que la invoca se le denomina proceso padre, y al proceso creado se le llama proceso hijo. La sintaxis de esta llamada es :

pid = fork() ;

Esta función retorna al procesos padre un identificador númerico asociado al proceso hijo. Los dos procesos poseen identicos contextos a nivel de ususario. El núcleo realiza la siguiente secuencia de operación cuando se invoca esta función:

1. Localiza una entrada en la tabla de procesos.

2. Se asigna un ID único al nuevo proceso.

3. Se realiza una copia del contexto del proceso padre. Si el proceso padre posee regiones comapartidas, entonces el núcleo incrementa el número de referencias en vez de copiarlas.

4. Se incrementan los contadores de ficheros y de inodes de los ficheros del proceso padre.

5. Se retorna el PID ( identificador de proceso) del proceso hijo al proceso padre, y cero al proceso hijo.

La implementación de esta llamada al sistema no es trivial, en el algoritmo que se propone a continuación se supone que hay memoria suficiente para el proceso hijo.

Algoritmo:	fork

Entrada:	Ninguna

Salida:	Al proceso padre el PID del proceso hijo

Al proceso hijo le retorna un 0

Comprobar que el núcleo dispone de recursos.

Obtener una entrada disponible en la tabla de procesos.

Comprobar que el propietario no sobrepasa el número de procesos.

Poner al proceso hijo en estado de "en creación".

Copiar información del proceso padre contenida en la tabla de procesos en la entrada asociada al proceso hijo.

Incrementar contadores de referencias en tabla de ficheros.

Realizar una copia del contexto del proceso padre:

- u_area.

- Texto.

- Datos.

- Pila.

Copiar contenidos de registros en el contexto de sistema del hijo.

"Si" (se ejecuta el proceso padre) "Entonces"

Cambiar estado del proceso hijo a "Listo para ejecutar".

Retornar ID del proceso hijo.

"Si no"

Inicializar campos de temporización en u_area.

retornar 0

"Fin si"

En este algoritmo habría que aclarar qué se entiende por "comprobar que el núcleo dispone de recursos"; ésta consiste en verificar que el sistema dispone de suficiente espacio para contener al proceso hijo en el área de swap, y para el caso de sistemas paginados, también habría que ver si se dispone de espacio en memoria para contener las tablas de páginas del proceso creado.

señales:

También se les denomina interrupciones software, en un entorno UNIX System V existen 19 señales y éstas informan a los procesos de la ocurrencia de eventos asíncronos. Se podrían clasificar en base a su origen de la siguiente manera:

- Terminación de procesos.

- Condiciones de excepción.

- Errores irrecuperables durante la ejecución de una llamada al sistema.

- Errores recuperables durante la ejecución de una llamada al sistema.

- Originadas por procesos en modo usuario.

- Interacción con terminales.

- Ejecución paso a paso procesos (debbuging).

El tratamiento de señales contempla varios aspectos, básicamente debemos tener claro los cuestiones:

- Como el núcleo envía señales a los procesos.

- Como los procesos tratan las señales.

- Como controlan su reacción a tales señales.

Para enviar una señal a un proceso, el núcleo utiliza el bit asociado en el campo de señales que toda entrada en la tabla de procesos posee. Si el proceso está dormido con prioridad interrumpible el núcleo lo despierta. El núcleo sólo maneja interrupciones cuando retorna de modo sistema a modo usuario, así pues, una señal tendrá efecto instantaneo sobre un proceso sólo cuando éste se esté ejecutando en modo sistema. Si un proceso se está ejecutando en modo usuario, y el núcleo trata una interrupción, que implica el envío de una señal al proceso, el núcleo reconocerá y tratará la señal cuando retorne del tratamiento de la interrupción. Un proceso cuando recibe una señal puede tratarla de diferentes maneras, éstas son:

- Acción por defecto.

- Ignorar la señal.

- Realizar una acción determinada.

Los casos segundo y tercero se deberán declarar préviamente. Cuando se quiera realizar una acción determinada, entoces se deberá especificar dicha acción a través de una función, que se ejecutará despues de que el núcleo haya realizado los siguientes pasos:

- El núcleo accede a los registro de programa y de pila.

- Se resetea el campo de señales en el u_area.

- El núcelo crea una nueva entrada en la pila de usuario copiando los valores de los registros de puntero a pila y contador de programa, y reserva más espacio si es necesario.

- El núcleo cambia el contexto de registro; pone en el contador de programa la diercción de la función asociada y el puntero a pila se situa en la nueva posición.

Despues de retornar de modo sistema a modo usuario, el proceso ejecuta la función de tratamiento de la señal; y cuando finaliza la función, el proceso se seguirá ejecutando en el punto donde se produjo la interrupción o la llamada al sistema.

Algoritmo:	issig /* Test de recepción de señales */

Entrada:	Ninguna

Salida:	Verdadero si se trata de una señal a no ignorar

falso en caso contrario

"Mientras" (campo en la tabla de procesos no sea 0) "Hacer"

Encontrar un número de señal enviada al proceso ;

"Si" ( señal de muerte de un hijo) "Entonces"

"Si" (ignorar señal de muerte de hijo) "Entonces"

Liberar entrada en la tabla de procesos (hijos zombies)

"Si no"

return verdadero

"Fin si"

"Si no"

"Si" (no ignorar señal) "Entoces" retornar vardadero ;

"Fin si"

Desactivar bit de la señal recibida en tabla de procesos ;

"Fin mientras"

Retornar falso ;

Algoritmo:	pseg /* Trata a una señal despues de reconocerla */

Entrada:	ninguna

salida:	ninguna

Obtener el número de señal en la entrada de la tabla de procesos ;

Resetear dicho número en la entrada de la tabla de procesos ;

"Si" (ignorar señal) "Entonces" return ;

"Si" (se especifica función de tratamiento) "Entonces"

Obtener los valores del contador de programa y de pila ;

Se resetea campo de señales en la u_area ;

Se crea nueva entrada en la pila ;

Cambio de contexto para ejecutar la función de tratamiento ;

return ;

"Fin si"

"Si" ( señal de tipo dump) "Entonces"

Se crea un fichero llamado"core" en el directorio actual ;

Se escribe el contexto del proceso en dicho fichero ;

"Fin si"

Invocar Inmediatammente a exit ;

Terminación de procesos

Los procesos UNIX finalizan su ejecución a través de la llamada al sistema exit. Un proceso que ejecuta un exit entra en el llamdo estado "zombie", libera sus recursos y se pierde su contexto excepto su entrada en la tabla de procesos. La sintaxis de la llamada es:

exit(status)

El valor de status es retornado al proceso padre que lo puede examinar y actuar en función del valor obtenido. Todo proceso invoca esta llamada explícita o implícitamente cuando retorna de la funcióm main. El sistema no impone límites de tiempo de ejecución de procesos; así por ejemplo el proceso 0, proceso de swapp, y el proceso 1, proceso init, existen durante toda la vida del sistema. Otros ejemplos de procesos que se ejecutan mientras "viva el sistema" son los procesos getty, que controla las líneas de terminales, y los procesos de administración del sistema (procesos de accounting).

Algoritmo:	exit

entrada:	Retorno para el proceso padre

Salida:	Ninguna

Ignorar todas las señales ;

"Si" ( es proceso propietario del control de terminales) "Entonces"

Enviar señal a los miembros del grupo ;

Resetear grupo de procesos ;

"Fin si"

Liberar recursos ;

Escribir registro de contabilidad (accounting) ;

Poner el proceso en estado zombie

Comunicar la muerte del proceso al proceso padre ;

Espera por la finalización de un proceso

Un proceso puede sincronizar su ejecución con la terminación de uno de sus procesos hijos a través de la llamada al sistema wait. La sintaxis de esta llamada es :

pid = wait(&status) ;

Siendo pid el identificador del proceso zombie hijo, y status contiene el código de salida del proceso hijo.

Algoritmo:	wait

Entrada:	Dirección de la variable que contendrá código de salida

Salida:	ID del proceso hijo

Código de salida

"Si" (no posee procesos hijos) "Entonces" error ;

"Mientras" (verdadero) "Hacer"

"Si" (existe proceso zombie) "Entonces"

Tomar el proceso zombie ;

Añadir su uso de CPU al proceso padre ;

Liberar entrada en la tabla de procesos ;

Retornar PID y código de salida ;

"Fin si"

sleep(evento: exit de proceso hijo) ;

"Fin mientras"

El núcleo busca un proceso zombie y en caso de no tener hijos retorna un error. Si encuentra un proceso hijo extrae su ID y su parámetro de salida para retornarlos. Así pues, los procesos pueden comunicar las distinas condiciones que dieron lugar a su finalización. El núcleo añade el tiempo de CPU del proceso hijo al proceso padre (se registra en el u_area) y finálmente libera la entrada en la tabla de procesos asociada al preceso hijo que lanzó el exit; sólo en este momento es cuando se puede utilizar esta entrada en la tabla de procesos para otro proceso a crear.

Como colofón a la descripción de los distintos subsistemas descritos, se muestra el diagrama de estados de un proceso genérico UNIX y los eventos que provocan sus transiciones

7. El Subsistema de E/S.

El Subsistema de E/S permite a los procesos comunicarse con los dispositivos periféricos tales como impresoras, terminales, discos, etc. Los módulos lógicos que se encargan de controlar a estos dispositivos se denominan manejadores de dispositivos. Normalmente, existe una correspondencia una a una entre tipo de dispositivo y manejador de dispositivo: Los sistemas pueden contener varias unidades de disco pero sólo un manejador de disco, o también, un sólo manejador de terminal para controlar a todos los terminales. En el caso opuesto, existen instalaciones que poseen varias unidades de cintas cuyo control difiere considerablemente, normalmente debido a que provienen de fabricantes diferentes, en estos casos se tendrán varios manejadores de cintas asociados cada uno a cada tipo de unidad.

En esta sección examinaremos las interfases entre los procesos y el subsistema de E/S y Examinaremos también la estructura interna de los manejadores de dispositivos.

7.1. Interfases de manejadores.

El sistema UNIX distingue dos tipos de dispositivos:

Dispositivos de Bloque y Dispositivos de caracter. Los Dispositivos de Bloque son aquellos que pueden transferir bloques de información ubicados en cualquier lugar de un medio de alamacenamiento, ejemplos clásicos de este tipo de dispositivo son las unidades de cintas y las unidades de disco. Los Dispositivos de Caracter son aquellos que no poseen esta característica de acceso a la información. UNIX suministra una interfase uniforme entre usuarios y dispositivos; esta interfase la suministra hace uso inicialmente de conceptos asociados al Sistema de Ficheros de UNIX, y en ella se distinguen dos tipos: Interfase orientada a bloque e interfase orientada a caracter, cada uno de estos tipos posee un conjunto de funciones y operaciones permitidas soportados por el Subsistema de E/S.

Para un dispositivo de bloque se pude usar tanto una interfase de bloque como de caracter, en cambio para un dispositivo de caracter sólo se puede usar una interfase de caracter. La uniformidad de tratatamiento de los dispositivos (interfase uniforme) se logra de la siguiente manera: Cada dispositivo tiene un nombre, al igual que un fichero, y el acceso a él se hace de forma análoga a como se hace en los ficheros. De cara al Sistema de Ficheros los dispositivos aparecen como ficheros; por lo tanto todo dispositivo tiene asociado un i_node, a estos ficheros se les denomina ficheros especiales de dispositivo, y en él se almacena el tipo de dispositivo (carcater o bloque) al que esta asociado. Si un dispositivo bloque posee una interfase caracter y otra de bloque, entonces tendrá asociado dos ficheros especiales.

Las llamadas al sistema para menejo de ficheros: open, read, write, close se pueden utilizar también para los ficheros especiales asociados a dispositivos. Concrétamente, se podrán utilizar sólo las que manejador de dispositivo soporte; que serán las utilizadas en el diseño de éste.

7.2. Configuración del sistema.

A través del procedimiento de configuración del sistema se especifican los parámetros que dependen de la instalación. Algunos parámetros especifican la configuración de dispositivos, que le dicen al núcleo que elementos físicos y lógicos forman el sistema y en que "direcciones" se encuentran. Otros parámetros especifican los tamaños de las tablas de control del sistema, por ejemplo: tabla de procesos, tabla de i_nodes, número de buffers a ubicar en el pool de buffers del sistema.

El nucleo utiliza dos tablas, llamadas tabla de dispositivos de bloque y tabla de dispositivos de caracteres, en donde cada tipo de dispositivo posee una entrada que especifica que llamadas al sistema se pueden utilizar para operar con él, o lo que es lo mismo, que funciones del sistema (open, read, write, ioctl, close, etc) utiliza el manejador asociado al tipo de dispositivo. A través del número mayor que el i_node asociado a un fichero especial de dispositivo tiene, el núcleo sabe que tipo de dispositivo representa, y a través del número menor el núcleo sabe a que unidad de dispositivo está asociado.

La interfase entre el hardware y los módulos manejadores de dispositivos la configura el conjunto de instrucciones de E/S dependientes del procesador del sistema, las instrucciones de acceso a memoria, cuando se requiera "mapear dispositivos en áreas de memoria específicas, y los vectores de interrupción.

7.3. Llamadas al Sistema e interfase de dispositivo.

Vamos a describir a continuación la interfase entre el núcleo y los manejadores de dispositivos. Por cada llamada al sistema que usa un descriptor de fichero, el núcleo accede a la tabla de descriptores de ficheros del proceso y obtiene la dirección de la entrada asociada en la tabla de ficheros del sistema y de ésta accede al i_node asociado. En este punto se comprueba que tipo de dispositivo es (carácter o bloque) y se obtiene el número mayor para acceder a la tabla de dispositivo, en donde se especifican las llamadas al sistema permitidas. Si la llamada es permitida, entonces se llama a la función del driver que corresponda; pasando como parámetro el número menor para saber que dispositivo debe atender la petición.

Open

Los pasos a seguir en la apertura de un dispositivo son los mismos que los pasos que se siguen con los ficheros regulares. Se activa el i_node asociado, se incrementa su contador de referncias y se asigna una entrada en la tabla de descriptores de ficheros del proceso, y en la tabla de ficheros del sistema. El núcleo retorna un descriptor de fichero al procesos llamador (al igual que un open sobre un fichero regular), pero el control se cede a la función open contenida en el manejdor de dispositivo. La dirección de esta función se encuentra en la tabla de dispositivos de bloque (si es de tipo bloque) o en la tabla de dispositivo de carácter (si es de tipo carácter).

El procedimiento open específico de cada manejador de dispositivo tiene por objetivos establecer una vínculo de unión entre un proceso y un dispositivo físico e inicializar las estructuras de datos de control propiedad del manejador de dispositivo.

Algoritmo:	open /* Para manejadores de dispositivos */

Entradas:	pathname

modo de apertura

Salidas:	descriptor de fichero

Convertir pathname a i_node ;

Incrementar su contador de referncias ;

Localizarle una entrada en la tabla de ficheros ;

Localizarle una entrada en la tabla de descriptores ;

Obtener el número mayor y menor del i_node ;

Salvar contexto (algoritmo setjmp) ;

"Si" (dispositivo de bloque) "Entonces"

Acceder a la tabla de dispositivos de bloque ;

Llamar a la función open del manejador;

"Si no"

Acceder a la tabla de dispositivos de carácter ;

Llamar a la función de open del manejador ;

"Fin si"

"Si" ( función open del dispositivo falla ) "Entonces"

Decrementar contador de referencias en el i_node ;

liberar entrada en la tabla de ficheros ;

Liberar entrada en la tabla de descriptores ;

Retornar valor de error ;

"Fin si"

Retornar Descriptor de ficheros ;

El núcleo debe salvar el contexto del proceso que realiza la apertura; ya que es posible que éste tenga que quedar suspendido temporálmente hasta recibir una señal y ésta nunca se produzca, entonces el núcleo debe suspender la operación de apertura y reanudar la ejecución del procesos detenido.

close

La llamada al sistema close se utiliza para eliminar el vínculo de unión existente entre un proceso y un dispositivo. La función close de un manejador de dispositivo es invocada por el núcleo cuando un proceso efectua la llamada al sistema close sobre un fichero especial de dispositivo y no hay ningún proceso que esté haciendo uso del dispositivo (proceso que hizo un open y no ha realizado un close).

El algoritmo close para un dispositivo es similar al algoritmo close para un fichero regular. Sin embargo, antes de que el sistema libere el i_node asociado al fichero especial de dispositivo, éste realiza una serie de pasos específicos:

1. Se asegura de que no hay procesos haciendo uso del dispositivo.

2. Para un dispositivo de tipo carácter, el núcleo invoca a la función close del dispositivo y luego retorna a modo usuario. En cambio para un dispositivo de tipo bloque, el núcleo debe comprobar primero que no existe un Sistema de Ficheros montado sobre el dispositivo.

3. Despues libera el i_node.

Algoritmo:	close /* Para manejadores de dispositivos */

Entradas:	descriptor de ficheros

Salidas:	ninguna ;

Realizar close para ficheros regulares ;

"Si" ( contador de referncias no es 0 ) "Entonces" Goto FIN ;

"Si" ( existe otro fichero abierto con igual número

mayor e igual número menor ) "Entonces"

Goto FIN ;

"Fin si"

"Si" ( dispositivo carácter ) "Entonces"

Acceder a la tabla de dispositivos de carácter ;

Llamar a close del manejador ;

"Fin si"

"Si" ( dispositivo bloque ) "Entonces"

"Si" ( dispositivo montado ) "Entonces" Goto FIN ;

Terminar de escribir datos del buffer ;

Acceder a la tabla de dispsoitivos de bloque ;

Llamar a la funcion close del manejador ;

Invalidar datos pendientes que queden en el buffer ;

"Fin si"

FIN: Liberar i_node ;

Read y write

Los algoritmos read y write para manejadores de dispositivos son similares a los empleados para ficheros regulares. Si un proceso está leyendo o escribiendo sobre un dispositivo de tipo carácter, el núcleo invocará a las funciones read y write del manejador de dispositivo.

El método utilizado para comunicara al manejador de dispositivo con el dispositivo depende del hardware. algunas máquinas proporcionan "E/S mapeada sobre memoria, significando ésto que ciertas direcciones del espacio del núcleo no son localizaciones físicas de memoria principal, son direcciones de acceso a regístros de dispositivos. Otras máquinas poseen "E/S programada", significandoque la máquina posee instrucciones de E/S que posibilitan el control de dispositivos.

Ioctl

La llamada al sistema ioctl proporciona una forma de ejecutar cualquier función contenida en el manejador de dispositivo. Esta llamada sólo se puede realizar sobre ficheros especiales de dispositivos, su sintaxis es:

ioctl( fd , comand , arg ) ;

Donde fd es un descriptor de ficheros, comand es un valor que especifica que operación se quiere realizar, y arg es una dirección que contiene los datos para realizar la operación deseada.

Bibliografía:

"The desing of the UNIX operating system"

Maurice J. Bach

Prentice Hall International Editions, 1986

"UNIX system architecture"

Prabhat K. Andleigh

Prentice Hall Inc., 1990

"The Design and Implementation of the 4.3 BSD UNIX Operating System".

S. Leffler, M. McKusick, M. Karels and J. Quarterman.

Addison Wesley, 1989.