Τι θα μάθεις;

Όταν ολοκληρώσεις το μάθημα αυτό, θα μπορείς: - Να εξηγείς τι είναι ο γράφος προβαδίσματος - Να αποφασίζεις πότε ένας γράφος προβαδίσματος παριστάνει διεργασίες που δεν μπορούν να εκτελεστούν - Να συμβολίζεις παράλληλες διεργασίες με τις εντολές parbegin και parend - Να περιγράφεις πώς φτιάχνουμε ένα πρόγραμμα με τις εντολές parbegin και parend από ένα γράφο προβαδίσματος

Ένας τρόπος για να αναπαραστήσουμε γραφικά τα ταυτόχρονα προγράμματα είναι να χρησιμοποιήσουμε το γράφο προβαδίσματος (precedence graph). Με τη βοήθεια ενός τέτοιου γράφου που αναπαριστά κάποιο πρόγραμμα, μπορούμε να δούμε ποια τμήματα του προγράμματος μπορούν να εκτελεστούν παράλληλα και ποια πρέπει να περιμένουν μέχρι να ολοκληρωθούν κάποια άλλα.

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

Ένας γράφος αποτελείται από κόμβους (vertices) και ακμές (edges). Μια ακμή συνδέει δυο κόμβους μεταξύ τους, και μπορεί να έχει ή όχι κατεύθυνση. Στην περίπτωση που η ακμή έχει κατεύθυνση ονομάζεται κατευθυνόμενη (directed).

Συνήθως σε ένα γράφο δεν εμφανίζονται μαζί κατευθυνόμενες και μη ακμές· όταν όλες οι ακμές είναι κατευθυνόμενες πρόκειται για ένα κατευθυνόμενο γράφο (directed graph), αλλιώς αποκαλείται απλώς γράφος.

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

Ένας καλός τρόπος για να φανταστούμε ένα γράφο είναι το οδικό δίκτυο μεταξύ πόλεων. Οι κόμβοι είναι οι πόλεις και οι ακμές είναι οι δρόμοι που συνδέουν ζεύγη πόλεων. Οι μονόδρομοι είναι κατευθυνόμενες ακμές, και οι δρόμοι διπλής κατευθύνσεως είναι μη κατευθυνόμενες ακμές.

Στο σχήμα οι κόμβοι του γράφου είναι οι «Αγρίνιο», «Αθήνα», «Θεσσαλονίκη», «Ιωάννινα», «Κόρινθος», «Λαμία» και «Πάτρα». Όλοι οι δρόμοι του γράφου είναι διπλής κατευθύνσεως, οπότε ο γράφος είναι απλός και κάθε ακμή μπορούμε να τη «διασχίσουμε» και προς τις δυο κατευθύνσεις. Αν είχε κάποιους μονόδρομους, τότε θα αντικαθιστούσαμε όλες τις απλές ακμές με δυο αντίθετης κατευθύνσεως. Έτσι για το δρόμο Θεσσαλονίκης-Ιωαννίνων, θα είχαμε μια ακμή Θεσσαλονίκη -> Ιωάννινα και μια Ιωάννινα -> Θεσσαλονίκη.

Σε ένα γράφο προβαδίσματος, κάθε διεργασία παριστάνεται με ένα κόμβο. Αν η διεργασία Δx πρέπει να έχει ολοκληρωθεί για να αρχίσει η Δy, τότε ο γράφος περιέχει μια κατευθυνόμενη ακμή από τον κόμβο της Δx σε αυτόν της Δy. Στην εποπτική αναπαράσταση του γράφου έχουμε ένα βέλος από τη Δx προς τη Δy.

Οι γράφοι προβαδίσματος είναι λοιπόν κατευθυνόμενοι και μια βασική ιδιότητά τους είναι ότι δεν έχουν κύκλους, είναι δηλαδή ακυκλικοί (acyclic). Ένας κύκλος είναι μια σειρά από ακμές την οποία μπορούμε να διασχίσουμε από κόμβο σε κόμβο, καταλήγοντας στο σημείο από όπου ξεκινήσαμε. Στο σχήμα του οδικού δικτύου ένας τέτοιος κύκλος είναι ο Κόρινθος -> Πάτρα -> Αγρίνιο -> Λαμία -> Αθήνα -> Κόρινθος.

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

Ο γράφος προβαδίσματος για το γλυκό που περιγράψαμε δίνεται στο σχήμα. Αν στο γράφο αυτό υπάρχει και μια ακμή ακόμα (η πράσινη γραμμή) από τη διεργασία «Ζύμη + ξηροί καρποί» στη διεργασία «Μαρέγκα», η οποία δημιουργεί ένα κύκλο θα έπρεπε: η ανάμιξη «Ζύμη + ξηροί καρποί» να γίνει πριν από τη «Μαρέγκα», η οποία πρέπει να γίνει πριν από την ανάμιξη «Μαρέγκα + άλλα υλικά», που πρέπει να γίνει πριν από τη «Ζύμη + ξηροί καρποί». Είναι φανερό ότι δεν είναι δυνατόν να παρασκευαστεί το γλυκό στην περίπτωση αυτή, εξαιτίας του κύκλου στο γράφο προβαδίσματος.

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

Ένα παράδειγμα ταυτόχρονου προγράμματος σε ένα υπολογιστή είναι η αριθμητική έκφραση x1 x x2 - (x3 - x4) / x5. Αν αναλύσουμε την έκφραση σε μερικά αποτελέσματα έχουμε μ1:= x1 x x2, μ2:= x3 - x4, μ3 := μ2 / x5, α:= μ1 - μ3. Για να υπολογιστεί ένα μερικό αποτέλεσμα, πρέπει να είναι διαθέσιμες όλες οι τιμές που χρησιμοποιεί, π.χ. για να υπολογιστεί το μ3 χρειάζονται οι τιμές των μ2 και x5.

Αν αντιστοιχίσουμε κάθε μερικό αποτέλεσμα σε μια διεργασία, η εξάρτηση των μερικών αποτελεσμάτων από άλλα μας δίνει το γράφο προβαδίσματος για την έκφραση, από όπου φαίνεται ότι π.χ. τα μ1 και μ2 ή τα μ1 και μ3 μπορούν να υπολογιστούν ταυτόχρονα, γιατί δε συνδέονται με κάποιο μονοπάτι, ενώ τα μ2 και μ3 που συνδέονται δεν μπορούν να υπολογιστούν ταυτόχρονα.

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