10.3 Υλοποίηση των Δεξαμενών Εργασίας

Επόμενο:10.4 Εξάλειψη της Συμφόρησης Πάνω: Κεφάλαιο 10o : Αντίγραφα Εργαζομένων Πίσω: 10.2 Αλγόριθμος Συντομότερου Μονοπατιού

10.3 Υλοποίηση των Δεξαμενών Εργασίας

Στον παράλληλο αλγόριθμο του Συντομότερου Μονοπατιού, η Δεξαμενή Εργασίας χρησιμοποιείται για να αντικαταστήσει την ουρά στον ακολουθιακό αλγόριθμο. Συνεπώς, είναι μια φυσική κατάληξη η υλοποίηση της Δεξαμενής Εργασίας με ένα κανάλι, το οποίο στην ουσία είναι μια ουρά παράλληλης προσπέλασης. Ακριβώς όπως ο ακολουθιακός αλγόριθμος εισάγει και αφαιρεί κόμβους από την ουρά, έτσι και ο παράλληλος αλγόριθμος μπορεί να εισάγει και να αφαιρέσει κόμβους από το κανάλι. Η Putwork(me, item) μπορεί να γράψει το item στο κανάλι και η Getwork(me, item) μπορεί να διαβάσει μια τιμή από το κανάλι στο item. Εφόσον ένα κανάλι της Multi-Pascal είναι σχεδιασμένο για παράλληλη προσπέλαση από πολλές διεργασίες συγγραφής και ανάγνωσης, δεν υπάρχουν λάθη συγχρονικότητας όταν επιτρέπεται η πρόσβαση όλων των Αντιγράφων Εργαζομένων στην Δεξαμενή Εργασίας παράλληλα. Η Δεξαμενή Εργασίας μπορεί να δηλωθεί με τον ακόλουθο τρόπο:

VAR workpool: CHANNEL OF worktype;

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

Συνθήκη Τερματισμού:

Η Δεξαμενή Εργασίας είναι άδεια

Όλες οι διεργασίες Εργαζόμενοι είναι αδρανείς

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

Και οι δύο παραπάνω συνθήκες τερματισμού μπορούν να ελεγχθούν αν χρησιμοποιήσουμε μια μεταβλητή μετρητή που θα δηλώνει το συνολικό αριθμό των αντικειμένων που βρίσκονται μέσα στη Δεξαμενή Εργασίας. Η Putwork θα αυξάνει τον μετρητή και η Getwork θα μειώνει τις τιμές του. Όταν ο μετρητής φτάσει την τιμή 0, τότε η Δεξαμενή Εργασίας είναι άδεια, πράγμα το οποίο ικανοποιεί τη συνθήκη 1. Στην πραγματικότητα, ο μόνος τρόπος με τον οποίο ένας Εργαζόμενος μπορεί να γίνει αδρανής είναι με το να καλέσει την Gtework όταν η Δεξαμενή Εργασίας είναι άδεια. Σε αυτή την κατάσταση η διαδικασία Getwork πρέπει να θέσει τον Εργαζόμενο σε μια κατάσταση αναμονής μέχρι να γραφούν κάποια άλλα αντικείμενα στην δεξαμενή Εργασίας από κάποιον άλλο ενεργό Εργαζόμενο. Για να διαπιστώσουμε αν έχει ικανοποιηθεί η συνθήκη τερματισμού 2, η διαδικασία Getwork πρέπει να διατηρεί το άθροισμα του συνολικού πλήθους των Εργαζομένων που περιμένουν την τρέχουσα στιγμή στην άδεια Δεξαμενή Εργασίας. Όταν αυτό το άθροισμα φτάσει το συνολικό αριθμό των Εργαζομένων, τότε ικανοποιείται η συνθήκη τερματισμού 2.

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

Ο κώδικας της Multi-Pascal για τις διαδικασίες Getwork και Putwork παρουσιάζεται στο σχήμα 10.4. Η Putwork απλά αυξάνει την τιμή του μετρητή της Δεξαμενής Εργασίας που διατηρείται στην μεταβλητή count και στη συνέχεια γράφει το νέο αντικείμενο item στο κανάλι workpool. Η διαδικασία Getwork αρχίζει με τη μείωση της τιμής του μετρητή της Δεξαμενής Εργασίας. Αν η τιμή του μετρητή φτάσει τον αρνητικό αριθμό του πλήθους των Εργαζομένων (-numworkers) τότε ο υπολογισμός πρέπει να σταματήσει. Διαφορετικά, ένα αντικείμενο διαβάζεται από το κανάλι workpool και επιστρέφεται στον εργαζόμενο που το καλεί. Αν στη συγκεκριμένη στιγμή η Δεξαμενή Εργασίας είναι άδεια η προσπάθεια να γίνει η ανάγνωση από το τέλος της διαδικασίας Getwork θα προκαλέσει τον εργαζόμενο να βρεθεί σε κατάσταση σταματημένη περιμένοντας στο κανάλι workpool. Όταν όλοι οι εργαζόμενοι βρεθούν σε αυτή την κατάσταση αναμονής ο υπολογισμός πρέπει να τερματιστεί. Στην πραγματικότητα, ο τελευταίος εργαζόμενος που θα εισέλθει στην Getwork όταν όλες οι άλλες περιμένουν, θα βρει ότι η τιμή της count έχει φτάσει την αρνητική τιμή -numworkers. Τότε ο βρόχος FOR στην Getwork θα ενεργοποιηθεί για να στείλει μηνύματα τερματισμού στη Δεξαμενή Εργασίας σε όλους τους εργαζόμενους που περιμένουν να διαβάσουν. Έτσι, όλοι οι εργαζόμενοι θα λάβουν τον κωδικό τερματισμού -1 και θα τερματίσουν τη λειτουργία μόνοι τους (δες τη διαδικασία Worker στο σχήμα 10.3).

Πρέπει να προστεθούν λίγες εντολές αρχικοποίησης στο σώμα του κυρίως προγράμματος, όπως φαίνεται και στο σχήμα 10.4. Ο κόμβος αφετηρία 1 πρέπει να εγγραφεί μέσα στη Δεξαμενή Εργασίας ως το σημείο αφετηρίας όλων των μονοπατιών. Εφόσον ο κόμβος 1 είναι η αφετηρία η συντομότερη απόσταση προς τον εαυτό του πρέπει να είναι 0 και έτσι η mindist[startvetrex] αρχικοποιείται με την τιμή 0. Εφόσον τώρα έχουμε ένα αντικείμενο στη Δεξαμενή Εργασίας ο αθροιστής αρχίζει με την τιμή 1.