Code-Review: Semaphore Implementierung mittels atomics + futex() syscall



  • Hallo zusammen!

    Ich experimentiere gerade ein wenig mit IPC. Dabei moechte ich erreichen, dass ich synchron in einen anderen Prozess callen kann, als ob es sich um eine normale Funktion handelt. Dazu hab ich mir ueberlegt, das ganze mittels 2 Semaphores zu loesen: Je ein Semaphore fuer den Prozess, der gerade auf den anderen wartet. Das ganze habe ich mit der Linux-Semaphore API geloest. (sem_open, sem_post, sem_wait)

    Nun ist das aber ein spezieller Fall, der die ganze Funktionalitaet gar nicht benotigt, die mir Semaphores zur Verfuegung stellen. Daher wollte ich testen, ob ich es nicht schneller hinbekomme, wenn ich das ganze selbst implementiere mittels atomics + futex(). Ich habe daher eigene Implementierungen von sem_post und sem_wait geschrieben und diese in mein Programm eingesetzt.

    Meine Implementierung sieht so aus:

    void sem_post(_Atomic int* s)
    {
    	atomic_store_explicit(s, 1, memory_order_release);
    
    	for(int i = 0; i != 100; ++i)
    	{
    		int n = atomic_load_explicit(s, memory_order_relaxed);
    
    		if(n == 0)
    			return;
    
    		if(n == -1)
    			break;
    	}
    
    	futex(s, FUTEX_WAKE, 1, nullptr, nullptr, 0);
    }
    
    void sem_wait(_Atomic int* s)
    {
    	int expected = 1;
    
    	for(int i = 0; i != 100; ++i)
    		if(atomic_compare_exchange_weak_explicit(s, &expected, 0, memory_order_acquire, memory_order_relaxed))
    			return;
    		else
    			expected = 1;
    
    	if(!atomic_compare_exchange_strong_explicit(s, &expected, -1, memory_order_acquire, memory_order_relaxed))
    		futex(s, FUTEX_WAIT, 0, nullptr, nullptr, 0);
    
    	atomic_store_explicit(s, 0, memory_order_relaxed);
    }
    

    Die Idee dazu ist folgende: Der Semaphore hat drei Zustaende: 1, 0 und -1.
    Der Zustand 1 bedeutet, dass der Semaphore gesignaled wurde, das heisst sem_post wurde aufgerufen und der Wartende soll geweckt werden.
    Der Zustand 0 bedeutet, dass niemand auf den Semaphore wartet, d.h. das ist der Initialzustand oder der Zustand nachdem der wartende Thread geweckt wurde.
    Der Zustand -1 ist eine Optimierung, mehr dazu gleich.

    Das ganze hat nun einen fast-path und einen slow-path. Zunaechst wird 100 mal versucht, den Zustand zu aendern ohne dass ein syscall benoetigt wird. Erst wenn das fehlschlaegt wird der slow-path mit futex() genommen.
    Fuer sem_post heisst das, dass zunaechst ueberprueft wird, ob der Wartende das Signal nicht schon bearbeitet hat. (also den Zustand des Semaphores von 1 auf 0 zurueckgeaendert hat)
    Im Falle von sem_wait bedeutet das, dass zunaechst geprueft wird, ob sich der Semaphore bereits im Zustand "signaled" (also 1) befindet, also der Thread inzwischen wieder aufgeweckt wurde.
    -1 bedeutet nun, dass sich der wartende Thread bereits im futex() syscall befindet, das heisst ein spinnen, um dem Thread Zeit zu geben, das Signal zu bearbeiten, ist unnoetig, der Thread soll direkt mittels futex() geweckt werden.

    Wichtig ist, dass diese Implementierung annimmt, dass es immer nur einen Thread gibt, der auf den Semaphore wartet. Das ganze ist spezifisch fuer meinen use case (synchroner cross-process call) designed. Alle anderen Semaphore Features benoetige ich nicht.

    Der fast-path ist bei meiner Implementierung 4x so schnell als Linux-Semaphores und der slow-path in etwa gleich. Bei atomics bin ich mir aber nicht sicher, ob ich das auch wirklich korrekt implementiert habe, daher waere es super, wenn sich das jemand, der sich besser mit atomics auskennt als ich, mal ansehen koennte.

    Danke im Voraus
    Der Kellerautomat



  • Liegts an der Fragestellung oder gibts hier einfach niemanden, der sich mit atomics wirklich gut auskennt?



  • Liegt an der Fragestellung.



  • Dann hilf mir doch bitte mal auf die Spruenge: Wie kann ich die Fragestellung verbessern? 😉



  • Soll ich dir die Gründe aufzählen warum ich der Meinung bin dass die Frage keinen interessiert bzw. keinen ausreichend motivieren kann?
    (EDIT: D.h. es liegt mMn. weniger an der Formulierung der Frage als an der Frage ansich. /EDIT)

    Ansonsten ist denke ich (zumindest) das
    if(!atomic_compare_exchange_strong_explicit
    in sem_wait falsch. In expected steht da immer noch 1, und das macht wohl keinen Sinn.


Log in to reply