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

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

Προηγούμενα θέματα για σκέψη

Σε τι υπερέχουν και σε τι υστερούν οι δηλωτικές και σε τι οι αλγοριθμικές γλώσσες;
Περιγράψτε σε BNF τη γλώσσα με την οποία απαγγέλει την ώρα η φωνή στο 141. Λάβετε υπόψη σας ότι μηδενικά λεπτά και δευτερόλεπτα δεν απαγγέλονται.
Μεταγλωττίστε σε συμβολική γλώσσα 8086 τον υπολογισμό της έκφρασης της Pascal Sum := Sum + 2 * Element[i];

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

Είσοδος έξοδος παράλληλα με την εκτέλεση
Διακοπές και διαμερισμός χρόνου (time sharing)
Πολλαπλοί επεξεργαστές

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

Διεργασίες που διαβάζουν στοιχεία και παράγουν αποτελέσματα
Επικοινωνία μέσα από έναν αγωγό (pipe)
Αναμονή για γράψιμο ή ανάγνωση

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

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

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

bc | 
number | 
speak

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

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

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

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

Η ιδιότητα της ζωτικότητας (liveness) σε μια σειρά από παράλληλες (concurrent) διεργασίες σχετίζεται με το ρυθμό της προόδου που επιτυγχάνεται.

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

Αδιέξοδο (Deadlock)

Επανάλαβε
    Πιάσε το αριστερό πηρούνι
    Πιάσε το δεξί πηρούνι
    Φάε
    Άφησε τα πηρούνια
    Σκέψου
Τέλος

Ζωντανό αδιέξοδο (Livelock)

Επανάλαβε
    Πιάσε το αριστερό πηρούνι
    Αν δεν υπάρχει δεξί πηρούνι 
        Άσε το αριστερό πηρούνι 
        Επανάλαβε
    Τέλος
    Πιάσε το δεξί πηρούνι
    Φάε
    Άφησε τα πηρούνια
    Σκέψου
Τέλος

Δικαιοσύνη (Fairness)

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

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

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

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

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

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

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

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

Ο λογικός προγραμματισμός (logic programming) έχει ως θεωρητική βάση την κατηγορηματική λογική (predicate logic).

Νησί(Σάμος).

Διπλάσιο(4, 8).

Αγαπά(Γιώργος, Μαρία).

Δρομολόγιο(Αθήνα, Σάμος).
Δρομολόγιο(Σάμος, Αθήνα).
Δρομολόγιο(Αθήνα, Ηράκλειο).
Δρομολόγιο(Ηράκλειο, Αθήνα).

Δρομολόγιο(Α, Β) :-
   Δρομολόγιο(Α, Αθήνα),
   Δρομολόγιο(Αθήνα, Β).

? Δρομολόγιο(Σάμος, Αθήνα).
? Δρομολόγιο(Σάμος, Ηράκλειο).
? Δρομολόγιο(Σάμος, Αλεξανδρούπολη).

Επέκταση του σχεσιακού μοντέλου βάσεων δεδομένων
Πολυμορφικές λίστες και ταίριασμα σχημάτων
```
len([], 0).

len([H | T], L) :-
  len(T, L1),
  L is L1 + 1.
```
Αυτόματο ψάξιμο όλων των συνδυασμών
Δυνατότητα παράλληλης υλοποίησης
Δυνατότητα μαθηματικής απόδειξης της ορθότητας ενός προγράμματος

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

Ο συναρτησιακός προγραμματισμός (functional programming) έχει ως θεωρητική βάση την ανάλυση λ (lambda calculus)
```
λχ.+(χ 2) 1 = 3
```
Αναφορική διαφάνεια (referential transparency)
Πολυμορφικές λίστες και ταίριασμα σχημάτων
```
len [] = 0
len (h : t) = 1 + len t
```

Συναρτήσεις ως πολίτες πρώτης κατηγορίας

map f [] = []
map f (h : t) = (f h) : (map f t)

map ((+) 1) [5, 8, 10] = [6, 9, 11]

Δυνατότητα παράλληλης υλοποίησης
Δυνατότητα μαθηματικής απόδειξης της ορθότητας ενός προγράμματος

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

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

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 * π * ακτίνα * ακτίνα);
	}
}

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

Peter Rechenberg. Εισαγωγή στην Πληροφορική. σ. 164-191 Κλειδάριθμος, 1992.

Edsger W. Dijkstra. Co-operating sequential processes. In F. Genuys, editor, Programming Languages: NATO Advanced Study Institute, pages 43–112. Academic Press, London, 1968.
Anthony J. Field and Peter G. Harrison. Functional Programming. Addison-Wesley, 1988.
Adele Goldberg and David Robson. Smalltalk-80: The Language. Adison-Wesley, 1989.
C. A. R. Hoare. Communicating Sequential Processes. Prentice–Hall, 1985.
Christopher John Hogger. Introduction to Logic Programming. Academic Press, 1984.
John Hughes. Why functional programming matters. In David A. Turner, editor, Research Topics in Functional Programming, chapter 2, pages 17–42. Addison-Wesley, 1990. Also appeared in the April 1989 issue of The Computer Journal.
Brian W. Kernighan and Rob Pike. The UNIX Programming Environment. Prentice-Hall, 1984.
Robert Kowalski. Logic as a computer language. In Keith L. Clark and Sten-Åke Tärnlund, editors, Logic Programming, pages 3–16. Academic Press, 1982.
Richard A. O'Keefe. The Art of Prolog. MIT Press, 1990.
Lewis J. Pinson and Richard S. Wiener. An Introduction to Object-Oriented Programming and Smalltalk. Addison-Wesley, 1988.
Ravi Sethi. Programming Languages: Convepts and Constructs. Addison-Wesley, 1989.

Ασκήσεις

Περιγράψτε σε ψευδοκώδικα πως πρέπει να γίνεται ανάληψη χρημάτων από λογαριασμό με έλεγχο μη υπέρβασης του υπολοίπου. Χρησιμοποιήστε σηματοφόρους για να ελέγξετε το ενδεχόμενο ταυτόχρονης ανάληψης από δύο υποκαταστήματα.
Περιγράψτε λογικό πρόγραμμα για την εύρεση δρομολογίων ανάμεσα σε τυχαίες πόλεις.
Ορίστε κάνοντας χρήση της κληρονόμικότητας πιθανές ιδιότητες των παρακάτω τάξεων:
- Λιοντάρι
- Έμβιο
- Θηλαστικό
- Καρχαρίας
- Έντομο
- Ψάρι
Ζωγραφίστε τη σχέση των τάξεων με τη μορφή δέντρου.

Περιεχόμενα