Μετάβαση στο περιεχόμενο

Γράφος Σειριοποιησιμότητας

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
 Το λήμμα παραθέτει τις πηγές του αόριστα, χωρίς παραπομπές. Βοηθήστε συνδέοντας το κείμενο με τις πηγές χρησιμοποιώντας παραπομπές, ώστε να είναι επαληθεύσιμο.
Το πρότυπο τοποθετήθηκε χωρίς ημερομηνία. Για τη σημερινή ημερομηνία χρησιμοποιήστε: {{χωρίς παραπομπές|19|11|2024}}

Ένας τρόπος ελέγχου αν ένα χρονοπρόγραμμα είναι σειριοποιήσιμο είναι ο γράφος συγκρούσεων ή γράφο προήγησης (precedence graph) ή γράφο σειριοποιησιμότητας (serialization graph). Ο γράφος χρησιμοποιείται στο πλαίσιο του Ελέγχου Ταυτοχρονισμου στις Βασεις δεδομένων. Με τον γράφο σειριοποιησιμότητας μοντελοποιούμε τις συγκρούσεις μέσα σε ένα χρονοπρόγραμμα με ένα γράφο ο οποίος περιέχει:

  • Ένα κόμβο για κάθε συναλλαγή
  • Μια κατευθυνόμενη ακμή από την συναλλαγή Ti στην συναλλαγή Tj, αν μια ενέργεια της Ti συγκρούεται με μια επακόλουθή της, της Tj. Δηλαδή για παράδειγμα αν έχουμε την εξής σύγκρουση R1(A);W2(A) τότε θα σχεδιάσουμε μία ακμή από τον προηγούμενο κόμβο στον επόμενο δηλαδή από το 1 προς το 2.

Το χρονοπρόγραμμα είναι σειριοποιήσιμο συγκρούσεων αν ο γράφος δεν περιέχει κύκλο. Σε αντίθετη περίπτωση δηλαδή αν ο γράφος έχει κύκλο δεν είναι σειριοποιήσιμο συγκρούσεων.

Αλγόριθμος Γράφου Συγκρούσεων

[Επεξεργασία | επεξεργασία κώδικα]

Υπάρχει ένας απλός αλγόριθμος για να προσδιοριστεί αν ένα χρονοπρόγραμμα είναι σειριοποιήσιμο συγκρούσεων. Στην πράξη οι περισσότερες μέθοδοι ελέγχου σειριοποιησιμότητας δεν ελέγχουν αν ένα χρονοπρόγραμμα είναι σειριοποιήσιμο συγκρούσεων αλλά αναπτύσσοντας πρωτόκολλα ή κανόνες εγγυούνται ότι ένα χρονοπρόγραμμα είναι σειριοποιήσιμο. Δύο τέτοιες μέθοδοι είναι το Κλείδωμα δύο Φάσεων (2PL – 2 Phase Locking) και μια παραλλαγή αυτού ο αυστηρός 2PL.

Ο αλγόριθμος χρησιμοποιείται για να ελεγθεί αν ένα χρονοπρόγραμμα είναι σειριοποιήσιμο συγκρούσεων. Θεωρούμε μόνο τις πράξεις ανάγνωση_αντικειμένου και εγγραφή_αντικειμένου για την κατασκευή του γράφου συγκρούσεων.

