sisoputnfrba / foro

Foro de consultas para el trabajo práctico
151 stars 7 forks source link

Duda sobre el algoritmo de detección #1081

Closed ltrinidad closed 6 years ago

ltrinidad commented 6 years ago

Buenas! Tenemos la siguiente duda:

Entendemos que el algoritmo del banquero para la detección de deadlock necesita conocer todos los recursos que el esi pueda llegar a pedir (en este caso todas las claves) a lo largo de su ejecución. La única forma que tenemos de saber esto es analizar previa ejecución del esi todo el script buscando los GETs y sus claves. ¿Esto es lo que quieren que hagamos, o hay una forma mas adecuada? porque hasta ahora se nos ocurrió como filtrar a los esis y recursos que pudieran estar bloqueados en algún deadlock, pero sin saber el conjunto de recursos que se pueden llegar a pedir no podemos aplicar el algoritmo porque nos falta una matriz, ¿el algoritmo del banquero seria la única opción?

iago64 commented 6 years ago

Buenas buenas!

Efectivamente, el algoritmo del banquero lo que te permite es encontrar la secuencia de ejecución que te permite terminar todo y eventualmente lo usas para suspender procesos.

En el TP la idea es que implementen solo al detección, con lo cual, que condiciones necesitas para tener deadlock?

1.- No expropiación (las claves por el enunciado no se desalojan, al menos no por si solas) 2.- Exclusión Mutua (las claves las toma solo un ESI) 3.- Espera circular, este es el punto que tienen que enfocarse uds, ya que van a tener que ver de alguna forma si tienen al ESI 1 tomando la clave A y bloqueada para B y el ESI 2 tomando la clave B y bloqueado para la clave A.

Tenemos la 4 que es retención y espera pero ya te tiro el spoiler de que muy posiblemente tengamos algún script que primero haga 2 o 3 GET y despues intente hacer otras cosas para las pruebas.

ltrinidad commented 6 years ago

¿O sea que no hay que implementar el algoritmo de detección propiamente dicho como lo vimos en la teoría, sino que hay que buscar una forma de encontrar todas las esperas circulares en el sistema, basándonos en las colas de esis bloqueados y en las asignaciones actuales que se produjeron en el sistema (quiero decir, la lista que contiene : "ESI0 tomó las claves 'pepe' y 'luis' , ESI1 tomó la clave 'juan',... etc") ?

iago64 commented 6 years ago

Buenas buenas!

Lo que uds necesitan implementar es la detección de interbloqueos (que si no me fallan los apuntes está explicado en el capítulo 7 del Silberchatz) y no algoritmos para determinar estados seguros (como por ej el banquero)

Tene en cuenta que al momento de detectar interbloqueos por ej vas a dejar de lado a los ESI que no tengan recursos asignados y después van a terminar armando (de alguna manera programática) los grafos de asignaciones y pedidos para después buscar los ciclos donde se les están generando los deadlocks

Saludos.-

iago64 commented 6 years ago

@ltrinidad Que tal? Quedo resuelta tu duda? podemos cerrar el issue?

ltrinidad commented 6 years ago

Buenas @iago64 ! Si, concluimos entonces que hay que ver, con alguna magia a manopla, cómo amar el grafo de asignaciones y con eso buscar las esperas circulares. Si es así, entonces ya estaría resuelta la duda. Muchas gracias!!

iago64 commented 6 years ago

Si, efectivamente tienen que hacer la magia a manopla para armar los grafos.

varas-c commented 6 years ago

@ltrinidad pudiste resolver tu duda? Caso afirmativo, no te olvides de cerrar el issue. Caso contrario, no te quedes con las dudas!