Algoritmo SJF o Trabajo Mas Corto

 

Caracteristicas

-Entra en la CPU el proceso con la ráfaga de CPU más corta.
-Minimiza el tiempo de espera medio.
-Riesgo de inaniciónde los procesos de larga duración.
-No es implementable. Se pueden estimar las duraciones de los procesos, según su historia reciente.
-Versión expulsiva (SRTF):el proceso en CPU es desalojado si llega a la cola un proceso con duración más corta.

Algoritmo SJF

El algoritmo SJF (Shortest-Job-First) se basa en los ciclos de vida de los procesos, los cuales transcurren en dos etapas o periodos que son: ciclos de CPU y ciclos de entrada/salida, también conocidos por ráfagas.
La palabra shortest (el más corto) se refiere al proceso que tenga el el próximo ciclo de CPU mas corto. La idea es escoger entre todos los procesos listos el que tenga su próximo ciclo de CPU más pequeño. El SJF se puede comportar de dos formas:

1. Con Desalojo: Si se incorpora un nuevo proceso a la cola de listos y este tiene un ciclo de CPU menor que el ciclo de CPU del proceso que se está ejecuando,entonces dicho proceso es desalojado y el nuevo proceso toma la CPU.
2. Sin desalojo: Cuando un proceso toma la CPU, ningún otro proceso podrá apropiarse de ella hasta que que el proceso que la posee termine de ejecutarce.

Ejemplo del Algoritmo SJF (Con Desalojo)

Para el siguiente ejemplo se tienen 4 procesos (P1, P2,P3 y P4). A medida que estos se van incorporando a la cola de listos, se les calcula su próximo ciclo de CPU.
Para calcular el próximo ciclo de CPU se pueden emplear: métodos estadísticos, cálculos probabilísticos, entre otros.

• CCPU: próximo ciclo de CPU. 

 

	En el ejemplo se toma como criterio que la cola de procesos listos está inicialmente vacía. En la figura se representa la llegada de P1 a la cola de listos con un tiempo de llegada (0,0). Luego a P1 se le calcula su CCPU (CCPU = 7) y en ese instante se comienza a ejecutar.
	Estando en ejecución el proceso P1, se incorpora a la cola de listos P2, al cual se le calcula su CCPU (CCPU = 4). Pero como el CCPU de P2 es menor que el CCPU de P1, entonces P1 es desalojado y P2 toma la CPU. En este caso P1 se reincorpora a la cola de listos porque no ha terminado su ejecución, y en ese instante se le vuelve a calcular el valor del CCPU (CCPU = 6).
	Luego llega el proceso P3 a la cola de listos y se le calcula el CCPU (CCPU = 1). Por lo que sucede igual que el caso anterior, el CCPU de P3 es menor que el CCPU de P2, por lo que se desaloja P2 para cederle la CPU a P3. P2 es reincorporado a la cola de listos porque no ha terminado su ejecución CCPU y se le vuelve a calcular su CCPU (CCPU = 3). El proceso P4 se incorpora a la cola de listos y se le calcula su CCPU (CCPU = 4). Luego P3 termina su ejecución para cederle la CPU al próximo proceso que le corresponda según el criterio que establece el algoritmo. Para el ejemplo le corresponde el turno a P2, luego a P4 y finalmente a P1.

Ejemplo del Algoritmo SJF (No Apropropiativa)

En esta implementación sucede muy similar a la Apropiativa, pues el SJF si reorganiza la cola por el TE, pero la diferencia es que cuando un proceso obtiene la CPU no lo abandona hasta que no concluye.

¿Algoritmo Óptimo?

El SJF se considera como un algoritmo óptimo, porque da el mínimo tiempo de espera promedio para un conjunto de procesos, así como las estimaciones de CPU. Su dificultad radica en que materialmente es un algoritmo imposible de implementar .

Daniel Andres Buitrago Pacheco

El Menor Tiempo Restante A Continuación

El menor tiempo restante a continuación

Shortest Remaining Time Next SRTN

El planificador selecciona el proceso que tenga el tiempo restante de ejecución mas corto y lo ejecuta. Este algoritmo es de tipo apropiativo, es decir, si un proceso mas corto llega, el proceso que se esta ejecutando actualmente se suspende y el nuevo proceso mas corto se ejecuta.