Ο αλγόριθμος σχεδίασης του γράφου συγκρούσεων είναι η εξής:

  1. Για κάθε συναλλαγή Τi η οποία συμμετέχει στο χρονοπρόγραμμα S δημιουργούμε έναν κόμβο με όνομα το όνομα της συναλλαγής Τi
  2. Για κάθε περίπτωση στο S όπου η Tj εκτελεί μια πράξη ανάγνωση _αντικ(Χ) μετά από μία πράξη εγγραφή_αντικ(Χ) που εκτελείται από την Ti δημιούργησε μία ακμή (Ti--> Tj) στον γράφο.
  3. Για κάθε περίπτωση στο S όπου η Tj εκτελεί μια πράξη εγγραφή_αντικ(Χ) μετά από μία πράξη ανάγνωση _αντικ(Χ) που εκτελείται από την Ti δημιούργησε μία ακμή (Ti--> Tj) στον γράφο.
  4. Για κάθε περίπτωση στο S όπου η Tj εκτελεί μια πράξη εγγραφή_αντικ(Χ) μετά από μία πράξη εγγραφή_αντικ(Χ) που εκτελείται από την Ti δημιούργησε μία ακμή (Ti--> Tj) στον γράφο.
  5. Το χρονοπρόγραμμα S είναι σειριοποιήσιμο αν ο γράφος σειριοποιησιμότητας δεν έχει κύκλους. Αν ο γράφος σειριοποιησιμότητας έχει κύκλους, τότε δεν μπορούμε να βγάλουμε συμπέρασμα για το αν το χρονοπρόγραμμα S είναι ή όχι σειριοποιήσιμο και η σειριοποιησιμότητα θα πρέπει να ελεγθεί με άλλες τεχνικές.

Ο γράφος σειριοποιησιμότητας κατασκευάζεται σύμφωνα με τον παραπάνω αλγόριθμο. Αν δεν υπάρχει κύκλος στο γράφο τότε το χρονοπρόγραμμα είναι σειριοποιήσιμο. Κύκλος σε έναν κατευθυνόμενο γράφο είναι μία ακολουθία ακμών με την ιδιότητα ότι ο αρχικός κόμβος ενός μονοπατιού είναι ίδιος με τον τελικό.

Ισοδύναμο Σειριακό Χρονοπρόγραμμα

[Επεξεργασία | επεξεργασία κώδικα]

Στον γράφο σειριοποιησιμότητας μια ακμή από τον κόμβο Ti στον κόμβο Tj σημαίνει ότι η συναλλαγή Ti πρέπει να προηγείται της Tj σε κάθε σειριακό χρονοπρόγραμμα που είναι ισοδύναμο με το χρονοπρόγραμμα S, διότι κάθε ζεύγος συγκρουόμενων πράξεων εμφανίζεται στο χρονοπρόγραμμα με την συγκεκριμένη σειρά. Αν στο γράφο σειριοποιησιμότητας δεν υπάρχει κύκλος τότε μπορούμε να δημιουργήσουμε ένα ισοδύναμο σειριακό χρονοπρόγραμμα S΄ το οποίο θα είναι ισοδύναμο με το S διατάσσοντας με τον ακόλουθο τρόπο τις συναλλαγές που συμμετέχουν στο S: όταν υπάρχει μία ακμή στο γράφο σειριοποιησιμότητας από τον κόμβο Ti στον Tj, η συναλλαγή Ti πρέπει να προηγείται της Tj στο ισοδύναμο σειριακό χρονοπρόγραμμα S΄.

Παράδειγμα Έστω το χρονοπρόγραμμα S: R1(X) R2(X) R3(Y) W2(X) W1(Z) W2(Y) R4(X) W2(Z). Σχεδιάζουμε τον γράφο σειριοποιησιμότητας:

Στον παραπάνω γράφο δεν υπάρχει κανένας κύκλος συνεπώς το αντίστοιχο πρόγραμμα είναι σειριοποιήσιμο. Τα ισοδύναμα σειριακά προγράμματα είναι τα:

  1. Τ1 -> Τ3 -> Τ2 -> Τ4
  2. Τ3 -> Τ1 -> Τ2 -> Τ4.

Παραδείγματα εφαρμογής αλγορίθμου

[Επεξεργασία | επεξεργασία κώδικα]

Παράδειγμα 1 - Εφαρμογή Αλγορίθμου

[Επεξεργασία | επεξεργασία κώδικα]

S1: R1(A),R1(B),W1(A),R2(A),R1(C),W1(C),R3(C),W2(A),R3(B),W3(A)

