El Algoritmo De Despacho

EL ALGORITMO DE DESPACHO.

Cuando hay más de un proceso que está en condiciones de ejecutar en la CPU, se debe
escoger alguno. El encargado de tomar esa decisión es el planificador o scheduler, y el
algoritmo que usa se llama algoritmo de despacho o planificación.
Posibles objetivos (algunos de ellos contradictorios) del algoritmo de planificación son:

Justicia. Asegurarse que todos losprocesos tengan su turno de CPU.

Eficiencia. Mantener la CPU ocupada todo el tiempo.

Tiempo de respuesta. Minimizar el tiempo de respuesta de los usuarios
interactivos.

Rendimiento o productividad (throughput). Maximizar el número de trabajos
terminados por unidad de tiempo.

Tiempo de espera. Minimizar el tiempo medio de espera (en la cola READY) de
los procesos. Tiempo transcurridoentre llegar y ser atendido.

Una complicación adicional que hay que tener presente es que cada proceso es único e
impredecible. Algunos son intensivos en I/O (I/O-bound), es decir, pierden la mayor
parte del tiempo esperando por I/O; otros son intensivos en CPU (CPU-bound), es decir,
requieren principalmente tiempo de CPU. En cualquier caso, todos los procesos alternan
entre una fase deejecución de CPU y otra de espera por I/O. Aunque la duración de las
fases de CPU es impredecible y varía mucho entre un proceso y otro, tiende a tener una
frecuencia como la de la figura: hay un gran número de fases de CPU cortos, y muy
pocos largos. Esta información puede ser importante para seleccionar un algoritmo de
planificación adecuado.

¿Cuándo hay que planificar? Recordando eldiagrama de transiciones, una decisión de
planificación puede o debe tomarse cuando ocurre cualquiera de las siguientes transiciones
entre estados de un proceso:

SISTEMAS OPERATIVOS I MODULO DESPACHO DE PROCESOS PAG No 1 / 7

1. EJECUTANDO a BLOQUEADO.

2. EJECUTANDO a TERMINADO.

3. EJECUTANDO a LISTO.

4. BLOQUEADO a LISTO.

En los casos 1 y 2, necesariamente hay que escoger un nuevoproceso, pero en los casos
3 y 4 podría no tomarse ninguna decisión de scheduling, y dejar que continúe ejecutando
el mismo proceso que estaba ejecutando. En ese caso, se habla de planificación no-
expropiadora (nonpreemptive, como en Windows 3.x). Si en cambio se toma una decisión
de scheduling en los casos 3 y 4, entonces se habla de planificación expropiadora.
Esta última es más segura y másjusta, pero tiene un problema: consideremos dos procesos
que comparten información, y que a uno de ellos se le quita la CPU justo cuando estaba
en medio de una actualización de los datos compartidos. Cuando sea el turno del segundo
proceso, éste podría intentar leer los datos cuando están en un estado inconsistente. Este
problema se remedia con sincronización.

El primero que llega seatiende primero

FCFS (First-come, first-served) por sus siglas en inglés. Es un algoritmo que no usa
expropiación, y que consiste en atender a los procesos por estricto orden de llegada a
la cola READY. Cada proceso ejecuta hasta que termina, o hasta que hace una llamada
bloqueante (de I/O), o sea, ejecuta su fase de CPU completa. La gracia es que se trata de un
algoritmo muy simple: la colaREADY se maneja como una simple cola FIFO. El problema
es que el algoritmo es bastante malo.

Tiempo de espera

Consideremos que los procesos P1, P2 y P3 están LISTOS para ejecutar su siguiente fase
de CPU, cuya duración será de 24, 3 y 3 milisegundos, respectivamente. Si ejecutan en el
orden P1, P2, P3, entonces los tiempos de espera son: 0 para P1, 24 para P2 y 27 para P3,
o sea, enpromedio, 17 ms. Pero si ejecutan en orden P2, P3, P1, entonces el promedio es
sólo 3 ms. En consecuencia, FCFS no asegura para nada que los tiempos de espera sean los
mínimos posibles; peor aún, con un poco de mala suerte pueden llegar a ser los máximos
posibles.

Utilización de CPU

Ahora supongamos que tenemos un proceso intensivo en CPU y varios procesos intensivos
en I/O. Entonces podría...