Използване на нишки с колекции, част 1

Нишките са неразделна част от езика Java. Използвайки нишки, много алгоритми, като системи за управление на опашки, са по-лесни за достъп, отколкото използват техники за анкетиране и цикли. Наскоро, докато пишех клас на Java, установих, че трябва да използвам нишки, докато изброявам списъци, и това разкри някои интересни проблеми, свързани с колекции, знаещи за нишки.

Тази колона в дълбочина на Java описва проблемите, които разкрих в опита си да разработя колекция, безопасна за нишки. Колекцията се нарича „безопасна за нишки“, когато може да се използва безопасно от множество клиенти (нишки) едновременно. "Та какъв е проблема?" ти питаш. Проблемът е, че при типично използване една програма променя колекция (наречена мутираща ) и я чете (наречена изброяване ).

Някои хора просто не регистрират изявлението „Платформата Java е многонишкова“. Разбира се, те го чуват и кимат с глава. Но те не разбират, че за разлика от C или C ++, при които резбата е била закрепена отстрани през ОС, нишките в Java са основни езикови конструкции. Това неразбиране или слабо разбиране на естеството на Java, свързано с резба, неизбежно води до два често срещани недостатъка в Java кода на програмистите: Или те не успяват да декларират метод като синхронизиран, който трябва да бъде (тъй като обектът е в противоречиво състояние по време на метод) или те декларират метод като синхронизиран, за да го защитят, което кара останалата част от системата да работи неефективно.

Попаднах на този проблем, когато исках колекция, която множество нишки могат да използват, без излишно да блокират изпълнението на останалите нишки. Нито един от класовете за събиране във версия 1.1 на JDK не е безопасен за нишки. По-конкретно, нито един от класовете за събиране няма да ви позволи да преброявате с една нишка, докато мутирате с друга.

Колекции, които не са безопасни за нишки

Основният ми проблем беше следният: Ако приемем, че имате подредена колекция от обекти, проектирайте Java клас, така че нишката да може да изброява цялата или част от колекцията, без да се притеснявате, че изброяването става невалидно поради други нишки, които променят колекцията. Като пример за проблема разгледайте Vectorкласа на Java . Този клас не е безопасен за нишки и създава много проблеми за новите програмисти на Java, когато го комбинират с многонишкова програма.

В Vectorклас осигурява много полезен инструмент за Java програмисти, а именно, динамично големина масив от обекти. На практика можете да използвате това съоръжение за съхраняване на резултати, при които окончателният брой обекти, с които ще имате работа, не е известен, докато не приключите с всички тях. Създадох следния пример, за да демонстрирам тази концепция.

01 импортиране java.util.Vector; 02 import java.util.Enumeration; 03 публичен клас Демо {04 публична статична празнота main (String args []) {05 Vector digits = 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 цифри.addElement (ново цяло число (c - '0')); 17 друго 18 почивка; 19} 20 System.out.println ("Има" + digits.size () + "цифри."); 21 за (Enumeration e = digits.elements (); e.hasMoreElements ();) {22 result = result * 10 + ((Integer) e.nextElement ()). IntValue (); 23} 24 System.out.println (аргументи [0] + "=" + резултат); 25 System.exit (0); 26} 27}

Простият клас по-горе използва Vectorобект за събиране на цифрови знаци от низ. След това колекцията се изброява, за да се изчисли целочислената стойност на низа. В този клас няма нищо лошо, освен че не е безопасен за нишки. Ако друга нишка случайно съдържа препратка към вектора на цифрите и тази нишка вмъкне нов символ във вектора, резултатите от цикъла в редове 21 до 23 по-горе биха били непредсказуеми. Ако вмъкването е настъпило преди обектът на изброяване да е преминал точката на вмъкване, резултатът от изчисленията на нишките ще обработи новия символ. Ако вмъкването се е случило, след като изброяването е преминало точката на вмъкване, цикълът няма да обработи знака. Най-лошият сценарий е, че цикълът може да хвърли aNoSuchElementException ако вътрешният списък е бил компрометиран.

Този пример е точно това - измислен пример. Той демонстрира проблема, но какъв е шансът да се изпълни друга нишка по време на кратко пет- или шестцифрено изброяване? В този пример рискът е нисък. Времето, което преминава, когато една нишка стартира операция в риск, което в този пример е изброяването и след това завършва задачата, се нарича прозорец на уязвимостта на нишката или прозорец . Този конкретен прозорец е известен като състезателно състояниезащото една нишка се „надпреварва“ да завърши задачата си, преди друга нишка да използва критичния ресурс (списъкът с цифри). Когато обаче започнете да използвате колекции за представяне на група от няколко хиляди елемента, например с база данни, прозорецът на уязвимост се увеличава, тъй като изброяването на нишките ще прекарва много повече време в своя цикъл на изброяване и това прави шансът да се изпълни друга нишка много по-високо. Със сигурност не искате друга нишка да променя списъка под вас! Това, което искате, е уверение, че Enumerationобектът, който държите, е валиден.

Един от начините да разгледаме този проблем е да отбележим, че Enumerationобектът е отделен от Vectorобекта. Тъй като са отделни, те не са в състояние да запазят контрол един над друг, след като са създадени. Това свободно свързване ми подсказа, че може би полезен път за изследване е изброяване, което е по-тясно обвързано с колекцията, която го е създала.

Създаване на колекции

