Implementieren eines thread-sicheren, generischen Stacks in C++ unter Linux

Question

In einem kürzlichen Interview wurde ich gebeten, einen threadsicheren generischen Stack auf C++ auf einem Linux-Rechner zu implementieren.
Ich kam schnell auf Folgendes (Es kann Kompilierungsfehler haben).
Ich kam durch. Der Interviewer mochte wahrscheinlich etwas in dieser Implementierung. Vielleicht der Entwurfsteil :)
Hier sind ein paar Probleme, die diese Implementierung haben kann: -
1. Falsche Implementierung, um Überlauf/Unterlauf anzuzeigen. Es gibt keine Überlaufbehandlung, da ich den STL-Vektor als zugrunde liegende Datenstruktur verwende. Sollte es eine solche Handhabung geben? Auch der Unterlauf (in Pop()) ergibt false als Rückgabewert. Sollte es durch Auslösen einer Ausnahme geschehen?
2. Implementierung der PopElem-Routine. Ist die folgende Implementierung korrekt?
3. Keine echte Verwendung des oberen Elements.
4. Bessere Zeit zwischen dem Start von Writer und Reader-Thread.

Bitte machen Sie Kommentare/Vorschläge/Verbesserungen.
Danke.

// Implementierung eines Thread-sicheren generischen Stacks.

#include<pthread.h> 
#include<iostream> 
#include<vector> 

using namespace std; 

template<typename T> 
class MyStack 
{ 
public: 
//interface 
bool Push(T elem); 
bool Pop(T& elem); 
bool IsEmpty(); 

//constructor 
MyStack() { 
pthread_mutex_init(&lock); 
top = 0; 
} 

//destructor 
~MyStack() { 
pthread_mutex_destroy(&lock); 
} 

private: 
pthread_mutex_t lock; 
int top; 
vector<T> stack; 

bool MyStack::Push(T elem); 
bool MyStack::PopElem(T& elem); 
}; //end of MyStack 

template<typename T> 
bool MyStack<T>::Push(T elem) 
{ 
    pthread_mutex_lock(&lock); 
    PushElem(elem); 
    pthread_mutex_unlock(&lock); 
} 

template<typename T> 
bool MyStack<T>::Pop(T& elem) 
{ 
    pthread_mutex_lock(&lock); 
    PopElem(elem); 
    pthread_mutex_unlock(&lock); 
} 

template<typename T> 
bool MyStack<T>::PushElem(T elem) 
{ 
    stack.push_back(elem); 
    top = stack.size(); 
} 

template<typename T> 
bool MyStack<T>::PopElem(T& elem) 
{ 
    if(this.IsEmpty()) 
    { 
     return false; 
    } 

    elem = stack.back(); //tricky, returns a reference to the last element 
    stack.pop_back(); // is elem valid after this ?? 
    top = stack.size(); 
    return true; 
}  


template<typename T> 
bool MyStack<T>::IsEmpty() 
{ 
    return stack.empty(); 
} 


class MyStackTest 
{ 
public: 
    void Initialize() { 
    pthread_init(&readerT); 
    pthread_init(&writerT); 
    } 

    void Run() { 
pthread_create(writerT,0,writer,0); 
pthread_create(readerT,0,reader,0); 
pthread_join(&writerT); 
pthread_join(&readerT); 
} 

private: 
pthread_t readerT; 
pthread_t writerT; 
MyStack<int> stack; 

void reader(void); 
void writer(void); 
}; 

void MyStackTest::writer() { 
    for(int i=0;i<20;i++) { 
     stack.Push(i); 
     cout<<"\n\t Pushed element: "<<i; 
    } //end for 
} 

void MyStackTest::reader() { 
    int elem; 
    while(stack.Pop(elem)) 
    { 
    cout<<"\n\t Popped: "<<elem; 
    } 
} 

int main() 
{ 
    MyStackTest Test; 

    Test.Run(); 
} 

Answer 1

Einige Fragen:

• ich eine Locker-Klasse implementieren würde & kostenlos die Mutex RAII
• mit Anspruch würde ich std :: Stapel
• verwenden würde ich den Benutzer von std machen :: stack verwendet den Locker, um die Sperrrichtlinie zu implementieren - ein Stack, der sich selbst sperrt, ist ein schlechtes Design, da der Stack nicht wissen kann, wie er verwendet werden soll

