Διδακτικά Βιβλία του Παιδαγωγικού Ινστιτούτου

Αναζήτηση

Βρες
Εμφάνιση

Γράφοι προβαδίσματος και προγράμματα

Πολλοί γράφοι προβαδίσματος μπορούν να αντιστοιχιστούν με περισσότερα από ένα προγράμματα γραμμένα με τις εντολές parbegin-parend. Στο γράφο του σχήματος, η εντολή δ4 μπορεί να εκτελεστεί ταυτόχρονα με οποιαδήποτε από τις δ1, δ2 και δ3, γιατί δεν υπάρχει μονοπάτι μέσα στο γράφο που να τις συνδέει. Έτσι μπορούν να γραφούν τουλάχιστον τρία διαφορετικά παράλληλα προγράμματα τα οποία υπακούουν στους περιορισμούς του γράφου.

Οι τρεις διαφορετικές λύσεις είναι:

1) Η δ4 εκτελείται παράλληλα με τις δ1 και δ2 (οι οποίες μπορούν να εκτελεστούν παράλληλα), πριν από την δ3. Το πρόγραμμα είναι:

parbegin δ1 || δ2 || δ4 parend; δ3; δ5

2) Πρώτα εκτελούνται παράλληλα οι δ1 και δ2, και στη συνέχεια η δ3 εκτελείται παράλληλα με την δ4.

parbegin δ1 || δ2 parend; parbegin δ3 || δ4 parend; δ5

3) Η δ1 και η δ2 εκτελούνται παράλληλα, και μόλις τελειώσουν και οι δυο εκτελείται η δ3. Η δ4 εκτελείται παράλληλα με ολόκληρη την ομάδα των δ1, δ2, δ3· ξεκινά μαζί με τις δ1, δ2, αλλά η δ3 ξεκινά ανεξάρτητα από αυτήν. Η δ5 περιμένει τις δ3 και δ4 να τερματίσουν για να ξεκινήσει.

parbegin begin parbegin δ1 || δ2 parend; δ3; end || δ4 parend; δ5

Από τα τρία προγράμματα μόνο το ένα είναι το «σωστό», δηλαδή αυτό που αντιπροσωπεύει καλύτερα το γράφο προβαδίσματος. Το πρώτο πρόγραμμα έχει ένα πρόβλημα: η διεργασία δ3 περιμένει και την δ4 να τελειώσει (εκτός από τις δ1 και δ2), ενώ αυτό δεν είναι απαραίτητο. Παρομοίως, στο δεύτερο πρόγραμμα η δ4 περιμένει τις δ1 και δ2 χωρίς να υπάρχει λόγος. Και τα δυο προγράμματα δηλαδή, θέτουν επιπλέον περιορισμούς στην εκτέλεση των διεργασιών από αυτούς που περιγράφει ο γράφος. Αυτό δε συμβαίνει στο τρίτο πρόγραμμα, το οποίο είναι και το σωστό για την προγραμματιστική αναπαράσταση του γράφου προβαδίσματος.