Was genau ist eine Wiedereintrittsfunktion?

Die meisten von den Zeiten , ist die Definition der erneuten Eintritt von zitierte Wikipedia :

Ein Computerprogramm oder eine Routine wird als wiedereintrittsfähig bezeichnet, wenn es sicher wieder aufgerufen werden kann, bevor sein vorheriger Aufruf abgeschlossen wurde (dh es kann sicher gleichzeitig ausgeführt werden). Wiedereintritt, ein Computerprogramm oder eine Routine:

1. Darf keine statischen (oder globalen) nicht konstanten Daten enthalten.
2. Die Adresse darf nicht an statische (oder globale) nicht konstante Daten zurückgegeben werden.
3. Darf nur mit den vom Anrufer bereitgestellten Daten arbeiten.
4. Darf nicht auf Sperren für Singleton-Ressourcen angewiesen sein.
5. Der eigene Code darf nicht geändert werden (es sei denn, er wird in einem eigenen Thread-Speicher ausgeführt).
6. Darf keine nicht wiedereintretenden Computerprogramme oder -routinen aufrufen.

Wie ist sicher definiert?

Wenn ein Programm sicher gleichzeitig ausgeführt werden kann , bedeutet dies immer, dass es wiedereintrittsfähig ist?

Was genau ist der rote Faden zwischen den sechs genannten Punkten, den ich beachten sollte, wenn ich meinen Code auf Wiedereintrittsfähigkeiten überprüfe?

Ebenfalls,

1. Sind alle rekursiven Funktionen wiedereintrittsfähig?
2. Sind alle thread-sicheren Funktionen wiedereintrittsfähig?
3. Sind alle rekursiven und threadsicheren Funktionen wiedereintrittsfähig?

Beim Schreiben dieser Frage fällt eines ein: Sind die Begriffe Wiedereintritt und Thread-Sicherheit überhaupt absolut, dh haben sie feste konkrete Definitionen? Wenn dies nicht der Fall ist, ist diese Frage nicht sehr aussagekräftig.

1. Wie ist sicher definiert?

Semantisch. In diesem Fall ist dies kein fest definierter Begriff. Es bedeutet nur "Sie können das ohne Risiko tun".

2. Wenn ein Programm sicher gleichzeitig ausgeführt werden kann, bedeutet dies immer, dass es wiedereintrittsfähig ist?

Nein.

Nehmen wir zum Beispiel eine C ++ - Funktion, die sowohl eine Sperre als auch einen Rückruf als Parameter verwendet:

#include <mutex>

typedef void (*callback)();
std::mutex m;

void foo(callback f)
{
    m.lock();
    // use the resource protected by the mutex

    if (f) {
        f();
    }

    // use the resource protected by the mutex
    m.unlock();
}

Eine andere Funktion muss möglicherweise denselben Mutex sperren:

void bar()
{
    foo(nullptr);
}

Auf den ersten Blick scheint alles in Ordnung zu sein ... Aber warte:

int main()
{
    foo(bar);
    return 0;
}

Wenn die Sperre für Mutex nicht rekursiv ist, geschieht Folgendes im Hauptthread:

1. mainwird anrufen foo.
2. foo wird das Schloss erwerben.
3. foowird anrufen bar, die anrufen wird foo.
4. Der zweite fooversucht, die Sperre zu erlangen, schlägt fehl und wartet, bis sie freigegeben wird.
5. Sackgasse.
6. Hoppla…

Ok, ich habe mit dem Rückruf betrogen. Es ist jedoch leicht vorstellbar, dass komplexere Codeteile einen ähnlichen Effekt haben.

3. Was genau ist der rote Faden zwischen den sechs genannten Punkten, den ich beachten sollte, wenn ich meinen Code auf Wiedereintrittsmöglichkeiten überprüfe?

Sie können ein Problem riechen , wenn Ihre Funktion Zugriff auf eine veränderbare persistente Ressource hat oder Zugriff auf eine Funktion hat, die riecht .

