Clase Iii - Planificacion De Procesos. Parte 1

Presentación

Planificación de Procesos. Parte 1 INGENIERÍA EN INFORMÁTICA Sistemas de Operación

UNIVERSIDAD NACIONAL EXPERIMENTAL DE GUAYANA Sistemas Operativos

Introducción • Planificador: módulo del SOP que controla la utilización de un recurso. • La ejecución de un proceso consta de ciclos sucesivos ráfagas de CPU-E/S

Sistemas Operativos

Introducción • Objetivos del Planificador: § Dar una participación adecuada del reparto de tiempo de CPU § Equilibrar el uso de recursos (load balancing). § Aplicar las políticas generales del SOP (prioridades, seguridad, etc.). § El resto depende del tipo de SOP (por lotes, tiempo real, distribuido, etc.).

Sistemas Operativos

Introducción • Problemas: § Alcanzar todos los objetivos puede provocar contradicciones. § El comportamiento de los procesos es impredecible ⇒ hay que estar preparado para manejar todos los casos posibles.

Sistemas Operativos

Introducción • Cola de planificación: § Conjunto de procesos esperando por la utilización de un determinado recurso. § Cada elemento es una estructura de control que representa la petición a servir. § Se administra según con la política de planificación usada por el planificador del recurso.

Sistemas Operativos

Introducción • Colas de procesos: § El SOP organiza los BCPs en colas de espera por el procesador o por los dispositivos de E/S.

Sistemas Operativos

Introducción • Colas de estados: § El SOP mantiene una cola de BCPs por estado, cada una de las cuales contentiva de los procesos que están en ese estado. § Al crear un proceso, su BCP se encola en la cola acorde a su estado actual. § Conforme un proceso cambia de estado, su BCP es retirado de la cola de su estado actual y encolado en la cola de su nuevo estado. § El SOP se puede modelar como un conjunto de procesadores y de colas. Sistemas Operativos

Introducción

Sistemas Operativos

Introducción a) Cola de trabajos: conjunto de todos los procesos del sistema. b) Cola de preparados: conjunto de todos los procesos que residen en memoria principal, preparados y esperando para ejecutarse. c) Cola(s) de espera: conjunto de todos los procesos esperando por un dispositivo de E/S particular o por un suceso (búfer de memoria, un semáforo, etc.). d) PCP (Planificador de Corto Plazo): o También llamado planificador de trabajos. o Asigna / desasigna la CPU a la cola de procesos preparados. o Debe ser muy rápido (frecuencias cortas). Sistemas Operativos

Introducción e) PLP (Planificador de Largo Plazo): o Para sistemas por lotes. o Suministra procesos normalmente almacenados en disco y los envía a la cola de preparados. o Se ejecuta a frecuencias largas. o Controlan el grado de multiprogramación (número de procesos en memoria). o UNIX no lo usa (los procesos pasan directamente a la cola de preparados una vez creados). o Deben seleccionar una mezcla de procesos limitados por E/S y limitados por CPU.

f) PMP (Planificador de Medio Plazo): o Usado por algunos SOPs como los de t-compartido. o Envía al disco procesos de poco interés (swapping).

Sistemas Operativos

Introducción

Sistemas Operativos

Introducción a) Cuando un proceso desea entrar en el sistema se coloca en una cola de trabajos a esperar que se le asigne memoria. b) Cuando a un trabajo se le asigna memoria, entra en la cola de procesos listos. c) Cuando un proceso realiza una operación de E/S pasa a una cola de dispositivo asociada al dispositivo en el que realiza la operación de E/S.

Sistemas Operativos

Mecanismos y Políticas • Un mecanismo es el código (a menudo de bajo nivel) que manipula un recurso: § CPU: cambio entre procesos, etc. § Memoria: asignar, liberar, etc. § Disco: leer, escribir, etc.

• Una política decide cómo, quién, cuándo y por qué: § ¿Cuánta CPU obtiene un proceso? § ¿Cuánta memoria se le da? § ¿Cuándo escribir en disco? Sistemas Operativos

Mecanismos y Políticas • En el diseño de un SOP es conveniente tratar de mantener separado los mecanismos de las políticas: § Facilita la reutilización de mecanismos. § Permite la adaptación de políticas.

• Un tema común de investigación es la separación de políticas y mecanismos: § En algunos casos el mecanismo de uno es la política de otro. § Reduce considerablemente el nivel de abstracción ⇒ Orientación a objetos. Sistemas Operativos

Mecanismos y Políticas • Políticas de planificación - planificar cuando se conmuta entre estados: § § § §

De ejecutándose a bloqueado. De ejecutándose a preparado. De bloqueado a preparado. De ejecutándose a finalizado.

⇒ Siempre que un proceso abandona la CPU, o se inserta un proceso en la cola de preparados.

Sistemas Operativos

