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
Sistemas Operativos 6ª edición
6.2
Silberschatz, Galvin y Gagne ©2003
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.
Sistemas Operativos 6ª edición
6.3
Silberschatz, Galvin y Gagne ©2003
Estados alternos – Ciclo de CPU y Espera E/S
Sistemas Operativos 6ª edición
6.4
Silberschatz, Galvin y Gagne ©2003
Ciclos de CPU
Sistemas Operativos 6ª edición
6.5
Silberschatz, Galvin y Gagne ©2003
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.
Sistemas Operativos 6ª edición
6.6
Silberschatz, Galvin y Gagne ©2003
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.
Sistemas Operativos 6ª edición
6.7
Silberschatz, Galvin y Gagne ©2003
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
Sistemas Operativos 6ª edición
6.8
Silberschatz, Galvin y Gagne ©2003
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
Sistemas Operativos 6ª edición
6.9
Silberschatz, Galvin y Gagne ©2003
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.
Sistemas Operativos 6ª edición
6.10
Silberschatz, Galvin y Gagne ©2003
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
0
24
P3
27
30
 Tiempo de espera para P1 = 0; P2 = 24; P3 = 27
 Tiempo de espera promedio es: (0 + 24 + 27)/3 = 17
 Tiempo de entrega para P1 = 24; P2 = 27; P3 = 30
 Tiempo de entrega promedio es: (24 + 27 + 30)/3 = 27
Sistemas Operativos 6ª edición
6.11
Silberschatz, Galvin y Gagne ©2003
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
0
P3
3
P1
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
Sistemas Operativos 6ª edición
6.12
Silberschatz, Galvin y Gagne ©2003
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.
Sistemas Operativos 6ª edición
6.13
Silberschatz, Galvin y Gagne ©2003
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
Sistemas Operativos 6ª edición
6.14
Silberschatz, Galvin y Gagne ©2003
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
 P1 está en el el momento 0, no hay otros procesos en la cola, es
seleccionado P1 y se ejecuta por 7 unidades de tiempo hasta
que finaliza.
 Al finalizar P1 en el momento 7, se encuentran en la cola P2, P3
y P4. Es seleccionado P3 con el menor ciclo de CPU.
 Al finalizar P3 en el momento 8, quedan en la cola P2 y P4 con el
mismo ciclo de CPU. Se aplica la estrategia FCFS y es
seleccionado P2.
 Al finalizar P2 su ejecución, queda P4 para ser despachado al
CPU.
Sistemas Operativos 6ª edición
6.15
Silberschatz, Galvin y Gagne ©2003
Ejemplo de SJF no apropiativo
 SJF (no apropiativo ). El proceso no puede ser
retirado del CPU por el sistema operativo.
P1
0
3
P3
7
P2
8
P4
12
16
 Tiempo de espera:
 P1 llegó en 0 y entró en 0 esperó 0, P3 llegó en 4 y
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
Sistemas Operativos 6ª edición
6.16
Silberschatz, Galvin y Gagne ©2003
Ejemplo de SJF no apropiativo
 SJF (no apropiativo ). El proceso no puede ser retirado del
CPU por el sistema operativo.
P1
0
3
P3
7
P2
8
P4
12
16
 Tiempo de entrega:
 P1 llegó en 0 y finalizó en 7 tiempo de entrega 7, P2 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
Sistemas Operativos 6ª edición
6.17
Silberschatz, Galvin y Gagne ©2003
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.
 P1 llega en el momento 0 siendo el único proceso en la cola es despachado
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.
Sistemas Operativos 6ª edición
6.18
Silberschatz, Galvin y Gagne ©2003
Ejemplo SJF apropiativo
P1
0
P2
2
P3
4
P2
5
P4
7
P1
11
16
 Tiempo de espera para P1 como ejemplo: P1 entra de
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 P2 como ejemplo: P2 sale del
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
Sistemas Operativos 6ª edición
6.19
Silberschatz, Galvin y Gagne ©2003
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.
Sistemas Operativos 6ª edición
6.20
Silberschatz, Galvin y Gagne ©2003
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.
Sistemas Operativos 6ª edición
6.21
Silberschatz, Galvin y Gagne ©2003
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
Sistemas Operativos 6ª edición
6.22
Silberschatz, Galvin y Gagne ©2003
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
Sistemas Operativos 6ª edición
6.23
Silberschatz, Galvin y Gagne ©2003
Predicción del ciclo de CPU
 Podemos observar en la gráfica como las predicciones siguen
aproximadamente al comportamiento real del proceso.
Sistemas Operativos 6ª edición
6.24
Silberschatz, Galvin y Gagne ©2003
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
Sistemas Operativos 6ª edición
6.25
Silberschatz, Galvin y Gagne ©2003
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 )
 P1 se encuentra en la cola de listos en el momento 0. No hay
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.
Sistemas Operativos 6ª edición
6.26
Silberschatz, Galvin y Gagne ©2003
Ejemplo de planificación con prioridad
 El diagrama de Gantt resultante, se muestra a continuación:
P1
0
3
P3
7
P2
8
P4
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
Sistemas Operativos 6ª edición
6.27
Silberschatz, Galvin y Gagne ©2003
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 )
 P1 se encuentra en la cola de listos en el momento 0. No hay
otros procesos en la cola por lo tanto es despachado al CPU.
Como la estratégia es apropiativa, al llegar P3 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 P2 con mayor prioridad
que P4 y se ejecuta hasta su final momento en el cual se
despacha P4 al CPU.
Sistemas Operativos 6ª edición
6.28
Silberschatz, Galvin y Gagne ©2003
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
Sistemas Operativos 6ª edición
6.29
Silberschatz, Galvin y Gagne ©2003
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
Sistemas Operativos 6ª edición
6.30
Silberschatz, Galvin y Gagne ©2003
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.
Sistemas Operativos 6ª edición
6.31
Silberschatz, Galvin y Gagne ©2003
Ejemplo 2 de planificación Round Robin
Proceso
P1
P2
P3
Tiempo de llegada Ciclo de CPU
0
10
1
6
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
Sistemas Operativos 6ª edición
6.32
Silberschatz, Galvin y Gagne ©2003
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.
Sistemas Operativos 6ª edición
6.33
Silberschatz, Galvin y Gagne ©2003
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.
Sistemas Operativos 6ª edición
6.34
Silberschatz, Galvin y Gagne ©2003
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.
Sistemas Operativos 6ª edición
6.35
Silberschatz, Galvin y Gagne ©2003
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.
Sistemas Operativos 6ª edición
6.36
Silberschatz, Galvin y Gagne ©2003
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.
Sistemas Operativos 6ª edición
6.37
Silberschatz, Galvin y Gagne ©2003
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 Q2.
Sistemas Operativos 6ª edición
6.38
Silberschatz, Galvin y Gagne ©2003
Ejemplo de colas de niveles múltiples con
retroalimentación
Sistemas Operativos 6ª edición
6.39
Silberschatz, Galvin y Gagne ©2003
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.
Sistemas Operativos 6ª edición
6.40
Silberschatz, Galvin y Gagne ©2003
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.
Sistemas Operativos 6ª edición
6.41
Silberschatz, Galvin y Gagne ©2003
Planificación en tiempo real
Latencia de despacho
Sistemas Operativos 6ª edición
6.42
Silberschatz, Galvin y Gagne ©2003
Final del Capítulo 6 – Parte a -
Descargar

Module 6: CPU Scheduling