Universidad Mariano Gálvez de Guatemala

Facultad De Ingeniería En Sistemas

Sistemas Operativos.

María de Los Ángeles Carpio Arana.

Algoritmos de planificación de sistemas operativos.

Nombre No. Carné

Lester Josué García Valladares 1790-19-13011

Leonel de Paz Martínez 1790-19-12688

Kimberly Stephanie Moreno López 1790-19-15534

Martes 17 de agosto de 2021

 Índice.
Algoritmos de planificación....................................................................................................3

Porcentaje de utilización de la CPU por procesos de usuario.............................................3

Rendimiento (throughput)...................................................................................................3

Tiempo de espera (E)..........................................................................................................3

Tiempo de finalización (F)..................................................................................................3

Penalización (P)...................................................................................................................3

1. Planificación de Plazo Fijo..............................................................................................4

2. Planificación Primero en Entrar-Primero en Salir (FIFO, First In First Out).................4

¿Para qué sirve esta Simulación?........................................................................................5

3. Planificación por Turno Rotatorio (Round Robin)..........................................................5

4. Tamaño del Cuanto..........................................................................................................7

5. Planificación por Prioridad al más corto (SJF, Short Job First)......................................8

6. Planificación por Prioridad al Tiempo Restante más Corto (SRTF, Short Remaining

Time First)...............................................................................................................................9

7. Planificación a la Tasa de Respuesta más Alta................................................................9

8. Planificación por el Comportamiento............................................................................10

Planificación apropiativa y no apropiativa............................................................................10

Ventajas y desventajas de los algoritmos de planificación...................................................12

 Algoritmos de planificación

En los siguientes sub apartados vamos a estudiar ciertos algoritmos utilizados para
planificar la CPU, la elección de uno (o de una mezcla de varios) depende de decisiones de
diseño. Antes de exponer los algoritmos vamos a explicar ciertas medidas que se utilizan
para evaluarlos.

Porcentaje de utilización de la CPU por procesos de usuario. La CPU es un recurso

caro que necesita ser explotado, los valores reales suelen estar entre un 40% y un 90%.

Rendimiento (throughput) = nº de ráfagas por unidad de tiempo. Se define

una ráfaga como el período de tiempo en que un proceso necesita la CPU; un proceso,
durante su vida, alternas ráfagas con bloqueos. Por extensión, también se define como el nº
de trabajos por unidad de tiempo.

Tiempo de espera (E) = tiempo que una ráfaga ha permanecido en estado listo.

Tiempo de finalización (F) = tiempo transcurrido desde que una ráfaga comienza a existir
hasta que finaliza. F = E + t (t = tiempo de CPU de la ráfaga).

Penalización (P) = E + t / t = F / t, es una medida adimensional que se puede aplicar

homogéneamente a las ráfagas independientemente de su longitud.

En general, hay que maximizar los dos primeros parámetros y minimizar los tres últimos.
Sin embargo, estos objetivos son contradictorios, el dedicar más tiempo de CPU a los
usuarios se hace a costa de llamar menos al algoritmo de planificación (menos cambios de
proceso), y de simplificarlo. Esto provoca que la CPU se reparta menos equitativamente
entre los procesos, en detrimento de los últimos tres parámetros.

  Así pues, dependiendo de los objetivos se elegirá cierto algoritmo. En los sistemas
por lotes suele primar el rendimiento del sistema, mientras que en los sistemas interactivos
es preferible minimizar.
 1. Planificación de Plazo Fijo 
 

En la planificación de plazo fijo se programan ciertos trabajos para terminarse en un tiempo

específico o plazo fijo. Estas tareas pueden tener un gran valor si se entregan a tiempo, y
carecer de él si se entregan después del plazo. Esta planificación es compleja por varios
motivos:

El usuario debe informar por adelantado de las necesidades precisas de recursos del
proceso. Semejante información rara vez está disponible.

 El sistema debe ejecutar el proceso en un plazo fijo sin degradar demasiado el servicio a
los otros usuarios y debe planificar cuidadosamente sus necesidades de recursos dentro del
plazo. Esto puede ser difícil por la llegada de nuevos procesos que impongan demandas
imprevistas al sistema.

 Si hay muchas tareas a plazo fijo activas al mismo tiempo, la planificación puede ser tan
compleja que se necesiten métodos de optimización avanzados para cumplir los plazos.

 La administración intensiva de recursos requerida por la planificación de plazo fijo puede
producir un gasto extra substancial.

2. Planificación Primero en Entrar-Primero en Salir (FIFO, First In First Out)

 

Cuando se tiene que elegir a qué proceso asignar la CPU se escoge al que llevara más
tiempo listo. El proceso se mantiene en la CPU hasta que se bloquea voluntariamente.

La ventaja de este algoritmo es su fácil implementación, sin embargo, no es válido para

entornos interactivos ya que un proceso de mucho cálculo de CPU hace aumentar el
tiempo de espera de los demás procesos . Para implementar el algoritmo (ver figura 2) sólo
se necesita mantener una cola con los procesos listos ordenada por tiempo de llegada.
Cuando un proceso pasa de bloqueado a listo se sitúa el último de la cola.

En a) el proceso P7 ocupa la CPU, los procesos P2, P4 y P8 se mantienen en la lista de

preparados. En b) P7 se bloquea (ya sea al realizar una E/S, una operación WAIT sobre un
semáforo a cero u otra causa) y P2 pasa a ocupar la CPU. En c) ocurre un evento
(finalización de la operación de E/S, operación SIGNAL, ...) que desbloquea a P7, esto lo
vuelve listo, pasando al final de la cola de procesos listos.

Algunas de las características de este algoritmo es que es no apropiativo y justo en el

sentido formal, aunque injusto en el sentido de que: los trabajos largos hacen esperar a los
cortos y los trabajos sin importancia hacen esperar a los importantes. Por otro lado
es predecible pero no garantiza buenos tiempos de respuesta y por ello se emplea como
esquema secundario.

¿Para qué sirve esta Simulación?

La siguiente herramienta presenta una simulación creada con el objetivo de hacer entender
al usuario el algoritmo de planificación Primero en Entrar Primero en Salir o F.I.F.O.

3. Planificación por Turno Rotatorio (Round Robin).

 

Este es uno de los algoritmos más antiguos, sencillos y equitativos en el reparto de la CPU
entre los procesos, muy válido para entornos de tiempo compartido. Cada proceso tiene
asignado un intervalo de tiempo de ejecución, llamado cuantum o cuánto. Si el proceso
agota su cuantum de tiempo, se elige a otro proceso para ocupar la CPU. Si el proceso se
bloquea o termina antes de agotar su cuantum también se alterna el uso de la CPU.
El round robin es muy fácil de implementar. Todo lo que necesita el planificador es
mantener una lista de los procesos listos, como se muestra en la figura 6.2.
En esta figura en a) el proceso P7 ocupa la CPU. En b) P7 se bloquea pasando P2 a ocupar
la CPU. En c) P2 agota su cuantum con lo que pasa al final de la lista y P4 ocupa la CPU.
La figura 4 representa un ejemplo más largo de la ocupación de la CPU utilizando el
algoritmo round robin.

Este algoritmo presupone la existencia de un reloj en el sistema. Un reloj es un dispositivo

que genera periódicamente interrupciones. Esto es muy importante, pues garantiza que el
sistema operativo (en concreto la rutina de servicio de interrupción del reloj) coge el mando
de la CPU periódicamente. El cuantum de un proceso equivale a un número fijo de pulsos o
ciclos de reloj. Al ocurrir una interrupción de reloj que coincide con la agotación
del cuantum se llama al dispatcher.

planificador a corto plazo o dispatcher (despachador). La misión del dispatcher consiste

en asignar la CPU a uno de los procesos ejecutables del sistema, para ello sigue un
determinado algoritmo
 4. Tamaño del Cuanto

  La determinación del tamaño del cuanto es vital para la operación efectiva de un sistema

