Capítulo 6: Planificación del

CPU – Parte a
Capítulo 6: Planificación del CPU
 Conceptos Básicos
 Ciclos de CPU
 Criterios de Planificación
 Algoritmos de Planificación
Primero en llegar, primero atendido FCFS
Primero el trabajo más corto SJF
Prioridades
Round - Robin
 Planificación con colas múltiples
 Planificación con colas múltiples y retroalimentación
 Planificación con procesadores múltiples
 Planificación en tiempo real
 Conceptos Básicos
 La multiprogramación permite tener a un proceso en ejecución
en todo momento para maximizar el uso del CPU.
 Los procesos se alternan entre ejecución en el CPU – ciclo de
CPU – y espera, normalmente por algún dispositivo de E/S.
 La duración de los ciclos de CPU siguen un comportamiento
similar al mostrado en la gráfica correspondiente a la lámina
número 5. La gráfica muestra una tendencia por los procesos
a tener ciclos de CPU de duración cercana a 3 milisegundos.
Estados alternos – Ciclo de CPU y Espera E/S
Ciclos de CPU
 Planificador del CPU

 Siempre que el CPU queda inactivo, el sistema operativo debe

seleccionar a uno de los procesos de la cola de listos para su
ejecución.
 El proceso de selección del siguiente proceso a ser ejecutado es
llevado a cabo por el planificador de corto plazo ( o planificador del
CPU ).
 La estrategia de selección del siguiente proceso en la cola de listos,
puede ser primero que entra primero que sale ( FIFO ), por
prioridades, lista desordenada y otras.
 Planificador de Corto Plazo
 El planificador de corto plazo selecciona al siguiente proceso
en la cola de procesos listos para ser asignado al CPU y
ejecutado.
 El planificador de corto plazo debe tomar decisiones cuando:
1. Un proceso pasa de estado ejecución a estado de espera
2. Un proceso pasa de estado ejecución a estado listo.
3. Un proceso para de estado ejecución a suspendido listo.
4. Un proceso finaliza.
 Un planificador apropiativo retira a procesos del CPU de
acuerdo a su estrategia. El proceso no puede evitar ser retirado
del CPU.
 Un planificador no apropiativo ( cooperativo ) no puede retirar
a un proceso del CPU. El proceso coopera abandonando
voluntariamente al CPU.
 Despachador
 El módulo Despachador, da control del CPU al proceso
seleccionado por el Planificador de Corto Plazo
Esto involucra:
 Conmutación de contexto

 Conmutación a modo usuario

 Establecer el contador del programa a la dirección de la

siguiente instrucción a ser ejecutada

 Latencia de Despacho – Es el tiempo que le toma al
despachador detener un proceso e iniciar la ejecución de otro
proceso
 Criterios de Planificiación
 Los diferentes algoritmos de planificación del CPU tienen los
siguientes criterios para ser comparados:
 Utilización del CPU – Hay que maximizar este parámetro
 Rendimiento – Número de procesos que finalizan su
ejecución por unidad de tiempo. Es necesario maximizar este
parámetro
 Tiempo de Entrega – Tiempo que tarda un proceso en
finalizar. Se desea minimizar este parámetro
 Tiempo de Espera – Tiempo que tarda un proceso esperando
en las colas del sistema. Se desea minimizar este parámetro
 Tiempo de Respuesta – Tiempo que tarda un proceso en
responder a una solicitud. Se aplica en sistemas de tiempo
compartido y es deseable minimizar este parámetro
 Planificación primero en llegar, primero en ser
atendido FCFS ( first come first served )
 El CPU se asigna al primer proceso que lo solicite. La
implementación de la política del FCFS se maneja con una cola
tipo FIFO ( first in, first out ).
 Como ejemplo tenemos la siguiente cola de procesos listos:
Proceso Ciclo de CPU
P1 24
P2 3
P3 3
 Los procesos llegaron a la cola de procesos listos en el siguiente
orden:
P1 , P2 , P3
 Vamos a determinar el tiempo de espera promedio para los
