Hacer que una lista enlazada sea segura

Question

Sé que esto se ha preguntado antes (y seguiré investigando), pero necesito saber cómo hacer que una función de lista vinculada particular funcione de manera segura. Mi problema actual es que tengo un hilo que recorre todos los elementos en una lista vinculada, y otro puede agregar más elementos al final de esta lista. A veces ocurre que el único hilo intenta agregar otro elemento a la lista mientras que el primero está ocupado iterando a través de él (lo que causa una excepción).

Estaba pensando en solo agregar una variable (indicador booleano) para decir que la lista está actualmente ocupada siendo iterada, pero ¿cómo la verifico y espero con el segundo hilo (está bien si espera, como el primer hilo se ejecuta bastante rápido). La única forma en que puedo pensar en hacer esto es mediante el uso de un ciclo while constantemente revisando esta bandera ocupada. Me di cuenta de que esta era una idea muy tonta ya que haría que la CPU trabajara duro sin hacer nada útil. Y ahora estoy aquí para pedir una mejor idea. He leído sobre cerraduras y demás, pero no parece ser relevante en mi caso, pero ¿quizás estoy equivocado?

Mientras tanto, seguiré buscando en Internet y publicando si encuentro una solución.

EDITAR: Avíseme si debo publicar algún código para aclarar las cosas, pero lo intentaré y lo explicaré más claramente.

Tengo una clase con una lista vinculada que contiene elementos que requieren procesamiento. Tengo un hilo que itera a través de esta lista a través de una llamada a función (llamémoslo "processElements"). Tengo un segundo hilo que agrega elementos para procesar de una manera no determinista. Sin embargo, a veces ocurre que intenta llamar a esta función addElement mientras se está ejecutando processElements. Esto significa que el elemento an se está agregando a la lista vinculada mientras el primer hilo lo itera. Esto no es posible y causa una excepción. Espero que esto lo aclare.

Necesito el hilo que agrega elementos nuevos para ceder hasta que el método processElements termine de ejecutarse.

• Para cualquier persona que tropiece con este problema. La respuesta aceptada le dará una solución rápida y fácil, pero consulte la respuesta de Brian Gideon a continuación para obtener una respuesta más completa, ¡que definitivamente le dará más información!

Answer 1

La excepción es probablemente el resultado de tener la colección cambiado en medio de una iteración a través de IEnumerator. Existen algunas técnicas que puede usar para mantener la seguridad de las hebras. Los presentaré en orden de dificultad.

Bloqueo Todo

Esto es, con mucho, el método más fácil y más trivial para conseguir el acceso a la estructura de datos seguro para subprocesos. Este patrón funciona bien cuando el número de operaciones de lectura y escritura coinciden por igual.

LinkedList<object> collection = new LinkedList<object>(); 

void Write() 
{ 
    lock (collection) 
    { 
    collection.AddLast(GetSomeObject()); 
    } 
} 

void Read() 
{ 
    lock (collection) 
    { 
    foreach (object item in collection) 
    { 
     DoSomething(item); 
    } 
    } 
} 

Copy-leer el modelo

Este es un patrón ligeramente más complejo. Notará que se hace una copia de la estructura de datos antes de leerla. Este patrón funciona bien cuando el número de operaciones de lectura son pocas en comparación con el número de escrituras y la penalización de la copia es relativamente pequeña.

LinkedList<object> collection = new LinkedList<object>(); 

void Write() 
{ 
    lock (collection) 
    { 
    collection.AddLast(GetSomeObject()); 
    } 
} 

void Read() 
{ 
    LinkedList<object> copy; 
    lock (collection) 
    { 
    copy = new LinkedList<object>(collection); 
    } 
    foreach (object item in copy) 
    { 
    DoSomething(item); 
    } 
} 

Patrón

Y por último tenemos el patrón propensa más compleja y error copiar-modificar-Swap. En realidad, no recomiendo usar este patrón a menos que realmente sepa lo que está haciendo. Cualquier desviación de lo que tengo a continuación podría ocasionar problemas. Es fácil arruinar esto. De hecho, inadvertidamente he jodido esta también en el pasado. Notará que se hace una copia de la estructura de datos antes de todas las modificaciones. La copia se modifica y finalmente la referencia original se intercambia con la nueva instancia. Básicamente siempre tratamos collection como si fuera inmutable. Este patrón funciona bien cuando el número de operaciones de escritura son pocas en comparación con el número de lecturas y la penalización de la copia es relativamente pequeña.

