Qu’est-ce qu’une impasse ?

StackOverflow https://stackoverflow.com/questions/34512

Question

Lors de l’écriture d’applications multithread, l’un des problèmes les plus courants rencontrés est celui des blocages.

Mes questions à la communauté sont les suivantes :

  1. Qu’est-ce qu’une impasse ?

  2. Comment les détecter ?

  3. Les manipulez-vous ?

  4. Et enfin, comment éviter qu’ils se produisent ?

Était-ce utile?

La solution

UN verrouillage se produit lorsque plusieurs processus tentent d'accéder à la même ressource en même temps.

Un processus est perdant et doit attendre que l’autre se termine.

UN impasse se produit lorsque le processus en attente conserve toujours une autre ressource dont le premier a besoin avant de pouvoir se terminer.

Alors, un exemple :

La ressource A et la ressource B sont utilisées par le processus X et le processus Y

  • X commence à utiliser A.
  • X et Y essaient de commencer à utiliser B
  • Y « gagne » et obtient B en premier
  • maintenant Y doit utiliser A
  • A est verrouillé par X, qui attend Y

La meilleure façon d’éviter les blocages est d’éviter que les processus se croisent de cette manière.Réduisez autant que possible le besoin de verrouiller quoi que ce soit.

Dans les bases de données, évitez d'apporter de nombreuses modifications à différentes tables en une seule transaction, évitez les déclencheurs et passez autant que possible aux lectures optimistes/sales/nolock.

Autres conseils

Laissez-moi vous expliquer un exemple réel (pas réellement réel) d'une situation d'impasse tirée des films policiers.Imaginez qu'un criminel tienne un otage et qu'en contrepartie, un flic tienne également en otage un ami du criminel.Dans ce cas, le criminel ne laissera pas partir l'otage si le flic ne laisse pas son ami le laisser partir.De plus, le flic ne laissera pas l'ami du criminel partir, à moins que le criminel ne libère l'otage.Il s’agit d’une situation sans fin et indigne de confiance, car les deux parties insistent pour que l’autre fasse le premier pas.

Scène criminelle et policière

enter image description here

Donc simplement, lorsque deux threads ont besoin de deux ressources différentes et que chacun d’eux a le verrou de la ressource dont l’autre a besoin, c’est une impasse.

Une autre explication de haut niveau de l’impasse :Cœurs brisés

Vous sortez avec une fille et un jour après une dispute, les deux parties ont le cœur brisé et attendent une réponse. Je-suis-désolé-et-tu-m'as-manqué appel.Dans cette situation, les deux parties veulent communiquer si et seulement si l'une d'elles reçoit un Je suis désolé appel de l'autre.Parce qu'aucun des deux ne va démarrer la communication et attendre dans un état passif, les deux attendront que l'autre démarre la communication, ce qui se terminera dans une situation de blocage.

Les blocages ne se produiront que lorsque vous disposez de deux verrous ou plus pouvant être acquis en même temps et qu'ils sont saisis dans un ordre différent.

Les moyens d’éviter les blocages sont les suivants :

  • éviter d'avoir des cadenas (si possible),
  • éviter d'avoir plus d'un verrou
  • prenez toujours les serrures dans le même ordre.

Pour définir l’impasse, je définirais d’abord le processus.

Processus : Comme nous le savons, le processus n'est rien d'autre qu'un program en exécution.

Ressource : Pour exécuter un processus de programme, il faut certaines ressources.Les catégories de ressources peuvent inclure la mémoire, les imprimantes, les processeurs, les fichiers ouverts, les lecteurs de bande, les CD-ROM, etc.

Impasse : Un blocage est une situation ou une condition dans laquelle deux processus ou plus détiennent certaines ressources et tentent d'acquérir des ressources supplémentaires, et ils ne peuvent pas libérer les ressources tant qu'ils n'ont pas terminé leur exécution.

Condition ou situation de blocage

enter image description here