Es la variedad expropiativa de SJF. Eso significa que el proceso con menor tiempo para acabar es el siguiente proceso en ejecutarse expropiando la CPU inmediatamente al proceso que este en ejecución en el instante correspondiente. El problema vendría en el caso que tengamos un proceso que requiera un tiempo de ejecución para finalizar igual que un proceso nuevo que entra. Existen dos soluciones, dar prioridad a los procesos nuevos sobre los procesos en ejecución o dar prioridad a los procesos en ejecución sobre los procesos nuevos.

Caracteristicas

• Optimiza la media del tiempo de espera y de rendimiento.
•  Da prioridad al proceso que le reste menos tiempo de CPU para terminar.
• Los procesos llegan a la lista de “ready” y solicitan un intervalo con la CPU. Si dicho intervalo es inferior al proceso en ejecución puede ser expulsado.
•   El intervalo de CPU es difícil de predecir.
•  Posibilidad de inanición debido a que los trabajos largos no se ejecutaran mientras hayan trabajos cortos. 

Referencias

http://books.google.com.co/books?id=k5ifRF67clgC&pg=PA39&lpg=PA39&dq=el+menor+tiempo+restante+a+continuacion&source=bl&ots=re1qOK75E3&sig=HpjaU3RRDIEvyY6KsUsZfbYvihM&hl=en#v=onepage&q=el%20menor%20tiempo%20restante%20a%20continuacion&f=false

http://tingsystems.com/2012/03/algoritmo-de-planificacion-srtn-2/

http://asirlasgalletas.blogspot.com/2010/10/algoritmos-de-planificacion.html

Presentado por:

Jhonatan Alexander González Núñez

·       

·        

Planificación por sorteo (lotería)

Planificación por sorteo (lotería)

La idea básica consiste en dar a los procesos boletos de lotería para los diversos recursos del sistema, como el tiempo de CPU: Cada vez que se hace necesario tomar una decisión de planificación, se escoge al azar un boleto de lotería, y el proceso poseedor de este boleto obtiene el recurso.

Características:

[1] Es de carácter aleatorio.

[2] Cada vez que aparezca un proceso nuevo, se le conceden boletos, con lo que ya tendrá una probabilidad de ganar proporcional al número de boletos recibidos.

[3] Este esquema de planificación es de resultados comparativamente rápidos en relación a lo pretendido con las reparticiones de boletos, pues tarda solamente hasta el próximo sorteo.

[4] Se pueden dar más boletos a los procesos más importantes, a fin de aumentar sus posibilidades de ganar.

[5] En procesos cooperativos pueden intercambiar boletos entre sí como en servicios cliente-servidor donde el cliente puede prestarle temporalmente al servidor sus boletos para una mayor posibilidad de ganar tiempos.

[6] En este tipo de planificación, la prioridad queda determinada por la cantidad de boletos asignados a un proceso, que influirán estadísticamente de acuerdo a dicha proporción.

Ejemplo:

Si hay 3 procesos preparados P1, P2 y P3, que cuentan respectivamente con 3, 1 y 5 papeletas, estarán ordenados en la cola como P3, P1 yP2. Cuando hay que elegir un nuevo proceso a planificar, el sistema realiza un sorteo generando un número aleatorio entre 1 y el número total de papeletas repartidas.

Tras el sorteo, encontraremos al ganador si contamos papeletas desde el principio dela cola de preparados. Por ejemplo, si sale ganadora la papeleta séptima, el ganador será el proceso P1.

El proceso ganador tomará control de la CPU hasta que se bloquee voluntariamente o el sistema le expulse porque haya consumido una porción de tiempo prestablecida.  El sorteo se repite siempre que haya que elegir un nuevo proceso a planificar, teniendo en cuenta que, en cada sorteo, el número de procesos preparados puede ser distinto y por tanto, el número total de papeletas a considerar también.

Código:

Referencias:

*  Documento proyecto planificación por lotería, Universidad Nacional de san Antonio Abad,   2008.  http://es.scribd.com/doc/40765110/Documentacion-Planificacion-por-loteria

*  Sistemas Operativos Diseño e Implementación, Andrew S. Tanenbaum, Prentice Hall

*  Documento Sistemas Operativos I,  E. U. de Informática, 10  diciembre 2003.

Diana Camila Sepulveda 

Sistemas de Tiempo Real

SISTEMAS DE TIEMPO REAL

Juan David Duran

