PDF de programación - Planificación de procesos: Algoritmos de planificación

Introducción
Métricas
Algoritmos de planicación
Esquemas híbridos y prioridades externas

Planicación de procesos: Algoritmos de

planicación

Gunnar Wolf

Facultad de Ingeniería, UNAM

Instituto de Investigaciones Económicas, UNAM

Gunnar Wolf

Planicación de procesos: Algoritmos de planicación

Introducción
Métricas
Algoritmos de planicación
Esquemas híbridos y prioridades externas

Índice

1

Introducción

2 Métricas

3 Algoritmos de planicación

4 Esquemas híbridos y prioridades externas

Gunnar Wolf

Planicación de procesos: Algoritmos de planicación

Introducción
Métricas
Algoritmos de planicación
Esquemas híbridos y prioridades externas

Referencia para esta sección

Buena parte del material de esta unidad toma por referencia al

capítulo 2 de An operating systems vade mecum (Raphael

Finkel, 1988), disponible para su descarga en el sitio Web del

autor.

Gunnar Wolf

Planicación de procesos: Algoritmos de planicación

Introducción
Métricas
Algoritmos de planicación
Esquemas híbridos y prioridades externas

Principal decisión en un sistema multitareas

¾Qué proceso es el siguiente a ejecutar?

¾Qué procesos han ido terminando?

¾Qué eventos ocurrieron que hacen que cambien de
estado?

Solicitudes (y respuestas) de E/S
Swap de/a disco

¾Cual es el siguiente proceso al que le toca atención del
CPU?

¾Y por cuánto tiempo?

Vemos que hay tres tipos muy distintos de planicación.

Gunnar Wolf

Planicación de procesos: Algoritmos de planicación

Introducción
Métricas
Algoritmos de planicación
Esquemas híbridos y prioridades externas

Planicador a largo plazo

Cual es el siguiente proceso a ser iniciado
Principalmente orientado a la operación en lotes

Principalmente a los sistemas con spool
También presente en la multiprogramación temprana

Decide en base a los requisitos pre-declarados de los
procesos, y a los recursos disponibles al ejecutarse
Periodicidad: segundos a horas
Hoy en día no se emplean

El usuario indica expresamente qué procesos iniciar
Podría verse a los programas como cron, at, o en
Windows al Planicador de procesos como cubriendo este
rol

Aunque son procesos plenamente en espacio de usuario

Gunnar Wolf

Planicación de procesos: Algoritmos de planicación

Introducción
Métricas
Algoritmos de planicación
Esquemas híbridos y prioridades externas

Planicador a largo plazo

Figure: Planicador a largo plazo

Gunnar Wolf

Planicación de procesos: Algoritmos de planicación

Introducción
Métricas
Algoritmos de planicación
Esquemas híbridos y prioridades externas

Planicador a mediano plazo

Cuáles procesos hay que bloquear

Por escasez/saturación de algún recurso (p.ej.
almacenamiento primario)
Por haber iniciado una operación que no puede
satisfacerse aún

Cuáles procesos hay que desbloquear

A la espera de algún dispositivo
Fueron enviados a swap, pero ya requieren o merecen
ejecutarse

Frecuentemente llamado agendador (scheduler)

Gunnar Wolf

Planicación de procesos: Algoritmos de planicación

Introducción
Métricas
Algoritmos de planicación
Esquemas híbridos y prioridades externas

Planicador a mediano plazo

Figure: Planicador a mediano plazo, o agendador

Gunnar Wolf

Planicación de procesos: Algoritmos de planicación

Introducción
Métricas
Algoritmos de planicación
Esquemas híbridos y prioridades externas

Planicador a corto plazo

Cómo compartir momento a momento al CPU entre
todos los procesos
Se efectúa decenas de veces por segundo

Debe ser simple, eciente y rápido

Se encarga de planicar los procesos listos para ejecución

Estados listo y ejecutando

Frecuentemente llamado despachador (dispatcher)

Gunnar Wolf

Planicación de procesos: Algoritmos de planicación

Introducción
Métricas
Algoritmos de planicación
Esquemas híbridos y prioridades externas

Planicador a corto plazo

Figure: Planicador a corto plazo, o despachador

Gunnar Wolf

Planicación de procesos: Algoritmos de planicación

Introducción
Métricas
Algoritmos de planicación
Esquemas híbridos y prioridades externas

Tipo de planicador según transición

Largo plazo:
Admitir
Mediano plazo:
Ocurrió evento,
Esperar evento
Corto plazo:
Activar ejecución,
Tiempo terminado

Figure: Diagrama de transición entre los
estados de un proceso

Gunnar Wolf

Planicación de procesos: Algoritmos de planicación

Introducción
Métricas
Algoritmos de planicación
Esquemas híbridos y prioridades externas

El enfoque de esta unidad

En esta unidad hablaremos particularmente del planicador a

corto plazo

Cuando un proceso es suspendido (o bloqueado) y

posteriormente reactivado, lo trataremos como un proceso

nuevo.

Gunnar Wolf

Planicación de procesos: Algoritmos de planicación

Introducción
Métricas
Algoritmos de planicación
Esquemas híbridos y prioridades externas

Tipos de proceso

Diversos procesos tienen distintas características
Alternan entre ráfagas (bursts)

CPU Trabajando con datos ya existentes en el

sistema

E/S Mayormente esperando a eventos de E/S
Un programa dado puede ser mayormente de un tipo u
otro  Dicho programa está limitado por CPU o limitado
por E/S
Cuando termina una ráfaga de CPU y se suspende
esperando E/S, deja de estar listo y sale de la vista del
despachador
Esto nos lleva a separar los procesos en. . .

