• Cada proceso toma una pequeña unidad de tiempo de CPU (quantum de tiempo), por lo general de 10-100 ms. Después de transcurrido este lapso de tiempo, el proceso es expropiado y ubicado en la cola de listos.
• Si hay n procesos en la cola de listos y el quantum es q, entonces cada proceso toma 1/n de tiempo de CPU en bloques de a lo más q unidades de tiempo a la vez. Ningún proceso espera más que (n-1)*q unidades de tiempo.
• Rendimiento
  • si q >> -> FIFO.
  • q << -> q debe ser mayor que la conmutación de contexto, de otra forma la sobrecarga es grande.

Ejemplo de RR con quantum de 20

Qué tan pequeño es el quantum para incrementar los cambios de contexto

Primero el de mayor tasa de respuesta (HRRN)

Se da a cada proceso un tiquete para varios recursos del sistema, tal como la CPU. Cuando se requiere planificar se selecciona al azar un tiquete, y el proceso que lo tiene obtiene el recurso. Si queremos que un proceso tenga más oportunidades se le entregan más tiquetes. Los procesos cooperativos pueden intercambiar sus tiquetes.

Un ejemplo es un servidor de video: supongamos que los procesos necesitan velocidades de 10,20,25 f/s podemos entregar a cada proceso 10,20 y 25 tiquetes respectivamente.

• La cola de listos se divide en colas separadas:
  • Primer plano (interactiva).
  • Segundo plano (lotes).
• Cada cola tiene su propio algoritmo de planificación
  • Primer plano RR.
  • Segundo plano FCFS.
• La planificación debe hacerse entre las colas:
  • Planificación de prioridad fija: es decir, sirva todos los procesos de primer plano y luego los de segundo plano. Existe la n posibilidad de inanición.
  • Cuanto de tiempo: Cada cola tiene cierta cantidad de tiempo que puede ser planificado entre sus procesos; por ejemplo:
    • 80% para primer plano en RR.
    • 20% para segundo plano en FCFS.

Planificación colas multinivel

Colas multinivel con retroalimentación

• Un proceso puede moverse entre varias colas; de esta manera puede implementarse el envejecimiento.
• La planificación con colas multinivel con retroalimentación está definida por los siguientes parámetros:
  • Número de colas.
  • Algoritmos de planificación por cola.
  • Método usado para determinar cuando degradar un proceso.
  • Método usado para determinar a qué cola entrará u proceso cuando requiera de servicio.

• Dos algoritmos: tiempo compartido y tiempo real
• Tiempo compartido
  • Prioridad basada en créditos: El proceso con más créditos se despacha.
  • Se restan los créditos cuando suceden interrupciones de temporizador.
  • Cuando el crédito = 0 se elige otro proceso.
  • Cuando todos los procesos tiene crédito = 0 se reacreditan (Cr=Cr/2+Pr).
    • Con base en factores como prioridad e historia.
• Tiempo real
  • Tiempo real blando.
  • Cumple con POSIX.1b –  de dos clases.
    • FCFS y RR.
    • El proceso de mayor prioridad siempre corre primero.

Planificación en POSIX

• Cada política de planificación lleva asociado un rango con almenos 32 niveles de prioridad.
• El planificador elegirá el proceso o proceso ligero con la prioridad más alta.
• Políticas de planificación
  • FIFO
  • Cíclica
  • Otra

Tabla de despacho de Solaris

Planificación en Solaris 2

• Las prioridades de windows se organizan en dos bandas o clases
  • Tiempo real
  • Variable
• Planificador expropiativo basado en prioridades.

Windows vs NT kernel Priorities

Relación entre las prioridades de Windows

• Los hilos de Java pueden ser creados por:
  • Extensión de la clase hilos
  • Implementando una interface que los corra.
• Los hilos de Java son administrados por la JVM.
• suspend() – suspende la ejecución del hilo que se está ejecutando
• sleep() – coloca el hilo que actualmente está corriendo a dormir un determinado tiempo.
• resume() – reasume la ejecución de hilos suspendidos
• stop() – para la ejecución de un hilo

Implementa mapeo uno a uno

Cada hilo contiene

• Una identificación de hilo
• Un conjunto de registros
• Pilas  de usuario y kernel separadas.
• Área de almacenamiento de datos privados

OBJETO PROCESO DE WINDOWS

OBJETO HILO DE WINDOWS

RELACIÓN ENTRE HILOS Y PROCESOS

Semejanzas: Los hilos operan, en muchos sentidos, igual que los procesos.

• Pueden estar en uno o varios estados: listo, bloqueado, en ejecución o terminado.
• También comparten la CPU.
• Sólo hay un hilo activo (en ejecución) en un instante dado.
• Un hilo dentro de un proceso se ejecuta secuencialmente.
• Cada hilo tiene su propia pila y contador de programa.
• Pueden crear sus propios hilos hijos.

• En una tarea multihilo, mientras un hilo servidor está bloqueado y esperando, un segundo hilo en la misma tarea puede estar corriendo.
  • La cooperación de múltiples hilos en el mismo trabajo le proporciona un alto rendimiento y mejora la eficiencia.
  • Las aplicaciones que requieren compartir un buffer común (por ejemplo, productor – consumidor) se benefician de la utilización de hilos.
• Los hilos proporcionan un mecanismo que permiten a los procesos secuenciales hacer llamadas al sistema bloqueadoras y al mismo tiempo lograr paralelismo.
• El núcleo puede apoyar los hilos como en Mach y OS/2.
• Los hilos a nivel de usuario; soportados arriba por el kernel, a través de una serie de llamadas de biblioteca en el nivel de usuario (como en el proyecto CMU de Andrew).
• Un enfoque híbrido implementa tanto los hilos de usuario como hilos apoyados por el kernel (como Solaris 2).