Departamento de Arquitectura y Tecnología de Computadores Konputagailuen Arkitektura eta Teknologia Saila

_________________________________________

Laboratorio de Sistemas Operativos _________________________________________

Núcleo de un Sistema Operativo

Alberto Lafuente

Febrero 2006

Contenido

1

Introducción

2

Una estructura en capas para el sistema operativo

3

Estructura de un núcleo de sistema operativo

4

3.1

Rutinas dependientes del hardware

3.2

Rutinas de manejo de colas y auxiliares

3.3

Rutinas para la gestión de procesos

3.4

Definiciones y estructuras de datos

3.5

Primitivas del núcleo

Funcionamiento del núcleo 4.1

Gestión de procesos

4.2

Primitivas bloqueantes

4.3

Rutinas de tratamiento de interrupciones

4.4

Primitivas no bloqueantes

4.5

Primitivas de sincronización

5

Puesta en marcha

A.1

Prueba del núcleo

UPV/EHU ATC Laboratorio de Sistemas Operativos

2

1

Introducción

Un sistema operativo se define desde dos puntos de vista. En primer lugar, el sistema operativo constituye la interfaz entre el usuario de un computador y los recursos de éste (hardware y software), proporcionando una visión funcional del sistema en forma de llamadas al sistema. En segundo lugar, el sistema operativo es el encargado de gestionar eficientemente la utilización de los recursos por los usuarios. Los servicios que un sistema operativo gestiona suelen dividirse en cuatro: procesador, memoria, dispositivos y ficheros. La complejidad inherente a la gestión de alguno de estos servicios hace necesario estructurar el sistema operativo en varias capas o niveles, cada una ofreciendo un conjunto de primitivas a la inmediatamente superior. Por ejemplo, el sistema de ficheros reside sobre el dispositivo disco, por lo que la gestión de ficheros se especificará en base a las primitivas que proporcione la gestión del disco, que será la que programe el hardware del dispositivo. El nivel básico de un sistema operativo, que oculta las características hardware de la máquina, se conoce como núcleo o kernel. En este documento se proporciona una descripción completa de la estructura del núcleo de un sistema operativo multiprogramado, que incluye gestión de procesos basada en prioridades, gestión de dispositivos (disco flexible, teclado, pantalla, impresora, línea serie y reloj), y primitivas de sincronización (semáforos). Se ha escogido como plataforma soporte la arquitectura PC basada en la familia i80x86. Ya que la mayor parte de las características dependientes de la arquitectura están encapsuladas en un conjunto de rutinas dependientes del hardware, esta elección no es especialmente determinante para el diseño del sistema operativo. La difusión de esta arquitectura es la única razón para su elección. Por otra parte, las rutinas dependientes del hardware proporcionan una interfaz C para su uso en el núcleo, lo que facilita la portabilidad a otras plataformas.

2

Una estructura en capas para el sistema operativo

El esquema general propuesto es una estructura en tres niveles o capas, de abajo arriba: 1

Nivel Núcleo. Gestión básica de procesos: planificación a corto plazo, cambio de contexto. Primitivas de sincronización. Gestión de E/S y tiempo, rutinas de atención.

2

Nivel del Sistema Básico de Ficheros, BFS. Sistema básico de ficheros: ubicación en disco, directorios. Rutinas de E/S, servidores de dispositivos.

3

Nivel Sistema. Implementación de las llamadas al sistema; independencia del dispositivo (tablas de canales); gestión de buffers para acceso a ficheros; carga, ejecución y finalización de procesos.

La Figura 1 muestra la estructura en niveles de un sistema operativo. Para un nivel n sólo son visibles las primitivas del nivel n-1. En general un nivel utilizará además una serie de rutinas auxiliares internas que no son visibles desde el nivel superior.

3

Estructura de un núcleo de sistema operativo

Como ejemplo de núcleo de sistema operativo, en esta sección describiremos las rutinas internas, estructuras de datos y primitivas de un núcleo multiprogramado para la arquitectura

UPV/EHU ATC Laboratorio de Sistemas Operativos

3

i80x86. Este núcleo es el que usaremos en el laboratorio. El funcionamiento del núcleo de presentará en la siguiente sección.

Rutinas de Librería

USUARIO