Mecanismos y Políticas • Dos tipos de políticas (dos maneras de hacer la multiprogramación): 1) No apropiativa: § Una vez que un proceso está activo continúa ejecutándose hasta que: a) Termina. b) Se bloquea por el inicio de una operación de E/S o un servicio solicitado por el SOP. c) El propio proceso hace una llamada al SOP para ceder el procesador a otro proceso.

§ Un proceso con mucho tiempo de procesador y pocas E/S puede monopolizar el uso de CPU. § Usada por MS-DOS y MacOS. Sistemas Operativos

Mecanismos y Políticas 2) Apropiativa / preferente / expulsiva: § El SOP puede interrumpir en cualquier momento el proceso activo con el objeto de dar paso a otro proceso que esté preparado. § Hace uso de un algoritmo determinado de planificación: turno aleatorio (round robin), por prioridad, FCFS (First Come First Served), SPN (Shortest Process Next), SRT (Shortest Remaining Time). § Usada por MS-Windows, UNIX y Linux.

Sistemas Operativos

Mecanismos y Políticas • Apropiación vs No apropiación: § La apropiación asegura que un trabajo no bloquea a otro igualmente importante. § ¿Tamaño de la fracción de tiempo? → afecta tiempo de respuesta y productividad. § No apropiar requiere que los trabajos invoquen explícitamente al planificador → Un trabajo erróneo puede “congelar” el sistema.

Sistemas Operativos

Despachador • Despachador (dispatcher): da el control de la CPU al proceso seleccionado por el planificador (scheduler). • Realiza lo siguiente: § Cambio de contexto (en modo núcleo). § Conmutación a modo usuario. § Salto a la instrucción del programa para su reanudación.

• Latencia de despacho: tiempo que emplea el despachador en detener un proceso y comenzar a ejecutar otro. Sistemas Operativos

Despachador • Ejemplo:

Sistemas Operativos

Despachador • El despachador obtiene el control de forma: § Síncrona – un proceso cede la CPU. § Asíncrona – iniciado por una interrupción u ocurrencia de un evento que afecta a un proceso (ej: fin de E/S, liberación de recurso, etc.).

• El gestor de interrupciones: 1. Salva el contexto del proceso en ejecución. 2. Determina el tipo de interrupción y ejecuta la rutina de servicio correspondiente. 3. Selecciona el proceso a ejecutar → Restaura su contexto. Sistemas Operativos

Criterios de Planificación • Utilización: mantener la CPU tan ocupada como sea posible. • Productividad: número de procesos que completan su ejecución por unidad de tiempo. • Tiempo de retorno: cantidad de tiempo necesario para ejecutar un proceso dado.

Sistemas Operativos

Criterios de Planificación • Tiempo de espera: tiempo que un proceso ha estado esperando en la cola de preparados. • Tiempo de respuesta: tiempo que va desde que se remite una solicitud hasta que se produce la primera respuesta.

Sistemas Operativos

Criterios de Planificación • Métricas: § § § § §

Máxima utilización. Máxima producción. Mínimo tiempo de retorno. Mínimo tiempo de espera. Mínimo tiempo de respuesta.

• Los algoritmos de planificación se diseñan en base a considerar una o más de estas métricas. • En la mayoría de los casos la mejora de una métrica puede perjudicar a otra. Sistemas Operativos

FCFS • Primero en llegar, primero en ser servido. • Se respeta el orden de llegada de los procesos → cola (FIFO – Primero en llegar, Primero en Salir). • Buscar mejorar el tiempo de respuesta. • Afecta los tiempos medios de espera (si los primeros procesos son largos, los demás deben esperar).

Sistemas Operativos

FCFS • Es simple de implementar (basta manejar una cola). • Es muy sensible al orden de llegada de los procesos. • Perjudica a los procesos intensivos en operaciones de E/S (efecto convoy). • Ejemplo: § Suponer los procesos P1, P2 y P3 con tiempos de ráfaga de 24, 3 y 3 respectivamente.

Sistemas Operativos

FCFS § Si los procesos llegan en ese mismo orden {P1, P2, P3}, el tiempo medio de espera (te medio) es (0 + 24 + 27) / 3 = 17.

§ Si se cambia el orden de los procesos {P2, P3, P1}, el te medio mejora (0 + 3 + 6) / 3 = 3.

Sistemas Operativos

FCFS • Ejemplo:

Sistemas Operativos

SPN • Primero el más corto. • Se planifica al proceso cuya siguiente ráfaga es la más corta (menos tiempo de CPU). • La idea es que los procesos cortos no se vean afectados por los largos (aumento en la productividad). • La presencia de muchos procesos cortos pueden perjudicar a los grandes ⇒ riesgo de inanición de los procesos de larga duración. Sistemas Operativos

