.
Στην επιστήμη υπολογιστών, ο ταυτοχρονισμός (concurrency) είναι η ιδιότητα ενός συστήματος, στο οποίο εκτελούνται ταυτόχρονα πολλοί υπολογισμοί, που μπορούν να αλληλεπιδρούν μεταξύ τους. Οι υπολογισμοί μπορεί να εκτελούνται σε πολλούς πυρήνες του ίδιου τσιπ, σαν χρονοπρογραμματισμένα νήματα στον ίδιο επεξεργαστή, ή σε φυσικά διακριτούς επεξεργαστές.
Έχουν αναπτυχθεί διάφορα μαθηματικά μοντέλα για γενικούς ταυτόχρονους υπολογισμούς, μεταξύ αυτών τα δίκτυα Πέτρι (Petri nets), οι λογισμοί διεργασιών (process calculi), το μοντέλο της Παράλληλης Μηχανής Τυχαίας Προσπέλασης (Parallel Random Access Machine) και το μοντέλο Actor.
Προβλήματα
Επειδή οι υπολογισμοί σε ένα ταυτόχρονο σύστημα μπορεί να αλληλεπιδρούν καθώς εκτελούνται, ο αριθμός των πιθανών μονοπατιών εκτέλεσης στο σύστημα μπορεί να είναι πολύ μεγάλος και το τελικό αποτέλεσμα να μην προσδιορίζεται. Η ταυτόχρονη χρήση κοινόχρηστων πόρων μπορεί να προκαλεί αυτήν την απροσδιοριστία, με αποτέλεσμα να προκύπτουν αδιέξοδα (deadlocks) και η λιμοκτονία πόρων (resource starvation).[1]
Η σχεδίαση ταυτόχρονων συστημάτων συχνά απαιτεί τεχνικές συντονισμού της εκτέλεσής τους, ανταλλαγής δεδομένων, δέσμευσης μνήμης και χρονοπρογραμματισμού της εκτέλεσης, ώστε να ελαχιστοποιείται ο χρόνος απόκρισης και να μεγιστοποιείται η απόδοση του συστήματος.
Θεωρία
Η θεωρία του ταυτοχρονισμού είναι ενεργό ερευνητικό πεδίο της θεωρητικής πληροφορικής. Μια από τις πρώτες συνεισφορές ήταν η σημαντική δουλειά του Καρλ Άνταμ Πέτρι (Carl Adam Petri) στα δίκτυα Πέτρι στις αρχές της δεκαετίας του 1960. Στο χρόνια που ακολούθησαν, αναπτύχθηκαν πολλοί φορμαλισμοί για τη μοντελοποίηση και τη συλλογιστική του ταυτοχρονισμού.
Μοντέλα
Έχουν αναπτυχθεί αρκετοί φορμαλισμοί για τη μοντελοποίηση και την κατανόηση των ταυτόχρονων συστημάτων, κάποιοι από αυτούς είναι:[2]
Η Παράλληλη Μηχανή Τυχαίας Προσπέλασης (Parallel Random Access Machine)[3]
Το μοντέλο Actor
Μοντέλα υπολογιστικής γεφύρωσης (computational bridging models) όπως το BSP
Τα δίκτυα Πέτρι
Οι λογισμοί διεργασιών
Οι χώροι ν-άδων (tuple spaces), όπως στη Linda
Το μοντέλο SCOOP
Κάποια από αυτά τα μοντέλο ταυτοχρονισμού έχουν σαν κύριο σκοπό τους να υποστηρίξουν τη συλλογιστική και τον ορισμό ταυτόχρονων συστημάτων, ενώ άλλα μπορούν να χρησιμοποιηθούν σε ολόκληρο τον κύκλο ανάπτυξης, συμπεριλαμβανομένης της σχεδίασης, της υλοποίησης, της απόδειξης, της δοκιμής και της εξομοίωσης των ταυτόχρονων συστημάτων.
Η ποικιλία διαφορετικών μοντέλων για τον ταυτοχρονισμό έκανε κάποιους ερευνητές να αναπτύξουν τρόπους να ενοποιήσουν αυτά τα διαφορετικά θεωρητικά μοντέλα. Για παράδειγμα, οι Lee και Sangiovanni-Vincentelli έδειξαν ότι ένα μοντέλο "tagged-signal" μπορεί να είναι ένα κοινό πλαίσιο για τον ορισμό δηλωτικής σημασιολογίας για αρκετά μοντέλα ταυτοχρονισμού,[4] ενώ οι Nielsen, Sassone και Winskel έδειξαν ότι η θεωρία κατηγοριών μπορεί να χρησιμοποιηθεί για να παρέχει μια παρόμοια ενοποιημένη θεώρηση διαφορετικών μοντέλων.[5]
Το Θεώρημα Αναπαράστασης του Ταυτοχρονισμού (Concurrency Representation Theorem) στο μοντέλο Actor παρέχει έναν αρκετά γενικό τρόπο να αναπαριστώνται ταυτόχρονα συστήματα που είναι κλειστά και δε λαμβάνουν μηνύματα επικοινωνίας από τον εξωτερικό κόσμο. (Άλλα συστήματα ταυτοχρονισμού, όπως οι λογισμοί διεργασιών, μπορούν να μοντελοποιηθούν στο μοντέλο Actor χρησιμοποιώντας το two-phase commit protocol.[6]) Η μαθηματική σημασία που δηλώνεται από ένα κλειστό σύστημα S κατασκευάζεται από διαδοχικές βελτιωμένες προσεγγίσεις από μια αρχική συμπεριφορά που αποκαλείται ⊥S, με τη χρήση μιας συνάρτησης εκτίμησης συμπεριφοράς progressionS για την κατασκευή μιας σημασίας για το S ως εξής:[7]
DenoteS ≡ ⊔i∈ω progressionSi(⊥S)
Κατά αυτόν τον τρόπο, το S μπορεί να χαρακτηριστεί μαθηματικά με βάση όλες τις πιθανές συμπεριφορές του.
Λογικές
Μπορούν να χρησιμοποιηθούν διάφοροι τύποι χρονικής λογικής[8] για την ανάλυση ταυτόχρονων συστημάτων. Κάποιες από αυτές τις λογικές, όπως η γραμμική χρονική λογική και η λογική υπολογιστικού δένδρου, επιτρέπουν βεβαιώσεις για ακολουθίες καταστάσεων, από τις οποίες μπορεί να περάσει ένα ταυτόχρονο σύστημα. Άλλες, όπως η λογική ενεργειών υπολογιστικού δένδρου (action computational tree logic), η λογική Hennessy-Milner και η Χρονική Λογική των Ενεργειών του Leslie Lamport, κατασκευάζουν τις βεβαιώσεις τους από ακολουθίες ενεργειών (actions), που είναι οι αλλαγές κατάστασης. Η βασική εφαρμογή αυτών των λογικών είναι στη συγγραφή προδιαγραφών για ταυτόχρονα συστήματα.[1]
Στην πράξη
Ο ταυτόχρονος προγραμματισμός περιλαμβάνει τις γλώσσες προγραμματισμού και τους αλγορίθμους που χρησιμοποιούνται στην υλοποίηση ταυτόχρονων συστημάτων. Ο ταυτόχρονος προγραμματισμός (concurrent programming) συχνά θεωρείται γενικότερος από τον παράλληλο προγραμματισμό (parallel programming) γιατί μπορεί να έχει αυθαίρετες και δυναμικές μορφές επικοινωνίας και αλληλεπίδρασης, ενώ τα παράλληλα συστήματα έχουν συνήθως προκαθορισμένο και καλά δομημένο τρόπο επικοινωνίας. Οι βασικοί σκοποί του ταυτόχρονου προγραμματισμού είναι η ορθότητα (correctness), η ταχύτητα (performance) και η ανθεκτικότητα (robustness). Ταυτόχρονα συστήματα όπως τα λειτουργικά συστήματα και τα συστήματα διαχείρισης βάσεων δεδομένων γενικά σχεδιάζονται για να εκτελούνται χωρίς χρονικό όριο, με αυτόματη ανάκαμψη από σφάλματα, χωρίς να τερματίζουν απροσδόκητα (δείτε Έλεγχος ταυτοχρονισμού). Κάποια ταυτόχρονα συστήματα υλοποιούν μια μορφή διαφανούς (transparent) ταυτοχρονισμού, στον οποίο οι ταυτόχρονες υπολογιστικές οντότητες μπορούν να ανταγωνίζονται για έναν πόρο, αλλά οι λεπτομέρειες αυτού του ανταγωνισμού να μη φαίνονται στον προγραμματιστή.
Επειδή χρησιμοποιούν κοινόχρηστους πόρους, τα ταυτόχρονα συστήματα γενικά απαιτούν κάποια μορφή διαιτησίας (arbiter) στην υλοποίησή τους (συχνά το ίδιο το υλικό), για να ελέγχεται η πρόσβαση σε αυτούς τους πόρους. Η χρήση διαιτητών εισάγει την πιθανότητα απροσδιοριστίας, που έχει συνέπειες στην πράξη, ειδικά στην ορθότητα και στην ταχύτητα. Για παράδειγμα, η διαιτησία εισάγει μη-ντετερμινισμό χωρίς άνω όριο (unbounded nondeterminism), ο οποίος προκαλεί προβλήματα στον έλεγχο μοντέλων γιατί προκύπτει έκρηξη του χώρου των καταστάσεων, σε σημείο που τα μοντέλα μπορεί να έχουν ακόμα και άπειρο αριθμό καταστάσεων.
Κάποια μοντέλα ταυτόχρονου προγραμματισμού περιλαμβάνουν συν-διεργασίες (coprocesses) και ντετερμινιστικό ταυτοχρονισμό. Σε αυτά τα μοντέλα, τα νήματα του ελέγχου επιστρέφουν ρητά τις θυρίδες χρόνου που τους δίνονται, είτε στο σύστημα, είτε σε κάποια άλλη διεργασία.
Δείτε επίσης
Έλεγχος Ταυτοχρονισμού
Μοντέλο πελάτη-διακομιστή
Νήμα (υπολογιστές)
Παράλληλα και κατανεμημένα συστήματα
Επικοινωνούσες Ακολουθιακές Διεργασίες (Communicating Sequential Processes, CSP)
OpenMP
Παραπομπές
Cleaveland, Rance; Scott Smolka (December, 1996). «Strategic Directions in Concurrency Research». ACM Computing Surveys 28 (4): 607. doi:10.1145/242223.242252.
Filman, Robert; Daniel Friedman (1984). Coordinated Computing - Tools and Techniques for Distributed Software. McGraw-Hill. ISBN 0-07-022439-0.
Keller, Jörg; Christoph Keßler, Jesper Träff (2001). Practical PRAM Programming. John Wiley and Sons.
Lee, Edward; Alberto Sangiovanni-Vincentelli (December, 1998). «A Framework for Comparing Models of Computation». IEEE Transactions on CAD 17 (12): 1217–1229. doi:10.1109/43.736561.
Mogens Nielsen (1993). «Relationships Between Models of Concurrency». REX School/Symposium.
Frederick Knabe. A Distributed Protocol for Channel-Based Communication with Choice PARLE 1992.
William Clinger (June 1981). Foundations of Actor Semantics. Mathematics Doctoral Dissertation. MIT.
Roscoe, Colin (2001). Modal and Temporal Properties of Processes. Springer. ISBN 0-387-98717-7.
Περαιτέρω διάβασμα
Lynch, Nancy A. (1996). Distributed Algorithms. Morgan Kauffman. ISBN 1558603484.
Tanenbaum, Andrew S.; Van Steen, Maarten (2002). Distributed Systems: Principles and Paradigms. Prentice Hall. ISBN 0-13-088893-1.
Kurki-Suonio, Reino (2005). A Practical Theory of Reactive Systems. Springer. ISBN 3-540-23342-3.
Garg, Vijay K. (2002). Elements of Distributed Computing. Wiley-IEEE Press. ISBN 0-471-03600-5.
Magee, Jeff;, Kramer, Jeff (2006). Concurrency: State Models and Java Programming. Wiley. ISBN 0-470-09355-2.
Εξωτερικοί σύνδεσμοι
Concurrent Systems, The WWW Virtual Library (Αγγλικά)
Hellenica World - Scientific Library
Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License
