SGBD distribué - Gestion des interblocages

Ce chapitre présente les mécanismes de gestion des interblocages dans les systèmes de base de données. Nous étudierons les mécanismes de gestion des blocages dans les systèmes de base de données centralisés et distribués.

Que sont les Deadlocks?

Le blocage est un état d'un système de base de données ayant deux transactions ou plus, lorsque chaque transaction attend un élément de données qui est verrouillé par une autre transaction. Un blocage peut être indiqué par un cycle dans le graphique d'attente. Il s'agit d'un graphe orienté dans lequel les sommets indiquent les transactions et les arêtes indiquent les attentes pour les éléments de données.

Par exemple, dans le graphique d'attente suivant, la transaction T1 attend la donnée X qui est verrouillée par T3. T3 attend Y qui est verrouillé par T2 et T2 attend Z qui est verrouillé par T1. Par conséquent, un cycle d'attente est formé et aucune des transactions ne peut continuer à s'exécuter.

Gestion des interblocages dans les systèmes centralisés

Il existe trois approches classiques pour la gestion des blocages, à savoir -

  • Prévention des blocages.
  • Évitement des blocages.
  • Détection et suppression des interblocages.

Les trois approches peuvent être intégrées à la fois dans un système de base de données centralisé et distribué.

Prévention des blocages

L'approche de prévention des interblocages ne permet à aucune transaction d'acquérir des verrous qui entraîneront des blocages. La convention est que lorsque plusieurs transactions demandent le verrouillage du même élément de données, une seule d'entre elles se voit accorder le verrou.

L'une des méthodes de prévention des blocages les plus populaires est la pré-acquisition de tous les verrous. Dans cette méthode, une transaction acquiert tous les verrous avant de commencer à s'exécuter et conserve les verrous pendant toute la durée de la transaction. Si une autre transaction nécessite l'un des verrous déjà acquis, elle doit attendre que tous les verrous dont elle a besoin soient disponibles. En utilisant cette approche, le système ne peut pas être bloqué car aucune des transactions en attente ne détient de verrou.

Évitement des blocages

L'approche d'évitement des blocages gère les blocages avant qu'ils ne se produisent. Il analyse les transactions et les verrous pour déterminer si l'attente entraîne ou non un blocage.

La méthode peut être brièvement énoncée comme suit. Les transactions commencent à s'exécuter et demandent les éléments de données qu'elles doivent verrouiller. Le gestionnaire de verrouillage vérifie si le verrou est disponible. S'il est disponible, le gestionnaire de verrouillage alloue l'élément de données et la transaction acquiert le verrou. Cependant, si l'élément est verrouillé par une autre transaction en mode incompatible, le gestionnaire de verrous exécute un algorithme pour tester si le maintien de la transaction en état d'attente provoquera un blocage ou non. En conséquence, l'algorithme décide si la transaction peut attendre ou si l'une des transactions doit être abandonnée.

Il existe deux algorithmes à cet effet, à savoir wait-die et wound-wait. Supposons qu'il y ait deux transactions, T1 et T2, où T1 essaie de verrouiller une donnée qui est déjà verrouillée par T2. Les algorithmes sont les suivants -

  • Wait-Die- Si T1 est plus ancien que T2, T1 est autorisé à attendre. Sinon, si T1 est plus jeune que T2, T1 est abandonné et redémarré ultérieurement.

  • Wound-Wait- Si T1 est plus ancien que T2, T2 est interrompu et redémarré ultérieurement. Sinon, si T1 est plus jeune que T2, T1 est autorisé à attendre.

Détection et suppression des interblocages

L'approche de détection et de suppression des interblocages exécute périodiquement un algorithme de détection des interblocages et supprime les interblocages au cas où il y en aurait un. Il ne vérifie pas le blocage lorsqu'une transaction place une demande de verrou. Lorsqu'une transaction demande un verrou, le gestionnaire de verrous vérifie s'il est disponible. S'il est disponible, la transaction est autorisée à verrouiller l'élément de données; sinon, la transaction est autorisée à attendre.

