Korištenje niti s zbirkama, 1. dio

Niti su sastavni dio jezika Java. Korištenjem niti, mnogim algoritmima, poput sustava za upravljanje redovima, lakše je pristupiti nego što koriste tehnike glasanja i ponavljanja. Nedavno, dok sam pisao Java klasu, otkrio sam da trebam koristiti niti dok nabrajam popise, a to je otkrilo neke zanimljive probleme povezane s kolekcijama svjesnim niti.

Ovaj Java In Depth stupac opisuje probleme koje sam otkrio u svom pokušaju da razvijem kolekciju sigurnu za nit. Zbirka se naziva "zaštićena od niti" kada je može istovremeno koristiti više klijenata (niti). "Pa u čemu je problem?" pitaš. Problem je u tome što, u tipičnoj upotrebi, program mijenja kolekciju (koja se naziva mutirajuća ) i čita je (koja se naziva enumeracija ).

Neki ljudi jednostavno ne registriraju izjavu: "Java platforma je višestruka." Svakako, čuju to i klimaju glavom. Ali oni ne shvaćaju da su, za razliku od C ili C ++, kod kojih je uvođenje navoja bočno pričvršćeno kroz OS, niti u Javi osnovne konstrukcije jezika. Ovo nerazumijevanje ili loše razumijevanje prirode koja Java ima nit, neizbježno dovodi do dvije uobičajene greške u Java kodu programera: Ili ne uspijevaju proglasiti metodu sinkroniziranom što bi trebalo biti (jer je objekt u nedosljednom stanju tijekom metoda) ili oni proglašavaju metodu sinkroniziranom kako bi je zaštitili, što dovodi do toga da ostatak sustava radi neučinkovito.

Na ovaj sam problem naišao kada sam želio kolekciju koju bi više niti moglo koristiti bez nepotrebnog blokiranja izvršavanja ostalih niti. Nijedna klasa kolekcije u verziji JDK 1.1 nije sigurna u niti. Točnije, nijedna klasa kolekcije neće vam dopustiti da nabrajate jednom niti dok mutirate drugom.

Zbirke koje nisu zaštićene nitima

Moj osnovni problem bio je sljedeći: Pod pretpostavkom da imate uređenu zbirku objekata, dizajnirajte Java klasu tako da nit može nabrojati cijelu ili dio zbirke bez brige da će nabrajanje postati nevaljano zbog drugih niti koje mijenjaju kolekciju. Kao primjer problema uzmimo Javinu Vectorklasu. Ova klasa nije sigurna u nitima i uzrokuje brojne probleme novim Java programerima kada je kombiniraju s višenitnim programom.

VectorKlase pruža vrlo koristan pogon za Java programera: naime, dinamički veličine niz objekata. U praksi biste ovu uslugu mogli koristiti za pohranu rezultata u kojima konačni broj predmeta s kojima ćete imati posla nije poznat dok ne završite sa svima njima. Izradio sam sljedeći primjer kako bih demonstrirao ovaj koncept.

01 import java.util.Vector; 02 import java.util.Enumeration; 03 javna klasa Demo {04 public static void main (String args []) {05 Vektorske znamenke = novi vektor (); 06 int rezultat = 0; 07 08 if (args.length == 0) {09 System.out.println ("Upotreba je java demo 12345"); 10 System.exit (1); 11} 12 13 za (int i = 0; i = '0') && (c <= '9')) 16 znamenki.addElement (novi cijeli broj (c - '0')); 17 ostalo 18 prekid; 19} 20 System.out.println ("Postoje" + digits.size () + "znamenke."); 21 za (Enumeration e = digits.elements (); e.hasMoreElements ();) {22 result = result * 10 + ((Integer) e.nextElement ()). IntValue (); 23} 24 System.out.println (args [0] + "=" + rezultat); 25 System.exit (0); 26} 27}

Gornja jednostavna klasa koristi Vectorobjekt za prikupljanje znakovnih znakova iz niza. Zatim se zbirka nabraja za izračunavanje cjelobrojne vrijednosti niza. S ovom klasom nema ništa loše, osim što nije zaštićena niti. Ako se slučajno u drugoj niti nalazi referenca na vektor znamenki , a ta nit u vektor ubaci novi znak, rezultati petlje u 21. do 23. retku bili bi nepredvidivi. Ako se umetanje dogodilo prije nego što je objekt popisivanja prošao točku umetanja, rezultat izračuna nit će obraditi novi znak. Ako se umetanje dogodilo nakon što je popisivanje prošlo točku umetanja, petlja neće obraditi znak. Najgori je scenarij da bi petlja mogla baciti aNoSuchElementException ako je interni popis bio ugrožen.

