lunes, 27 de agosto de 2012

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

    8 comentarios:

    Unknown dijo...

    Felicidades muy buena informacion
    Me quedo claro todo :)

    Unknown dijo...

    Felicidades muy buena informacion
    Me quedo claro todo :)

    maria fernanda dijo...

    Gracias esta muy bien explicado

    richi dijo...

    me ha servido para entender sistema con desalojo, sistema sin desalojo

    richi dijo...
    Este comentario ha sido eliminado por el autor.
    mora dijo...

    Bien bien

    Unknown dijo...

    Buena informacion

    Anónimo dijo...

    Hola de casualidad habra una explicacion sobre el proceso mas corto a continuación? Un tipo de palnificacion parecido a este pero para sistemas interactivos

    Publicar un comentario

     

    Algoritmos de Planificación Copyright © 2010 | Designed by: Compartidisimo