logo elektroda
logo elektroda
X
logo elektroda
REKLAMA
REKLAMA
Adblock/uBlockOrigin/AdGuard mogą powodować znikanie niektórych postów z powodu nowej reguły.

[C++/Thread] Równoległe obliczenia a problem synchronizacji

eruanno 27 Mar 2009 19:16 4026 3
REKLAMA
  • #1 6341204
    eruanno
    Poziom 10  
    Posty: 6
    Ocena: 2
    Witam!

    Ostatnio napisałem program do pewnych symulacji fizycznych. Jak to bywa w tego typu programach, potrzebna jest duża moc obliczeniowa. Ponieważ dotychczas obliczeniami zajmował się jeden rdzeń procesora (posiadam dwurdzeniowy), postanowiłem sprawdzić jaki będzie wzrost wydajności, jeśli podzielę obliczenia na dwa równoległe wątki.
    Powiedzmy, że tworzenie wątków oraz ogólna idea semaforów i mutexów nie jest mi obca. Problem niestety mam we właściwym zastosowaniu tych mechanizmów, aby obliczenia przebiegały w sposób sensowny i zsynchronizowany. Ma to wyglądać mniej więcej tak:

    
    int independent1(void* data)
    {
    	while(1)
    	{
    		SDL_Delay(rand()%1500 + 500);		// Bardzo długie obliczenia ;)
    		printf("Thread 1: Wykonano obliczenia.\n");
    	}
    }
    
    int independent2(void* data)
    {
    	while(1)
    	{
    		SDL_Delay(rand()%1500 + 500);
    		printf("Thread 2: Wykonano obliczenia.\n");
    	}
    }
    
    int main(int argc, char *argv[])
    	{
    	...
    	/* Mniej wazne sprawy, tj. tworzenie watkow itp. */
    	...
    
    	while(!jakis_warunek)
    	{
    		OdrysowanieWynikowObliczen();
    	}
    }
    


    Wątek główny (funkcja main) zajmuje się jedynie odrysowaniem danego stanu, przy czym może to zrobić tylko po zakończeniu cyklu obliczeń przez independentx. Jeśli nie może, to czeka nie marnując zasobów. Obliczenia mogą się ciągnąć wieki lub wykonywać błyskawicznie - tak czy siak wątek, który skończy wcześniej nie może przejść do następnego etapu obliczeń, dopóki drugi też nie skończy tego samego etapu. Na wyjściu w konsoli dla powyższego przykładu chciałbym otrzymać np. coś takiego:
    
    Thread 1: Wykonano obliczenia.
    Thread 2: Wykonano obliczenia.
    Odrysowano ekran!
    Thread 1: Wykonano obliczenia.
    Thread 2: Wykonano obliczenia.
    Odrysowano ekran!
    Thread 2: Wykonano obliczenia.
    Thread 1: Wykonano obliczenia.
    Odrysowano ekran!
    Thread 1: Wykonano obliczenia.
    Thread 2: Wykonano obliczenia.
    Odrysowano ekran!
    


    Próbowałem na różne sposoby stosować semafory bądź mutexy, ale zawsze kończyło się to albo deadlockiem, albo wątki się rozbiegały w obliczeniach. Może mi ktoś pomóc, jak rozmieścić te "waity i posty", żeby wszystko działało jak należy?
  • REKLAMA
  • #2 6341356
    Dżyszla
    Poziom 42  
    Posty: 7077
    Pomógł: 1095
    Ocena: 226
    Jeśli oba wątki pracują na różnych danych (to znaczy nie są od siebie wzajemne zależne) to do osiągnięcia takiego rezultatu:
    w wątku głównym ustawiasz dwa semafory
    czekasz na ich zwolnienie
    w wątkach potomnych na ich końcu zwalniasz odpowiednie im semafory (najlepiej przekazać je jako parametry lub poprzez zmienne globalne).

    BTW - dwuwątkowa praca wcale nie będzie oznaczać, że wykorzystane zostaną dwa rdzenie ;) Ot, taka uroda procesorów wielordzeniowych i systemów Windosowskich.

    Aha - nie polecam, aby oba wątki miały dostęp do pisania po konsoli! Lepiej zrealizować to w wątku głównym (przy czym tu niemożliwe stanie się zachowanie kolejności), lub wykonać rysowanie w sekcji krytycznej.
  • REKLAMA
  • #3 6341359
    BoskiDialer
    Poziom 34  
    Posty: 1530
    Pomógł: 353
    Ocena: 42
    Pierwszy pomysł: mutex'em chronić dostęp do jakiegoś licznika, który informował by ile wątków skończyło obliczenia. Po zakończeniu obliczeń wątek główny wykryje, że licznik ma wartość równą liczbie wątków czyli obliczenia się zakończyły

    Drugi pomysł: bez semaforów i muteksów. Dla każdego wątku przydzielić jeden bajt dostępny z poziomu wątku obliczeniowego jak i wątku głównego. Jeśli dany bajt jest równy 1, to znaczy wątek liczy. Pod koniec wątek zeruje ten bajt i przed rozpoczęciem kolejnych obliczeń czeka na ponowne ustawienie bajtu. Wątek główny czeka na wyzerowanie znaczników od wszystkich wątków, po czym ponownie ustawia wszystkie bajty wznawiając obliczenia.

    Trzeci pomysł: Zrobić listę zadań do wykonania. Każdy wątek w sekcji krytycznej wyciąga jedno zadanie z listy, zwalnia sekcję po czym realizuje zadanie. Pod koniec może zostać zwiększony jakiś licznik ile zadań już policzono. Plusem tego rozwiązania jest, że jeśli jeden wątek skończy wcześniej, to może zabrać się za kolejne zadania. Wątków może być tyle ile procesorów, zawsze wszystkie będą zajęte liczeniem, jeśli tylko będzie dość zadań w kolejce.

    Jest też kilka innych rozwiązań, jednak spróbuj najpierw samemu zaimplementować którekolwiek z tych rozwiązań.
  • #4 6341640
    Akane
    Poziom 27  
    Posty: 638
    Pomógł: 144
    Ocena: 33
    Jeżeli oba wątki po zakończeniu obliczeń kończą działanie, to uchwyt do nich zmienia stan na 'signalled', co możesz użyć w funkcji WaitForMultipleObjects z bWaitAll=TRUE.
    Oczywiście nie znam Twoich założeń co do tego jak wszystko razem ma działać, ale to jest jeden z przykładów, gdzie całą pracę z góry dzieli się na dwie niezależne połowy obliczane w osobnych wątkach, a gdy cała praca zostanie wykonana to coś się dzieje.

    Jeżeli zadanie można podzielić na wiele równoległych etapów, to należy uruchomić tyle wątków ile jest rdzeni, a każdy z nich oczekuje na polecenia i zgłasza zakończenie zadania np. ustawiając hEvent. Pętla zarządzająca wątkami wg. jakiegoś algorytmu przydziela pracę wątkom które nie mają co robić i jeżeli wszystkie wątki są już zajęte pracą lub nie da się zacząć pracy bez wyniku, to pętla oczekuje na wynik funkcją WaitForMultipleObjects.
    Dla każdego wątku tworzysz event (CreateEvent) i udostępniasz jego uchwyt wątkowi. Wątek na samym początku wchodzi w nieskończoną pętlę z funkcją GetMessage lub oczekując na zasygnalizowanie jednego z dwóch eventów: oblicz/wyłącz_się. Dane przekazuj przez void* data, tylko zmień typ na jakąś swoją strukturę w której będą wszystkie eventy i rozkazy do wykonania.
    Przykładowo:
    struct THREAD_COMMANDSET
    {
    	int status;        // opcjonalnie
    	HANDLE hThread;
    	HANDLE hQuitEvent;
    	HANDLE hCalculateEvent;
    	HANDLE hIdleEvent;
    	// tutaj rozkazy do wykonania i wynik
    }
    
    DWORD ThreadProc(THREAD_COMMANDSET *data)
    {
    	// zgłoś gotowość
    	data->status = STATUS_IDLE;
    	SetEvent(data->hIdleEvent);
    
    	HANDLE array[2] = {data->hQuitEvent, data->hCalculateEvent;};
    	while (1)
    	{
    		DWORD index = WaitForMultipleObjects(2, array, FALSE, INFINITE);
    
    		if (index == 0) // hQuitEvent
    		{
    			// zakończ wątek
    			break;
    		}
    		else if (index == 1) // hCalculateEvent
    		{
    			// 1. oblicz dane
    			data->status = STATUS_BUSY;
    			// 2. zgłoś gotowość
    			data->status = STATUS_WYNIK;
    			SetEvent(data->hIdleEvent);
    		}
    	}
    	return 0;
    }

    Wiedząc że masz dwa rdzenie, alokujesz dwie struktury THREAD_COMMANDSET jako tablicę, wpisujesz do nich eventy i na końcu tworzysz wątki. Wchodzisz do głównej pętli wiedząc że nie możesz na razie przydzielić żadnej pracy, wiec wszystkie .hIdleEvent kopiujesz do innej tablicy i używasz jej w funkcji WaitForMultipleObjects(bWaitAll=FALSE). Funkcja ta zwróci indeks wątku który zgłosił gotowość, więc jemu przydzielasz część pracy kopiując odpowiednie dane do THREAD_COMMANDSET, oraz ustawiając event hCalculateEvent funkcją SetEvent.
    Mniej więcej będzie to wyglądało tak:
    THREAD_COMMANDSET *watki = new THREAD_COMMANDSET[ilosc_rdzeni];
    // eventy
    for (int a=0; a<ilosc_rdzeni; a++)
    {
    	watki[a].hQuitEvent = CreateEvent(0,0,0,0);
    	watki[a].hCalculateEvent = CreateEvent(0,0,0,0);
    	watki[a].hIdleEvent = CreateEvent(0,0,0,0);
    }
    // uruchom wątki
    for (int a=0; a<ilosc_rdzeni; a++)
    {
    	watki[a].hThread = CreateThread(0,0,(LPTHREAD_START_ROUTINE)ThreadProc, &watki[a], 0, &id);
    }
    
    // dodatkowa tablica do oczekiwania na gotowość dowolnego wątku
    HANDLE *hIdleArray = new HANDLE[ilosc_rdzeni];
    for (int a=0; a<ilosc_rdzeni; a++)
    {
    	hIdleArray[a] = watki[a].hIdleEvent;
    }
    
    // gówna pętla
    while (JestCosDoZrobienia())
    {
    	// czekaj na dowolny wątek
    	int nThreadIndex = WaitForMultipleObjects(ilosc_rdzeni, hIdleArray, FALSE, INFINITE);
    	if (MoznaTerazCosPoliczyc())
    	{
    		// skopiuj mu rozkazy
    		watki[nThreadIndex].xx = yy;
    		// każ mu obliczyć
    		SetEvent(watki[nThreadIndex].hCalculateEvent);
    	}
    	else
    	{
    		// czekamy na wynik z wątku x, y, z
    		#define IsIdle(index) (!WaitForSingleObject(watki[index].hIdleEvent, 0))
    		// IsIdle powinno dodatkowo sprawdzić czy jest wynik, by nie zwrócić
    		// TRUE gdy wątek poraz pierwszy zgłosi gotowość bez wykonania pracy: np. (watki[index].status == STATUS_WYNIK)
    		if (IsIdle(x) && IsIdle(y) && IsIdle(z))
    		{
    			// przetwórz wyniki (w wątku?)
    		}
    	}
    }
    // zakończ wątki
    for (int a=0; a<ilosc_rdzeni; a++)
    {
    	SetEvent(watki[a].hQuitEvent);
    	hIdleArray[a] = watki[a].hThread;
    }
    
    // czekaj aż wszystkie zakończą
    WaitForMultipleObjects(ilosc_rdzeni, hIdleArray, TRUE, INFINITE);
    
    for (int a=0; a<ilosc_rdzeni; a++)
    {
    	CloseHandle(watki[a].hQuitEvent);
    	CloseHandle(watki[a].hCalculateEvent);
    	CloseHandle(watki[a].hIdleEvent);
    	CloseHandle(watki[a].hThread);
    }
    delete hIdleArray;
    delete watki;


    Przemyśl to, pomyśl jak kierownik budowy - najpierw fundamenty, jeden wątek wydajnie produkuje beton, 3 inne go wylewają.
REKLAMA