PDF de programación - 5.- Despacho de CPU

5.- Despacho de CPU

Capítulo 5:
Despacho de CPU

n  Conceptos Básicos

n  Criterio de Asignación

n  Algoritmos de Asignación

n  Despacho de Threads

n  Ejemplos de SOs

n  Despacho de Threads de Java

n  Evaluación de Algoritmos

Conceptos Básicos

n  Utilización máxima de CPU con multiprogramación

n  Ciclo CPU–I/O – Ejecución de un proceso = ciclo de CPU

(ejecución) y espera de I/O

n  Distribución de periodos CPU (bursts)

Secuencia CPU - I/O


Histograma de
Tiempos de CPU

Despachador de CPU

n  Selecciona un proceso (ready) en memoria y le asigna el

CPU

n  Decisiones de asignación de CPU se requieren cuando

un proceso:
1. Cambia de estado running a waiting
2. Cambia de running a ready
3. Cambia de waiting a ready
4. Termina

n  Asignación en 1 y 4 es sin desalojo (nonpreemptive)

n  Las otas son con desalojo (preemptive)

Despachador de CPU

n  El Despachador le pasa el control del CPU a los procesos

seleccionados por el despachador de corto plazo; ésto involucra:
n  Context switching
n  Cambio a user mode
n  Salto a la localidad adecuada en el programa para resumir ejecución

n  Latencia de Despacho – tiempo que le lleva al despachador en

deterner un proceso y resumir el otro

Criterio de Despacho

n  Utilización de CPU – mantener el CPU ocupado

n  Throughput – # de procesos que completan ejecución por

unidad de tiempo

n  Tiempo Turnaround – time para ejecutar un proceso en

particular

n  Tiempo de Espera (Waiting time) – time que un proceso ha

estado esperando en la cola ready

n  Tiempo de Respuesta – Tiempo entre el punto en que el

proceso fue lanzado hasta que se produce la primer
respuesta, no output (para ambientes time-sharing)

Criterio de
Optimización

n  Max utilización de CPU

n  Max throughput

n  Min turnaround time

n  Min waiting time

n  Min response time

Despacho First-Come,
First-Served (FCFS)

n  Suponga que los procesos llegan en orden: P1 , P2 , P3



n  La gráfica de Gantt del despacho es:
Burst Time

Process
P1
P2
P3



24
3
3

P1"

0"

n  Waiting time para P1 = 0; P2 = 24; P3 = 27

n  Waiting time promedio: (0 + 24 + 27)/3 = 17

P2"

P3"

24"

27"

30"

FCFS Scheduling (Cont.)

n  Suponga que los procesos llegan en el orden P2 , P3 , P1
n  La gráfica de Gantt del despacho es:



P2"

P3"

P1"

3"

6"

0"

n  Waiting time para P1 = 6; P2 = 0; P3 = 3
n  Waiting time promedio: (6 + 0 + 3)/3 = 3

30"

n  Mucho mejor que el anterior

n  Efecto Convoy: procesos cortos antes que los largos

Despacho
Shortest-Job-First (SJF)

n  Asociate con cada proceso la longitud de su próximo

espacio de CPU (burst). Usar esas longitudes para
asignar el procesador al proceso con el menor tiempo

n  Dos esquemas :

n  nonpreemptive – una vez que se asigna el CPU a un

proceso, no puede ser desalojado, hasta que termina su
CPU burst

n  preemptive – si llega un proceso nuevo, con un CPU burst
menor que el tiempo restante del proceso actual, desalojar.
Este esquema se denomina Shortest-Remaining-Time-First
(SRTF)

n  SJF es óptimo – produce el mínimo promedio waiting

time para un conjunto de procesos

Ejemplo de un
SJF sin Desalojo

Proceso

Tiempo de Llegada

Burst Time

P1
P2
P3
P4

0.0
2.0
4.0
5.0

7
4
1
4



n  SJF (non-preemptive)

P1"

3"

0"

P3"

P2"

P4"

7"

8"

12"

16"

n  Waiting time promedio = (0 + 6 + 3 + 7)/4 = 4

Ejemplo de SJF
con Desalojo



Proceso

Tiempo de llegada

Burst Time

P1
P2
P3
P4

0.0
2.0
4.0
5.0

7
4
1
4

n  SJF (preemptive)

P1"

P2"

P3"

P2"

P4"

P1"

0"

2"

4"

5"

7"

11"

16"

n  Tiempo de espera (Waiting time) promedio

= (9 + 1 + 0 +2)/4 = 3

Longitud del Siguiente
CPU Burst

n  Estimación de la longitud

tn = longitud del n − ésimo CPU burst

n  Promedio exponencial de las longitudes de los CPU

bursts previos

n  Para

τn +1 = predicción del siguiente CPU burst
0 ≤ α≤1

t
ατ
==
1

definir:

n

n

1
(
−+

) .
τα
n

€

€

€



Predicción de la Longitud del

Siguiente CPU Burst

Ejemplos de
Promediado Exponencial

n  α =0

n  τn+1 = τn
n  La historia reciente no cuenta

n  Como α y (1 - α) son menores o

iguales a 1, cada término sucesivo
tiene menos peso que su predecesor

n  α =1

τn+1 = α tn

n 
n  Solo el último CPU burst cuenta

n  Expandiendo la fórmula:

τn+1 = α tn+(1 - α)α tn -1 + …
+(1 - α )j α tn -j + …
+(1 - α )n +1 τ0