1. Δημιουργούμε 3 κόμβους με ονόματα Τ1, Τ2, Τ3 όσες και οι συναλλαγές του χρονοπρογράμματος S1.

2. Για κάθε περίπτωση στο S όπου η Tj εκτελεί μια πράξη ανάγνωση _αντικ(Χ) μετά από μία πράξη εγγραφή_αντικ(Χ) που εκτελείται από την Ti δημιούργησε μία ακμή (Ti--> Tj) στον γράφο.

  • Για το αντικείμενο Α έχουμε: W1(Α) και μετά ανάγνωση R2(Α) άρα ακμή Τ1->Τ2.
  • Για το αντικείμενο B δεν υπάρχει κάποια σύγκρουση για αυτόν τον κανόνα.
  • Για το αντικείμενο C έχουμε: W1(C) και μετά ανάγνωση R3(C) άρα ακμή Τ1->Τ3

3. Για κάθε περίπτωση στο S όπου η Tj εκτελεί μια πράξη εγγραφή_αντικ(Χ) μετά από μία πράξη ανάγνωση _αντικ(Χ) που εκτελείται από την Ti δημιούργησε μία ακμή (Ti--> Tj) στον γράφο.

  • Για το αντικείμενο Α έχουμε: α) R1(Α) και μετά εγγραφή W2(Α) άρα ακμή Τ1->Τ2 η οποία υπάρχει ήδη λόγω άλλης σύγκρουσης άρα δεν χρειάζεται να την ξανασχεδιάσουμε και β) R1(Α) και μετά εγγραφή W3(Α) άρα ακμή Τ1->Τ3 η οποία υπάρχει ήδη λόγω άλλης σύγκρουσης άρα δεν χρειάζεται να την ξανασχεδιάσουμε.
  • Για το αντικείμενο B δεν υπάρχει κάποια σύγκρουση για αυτόν τον κανόνα.
  • Για το αντικείμενο C υπάρχει κάποια σύγκρουση για αυτόν τον κανόνα.

4. Για κάθε περίπτωση στο S όπου η Tj εκτελεί μια πράξη εγγραφή_αντικ(Χ) μετά από μία πράξη εγγραφή_αντικ(Χ) που εκτελείται από την Ti δημιούργησε μία ακμή (Ti--> Tj) στον γράφο.

  • Για το αντικείμενο Α έχουμε: α) W1(Α) και μετά εγγραφή W2(Α) άρα ακμή Τ1->Τ2 η οποία υπάρχει ήδη λόγω άλλης σύγκρουσης άρα δεν χρειάζεται να την ξανασχεδιάσουμε, β) W1(Α) και μετά εγγραφή W3(Α) άρα ακμή Τ1->Τ3 η οποία υπάρχει ήδη λόγω άλλης σύγκρουσης άρα δεν χρειάζεται να την ξανασχεδιάσουμε και γ) W2(Α) και μετά εγγραφή W3(Α) άρα ακμή Τ2->Τ3.
  • Για το αντικείμενο B δεν υπάρχει κάποια σύγκρουση για αυτόν τον κανόνα.
  • Για το αντικείμενο C υπάρχει κάποια σύγκρουση για αυτόν τον κανόνα.

5. Στον παρακάτω γράφο δεν υπάρχει κανένας κύκλος συνεπώς το χρονοπρόγραμμα S1 είναι σειριοποιήσιμο.

  • Ο γράφος σειριοποιησιμότητας θα έχει την εξής μορφή: (Η παρακάτω εικόνα έχει αντίστροφη την ακμή Τ3->Τ1, καθώς πρέπει να είναι Τ1->Τ3, και θα διορθωθεί σύντομα.)

  • Το ισοδύναμο σειριακό πρόγραμμα είναι το: Τ1 -> Τ2 -> Τ3.

Παράδειγμα 2 - Εφαρμογή Αλγορίθμου

[Επεξεργασία | επεξεργασία κώδικα]

S2: W2(Ζ), R5(Χ), W5(Ζ), W5(Χ), W4(Ζ), W4(Χ), R2(Χ), R3(Ζ), W3(Υ), W4(Υ)