Dans le diagramme ci-dessus, il y a deux processus P1 et p2 et il y a deux ressources R1 et R2.

Ressource R1 est affecté au processus P1 et ressource R2 est affecté au processus p2.Pour terminer l’exécution du processus P1 a besoin de ressources R2, donc P1 demande R2, mais R2 est déjà attribué à P2.

De la même manière Processus P2 pour compléter ses besoins d'exécution R1, mais R1 est déjà attribué à P1.

les deux processus ne peuvent pas libérer leur ressource tant qu'ils n'ont pas terminé leur exécution.Les deux attendent donc d’autres ressources et attendront éternellement.C'est donc un IMPASSE Condition.

Pour qu’une impasse se produise, quatre conditions doivent être remplies.

  1. Exclusion mutuelle - Chaque ressource est soit actuellement allouée à exactement un processus, soit elle est disponible.(Deux processus ne peuvent pas contrôler simultanément la même ressource ou être dans leur section critique).
  2. Attendez et attendez - les processus détenant actuellement des ressources peuvent demander de nouvelles ressources.
  3. Pas de préemption - Une fois qu'un processus détient une ressource, elle ne peut pas être retirée par un autre processus ou par le noyau.
  4. Attente circulaire - Chaque processus attend d'obtenir une ressource qui est détenue par un autre processus.

et toutes ces conditions sont satisfaites dans le diagramme ci-dessus.

Un blocage se produit lorsqu'un thread attend quelque chose qui ne se produit jamais.

Généralement, cela se produit lorsqu'un thread attend un mutex ou un sémaphore qui n'a jamais été publié par le propriétaire précédent.

Cela arrive également fréquemment lorsque vous vous trouvez dans une situation impliquant deux threads et deux verrous comme celui-ci :

Thread 1               Thread 2

Lock1->Lock();         Lock2->Lock();
WaitForLock2();        WaitForLock1();   <-- Oops!

Vous les détectez généralement parce que les choses que vous attendez ne se produisent jamais ou que l'application se bloque complètement.

Vous pouvez jeter un oeil à ceci articles merveilleux, sous section Impasse.C'est en C# mais l'idée est toujours la même pour les autres plateforme.Je cite ici pour faciliter la lecture

Une impasse se produit lorsque deux threads attendent chacun une ressource détenue par l'autre, donc ni l'un ni l'autre ne peut continuer.La façon la plus simple d'illustrer cela est avec deux serrures:

object locker1 = new object();
object locker2 = new object();

new Thread (() => {
                    lock (locker1)
                    {
                      Thread.Sleep (1000);
                      lock (locker2);      // Deadlock
                    }
                  }).Start();
lock (locker2)
{
  Thread.Sleep (1000);
  lock (locker1);                          // Deadlock
}

Le blocage est un problème courant dans les problèmes de multitraitement/multiprogrammation dans le système d'exploitation.Supposons qu'il existe deux processus P1, P2 et deux ressources partageables globalement R1, R2 et que dans la section critique, les deux ressources doivent être accessibles

Initialement, le système d'exploitation attribue R1 au processus P1 et R2 au processus P2.Comme les deux processus s'exécutent simultanément, ils peuvent commencer à exécuter leur code, mais le PROBLÈME survient lorsqu'un processus atteint la section critique.Le processus R1 attendra donc que le processus P2 libère R2 et vice versa...Ils attendront donc éternellement (CONDITION DEADLOCK).

Une petite ANALOGIE...

Votre mère (OS),
Vous (P1),
Ton frère(P2),
Pomme(R1),
Couteau(R2),
section critique (couper la pomme avec un couteau).

Au début, ta mère te donne la pomme et le couteau à ton frère.
Les deux sont heureux et jouent (exécutant leurs codes).
N'importe lequel d'entre vous veut couper la pomme (section critique) à un moment donné.
Tu ne veux pas donner la pomme à ton frère.
Ton frère ne veut pas te donner le couteau.
Donc vous allez tous les deux attendre très très longtemps :)

