Sistemas de Computación

2. PLANIFICACION DE UCP

2.1 Multiprogramación y planificación

Uno de los conceptos más importantes en SOs modernos es el

multiprogramación. Básicamente, multiprogramación consiste en tener más
de un programa en la memoria al mismo tiempo y la UCP puede ser
compartida por estos programas. Este esquema de trabajo mejora la
eficiencia de un sistema computacional obteniendo más trabajo en menos
tiempo.

La idea de multiprogramación es más o menos simple, un job 1 es

ejecutado hasta que este debe esperar, típicamente la espera se debe a la
necesidad de completar una operación de E/S. En los sistemas más simples,
este tiempo de espera es tiempo perdido de la UCP. Con multiprogramación
se intenta utilizar este tiempo perdido con la ejecución de otro job.

Lo anterior implica que la UCP estará ejecutando gran cantidad de

jobs o tareas, principalmente provenientes de los usuarios, sin embargo,
algunas de las tareas corresponderán a actividades del sistema. La UCP debe
responder a interrupciones por errores, interrupciones de E/S, etc. Llamaremos
a cualquier programa que se esté ejecutando proceso.

2.2 Estados de los procesos

El éxito de la planificación de la UCP depende de la siguiente

propiedad observada en relación con la ejecución de un proceso, la
ejecución de un proceso es un ciclo de ejecución de UCP y espera por E/S. Un
proceso alterna entre estos dos estados repetidamente.

1 job es el nombre que se le da a un programa en ejecución sobre un sistema computacional

Javier Vidal Valenzuela 6

 Sistemas de Computación

…
LOAD
STORE
ADD proceso en UCP
STORE
READ from file
espera por E/S proceso en E/S
STORE
INCR INDEX proceso en UCP
WRITE to file
espera por E/S proceso en E/S
LOAD
STORE
ADD proceso en UCP
STORE
READ from file
espera por E/S proceso en E/S

…
Cuando un programa se ejecuta este cambia de estado. El estado de
un proceso está definido por su actividad actual y puede ser: nuevo, listo,
ejecutando, esperando y detenido.

2.3 Concepto de PCB (Process Control Block)

Como el SO debe administrar todos los procesos que se estén

ejecutando, entonces requiere la información de cada uno, el bloque de
control de procesos (PCB) se encarga de almacenar dicha información. Entre
la información necesaria para la planificación de los procesos se encuentra:

• El estado del proceso

• El valor del contador de programa

• Los registros de la UCP

• Información sobre la administración de la memoria

• Información sobre la cantidad de UCP utilizada

• Información de estado de E/S

• Información sobre planificación de UCP (prioridad, etc.)

y en general, cualquier información que varíe entre los procesos.

Javier Vidal Valenzuela 7

 Sistemas de Computación

Puede existir un número máximo fijo de procesos que se pueden

ejecutar (número de PCBs máximo fijo), o bien, el número de PCBs puede
variar dinámicamente.

Cuando un proceso requiere una E/S o cuando el SO le quita el control

a un proceso para entregarlo a otro proceso ocurre lo ilustrado en la siguiente
figura:

2.4 Algoritmos de planificación.

La UCP tiene dos planificadores principales denominados planificador

long-term y planificador short-term. Un planificador long-term determina que
jobs serán admitidos en el sistema, generalmente, hay más jobs que se quieren
ejecutar que los que realmente soporta el sistema. El planificador short-term
selecciona los jobs que ya están en la memoria, listos para ejecutarse, y les
entrega el control de la UCP.

long-term short-term

fin
Cola de listos UCP

Cola de esp era

E/S p or E/S

Obviamente, el planificador short-term es más frecuentemente

utilizado que el planificador long-term, debido a que será más frecuente los
requerimientos de los procesos por E/S que la ejecución de comandos por
parte del usuario.

Javier Vidal Valenzuela 8

 Sistemas de Computación

Los algoritmos de planificación de la UCP tienen diferentes

propiedades que pueden favorecer a algún tipo de proceso. Para decidir
que algoritmo usar debe existir criterios de comparación, siendo los más
importantes:

• Utilización de la UCP Siempre se espera que la UCP esté siendo utilizada en

un 100%, sin embargo, en sistemas reales el rango varía
normalmente entre 40% (para sistemas de carga baja)
a 90% (para sistemas altamente cargados).

• Throughput Corresponde al número de jobs que son completados

en alguna unidad de tiempo.

• Turnaround time Desde el punto de vista de un job particular, resulta

importante determinar cuánto tiempo le toma a un job
en ejecutarse. El intervalo desde el momento en que
un job es suministrado al sistema hasta que éste
completa su ejecución se denomina turnaround time.
El turnaround time es la suma de los periodos gastados
por el proceso en espera de un dato desde memoria,
esperando en la cola de listos, ejecutándose o en un
proceso de E/S.

• Tiempo de espera Los algoritmos de planificación de UCP no son

