wake-up-neo.com

Was genau ist eine Wiedereintrittsfunktion?

Mostofthetimes , die Definition des Wiedereintritts wird zitiert aus Wikipedia :

Ein Computerprogramm oder eine Routine wird als wiedereintrittsfähig bezeichnet, wenn es sicher erneut aufgerufen werden kann, bevor sein vorheriger Aufruf abgeschlossen wurde (dh es kann gleichzeitig sicher ausgeführt werden). Wiedereintritt, Computerprogramm oder 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 Daten arbeiten, die der Anrufer ihm übermittelt hat.
  4. Darf sich nicht auf Sperren für Singleton-Ressourcen verlassen.
  5. Darf seinen eigenen Code nicht ändern (es sei denn, er wird in seinem eigenen eindeutigen Thread-Speicher ausgeführt)
  6. Darf keine nicht wiedereintretenden Computerprogramme oder Routinen aufrufen.

Wie ist sicher definiert?

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

Was genau ist der gemeinsame Faden zwischen den sechs genannten Punkten, an den ich denken sollte, wenn ich meinen Code auf wiedereintrittsfähige Funktionen überprüfe?

Ebenfalls,

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

Beim Schreiben dieser Frage fällt mir Folgendes ein: Sind die Begriffe Wiedereintrittssicherheit und Threadsicherheit überhaupt absolut dh haben sie feste konkrete Definitionen? Wenn dies nicht der Fall ist, ist diese Frage nicht sehr aussagekräftig.

182
Lazer

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 gleichzeitig sicher 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 akzeptiert:

#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, passiert im Haupt-Thread Folgendes:

  1. main ruft foo auf.
  2. foo wird die Sperre erwerben.
  3. foo ruft bar auf, wodurch foo aufgerufen wird.
  4. das zweite foo versucht, die Sperre zu erhalten, schlägt fehl und wartet, bis sie freigegeben wird.
  5. Sackgasse.
  6. Hoppla…

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

3. Was genau ist der gemeinsame Thread zwischen den sechs genannten Punkten, an den ich denken sollte, wenn ich meinen Code auf wiedereintrittsfähige Funktionen überprüfe?

Sie können geruch Ein Problem, wenn Ihre Funktion Zugriff auf eine veränderbare persistente Ressource hat/gibt oder Zugriff auf eine Funktion hat/gibt, die riecht.

(Okay, 99% unseres Codes sollten riechen, dann ... Siehe letzten Abschnitt, um das zu handhaben ...)

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

  1. Die Funktion hat einen Zustand (d. H. Zugriff auf eine globale Variable oder sogar eine Klassenmitgliedsvariable)
  2. Diese Funktion kann von mehreren Threads aufgerufen werden oder zweimal im Stapel erscheinen, während der Prozess ausgeführt wird (d. H., Die Funktion kann sich selbst direkt oder indirekt aufrufen). Funktion, die Callbacks als Parameter annimmt geruch viel.

Beachten Sie, dass Nichteintritt viral ist: Eine Funktion, die eine mögliche Nichteintrittsfunktion aufrufen könnte, kann nicht als erneut eintritt angesehen werden.

Beachten Sie auch die C++ - Methoden geruch weil sie Zugriff auf this haben, sollten Sie den Code studieren, um sicherzugehen, dass sie keine lustigen Interaktionen haben.

4.1. Sind alle rekursiven Funktionen wiedereintrittsfähig?

Nein.

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

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

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

Im obigen Beispiel habe ich gezeigt, dass eine anscheinend threadsichere Funktion nicht wiedereintrittsfähig ist. Ok Ich habe wegen des Rückrufparameters geschummelt. Dann gibt es jedoch mehrere Möglichkeiten, einen Thread zu blockieren, indem er zweimal eine nicht rekursive Sperre erhält.

4.3. Sind alle rekursiven und thread-sicheren Funktionen wiedereintrittsfähig?

Ich würde "Ja" sagen, wenn Sie mit "rekursiv" "rekursiv-sicher" meinen.

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

Das Problem ist die Bewertung dieser Garantie… ^ _ ^

5. Sind die Begriffe wie Wiedereintritt und Fadensicherheit überhaupt absolut, d. H. Haben sie feste konkrete Definitionen?

Ich glaube, sie haben, aber dann ist die Bewertung einer Funktion thread-sicher oder Wiedereintritt kann schwierig sein. Deshalb habe ich den Begriff verwendet geruch oben: Sie können feststellen, dass eine Funktion nicht wiedereintrittsfähig ist, aber es kann schwierig sein, sicherzustellen, dass ein komplexer Code wiedereintrittsfähig ist

6. Ein Beispiel

