Tråder er en integrert del av Java-språket. Ved å bruke tråder er det enklere å få tilgang til mange algoritmer, som køhåndteringssystemer, enn de bruker avstemning og looping-teknikker. Nylig, mens jeg skrev en Java-klasse, fant jeg ut at jeg trengte å bruke tråder mens jeg oppregnet lister, og dette avdekket noen interessante problemer knyttet til trådbevisste samlinger.
Dette Java i dybden kolonne beskriver problemene jeg avdekket i mitt forsøk på å utvikle en trådsikker samling. En samling kalles "trådsikker" når den kan brukes trygt av flere klienter (tråder) samtidig. "Så hva er problemet?" du spør. Problemet er at, i vanlig bruk, endrer et program en samling (kalt mutering), og leser den (kalt oppregning).
Noen mennesker registrerer rett og slett ikke utsagnet "Java-plattformen er multitrådet." Visst, de hører det, og de nikker på hodet. Men de forstår ikke at, i motsetning til C eller C ++, hvor tråder ble boltet på fra siden gjennom operativsystemet, er tråder i Java grunnleggende språkkonstruksjoner. Denne misforståelsen, eller den dårlige forståelsen, av den iboende gjengede naturen til Java, fører uunngåelig til to vanlige feil i programmererens Java-kode: Enten klarer de ikke å erklære en metode som synkronisert som skal være (fordi objektet er i en inkonsekvent tilstand under metodeens utførelse) eller de erklærer en metode som synkronisert for å beskytte den, noe som får resten av systemet til å fungere ineffektivt.
Jeg kom over dette problemet da jeg ønsket en samling som flere tråder kunne bruke uten å unødvendig blokkere utførelsen av de andre trådene. Ingen av samlingsklassene i 1.1-versjonen av JDK er trådsikre. Spesielt vil ingen av samlingsklassene tillate deg å telle opp med en tråd mens du muterer med en annen.
Ikke-trådsikre samlinger
Mitt grunnleggende problem var som følger: Forutsatt at du har en ordnet samling av objekter, design en Java-klasse slik at en tråd kan telle hele eller deler av samlingen uten å bekymre deg for at opptellingen blir ugyldig på grunn av andre tråder som endrer samlingen. Som et eksempel på problemet, kan du vurdere Java Vector klasse. Denne klassen er ikke trådsikker og forårsaker mange problemer for nye Java-programmerere når de kombinerer den med et flertrådet program.
De Vector klasse gir et veldig nyttig anlegg for Java-programmerere: nemlig et dynamisk stort utvalg av objekter. I praksis kan du bruke dette anlegget til å lagre resultater der det endelige antall objekter du vil håndtere ikke er kjent før du er ferdig med dem alle. Jeg konstruerte følgende eksempel for å demonstrere dette konseptet.
01 import java.util.Vector; 02 importere java.util.Enumeration; 03 public class Demo {04 public static void main (String args []) {05 Vector digits = new Vector (); 06 int resultat = 0; 07 08 if (args.length == 0) {09 System.out.println ("Bruk er java demo 12345"); 10 System.exit (1); 11} 12 13 for (int i = 0; i = '0') && (c <= '9')) 16 sifre.addElement (nytt heltal (c - '0')); 17 andre 18 pause; 19} 20 System.out.println ("Det er" + sifre. Størrelse () + "sifre."); 21 for (Enumeration e = digits.elements (); e.hasMoreElements ();) {22 result = result * 10 + ((Integer) e.nextElement ()). IntValue (); 23} 24 System.out.println (args [0] + "=" + resultat); 25 System.exit (0); 26} 27} Den enkle klassen ovenfor bruker a Vector objekt for å samle siffertegn fra en streng. Samlingen blir deretter oppregnet for å beregne strengverdiens heltall. Det er ikke noe galt med denne klassen bortsett fra at den ikke er trådsikker. Hvis en annen tråd tilfeldigvis inneholdt en referanse til sifre vektor, og den tråden satte inn et nytt tegn i vektoren, ville resultatene av sløyfen i linje 21 til 23 ovenfor være uforutsigbare. Hvis innsettingen skjedde før nummereringsobjektet hadde passert innsettingspunktet, beregner tråden resultat ville behandle den nye karakteren. Hvis innsettingen skjedde etter at opptellingen hadde passert innsettingspunktet, ville ikke løkken behandle tegnet. Det verste tilfellet er at løkken kan kaste et NoSuchElementException hvis den interne listen var kompromittert.
Dette eksemplet er nettopp det - et konstruert eksempel. Det demonstrerer problemet, men hva er sjansen for at en annen tråd kjører under en kort fem- eller sekssifret oppregning? I dette eksemplet er risikoen lav. Hvor lang tid som går når en tråd starter en operasjon i fare, som i dette eksemplet er opptellingen, og deretter fullfører oppgaven kalles trådens sårbarhetsvindu, eller vindu. Dette spesielle vinduet er kjent som en løpstilstand fordi den ene tråden "løper" for å fullføre oppgaven før en annen tråd bruker den kritiske ressursen (listen over sifre). Når du begynner å bruke samlinger for å representere en gruppe på flere tusen elementer, for eksempel med en database, øker sårbarhetsvinduet fordi tråden som teller, vil bruke mye mer tid i opptellingssløyfen, og det gjør sjansen for at en annen tråd kjører mye høyere. Du vil absolutt ikke ha noen annen tråd som endrer listen under deg! Det du ønsker er en forsikring om at Oppregning objektet du holder er gyldig.
En måte å se på dette problemet er å merke seg at Oppregning objektet er skilt fra Vector gjenstand. Fordi de er adskilte, klarer de ikke å beholde kontrollen over hverandre når de er opprettet. Denne løse bindingen foreslo for meg at kanskje en nyttig vei å utforske var en oppregning som var tettere bundet til samlingen som produserte den.
Opprette samlinger
For å lage min trådsikre samling, trengte jeg først en samling. I mitt tilfelle var det nødvendig med en sortert samling, men jeg gadd ikke å gå hele den binære treveien. I stedet opprettet jeg en samling som jeg kalte en SynchroList. Denne måneden vil jeg se på kjerneelementene i SynchroList-samlingen og beskrive hvordan du bruker den. Neste måned, i del 2, tar jeg samlingen fra en enkel, lettfattelig Java-klasse til en kompleks flertrådet Java-klasse. Målet mitt er å holde utformingen og implementeringen av en samling tydelig og forståelig i forhold til teknikkene som brukes til å gjøre den trådbevisst.
Jeg kalte klassen min SynchroList. Navnet "SynchroList" kommer selvfølgelig fra sammenkoblingen av "synkronisering" og "liste". Samlingen er ganske enkelt en dobbeltkoblet liste som du kan finne i hvilken som helst college-lærebok om programmering, men gjennom bruk av en indre klasse som heter Link, kan en viss eleganse oppnås. Den indre klassen Link er definert som følger:
class Link {private Objektdata; private Link nxt, prv; Link (Object o, Link p, Link n) {nxt = n; prv = p; data = o; hvis (n! = null) n.prv = dette; hvis (p! = null) p.nxt = dette; } Object getData () {return data; } Koble neste () {retur nxt; } Link neste (Link newNext) {Link r = nxt; nxt = newNext; return r;} Link prev () {return prv; } Link prev (Link newPrev) {Link r = prv; prv = newPrev; returner r;} offentlig String toString () {return "Link (" + data + ")"; }} Som du kan se i koden ovenfor, a Link objekt innkapsler koblingsatferden som listen vil bruke til å organisere objektene. For å implementere den dobbeltkoblede listen, inneholder objektet referanser til dataobjektet, en referanse til neste lenke i kjeden og en referanse til forrige lenke i kjeden. Videre metodene neste og prev er overbelastet for å gi et middel for å oppdatere objektets peker. Dette er nødvendig da foreldreklassen må sette inn og slette lenker i listen. Koblingskonstruktøren er designet for å opprette og sette inn en lenke samtidig. Dette sparer en metodeanrop i implementeringen av listen.
En annen indre klasse brukes i listen - i dette tilfellet en tellerklasse som heter ListEnumerator. Denne klassen implementerer java.util.Enumeration grensesnitt: standardmekanismen som Java bruker til å iterere over en samling objekter. Ved å la vår teller implementere dette grensesnittet, vil samlingen vår være kompatibel med andre Java-klasser som bruker dette grensesnittet til å telle opp innholdet i en samling. Implementeringen av denne klassen vises i koden nedenfor.
klasse LinkEnumerator implementerer Enumeration {private Link current, previous; LinkEnumerator () {current = head; } offentlige boolske hasMoreElements () {retur (nåværende! = null); } public Object nextElement () {Object result = null; Link tmp; hvis (gjeldende! = null) {resultat = gjeldende.getData (); gjeldende = gjeldende.neste (); } returnere resultat; }} I sin nåværende inkarnasjon, har LinkEnumerator klassen er ganske grei; det vil bli mer komplisert når vi endrer det. I denne inkarnasjonen går den ganske enkelt gjennom listen for det kallende objektet til den kommer til den siste lenken i den interne koblede listen. De to metodene som kreves for å implementere java.util.Enumeration grensesnitt er hasMoreElements og nesteElement.
Selvfølgelig, en av grunnene til at vi ikke bruker java.util.Vector klasse er fordi jeg trengte å sortere verdiene i samlingen. Vi hadde et valg: å bygge denne samlingen for å være spesifikk for en bestemt type objekt, og dermed bruke den intime kunnskapen om objekttypen for å sortere den, eller for å lage en mer generisk løsning basert på grensesnitt. Jeg valgte sistnevnte metode og definerte et grensesnitt som heter Komparator å kapsle inn metodene som er nødvendige for å sortere objekter. Grensesnittet er vist nedenfor.
offentlig grensesnitt Comparator {public boolean lessThan (Object a, Object b); offentlig boolsk greaterThan (Objekt a, Objekt b); offentlig boolsk equalTo (Objekt a, Objekt b); void typeCheck (Objekt a); } Som du kan se i koden ovenfor, Komparator grensesnittet er ganske enkelt. Grensesnittet krever en metode for hver av de tre grunnleggende sammenligningsoperasjonene. Ved hjelp av dette grensesnittet kan listen sammenligne objektene som legges til eller fjernes med objekter som allerede er på listen. Den endelige metoden, type Sjekk, brukes til å sikre samlingen typesikkerhet. Når Komparator objektet brukes, Komparator kan brukes til å sikre at gjenstander i samlingen er av samme type. Verdien av denne typekontrollen er at den sparer deg for å se unntak for objektkasting hvis objektet i listen ikke var av typen du forventet. Jeg har et eksempel senere som bruker en Komparator, men før vi kommer til eksemplet, la oss se på SynchroList klasse direkte.
offentlig klasse SynchroList {class Link {... dette ble vist ovenfor ...} class LinkEnumerator implementerer Enumeration {... the enumerator class ...} / * Et objekt for å sammenligne elementene våre * / Comparator cmp; Link hodet, halen; offentlig SynchroList () {} offentlig SynchroList (Comparator c) {cmp = c; } privat tomrom før (Objekt o, Link p) {ny Link (o, p.prev (), p); } privat tomrom etter (Object o, Link p) {new Link (o, p, p.next ()); } privat tomrom fjern (Link p) {if (p.prev () == null) {head = p.next (); (s.neste ()). prev (null); } annet hvis (p.next () == null) {tail = p.prev (); (s. forrige ()). neste (null); } annet {s. forrige (). neste (s. neste ()); p.next (). prev (p.prev ()); }} public void add (Object o) {// hvis cmp er null, legg alltid til i halen på listen. if (cmp == null) {if (head == null) {head = new Link (o, null, null); hale = hode; } annet {tail = new Link (o, tail, null); } komme tilbake; } cmp.typeCheck (o); if (head == null) {head = new Link (o, null, null); hale = hode; } annet hvis (cmp.lessThan (o, head.getData ())) {head = new Link (o, null, head); } annet {Link l; for (l = head; l.next ()! = null; l = l.next ()) {if (cmp.lessThan (o, l.getData ())) {before (o, l); komme tilbake; }} hale = ny lenke (o, hale, null); } komme tilbake; } public boolean delete (Object o) {if (cmp == null) returner false; cmp.typeCheck (o); for (Link l = head; l! = null; l = l.next ()) {if (cmp.equalTo (o, l.getData ())) {remove (l); returner sant; } if (cmp.lessThan (o, l.getData ())) break; } returner falsk; } offentlige synkroniserte oppføringselementer () {return new LinkEnumerator (); } offentlig int-størrelse () {int-resultat = 0; for (Link l = head; l! = null; l = l.next ()) result ++; returresultat; }}
