Le graphe d'attente

Le graphe d'attente. Un système possède quatre ressources $R_{1}$ , $R_{2}$ , $R_{3}$ , $R_{4}$ , chacune en un seul exemplaire. À un instant donné :

$P_{1}$ détient $R_{1}$ et demande $R_{2}$ ;
$P_{2}$ détient $R_{2}$ et demande $R_{3}$ ;
$P_{3}$ détient $R_{3}$ et demande $R_{1}$ ;
$P_{4}$ détient $R_{4}$ et demande $R_{2}$ .

Construire le graphe d'attente : un sommet par processus, et un arc $P \to Q$ lorsque $P$ attend une ressource détenue par $Q$ .
Y a-t-il interblocage ? Quels processus sont bloqués pour toujours ? $P_{4}$ fait-il partie du cycle ?
Le système décide d'arrêter $P_{3}$ , ce qui libère $R_{3}$ . Montrer que tous les autres processus peuvent alors se terminer.
On représente la situation en Python par deux dictionnaires :


detient = {"R1": "P1", "R2": "P2", "R3": "P3", "R4": "P4"}
demande = {"P1": "R2", "P2": "R3", "P3": "R1", "P4": "R2"}

Écrire une fonction graphe_attente(detient, demande) qui renvoie le dictionnaire des arcs (chaque processus en attente est associé au processus qu'il attend), puis une fonction bloque_pour_toujours(attente, p) qui renvoie True si, en suivant les attentes depuis p, on retombe sur un processus déjà rencontré.

Énoncé

Exercices semblables