de cómputo. ¿Debe el cuanto ser pequeño o grande?, ¿fijo o variable?, ¿el mismo para
todos los usuarios o debe determinarse por separado para cada uno?

  Si el cuanto de tiempo es muy grande, cada proceso tendrá el tiempo necesario para
terminar, de manera que el esquema de planificación por turno rotatorio degenera en uno de
primero-en-entrar-primero-en-salir. Si el cuanto es muy pequeño, el gasto extra por
cambio de proceso se convierte en el factor dominante y el rendimiento del sistema se
degradará hasta el punto en que la mayor parte del tiempo se invierte en la conmutación del
procesador, con muy poco o ningún tiempo para ejecutar los programas de los usuarios.

  ¿Exactamente dónde, entre cero e infinito, debe fijarse el tamaño del cuanto? La respuesta
es, lo bastante grande como para que la mayoría de las peticiones interactivas requieran
menos tiempo que la duración del cuanto.

Pongamos un ejemplo, supongamos que el cambio de proceso tarda 5 mseg., y la duración

del cuantum es de 20 mseg. Con estos parámetros, se utiliza un mínimo del 20% del tiempo
de la CPU en la ejecución del sistema operativo. Para incrementar la utilización de la CPU
por parte de los procesos de usuario podríamos establecer un cuantum de 500 mseg., el
tiempo desperdiciado con este parámetro sería del 1%. Pero consideremos lo que ocurriría
si diez usuarios interactivos oprimieran la tecla enter casi al mismo tiempo. Diez procesos
se colocarían en la lista de procesos listos. Si la CPU está inactiva, el primero de los
procesos comenzaría de inmediato, el segundo comenzaría medio segundo después, etc.
Partiendo de la hipótesis de que todos los procesos agoten su cuantum, el último proceso
deberá de esperar 4'5 seg. para poder ejecutarse. Esperar 4'5 seg. para la ejecución de una
orden sencilla como pwd parece excesivo.

En conclusión, un cuantum pequeño disminuye el rendimiento de la CPU, mientras que

un cuantum muy largo empobrece los tiempos de respuesta y degenera en el algoritmo
FIFO. La solución es adoptar un término medio como 100 mseg.

5. Planificación por Prioridad al más corto (SJF, Short Job First).

 

Al igual que en el algoritmo FIFO las ráfagas se ejecutan sin interrupción, por tanto, sólo
es útil para entornos batch. Su característica es que cuando se activa el planificador, éste
elige la ráfaga de menor duración. Es decir, introduce una noción de prioridad entre
ráfagas. Hay que recordar que en los entornos batch se pueden hacer estimaciones del
tiempo de ejecución de los procesos.

  La ventaja que presenta este algoritmo sobre el algoritmo FIFO es que minimiza el tiempo
de finalización promedio, como puede verse en el siguiente ejemplo:

Ej: Supongamos que en un momento dado existen tres ráfagas listas R1, R2 y R3, sus
tiempos de ejecución respectivos son 24, 3 y 3 ms. El proceso al que pertenece la ráfaga R1
es la que lleva más tiempo ejecutable, seguido del proceso al que pertenece R2 y del de R3.
Veamos el tiempo medio de finalización (F) de las ráfagas aplicando FIFO y SJF:

  FIFO F = (24 + 27 + 30) / 3 = 27 ms.

  SJF F = (3 + 6 + 30) / 3 = 13 ms.

Se puede demostrar que este algoritmo es el óptimo. Para ello, consideremos el caso de
cuatro ráfagas, con tiempos de ejecución de a, b, c y d. La primera ráfaga termina en el
tiempo a, la segunda termina en el tiempo a+b, etc. El tiempo promedio de finalización es
(4a+3b+2c+d) /4. Es evidente que a contribuye más al promedio que los demás tiempos,
por lo que debe ser la ráfaga más corta, b la siguiente, y así sucesivamente. El mismo
razonamiento se aplica a un número arbitrario de ráfagas.