object lockobj = new object(); 
volatile LinkedList<object> collection = new LinkedList<object>(); 

void Write() 
{ 
    lock (lockobj) 
    { 
    var copy = new LinkedList<object>(collection); 
    copy.AddLast(GetSomeObject()); 
    collection = copy; 
    } 
} 

void Read() 
{ 
    LinkedList<object> local = collection; 
    foreach (object item in local) 
    { 
    DoSomething(item); 
    } 
} 

Actualización:

Así que plantea dos preguntas en la sección de comentarios:

• lock(lockobj) ¿Por qué en lugar de lock(collection) el lado de escritura?
• ¿Por qué local = collection en el lado de lectura?

En cuanto a la primera pregunta, considere cómo el compilador de C# ampliará el lock.

void Write() 
{ 
    bool acquired = false; 
    object temp = lockobj; 
    try 
    { 
    Monitor.Enter(temp, ref acquired); 
    var copy = new LinkedList<object>(collection); 
    copy.AddLast(GetSomeObject()); 
    collection = copy; 
    } 
    finally 
    { 
    if (acquired) Monitor.Exit(temp); 
    } 
} 

Ahora es de esperar que sea más fácil ver lo que puede salir mal si usamos collection como la expresión de bloqueo.

• El hilo A ejecuta object temp = collection.
• El hilo B ejecuta collection = copy.
• El hilo C ejecuta object temp = collection.
• El hilo A adquiere el candado con la referencia original.
• El subproceso C adquiere el bloqueo con la nueva referencia .

¡Claramente esto sería desastroso! Las escrituras se perderían ya que la sección crítica se ingresa más de una vez.

Ahora la segunda pregunta fue un poco complicada. Usted no necesariamente tiene para hacer esto con el código que publiqué arriba. Pero eso es porque usé el collection solo una vez. Ahora considere el siguiente código.

void Read() 
{ 
    object x = collection.Last; 
    // The collection may get swapped out right here. 
    object y = collection.Last; 
    if (x != y) 
    { 
    Console.WriteLine("It could happen!"); 
    } 
} 

El problema aquí es que collection podría conseguir cambiados en cualquier momento. Esto sería increíblemente error difícil de encontrar. Esta es la razón por la que siempre extraigo una referencia local en el lado de lectura cuando hago este patrón. Eso asegura que estamos usando la misma colección en cada operación de lectura.

Una vez más, debido a problemas como estos son tan sutiles que no recomiendo usar este patrón a menos que realmente lo necesite.

Answer 2

Aquí está un ejemplo rápido de cómo usar cerraduras para sincronizar el acceso a la lista:

private readonly IList<string> elements = new List<string>(); 

public void ProcessElements() 
{ 
    lock (this.elements) 
    { 
     foreach (string element in this.elements) 
      ProcessElement(element); 
    } 
} 

public void AddElement(string newElement) 
{ 
    lock (this.elements) 
    { 
     this.elements.Add(element); 
    } 
} 

Una declaración lock(o) significa que el hilo de ejecución debe adquirir un bloqueo de exclusión mutua en el objeto o, Ejecute el bloque de instrucción y finalmente libere el bloqueo en o. Si otro hilo intenta adquirir un bloqueo al o al mismo tiempo (ya sea para el mismo bloque de código o para cualquier otro), bloqueará (esperará) hasta que se libere el bloqueo.

Por lo tanto, el punto crucial es que utiliza el mismo objeto para todas las declaraciones lock que desea sincronizar. El objeto real que usa puede ser arbitrario, siempre que sea consistente. En el ejemplo anterior, declaramos que nuestra colección es de solo lectura, por lo que podemos usarla de forma segura como nuestro candado. Sin embargo, si este no fuera el caso, se debe bloquear en otro objeto:

private IList<string> elements = new List<string>(); 

private readonly object syncLock = new object(); 

public void ProcessElements() 
{ 
    lock (this.syncLock) 
    { 
     foreach (string element in this.elements) 
      ProcessElement(element); 
    } 
} 

public void AddElement(string newElement) 
{ 
    lock (this.syncLock) 
    { 
     this.elements.Add(element); 
    } 
}