Επόμενο:11.1 Πρόγραμμα Συντομότερου Μονοπατιού Συστήματος Κατανεμημένης Μνήμης Πάνω: Περιεχόμενα Πίσω: Aσκήσεις
Κεφάλαιο 11o : Κατανεμημένη Ανίχνευση Τερματισμού
Το υπόδειγμα των Αντιγράφων Εργαζομένων επιτρέπει σε ένα παράλληλο πρόγραμμα τη δυναμική δημιουργία υπολογιστικών εργασιών καθώς το πρόγραμμα εκτελείται. Αυτές οι εργασίες είναι αποθηκευμένες στη Δεξαμενή Εργασίας, από όπου μπορούν να προσπελαστούν από τους εργαζόμενους. Στο προηγούμενο κεφάλαιο είδαμε πως μπορούμε να υλοποιήσουμε αυτό το υπόδειγμα σε ένα σύστημα διαμοιραζόμενης μνήμης. Όμως, το υπόδειγμα των Αντιγράφων Εργαζομένων υλοποιείται και σε συστήματα κατανεμημένης μνήμης. Η βασική αρχή όμως του υποδείγματος πρέπει να τροποποιηθεί λίγο εξαιτίας της τοπικής φύσης της μνήμης στα συστήματα κατανεμημένης μνήμης. Δεν μπορούμε πλέον να θεωρούμε τη Δεξαμενή Εργασίας ως μια συγκεντρωτική και διαμοιραζόμενη δεξαμενή κοινών αντικειμένων εργασίας που μπορούν ελεύθερα να ανακτηθούν από τις διεργασίες εργαζόμενους. Η Δεξαμενή Εργασίας πρέπει να επιμεριστεί και να κατανεμηθεί στις τοπικές μνήμες του συστήματος κατανεμημένης μνήμης. Εξαιτίας αυτής της αλλαγής και των νέων ζητημάτων υλοποίησης που προκύπτουν θα χρησιμοποιήσουμε ένα νέο όνομα για αυτή την παράλληλη τεχνική στα συστήματα κατανεμημένης μνήμης: Κατανεμημένοι Εργαζόμενοι.
Στην υλοποίηση των Κατανεμημένων Εργαζομένων το πιο δύσκολο θέμα είναι η ανίχνευση τερματισμού. Απαιτείται ένας καινούργιος και κάπως πιο δύσκολος αλγόριθμος κατανεμημένου τερματισμού. Το όλο θέμα του κατανεμημένου τερματισμού είναι ένα σημαντικό γενικό θέμα στον προγραμματισμό των συστημάτων κατανεμημένης μνήμης και αποτελεί το κυρίαρχο θέμα του κεφαλαίου. Ένα άλλο σημαντικό θέμα των Κατανεμημένων Εργαζομένων είναι η μέθοδος κατανομής των αντικειμένων εργασίας. Η Δεξαμενή Εργασίας είναι εντελώς επιμερισμένη στους εργαζόμενους και συνεπώς κάθε αντικείμενο εργασίας πρέπει να στέλνεται κατευθείαν σε έναν συγκεκριμένο εργαζόμενο. Στο υπόδειγμα των Αντιγράφων Εργαζομένων θεωρήσαμε ότι οι εργαζόμενοι είναι ουσιαστικά μη-διακριτοί, έτσι ώστε κάθε εργαζόμενος να μπορεί να λάβει οποιοδήποτε αντικείμενο εργασίας. Όμως, στην περίπτωση των Κατανεμημένων Εργαζομένων συμβαίνει συχνά οι εργαζόμενοι να είναι διακριτοί και συνεπώς είναι απαραίτητο συγκεκριμένα αντικείμενα εργασίας να πάνε σε συγκεκριμένους εργαζόμενους. Αυτή η απαίτηση είναι αποτέλεσμα του επιμερισμού δεδομένων που είναι συχνά αναγκαίος στους αλγορίθμους συστημάτων κατανεμημένης μνήμης.
Στα προγράμματα των Αντιγράφων Εργαζομένων οι εργαζόμενοι συχνά χρησιμοποιούν κάποιες επιπλέον διαμοιραζόμενες δομές δεδομένων εκτός από τη Δεξαμενή Εργασίας. Για παράδειγμα, στο πρόγραμμα του Συντομότερου Μονοπατιού οι εργαζόμενοι χρησιμοποιούν έναν πίνακα που καταγράφει τη συντομότερη απόσταση που έχει βρεθεί μέχρι στιγμής προς κάθε κόμβο του γραφήματος. Σε μια υλοποίηση συστήματος κατανεμημένης μνήμης για να προωθηθεί πιο αποδοτική πρόσβαση και να ελαχιστοποιηθούν οι καθυστερήσεις επικοινωνίας αυτές οι διαμοιραζόμενες δομές δεδομένων πρέπει να επιμεριστούν στις τοπικές μνήμες. Στα περισσότερα προγράμματα Κατανεμημένων Εργαζομένων αυτό σημαίνει ότι τα αντικείμενα εργασίας δεν μπορούν κατανεμηθούν σε οποιονδήποτε εργαζόμενο. Τα αντικείμενα εργασίας μπορεί να αναφέρονται σε ένα συγκεκριμένο τμήμα της διαμοιραζόμενης δομής δεδομένων και συνεπώς πρέπει να σταλούν στον εργαζόμενο που έχει τοπική πρόσβαση σε αυτό το συγκεκριμένο τμήμα.
Όπως και στο προηγούμενο κεφάλαιο θα χρησιμοποιήσουμε τον αλγόριθμο του Συντομότερου Μονοπατιού ως πρωταρχικό άξονα για την κατανόηση και την ανάπτυξη του υποδείγματος των Κατανεμημένων. Πρώτα θα ασχοληθούμε με το θέμα του επιμερισμού δεδομένων και στη συνέχεια με τον αλγόριθμο ανίχνευσης τερματισμού. Το πιο ενδιαφέρον σημείο του αλγόριθμου ανίχνευσης τερματισμού είναι η χρήση των μηνυμάτων επιβεβαίωσης για να πληροφορήσουν έναν αποστολέα ότι το μήνυμα που έστειλε έχει ληφθεί σωστά. Αυτό επιτρέπει την σωστή λειτουργία παρ’ όλες τις αυθαίρετες καθυστερήσεις μετάδοσης μεγάλων μηνυμάτων στο δίκτυο επικοινωνίας. Ο αλγόριθμος είναι ιδιαίτερα γενικός και έχει εφαρμογές και σε άλλα προγράμματα πέρα από αυτά των Κατανεμημένων Εργαζομένων. Το κεφάλαιο κλείνει με μια αναφορά στους ασύγχρονους επαναληπτικούς αλγόριθμους, οι οποίοι υπόσχονται πολλά για το μέλλον του παράλληλου προγραμματισμού. Οι αλγόριθμοι αυτοί μπορούν να υλοποιηθούν στο υπόδειγμα των Κατανεμημένων Εργαζομένων.
Επόμενο:11.1 Πρόγραμμα Συντομότερου Μονοπατιού Συστήματος Κατανεμημένης Μνήμης Πάνω: Περιεχόμενα Πίσω: Aσκήσεις