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

Αναζήτηση

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

Κρίσιμα τμήματα

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

Οι οδηγίες του ιδιοκτήτη προς το ζαχαροπλάστη (ΚΜΕ), δηλαδή το ΛΣ, πρέπει να μεριμνούν ώστε κάτι τέτοιο να αποφευχθεί.

Σε ένα υπολογιστικό σύστημα, υπάρχουν μοιραζόμενοι πόροι (shared resources) -στο παράδειγμά μας ο θερμοθάλαμος- που χρησιμοποιούνται από πολλές διεργασίες και για να διαβαστούν αλλά και για να γραφτούν. Ο τρόπος που γίνονται οι προσπελάσεις σε αυτά έχει πολύ μεγάλη σημασία, γιατί όπως είδαμε και στο παράδειγμα, μια αλλαγή στα δεδομένα από τη μια διεργασία επηρεάζει και τις υπόλοιπες.

Μια τέτοια χαρακτηριστική περίπτωση διεργασιών που μοιράζονται δεδομένα είναι ένα online σύστημα τράπεζας. Η διαδικασία ανάληψης ενός ποσού Α από ένα μηχάνημα ATM γίνεται σε πέντε φάσεις: 1. Ρώτα τον πελάτη για το χρηματικό ποσό Α που θέλει 2. Διάβασε το υπόλοιπο Υ του λογαριασμού 3. Υπολόγισε το νέο υπόλοιπο Υ' μετά την ανάληψη του ποσού Α, Υ':=Υ-Α 4. Αποθήκευσε το νέο υπόλοιπο 5. Δώσε τα χρήματα και την απόδειξη

Τι θα γίνει αν γίνονται από δυο διαφορετικά μηχανήματα συγχρόνως αναλήψεις για τον ίδιο λογαριασμό; Ας φανταστούμε ότι σε ένα κοινό λογαριασμό το αρχικό υπόλοιπο του λογαριασμού είναι 200.000, ο ένας πελάτης (π.χ. η σύζυγος) ζητά 50.000, ενώ ο άλλος (ο σύζυγος) ζητά 20.000. Επίσης υποθέτουμε ότι η εναλλαγή των διεργασιών γίνεται με τέτοιο ρυθμό ώστε σε κάθε κβάντο χρόνου, το οποίο έχει διάρκεια 1', μια διεργασία εκτελεί μια από τις τέσσερις παραπάνω φάσεις. Το υπόλοιπο του λογαριασμού μετά από τις δυο αναλήψεις θα πρέπει να είναι βέβαια 130.000.

Διεργασία Α - Διεργασία Β - Λογαριασμός Ρώτα για το ποσό Α=50.000 - - 200.000 - Ρώτα για το ποσό Α=20.000 - 200.000 Διάβασε το υπόλοιπο Υ=200.000 - - 200.000 - Διάβασε το υπόλοιπο Υ=200.000 - 200.000 Υ':= Υ - Α = 1200.000-50.000 = 150.000 - - 200.000 - Υ' := Υ - Α = 200.000-20.000 = 180.000 - 200.000 Αποθήκευσε το Υ' - - 150.000 - Αποθήκευσε το Υ' - 180.000

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

Το λάθος στο πρόγραμμα προέρχεται από το γεγονός ότι πολλές διεργασίες μοιράζονται δεδομένα. Αν διαβάζουν και γράφουν σε αυτά ανεξέλεγκτα, τότε τα δεδομένα δεν παίρνουν τις σωστές τιμές. Το πρόβλημα αυτό ονομάζεται το πρόβλημα του κρισίμου τμήματος (critical section) όπου πρέπει να εξασφαλισθεί η ακεραιότητα των δεδομένων (data integrity).

Για να λύσει το πρόβλημα με το θερμοθάλαμο, οι οδηγίες προς το ζαχαροπλάστη (ΛΣ) μπορούν να προβλέπουν δυο λύσεις:

- Παρότι το πεντάλεπτο της πρώτης συνταγής έχει τελειώσει, να συνεχίσει να ασχολείται με αυτή μέχρι να έρθει η στιγμή που χρησιμοποιεί τη σοκολάτα και να απελευθερώσει το θερμοθάλαμο. Τότε θα τη διακόψει και θα προχωρήσει στην επόμενη.

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

Δυο αντίστοιχες λύσεις μπορούν να εφαρμοστούν και στο πρόβλημα του τραπεζικού λογαριασμού:

- Μέχρι να ολοκληρωθεί η συναλλαγή του πρώτου πελάτη δεν ξεκινά αυτή του δεύτερου. Υλοποίηση: Αδρανοποιείται το σύστημα διακοπών του χρονιστή (ο οποίος είναι υπεύθυνος να ενημερώνει την ΚΜΕ κάθε φορά που πρέπει να διακοπεί μια διεργασία για να εκτελεστεί άλλη) μέχρι η πρώτη συναλλαγή να ολοκληρωθεί, οπότε δεν είναι δυνατόν να διακοπεί αυτή για να εκτελεστεί κάποια άλλη.

- Το ΛΣ «σημειώνει» ότι ο λογαριασμός χρησιμοποιείται από την πρώτη διεργασία, και η δεύτερη περιμένει έως ότου ο λογαριασμός «αποσημειωθεί», ελευθερωθεί δηλαδή. Υλοποίηση: Με ειδικούς μηχανισμούς, όπως οι σηματοφορείς, που θα εξεταστούν σε επόμενο μάθημα.

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

Βλέπουμε λοιπόν ότι μόνο σε ένα τμήμα της κάθε διεργασίας εμφανίζεται κίνδυνος για την ακεραιότητα των δεδομένων. Το τμήμα αυτό του κώδικα ονομάζεται κρίσιμο τμήμα.

Όταν μια διεργασία εκτελεί τον κώδικα του κρίσιμου τμήματός της, καμία άλλη δεν μπορεί να εκτελεί το δικό της κρίσιμο τμήμα, έχουμε δηλαδή το φαινόμενο του αμοιβαίου αποκλεισμού (mutual exclusion).

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

Ο Dijkstra (1965) έθεσε μερικούς ακόμα περιορισμούς για τα κρίσιμα τμήματα: 1. Όταν μια διεργασία εκτελεί κώδικα εκτός του κρίσιμου τμήματός της, δεν μπορεί να αποτρέψει άλλες διεργασίες να εκτελέσουν το δικό τους κρίσιμο τμήμα. 2. Όταν δυο ή περισσότερες διεργασίες είναι ταυτόχρονα έτοιμες να εισέλθουν στο κρίσιμο τμήμα τους, η λήψη απόφασης δεν πρέπει να αναβάλλεται επ' άπειρο. 3. Πρέπει να υπάρχει δικαιοσύνη (fairness) στον τρόπο επιλογής της διεργασίας που θα εισέλθει στο κρίσιμο τμήμα· όλες οι διεργασίες πρέπει να έχουν την ίδια πιθανότητα να εξυπηρετηθούν μέσα σε κάποιο λογικό χρονικό διάστημα και όχι κάποιες να μονοπωλούν το σύστημα.

Οι δυο πρώτοι περιορισμοί προφυλάσσουν το σύστημα από το αδιέξοδο (deadlock) ή το αμοιβαίο μπλοκάρισμα (mutual blocking), όπου όλες οι διεργασίες εμποδίζονται να εκτελέσουν το κρίσιμο τμήμα τους ενώ τουλάχιστον μία θα μπορούσε να το κάνει.