18 listopada 2008

SCJP - Stany wątków

Czytam sobie 9. rozdział książki "SCJP Sun Certified Programmer for Java 5 Study Guide (Exam 310-055)", tj. o wątkach, a konkretnie fragment o stanach w jakich wątek może się znajdować i... oczom nie wierzę. Stany o których piszą, w szczególności rozróżnienie ‘Running’/’Runnable’ po prostu nie istnieją! A na stan 'Terminated’ mówią – chyba tylko po to by wprowadzić zamęt – ‘Dead’. Kto nie wierzy, że jest inaczej niż piszą w Książce niech sprawdzi JavaDoca dla typu Thread.State. To już drugi poważny błąd jaki wykryłem w tej książce. O pierwszym pisałem niespełna miesiąc temu w artykule „SCJP - Statyczne klasy zagnieżdżone”. Trochę mnie to martwi, bo nie wiem ile tego typu nie wykrytych „psikusów” znajduje się w książce, na której bądź co bądź oparłem swój proces edukacyjny dla certyfikatu SCJP.

16 listopada 2008

SCJP - Tworzenie i uruchamianie wątków

Czasem spotyka się z opinią, że programowanie w języku Java jest na tyle proste, że studia informatyczne są zupełnie nie potrzebne by móc to robić dobrze – wystarczy kurs w stylu „Java dla opornych”. Oczywiście wszystko zależy od tego jak zdefiniujemy słowo „dobrze”. Można argumentować że aplikacja – by działać – nie musi być dobrze zaprojektowana, tj. z uwzględnieniem paradygmatów obiektowości i wzorców projektowych, że nie trzeba rozumieć pojęcia złożoności obliczeniowej żeby implementować algorytmy; ale nie da się zaprzeczyć temu, że aby tworzyć bezpieczne aplikacje współbieżne trzeba znać podstawowe zagadnienia programowania współbieżnego. Tu już nie chodzi przecież ani o elegancję ani nawet o wydajności. Tu chodzi o poprawność. W dzisiejszym artykule napiszę o podstawach pracy z wątkami w języku Java czyli właściwie o tym, jak sprawić by problemy współbieżności zaczęły się pojawiać – tj. jak uruchomić kod w osobnym wątku wykonania.

Wątek to nic innego jak pewien kod, który wykonywany jest przez Wirtualną Maszynę Javy niezależnie od kodu innych wątków, przy czym owo niezależnie oznacza współbieżnie. Aby wykonać pewien kod w osobnym wątku wykonania należy przede wszystkim określić jaki kod chcemy wykonać; należy więc nowy wątek zdefiniować. Definicja wątku to nic innego jak implementacja podklasy klasy java.lang.Thread.

Implementacja programu w języku Java jest równoznaczna z implementacją metody main(…). Uruchomienie programu napisanego w Javie to de facto uruchomienie metody main(…). Zakończenie się metody main(…) jest równoznaczne z zakończeniem się programu. Metoda main(…) to nic innego jak implementacja głównego wątku wykonania naszej aplikacji – wątek ten uruchamiamy uruchamiając aplikację. Każdy inny wątek implementujemy tworząc podklasę klasy java.lang.Thread i nadpisując jej metodę run() a więc analogicznie – implementując metodę, tyle że run() a nie main(…). Definicja wątku to jednak nic więcej jak tylko pewna klasa zawierająca fragment kodu w metodzie run(). Aby utworzyć nowy wątek i uruchomić w jego ramach kod zdefiniowany we wspomnianej metodzie run() należy wywołać metodę start() na instancji tejże klasy – dopiero wówczas tworzony i równocześnie uruchamiany jest wątek. Przykład poniżej.

public class TestClass {
public static void main(String[] args) {
System.out.println("Kod wykonany w wątku głównym");

Thread newThread = new MyThread();

// dopiero wywołując metodę start() tworzymy nowy wątek
newThread.start();
}
}

// ta klasa to tylko definicja wątku
class MyThread extends Thread {
public void run() {
System.out.println("Kod wykonany w nowym wątku");
}
}

