Comunicación y Sincronizacion

1 Tarea #1

“Comunicación y Sincronización entre Procesos”

1. Enumere cuatro elementos de diseño para los cuales es necesario el concepto de concurrencia. La concurrencia comprende un gran número de cuestiones de diseño, las cuales incluye: la comunicación entre los procesos, compartición y competencia por los recursos, sincronización de la ejecución de varios procesos y asignación del tiempo de procesador de los procesos. 2. En qué tres contextos se presenta la concurrencia? La concurrencia puede presentarse en tres contextos diferentes: •

Múltiples Aplicaciones: la multiprogramación se creó para permitir que el tiempo de procesador de la máquina fuese compartido dinámicamente entre varias aplicaciones activas.

•

Aplicaciones Estructuradas: como ampliación de los principios del diseño modular y la programación estructurada, algunas aplicaciones pueden implementarse eficazmente como un conjunto de procesos concurrentes.

•

Estructura del Sistema Operativo: las mismas ventajas de estructuración son aplicables a los programadores de sistemas y se ha comprobado que algunos sistemas operativos están implementados como un conjunto de procesos o hilos.

3. Cuáles son los requisitos básicos para la ejecución de procesos concurrentes? Para que haya ejecución de procesos concurrentes tiene que existir la intercalación y superposición entre procesos. 4. Enumere tres niveles de conocimientos entre procesos y defina brevemente cada uno de ellos.

Edgar A. Mendieta

Comunicación y Sincronizacion

2

Existen tres niveles de conocimiento: •

Los procesos no tienen conocimiento de los demás. Estos son procesos independientes que no están pensados para operar juntos. El mejor ejemplo de esta situación es la de multiprogramación de varios procesos independientes. Estos pueden ser tanto trabajos por lotes como sesiones interactivas o una combinación de ambos. Aunque los procesos no trabajen juntos, el sistema operativo tiene que encargarse de la competencia

por

los

recursos.

independientes pueden querer

Por

ejemplo,

dos

aplicaciones

acceder al mismo disco, archivo o

impresora. El sistema operativo debe regular estos accesos. •

Los procesos tienen un conocimiento indirecto de los otros: los procesos no conocen necesariamente a los otros por sus identificadores de proceso, pero comparten el acceso a algunos objetos, como un buffer de E/S. Estos procesos muestran cooperación para compartir el objeto común.

•

Los procesos tienen un conocimiento directo de los otros: los procesos son capaces de comunicarse con los demás por el identificador de proceso y están diseñados para trabajar conjuntamente en alguna actividad. Estos procesos también muestran cooperación.

5. Cuál es la diferencia entre proceso en competencia y procesos en cooperación? Los procesos en competencia son aquellos que compiten por el uso del mismo recurso; dos o más procesos necesitan acceder a un recurso durante el curso de su ejecución; ningún proceso es consciente de la existencia de los otros. En el caso de la cooperación entre procesos son aquellos que interactúan con otros sin tener conocimientos explícitos de ellos. 6. Enumere los tres problemas asociados a la competencia entre procesos y defina brevemente cada uno de ellos. Cuando existe la competencia entre los procesos se puede dar varios problemas:

Edgar A. Mendieta

Comunicación y Sincronizacion •

3

Exclusión Mutua. Condición por la cual un conjunto de procesos, solo uno puede acceder a un recurso dado o realizar una función dada en un instante de tiempo.

•

Interbloqueo. Este problema lo tenemos cuando dos procesos tienen que hacer uso del mismo recurso y uno se encuentra en espera de que el recurso sea liberado por el proceso que lo esta utilizando. A su vez el otro proceso necesita de un recurso que esta siendo utilizado por el proceso en espera.

•

Inanición. Este problema se debe a la espera indefinida de un proceso causado por la asignación de preferencias de ejecución a otro proceso.

7. Requisitos para la ejecución mutua. La exclusión mutua debe cumplir con los siguientes requisitos; •

Debe cumplirse la exclusión mutua: solo un proceso de entre todos los que poseen secciones críticas por el mismo recurso u objeto compartido, debe tener permiso para entrar en ella en un instante de tiempo.

•

Un proceso que se interrumpe en una sección crítica debe hacerlo sin interferir con los otros procesos.

•

Un proceso no debe poder solicitar acceso a una sección crítica para después ser demorado indefinidamente; no puede permitirse el interbloqueo o la inanición.

•

Cuando ningún proceso está en su sección crítica, cualquier proceso que solicite entrar en la suya debe poder hacerlo sin dilación.

•

No se deben hacer suposiciones sobre la velocidad relativa de los procesos o el número de procesadores.

•

Un proceso permanece en su sección crítica solo por un tiempo finito.