Ovaj je primjer upravo to - izmišljeni primjer. To pokazuje problem, ali kakva je šansa da se druga nit pokrene tijekom kratkog nabrajanja od pet ili šest znamenki? U ovom primjeru rizik je nizak. Količina vremena koje prolazi kada jedna nit pokrene rizičnu operaciju, što je u ovom primjeru nabrajanje, a zatim završava zadatak naziva se prozor ranjivosti niti, odnosno prozor . Ovaj određeni prozor poznat je kao stanje utrkejer se jedna nit "utrkuje" kako bi dovršila svoj zadatak prije nego što druga nit upotrijebi kritični resurs (popis znamenki). Međutim, kada započnete koristiti zbirke za predstavljanje skupine od nekoliko tisuća elemenata, na primjer s bazom podataka, prozor ranjivosti se povećava jer će nabrajanje niti potrošiti puno više vremena u svojoj petlji za nabrajanje, a to čini šansu da se nova nit pokrene mnogo više. Sigurno ne želite da neka druga nit mijenja popis ispod vas! Ono što želite je jamstvo da je Enumerationpredmet koji držite valjan.

Jedan od načina da se sagleda ovaj problem jest primijetiti da je Enumerationobjekt odvojen od Vectorobjekta. Budući da su odvojeni, nisu u stanju zadržati kontrolu jedni nad drugima kad su stvoreni. Ovo labavo vezivanje sugeriralo mi je da je možda koristan put za istraživanje nabrajanje koje je čvršće vezano za zbirku koja ga je stvorila.

Stvaranje zbirki

Da bih stvorio svoju kolekciju sigurnu za nit, prvo mi je trebala kolekcija. U mom slučaju bila je potrebna sortirana kolekcija, ali nisam se trudio proći puni put binarnog stabla. Umjesto toga, stvorio sam kolekciju koju sam nazvao SynchroList . Ovaj mjesec pregledat ću osnovne elemente zbirke SynchroList i opisati kako ih koristiti. Sljedeći mjesec, u 2. dijelu, prenijet ću zbirku iz jednostavne, lako razumljive Java klase u složenu višetretnu Java klasu. Cilj mi je održati dizajn i provedbu kolekcije različitim i razumljivim u odnosu na tehnike koje se koriste za osvješćivanje niti.

Nazvao sam svoj razred SynchroList. Naziv "SynchroList", naravno, dolazi od spajanja "sinkronizacije" i "popisa". Zbirka je jednostavno dvostruko povezan popis kakav možete pronaći u bilo kojem fakultetskom udžbeniku o programiranju, iako se upotrebom unutarnjeg razreda s imenom Linkmože postići određena elegancija. Unutarnja klasa Linkdefinirana je kako slijedi:

klasa Link {podaci privatnog objekta; privatna veza nxt, prv; Veza (objekt o, veza p, veza n) {nxt = n; prv = p; podaci = o; if (n! = null) n.prv = ovo; if (p! = null) p.nxt = ovo; } Objekt getData () {povratak podataka; } Link next () {return nxt; } Sljedeća veza (Link newNext) {Link r = nxt; nxt = novoSljedeće; return r;} Link prev () {return prv; } Link prev (Link newPrev) {Link r = prv; prv = novoPrev; return r;} javni String toString () {return "Link (" + podaci + ")"; }}

Kao što možete vidjeti u gornjem kodu, Linkobjekt enkapsulira ponašanje povezivanja koje će popis koristiti za organiziranje svojih objekata. Da bi implementirao dvostruko povezano ponašanje popisa, objekt sadrži reference na svoj podatkovni objekt, referencu na sljedeću vezu u lancu i referencu na prethodnu vezu u lancu. Nadalje, metode nexti prevsu preopterećene kako bi osigurale sredstvo za ažuriranje pokazivača objekta. To je neophodno jer će nadređena klasa trebati umetnuti i izbrisati veze na popis. Konstruktor veze dizajniran je za istovremeno stvaranje i umetanje veze. Ovo sprema poziv metode u provedbi popisa.

