Προγραμματισμός

Java 101: Ταυτόχρονη Java χωρίς πόνο, Μέρος 2

Προηγούμενο 1 2 3 4 Σελίδα 3 Επόμενο Σελίδα 3 από 4

Ατομικές μεταβλητές

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

Ωστόσο, ο παραδοσιακός μηχανισμός συγχρονισμού της Java, ο οποίος επιβάλλει αμοιβαίος αποκλεισμός (το νήμα που κρατά την κλειδαριά που προστατεύει ένα σύνολο μεταβλητών έχει αποκλειστική πρόσβαση σε αυτές) και ορατότητα (οι αλλαγές στις προστατευμένες μεταβλητές γίνονται ορατές σε άλλα νήματα που στη συνέχεια αποκτούν το κλείδωμα), επηρεάζουν τη χρήση του υλικού και την επεκτασιμότητα, ως εξής:

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

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

Το Java 5 εισήγαγε μια εναλλακτική λύση συγχρονισμού που προσφέρει αμοιβαίο αποκλεισμό σε συνδυασμό με την απόδοση του πτητικός. Αυτό ατομική μεταβλητή Η εναλλακτική λύση βασίζεται σε μια εντολή σύγκρισης και ανταλλαγής μικροεπεξεργαστή και αποτελείται σε μεγάλο βαθμό από τους τύπους στο java.util.concurrent.atomic πακέτο.

Κατανόηση σύγκρισης και ανταλλαγής

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

Οδηγίες μικροεπεξεργαστή CAS

Οι σύγχρονοι μικροεπεξεργαστές προσφέρουν κάποιου είδους οδηγίες CAS. Για παράδειγμα, οι μικροεπεξεργαστές Intel προσφέρουν το cmpxchg οικογένεια οδηγιών, ενώ οι μικροεπεξεργαστές PowerPC προσφέρουν σύνδεση φορτίου (π.χ. Λάραξ) και υπό όρους (π.χ., stwcx) οδηγίες για τον ίδιο σκοπό.

Το CAS καθιστά δυνατή την υποστήριξη ατομικών ακολουθιών ανάγνωσης-τροποποίησης-εγγραφής. Συνήθως χρησιμοποιείτε το CAS ως εξής:

  1. Διαβάστε την τιμή v από τη διεύθυνση X.
  2. Εκτελέστε έναν υπολογισμό πολλαπλών σταδίων για να αποκομίσετε μια νέα τιμή v2.
  3. Χρησιμοποιήστε το CAS για να αλλάξετε την τιμή του Χ από v σε v2. Το CAS πετυχαίνει όταν η τιμή του X δεν έχει αλλάξει κατά την εκτέλεση αυτών των βημάτων.

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

Λίστα 4. Counter.java (έκδοση 1)

Μετρητής δημόσιας τάξης {private int value; δημόσιο συγχρονισμένο int getValue () {τιμή επιστροφής; } δημόσια συγχρονισμένη int increment () {return ++ value; }}

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

Η εναλλακτική λύση CAS απαιτεί την εφαρμογή της εντολής σύγκρισης και ανταλλαγής. Η ακόλουθη τάξη μιμείται το CAS. Χρησιμοποιεί συγχρονισμένος αντί για την πραγματική οδηγία υλικού για την απλοποίηση του κώδικα:

Λίστα 5. EmulatedCAS.java

δημόσια τάξη EmulatedCAS {ιδιωτική τιμή int; δημόσιο συγχρονισμένο int getValue () {τιμή επιστροφής; } δημόσιο συγχρονισμένο int membandingkanAndSwap (int waitingValue, int newValue) {int readValue = τιμή; if (readValue == expectValue) τιμή = νέα τιμή; επιστροφή readValue; }}

Εδώ, αξία προσδιορίζει μια θέση μνήμης, η οποία μπορεί να ανακτηθεί από getValue (). Επίσης, σύγκρισηAndSwap () εφαρμόζει τον αλγόριθμο CAS.

Η ακόλουθη τάξη χρησιμοποιεί EmulatedCAS να εφαρμόσει ένα μησυγχρονισμένος μετρητής (προσποιηθείτε αυτό EmulatedCAS δεν απαιτεί συγχρονισμένος):

Λίστα 6. Counter.java (έκδοση 2)

Μετρητής δημόσιας τάξης {private EmulatedCAS value = new EmulatedCAS (); δημόσιο int getValue () {return value.getValue (); } δημόσια int increment () {int readValue = value.getValue (); ενώ (value.compareAndSwap (readValue, readValue + 1)! = readValue) readValue = value.getValue (); επιστροφή readValue + 1; }}