No obstante, este algoritmo sólo es óptimo cuando se tienen simultáneamente todas las
ráfagas. Como contraejemplo, considérense cinco ráfagas desde A hasta E, con tiempo se
ejecución de 2, 4, 1, 1 y 1 respectivamente. Sus tiempos de llegada son 0, 0, 3, 3 y 3.
Primero se dispone de A y B, puesto que las demás ráfagas no han llegado aún. Con el
algoritmo SJF las ejecutaríamos en orden A, B, C, D, y E con un tiempo de finalización
promedio de 4.6. Sin embargo, al ejecutarlas en orden B, C, D, E y A se tiene un promedio
de finalización de 4.4.

6. Planificación por Prioridad al Tiempo Restante más Corto (SRTF, Short

Remaining Time First).

Es similar al anterior, con la diferencia de que si un nuevo proceso pasa a listo se activa
el dispatcher para ver si es más corto que lo que queda por ejecutar del proceso en
ejecución. Si es así el proceso en ejecución pasa a listo y su tiempo de estimación se
decremento con el tiempo que ha estado ejecutándose.
En la figura 6.5 tenemos un ejemplo de funcionamiento del algoritmo en el que se observa
cómo se penalizan las ráfagas largas (como en SJF). Un punto débil de este algoritmo se
evidencia cuando una ráfaga muy corta suspende a otra un poco más larga, siendo más
largo la ejecución en este orden al ser preciso un cambio adicional de proceso y la
ejecución del código del planificador.

7. Planificación a la Tasa de Respuesta más Alta

Brinch Hansen desarrolló la estrategia de prioridad a la tasa de respueta más alta (HRN,
highest-response-ratio-next) que corrige algunas deficiencias de SJF, particularmente el
retraso excesivo de trabajos largos y el favoritismo excesivo para los trabajos cortos. HRN
es una disciplina de planificación no apropiativa en la cual la prioridad de cada proceso no
sólo se calcula en función del tiempo de servicio, sino también del tiempo que ha esperado
para ser atendido. Cuando un trabajo obtiene el procesador, se ejecuta hasta terminar. Las
prioridades dinámicas en HRN se calculan de acuerdo con la siguiente expresión:

  prioridad = (tiempo de espera + tiempo de servicio) / tiempo de servicio

Como el tiempo de servicio aparece en el denominador, los procesos cortos tendrán

preferencia. Pero como el tiempo de espera aparece en el numerador, los procesos largos
que han esperado también tendrán un trato favorable. Obsérvese que la suma tiempo de
espera + tiempo de servicio es el tiempo de respuesta del sistema para el proceso si éste se
inicia de inmediato.

8. Planificación por el Comportamiento

Con este tipo de planificación se pretende garantizar al usuario cierta prestación del sistema
y tratar de cumplirla. Si en un sistema tenemos 'n' usuarios lo normal será garantizar a cada
uno de ellos al menos 1/n de la potencia del procesador. Para ello necesitamos del tiempo
consumido por el procesador y el tiempo que lleva el proceso en el sistema. La cantidad de
procesador que tiene derecho a consumir el proceso será el cociente entre el tiempo que
lleva en el sistema entre el número de procesos que hay en el sistema. A esa cantidad se le
puede asociar una prioridad que vendrá dada como el cociente entre tiempo de procesador
que ha consumido y el tiempo que se le prometió (el tiempo que tiene derecho a consumir).
De tal modo que si esa proporción es de 0'5 significa que tan sólo ha consumido la mitad
del tiempo prometido, pero si es de 2 quiere decir que ha consumido más de lo debido,
justamente el doble.

En sistemas de tiempo real se puede adoptar una variante de este algoritmo en el que se
otorgue mayor prioridad al proceso cuyo riesgo de no cumplir el plazo sea mayor.

Planificación apropiativa y no apropiativa.

La planificación no apropiativa (en inglés, no preemptive) es aquélla en la que, cuando a

