Θέματα ορθότητας ταυτόχρονων αλγορίθμων σε δομές ευρετηρίου

• Κύριος συγγραφέας: Θεοδωρόπουλος, Κωνσταντίνος
• Άλλοι συγγραφείς: Κοσμαδάκης, Σταύρος
• Έκδοση: 2007
• Θέματα: Ταυτοχρονισμός; Βάσεις δεδομένων; Ορθότητα προγραμμάτων; Concurrency; Databases; Program correctness; 005.1

Η εργασία αυτή αφορά την μελέτη ταυτόχρονων (concurrent) αλγορίθμων σε δομές ευρετηρίου (δευτερεύουσας μνήμης) καθώς και τα μοντέλα ορθότητάς τους. Οι δομές ευρετηρίου που θα μελετήσουμε είναι τα Β-δέντρα κατάλληλα τροποποιημένα έτσι ώστε να μεγιστοποιείται η απόδοσή τους σε περιβάλλον ταυτοχρονισμού . Συγκεκριμένα εκτός από τους δείκτες του Β-δέντρου έxουν προστεθεί και δείκτες που ενώνουν τον έναν κόμβο με τον άλλον στο ίδιο επίπεδο του δέντρου σχηματίζοντας έτσι αλυσίδες. Στην αρχή θα δούμε μερικά φαινόμενα που ανακύπτουν όταν διάφορες διεργασίες εκτελούνται παράλληλα. Τα φαινόμενα αυτά έχουν την βάση τους στην πρόσβαση των διεργασιών σε κοινά δεδομένα από τα οποία εξαρτάται η εκτέλεσή τους. Θα δούμε πως μπορούμε να συγχρονίσουμε τις διεργασίες έτσι ώστε να μην προκύπτουν ανεπιθύμητα φαινόμενα Κατόπιν θα δούμε μερικούς βασικούς ταυτόχρονους αλγορίθμους που αντιπροσωπεύουν την λύση σε μερικά βασικά προβλήματα στην θεωρία ταυτοχρονισμού (concurrency) ,όπως τα consumer-producer problem κ.ά. Στην συνέχεια θα μετακινηθούμε στο πεδίο των αλγορίθμων για δομές ευρετηρίου. Η δομή ευρετηρίου που θα εξετάσουμε είναι το Β-δέντρο. Το δέντρο αυτό αποτελεί την κατεξοχήν επιλογή για τους σχεδιαστές βάσεων δεδομένων για την οργάνωση μεγάλου όγκου πληροφορίας στην δευτερεύουσα μονάδα μνήμης του συστήματος. Η ανάγκη για ταυτοχρονισμό σε αυτήν την δομή είναι επιβεβλημένη για την υποστήριξη πολυχρηστικών βάσεων δεδομένων και άλλων χρήσιμων εφαρμογών. Η αποδοτικότητα των αλγορίθμων μετριέται σε μέγεθος μνήμης για το οποίο έχουν αποκλειστική πρόσβαση έτσι ώστε να συγχρονίζονται μεταξύ τους οι αλγόριθμοι. Θα δούμε διάφορους αλγορίθμους καθώς και έναν δικό μας. Τέλος θα εξετάσουμε την έννοια της ορθότητας σε ταυτόχρονους αλγορίθμους. Θα δούμε διάφορα μοντέλα ορθότητας καθώς και διάφορα κριτήρια. Σε αυτά θα προσθέσουμε και ένα δικό μας κριτήριο το οποίο εξασφαλίζει απλότητα στον σχεδιασμό των αλγορίθμων πολύ μεγαλύτερη απότι προηγούμενα κριτήρια. Η συνεισφορά αυτής της εργασίας έγκειται στα εξής : 1) Στην ανάπτυξη ενός καινούριου αλγορίθμου ο οποίος επιτυγχάνει μεγαλύτερη απόδοση από προηγούμενους λόγω του νέου τρόπου συγχρονισμού που προτείνει. Συγκεριμένα ο συγχρονισμός επιτυγχάνεται όχι μέσω καθολικού αμοιβαίου αποκλεισμού (όπως μέχρι τώρα) αλλά κατά περίπτωση αμοιβαίου αποκλεισμού. 2) Στην ανάπτυξη ενός κριτηρίου ορθότητας που επιτρέπει την απλότητα και την σαφήνεια στην ανάπτυξη ιδιαίτερα αποδοτικών ταυτόχρονων αλγορίθμων. Το κριτήριο λαμβάνει υπόψη του τις καταστάσεις που μπορεί να προκύψουν σε ένα ορισμένο τμήμα κοινής μνήμης και προσφέρει έναν τρόπο να αποκλείσουμε την μετάβαση του συστήματος σε αυτές τις καταστάσεις.