Diseño de estructura de datos Thread-Safe

Question

Tengo que diseñar una estructura de datos que se utilizará en un entorno de subprocesos múltiples. La API básica es simple: insertar elemento, eliminar elemento, recuperar elemento, verificar que ese elemento exista. La implementación de la estructura usa un bloqueo implícito para garantizar la atomicidad de una única llamada API. Después de implementar esto, se hizo evidente, que lo que realmente necesito es la atomicidad en varias llamadas API. Por ejemplo, si una persona que llama tiene que comprobar la existencia de un elemento antes de tratar de insertarlo él no puede hacer eso de forma atómica, incluso si cada llamada a la API sola es atómica:

if(!data_structure.exists(element)) { 
    data_structure.insert(element); 
} 

El ejemplo es algo torpe, pero el punto básico es que no podemos confiar más en el resultado de la llamada a "existir" después de regresar del contexto atómico (el conjunto generado muestra claramente una pequeña posibilidad de cambio de contexto entre las dos llamadas).

Lo que actualmente tengo en mente para resolver esto es exponer el bloqueo a través de la API pública de la estructura de datos. De esta forma, los clientes tendrán que bloquear explícitamente las cosas, pero al menos no tendrán que crear sus propios bloqueos. ¿Existe una solución mejor conocida para este tipo de problemas? Y mientras lo hagamos, ¿puede aconsejarnos buena literatura sobre diseño seguro para subprocesos?

EDIT: Tengo un mejor ejemplo. Supongamos que la recuperación de elementos devuelve una referencia o un puntero al elemento almacenado y no su copia. ¿Cómo se puede proteger a una persona que llama para usar de forma segura este puntero \ referencia después de que la llamada vuelve? Si cree que no devolver copias es un problema, entonces piense en copias en profundidad, es decir, objetos que también deberían copiar otros objetos a los que apuntan internamente.

Gracias.

Answer 1

O bien proporciona un mecanismo para el bloqueo externo (malo), o rediseña la API, como putIfAbsent. Este último enfoque se utiliza por ejemplo para Java concurrent data-structures.

Y, cuando se trata de tales tipos de colecciones básicas, debe verificar si su idioma de elección ya las ofrece en su biblioteca estándar.

[edit] Para aclarar: el bloqueo externo es malo para el usuario de la clase, ya que introduce otra fuente de posibles errores. Sí, hay veces en que las consideraciones de rendimiento empeoran las estructuras de datos concurrentes en comparación con las sincronizadas externamente, pero esos casos son raros, y generalmente solo pueden ser resueltos/optimizados por personas con mucho más conocimiento/experiencia que yo.

Una, tal vez importante, pista de rendimiento se encuentra en Will's answer a continuación. [/ edit]

[edit2] Dado su nuevo ejemplo: Básicamente debe tratar de mantener la sincronización de la colección y la de los elementos separados tanto como sea posible. Si el tiempo de vida de los elementos está ligado a su presencia en una colección, se encontrará con problemas; cuando se usa un GC, este tipo de problema en realidad se vuelve más simple. De lo contrario, tendrá que usar un tipo de proxy en lugar de elementos sin procesar para estar en la colección; en el caso más simple para C++, debería usar boost::shared_ptr, que usa un conteo de ref atómico. Inserte el descargo de responsabilidad de rendimiento habitual aquí. Cuando está usando C++ (como sospecho mientras habla de punteros y referencias), la combinación de boost::shared_ptr y boost::make_shared debería ser suficiente por un tiempo. [/ edit2]

Answer 2

¿Qué hay de mover la comprobación de presencia en el método .insert()? Un cliente lo llama y si devuelve false sabrá que algo salió mal.Al igual que lo que hace malloc() en el antiguo C simple - devuelve NULL si falló, configure ERRNO.

Obviamente también se puede devolver una excepción, o una instancia de un objeto, y complicar su vida a partir de ahí ..

Pero, por favor, no se basan en el establecimiento de sus propias cerraduras usuario.

Answer 3

A veces es costoso crear un elemento que se inserta. En estos escenarios, no puede darse el lujo de crear rutinariamente objetos que ya podrían existir por si acaso lo hacen.

Un método es para que el método insertIfAbsent() devuelva un "cursor" que está bloqueado: inserta un marcador de posición en la estructura interna para que ningún otro hilo pueda creer que está ausente, pero no inserta el nuevo objeto. El marcador de posición puede contener un bloqueo para que otros hilos que deseen acceder a ese elemento particular deban esperar a que se inserte.

En un lenguaje RAII como C++ se puede utilizar una clase de pila inteligentes para encapsular el cursor devuelto para que automáticamente rollos de devolución si el código de llamada no se compromete. En Java es un poco más diferido con el método finalize(), pero todavía puede funcionar.

Otro enfoque es para la persona que llama para crear el objeto que no está presente, pero que ocasionalmente falla en la inserción real si otro hilo ha "ganado la carrera". Así es como, por ejemplo, se realizan las actualizaciones de Memcache. Puede funcionar muy bien.

Answer 4

En primer lugar, realmente debería separar sus preocupaciones. Tiene dos cosas de qué preocuparse:

1. La estructura de datos y sus métodos.
2. La sincronización del hilo.

Le sugiero que use una interfaz o clase base virtual que represente el tipo de estructura de datos que está implementando. Cree una implementación simple que no haga ningún bloqueo, en absoluto. Luego, cree una segunda implementación que envuelva la primera implementación y agregue el bloqueo en la parte superior. Esto permitirá una implementación más eficiente donde el bloqueo no es necesario y simplificará en gran medida su código.

Parece que va a implementar algún tipo de diccionario. Una cosa que puede hacer es proporcionar métodos que tengan semántica que sean equivalentes a la instrucción combinada. Por ejemplo, setdefault es una función razonable para proporcionar que establecerá un valor solo si la clave correspondiente no existe en el diccionario.

En otras palabras, mi recomendación sería la de averiguar qué combinaciones de métodos se utilizan con frecuencia juntos, y simplemente crear métodos de la API que realizan esa combinación de operaciones atómicamente.

Answer 5

En un estilo de moda RAII puede crear objetos de acceso/manija (no sé cómo se llama su, probablemente existe un patrón de este), por ejemplo, una lista:

template <typename T> 
class List { 
    friend class ListHandle<T>; 
    // private methods use NO locking 
    bool _exists(const T& e) { ... } 
    void _insert(const T& e) { ... } 
    void _lock(); 
    void _unlock(); 
public: 
    // public methods use internal locking and just wrap the private methods 
    bool exists(const T& e) { 
     raii_lock l; 
     return _exists(e); 
    } 
    void insert(const T& e) { 
     raii_lock l; 
     _insert(e); 
    } 
    ... 
}; 

template <typename T> 
class ListHandle { 
    List<T>& list; 
public: 
    ListHandle(List<T>& l) : list(l) { 
     list._lock(); 
    } 
    ~ListHandle() { 
     list._unlock(); 
    } 
    bool exists(const T& e) { return list._exists(e); } 
    void insert(const T& e) { list._insert(e); } 
}; 


List<int> list; 

void foo() { 
    ListHandle<int> hndl(list); // locks the list as long as it exists 
    if(hndl.exists(element)) { 
     hndl.insert(element); 
    } 
    // list is unlocked here (ListHandle destructor) 
} 

duplica (o incluso triplicado) de la interfaz pública, sino que ofrece a los usuarios la opción de elegir entre el bloqueo interno y externo seguro y cómodo donde sea necesario.