Μετρητής ενσωματώνει ένα EmulatedCAS στιγμιότυπο και δηλώνει μεθόδους για ανάκτηση και αύξηση μιας αξίας μετρητή με βοήθεια από αυτήν την παρουσία. getValue () ανακτά την "τρέχουσα τιμή μετρητή" της παρουσίας και αύξηση() αυξάνει με ασφάλεια την τιμή μετρητή.

αύξηση() επανειλημμένα επικαλείται σύγκρισηAndSwap () μέχρι readValueΗ τιμή δεν αλλάζει. Στη συνέχεια, είναι ελεύθερο να αλλάξετε αυτήν την τιμή. Όταν δεν εμπλέκεται κλείδωμα, αποφεύγεται η διαμάχη μαζί με την υπερβολική εναλλαγή περιβάλλοντος. Η απόδοση βελτιώνεται και ο κώδικας είναι πιο επεκτάσιμος.

ReentrantLock και CAS

Το μάθατε προηγουμένως ReentrantLock προσφέρει καλύτερη απόδοση από ό, τι συγχρονισμένος υπό υψηλό νήμα. Για την ενίσχυση της απόδοσης, ReentrantLockΟ συγχρονισμός διαχειρίζεται από μια υποκατηγορία της περίληψης java.util.concurrent.locks.AbstractQueuedSynchronizer τάξη. Με τη σειρά του, αυτή η τάξη αξιοποιεί τα χωρίς έγγραφα sun.misc.Usafe τάξη και του σύγκρισηAndSwapInt () Μέθοδος CAS.

Εξερεύνηση του πακέτου ατομικών μεταβλητών

Δεν χρειάζεται να εφαρμόσετε σύγκρισηAndSwap () μέσω της μη φορητής Java Native Interface. Αντ 'αυτού, το Java 5 προσφέρει αυτήν την υποστήριξη μέσω java.util.concurrent.atomic: μια εργαλειοθήκη κλάσεων που χρησιμοποιούνται για προγραμματισμό χωρίς κλειδαριά και ασφαλή νήμα σε μεμονωμένες μεταβλητές.

Σύμφωνα με java.util.concurrent.atomicJavadoc, αυτά τα μαθήματα

επεκτείνει την έννοια του πτητικός τιμές, πεδία και στοιχεία πίνακα σε εκείνα που παρέχουν επίσης μια ατομική λειτουργία υπό όρους ενημέρωσης της φόρμας boolean membandingkanAndSet (αναμενόμενη τιμή, ενημέρωση τιμής). Αυτή η μέθοδος (η οποία διαφέρει σε τύπους ορίσματος σε διαφορετικές κατηγορίες) ορίζει ατομικά μια μεταβλητή στο updateValue εάν διατηρεί επί του παρόντος το αναμενόμενη αξία, αναφέροντας αλήθεια για την επιτυχία.

Αυτό το πακέτο προσφέρει μαθήματα για Boolean (AtomicBoolean), ακέραιος (AtomicInteger), ακέραιος ακέραιος (AtomicLong) και αναφορά (AtomicReference) τύποι. Προσφέρει επίσης εκδόσεις πινάκων ακέραιου, μεγάλου ακέραιου και αναφοράς (AtomicIntegerArray, AtomicLongArray, και AtomicReferenceArray), σημαντικές και σφραγισμένες κλάσεις αναφοράς για την ατομική ενημέρωση ενός ζεύγους τιμών (AtomicMarkableReference και AtomicStampedReference), κι αλλα.

Εφαρμογή σύγκρισηςAndSet ()

Εφαρμόζει Java σύγκρισηAndSet () μέσω της γρηγορότερης διαθέσιμης εγγενής κατασκευής cmpxchg ή load-link / store-υπό όρους) ή (στη χειρότερη περίπτωση) κλειδαριές περιστροφής.

Σκεφτείτε AtomicInteger, που σας επιτρέπει να ενημερώσετε ένα int αξία ατομικά. Μπορούμε να χρησιμοποιήσουμε αυτήν την τάξη για να εφαρμόσουμε τον μετρητή που εμφανίζεται στην λίστα 6. Η λίστα 7 παρουσιάζει τον ισοδύναμο πηγαίο κώδικα.

Λίστα 7. Counter.java (έκδοση 3)

