Επόμενο2.7 Ο νόμος του AMDAHL Πάνω:Κεφάλαιο 2ο: Παραλληλισμός Δεδομένω Πίσω:2.5 Διαμοιραζόμενες και Τοπικές Μεταβλητές
2.6 Ο τελεστής FORK
Στα περισσότερα παραδείγματα του βιβλίου οι διεργασίες θα δημιουργηθούν με την χρήση της γραμμής εντολών της FORALL. Σε ορισμένες περιπτώσεις, όμως μπορεί να είναι χρήσιμη η δημιουργία μιας ανεξάρτητης διεργασίας παιδί. Γι’ αυτό το λόγο υπάρχει μια επιπλέον εντολή δημιουργίας διεργασίας - ο τελεστής FORK. Οποιαδήποτε γραμμή εντολής ακολουθεί την FORK, μετατρέπεται σε διεργασία παιδί που τρέχει παράλληλα με τον γονέα. Η γενική σύνταξη της εντολής FORK είναι:
FORK <γραμμή εντολής>;
Η <γραμμή εντολής> είναι μια οποιαδήποτε αποδεκτή για την Pascal γραμμή εντολής. Αυτή η <γραμμή εντολής> θα μετατραπεί σε διεργασία παιδί που θα εκτελεστεί σε διαφορετικό επεξεργαστή. Η διεργασία γονέας θα συνεχίσει να εκτελείται αμέσως μετά την δημιουργία χωρίς για κανένα λόγο να περιμένει την διεργασία παιδί. Μελετήστε το παρακάτω παράδειγμα:
... x := y * 3; FORK FOR i := 1 TO 10 DO A[i] := i; z := SQRT(x); ...
Αφού ολοκληρωθεί η ανάθεση τιμής στην μεταβλητή x, η διεργασία γονέας θα δημιουργήσει την διεργασία παιδί που θα αποτελείται από την γραμμή εντολής FOR. Ενώ εκτελείται η διεργασία παιδί ο γονέας θα εκτελεστεί την εντολή ανάθεσης τιμής στην μεταβλητή z και μετά θα συνεχίσει να τρέχει παράλληλα με το παιδί. Ο τελεστής FORK μπορεί να τοποθετηθεί σε οποιαδήποτε γραμμή εντολής της Multi-Pascal, έχοντας σαν αποτέλεσμα ολόκληρη η γραμμή εντολής να εκτελείται σαν παράλληλη διεργασία. Η FORK μπορεί ακόμα να χρησιμοποιηθεί μπροστά από μια κλήση διαδικασίας όπως στο ακόλουθο παράδειγμα:
... FORK Normalize(A); FORK Normalize(B); FORK Normalize(C); ...
Στο παραπάνω παράδειγμα δημιουργούνται τρεις παράλληλες διεργασίες που η κάθε μια περιλαμβάνει μια κλήση στη διαδικασία Normalize. Όταν εκτελούνται αυτές οι κλήσεις στην διαδικασία, η διεργασία γονέας εξακολουθεί να εκτελεί τις υπόλοιπες εντολές.
2.6.1 Τερματισμός Διεργασίας
Για να καταλάβουμε την διαφορά ανάμεσα στην FORK και FORALL, είναι απαραίτητο να μελετήσουμε το ζήτημα του τερματισμού διεργασίας πιο προσεκτικά. Πότε πραγματικά τερματίζεται μια διεργασία; Η απάντηση είναι απλή-μια διαδικασία τερματίζεται όταν φτάνει στο τέλος του κώδικα της. Αναφερόμενοι στο πρόγραμμα Ταξινόμησης Σειράς του Σχήματος 2.3, παρατηρούμε ότι κάθε διεργασία αποτελείται από μια απλή εντολή, που είναι μια κλήση στην διαδικασία PutinPlace. Όταν αυτή η κλήση διαδικασίας φτάνει στο τέλος της, η αντίστοιχη διεργασία τερματίζει αυτόματα. Αν όλοι οι φυσικοί επεξεργαστές είναι όμοιοι, είναι φυσικό να αναμένεται ότι όλες οι διεργασίες παιδιά θα τερματίσουν περίπου την ίδια στιγμή. Όμως ελάχιστες αποκλίσεις της ταχύτητας των επεξεργαστών ή άλλες επιρροές από το περιβάλλον μπορεί να έχουν σαν αποτέλεσμα τη μεταβολή του χρόνου τερματισμού. Σε οποιαδήποτε περίπτωση η διεργασία γονέας της εντολής FORALL περιμένει όλες τις διεργασίες παιδιά να τερματίσουν. Για το Σχήμα 2.3 αυτό σημαίνει ότι η εκτέλεση της κύριας διεργασίας θα ανασταλεί στη γραμμή 21 έως ότου όλες οι διεργασίες να τερματίσουν. Επομένως ολόκληρο το πρόγραμμα θα τερματίσει όταν , η κύρια διεργασία θα εκτελέσει την εντολή END στη γραμμή 22, και θα τερματιστεί.
Μελετήστε την γενική περίπτωση της ακόλουθης εντολής FORALL που δημιουργεί n διεργασίες παιδιά:
FORALL i := 1 TO n DO
‹γραμμή εντολής›;
Αυτή η δομή FORALL έχει σαν αποτέλεσμα την παρακάτω ακολουθία ενεργειών:
Δημιούργησε n διεργασίες παιδιά από την <γραμμή εντολής>
Περίμενε έως ότου τερματίσουν και οι n διεργασίες παιδιά
Συνέχισε την εκτέλεση του προγράμματος μετά την FORALL
Ολόκληρη η δομή της FORALL είναι από μόνη της μια απλή εντολή στη διεργασία γονέα. Η εκτέλεση της εντολής FORALL ξεκινάει με το να δημιουργήσει τις διεργασίες παιδιά. Στη συνέχεια η εκτέλεση αυτής της διεργασίας γονέα, παροδικά αναστέλλεται, όταν οι διεργασίες παιδιά εκτελούνται στους αντίστοιχους επεξεργαστές. Όταν οι διεργασίες παιδιά τερματίσουν, η εκτέλεση της διεργασίας πατέρα συνεχίζεται από την εντολή που ακολουθεί την FORALL.
Στην περίπτωση της εντολής FORK τα πράγματα είναι λίγο διαφορετικά. Εδώ δημιουργείται μια μόνο διεργασία παιδί και ο γονέας συνεχίζει να εκτελείται αμέσως μετά την δημιουργία χωρίς να περιμένει την διεργασία παιδί να τερματίσει. Για να καταλάβετε καλύτερα την διαφορά ανάμεσα στην FORK και FORALL, μελετήστε τον παρακάτω βρόχο που εμφανίζεται σε μια κύρια διεργασία:
FORALL i := 1 TO n DO
FORK ‹γραμμή εντολής›;
Κάθε επανάληψη του παραπάνω βρόχου θα δημιουργήσει μια διεργασία παιδί από την <γραμμή εντολής>. Από τη στιγμή που θα δημιουργηθεί μια διεργασία παιδί, θα ακολουθήσει άμεσα η επόμενη επανάληψη του βρόχου. Αφότου δημιουργηθούν και οι n διεργασίες παιδιά ο βρόχος FOR θα τερματίσει και η εκτέλεση της κύριας διεργασίας θα συνεχιστεί αμέσως από την επόμενη εντολή του βρόχου FOR. Έτσι η διεργασία γονέας και αυτές που ακολουθούν θα εκτελούνται παράλληλα με τα n παιδιά του. Εδώ βρίσκεται και η διαφορά με τον βρόχο FORALL, στον οποίο η διεργασία γονέας περιμένει έως ότου όλα τα παιδιά τερματίσουν.
Παρότι η διεργασία γονέας συνεχίζει την εκτέλεση της, ενώ οι διεργασίες παιδιά που έχουν δημιουργηθεί με την FORK εξακολουθούν να εκτελούνται, ο γονέας δεν επιτρέπεται να τερματίσει έως ότου όλα τα παιδιά του τερματίσουν. Αν ο γονέας φτάσει στο τέλος του κώδικα, ενώ ένα ή περισσότερα από τα παιδιά του εξακολουθούν να εκτελούνται, η εκτέλεση του γονέα αναστέλλεται έως ότου όλα τα παιδιά τερματίσουν και στη συνέχεια τερματίζει και ο γονέας. Αυτή η συμπεριφορά εμποδίζει τον πρόωρο τερματισμό του κυρίως προγράμματος όταν μερικές από τις διεργασίες παιδιά εκτελούνται.
2.6.2 Η Εντολή JOIN
Σε ορισμένα προγράμματα είναι επιθυμητό ο γονέας να περιμένει σε ορισμένα σημεία να τερματίσουν ένα ή περισσότερα από τα παιδιά που έχουν δημιουργηθεί με την FORK. Γι’ αυτή την περίπτωση η Multi-Pascal χρησιμοποιεί την εντολή JOIN. Αν ο γονέας έχει ένα παιδί διεργασία που δημιούργησε η FORK, η JOIN που εκτελείται από τον γονέα θα του επιβάλλει να περιμένει έως ότου το παιδί τερματίσει. Αν το παιδί έχει ήδη τερματίσει η εκτέλεση της JOIN δεν θα έχει καμία επίδραση στον γονέα. Κατά κάποιον τρόπο η JOIN είναι το αντίθετο της FORK. Η FORK διαχωρίζει την διεργασία παιδί από τον γονέα, ενώ η JOIN έχει σαν αποτέλεσμα ο γονέας να τερματίσει μαζί με το παιδί.
Για παράδειγμα, μελετήστε το ακόλουθο τμήμα της διεργασίας γονέα:
...
FORK Normalize(A);
FOR i := 1 TO 10 DO
B[i] := 0;
JOIN;
Ο γονέας δημιουργεί ένα FORK παιδί που περιέχει μια κλήση στην διαδικασία Normalize. Στη συνέχεια ενώ το παιδί εκτελείται, ο γονέας τον βρόχο FOR που ακολουθεί για τον μηδενισμό του πίνακα Β. Όταν ολοκληρωθεί η εκτέλεση του βρόχου ο πατέρας εκτελεί την εντολή JOIN. Αν το παιδί FORK έχει ήδη τερματίσει, ο γονέας απλά τερματίζει την εκτέλεση του αμέσως μετά την JOIN. Όμως αν το παιδί εξακολουθεί να εκτελείται, ο γονέας θα αναστείλει την εκτέλεση του όταν φτάσει στην εντολή JOIN έως ότου το παιδί τερματίσει και μετά θα συνεχίσει με ότι ακολουθεί την JOIN.
Αν ο γονέας έχει πολλά FORK παιδιά, τότε ο τερματισμός οποιουδήποτε από τα παιδιά θα ενημερώσει κάθε JOIN του γονέα. Όταν εκτελείται η JOIN ο γονέας δεν αναφέρεται σε ένα συγκεκριμένο παιδί. Αν ο γονέας έχει πολλά FORK παιδιά, θα εκτελέσει πολλές εντολές JOIN προκειμένου να περιμένει καθένα παιδί να τερματίσει. Η εκτέλεση της κάθε JOIN από τον γονέα συνδυάζεται με τον τερματισμό ενός μόνο FORK παιδιού. Αν ο γονέας κατά λάθος εκτελέσει περισσότερες εντολές JOIN απ’ ότι τα παιδιά που έχει, θα ανασταλεί για πάντα, προκαλώντας “αδιέξοδο” στην εκτέλεση του προγράμματος.
Μελετήστε το ακόλουθο παράδειγμα μιας διεργασίας γονέα με πολλά FORK παιδιά:
...
FOR i := 1 TO 10 DO
FORK Compute(A[i]);
FOR i := 1 TO 10 DO
JOIN;
Ο πρώτος βρόχος δημιουργεί δέκα FORK διεργασίες παιδιά. Κάθε παιδί καλεί την διεργασία Compute, χρησιμοποιώντας ένα διαφορετικό στοιχείο του πίνακα Α σαν παράμετρο. Στη συνέχεια στον επόμενο βρόχο FOR, ο πατέρας εκτελεί την εντολή JOIN 10 φορές, περιμένοντας για τον τερματισμό και των 10 παιδιών. Χωρίς τον δεύτερο βρόχο ο γονέας απλά θα εξακολουθούσε την εκτέλεση του, παράλληλα με τα παιδιά. Όμως, όταν ο γονέας έφτανε στο τέλος δεν θα τερμάτιζε εκτός και αν όλα τα παιδιά του είχαν ήδη τερματίσει.
2.6.3 Λίστα Παράλληλης Επεξεργασίας
Ο τελεστής FORK είναι ιδιαίτερα χρήσιμος στην εφαρμογή του παραλληλισμού λειτουργιών (fuctional parallelism), όπου πολλές υπολογιστικές ενέργειες εκτελούνται παράλληλα. Αυτό έρχεται σε αντίθεση με τον παραλληλισμό δεδομένων, όπου ο ίδιος υπολογισμός εφαρμόζεται παράλληλα σε διαφορετικές μονάδες δεδομένων. Για παράδειγμα τέσσερις διαφορετικές διαδικασίες μπορούν να εκτελούνται παράλληλα, όπως στο παράδειγμα που ακολουθεί:
FORK ProcedureA; FORK ProcedureB; FORK ProcedureC; FORK ProcedureD;
Μια άλλη σημαντική χρήση του τελεστή FORK είναι η παράλληλη επεξεργασία των δομών δεδομένων που μορφοποιούνται με τους δείκτες. Για παράδειγμα ο ακόλουθος κώδικας εφαρμόζει παράλληλα την διαδικασία Compute σε κάθε στοιχείο της συνδεδεμένης λίστας:
PROGRAM ParallelListApply;
TYPE pnttype = ^elementtype;
elementtype = RECORD
data:REAL;
next: pnttype;
END;
VAR pnt, listhead: pnttype;
PROCEDURE Compute(value: REAL);
BEGIN
...
END;
BEGIN (*Κυρίως πρόγραμμα*)
...
pnt := listhead;
WHILE pnt ‹› nil DO
BEGIN
FORK Compute(pnt^.data); (* Δημιουργεί την διεργασία παιδί*)
pnt := pnt^.next; (*Μετακινείται στο επόμενο στοιχείο της λίστας*)
END;
...
END.
Η χρήση του τελεστή FORK υπάρχει πριν από κάθε κλήση της διαδικασίας Compute μετατρέποντας την εκτέλεση της διαδικασίας σε ξεχωριστή διεργασία παιδί, που εκτελείται άμεσα και επιτρέπει στον γονέα να συνεχίσει να εκτελεί τον βρόχο WHILE. Έτσι, ο γονέας σειριακά διασχίζει την δομή της λίστας ακολουθώντας τους δείκτες, και δημιουργεί μια διεργασία παιδί για κάθε μονάδα δεδομένων στης λίστα. Αν υποθέσουμε ότι ο χρόνος εκτέλεσης της διαδικασίας Compute είναι μεγάλος συγκριτικά με τον χρόνο που απαιτείται για την διάσχιση της συνδεδεμένης λίστας, τότε αυτό το πρόγραμμα μπορεί να έχει σαν αποτέλεσμα υψηλό βαθμό παραλληλισμού για μεγάλες λίστες. Παρατηρείστε ότι η χρήση του τελεστή FORK σε αυτό το πρόγραμμα είναι πολύ απλή. Επιτρέπεται στον βρόχο WHILE να συνεχίζει με μέγιστη ταχύτητα να δημιουργεί μια διεργασία παιδί σε κάθε επανάληψη. Παρότι αυτό είναι ένα παράδειγμα παραλληλισμού δεδομένων, η χρήση της εντολής FORALL σε ένα τέτοιο είδος προγράμματος μπορεί να είναι προβληματική.
Επόμενο2.7 Ο νόμος του AMDAHL Πάνω:Κεφάλαιο 2ο: Παραλληλισμός Δεδομένων Πίσω:2.5 Διαμοιραζόμενες και Τοπικές Μεταβλητές