Implementación de una pila genérica segura para subprocesos en C++ en linux

Question

En una entrevista reciente, me pidieron que implementara una pila genérica segura (es decir, basada en una plantilla) en C++, en una máquina Linux.
Rápidamente se me ocurrió lo siguiente (Puede tener errores de compilación).
Terminé. Al entrevistador probablemente le gustó algo en esta implementación. Tal vez la parte de diseño :)
Aquí hay algunos problemas que puede tener esta implementación: -
1. Implementación incorrecta para indicar desbordamiento/subdesbordamiento. No hay manejo de desbordamiento ya que estoy usando el vector STL como la estructura de datos subyacente. ¿Debería haber tal manejo? Además, underflow (en Pop()) produce falso como valor de retorno. ¿Debería hacerse lanzando una excepción?
2. Implementación de la rutina PopElem. ¿La implementación a continuación es correcta?
3. No uso real del elemento superior.
4. Mejor sincronización entre el inicio del escritor y el hilo del lector.

Por favor, haga cualquier comentario/sugerencia/mejora.
Gracias.

// Implementando una pila genérica segura para hilos.

#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

Algunas cuestiones:

• Me gustaría implementar una clase Locker para reclamar & libre de la exclusión mutua utilizando RAII
• me gustaría utilizar std :: pila
• Me gustaría hacer el usuario del ETS :: pila utilizar el armario para poner en práctica la política de bloqueo - que tiene una pila que encierra en sí es un mal diseño, ya que la pila no se sabe cómo se va a utilizar

Answer 2

Yo añadiría una variable condición para que "poppers" pueden esperar sin quemar tiempo de CPU.

Answer 3

// complicado, devuelve una referencia al último elemento

la asignación copia el último elemento antes de que se desprendió el vector, por lo que está muy bien.

Como dices, "arriba" no tiene sentido. Puede tomar el tamaño del vector en cualquier momento que lo desee.

Solo debe llamar a stack.empty() con el bloqueo retenido, ya que no hay garantía de que haga un acceso atómico. Puede obtener una respuesta incoherente si la llama mientras otro hilo está en el medio de actualizar la pila. Por lo tanto, su función pública IsEmpty debe tomar el mutex, lo que significa que no desea llamarlo usted mismo desde otro lugar.

Pero de todos modos, IsEmpty no es muy útil en el código paralelo. El hecho de que sea falso cuando lo llamas no significa que seguirá siendo falso una línea más adelante cuando Pop. Así que, o usted debe deshacerse de él desde la interfaz pública, o de lo contrario debe dejar expuesto el bloqueo de modo que los usuarios pueden escribir sus propias operaciones atómicas. En ese caso, no tendría ninguna comprobación de subdesbordamiento salvo una afirmación en modo de depuración. Pero entonces, nunca he creído en personas que se mueven por el culo y que llegan tan lejos como el modo de lanzamiento sin leer la documentación o probar su código.

[Editar: Cómo utilizar RAII para cerraduras

Cuando la gente dice utilizar RAII para una cerradura, que no sólo significan para asegurarse de que el mutex se destruye. Significan usarlo para asegurarse de que el mutex esté desbloqueado. El punto es que si usted tiene código que se parece a esto:

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

y doSomething() emite una excepción, entonces no desbloquear el mutex. Ay.

tanto, aquí está una clase de ejemplo, junto con el uso de:

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; 
}; 

Entonces en algún lugar de su código tendrá un bloqueo asociado con los datos que desea proteger, y lo usará algo como lo siguiente:

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

o

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

Ahora no importa si doSomething() arroja una excepción o regresa normalmente (bueno, en el segundo ejemplo doSomethingElse no ocurrirá en la excepción, pero asumo que es algo que no necesita hacerse en una situación de error). De cualquier manera, se destruye session y su destructor libera el mutex. En particular, las operaciones como "empujar" en una pila asignan memoria, y por lo tanto pueden arrojar, y por lo tanto, tiene que lidiar con eso.

RAII significa Resource Acquisition Is Initialization. En el caso de doSomethingWithLock(), el recurso que desea adquirir es que desea mantener el bloqueo. Entonces, usted escribe una clase que le permite hacer eso inicializando un objeto (LockSession). Cuando el objeto se destruye, se abandona el bloqueo. Así que está tratando "bloquear/desbloquear el mutex" exactamente de la misma manera que trata "initing/deiniting the mutex", y se protege de las pérdidas de recursos de la misma manera.

Un hecho poco molesto es que este código es completamente roto y con errores, y hay que estar seguro de no querer hacerlo, a pesar de que se ve a simple descuido al igual que el código correcto:

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

Aquí la primera línea crea un objeto temporal y lo destruye inmediatamente, liberando nuevamente el bloqueo. doSomething() no se llama con el bloqueo mantenido.

Boost tiene una plantilla de clase scoped_lock, que hace lo que hace LockSession, y más.]

Answer 4

me tire encima al principio. ¡Cuando no lo necesitas es solo basura!

pequeño es hermoso

también si desea optimizar los accesos a vectores: Duplicar manejo de información de gestión (aquí: stacklength) es siempre propenso a errores. Mejor esperanza, ese vector es brillantemente rápido (STL la mayoría de las veces lo es) y tan vacío() también lo es.

Answer 5

Esto no es idiomático en C++ y puede que no tenga ninguna ventaja, pero solo por la novedad, ¿ha considerado implementar una pila inmutable? De esa forma, automáticamente sería seguro para subprocesos.

Eric Lippert ha hecho un C# implementation. Es cierto que el código C++ sería bastante más complicado.

Answer 6

Una cosa que no resolvió es la cuestión de la cancelación de subprocesos. El stl se comporta mal cuando un hilo se cancela durante una operación en un contenedor stl. Necesita deshabilitar la cancelación cuando está operando en el vector. Descubrí lo difícil de esto. No es divertido cuando tienes un punto muerto y los hilos están todos en código stl con plantillas y estás tratando de depurar exactamente lo que sucedió. Use pthread_setcancelstate para cambiar el estado de cancelación de los hilos.

Answer 7

Neil, Onebyone:
Se ha intentado utilizar RAII para el bloqueo de exclusión mutua. ¿Algún comentario?

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(); 
}