Στους τομείς των Βάσεων Δεδομένων (ΒΔ) και την Επεξεργασία Συναλλαγών (διαχείριση συναλλαγών) ένα χρονοπρόγράμμα ενός συστήματος είναι ένα αφηρημένο μοντέλο που περιγράφει την εκτέλεση συναλλαγών που τρέχουν στο σύστημα. Συχνά είναι μια λίστα από ενέργειες οι οποίες αναπαρίστανται με χρονική σειρά και εκτελούνται από ένα σύνολο συναλλαγών οι οποίες με την σειρά τους εκτελούνται όλες μαζί στο σύστημα. Παραδείγματα αυτών των ενεργειών είναι τα read, write, abort , commit, αίτηση κλειδώματος, κλείδωμα κοκ. Δεν λαμβάνουν μέρος όλα τα είδη ενεργειών των συναλλαγών σε ένα χρονοπρόγραμμα και μόνο προεπιλεγμένα είδη ενεργειών συμπεριλαμβάνονται, που χρειάζονται για να περιγράψουν συγκεκριμένα φαινόμενα. Χρονοπρογράμματα και ιδιότητες χρονοπρογραμμάτων είναι απαραίτητα στοιχεία για τον έλεγχο ταυτοχρονισμού σε μια ΒΔ.
Περιγραφή ενός Χρονοπρογράμματος
Το παρακάτω είναι ένα παράδειγμα χρονοπρογράμματος:
\( {\displaystyle D={\begin{bmatrix}T1&T2&T3\\R(X)&&\\W(X)&&\\Com.&&\\&R(Y)&\\&W(Y)&\\&Com.&\\&&R(Z)\\&&W(Z)\\&&Com.\end{bmatrix}}} \)
Σε αυτό το παράδειγμα ο οριζόντιος άξονας αναπαριστά τις διαφορετικές συναλλαγές στο χρονοπρόγραμμα D. Ο κάθετος άξονας αναπαριστά την χρονική σειρά των εργασιών. Το χρονοπρόγραμμα D αποτελείται από τρεις συναλλαγές T1, T2, T3. Το χρονοπρόγραμμα περιγράφει τις ενέργειες των συναλλαγών όπως τις βλέπουμε σε ένα ΣΔΒΔ. Πρώτα η T1 διαβάζει και γράφει το αντικείμενο Χ και μετά κάνει commit (η συναλλαγή τερματίζει επιτυχώς). Η Τ2 διαβάζει και γράφει το αντικείμενο Υ και μετά κάνει commit και η Τ3 διαβάζει και γράφει το αντικείμενο Ζ και μετά κάνει commit. Αυτό είναι ένα παράδειγμα σειρακού χρονοπρογράμματος επειδή οι ενέργειες των τριών συναλλαγών δεν περιπλέκονται μεταξύ τους.
Το χρονοπρόγραμμα D αναπαρίσταται από ένα πίνακα (αντί από μια λίστα) και αυτό γίνεται για διευκόλυνση του αναγνώστη να κοιτάζει κάθε συναλλαγή με μια ματιά. Αυτή η σημείωση χρησιμοποιείται στο άρθρο παρακάτω. Ένας πιο κοινός τρόπος να περιγράψεις αυτό το χρονοπρόγραμμα είναι με την χρήση λίστας όπως φαίνεται παρακάτω:
D = R1(X) W1(X) Com1 R2(Y) W2(Y) Com2 R3(Z) W3(Z) Com3
Συνήθως για την αιτιολόγηση του ελέγχου ταυτοχρονισμού στις ΒΔ, μία ενέργεια χαρακτηρίζεται σαν ατομική όταν προκύπτει σε μια χρονική στιγμή (χωρίς διάρκεια). Όταν αυτό δεν είναι ικανοποιητικό, χρονικά σημεία αρχής και τέλους και πιθανότητα άλλα σημεία γεγονότων προσδιορίζονται (σπανίως βέβαια). Οι ενέργειες που εκτελούνται έχουν πάντα συγκεκριμένο χρόνο εκτέλεσης (π.χ. ακριβής χρόνος μέχρι την ολοκλήρωση τους), όμως για την αιτιολόγηση του ελέγχου ταυτοχρονισμού μόνο η χρονική προτεραιότητα έχει σημασία. Επιπρόσθετα σε πολλές περιπτώσεις οι πριν/μετά σχέσεις μεταξύ δυο ενεργειών δεν έχουν σημασία και δεν ορίζονται, αφού ορίζονται για άλλους συνδυασμούς ενεργειών.
Γενικά οι ενέργειες των συναλλαγών σε ένα χρονοπρόγραμμα μπορούν να περιπλέκουν (εκτελούνται ταυτόχρονα), καθώς η χρονική σειρά των λειτουργιών σε κάθε συναλλαγή δεν αλλάζει όπως προϋποθέτει το πρόγραμμα της συναλλαγής. Αφού δεν έχει μόνο σημασία η χρονική σειρά όλων των συναλλαγών, πρέπει να οριστούν κιόλας, έτσι ορίζεται ένα χρονοπρόγραμμα. Γενικά μια μερική διαμέριση μεταξύ των ενεργειών αντί μιας ολικής διαμέρισης όπου η διαμέριση για κάθε συνδυασμό διευκρινίζεται όπως σε μια λίστα ενεργειών. Επίσης σε γενικές περιπτώσεις κάθε συναλλαγή μπορεί να αποτελείται από πολλές διεργασίες και μπορεί να αναπαρίσταται από μερική διαμέριση διεργασιών παρά από μια ολική διαμέριση. Έτσι γενικά ένα χρονοπρόγραμμα είναι η μερική διαμέριση ενεργειών που περιέχουν (ενσωματώνουν) τις μερικές διαμερίσεις όλων των συναλλαγών τους.
Η χρονική σειρά μεταξύ δυο ενεργειών μπορεί να αναπαρασταθεί από ένα ζεύγος αυτών των ενεργειών (π.χ. η ύπαρξη ενός ζεύγους (OP1,OP2) σημαίνει ότι η OP1 είναι πάντα πριν από την ενέργεια OP2), και ένα χρονοπρόγραμμα είναι ένα σύνολο τέτοιων ορισμένων ζευγών. Ένα τέτοιο σύνολο, δηλαδή ένα χρονοπρόγραμμα μπορεί να αναπαρασταθεί από ένα μη κυκλικό κατευθυνόμενο γράφο με τις ενέργειες σαν κόμβους και την χρονική σειρά σαν ακμές (δεν επιτρέπονται κύκλοι αφού κύκλος σημαίνει ότι μια λειτουργία μπορεί να γίνει και πριν αλλά και μετά από μια άλλη, που αντιτίθεται με την αντίληψη μα για τον χρόνο). Σε πολλές περιπτώσεις μια γραφική αναπαράσταση τέτοιων γράφων χρησιμοποιείται για να αναπαραστήσει ένα χρονοπρόγραμμα.
Τύποι χρονοπρογραμμάτων
Σειριακά
Οι συναλλαγές εκτελούνται μη περιπλεγμένα (βλέπε παράδειγμα παραπάνω), δηλαδή σειριακό χρονοπρόγραμμα είναι ένα χρονοπρόγραμμα στο οποίο καμία συναλλαγή δεν αρχίζει πριν τελειώσει μια συναλλαγή η οποία ήδη τρέχει.
Σειριοποιήσιμο
Ένα χρονοπρόγραμμα που είναι ισοδύναμο (ως προς το αποτέλεσμα) με ένα σειριακό χρονοπρόγραμμα έχει την ιδιότητα σειριοποιησιμότητας.
Στο χρονοπρόγραμμα Ε η σειρά με την οποία εκτελούνται οι πράξεις δεν είναι ίδια όπως το D αλλά έχει τα ίδια αποτελέσματα με το D.
\( {\displaystyle E={\begin{bmatrix}T1&T2&T3\\R(X)&&\\&R(Y)&\\&&R(Z)\\W(X)&&\\&W(Y)&\\&&W(Z)\\Com.&Com.&Com.\end{bmatrix}}} \)
Συγκρούσεις
Δύο οι περισσότερες ενέργειες καταλήγουν σε σύγκρουση αν:
Οι ενέργειες ανήκουν σε διαφορετικές συναλλαγές
Τουλάχιστον μια ενέργεια είναι write
Οι ενέργειες αυτές προσπελαύνουν το ίδιο αντικείμενο.
Το ακόλουθο σύνολο ενεργειών οδηγεί σε σύγκρουση:
T1:R(X), T2:W(X), T3:W(X)
Ενώ το ακόλουθο σύνολο ενεργειών δεν οδηγεί σε σύγκρουση:
T1:R(X), T2:R(X), T3:R(X)
T1:R(X), T2:W(Y), T3:R(X)
Ισοδύναμα Συγκρούσεων
Τα χρονοπρογράμματα S1, S2 μπορούμε να πούμε ότι είναι ισοδύναμα συγκρούσεων αν ισχύουν τα ακόλουθα:
Και τα δυο χρονοπρογράμματα περιπλέκουν το ίδιο σύνολο από συναλλαγές
Η σειρά συγκρουόμενων ενεργειών στα χρονοπρογράμματα S1 και S2 είναι ίδια .
Σειριοποιησιμότητα Συγκρούσεων
Ένα χρονοπρόγραμμα είναι σειριοποιήσιμο συγκρούσεων όταν το χρονοπρόγραμμα είναι ισοδύναμο συγκρούσεων με ένα ή περισσότερα σειριακά χρονοπρογράμματα.
Μια αλλά εκδοχή για την σειριοποιησιμότητα συγκρούσεων είναι ότι ένα χρονοπρόγραμμα είναι σειριοποιήσιμο συγκρούσεων αν και μόνο αν υπάρχει ακυκλικός γράφος σειριοποιησιμότητας για το χρονοπρόγραμμα.
G \( {\displaystyle G={\begin{bmatrix}T1&T2\\R(A)&\\&R(A)\\W(B)&\\Com.&\\&W(A)\\&Com.\\&\end{bmatrix}}} \)
Το οποίο είναι ισοδύναμο συγκρούσεων με το σειριακό χρονοπρόγραμμα <Τ1,Τ2> αλλά όχι με το <T2,T1>.
Ισοδυναμία Όψεως
Δυο χρονοπρογράμματα S1, S2 είναι ισοδύναμα όψεως όταν ισχύουν οι ακόλουθες συνθήκες:
Τα S1 και S2 περιέχουν το ίδιο σύνολο δοσοληψιών και τις ίδιες πράξεις των συγκεκριμένων δοσοληψιών
Για κάθε στοιχείο Χ, αν η Τi διαβάζει την αρχική του τιμή στο S1, πρέπει να διαβάζει επίσης την αρχική τιμή στο S2
Για κάθε πράξη Ri(X) στο S1 μετά από μια πράξη Wj(X) πρέπει να ισχύει η ίδια συνθήκη και στο S2.
Αν η πράξη Wi(Y) στο S1 είναι η τελευταία πράξη που τροποποιεί το Y τότε πρέπει να ισχύει η ίδια συνθήκη και στο S2.
Σειριοποιησιμότητα Όψεως
Ένα χρονοπρόγραμμα είναι σειριοποιήσιμο όψεως αν είναι ισοδύναμο όψεως με μερικά σειριακά χρονοπρογράμματα. Εξ’ ορισμού όλα τα σειριοποιήσιμα συγκρούσεως είναι σειριοποιήσιμα όψεως.
\( {\displaystyle G={\begin{bmatrix}T1&T2\\R(A)&\\&R(A)\\W(B)&\\\end{bmatrix}}} \)
Το παραπάνω παράδειγμα (το οποίο είναι το ίδιο για το οποίο μιλήσαμε στην σειριοποιησιμότητα συγκρούσεων) είναι τόσο σειριοποιήσιμο συγκρούσεων όσο και σειριοποιήσιμο όψεως. Υπάρχουν βέβαια χρονοπρογράμματα τα οποία είναι σειριοποιήσιμα όψεως αλλά όχι σειριοποιήσιμα συγκρούσεων, αυτά τα χρονοπρογράμματα συνήθως έχουν μια συναλλαγή η οποία γράφει ένα αντικείμενο χωρίς να το διαβάζει (blind write):
\( {\displaystyle H={\begin{bmatrix}T1&T2&T3\\R(A)&&\\&W(A)&\\&Com.&\\W(A)&&\\Com.&&\\&&W(A)\\&&Com.\\&&\end{bmatrix}}} \)
Το παραπάνω παράδειγμα δεν είναι σειριοποιήσιμο συγκρούσεων αλλά είναι σειριοποιήσιμο όψεως μια και είναι σειριακό χρονοπρόγραμμα ισοδύναμο όψεως <T1, T2, T3>.
Ανακτησιμότητα
Οι συναλλαγές κάνουν commit μόνο αφού όλες οι συναλλαγές οι οποίες έχουν αλλάξει έχουν διαβάσει το commit.
\( {\displaystyle F={\begin{bmatrix}T1&T2\\R(A)&\\W(A)&\\&R(A)\\&W(A)\\Com.&\\&Com.\\&\end{bmatrix}}F2={\begin{bmatrix}T1&T2\\R(A)&\\W(A)&\\&R(A)\\&W(A)\\Abort&\\&Abort\\&\end{bmatrix}}} \)
Αυτά τα χρονοπρογράμματα είναι ανακτήσιμα. Το F είναι ανακτήσιμο επειδή η Τ1 κάνει commit πριν την Τ2 και αυτό κάνει το διάβασμα ορθό. Έπειτα η Τ2 κάνει commit. Σε περίπτωση που η Τ1 κάνει abort τότε και η Τ2 κάνει abort επειδή το αντικείμενο που διαβάζει από το Α δεν είναι σωστό. Και στις δυο περιπτώσεις υπάρχει συνέπεια.
Μη – ανακτήσιμο
Αν μια συναλλαγή Τ1 κάνει abort και η συναλλαγή Τ2 που βασίζεται πάνω στην Τ1 κάνει commit τότε έχουμε ένα μη ανακτήσιμο χρονοπρόγραμμα.
\( {\displaystyle G={\begin{bmatrix}T1&T2\\R(A)&\\W(A)&\\&R(A)\\&W(A)\\&Com.\\Abort&\\&\end{bmatrix}}} \)
Σε αυτό το παράδειγμα το G χρονοπρόγραμμα είναι μη – ανακτήσιμο επειδή η Τ2 διάβασε την Τ1 η οποία δεν έγινε commit και έτσι έχουμε μια εσφαλμένη Τ2 αφού μετά μαθαίνουμε ότι η Τ1 έχει γίνει abort.
Αποφυγή διαδοχικών abort (rollbacks)
Ένα abort σε μια συναλλαγή μπορεί να οδηγήσει σε πολλά περισσότερα. Μια στρατηγική για να αποφευχθεί αυτό είναι να μην επιτρέπεται από μια συναλλαγή να διαβάζει συναλλαγές οι οποίες δεν έχουν γίνει commit από το ίδιο χρονοπρόγραμμα. Το ακόλουθο παράδειγμα είναι το ίδιο με το παραπάνω όταν αναφέραμε την ανακτησιμότητα:
\( {\displaystyle F={\begin{bmatrix}T1&T2\\R(A)&\\W(A)&\\&R(A)\\&W(A)\\Com.&\\&Com.\\&\end{bmatrix}}F2={\begin{bmatrix}T1&T2\\R(A)&\\W(A)&\\&R(A)\\&W(A)\\Abort&\\&Abort\\&\end{bmatrix}}} \)
Σε αυτό το παράδειγμα παρόλο που η F2 είναι ανακτήσιμη δεν μπορεί να αποφύγει τα διαδοχικά aborts. Μπορούμε να δούμε αν κάνει abort η Τ1 τότε και η Τ2 θα πρέπει να γίνει abort για να διατηρηθεί η ορθότητα.
Το παρακάτω είναι ένα ανακτήσιμο χρονοπρόγραμμα το οποίο αποφεύγει διαδοχικά abort. Όμως χάνεται το γράψιμο της Τ1.
\( {\displaystyle F3={\begin{bmatrix}T1&T2\\&R(A)\\R(A)&\\W(A)&\\&W(A)\\Abort&\\&Commit\\&\end{bmatrix}}} \)
Η τεχνική αποφυγής διαδοχικών abort αλλά όχι απαραίτητη για χρονοπρογράμματα έτσι ώστε να είναι ανακτήσιμα.
Strict
Ένα χρονοπρόγραμμα είναι strict, έχει την ιδιότητα strictness, αν για οποιαδήποτε από τις δυο συναλλαγές Τ1, Τ2 αν μια ενέργεια διαβάσματος της Τ1 οδηγήσει σε σύγκρουση με την Τ2 (είτε με διάβασμα είτε με γράψιμο), τότε το commit της Τ1 επίσης οδηγεί σε σύγκρουση με την ενέργεια Τ2.
Οποιοδήποτε strict χρονοπρόγραμμα είναι μη – διαδοχικών abort, αλλά όχι το αντίθετο. Η ιδιότητα αυτή είναι αποτελεσματική στην ανακτησιμότητα και αποτρέπει αποτυχίες στην βάση δεδομένων.
Ιεραρχία μεταξύ σειριοποιήσιμο κλάσεων
Η παρακάτω διάταξη υποκλάσεων δείχνει την ιεραρχία μεταξύ σειριοποιήσιμων κλάσεων.
Serial ⊂ commitment-ordered ⊂ conflict-serializable ⊂ view-serializable ⊂ all schedules
Serial ⊂ strict ⊂ avoids cascading aborts ⊂ recoverable ⊂ all schedules
Το διάγραμμα Venn επεξηγεί τις παραπάνω διατάξεις γραφικά.
Αναφορές
Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems, Addison Wesley Publishing Company, 1987, ISBN 0-201-10715-5
Gerhard Weikum, Gottfried Vossen: Transactional Information Systems, Elsevier, 2001, ISBN 1-55860-508-8
Hellenica World - Scientific Library
Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License
