Remerciez-le!

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

C018SA-W1-S5 1 SEMAINE 1 : Transactions et concurrence BASES DE DONNÉES RELATIO

C018SA-W1-S5 1 SEMAINE 1 : Transactions et concurrence BASES DE DONNÉES RELATIONNELLES Benjamin Nguyen 1. Introduction : les transactions 2. Les problèmes 3. Sérialisabilité 4. Estampillage 5. Verrouillage à 2 phases (2PL) 6. Degrés d'isolation dans les SGBD 7. Verrouillage hiérarchique Le verrouillage : pourquoi partir lorsqu’on peut attendre • Estampillage : soit tout se passe bien, soit on annule • Fonctionne-t-on comme ça « dans la vraie vie » ? Files d’attente, trains, etc … • Garantir le bon fonctionnement à On pose des verrous de plusieurs type pour empêcher une utilisation potentiellement conflictuelle des ressources (nuplets) à Selon le type de verrou, d’autres transactions pourront ou non interagir avec la ressource 3 Principe de fonctionnement 2-Phase Locking Phase 1 : Verrouillage • Lecture : Verrou « S » (Shared) • Ecriture : Verrou « X » (Exclusive) • Tenter d’exécuter une lecture (SELECT) ou une écriture (UPDATE) = essayer de poser un verrou Verrou détenu Verrou demandé S X S Accordé Mise en attente X Mise en attente Mise en attente nuplet Verrou A B Théorème : un ordonnancement construit avec 2PL est sérialisable 4 Principe de fonctionnement 2-Phase Locking Phase 1 : Verrouillage • Lecture : Verrou « S » (Shared) • Ecriture : Verrou « X » (Exclusive) • Tenter d’exécuter une lecture (SELECT) ou une écriture (UPDATE) = essayer de poser un verrou Verrou détenu Verrou demandé S X S Accordé Mise en attente X Mise en attente Mise en attente R1(A) nuplet Verrou A B S1 Théorème : un ordonnancement construit avec 2PL est sérialisable 4 Principe de fonctionnement 2-Phase Locking Phase 1 : Verrouillage • Lecture : Verrou « S » (Shared) • Ecriture : Verrou « X » (Exclusive) • Tenter d’exécuter une lecture (SELECT) ou une écriture (UPDATE) = essayer de poser un verrou Verrou détenu Verrou demandé S X S Accordé Mise en attente X Mise en attente Mise en attente R1(A) nuplet Verrou A B R2(B) S1 S2 Théorème : un ordonnancement construit avec 2PL est sérialisable 4 Principe de fonctionnement 2-Phase Locking Phase 1 : Verrouillage • Lecture : Verrou « S » (Shared) • Ecriture : Verrou « X » (Exclusive) • Tenter d’exécuter une lecture (SELECT) ou une écriture (UPDATE) = essayer de poser un verrou Verrou détenu Verrou demandé S X S Accordé Mise en attente X Mise en attente Mise en attente R1(A) nuplet Verrou A B R2(B) S1 S2 W1(A) X1 Théorème : un ordonnancement construit avec 2PL est sérialisable 4 Principe de fonctionnement 2-Phase Locking Phase 1 : Verrouillage • Lecture : Verrou « S » (Shared) • Ecriture : Verrou « X » (Exclusive) • Tenter d’exécuter une lecture (SELECT) ou une écriture (UPDATE) = essayer de poser un verrou Verrou détenu Verrou demandé S X S Accordé Mise en attente X Mise en attente Mise en attente R1(A) nuplet Verrou A B R2(B) S1 S2 W1(A) W2(A) Théorème : un ordonnancement construit avec 2PL est sérialisable 4 Principe de fonctionnement 2-Phase Locking • Tenter d’exécuter une lecture (SELECT) ou une écriture (UPDATE) = essayer de poser un verrou Verrou détenu Verrou demandé S X S Accordé Mise en attente X Mise en attente Mise en attente R1(A) nuplet Verrou A B R2(B) S1 S2 W1(A) W2(A) COMMIT1 Phase 2 : libération lors du commit ou du rollback Fin d’une transaction = retirer les verrous Théorème : un ordonnancement construit avec 2PL est sérialisable 4 Principe de fonctionnement 2-Phase Locking • Tenter d’exécuter une lecture (SELECT) ou une écriture (UPDATE) = essayer de poser un verrou Verrou détenu Verrou demandé S X S Accordé Mise en attente X Mise en attente Mise en attente R1(A) nuplet Verrou A B R2(B) S2 W1(A) W2(A) COMMIT1 X2 Phase 2 : libération lors du commit ou du rollback Fin d’une transaction = retirer les verrous Théorème : un ordonnancement construit avec 2PL est sérialisable 4 Problèmes du verrouillage à 2 phases • Verrou mortel (cycle) ou « Deadlock » § Transactions qui s’attendent mutuellement • Performance § Petit granule (nuplet) : à verrouillage coûteux § Gros granule (page, table) à temps d’attente plus important 5 Problèmes : verrou mortel • Détection : graphe des attentes (comme le graphe de précédence) § Ti attend Tj si Ti demande un verrou détenu par Tj § Si un cycle apparaît, on a un verrou mortel ! § Sur l’exemple : T1 : R(A) = SA T2 : R(B) = SB T1 : W(B) = XB T2 : W(A) = XA TEMPS t1 t2 t3 t4 T1 T2 DEADLOCK ! 6 Résolution du problème de Deadlock : Wait-Die • Wait-Die : Technique non-préemptive (n’interrompt pas) § Si Ti demande un verrouillage accordé à Tj et Ti est plus vieille alors Ti est mise en attente § Si Ti demande un verrouillage accordé à Tj et Ti est plus jeune alors Ti est annulée 7 Résolution du problème de Deadlock : Wait-Die • Wait-Die : Technique non-préemptive (n’interrompt pas) § Si Ti demande un verrouillage accordé à Tj et Ti est plus vieille alors Ti est mise en attente § Si Ti demande un verrouillage accordé à Tj et Ti est plus jeune alors Ti est annulée T1 T1 : R(A) = SA 7 Résolution du problème de Deadlock : Wait-Die • Wait-Die : Technique non-préemptive (n’interrompt pas) § Si Ti demande un verrouillage accordé à Tj et Ti est plus vieille alors Ti est mise en attente § Si Ti demande un verrouillage accordé à Tj et Ti est plus jeune alors Ti est annulée T1 T2 T1 : R(A) = SA T2 : R(B) = SB 7 Résolution du problème de Deadlock : Wait-Die • Wait-Die : Technique non-préemptive (n’interrompt pas) § Si Ti demande un verrouillage accordé à Tj et Ti est plus vieille alors Ti est mise en attente § Si Ti demande un verrouillage accordé à Tj et Ti est plus jeune alors Ti est annulée T1 T2 T1 : vieille = attend T1 : R(A) = SA T2 : R(B) = SB T1 : W(B) = XB 7 Résolution du problème de Deadlock : Wait-Die • Wait-Die : Technique non-préemptive (n’interrompt pas) § Si Ti demande un verrouillage accordé à Tj et Ti est plus vieille alors Ti est mise en attente § Si Ti demande un verrouillage accordé à Tj et Ti est plus jeune alors Ti est annulée T1 T2 T1 : vieille = attend T1 : R(A) = SA T2 : R(B) = SB T1 : W(B) = XB 7 T2 : W(A) = XA T2 : annule Résolution du problème de Deadlock : Wait-Die • Wait-Die : Technique non-préemptive (n’interrompt pas) § Si Ti demande un verrouillage accordé à Tj et Ti est plus vieille alors Ti est mise en attente § Si Ti demande un verrouillage accordé à Tj et Ti est plus jeune alors Ti est annulée T1 T2 T1 : vieille = attend T1 : R(A) = SA T1 : W(B) = XB 7 T2 : annule Résolution du problème de Deadlock : Wait-Die • Wait-Die : Technique non-préemptive (n’interrompt pas) § Si Ti demande un verrouillage accordé à Tj et Ti est plus vieille alors Ti est mise en attente § Si Ti demande un verrouillage accordé à Tj et Ti est plus jeune alors Ti est annulée T1 T2 T1 : R(A) = SA T1 : W(B) = XB T1 : verrouille B et continue T’2 : R(B) = SB T’2 : W(A) = XA T’2 : relance 7 Résolution du problème de Deadlock : Wound-Wait • Wound-Wait : Technique préemptive (interrompt) § Si Ti demande un verrouillage accordé à Tj et Ti est plus vieille alors Ti est annulée § Si Ti demande un verrouillage accordé à Tj et Ti est plus jeune alors Ti est mise en attente 8 Résolution du problème de Deadlock : Wound-Wait • Wound-Wait : Technique préemptive (interrompt) § Si Ti demande un verrouillage accordé à Tj et Ti est plus vieille alors Ti est annulée § Si Ti demande un verrouillage accordé à Tj et Ti est plus jeune alors Ti est mise en attente T1 T1 : R(A) = SA 8 Résolution du problème de Deadlock : Wound-Wait • Wound-Wait : Technique préemptive (interrompt) § Si Ti demande un verrouillage accordé à Tj et Ti est plus vieille alors Ti est annulée § Si Ti demande un verrouillage accordé à Tj et Ti est plus jeune alors Ti est mise en attente T1 T2 T1 : R(A) = SA T2 : R(B) = SB 8 Résolution du problème de Deadlock : Wound-Wait • Wound-Wait : Technique préemptive (interrompt) § Si Ti demande un verrouillage accordé à Tj et Ti est plus vieille alors Ti est annulée § Si Ti demande un verrouillage accordé à Tj et Ti est plus jeune alors Ti est mise en attente T1 T2 T1 : vieille = abandonnée T1 : R(A) = SA T2 : R(B) = SB T1 : W(B) uploads/Litterature/ c018sa-w1-s5-v3.pdf