procesos. El tiempo de espera es el tiempo que un proceso se
encuentra en la cola de procesos listos esperando a ser
despachado al CPU para su ejecución.
 También determinaremos el tiempo de entrega promedio para los
procesos. El tiempo de entrega es el tiempo que dura un
proceso en el sistema antes de finalizar su tarea.
 Planificación primero en llegar, primero en ser
atendido FCFS ( first come first served )

 El diagrama de Gantt muestra el tiempo que duran los procesos

ejecutándose en el CPU.
 El diagrama de Gantt para nuestro ejemplo es el siguiente:

P1 P2 P3

0 24 27 30

 Tiempo de espera para P = 0; P = 24; P = 27

1 2 3
 Tiempo de espera promedio es: (0 + 24 + 27)/3 = 17
 Tiempo de entrega para P = 24; P = 27; P = 30
1 2 3
 Tiempo de entrega promedio es: (24 + 27 + 30)/3 = 27
 Planificación primero en llegar, primero en ser
atendido FCFS ( first come first served )

 Suponga que los procesos llegan en el siguiente orden

P2 , P3 , P1
 El correspondiente diagrama de Gantt:

P2 P3 P1

0 3 6 30

 Tiempo de espera para P1 = 6; P2 = 0; P3 = 3

 Tiempo de espera promedio: (6 + 0 + 3)/3 = 3
 Mejor que en el caso anterior. Muestra la varianza.
 Tiempo de entrega para P1 = 30; P2 = 3; P3 = 6
 Tiempo de entrega promedio: (30 + 3 + 6)/3 = 13
Planificación primero en llegar, primero en ser
atendido FCFS ( first come first served )

 La estrategia FCFS es muy sencilla de implementar sin

embargo observamos en el ejemplo que el tiempo de espera
promedio puede experimentar variaciones ( varianza )
significativas dependiendo de los ciclos de CPU de los
procesos. En general el tiempo de espera no es mínimo.
 Planificación de primero el trabajo más corto
SJF ( Shortest job first )
 Asocia con cada proceso el tiempo de su siguiente Ciclo de
CPU. Utiliza este tiempo para seleccionar al próximo
proceso a ser despachado al CPU. Cuando el CPU está
disponible, se le asigna el proceso con el menor ciclo de
CPU. Si dos procesos tienen el mismo ciclo de CPU, se
utiliza la estrategia FCFS para tomar la decisión.
 Dos esquemas:
 No apropiativo – un proceso ejecutandose en el CPU no
puede ser retirado hasta que el mismo lo decida
 Apropiativo – Si un nuevo proceso llega a la cola de listos
con un ciclo de CPU menor a los demás procesos
incluyendo al que se está ejecutando en el CPU, este
nuevo proceso reemplaza al proceso en el CPU. Este
algoritmo se llama también primero el que tenga el tiempo
de ejecución remanente más corto
Shortest-Remaining-Time-First (SRTF)
 SJF is óptimo – con este algoritmo se obtiene el menor
tiempo de espera promedio para un conjunto de procesos en
la cola de procesos listos
 Ejemplo de SJF no apropiativo
Proceso Tiempo de llegada Ciclo de CPU
P1 0 7
P2 2 4
P3 4 1
P4 5 4
 Para SJF no apropiativo
 P está en el el momento 0, no hay otros procesos en la cola, es
1
seleccionado P1 y se ejecuta por 7 unidades de tiempo hasta que
finaliza.
 Al finalizar P en el momento 7, se encuentran en la cola P , P y
1 2 3
P4. Es seleccionado P3 con el menor ciclo de CPU.
 Al finalizar P en el momento 8, quedan en la cola P y P con el
3 2 4
mismo ciclo de CPU. Se aplica la estrategia FCFS y es
seleccionado P2.
 Al finalizar P su ejecución, queda P para ser despachado al
2 4
CPU.
 Ejemplo de SJF no apropiativo
 SJF (no apropiativo ). El proceso no puede ser
retirado del CPU por el sistema operativo.

P1 P3 P2 P4

0 3 7 8 12 16
 Tiempo de espera:
 P llegó en 0 y entró en 0 esperó 0, P llegó en 4 y
