ΑΠΟΦΥΓΗ ΑΝΑΜΟΝΗΣ ΣΤΟΝ ΣΥΝΤΟΝΙΣΜΟ ΚΑΙ ΣΤΗΝ ΕΠΙΚΟΙΝΩΝΙΑ ΠΟΛΥΕΠΕΞΕΡΓΑΣΤΙΚΩΝ ΣΥΣΤΗΜΑΤΩΝ. ΑΛΓΟΡΙΘΜΙΚΑ ΘΕΜΑΤΑ

Abstract

Η ΔΙΑΤΡΙΒΗ ΑΥΤΗ ΠΑΡΟΥΣΙΑΖΕΙ ΝΕΕΣ ΥΛΟΠΟΙΗΣΕΙΣ ΕΛΕΥΘΕΡΕΣ ΑΝΑΜΟΝΗΣ ΒΑΣΙΚΩΝ ΚΟΙΝΩΝ ΔΙΑΜΟΙΡΑΖΟΜΕΝΩΝ ΑΝΤΙΚΕΙΜΕΝΩΝ ΔΕΔΟΜΕΝΩΝ ΠΟΥ ΧΡΗΣΙΜΟΠΟΙΟΥΝΤΑΙ ΕΥΡΕΩΣ ΓΙΑ ΤΟ ΣΥΝΤΟΝΙΣΜΟ ΔΙΑΔΙΚΑΣΙΩΝ. ΟΙ ΥΛΟΠΟΙΗΣΕΙΣ ΑΥΤΕΣ ΕΙΝΑΙ ΠΙΟ ΑΠΟΔΟΤΙΚΕΣ ΑΠΟ ΤΙΣ ΠΡΟΗΓΟΥΜΕΝΕΣ ΚΑΙ ΒΑΣΙΖΟΝΤΑΙ ΣΕ ΝΕΕΣ ΑΛΓΟΡΙΘΜΙΚΕΣ ΤΕΧΝΙΚΕΣ, ΟΡΙΣΜΕΝΕΣ ΑΠΟ ΤΙΣ ΟΠΟΙΕΣ ΕΧΟΥΝ ΗΔΗ ΧΡΗΣΙΜΟΠΟΙΗΘΕΙ ΑΠΟ ΑΛΛΟΥΣ ΕΡΕΥΝΗΤΕΣ ΣΤΗΝ ΕΙΣΑΣΓΩΓΗ ΝΕΩΝ ΑΠΟΔΟΤΙΚΩΝ ΜΗΧΑΝΙΣΜΩΝ ΣΥΓΧΡΟΝΙΣΜΟΥ. ΠΙΟ ΣΥΓΚΕΚΡΙΜΕΝΑ, Η ΔΙΑΤΡΙΒΗ ΠΑΡΟΥΣΙΑΖΕΙ (1) ΜΙΑ ΝΕΑ ΑΛΓΟΡΙΘΜΙΚΗ ΧΩΡΙΣ ΑΝΑΜΟΝΗ ΥΛΟΠΟΙΗΣΗ ΚΑΤΑΧΩΡΗΤΗ ΟΠΟΥ Η ΔΙΑΔΙΚΑΣΙΑ ΓΡΑΦΕΑΣ ΕΧΕΙ ΠΕΡΙΟΡΙΣΜΟ ΣΤΟ ΝΑ ΑΛΛΑΖΕΙ ΤΗΝ ΤΙΜΗ ΕΝΟΣ ΜΟΝΟ ΔΥΑΔΙΚΟΥ ΨΗΦΙΟΥ ΣΕ ΚΑΘΕ ΠΡΑΞΗ ΕΓΓΡΑΦΗΣ. (2) ΝΕΕΣ ΥΛΟΠΟΙΗΣΕΙΣ ΕΛΕΥΘΕΡΗΣ ΑΝΑΜΟΝΗΣ ΚΑΙ ΓΡΑΜΜΙΚΗΣ ΠΟΛΥΠΛΟΚΟΤΗΤΑΣ ΣΥΝΘΕΤΟΥ ΚΑΤΑΧΩΡΗΤΗ ΕΝΟΣ ΑΝΑΓΝΩΣΤΗ. ΕΝΑΣ ΣΥΝΘΕΤΟΣ ΚΑΤΑΧΩΡΗΤΗΣ ΥΠΟΣΤΗΡΙΖΕΙ ΕΝΕΡΓΕΙΕΣ ΑΝΑΓΝΩΣΗΣ ΠΟΥ ΕΠΙΣΤΡΕΦΟΥΝ ΣΤΙΓΜΙΟΤΥΠΑ ΤΩΝ ΤΜΗΜΑΤΩΝ ΤΟΥ. (3) ΕΝΑΝ ΠΙΘΑΝΟΤΙΚΟ ΑΛΓΟΡΙΘΜΟ ΧΩΡΙΣ ΑΝΑΜΟΝΗ ΓΙΑ ΤΟ ΠΡΟΒΛΗΜΑ ΤΟΥ ΟΝΟΜΑΤΙΣΜΟΥ ΔΙΑΔΙΚΑΣΙΩΝ. ΣΤΟ ΠΡΟΒΛΗΜΑ ΤΟΥ ΟΝΟΜΑΤΙΣΜΟΥ N ΤΑΥΤΟΧΡΟΝΕΣ ΔΙΑΔΙΚΑΣΙΕΣ ΠΡΟΣΠΑΘΟΥΝ ΝΑ ΛΑΒΟΥΝ ΤΑΥΤΟΤΗΤΕΣ ΑΠΟ ΤΟ ΜΙΚΡΟΤΕΡΟ ΔΥΝΑΤΟ ΠΕΔΙΟ ΤΙΜΩΝ (ΚΑΤΑ ΠΡΟΤΙΜΗΣΗ {1,...,N}). (4) ΜΙΑ ΝΕΑ ΠΡΟΣΕΓΓΙΣΗ ΣΤΟ ΠΡΟΒΛΗΜΑ ΤΟΥ ΑΥΤΟΣΤΑΘΕΡΟΠΟΙΟΥΜΕΝΟΥ ΣΥΓΧΡΟΝΙΣΜΟΥ ΡΟΛΟΓΙΩΝ ΧΩΡΙΣ ΑΝΑΜΟΝΗ ΣΕ ΠΟΛΥΕΠΕΞΕΡΓΑΣΤΙΚΟ ΣΥΣΤΗΜΑ. ΧΡΗΣΙΜΟΠΟΙΩΝΤΑΣ ΝΕΑ ΠΡΟΣΕΓΓΙΣΗ ΣΤΗΝ ΑΝΑΛΥΣΗ ΤΟΥ ΠΡΟΒΛΗΜΑΤΟΣ, ΠΡΟΤΕΙΝΕΤΑΙ ΕΠΑΝΑΠΡΟΣΔΙΟΡΙΣΜΟΣ ΤΩΝ ΠΑΡΑΜΕΤΡΩΝ ΤΟΥ ΠΡΟΗΓΟΥΜΕΝΟΥ ΚΑΛΥΤΕΡΟΥ ΑΛΓΟΡΙΘΜΟΥ, ΠΟΥ ΗΤΑΝ ΚΥΒΙΚΗΣ ΠΟΛΥΠΛΟΚΟΤΗΤΑΣ, ΔΙΝΟΝΤΑΣ ΕΤΣΙ ΤΕΤΡΑΓΩΝΙΚΗΣ ΠΟΛΥΠΛΟΚΟΤΗΤΑΣ ΛΥΣΗ.