( Ok, 99% unseres Codes sollten riechen, dann ... Siehe den letzten Abschnitt, um damit umzugehen ... )

Wenn Sie also Ihren Code studieren, sollte einer dieser Punkte Sie alarmieren:

1. Die Funktion hat einen Status (dh Zugriff auf eine globale Variable oder sogar eine Klassenmitgliedsvariable)
2. Diese Funktion kann von mehreren Threads aufgerufen werden oder während der Ausführung des Prozesses zweimal im Stapel angezeigt werden (dh die Funktion kann sich direkt oder indirekt selbst aufrufen). Funktion, die Rückrufe als Parameter nimmt, riecht viel.

Beachten Sie, dass Nicht-Wiedereintritt viral ist: Eine Funktion, die eine mögliche nicht-Wiedereintrittsfunktion aufrufen könnte, kann nicht als Wiedereintritt betrachtet werden.

Beachten Sie auch, dass C ++ - Methoden riechen, weil sie Zugriff darauf thishaben. Sie sollten daher den Code studieren, um sicherzustellen, dass sie keine lustige Interaktion haben.

4.1. Sind alle rekursiven Funktionen wiedereintrittsfähig?

Nein.

In Multithread-Fällen kann eine rekursive Funktion, die auf eine gemeinsam genutzte Ressource zugreift, von mehreren Threads gleichzeitig aufgerufen werden, was zu fehlerhaften / beschädigten Daten führt.

In Fällen mit Singuletthread kann eine rekursive Funktion eine nicht wiedereintretende Funktion (wie die berüchtigte strtok) verwenden oder globale Daten verwenden, ohne die Tatsache zu behandeln, dass die Daten bereits verwendet werden. Ihre Funktion ist also rekursiv, weil sie sich direkt oder indirekt aufruft, aber dennoch rekursiv-unsicher sein kann .

4.2. Sind alle thread-sicheren Funktionen wiedereintrittsfähig?

Im obigen Beispiel habe ich gezeigt, dass eine scheinbar threadsichere Funktion nicht wiedereintrittsfähig ist. OK, ich habe wegen des Rückrufparameters betrogen. Es gibt jedoch mehrere Möglichkeiten, einen Thread zu blockieren, indem er zweimal eine nicht rekursive Sperre erhält.

4.3. Sind alle rekursiven und threadsicheren Funktionen wiedereintrittsfähig?

Ich würde "Ja" sagen, wenn mit "rekursiv" "rekursiv-sicher" gemeint ist.

Wenn Sie garantieren können, dass eine Funktion von mehreren Threads gleichzeitig aufgerufen werden kann und sich direkt oder indirekt problemlos aufrufen kann, ist sie wiedereintrittsfähig.

Das Problem ist die Bewertung dieser Garantie… ^ _ ^

5. Sind die Begriffe Wiedereintritt und Gewindesicherheit überhaupt absolut, dh haben sie feste konkrete Definitionen?

Ich glaube, dass sie es tun, aber dann kann die Bewertung einer Funktion threadsicher oder wiedereintrittsfähig sein. Aus diesem Grund habe ich oben den Begriff Geruch verwendet : Sie können feststellen, dass eine Funktion nicht wiedereintrittsfähig ist, es kann jedoch schwierig sein, sicherzustellen, dass ein komplexer Code wiedereintrittsfähig ist

6. Ein Beispiel

Angenommen, Sie haben ein Objekt mit einer Methode, die eine Ressource verwenden muss:

struct MyStruct
{
    P * p;

    void foo()
    {
        if (this->p == nullptr)
        {
            this->p = new P();
        }

        // lots of code, some using this->p

        if (this->p != nullptr)
        {
            delete this->p;
            this->p = nullptr;
        }
    }
};

Das erste Problem ist, dass, wenn diese Funktion irgendwie rekursiv aufgerufen wird (dh diese Funktion ruft sich direkt oder indirekt auf), der Code wahrscheinlich abstürzt, weil er this->pam Ende des letzten Aufrufs gelöscht wird und wahrscheinlich noch vor dem Ende verwendet wird des ersten Anrufs.