un proceso le toca su turno de ejecución, ya no puede ser suspendido; es decir, no se le
puede arrebatar el uso de la CPU, hasta que el proceso no lo determina no se podrá ejecutar
otro proceso. Este esquema tiene sus problemas, puesto que si el proceso contiene ciclos
infinitos, el resto de los procesos pueden quedar aplazados indefinidamente. Otro caso
puede ser el de los procesos largos que penalizarían a los cortos si entran en primer lugar.

La planificación apropiativa (en inglés, preemptive) supone que el sistema

operativo puede arrebatar el uso de la CPU a un proceso que esté ejecutándose. En la
planificación apropiativa existe un reloj que lanza interrupciones periódicas en las cuales el
planificador toma el control y se decide si el mismo proceso seguirá ejecutándose o se le da
su turno a otro proceso.

En ambos enfoques de planificación se pueden establecer distintos algoritmos de

planificación de ejecución de procesos. 
 Ventajas y desventajas de los algoritmos de planificación

Algoritmo Características Ventajas Desventajas

No optimiza el tiempo de
Los procesos que llegan
Optimiza la utilización. espera. Rendimiento muy
FCFS primero son los primeros en
Fácil de implementar. variable. No adecuado para
ser ejecutados
sistemas interactivos.

Estimación del tiempo de

Prioridad para el proceso que Asocia cada proceso un
utilización de CPU por parte de
FJS va a necesitar menor tiempo tiempo aproximado de
un proceso (a veces se modela
de la CPU la CPU.
con técnicas estadísticas).

Da prioridad al proceso que Intervalo de CPU difícil de

Optimiza la media del
le resta menos tiempo de predecir. Los trabajos largos no
SRTF tiempo de espera y
CPU para terminar (variante se ejecutarán mediante hayan
rendimiento
del SJF con expulsión). trabajos cortos.

Round Selecciona todos los procesos Equitativo. Fácil de Tiempo medio de retorno alto.
Robin de manera equitativa y en un implementar. Buen
orden racional, comenzando tiempo de respuesta.
por el primer proceso de la
lista hasta llegar al último y
empezando de nuevo desde el
primer elemento.
 Tipo de Planificador Ventajas Desventajas

Puede decidir quitar prioridad a

Apropiativo Usa interrupciones de reloj
un proceso para dársela a otro

Puede terminar o bloquear Una vez que los procesos se integran a la

No Apropiativo
poniendo en espera un proceso CPU no los liberan

Algoritmos no 
Ventajas Desventajas
Apropiativos
Fácil de implementar puede provocar baja productividad;
efecto “convoy”
First Come First Served Es bastante justo, si entendemos que
(FCFS) procesos con menos CPU

tienen menos derecho a usarla.

Es el óptimo para minimizar el Tiene sólo utilidad teórica, ya que
tiempo de paso o de retorno precisa conocer el tiempo que

Algoritmo Shortest Job (Turnaround) con varios procesos Va a usarse la CPU antes de usarla.
First (SJF) listos en llegada simultánea.
Un proceso queda
Se puede usar de modo apropiativos
siempre esperando
o no apropiativo

Algoritmos Ventajas Desventajas

 Apropiativos
Si hay un trabajo nuevo más corto que lo Cada vez que entran trabajos se
Algoritmo Shortest
que le falta al actual en interrumpe el actual y se
Remaining Time First
CPU, echamos el actual y metemos el compara el tiempo restante de éste
(SRTF)
nuevo. con el de los entrantes.
 es fácil de implementar. Es el algoritmo fijar el valor de q es crítico

Algoritmo Round- más justo: todos

Robin (RR) los procesos tienen garantizada su porción

de CPU.
Tenemos una cola por cada nivel de Menor prioridad para procesos
prioridad. Cada cola puede background. Usamos FCFS

tener su propio algoritmo de planificación.

para evitar inanición, se suele calcular

Algoritmo Colas
dinámicamente la
Multinivel
prioridad permitiendo cambio de cola

Si entra un trabajo con mayor prioridad,

desbanca a los de menor