4. MT: Gemeinsame Ressourcen managen

MT: Gemeinsame Ressourcen managen

  • F

    Hallo,

    ich habe mehrere Threads die auf gemeinsame Ressourcen zugreifen. Ich habe das Problem mal auf den Kern heruntergebrochen:

    class SharedClass
{
private:
	WindowsMutex _mutex;

public:
	int volatile num;

	bool InvokeOwnership()	{ return this->_mutex.TryLock(); }
	void ReleaseOwnership() { this->_mutex.Unlock(); }
};

SharedClass arr[10];

unsigned __stdcall ThreadProc(void*)
{	
	for( int i = 0; i < 100; ++i )
	{
		int r = rand() % 20 + 1;
		int j = 0;
		while( j < 10 )
		{
			if( arr[j].num == r )
				break;
			++j;
		}

		if( j == 10 )
		{
			j = 0;
			while( !arr[j].InvokeOwnership() ) ++j;
			arr[j].num = r;
			arr[j].ReleaseOwnership();
		}
	}
	_endthreadex(0);
	return 0;
}

    Das Problem wird schnell klar. Sollten zwei Threads die selbe Nummer zur gleichen Zeit suchen, kann es passieren, dass beide denken, die Nummer würde noch nicht existieren. Sie legen dann beide an Position 0 und 1 des Arrays ihre Nummer an. Das darf nicht passieren 😃

    Hat jemand eine Idee?

    EIDT:
    Das wäre die letzte Lösung:

    unsigned __stdcall ThreadProc(void*)
{	
	static WindowsMutex lock;
	for( int i = 0; i < 100; ++i )
	{
		int r = rand() % 20 + 1;
		int j = 0;

		lock.Lock();
		while( j < 10 )
		{
			if( arr[j].num == r )
				break;
			++j;
		}

		arr[0].num = r;
		lock.Unlock();
	}
	_endthreadex(0);
	return 0;	
}

    EDIT2:
    Okay, ehrlich gesagt, fällt mir keine andere Möglichkeit ein ... Was wohl daran liegt, dass es keine gibt

    0
  • Mod

    Es geht:
    - Wenn ein Thread beginnt zu suchen, dann holt er sich eine Status Nummer aus einem Feld (atomare Operation)
    - Der Thread sucht nun in dem Array.
    - Findet er die Daten nicht, dann lockt er die gemeinsamen Daten.
    - Nachdem er die Daten gelockt hat prüft er ob die Statusnummer immer noch identisch ist mit der Nummer, die zu Anfang bezogen hat.
    - Ist die nummer nicht identisch, entsperrt er die Ressource und beginnt bei Schritt 1.
    - ist die Nummer identisch trägt er die neue Zahl in den Array ein und inkrementiert die Status Nummer (atomare Operation).
    - Nun gibt er den gesperrten Array wieder frei.

    Durch die Status Nummer merkt ein Thread ob in der Zwischenzeit der Zustand des Arrays sich verändert hat.

    Anmerkung:
    Ich glaube allerdings, dass eine Multithreading Variante wie Du sie hier bastelst weitaus schlechter laufen muss als eine single Threaded Variante, die einen set verwendet für die Prüfung. Alleine, dass bei jeder Prüfung der Array mit n Elementn durchlaufen wird ist schlecht.

    BTW: Ich hoffe Dein WindowMutex ist eine Critical Section und kein Mutex!

    0
  • F

    Martin Richter schrieb:

    BTW: Ich hoffe Dein WindowMutex ist eine Critical Section und kein Mutex!

    Natürlich 😉

    Das Beispiel sollte nur das Problem hervorheben. Mein Programm ist dann doch etwas umfangreicher 😉

    Die entsprechende Funktion wird nur in unregelmäßigen Abständen aufgerufen. Ansonsten arbeiten die Threads unabhängig von gemeinsamen Ressourcen.

    0

  • @Martin Richter:
    Ich würde hier keinen "wait-free" (oder "fast" wait-free) Algorithmus verwenden, sondern ganz klassisch die Mutex sperren, dann suchen, dann ggf. einfügen, dann entsperren.

    @FrEEzE2046:
    Tu dir selbst und uns einen gefallen, und versuch keine neuen Begriffe zu erfinden. Oft genug machen die dann für keinen ausser dir Sinn. InvokeOwnership/ReleaseOwnership ... nie gehört, verwendet keiner, versteht keiner.
    Was stört dich an Lock/Unlock?

    Und nochwas: du wirst wohl kaum *genau das* in deinem Programm machen wollen, oder? Und vielleicht lässt sich das echte Problem ja eleganter lösen...

    0
  • Mod

    hustbaer schrieb:

    @Martin Richter:
    Ich würde hier keinen "wait-free" (oder "fast" wait-free) Algorithmus verwenden, sondern ganz klassisch die Mutex sperren, dann suchen, dann ggf. einfügen, dann entsperren.

    Wenn oft gesuchtwird und selten eingefügt wird, würde ich so vorgehenwie beschrieben. Hängt von der Quote ab...
    Man kann ja auch realtiv die einfach die Komplexität errechnen.

    Wenn man immer sperrt hat man bei extrem häufiger Suche evtl. Nachteile bei mehreren Threads, abr da erzähle ich Dir vermutlich nichts neues... 😉

    0

  • Nö, nix neues. Und du hast natürlich Recht.

    Ich meine nur klassische lock/unlock Varianten sind einfacher zu programmiere. Vor allem ist die Chance viel höher dass man sie auch wirklich fehlerfrei hinbekommt.
    Da es in den meisten Fällen vollkommen schnuppe ist, da der engste Flaschenhals meist ganz wo anders liegt, tu ich mir das aber nimmer an. Ist meiner Meinung nach verschwendete Zeit.

    (Ausser natürlich man hat einen dieser seltenen Fälle wo doch der Flaschenhals Lock-Contention ist. Und dann würde es mir auch Spass machen nen passenden schnellen wait-free/lock-free Algorithmus zu suchen/erfinden/implementieren.)

    0
Anmelden zum Antworten