За да създам моята колекция, безопасна за нишки, първо се нуждаех от колекция. В моя случай беше необходима сортирана колекция, но не си направих труда да извървя пълния маршрут на двоичното дърво. Вместо това създадох колекция, която нарекох SynchroList . Този месец ще разгледам основните елементи на колекцията SynchroList и ще опиша как да я използвам. Следващият месец, в Част 2, ще пренеса колекцията от прост, лесен за разбиране Java клас до сложен многонишков Java клас. Целта ми е да запазя дизайна и изпълнението на една колекция различна и разбираема по отношение на техниките, използвани за нейното осъзнаване.

Кръстих класа си SynchroList. Името "SynchroList", разбира се, идва от обединяването на "синхронизация" и "списък". Колекцията е просто двойно свързан списък, както бихте могли да намерите във всеки учебник по програмиране в колежа, въпреки че чрез използването на вътрешен клас, наречен Link, може да се постигне известна елегантност. Вътрешният клас Linkсе дефинира както следва:

клас Link {private Object data; частна връзка nxt, prv; Връзка (Обект o, Връзка p, Връзка n) {nxt = n; prv = p; данни = o; if (n! = null) n.prv = това; ако (p! = нула) p.nxt = това; } Обект getData () {връщане на данни; } Връзка следваща () {return nxt; } Следваща връзка (Връзка newNext) {Връзка r = nxt; nxt = newNext; return r;} Връзка prev () {return prv; } Връзка prev (Връзка newPrev) {Връзка r = prv; prv = newPrev; return r;} public String toString () {return "Link (" + data + ")"; }}

Както можете да видите в горния код, Linkобект капсулира поведението на свързване, което списъкът ще използва, за да организира своите обекти. За да реализира поведението на двойно свързания списък, обектът съдържа препратки към своя обект от данни, препратка към следващата връзка във веригата и препратка към предишната връзка във веригата. Освен това методите nextи prevса претоварени, за да осигурят средство за актуализиране на показалеца на обекта. Това е необходимо, тъй като родителският клас ще трябва да вмъква и изтрива връзки в списъка. Конструкторът на връзки е предназначен да създава и вмъква връзка едновременно. Това спестява извикване на метод при изпълнението на списъка.

В списъка се използва друг вътрешен клас - в този случай име на клас на изброител ListEnumerator. Този клас изпълнява java.util.Enumerationинтерфейса: стандартният механизъм, който Java използва за итерация над колекция от обекти. Като накараме нашия изброител да внедри този интерфейс, нашата колекция ще бъде съвместима с всички други Java класове, които използват този интерфейс за изброяване на съдържанието на колекция. Изпълнението на този клас е показано в кода по-долу.

клас LinkEnumerator изпълнява Enumeration {private Link current, previous; LinkEnumerator () {текущ = глава; } публичен булев hasMoreElements () {return (текущ! = null); } публичен обект nextElement () {резултат на обекта = нула; Връзка tmp; if (current! = null) {result = current.getData (); текущ = current.next (); } връщане на резултат; }}

В сегашното си въплъщение LinkEnumeratorкласът е доста ясен; ще стане по-сложно, докато го модифицираме. В това въплъщение той просто преминава през списъка за извикващия обект, докато стигне до последната връзка във вътрешния свързан списък. Двата метода, необходими за реализиране на java.util.Enumerationинтерфейса, са hasMoreElementsи nextElement.

Разбира се, една от причините да не използваме java.util.Vectorкласа е, защото трябваше да сортирам стойностите в колекцията. Имахме избор: да изградим тази колекция, за да бъде специфична за определен тип обект, като по този начин използваме това интимно познание за типа обект, за да го сортираме, или да създадем по-общо решение, базирано на интерфейси. Избрах последния метод и определих интерфейс, наречен Comparatorда капсулира методите, необходими за сортиране на обекти. Този интерфейс е показан по-долу.

публичен интерфейс за сравнение {публично булево по-малкоThan (Обект a, Обект b); публичен булев по-голям от обект (обект a, обект b); публичен булев еквивалент (Обект a, Обект b); void typeCheck (Обект а); }

Както можете да видите в горния код, Comparatorинтерфейсът е доста прост. Интерфейсът изисква един метод за всяка от трите основни операции за сравнение. Използвайки този интерфейс, списъкът може да сравнява обектите, които се добавят или премахват с обекти, които вече са в списъка. Последният метод, typeCheckсе използва, за да се гарантира безопасността на типа на колекцията. Когато Comparatorобектът се използва, Comparatorможе да се използва, за да се гарантира, че всички обекти в колекцията са от един и същи тип. Стойността на тази проверка на типа е, че ви спестява да видите изключения за преместване на обекти, ако обектът в списъка не е от типа, който сте очаквали. По-късно имам пример, който използва a Comparator, но преди да стигнем до примера, нека разгледаме SynchroListкласа директно.

 public class SynchroList { class Link { ... this was shown above ... } class LinkEnumerator implements Enumeration { ... the enumerator class ... } /* An object for comparing our elements */ Comparator cmp; Link head, tail; public SynchroList() { } public SynchroList(Comparator 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().prev(p.prev()); } } public void add(Object o) { // if cmp is null, always add to the tail of the list. if (cmp == null) { if (head == null) { head = new Link(o, null, null); tail = head; } else { tail = new Link(o, tail, null); } return; } cmp.typeCheck(o); if (head == null) { head = new Link(o, null, null); tail = head; } 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); return; } } tail = new Link(o, tail, null); } return; } 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); return true; } if (cmp.lessThan(o, l.getData())) break; } return false; } public synchronized Enumeration elements() { return new LinkEnumerator(); } public int size() { int result = 0; for (Link l = head; l != null; l = l.next()) result++; return result; } }