Los sistemas de tiempo real se clasifican en general en dos tipos dependiendo de lo serio de sus tiempos límite y de las consecuencias de omitir uno de ellos. Estos son:

Sistema de tiempo real suave.

Sistema de tiempo real duro.

El tiempo real suave significa que no existe problema si se rebasa un tiempo límite. Un sistema de tiempo real duro es aquel en el que un tiempo límite no cumplido puede resultar catastrófico.

SISTEMA DE TIEMPO REAL DURO

(Hard Real Time Systems): Un sistema de tiempo real duro garantiza que un trabajo se completará en un plazo de tiempo especificado. Dicho sistema deberá garantizar que todos los retrasos en el procesamiento, la entrada y salida son limitadas. El sistema no puede esperar indefinidamente por lo que los sistemas de tiempo real duro suelen ser muy limitados. Generalmente no hay almacenamiento secundario, tales como unidades de disco ya que un acceso a disco puede tardar un tiempo variable en el proceso.

Algunos ejemplos de un sistema de tiempo real duro son:

·         El software que ejecuta el piloto automático en un avión jumbo.

·         El software de imágenes en un misil.

·         Una central nuclear.

·         Marcapasos.

Características:

·         Garantiza que las tareas críticas se terminen a tiempo.

·         Requiere que todos los retardos del sistema estén limitados.

·         Tales restricciones de tiempo determinan los recursos que están disponibles en este tipo de sistemas.

·         Para este tipo de sistema el almacenamiento secundario suele ser limitado o ausente.

·         Los datos se almacenan en la memoria de corto plazo o memoria de solo lectura.

·         Son incompatibles con el funcionamiento de los sistemas de tiempo compartido y no pueden combinarse con ellos.

Ejemplo:

·         El sistema ABS (anti-lock breaking system) de un auto.

·         Un marcapasos

·         Alarma sísmica.

SISTEMA DE TIEMPO REAL SUAVE

Es el sistema de tiempo real menos restrictivo.

Es una forma de caracterizar una tarea o sistema de tiempo real en el que se busca que el tiempo medio de respuesta sea menor de un tiempo predefinido.

Los procesos críticos tienen mayor prioridad que los demás, y conserva esa prioridad hasta que se lleva a cabo. Esto podría dar pie a una asignación de recursos no equitativa. Este sistema puede apoyar multimedia y gráficos de alta velocidad, que no serían posibles en otro sistema.

La implementación debe ser cuidadosa con el planificador, y debe ser por prioridad, asignando la más alta a los procesos críticos, la cual no se puede degradar. La latencia del despacho debe ser pequeña.

Características:

·         Puede combinarse con otros sistemas.

·         Utilidad mas limitada que los duros.

·         Es riesgoso utilizarlos en control industrial y robótica.

Ejemplo:

·         Procesamiento de video (Porque es aceptable que se pierda algún que otro cuadro).

·      Un reproductor de DVD – Interfaces al usuario en general Sistema de tiempo real duro.

·      Conmutador telefónico

WEBGRAFIA:

http://es.scribd.com/doc/91306464/90/Planificacion-en-tiempo-real

http://es.wikipedia.org/wiki/Tiempo_real_duro

http://www.slideshare.net/AreliDA/sistemas-en-tiempo-real

http://www.monografias.com/trabajos37/sistemas-tiempo-real/sistemas-tiempo-real2.shtml

Planificación por reparto equitativo

Planificación por reparto equitativo

Se usa en los sistemas multiusuario.
Cada usuario tiene asignado algún tipo de ponderación, que indica la parte de los recursos del sistema para el usuario como una fracción de la utilización total de dichos recursos. En particular, cada usuario dispone de una parte del procesador. Este esquema debe funcionar de una forma más o menos lineal, por lo que si un usuario A tiene un peso dos veces mayor que el de un usuario B, entonces, a la larga, el usuario A debe poder hacer el doble de trabajo que B. El objetivo de un planificador por reparto equitativo es supervisar el uso, de forma que se asignen menos recursos a los usuarios que han consumido más de lo que les corresponde y más recursos a los que han consumido menos de lo que le corresponde.

En un sistema multiusuario, si las aplicaciones o los trabajos de los usuarios pueden organizarse en forma de varios procesos (o hilos), se dispone de una estructura para el conjunto de procesos que no se identifica con ningún planificador tradicional. Desde el punto de vista del usuario, el interés no está en cómo se comporta un proceso en particular, sino en cómo se comporta el conjunto de procesos de usuario que constituyen una aplicación. Así pues, sería interesante poder tomar decisiones de planificación en función de estos grupos de procesos. Este enfoque se conoce generalmente como planificación por reparto equitativo.

