2008-08-26:

Włókna w nici, czyli fibers vs threads.

windows:winapi:c:c++
Zainspirowany postem noglorp'a na OpenRCE zdecydowałem się pobawić w końcu fiberami pod Windowsem, i okazało się że to całkiem interesujący temat.

Czym więc jest fiber? Otóż można napisać że fiber (dosłowne tłumaczenie - włókno) jest rodzajem wątku (czyli jednostki wykonania w procesach). Czym się więc różni fiber od normalnego threada? Otóż różnica leży w schedulerze (planiście) - planista odpowiedzialny za wątki jest umieszczony w kernelu systemu, i przełącza wątki w niewidoczny dla programisty sposób, oraz kiedy sam tego chce (z dokładnością do poproszenia przez programistę o wywłaszczenie wątku - Sleep(0) czy SwitchToThread(), czy funkcji które blokują program). Natomiast planistę fiberów programista musi (może?) stworzyć sam (tzn nie ma żadnego kernel-level schedulera który po cichu "krąży" między fiberami). W tym celu programista dostaje od WinAPI kilka bardzo prostych i intuicyjnych funkcji:
SwitchToFiber(void *pFiber) - przejście z obecnie wykonywanego fibera do podanego fibera (należy zauważyć że używając SwitchToThread nie możemy określić który wątek ma się wykonać, natomiast SwitchToFiber wymaga podania włókna które ma być dalej wykonywane).
ConvertThreadToFiber(void *pParam) - skonwertowanie wątku na fiber, a tak na prawdę to przystosowanie wątku do przełączania się między fiberami.

Dodatkowo do definiowania nowych fiberów dostajemy funkcję:
CreateFiber - która służy do stworzenia nowego fibera, jednak w przeciwieństwie do CreateThread, nowo utworzony fiber nie zaczyna od razu wykonywać podanej mu funkcji - określenie kiedy fiber ma rozpocząć działanie należy w końcu do stworzonego przez programisty schedulera (choćby ograniczającego się do pojedynczego SwitchToFiber).

Jest jeszcze kilka funkcji, ale powyższe w zupełności wystarczą.

Patrząc z punktu logicznego, należy stworzyć kilka fiberów (CreateFiber) i oczywiście zapamiętać ich uchwyty (wartość zwracana przez CreateFiber). Następnie należy skonwertować wątek który chcemy przeznaczyć na wykonywanie fiberów do fibera (ConvertThreadToFiber), a potem za pomocą SwitchToFiber przełączać się między fiberami (w ramach tego jednego wątku). Czyli w sumie można powiedzieć że fibery stają się unitami wykonującymi wewnątrz jednego threada, przy czym nigdy nie działa naraz więcej niż jeden fiber (oczywiście konwertując więcej threadów na fibery można sprawić że kilka fiberów będzie się wykonywało naraz).

Jak zrobić prosty scheduler? Osobiście dla testów stworzyłem 4 fibery pracujące, oraz jeden fiber-scheduler. Po konwersji wątku przełączyłem go (wątek) na fiber-scheduler, który był po prostu pętlą która przełączała się na kolejne fibery. Należy w tym miejscu zaznaczyć że SwitchToFiber powoduje dokładne zapamiętanie miejsca wykonania w starym "włóknie", i w momencie gdy wykonanie powróci do tego fibera (czyli inny fiber zrobi SwitchToFiber do niego) wykonanie wznowi się DOKŁADNIE w tym miejscu w którym zostało przerwane. Tak więc fibery pracujące wykonywały kawałek zadania, a następnie za pomocą SwitchToFiber przełączały się z powrotem do fiber-schedulera, który z kolei przełączał się do kolejnego fiberu. I tak aż wszystkie zadania zostały wykonane.

Kod wyglądał mniej więcej tak (pełna wersja kodu jest na dolę postu do ściągnięcia):

Najpierw kilka deklaracji:
#define FIBER_COUNT 4

LPVOID FiberScheduler;
LPVOID Fibers[FIBER_COUNT];
int    FiberDone[FIBER_COUNT];


Następnie funkcje robiące cokolwiek - wykonywane przez worker-fibery:
void __stdcall MyFiber(void* Param)
{
 int i;
 int FiberNr = (int)Param;
 printf("%i: start\n", FiberNr);

 for(i = 0; i < 5; i++)
 {
   // Do something
   printf("%i: in loop %i, before switch\n", FiberNr, i);
   // Go back to scheduler
   SwitchToFiber(FiberScheduler);
   // Do something again
   printf("%i: in loop %i, back from switch\n", FiberNr, i);
 }

 // End of work
 printf("%i: done\n", FiberNr); fflush(stdout);
 FiberDone[FiberNr] = 1;

 // Back to scheduler
 SwitchToFiber(FiberScheduler);
}


Powyższa funkcja wykonuje po prostu 5 iteracji prostej pętli, i co iterację wraca do schedulera.
Czas na samego schedulera:

void __stdcall MyScheduler(void *Param)
{
 int i;
 int CurrentFiber = -1;
 puts("S: start");

 while(1)
 {
   int DoneCount = 0;
   puts("S: schedule loop begining");

   // Check if all done
   for(i = 0; i < FIBER_COUNT; i++)
     DoneCount += FiberDone[i];

   if(DoneCount == FIBER_COUNT)
     break;

   // Switch to next av. fiber
   // There has to be at least one
   do
   {
     CurrentFiber++;
     if(CurrentFiber == FIBER_COUNT)
       CurrentFiber = 0;
   }
   while(FiberDone[CurrentFiber]);

   // Switch to it
   printf("S: schedule loop switching to fiber %i\n", CurrentFiber);
   SwitchToFiber(Fibers[CurrentFiber]);
   printf("S: schedule loop back from fiber %i\n", CurrentFiber);
 }

 puts("S: done");
}


Jak widać kod jest raczej prosty - cały planista jest w pętli, która przerywa się dopiero gdy wszystkie fibery wykonają swoje zadania (co jest sprawdzane na początku pętli). W pętli jest na dobrą sprawę tylko w/w sprawdzanie stanu fiberów, wybieranie kolejnego nie-zakończonego fibera, oraz przełączenie się do niego. Po powrocie z worker-fibera kod wykonuje się dalej od miejsca przełączenia, czyli leci kolejny "obrót" pętli, i tak aż wszystkie włókna wykonają swoje zadania.
Wykonanie wątku tego typu wygląda tak: ConvertThreadToFiber -> SwitchToFiber(FiberScheduler) -> SwitchToFiber(Fiber[0]) -> SwitchToFiber(FiberScheduler) -> SwitchToFiber(Fiber[1]) -> SwitchToFiber(FiberScheduler) -> ...

Co ciekawe, planista wcale nie musi mieć oddzielnego fibera - można go zintegrować z worker-fiberami tak aby zrobić coś na zasadzie zapętlonej linked listy - każdy fiber wie który fiber jest "następny" w kolejce do wywołania, i robi po prostu SwitchToFiber(NextFiber).

Oczywiście fibery nie muszą udawać wątków (emulacja wywłaszczania, zmienianie zadań w trakcie wykonania, etc), mogą być zorientowane czysto zadaniowo - każdy fiber wykonywał by się od początku do końca, a następnie przełączał by się na scheduler, który wybierał by kolejne zadanie. Brzmi nawet użytecznie.

A teraz rzut okiem na temat od innej strony. Jak to wszystko działa? Po chwili zastanowienia można dość do całkiem słusznego wniosku że dość prosto. Sam fiber może być opisany przez prostą strukturę ze stanami rejestrów (ogólne, flagi, oraz rejestry koprocesora, i rozszerzeń (choć to prawie to samo ;>)), adresem EIP od którego należy kontynuować wykonanie, oraz danymi o zarezerwowanej na potrzeby fibera fragmentami pamięci (np. o stosie - każdy fiber ma własny stos). Mając taką strukturę sam SwitchToFiber jest banalny do napisania (zachowanie wartości rejestrów, wczytanie wartości rejestrów następnego fibera, i skok do jego EIP) i może działać całkowicie w user mode. Idąc dalej tym tropem - CreateFiber to na dobrą sprawę alokacja pamięci + drobne setupy, a więc to też można spokojnie w user mode sobie zrobić, a ConvertThreadToFiber dużo od CreateFiber się nie różni. Więc tak na prawdę cały mechanizm fiberów wydaje się być bardzo prosty, i w cale nie wymagający użycia Fiber API (niemniej jednak bardzo dobrze że taki API jest).

Czy fibery są tak na prawdę użyteczne? Szczerze to trudno powiedzieć, nie przychodzi mi nic do głowy gdzie użycie fiberów było by lepiej uzasadnione niż jakiejś innej metody. Natomiast nie przychodzą mi do głowy również żadne przeciwwskazania mówiące że włókien nie powinno się używać. Przypuszczam że w jakimś daemonie o strikte zadaniowym trybie pracy fiberki mogłyby być całkiem użyteczne. W przypadku interpreterów/maszyn wirtualnych również widzę parę zastosowań - np. multithreading w VM obsługiwany w połowie przez wątki, a w połowie przez fibery - kilkadziesiąt fiberów chodzące wewnątrz kilku wątków. Należy zaznaczyć iż fibery mają w takim wypadku bardzo ważną zaletę - mają własny stos, i jak coś namiesza na stosie, to inne fibery pozostaną nietknięte.

Moim zdaniem fibery są całkiem ciekawe, i można nawet je gdzieś wepchnąć, byle nie na siłę. Jeżeli przyjdzie mi do głowy jakieś sensowne zastosowanie, to dam znać ;>
Dodam że w przypadku Linuxa wbudowanego wsparcia dla "włókien" nie widziałem, natomiast google wyrzuciło kilka libów do fiberów (choć głowy nie dam czy to te same fiberki).

OK, tyle na dziś.

fibers.cpp (3kb)

UPDATE 2009-03-10: Od darkjames'a (thx!) otrzymałem linka do świetnego wykładu (EN) o fiberkach (slajdy też są dostępne): Tango conference 2008 - Fibers talk by Mikola Lysenko

Add a comment:

Nick:
URL (optional):
Math captcha: 10 ∗ 4 + 7 =