Definiowanie wątków poprzez implementację podklas klasy Thread jest jak najbardziej poprawne, jednak zalecane jest aby robić to nieco inaczej. Metoda start() z klasy Thread pokazana w powyższym przykładzie tworzy nowy wątek i uruchamia w jego ramach kod zdefiniowany w metodzie run(). Oczywiście kod ten może nie robić nic innego, jak tylko uruchamiać kolejną metodę zdefiniowaną w innej klasie, w szczególności metodę run() zdefiniowaną w klasie implementującej interfejs java.lang.Runnable. Klasa Thread udostępnia także konstruktor jednoargumentowy, akceptujący instancje klasy implementującej interfejs Runnable. Implementacja metody run() w klasie Thread jest właśnie taka, że jeśli tworząc jej instancję przekazaliśmy obiekt Runnable, to w ramach wątku zostanie uruchomiona metoda run() tego właśnie obiektu. Wszystko powinno stać się jasne po przestudiowaniu kolejnego przykładu.

public class TestClass {
public static void main(String[] args) {
System.out.println("Kod wykonany w wątku głównym");

// wątek tworzymy na bazie instancji klasy implementującej Runnable
Thread newThread = new Thread(new MyRunnable());

newThread.start();
}
}

class MyRunnable implements Runnable {
public void run() {
System.out.println("Kod wykonany w nowym wątku");
}
}

Oprócz metody start() klasa Thread udostępnia jeszcze szereg innych, mniej lub bardziej kluczowych metod. Jedną z nich jest metoda getName(), która zwraca nazwę wątku. Wątek główny zawsze nazywa się ‘main’. Wątki tworzone przez programistę mają nazwy wygenerowane automatycznie przez Wirtualną Maszynę Javy, ale naturalnie nazwa ta może być zmieniona. W tym celu można użyć metody setName(…) albo konstruktora, który jako argument wywołania (drugi jeśli przekazujemy instancję Runnable lub pierwszy i jedyny, jeśli nie) akceptuje nazwę nowo tworzonego wątku. Nazwy te nie muszą być unikalne – różne wątki mogą mieć tą samą nazwę. Unikalny natomiast jest identyfikator wątku, który możemy odczytać z użyciem metody getId() i którego nie możemy zmienić. Przydatna jest także statyczna metoda currentThread(), która zwraca instancję klasy Thread opisującą aktualnie wykonywany wątek.

Ważną właściwością wątku jest jego stan. Aktualny stan wątku możemy sprawdzić posługując się metodą getState(), która zwraca jedną z wartości wyliczeniowych typu java.lang.Thread.State. Nowo utworzonej instancji wątku, który jeszcze nie został uruchomiony odpowiada stan NEW. Gdy wątek jest startowany, jego stan automatycznie zmienia się na RUNNABLE, by w końcu – potencjalnie przechodząc przez różne stany przejściowe – zakończyć się w stanie TERMINATED. Bardzo ważne jest by zapamiętać – zwłaszcza z perspektywy egzaminu SCJP – że wystartować można tylko i wyłącznie wątek który znajduje się w stanie NEW. Oznacza to, że każdy wątek może być uruchomiony tylko raz! Każde następne – tj. nie pierwsze – wywołanie metody start() na instancji reprezentującej wątek spowoduje zwrócenie wyjątku IllegalThreadStateException. Zerknijmy na poniższy przykład.

public class TestClass {
public static void main(String[] args) {
Thread newThread = new Thread(new MyRunnable(), "newThread");

System.out.println(
"Wątek " + newThread.getName() + " w stanie " + newThread.getState());

newThread.start();
}
}

class MyRunnable implements Runnable {
public void run() {
Thread thread = Thread.currentThread();

System.out.println(
"Wątek " + thread.getName() + " w stanie " + thread.getState());
}
}

Zauważmy, że w metodzie run() implementowanej w klasie MyRunnable nie mamy dostępu do instancji klasy Thread – bo też póki co kod ten nie jest powiązany z żadną instancją reprezentującą wątek – a więc musimy się posłużyć metodą statyczną currentThread(). Uruchomienie tego programu spowoduje wyświetlenie napisu:

Wątek newThread w stanie NEW
Wątek newThread w stanie RUNNABLE

Wiemy już, że wątek możemy uruchomić tylko i wyłącznie raz (także wątek który się zakończył nie może być uruchomiony ponownie), ale czy możemy utworzyć i uruchomić wiele wątków wykonujących jednocześnie (współbieżnie) ten sam kod? Oczywiście możemy – przykład poniżej.

public class TestClass {
public static void main(String[] args) {
Runnable runnable = new MyRunnable();

// wszystkie wątki będą wykonywały dokładnie ten sam kod
Thread threadA = new Thread(runnable);
Thread threadB = new Thread(runnable);
Thread threadC = new Thread(runnable);
Thread threadD = new Thread(runnable);

threadA.start();
threadB.start();
threadC.start();
threadD.start();
}
}