afectados por la cantidad de tiempo que un job pasa
ejecutándose o realizando una E/S, sino que son
afectados por el tiempo que un job pasa en la lista de
listos esperando por la UCP. Así, podría ser mejor
conocer el tiempo de espera de cada job que
conocer su turnaround time.

Una vez que se ha seleccionado el criterio para decidir que tipo de

procesos tendrá prioridad es posible concebir algún algoritmo. Algunos
algoritmos exponentes son: FCFS (First Come First Service), SJF (Shortest Job
First) y Prioridad.

2.4.1. FCFS

Sin duda, el algoritmo de planificación más simple es FCFS y consiste

en entregar el control de la UCP a los procesos, en el orden en que estos

Javier Vidal Valenzuela 9

 Sistemas de Computación

llegan a la lista de listos. Para su implementación basta con utilizar una fila
FIFO que administre la asignación de los procesos a la UCP.

El rendimiento de FCFS es bastante bajo, para ejemplificar,

consideremos los siguientes tres procesos (se supondrá que se conoce el
tiempo de UCP de cada job):
Job 1 2 3
Tiempo de UCP 24 3 3
Si los jobs llegan en orden 1, 2 y 3, y son asignados por un algoritmo
FCFS, el resultado será el siguiente:

JOB

24 27 30 Tiempo de ejecución

El turnaround time para el job 1 es 24, para el job 2 es 27 y para el job 3

es 30. De esta manera, el turnaround time promedio será (24+27+30)/3=27. Por
otro lado, si los jobs llegan en orden 2, 3 y 1, y son asignados por un algoritmo
FCFS, el resultado será el siguiente:

JOB

3 6 30 Tiempo de ejecución

En este caso, el turnaround time promedio desciende a 13. Lo que

demuestra que FCFS no es eficiente y puede variar sustancialmente.

Además, se debe considerar el rendimiento de FCFS en situaciones

dinámicas. Por ejemplo, supóngase un proceso 1 que es altamente intensivo
en recursos y un conjunto de procesos 2, 3, 4 y 5 de muy pequeña carga. Si el
proceso 1 es el primero en ocupar la UCP tardará suficiente tiempo en
ejecutarse, lo que permitirá que los procesos 2, 3 ,4 y 5 entren en la lista de
listos a la espera de la UCP. Cuando el proceso 1 libere la UCP, pasará a
satisfacer un requerimiento de E/S y tardará allí también tanto tiempo como
para que los procesos 2, 3, 4 y 5 ocupen y liberen la UCP, quedando cada uno

Javier Vidal Valenzuela 10

 Sistemas de Computación

de ellos en una cola de espera por E/S mientras el proceso 1 termina. En

resumen, si existe un proceso muy intensivo en recursos en comparación con
el resto de los procesos en un sistema, se produce el llamado efecto convoy,
que consiste en que todos los procesos "persiguen" al proceso más intensivo
en recursos, quedando siempre a la espera por los recursos ocupados por
dicho proceso.

2.4.2. SJF

Este algoritmo asocia a cada job en la lista de listos, el tiempo de UCP

de cada proceso, de tal manera que, cuando la UCP está disponible, es
asignada al job con el tiempo de UCP más pequeño.

Como un ejemplo considere el siguiente conjunto de jobs:

Job Tiempo de UCP
1 6
2 3
3 8
4 7
Usando algoritmo de planificación SJF se obtendrá el siguiente
resultado:

JOB

3 9 16 24 Tiempo de ejecución

En este caso el turnaround time promedio es 13.

SJF es probablemente óptimo, ya que reduce el tiempo de espera

promedio de cada job. Sin embargo, la dificultad principal para la
implementación de este algoritmo es que no se conoce ni es posible conocer
el tiempo de UCP real de cada proceso, por lo cual, se han definido algunas
formas de estimar dicho tiempo. De esta manera, SJF es aplicable pero sólo
con estimaciones de tiempo para la duración de cada proceso en uso de la
UCP.

El tiempo de UCP es generalmente predicho como una media

exponencial de los tiempos de UCP anteriores. Supongamos que tn el tiempo

Javier Vidal Valenzuela 11

 Sistemas de Computación

de duración n-ésimo, y sea τn el valor predicho para el n-ésimo tiempo de

UCP. Entonces, para 0 ≤ α ≤ 1, se define:

τn+1 = α * tn + (1 - α) * τn

Esta fórmula define una media exponencial para los tiempos estimados
de UCP. El valor de tn contiene la información más reciente; τn almacena la
historia pasada; y, el parámetro α controla el peso relativo de la historia y la
información reciente para hacer una predicción.

Generalmente α = ½ (ver siguiente gráfico)

Se puede extender la fórmula a

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

2.4.3. Prioridad

En este caso, a los procesos se asocia un criterio que permite

asignarles prioridad, de tal manera que cuando un proceso libera la UCP, la
ocupa el proceso de mayor prioridad. Si dos o más procesos tienen la misma
prioridad entonces se asignan según FCFS. Nótese que el algoritmo SJF es un
caso particular de los algoritmos de prioridad.

Las prioridades pueden ser definidas interna o externamente. Las

