Detección de interbloqueos en el uso de mutex

Práctica de carácter optativo. El desarrollo satisfactorio de la misma puede proporcionar un punto más en la nota total. Sólo se podrá realizar esta práctica una vez que se ha completado satisfactoriamente la práctica obligatoria. La funcionalidad que se plantea en esta práctica se puede incluir en la versión obligatoria de la práctica o, si ya se ha desarrollado otra práctica optativa, puede juntarse con esta, aunque no obligatoriamente. Idealmente, un grupo de prácticas podría desarrollar una única versión de la práctica que incluyera toda la funcionalidad planteada en los distintos enunciados.

Descripción de la funcionalidad pedida

El objetivo principal es intentar llevar a la práctica uno de los temas que tradicionalmente se han considerado como más teóricos dentro de los sistemas operativos: los interbloqueos. En ella se pretende implementar un algoritmo de detección de interbloqueos para los mutex desarrollados en la práctica obligatoria. En los mutex implementados en dicha práctica no se controlaba la posibilidad de que se produjese un interbloqueo, con la excepción del caso trivial de un proceso bloqueándose a sí mismo.

Como se estudia en la teoría de la asignatura, los algoritmos de detección de interbloqueo se basan en mantener un grafo de asignación de recursos que refleje qué recursos tiene asignado cada proceso y cuáles tiene pedidos pero no se le han concedido porque están asignados a otro proceso. Si se detecta un ciclo en el grafo, implica que hay un interbloqueo y que, por tanto, hay que aplicar un algoritmo de recuperación de ese estado. En el caso específico de los mutex, el grafo reflejaría, por cada mutex, qué proceso lo tiene bloqueado, si alguno lo tiene, y, por cada proceso, en qué mutex está esperando, en caso de que lo esté. A priori, puede parecer que es necesario empezar a definir nuevas estructuras de datos que implementen este grafo. La buena noticia es que va a ser suficiente con las estructuras ya existentes, puesto que éstas ya reflejan estas relaciones entre los procesos y los mutex. Por lo que se refiere al algoritmo de detección, se ejecutará cada vez que un proceso realiza una llamada “lock” y se encuentra que el mutex está bloqueado por otro proceso. El alumno deberá diseñar el algoritmo siguiendo las pautas establecidas en la teoría de la asignatura.

Con respecto a la estrategia de recuperación que se aplicará una vez detectado el interbloqueo, se plantean dos alternativas que dan lugar a dos versiones de la práctica:

  • Una menos drástica, que consiste simplemente en devolver un valor de error en la primitiva “lock” correspondiente. Nótese que, en este caso, el resto de los procesos implicados en el interbloqueo no van a poder continuar hasta que este proceso desbloquee alguno de los mutex. Supóngase el siguiente ejemplo:
      **Proceso P1**            **Proceso P2**		
      lock(M1)                  lock(M2)
      lock(M2)                  lock(M1)
      ..........                ..........
      unlock(M2)                unlock(M1)
      unlock(M1)                unlock(M2)

    Considérese la siguiente situación:

    • P1 bloquea M1
    • P2 bloquea M2
    • P1 intenta bloquear M2 pero, como lo tiene otro proceso, se aplica el algoritmo de detección que comprueba que no hay ningún ciclo.
    • P2 intenta bloquear M1 pero, como lo tiene otro proceso, se aplica el algoritmo de detección que encuentra un ciclo. Se devuelve un error en esa llamada “lock”. Nótese que, de todas formas, P1 seguirá esperando hasta que P2 desbloquee el mutex M2. En el peor de los casos, eso ocurrirá cuando termine P2, aunque lo más lógico es que el programador controle si la llamada “lock” devuelve un error y, si es así, termine el proceso.
      . . . . . . . . . . . . 
      if (lock(M1)<0) {
          printf("Error bloqueando M1\n");
          terminar_proceso();
      }
      . . . . . . . . . . . . 
  • Una más agresiva, en la que se va a “matar” directamente al proceso que ha invocado la llamada “lock”. Con esta estrategia se liberan inmediatamente los mutex que tenía bloqueados el proceso, quedando disponibles para el resto de los procesos. Así, en el ejemplo, se abortaría la ejecución de P2, y P1 pasaría inmediatamente al estado de listo para ejecutar.

El uso de una u otra estrategia se seleccionará mediante la macro “ABORTAR”. Si está definida (incluida en el archivo “const.h”), se usará la estrategia de abortar el proceso. En caso contrario, sólo se devolverá un error en la llamada.

Si se pretende incluir esta funcionalidad sobre una versión con threads, evidentemente, toda la estrategia de detección planteada se aplicará en el nivel de threads. En el caso de aplicar una recuperación basada en abortar al solicitante, sólo se abortará al thread involucrado, no a todo el proceso.

Código fuente de apoyo

Para la realización de esta práctica se tomará como base el código desarrollado en la práctica obligatoria del minikernel (o en otra práctica optativa). Para poder trabajar en esta práctica sin afectar al código de la parte obligatoria y poderla entregar de manera independiente, se debe copiar a un nuevo directorio denominado “minikernel_inter.201X”. Desde el directorio base del usuario, se pueden ejecutar los siguientes mandatos para realizar esta copia:

$ mkdir dso4/minikernel_inter.201X
$ cp -R dso4/minikernel.201X/* dso4/minikernel_inter.201X

Documentación que se debe entregar

El mandato a ejecutar es:

entrega.dso4 minikernel_inter.201X

Este mandato realizará la recolección de los mismos ficheros que en la práctica obligatoria del minikernel.

No existe un corrector automático para esta práctica. El alumno deberá usar sus propios programas de prueba.

Las prácticas entregadas serán corregidas una vez terminado el plazo de entrega, que es el mismo de las prácticas obligatorias.

 
docencia/asignaturas/dso/practicas/minikernel_interbloqueos.txt · Última modificación: 2013/10/18 17:19 por fperez
 
Recent changes RSS feed Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki