La política más simple de planificación es la FCFS. A medida que un proceso pasa al estado listo, este es agregado a la cola de listos. Cuando el proceso que actualmente está ejecutando cesa su ejecución entonces el proceso más viejo en la cola es seleccionado para correr. La implementación de esta política es a través de colas FIFO (First-In, First-Out). Cuando el CPU está libre, éste es asignado al proceso que está en la cabeza de la cola.
FCFS es un algoritmo nonpreemptive, pues una vez que el CPU es asignado a un proceso, este lo mantiene hasta que espontáneamente lo suelta, ya sea porque el proceso finalizó o por algún requerimiento de E/S.
El tiempo de espera bajo esta política tiende a ser alto. Además , tiende a favorecer aquellos procesos que requieren más tiempo de CPU (CPU-bound). Consideren el caso donde tenemos una colección de procesos. Uno de ellos utiliza más CPU que los otros, y el resto de los procesos requieren más trabajo de E/S (I/O-bound). Cuando el proceso CPU-bound ejecuta, los otros procesos esperan. Algunos de estos estarán en las colas de los dispositivos de E/S pero eventualmente en algún instante pasarán a la cola de procesos listos. En este momento, muchos de los dispositivos de E/S estarán ociosos. Cuando el proceso en ejecución deje el estado Running, los procesos I/O-bound pasarán a ejecutar y rápidamente volverán a bloquearse en espera de E/S. Si el proceso CPU-bound se encuentra bloqueado, entonces el procesador estará ocioso. Por lo tanto, FCFS puede ocasionar un uso indeficiente tanto del procesador como de los dispositivos de E/S.
Proceso
|
Tiempo de llegada
|
Tiempo de Servicio
|
Tiempo de Comienzo
|
Tiempo de Finalización
|
Turnaround
|
Tiempo de Espera
|
A
|
0
|
1
|
0
|
1
|
1
|
0
|
B
|
1
|
100
|
1
|
101
|
100
|
0
|
C
|
2
|
1
|
101
|
102
|
100
|
101-2=99
|
D
|
3
|
100
|
102
|
202
|
199
|
102-3=99
|
Promedio
|
100
|
49.50
|
Proceso
|
Tiempo de llegada
|
Tiempo de Servicio
|
Tiempo de Comienzo
|
Tiempo de Finalización
|
Turnaround
|
Tiempo de Espera
|
B
|
0
|
100
|
0
|
100
|
100
|
0
|
D
|
1
|
100
|
100
|
200
|
199
|
100-1=99
|
A
|
2
|
1
|
200
|
201
|
201-2=199
|
200-2=198
|
C
|
3
|
1
|
201
|
202
|
202-3=199
|
201-3=198
|
Promedio
|
232
|
123.50
|
El tiempo promedio de espera bajo una política FCFS generalmente no es mínimo y puede variar sustancialmente si hay mucha diferencia entre las duraciones de ciclo de los procesos.
En el segundo ejemplo, se presenta un efecto convoy donde los procesos esperan a que un proceso grande deje el CPU
Shortest-Job-First (SJF)
Este algoritmo selecciona al proceso con el próximo tiempo de ejecución más corto. Un proceso corto saltará a la cabeza de la cola. La ejecución de un proceso consiste en ciclos de ejecución de CPU y ciclos de espera por E/S. El algoritmo selecciona aquel proceso cuyo próximo ciclo de ejecución de CPU sea menor. El problema está en conocer dichos valores, pero podemos predecirlos usando la información de los ciclos anteriores ejecutados.
SJF
| ||||||
Proceso
|
Tiempo de llegada
|
Tiempo de Servicio
|
Tiempo de Comienzo
|
Tiempo de Finalización
|
Turnaround
|
Tiempo de Espera
|
A
|
0
|
8
|
0
|
8
|
8
|
0
|
B
|
1
|
4
|
8
|
12
|
12-1=11
|
8-1=7
|
C
|
2
|
9
|
17
|
26
|
26-2=24
|
17-2=15
|
D
|
3
|
5
|
12
|
17
|
17-3=14
|
12-3=9
|
Promedio
|
14.25
|
10.33
| ||||
FCFS
| ||||||
Proceso
|
Tiempo de llegada
|
Tiempo de Servicio
|
Tiempo de Comienzo
|
Tiempo de Finalización
|
Turnaround
|
Tiempo de Espera
|
A
|
0
|
8
|
0
|
8
|
8
|
0
|
B
|
1
|
4
|
8
|
12
|
12-1=11
|
8-1=7
|
C
|
2
|
9
|
12
|
21
|
21-2=19
|
12-2=10
|
D
|
3
|
5
|
21
|
26
|
26-3=23
|
21-3=18
|
Promedio
|
20.33
|
11.66
| ||||
El SJF es probablemente optimal pues da el mínimo tiempo promedio de espera. El problema está en conocer la duración del próximo requerimiento de CPU para cada proceso. Esta duración puede predecirse suponiendo que el próximo ciclo puede ser similar a los anteriores.
Este algoritmo puede ser preemptive o no. Cuando un nuevo proceso llega a la cola de procesos listos mientras otro se está ejecutando, el nuevo proceso puede tener el ciclo de duración de CPU más corto que lo que falta por ejecutar del proceso actual. En el caso de un esquema preemptive, el CPU será asignado al proceso que acaba de llegar a la cola. Este algoritmo se conoce como Shortest Remaining Time First (SRTF).
Prioridad
En muchos sistemas, los procesos tienen prioridades asignadas, y el planificador escogerá aquel proceso con mayor prioridad.
Cuando un proceso debe ser seleccionado, el planificador por prioridades seleccionará aquel proceso que tenga mayor prioridad. Si hay más de un proceso entonces se deberá seguir alguna política de selección.
Un problema que presenta un esquema de planificación por prioridades puro es que los procesos con la prioridad más baja pueden sufrir de inanición o bloqueo indefinido. Un proceso que está listo para correr pero espera porque siempre hay procesos con prioridad más alta.
Para evitar este problema, se puede ir incrementando gradualmente la prioridad de los procesos (envejecimiento).
SJF es un caso especial de planificación por Prioridad, donde la prioridad es el inverso del valor estimado del próximo ciclo de CPU ( a menor ciclo, mayor prioridad).
Proceso
|
Tiempo de llegada
|
Prioridad
|
Tiempo de Servicio
|
Tiempo de Comienzo
|
Tiempo de Finalización
|
Turnaround
|
Tiempo de Espera
|
A
|
0
|
2
|
8
|
0
|
8
|
8
|
0
|
B
|
1
|
1
|
4
|
22
|
26
|
26-1=25
|
22-1=21
|
C
|
2
|
4
|
9
|
8
|
17
|
17-2=15
|
8-2= 6
|
D
|
3
|
2
|
5
|
17
|
22
|
22-3=19
|
17-3=14
|
Promedio
|
16.75
|
10.25
|
Este algoritmo puede ser preemptive y nonpreemptive. En el caso de preemptive, cuando un proceso llega a la cola de procesos listos, su prioridad es comparada con la prioridad del proceso que está corriendo. Si la prioridad del nuevo proceso es mayor, entonces se atiende al nuevo proceso.
Round Robin
Una manera rápida de reducir la penalización que los procesos cortos sufren con FCFS es usar expropiación basada en un reloj. Una interrupción de reloj es generada a intervalos periódicos. Cuando ocurre la interrupción, el proceso en ejecución es colocado en la cola de procesos listos y el próximo trabajo es seleccionado basado en el esquema FCFS. A cada proceso se le da un trozo de tiempo.
La principal decisión de diseño que surge con Round Robin es el tamaño del trozo o quantum. Si el quantum es muy corto, entonces los procesos se moverán a través del sistema rápidamente. Por otro lado, hay un cierto overhead o desperdicio de tiempo envuelto con el manejo de la interrupción de reloj y las funciones de planificación y despacho. Por lo tanto quanta muy pequeños deberían evitarse. Una alternativa es usar un quantum de tiempo que sea un poco más grande que el tiempo promedio requerido para una interacción típica.
Round Robin es particularmente efectivo para sistemas generales de tiempo compartido. Se implementa con una cola FIFO de procesos. Nuevos procesos son agregados al final de la cola, y toma el proceso que se encuentra en la cabeza de la cola. Actualiza el timer para que interrumpa después del quantum de tiempo.
El desempeño de este algoritmo dependerá del tamaño del quantum. Si el quantum es infinito entonces degenera en FCFS. Si el quantum es muy pequeño entonces Round Robin es llamado compartición de CPU y en teoría pareciera que cada proceso tiene su propio procesador corriendo a 1/n la velocidad del procesador real.
Bajo este esquema es importante considerar el efecto del cambio de contexto.
Round Robin (RR q=3)
| ||||||
Proceso
|
Tiempo de llegada
|
Tiempo de Servicio
|
Tiempo de Comienzo
|
Tiempo de Finalización
|
Turnaround
|
Tiempo de Espera
|
A
|
0
|
8
|
0, 12, 21
|
3, 15, 23
|
23
|
15
|
B
|
1
|
4
|
3, 15
|
6, 16
|
16-1=15
|
11
|
C
|
2
|
9
|
6, 16, 23
|
9, 19, 26
|
26-2=24
|
15
|
D
|
3
|
5
|
9, 19
|
12,21
|
21-3=18
|
11
|
Promedio
| ||||||
0 comentarios:
Publicar un comentario