8. Que operaciones se pueden efectuar sobre un semáforo? •

Un semáforo puede iniciarse con un valor no negativo.

•

La operación wait disminuye el valor del semáforo. Si el valor se hace negativo, el proceso que ejecuta el wait se bloquea.

Edgar A. Mendieta

Comunicación y Sincronizacion •

4

La operación signal incrementa el valor del semáforo. Si el valor no es positivo, se desbloquea un proceso bloqueado por una operación wait.

9. Cuál es la diferencia entre los semáforos Generales y los Binarios? Los semáforos binarios solo puede tomar los valores de 0 y 1; siendo mas sencillo de implementar que los generales, ya que son mas limitados. Pero manejan la misma potencia que estos últimos. 10. Cuál es la diferencia entre los semáforos débiles y los robustos. Los semáforos robustos tienen un orden definido para retirar los procesos que se encuentra en cola de espera. Mientras que los semáforos débiles no especifican el orden para llevar a cabo esta labor. 11. Que es un monitor? Los monitores son estructuras de un lenguaje de programación que ofrecen una funcionalidad equivalente a la de los semáforos y que son más fáciles de controlar. 12. Cuál es la diferencia entre bloqueador y no bloqueador con relación a los mensajes? La diferencia que existe entre uno y el otro es que cuando se envía un mensaje el proceso emisor o receptor puede estar o no bloqueados. Si el mensaje es bloqueador el proceso quedara bloqueado hasta que llegue el próximo mensaje. Pero si es no bloqueador, usado mucho en procesos concurrentes, el proceso continuara su ejecución normalmente tenga o no tenga mensajes. 13. Cuales son las condiciones asociadas, en general, con el problema de los lectores/escritores? Se deben satisfacer las siguientes condiciones: •

Cualquier número de lectores puede leer el archivo simultáneamente.

•

Sólo puede escribir en el archivo un escritor en cada instante.

•

Si un escritor está accediendo al archivo, ningún lector puede leerlo.

Edgar A. Mendieta

Comunicación y Sincronizacion

5 Problemas.

1. Considérese el algoritmo de Dekker, escrito para un número de arbitrario de procesos, cambiando la sentencia ejecutada cuando se abandona la sección crítica de turno = 1 – i

/* es decir, P0 pone turno a 1 y P1 pone turno a 0 */

a turno = ( turno + 1 ) % n

/* n= números de procesos */