Angenommen, Sie haben ein Objekt mit einer Methode, die Ressourcen 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 auf irgendeine Weise rekursiv aufgerufen wird (dh diese Funktion ruft sich selbst direkt oder indirekt auf), der Code wahrscheinlich abstürzt, weil this->p Am Ende des letzten Aufrufs gelöscht wird und immer noch Wird wahrscheinlich vor dem Ende des ersten Anrufs verwendet.

Somit 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 c und p atomar mit a durchgeführt werden rekursiv Mutex (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 dies alles setzt natürlich voraus, dass lots of code Selbst wiedereintrittsfähig ist, einschließlich der Verwendung von p.

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

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

Es ist ganz richtig für Spaghetti-Code. Wenn Sie Ihren Code jedoch richtig partitionieren, vermeiden Sie Probleme mit dem Wiedereintritt.

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

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

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 (d. H., Methode A aufrufen) und dann an einem anderen Punkt (d. H. Methode B aufrufen), ohne das gesamte Objekt zu beschädigen. Entwerfen Sie Ihr Objekt, um sicherzustellen, 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 eingekapselt 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;
    }

Sogar das Zurückgeben einer const-Referenz kann gefährlich sein, wenn die Verwendung 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

Somit ist der Benutzer dafür verantwortlich, Mutexe zu verwenden, um ein zwischen Threads geteiltes Objekt zu verwenden.

Die Objekte aus der STL sind nicht threadsicher (aufgrund von Leistungsproblemen). Wenn ein Benutzer also einen std::string Zwischen zwei Threads teilen möchte, muss er seinen Zugriff mit Parallelitätsprimitiven schützen.

7.5. Stellen Sie sicher, dass Ihr threadsicherer Code rekursiv sicher ist

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

178
paercebal

"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 die Voraussetzungen dafür ziemlich deutlich aus.

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 durcheinander bringen, 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 z.B. Indem Sie einen Mutex verwenden, um die Ausführung des zweiten Aufrufs zu blockieren, bis der erste abgeschlossen ist, funktioniert immer nur ein Aufruf. Wiedereintritt bedeutet , dass gleichzeitig ausgeführt wird, ohne andere Aufrufe zu stören .


Sind alle rekursiven und thread-sicheren Funktionen wiedereintrittsfähig?

NEIN!

Siehe oben.

21
slacker

Der rote Faden:

Ist das Verhalten klar definiert, wenn die Routine während einer Unterbrechung aufgerufen wird?

Wenn Sie eine Funktion wie diese haben:

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

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

Wenn Sie eine Funktion wie diese haben:

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

Das Ergebnis ist auf mehreren Threads nicht gut definiert. Informationen könnten verloren gehen, wenn das Timing einfach falsch wäre.

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

10
drawnonward

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

Ich behaupte, dass ich die Schlussfolgerung bestreite: Damit eine Funktion bei gleichzeitiger Verwendung sicher ist, muss sie erneut aufgerufen werden. Daher impliziert Concurrent-Safe (normalerweise thread-safe geschrieben) einen erneuten Einstieg.

Weder threadsicher noch re-entrant haben etwas zu Argumenten zu sagen: Es handelt sich um die gleichzeitige Ausführung der Funktion, die bei Verwendung ungeeigneter Parameter immer noch unsicher sein kann.

Zum Beispiel ist memcpy () thread-sicher und (normalerweise) wiedereintrittsfähig. Offensichtlich funktioniert es nicht wie erwartet, wenn es mit Zeigern auf dieselben Ziele von zwei verschiedenen Threads aufgerufen wird. Das ist der Punkt der SGI-Definition, der darin besteht, dass der Client die Verantwortung dafür trägt, dass Zugriffe auf dieselbe Datenstruktur vom Client synchronisiert werden.

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

Der Punkt ist, dass "Korruption" nicht den Speicher auf Ihrem Computer mit unserialisierten Schreibvorgängen durcheinander bringen muss: Korruption kann auch dann auftreten, wenn alle einzelnen Vorgänge serialisiert sind. Daraus folgt, dass bei der Frage, ob eine Funktion thread-sicher oder wiedereintrittsfähig ist, die Frage für alle entsprechend getrennten Argumente gilt: Die Verwendung gekoppelter Argumente ist kein Gegenbeispiel.

Es gibt viele Programmiersysteme: Ocaml ist eines, und ich denke auch, dass Python) viele nicht wiedereintrittsfähige Codes enthält, die jedoch eine globale Sperre zum Verschachteln von Thread-Zugriffen verwenden. Diese Systeme sind nicht wiedereintrittsfähig und nicht thread- oder gleichzeitig sicher. Sie funktionieren sicher, nur weil sie die globale Parallelität 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. Das Verwenden von Schlössern macht es nicht sicher: Es ist definitiv kein Wiedereintritt. Wenn die Schnittstelle zu malloc richtig gestaltet wäre, wäre es möglich, sie re-entrant und thread-sicher zu machen:

malloc(heap*, size_t);

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

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

7
Yttrill

Der "allgemeine Thread" (Wortspiel beabsichtigt !?) unter den aufgelisteten Punkten ist, dass die Funktion nichts tun darf, was das Verhalten von rekursiven oder gleichzeitigen Aufrufen derselben Funktion beeinträchtigen 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 und beeinflussen so ihr Verhalten. Selbstmodifizierender Code (obwohl er nur selten auftritt und in einigen Fällen verhindert wird) wäre ein Problem, da es zwar mehrere Threads gibt, aber nur eine Kopie des Codes gibt. Der Code ist auch wichtige statische Daten.

Grundsätzlich muss jeder Thread die Funktion verwenden können, als wäre er der einzige Benutzer. Dies ist jedoch nicht der Fall, wenn ein Thread das Verhalten eines anderen Threads nicht deterministisch beeinflussen kann. In erster Linie beinhaltet dies, dass jeder Thread entweder separate oder konstante Daten hat, mit denen die Funktion arbeitet.

Alles, was gesagt wurde, Punkt (1) ist nicht unbedingt wahr; Beispielsweise können Sie legitimerweise und beabsichtigt eine statische Variable verwenden, um eine Rekursionsanzahl beizubehalten, um eine übermäßige Rekursion zu verhindern, oder um ein Profil für einen Algorithmus zu erstellen.

Eine thread-sichere Funktion muss nicht wiedereintrittsfähig sein. Sie kann die Gewindesicherheit durch gezielte Verhinderung des Wiedereintritts mit einer Sperre erreichen, und Punkt (6) besagt, dass eine solche Funktion nicht wiedereintrittsfähig ist. In Bezug auf Punkt (6) ist eine Funktion, die eine thread-sichere Funktion aufruft, die gesperrt wird, für die Verwendung in der Rekursion nicht sicher (sie wird nicht gesperrt) und wird daher nicht als wiedereintrittsfähig bezeichnet, obwohl sie für die gleichzeitige Verwendung sicher sein kann wäre immer noch neu in dem Sinne, dass mehrere Threads ihre Programmzähler in einer solchen Funktion gleichzeitig haben können (nur nicht mit dem gesperrten Bereich). Möglicherweise hilft dies dabei, die Thread-Sicherheit von der Wiederholung zu unterscheiden (oder trägt zu Ihrer Verwirrung bei!).

3
Clifford

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

Jeder dieser Funktionstypen kann in allen von Ihnen angegebenen Punkten fehlschlagen. (Obwohl ich mir Punkt 5 nicht zu 100% sicher bin).

1
ChrisF

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

"Sicher" bedeutet hier sicher nicht im weiteren Sinne, dass das Aufrufen einer bestimmten Funktion in einem bestimmten Kontext Ihre Anwendung nicht völlig auslaugt. Insgesamt kann eine Funktion in Ihrer Multithread-Anwendung möglicherweise zuverlässig einen gewünschten Effekt erzielen, ist jedoch gemäß den Definitionen weder als wiedereintrittsfähig noch als threadsicher zu qualifizieren. Umgekehrt können Sie wiedereintretende Funktionen auf eine Weise aufrufen, die eine Vielzahl von unerwünschten, unerwarteten und/oder unvorhersehbaren Effekten in Ihrer Multithread-Anwendung hervorruft.

Rekursive Funktion kann alles sein und Wiedereinsteiger haben eine stärkere Definition als Thread-sicher, so dass die Antworten auf Ihre nummerierten Fragen alle Nein sind.

Wenn man die Definition des Wiedereintritts liest, könnte man sie als eine Funktion zusammenfassen, die nichts ändert, außer dem, was man es nennt, um es zu ändern. Sie sollten sich jedoch nicht nur auf die Zusammenfassung verlassen.

Multithread-Programmierung ist nur extrem schwierig im allgemeinen Fall. Zu wissen, welcher Teil des Codes erneut eingegeben wird, ist nur ein Teil dieser Herausforderung. Die Fadensicherheit ist nicht additiv. Anstatt zu versuchen, wiedereintretende Funktionen zusammenzufügen, ist es besser, ein allgemeines threadsicherEntwurfsmuster zu verwenden und dieses Muster als Anleitung für die Verwendung von every zu verwenden Thread und freigegebene Ressourcen in Ihrem Programm.

1