εισαγωγή java.util.concurrent.atomic.AtomicInteger; Μετρητής δημόσιας τάξης {private AtomicInteger value = new AtomicInteger (); δημόσια int getValue () {return value.get (); } δημόσια int increment () {int readValue = value.get (); ενώ (! value.compareAndSet (readValue, readValue + 1)) readValue = value.get (); επιστροφή readValue + 1; }}

Η καταχώριση 7 μοιάζει πολύ με την καταχώριση 6, εκτός από το ότι αντικαθιστά EmulatedCAS με AtomicInteger. Παρεμπιπτόντως, μπορείτε να απλοποιήσετε αύξηση() επειδή AtomicInteger προμηθεύει τη δική του int getAndIncrement () μέθοδος (και παρόμοιες μέθοδοι).

Πλαίσιο Fork / Join

Το υλικό του υπολογιστή έχει εξελιχθεί σημαντικά από το ντεμπούτο της Java το 1995. Πίσω στην εποχή, τα συστήματα ενός επεξεργαστή κυριάρχησαν στο τοπίο των υπολογιστών και στα πρωτόγοντα συγχρονισμού της Java, όπως συγχρονισμένος και πτητικός, καθώς και τη βιβλιοθήκη με νήματα (το Νήμα τάξη, για παράδειγμα) ήταν γενικά επαρκείς.

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

Τι είναι ο παραλληλισμός;

Παραλληλισμός είναι η ταυτόχρονη εκτέλεση πολλαπλών σπειρωμάτων / εργασιών μέσω κάποιου συνδυασμού πολλαπλών επεξεργαστών και πυρήνων επεξεργαστών.

Το πλαίσιο Java Concurrency Utilities απλοποιεί την ανάπτυξη αυτών των εφαρμογών. Ωστόσο, τα βοηθητικά προγράμματα που προσφέρονται από αυτό το πλαίσιο δεν κλιμακώνονται σε χιλιάδες επεξεργαστές ή πυρήνες επεξεργαστών. Στην εποχή μας πολλών πυρήνων, χρειαζόμαστε μια λύση για την επίτευξη ενός λεπτότερου παραλληλισμού ή κινδυνεύουμε να διατηρήσουμε τους επεξεργαστές σε αδράνεια ακόμα και όταν υπάρχει πολλή δουλειά για να χειριστούν.

Ο καθηγητής Doug Lea παρουσίασε μια λύση σε αυτό το πρόβλημα στην εργασία του, παρουσιάζοντας την ιδέα για ένα πλαίσιο πιρούνι / ένταξης που βασίζεται σε Java. Η Lea περιγράφει ένα πλαίσιο που υποστηρίζει "ένα στυλ παράλληλου προγραμματισμού στο οποίο τα προβλήματα επιλύονται με (αναδρομικά) διαχωρισμό τους σε δευτερεύουσες εργασίες που επιλύονται παράλληλα." Το πλαίσιο Fork / Join τελικά συμπεριλήφθηκε στο Java 7.

Επισκόπηση του πλαισίου Fork / Join

Το πλαίσιο Fork / Join βασίζεται σε μια ειδική υπηρεσία εκτελεστών για την εκτέλεση ενός ειδικού είδους εργασίας. Αποτελείται από τους ακόλουθους τύπους που βρίσκονται στο java.util.concurrent πακέτο:

  • ForkJoinPool: ένα Εξυπηρέτηση εφαρμογή που εκτελείται ForkJoinTaskμικρό. ForkJoinPool παρέχει μεθόδους υποβολής εργασιών, όπως void execute (εργασία ForkJoinTask), μαζί με μεθόδους διαχείρισης και παρακολούθησης, όπως int getParallelism () και μακρύ getStealCount ().
  • ForkJoinTask: μια αφηρημένη βασική κλάση για εργασίες που εκτελούνται εντός α ForkJoinPool συμφραζόμενα. ForkJoinTask περιγράφει οντότητες που μοιάζουν με νήματα που έχουν πολύ ελαφρύτερο βάρος από τα κανονικά νήματα. Πολλές εργασίες και δευτερεύουσες εργασίες μπορούν να φιλοξενηθούν από πολύ λίγα πραγματικά νήματα στο α ForkJoinPool παράδειγμα.
  • ForkJoinWorkerThread: μια τάξη που περιγράφει ένα νήμα το οποίο διαχειρίζεται ένα ForkJoinPool παράδειγμα. ForkJoinWorkerThread είναι υπεύθυνη για την εκτέλεση ForkJoinTaskμικρό.
  • Αναδρομική δράση: μια αφηρημένη τάξη που περιγράφει ένα αναδρομικό αποτέλεσμα χωρίς αποτέλεσμα ForkJoinTask.
  • Αναδρομική εργασία: μια αφηρημένη τάξη που περιγράφει ένα αναδρομικό αποτέλεσμα ForkJoinTask.

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