Na popisu se koristi još jedna unutarnja klasa - u ovom slučaju, imenovana klasa popisivača ListEnumerator. Ova klasa implementira java.util.Enumerationsučelje: standardni mehanizam koji Java koristi za itiriranje preko kolekcije objekata. Ako naš popisivač implementira ovo sučelje, naša će zbirka biti kompatibilna s bilo kojim drugim Java klasama koje koriste ovo sučelje za nabrajanje sadržaja zbirke. Implementacija ove klase prikazana je u donjem kodu.

klasa LinkEnumerator implementira Enumeration {private Link current, previous; LinkEnumerator () {trenutno = glava; } javna logička vrijednost hasMoreElements () {return (trenutno! = null); } javni objekt nextElement () {rezultat objekta = null; Veza tmp; if (trenutno! = null) {rezultat = current.getData (); trenutna = trenutna.sljedeća (); } vratiti rezultat; }}

U svojoj sadašnjoj inkarnaciji, LinkEnumeratorklasa je prilično jednostavna; postat će kompliciraniji dok ga mijenjamo. U ovoj inkarnaciji jednostavno prolazi kroz popis pozivajućih objekata sve dok ne dođe do posljednje veze na unutarnjem povezanom popisu. Dvije metode potrebne za implementaciju java.util.Enumerationsučelja su hasMoreElementsi nextElement.

Naravno, jedan od razloga što ne koristimo java.util.Vectorklasu je taj što sam trebao sortirati vrijednosti u zbirci. Imali smo izbor: izraditi ovu kolekciju kako bi bila specifična za određenu vrstu objekta, koristeći na taj način intimno znanje o tipu objekta kako bismo ga razvrstali ili stvoriti generičnije rješenje temeljeno na sučeljima. Odabrao sam potonju metodu i definirao sučelje imenovano Comparatorza inkapsulaciju metoda potrebnih za sortiranje objekata. To sučelje je prikazano u nastavku.

javno sučelje Usporednik {javno boolean lessThan (objekt a, objekt b); javna logička vrijednost largerThan (objekt a, objekt b); javna boolean jednakaTo (objekt a, objekt b); void typeCheck (objekt a); }

Kao što možete vidjeti u gornjem kodu, Comparatorsučelje je prilično jednostavno. Sučelje zahtijeva jednu metodu za svaku od tri osnovne operacije usporedbe. Pomoću ovog sučelja popis može usporediti objekte koji se dodaju ili uklanjaju s objektima koji su već na popisu. Konačna metoda, typeCheckkoristi se za osiguravanje tipske sigurnosti zbirke. Kada se Comparatorobjekt koristi, pomoću njega Comparatorse može osigurati da su svi predmeti u zbirci istog tipa. Vrijednost ove provjere tipa je što vas sprečava da vidite iznimke za lijevanje objekata ako objekt na popisu nije bio tipa koji ste očekivali. Kasnije imam primjer koji koristi a Comparator, ali prije nego što prijeđemo na primjer, pogledajmo SynchroListrazred izravno.

