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

Χρήση νημάτων με συλλογές, Μέρος 1

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

Αυτό Java σε βάθος Η στήλη περιγράφει τα ζητήματα που ανακάλυψα στην προσπάθειά μου να αναπτύξω μια συλλογή ασφαλή για θέματα. Μια συλλογή ονομάζεται "thread-safe" όταν μπορεί να χρησιμοποιηθεί με ασφάλεια από πολλούς πελάτες (νήματα) ταυτόχρονα. "Ποιο ειναι το πρόβλημα?" εσύ ρωτάς. Το πρόβλημα είναι ότι, στην τυπική χρήση, ένα πρόγραμμα αλλάζει και τα δύο μια συλλογή (που ονομάζεται μετάλλαξη), και το διαβάζει (ονομάζεται απαρίθμηση).

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

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

Συλλογές χωρίς νήμα

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

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

01 εισαγωγή java.util.Vector; 02 εισαγωγή java.util.Enumeration; 03 δημόσια τάξη επίδειξης {04 public static void main (String args []) {05 Vector digit = new Vector (); 06 int αποτέλεσμα = 0; 07 08 if (args.length == 0) {09 System.out.println ("Η χρήση είναι java demo 12345"); 10 System.exit (1); 11} 12 13 για (int i = 0; i = '0') && (c <= '9')) 16 digit.addElement (new Integer (c - '0')); 17 άλλα 18 διάλειμμα. 19} 20 System.out.println ("Υπάρχουν" + ψηφία. Μέγεθος () + "ψηφία."); 21 για [Αρίθμηση e = digits.elements (); e.hasMoreElements ();) {22 αποτέλεσμα = αποτέλεσμα * 10 + ((Integer) e.nextElement ()). IntValue (); 23} 24 System.out.println (args [0] + "=" + αποτέλεσμα); 25 System.exit (0); 26} 27} 

Η παραπάνω απλή κλάση χρησιμοποιεί ένα Διάνυσμα αντικείμενο για τη συλλογή ψηφίων χαρακτήρων από μια συμβολοσειρά. Στη συνέχεια, η συλλογή απαριθμείται για τον υπολογισμό της ακέραιας τιμής της συμβολοσειράς. Δεν υπάρχει τίποτα λάθος με αυτήν την τάξη εκτός από το ότι δεν είναι ασφαλές για νήματα. Εάν ένα άλλο νήμα έβγαλε μια αναφορά στο ψηφία διάνυσμα, και ότι το νήμα εισήγαγε έναν νέο χαρακτήρα στο φορέα, τα αποτελέσματα του βρόχου στις γραμμές 21 έως 23 παραπάνω θα ήταν απρόβλεπτα. Εάν η εισαγωγή έγινε πριν το αντικείμενο απαρίθμησης περάσει το σημείο εισαγωγής, το νήμα υπολογίζει αποτέλεσμα θα επεξεργαζόταν τον νέο χαρακτήρα. Εάν η εισαγωγή έγινε μετά την απαρίθμηση του σημείου εισαγωγής, ο βρόχος δεν θα επεξεργαζόταν τον χαρακτήρα. Το χειρότερο σενάριο είναι ότι ο βρόχος μπορεί να ρίξει ένα NoSuchElementException εάν η εσωτερική λίστα είχε παραβιαστεί.

Αυτό το παράδειγμα είναι ακριβώς αυτό - ένα παραδειγματικό παράδειγμα. Δείχνει το πρόβλημα, αλλά ποια είναι η πιθανότητα να τρέξει ένα άλλο νήμα κατά τη διάρκεια μιας σύντομης πενταψήφιας ή εξαψήφιας απαρίθμησης; Σε αυτό το παράδειγμα, ο κίνδυνος είναι χαμηλός. Ο χρόνος που περνά όταν ένα νήμα ξεκινά μια λειτουργία σε κίνδυνο, το οποίο σε αυτό το παράδειγμα είναι η απαρίθμηση και, στη συνέχεια, ολοκληρώνει την εργασία ονομάζεται νήμα παράθυρο ευπάθειας, ή παράθυρο. Αυτό το συγκεκριμένο παράθυρο είναι γνωστό ως κατάσταση του αγώνα επειδή ένα νήμα είναι "αγωνιστικά" για να ολοκληρώσει την εργασία του προτού ένα άλλο νήμα χρησιμοποιήσει τον κρίσιμο πόρο (τη λίστα των ψηφίων). Ωστόσο, όταν αρχίζετε να χρησιμοποιείτε συλλογές για να αντιπροσωπεύσετε μια ομάδα αρκετών χιλιάδων στοιχείων, όπως με μια βάση δεδομένων, το παράθυρο ευπάθειας αυξάνεται επειδή η απαρίθμηση του νήματος θα ξοδέψει πολύ περισσότερο χρόνο στον βρόχο απαρίθμησης και αυτό καθιστά την πιθανότητα να εκτελεστεί ένα άλλο νήμα πολύ ψηλότερα. Σίγουρα δεν θέλετε κάποιο άλλο νήμα να αλλάξει τη λίστα κάτω από εσάς! Αυτό που θέλετε είναι μια διαβεβαίωση ότι το Απαρίθμηση το αντικείμενο που κρατάτε είναι έγκυρο.

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