THIS THESIS PRESENTS NEW ALGORITHMS IMPLEMENTING SEVERAL WAIT-FREE CONCURRENT OBJECTS THAT ARE WIDELY USED FOR MULTI-PROCESS COORDINATION. THESE ALGORITHMSARE MORE EFFICIENT THAN PREVIOUS ONES AND HAVE ALREADY BEEN USED BY OTHER RESEARCHERS IN INTRODUCING NEW COORDINATION MECHANISMS. IN PARTICULAR, THIS THESIS PRESENTS THE FOLLOWING RESULTS: (1) A NOVEL WAIT-FREE ALGORITHM IMPLEMENTING AN ONE-WRITE ATOMIC REGISTER. THE PROBLEM OF ONE-WRITE CONSTRUCTIONS HAS RECEIVED SOME ATTENTION, SINCE IT LIES AT THE HEART OF STUDYING LOWER BOUNDSAND TRADE-OFFS OF THE COMPLEXITIES OF REGISTER CONSTRUCTIONS. (2) NOVEL WAIT-FREE SOLUTION TO THE SNAPSHOT CONCURRENT OBJECT WITH ONE SCANNER. A WAIT-FREE SNAPSHOT ALGORITHM TAKES AN "INSTANTANEOUS" PICTURE OF A SET OF SHARED VARIABLES. (3) A NOVEL WAIT-FREE RANDOMIZED NAMING ALGORITHM. IN THE NAMING PROBLEM N CONCURRENT ASYNCHRONOUS PROCESSES TRY TO GET A DISTINCT NAME FROM A NAME SPACE AS SMALL AS POSSIBLE (PREFERABLY {1,..., N}). (4) A NOVEL APPROACH ON THE PROBLEM OF WAIT-FREE SELF-STABILIZING CLOCK SYNCHRONIZATION OF N PROCESSESIN A MULTIPROCESSOR SYSTEM. BY USING A DIFFERENT APPROACH IN ANALYZING THE DIFFICULTIES OF THE PROBLEM, THIS THESIS SHOWS HOW TO "REPARAMETRIZE" THE CUBIC BEST PREVIOUSLY KNOWN SOLUTION IN ORDER TO GET A QUADRATIC ONE.