NIVEL SISTEMA

NIVEL BFS

NIVEL NUCLEO

Rutinas internas Nivel Sistema

Primitivas Nivel Sistema

Rutinas internas Nivel BFS

Primitivas Nivel BFS

Rutinas internas Nivel Núcleo

Primitivas Nivel Núcleo

Rutinas dependientes del Hardware

HARDWARE Figura 1. Niveles en un sistema operativo

3.1

Rutinas dependientes del hardware

Son las rutinas del núcleo de más bajo nivel. Distinguiremos dos grupos. Las más elementales están escritas en ensamblador y tratan con direcciones específicas de E/S o de memoria (para los dispositivos memory-mapped), o bien inhiben/activan interrupciones o manipulan directamente la pila del programa para proporcionar los cambios de contexto. Sus prototipos se describen en la Figura 2. El segundo grupo de rutinas internas del núcleo, que programan los dispositivos, están codificadas en C. Estas se describen en la Figura 3. Las rutinas dependientes del hardware se llamarán únicamente desde el núcleo. Encapsulan las características de la arquitectura.

UPV/EHU ATC Laboratorio de Sistemas Operativos

4

RUTINAS BASICAS DEL NUCLEO int flag inhibir (); void desinhibir (int flag); int in_port (int puerto); void out_port (int puerto, int dato); void strobe (int puerto, char mascara); void eoi (); void vector_int (int num_int , void (*rutina )()); int mascara_anterior enmascarar (int mascara); void salvar_flags (); void salvar_reg (); void restaurar (); void reset (); void timer (int valor);

Figura 2. Rutinas dependientes del hardware en ensamblador RELACIONADAS CON EL TERMINAL char leer_teclado (); void escribir_pantalla (int fila, int columna, char car, char atrib); void posicionar_cursor (int fila , int columna); void scroll (int fila_ini , int fila_fin); int estado escribir_impresora (char car); void beep (long tono_sonido); RELACIONADAS CON LA LINEA SERIE void ini_ls (); int estado escribir_ls (char car); char leer_ls (); int estado consulta_ls_iir (); int estado consulta_ls_lsr (); int estado consulta_ls_msr (); RELACIONADAS CON EL DISCO void motor_on (int drive); void motor_off (); void posicionar_pista (int pista, int drive); void programar_disco (int op, int cara, int pista, int sector, int drive); int estado programar_dma (int operacion, char *buffer ); void comando_disco (int comando); int estado comprobar_posicionado (); int estado comprobar_trasferencia (); int estado leer_status (); void recalibrar (int drive);

Figura 3. Rutinas dependientes del hardware en C

3.2

Rutinas de manejo de colas y auxiliares

La mayoría se utilizan en el núcleo para el manejo de los PCBs. Fundamentalmente son rutinas de acceso a colas, cuyos prototipos se describen en la Figura 4. Otras rutinas auxiliares, de apoyo a la programación, se ilustran en la Figura 5. En general, las rutinas auxiliares se utilizarán también en los niveles superiores. Por esta razón se definen las estructuras item y cola de forma genérica, sin incluir información específica de los elementos que enlazan (en general procesos).

UPV/EHU ATC Laboratorio de Sistemas Operativos

5

RUTINAS PARA MANEJO DE COLAS struct item { struct item *siguiente; struct item *anterior; int prioridad; }; struct cola { struct item *primero; struct item *ultimo; }; void inicializar_cola (struct cola *cola); int vacia (struct cola *cola); struct item *primero (struct cola *cola); /* Elimina y devuelve el primer elemento de cola */ struct item *extraer (struct cola *cola, int prio); /* Elimina y devuelve el primero de los de prioridad prio */ struct item *extirpar (struct cola *cola, struct item *elem); /* Elimina y devuelve el elemento apuntado por elem */ void encolar (struct cola *cola, struct item *elem); /* Encola elem al final de cola */ void insertar(struct cola *cola, struct item *elem, int prio); /* Encola elem al final de los de prioridad prio */ void meter(struct cola *cola, struct item *elem, int estado); /* Inserta elem actualizando estado en el PCB */

