Gestión De Procesos

Transcript

15/12/2009 Tema 4: Gestión de procesos Capítulo 4: Gestión de procesos Procesos Procesos ligeros ((threads threads)) Políticas y algoritmos de planificación Señales y excepciones Temporizadores Servidores y demonios Servicios POSIX 1 15/12/2009 Procesos Concepto p de Proceso Multitarea Información del proceso (BCP) Creación de procesos Terminación de procesos Estados de los procesos Cambio de contexto Planificación Concepto de proceso I PROGRAMA: Archivo ejecutable en un dispositivo de almacenamiento permanente (ej. disco) PROCESO: Un programa en ejecución, reside en MP y según se ejecuta modifica su contexto Desde el punto de vista del usuario: código + estructuras de datos El sistema operativo le asigna recursos y controla su ejecución Desde el punto de vista del sistema operativo: Técnicas de multiplexado (planificación) Caracterización de un proceso: tabla o bloque de control de procesos (BCP). En Linux: task_struct Cada proceso posee un espacio de direccionamiento virtual Independiente 2 15/12/2009 Jerarquía de procesos Jerarquía de procesos Proceso hijo Proceso padre Proceso hermano Proceso abuelo Vida de un proceso Crea Ejecuta Muere o termina Ejecución del proceso Batch Interactivo Grupo de procesos Árbol típico de procesos en Solaris Entorno del proceso Tabla NOMBRENOMBRE-VALOR que se pasa al proceso en su creación Se incluye en la pila Se establece: Por defecto (se copia la del padre) Mediante mandatos del shell (export export)) Mediante API del SO ((putenv putenv,, getenv) getenv) Ejemplo: PATH=/usr//bin PATH=/usr bin:/home/pepe/ :/home/pepe/bin bin TERM=vt100 HOME=/home/pepe PWD=/home/pepe/libros/primero TIMEZONE=MET 3 15/12/2009 Conceptos Usuario: Persona autorizada a utilizar un sistema Se identifica en la autenticación mediante: Código de cuenta Cl Clave ((password password) d) Internamente el SO le asigna el “uid “uid” ” (user (user identification identification)) Super-usuario SuperTiene todos los derechos Administra el sistema Grupo de usuarios Los usuarios se organizan en grupos Alumnos Profesores Todo usuario ha de pertenecer a un grupo Bases de la Multiprogramación Paralelismo real entre E/S y UCP (DMA) Alternancia en los procesos de fases de E/S y de procesamiento La memoria almacena varios procesos Procesamiento Entrada/salida Tiempo 4 15/12/2009 Ejemplo de ejecución en un sistema multitarea. Proceso nulo Proceso A Proceso B Procesamiento Entrada/salida Listo SO Proceso nulo Proceso C Procesador Tiempo •Estados de los procesos: ejecución, bloqueado, listo Conceptos •Multitarea: varios procesos activos a la vez p varios usuarios en varias terminales •Multiusuario: soporta •Tiempo compartido: reparto “equitativo” del tiempo de CPU entre varios usuarios •Planificador (sheduler): seleciona el siguiente proceso a ejecutar •Activador (dispacher): Prepara la ejecución del proceso planificado -> cambio de contexto •Grado de multiprogramación: nº de procesos activos •Con BCP vigente •Necesidades de memoria principal: Memoria virtual 5 15/12/2009 Ventajas de la multitarea •Facilita la programación, dividiendo los programas en procesos (modularidad) •Permite el servicio interactivo simultáneo de varios usuarios de forma eficiente •Aprovecha los tiempos que los procesos pasan esperando a que se completen sus operaciones de E/S •Aumenta el uso de la CPU Concepto de proceso II INFORMACIÓN DEL PROCESO (BCP): Imagen de memoria (core (core image) image) Estado del procesador (registros del modelo de programación) Bloque de control del proceso BCP  Estado actual del proceso Identificación “pid “pid”, ”, ppid Uid Uid,, gid gid.. euid,egid Prioridad del proceso Registros de procesador cuando el proceso no está en ejecución Puntero a la zona de memoria: Segmentos de memoria Recursos asignados: Ficheros abiertos, Temporizadores, Señales, Semáforos, Puertos Un puntero al siguiente BCP 6 15/12/2009 Memoria de un proceso Contexto del nucleo Contexto de usuario Registros especiales FFFF Pila Registros generales Heap PC Datos Texto SP 0000 Estado Process Control Block (PCB) Planificación y estado Id de p proceso y p padre uid,guid,, euid uid,guid euid,, egid puntero de pila registros CPU descripción de la memoria recursos asignados punteros para formar listas … señales, mensajes, … 7 15/12/2009 El SO mantiene estructuras de datos asociadas a los procesos Mapa de memoria del Proceso A Mapa de memoria del Proceso B Tablas del sistema operativo Mapa de memoria del Proceso C Tabla de procesos Tablas SO BCP Proceso A BCP Proceso B BCP Proceso C - Estado (registros) - Estado (registros) - Estado (registros) - Identificación - Identificación - Identificación - Control - Control - Control Mapa de Memoria - Tabla de memoria - Tabla de E/S: drivers de bloques, de caracteres - Tabla de ficheros, de montajes Tablas del sistema operativo Tabla de procesos (tabla de BCP) Tabla de memoria: información sobre el uso de la memoria. Tabla de E/S: guarda información asociada a los periféricos y a las operaciones de E/S Tabla de fichero: información sobre los ficheros abiertos. Criterios C i i para iincluir l i o no una iinformación f ió en ell BCP BCP:  Eficiencia  Compartición 8 15/12/2009 Información fuera del BCP Se considera del BCP p g Por eficiencia: eficiencia Tabla de páginas Describe la imagen de memoria del proceso en sistemas con MV Tamaño variable -> El BCP contiene el puntero a la tabla de páginas (La compartición de memoria requiere que sea externa al BCP) Por compartición: Punteros de posición de los ficheros En la tabla de ficheros abiertos del BCP no se pueden compartir Si se asocian al nodo-i se comparte siempre Se ponen en una estructura común a los procesos y se asigna uno nuevo en cada servicio OPEN Memoria Virtual de un proceso RIED Memoria virtual i t l Memoria principal Código Datos Pila Tamaño Disco Tabla de páginas Una tabla de páginas á i por proceso Preasignación de zona de intercambio: Todas las páginas están en disco, algunas están copiadas en marcos de página. La información de traducción está en la tabla de páginas 9 15/12/2009 Creación de procesos I Objeto ejecutable Bibliotec a sistema Cargador Mapa de memoria Imagen del proceso Tabla de procesos BCP Creación de procesos II  El proceso padre crea un proceso, que a su vez, crea otros procesos, formando un árbol de procesos  Esquemas de compartición de recursos recursos:: A. El padre y el hijo comparten todos los recursos B. El hijo comparte unsubconjunto de los recursos del padre C. El padre y el hijo no comparten recursos  Ejecución j  El hijo comparte un subconjunto de los recursos del padre  El padre espera hasta que el hijo termine 10 15/12/2009 Creación de procesos III  Espacio de direcciones  El hijo hace una réplica del padre  El hijo carga un programa en su espacio de direcciones  Ejempos UNIX  La lamada al sistema fork crea un proceso nuevo  La lamada al sistema exec, exec, después de fork fork,, reemplaza el espacio de direcciones del proceso con un nuevo código de programa Terminación de procesos  El proceso ejecuta la última sentencia y pide al SO Su eliminación (exit (exit): ):  Devuelve la salida desde el hijo al padre (via wait wait))  Libera los recursos asignados  El padre puede abortar la ejecución del hijo hijo::  El hijo excede sus recursos  La tarea asignada al hijo ya no se necesita  Cuando el padre termina  Algunos SSOO no permiten continuar al hijo cuando el padre ha terminado  Todos los hijos terminan en cascada 11 15/12/2009 Realción padre padre--hijo en procesos padre Wait() Fork() hijo Exec() reanuda Exit() Estados de los procesos I Cuando un proceso se ejecuta, cambia su estado:  Ejecución Ejecución:: Se ejecutan las instruciones del código del proceso  Bloqueado Bloqueado:: El proceso espera la ocurrencia de un evento  Listo Listo:: El proceso espera que se le asigne tiempo de CPU para ejecutarse Zombie: El proceso ha terminado su ejecución pero aún tiene una entrada en la tabla de procesos (UNIX) 12 15/12/2009 Estados de los procesos II Diagrama de estados de los procesos: termina Zombie se interrumpe Ejecución Listo Termina la E/S o elevento se planifica Espera E/S o un evento Bloqueado Cambio de contexto I 13 15/12/2009 Cambio de contexto II Se produce por una interrupción. Cambio de contexto es el conjunto de dos operaciones: Se p pasa a ejecutar j la rutina de tratamiento de interrupción p Se salva el estado del procesador en el correspondiente BCP Planificador: decide el siguiente proceso a ejecutar. Activador: pone a ejecutar un proceso. Copia el estado del BCP a los registros Termina con una instrucción RETI (retorno de interrupción) Restituye R tit ell registro i t de d estado t d (bit d de nivel i ld de ejecución) j ió ) Restituye el contador de programa (para el nuevo proceso). El tiempo de cambio de contexto supone una sobrecarga; sobrecarga; el sistema no realiza trabajo útil durante este tiempo  El tiempo de cambio de contexto depende del soporte hardware Cambio de contexto III Estado Registros especiales Registros generales PC SP Tabla de procesos BCP Proceso A Estado (registros) BCP Proceso B Estado (registros) BCP Proceso N Estado (registros) Información de identificación Información de identificación Información de identificación Información de Control Información de Control Información de Control Estado 14 15/12/2009 Planificación de procesos I Los procesos migran entre varias colas: Cola C l trabajos t b j (job): (j b) soporta t todos t d los l procesos del d l sistema  Cola Listos (ready) ready):: soporta todos los procesos que residen en memoria memoria,, preparados para ser ejecutados  Colas Bloqueados Bloqueados:: soportan los procesos que esperan por un dispositivo p p de E/S Planificación de procesos II: Colas de listos y bloqueados 15 15/12/2009 Planificación de procesos III Llamadas al sistema I pid = fork fork() () Crea un proceso idéntico al padre int execl(const char *path, const char *arg, ...) int execlp(const char *file, *file const char *arg, *arg ...)) int execvp(const char *file, char *const argv[]) Reemplaza la imagen del proceso ((código+entorno código+entorno)) exit(status) exit (status) Termina la ejecución del proceso y devuelve el estado pid = waitpid waitpid((pid, pid, & &statloc statloc,, options) options) E Espera la l terminación t i ió de d un hijo hij pid_t getpid( getpid(void) void) Devuelve el identificador del proceso. pid_t getppid( getppid(void) void) Devuelve el identificador del proceso padre. 16 15/12/2009 Llamadas al sistema. Fork #include types.h> pid = fork fork((void void)) Crea un proceso idéntico al padre Devuelve: – El identificador de proceso hijo al proceso padre y 0 al hijo – -1 el caso de error Descripción : – Crea un proceso hijo que ejecuta el mismo programa que el padre – Hereda los ficheros abiertos (se copian los descriptores). – Las alarmas pendientes se desactivan. Llamadas al sistema. Fork Mapa de memoria Imagen del proceso A Tabla de procesos BCP A El proceso A hace un fork y crea el proceso hijo B Mapa de memoria Imagen del proceso A Imagen del proceso B Tabla de procesos BCP A BCP B Nuevo PID Nueva descripción de memoria Distinto valor de retorno (0 en el hijo) 17 15/12/2009 Llamadas al sistema.Exec int execl(const char *path, const char *arg, ...) int execlp(const char *file, const char *arg, ...) int execvp(const char *file, char *const argv[]) Reemplaza la imagen del proceso (código+entorno ((código código+entorno) código entorno) entorno) Argumentos: path, file: nombre del archivo ejecutable arg: argumentos Descripción: Devuelve -1 en caso de error, en caso contrario no retorna. Cambia la imagen de memoria del proceso. El mismo proceso ejecuta otro programa. Los ficheros abiertos permanecen abiertos Las señales con la acción por defecto seguirán por defecto, las señales con manejador tomarán la acción por defecto. Llamadas al sistema.Exec Mapa de memoria I Imagen del proceso Tabla de procesos El proc eso h hac e un exec BCP Mapa de memoria Tabla de procesos BCP Se borra la imagen de memoria Se borra la desc ripción de la memoria y registros Se c onserva el PID Objeto ejecutable Biblioteca sistema Cargador Mapa de memoria Imagen del proceso Tabla de procesos BCP Se c arga la nueva imagen Se pone PC en direcc ión de arranque Se c onservan los fd 18 15/12/2009 Llamadas al sistema. Exit y Wait int exit( exit(int status) Argumentos: – Código de retorno al proceso padre Descripción: – Finaliza la ejecución del proceso. – Se cierran todos los descriptores de ficheros abiertos. Se liberan todos los recursos del proceso pid = waitpid waitpid((pid, pid, & &statloc statloc,, options) options) Espera la terminación de un hijo Argumentos: g – Devuelve el código de terminación del proceso hijo. Descripción: – Devuelve el identificador del proceso hijo o -1 en caso de error. – Permite a un proceso padre esperar hasta que termine un proceso hijo. Devuelve el identificador del proceso hijo y el estado de terminación del mismo. Llamadas al sistema. Exit y Wait I El padre muere: INIT acepta los hijos Init Init Init Proceso A fork() Proceso A Proceso A exit() Proceso B Proceso B Init wait() Init wait() Proceso B Proceso B exit() 19 15/12/2009 Llamadas al sistema. Exit y Wait II Zombie: el hijo muere y el padre no hace wait Init Init Init Init Init Proceso A fork() Proceso A Proceso A Proceso A Proceso A wait() Proceso B Proceso B exit() Proceso B zombie Proceso B zombie Llamadas al sistema.Ejemplo Código C para crear un proceso int main() { pid t pid; pid_t pid = fork(); if (pid < 0) { fprintf(stderr, "Fork ha fallado"); exit(-1); } else if (pid != 0) { …. wait(NULL); exit(0); } else { execlp ("/bin/ls", "ls", NULL); } } /* crea un proceso /* error /* Es el padre /* Código del padre /* Espera el fin del hijo /* El padre termina /* Es el hijo /* Ejecutar código 20 15/12/2009 Threads Concepto de thread Modelos multithread Diseño con threads Threads en Linux Threads en Java Pthreads (POSIX threads) Concepto de thread I Proceso sencillo y multithread: código registros datos ficheros ficheros código datos pila registros registros registros registros registros pila pila pila thread thread Proceso con un único thread Proceso con varios threads 21 15/12/2009 Estados de los threads • Por thread – Contador de programa, Registros – Pila – Procesos ligeros hijos – Estado (ejecutando, listo o bloqueado) • Por proceso – Espacio de memoria – Variables globales – Ficheros abiertos – Procesos hijos – Temporizadores – Señales y semáforos – Contabilidad Proceso Bloqueado por comunicación Bloqueado por acceso a disco Activo Procesos ligeros Tipos de Threads Threads-kernel (ULT): Gestión the thread en el kernel Conocidos y g gestionados p por el núcleo del sistema operativo. p Ej, libpthread en Linux o threads en WindowsNT Threads de usuario (KLT): Gestión the threads a nivel biblioteca de usuario Conocidos y gestionados por el lenguaje (ej, Java) o una biblioteca de funciones de usuario sin que el núcleo del sistema operativo los conozca Ej Mach c-threads, Ej, c threads fibras de WindowsNT Threads mixtos Conocidos y gestionados por una biblioteca de funciones de usuario que recurre al núcleo del sistema operativo para implementarlos vinculación o binding según distintas relaciones: 1 a 1, o varios a 1. 22 15/12/2009 Modelos de vinculación de Threads I  Many Many--to to--One: varios threads de usuario soportados en un thread del kernel Solaris Green Threads GNU Portable Threads Threads de usuario K Thread del kernel  One One--to to--One: cada thread de usuario está soportado en un thread th d del d l kernel k l Windows NT/XP/2000 Linux Threads de usuario Solaris posteriores a v9 K K K K Threads del kernel Modelos de vinculación de Threads II  Many Many--to to--Many: varios threads de usuario soportados en varios thread del kernel Solaris v9 Threads de usuario Windows NT K K K Thread del kernel  Dos niveles niveles:: similar a M:M pero cada thread de usuario se puede enlazar con un thread del kernel Solaris v8 Threads de usuario K K K K Thread del kernel 23 15/12/2009 Paralelización utilizando threads Procedimiento 1 P Procedimiento 2 F P Espera en E/S jecuc ó F Ejecución Espera en E/S serie Procedimiento 1 P F Espera en E/S Ejecución paralela p P Procedimiento di i t 2 P F Espera en E/S Procesamiento Threads en el diseño de servidores Núcleo P t Puerto Núcleo P t Puerto S o lic itu d e s P t Puerto S o lic itu d e s Núcleo S o lic itu d e s Trabajador abajado Distribuidor 24 15/12/2009 Diseño con threads • Proceso con un solo thread – No hay paralelismo • Llamadas al sistema bloqueantes – Paralelismo gestionado por el programador • Llamadas al sistema no bloqueantes • Múltiples p p procesos cooperando p – Permite paralelismo gestionado por el SO – No comparten variables – Mayor sobrecarga de ejecución Linux Threads • Proceso varios threads – Paralelismo y variables compartidas – Llamadas al sistema bloqueantes por thread – Permite división de tareas – Aumenta la velocidad de ejecución del trabajo – Programación concurrente • Simplicidad vs exclusión • Imaginar otra llamada al mismo código • Mutex • Variables globales Linux Threads  Linux se refiere a los threads como “tareas tareas” ” ((tasks tasks))  La creación de threads se realiza mediante la llamada al sistema clone()  clone() permite a la tarea hija compartir el espacio de direcciones de la tarea padre ((proceso proceso)) Java Threads Java threads se pueden crear: crear: Extendiendo la claseThread Implementando el interfaz Runnable Los threads en Java los gestiona gestiona:: La JVM: green threads El SO: correspondencia 1 a 1. 25 15/12/2009 PThreads  El API del standard POSIX (IEEE 1003.1c) 1003 1c) para creación y sincronización de threads  Este API especifíca el comportamiento de la biblioteca de thread, la implementación será el desarrollo de las especificaciones de esta biblioteca  Es muy y normal en SSOO tipo p UNIX ((Solaris,, Linux,, Mac OS X) Servicios POSIX para threads int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*func)(void *), void *arg) Crea un thread que ejecuta "func" con argumento "arg" y atributos "attr". Los atributos permiten especificar: tamaño de la pila, pila prioridad, prioridad política de planificación, etc. Existen diversas llamadas para modificar los atributos. int pthread_join(pthread_t thid, void **value) Suspende la ejecución de un thread hasta que termina el thread con identificador "thid". Devuelve el estado de terminación del thread. int pthread_exit(void *value) Permite a un thread finalizar su ejecución, indica el estado de terminación. pthread_t pthread_self(void) Devuelve el identificador del thread que ejecuta la llamada llamada. int pthread_attr_setdetachstate(pthread_attr_t *attr, int detachstate) Establece el estado de terminación de un thread. Si "detachstate" = PTHREAD_CREATE_DETACHED el thread liberara sus recursos cuando finalice su ejecución. Si "detachstate" = PTHREAD_CREATE_JOINABLE no se liberarn los recursos, es necesario utilizar pthread_join(). 26 15/12/2009 Jerarquía de threads threads Proceso ligero A p_create p_create p_create No independ. Proceso ligero D Proceso ligero B Proceso ligero C p_exit p_join p_exit Programa de ejemplo I #include #include #define MAX_THREADS 10 void func(void) { printf("Thread %d \n", pthread_self()); pthread_exit(0); } main() { int j; pthread_attr_t attr; pthread_t thid[MAX_THREADS]; pthread attr init(&attr); pthread_attr_init(&attr); for(j = 0; j < MAX_THREADS; j ++) pthread_create(&thid[j], &attr, func, NULL); for(j = 0; j < MAX_THREADS; j ++) pthread_join(thid[j], NULL); } 27 15/12/2009 Programa de ejemplo II #include #include #define MAX_THREADS 10 void func(void) { printf("Thread %d \n", pthread_self()); pthread_exit(0); } main() { int j; pthread_attr_t attr; pthread_t thid[MAX_THREADS]; pthread_attr_init(&attr); pthread_attr_setdetachstate(&attr,PTHREAD_CREATE_DETACHED); for(j = 0; j < MAX_THREADS; j ++) pthread_create(&thid[j], &attr, func, NULL); sleep(5); } Planificación Planificación a medio y largo plazo Planificación a corto plazo FIFO ó FCFS SJF, SRTF Prioridades Round Round--robin Tiempo real Planificación de Pthreads Planificación en POXIS Planificación en Linux Planificación en Windows Windows--NT Servicios POXIS para planificación 28 15/12/2009 Planificación de la CPU • Planificación – A largo plazo (añadir procesos a ejecutar) – A medio plazo (añadir procesos a RAM desde disco) – A corto t plazo l ((qué é proceso titiene lla UCP) – Planificación de E/S • Tipos de planificación – Sin expulsión: el proceso conserva la UCP mientras desee. – Con expulsión: el SO quita la UCP al proceso Exige un reloj que interrumpe periódicamente • Colas de procesos – Por prioridad – Por tipo Planificación a medio y largo plazo Nuevos de estados de los procesos:  En espera (Bach): Espera entrar en el sistema  Suspendido Suspendido:: En espera de asignación de memoria Suspendido y bloqueado Suspendido y lista 29 15/12/2009 Estados de los procesos II Diagrama de estados de los procesos: En espera Suspendido y listo se expulsa a disco se interrumpe Suspendido y bloqueado Zombie Ejecución Listo se recupera de disco Termina la E/S o el evento termina se admite se planifica Espera E/S o un evento Termina la E/S o el evento se expulsa a disco Bloqueado Planificación a corto plazo • Planificación a corto plazo: cuando un proceso: 1. Se bloquea 2 Pasa 2. P d de ejecutando j t d a lilisto t 3. Pasa de bloqueado a listo 4. Termina • La planificación en los casos 1 y 4 es no expulsora (nonpreemptive) • En el resto de casos es expulsora (preemptive) 30 15/12/2009 Criterios de planificación • MÁXIMIZAR – Utilización de la CPU – que sea máxima – Productividad bach (throughput) – # de procesos que se procesan por unidad de tiempo p • MÍNIMIZAR – Tiempo de respuesta (Turnaround) – tiempo en ejecutar un trabajo en particular – Tiempo de espera – tiempo que un proceso pasa en la cola de listos – Tiempo de respuesta interactivo– tiempo que pasa desde que se envía el trabajo hasta que se obtiene una respuesta • CONSEGUIR – Reparto equitativo del procesador – Cumplimiento de plazos (tiempo real) – Calidad de servicio (sistemas multimedia) Algoritmos de planificación I • • FIFO ó FCFS – Organización en una lista ordenada por tiempo de llegada SJF, SRTF – Organización en lista ordenada por tiempo previsto de ejecución • Bach: tiempo previsto para la ejecución de un proceso • Interactivo: tiempo previsto para la próxima ráfaga de CPU • • • • Prioridades – Fíjas o dinámicas – Organización en una lista ordenada por prioridades calculadas Round--Robin Round – Organización en una lista circular con “quantos” de tiempo – Expropiación por agotamiento del quanto y replanificación Lotería – Se asigna a cada proceso un rango de valores y se genera un número a leatorio Tiempo real – A plazo fijo: EDF (prioridades dinámicas) – Periódicos: RMS (prioridades estáticas) 31 15/12/2009 FIFO ó First First--Come, First First--Served (FCFS) I Procesos T. cómputo P1 24 3 P2 P3 3 Suponiendo que los procesos llegan en el siguiente orden P1 , P2 , P3 • El diagrama de Gantt es: P1 P2 0 24 P3 27 30 • Tiempo de espera para: P1 = 0; P2 = 24; P3 = 27 • Tiempo medio de espera: (0 + 24 + 27)/3 = 17 FIFO ó First First--Come, First First--Served (FCFS) II Suponiendo que los procesos llegan en el siguiente orden P2 , P3 , P1 • El diagrama de Gantt es: P2 0 • • • • P3 3 P1 6 30 Tiempo de espera para: P1 = 6; P2 = 0; P3 = 3 Tiempo medio de espera: (6 + 0 + 3)/3 = 3 Mucho mejor que el caso anterior Efecto Convoy: los procesos cortos detrás de los largos 32 15/12/2009 Shortest--Job Shortest Job--First (SJF) Scheduling I • Asocia a cada proceso el tiempo previsto de ejecución. Selecciona para ejecutar el proceso con menor tiempo. • Dos esquemas: – No expulsor (nonpreemptive) – una vez planificado sigue en la CPU hasta que completa su ráfaga de CPU. – Expulso Expulsor (preemptive) – si llega un nuevo proceso con un tiempo menor que el que se está ejecutanto, este último se expulda. También se llama Shortest-Remaining-Time-First (SRTF) • SJF es óptimo – da el menor tirmpo de espera medio para un conjunto de procesos. • Problema Problema:: se debe suministrar el siguiente tiempo de ráfaga -> estimación teniendo en cuenta las anteriores Ejemplo de SJF no expulsivo Procesos P1 P2 P3 P4 • SJF (no-expulsivo) T. llegada T. cómputo 0.0 20 2.0 4.0 5.0 7 4 1 4 P1 0 3 P3 7 P2 8 P4 12 16 • Tiempo medio de espera = (0 + 6 + 3 + 7)/4 = 4 33 15/12/2009 Ejemplo de SJF expulsivo Procesos T. llegada T. cómputo 0.0 2.0 4.0 5.0 7 4 1 4 P1 P2 P3 P4 • SJF (expulsivo) P1 0 P2 2 P3 4 P2 5 P4 7 P1 11 16 • Tiempo medio de espera = (9 + 1 + 0 +2)/4 = 3 Planificación basada en prioridades I • Se asocia un número de prioridad (entero) a cada proceso • La CPU ejecuta el proceso de mayor prioridad (menor entero  mayor priodad) – Expulsivo – No expulsivo • SJF es un planificador de prioridad, en el que la prioridad es el tiempo de cómputo de cada ráfaga de CPU (a menor ráfaga mayor prioridad). i id d) • Problema  Inanición (starvation) – el proceso de menor prioridad puede no ejecutarse nunca • Solución  Envejecimiento (aging) – a medida que pasa el tiempo, el proceso aumenta su prioridad 34 15/12/2009 Planificación basada en prioridades II • Establecimiento de prioridades: • Interno Interno:: uso de la memoria, bloqueos de E/S, duración estimada de la siguiente ráfaga de CPU Procesos T. llegada T. Ráfaga estimado Prioridad P1 P2 P3 P4 0.0 2.0 4.0 5.0 7 4 1 4 3 2 1 2 • Externo: coste, frecuencia, importancia,.. Procesos P1 P2 P3 P4 T. llegada 0.0 2.0 4.0 5.0 Frecuencia 1 3 6 2 Prioridad 4 2 1 3 Round Robin (RR) • Cada proceso tiene una unidad de tiempo de CPU (quantum), normalmente 10-100 milliseg. Cuando pasa el proceso es expulsado y puesto en la cola de Listos p • Si hay n procesos en la cola de Listos, y el quantum es q, a cada proceso le toca 1/n del tiempo CPU en trozos de al menos q unidades de tiempo cada uno. • Ningún proceso espera más de (n-1)q unidades de tiempo. • Performance – q grande  FIFO – q pequeño  q debe ser grande respecto al tiempo de cambio de contexto (latencia) para que el overhead no sea demasiado grande 35 15/12/2009 Ejemplo de RR con Quantum = 20 Process P1 P2 P3 P4 • El diagrama de es: P1 0 P2 20 37 P3 Burst Time 53 17 68 24 P4 57 P1 77 P3 97 117 P4 P1 P3 P3 121 134 154 162 • Normalemente , la media de turnaround es mayor que en SJF, pero mejor tiempo de respuesta El quantum y la latencia de cambio de contexto 36 15/12/2009 El tiempo de Turnaround varía con el Quantum Colas multilevel I • La cola de Listos se particiona en colas separadas : foreground (interactivo) background (batch) • Cada cola tiene su propio algoritmo de planificación – foreground – RR – background – FCFS • La planificación se aplica entre las colas: – Planificación de prioridad fija; (se sirven todos de foreground y después de background) background). Se puede producir inanición inanición. – Rodaja de tiempo – cada cola tiene una cierta cantidad de tiempo de CPU time que se reparte entres sus procesos; – ej.., 80% to foreground in RR y 20% to background in FCFS 37 15/12/2009 Colas multilevel II Colas multilevel con realimentación • Tres colas: – Q0 – RR con quantum de 8 milisegundos y FIFO – Q1 – RR con quantum de 16 milisegundos y FIFO – Q2 – FIFO • Planificación – Un nuevo trabajo llega a la Q0 con planificación FIFO. Cuando gana la CPU, se ejecuta 8. Si no termina se mueve a Q1. – En Q1 se sirve con FIFO y se le dan 16 m. Si no termina se mueve a Q1. 38 15/12/2009 Planificación en Tiempo real • Tiempo real duro o crítico (Hard real-time) – las tareas se debe complentar dentro de un plazo preestablecido (con unas garantías de tiempo) – RMA: Asignas las prioridades según la frecuencia (tareas periódicas e independientes). Garantiza que cumplen el plazo para una utilización del procesador < 70% – EDF: Primero la tarea que antes cumpla en plazo (prioridades dinámica). Más dificil de implementar que el anterior. La utilización del procesador puede ser del 100% • Tiempo real blando o no crítico (Soft real-time) – las tareas críticas deben teber prioridades más altas que las que no lson de tiempo real. Planificación en Tiempo real. RMS I Tarea 1 2 3 Cómputo 4 Plazo= T Prioridad 10 1 4 15 2 10 35 3 1 2 3 tiempo Tiempo de cómputo (C) Fin de periodo (T = Periodo ) 39 15/12/2009 Planificación en Tiempo real. RMS II Ci Utilización del procesador pora una tarea i Utilization del procesador para n tareas Ui = Ti 1 U(n) = n(2n - 1) Resultados: • Si  Ui ≤ U(n) el conjunto de tareas es planificable. planificable • If  Ui > 1 el conjunto de tareas es no planificable. • Si U(n) <  Ui ≤ el conjunto de tareas es inconcluso *si todas las tareas cumplen su plazo en el primer hiperperiodo el conjunto de tareas es planificable. Planificación en Tiempo real. RMS III Tarea Cómputo 1 2 3 4 Plazo= T Prioridad 10 1 4 15 2 10 35 3 U(3) = 3(21/3 – 1) = 0.779 U1 = 4 / 10 = 0.4 U2 = 4 / 15 = 0.267 0 267 U3 = 10 / 35 = 0.286 Utotal = 0.953 Resultados: U1+2 = 0.667, planificanle. Sin embargo, 0.779 < 0.953 < 1 Por lo que es inconcluso para 3. Si las tareas cumplen el plazo en el primer HIPERPERIODO (35 en este caso) son planificables 40 15/12/2009 Planificación en Tiempo real. EDF • Las prioridades se asignan de acuerdo a sus plazos: El plazo más corto, la prioridad mayor; El plazo más largo, la prioridad menor. Planificación en POSIX I • Cada política de planificación lleva asociado un rango con al menos 32 niveles de prioridad. • El planificador elegirá el proceso o thread con la prioridad más alta • Políticas de planificación – Para compartición de tiempo – prioridad variable • Otra (SCHED_OTHER) – Para tiempo real – prioridad fija, superior a SCHED_OTHER • FIFO (SCHED_FIFO) • Cíclica (SCHED_RR) 41 15/12/2009 Planificación SCHED_OTHER en LINUX • Funcionamiento general – LINUX divide el tiempo de CPU en épocas (epoch) – En cada época cada proceso tiene un quantum de tiempo que se le asigna al comenzar la época – Cuando un proceso agota su quantum se le expulsa y se selecciona otro proceso ejecutable – Un proceso puede ser seleccionado múltiples veces mientras le quede quantum • Por ejemplo, puede haber sido expulsado tras una E/S, propia o ajena, y luego vuelto a asignar la CPU – La época termina cuando todos los procesos ejecutables han agotado su quantum • En E ese momento, t se reasigna i los l quantum t para la l é época siguiente LINUX favorece los procesos que no han agotado su quantum en la época anterior • La prioridad está relacionada con el quantum restante (a mayor quantum, mayor prioridad) Planificación Pthread • Políticas de planificación a definir como en procesos. • Ambitos de planificación: p – PTHREAD_SCOPE_PROCESS: Planificación local – La librería de threads decide que thread se ejecuta. – PTHREAD_SCOPE_SYSTEM: Planificación global – El kernel decide qué thread se ejecuta. • Los atributos de planificación se pueden añadir mediante servicios a los atributos de creación de un thread: • #include – – – – int pthread_attr_setscope(pthread_attr_t *attr, int scope); int pthread_attr_getscope(const pthread_attr_t *attr, int *scope); int pthread_attr_setschedpolicy(pthread_attr_t *attr, int policy); int pthread_attr_getschedpolicy(const pthread_attr_t *attr, int *policy); 42 15/12/2009 Planificación en Windows NT I Reiniciado Iniciado Sit Situar en lla cola l de listos Finalizado Fin de bloqueo Bloqueado Ejecución finalizada Espera terminada Bloqueado Pila del kernel en swap Pila del kernel en memoria Transición Listo Seleccionado Expulsado para ejecución Expulsado Ejecución Cambio de contexto. Comienzo de ejecución Reserva Planificación en Windows NT II Pt: Prioridades relativas de threads Promoción dinámica: +n si se desbloquea (hasta 15) Decaimiento dinámico: -1 si agota el quantum (hasta Pt) Anti-inanición: Si no se ha ejecutado en los últimos 3 segundos, adopta prioridad 15 para ejecutar 2*quantum 43 15/12/2009 Servicios POSIX para planificación I #include • Modificar la prioridad de un proceso – int sched_setparam(pid_t pid, const struct_param *param); • Modificar la prioridad y la política – int sched_setscheduler(pid_t pid, const sched_param *param); • Obtener los parámetros de planificación de un proceso – int sched_getparam(pid_t pid, const struct_param *param); • Obtener la prioridad de un proceso – int sched_getscheduler(pid_t pid); Capítulo 4: Gestión de procesos Señales y excepciones Temporizadores Servidores y demonios 44 15/12/2009 Señales I Señal: Mecanismo por el que un proceso puede ser notificado de, o afectado por, un evento que se produce en el sistema: - excepciones detectadas por hardware - expiración de una alarma o temporizador - finalización de una operación de I/O asíncrona - llegada de un mensaje - invocación de la función kill() y similares -actividad del terminal, etc. Número de señal: •Entero positivo que identifica una señal. •Existen también constantes predefinidas para dar nombre a las señales Señales II • Las señales son interrupciones al proceso • Envío o generación – Proceso Proceso- Proceso (dentro del grupo) con el kill – SO - Proceso Señal Proceso Código Función tratamiento 45 15/12/2009 Señales III  Una señal se puede generar para un proceso o para un thread.  Cada thread tiene una máscara de señales, señales, que define las señales bloqueadas bloqueadas..  La máscara se hereda del padre  Señal no bloqueada: bloqueada: se entrega  Ignorar  Terminar el proceso  Ejecutar manejador  Señal bloqueada: bloqueada: queda pendiiente hasta que se acepta con sigwait() sigwait() Tratamiento de señales I  Opciones para tratar una señal señal::  Enviar la señal al thread al q que la señal se refiere  Enviar la señal a todos los threads del proceso  Asignar un thread específico para recibir todas las señales del proceso  Cada señal se trata mediante un “manejador “manejador”” 1. La señal se genera por un evento particular 2. La señal se envía al proceso 3. La señal se trata 46 15/12/2009 Tratamiento de señales II • Hay muchos tipos de señales, según su origen • SIGILL instrucción ilegal • SIGALRM vence el temporizador • SIGKILL mata al proceso • El SO las transmite al proceso – El proceso debe estar preparado para recibirla • Especificando un procedimiento de señal con sigaction() • Enmascarando la señal con sigprogmask() – Si no está preparado  acción por defecto • El proceso, en general, muere • Hay algunas señales que se ignoran o tienen otro efecto • El servicio pause() para el proceso hasta que recibe una señal Señales. Ejemplo Unix /* Programa A. Fichero – Fichero padre.c * Manda ejecutar el programa B * Lee caracteres del terminal y cada vez que detecta “salto de linea” * envia una señal al proceso B */ #include #include #include #include pid_t resp; char buf[1]; main() { resp = fork(); if (resp == 0) if (execlp("./hijo","hijo", NULL) == -1) { perror("exec"), exit(1); } while (read(0, buf, 1) == 1) { if (buf[0] == '\n') { kill(resp, SIGUSR2); } } } 47 15/12/2009 Señales. Ejemplo Unix /* Programa B. Fichero hijo.c * Crea un fichero y escribe en él * una línea por cada señal que recibe, hasta un máximo de 5 */ #include #include #include int fd, n=5; void proc(int arg) { n--; return; } int main() { signal(SIGUSR2, proc); if ((fd = open("fichero", O_CREAT|O_TRUNC|O_WRONLY)) == -1) { perror("open"); exit(1); } while (n!= 0) { pause(); write(fd, "Linea\n", 7); } return 0; } Excepciones • Evento que ocurre durante la ejecución de un programa y que requiere la ejecución de un fragmento de código fuera del flujo normal de ejecución. • Manejo de excepcion en Java try { Bloque donde puede producirse una excepción } catch { Bloque que se ejecutará si se produce una excepción en el bloque anterior } 48 15/12/2009 Temporizadores • El SO mantiene un temporizador por proceso – El proceso activa el temporizador con alarm() • El SO envía una señal SIGALRM al proceso cuando vence su temporizador Proceso servidor • Es un proceso que: – Está pendiente de recibir órdenes de un proceso “cliente” – Estructura de bucle infinito – Uso de puertos de comunicación PROCESOS CLIENTES PROCESO SERVIDOR RECURSO • Servidor secuencial: – El servidor mismo ejecuta las órdenes • Servidor paralelo: – Delega ejecución las órdenes a threads o procesos hijos 49 15/12/2009 Proceso servidor. Funcionamiento a) b) c) Servidor Padre Servidor Padre Servidor Padre Servidor Hijo Puerto A Puerto A Puerto A Puerto B Cliente A Cliente A Proceso servidor. Máquinas distribuidas Procesos cliente y servidor en máquinas distintas Puerto Cliente Servidor ficheros Servidor impresión Servidor e_mail SO SO SO SO RED 50 15/12/2009 Procesos demonios • Es un proceso que ejecuta: – – – – – En background (su padre no le espera) No asociado a un terminal o proceso login Que espera que ocurra un evento Funciona como servior O que debe realizar una tarea de forma periódicas • Características – – – – Se arrancan al iniciar el sistema No mueren Están normalmente en espera de evento No hacen el trabajo, lanzan otros procesos o procesos ligeros • Ejemplos:Telnetd, httpd, lpd Servicios POSIX para señales I include #include g Manipular conjuntos de señales: int sigemptyset (sigset_t *set); int sigfillset (sigset_t *set); int sigaddset (sigset_t *set, int signo); int sigdelset (sigset_t *set, int signo); int sigismember (const sigset_t *set, int signo); Estas funciones no afectan de forma directa al comportamiento del sistema 51 15/12/2009 Servicios POSIX para señales II Examinar y cambiar la acción asociada a una señal (armado): int sigaction (int sig, const struct sigaction *act, struct sigaction *oact); • si act es NULL, la acción actual no se cambia • si oact no es NULL, la acción actual se devuelve en *oact Enviar una señal a un proceso: int kill (pid_t pid, int sig); Enviar una señal a un thread: pthread kill(pthread t thread, pthread_kill(pthread_t thread int sig); sig) Aceptar una señal bloqueada: int sigwait (const sigset_t *set, int *sig); Servicios POSIX para señales III Máscara de señales: int sigprocmask (int how, sigset_t *set, sigset_t *oset); • Permite modificar o examinar la máscara de señales de un proceso. int sigpending (sigset_t *set); • Devuelve el conjunto de señales bloqueadas pendientes del proceso. Espera de señales: int pause(void); • Bloquea al proceso hasta que llegue una señal. Servicios de temporización: unsigned int alarm(unsigned int seconds); • Activa un temporizador unsigned int sleep(unsigned int seconds); • El proceso se suspende en num de segundos. 52