Programování

Používání vláken se sbírkami, část 1

Vlákna jsou nedílnou součástí jazyka Java. Pomocí vláken je mnoho algoritmů, například systémů správy front, snadněji přístupných než pomocí technik dotazování a opakování. Nedávno jsem při psaní třídy Java zjistil, že při výčtu seznamů potřebuji používat vlákna, a to odhalilo některé zajímavé problémy spojené s kolekcemi podporujícími vlákna.

Tento Java v hloubce Sloupec popisuje problémy, které jsem odhalil při pokusu o vytvoření kolekce bezpečné pro vlákna. Kolekce se nazývá „bezpečná pro vlákna“, když ji může bezpečně používat více klientů (vláken) současně. "Tak co je za problém?" ptáš se. Problém je v tom, že při běžném používání program mění kolekci (tzv mutovat) a přečte (volá se) výčet).

Někteří lidé prostě neregistrují prohlášení „Platforma Java je vícevláknová.“ Jistě, slyší to a kývnou hlavami. Nepochopili však, že na rozdíl od C nebo C ++, ve kterém bylo vlákno přišroubováno ze strany přes OS, jsou vlákna v Javě základními jazykovými konstrukty. Toto nedorozumění nebo špatné pochopení inherentně vláknové povahy Javy nevyhnutelně vede ke dvěma běžným nedostatkům v kódu Java programátorů: Buď nedokážou deklarovat synchronizovanou metodu, která by měla být (protože objekt je v průběhu spuštění metody) nebo deklarují metodu jako synchronizovanou, aby ji chránili, což způsobí, že zbytek systému bude fungovat neefektivně.

Na tento problém jsem narazil, když jsem chtěl kolekci, kterou by mohlo používat více vláken, aniž by zbytečně blokovalo provádění ostatních vláken. Žádná z tříd kolekce ve verzi JDK verze 1.1 není bezpečná pro vlákna. Konkrétně vám žádná z tříd kolekce neumožní výčet s jedním vláknem při mutování s jiným.

Kolekce, které nejsou bezpečné pro vlákna

Můj základní problém byl následující: Za předpokladu, že máte objednanou sbírku objektů, navrhněte třídu Java tak, aby vlákno mohlo vyjmenovat celou nebo část sbírky, aniž by se obávalo, že výčet bude neplatný kvůli jiným vláknům, které mění kolekci. Jako příklad problému zvažte Java Vektor třída. Tato třída není bezpečná pro vlákna a způsobuje mnoho problémů novým programátorům Java, když ji kombinují s vícevláknovým programem.

The Vektor třída poskytuje programátorům Java velmi užitečné zařízení: jmenovitě dynamicky velké pole objektů. V praxi můžete použít toto zařízení k ukládání výsledků, kde konečný počet objektů, se kterými budete pracovat, není znám, dokud nedokončíte všechny. Sestavil jsem následující příklad, abych demonstroval tento koncept.

01 import java.util.Vector; 02 import java.util.Enumeration; 03 ukázka veřejné třídy {04 public static void main (String args []) {05 Vector digits = new Vector (); 06 int výsledek = 0; 07 08 if (args.length == 0) {09 System.out.println ("Použití je java demo 12345"); 10 System.exit (1); 11} 12 13 pro (int i = 0; i = '0') && (c <= '9')) 16 digits.addElement (new Integer (c - '0')); 17 dalších 18 přestávka; 19} 20 System.out.println ("Existují" + digits.size () + "číslice."); 21 for (Enumeration e = digits.elements (); e.hasMoreElements ();) {22 result = result * 10 + ((Integer) e.nextElement ()). IntValue (); 23} 24 System.out.println (args [0] + "=" + výsledek); 25 System.exit (0); 26} 27} 

Jednoduchá třída výše používá a Vektor objekt sbírat číselné znaky z řetězce. Kolekce je poté vyčíslena pro výpočet celočíselné hodnoty řetězce. S touto třídou není nic špatného kromě toho, že není bezpečná pro vlákna. Pokud se stalo, že jiné vlákno obsahovalo odkaz na číslice vektor a toto vlákno vložilo do vektoru nový znak, výsledky smyčky v řádcích 21 až 23 výše by byly nepředvídatelné. Pokud k vložení došlo předtím, než objekt výčtu prošel bod vložení, výpočet vlákna výsledek zpracuje novou postavu. Pokud k vložení došlo poté, co výčet prošel bod vložení, smyčka by nezpracovala znak. Nejhorším scénářem je, že smyčka může hodit a NoSuchElementException pokud byl narušen interní seznam.