Δημιουργία συλλογών

Για να δημιουργήσω τη συλλογή μου που είναι ασφαλής για νήματα, χρειαζόμουν πρώτα μια συλλογή. Στην περίπτωσή μου, χρειάστηκε μια ταξινομημένη συλλογή, αλλά δεν ενοχλήθηκα να ακολουθήσω ολόκληρη τη δυαδική δέντρα. Αντ 'αυτού, δημιούργησα μια συλλογή που ονόμασα α Συγχρονιστική λίστα. Αυτό το μήνα, θα εξετάσω τα βασικά στοιχεία της συλλογής SynchroList και θα περιγράψω τον τρόπο χρήσης της. Τον επόμενο μήνα, στο Μέρος 2, θα μεταφέρω τη συλλογή από μια απλή, κατανοητή τάξη Java σε μια πολύπλοκη τάξη πολλαπλών νημάτων Java. Στόχος μου είναι να διατηρήσω το σχεδιασμό και την υλοποίηση μιας συλλογής ξεχωριστή και κατανοητή σε σχέση με τις τεχνικές που χρησιμοποιούνται για να την καταστήσει ενήμερη.

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

 τάξη Link {προσωπικά δεδομένα αντικειμένου; ιδιωτικός σύνδεσμος nxt, prv; Σύνδεσμος (Object o, Link p, Link n) {nxt = n; prv = p; δεδομένα = o; αν (n! = null) n.prv = αυτό; αν (p! = null) p.nxt = αυτό; } Αντικείμενο getData () {δεδομένα επιστροφής; } Σύνδεση επόμενου () {return nxt; } Σύνδεσμος επόμενος (Σύνδεση newNext) {Link r = nxt; nxt = νέοΕπόμενο; return r;} Σύνδεσμος prev () {return prv; } Σύνδεσμος prev (Link newPrev) {Link r = prv; prv = newPrev; return r;} public String toString () {return "Link (" + data + ")"; }} 

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

Μια άλλη εσωτερική τάξη χρησιμοποιείται στη λίστα - σε αυτήν την περίπτωση, μια κλάση απαριθμητή που ονομάζεται ΛίσταEnumerator. Αυτή η τάξη εφαρμόζει το java.util.Αριθμός διεπαφή: ο τυπικός μηχανισμός που χρησιμοποιεί η Java για να επαναλάβει μια συλλογή αντικειμένων. Έχοντας ζητήσει από τον απαριθμητή μας αυτή τη διεπαφή, η συλλογή μας θα είναι συμβατή με οποιεσδήποτε άλλες τάξεις Java που χρησιμοποιούν αυτήν τη διεπαφή για να απαριθμήσουν τα περιεχόμενα μιας συλλογής. Η εφαρμογή αυτής της τάξης φαίνεται στον παρακάτω κώδικα.

 Η κλάση LinkEnumerator εφαρμόζει την απαρίθμηση {private Link current, sebelumnya; LinkEnumerator () {current = head; } δημόσια boolean hasMoreElements () {return (current! = null); } δημόσιο αντικείμενο nextElement () {Object result = null; Σύνδεσμος tmp; if (current! = null) {αποτέλεσμα = current.getData (); current = current.next (); } αποτέλεσμα επιστροφής; }} 

