Επόμενο:Κεφάλαιο 6ο : Σύγχρονος παραλληλισμός Πάνω: Κεφάλαιο 5ο : Μοίρασμα Δεδομένων Πίσω: Προγραμματιστικές Εργασίες
ΑΣΚΗΣΕΙΣ
1. Έστω το παρακάτω πρόγραμμα που επιχειρεί να χρησιμοποιήσει μια παράλληλη τεχνική για τον υπολογισμό της δύναμης του δυο ενός αριθμού :
PROGRAM power2; VAR value, power: Integer; BEGIN Write(‘Power of two : ‘); (*Υποθέτουμε ότι ο αριθμός είναι μεγαλύτερος από 0*) Readln(power); value := 1; FORALL I := 1 to power do value := 2 * value; Writeln(‘Answer is : ‘, value); END.
Γράψτε και εκτελέστε αυτό το πρόγραμμα στον προσομοιωτή της Multi-Pascal. (Για τη συγκεκριμένη άσκηση αυτό που μας ενδιαφέρει είναι η ορθότητα των απαντήσεων. Το θέμα της γρήγορης εκτέλεσης θα μας απασχολήσει σε άλλες ασκήσεις.)
(α) Γιατί οι απαντήσεις που παράγονται από το πρόγραμμα δεν είναι σωστές;
(β) Χρησιμοποιήστε την επιλογή “VARIATION” του συστήματος της Multi-Pascal για να διαφοροποιήσετε την ταχύτητα του επεξεργαστή. Γιατί αυτή η μεταλλαγή που δημιουργείται αλλάζει και την απάντηση που παράγεται από το πρόγραμμα;
(γ) Χρησιμοποιήστε τις λειτουργίες κλειδώματος και ξεκλειδώματος ώστε το πρόγραμμα να εκτελεστεί σωστά. Ελέγξτε τις αλλαγές σας χρησιμοποιώντας τον προσομοιωτή της Multi-Pascal.
2. Πριν να κάνετε αυτή την άσκηση κάντε πρώτα την 1.(γ)
(α) Εξηγήστε γιατί η πραγματική ταχύτητα εκτέλεσης του προγράμματος είναι ιδιαίτερα χαμηλή παρά το ότι δημιουργείται ένας μεγάλος αριθμός παράλληλων διεργασιών.
(β) Προσπαθώντας να αυξήσετε την ταχύτητα χρησιμοποιήστε την επιλογή GROUPING στη δήλωση FORALL και εκτελέστε το πρόγραμμα στον προσομοιωτή της Multi-Pascal. Εξηγείστε γιατί η ταχύτητα εξακολουθεί να είναι τόσο χαμηλή.
3. Στο κεφάλαιο αυτό έχει παρουσιαστεί η ακόλουθη μέθοδος εφαρμογής της λειτουργίας κλειδώματος :
Lock(L): Repeat X := TestandSet(L); (*Διαβάζει την παλιά κατάσταση του κλειδώματος και το ενεργοποιεί*) Until X = 0; (*Σταματά την επανάληψη του βρόχου αν το L ήταν απενεργοποιημένο*)
Για να δουλέψει αυτή η εφαρμογή καλά πρέπει η TestandSet να είναι αδιαίρετη εντολή γλώσσας μηχανής, δηλαδή όταν εκτελείται από έναν επεξεργαστή να μην μπορεί να διακοπεί από κάποιον άλλο.
Περιγράψτε με λεπτομέρειες πως μπορεί να δημιουργηθεί κάποιο λάθος αν η TestandSet δεν είναι αδιαίρετη. Περιγράψτε ένα συγκεκριμένο σενάριο για το πως κάποιο λάθος μπορεί να δημιουργηθεί σε αυτή την περίπτωση.
4. Στην εφαρμογή Lock(L) στην παράγραφο 5.2.1 μια τεχνική ενεργού αναμονής χρησιμοποιείται για την επαναληπτική εξέταση των περιεχομένων μιας θέσης μνήμης. Όταν υπάρχουν πολλές διεργασίες σε κατάσταση ενεργού αναμονής στο ίδιο κλείδωμα, μπορεί να συμβεί πρόβλημα ανταγωνισμού πρόσβασης στη μνήμη του πολυεπεξεργαστή, σύμφωνα με τις αρχές που αναπτύχθηκαν στο κεφάλαιo 3. Όμως, εάν το παράλληλο σύστημα έχει κρυφή μνήμη για κάθε πολυεπεξεργαστή, τότε αυτό το πρόβλημα ανταγωνισμού μπορεί να ελαχιστοποιηθεί προσθέτοντας την ακόλουθη εντολή μέσα στο βρόχο επανάληψης του Lock(L): While L<>0 Do ;
Εξηγείστε πώς αυτή η αλλαγή μειώνει το πρόβλημα του ανταγωνισμού.
5. Σε κάποια προγράμματα, μια διεργασία μπορεί να απαιτεί πρόσβαση σε διάφορα κλειδωμένα δεδομένα στην ίδια χρονική στιγμή. Η διεργασία μπορεί να πραγματοποιεί κάποια τροποποίηση σε διάφορα δεδομένα καθένα από τα οποία έχει και το δικό του κλείδωμα για προστασία. Στην περίπτωση αυτή, η διεργασία πρέπει να πραγματοποιήσει μια λειτουργία κλειδώματος σε κάθε ένα, να τροποποιήσει το καθένα και στη συνέχεια να απενεργοποιήσει κάθε κλείδωμα. Αν πολλές διεργασίες πραγματοποιούν πολλές λειτουργίες κλειδώματος με αυτόν τον τρόπο μπορεί να προκύψει ένα ενδιαφέρον πρόβλημα που ονομάζεται αδιέξοδο. Για την κατανόηση του προβλήματος έστω ότι έχουμε το παρακάτω σενάριο με δυο διεργασίες και δυο κλειδώματα :
Process 1 Process 2 .......... .......... Lock(A); Lock(B); Lock(B): Lock(A); ......... .......... Unlock(B); Unlock(A); Unlock(A); Unlock(B);
(α) Περιγράψτε ένα σενάριο εκτέλεσης για τις παραπάνω διεργασίες που καταλήγει σε αδιέξοδο - μια κατάσταση κατά την οποία δυο διεργασίες αναστέλλουν την εκτέλεσή τους για πάντα.
(β) Παρουσιάστε μια μικρή τροποποίηση στις δυο διεργασίες σύμφωνα με την οποία μπορούν να ενεργοποιήσουν και τα δύο κλειδώματα, να πραγματοποιήσουν τις ατομικές τους λειτουργίες αλλά να μην καταλήξουν σε αδιέξοδο.
(γ) Το ίδιο πρόβλημα μπορεί να προκύψει με πολλές διεργασίες και πολλά κλειδώματα. Μπορεί να εξαλειφθεί εντελώς με μια απλή τεχνική που δίνει στον προγραμματιστή ένα αυθαίρετο σχήμα αρίθμησης όλων των κλειδωμάτων. Κάθε διεργασία πρέπει να προγραμματιστεί έτσι ώστε να ακολουθεί τον παρακάτω κανόνα: όταν πολλά κλειδώματα πρόκειται να ενεργοποιηθούν στην ίδια χρονική στιγμή, τότε οι λειτουργίες κλειδώματος πρέπει να πραγματοποιηθούν κατά αύξουσα αριθμητική σειρά. Δείξτε πώς αυτή η τεχνική λύνει το πρόβλημα του αδιεξόδου.
6. Γράψτε μια διαδικασία σε Multi-Pascal που εισάγει ένα στοιχείο σε μια ταξινομημένη, συνδετική λίστα. Υποθέστε ότι αυτή η διαδικασία μπορεί να καλείται από πολλές διεργασίες παράλληλα για την τροποποίηση μιας απλής διαμοιραζόμενης λίστας. Για να μειώσετε την πιθανότητα ύπαρξης ανταγωνισμού, χρησιμοποιήστε ένα ξεχωριστό κλείδωμα για κάθε στοιχείο της λίστας παρά ένα κλείδωμα για όλη τη λίστα.
7. Γράψτε ένα πρόγραμμα σε Multi-Pascal που θα βρίσκει το μικρότερο στοιχείο ενός πίνακα. Υποθέστε ότι ο πίνακας είναι αρκετά μεγάλος, έτσι ώστε να μπορούν εύκολα να εφαρμοστούν παράλληλες διεργασίες στο πρόγραμμα. Γράψτε το παράλληλο πρόγραμμα για να ελαχιστοποιήσετε το συνολικό, παράλληλο χρόνο εκτέλεσης. Βεβαιωθείτε ότι έχετε λάβει υπόψη σας τα δυο σημαντικά στοιχεία της απόδοσης του προγράμματος - το μέγεθος των διεργασιών και τον ανταγωνισμό για τα διαμοιραζόμενα δεδομένα. Εκτελέστε και ελέγξτε το πρόγραμμά σας χρησιμοποιώντας το σύστημα αλληλεπίδρασης της Multi-Pascal.
8. Μια στοίβα δημιουργείται από τις ακόλουθες τρεις διαδικασίες :
Push(stack, x) εισάγει το στοιχείο x στην κορυφή της στοίβας Pop(stack, y) αφαιρεί το στοιχείο της κορυφής της στοίβας και το επιστρέφει στη μεταβλητή y Clear(stack) αρχικοποιεί τη στοίβα αφήνοντας τη κενή
Γράψτε τις παραπάνω διαδικασίες σεMulti-Pascal. Υποθέστε ότι πολλές παράλληλες διεργασίες μπορούν να χρησιμοποιούν τη δοσμένη στοίβα κατά την ίδια χρονική στιγμή. Ελέξτε τις διαδικασίες χρησιμοποιώντας το σύστημα αλληλεπίδρασης της Multi-Pascal. Στους ελέγχους χρησιμοποιήστε πολλές παράλληλες διεργασίες που προσπελαύνουν τη στοίβα.
9. Μια άλλη μέθοδος για την υλοποίηση αριθμητικής ολοκλήρωσης είναι ο κανόνας του Simpson. Για την ολοκλήρωση μιας συνάρτησης f μεταξύ δύο σημείων a και b, παίρνουμε δείγμα της συνάρτησης σε n εσωτερικά σημεία που διαφέρουν μεταξύ τους κατά απόσταση w. Ο τύπος είναι ο ακόλουθος :
(w/3)[f(a)+2f(a+w)+4f(a+2w)+2f(a+3w)+4f(a+4w)+…+2f(a+(n-1)w)+4f(a+nw)+f(b)]
Σε αυτό τον τύπο το n πρέπει να είναι περιττός αριθμός. Τροποποιήστε το πρόγραμμα της αριθμητικής ολοκλήρωσης του σχήματος 5.8 έτσι ώστε να χρησιμοποιηθεί ο κανόνας του Simpson.
10. Στο πρόγραμμα της αριθμητικής ολοκλήρωσης του σχήματος 5.8 φαίνεται ότι μάλλον θα υπάρξει κάποιος ανταγωνισμός όταν όλες οι διεργασίες τροποποιούν την μεταβλητή globalsum. Όμως όταν το πρόγραμμα αυτό εκτελείται μέσα στο περιβάλλον της Multi-Pascal δεν παρουσιάζεται κανένα πρόβλημα ανταγωνισμού κατά τη διάρκεια της τροποποίησης.
Ο λόγος για αυτή την απουσία ανταγωνισμού είναι η μέθοδος που ακολουθεί η Multi-Pascal στην δημιουργία διεργασιών. Οι διεργασίες δημιουργούνται μια κάθε φορά από μια διεργασία-γονέα. Υπάρχει ένα συγκεκριμένο χρονικό διάστημα που δαπανάται από τη διεργασία-γονέα για τη δημιουργία κάθε διεργασίας. Εξηγείστε πως αυτή η μέθοδος δημιουργίας των διεργασιών καταλήγει σε απουσίαανταγωνισμού κατά τη διάρκεια της τροποποίησης της μεταβλητής globalsum.
11. Στην αρχή του κεφαλαίου, δόθηκε ένα πρόγραμμα αναζήτησης σε ένα πίνακα με τη χρήση κλειδώματος. Ξαναγράψτε το πρόγραμμα χωρίς να χρησιμοποιήσετε κλείδωμα, αλλά χρησιμοποιώντας κανάλια σαν μηχανισμό δημιουργίας ατομικών λειτουργιών.
12. Γράψτε δυο διαδικασίες Readchan και Writechan που προσομοιώνουν το CHANNEL OF INTEGER της Multi-Pascal χρησιμοποιώντας μια συνδεδεμένη λίστα με τους δείκτες Head και Tail. Πρέπει να χρησιμοποιηθεί ένα κλείδωμα για την πρόληψη του αμοιβαίου αποκλεισμού.
Επόμενο:Κεφάλαιο 6ο : Σύγχρονος παραλληλισμός Πάνω: Κεφάλαιο 5ο : Μοίρασμα Δεδομένων Πίσω: Προγραμματιστικές Εργασίες