Figura 4. Rutinas auxiliares para manejo de colas RUTINAS AUXILIARES DIVERSAS void copiar (char *str1 , char *str2 , int lon); int comparar (char *str1, char *str2 , int lon); int buscar (char *str, char car, int lon); void rellenar (char *str, char car, int lon); void mayuscula (char *str, int lon); void minuscula (char *str, int lon); int long_a_ascii (long num, char *str, int base, int lon); int int_a_ascii (int num, char *str, int base, int lon); long ascii_a_long (char *str, int lon, int base); int ascii_a_ int (char *str, int lon, int base);

Figura 5. Otras rutinas auxiliares

3.3

Rutinas para la gestión de procesos

La gestión de procesos está soportada por rutinas que manejan colas y proporcionan cambios de estado en los procesos: bloquear(), scheduler(), dispatcher. Otras rutinas inicializan estructuras de datos (PCB y pila) para los procesos en su creación. Estas rutinas se muestran en la Figura 6 y se estudiarán más adelante. RUTINAS PARA LA GESTION DE PROCESOS void bloquear (struct cola *cola, int estado); struct item *scheduler(); void dispatcher (struct item este_item) void crear_pcb(void (*codigo)(), int *pila, int prio, int q, int id_proc)); void crear ();

Figura 6. Rutinas para la gestión de procesos

UPV/EHU ATC Laboratorio de Sistemas Operativos

6

3.4

Definiciones y estructuras de datos

Se refieren a la estructura del PCB y a las colas que modelan el funcionamiento del núcleo. Aparecen en la Figura 7. Existe además una serie de definiciones de símbolos para los estados de los procesos, dispositivos, etc, que no se muestran en la figura. #define NUM_PCBS … #define TAM_PILA …

/* /*

numero maximo de PCB */ tamaño de la pila de un proceso

*/

struct pcb { struct item elemento_cola; int id_proceso; int ax; int dx; int far *pila; int quantum; long cpu_time; int status; }; struct pcb proc[NUM_PCBS]; int pilas[NUM_PCBS][TAM_PILA]; struct info_proc { int quantum; int prioridad; long t_cpu; int status; }; struct cola libres, ready, run, teclado, disco, retardo, lectura_ls, escritura_ls; int ntr = 0;

/* numero de ticks de reloj */

#define NSEM …

/* semáforos */

struct semaforo { struct cola s; int cont; }; struct semaforo sem[NSEM];

Figura 7. Definiciones fundamentales del núcleo Otro conjunto de definiciones (que tampoco se muestran aquí) especifican la configuración de la máquina concreta (direcciones de pantalla, mapa de teclado, etc).

3.5

Primitivas del núcleo

Las primitivas del núcleo constituyen el conjunto de rutinas visibles desde el nivel superior. Se definen en C y utilizan las rutinas dependientes del hardware y a las rutinas auxiliares introducidas anteriormente. Las diferenciaremos denominándolas con el sufijo _nuc. Se pueden dividir en los siguientes grupos:

UPV/EHU ATC Laboratorio de Sistemas Operativos

7

1

Control de dispositivos (a) disco void motor_on_nuc (int drive) void motor_off_nuc () int posicionar_pista_nuc (int n_pista, int drive) int leer_sector_nuc (int n_cara, int n_sector, char *p_buff) int escribir_sector_nuc (int n_cara, int n_sector, char *p_buff) int recalibrar_nuc (int drive) (b) terminal char leer_teclado_nuc () int escribir_pantalla_nuc (int lin, int col, char car, char atributo) int scroll_nuc (int lin_sup, int lin_inf) (c) línea serie int leer_l_s_nuc () void escribir_l_s_nuc (char car) void init_l_s_nuc () (d) impresora int escribir_impresora_nuc (char car)

2

Control de procesos int crear_pcb_nuc (void (*cod)(), int *pila, int prio, int quantum, int pid) int destruir_pcb_nuc (int id_proc) int quisoc_nuc () int info_proc_nuc (int id_proceso, struct info_proc *p_info) int modif_proc_nuc (int id_proceso, struct info_proc *p_info)

3

Espera por tiempo void retardo_nuc (int n_tics)

4

Sincronización entre procesos int wait_nuc (int n_sem) int signal_nuc (int n_sem) int init_sem_nuc (int n_sem, int valor_inicial)

5

Reset void reset_nuc ()

