Please enable JavaScript.
Coggle requires JavaScript to display documents.
Planificación de procesos (Algoritmos de planificación para procesos a…
Planificación de procesos
Objetivo
Ceder uso del procesador
Tipos
A largo plazo
Periodicidad de segundos, minutos, horas
Usado en los sistemas por lotes
Admite un nuevo proceso: transición de nuevo a listo
A mediano plazo
También agendador o scheduler
Decide que procesos bloquear
Activación y bloqueo de procesos relacionados con eventos
Transición entre ejecución y bloqueado y entre bloqueado y listo
A corto plazo
Planifica los proceso listos para ejecución
También despachador o dispatcher
Involucra código simple
Transiciones entre estados listo y en ejecución
Tipos de procesos
Por duración
Procesos largos
Procesos que estén en una larga ráfaga limitada por CPU
Procesos cortos
Ráfaga limitada por entrada-salida
Procesos interactivos
Por tipo de acción
Ráfagas o de cómputo interno
Los que transmiten datos o limitados por entrada y salida
Medida de la respueta
Tick
Fracción de tiempo durante la cual se puede usar la CPU sin interrupción
Quantum
El tiempo mínimo que se permitirá a un proceso el uso del procesador
Métricas
Tiempo de respuesta (T)
Tiempo total es necesario para completar el trabajo
Tiempo en espera (E)
E = T-t
Tiempo perdido
Proporción de penalización
P=T/t
Proporción de respuesta
R=t/T
Tiempo núcleo o kernel
Tiempo que pasa el sistema en espacio de núcleo
Tiempo de sistema
Tiempo que pasa un proceso en espacio núcleo
Tiempo de usuario
Tiempo que pasa un proceso en modo usuario
Tiempo de uso del procesador
Tiempo durante el cual el procesador ejecutó instrucciones, sean en modo usuario o en modo núcleo
Tiempo desocupado
Tiempo en que la cola de procesos listos está vacía
Utilización del CPU
Porcentaje del tiempo en que el CPU está realizando trabajo útil
Algoritmos de planificación para procesos a corto plazo
Se invoca cuando un proceso esta en alguna de las 4 de siguen tes circunstancias
Pasa de estar ejecutando a estar en espera
Pasa de estar ejecutando a estar listo
Deja de estar en espera a estar listo
Pasa de ejecutando a terminado
Objetivos
Ser justo
Maximizar el rendimiento
Ser predecible
Minimizar la sobrecarga
Equilibrar el uso de recursos
Evitar la postergación indefinida
Favorecer el uso esperado del sistema
Dar preferencia a los procesos que podrían causar bloqueo
Favorecer los procesos con un comportamiento deseable
Degradarse suavemente
FCFS
Primero llegado, primero servido
El esquema más simple de planificación
Cooperativo
Cada proceso se ejecuta en el orden en que fue llegando, y hasta que suelta el control
Favorece los procesos largos
Apropiativo
Ronda
Round Robin
Emplea multitarea apropiativa
Cada proceso que esté en la lista de procesos listos puede ejecutarse por un sólo quantum (q)
Puede ser ajustada modificando la duración de q
SPN
El proceso más corto a continuación
Algoritmo justo
Cuenta con información por anticipado del proceso
Promedio exponencial y factor atenuante
Favorece a los procesos cortos
SPN apropiativo
Beneficia procesos largos y cortos
HPRN
El más penalizado a continuación
Algoritmo balanceado
Beneficia procesos largos y cortos
Todo proceso inicia su paso por la cola de procesos listos con un valor de penalización P = 1
P se actualiza como P=(w+t)/t
El proceso que se elige como activo será el que tenga mayor P
Apropiativo
SRR
Ronda egoísta
Favorece procesos que llevan tiempo en ejecución
Cola de procesos nuevos y cola de procesos aceptados
Parámetros a y b ajustables
FB
Retroalimentación multinivel
Múltiples colas de prioridad
El despachador elegirá para su ejecución al proceso que esté al frente de la cola de mayor prioridad que tenga algún proceso esperando Ci, y tras un número predeterminado de ejecuciones, lo degrada a la cola de prioridad inmediata inferior Ci+1
Favorece los procesos cortos
Beneficia a los procesos recién llegados
Se ajustan dos parámetros: cantidad
de veces que un proceso debe ser ejecutado antes de ser degradado a la
prioridad inferior, y la otra es la duración del quantum asignado a las colas
subsecuentes.
Lotería
Cada proceso tiene un número determinado
de boletos
Se asigna el siguiente quantum al proceso que tenga el boleto ganador
Esquemas híbridos
Algoritmo por cola dentro de FB
Introduce varias colas
Cada una con un esquema diferente
Métodos dependientes del estado del sistema
Variando parámetros del sistema
Planificación de hilos
Depende de cómo éstos son mapeados a procesos a ojos del planificador.
Tipos
Hilos de usuario
Hilos verdes
Modelos
Muchos a uno
Muchos hilos son agrupados en un sólo proceso
Para el sistema operativo, hay un sólo proceso
Aplica para hilos verdes
Los hilos no aprovechan realmente al paralelismo
Uno a uno
Cada hilo es ejecutado como un proceso ligero o LWP
Los hilos comparte memoria
Menor información de estado
Paralelismo
Muchos a muchos
Maneja modelos: muchos a uno y uno uno
Permite hilos unidos en que cada hilo corresponde a un (y solo un) LWP y de hilos no unidos, de los cuales uno o más estarán mapeados a cada LWP
Los hilos POSIX (pthreads)
Ambito de contención
Contención de proceso
Todos los hilos deben ser atendidos sin exceder el tiempo que sería asignado a un solo proceso
Hilo que multiplexa varios hilos no unidos bajo un modelo muchos a muchos
Varios hilos siguiendo el modelo muchos a uno
Contención de sistema
Cada hilo es visto por el planificador como un proceso independiente
Hilos bajo el modelo uno a uno
Cada uno de los hilos unidos bajo un modelo muchos a muchos
Planificación de multiprocesadores
Para trabajar en multiprocesadores, puede mantenerse una sola lista de procesos e ir despachándolos a cada uno de los procesadores como unidades de ejecución equivalentes e idénticas, o pueden mantenerse listas separadas de
procesos.
Afinidad a procesador
Un proceso que fue ejecutado en determinado
procesador vuelva a hacerlo en el mismo
Balanceo de cargas
La divergencia entre la carga de cada uno de los procesadores debe ser lo más pequeña posible
Colas de procesos
El enfoque de una sola cola no tiene uso actualmente por que afecta la afinidad al procesador
Procesadores con soporte a hilos hardware
Forman parte de ciertos procesadores, ofreciendo al sistema una casi concurrencia adicional
En todo momento habrá una instrucción diferente ejecutando en cada una de las secciones del procesador
Estructura conocida como pipeline (tubería)
Tiempo real
Procesos que requieren garantías de tiempo
Es comun en los controladores de dispositivos y los recodificadores o reproductores de medios (audio, video)
Se debe declarar los requisitos de tiempo (formalmente, efectuar la reserva de recursos)
Tiempo real duro
Los sistemas en que el tiempo máximo es garantizable son conocidos como de tiempo real duro
Tiempo real suave
Aplica en sistemas operativos de propósito general que usan hardware estándar ya que no pueden implementar tiempo real duro
Los procesos críticos reciban un trato prioritario por encima de los procesos comunes
Sistema operativo interrumpible (prevenible)
Para lograr que el núcleo pueda ser interrumpido para dar el control de vuelta a procesos de usuario, un enfoque fue el poner puntos de interrupción en los puntos de las funciones del sistema donde fuera seguro, tras asegurarse que las estructuras estaban en un estado estable
Inversión de prioridades
Efecto colateral de que las estructuras del núcleo estén protegidas por mecanismos de sincronización