1 3
entró en 7 esperó 3, P2 llegó en 2 y entró en 8
esperó 6, P4 llegó en 5 y entró en 12 esperó 7.
 Tiempo de espera promedio = (0 + (8 -2 ) + ( 7 –
4 ) + ( 12 – 5 ))/4 = ( 0 + 6 + 3 + 7 )/4 = 4
 Ejemplo de SJF no apropiativo
 SJF (no apropiativo ). El proceso no puede ser retirado del
CPU por el sistema operativo.

P1 P3 P2 P4

0 3 7 8 12 16

 Tiempo de entrega:
 P1 llegó en 0 y finalizó en 7 tiempo de entrega 7, P 2 llegó en 2 y
finalizó en 12 tiempo de entrega 10, P3 llegó en 4 y finalizó en
8 tiempo de entrega 4, P4 llegó en 5 y finalizó en 16 tiempo de
entrega 11.
 Tiempo de entrega promedio = (( 7 – 0 ) + (12 – 2) + ( 8 – 4 ) +
( 16 – 5 ))/4 = ( 7 + 10 + 4 + 11 )/4 = 8
 Ejemplo SJF apropiativo
Proceso Tiempo de Llegada Ciclo de CPU
P1 0 7
P2 2 4
P3 4 1
P4 5 4
 SJF ( apropiativo ). El proceso puede ser retirado del CPU por el sistema
operativo.
 P llega en el momento 0 siendo el único proceso en la cola es despachado
1
al CPU. P2 llega en el momento 2, tiene un ciclo de CPU 4 menor que los 5
restantes ( 7 – 2 ) de P1. Por lo tanto P1 es retirado del CPU y entra P2. En el
momento 4 llega P3 que tiene el ciclo de CPU 1 menor que los 2 restantes
de P2. Por lo tanto P2 es retirado del CPU y entra P3. En el momento 5 P3
finaliza su ejecución y el planificador debe decidir a quién seleccionar en la
cola. P1 le quedan 5 ciclos de CPU, a P2 le quedan 2 ciclos de CPU y P4
tiene 4 ciclos de CPU. Por lo tanto, P2 es despachado al CPU. En el
momento 7, P2 finaliza y es seleccionado P4 que tiene 4 ciclos de CPU
menor a los 5 que tiene P1. P4 finaliza su ejecución en el momento 11 y entra
P1 que finaliza en el momento 16.
 Ejemplo SJF apropiativo
P1 P2 P3 P2 P4 P1

0 2 4 5 7 11 16

 Tiempo de espera para P como ejemplo: P entra de

1 1
inmediato al CPU con espera 0, pero luego sale en el
momento 2 y espera hasta el momento 11 para volver al
CPU, por lo tanto P1 espera ( 11 – 2 ) = 9 unidades de
tiempo.
 Tiempo de espera promedio = ((0 + ( 11 – 2 )) + ( 0 + (5 – 4
)) + ( 0 ) + ( 7 – 5 ))/4 = ( 9 + 1 + 0 + 2 )/4 = 3
 Tiempo de entrega para P como ejemplo: P sale del
2 2
sistema en el momento 7, llegó en 2 por lo tanto el tiempo de
entrega es 7 – 2 = 5.
 Tiempo de entrega promedio = (16 + ( 7 – 2 )+ ( 5 – 4 ) +
( 11 – 5 ))/4 = ( 16 + 5 + 1 + 6 )/4 = 7
 Predicción del siguiente ciclo de
CPU
 El siguiente ciclo de CPU de un proceso puede ser estimado.
 Se basa en la historia del proceso dentro del sistema.

  toma un valor entre 0 y 1 dado por el administrador o

diseñador del sistema de acuerdo a las características de los
procesos que se ejecutan en el CPU.
 Predicción del ciclo de CPU
 Al expandir la formula para predecir el próximo ciclo de CPU,
obtenemos:
n+1 =  tn+(1 - ) tn -1 + …
+(1 -  )j  tn -j + …
+(1 -  )n +1 0

 Si  =0
 Solo se toma en cuanta el histórico del proceso. El último