UPV/EHU ATC Laboratorio de Sistemas Operativos

8

4

Funcionamiento del núcleo

4.1

Gestión de procesos

Incluiremos aquí planificación, creación y destrucción de procesos. Un proceso se representa en un PCB (struct pcb) que se identifica por un entero (índice en la tabla de PCBs). 3.4.1 Planificación de procesos En la versión del núcleo propuesta, se proporciona planificación de procesos de tiempo compartido y prioridades, con expulsión por desbloqueo de un proceso. Esto implica que la gestión de procesos involucra a las rutinas de atención (muy en particular a la de reloj para control de fin de quantum), además de las que hacen que un proceso pase a estado bloqueado (más adelante nos referiremos a estas rutinas como bloqueantes). Los procesos preparados para ejecución se encolan en la cola ready de acuerdo a su prioridad, por lo que la rutina del scheduler se limita a coger el primer elemento de la cola, que pasa al dispatcher para que lo cargue en ejecución (cola run, que tendrá un único elemento). Por ortogonalidad, se asume la existencia de un proceso nulo, que siempre estará preparado para ejecución o ejecutándose. La Figura 8 muestra el código de las rutinas scheduler() y el dispatcher(). La rutina bloquear() es la encargada de sacar a un proceso de la cola, lo que implica como efecto colateral la actualización del tiempo de CPU. Su código se muestra en la Figura 9. struct item *scheduler() { return (primero(&ready)); } void dispatcher (este_item) struct item *este_item; { meter (&run, este_item, RUN); }

Figura 8. Rutinas scheduler y dispatcher void bloquear (c, status) struct cola *c; int status; { ((struct pcb *)run.primero)->cpu_time += ntr; meter(c, primero(&run), status); ntr=0; }

Figura 9. Rutina bloquear Una vez actualizadas la colas de procesos, la multiplexación se completa reestableciendo el estado del procesador para que ejecute el proceso planificado. Básicamente esto implica hacer que el SP apunte a la pila del nuevo proceso. La rutina restaurar(), codificada en ensamblador, es la que se encarga de ello, manipulando el bloque de activación anterior. Previamente, la rutina salvar_reg() habrá salvado el estado del proceso que estaba en ejecución.

UPV/EHU ATC Laboratorio de Sistemas Operativos

9

La gestión del tiempo compartido la realiza la rutina de atención al reloj, multiplexar(), como se ilustra en la Figura 10. Esta rutina incluye otras funciones (apagado automático del motor de la unidad de disco y control del periodo transitorio tras el encendido, retardo de procesos por tiempo), que no aparecen en la figura. void multiplexar () { salvar_reg(); /* FIN DE QUANTUM: */ if (++ntr==((struct pcb*)run.primero)->quantum) cambiar = TRUE; … if (cambiar) { bloquear (&ready, READY); dispatcher (scheduler()); } eoi(); restaurar(); }

Figura 10. Rutina multiplexar. Control de quantum. 3.4.2 Creación, control y destrucción de procesos La rutina crear_pcb_nuc() asigna un PCB para un nuevo proceso, provocando la expulsión del que está en ejecución. Existen primitivas para extraer información de un proceso y su identificador (info_proc_nuc(), quisoc_nuc()) y para modificar su quantum y prioridad (modif_proc_nuc()). Finalmente, en la Figura 11 se incluye el código de destruir_pcb_nuc(). Nótese las situaciones en que el PCB no se libera (el proceso tiene una petición pendiente), sino que el proceso queda en estado finalizado (DEAD). La rutina de atención correspondiente liberará el PCB del proceso DEAD con la petición pendiente.

4.2

Primitivas bloqueantes

Llamaremos rutinas bloqueantes del núcleo a las que solicitan un servicio del hardware (un dispositivo, el reloj…) y dejan al proceso en estado bloqueado, provocando la planificación de un nuevo proceso. Son varias las primitivas que trabajan de esta forma, en general aquéllas cuyo servicio se atenderá mediante interrupciones, como motor_on_nuc(), retardo_nuc() — por tiempo—; leer_teclado_nuc() —por teclado—; escribir_impresora_nuc() —por impresora— leer_l_s_nuc, escribir_l_s_nuc() —por línea serie—; posicionar_pista_nuc(), leer_sector_nuc(), escribir_sector_nuc(), y recalibrar_nuc() —por disco—. Como ejemplo, en la Figura 12 se muestra el código de leer_teclado_nuc(). Todas las rutinas bloqueantes siguen el protocolo de salvar el contexto del proceso (salvar_flags y salvar_reg), bloquear al proceso y planificar otro proceso cargando su contexto. Nótese también que se exige que la cola de bloqueado esté vacía: se sugiere la implementación de un esquema cliente-servidor en el nivel superior.

