Επόμενο:Παράρτημα Α Πάνω: Κεφάλαιο 11o : Κατανεμημένη Ανίχνευση Τερματισμού Πίσω: Προγραμματιστικές Εργασίες
ΑΣΚΗΣΕΙΣ
1. Στο πρόγραμμα του Συντομότερου Μονοπατιού που παρουσιάσαμε στο κεφάλαιο μόνο ένας κόμβος ανατίθεται σε κάθε εργαζόμενο. Περιγράψτε τις απαραίτητες αλλαγές στο πρόγραμμα ώστε να ανατίθενται περισσότεροι από ένας κόμβοι σε κάθε Εργαζόμενο.
(α) Περιγράψτε τις αλλαγές στην διαδικασία Worker.
(β) Περιγράψτε τις αλλαγές στις διαδικασίες Getwork και Putwork.
2. Για το ίδιο γράφημα το πρόγραμμα Συντομότερου Μονοπατιού σε σύστημα κατανεμημένης μνήμης (σχήμα 11.1) θα δημιουργήσει πολύ περισσότερα αντικείμενα εργασίας σε σχέση με το ίδιο πρόγραμμα σε σύστημα διαμοιραζόμενης μνήμης (σχήμα 10.3). Εξηγείστε με λεπτομέρειες γιατί συμβαίνει αυτό.
3. Στην παράγραφο 11.2.1 περιγράφτηκε μια μέθοδος τερματισμού πρωτεύοντος μετρητή και συμπεριλήφθηκαν οι λόγοι για τους οποίους μπορεί να μην δουλεύει σωστά. Αναφέραμε ότι μια μεγάλη χρονική καθυστέρηση στον πρωτεύοντα μετρητή μπορεί να διορθώσει το πρόβλημα για πρακτικούς σκοπούς σε κάποια πραγματικά συστήματα. Δώστε μια περιγραφή υψηλού επιπέδου των διαδικασιών Getwork, Putwork και Monitor που απαιτούνται για αυτή τη μέθοδο τερματισμού. Μπορείτε να χρησιμοποιήσετε της δήλωση Duration της Multi-Pascal, όπως αυτή περιγράφεται στο Παράρτημα.
4. Στην παράγραφο 11.2.1 περιγράφτηκε μια μέθοδος τερματισμού πρωτεύοντος μετρητή και συμπεριλήφθηκαν οι λόγοι για τους οποίους μπορεί να μην δουλεύει σωστά. Αναφέραμε ότι μπορεί να διορθωθεί με τη χρήση μηνυμάτων επιβεβαίωσης. Περιγράψτε λεπτομερώς τη μέθοδο τερματισμού πρωτεύοντα αθροιστή με τη χρήση μηνυμάτων επιβεβαίωσης. Δώστε μια περιγραφή υψηλού επιπέδου των διαδικασιών Getwork, Putwork και Monitor.
5. Υποθέστε ότι ο κατανεμημένος αλγόριθμος τερματισμού της παραγράφου 11.2.2 τροποποιείται έτσι ώστε κάθε εργαζόμενος να στέλνει μήνυμα επιβεβαίωσης στον γονέα του ακριβώς όπως γίνεται με κάθε άλλο αντικείμενο εργασίας. Εξηγείστε με λεπτομέρειες πώς αυτό μπορεί να προκαλέσει έναν λανθασμένο τερματισμό.
6. Στην υλοποίηση των Κατανεμημένων Εργαζομένων του σχήματος 11.5 κάθε εργαζόμενος συνεχίζει να διαβάζει τη θύρα επικοινωνίας του κάθε φορά που χρειάζεται ένα νέο αντικείμενο εργασίας. Αν η θύρα είναι άδεια τότε περιμένει να διαβάσει. Φαίνεται ότι ίσως προκύψει ένα αδιέξοδο, κατά το οποίο όλοι οι εργαζόμενοι περιμένουν για μια άδεια θύρα. Εξηγείστε λεπτομερώς γιατί αυτό το αδιέξοδο δεν μπορεί να συμβεί ποτέ στο σχήμα 11.5.
7. Στην υλοποίηση της Δεξαμενής Εργασίας του σχήματος 11.3 τα μηνύματα επιβεβαίωσης και τα αντικείμενα εργασίας εισέρχονται από το ίδιο κανάλι εισόδου. Ξαναγράψτε την περιγραφή υψηλού επιπέδου της Getwork υποθέτοντας ότι υπάρχουν δύο θύρες για κάθε εργαζόμενο: η θύρα workpool[me] για τη λήψη των αντικειμένων εργασίας και η θύρα acknowledge[me] για τη λήψη των μηνυμάτων επιβεβαίωσης. Να είστε ιδιαίτερα προσεκτικοί στην κατάσταση κατά την οποία και οι δύο θύρες είναι άδειες, αλλά υπάρχουν κάποια εκκρεμή μηνύματα επιβεβαίωσης που δεν έχουν ακόμα ληφθεί. Για να λειτουργήσει σωστά ο αλγόριθμος ο εργαζόμενος μπορεί να χρειαστεί να βρίσκεται σε ενεργή αναμονή ελέγχοντας συνεχώς και τις δύο θύρες για είσοδο.
8. Στην υλοποίηση της Δεξαμενής Εργασίας του σχήματος 11.5 η διεργασία επόπτης διαβάζει ένα αντικείμενο από την workpool[0]. Εφόσον δεν υπάρχει κόμβος με αριθμό 0 στο γράφημα πώς γίνεται να γράφονται αντικείμενα εργασίας σε αυτό το κανάλι; (Εξηγείστε).
9. Στην παράγραφο 11.4.2 έχουμε μια γενική έκφραση για την καθυστέρηση επικοινωνίας που σχετίζεται με την δημιουργία του αρχικού δένδρου των ενεργών εργαζομένων σε Υπερκύβο. Περιγράψτε γενικά πώς αυτή η απόδειξη πρέπει να τροποποιηθεί για τις διάφορες τοπολογίες συστημάτων κατανεμημένης μνήμης.
10. Η ανάλυση απόδοσης του κατανεμημένου αλγόριθμου τερματισμού έδειξε ότι προκύπτει κάποια συμφόρηση αν η βασική καθυστέρηση επικοινωνίας είναι μεγάλη. Αυτή η συμφόρηση συμβαίνει κατά τη διάρκεια της κατανομής των τελικών μηνυμάτων τερματισμού από τη διεργασία επόπτη.
(α) Περιγράψτε λεπτομερώς τους λόγους αυτής της συμφόρησης.
(β)Δείξτε ότι αυτή η συμφόρηση μπορεί να μειωθεί σημαντικά χρησιμοποιώντας έναν τυπικό αλγόριθμο διάδοσης Υπερκύβου για την κατανομή των μηνυμάτων τερματισμού.
(γ) Περιγράψτε τις απαραίτητες αλλαγές στην διαδικασία Getwork για την υλοποίηση αυτής της διάδοσης των μηνυμάτων τερματισμού.
11. Θεωρείστε την τυχαία κατανομή n αντικειμένων εργασίας σε p εργαζόμενους. Στην ανάλυση απόδοσης της παραγράφου 11.4 εξηγήσαμε ότι ο αναμενόμενος φόρτος εργασίας για κάθε εργαζόμενο είναι m=n/p και η τυπική απόκλιση του φόρτου είναι m1/2. Ο φόρτος εργασίας συνεπώς για κάθε εργαζόμενο μπορεί να προσεγγιστεί σαν Κανονική Κατανομή με μέσο m και τυπική απόκλιση m1/2. Χρησιμοποιώντας αυτό το μοντέλο μπορεί να υπολογιστεί ο αναμενόμενος μέγιστος φόρτος εργασίας μεταξύ των p εργαζομένων και να έχει την ακόλουθη μορφή:
Αναμενόμενο μέγιστο: m + km1/2
Η τιμή του k εξαρτάται από το p σύμφωνα με τον ακόλουθο πίνακα:
p 10 20 30 40 50 60 70 80
k 1.55 1.87 2.04 2.16 2.24 2.31 2.37 2.42
(α)Εξάγετε μια γενική έκφραση για τον αναμενόμενο χρόνο που απαιτείται για να επεξεργαστούν οι εργαζόμενοι όλα τα αντικείμενα εργασίας τους. Θεωρείστε τον σταθερό χρόνο T για την επεξεργασία κάθε αντικειμένου. Επίσης, υποθέστε ότι κάθε εργαζόμενος δεν περιμένει ποτέ για την άφιξη κάποιου αντικειμένου.
(β)Χρησιμοποιώντας τις ίδιες υποθέσεις με του (α) υπο-ερωτήματος εξάγετε μια γενική έκφραση για τον ιδανικό ελάχιστο χρόνο που απαιτείται για την επεξεργασία των αντικειμένων εργασίας υποθέτοντας ότι υπάρχει μια πολύ καλή εξισορρόπηση φορτίου.
(γ) Η αναμενόμενη απώλεια της απόδοσης εξαιτίας της ανισορροπίας φορτίου μπορεί να προσεγγιστεί διαιρώντας τον ιδανικό χρόνο του (β) υπο-ερωτήματος με τον αναμενόμενο χρόνο του (α). Σχεδιάστε ένα διάγραμμα αυτής της αναμενόμενης απώλειας σε σχέση με τον αριθμό των Εργαζομένων, χρησιμοποιώντας m=1000. Σχεδιάστε ένα παρόμοιο διάγραμμα για m=10.000.
(δ) Ποια γενικά συμπεράσματα μπορούν να εξαχθούν από αυτά τα διαγράμματα απόδοσης σχετικά με την επίδραση των προβλημάτων εξισορρόπησης φορτίου στην απόδοση των Κατανεμημένων Εργαζομένων;
12. Στο σχήμα 10.12 παρουσιάζεται ένα πρόγραμμα συστήματος διαμοιραζόμενης μνήμης για το πρόβλημα των Ν Βασιλισσών. Περιγράψτε λεπτομερώς τις τροποποιήσεις που είναι απαραίτητες για την υλοποίησή του σε σύστημα κατανεμημένης μνήμης με τη χρήση Κατανεμημένων Εργαζομένων. Χρησιμοποιήστε την υλοποίηση της Δεξαμενής Εργασίας που δίνεται στο σχήμα 11.5. Δείξτε όλες τις απαραίτητες αλλαγές σε αυτή την υλοποίηση Δεξαμενής Εργασίας και επίσης τις αλλαγές που ίσως χρειάζονται στην διαδικασία Worker των Ν Βασιλισσών του σχήματος 10.12.
13. Το σχήμα 11.8 παρουσιάζει ένα διάγραμμα αλλαγής κατάστασης για την διαδικασία Getwork με συμπίεση εργασίας. Σχεδιάστε ένα παρόμοιο διάγραμμα για την διαδικασία Getwork χωρίς όμως συμπίεση εργασίας, όπως φαίνεται στο σχήμα 11.5. Συμπεριλάβετε την “συνθήκη” και την “δράση” σε κάθε βέλος αλλαγής.
14. Το σχήμα 11.8 δίνει ένα διάγραμμα αλλαγής κατάστασης για την διαδικασία Getwork με συμπίεση εργασίας. Γράψτε αυτή την διαδικασία Getwork σε Multi-Pascal.
15. Υποθέστε ότι υπάρχει ένα γνωστό άνω όριο L στον χρόνο επικοινωνίας μεταξύ των επεξεργαστών σε ένα σύστημα κατανεμημένης μνήμης και ότι είναι δυνατή η χρήση μιας τεχνικής ψηφοφορίας για την ανίχνευση τερματισμού των Κατανεμημένων Εργαζομένων. Σε αυτή την τεχνική μια διεργασία επόπτης στέλνει τακτικά ένα μήνυμα ψηφοφορίας σε κάθε εργαζόμενο, προκαλώντας τον να επιστρέψει ένα μήνυμα “κατάστασης” πίσω στον επόπτη. Με αυτή τη μέθοδο μπορούν να ελαχιστοποιηθούν τα μηνύματα επιβεβαίωσης και το δένδρο των ενεργών εργαζόμένων.
Περιγράψτε με λεπτομέρειες την υλοποίηση αυτής της τεχνικής για την ανίχνευση τερματισμού. Συμπεριλάβετε και μια περιγραφή υψηλού επιπέδου για την λεπτομερή συμπεριφορά της διεργασίας επόπτη και των διαδικασιών Putwork και Getwork. Η υλοποίηση σας πρέπει να επιτρέπει την πιθανότητα διακυμάνσεων στις ταχύτητες του επεξεργαστή.
16. Στην περιγραφή υψηλού επιπέδου της διεργασίας Worker για την ασύγχρονη επανάληψη (παράγραφος 11.5.2) κάθε νέα τιμή στέλνεται σε όλους τους εργαζόμενους. Κάποια συστήματα εξισώσεων είναι αραιά, που σημαίνει ότι ο υπολογισμός της νέας τιμής για κάθε xi βασίζεται στις τιμές κάποιων μόνο στοιχείων του διανύσματος κατάστασης. Συνεπώς, κάθε εργαζόμενος δεν χρειάζεται να έχει ένα αντίγραφο του πλήρους διανύσματος κατάστασης, αλλά μόνο των στοιχείων που απαιτούνται για τον επαν-υπολογισμό του στοιχείου που του έχει ανατεθεί. Δώστε μια λεπτομερή περιγραφή υψηλού επιπέδου αυτού του νέου τύπου διεργασίας εργαζομένου για αραιά συστήματα.
Επόμενο:Παράρτημα Α Πάνω: Κεφάλαιο 11o : Κατανεμημένη Ανίχνευση Τερματισμού Πίσω: Προγραμματιστικές Εργασίες