ciclo de CPU es descartado.
 Si  =1
 
n+1 = tn
 Solamente se toma en cuenta el último ciclo de CPU.

 Como  y (1 - ) tienen un valor menor o igual a 1, cada

término sucesivo en la fórmula tiene menor peso que su
predecesor.
 Predicción del ciclo de CPU
Ejemplo: asignamos  = 0,5. Le damos igual peso al último ciclo de
CPU y al histórico.
Un proceso comenzará su ejecución. No existe historia sobre este
proceso por lo tanto al azar predecimos que su ciclo de CPU será tn =
10.

Se ejecuta el proceso y su ciclo de CPU fue 6. En base a esto, se

predice su próximo ciclo de CPU de la siguiente manera,
n+1 = ( 0,5 ) ( 6 ) + ( 0,5 ) ( 10 ) = 8

Se vuelve a ejecutar el proceso y resulta que su ciclo de CPU fue 4 en

lugar del 8 pronosticado. Se procede a predecir el próximo ciclo de
CPU como sigue,
n+1 = ( 0,5 ) ( 4 ) + ( 0,5 ) ( 8 ) = 6

El proceso se ejecuta en el CPU y resulta que su ciclo de CPU fue 6, la

predicción para el próximo ciclo de CPU es,
n+1 = ( 0,5 ) ( 6 ) + ( 0,5 ) ( 6 ) = 6
 Predicción del ciclo de CPU
Se ejecuta el proceso y su ciclo de CPU fue 4. En base a esto,
se predice su próximo ciclo de CPU de la siguiente manera,
n+1 = ( 0,5 ) ( 4 ) + ( 0,5 ) ( 6 ) = 5

Se vuelve a ejecutar el proceso y resulta que su ciclo de CPU

fue 13 en lugar del 5 pronosticado. Se procede a predecir el
próximo ciclo de CPU como sigue,
n+1 = ( 0,5 ) ( 13 ) + ( 0,5 ) ( 5 ) = 9

Seguidamente el ciclo de CPU del proceso es 13,

n+1 = ( 0,5 ) ( 13 ) + ( 0,5 ) ( 9 ) = 11

Finalmente el proceso tiene un ciclo de CPU de 13,

n+1 = ( 0,5 ) ( 13 ) + ( 0,5 ) ( 11 ) = 12
 Predicción del ciclo de CPU
 Podemos observar en la gráfica como las predicciones siguen
aproximadamente al comportamiento real del proceso.
 Planificación con Prioridad

 Una prioridad está asociada a cada proceso

 El CPU es asignado al proceso con la prioridad más alta
( número menor  mayor prioridad, para los ejemplos a
continuación)
 Puede ser apropiativa

 Puede ser no apropiativa

 Un problema con este algoritmo es la inanición. Procesos con baja

prioridad pueden no ser ejecutados nunca
 El envejecimiento aumenta la prioridad de los procesos cada cierto
tiempo. Esto evita la inanición
 Cuando existen procesos con la misma prioridad en la cola de
procesos listos, se aplica FCFS
Ejemplo de planificación con prioridad
Proceso Tiempo de Llegada Ciclo de CPU
Prioridad
P1 0 7 2
P2 2 4 3
P3 4 1 1
P4 5 4 4
 Prioridad ( no apropiativo )
 P se encuentra en la cola de listos en el momento 0. No hay
1
otros procesos en la cola por lo tanto es despachado al CPU.
Como la estratégia es no apropiativa, P1 se ejecuta hasta el
final. En el momento 7, se encuentran P2, P3 y P4 en la cola. P3
tiene la prioridad más alta por lo tanto es seleccionado y
despachado al CPU. Al finalizar P3 en el momento 8, es
seleccionado P2 por tener prioridad más alta que P4. Finalmente
en el momento 12 es seleccionado el último proceso P4.
Ejemplo de planificación con prioridad

 El diagrama de Gantt resultante, se muestra a continuación :

P1 P3 P2 P4