Puisqu'il n'y a aucune précaution lors de l'octroi des demandes de verrouillage, certaines des transactions peuvent être bloquées. Pour détecter les blocages, le gestionnaire de verrouillage vérifie périodiquement si le graphique d'attente comporte des cycles. Si le système est bloqué, le gestionnaire de verrous choisit une transaction victime de chaque cycle. La victime est avortée et annulée; puis redémarré plus tard. Certaines des méthodes utilisées pour la sélection des victimes sont:

  • Choisissez la transaction la plus récente.
  • Choisissez la transaction avec le moins d'éléments de données.
  • Choisissez la transaction qui a effectué le moins de mises à jour.
  • Choisissez la transaction ayant le moins de frais généraux de redémarrage.
  • Choisissez la transaction commune à deux ou plusieurs cycles.

Cette approche est principalement adaptée aux systèmes dont les transactions sont faibles et où une réponse rapide aux demandes de verrouillage est nécessaire.

Gestion des interblocages dans les systèmes distribués

Le traitement des transactions dans un système de base de données distribué est également distribué, c'est-à-dire que la même transaction peut être traitée sur plus d'un site. Les deux principaux problèmes de gestion des interblocages dans un système de base de données distribuée qui ne sont pas présents dans un système centralisé sonttransaction location et transaction control. Une fois que ces problèmes sont résolus, les blocages sont traités par le biais de la prévention des blocages, de l'évitement des blocages ou de la détection et de la suppression des blocages.

Emplacement de la transaction

Les transactions dans un système de base de données distribué sont traitées dans plusieurs sites et utilisent des éléments de données dans plusieurs sites. Le volume de traitement des données n'est pas uniformément réparti entre ces sites. La période de traitement varie également. Ainsi, la même transaction peut être active sur certains sites et inactive sur d'autres. Lorsque deux transactions conflictuelles se trouvent sur un site, il se peut que l'une d'elles soit à l'état inactif. Cette condition ne se pose pas dans un système centralisé. Ce problème est appelé problème de localisation de transaction.

Ce problème peut être résolu par le modèle Daisy Chain. Dans ce modèle, une transaction comporte certains détails lorsqu'elle passe d'un site à un autre. Certains des détails sont la liste des tables requises, la liste des sites requis, la liste des tables et sites visités, la liste des tables et sites qui n'ont pas encore été visités et la liste des verrous acquis avec les types. Après la fin d'une transaction par validation ou abandon, les informations doivent être envoyées à tous les sites concernés.

Contrôle des transactions

Le contrôle des transactions concerne la désignation et le contrôle des sites nécessaires au traitement d'une transaction dans un système de base de données distribué. Il existe de nombreuses options concernant le choix du lieu de traitement de la transaction et la manière de désigner le centre de contrôle, comme -

  • Un serveur peut être sélectionné comme centre de contrôle.
  • Le centre de contrôle peut se déplacer d'un serveur à un autre.
  • La responsabilité du contrôle peut être partagée par un certain nombre de serveurs.

Prévention de blocage distribuée

Tout comme dans la prévention centralisée des interblocages, dans l'approche de prévention des interblocages distribués, une transaction doit acquérir tous les verrous avant de commencer à s'exécuter. Cela évite les blocages.

Le site sur lequel la transaction entre est désigné comme site de contrôle. Le site de contrôle envoie des messages aux sites où se trouvent les éléments de données pour verrouiller les éléments. Ensuite, il attend la confirmation. Lorsque tous les sites ont confirmé qu'ils ont verrouillé les éléments de données, la transaction démarre. Si un site ou un lien de communication échoue, la transaction doit attendre jusqu'à ce qu'ils soient réparés.