ForkJoinPool διαχειρίζεται μια ομάδα από νήματα εργαζομένων, όπου κάθε νήμα εργαζομένου έχει τη δική του ουρά εργασίας (διπλή). Όταν μια εργασία πιάνει ένα νέο δευτερεύον έργο, το νήμα σπρώχνει το δευτερεύον έργο πάνω στο κεφάλι του deque. Όταν μια εργασία προσπαθεί να ενώσει με μια άλλη εργασία που δεν έχει τελειώσει, το νήμα αναδύει μια άλλη εργασία από το κεφάλι της deque και εκτελεί την εργασία. Εάν το ντεκόκ του νήματος είναι άδειο, προσπαθεί να κλέψει μια άλλη εργασία από την ουρά της άλκης ενός άλλου νήματος. Αυτό δουλεύει κλοπή η συμπεριφορά μεγιστοποιεί την απόδοση ενώ ελαχιστοποιεί τη διαμάχη.

Χρησιμοποιώντας το πλαίσιο Fork / Join

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

Το έγγραφο της Lea παρουσιάζει τον ακόλουθο ψευδοκώδικα για να περιγράψει τη συμπεριφορά διαίρεσης και κατάκτησης:

Επίλυση αποτελεσμάτων (Πρόβλημα προβλήματος) {εάν (το πρόβλημα είναι μικρό) επιλύστε άμεσα το πρόβλημα αλλιώς {διαχωρίστε το πρόβλημα σε ανεξάρτητα μέρη πιρούνι νέες δευτερεύουσες εργασίες για την επίλυση κάθε τμήματος ενώστε όλες τις δευτερεύουσες εργασίες που συνθέτουν το αποτέλεσμα από τις δευτερεύουσες}}

Ο ψευδοκώδικας παρουσιάζει ένα λύσει μέθοδο που καλείται με μερικά πρόβλημα για επίλυση και που επιστρέφει a Αποτέλεσμα που περιέχει το πρόβλημαλύση. Εάν το πρόβλημα είναι πολύ μικρό για να επιλυθεί μέσω παραλληλισμού, λύνει άμεσα. (Η επιβάρυνση της χρήσης παραλληλισμού σε ένα μικρό πρόβλημα υπερβαίνει κάθε όφελος που έχει αποκτηθεί.) Διαφορετικά, το πρόβλημα χωρίζεται σε δευτερεύουσες εργασίες: κάθε δευτερεύουσα εργασία εστιάζει ανεξάρτητα σε μέρος του προβλήματος.

Λειτουργία πιρούνι ξεκινά ένα νέο δευτερεύον έργο fork / join που θα εκτελεστεί παράλληλα με άλλα δευτερεύοντα καθήκοντα. Λειτουργία Συμμετοχή καθυστερεί την τρέχουσα εργασία έως ότου ολοκληρωθεί το διχασμένο δευτερεύον έργο. Σε κάποιο σημείο, το πρόβλημα θα είναι αρκετά μικρό για να εκτελεστεί διαδοχικά, και το αποτέλεσμα θα συνδυαστεί με άλλα δευτερεύοντα αποτελέσματα για να επιτευχθεί μια συνολική λύση που επιστρέφεται στον καλούντα.

Το Javadoc για το Αναδρομική δράση και Αναδρομική εργασία Τα μαθήματα παρουσιάζουν διάφορα παραδείγματα αλγορίθμου διαίρεσης και κατακράτησης που εφαρμόζονται ως εργασίες fork / join. Για Αναδρομική δράση τα παραδείγματα ταξινομούν έναν πίνακα μεγάλων ακεραίων, αυξάνουν κάθε στοιχείο σε έναν πίνακα και αθροίζουν τα τετράγωνα κάθε στοιχείου σε έναν πίνακα διπλόμικρό. Αναδρομική εργασίαΤο μοναχικό παράδειγμα υπολογίζει έναν αριθμό Fibonacci.

Η λίστα 8 παρουσιάζει μια εφαρμογή που δείχνει το παράδειγμα ταξινόμησης σε περιβάλλοντα εκτός fork / join καθώς και fork / join. Παρουσιάζει επίσης μερικές πληροφορίες χρονισμού για να συγκρίνει τις ταχύτητες ταξινόμησης.