0 3 7 8 12 16

 Tiempo de espera promedio = (0 + ( 8 – 2 ) + ( 7 – 4 ) +

( 12 – 5 ))/4 = ( 0 + 6 + 3 + 7 )/4 = 4
 Tiempo de entrega promedio = (7 + ( 12 – 2 ) + ( 8 – 4 ) +
( 16 – 5 ))/4 = ( 7 + 10 + 4 + 11 )/4 = 8
Ejemplo de planificación con prioridad
Proceso Tiempo de Llegada Ciclo de CPU Prioridad
P1 0 7 2
P2 2 4 3
P3 4 1 1
P4 5 4 4
 Prioridad ( apropiativo )
 P se encuentra en la cola de listos en el momento 0. No hay
1
otros procesos en la cola por lo tanto es despachado al CPU.
Como la estratégia es apropiativa, al llegar P 3 con prioridad
mayor, P1 es retirado del CPU con 3 ciclos de CPU faltantes y
entra P3 al CPU que se ejecuta hasta su final en el momento 5.
En este momento se encuentran P1, P2 y P4 en la cola, P1 tiene
mayor prioridad, vuelve al CPU y se ejecuta hasta su final. En el
momento 8 se selecciona al proceso P 2 con mayor prioridad que
P4 y se ejecuta hasta su final momento en el cual se despacha P 4
al CPU.
 Ejemplo de planificación con
prioridad
 El diagrama de Gantt resultante, se muestra a continuación:

 Tiempo de espera promedio = ((0 + ( 5 – 4 )) + ( 8 -2 ) + 0 + ( 12 –

5 ))/4 = ( 1 + 6 + 0 + 7 )/4 = 3,5
 Tiempo de entrega promedio = ( ( 8 – 0 ) + ( 12 – 2 ) + ( 5 – 4 ) + ( 16
– 5 ))/4 = ( 8 + 10 + 1 + 11 )/4 = 7,5
 Planificación Round Robin (RR)
 Cada proceso obtiene un tiempo ( quantum ) para ser
ejecutado por el CPU, tiempos típicos del quantum están
entre 1 y 100 milisegundos. Al finalizar un quantum, el
proceso es retirado del CPU y colocado al final de la cola
de procesos listos
 La cola de procesos listos es tratada como una cola
circular
 Dependiendo del tamaño del quantum q, tenemos
 q grande  FIFO

 q pequeño  q debe se mayor al tiempo promedio para

cambio de contexto en los procesos que se están

ejecutando
 Ejemplo 1 de planificación Round
Robin
Proceso Ciclo de CPU
P1 24
P2 3
P3 3
quantum = 4
 El diagrama de Gantt para el ejemplo:

 Tiempo de espera promedio = ( 0 + ( 10 – 4 ) + 4 + 7 )/ 3 =

( 6 + 4 + 7 ) / 3 = 5,67
 Tiempo de entrega promedio = ( 30 + 7 + 10 ) / 3 = 15,67
 La planificación RR muestra tiempos de espera y de entrega
mayores que la planificación SJF, sin embargo su respuesta en
sistemas de tiempo compartido es superior.
 Ejemplo 2 de planificación Round
Robin
Proceso Tiempo de llegada Ciclo de CPU
P1 0 10
P2 1 6
P3 2 3
quantum = 4
 El diagrama de Gantt para el ejemplo:

 Tiempo de espera promedio = ( ( 0 + ( 11 – 4 ) + ( 17 – 15 )) +

(( 4 – 1 ) + ( 15 – 8 )) + ( 8 – 2 ) )/ 3 = ( 9 + 10 + 6 )/ 3 = 8,34

 Tiempo de entrega promedio = ( 19 + ( 17 – 1 ) + ( 11 – 2 ))/ 3 =

( 19 + 16 + 9 ) / 3 = 14,67
 Tamaño del quantum y el cambio de
contexto
Con la planificación Round-Robin, si el quantum es muy grande, la
política RR se comporta como FCFS. Si el quantum es muy pequeño
la estrategia RR se denomina compartimiento del procesador y aparece
a los usuarios como si cada uno de los n procesos tuviera su propio
procesador en ejecución a 1/n de la velocidad del procesador real.
Variación del tiempo de entrega con respecto al
tamaño del quantum