Gunnar Wolf

Planicación de procesos: Algoritmos de planicación

Introducción
Métricas
Algoritmos de planicación
Esquemas híbridos y prioridades externas

Tipos de proceso

Ojo: ½Un poco contraintuitivo!

Largos Han estado listos o en ejecución por mucho

tiempo

Esto es, están en una ráfaga de CPU

Cortos En este momento están en una ráfaga de E/S

Requieren atención meramente ocasional del
procesador
Tienden a estar bloqueados, esperando a
eventos

Como buena parte de los procesos
interactivos

Gunnar Wolf

Planicación de procesos: Algoritmos de planicación

Introducción
Métricas
Algoritmos de planicación
Esquemas híbridos y prioridades externas

Índice

1

Introducción

2 Métricas

3 Algoritmos de planicación

4 Esquemas híbridos y prioridades externas

Gunnar Wolf

Planicación de procesos: Algoritmos de planicación

Introducción
Métricas
Algoritmos de planicación
Esquemas híbridos y prioridades externas

Unidades a manejar

Para hablar de planicación del procesador, no vamos a

manejar tiempos estándar (s, ms, ns), sino que:

Tick Un tiempo mínimo dado durante el cual se puede

realizar trabajo útil. Medida caprichosa y
arbitraria.

En Windows, un tick dura entre 10 y 15 ms.
En Linux (2.6.8 en adelante), dura 1 ms.

Quantum Tiempo mínimo, expresado en ticks, que se

permitirá a un proceso el uso del procesador.
En Windows, 2 a 12 ticks (esto es, 20 a
180ms).
En Linux, 10 a 200 ticks (10 a 200ms)

Gunnar Wolf

Planicación de procesos: Algoritmos de planicación

Introducción
Métricas
Algoritmos de planicación
Esquemas híbridos y prioridades externas

¾Qué es mejor?

No hay un sólo criterio para denir qué es una mejor
respuesta
El patrón correcto varía según el propósito del sistema
Un proceso interactivo sufre si el tiempo de respuesta
incrementa, aunque pueda procesar por más tiempo
corrido

En caso de sufrir demoras, debemos intentar que sean
consistentes, aunque el tiempo promedio resulte
deteriorado
Es mejor saber que el sistema siempre tardará 0.5s en
responder a mis necesidades a que unas veces responda
de inmediato y otras tarde 3s.

¾O no?

Gunnar Wolf

Planicación de procesos: Algoritmos de planicación

Introducción
Métricas
Algoritmos de planicación
Esquemas híbridos y prioridades externas

¾Qué es mejor?

No hay un sólo criterio para denir qué es una mejor
respuesta
El patrón correcto varía según el propósito del sistema
Un proceso interactivo sufre si el tiempo de respuesta
incrementa, aunque pueda procesar por más tiempo
corrido

En caso de sufrir demoras, debemos intentar que sean
consistentes, aunque el tiempo promedio resulte
deteriorado
Es mejor saber que el sistema siempre tardará 0.5s en
responder a mis necesidades a que unas veces responda
de inmediato y otras tarde 3s.

¾O no?

Gunnar Wolf

Planicación de procesos: Algoritmos de planicación

Introducción
Métricas
Algoritmos de planicación
Esquemas híbridos y prioridades externas

¾Qué métricas compararemos?

Para un proceso p que requiere ejecutarse por tiempo t,

Tiempo de respuesta (T ) Tiempo total que toma el trabajo.
Incluye el tiempo que pasó inactivo (pero listo).
Tiempo en espera (E ) De T , cuánto tiempo está esperando

ejecutar. (Tiempo perdido)

E = T − t; Idealmente, para p, Ep → 0

Proporción de penalización (P) Fracción del tiempo de

respuesta durante la cual p estuvo en espera.

P = T
t

Proporción de respuesta (R) Fracción del tiempo de respuesta

durante la cual p pudo ejecutarse.

R = t

T ; R = 1

P

Gunnar Wolf

Planicación de procesos: Algoritmos de planicación

Introducción
Métricas
Algoritmos de planicación
Esquemas híbridos y prioridades externas

Además de los anteriores, para el sistema. . .

Tiempo núcleo o kernel Tiempo que pasa el sistema en

espacio de núcleo

Tiempo desocupado (idle) Tiempo en que la cola de procesos

listos está vacía y no puede realizarse ningún
trabajo.

El sistema operativo aprovecha este tiempo
para realizar tareas de mantenimiento

Utilización del CPU Porcentaje del tiempo en que el CPU está

realizando trabajo útil.

Conceptualmente, entre 0 y 100%
En realidad, en un rango entre 40 y el 90%.

Gunnar Wolf

Planicación de procesos: Algoritmos de planicación

Introducción
Métricas
Algoritmos de planicación
Esquemas híbridos y prioridades externas

Por ejemplo. . .

Los siguientes procesos forman la cola de procesos listos:

Proceso Ticks Llegada
0
A
2
B
C
6
20
D

7
3
12
4

Toma 1 tick realizar un cambio de contexto; cada quantum es

de 5 ticks, y tenemos un ordenamiento de ronda1

1Que pronto describiremos

Gunnar Wolf

Planicación de procesos: Algoritmos de planicación

Introducción
Métricas
Algoritmos de planicación
Esquemas híbridos y prioridades externas

Precisiones sobre el ejemplo