class MyRunnable implements Runnable {
private int val = 0;

public void run() {
for (int i = 0; i < 100; i++)
System.out.println(
"id == " + Thread.currentThread().getId() + ", val == " + getVal());
}

private synchronized int getVal() {
return ++val;
}
}

Powyższy program tworzy i uruchamia cztery nowe wątki, z których każdy, współbieżnie z pozostałymi wykonuje metodę run() dokładnie tej samej instancji klasy MyRunnable, a więc wyświetla i inkrementuje wartość tej samej zmiennej ‘val’. Poniżej fragment tego, co wypisał ten program po uruchomieniu w trakcie moich testów. Jak widać, wątki rzeczywiście przeplatają się między sobą (choć często występują też długie fragmenty, gdy nieprzerwanie wykonywał się jeden z wątków). Co ciekawe, w drugiej linii pojawia się wartość 150, mimo że w linii pierwszej pojawiła się wartość 224. Dowodzi to, że wątek o identyfikatorze 9 wykonał operację getVal() w momencie gdy wartość zmiennej ‘val’ wynosiła 149 poczym przestał się wykonywać przed wypisaniem komunikatu „id == 9, val == 150” i wznowił swe wykonanie, tj. wypisał ten komunikat, dopiero po tym jak inne wątki zwiększyły wartość tej zmiennej grubo ponad 200.

id == 10, val == 224
id == 9, val == 150
id == 10, val == 226
id == 11, val == 225
id == 10, val == 228

11 listopada 2008

SCJP - Sortowanie list i tablic oraz wyszukiwanie binarne

Dziś będzie o sortowaniu list i tablic oraz o wyszukiwaniu binarnym w tychże, a więc o klasach java.util.Arrays i java.util.Collections (nie mylmy z interfejsem java.util.Collection) oraz interfejsach java.util.Comparator<T> i java.lang.Comparable<T>.

Klasy Arrays oraz Collections to klasy narzędziowe implementujące szereg operacji statycznych ułatwiających pracę z kolekcjami i tablicami. Różnych ciekawych metod jest tam kilka, jednak z perspektywy egzaminu SCJP interesują nas głównie operacje sort(…) i binarySearch(…) zaimplementowane w wielu wersjach w obydwu klasach.

Operacja sort(…) z klasy Arrays służy do sortowania tablic a analogiczna operacja zaimplementowana w klasie Collections do sortowania list. Podstawowa wersja operacji sort(…) z klasy Arrays akceptuje jeden argument – tablicę wartości prymitywnych lub tablicę obiektów. Mamy także wersje sortujące tylko pewien fragment tablicy. Wtedy jako drugi argument wywołania podajemy indeks tablicy od którego (włącznie) należy zacząć sortowanie a jako trzeci argument indeks końca (nie włącznie) sortowanego fragmentu. Mamy więc do dyspozycji następujące funkcje:

  // dla tablic byte[], short[], int[], long[], float[], double[], char[] i Object[]
public static void sort(int[] tab)

// dla tablic byte[], short[], int[], long[], float[], double[], char[] i Object[]
public static void sort(int[] tab, int fromIndex, int toIndex)

Operacje te sortują elementy tablicy w porządku rosnącym. Oczywiste jest, jak wygląda ten porządek w przypadku liczb – znaki (tablica char[]) sortowane są alfabetycznie – co jednak z sortowaniem tablicy obiektów? Żeby posortować elementy musimy wiedzieć, jak porównać je między sobą (który z dwu obiektów jest większy?) – obiekty w sortowanej tablicy muszą być więc porównywalne. W języku Java obiekty są porównywalne jeśli implementują interfejs Comparable<T>. Interfejs ten definiuje jedną metodę:

int compareTo(T obj) 

Metoda ta zwraca liczbę ujemną, jeśli obiekt dla którego ją wywołano jest mniejszy od obiektu przekazanego jako argument; liczbę 0 jeśli obiekty są równe; liczbę dodatnią jeśli jest większy.

Interfejs Comparable<T> implementowany jest przez wiele klas z Javy SE, w tym przez wszystkie klasy opakowujące typów prostych (np. Integer, Double, Character) a także klasy Calendar, Date, Time czy String.

