.
Στην επιστήμη των υπολογιστών ιδιαίτερα στους κλάδους του προγραμματισμού, λειτουργικών συστημάτων, μικροεπεξεργαστών και βάσεων δεδομένων (ΒΔ) ο έλεγχος ταυτοχρονισμού διασφαλίζει την ορθότητα των αποτελεσμάτων για ταυτόχρονες ενέργειες/συναλλαγές το ταχύτερο δυνατό. Τα υπολογιστικά συστήματα αποτελούνται από υποσυστήματα. Κάθε υποσύστημα σχεδιάζεται υιοθετώντας κάποιους κανόνες συνέπειας. Όταν τα υποσυστήματα που λειτουργούν ταυτόχρονα αλληλεπιδρούν στέλνοντας μηνύματα το ένα στο άλλο ή διακινώντας δεδομένα ίσως η συνέπεια κάποιου υποσυστήματος να παραβιάζεται από κάποιο άλλο. Ο έλεγχος ταυτοχρονισμού παρέχει κανόνες , μεθόδους και σχεδιαστικές μεθοδολογίες οι οποίες διατηρούν την συνέπεια των υποσυστημάτων τα οποία λειτουργούν ταυτόχρονα όταν αλληλεπιδρούν και επομένως διατηρεί την συνέπεια ολόκληρου του συστήματος. Οι κανόνες της συνέπειας και της ορθότητας συνάδουν με την αποδοτικότητα του συστήματος.
Έλεγχος ταυτοχρονισμού στις Βάσεις Δεδομένων
Ο έλεγχος ταυτοχρονισμού στα Συστήματα Διαχείρισης Βάσεων Δεδομένων (ΣΔΒΔ), σε άλλα Αντικείμενα Συναλλαγής (αντικείμενα με καταστάσεις οι οποίες αλλάζουν και προσπελαύνονται από συναλλαγές βάσεων δεδομένων) και συσχετιζόμενες κατανεμημένες εφαρμογές (π.χ. Grid Computing και Cloud Computing) διασφαλίζει ότι οι συναλλαγές ΒΔ πραγματοποιούνται ταυτόχρονα χωρίς ο ταυτοχρονισμός να παραβιάζει την ακεραιότητα των δεδομένων της βάσης. Μια συναλλαγή στις ΒΔ ορίζεται σαν ένα αντικείμενο το οποίο τηρεί τους κανόνες ACID οι οποίοι περιγράφονται πιο κάτω. Ένα ΣΔΒΔ συνήθως εγγυάται ότι πραγματοποιούνται μόνο σειριοποιήσιμα χρονοπρογράμματα για ορθότητα (εκτός αν η σειριοποιησιμότητα αγνοείται σκόπιμα). Για να διατηρείται η ορθότητα σε περίπτωση εσφαλμένων συναλλαγών στα χρονοπρογράμματα πρέπει να είναι ανακτήσιμα (Η ανακτησιμότητα (recoverability) σημαίνει ότι οι δεσμευμένες συναλλαγές δεν έχουν δεδομένα γραμμένα από ακυρωμένες συναλλαγές (και οι συνέπειες τους δεν υπάρχουν στις καταστάσεις της βάσης δεδομένων). Αφού η σειριοποιησιμότητα είναι εκτεθειμένη σκόπιμα σε πολλές εφαρμογές για καλύτερη εφαρμογή (μόνο σε περιπτώσεις όπου η ορθότητα της εφαρμογής δεν επηρεάζεται), εκθέτοντας την ανακτησιμότητα θα παραβιαζόταν η ακεραιότητα της βάσης αλλά και θα εξέθετε τα αποτελέσματα των συναλλαγών.). Ένα ΣΔΒΔ εγγυάται επίσης ότι δεν χάνεται κανένα αποτέλεσμα συναλλαγής η οποία έχει πάρει commit και δεν παραμένει κανένα αποτέλεσμα συναλλαγής στην σχετική βάση δεδομένων η οποία έχει γίνει abort.
Κανόνες ACID
Κύριο λήμμα: ACID
Ατομικότητα (Atomicity) – Είτε επιτυγχάνουν όλες οι ενέργειες σωστά είτε θα αποτύχουν (αν αποτύχει μια ενέργεια τότε αποτυγχάνει ολόκληρη η συναλλαγή) – πιο απλά μια συναλλαγή είναι αδιαίρετη, ατομική
Συνέπεια (Consistency) – Κάθε συναλλαγή πρέπει να είναι συνεπής όταν αποχωρεί από την βάση δηλαδή να διατηρείται οι προκαθορισμένοι κανόνες της.
Απομόνωση (Isolation) – Οι συναλλαγές δεν μπορούν να παρεμβαίνουν η μία στην άλλη – δηλαδή κάθε συναλλαγή θεωρεί ότι τρέχει μόνη της χωρίς άλλες συναλλαγές μέχρις ότου να τερματιστεί. Η απομόνωση είναι ο κύριος στόχος του έλεγχου ταυτοχρονισμού.
Μονιμότητα (Durability) – Τα αποτελέσματα συναλλαγών που έχουν εξασφαλίσει commit πρέπει να παραμένουν ακόμα μετά από αποτυχίες του συστήματος.
Τεχνικές Ελέγχου Ταυτοχρονισμού
Οι κύριες κατηγορίες τεχνικών ελέγχου ταυτοχρονισμού είναι:
Αισιόδοξη Τεχνική – Καθυστέρηση του ελέγχου της συναλλαγής όσο αφορά την απομόνωση ή την ατομικότητα της μέχρι το τέλος της χωρίς να εμποδίζει καμία από τις ενέργειες της και μετά να την τερματίζει αν οι κανόνες αυτοί παραβιάζονται.
Απαισιόδοξη Τεχνική – Μπλοκάρονται οι ενέργειες της συναλλαγής αν υπάρχει παραβίαση οποιουδήποτε κανόνα.
Ημί – Αισιόδοξη Τεχνική – Μπλοκάρονται ενέργειες σε μερικές περιπτώσεις ενώ καθυστερείται ο έλεγχος των κανόνων στο τέλος μιας συναλλαγής όπως και στην αισιόδοξη τεχνική.
Υπάρχουν πολλές μέθοδοι ελέγχου ταυτοχρονισμού. Οι περισσότερες από αυτές μπορούν να υλοποιηθούν με οποιαδήποτε από τις παραπάνω τεχνικές. Οι κυριότερες μέθοδοι οι οποίες έχουν πολλές παραλλαγές περιλαμβάνουν:
Κλείδωμα δύο Φάσεων (2PL)
Γράφος Σειριοποιησιμότητας
Χρονοσήματα
Commitment Ordering
Έλεγχος Ταυτοχρονισμού Πολλαπλών Εκδοχών
Έλεγχος Ταυτοχρονισμού με Ευρετήρια
Ένας κοινός κύριος στόχος του έλεγχου ταυτοχρονισμού είναι να δημιουργούν σειριοποιήσιμα χρονοπρογράμματα. Η σειριοποιησιμότητα θεωρείται το υψηλότερο επίπεδο απομόνωσης μεταξύ συναλλαγών και το μεγαλύτερο κριτήριο ορθότητας για ταυτόχρονες συναλλαγές. Σε μερικές περιπτώσεις πιο απλές μορφές σειριοποιησιμότητας επιτρέπονται για καλύτερη ταχύτητα του συστήματος, αν η ορθότητα της εφαρμογής δεν παραβιάζεται από την απλούστευση. Σχεδόν όλες οι υλοποιημένες τεχνικές ελέγχου ταυτοχρονισμού πετυχαίνουν σειριοποιησιμότητα προσφέροντας σειριοποιησιμότητα συγκρούσεων, μια ειδική περίπτωση σειριοποιησιμότητας (η άλλη περίπτωση είναι η σειριοποιησιμότητα όψεως) η οποία μπορεί να υλοποιηθεί ανάλογα με την περίσταση.
Ο έλεγχος ταυτοχρονισμού διασφαλίζει επίσης την ιδιότητα της ανακτησιμότητας των χρονοπρογραμμάτων, για διατήρηση ορθότητας όταν οι συναλλαγές δεχτούν abort (το οποίο μπορεί να συμβεί για διαφορετικούς λόγους).
Καθώς τα ΣΔΒΔ γίνονται κατανεμημένα ή συνεργάζονται με κατανεμημένα περιβάλλοντα δημιουργείται η ανάγκη για τεχνικές κατανεμημένου ελέγχου ταυτοχρονισμού. Επιτυγχάνοντας κατανεμημένη σειριοποιησιμότητα και ευρεία σειριοποιησιμότητα προϋποθέτει ειδικές απαιτήσεις οι οποίες τυπικά δεν υιοθετούνται από τοπικές τεχνικές σειριοποιησιμότητας. Η τεχνική Commitment Ordering παρέχει μια αποτελεσματική λύση και για τα δυο (ευρεία και κατανεμημένη σειριοποιησιμότητα).
Αναφορές
Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems, Addison Wesley Publishing Company, 1987, ISBN 0-201-10715-5
Εξωτερικά Links
Database concurrency control research: 20 years of incompetence. Post in dbforums conversation about Commitment ordering on 02-21-2010.
Portland Pattern Repository: Synchronization Strategies
Portland Pattern Repository: Category Concurrency
Database Locking: What it is, Why it Matters and What to do About it
Hellenica World - Scientific Library
Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License
