miércoles, 14 de septiembre de 2016

Algoritmos de planificación

Tomando en cuenta el problema de planificación de procesos planteado en el libro  Sistemas Operativos de Tanenbaum ,  resolviendo este veremos como es el trabajo de 4 algoritmos de planificacion.

El problema es el siguiente :

"Cinco trabajos de procesamiento por lotes, A a E, llegan a un centro de cómputo casi al mismo tiempo. Tienen tiempos de ejecución estimados de 10, 6, 2, 4 y 8 minutos. Sus prioridades (determinadas en forma externa) son 3, 5, 2, 1 y 4, respectivamente, en donde 5 es la prioridad más alta. Para cada uno de los siguientes algoritmos de planificación, determine el tiempo de respuesta de proceso promedio. Ignore la sobrecarga por conmutación de procesos.

a) Por turno circular. 

b) Por prioridad.
c) Primero en entrar, primero en ser atendido (ejecutados en el orden 10, 6, 2, 4, 8).
d) El trabajo más corto primero.
Para (a), suponga que el sistema es multiprogramado y que cada trabajo recibe su parte equitativa de la CPU. Para los incisos del (b) al (d), suponga que sólo se ejecuta un trabajo a la vez hasta que termina. Todos los trabajos están completamente ligados a la CPU."

a) 

Round Robin (Turno circular)


Uno de los algoritmos más antiguos, simples, equitativos y de mayor uso es el de turno circular (round-robin). A cada proceso se le asigna un intervalo de tiempo, conocido como quantum, durante el cual se le permite ejecutarse. Si el proceso se sigue ejecutando al final del cuanto, la CPU es apropiada para dársela a otro proceso. Si el proceso se bloquea o termina antes de que haya transcurrido el quantum la CPU pasa al siguiente proceso en la lista .

 En el problema podemos elegir un quantum como el de 4min , es decir cada 4 min el CPU ira turnando los procesos hasta terminarlos.

 En  la siguiente imagen se hace la simulación de como se ejecutaría este algoritmo turnado los procesos , considerando que cada cuadrado es 1 min , se puede apreciar fácilmente los tiempos de espera para cada proceso:

                        Proceso A    20
                        Proceso B    18
                        Proceso C    4
                        Proceso D    10
                        Proceso E    20                                  Tiempo promedio : 14.4 min




b)

Por Prioridades


    La idea básica es simple: a cada proceso se le asigna una prioridad y el proceso ejecutable con la prioridad más alta es el que se puede ejecutar.
Incluso hasta en una PC con un solo propietario puede haber varios procesos, algunos de ellos más importantes que los demás. Por ejemplo, un proceso demonio que envía correo electrónico en segundo plano debería recibir una menor prioridad que un proceso que muestra una película de video en la pantalla en tiempo real. Para evitar que los procesos con alta prioridad se ejecuten de manera indefinida, el planificador puede reducir la prioridad del proceso actual en ejecución en cada pulso del reloj (es decir, en cada interrupción del reloj). Si esta acción hace que su prioridad se reduzca a un valor menor que la del proceso con la siguiente prioridad más alta, ocurre una conmutación de procesos.

En el problema no se tomara en cuenta la interrupción del reloj.


Se puede apreciar que la ejecucion es muy diferente a la anterior , dadas las prioridades tomadas del problema.

Calculando el tiempo de espera promedio:


                        Proceso A    14
                        Proceso B    0
                        Proceso C    24
                        Proceso D    26
                        Proceso E    6                                  Tiempo promedio : 14 min



c)

Shortest  Job First


Como dice su nombre el trabajo mas corto se realizara primero , es por lo general el que tiene tiempo de respuesta promedio mínimo para sistemas de procesamiento en lotes , pero no es muy aplicable en otros sistemas ya que no se sabe el tiempo del proceso mas corto , teniendo que hace un trabajo extra para saber esto.


Su tiempo de espera:

                        Proceso A    20
                        Proceso B    6
                        Proceso C    0
                        Proceso D    2
                        Proceso E    12                                  Tiempo promedio : 8 min


d)

Firts-Come, First-Served


 No hay mucho que explicar , los procesos como van llegando se van a ir ejecutando mientras los que lleguen mientras alguno este ejecutándose van a una cola de espera .


Este método es usado comúnmente por su simplicidad , a pesar de no ser tan eficiente como veremos :


                        Proceso A    0
                        Proceso B    10
                        Proceso C    16
                        Proceso D    18
                        Proceso E     22                                Tiempo promedio : 13.2 min
Conclusión:
Teniendo en cuenta los tiempos promedios de respuesta 14.4 ,14, 8 ,13.2 min el como se esperaba mas corto fue el de primero en entrar primero en ser ejecutado , pero como ya se a dicho este no es tan eficiente en sistemas que no se sabe el costo de cada promedio . Los  algoritmos que dan prioridades hacen un mejor uso de recursos y de procesamiento en segundo plano asi que para cada tipo de sistema podemos hacer uso de estos dependiendo con que recursos tenemos .




No hay comentarios:

Publicar un comentario