Halting Problem

Newsqueak w C#

Zapoznamy się z kilkoma mechanizmami do pracy z wątkami, oferowanymi przez .NET, a zrobimy to podpatrując i emulując pewne idee z mało znanego języka programowania Newsqueak.

Also available in English

Grudzień 2007

Newsqueak

Ciekawe podejście do wątków prezentuje język Newsqueak (nie mylić ze Squeakiem, implementacją Smalltalka) autorstwa m. in. Roba Pike'a. Komunikacja między wątkami odbywa się tam przy pomocy kanałów (channels), które są częścią samego języka. Na przykładach przekonamy się na czym polega praca z kanałami.

c = chan of int;
c = mk();

W pierwszej linii deklarujemy c jako kanał mogący przyjmować i odbierać liczby całkowite. W lini drugiej tworzymy i inicjalizujemy zdeklarowany wcześniej kanał (dla uproszczenia przyjmijmy, że mk() działa jak operator new w C#). Czas skorzystać z kanału i przesłać jakieś dane.

c <-= 3;

// tymczasem gdzieś w innym wątku...
int x <-= c;

Najpierw wysyłamy liczbę 3 do kanału c. Gdy zmienna typu chan jest z lewej strony operatora <-=, dane są umieszczane w kanale, gdy <-= znajduje się z prawej strony kanału, odbieramy dane. Jak łatwo się domyślić zmienna x zawiera teraz liczbę 3.

Komunikacja z użyciem kanałów jest całkowicie synchroniczna, tzn. wątek wysyłający dane blokuje się dopóki ktoś ich nie pobierze. Jeśli odbiorca próbuje pobrać dane z kanału, jego wątek blokuje się dopóki nadawca nie wyśle danych. Z tego powodu jeden wątek nie może jednocześnie nadać do siebie i odebrać danych tym samym kanałem. Nie istnieje żaden bufor, który umożliwiałby umieszczenie w kanale kilku wartości na raz.

Dzięki kanałom Newsqueak pozwala na łatwe pobieranie wartości z funkcji wykonujących się niezależnie od głównego wątku. Mając jakąś funkcję foo, która pobiera argumenty x i y, możemy stworzyć nowy wątek komendą begin.

begin foo(x, y)

Jeśli gdzieś w ciele funkcji foo mamy zdefiniowane kanał, możemy komunikować się z nowo stworzonym wątkiem. Oczywiście do komunikacji w obie strony potrzebne będą dwa kanały.

Składając to wszystko razem, spójrzmy na prosty przykład użycia kanałów.

void Counter(c: chan of int)
{
    int n = 1;
    for(;;)
    {
        c <-= n++;
    }           
}

nat := mk(chan of int);
begin Counter(nat);
int n;
for(;;)
{
    n <-= nat;
    print("%d\n", n);
}

Po tej krótkiej, lecz mocno skróconej prezentacji języka Newsqueak, możemy spróbować odtworzyć tę funcjonalność w C#.

EventWaitHandle

Aby uniknąć typowych dla pracy z wieloma wątkami problemów z synchronizacją, możemy skorzystać z kilku klas biblioteki .NET. Jedną z nich jest EventWaitHandle zawarta w przestrzeni nazw System.Threading. Choć nie jest to najwydajniejszy sposób, pozwoli nam w łatwy sposób emulować działanie newsqueakowych kanałów. Klasa EventWaitHandle pozwala wątkom komunikować się między sobą, choć w dość ograniczony sposób.

Implementacja

Stworzymy klasę Channel wraz z dwoma publicznymi metodami: Send i Receive. Najistotniejszymi elementami tej klasy będą dwa obiekty typu EventWaitHandle. Zawierają one metody Set i WaitOne. Wątek, który wywołał WaitOne blokuje się, dopóki inny wątek nie zasygnalizuje gotowości, wywołując Set na tym samym obiekcie EventWaitHandle.

Domyślny konstruktor klasy Channel tworzy oba obiekty EventWaitHandle w następujący sposób:

sendIt = new EventWaitHandle(false, EventResetMode.AutoReset);
waitForData = new EventWaitHandle(false, EventResetMode.AutoReset);

Wartość pierwszego argumentu , false, oznacza, że utworzona instancja nie będzie domyślnie sygnalizowała gotowości (natomiast wartość true spowoduje, że po stworzeniu obiektu zostanie wywołana metoda Set). Drugi argument ustawia tryb działania danej instancji EventWaitHandle. Gdy kilka wątków da sygnał za pomocą WaitOne, tworzy się kolejka. AutoReset oznacza, że każde wywołnie Set odblokuje tylko jeden z czekających wątków.

Spójrzmy na kod źródłowy wspomnianych metod naszego kanału, pamiętając o tym, że obie będą wywoływane w odrębnych wątkach.

public void Send(T packet) 
{
    waitForData.WaitOne();
    lock (locker) { data = packet; }
    sendIt.Set();
}

public T Receive()
{
    T packet;
    waitForData.Set();
    sendIt.WaitOne();
    lock (locker)
    {
        packet = data;
        data = default(T);
    }
    return packet;
}

Podczas wysyłania najpierw sprawdzamy czy inny wątek nie zasygnalizował, że chce odebrać dane. Taki sygnał wydajemy w metodzie Receive wywołując Set na prywatnej składowej waitForData. Nie wyślemy niczego, jeśli jakiś wątek nie zasygnalizuje chęci odebrania danych. Analogicznie jest w odwrotnym przypadku.

Send i Receive korzystają również z locka - innego narzędzia do pracy wielowątkowej. Instrukcja lock gwarantuje, że inny wątek nie zmodyfikuje danych, z których właśnie korzystamy. Dzięki temu możemy ustrzec się przed sytuacjami podobnymi do poniższej:

float x = NumberFactory.X;
float y = SomeCalculation();
if(y != 0) {
// w tym momencie inny wątek wykonuje: y = 0,
// po czym wracmy do wykonywania naszego wątku i...
    float result = x/y;  
}

Wystarczy, że obejmiemy ten fragment kodu lockiem.

lock(someObject)
{
    // powyższy kod tutaj
}

Wszystko co znajduje się w klamrach - fragment kodu, do którego chcemy mieć wyłączność w danym momencie - tylko jeden wątek może założyć locka na obiekt blokujący. Jeśli wątek próbuje założyć locka na zajęty już obiekt, zostaje zablokowany i czeka aż lock zostanie zdjęty.

Należy minimalizować użycie locków, ponieważ łatwo doprowadzić do sytuacji, gdzie nasze wątki więcej czasu spędzają oczekując na swoją kolej, zamiast wykonywać powierzone im zadanie.

Przykład

Przykładem zastosowania klasy Channel będzie sito Erastotenesa - prosty algorytm pozwalający na uzyskanie kolejnych liczb pierwszych. Działa on w następujący sposób: wybieramy najmniejszą liczbę większą od 1, czyli 2, po czym wyrzucamy wszystkie jej wielokrotności. Przechodzimy do najmniejszej z pozostałych liczb, będzie to 3, i znów wyrzucamy kolejne jej wielokrotności. Postępując dalej w ten sposób otrzymamy kolejne liczby pierwsze.

Pomysł implementacji, jak i sama idea kanałów, zaczerpnięty został z wykładu Roba Pike'a dostępnego na Google Video. Kod wygląda bardzo podobnie, nawet biorąc pod uwagę różnice między Newsqueakiem a C#, co było zamiarem autora.

Channel<int> chan = Sieve();
// wypisz pierwsze 100 liczb pierwszych 
for (int i = 0; i < 100; i++)
{
    Console.WriteLine("{0}", chan.Receive());
}

Metoda Sieve zwraca kanał do przesyłania liczb całkowitych, z którego odbieramy kolejne liczby pierwsze i wypisujemy je na ekran. Początkowo utworzony powyżej kanał, przesyła do pętli dane bezpośrednio z metody Counter, uruchomionej w nowym wątku, a której implementacja jest analogiczna do przedstawionej wcześniej wersji newsqueakowej, z tą drobną różnicą, że wyliczanie zaczyna od liczby 2.

static public Channel<int> Sieve()
{
    Channel<int> c = new Channel<int>();
    new Thread(Counter).Start(c);
    Channel<int> prime = new Channel<int>();
    new Thread(delegate()
    {
        int p;
        Channel<int> newChan;
        for (; ; ) {
            p = c.Receive();
            prime.Send(p);
            newChan = new Channel<int>();
            FilterArg arg = new FilterArg();
            arg.Prime = p;
            arg.Listener = c;
            arg.Sender = newChan;
            new Thread(Filter).Start(arg);
            c = newChan;
        }
    }).Start();
    return prime;
}

Sieve rozpoczyna kolejny wątek, a w nim w nieskończonej pętli sprzęgamy ze sobą kolejne filtry (metoda Filter), które wykreślają wielokrotności pewnej liczby pierwszej (otrzymanej jako składowa argumentu). Jak widać rozpoczęcie wątku sprowadza się do utworzenia obiektu typu Thread, jako argument konstruktora podając instancję jednego z poniższych delegatów:

public delegate void ThreadStart();
public delegate void ParametrizedThreadStart(Object obj);

Jednak w powyższym przykładzie nie tworzymy żadnych delegatów explicite, lecz używamy skróconego zapisu, tzn. jako parametr dla Thread użyto nazwy metody, którą chcemy uruchomić w osobnym wątku, zgodnej z sygnaturą jednego z ww. delegatów. Po utworzeniu obiektu typu Thread wystarczy wywołać jego metodę Start.

Gdy cała maszyneria zostaje wpuszczona w ruch, w nieskończonej pętli odbieramy liczbę 2 - najmniejszą w danej chwili liczbę całkowitą i przesyłamy ją dalej (w tym etapie zostaje ona wypisana na ekran). Następnie zostaje uruchomiony wątek "wykreślający" kolejne wielokrotności dwójki. Teraz każda liczba zanim pojawi się w pętli w Main, najpierw z Counter trafi do wątku odrzucającego wielokrotności liczby 2. Kolejne iteracje pętli zawartej w metodzie Sieve dodają koleje filtry; dla wielokrotności liczby 3, liczby 5 itd., czyli liczb otrzymywanych z kanału c.

Warto zauważyć, że w kodzie naszego sita, mimo dużej liczby uruchomionych wątków, nigdzie nie korzystamy z locka. Tak też jest w oryginalnej implementacji - właśnie dzięki kanałom.

Na koniec

Podkreślam, że zarówno kanały i podany powyżej przykład ich użycia zaczerpnąłem m. in. z wykładu Roba Pike'a, który naprawdę warto obejrzeć. Aby dowiedzieć się więcej o Newsqueaku, warto zapoznać się ze slajdami z wykładu zatytułowanego "Construction of Concurrent Systems Software" (PDF: 1, 2, 3). Klasa Channel to ćwiczenia pozwalające zapoznać się z właściowściami klasy EventWaitHandle. Nie jesteśmy w stanie w 100% odtworzyć wszystkich możliwości języka Newsqueak (np. wszystkie dane są tam przekazywane przez wartość) i nie to było moim celem.

Marginalia

Ściągnij klasę Channel i przykłady użycia jako VS2005 Solution

Pierwotnie tekst opublikowano w portalu Codeguru.pl. Nie można tam edytować już opublikowanych artykułów, więc wersja, którą czytasz zawiera poprawki i uaktualnienia.

Update: Maj 2010: Mały update do artykułu na moim blogu, uaktualnienie kodu do .Net 4.0.