SPN • Dos versiones: § No apropiativa: el proceso en ejecución no se apropia hasta que complete su ráfaga. § Apropiativa: también conocido como SRTF (primero el de tiempo restante menor); un proceso con ráfaga más corta que el tiempo restante del proceso en ejecución, apropia al proceso actual.

• Minimiza el te medio para un conjunto dado de procesos (no así el tiempo de respuesta). Sistemas Operativos

SPN • Funcionamiento (versión no apropiativa): 1) Asocia a cada proceso un tiempo aproximado de CPU. 2) Asigna la CPU al proceso con menor tiempo. 3) Cuando un proceso consigue la CPU la conserva hasta que decide liberarla.

• La estimación del tiempo de uso de CPU por parte de un proceso puede ser un inconveniente (a veces se modela con técnicas estadísticas). Sistemas Operativos

SPN • Funcionamiento SRTF: 1) Los procesos llegan a la cola y solicitan un intervalo de CPU. 2) Si dicho intervalo es inferior al que le falta al proceso en ejecución para abandonar la CPU, el nuevo proceso pasa a la CPU y el que se ejecutaba a la cola de preparados.

• El intervalo de CPU es difícil de predecir. • Mientras haya trabajos cortos, los procesos largos pueden no ejecutarse → inanición → efecto convoy. Sistemas Operativos

SPN • Si todos los procesos tienen la misma duración de ráfaga, se comporta igual que FCFS. • En la actualidad existen variantes para la planificación de procesos en tiempo-real. • Ejemplo: § Suponer los procesos P1, P2, P3 y P4 con tiempos de ráfaga de 7, 4, 1 y 4 respectivamente.

Sistemas Operativos

SPN • Ejemplo:

Sistemas Operativos

Round-Robin • También conocido como turno rotatorio. • A cada proceso se le asigna una fracción de tiempo (quantum) de CPU (entre 10 y 100 ms). Pasado este tiempo, si no ha finalizado ni se ha bloqueado, el SOP apropia al proceso y lo pone al final de la cola de preparados. • El objetivo principal es realizar una asignación imparcial de la CPU entre los trabajos. Sistemas Operativos

Round-Robin • Es uno de los más utilizados, sencillos y equitativo. • Adecuado para implementar tiempo compartido. • La cola de procesos preparados se gestiona como FIFO. • Si el quantum de tiempo es q y hay N procesos en cola, el tiempo de respuesta es, en el peor de los casos, q(N-1). Sistemas Operativos

Round-Robin • El tiempo de espera medio es: § Bajo si la duración de los trabajos varía. § Malo si la duración de los trabajos es idéntica.

• Por lo general tiene un mayor tiempo de retorno que SRTF pero mejor tiempo de respuesta. • El rendimiento depende del tamaño del quantum (q):

Sistemas Operativos

Round-Robin § Grande ⇒ igual que en FCFS (los procesos terminan sus ráfagas de CPU antes de que termine el quantum). § Pequeño ⇒ mucha sobrecarga si q no es lo suficientemente grande respecto a la duración del cambio de contexto ⇒ baja el rendimiento. § Un q ≥ 0 adecuado tiende a un sistema en el que cada proceso dispone de un procesador a 1/N de la velocidad del procesador real (procesador compartido).

Sistemas Operativos

Round-Robin • Ejemplo: Sean los procesos P1, P2, P3 y P4 con tiempos de ráfaga 53, 17, 68 y 24 respectivamente; sea q = 20.

Sistemas Operativos

Round-Robin • Ejemplo:

Sistemas Operativos

Por prioridades • Cada proceso tiene una prioridad; entra en CPU aquél con mayor prioridad. • La política puede ser expulsiva o no. • Las prioridades se pueden definir de forma interna (por el SOP) o externa (por los usuarios). • Las prioridades pueden ser: a) Estáticas: se asigna antes de la ejecución y no cambia. b) Dinámicas: cambia con el tiempo. Sistemas Operativos

Por prioridades • Si la prioridad es estática, existe riesgo de inanición de los procesos de con menos prioridad. • Una posible solución es manejar envejecimiento ⇒ aumentar progresivamente la prioridad a los procesos en espera (baja prioridad) → prioridades dinámicas.

Sistemas Operativos

Con clases de prioridades • Los procesos se clasifican en distintos grupos: sistema, interactivos, tiempo real, etc. • La cola de procesos preparados consiste en varias colas donde cada una de ellas tiene su propio algoritmo; además existe un algoritmo entre colas (por ejemplo, RR con q alto).

Sistemas Operativos

Con clases de prioridades

Sistemas Operativos

Multiprocesadores • Dos opciones: § Una cola por procesador → la carga puede quedar mal repartida. § Una cola común → el reparto es equilibrado, pero hay riesgos de inconsistencia si varios procesadores manipulan simultáneamente la cola ⇒ sincronización.

Sistemas Operativos