Daher ist dieser Code nicht rekursiv sicher .

Wir könnten einen Referenzzähler verwenden, um dies zu korrigieren:

struct MyStruct
{
    size_t c;
    P * p;

    void foo()
    {
        if (c == 0)
        {
            this->p = new P();
        }

        ++c;
        // lots of code, some using this->p
        --c;

        if (c == 0)
        {
            delete this->p;
            this->p = nullptr;
        }
    }
};

Auf diese Weise wird der Code rekursiv sicher… Aufgrund von Multithreading-Problemen ist er jedoch immer noch nicht wiedereintrittsfähig: Wir müssen sicher sein, dass die Änderungen von cund von patomar mithilfe eines rekursiven Mutex vorgenommen werden (nicht alle Mutexe sind rekursiv):

#include <mutex>

struct MyStruct
{
    std::recursive_mutex m;
    size_t c;
    P * p;

    void foo()
    {
        m.lock();

        if (c == 0)
        {
            this->p = new P();
        }

        ++c;
        m.unlock();
        // lots of code, some using this->p
        m.lock();
        --c;

        if (c == 0)
        {
            delete this->p;
            this->p = nullptr;
        }

        m.unlock();
    }
};

Und natürlich setzt dies alles voraus, dass lots of codees selbst wiedereintritt, einschließlich der Verwendung von p.

Und der obige Code ist nicht einmal ausnahmsweise ausnahmesicher , aber dies ist eine andere Geschichte… ^ _ ^

7. Hey, 99% unseres Codes sind nicht wiedereintrittsfähig!

Es ist ganz richtig für Spaghetti-Code. Wenn Sie Ihren Code jedoch korrekt partitionieren, vermeiden Sie Wiedereintrittsprobleme.

7.1. Stellen Sie sicher, dass alle Funktionen den Status NO haben

Sie dürfen nur die Parameter, ihre eigenen lokalen Variablen und andere Funktionen ohne Status verwenden und Kopien der Daten zurückgeben, wenn sie überhaupt zurückkehren.

7.2. Stellen Sie sicher, dass Ihr Objekt "rekursiv sicher" ist.

Eine Objektmethode hat Zugriff auf this, sodass sie einen Status mit allen Methoden derselben Instanz des Objekts teilt.

Stellen Sie also sicher, dass das Objekt an einem Punkt im Stapel verwendet werden kann (dh Methode A aufrufen) und dann an einem anderen Punkt (dh Methode B aufrufen), ohne das gesamte Objekt zu beschädigen. Entwerfen Sie Ihr Objekt so, dass sichergestellt ist, dass das Objekt beim Beenden einer Methode stabil und korrekt ist (keine baumelnden Zeiger, keine widersprüchlichen Elementvariablen usw.).

7.3. Stellen Sie sicher, dass alle Ihre Objekte korrekt gekapselt sind

Niemand sonst sollte Zugriff auf seine internen Daten haben:

    // bad
    int & MyObject::getCounter()
    {
        return this->counter;
    }

    // good
    int MyObject::getCounter()
    {
        return this->counter;
    }

    // good, too
    void MyObject::getCounter(int & p_counter)
    {
        p_counter = this->counter;
    }

Selbst die Rückgabe einer const-Referenz kann gefährlich sein, wenn der Benutzer die Adresse der Daten abruft, da ein anderer Teil des Codes diese ändern könnte, ohne dass der Code, der die const-Referenz enthält, darüber informiert wird.

7.4. Stellen Sie sicher, dass der Benutzer weiß, dass Ihr Objekt nicht threadsicher ist

Daher ist der Benutzer dafür verantwortlich, Mutexe zu verwenden, um ein Objekt zu verwenden, das von Threads gemeinsam genutzt wird.

Die Objekte aus der STL sind so konzipiert, dass sie (aufgrund von Leistungsproblemen) nicht threadsicher sind. Wenn ein Benutzer also std::stringzwei Threads gemeinsam nutzen möchte, muss der Benutzer seinen Zugriff mit Parallelitätsprimitiven schützen.