Answer 2

Ich würde eine Bedingung Variable hinzufügen, so dass "Poppers" warten können, ohne CPU-Zeit zu brennen.

Answer 3

// heikel, gibt einen Verweis auf das letzte Element

Die Zuweisung kopiert das letzte Element, bevor er den Vektor tauchte weg ist, so ist das in Ordnung.

Wie Sie sagen, "top" ist sinnlos. Sie können jederzeit die Größe des Vektors abrufen.

Sie sollten stack.empty() nur mit gehaltener Sperre aufrufen, da es keine Garantie gibt, dass ein atomarer Zugriff erfolgt. Sie könnten eine inkonsistente Antwort erhalten, wenn Sie sie aufrufen, während ein anderer Thread gerade dabei ist, den Stack zu aktualisieren. Ihre öffentliche IsEmpty-Funktion sollte daher den Mutex verwenden, was bedeutet, dass Sie sie nicht von woanders selbst aufrufen wollen.

Aber wie auch immer, IsEmpty ist nicht sehr nützlich in parallelen Code. Nur weil es falsch ist, wenn du es anrufst, bedeutet es nicht, dass es eine Zeile später falsch ist, wenn du Pop machst. Entweder Sie sollten es von der öffentlichen Schnittstelle loswerden oder Sie sollten die Sperre aufdecken, damit Benutzer ihre eigenen atomaren Operationen schreiben können. In diesem Fall hätte ich überhaupt keine Unterlaufprüfung, außer eine Assert im Debug-Modus. Aber ich habe nie daran geglaubt, Menschen, die bis zum Veröffentlichungsmodus kommen, zu molligen, ohne die Dokumentation zu lesen oder ihren Code zu testen.

[Edit: Wie RAII für Schlösser verwenden

Wenn die Leute sagen RAII für eine Sperre zu verwenden, sie bedeuten nicht nur sicherstellen, dass der Mutex zerstört wird. Sie meinen damit, dass der Mutex freigeschaltet ist. Der Punkt ist, dass, wenn Sie Code haben, die wie folgt aussieht:

lock(); 
doSomething(); 
unlock(); 

und doSomething() löst eine Ausnahme aus, dann werden Sie den Mutex nicht entsperren. Autsch.

So, hier ist ein Beispiel Klasse, zusammen mit Nutzung:

class LockSession; 
class Lock { 
    friend class LockSession; 
    public: 
    Lock()  { pthread_mutex_init(&lock); } 
    ~Lock()  { pthread_mutex_destroy(&lock); } 

    private: 
    void lock() { pthread_mutex_lock(&lock); } 
    void unlock() { pthread_mutex_unlock(&lock); } 

    private: 
    Lock(const Lock &); 
    const Lock &operator=(const Lock &); 

    private: 
    pthread_mutex_t lock; 
}; 

class LockSession { 
    LockSession(Lock &l): lock(l) { lock.lock(); } 
    ~LockSession()    { lock.unlock(); } 
    private: 
    LockSession(const LockSession &); 
    LockSession &operator=(const LockSession &); 

    private: 
    Lock &lock; 
}; 

Dann irgendwo wird Ihr Code eine Sperre mit dem Daten, die Sie schützen möchten zugeordnet haben, und es wird in etwa wie folgt verwendet werden:

void doSomethingWithLock() { 
    LockSession session(lock); 
    doSomething(); 
} 

oder

void doSeveralThings() { 
    int result = bigSlowComputation(); // no lock 
    { 
     LockSession s(lock); 
     result = doSomething(result); // lock is held 
    } 
    doSomethingElse(result);  // no lock 
} 

Jetzt spielt es keine Rolle, ob doSomething() löst eine Ausnahme aus oder kehrt normal zurück (im zweiten Beispiel wird doSomethingElse bei Ausnahme nicht vorkommen, aber ich gehe davon aus, dass dies in einer Fehlersituation nicht erforderlich ist). In jedem Fall wird session zerstört, und sein Destruktor gibt den Mutex frei. Insbesondere Operationen wie "push" auf einem Stapel belegen Speicher und können daher werfen, und daher müssen Sie damit umgehen.

RAII steht für Resource Acquisition Is Initialization. Im Falle von doSomethingWithLock() ist die Ressource, die Sie erwerben möchten, dass Sie die Sperre halten möchten. Sie schreiben also eine Klasse, die dies ermöglicht, indem Sie ein Objekt initialisieren (LockSession). Wenn das Objekt zerstört wird, wird die Sperre aufgehoben. Sie behandeln also das Sperren/Entsperren des Mutex genau so, wie Sie das Ein- und Ausschalten des Mutex behandeln, und Sie schützen sich auf dieselbe Weise vor Ressourcenlecks.

Eine etwas ärgerlich Tatsache ist, dass dieser Code vollständig gebrochen ist und Buggy, und Sie müssen sicher sein, nicht versehentlich es tun, auch wenn es auf den unvorsichtigen Auge sieht genauso aus wie der richtige Code:

void doSomethingWithLock() { 
    LockSession(lock); 
    doSomething(); 
} 

Hier erstellt die erste Zeile ein temporäres Objekt und zerstört es sofort, wodurch das Schloss wieder freigegeben wird. doSomething() wird nicht mit gehaltener Sperre aufgerufen.

-Boost hat eine Klassenvorlage scoped_lock, das tut, was LockSession tut und mehr.]