Στην παρούσα ενσάρκωσή του, το LinkEnumerator η τάξη είναι αρκετά απλή. θα γίνει πιο περίπλοκο καθώς το τροποποιούμε. Σε αυτήν την ενσάρκωση, περπατά απλώς στη λίστα για το αντικείμενο κλήσης μέχρι να φτάσει στον τελευταίο σύνδεσμο στη λίστα εσωτερικών συνδεδεμένων. Οι δύο μέθοδοι που απαιτούνται για την εφαρμογή του java.util.Αριθμός διεπαφή είναι hasMoreElements και επόμενο στοιχείο.

Φυσικά, ένας από τους λόγους που δεν χρησιμοποιούμε το java.util.Vector Η τάξη είναι επειδή έπρεπε να ταξινομήσω τις τιμές στη συλλογή. Είχαμε μια επιλογή: να δημιουργήσουμε αυτήν τη συλλογή ώστε να είναι συγκεκριμένη για έναν συγκεκριμένο τύπο αντικειμένου, χρησιμοποιώντας έτσι την οικεία γνώση του τύπου αντικειμένου για να το ταξινομήσουμε ή για να δημιουργήσουμε μια πιο γενική λύση βασισμένη σε διεπαφές. Επέλεξα την τελευταία μέθοδο και καθόρισα μια διεπαφή που ονομάζεται Συγκριτής για να ενθυλακώσει τις απαραίτητες μεθόδους για την ταξινόμηση αντικειμένων. Αυτή η διεπαφή φαίνεται παρακάτω.

 δημόσια διεπαφή Συγκριτής {public boolean lessThan (Object a, Object b); public boolean μεγαλύτερος (αντικείμενο a, αντικείμενο b); δημόσιο boolean equalTo (Object a, Object b); void typeCheck (Αντικείμενο a); } 

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

 δημόσια κλάση SynchroList {class Link {... αυτό παρουσιάστηκε παραπάνω ...} Το class LinkEnumerator υλοποιεί την απαρίθμηση {... την κλάση αριθμητών ...} / * Ένα αντικείμενο για σύγκριση των στοιχείων μας * / Συγκριτικό cmp; Σύνδεση κεφάλι, ουρά; δημόσια SynchroList () {} δημόσια SynchroList (Συγκριτής c) {cmp = c; } ιδιωτικό κενό πριν (Object o, Link p) {new Link (o, p.prev (), p); } ιδιωτικό κενό μετά (Object o, Link p) {new Link (o, p, p.next ()); } αφαίρεση ιδιωτικού κενού (Link p) {if (p.prev () == null) {head = p.next (); (p.επόμενο ()). prev (null); } αλλιώς εάν (p.next () == null) {tail = p.prev (); (p.prev ()). επόμενο (null); } αλλιώς {p.prev (). next (p.next ()); p.next (). prev (p.prev ()); }} δημόσια κενή προσθήκη (Αντικείμενο o) {// εάν το cmp είναι μηδενικό, προσθέστε πάντα στην ουρά της λίστας. if (cmp == null) {if (head == null) {head = νέο σύνδεσμο (o, null, null); ουρά = κεφάλι; } αλλιώς {tail = new Link (o, tail, null); } ΕΠΙΣΤΡΟΦΗ; } cmp.typeCheck (o); if (head == null) {head = νέο σύνδεσμο (o, null, null); ουρά = κεφάλι; } αλλιώς εάν (cmp.lessThan (o, head.getData ())) {head = new Link (o, null, head); } αλλιώς {Link l; για (l = head; l.next ()! = null; l = l.next ()) {if (cmp.lessThan (o, l.getData ())) {πριν (o, l); ΕΠΙΣΤΡΟΦΗ; }} tail = νέο σύνδεσμο (o, tail, null); } ΕΠΙΣΤΡΟΦΗ; } δημόσια boolean delete (Object o) {if (cmp == null) επιστροφή false cmp.typeCheck (o); για (Link l = head; l! = null; l = l.next ()) {if (cmp.equalTo (o, l.getData ())) {remove (l); επιστροφή αληθινή? } εάν (cmp.lessThan (o, l.getData ())) διακοπή; } επιστροφή ψευδής; } δημόσια συγχρονισμένα στοιχεία απαρίθμησης () {return new LinkEnumerator (); } δημόσιο μέγεθος int () {int αποτέλεσμα = 0; για (Link l = head; l! = null; l = l.next ()) αποτέλεσμα ++; αποτέλεσμα επιστροφής; }}