7.5. Stellen Sie sicher, dass Ihr thread-sicherer Code rekursiv ist

Dies bedeutet, dass Sie rekursive Mutexe verwenden, wenn Sie glauben, dass dieselbe Ressource zweimal von demselben Thread verwendet werden kann.

"Sicher" ist genau so definiert, wie es der gesunde Menschenverstand vorschreibt - es bedeutet "seine Sache richtig zu machen, ohne andere Dinge zu stören". Die sechs Punkte, die Sie zitieren, drücken ganz klar die Anforderungen aus, um dies zu erreichen.

Die Antwort auf Ihre 3 Fragen lautet 3 × "Nein".

Sind alle rekursiven Funktionen wiedereintrittsfähig?

NEIN!

Zwei gleichzeitige Aufrufe einer rekursiven Funktion können sich leicht gegenseitig vermasseln, wenn sie beispielsweise auf dieselben globalen / statischen Daten zugreifen.

Sind alle thread-sicheren Funktionen wiedereintrittsfähig?

NEIN!

Eine Funktion ist threadsicher, wenn sie bei gleichzeitigem Aufruf nicht fehlerhaft funktioniert. Dies kann jedoch beispielsweise erreicht werden, indem ein Mutex verwendet wird, um die Ausführung des zweiten Aufrufs zu blockieren, bis der erste abgeschlossen ist, sodass jeweils nur ein Aufruf funktioniert. Wiedereintritt bedeutet , gleichzeitig ausgeführt zu werden, ohne andere Aufrufe zu stören .

Sind alle rekursiven und threadsicheren Funktionen wiedereintrittsfähig?

NEIN!

Siehe oben.

Der rote Faden:

Ist das Verhalten gut definiert, wenn die Routine aufgerufen wird, während sie unterbrochen wird?

Wenn Sie eine Funktion wie diese haben:

int add( int a , int b ) {
  return a + b;
}

Dann ist es nicht abhängig von einem äußeren Zustand. Das Verhalten ist gut definiert.

Wenn Sie eine Funktion wie diese haben:

int add_to_global( int a ) {
  return gValue += a;
}

Das Ergebnis ist für mehrere Threads nicht genau definiert. Informationen könnten verloren gehen, wenn das Timing falsch wäre.

Die einfachste Form einer Wiedereintrittsfunktion arbeitet ausschließlich mit den übergebenen Argumenten und konstanten Werten. Alles andere erfordert eine besondere Behandlung oder ist häufig nicht wiedereintrittsfähig. Und natürlich dürfen sich die Argumente nicht auf veränderliche Globale beziehen.

Jetzt muss ich auf meinen vorherigen Kommentar eingehen. @ paercebal Antwort ist falsch. Hat im Beispielcode niemand bemerkt, dass der Mutex, der als Parameter gelten soll, nicht tatsächlich übergeben wurde?

Ich bestreite die Schlussfolgerung, die ich behaupte: Damit eine Funktion bei gleichzeitiger Verwendung sicher ist, muss sie erneut eintreten. Daher bedeutet Concurrent-Safe (normalerweise geschriebener Thread-Safe) einen Wiedereintritt.

Weder Thread-sicher noch Wiedereinsteiger haben etwas zu Argumenten zu sagen: Es handelt sich um die gleichzeitige Ausführung der Funktion, die bei Verwendung unangemessener Parameter immer noch unsicher sein kann.

Zum Beispiel ist memcpy () threadsicher und (normalerweise) wiedereintrittsfähig. Offensichtlich funktioniert es nicht wie erwartet, wenn es mit Zeigern auf dieselben Ziele von zwei verschiedenen Threads aufgerufen wird. Dies ist der Punkt der SGI-Definition, bei dem der Client verpflichtet ist, sicherzustellen, dass die Zugriffe auf dieselbe Datenstruktur vom Client synchronisiert werden.

