Apuntes sobre sistemas operativos: Procesos: planificación

Planificación de procesos

• Problema: ¿cómo repartir el tiempo de CPU?

• Tipos de procesos
– cálculo: uso intensivo de CPU, pocas operaciones de E/S

– interactivos, E/S: poco uso de CPU, mucha E/S

• interactivos: requieren respuestas rápidas

• E/S: darles prioridad aumenta el aprovechamiento de los recursos

• Objetivos

– realizar la mayor cantidad posible de trabajo por unidad de tiempo

– dar un servicio “razonable” a todos los procesos

• equidad

• respuestas rápidas

• ...

Planificadores

• Planificador a corto plazo

– reparte el tiempo de CPU entre los procesos preparados

– invocado muy frecuentemente (cada 10-100 ms es habitual)

– debe consumir poco tiempo (O(0), a ser posible)

• Planificador a medio plazo

– decide qué procesos pueden competir por la CPU

– mueve procesos de memoria principal a disco: suspensión

– y de disco a memoria principal: activación

• Planificador a largo plazo

– acepta trabajos para su ejecución posterior

– decide en qué orden y cuándo se crean los procesos que ejecutarán los trabajos

– invocación poco frecuente

Diagrama de estados de los procesos

Planificación a corto plazo

• Motivos de invocación

– cuando el proceso en ejecución deja de estar listo

– a intervalos fijos

– cuando hay nuevos procesos listos

• Criterios de evaluación

– porcentaje de utilización de la CPU = 100 · (tútil/ttotal)

– productividad (throughput) = (nº de procesos terminados)/t

– tiempo de retorno; tret = tsal - tlleg

– tiempo ponderado de retorno; w = tret/tejec

– tiempo de espera; tesp = tret – (tcpu + te/s)

– tiempo de respuesta

• Objetivo

– maximizar los dos primeros

– minimizar el resto

Algoritmos de planificación

Atención según el orden de llegada FCFS – First Come-First Served

• Mecanismo

– el procesador lo consigue el proceso más antiguo

– lo mantiene hasta que deja de estar listo (no es expulsivo)

– estructura de datos: lista FIFO de procesos listos

• Características
– garantiza que todos los procesos son ejecutados
– favorece a procesos con pocas interrupciones en el uso de la CPU
– penaliza a los procesos de E/S e interactivos

• E/S: bajo porcentaje de utilización de los dispositivos de E/S

• interactivos: incómodos de utilizar (t. de respuesta muy variable)

Turno rotatorio RR – Round-Robin

• Mecanismo
– cuanto: intervalo máximo de ejecución ininterrumpida
– procesos listos: lista FIFO
– se elige al proceso que está en cabeza de la lista
– expira el cuanto: se pasa el proceso en ejecución al final

• Características
– dependen de la longitud del cuanto

• si es óptimo ->
– la mayor parte de los procesos acaban con un cuanto
– el tiempo de respuesta es razonablemente pequeño

• si es muy grande -> FCFS
– aumenta el aprovechamiento de la CPU

• si es muy pequeño -> el tiempo se dedica a los cambios de contexto
– se reduce el tiempo de respuesta
– reparto equitativo (no se beneficia tanto a los procesos largos)
– con N procesos en la cola, el tiempo máximo de espera es (n-1)·c
– adecuado para sistemas en tiempo compartido
– beneficia a los procesos largos

Turno rotativo virtual VRR – Virtual Round-Robin

• Mecanismo
– existe una lista FIFO auxiliar
– la lista auxiliar tiene preferencia sobre la lista de preparados
– los procesos de la lista auxiliar no obtienen un nuevo cuanto, sólo tienen lo que les queda del obtenido en la lista ordinaria

• Características
– es más equitativo que el RR

Primero el proceso más corto (SPN)
Primero al que menos le queda (SRT)

• Mecanismo
– listos: lista ordenada por duración de los procesos
– se da la CPU al proceso listo más corto (cabeza de la lista)
– cuando llega un nuevo proceso:
• SPN: no se planifica (no es expulsivo)
• SRT: si le queda menos que el que está en ejecución, le expulsa

• Características
– minimizan el tiempo de espera medio

– es necesario estimar la duración del siguiente paso por la CPU
– permiten la inanición de los procesos largos
– SPN: gran variación en el tiempo de espera (inapropiado para sistemas en tiempo compartido)
– lista de preparados:

Planificación por prioridades

• Mecanismo
– a cada proceso se le asigna un número que indica su prioridad
– se elige para ser ejecutado al proceso más prioritario
– (habitualmente un número menor indica mayor prioridad, siendo 0 la prioridad máxima)
– lista de preparados

• lista ordenada por prioridades (izq.)

• vector de listas de preparados (dcha.)

• ¿Qué hacer con procesos con igual prioridad?
– utilizar otro algoritmo de planificación
– habitualmente: FIFO ó round-robin

• ¿Cómo asignar prioridades?
– asignación externa: el administrador, el usuario, el programador...
– asignación interna: según el tiempo de CPU, el tiempo de espera...
– pueden ser fijas (estáticas) o variables (dinámicas)

• Características
– suelen ser expulsivos
– versatilidad (flexibilidad para asignar prioridades)
– pueden producir inanición de lo los procesos poco prioritarios

• ¿Cómo solucionar la inanición?
– aumentando periódicamente la prioridad de los procesos que no han conseguido la CPU en ese periodo
– cuando consiguen la CPU recuperan su prioridad original