Επόμενο:Αναφορές Πάνω: Κεφάλαιο 10o : Αντίγραφα Εργαζομένων Πίσω: 10.5 Πρόβλημα των Ν-Βασιλισσών

10.6 Περίληψη

Σκοπός αυτού του κεφαλαίου είναι να περιγράψει μια σημαντική προγραμματιστική τεχνική: το υπόδειγμα των Αντιγράφων Εργαζομένων. Αυτή η τεχνική απαιτείται από προγράμματα στα οποία η υπολογιστική διαδικασία αναπτύσσεται δυναμικά και απρόβλεπτα καθώς το πρόγραμμα προχωράει. Για τέτοιου είδους προγράμματα οι απλοί φωλιασμένοι FORALL βρόχοι που χρησιμοποιήσαμε στα προηγούμενα κεφάλαια είναι ανεπαρκείς. Το πρόγραμμα πρέπει να είναι έτσι οργανωμένο ώστε να αποθηκεύει και να κατανέμει τον μεγάλο αριθμό των υπολογιστικών εργασιών καθώς αυτές δημιουργούνται δυναμικά. Για αυτό το σκοπό παρουσιάσαμε την έννοια της Δεξαμενής Εργασίας. Κάθε απαιτούμενη μονάδα υπολογισμών αναπαριστάνεται με έναν περιγραφέα υπολογιστικής εργασίας, που είναι αποθηκευμένος στην Δεξαμενή Εργασίας. Μία ομάδα ίδιων Διεργασιών Εργαζομένων συνεχώς γράφει και διαβάζει περιγραφείς εργασιών από τη Δεξαμενή Εργασίας. Όταν ένας εργαζόμενος είναι ελεύθερη θα διαβάσει έναν περιγραφέα εργασίας από την Δεξαμενή Εργασίας και θα πραγματοποιήσει τον απαιτούμενο υπολογισμό. Κατά τη διάρκεια αυτού του υπολογισμού μπορεί να δημιουργηθούν νέοι περιγραφείς εργασιών από τον εργαζόμενο και να προστεθούν στη Δεξαμενή Εργασίας.

Σε αυτό το κεφάλαιο κυρίαρχο θέμα μας ήταν η περιγραφή της υλοποίησης της Δεξαμενής Εργασίας σε πολυεπεξεργαστές. Το πρώτο θέμα της υλοποίησης ήταν η συμφόρηση της Δεξαμενής Εργασίας από τις αιτήσεις των εργαζομένων. Για να αποφευχθεί η συμφόρηση καναλιών η Δεξαμενή Εργασίας αποκεντρώθηκε μέσω μικρού αριθμού καναλιών, καθένα από τα οποία έχει την δική του τοπική Ομάδα Εργαζομένων. Αυτή η αποκέντρωση έφερε στην επιφάνεια το θέμα της εξισορρόπησης του φορτίου εξαιτίας της πιθανότητας κάποιες ομάδες εργαζομένων να είναι αδρανείς ενώ άλλες να έχουν πολλά αντικείμενα εργασίας. Πρακτικά βρέθηκε ότι το πρόβλημα αυτό μπορεί να ξεπεραστεί με μια απλή τεχνική κατανομής των αντικειμένων εργασίας, όπως για παράδειγμα να έχουμε κάθε εργαζόμενο να χρησιμοποιεί εκ περιτροπής όλα τα κανάλια της Δεξαμενή Εργασίας.

