Tratamiento de excepciones Rutina en ensamblador: vector contiene dirección de comienzo Estructura típica: similar al tratamiento de interrupciones Se debe comprobar nivel previo de procesador: Si era sistema: Pánico: Error en el código del S.O. Se muestra mensaje e info. de depuración y S.O. se para Si era usuario: Error en programa de usuario Tratamiento dependiente de S.O. En UNIX manda señal a proceso No siempre error: Puede tratarse de un fallo de página
Tratamiento de llamadas (1/2) Típicamente un único vector de int. para todas las llamadas Cada llamada tiene asignado un número S.O. tiene definido un vector con direcciones de rutinas que llevan a cabo cada servicio S.O. recibe nº de llamada (normalmente en un registro): S.O. indexa con él en el vector Parámetros de la llamada normalmente en pila de usuario Linux usa registros (como mucho 6 parámetros) Resultado de la llamada se suele devolver en un registro
Tratamiento de llamadas (2/2) Rutina en ensamblador: vector contiene dirección de comienzo Estructura típica similar a anteriores: Salvar registros en pila de núcleo Obtener número de llamada (N). Invocar función indexando en tabla de llamadas resultado=(*tabla_servicios[N])(); la función obtiene y valida los parámetros de la llamada recibidos en pila de usuario Devuelve resultado (puede devolverlo en un registro) Restaurar registros de pila del núcleo del proceso RETI
Invocación de llamadas al sistema Interfaz a los programas: rutina de biblioteca read(f, buf, tam) Programa se enlaza con biblioteca de llamadas Rutina de llamada codificada en ensamblador: read(){ PUSH parámetro1 ……………………….. MOVE R0, #NUM_READ INT 0x80 Valor devuelto está en R0 ……………………….. RET }
Multiplexación de procesos Cambio de modo: De usuario a núcleo (excepción, llamada o interrupción) De sistema a usuario (RETI) No hay c. de contexto: Mismo proceso en distinto modo Multiprogramación implica reasignar el procesador cuando: Proceso se bloquea Es conveniente ejecutar otro proceso en vez del actual Necesidad salvar/restaurar información de los procesos Info. del proceso ? Contexto del proceso
Contexto de un proceso Información asociada con el proceso Almacenada en el Bloque de Control del Proceso (BCP) Tabla de procesos: Vector de BCPs (mejor lista de BCPs) Contenido típico: Estado del proceso Copia del contenido de los registros del procesador Información de planificación (p.e. prioridad) Información sobre el mapa de memoria del proceso Información de ficheros y E/S Información de contabilidad (p.e. tiempo de UCP usado) "Dueño" del proceso (uid y gid en UNIX) Punteros para construir listas de BCPs Y muchos más: Relaciones entre procs., pid, señales, etc.
Definición de BCP S.O. es sólo otro programa: Usa definiciones convencionales struct task_struct { long state; long priority; unsigned long signal; struct task_struct *next_run, *prev_run; /* filesystem information */ struct fs_struct *fs; /* open file information */ struct files_struct *files; /* memory management info */ struct mm_struct *mm; ………………….. }
Estado de un proceso Elemento del contexto del proceso Durante su vida el proceso pasa por varios estados: En ejecución: UCP asignada Núm. Procesos en ejecución ? Núm. Procesadores Listo para ejecutar: No hay procesador disponible para él Bloqueado: Esperando un evento En sistemas con suspensión de procesos, estados adicionales: Suspendido y listo: Expulsado pero listo para ejecutar Suspendido y bloqueado: Expulsado y esperando un evento
Transiciones entre estados Transición disparada siempre por activación del S.O. No toda activación del S.O. implica c. de estado de un proceso. Posibles transiciones para modelo con 3 estados:
Cambio de contexto Cambio del proceso asignado al procesador Activación del S.O. que cambia estado de dos procesos: Proceso P pasa de en ejecución a listo o bloqueado Proceso Q pasa de listo a en ejecución C. contexto: Cambio de proceso Sólo cuando proceso está en modo núcleo El propio proceso (P): cambia su estado activa el planificador ? selecciona Q salva su contexto en BCP restaura contexto de Q del BCP ? ya está ejecutando Q
Cambio de contexto Cuando proceso P vuelva a ejecutar: Seguirá en el punto donde estaba (después de c. contexto) Dificultad para entender el código de gestión de procesos No toda activación del S.O. implica c. contexto No es "trabajo útil". Duración típica: decenas de microsegs. Código del c. contexto depende de arquitectura: Escrito en ensamblador En Linux switch_to(prev,next)
Tipos de c. de contexto Cambio "voluntario": Proceso realiza llamada al sistema que implica esperar por evento Transición de en ejecución a bloqueado Ejemplos: leer del terminal o bajar un semáforo cerrado Motivo: Eficiencia en el uso del procesador Cambio "involuntario": S.O. le quita la UCP al proceso Transición de en ejecución a listo Ejemplos: fin de rodaja de ejecución o pasa a listo proceso bloqueado de mayor prioridad Motivo: Reparto del procesador
Colas de procesos S.O. enlaza BCPs en colas BCP contiene punteros para permitir formar colas Algunos ejemplos: Cola de procesos listos en muchos sistemas, proceso en ejecución también está en ella Cola de procesos bloqueados esperando operación sobre un disco Cola de procesos bloqueados en un semáforo Cola de procesos esperando que transcurra un plazo de tiempo En Linux, colas de bloqueados: wait queues Un BCP debería estar en una sola cola en cada instante Cambio de estado implica pasar el BCP de una cola a otra
Bloqueo de un proceso Bloquear (cola de bloqueo) { Estado de proceso actual = BLOQUEADO; NivelUCPPrevio = FijarNivelIntUCP(máximo); /* Prohibir interrupciones */ Mover BCP de cola de listos a cola del evento; nuevo_proceso = planificador( ); Cambio_contexto(proceso_actual, nuevo_proceso); FijarNivelIntUCP(NivelUCPPrevio); /* Por aquí continuará, restaurando nivel int. de UCP, cuando se desbloquee y sea elegido por planificador, mientras habrán ejecutado otros procesos */ }
Bloquear no debe invocarse desde rutina de interrupción Proceso actual no está relacionado con la interrupción
Desbloqueo de un proceso
Desbloquear (cola de bloqueo) { NivelUCPPrevio = FijarNivelIntUCP(máximo); /* Prohibir interrupciones */ Seleccionar proceso en la cola (primero si política FIFO); Estado de proceso elegido = LISTO; Mover BCP de proceso elegido de cola del evento a cola de listos; FijarNivelIntUCP(NivelUCPPrevio); }
Desbloquear puede invocarse desde rutina de interrupción (p.e. del terminal) o desde llamada (p.e. subir un semáforo)
C. de contexto voluntario Proceso en modo usuario invoca llamada con posible bloqueo sis_llamada_X () { ……… Si (condición_1) Bloquear(cola de evento 1); ……… ? Cuando se desbloquee seguirá por aquí ……… Mientras ( ! condición_2) Bloquear(cola de evento 2); ……… ? Cuando se desbloquee y se cumpla la condición seguirá por aquí ……… }
C. de contexto involuntario Rutina de int. o llamada puede desbloquear proceso más importante o indicar que proceso actual ha consumido su turno Situación puede ocurrir dentro de anidamiento de interrup. Hay que esperar a que terminen Puede estar activa una llamada al sistema Mayoría de SS.OO. esperan a que termine Véase "sincronización dentro del S.O." Necesidad de diferir c. contexto hasta terminar trabajo de S.O. Se indica que replanificación pendiente (need_resched en Linux) Se activa interrupción software Si UCP no tiene int. SW, se puede simular por software Cuando termina actividad del S.O. (justo antes de volver proceso a modo usuario) se trata int. SW que realiza c. contexto
C. c. involuntario por desbloqueo Llamada o rutina de int. que causa desbloqueo rutina_X () { ……… Si (condición) Desbloquear(cola de evento); Si proceso desbloqueado más prioridad que actual { replanificación_pendiente = verdadero; Activar interrupción SW; } ……… } Int. SW se tratará cuando acabe rutina_X y otras rutinas del S.O. anidadas, si las hay
C. c. involuntario por fin de rodaja Interrupción de reloj que indica final de rodaja de p. actual rutina_int_reloj () { ……… Si (–rodaja == 0) { replanificación_pendiente = verdadero; Activar interrupción SW; } ……… }
Int. SW se tratará cuando acabe rutina_int_reloj y otras rutinas del S.O. anidadas, si las hay
Replanificación Tratamiento de int. SW rutina_int_SW () { ……… Si (replanificación_pendiente) { replanificación_pendiente = falso; NivelUCPPrevio = FijarNivelIntUCP(máximo); /* Prohibir int. */ nuevo_proceso = planificador( ); Cambio_contexto(proceso_actual, nuevo_proceso); FijarNivelIntUCP(NivelUCPPrevio); /* Por aquí continuará cuando sea elegido de nuevo por planificador, mientras habrán ejecutado otros procesos */ } }
Sincronización dentro del S.O. (1/2) S.O. es un programa con alto grado de concurrencia: Varias llamadas al sistema pueden ejecutarse concurrentemente Puede activarse una interrupción mientras se sirve una llamada Problemas de sincronización complejos: Es muy difícil asegurar que un S.O. funciona correctamente Ejemplos de problemas de sincronización: Dos llamadas concurrentes para crear un proceso podrían elegir el mismo BCP para los dos nuevos procesos Mientras una llamada manipula la cola de listos, se puede activar rutina de interrupción que también la cambie Es necesario secciones críticas dentro del S.O.
Sincronización dentro del S.O. (2/2) Solución usada en la mayoría de sistemas (Linux, Windows, …): Sincronización entre una llamada y una rutina de interrupción: código de la llamada prohíbe interrupciones durante s. crítica P.e. cuando manipula cola procesos listos (bloquear/desbloquear) Sincronización entre llamadas concurrentes: Limitar concurrencia dentro del S.O. Mientras proceso en modo núcleo no c. contexto involuntario: Se difieren a que termine trabajo en modo núcleo (int SW) Se tratan int. mientras proc. en modo núcleo pero sin c. contexto No hay concurrencia entre llamadas: Más sencillo pero no apropiado para multiprocesadores o s. de tiempo real Para dar soporte SMP (Symmetric MultiProcessing) Se debe permitir paralelismo en llamadas Se usan spin-locks y semáforos para sincronización
Aplazamiento de operaciones de int. Se debe minimizar duración de rutina de interrupción Mientras prohibidas int. de ese nivel e inferiores En rutina de int. se realizan operaciones urgentes Resto de operaciones (menos urgentes y más largas) se difieren Las realiza rutina que ejecuta con int. habilitadas Se suele usar el mecanismo de int. SW S.O. mantiene una lista de operaciones diferidas Rutina de int. realiza operaciones urgentes, encola operaciones pendientes en la lista y activa interrupción SW El tratamiento de int. SW realiza operaciones diferidas En Linux: bottom halves y task queues En Windows: DPCs (Deferred Procedure Calls)
Tratamiento ampliado de int. SW Tratamiento de int. SW rutina_int_SW () { Mientras (tareas pendientes) Ejecutar siguiente tarea: Si (replanificación_pendiente) { Realiza c.c. involuntario (como se vio previamente) } }
Las tareas diferidas se ejecutan con ints. habilitadas, pero de manera asíncrona (p. actual no relacionado con ellas) No deben llamar a bloquear ni acceder a mapa de proceso actual
Creación de un proceso Operaciones típicas para modelo convencional (Win32) Buscar entrada libre en tabla de procesos Leer fichero ejecutable Crear mapa de memoria a partir del ejecutable Crear pila inicial de usuario con el entorno del proceso Crear pila del núcleo con dir. del punto de arranque del programa Proceso comienza en modo núcleo haciendo RETI Crear contexto inicial en BCP: Fijar valores iniciales de regs. PC inicial=dirección de código de S.O. que contiene RETI Estado = LISTO Incluir BCP en cola de listos En UNIX estas operaciones están repartidas entre: FORK EXEC
Operaciones en la creación (UNIX) Operaciones en FORK Buscar entrada libre en tabla de procesos Copiar BCP del padre Duplicar mapa de memoria del padre (incluyendo pilas) Estado = LISTO + Incluir BCP en cola de listos Otras: actualización de filp, etc. Operaciones en EXEC Leer fichero ejecutable Liberar mapa de memoria del proceso Crear nuevo mapa de memoria a partir del ejecutable Crear pila inicial de usuario con el entorno del proceso Crear pila del núcleo con dir. del punto de arranque del programa Crear contexto inicial en BCP: Fijar valores iniciales de regs. PC inicial= dirección de código de S.O. que contiene RETI Otras: Gestión de señales, SETUID, CLOSE_ON_EXEC, etc.
Terminación de un proceso Tipo de terminación: Voluntaria: invoca llamada al sistema (EXIT en UNIX) Error de ejecución: excepciones (división por cero, …) Abortado: por un usuario u otro proceso UNIX unifica los dos últimos mediante el uso de señales ¿Qué ocurre con procesos hijos? En UNIX pasan a depender del proceso init Influencia de la jerarquía: UNIX: proceso terminado pasa a estado Zombie Proceso no desaparece hasta que padre espera por él (WAIT)
Operaciones implicadas en la terminación Operaciones típicas: liberar mapa de memoria cerrar ficheros y liberar otros recursos eliminar BCP de cola de procesos listos liberar entrada de tabla de procesos activa planificador y realiza c. de contexto al proceso elegido En UNIX estas operaciones están repartidas entre: EXIT: realiza la mayor parte de las operaciones WAIT: libera entrada de tabla de procesos
Threads Concepto moderno de proceso: Contiene múltiples flujos de ejecución (threads o procs. ligeros) El proceso se corresponde con un entorno de ejecución: Un mapa de memoria Un conjunto de recursos asociados (ficheros, semáforos, …) Un conjunto de threads Proceso tiene un thread implícito: el flujo de ejecución inicial Threads de un mismo proceso comparten: Mapa de memoria (código, datos, zonas de mem. compartida, …) Recursos asociados al proceso (ficheros, semáforos, …) Cada thread tiene recursos propios: Una pila, un estado y una copia del contenido de los regs. Colas de listos y bloqueo contienen threads en vez de procesos
Threads BCP sólo contiene info. gral. del proceso + lista de threads BCT (Bloque de Control de Thread): Info. específica del thread (estado, copia de regs., pilas de usuario y núcleo, prioridad, puntero a BCP del proceso, etc.) Creación de un thread: Crear pila de usuario con argumentos Crear pila del núcleo con dir. inicial del thread Crear contexto inicial en BCT: Fijar valores iniciales de regs. PC inicial=dirección de código de S.O. que contiene RETI Incluir BCT en cola de listos Ventajas del uso de threads vs. procesos convencionales: Permiten expresar concurrencia "ligera" y fuertemente acoplada Ligera: C. de contexto más rápido Fuertemente acoplada: Mayor grado de compartición
Threads de biblioteca Threads creados por biblioteca: S.O. no conoce su existencia Desventajas: Llamada bloqueante de thread bloquea todo el proceso No sacan provecho de múltiples procesadores Ventaja: gestión de threads no implica al S.O. Más ligeros BCTs no consumen memoria del S.O. Posibilidad de crear programas con nº muy elevado de threads Existen esquemas híbridos (Solaris)
Threads en Solaris S.O. gestiona LWPs Usuario crea threads de biblioteca Biblioteca se encarga de correspondencia entre LWPs y threads En cada momento un LWP ejecuta thread asociado Biblioteca multiplexa threads entre LWPs Nº de threads > Nº de LWPs Cuando thread hace llamada bloqueante, LWP asociado se bloquea Biblioteca puede crear nuevo LWP Biblioteca ajusta dinámicamente nº de LWPs de manera que: Sean suficientes para ejecutar threads activos No gasten muchos recursos del S.O.
Procesos de "peso variable" En Linux y UNIX BSD no hay soporte directo de threads, pero: Se permite especificar qué recursos comparten padre/hijo Extensión de FORK Peso variable: Más compartimiento ? más ligeros En Linux, CLONE permite especificar si comparten: Info. sobre ficheros (directorio actual, ficheros abiertos, …) Info. de mapa de memoria Info. de manejo de señales BCP incluye punteros en vez de la propia información: No hay BCTs, un BCP por proceso
Planificación del procesador ¿Cómo seleccionar el "mejor" algoritmo? Diferentes criterios (incluso contrapuestos): Buscar compromiso Maximizar grado de utilización de UCP Maximizar rendimiento: nº de procesos terminados/u. de tiempo Minimizar tiempo de espera de cada proceso: tiempo gastado esperando en cola de listos Minimizar tiempo de respuesta de procesos interactivos: tiempo desde que usuario realiza petición hasta que el proceso empieza a responder Tendencia general: Favorecer trabajos más interactivos Teoría de colas: servir primero peticiones más cortas Racha de UCP de un proceso: tiempo que va a usar la UCP hasta que se bloquee Mayoría de SS.OO. favorecen procs. con mucha E/S aunque no sean interactivos
Escenarios de c. de contexto Potenciales: Depende del algoritmo de planificación Posibles escenarios: 1) Proceso en ejecución finaliza 2) Proceso realiza llamada al sistema que lo bloquea 3) Proceso realiza llamada al sistema que desbloquea proceso "más importante" 4) Interrupción desbloquea proceso "más importante" 5) Se crea un proceso "más importante" que el que está en ejecución 6) Interrupción de reloj marca fin de rodaja de ejecución Dos tipos de algoritmos: no expulsivos: sólo c. de contexto voluntarios (1 y 2) expulsivos: además c. de contexto involuntarios (3, 4, 5 y/o 6)
Algoritmos de planificación FIFO (o FCFS) Primero el más corto (SJF) Prioridad Round-Robin Colas multinivel Planificación por lotería Planificación en Linux
Algoritmo FIFO Selección: Proceso que lleva más tiempo en cola de listos Algoritmo no expulsivo: sólo se activa cuando proceso en ejecución se bloquea o termina Fácil de implementar: Cola de listos gestionada en modo FIFO No válido para procesos interactivos Mal tiempo medio de espera en cola de listos: Proceso con rachas de UCP más pequeñas puede tener que esperar Mejor realizar antes "servicios" más cortos: Algoritmo "primero el más corto" (SJF, Shortest Job First)
Algoritmo SJF Selección: Proceso en la cola de listos que tenga una próxima racha de UCP más corta Versión no expulsiva: sólo se activa cuando proceso en ejecución se bloquea o termina Versión expulsiva: también se activa cuando aparece un nuevo proceso en cola de listos (escenarios 3, 4 y 5) Se favorecen los procesos con más E/S ¿Cómo se conoce a priori la duración de la próxima racha? Estimaciones a partir de las anteriores Puede producir inanición: A un proceso con rachas muy largas se le "cuelan" todos
Planificación por prioridad Cada proceso tiene asignada una prioridad Selección: Proceso en cola de listos que tenga mayor prioridad SJF es de este tipo: Prioridad depende de tamaño de racha Como SJF, existe versión no expulsiva y expulsiva Las prioridades pueden ser estáticas o dinámicas La prioridad de un proceso puede venir dada por factores: externos: ¿quién es el usuario? ¿qué importancia asigna el usuario a este proceso (en UNIX nice)? internos: comportamiento del proceso Puede producir inanición: A un proceso con baja prioridad se le "cuelan" todos "Envejecimiento": Prioridad aumenta con el tiempo
Algoritmo Round-Robin Algoritmo FIFO + cuanto de tiempo Cuando se asigna UCP a proceso se le da un cuanto de tiempo Si lo gasta (racha>cuanto) es expulsado al final de cola de listos Algoritmo expulsivo pero sólo con fin del cuanto (escenario 6) Tiempo de respuesta acotado: Si cuanto igual a C y N procesos listos: proceso no esperará más de (N-1)*C u. de tiempo Tamaño del cuanto: grande: tiende a FIFO. Mal tiempo de respuesta pequeño: demasiada sobrecarga Debe ser grande con respecto al tiempo de c. de contexto Típico: 10-100 milisegundos
Colas multinivel Modelo más general: Cola de listos organizada en múltiples niveles P.ej. Dependiendo de la interactividad de los procesos Cada nivel puede tener su propio algoritmo: P.ej. RR para niveles más interactivos y FIFO para los menos Existe un algoritmo para seleccionar entre niveles: P.ej. Por prioridades, mayor los niveles más interactivos Realimentación: Posibilidad de que los procesos cambien de nivel Deben existir criterios de cambio de nivel: P.ej. Mover de nivel un proceso si tiende a aumentar o disminuir su interactividad
Planificación por lotería Carácter aleatorio Cada proceso posee un "billete" de lotería Planificador: escoge billete y selecciona al premiado Procesos "importantes" pueden tener varios billetes Procesos cooperantes pueden intercambiarse billetes: Proceso cliente una vez hecha la petición puede ceder sus billetes al servidor
Planificación en Linux (1/2) Cumple estándar POSIX: soporta clases de planificación Clase de tiempo real (no crítico): Proceso tiene asignada una prioridad Dos clases de planificación: FIFO: ejecuta hasta que se bloquea Round-Robin: reparto UCP entre procesos de igual prioridad Clase de tiempo compartido: Procesos de esta clase sólo ejecutan si no hay de tiempo real Cada proceso tiene una prioridad estática (nice) Algoritmo basado en créditos En cada interrup. de reloj: proceso en ejecución pierde un crédito Si se queda sin créditos: se le revoca la UCP
Planificación en Linux (2/2) Planificador selecciona proceso con más créditos Si ningún proceso tiene créditos -> Reasignación de créditos. Reasignación de créditos: Para todo proceso del sistema: créditos = créditos/2 + prioridad
Propiedades: Compagina la "historia" del proceso con su prioridad Procesos que usan mucha UCP pierden rápido sus créditos Procesos con mucha E/S acumulan créditos Se favorecen procesos interactivos
| Página siguiente |