Ταυτοχρονισμός

Στην επιστήμη υπολογιστών, ο ταυτοχρονισμός (concurrency) είναι η ιδιότητα ενός συστήματος, στο οποίο εκτελούνται ταυτόχρονα πολλοί υπολογισμοί, που μπορούν να αλληλεπιδρούν μεταξύ τους. Οι υπολογισμοί μπορεί να εκτελούνται σε πολλούς πυρήνες του ίδιου τσιπ, σαν χρονοπρογραμματισμένα νήματα στον ίδιο επεξεργαστή, ή σε φυσικά διακριτούς επεξεργαστές.
Έχουν αναπτυχθεί διάφορα μαθηματικά μοντέλα για γενικούς ταυτόχρονους υπολογισμούς, μεταξύ αυτών τα δίκτυα Πέτρι (Petri nets), οι λογισμοί διεργασιών (process calculi), το μοντέλο της Παράλληλης Μηχανής Τυχαίας Προσπέλασης (Parallel Random Access Machine) και το μοντέλο Actor.

Προβλήματα

Επειδή οι υπολογισμοί σε ένα ταυτόχρονο σύστημα μπορεί να αλληλεπιδρούν καθώς εκτελούνται, ο αριθμός των πιθανών μονοπατιών εκτέλεσης στο σύστημα μπορεί να είναι πολύ μεγάλος και το τελικό αποτέλεσμα να μην προσδιορίζεται. Η ταυτόχρονη χρήση κοινόχρηστων πόρων μπορεί να προκαλεί αυτήν την απροσδιοριστία, με αποτέλεσμα να προκύπτουν αδιέξοδα (deadlocks) και η λιμοκτονία πόρων (resource starvation).
Η σχεδίαση ταυτόχρονων συστημάτων συχνά απαιτεί τεχνικές συντονισμού της εκτέλεσής τους, ανταλλαγής δεδομένων, δέσμευσης μνήμης και χρονοπρογραμματισμού της εκτέλεσης, ώστε να ελαχιστοποιείται ο χρόνος απόκρισης και να μεγιστοποιείται η απόδοση του συστήματος.

Θεωρία

Η θεωρία του ταυτοχρονισμού είναι ενεργό ερευνητικό πεδίο της θεωρητικής πληροφορικής. Μια από τις πρώτες συνεισφορές ήταν η σημαντική δουλειά του Καρλ Άνταμ Πέτρι (Carl Adam Petri) στα δίκτυα Πέτρι στις αρχές της δεκαετίας του 1960. Στο χρόνια που ακολούθησαν, αναπτύχθηκαν πολλοί φορμαλισμοί για τη μοντελοποίηση και τη συλλογιστική του ταυτοχρονισμού.

Λογικές

Μπορούν να χρησιμοποιηθούν διάφοροι τύποι χρονικής λογικής για την ανάλυση ταυτόχρονων συστημάτων. Κάποιες από αυτές τις λογικές, όπως η γραμμική χρονική λογική και η λογική υπολογιστικού δένδρου, επιτρέπουν βεβαιώσεις για ακολουθίες καταστάσεων, από τις οποίες μπορεί να περάσει ένα ταυτόχρονο σύστημα. Άλλες, όπως η λογική ενεργειών υπολογιστικού δένδρου (action computational tree logic), η λογική Hennessy-Milner και η Χρονική Λογική των Ενεργειών του Leslie Lamport, κατασκευάζουν τις βεβαιώσεις τους από ακολουθίες ενεργειών (actions), που είναι οι αλλαγές κατάστασης. Η βασική εφαρμογή αυτών των λογικών είναι στη συγγραφή προδιαγραφών για ταυτόχρονα συστήματα.

Στην πράξη

Ο ταυτόχρονος προγραμματισμός περιλαμβάνει τις γλώσσες προγραμματισμού και τους αλγορίθμους που χρησιμοποιούνται στην υλοποίηση ταυτόχρονων συστημάτων. Ο ταυτόχρονος προγραμματισμός (concurrent programming) συχνά θεωρείται γενικότερος από τον παράλληλο προγραμματισμό (parallel programming) γιατί μπορεί να έχει αυθαίρετες και δυναμικές μορφές επικοινωνίας και αλληλεπίδρασης, ενώ τα παράλληλα συστήματα έχουν συνήθως προκαθορισμένο και καλά δομημένο τρόπο επικοινωνίας. Οι βασικοί σκοποί του ταυτόχρονου προγραμματισμού είναι η ορθότητα (correctness), η ταχύτητα (performance) και η ανθεκτικότητα (robustness). Ταυτόχρονα συστήματα όπως τα λειτουργικά συστήματα και τα συστήματα διαχείρισης βάσεων δεδομένων γενικά σχεδιάζονται για να εκτελούνται χωρίς χρονικό όριο, με αυτόματη ανάκαμψη από σφάλματα, χωρίς να τερματίζουν απροσδόκητα (δείτε Έλεγχος ταυτοχρονισμού). Κάποια ταυτόχρονα συστήματα υλοποιούν μια μορφή διαφανούς (transparent) ταυτοχρονισμού, στον οποίο οι ταυτόχρονες υπολογιστικές οντότητες μπορούν να ανταγωνίζονται για έναν πόρο, αλλά οι λεπτομέρειες αυτού του ανταγωνισμού να μη φαίνονται στον προγραμματιστή.
Επειδή χρησιμοποιούν κοινόχρηστους πόρους, τα ταυτόχρονα συστήματα γενικά απαιτούν κάποια μορφή διαιτησίας (arbiter) στην υλοποίησή τους (συχνά το ίδιο το υλικό), για να ελέγχεται η πρόσβαση σε αυτούς τους πόρους. Η χρήση διαιτητών εισάγει την πιθανότητα απροσδιοριστίας, που έχει συνέπειες στην πράξη, ειδικά στην ορθότητα και στην ταχύτητα. Για παράδειγμα, η διαιτησία εισάγει μη-ντετερμινισμό χωρίς άνω όριο (unbounded nondeterminism), ο οποίος προκαλεί προβλήματα στον έλεγχο μοντέλων γιατί προκύπτει έκρηξη του χώρου των καταστάσεων, σε σημείο που τα μοντέλα μπορεί να έχουν ακόμα και άπειρο αριθμό καταστάσεων.
Κάποια μοντέλα ταυτόχρονου προγραμματισμού περιλαμβάνουν συν-διεργασίες (coprocesses) και ντετερμινιστικό ταυτοχρονισμό. Σε αυτά τα μοντέλα, τα νήματα του ελέγχου επιστρέφουν ρητά τις θυρίδες χρόνου που τους δίνονται, είτε στο σύστημα, είτε σε κάποια άλλη διεργασία.