Answer 4

Ich würde auf den ersten Top-wegzuwerfen. Wenn Sie es nicht brauchen, ist es nur Müll!

Small is beautiful

Auch wenn Sie die Zugriffe auf Vektor optimieren wollte: (: stacklength hier) ist immer fehleranfällige Handhabung von Managementinformationen Duplizieren. Bessere Hoffnung, dieser Vektor ist brillant schnell (STL ist die meiste Zeit) und so leer() ist es auch.

Answer 5

Dies ist kein idiomatisches C++ und hat vielleicht keine Vorteile, aber nur für die Neuheit, haben Sie überlegt, einen unveränderlichen Stack zu implementieren? Auf diese Weise wäre es automatisch Thread-sicher.

Eric Lippert hat eine C# implementation getan. Zugegebenermaßen wäre der C++ Code eher involviert.

Answer 6

Eine Sache, die Sie nicht angesprochen haben, ist das Problem der Thread-Löschung. Der stl verhält sich schlecht, wenn ein Thread während einer Operation in einem STL-Container abgebrochen wird. Sie müssen die Löschung deaktivieren, wenn Sie mit dem Vektor arbeiten. Ich habe es auf die harte Tour herausgefunden. Es macht keinen Spaß, wenn Sie einen Deadlock haben und die Threads alle im Template-Stl-Code sind und Sie versuchen genau zu debuggen, was passiert ist. Verwenden Sie pthread_setcancelstate, um den Löschstatus der Threads zu ändern.

Answer 7

Neil, Onebyone:
Ein Versuch, RAII für Mutex-Sperre zu verwenden. Irgendwelche Kommentare?

template<typename T> 
class MyStack 
{ 
public: 
//interface 
bool Push(T elem); 
bool Pop(T& elem); 
bool IsEmpty(); 

//constructor 
MyStack() { 
//top = 0; 
} 

//destructor 
~MyStack() { 

} 

private: 
    class Locker {   //RAII 
    public: 
     Locker() { 
      pthread_mutex_init(&lock); 
     } 
     ~Locker() { 
      pthread_mutex_destroy(&lock); 
     } 
     void Lock() { 
      pthread_mutex_lock(&lock); 
     } 
     void UnLock() { 
      pthread_mutex_unlock(&lock); 
     } 
    private: 
     pthread_mutex_t lock; 
    }; 
Locker MyLock; 
//int top; 
stack<T> mystack; 

bool MyStack::Push(T elem); 
bool MyStack::PushElem(T elem); 
bool MyStack::Pop(T& elem); 
bool MyStack::PopElem(T& elem); 
}; //end of MyStack 

template<typename T> 
bool MyStack<T>::Push(T elem) 
{ 
    MyLock.Lock(); 
    PushElem(elem); 
    MyLock.UnLock(); 
} 

template<typename T> 
bool MyStack<T>::Pop(T& elem) 
{ 
    MyLock.Lock(); 
    PopElem(elem); 
    MyLock.UnLock(); 
}