Despacho por Prioridad

n  Se asocia un número (entero) de prioridad con cada proceso

n  El CPU se asigna al proceso con la prioridad más alta (número más

pequeño ≡ prioridad más alta)
n  Preemptive
n  nonpreemptive

n  SJF es un caso de despacho por prioridad, donde la prioridad es el

tiempo predicho del siguiente CPU burst

n  Problema ≡ Inanición (Starvation) – procesos de baja prioridad pueden

quedarse en la cola para siempre

n  Solución ≡ Envejecimiento (Aging) – Incrementar la prioridad conforme

avanza el tiempo

Round Robin (RR)

n  Se asigna a cada proceso una unidad de tiempo de CPU (time

quantum), típicamente 10-100 milisegundos. Cuando se le
termina el tiempo, el CPU se le retira y el proceso se envía al
final de la cola ready queue.

n  Si hay n procesos en la cola y el time quantum es q, cada

proceso obtiene 1/n del tiempo de CPU en periodos de a lo
más q unidades de tiempo consecutivas. Ningún proceso
espera más de (n-1) q unidades de tiempo.

n  Desempeño (Performance)

n  q grande ⇒ FIFO
n  q pequeño ⇒ q debe ser grande con respecto al tiempo para hacer

context switch, si no, el costo (overhead) es demasiado

Ejemplo de RR con
Time Quantum = 20

Proceso

P1
P2
P3
P4
n  Gráfica de Gantt:



CPU Burst

53
17
68

24



P1" P2" P3" P4" P1" P3" P4" P1" P3" P3"

0"

20" 37"

57"

77" 97" 117" 121" 134" 154" 162"

n  Típicamente, el tiempo turnaround es mayor que en SJF, pero

se tiene mejor respuesta

Time Quantum y el Tiempo
de Context Switch

Tiempo Turnaround y el
Time Quantum

Colas Multinivel

n  La cola Ready queue se particiona en colas independientes:

foreground (interactivos)
background (batch)

n  Cada cola tiene su propio algoritmo de despacho

foreground – RR

n 
n  background – FCFS

n  Se debe hacer despacho entre colas

n  Despacho de prioridad fija (i.e., servir a todos los del foreround y

después a los del background). Posibilidad de inanición
(starvation).

n  Rebanada de tiempo (Time slice) – cada cola obtiene una cantidad
de tiempo de CPU, el cual puede despachar entre sus procesos; i.e.,
80% al foreground en RR, 20% al background en FCFS

Despacho en
Colas Multinivel

Colas Multinivel con
Retroalimentacón

n  Un proceso puede migrar entre varias colas (i.e. aging)

n  Un despachador multinivel con retroalimentación se define por

los siguientes parámetros:
n  Número de colas
n  Algoritmos de despacho para cada cola
n  Método para determinar cuando promover un proceso
n  Método para determinar cuando demover a un proceso
n  Método para determinar a que cola se asigna un proceso cuando

necesita servicio

Ejemplo de Colas Multinivel
con Retroalimentacón

n  Tres colas:

n  Q0 – RR con time quantum de 8 milisegundos
n  Q1 – RR con time quantum de 16 milisegundos
n  Q2 – FCFS

n  Despacho (Scheduling)

n  Un proceso nuevo entra a Q0 la cual opera en FCFS.
Cuando le toca, recibe el CPU por 8 milisegundos. Si
no termina en 8 milisegundos, migra a Q1.

n  En Q1 el proceso vuelve a ser servido mediante FCFS y
recibe 16 milisegundos adicionales. Si aún no termina,
se desaloja (preemption) y migra a Q2.

Colas Multinivel con
Retroalimentacón

Despacho de Threads

n  Despacho local – ¿Cómo decide la biblioteca de threads

qué thread poner en un LWP disponible?

n  Despacho global – ¿Cómo decide el kernel que thread

ejecutar?

Ejemplos

n  Solaris scheduling

n  Windows XP scheduling

n  Linux scheduling

Despacho en Solaris 2

Tabla de Despacho en
Solaris

Prioridades en
Windows XP

Despacho en Linux

n  Dos algoritmos: time-sharing y real-time
n  Time-sharing

n  Priorides basadas en créditos – el proceso con más créditos es

despachado

n  Restar crédito cuando el timer interrumpe
n  Cuando crédito = 0, se despacha otro proceso
n  Cuando todos los procesos tienen crédito = 0, restablecer créditos

n  Basado en prioridad, historia y otros factores

n  Real-time

n  Soft real-time
n  Cumple con Posix.1b – dos clases

n  FCFS y RR
n  Procesos con alta prioridad son ejecutados primero

Prioridades y el tamaño
del Time-slice

Listas de Tareas
Indexadas por Prioridades

Evaluación de Algoritmos

n  Modelado determinista – toma una carga particular

predetermnada y define el desempeño de cada
algoritmo para esa carga

n  Modelos de Colas (Queueing models)

n  Implementación

Modelado Determinista
FCFS

Proceso

CPU Burst

P1
P2
P3
P4
P5

10
29
3
7
12



Modelado Determinista
SJF Sin Desalojo

Proceso

CPU Burst

P1
P2
P3
P4
P5

10
29
3
7
12



Modelado Determinista
Round Robin

Proceso

CPU Burst

P1
P2
P3
P4
P5

10
29
3
7
12



Evaluación de Algoritmos