martes, 27 de septiembre de 2016

Semáforos binario y multi variable


Vamos a intentar explicar un poco el uso de semáforos para ciertas acciones , lo mas simple posible , para esto tomaremos un caso de la vida diaria que es el esperar en una cola para entrar a un baño.

Primeramente el concepto de semáforo se puede apreciar como :

"Un semáforo es una variable entera  que se incluye , para realizar con este un método de  restringir o permitir el acceso a recursos compartidos ."

Con esto veamos el caso que se ah planteado , el de entrar a un baño.Imaginemos un baño con el numero de baños es variable , donde cada baño tiene una llave que se le da al usuario que lo vaya a usar .

En un primer caso podemos ver en el que solo existe un baño y su única llave para usarlo , en este caso todas las personas que lleguen van a tener que esperar al primer usuario que llego y que este termine su uso mientras los demás están en espera .Ya que el estado de este único baño puede ser en uso o no , se puede referir a un semáforo binario que tiene valores 0-1 comenzando su valor en 1 (como `primer uso en nuestro ejemplo) y tomando el valor 0 cuando el usuario sale .


                                                                              Figura 1 : En espera

Si en cambio nuestro baño tuviera un nuevo de baños con su respectivo nuevo de llaves , entonces el numero de llaves disponibles seria nuestro semáforo , distribuyendo así los usuarios en cada baño y generando así que cada uno se realice sin interrupción (ya que la llave es única en nuestro caso) , en este sentido el semáforo puede tomar varios valores dependiendo el caso.

                                                           Figura 2: Mayor numero de baños 

Como algo adicional se puede decir de los mutexs que es una variable de exclusión mutua , que en nuestro caso se puede apreciar como la llave de cada baño , que sin ella no se puede acceder a este .

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 .