Evaluar el algoritmo cuando el número de procesos que ejecutan concurrentemente es mayor de dos. Si tenemos varios procesos concurrente con un algoritmo de esta forma se estará viendo solamente que la sección critica estará libre cuando el residuo de la división del total de los procesos sea un numero exactamente divisible entre la cantidad n de procesos. 2. Otro método de software para la exclusión mutua es el algoritmo de la panadería de Lamport, llamado así porque está basado en la costumbre de las panaderías y de otras tiendas en las que cada cliente recibe un número al llegar, lo que permite servirles por turnos. El algoritmo es como sigue: booleano eleccion[n]; int numero[n]; while (cierto) { eleccion[i] = cierto; numero[i] = 1 + max(numero[ ], n); eleccion[i] = falso; for (int j=0; jn; j++) { while (eleccion[j]) { };

Edgar A. Mendieta

Comunicación y Sincronizacion

6

while ((numero[j] !=0) && (numero[j], j) (numero[i], i)) { }; /* seccion critica */; numero[i] = 0; /* resto */; } } Los vectores eleccion y numero se inicia a falso y a 0, respectivamente. El iesimo elemento de cada vector puede ser leído y modificado por el proceso i, pero solo puede ser leído por otros procesos. La notación (a, b) < (c, d) se define como: (a dormir(int(random(1000*tiempo_paseo))) P(coche_vacio); V(tomar_coche); P(coche_lleno) P(pasaj_libre) od end pasajero process coche(j:=1 to num_coches) do true -> V(coche_libre); P(tomar_coche); V(coche_lleno) dormir(int (random(1000*tiempo_recorrido)) V(pasaj_libre) od end coche end Parque_Jurasico \end{literalmente} Según mi punto de vista la lógica tiene sentido, en lo que se ve se usan tres semáforos y un contador de procesos (pasajeros). Los semáforos serán coche_vacio, tomar_coche, coche_lleno. Estos semáforos le envían la señal de wait o signal a los procesos (pasajeros) para que se ejecuten (tomen el bus). La codificación utilizada es un poco enredada pero se tiene la lógica, la política utilizada para definir los semáforos es bastante buena. 5. Considérese el algoritmo de semáforos. ¿Cambiara el significado del programa si se intercambian las siguientes sentencias? •

Wait(e); wait(s)

•

Signal(s); signal(n)

•

Wait(n); wait(s)

•

Signal(s); signal(e)

Edgar A. Mendieta

Comunicación y Sincronizacion

9

Si nos basamos en el algoritmo del Productor-Consumidor del libro de Stalling (figura 5.16), podemos ver que las funciones declaradas se ejecutan mediante caída libre; al momento de hacer dichos cambios estaremos cambiando el significado del programa. Si tomamos la función productor y cambiamos wait(e) por wait(s) el wait del tamaño de buffer estará en 1 siempre y si el tamaño requerido por el proceso es mayor puede generar errores. Al ir bajando en la ejecución del programa vemos que a la hora de enviar una señal para la inserción de otro proceso en el buffer se vera siempre en 0, o sea no habrá una señal de que se ha insertado un proceso. Analizando el algoritmo para la parte del consumidor el primer wait entrará en 1, en primera instancia el programa puede tomarlo como si ya el consumidor ha tomado ya el proceso. 6. Responda a las siguientes cuestiones relativas a la barbería equitativa: •

Requiere el código que cobre el pago de un corte de pelo a un cliente el mismo barbero que lo terminó?

Si se coloca en el código que el mismo barbero sea el que cobre el corte, el proceso (cliente) se demorara más tiempo con el barbero y dejara a los otros procesos esperando más tiempo. Esto puede llevar a una gran espera y retrazar todo el funcionamiento. •

Usan los barberos siempre la misma silla?

La misma silla será utilizada, ya que existe una relación entre el barbero y la silla; al momento que se liberó la silla, será liberado el barbero el cual estará dispuesto para atender otro cliente. 7. Este problema demuestra el modo en que se usan tres semáforos para coordinar tres tipos de procesos. Santa Claus duerme en su taller del Polo Norte y sólo puede despertarse por (1) los nueve renos que vuelven de sus vacaciones en el Pacifico Sur o (2) algún duende que tiene dificultades para hacer juguetes; para permitir que Santa Claus duerme, los duendes sólo pueden despertarle cuando son tres los que tienen problemas. Cuando tres

Edgar A. Mendieta

Comunicación y Sincronizacion

10

duendes van a plantear sus problemas, cualquier otro que desee visitar a Santa Claus debe esperar a que vuelvan. Si Santa Claus despierta y encuentra y encuentra tres duendes en la puerta de su taller, junto con el último reno que vuelve al trópico, Santa Claus decide que los duendes pueden esperar hasta después de Navidad, porque es mas importante poner su trineo a punto (se supone que los renos no quieren dejar trópico y que permanecen allí hasta el ultimo momento posible). El último reno en llegar debe avisar a Santa Claus mientras los otros esperan calentitos en un refugio antes de ser enjaezados al trineo. Resuelva este problema por método de semáforos. semáforo re = 0 semáforo en = 0 semáforo enj = 1 semáforo noenj = 1 semáforo en-cuar = 1 semáforo salir = 1 /* Enanos */ while (true) { hacer(); en-espera(); wait(en-cuar); consul(); wait(salir); } void en-espera() { if (e3) then { wait(en) en=en + 1 else en-listo(); } /* Renos */ while (true) { navidad(); re-regre(); wait(enj); entregar(); wait(noenj); } void re-regre(){ if (r==8) { wait(enj); else

Edgar A. Mendieta

Comunicación y Sincronizacion

11

re = re + 1; } /* Santa Claus */ while (true) { despertado(); } void despertado() { wait(enj) entregar() wait(noenj); } void despertado() & en-listo() { wait(en-cuar); consulta() wait(salir) }

8. Demostrar que el paso de mensajes y los semáforos tienen una funcionalidad equivalente: a. implementando el paso de mensajes por medio de semáforos. Pista: haga uso de un área de elementos compartidos para contener buzones, cada uno de ellos formado por un vector de espacios para mensajes. /* productor – consumidor */ cap = prod = 1 cons = 1 void productor () { while (cierto) producir() wait(e) wait(prod) signal(prod) mens() } } void consumidor () {

Edgar A. Mendieta

Comunicación y Sincronizacion

12

while (cierto) { coger () wait(cons) signal(cons) mens() } } void mens() { msg[prod] = prod + 1 msg[cons] = cons + 1 }

b. implementando un semáforo por medio del paso de mensajes. Pista: cree un proceso independiente para la sincronización. void productor () { while (cierto) { receive(producir, msjp) msj. = producir( ) send(consumir, msjp) } } void consumidor () { while (cierto) { receive(consumir, msjp) consumir(mjsp) send(producir, null)

Edgar A. Mendieta

Comunicación y Sincronizacion } } void mens() { buzon1(producir) buzon2(consumir) producir = producir + 1 consumir = consumir + 1 }

Edgar A. Mendieta

13