Tento příklad je právě ten - vymyšlený příklad. Ukazuje problém, ale jaká je šance, že během krátkého pětimístného nebo šestimístného výčtu běží další vlákno? V tomto příkladu je riziko nízké. Množství času, které uplyne, když jedno vlákno zahájí rizikovou operaci, což je v tomto příkladu výčet, a poté dokončí úkol, který se nazývá vlákno okno zranitelnostinebo okno. Toto konkrétní okno je známé jako stav závodu protože jedno vlákno „závodí“, aby dokončilo svůj úkol, než jiné vlákno použije kritický zdroj (seznam číslic). Když však začnete používat kolekce k reprezentaci skupiny několika tisíc elementů, například s databází, okno zranitelnosti se zvýší, protože výčet podprocesů stráví ve své výčtové smyčce mnohem více času, a to dělá šanci na spuštění jiného podprocesu O mnoho vyšší. Určitě nechcete, aby nějaké jiné vlákno měnilo seznam pod vámi! To, co chcete, je ujištění, že Výčet objekt, který držíte, je platný.

Jedním ze způsobů, jak se na tento problém dívat, je poznamenat, že Výčet objekt je oddělen od Vektor objekt. Protože jsou oddělené, nemohou si nad sebou navzájem udržet kontrolu, jakmile jsou vytvořeny. Tato volná vazba mi naznačila, že snad užitečnou cestou k prozkoumání byl výčet, který byl pevněji svázán s kolekcí, která ji vytvořila.

Vytváření sbírek

K vytvoření mé kolekce bezpečné pro vlákna jsem nejprve potřeboval kolekci. V mém případě byla nutná tříděná sbírka, ale neobtěžoval jsem se jít po celé trase binárního stromu. Místo toho jsem vytvořil kolekci, kterou jsem nazval a SynchroList. Tento měsíc se podívám na základní prvky kolekce SynchroList a popíšu, jak ji používat. Příští měsíc, v části 2, vezmu kolekci od jednoduché a snadno srozumitelné třídy Java po složitou třídu Java s více vlákny. Mým cílem je udržet design a implementaci kolekce odlišnou a srozumitelnou ve srovnání s technikami používanými k jejímu uvědomění.

Pojmenoval jsem svou třídu SynchroList. Název „SynchroList“ samozřejmě pochází ze zřetězení „synchronizace“ a „seznamu“. Sbírka je jednoduše dvojnásobně propojený seznam, jak můžete najít v jakékoli vysokoškolské učebnici programování, i když pomocí vnitřní třídy s názvem Odkaz, lze dosáhnout určité elegance. Vnitřní třída Odkaz je definována takto:

 třída Link {data soukromého objektu; soukromý odkaz nxt, prv; Odkaz (Objekt o, Odkaz p, Odkaz n) {nxt = n; prv = p; data = o; if (n! = null) n.prv = this; if (p! = null) p.nxt = this; } Objekt getData () {návratová data; } Odkaz next () {return nxt; } Link next (Link newNext) {Link r = nxt; nxt = newNext; návrat r;} Odkaz předchozí () {návrat prv; } Link předchozí (Link newPrev) {Link r = prv; prv = newPrev; return r;} public String toString () {return "Link (" + data + ")"; }} 

Jak vidíte v kódu výše, a Odkaz object encapsulates the linking behavior that the list will use to organize its objects. Chcete-li implementovat chování seznamu s dvojnásobným propojením, objekt obsahuje odkazy na jeho datový objekt, odkaz na další odkaz v řetězci a odkaz na předchozí odkaz v řetězci. Dále metody další a předchozí jsou přetížené, aby poskytly prostředky k aktualizaci ukazatele objektu. To je nezbytné, protože nadřazená třída bude muset vložit a odstranit odkazy do seznamu. Konstruktor odkazu je navržen tak, aby vytvořil a současně vložil odkaz. Uloží volání metody při implementaci seznamu.

