UNIVERSIDAD NACIONAL DE LOJA

ÁREA DE LA ENERGÍA, LAS INDUSTRIAS Y LOS

RECURSOS NATURALES NO RENOVABLES

SISTEMAS OPERATIVOS

DOCENTE:

ING. HERNÁN TORRES

ALUMNO:

EDGAR MANUEL MACAS

TEMA:

ALGORITMOS DE PLANIFICACIÓN

MODULO:

7mo MÓDULO “B”

FECHA:

2011-11-28

LOJA - ECUADOR

ALGORITMOS DE PLANIFICACIÓN

Antes de comenzar a describir los respectivos algoritmos de planificación, es importante conocer

dos conceptos relacionados. Uno de ellos es la función de selección que determina qué proceso,

de entre los listos, se elige para ejecutar a continuación. El otro es el modo de decisión o esquema

de planificación, que especifica los instantes de tiempo en que se aplica la función de selección.

Hay dos categorías generales:

1. Nonpreemptive scheduling (apropiativo) También conocido como cooperative

multitasking. Una vez que el proceso pasa al estado de ejecución, continúa ejecutando

hasta que termina, se bloquean en espera de una E/S o al solicitar algún servicio del

sistema. Esta política de ejecución para terminación fue implementada en los primeros

sistemas de lote (batch).

2. Preemptive scheduling (no apropiativo) Generalmente conocida como política de

planificación por torneo. El proceso que se está ejecutando actualmente puede ser

interrumpido y pasado al estado de listos por el sistema operativo. La decisión de

sustituirlos por otro proceso puede llevarse a cabo cuando llega un nuevo proceso, cuando

se produce una interrupción que lleva a un proceso bloqueado al estado listo o

periódicamente, en función de una interrupción del reloj.

1. Primero en llegar, primero en ser servido (FCFS First come

first served) La lista de procesos en estado listo esta ordenada según el orden de llegada al sistema (creación

del proceso), siendo el más antiguo el que está en la cabecera de dicha lista.

Es una disciplina no apropiativa, por lo tanto al proceso que está activo no se le puede retirar la

CPU hasta que él la abandone voluntariamente.

Inconvenientes:

bajos rendimientos, procesos largos hacen esperar a procesos cortos;

no es útil en sistemas interactivos puesto que no garantiza buenos tiempos de respuesta.

Ventajas:

permite predecir el orden de ejecución de los procesos;

es fácil de implementar.

FCFS, ejemplo:

2. Planificación por Prioridad al más corto (SJF, Short Job First). Es una disciplina no apropiativa. La lista de procesos en estado listo esta ordenada por la cantidad

de tiempo de ejecución estimada, de forma que el proceso más corto es el primero en la cola. Para

establecer este orden se necesita saber el periodo de tiempo de ejecución de un proceso, y como

esto raramente está disponible, se confía en las estimaciones de los usuarios.

Inconvenientes:

con respecto al algoritmo FIFO, es menos predecible los tiempos de respuesta, sobre todo

de los procesos largos;

es poco útil en sistemas interactivos puesto que no garantiza tiempos de respuesta

razonables.

Ventajas:

con respecto al algoritmo FIFO, reduce al mínimo el tiempo promedio de espera de los

trabajos, ya que al favorecer los trabajos cortos sobre los largos reduce el número de

trabajos en espera.

Ej.: Supongamos que en un momento dado existen tres ráfagas listos 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.

3. Planificación del tiempo restante más corto (SRT). Esta disciplina elige siempre al proceso que le queda menos tiempo de ejecución estimado para

completar su ejecución; de esta forma aunque un proceso requiera mucho tiempo de ejecución, a

medida que se va ejecutando iría avanzando en la lista de procesos en estado listo hasta llegar a

ser el primero.

Para realizar esta elección, es necesario actualizar el PCB de los procesos a medida que se le asigna

tiempo de servicio, lo que supone una mayor sobrecarga adicional.

Es una disciplina apropiativa ya que a un proceso activo se le puede retirar la CPU si llega a la lista

de procesos en estado listo otro con un tiempo restante de ejecución estimado menor.

4. HRN (Prioridad a la tasa de respuesta más alta) 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.

5. 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.

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

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 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.

7. 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).

8. Planificación con colas de niveles múltiples. A cada proceso se le asigna una prioridad.

La lista de procesos en estado listo está formada por una serie de colas circulares, donde cada una

de ellas contiene a todos aquellos procesos que tienen una misma prioridad. La CPU se asigna

siempre al proceso de la cola de mayor prioridad que no esté vacía.

Problema: procesos de baja prioridad quedan

postergados indefinidamente.

Solución: prioridad por envejecimiento. La prioridad

aumenta gradualmente a medida que el proceso

pasa cierto tiempo en el sistema, garantizando su

terminación en un tiempo finito.

9. Planificación con colas de retroalimentación de niveles

múltiples. Su objetivo es tratar a los procesos de acuerdo a su comportamiento:

si el proceso se suspende

frecuentemente se le debe asignar bastantes

veces el procesador con un quantum pequeño;

si el proceso se suspende poco se le

debe asignar el procesador menos veces pero

con un quantum grande.

La lista de procesos en estado listo está formada por varios niveles y cada uno de ellos con una

cola circular.

Cuando se inserta un nuevo proceso este se añade al final de la cola de mayor nivel gestionada de

forma FIFO.

BIBLIOGRAFIA

“Algoritmos de Planificación”,

http://wwwdi.ujaen.es/%7Elina/TemasSO/ALGORITMOSDEPLANIFICACION/6Algoritmosde

PlanificacionI.htm, Fecha consulta [27/11/2011].

Ángela Di Serio , “Algoritmos de planificación de la CPU”,

Http://ldc.usb.ve/%7Espd/Docencia/ci-3821/Tema4/node7.html, Fecha consulta

[27/11/2011].

Malw Dark , “Algoritmo de planificación de proceso”,

http://apuntessis.blogspot.com/2007/12/algoritmos-de-planificacin-de-proceso.html,

Fecha consulta [27/11/2011].