UPV/EHU ATC Laboratorio de Sistemas Operativos

10

int destruir_pcb_nuc (id_proceso) int id_proceso; { inhibir(); salvar_flags(); salvar_reg(); id_proceso = id_proceso % NUM_PCBS; switch (proc[id_proceso].status) { case LIBRE: ((struct pcb *)run.primero)->ax = -1; break; case READY: proc[id_proceso].status = LIBRE; encolar (&libres, extirpar(&ready, &(proc[id_proceso].elemento_cola))); ((struct pcb *)run.primero)->ax = 0; break; case RUN: proc[id_proceso].status = LIBRE; encolar (&libres,primero (&run)); dispatcher (scheduler()); break; case BLOQ_TEC : case BLOQ_DISC: case BLOQ_RET: proc[id_proceso].status = DEAD; ((struct pcb *)run.primero)->ax = 0; break; default: proc[id_proceso].status = LIBRE; encolar(&libres, extirpar (&sem[proc[id_proceso].status].s, &(proc[id_proceso].elemento_cola))); ((struct pcb *)run.primero)->ax = 0; break; } restaurar(); }

Figura 11. Rutina destruir_pcb_nuc char leer_teclado_nuc () { inhibir(); salvar_flags(); salvar_reg(); if (vacia (&teclado)) { bloquear(&teclado, BLOQ_TEC); dispatcher (scheduler()); restaurar(); } else crash(); }

Figura 12. Ejemplo de rutina bloqueante

4.3

Rutinas de tratamiento de interrupciones

Aunque la rutina multiplexar puede servir como ejemplo de rutina de tratamiento de interrupciones, resultará clarificador en este momento introducir el código de la rutina de tratamiento de las interrupciones de teclado (Figura 13) para completar el ejemplo de tratamiento de peticiones del apartado anterior. Hay que resaltar alguna cuestión importante, común al resto de rutinas de este tipo:

UPV/EHU ATC Laboratorio de Sistemas Operativos

11

•

Tratamiento de peticiones pendientes de pocesos finalizados. La rutina de atención detecta que el proceso está en estado DEAD (véase destruir_pcb_nuc()) y libera su PCB.

•

Valores de retorno. El carácter leído (o un código de error en otras rutinas) debe ser devuelto a través del PCB del proceso (campo ax), que será lo que entregue como valor de retorno la primitiva que produjo el bloqueo (leer_teclado en nuestro ejemplo) al restaurarse el contexto del proceso (rutina restaurar()) cuando éste sea planificado nuevamente.

void int_teclado() { salvar_reg(); if ((c=leer_teclado()) != -1) if (!vacia(&teclado)) if (((struct pcb *)teclado.primero)->status == DEAD) { ((struct pcb *)teclado.primero)->status= LIBRE; encolar(&libres, primero(&teclado)); } else { ((struct pcb *)teclado.primero)->ax= c; meter(&ready, primero(&teclado), READY); bloquear(&ready, READY); dispatcher (scheduler()); } else beep(); eoi(); restaurar(); }

Figura 13. Ejemplo de rutina de tratamiento de interrupciones

4.4

Primitivas no bloqueantes

Llamaremos rutinas no bloqueantes a las que no dejan al proceso bloqueado. En general serán de este tipo aquellas primitivas que no se sirven mediante interrupciones, como es el caso de esribir_pantalla_nuc(), que se muestra en la Figura 14. Otras primitivas de este tipo son: scroll_nuc(), motor_off_nuc(), quisoc_nuc() e info_proc_nuc(). Estas primitivas se resuelven como simples llamadas a funciones y no producen cambios de contexto. int escribir_pantalla_nuc (linea, columna, caracter, atributo) int linea, columna; char caracter, atributo; { if (0