Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

1 Chapitre 2 : TECHNIQUES DE CONTROLE DE CONCURRENCE 2.1 Définition Le contrôle

1 Chapitre 2 : TECHNIQUES DE CONTROLE DE CONCURRENCE 2.1 Définition Le contrôle de concurrence consiste à coordonner l'exécution simultanée de transactions dans un système multi-tâches de gestion de base de données. L'objectif est d'assurer la sérialisabilité des transactions. 2.2 Verrouillage Un bon moyen d'assurer la sérialisabilité est d'imposer que les accès aux données de la base se fassent de façon mutuellement exclusive. Un verrou garantit un usage exclusif d'une donnée à une transaction. Un verrou sert à interdire l'accès à une donnée qui est en cours d'utilisation par une autre transaction. Si une transaction T1 pose un verrou sur l'accès d'une donnée, une transaction T2 n'aura pas accès à cette donnée. Le verrou est levé lorsque la transaction T1 est terminée, la transaction T2 pourra alors poser elle-même un verrou pour son usage. Notons qu'une transaction doit maintenir son verrou sur une donnée aussi longtemps qu'elle y a accès. De plus, il n'est pas toujours souhaitable qu'une transaction déverrouille la donnée qu'elle traite immédiatement après y avoir eu accès, puisqu'on n'est pas sûr de sa sérialisabilité. 2.2.1. Modes de verrouillage Le mode partagé. Dans ce mode, une transaction peut lire un objet mais non l'écrire. C'est un verrou en lecture. Aucune transaction T ne peut mettre à jour la donnée E mais des transactions concurrentes T4, T3 ... peuvent l'accéder en lecture. Le mode exclusif. Dans ce mode, une transaction peut lire et écrire l'objet. C'est un verrou en écriture. Seulement la transaction T peut mettre à jour la donnée E et tout autre accès est interdit. Le mode partagé est toujours compatible avec lui-même, mais incompatible avec le mode exclusif. On peut entretenir plusieurs modes partagés, à un instant donné, entre plusieurs transactions pour un objet donné, c'est à dire, plusieurs verrous en lecture sur un même objet. Une demande ultérieure de mode exclusif doit attendre la relaxation du mode partagé pour être prise en compte. 2.2.2. Le protocole de verrouillage deux-phases. On a vu que le verrouillage des données d'une base doit être appliqué avec modération. Si, d'une part, on tente d'augmenter le rendement du traitement simultané des transactions en déverrouillant les données dès que possible, la base peut se retrouver en état inconsistant. Si d'autre part on ne déverrouille pas un article avant d'en verrouiller un autre, on crée des interblocages. Nous imposerons donc aux transactions de respecter un ensemble de règles appelées protocole de verrouillage qui organise le verrouillage et le déverrouillage des données concernées par les transactions. Le protocole de verrouillage le plus important est le protocole deux-phases. Si toutes les transactions utilisent ce protocole, alors tous les schémas parallèles qu'on peut former seront sérialisables. Ce protocole implique que chacune des transactions de la séquence émette ses demandes de verrouillage et de déverrouillage en deux phases : Verrouillage croissant : Une transaction peut obtenir des verrouillages, mais pas de nouveau déverrouillage. On pose tous les verrous nécessaires pendant cette phase. Verrouillage décroissant : Une transaction peut obtenir des déverrouillages, mais pas de nouveau verrouillage. Initialement, une transaction donnée est en phase de verrouillage croissant. Lorsqu'elle libère un verrou, elle entre en phase de décroissance et aucun verrou ne peut plus être imposé. 2.2.3. Algorithme VERROUILLAGE EXCLUSIF  Un ordre de priorité pour les transactions est choisi.  Chaque quantum de temps, l'ordonnanceur passe la main à la première transaction dans la liste de priorité choisi.  Une transaction Ti demande un objet Ok.  S'il n'y a pas un verrou sur l'objet Ok, on  S'il y a un verrou sur l'objet Ok, alors la transaction Ti est mise en attente et le processeur est attribué à la transaction suivante Lorsqu'une transaction est validée, on lui affecte la priorité la plus basse VERROUILLAGE PARTAGE Dans le verrouillage partagé, on distingue les demandes en écriture des demandes en lecture.  Si la demande est une écriture, alors on fait comme dans le verrouillage exclusif.  Si la transaction Ti demande l'objet Ok pour une lec sur Ok, alors on pose un verrou en lecture pas. 2.2.4 Avantages et inconvénients Un mécanisme de verrouillage permet à une transaction de se réserver l'usage exclusif d donnée aussi longtemps que c'est nécessaire. Un inconvénient du verrouillage est son coût élevé lorsque les transactions font référence à de nombreuses données de la base. En contre partie, le degré de parallélisme est maximum puisque seules son ver données réellement manipulées par les transactions. On doit aussi tenir en compte le problème 2.3 Estampillage Dans le paragraphe précédent, nous avons étudié la méthode de verrouillage qui, associée à un protocole deux phases (par exemple) garantit la sérialisabilité d'une exécution de transactions en parallèle. Si une transaction demande un objet qui est bloqué, : Une transaction peut obtenir des déverrouillages, mais pas de Initialement, une transaction donnée est en phase de verrouillage croissant. Lorsqu'elle libère un verrou, elle entre en phase de décroissance et aucun verrou ne peut plus être imposé. VERROUILLAGE EXCLUSIF Un ordre de priorité pour les transactions est choisi. Chaque quantum de temps, l'ordonnanceur passe la main à la première transaction dans la liste de priorité choisi. Une transaction Ti demande un objet Ok. S'il n'y a pas un verrou sur l'objet Ok, on verrouille Ok. S'il y a un verrou sur l'objet Ok, alors la transaction Ti est mise en attente et le processeur est attribué à la transaction suivante dans la liste de priorité. Lorsqu'une transaction est validée, on lui affecte la priorité la plus basse. VERROUILLAGE PARTAGE Dans le verrouillage partagé, on distingue les demandes en écriture des demandes en lecture. Si la demande est une écriture, alors on fait comme dans le verrouillage exclusif. Si la transaction Ti demande l'objet Ok pour une lecture et s'il y a un verrou en lecture sur Ok, alors on pose un verrou en lecture sur l'objet Ok et la transaction ne se bloque .4 Avantages et inconvénients Un mécanisme de verrouillage permet à une transaction de se réserver l'usage exclusif d donnée aussi longtemps que c'est nécessaire. Un inconvénient du verrouillage est son coût élevé lorsque les transactions font référence à de nombreuses données de la base. En contre partie, le degré de parallélisme est maximum puisque seules son ver données réellement manipulées par les transactions. On doit aussi tenir en compte le problème de verrou mortel. Dans le paragraphe précédent, nous avons étudié la méthode de verrouillage qui, associée à un protocole deux phases (par exemple) garantit la sérialisabilité d'une exécution de transactions en parallèle. Si une transaction demande un objet qui est bloqué, il doit attendre que l'objet se 2 : Une transaction peut obtenir des déverrouillages, mais pas de Initialement, une transaction donnée est en phase de verrouillage croissant. Lorsqu'elle libère un verrou, elle entre en phase de décroissance et aucun verrou ne peut plus être imposé. Chaque quantum de temps, l'ordonnanceur passe la main à la première transaction S'il y a un verrou sur l'objet Ok, alors la transaction Ti est mise en attente et le dans la liste de priorité. Dans le verrouillage partagé, on distingue les demandes en écriture des demandes en lecture. Si la demande est une écriture, alors on fait comme dans le verrouillage exclusif. ture et s'il y a un verrou en lecture sur l'objet Ok et la transaction ne se bloque Un mécanisme de verrouillage permet à une transaction de se réserver l'usage exclusif d'une Un inconvénient du verrouillage est son coût élevé lorsque les transactions font référence à de En contre partie, le degré de parallélisme est maximum puisque seules son verrouillées les Dans le paragraphe précédent, nous avons étudié la méthode de verrouillage qui, associée à un protocole deux phases (par exemple) garantit la sérialisabilité d'une exécution de transactions il doit attendre que l'objet se 3 libère : L'ordre est fixé à l'exécution suivant l'ordre dans lequel les transactions successivement bloquent les objets, ie demandent les objets. Ici, la méthode de l'estampillage est une autre approche du problème: L'ordre est fixé à priori suivant l'ordre d'apparition des transactions; notre but ici étant toujours de garantir la sérialisabilité d'une exécution. 3.2.1. Estampilles a. Estampille d'une transaction. Une estampille doit identifier de façon unique une transaction et doit être créée avant l'exécution de la transaction. Les estampilles sont gérées par le SGBD et sont assignées typiquement dans l'ordre chronologique de soumission des transactions au système. Ainsi, on peut considérer l'estampille d'une transaction comme la date de début de celle-ci. Le système doit gérer les estampilles de façon que chaque estampille soit unique. Pour ce faire, il y a deux méthodes : 1. Utilisation de l'horloge système pour dater les transactions. Il faut alors vérifier l'unicité des estampilles. 2. Utilisation d'un compteur qui s'incrémente à chaque fois que sa valeur est attribuée à une transaction: cette valeur est alors l'estampille de la transaction. Comme le compteur a une valeur maximale finie, il faut veiller à le remettre à zéro pendant une période où il n'y a pas de transactions à exécuter. b. Estampille d'un objet. L'estampille d'un objet correspond uploads/Finance/ chapitre-2-techniques-controle-concurrences.pdf