1. Δημιουργούμε 4 κόμβους με ονόματα Τ2, Τ3, Τ4, Τ5 όσες και οι συναλλαγές του χρονοπρογράμματος S2.

2. Για κάθε περίπτωση στο S όπου η Tj εκτελεί μια πράξη ανάγνωση _αντικ(Χ) μετά από μία πράξη εγγραφή_αντικ(Χ) που εκτελείται από την Ti δημιούργησε μία ακμή (Ti--> Tj) στον γράφο.

  • Για το αντικείμενο Ζ έχουμε: α) W2(Ζ) και μετά ανάγνωση R3(Ζ) άρα ακμή Τ2->Τ3 β) W5(Ζ) και μετά ανάγνωση R3(Ζ) άρα ακμή Τ5->Τ3 γ) W4(Ζ) και μετά ανάγνωση R3(Ζ) άρα ακμή Τ4->Τ3
  • Για το αντικείμενο Χ έχουμε: α) W5(Χ) και μετά ανάγνωση R2(Χ) άρα ακμή Τ5->Τ2 β) W4(Χ) και μετά ανάγνωση R2(Χ) άρα ακμή Τ4->Τ2
  • Για το αντικείμενο Υ δεν υπάρχει κάποια σύγκρουση για αυτόν τον κανόνα.

3.Για κάθε περίπτωση στο S όπου η Tj εκτελεί μια πράξη εγγραφή_αντικ(Χ) μετά από μία πράξη ανάγνωση _αντικ(Χ) που εκτελείται από την Ti δημιούργησε μία ακμή (Ti--> Tj) στον γράφο.

  • Για το αντικείμενο X έχουμε: R5(Ζ) και μετά εγγραφή W4(Ζ) άρα ακμή Τ5->Τ4
  • Για το αντικείμενο Z δεν υπάρχει κάποια σύγκρουση για αυτόν τον κανόνα.
  • Για το αντικείμενο Υ δεν υπάρχει κάποια σύγκρουση για αυτόν τον κανόνα.

4. Για κάθε περίπτωση στο S όπου η Tj εκτελεί μια πράξη εγγραφή_αντικ(Χ) μετά από μία πράξη εγγραφή_αντικ(Χ) που εκτελείται από την Ti δημιούργησε μία ακμή (Ti--> Tj) στον γράφο.

  • Για το αντικείμενο Ζ έχουμε: α) W2(Ζ) και μετά εγγραφή W5(Ζ) άρα ακμή Τ2->Τ5 β) W2(Ζ) και μετά ανάγνωση W4(Ζ) άρα ακμή Τ2->T4.
  • Για το αντικείμενο Χ έχουμε: W5(Χ) και μετά εγγραφή W4(Χ) άρα ακμή Τ5->Τ4 η οποία υπάρχει ήδη λόγω άλλης σύγκρουσης άρα δεν χρειάζεται να την ξανασχεδιάσουμε.
  • Για το αντικείμενο Y έχουμε: W3(Χ) και μετά εγγραφή W4(Χ) άρα ακμή Τ3->Τ4.

5. Το χρονοπρόγραμμα S2 δεν είναι σειριοποιήσιμο διότι υπάρχουν κατευθυνόμενες ακμές οι οποίες σχηματίζουν κύκλο. Μερικοί κύκλοι στον γράφο είναι 1) Τ2, Τ4 2) Τ2, Τ5 3)Τ2, Τ3, Τ4.

Ο γράφος σειριοποιησιμοτητας θα έχει την εξής μορφή (όπου παρατηρούμε τους κύκλους που σχηματίζονται):

Δεν έχει ισοδύναμα σειριακά χρονοπρογράμματα διότι έχει κύκλους.

[Επεξεργασία | επεξεργασία κώδικα]
Ανακτήθηκε από "https://el.wikipedia.org/w/index.php?title=Γράφος_Σειριοποιησιμότητας&oldid=10273571"