synchronization problem



  • hi,

    ich habe 3 taks: T1, T2, T3 and 2 reourcen: R1, R2.

    resource R1 wird geshared mit T1, T2, T3 und resource R2 wird geshared mit T2, T3.

    wie kann ich das synchronizieren ohne einem deadlock?



  • Prinzipiell die Ressourcen nicht gleichzeitg locken (also innerhalb des Threads). Falls es doch sein muss, penibel auf die Lock-Reihenfolge in den kritischen Codes achten und solche Situationen möglichst minimieren.



  • @Jodocus: wie lockt man dann hier in diesem beispiel?

    mein ansatz:

    std::mutex m1;
    std::mutex m2;
    
    void Task1() {
      unique_lock<mutex> l(m1);
        access_R1
    }
    
    void Task2() {
      {
      unique_lock<mutex> l(m1);
        access_R1
      }
    
      {
      unique_lock<mutex> l(m2);
        access_R2
      }
    }
    
    void Task3() {
      {
      unique_lock<mutex> l(m1);
        access_R1
      }
    
      {
      unique_lock<mutex> l(m2);
        access_R2
      }
    }
    


  • Bei diesem Code dürfte nichts passieren, denn du lockst innerhalb eines Threads/Tasks nicht zwei Mutexe gleichzeitig. Erst, wenn du das tust (was man, wie gesagt, am besten vermeiden sollte, wenn es geht), musst du höllisch aufpassen, dass du Mutexe immer in der gleichen Reihenfolge lockst, in jedem Task. Deshalb sollte man solche Zugriffe auf wenigen, zentralen Code reduzieren, wenn es geht. Nur so kannst du garantieren, dass keine Deadlocks auftauchen.



  • kann man den aktuellen code noch verbessern? wenn task1 resource 1 hat, dann kann ja task2 oder task3 resource 2 bekommen und muss nicht warten bis task1 fertig ist...?



  • Wenn die einzelnen Algorithmen voneinander unabhängig sind, kannst du das natürlich machen, z.B. mit try_lock.



  • @Jodocus ich habe mal ein beispiel zusammen gebastelt...meisnt du das so?

    #include <iostream>
    #include <thread>
    #include <mutex>
    #include <condition_variable>
    #include <vector>
    #include <algorithm>
    #include <cassert>
    using namespace std;
    
    class SynchronizationTest {
    private:
    	mutex lock_r1;
    	mutex lock_r2;
    	vector<pair<string, int>> buffer_r1;
    	vector<pair<string, int>> buffer_r2;
    	int buffer_r1_max_size;
    	int buffer_r2_max_size;
    
    	bool buffer_r1_inc_element(const string &thread_id) {
    		if (buffer_r1.size() == buffer_r1_max_size) {
    			return true;
    		}
    
    		if (buffer_r1.size() == 0) {
    			buffer_r1.push_back(make_pair(thread_id, 0));
    		}
    		else {
    			int last_val = buffer_r1.back().second;
    			buffer_r1.push_back(make_pair(thread_id, ++last_val));
    		}
    
    		return false;
    	}
    
    	bool buffer_r2_inc_element(const string &thread_id) {
    		if (buffer_r2.size() == buffer_r2_max_size) {
    			return true;
    		}
    
    		if (buffer_r2.size() == 0) {
    			buffer_r2.push_back(make_pair(thread_id, 0));
    		}
    		else {
    			int last_val = buffer_r2.back().second;
    			buffer_r2.push_back(make_pair(thread_id, ++last_val));
    		}
    
    		return false;
    	}
    
    public:
    	SynchronizationTest(int buff_r1_size, int buff_r2_size) : buffer_r1_max_size(buff_r1_size),
                                                                  buffer_r2_max_size(buff_r2_size) {}
    
    	void thread1() {
    		bool buffer_r1_full = false;
    
    		while (!buffer_r1_full) {
    			{
    				unique_lock<mutex> l(lock_r1, std::defer_lock);
    				if (l.try_lock()) {
    					buffer_r1_full = buffer_r1_inc_element("thread1");
    				}
    			}
    
    			std::this_thread::sleep_for(std::chrono::milliseconds(10));
    		}
    	}
    
    	void thread2() {
    		bool buffer_r1_full = false;
    		bool buffer_r2_full = false;
    
    		while (!buffer_r1_full || !buffer_r2_full) {
    			if (!buffer_r1_full) {
    				unique_lock<mutex> l(lock_r1, std::defer_lock);
    				if (l.try_lock()) {
    					buffer_r1_full = buffer_r1_inc_element("thread2");
    				}
    			}
    
    			if (!buffer_r2_full) {
    				unique_lock<mutex> l(lock_r2, std::defer_lock);
    				if (l.try_lock()) {
    					buffer_r2_full = buffer_r2_inc_element("thread2");
    				}
    			}
    
    			std::this_thread::sleep_for(std::chrono::milliseconds(10));
    		}
    	}
    
    	void thread3() {
    		bool buffer_r1_full = false;
    		bool buffer_r2_full = false;
    
    		while (!buffer_r1_full || !buffer_r2_full) {
    			if (!buffer_r1_full) {
    				unique_lock<mutex> l(lock_r1, std::defer_lock);
    				if (l.try_lock()) {
    					buffer_r1_full = buffer_r1_inc_element("thread3");
    				}
    			}
    
    			if (!buffer_r2_full) {
    				unique_lock<mutex> l(lock_r2, std::defer_lock);
    				if (l.try_lock()) {
    					buffer_r2_full = buffer_r2_inc_element("thread3");
    				}
    			}
    
    			std::this_thread::sleep_for(std::chrono::milliseconds(10));
    		}
    	}
    
    	void print_buffer() {
    		for_each(buffer_r1.begin(), buffer_r1.end(), [](pair<string, int> p) { cout << p.first.c_str() << " " << p.second << endl; });
    		cout << '\n';
    		for_each(buffer_r2.begin(), buffer_r2.end(), [](pair<string, int> p) { cout << p.first.c_str() << " " << p.second << endl; });
    	}
    };
    
    int main() {
    	// your code goes here
    	SynchronizationTest st(20, 20);
    
    	thread t1(&SynchronizationTest::thread1, &st);
    	thread t2(&SynchronizationTest::thread2, &st);
    	thread t3(&SynchronizationTest::thread3, &st);
    
    	t1.join();
    	t2.join();
    	t3.join();
    
    	st.print_buffer();
    
    	return 0;
    }
    


  • Die eigentliche Implementation haengt vom Problem ab. Aktives Warten oder die Nutzung von sleep will man aber im Allgemeinen vermeiden. Deswegen ist deine Umsetzung als eher schlecht einzustufen. Genau wie bei anderen Problemen gibt es im Bereich paralleler Datenverarbeitung auch Muster, z.B. Producer-Consumer, Pipeline, ... Es hilft diese zu kennen. 🙂 Darueber hinaus gibt es weitere Sychronisationsprimitive wie condition variables oder Semaphore. Es hilft diese zu kennen. Darueber hinaus gibt es weitere Probleme bei Multithreading, z.B. Starvation oder Live-Lock. Es hilft ...



  • Abgesehen von der schon genannten Tatsache, dass du Threads schlafen legst (Task 1 könnte doch einfach so lange blockieren, bis er Zugriff bekommt, was anderes kann er in der Zeit eh nicht machen) und viel vermeidbare Codeverdoppelung hast hier mein Tipp:

    Ich meinte, du sollst std::try_lock (also die Funktion) benutzen. Mit der versuchst du mehrere Locks zu locken und bekommst den Index zurück, bei dem ein Lock nicht geklappt hat oder -1. Dann kannst du automatisch je nach Rückgabewert entscheiden, auf welche Resource du zugreifen kannst (oder sogar auf beide), anstatt das selber mit Locks und Sleeps hinzufrickeln. std::try_lock ist garantiert dead_lock-sicher (solange du mit std::unique_locks auf defer_lock und nicht mit reinen Mutexen damit arbeitest).



  • Jodocus schrieb:

    Prinzipiell die Ressourcen nicht gleichzeitg locken (also innerhalb des Threads). Falls es doch sein muss, penibel auf die Lock-Reihenfolge in den kritischen Codes achten und solche Situationen möglichst minimieren.

    Glücklicherweise stellt der Standard hier die freie Funktion std::lock zur Verfügung. Ein Thread der mehrere Mutexe gleichzeitig hält, sollte diese immer auf einen Schlag mit std::lock locken, um Lock-Order Problemen aus dem Weg zu gehen.

    Das Beispiel auf der Seite ist etwas unglücklich, weil es die Mutexe direkt lockt und freigibt. Im wirklichen Leben willst du nach dem Aufruf von std::lock die Ownership für den Lock an eine RAII Klasse wie std::lock_guard (mittels std::adopt_lock) abtreten. Diese Seite hat ein besseres Beispiel.



  • Desdemona schrieb:

    Jodocus schrieb:

    Prinzipiell die Ressourcen nicht gleichzeitg locken (also innerhalb des Threads). Falls es doch sein muss, penibel auf die Lock-Reihenfolge in den kritischen Codes achten und solche Situationen möglichst minimieren.

    Glücklicherweise stellt der Standard hier die freie Funktion std::lock zur Verfügung.

    Das habe ich alles in meinem letzten Beitrag schon erwähnt. Aber Wiederholung ist natürlicher einprägsamer.

    Desdemona schrieb:

    Ein Thread der mehrere Mutexe gleichzeitig hält, sollte diese immer auf einen Schlag mit std::lock locken, um Lock-Order Problemen aus dem Weg zu gehen.

    Und an der Stelle kann man auf knivils Beitrag hinweisen: std::lock ist kein Allheilmittel für jedes Mehrfach-Lock-Problem. Ich muss an bestimmten Stellen im Algorithmus z.B. garnicht Ressource B besitzen, sondern nur Resource A. Erst später brauche ich Ressource B, muss aber Ressource A im definierten Zustand halten während ich mit B arbeite und schon ist std::lock keine Option mehr, es sei denn, man lockt sinnlos Ressourcen. In dem Fall muss man sich mit hierachischen Mutexen o.a. Optionen beschäftigen.

    Wie knivil schon sagte:

    knivil schrieb:

    Die eigentliche Implementation haengt vom Problem ab.

    Multithreading ist nun mal nicht leicht.



  • Ein Werkzeug wie std::lock, mit dem man mehrere Mutexen auf einmal locken kann ist nett, aber wie Jodocus schon geschrieben hat nicht überall anwendbar.
    Ich würde sogar noch einen Schritt weiter gehen, und sagen: nur sehr begrenzt anwendbar.

    Fälle wo ein Thread mehrere Mutexen hält, und man auch nicht std::lock verwenden kann, hat man *andauernd*. Viele davon sind aber relativ trivial. Nämlich wenn sich "auf ganz natürliche Art und Weise" eine klare Reihenfolge ergibt in der gelockt wird.

    Jeder der schon etwas mehr mit SMP gemacht hat wird wohl wissen was ich meine. Und da es nicht leicht zu erklären ist, und ich grad nicht viel Zeit habe, belasse ich es mal damit.
    Nur soviel: man muss halt aufpassen wenn man Aufrufe macht die in der "high-level <-> low-level" Hierarchie nicht klar nach "unten gehen". Also z.B. nach oben (was man aber eh nie haben sollte), nach unbekannt (wie bei Callbacks - die dann natürlich "nach oben" verdrahtet sein dürfen) oder "sideways" (also z.B. wenn man ne Memberfunktion der eigenen Klasse auf einer anderen Instanz aufruft).



  • hi, ich habe meinen code umgeschrieben und nutze nun try_lock...warum gibt es hier einen deadlock?

    #include <iostream> 
    #include <thread> 
    #include <mutex> 
    #include <condition_variable> 
    #include <vector> 
    #include <algorithm> 
    #include <cassert> 
    using namespace std; 
    
    class SynchronizationTest { 
    private: 
        mutex lock_r1; 
        mutex lock_r2; 
        vector<pair<string, int>> buffer_r1; 
        vector<pair<string, int>> buffer_r2; 
        unsigned int buffer_r1_max_size; 
        unsigned int buffer_r2_max_size; 
    
        bool buffer_r1_inc_element(const string &thread_id) {       
            if (buffer_r1.size() == buffer_r1_max_size) { 
                return true;
            } 
    
            if (buffer_r1.size() == 0) { 
                buffer_r1.push_back(make_pair(thread_id, 0)); 
            } 
            else { 
                int last_val = buffer_r1.back().second; 
                buffer_r1.push_back(make_pair(thread_id, ++last_val)); 
            } 
    
            return false;
        } 
    
        bool buffer_r2_inc_element(const string &thread_id) {  
            if (buffer_r2.size() == buffer_r2_max_size) { 
                return true;
            } 
    
            if (buffer_r2.size() == 0) { 
                buffer_r2.push_back(make_pair(thread_id, 0)); 
            } 
            else { 
                int last_val = buffer_r2.back().second; 
                buffer_r2.push_back(make_pair(thread_id, ++last_val)); 
            } 
    
            return false;
        } 
    
    public: 
        SynchronizationTest(int buff_r1_size, int buff_r2_size) : buffer_r1_max_size(buff_r1_size), 
                                                                  buffer_r2_max_size(buff_r2_size) {} 
    
        void thread1() { 
            bool buffer_r1_full = false; 
    
            while (!buffer_r1_full) { 
                { 
                    unique_lock<mutex> l(lock_r1, std::defer_lock); 
                    if (l.try_lock()) { 
                        buffer_r1_full = buffer_r1_inc_element("thread1"); 
                    } 
                } 
    
                std::this_thread::sleep_for(std::chrono::milliseconds(10)); 
            } 
        } 
    
        void thread2() { 
            bool buffer_r1_full = false; 
            bool buffer_r2_full = false; 
    
            while (!buffer_r1_full || !buffer_r2_full) {
                {
                    unique_lock<mutex> lock1(lock_r1, defer_lock);
                    unique_lock<mutex> lock2(lock_r2, defer_lock);
    
                    int result = try_lock(lock1, lock2);
                    if(result == -1) {
                        buffer_r1_full = buffer_r1_inc_element("thread2");
                        buffer_r2_full = buffer_r2_inc_element("thread2");
                    }
                    else if(result != 0) { 
                        buffer_r1_full = buffer_r1_inc_element("thread2");
                    }
                    else if(result != 1) { 
                        buffer_r2_full = buffer_r2_inc_element("thread2");
                    }
                }
    
                std::this_thread::sleep_for(std::chrono::milliseconds(10)); 
            } 
        } 
    
        void thread3() { 
            bool buffer_r1_full = false; 
            bool buffer_r2_full = false; 
    
            while (!buffer_r1_full || !buffer_r2_full) { 
                {
                    unique_lock<mutex> lock1(lock_r1, defer_lock);
                    unique_lock<mutex> lock2(lock_r2, defer_lock);
    
                    int result = try_lock(lock1, lock2);
                    if(result == -1) {
                        buffer_r1_full = buffer_r1_inc_element("thread3");
                        buffer_r2_full = buffer_r2_inc_element("thread3");
                    }
                    else if(result != 0) { 
                        buffer_r1_full = buffer_r1_inc_element("thread3");
                    }
                    else if(result != 1) { 
                        buffer_r2_full = buffer_r2_inc_element("thread3");
                    }
                }
    
                std::this_thread::sleep_for(std::chrono::milliseconds(10)); 
            } 
        } 
    
        void print_buffer() { 
            for_each(buffer_r1.begin(), buffer_r1.end(), [](pair<string, int> p) { cout << p.first.c_str() << " " << p.second << endl; }); 
            cout << '\n'; 
            for_each(buffer_r2.begin(), buffer_r2.end(), [](pair<string, int> p) { cout << p.first.c_str() << " " << p.second << endl; }); 
        } 
    }; 
    
    int main() { 
        // your code goes here 
        SynchronizationTest st(20, 20); 
    
        thread t1(&SynchronizationTest::thread1, &st); 
        thread t2(&SynchronizationTest::thread2, &st); 
        thread t3(&SynchronizationTest::thread3, &st); 
    
        t1.join(); 
        t2.join(); 
        t3.join(); 
    
        st.print_buffer(); 
    
        return 0; 
    }
    


  • Nur geraten: Versuche mal den Lockguard unique_lock nach dem try_lock zu definieren ... wurde aber schon drauf hingewiesen (adapt_lock):

    Diese Seite hat ein besseres Beispiel.



  • unique_lock, try_lock, dann try_lock?



  • hi, habs so versucht...gleiches problem...wenn ich nur die condition: if(result == -1) habe...dann funktioniert es...warum?

    int result = try_lock(lock_r1, lock_r2);
    unique_lock<mutex> lock1(lock_r1, adopt_lock);
    unique_lock<mutex> lock2(lock_r2, adopt_lock);
    
    if(result == -1) {
        buffer_r1_full = buffer_r1_inc_element("thread2");
        buffer_r2_full = buffer_r2_inc_element("thread2");
    }
    else if(result != 0) { 
        buffer_r1_full = buffer_r1_inc_element("thread2");
    }
    else if(result != 1) { 
        buffer_r2_full = buffer_r2_inc_element("thread2");
    }
    


  • hm?



  • any idea?


Log in to reply