Aller au contenu

TNSI : Exercices Interblocage⚓︎

Exercice 1⚓︎

1°) Identifiez et explicitez sur l'exemple du carrefour à priorité à droite les 4 conditions de Coffman menant à l'interblocage.
2°) Imaginez des situations de la vie quotidienne - comme l'exemple du carrefour - où un interblocage peut survenir.

Exercice 2⚓︎

On dispose de \(7\) processus notés :

flowchart TD P1((P1)) P2((P2)) P3((P3)) P4((P4)) P5((P5)) P6((P6)) P7((P7))

et de \(7\) ressources notées:

flowchart TD R1[R1] R2[R2] R3[R3] R4[R4] R5[R5] R6[R6] R7[R7]

Ces \(7\) processus sont dans la situation suivante par rapport aux \(7\) ressources :

  • P1 a obtenu R1 et demande R2
  • P2 demande R3 et n'a obtenu aucune ressource tout comme P3 qui demande R2
  • P4 a obtenu R2 et R4, et demande R3
  • P5 a obtenu R3 et demande R5
  • P6 a obtenu R6 et demande R2
  • P7 a obtenu R5 et demande R2

On voudrait savoir s'il y a interblocage.

  1. Construire le graphe (orienté) d'allocation des ressources1 qui est le graphe (orienté) composé de deux types de noeuds/sommets :
    • les processus, qui sont représentés par des cercles
    • les ressources, qui sont représentées par des rectangles. Chaque rectangle contient autant de points qu'il y a d'exemplaires de la ressource représentée.
      Dans ce graphe :
    • La présence d'un arc Ri \(\rightarrow\) Pj signifie que la ressource Ri a été allouée au processus Pj
    • La présence d'un arc Pj \(\rightarrow\) Ri signifie que le processus Pj demande (càd est bloqué en attente de) la ressource Ri
    Corrigé
    flowchart LR R4[R4]-->P4((P4))-->R3-->P5((P5))-->R5-->P7((P7))-->R2-->P4 R1-->P1((P1))-->R2 R6-->P6((P6))-->R2 P2((P2))-->R3 P3((P3))-->R2 R2-->P4

  2. Quelles informations peut-on déduire de ce graphe quant aux ressources de chaque processus?

    Corrigé

    Ce graphe indique pour chaque processus les ressources qu’il détient ainsi que celles qu’il demande

  3. À quelle condition sur ce graphe a-t-on la garantie qu'il y a interblocage?

    Corrigé

    Il y a interblocage lorsque des cycles sont présents dans le graphe.

  4. Déterminer s'il y a interblocage, ou pas.

    Corrigé

    Ici, il y a interblocage car il y a un cycle dans le graphe orienté : P4 \(\rightarrow\) R3 \(\rightarrow\) P5 \(\rightarrow\) R5 \(\rightarrow\) P7 \(\rightarrow\) R2 \(\rightarrow\) P4

Exercice 3⚓︎

On se donne 3 processus A, B et B, qui utilisent 3 ressources R, S et T :

flowchart TD A((A)) B((B)) C((C)) R[R] S[S] T[T]

  1. Les ressources sont dans la situation suivante :

    • A a obtenu R, et demande S
    • B a obtenu S, et demande T
    • C a obtenu T, et demande R

Établir le graphe d'allocation des ressources

Corrigé
flowchart LR R-->A((A)) S-->B((B)) T-->C((C)) A-->S B-->T C-->R
  1. Y-a-til interblocage? pourquoi?

Exercice 4 (Polynésie 2023, Jour 2)⚓︎

On donne dans le tableau ci-dessous quatre processus qui doivent être exécutés par un processeur. Chaque processus a un instant d’arrivée et une durée, donnés en nombre de cycles du processeur.

Processus P1 P2 P3 P4
Instant d'arrivée 0 2 3 7
Durée 8 6 2 2

Les processus sont placés dans une file d’attente en fonction de leur instant d’arrivée. On se propose d’ordonnancer ces quatre processus avec la méthode suivante :

  • Parmi les processus présents en liste d’attente, l’ordonnanceur choisit celui dont la durée restante est la plus courte ;
  • Le processeur exécute un cycle de ce processus puis l’ordonnanceur désigne de nouveau le processus dont la durée restante est la plus courte ;
  • En cas d’égalité de temps restant entre plusieurs processus, celui choisi sera celui dont l’instant d’arrivée est le plus ancien ;
  • Tout ceci jusqu’à épuisement des processus en liste d’attente. On donne en exemple ci-dessous, l’ordonnancement des quatre processus de l’exemple précédent suivant l’algorithme ci-dessus.

Notes⚓︎

  1. Communication et Synchronisation dans les Systèmes Temps Réels, Naïm Rahmani, Univ. Ottawa, 🇨🇦 p23 ↩