El tiempo de entrega promedio no

necesariamente se reduce a
medida que aumenta el tamaño del
quantum. En general, el tiempo de
entrega promedio puede reducirse
si la mayoría de los procesos
terminan su siguiente ciclo de
CPU en un solo quantum.
 Planificación de colas de niveles múltiples
 Existen algoritmos de planificación para situaciones en las cuales los
procesos se clasifican fácilmente en grupos diferentes.
 Es común separar procesos:
De primer plano (interactivos).
De segundo plano (en lotes).
 Cada cola de procesos tiene us propia estrategia de planificación del CPU:
 De primer plano – RR.

 De segundo plano – FCFS.

 Debe existir planificación entre las colas:

 Planificación por prioriodad; (primero son atendidas las colas de primer

plano, luego las de segundo plano. – Existe el peligro de inanición ).

 Round Robin – a cada cola se le asigna un tiempo de CPU. El

porcentaje puede ser mayor para las colas de primer plano.

 Planificación de colas con niveles múltiples
Como ejemplo de planificación con niveles múltiples se muestra un
esquema en el cual cada cola tiene prioridad absoluta sobre las colas de
menor prioridad. Por ejemplo, ningún proceso en la cola de procesos por
lotes se podrá ejecutar si existen proceso en las colas de procesos del
sistema, procesos interactivos o procesos para edición interactivos.
Planificación con colas de niveles múltiples
y retroalimentación
 Esta planificación permite que un proceso se mueva entre
colas. El propósito es separar procesos con diferentes
características de ciclo de CPU. Si un proceso emplea
demasiado tiempo de CPU, será movido a una cola de
menor prioridad.
 En general, un planificador con niveles múltiples y
retroalimentación se define mediante los siguientes
parámetros:
 El número de colas.
 El algoritmo de planificación para cada cola.
 El método utilizado para determinar cuándo un proceso
pasa a una cola de nivel superior.
 El método utilizado para determinar cuándo un proceso
pasa a una cola de nivel inferior.
 El método utilizado para determinar en que cola será
colocado un proceso nuevo.
 Ejemplo de colas de niveles
múltiples

 El sistema tiene tres colas:

 Q0 – RR con quantum de 8 milisegundos.
 Q1 – RR con quantum de 16 milisegundos.
 Q2 – FCFS
 Planificación:
 Un proceso nuevo es colocado en la cola Q0 mediante una
estrategia FCFS. Al ser despachado al CPU, recibe 8 milisegundos
de tiempo, si no finaliza en ese tiempo, el proceso es retirado del
CPU y enviado a la cola Q1.
 El proceso entra a la cola Q1 con una estrategia FCFS. Al ser
despachado al CPU recibe 16 milisegundos de tiempo, si no finaliza
en este tiempo, es retirado del CPU y enviado a la cola Q 2.
Ejemplo de colas de niveles múltiples con
retroalimentación
 Planificación de procesadores
múltiples
 La planificación del CPU con múltiples procesadores es más
compleja.
 Si existen varios procesadores idénticos, se puede
implementar la compartición de carga. Se puede utilizar una
cola distinta para cada procesador. En este caso, un
procesador puede estar ocioso con una cola vacía, mientras
otro procesador está sobrecargado de procesos.
 Se puede utilizar una cola común para varios procesadores.
Todos los procesos van a una sola cola y se planifican para
cualquier procesador disponible. Con este esquema a su vez
tenemos dos alternativas:
 Multiprocesamiento simétrico, en el cual cada procesador

se planifica a sí mismo.
 Multiprocesamiento asimétrico, en el cual un procesador

toma todas las decisiones de planificación, los otros

procesadores solo ejecutan código de usuario.
 Planificación en tiempo real

 El cálculo en tiempo real puede ser de dos tipos.

 Tiempo real estricto – Utilizado para completar una tarea crítica
dentro de una cantidad de tiempo garantizada.
 Tiempo real suave – Requiere que los procesos críticos reciban
prioridad sobre los procesos no críticos.
Planificación en tiempo real
Latencia de despacho
Final del Capítulo 6 – Parte
a-