V seznamu se používá jiná vnitřní třída - v tomto případě třída enumerátoru s názvem ListEnumerator. Tato třída implementuje java.util.Enumeration interface: standardní mechanismus, který Java používá k iteraci přes kolekci objektů. Tím, že náš enumerátor implementuje toto rozhraní, bude naše kolekce kompatibilní s jakýmikoli jinými třídami Java, které používají toto rozhraní k výčtu obsahu kolekce. Implementace této třídy je uvedena v kódu níže.

 třída LinkEnumerator implementuje výčet {soukromý odkaz aktuální, předchozí; LinkEnumerator () {current = head; } public boolean hasMoreElements () {return (current! = null); } public Object nextElement () {Object result = null; Link tmp; if (current! = null) {result = current.getData (); current = current.next (); } vrátit výsledek; }} 

Ve své současné inkarnaci LinkEnumerator třída je docela přímočará; jak to upravíme, bude to komplikovanější. V této inkarnaci jednoduše prochází seznamem volajícího objektu, dokud nedojde k poslednímu odkazu v interním propojeném seznamu. Tyto dvě metody potřebné k implementaci java.util.Enumeration rozhraní jsou hasMoreElements a nextElement.

Jedním z důvodů, proč nepoužíváme java.util.Vector třída je proto, že jsem potřeboval třídit hodnoty v kolekci. Měli jsme na výběr: sestavit tuto kolekci tak, aby byla specifická pro určitý typ objektu, a tak využívat tuto důvěrnou znalost typu objektu k jeho třídění, nebo vytvořit obecnější řešení založené na rozhraních. Zvolil jsem druhou metodu a definoval rozhraní s názvem Komparátor zapouzdřit metody nezbytné pro třídění objektů. Toto rozhraní je zobrazeno níže.

 public interface Comparator {public boolean lessThan (Object a, Object b); public boolean greaterThan (Objekt a, Objekt b); public boolean equalTo (Object a, Object b); void typeCheck (Objekt a); } 

Jak vidíte ve výše uvedeném kódu, Komparátor rozhraní je docela jednoduché. Rozhraní vyžaduje jednu metodu pro každou ze tří základních porovnávacích operací. Pomocí tohoto rozhraní může seznam porovnávat přidávané nebo odebírané objekty s objekty, které jsou již v seznamu. Konečná metoda, typ Zkontrolovat, se používá k zajištění typové bezpečnosti kolekce. Když Komparátor je použit objekt, Komparátor lze použít k zajištění toho, aby všechny objekty v kolekci byly stejného typu. Hodnota této kontroly typu spočívá v tom, že vám ušetří možnost vidět výjimky obsazení objektu, pokud objekt v seznamu nebyl typu, který jste očekávali. Později mám příklad, který používá a Komparátor, ale než se dostaneme k příkladu, podívejme se na SynchroList třída přímo.

 veřejná třída SynchroList {třída Link {... toto bylo ukázáno výše ...} třída LinkEnumerator implementuje Enumeration {... třída enumerátoru ...} / * Objekt pro porovnání našich prvků * / Comparator cmp; Spojovací hlava, ocas; public SynchroList () {} public SynchroList (komparátor 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 (); (p.next ()). prev (null); } else if (p.next () == null) {tail = p.prev (); (p.prev ()). next (null); } else {p.prev (). next (p.next ()); p.next (). předchozí (p.prev ()); }} public void add (Object o) {// je-li cmp null, vždy přidejte na konec seznamu. if (cmp == null) {if (head == null) {head = new Link (o, null, null); ocas = hlava; } else {tail = new Link (o, tail, null); } vrátit se; } cmp.typeCheck (o); if (head == null) {head = new Link (o, null, null); ocas = hlava; } else if (cmp.lessThan (o, head.getData ())) {head = new Link (o, null, head); } else {Link l; for (l = head; l.next ()! = null; l = l.next ()) {if (cmp.lessThan (o, l.getData ())) {before (o, l); vrátit se; }} ocas = nový odkaz (o, ocas, null); } vrátit se; } public boolean delete (Object 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); návrat true; } if (cmp.lessThan (o, l.getData ())) break; } vrátit false; } public synchronized Enumeration elements () {return new LinkEnumerator (); } public int size () {int vysledek = 0; for (Link l = head; l! = null; l = l.next ()) result ++; vrátit výsledek; }}