Un blocage se produit lorsqu'il existe une chaîne circulaire de threads ou de processus qui contiennent chacun une ressource verrouillée et tentent de verrouiller une ressource détenue par l'élément suivant de la chaîne.Par exemple, deux threads qui détiennent respectivement le verrou A et le verrou B, et tentent tous deux d'acquérir l'autre verrou.

Un blocage se produit lorsque deux threads acquièrent des verrous qui empêchent l'un ou l'autre de progresser.La meilleure façon de les éviter est de les développer avec soin.De nombreux systèmes embarqués s'en protègent en utilisant un minuteur de surveillance (un minuteur qui réinitialise le système à chaque fois qu'il se bloque pendant un certain temps).

Un blocage est un état d'un système dans lequel aucun processus/thread n'est capable d'exécuter une action.Comme mentionné par d'autres, un blocage est généralement le résultat d'une situation dans laquelle chaque processus/thread souhaite acquérir un verrou sur une ressource qui est déjà verrouillée par un autre (ou même le même) processus/thread.

Il existe différentes méthodes pour les trouver et les éviter.On réfléchit très fort et/ou on essaie beaucoup de choses.Cependant, gérer le parallélisme est notoirement difficile et la plupart (sinon la totalité) des gens ne seront pas en mesure d’éviter complètement les problèmes.

Certaines méthodes plus formelles peuvent être utiles si vous souhaitez sérieusement résoudre ce type de problèmes.La méthode la plus pratique que je connaisse consiste à utiliser l'approche théorique des processus.Ici, vous modélisez votre système dans un langage de processus (par ex.CCS, CSP, ACP, mCRL2, LOTOS) et utilisez les outils disponibles pour (modéliser) vérifier les blocages (et peut-être également d'autres propriétés).Des exemples d'outils à utiliser sont FDR, mCRL2, CADP et Uppaal.Certaines âmes courageuses pourraient même prouver que leurs systèmes sont débarrassés de toute impasse en utilisant des méthodes purement symboliques (preuve de théorème ;cherchez Owicki-Gries).

Cependant, ces méthodes formelles nécessitent généralement un certain effort (par ex.apprendre les bases de la théorie des processus).Mais je suppose que c’est simplement une conséquence du fait que ces problèmes sont difficiles.

Une impasse est une situation qui se produit lorsqu’il y a moins de ressources disponibles car elles sont demandées par les différents processus.Cela signifie que lorsque le nombre de ressources disponibles devient inférieur à celui demandé par l'utilisateur, le processus passe alors en état d'attente. Parfois, l'attente augmente davantage et il n'y a aucune chance de vérifier le problème du manque de ressources. cette situation est connue sous le nom d'impasse.En fait, le blocage est un problème majeur pour nous et il ne se produit que dans les systèmes d'exploitation multitâches. Un blocage ne peut pas se produire dans un système d'exploitation monotâche car toutes les ressources ne sont présentes que pour la tâche en cours d'exécution......

Ci-dessus, certaines explications sont sympas.J'espère que cela pourra également être utile :https://ora-data.blogspot.in/2017/04/deadlock-in-oracle.html

Dans une base de données, lorsqu'une session (par ex.ora) veut une ressource détenue par une autre session (par ex.data), mais cette session (data) veut également une ressource qui est détenue par la première session (ora).Il peut également y avoir plus de 2 sessions impliquées, mais l'idée sera la même.En fait, les blocages empêchent certaines transactions de continuer à fonctionner.Par exemple:Supposons que Ora-Data ait le verrouillage A et demande le verrouillage B et SKU tient le verrouillage B et demande le verrouillage A.

Merci,

Un blocage se produit lorsqu'un thread attend la fin d'un autre thread et vice versa.

Comment éviter?
- Évitez les verrous imbriqués
- Évitez les verrous inutiles
- Utiliser la jointure de fil()

Comment le détecter ?
exécutez cette commande dans cmd : 