Bien que la mise en œuvre soit simple, cette approche présente certains inconvénients -

  • La pré-acquisition des verrous nécessite beaucoup de temps pour les retards de communication. Cela augmente le temps requis pour la transaction.

  • En cas de défaillance du site ou du lien, une transaction doit attendre longtemps pour que les sites se rétablissent. Pendant ce temps, dans les sites en cours d'exécution, les éléments sont verrouillés. Cela peut empêcher l'exécution d'autres transactions.

  • Si le site de contrôle échoue, il ne peut pas communiquer avec les autres sites. Ces sites continuent de conserver les éléments de données verrouillés dans leur état verrouillé, ce qui entraîne un blocage.

Évitement de blocage distribué

Comme dans le système centralisé, l'évitement distribué des interblocages gère les interblocages avant leur occurrence. De plus, dans les systèmes distribués, les problèmes de localisation des transactions et de contrôle des transactions doivent être résolus. En raison de la nature distribuée de la transaction, les conflits suivants peuvent survenir -

  • Conflit entre deux transactions sur le même site.
  • Conflit entre deux transactions sur des sites différents.

En cas de conflit, l'une des transactions peut être abandonnée ou autorisée à attendre selon les algorithmes d'attente distribuée ou distribuée d'attente de blessure.

Supposons qu'il y ait deux transactions, T1 et T2. T1 arrive sur le site P et tente de verrouiller une donnée qui est déjà verrouillée par T2 sur ce site. Par conséquent, il y a un conflit sur le site P. Les algorithmes sont les suivants -

  • Distributed Wound-Die

    • Si T1 est plus ancien que T2, T1 est autorisé à attendre. T1 peut reprendre l'exécution après que le site P reçoive un message indiquant que T2 a réussi ou abandonné avec succès sur tous les sites.

    • Si T1 est plus jeune que T2, T1 est abandonné. Le contrôle de concurrence sur le site P envoie un message à tous les sites où T1 a visité pour abandonner T1. Le site de contrôle informe l'utilisateur lorsque T1 a été abandonné avec succès dans tous les sites.

  • Distributed Wait-Wait

    • Si T1 est plus ancien que T2, T2 doit être interrompu. Si T2 est actif sur le site P, le site P abandonne et annule T2, puis diffuse ce message à d'autres sites pertinents. Si T2 a quitté le site P mais est actif sur le site Q, le site P diffuse que T2 a été abandonné; Le site L abandonne ensuite et annule T2 et envoie ce message à tous les sites.

    • Si T1 est plus jeune que T1, T1 est autorisé à attendre. T1 peut reprendre l'exécution après que le site P a reçu un message indiquant que T2 a terminé le traitement.

Détection de blocage distribuée

Tout comme l'approche de détection de blocage centralisée, les blocages sont autorisés à se produire et sont supprimés s'ils sont détectés. Le système n'effectue aucun contrôle lorsqu'une transaction place une demande de verrouillage. Pour l'implémentation, des graphes d'attente globaux sont créés. L'existence d'un cycle dans le graphique global d'attente indique des blocages. Cependant, il est difficile de repérer les blocages car la transaction attend des ressources sur le réseau.

Les algorithmes de détection de blocage peuvent également utiliser des minuteries. Chaque transaction est associée à un minuteur qui est réglé sur une période de temps dans laquelle une transaction devrait se terminer. Si une transaction ne se termine pas dans ce délai, la minuterie s'éteint, indiquant un possible blocage.

Un autre outil utilisé pour la gestion des interblocages est un détecteur d'interblocage. Dans un système centralisé, il existe un détecteur de blocage. Dans un système distribué, il peut y avoir plusieurs détecteurs de blocage. Un détecteur de blocage peut trouver des blocages pour les sites sous son contrôle. Il existe trois alternatives pour la détection de blocage dans un système distribué, à savoir.

  • Centralized Deadlock Detector - Un site est désigné comme détecteur central de blocage.

  • Hierarchical Deadlock Detector - Un certain nombre de détecteurs de blocage sont organisés en hiérarchie.

  • Distributed Deadlock Detector - Tous les sites participent à la détection des blocages et à leur suppression.