Ασκήσεις

Επόμενο:Κεφάλαιο 5ο : Μοίρασμα Δεδομένων Πάνω: Κεφάλαιο 4o : Επικοινωνία διεργασιών Πίσω: Προγραμματιστικές Εργασίες

ΑΣΚΗΣΕΙΣ

1. Στο παράδειγμα Παραγωγού - Καταναλωτή του Σχήματος 4.3 ο τερματισμός της επικοινωνίας σηματοδοτείται με την χρήση της τιμής end-marker στο κανάλι. Μια εναλλακτική μέθοδος για τον έλεγχο της επικοινωνίας είναι να επιτρέψετε η πρώτη τιμή που στέλνεται μέσω του καναλιού να είναι ο συνολικός αριθμός από τις επόμενες τιμές που θα σταλούν μέσω του καναλιού. Ξαναγράψτε το παράδειγμα Παραγωγού - Καταναλωτή χρησιμοποιώντας αυτή τη νέα τεχνική.

2. Γράψτε ένα πρόγραμμα που να περιλαμβάνει 2 διεργασίες - την διεργασία Ανάγνωσης και την διεργασία Εγγραφής. Η διεργασία Ανάγνωσης διαβάζει μια σειρά τιμές από τον χρήστη και τις στέλνει στην διεργασία εγγραφής μέσω του καναλιού. Η διεργασία Εγγραφής διαβάζει τις τιμές από το κανάλι και τις γράφει στην οθόνη. Το τέλος των τιμών σηματοδοτείται με μια ειδική τιμή τέλους ροής.

3. Αλλάξτε το παράδειγμα Παραγωγού - Καταναλωτή του Σχήματος 4.3 για να ελαχιστοποιήσετε την αναγκαιότητα της τιμής endmarker χρησιμοποιώντας τον καταναλωτή για να ελέγξετε αν το κανάλι είναι άδειο όπως φαίνεται παρακάτω:

BEGIN (*Διεργασία Καταναλωτής*)


    WHILE commchan? DO


    BEGIN


        outval := commchan;


        ... (* Χρησιμοποιήστε την “outval” σε μερικούς υπολογισμούς*)


    END;

Εξηγείστε γιατί αυτή η διαφοροποίηση μπορεί να δουλέψει για μερικές διαδικασίες Παραγωγού-Καταναλωτή ενώ για άλλες όχι. Περιγράψτε ένα πιθανό σενάριο επικοινωνίας που θα προκαλέσει λάθος στο πρόγραμμα.

4. Γράψτε ένα πρόγραμμα που να διαβάζει 10 τιμές από ένα κανάλι και να τις γράφει σε ένα άλλο κανάλι. Αυτό μπορεί να γίνει με την χρήση ενός απλού βρόχου.

5. Γράψτε ένα πρόγραμμα που να μετράει τον αριθμό των στοιχείων που υπάρχουν σε ένα κανάλι, έτσι ώστε το κανάλι να επιστρέφει στην αρχική του κατάσταση μετά την μέτρηση. Αυτό μπορεί να γίνει γράφοντας πρώτα το ειδικό σύμβολο endmarker στο κανάλι και μετά διαβάζοντας τις τιμές σειριακά από το κανάλι έως ότου μετρηθεί και το endmarker. Kαθώς κάθε τιμή διαβάζεται γράφεται ταυτόχρονα στο κανάλι. Για να εξασφαλιστεί ότι το endmarker απομακρύνεται από το κανάλι πρέπει το κανάλι να επιστρέψει στην αρχική του κατάσταση.

6. Θεωρήστε την γενική μορφή ενός προγράμματος διασωλήνωσης, στο οποίο μια μεγάλη σειρά από τιμές δεδομένων συνεχίζουν να ρέουν διαμέσω της διασωλήνωσης. Σε αυτή την γενική μορφή διασωλήνωσης διαφορετικοί τύποι λειτουργιών μπορούν να εκτελούνται από διαφορετικές διεργασίες. Υποθέστε ότι η συγκεκριμένη λειτουργία που εκτελείται από κάθε διεργασία i απαιτεί Τ_i μονάδες χρόνου. Επιτρέψτε στην διεργασία k να είναι αυτή με τον μεγαλύτερο χρόνο. Εξηγείστε γιατί ο χρόνος Τ_κ περιορίζει την απόδοση της διασωλήνωσης, ακόμα και αν όλα τα υπόλοιπα Τ_i είναι μικρότερα από το Τ_κ .

7. Σε αυτό το κεφάλαιο, δόθηκε το παρακάτω σειριακό πρόγραμμα της προς τα πίσω αντικατάστασης:

FOR i:=1 TO n DO

    BEGIN (* Επίλυση της i εξίσωσης για την τιμή xi *)
	
        sum:=0;
		
        FOR j:=1 TO i-1 DO
		
           sum:=sum+A[i,j]*x[j];
		   
        x[i]:=(B[i]-sum)/A[i,i];
		
    END;

Στην προσπάθεια να μετατρέψουμε το παραπάνω πρόγραμμα σε παράλληλο, υποθέστε ότι ο εξωτερικός βρόχος FOR αντικαθίσταται από μια πρόταση FORALL.

(α) Εξηγείστε γιατί το παράλληλο πρόγραμμα που προκύπτει από αυτή τη αντικατάσταση δεν είναι σωστό. Δείξτε λεπτομερειακά πως μπορεί σε αυτή την περίπτωση να πραγματοποιηθεί κάποιος λανθασμένος υπολογισμός.

(β) Φανταστείτε ένα πολυεπεξεργαστή στον οποίο ο χρόνος δημιουργίας μιας διεργασίας είναι μεγαλύτερος από το χρόνο εκτέλεσης κάθε επανάληψης του εσωτερικού βρόχου FOR. Κάτω από αυτές τις ειδικές συνθήκες, το παράλληλο πρόγραμμα θα παράγει το σωστό αποτέλεσμα. Εξηγείστε τους λόγους που συμβαίνει κάτι τέτοιο.

8. Αναφέρεται σε αυτό το κεφάλαιο ότι το παράλληλο πρόγραμμα της προς τα πίσω αντικατάστασης έχει χρόνο εκτέλεσης O(n). Δώστε μια εξήγηση της πρότασης βασισμένη στη δομή του κώδικα του προγράμματος.

9. Στο σχεδιάγραμμα 4.8 παρουσιάζεται το διάγραμμα εκτέλεσης του προγράμματος της προς τα πίσω αντικατάστασης. Παρατηρώντας το διάγραμμα, είναι δυνατόν να καταλήξουμε στο συμπέρασμα ότι η σπατάλη δημιουργίας των διεργασιών δεν επηρεάζει το χρόνο εκτέλεσης του προγράμματος.

(α) Δικαιολογείστε την πρόταση αναφορικά με το κόστος δημιουργίας των διεργασιών.

(β) Εάν το κόστος δημιουργίας των διεργασιών ήταν μεγαλύτερο τότε θα επηρέαζε το χρόνο εκτέλεσης του προγράμματος. Προσεγγιστικά πόσο μεγάλο πρέπει να είναι το κόστος ώστε να επηρεάσει το χρόνο εκτέλεσης του προγράμματος;

10. Στο πρόγραμμα διασωλήνωσης με p διεργασίες, μια σειρά από n τιμές δεδομένων διαπερνάει την διασωλήνωση από την αρχή μέχρι το τέλος. Κάθε διεργασία στην διασωλήνωση μεταβάλλει κάθε τιμή δεδομένων που απαιτεί Τ μονάδες χρόνου και μετά την στέλνει στην επόμενη διεργασία. Ο χρόνος επικοινωνίας μεταξύ των διεργασιών είναι C μονάδες χρόνου. Το πρόγραμμα τερματίζει όταν και οι n τιμές δεδομένων περνούν την διασωλήνωση. Θεωρώντας την αμελητέα σπατάλη από την δημιουργία της διεργασίας, παράγετε μια αλγεβρική έκφραση για τον χρόνο εκτέλεσης του προγράμματος, την επιτάχυνση, και την μέση απόδοση του επεξεργαστή.

11. Θεωρήστε τις παρακάτω δηλώσεις:



TYPE artyp = ARRAY [1..20] OF INTEGER;


     rectyp = RECORD


               a, b : INTEGER;


               c: REAL;


               END;


VAR achan: CHANNEL OF artyp;


    rchan: CHANNEL OF rectyp;

Για κάθε ένα από τα παρακάτω, γράψτε τις απαραίτητες προτάσεις εντολών. Συμπεριλάβετε και τις δηλώσεις για όλες τις μεταβλητές που χρησιμοποιούνται:

α) Απομακρύνετε όλα τα στοιχεία που υπάρχουν στο κανάλι achan.

β)Γράψτε τις τιμές των a και b από το πρώτο στοιχείο στο κανάλι rchan.

γ)Δημιουργήστε ένα πίνακα που να περιέχει τους αριθμούς από 101 έως 120 και γράψτε αυτόν τον πίνακα στο κανάλι achan.

δ)Δημιουργήστε μια εγγραφή rectyp διαβάζοντας τρεις τιμές και γράψτε αυτήν την εγγραφή στο κανάλι rchan.

ε)Γράψτε το πέμπτο και δέκατο στοιχείο του πίνακα στην αρχή του καναλιού achan.