jcmd $PID Thread.print

référence :geeksforgeeks

Un programme classique et très simple pour comprendre Impasse situation :-

public class Lazy {

    private static boolean initialized = false;

    static {
        Thread t = new Thread(new Runnable() {
            public void run() {
                initialized = true;
            }
        });

        t.start();

        try {
            t.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

    public static void main(String[] args) {
        System.out.println(initialized);
    }
}

Lorsque le fil principal invoque Lazy.main, il vérifie si la classe Lazy a été initialisée et commence à initialiser la classe.Le thread principal définit désormais l'initialisation sur FALSE, crée et démarre un thread d'arrière-plan dont la méthode d'exécution définit l'initialisation sur true et attend que le thread d'arrière-plan se termine.

Cette fois, la classe est en cours d'initialisation par un autre thread.Dans ces circonstances, le thread actuel, qui est le thread d'arrière-plan, attend l'objet de classe jusqu'à ce que l'initialisation soit terminée.Malheureusement, le thread qui fait l'initialisation, le thread principal, attend que le thread d'arrière-plan se termine.Parce que les deux threads s'attendent maintenant, le programme est DANS UNE IMPASSE.

Le problème de l’impasse

  • Les premiers systèmes d'exploitation informatiques ont effectué un seul programme à la fois
  • Toutes les ressources du système étaient disponibles pour ce programme
  • Plus tard, les systèmes d'exploitation ont organisé plusieurs programmes à la fois, en les entrelacement
  • Des programmes devaient spécifier à l'avance les ressources dont ils avaient besoin afin qu'ils puissent éviter les conflits avec d'autres programmes exécutés en même temps
  • Finalement, certains systèmes d'exploitation proposaient une allocation dynamique des ressources
  • Les programmes pourraient demander d'autres allocations de ressources après avoir commencé à courir
  • Cela a conduit au problème de l'impasse

Un ensemble de processus bloqués tenant chacun une ressource et attendant d'acquérir une ressource détenue par un autre processus de l'ensemble

Une situation dans laquelle 02 ou plus d'actions concurrentes attendent chacune que l'autre se termine, et donc aucun des deux

Caractérisation des impasses

  • Exclusion mutuelle
  • Tenir et attendre
  • Pas de préemption
  • Attente circulaire

Méthodes de gestion des blocages

  • Assurez-vous que le système n’entrera jamais dans un état de blocage
  • Permettez au système d'entrer dans un état de blocage, puis de récupérer
  • Ignorez le problème et prétendez que les impasses ne se produisent jamais dans le système;Utilisé par la plupart des systèmes d'exploitation, y compris Unix

Prévention des blocages

  • Exclusion mutuelle – non requis pour les ressources partageables ;doit être conservé pour les ressources non partageables

  • Attendez et attendez - Doit garantir que chaque fois qu'un processus demande une ressource, il ne contient aucune autre ressource

  • Pas de préemption - Si un processus qui tient des ressources demande une autre ressource qui ne peut pas y être immédiatement allouée, alors toutes les ressources actuellement détenues sont publiées

  • Attente circulaire - imposer une commande totale de tous les types de ressources et exiger que chaque processus demande des ressources dans un ordre croissant d'énumération

Mutex est essentiellement un verrou offrant un accès protégé aux ressources partagées.Sous Linux, le type de données mutex du thread est pthread_mutex_t.Avant utilisation, initialisez-le.

Pour accéder aux ressources partagées, vous devez verrouiller le mutex.Si le mutex est déjà sur le verrou, l'appel bloquera le thread jusqu'à ce que le mutex soit déverrouillé.À la fin de la visite des ressources partagées, vous devez les débloquer.

Globalement, il existe quelques principes de base non écrits :

  • Obtenez le verrou avant d'utiliser les ressources partagées.

  • Maintenir le verrou le moins longtemps possible.

  • Libérez le verrou si le thread renvoie une erreur.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top