La planificación se lleva a cabo por prioridades, teniendo en cuenta la prioridad básica del proceso, su utilización reciente de la CPU y la utilización reciente de la CPU por parte del grupo al que pertenece. Cuanto mayor es el valor numérico de la prioridad, menor es ésta. Las fórmulas siguientes se aplican al proceso j del grupo k.

CPUj(i) = CPUj(i - 1) / 2

GCPUk(i) = GCPUk(i - 1) / 2

Pj(i) = Basej + CPUj(i - 1) / 2 + GCPUk(i - 1) / (4 x Wk)

Donde:

CPUj(i) = Media ponderada de la utilización de la CPU del proceso j en el intervalo i.

GCPUk(i) = Media ponderada de la utilización de la CPU del grupo k en el intervalo i.

Pj(i) = Prioridad del proceso j al principio del intervalo i; los valores más bajos indican prioridades más altas.

Basej = Prioridad de base del proceso j.

Wk = Peso asignado al grupo k, con la restricción de 0 <= Wk <= 1 y S Wk = 1.

Cada proceso tiene asignada una prioridad de base. Esta prioridad desciende a medida que el proceso y el grupo al que pertenece utilizan la CPU. En el caso de la utilización del grupo, la media se normaliza dividiendo por el peso del grupo. Cuanto mayor es el peso asignado al grupo, menos afecta su utilización a la prioridad.

Implementación de acciones:

Cada segundo t1: programación a nivel de usuario

para cada usuario

Cada uso y actualización de los costos incurridos en los últimos segundos t1

Usado por usuario = usageuser × K1 + chargesuser

Restablecer recuento del costo

chargesuser = 0

Cada segundo T2: decaimiento de las prioridades del proceso

para cada proceso

priorityprocess priorityprocess = K2 × × (niceprocess + K3)

Cada segundo t3: ajuste de prioridad

prioritycurrent_process = prioritycurrent_process +

usagecurrent_user × active_processescurrent_user acciones 2

current_user

En cada evento de programación: el proceso de selección actual

chargescurrent_user = costo + chargescurrent_user + costo  del evento

ejecutar el proceso con prioridad más baja

Prioridad de normalización:

max_priorida = 0

for each process

if

max_priorida < priorityprocess ≤ priority_bound

then

max_priorida= priorityprocess

for each process

Scale priority to appropriate range

if

priorityprocess ≤ max_priorida

then

normalised_priorityprocess = (K4 − 1) ×

priorityprocess

max_priorida

else

normalised_priorityprocess = K4

Ajustando grupos:

for each group (descend hierarchy)

if

actual_machine_proportiongroup <  K6 ×  machine_proportion_duegroup

entonces

for each user in the group (descend hierarchy)

chargesuser = chargesuser  × actual_machine_proportiongroup K6 × machine_proportion_duegroup

Web Grafía  :

http://www.cs.cornell.edu/courses/cs614/2003sp/papers/KL89.pdf

http://www.monografias.com/trabajos16/procesadores/procesadores.shtml

Primero En Entrar Primero En Ser Atendido.

Cristhian Amezquita Castro

First-Come, First Served (FCFS)

Primero en entrar primero en ser atendido.

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 o interrupción E/S.

• Tiende a favorecer aquellos procesos que requieren más tiempo de CPU (CPU-bound). 
• Puede ocasionar un uso indeficiente tanto del procesador como de los dispositivos de E/S.
• „ Es el algoritmo más sencillo, el primer proceso que solicita la CPU es el primero en recibirla.
• „ Fácil de implementar con una política FIFO para la cola de preparados.
• „ Tiempo de espera promedio bastante largo.

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.

En el siguiente enlace podrá simular el funcionamiento de este algoritmo

ALGORITMO FCFS SIMULACION

Cibergrafia:

http://www.infor.uva.es/~fjgonzalez/apuntes/Tema5.pdf

http://wwwdi.ujaen.es/~lina/TemasSO/PLANIFICACIONDEPROCESOS/PlanificadorProcesos/alg_planif_FIFO.html

http://ldc.usb.ve/~spd/Docencia/ci-3821/Tema4/node8.html