prioridades internas derivan de algunos elementos cuantificables por el SO,
tales como, el tiempo de UCP, cantidad de memoria utilizada, número de
archivos abiertos, etc. Externamente, las prioridades son asignadas por
criterios como, tipo de usuario, costo de la conexión o de uso del sistema,
departamento que ejecuta el trabajo, etc.

Javier Vidal Valenzuela 12

 Sistemas de Computación

Un problema importante con los algoritmos de prioridad es el bloqueo

indefinido. Se trata de proceso que están listos para ejecutarse, pero que por
su baja prioridad no les es asignado el procesador. Una solución para este tipo
de problema es el envejecimiento, el cual consiste en aumentar
gradualmente la prioridad de un proceso mientras éste permanece en el
sistema, de esta manera se puede asegurar su finalización.

2.4.4. Algoritmos Apropiativos

Los algoritmos FCFS, SJF y de prioridad descritos hasta ahora son no

apropiativos, esto es, una vez que la CPU ha sido asignada a un proceso, no
es liberada sino hasta que el proceso termina o hasta que el proceso entra en
un requerimiento de E/S, pudiendo eventualmente ser retenida por un largo
tiempo. Un algoritmo apropiativo obliga a la liberación del procesador si éste
ha estado ocupado por un largo tiempo sólo por un proceso.

FCFS es intrínsecamente no aprpiativo, es decir, no hay forma de

modificarlo para hacerlo apropiativo. Sin embargo, SJF puede ser apropiativo
o no apropiativo. Para implementarlo apropiativo se debe verificar, cada vez
que un proceso entra a la lista de listos, si lo que le resta al proceso que se
está ejecutando es mayor que el proceso recien ingresado a dicha lista, si es
así, se libera el procesador dejándolo al nuevo proceso. Este algoritmo es
llamado SRTF (Shortest Remaining Time First).

En el caso de los algoritmos de prioridad ocurre una situación muy

análoga que la descrita para SJF, ya que como se mencionó, SJF es un caso
particular de prioridad.

El siguiente ejemplo ilustra el comportamiento de SRJF. Supongamos el

siguiente conjunto de jobs:

Job Tiempo de Tiempo de UCP

llegada
1 0 8
2 1 4
3 2 9
4 3 5

El resultado de la aplicación de SRJF a estos procesos queda

gráficamente:

Javier Vidal Valenzuela 13

 Sistemas de Computación

JOB

4
3
2
1

1 5 10 17 24 Tiempo de ejecución

2.4.5. Round Robin

El algoritmo de planificación Round Robin ha sido diseñado

especialmente para sistemas de tiempo compartido, para su aplicación se
define una pequeña unidad de tiempo denominada quantum y la lista de
listos es tratada como una fila circular. En sistemas reales un quantum
típicamente dura entre 10 y 100 ms.

Para su aplicación, el SO toma el primer proceso de la lista de listos,

inicializa el timer para interrumpir el proceso cuando se cumpla el quantum y
entrega el control de la UCP al proceso. Después de esto el proceso puede
terminar o entrar en una espera por E/S, con lo cual se libera la UCP y el SO la
asigna al siguiente proceso, por otro lado, se puede cumplir el quantum de
tiempo, y el SO le quitará el control del procesador al proceso para
entregárselo al siguiente en la lista de listos, ubicando al proceso retirado al
final de dicha lista.

El siguiente ejemplo ilustra la operación de Round Robin.

Supongamos los siguientes procesos:
Job 1 2 3
Tiempo de UCP 24 3 5
El resultado de la planificación usando Round Robin es:

JOB

3
2
1

4 8 12 16 20 Tiempo de ejecución

Notar que si el quantum es muy grande, entonces, el SO asignará los

procesos según el algoritmo FCFS. En el caso de quantum pequeño se debe
aclarar que, hasta ahora se ha supuesto que en el momento en que un
proceso entrega el control de la UCP, otro proceso toma el control

Javier Vidal Valenzuela 14

 Sistemas de Computación

instantáneamente, sin embargo, esto no ocurre así realmente. Lo que en

verdad ocurre es que el control del procesador es entregado al SO para que
realice el cambio de proceso, que técnicamente se denomina conmutación
de contexto. La conmutación de contexto consiste en guardar el estado del
proceso saliente en una estructura denominada PCB (Program Control Block)
y en recuperar de la misma estructura el estado del proceso que tomará el
control del procesador.

JOB
S.O.
3
2
1
Tiempo ocupado por por el
el SO
SO
para hacer
hacer lala conmutación
conmutación
4 4+t
4+ de contexto.

El PCB guarda , por cada proceso en espera, los valores de los

registros, las posiciones de memoria utilizadas, los archivos abiertos, etc.

Por tanto, si el quantum es muy pequeño, entonces la mayor parte de

la actividad del procesador corresponderá al proceso del SO que realiza el
cambio de contexto, lo cual, obviamente va en desmedro de la actividad de
los procesos de los usuarios.

Javier Vidal Valenzuela 15