Es ist wichtig zu verstehen, dass es im Allgemeinen Unsinn ist , wenn threadsichere Operationen die Parameter enthalten. Wenn Sie eine Datenbankprogrammierung durchgeführt haben, werden Sie verstehen. Das Konzept dessen, was "atomar" ist und möglicherweise durch einen Mutex oder eine andere Technik geschützt wird, ist notwendigerweise ein Benutzerkonzept: Die Verarbeitung einer Transaktion in einer Datenbank kann mehrere ununterbrochene Änderungen erfordern. Wer kann sagen, welche außer dem Client-Programmierer synchron gehalten werden müssen?

Der Punkt ist, dass "Korruption" nicht den Speicher Ihres Computers mit unserialisierten Schreibvorgängen durcheinander bringen muss: Korruption kann auch dann auftreten, wenn alle einzelnen Vorgänge serialisiert sind. Wenn Sie also fragen, ob eine Funktion threadsicher ist oder erneut eingegeben wird, bedeutet die Frage für alle entsprechend getrennten Argumente: Die Verwendung gekoppelter Argumente ist kein Gegenbeispiel.

Es gibt viele Programmiersysteme: Ocaml ist eines, und ich denke auch Python, das viel nicht wiedereintrittsfähigen Code enthält, aber eine globale Sperre verwendet, um Thread-Zugriffe zu verschachteln. Diese Systeme sind nicht wiedereintrittsfähig und nicht threadsicher oder gleichzeitig sicher. Sie arbeiten sicher, einfach weil sie die Parallelität global verhindern.

Ein gutes Beispiel ist Malloc. Es ist nicht wiedereintrittsfähig und nicht threadsicher. Dies liegt daran, dass auf eine globale Ressource (den Heap) zugegriffen werden muss. Die Verwendung von Schlössern macht es nicht sicher: Es ist definitiv kein Wiedereintritt. Wenn die Schnittstelle zu malloc ordnungsgemäß gestaltet worden wäre, wäre es möglich, sie wiedereintrittsfähig und threadsicher zu machen:

malloc(heap*, size_t);

Jetzt kann es sicher sein, da es die Verantwortung für die Serialisierung des gemeinsam genutzten Zugriffs auf einen einzelnen Heap auf den Client überträgt. Insbesondere ist keine Arbeit erforderlich, wenn separate Heap-Objekte vorhanden sind. Wenn ein gemeinsamer Heap verwendet wird, muss der Client den Zugriff serialisieren. Die Verwendung einer Sperre innerhalb der Funktion reicht nicht aus: Betrachten Sie einfach ein Malloc, das einen Heap * sperrt, und dann kommt ein Signal und ruft malloc mit demselben Zeiger auf: Deadlock: Das Signal kann nicht fortgesetzt werden, und der Client kann es auch nicht, weil es ist unterbrochen.

Im Allgemeinen machen Sperren die Dinge nicht threadsicher. Sie zerstören tatsächlich die Sicherheit, indem sie unangemessen versuchen, eine Ressource zu verwalten, die dem Client gehört. Das Sperren muss vom Objekthersteller durchgeführt werden. Dies ist der einzige Code, der weiß, wie viele Objekte erstellt werden und wie sie verwendet werden.

Der "gemeinsame Thread" (Wortspiel beabsichtigt!?) Unter den aufgelisteten Punkten ist, dass die Funktion nichts tun darf, was das Verhalten von rekursiven oder gleichzeitigen Aufrufen derselben Funktion beeinflussen würde.

So sind beispielsweise statische Daten ein Problem, da sie allen Threads gehören. Wenn ein Aufruf eine statische Variable ändert, verwenden alle Threads die geänderten Daten, was sich auf ihr Verhalten auswirkt. Selbstmodifizierender Code (obwohl selten anzutreffen und in einigen Fällen verhindert) wäre ein Problem, da es zwar mehrere Threads gibt, aber nur eine Kopie des Codes gibt. Der Code ist auch wesentliche statische Daten.