A co jeśli chcemy posortować tablicę zgodnie z innym porządkiem niż rosnący? A może tablicę Stringów chcemy posortować inaczej niż leksykograficznie (standardowy porządek dla Stringów to porządek leksykograficzny)? Może ważniejsza jest dla nas w danym zastosowaniu długość Stringa? A może chcielibyśmy posortować ignorując wielkość liter? Da się? Da! Wystarczy zdefiniować interesujący nas porządek implementując interfejs Comparator<T>. Klasa Arrays oprócz dwu wersji operacji sort(…) pokazanych powyżej implementuje jeszcze dwie wersje różniące się tym, że jako kolejny argument wywołania dodajemy obiekt implementujący interfejs Comparator<T>, który to określa porządek sortowanych elementów. Poniżej przykład.

public class TestClass {
public static void main(String[] args) {
String[] strings = { "Urszula", "Ola", "Agata", "Jola" };

Arrays.sort(strings, new LengthComparator());

for(String s : strings)
System.out.print(s + " ");
}
}

// określa sortowanie Stringów od najkrótszego do najdłuższego
class LengthComparator implements Comparator<String> {
public int compare(String strA, String strB) {
return strA.length() - strB.length();
}
}

Interfejs Comparator<T> wymaga implementacji metody compare(…), która zwraca liczbę ujemną, jeśli pierwszy argument wywołania jest mniejszy niż drugi; liczbę 0, jeśli są równe; liczbę dodatnią jeśli pierwszy argument jest większy. Efektem uruchomienia powyższego programu będzie wyświetlenie napisu:
Ola Jola Agata Urszula

Klasa Collections implementuje dwie wersje metody sort(…). Pierwsza służy do sortowania listy elementów które są porównywalne same z siebie, tj. implementują interfejs Comparable<T> zaś druga do sortowania listy dowolnych obiektów, ale za to musimy określić porządek sortowania przekazując jako drugi argument wywołania instancję komparatora, tj. instancję klasy implementującej interfejs Comparator<T>. Sygnatury tych metod wyglądają nieco odstraszająco i są następujące:

public static <T extends Comparable<? super T>> void sort(List<T> list)

public static <T> void sort(List<T> list, Comparator<? super T> comp)

Wyszukiwanie w kontekście list i tablic oznacza szukanie odpowiedzi na pytanie, czy dana lista lub tablica zawiera zadany element i jeśli tak to na której pozycji. Wyszukiwanie binarne implementowane przez metody binarySearch(…) z klasy Collections oraz Arrays to algorytm, który działa tylko dla kolekcji (list i tablic) posortowanych. Wyszukiwanie z zastosowaniem tego algorytmu działa o rząd wielkości szybciej niż wyszukiwanie liniowe (tj. przeglądanie listy element po elemencie) ale musimy pamiętać, że można go użyć tylko i wyłącznie do wyszukiwania w listach lub tablicach posortowanych. Co więcej, użycie algorytmu wyszukiwania binarnego dla listy czy tablicy nie posortowanej nie spowoduje błędu kompilacji czy wyjątku. Metoda binarySearch(…) wykona się, tyle że otrzymamy wynik nie zgodny ze stanem faktycznym.

W klasie Collections zaimplementowano dwie wersje metody binarySearch(…). Analogicznie jak w przypadku sortowania, pierwsza z nich służy do wyszukiwania z listy elementów, które są porównywalne a więc implementują interfejs Comparable<T>. Druga wersja służy do wyszukiwania z listy elementów, które same z siebie nie są porównywalne a więc musimy przekazać także komparator – obiekt, który będzie używany do porównywania – a więc obiekt implementujący interfejs Comparator<T>. Sygnatury tych metod są następujące:

public static <T> int binarySearch(List<? extends Comparable<? super T>> list,
T key)

public static <T> int binarySearch(List<? extends T> list,
T key,
Comparator<? super T> comp)

Drugiej wersji metody – tej w której przekazujemy także komparator – należy użyć także w przypadku, gdy lista posortowana jest zgodnie z porządkiem innym niż naturalny (określony przez metodę compareTo(…) interfejsu Comparable<T>). W szczególności, jeśli listę sortowaliśmy z użyciem konkretnego komparatora to do wyszukiwania binarnego powinniśmy użyć tego samego komparatora.

W klasie Arrays zaimplementowano po jednej metodzie dwuargumentowej dla tablicy każdego typu prostego i dla tablicy obiektów. Pierwszym argumentem jest tablica a drugim szukany element. Zaimplementowano także metodę, która akceptuje komparator. Sygnatury tych metod są następujące:

  // dla tablic byte[], short[], int[], long[], float[], double[], char[] i Object[]
public static int binarySearch(int[] a, int key)

public static <T> int binarySearch(T[] a,
T key,
Comparator<? super T> comp)