Ένα άλλο ενδιαφέρον θέμα που προκύπτει από το πρόγραμμα των Αντιγράφων Εργαζομένων είναι η ανίχνευση τερματισμού. Το πρόγραμμα πρέπει να σταματήσει όταν η Δεξαμενή Εργασίας είναι άδεια και όλοι οι εργαζόμενοι περιμένουν νέα δουλειά. Καθώς η Δεξαμενή Εργασίας αποκεντρώνεται η συνθήκη τερματισμού είναι δύσκολο να ανιχνευτεί. Στην υλοποίηση αποκεντρωμένων Δεξαμενών Εργασίας που παρουσιάστηκε στο κεφάλαιο αυτό ο τερματισμός ανιχνεύεται με τη χρήση πινάκων αθροιστών, ένας για κάθε κανάλι, που καταγράφουν τον αριθμό των αδρανών εργαζομένων που περιμένουν σε ένα δεδομένο κανάλι.

Σαν παράδειγμα των Αντιγράφων Εργαζομένων παρουσιάστηκε ένα παράλληλο πρόγραμμα για τον υπολογισμό του Συντομότερου Μονοπατιού από ένα συγκεκριμένο κόμβο προς όλους τους άλλους κόμβους σε ένα γράφημα με βάρη. Καθώς το πρόγραμμα προχωρεί βρίσκονται συνεχώς νέες συντομότερες αποστάσεις προς τους κόμβους. Αυτές σχηματίζουν τις περιγραφές εργασιών ή τα αντικείμενα εργασίας της Δεξαμενής Εργασίας. Ένας εργαζόμενος διαβάζει μια συντομότερη απόσταση από τη Δεξαμενή Εργασίας και υπολογίζει τις νέες αποστάσεις ελέγχου προς όλους τους άμεσους γείτονες αυτού του κόμβου. Αν βρεθεί μια συντομότερη απόσταση για κάποιον από τους γείτονες τότε δημιουργείται ένα νέο αντικείμενο εργασίας και προστίθεται στην Δεξαμενή Εργασίας. Αυτό το παράδειγμα του Συντομότερου Μονοπατιού επιλέχτηκε απλά για να γίνει κατανοητό το υπόδειγμα των Αντιγράφων Εργαζομένων και να χρησιμοποιηθεί ως βάση για την περιγραφή των τεχνικών υλοποίησης της Δεξαμενής Εργασίας.

Υπάρχει μια μεγάλη ποικιλία άλλων παραδειγμάτων για τα οποία το υπόδειγμα των Αντιγράφων Εργαζομένων είναι η καλύτερη λύση. Αυτά περιλαμβάνουν πολλούς αλγόριθμους γραφημάτων και προβλήματα συνδυαστικής αναζήτησης. Ένα απλό παράδειγμα είναι το πρόβλημα των Ν Βασιλισσών που παρουσιάσαμε στο τέλος του κεφαλαίου. Είδαμε ότι η υλοποίηση της Δεξαμενής Εργασίας που αναφέρθηκε στο πρόγραμμα του Συντομότερου Μονοπατιού μπορεί επίσης να χρησιμοποιηθεί σαν μια λύση Αντιγράφων Εργαζομένων στο πρόβλημα των Ν Βασιλισσών. Η μόνη τροποποίηση που χρειάζεται είναι να αλλάξουμε τον ορισμό του αντικειμένου εργασίας για να καταστήσουμε την Δεξαμενή Εργασίας κατάλληλη για αυτό το πρόβλημα.

Στις εργασίες προγραμματισμού που ακολουθούν δίνονται δύο επιπλέον παραδείγματα: το πρόβλημα του Περιοδεύοντος Πωλητή και το πρόγραμμα της Αναζήτησης Μάζας. Για αυτά τα προγράμματα και πολλά άλλα ακόμη το υπόδειγμα παράλληλου προγραμματισμού των Αντιγράφων Εργαζομένων είναι κατάλληλο και οι υλοποιήσεις της Δεξαμενής Εργασίας που περιγράφτηκαν μπορούν εύκολα να χρησιμοποιηθούν με μικρές μόνο μετατροπές.

Επόμενο:Αναφορές Πάνω: Κεφάλαιο 10o : Αντίγραφα Εργαζομένων Πίσω: 10.5 Πρόβλημα των Ν-Βασιλισσών