Im Wesentlichen muss jeder Thread in der Lage sein, die Funktion so zu verwenden, als wäre er der einzige Benutzer. Dies ist nicht der Fall, wenn ein Thread das Verhalten eines anderen Threads auf nicht deterministische Weise beeinflussen kann. In erster Linie hat jeder Thread separate oder konstante Daten, mit denen die Funktion arbeitet.

Alles in allem ist Punkt (1) nicht unbedingt wahr; Sie können beispielsweise eine statische Variable verwenden, um eine Rekursionszahl beizubehalten, um eine übermäßige Rekursion zu vermeiden oder um einen Algorithmus zu profilieren.

Eine thread-sichere Funktion muss nicht wiedereintrittsfähig sein. Es kann die Gewindesicherheit erreichen, indem es das Wiedereintreten mit einer Verriegelung gezielt verhindert, und Punkt (6) besagt, dass eine solche Funktion nicht wiedereintritt. In Bezug auf Punkt (6) ist eine Funktion, die eine thread-sichere Funktion aufruft, die sperrt, für die Verwendung in der Rekursion nicht sicher (sie wird Deadlock) und wird daher nicht als wiedereintrittsfähig bezeichnet, obwohl sie dennoch sicher für die Parallelität sein kann, und wäre immer noch neu in dem Sinne, dass mehrere Threads ihre Programmzähler gleichzeitig in einer solchen Funktion haben können (nur nicht mit dem gesperrten Bereich). Möglicherweise hilft dies dabei, die Thread-Sicherheit von der Wiedergeburt zu unterscheiden (oder trägt möglicherweise zu Ihrer Verwirrung bei!).

Die Antworten auf Ihre "Auch" -Fragen lauten "Nein", "Nein" und "Nein". Nur weil eine Funktion rekursiv und / oder threadsicher ist, wird sie nicht erneut eingegeben.

Jede dieser Arten von Funktionen kann an allen von Ihnen angegebenen Punkten fehlschlagen. (Obwohl ich mir Punkt 5 nicht 100% sicher bin).

Die Begriffe "Thread-sicher" und "Wiedereinsteiger" bedeuten nur und genau das, was ihre Definitionen sagen. "Sicher" bedeutet in diesem Zusammenhang nur, was die Definition, die Sie unten zitieren, sagt.

"Sicher" bedeutet hier sicherlich nicht sicher im weiteren Sinne, dass das Aufrufen einer bestimmten Funktion in einem bestimmten Kontext Ihre Anwendung nicht vollständig beeinträchtigt. Insgesamt kann eine Funktion in Ihrer Multithread-Anwendung zuverlässig einen gewünschten Effekt erzielen, sich jedoch gemäß den Definitionen weder als Wiedereinsteiger noch als Thread-sicher qualifizieren. Im Gegensatz dazu können Sie wiedereintretende Funktionen auf eine Weise aufrufen, die eine Vielzahl von unerwünschten, unerwarteten und / oder unvorhersehbaren Effekten in Ihrer Multithread-Anwendung erzeugt.

Die rekursive Funktion kann alles sein und der Wiedereintritt hat eine stärkere Definition als die thread-sichere, sodass die Antworten auf Ihre nummerierten Fragen alle Nein lauten.

Wenn man die Definition des Wiedereintritts liest, kann man sie als eine Funktion zusammenfassen, die nichts ändert, was über das hinausgeht, was man zum Ändern nennt. Sie sollten sich jedoch nicht nur auf die Zusammenfassung verlassen.

Multithread-Programmierung ist im allgemeinen Fall nur äußerst schwierig . Zu wissen, welcher Teil des Code-Wiedereintritts vorhanden ist, ist nur ein Teil dieser Herausforderung. Die Gewindesicherheit ist nicht additiv. Anstatt zu versuchen, wiedereintretende Funktionen zusammenzufügen, ist es besser, ein allgemeines thread-sicheres Entwurfsmuster zu verwenden und dieses Muster zu verwenden, um die Verwendung jedes Threads und der gemeinsam genutzten Ressourcen in Ihrem Programm zu steuern.