Παραλληλία και προγραμματιστικά παραδείγματα

Διομήδης Σπινέλλης
 Τμήμα Διοικητικής Επιστήμης και Τεχνολογίας
Οικονομικό Πανεπιστήμιο Αθηνών
dds@aueb.gr

Παραλληλία σε επίπεδο υλικού

Παραλληλία με τη χρήση αγωγών

Παραδείγματα

Ανάγνωση αποτελεσμάτων

υπολογισμός |
μετατροπή σε λέξη |
φωνητική ανάγνωση

bc | 
number | 
speak

Συχνότητα λέξεων

Μετατροπή κειμένου σε λέξεις |
φιλτράρισμα λέξεων |
ταξινόμηση |
μέτρηση κοινών γραμμών |
ταξινόμηση

tr -cs A-Za-z '\012' | 
grep '^A-Za-z' | 
sort | 
uniq -c | 
sort -rn

Ιδιότητες ζωτικότητας

Η ιδιότητα της ζωτικότητας (liveness) σε μια σειρά από παράλληλες (concurrent) διεργασίες σχετίζεται με το ρυθμό της προόδου που επιτυγχάνεται. Ένα σύνολο διεργασιών βρίσκεται σε αδιέξοδο (deadlock) αν κάθε διεργασία του συνόλου περιμένει ένα γεγονός που μόνο μια άλλη διεργασία του συνόλου μπορεί να προκαλέσει. (Tanenbaum)

Τα αδιέξοδα δημιουργούνται ως αποτέλεσμα της διαχείρισης των πόρων από τις διαδικασίες. Κάθε πόρος (resource) μπορεί να είναι προεκχωρήσιμος (preemptable) δηλαδή να αποδεσμευτεί από μια διεργασία που τον κατέχει χωρίς παρενέργιες ή μη προεκχωρήσιμος (nonpreemptable). Παραδείγματα της πρώτης κατηγορίας είναι ο δίσκος και η μνήμη. Παραδείγματα της δεύτερης κατηγορίας είναι ο εκτυπωτής και η μονάδα ταινίας. Τυπικά μια διεργασία χρησιμοποιεί έναν πόρο ως εξής:

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

Οι δειπνούντες φιλόσοφοι

Αδιέξοδο 
Επανάλαβε
    Πιάσε το αριστερό πηρούνι
    Πιάσε το δεξί πηρούνι
    Φάε
    Άφησε τα πηρούνια
    Σκέψου
Τέλος
Ζωντανό αδιέξοδο (Livelock) 
Επανάλαβε
    Πιάσε το αριστερό πηρούνι
    Αν δεν υπάρχει δεξί πηρούνι 
        Άσε το αριστερό πηρούνι 
        Επανάλαβε
    Τέλος
    Πιάσε το δεξί πηρούνι
    Φάε
    Άφησε τα πηρούνια
    Σκέψου
Τέλος
Δικαιοσύνη (Fairness) 
Επανάλαβε
    Περίμενε να ελευθερωθούν και τα δύο πηρούνια
    Πιάσε το αριστερό και το δεξί πηρούνι
    Φάε
    Άφησε τα πηρούνια
    Σκέψου
Τέλος

Ιδιότητες ασφάλειας

Η ιδιότητα της ασφάλειας (safety) σε μια σειρά από παράλληλες διεργασίες σχετίζεται με την επίτευξη του σωστού αποτελέσματος.

Κράτηση εισιτηρίων

Αν υπάρχει θέση
   Κράτησε ένα εισητήριο
Τέλος

Αλληλοαποκλεισμός (Mutual exclusion) με βάση σηματοφόρο (semaphore)

P(Κράτηση)
    Αν υπάρχει θέση
       Κράτησε ένα εισητήριο
    Τέλος
V(Κράτηση)

Προγραμματισμός με βάση τη λογική

Προγραμματισμός με βάση τις συναρτήσεις

Προγραμματισμός με βάση τα αντικείμενα

class σχήμα {
        int χρώμα;

        void χρωμάτισε(int χρώμα) {
                this.χρώμα = χρώμα;
                ζωγράφισε();
        }
};

class τετράγωνο extends σχήμα {
        int x1, y1, x2, y2;

        void ζωγράφισε(void) {
                line(x1, y1, x1, y2, χρώμα);
                line(x1, y1, x2, y1, χρώμα);
                line(x2, y2, x1, y2, χρώμα);
                line(x2, y2, x2, y1, χρώμα);
        }
        int εμβαδό(void) {
                return (abs(x2 - x1) * abs(y2 - y1));
        }
}

class κύκλος extends σχήμα {
        int x, y, ακτίνα;

        void ζωγράφισε(void) {
                circle(x, y, ακτίνα, χρώμα);
        }
        int εμβαδό(void) {
                return (2 * π * ακτίνα * ακτίνα);
        }
}

Βιβλιογραφία

Ασκήσεις

Creative Commons License  Τελευταία αλλαγή: Δευτέρα, 2 Αυγούστου 2004 12:30 πμ
 Εκτός αν αναφέρεται κάτι διαφορετικό, όλο το πρωτότυπο υλικό της σελίδας αυτής του οποίου δημιουργός είναι ο Διομήδης Σπινέλλης παρέχεται σύμφωνα με τους όρους της άδειας «Creative Commons Attribution-Share Alike 3.0 Greece License».