SGBD - Impasse

Dans un système multi-processus, le blocage est une situation indésirable qui survient dans un environnement de ressources partagées, où un processus attend indéfiniment une ressource détenue par un autre processus.

Par exemple, supposons un ensemble de transactions {T 0 , T 1 , T 2 , ..., T n }. T 0 a besoin d'une ressource X pour accomplir sa tâche. La ressource X est détenue par T 1 , et T 1 attend une ressource Y, qui est détenue par T 2 . T 2 attend la ressource Z, qui est détenue par T 0 . Ainsi, tous les processus attendent les uns les autres pour libérer des ressources. Dans cette situation, aucun des processus ne peut terminer sa tâche. Cette situation est connue comme une impasse.

Les blocages ne sont pas sains pour un système. Dans le cas où un système est bloqué dans un blocage, les transactions impliquées dans le blocage sont annulées ou redémarrées.

Prévention des blocages

Pour éviter toute situation de blocage dans le système, le SGBD inspecte de manière agressive toutes les opérations, là où les transactions sont sur le point de s'exécuter. Le SGBD inspecte les opérations et analyse si elles peuvent créer une situation de blocage. S'il constate qu'une situation de blocage peut se produire, cette transaction n'est jamais autorisée à être exécutée.

Il existe des schémas de prévention des blocages qui utilisent un mécanisme de classement par horodatage des transactions afin de prédéterminer une situation de blocage.

Schéma Wait-Die

Dans ce schéma, si une transaction demande de verrouiller une ressource (élément de données), qui est déjà détenue avec un verrou en conflit par une autre transaction, alors l'une des deux possibilités peut se produire -

  • Si TS (T i ) <TS (T j ) - c'est-à-dire T i , qui demande un verrou en conflit, est plus ancien que T j - alors T i est autorisé à attendre jusqu'à ce que l'élément de données soit disponible.

  • Si TS (T i )> TS (t j ) - c'est-à-dire T i est plus jeune que T j - alors T i meurt. T i est redémarré plus tard avec un retard aléatoire mais avec le même horodatage.

Ce schéma permet à la transaction plus ancienne d'attendre mais tue la plus jeune.

Schéma Wound-Wait

Dans ce schéma, si une transaction demande de verrouiller une ressource (élément de données), qui est déjà détenue avec un verrou en conflit par une autre transaction, l'une des deux possibilités peut se produire -

  • Si TS (T i ) <TS (T j ), alors T i force T j à reculer - c'est-à-dire que T i blesse T j . T j est redémarré plus tard avec un retard aléatoire mais avec le même horodatage.

  • Si TS (T i )> TS (T j ), alors T i est forcé d'attendre que la ressource soit disponible.

Ce schéma permet à la transaction plus jeune d'attendre; mais lorsqu'une transaction plus ancienne demande un article détenu par un plus jeune, la transaction plus ancienne force la plus jeune à abandonner et à libérer l'article.

Dans les deux cas, la transaction qui entre dans le système à un stade ultérieur est abandonnée.

Évitement des blocages

L'annulation d'une transaction n'est pas toujours une approche pratique. Au lieu de cela, des mécanismes d'évitement de blocage peuvent être utilisés pour détecter à l'avance toute situation de blocage. Des méthodes telles que «graphe d'attente» sont disponibles mais elles ne conviennent qu'aux systèmes où les transactions sont légères et ont moins d'instances de ressources. Dans un système encombrant, les techniques de prévention des blocages peuvent bien fonctionner.

Graphique en attente

Il s'agit d'une méthode simple disponible pour suivre si une situation de blocage peut survenir. Pour chaque transaction entrant dans le système, un nœud est créé. Lorsqu'une transaction T i demande un verrou sur un élément, disons X, qui est détenu par une autre transaction T j , un bord dirigé est créé de T i à T j . Si T j libère l'élément X, le bord entre eux est supprimé et T i verrouille l'élément de données.

Le système maintient ce graphique d'attente pour chaque transaction en attente de certains éléments de données détenus par d'autres. Le système continue de vérifier s'il y a un cycle dans le graphique.

Ici, nous pouvons utiliser l'une des deux approches suivantes -

  • Tout d'abord, n'autorisez aucune demande pour un article, qui est déjà verrouillé par une autre transaction. Cela n'est pas toujours faisable et peut entraîner une famine, où une transaction attend indéfiniment un élément de données et ne peut jamais l'acquérir.

  • La deuxième option consiste à annuler l'une des transactions. Il n'est pas toujours possible d'annuler la transaction la plus jeune, car elle peut être plus importante que la plus ancienne. À l'aide d'un algorithme relatif, une transaction est choisie, qui doit être abandonnée. Cette transaction est connue sous le nom devictim et le processus est connu comme victim selection.