javna klasa SynchroList {klasa Link {... ovo je prikazano gore ...} klasa LinkEnumerator implementira Enumeration {... klasa enumerator ...} / * Objekt za usporedbu naših elemenata * / Comparator cmp; Karika glava, rep; javni SynchroList () {} javni SynchroList (komparator c) {cmp = c; } private void before (Object o, Link p) {new Link (o, p.prev (), p); } private void after (Object o, Link p) {new Link (o, p, p.next ()); } private void remove (Link p) {if (p.prev () == null) {head = p.next (); (str.sljedeća ()). prev (null); } else if (p.next () == null) {tail = p.prev (); (p.prev ()). next (null); } else {p.prev (). next (p.next ()); p.sljedeća (). prev (p.prev ()); }} public void add (Object o) {// ako je cmp null, uvijek dodajte u rep popisa. if (cmp == null) {if (head == null) {head = new Link (o, null, null); rep = glava; } else {rep = nova veza (o, tail,null); } povratak; } cmp.typeCheck (o); if (head == null) {head = new Link (o, null, null); rep = glava; } else if (cmp.lessThan (o, head.getData ())) {head = nova veza (o, null, head); } else {Link l; for (l = head; l.next ()! = null; l = l.next ()) {if (cmp.lessThan (o, l.getData ())) {before (o, l); povratak; }} tail = nova veza (o, tail, null); } povratak; } javno logičko brisanje (objekt o) {if (cmp == null) return false; cmp.typeCheck (o); for (Link l = head; l! = null; l = l.next ()) {if (cmp.equalTo (o, l.getData ())) {remove (l); povratak istinit; } if (cmp.lessThan (o, l.getData ())) break; } return false; } javni sinkronizirani elementi nabrajanja () {return new LinkEnumerator (); } javna int veličina () {int rezultat = 0; for (Link l = head; l! = null; l = l.next ()) rezultat ++; povratni rezultat; }}if (head == null) {head = new Link (o, null, null); rep = glava; } else if (cmp.lessThan (o, head.getData ())) {head = nova veza (o, null, head); } else {Link l; for (l = head; l.next ()! = null; l = l.next ()) {if (cmp.lessThan (o, l.getData ())) {before (o, l); povratak; }} tail = nova veza (o, tail, null); } povratak; } javno logičko brisanje (objekt o) {if (cmp == null) return false; cmp.typeCheck (o); for (Link l = head; l! = null; l = l.next ()) {if (cmp.equalTo (o, l.getData ())) {remove (l); povratak istinit; } if (cmp.lessThan (o, l.getData ())) break; } return false; } javni sinkronizirani elementi nabrajanja () {return new LinkEnumerator (); } javna int veličina () {int rezultat = 0; for (Link l = head; l! = null; l = l.next ()) rezultat ++; povratni rezultat; }}if (head == null) {head = new Link (o, null, null); rep = glava; } else if (cmp.lessThan (o, head.getData ())) {head = nova veza (o, null, head); } else {Link l; for (l = head; l.next ()! = null; l = l.next ()) {if (cmp.lessThan (o, l.getData ())) {before (o, l); povratak; }} tail = nova veza (o, tail, null); } povratak; } javno logičko brisanje (objekt o) {if (cmp == null) return false; cmp.typeCheck (o); for (Link l = head; l! = null; l = l.next ()) {if (cmp.equalTo (o, l.getData ())) {remove (l); povratak istinit; } if (cmp.lessThan (o, l.getData ())) break; } return false; } javni sinkronizirani elementi nabrajanja () {return new LinkEnumerator (); } javna int veličina () {int rezultat = 0; for (Link l = head; l! = null; l = l.next ()) rezultat ++; povratni rezultat; }}} else {Link l; for (l = head; l.next ()! = null; l = l.next ()) {if (cmp.lessThan (o, l.getData ())) {before (o, l); povratak; }} tail = nova veza (o, tail, null); } povratak; } javno logičko brisanje (objekt o) {if (cmp == null) return false; cmp.typeCheck (o); for (Link l = head; l! = null; l = l.next ()) {if (cmp.equalTo (o, l.getData ())) {remove (l); povratak istinit; } if (cmp.lessThan (o, l.getData ())) break; } return false; } javni sinkronizirani elementi nabrajanja () {return new LinkEnumerator (); } javna int veličina () {int rezultat = 0; for (Link l = head; l! = null; l = l.next ()) rezultat ++; povratni rezultat; }}} else {Link l; for (l = head; l.next ()! = null; l = l.next ()) {if (cmp.lessThan (o, l.getData ())) {before (o, l); povratak; }} tail = nova veza (o, tail, null); } povratak; } javno logičko brisanje (objekt o) {if (cmp == null) return false; cmp.typeCheck (o); for (Link l = head; l! = null; l = l.next ()) {if (cmp.equalTo (o, l.getData ())) {remove (l); povratak istinit; } if (cmp.lessThan (o, l.getData ())) break; } return false; } javni sinkronizirani elementi nabrajanja () {return new LinkEnumerator (); } javna int veličina () {int rezultat = 0; for (Link l = head; l! = null; l = l.next ()) rezultat ++; povratni rezultat; }}typeCheck (o); for (Link l = head; l! = null; l = l.next ()) {if (cmp.equalTo (o, l.getData ())) {remove (l); povratak istinit; } if (cmp.lessThan (o, l.getData ())) break; } return false; } javni sinkronizirani elementi nabrajanja () {return new LinkEnumerator (); } javna int veličina () {int rezultat = 0; for (Link l = head; l! = null; l = l.next ()) rezultat ++; povratni rezultat; }}typeCheck (o); for (Link l = head; l! = null; l = l.next ()) {if (cmp.equalTo (o, l.getData ())) {remove (l); povratak istinit; } if (cmp.lessThan (o, l.getData ())) break; } return false; } javni sinkronizirani elementi nabrajanja () {return new LinkEnumerator (); } javna int veličina () {int rezultat = 0; for (Link l = head; l! = null; l = l.next ()) rezultat ++; povratni rezultat; }}