Kolekcja Threadsafe bez blokady

Question

Przygotowuję się do rozmowy kwalifikacyjnej i natknąłem się na następujące pytanie. Próbowałem, ale nie mogłem znaleźć niczego, co mogłoby stworzyć klasę zawierającą bezpieczny wątek bez "blokady". Jeśli znasz jakieś rozwiązanie, proszę o pomoc.

Tworzenie klasy C# pochodzące od obiektu i realizuje następujące metody:

• addstring - Sposób ten powinien dodać dany ciąg kolekcji wewnętrznej
• ToString - nadrzędny ten sposób i zwrócić jeden, przecinki -delimited łańcuch zawierający wszystkie sznurki w kolekcji wewnętrznego

Wymagania:

• Musi być bezpieczny wątku
• Musi obsługiwać wielu czytelników współbieżnych
• nie wolno używać wstępnie istniejących zbiorów wątku bezpieczny
• Bonus: nie stosować dowolny typ zamka

Answer 1

Mogłabyś utwórz listę połączoną bez blokowania. Na przykład coś takiego jak this.

Framework .net udostępnia metody takie jak CompareExchange(Object, Object, Object), które pozwalają pisać bezpieczny kod bez blokowania całej listy.

Answer 2

Oto sposobem uzyskania blokady wolne modyfikację kolekcji pracując na lokalnej kopii, a następnie próbuje atomowo zamienić go z kolekcją światowej podczas sprawdzania dla ras:

public class NonLockingCollection 
{ 
    private List<string> collection; 

    public NonLockingCollection() 
    { 
     // Initialize global collection through a volatile write. 
     Interlocked.CompareExchange(ref collection, new List<string>(), null); 
    } 

    public void AddString(string s) 
    { 
     while (true) 
     { 
      // Volatile read of global collection. 
      var original = Interlocked.CompareExchange(ref collection, null, null); 

      // Add new string to a local copy. 
      var copy = original.ToList(); 
      copy.Add(s); 

      // Swap local copy with global collection, 
      // unless outraced by another thread. 
      var result = Interlocked.CompareExchange(ref collection, copy, original); 
      if (result == original) 
       break; 
     } 
    } 

    public override string ToString() 
    { 
     // Volatile read of global collection. 
     var original = Interlocked.CompareExchange(ref collection, null, null); 

     // Since content of global collection will never be modified, 
     // we may read it directly. 
     return string.Join(",", original); 
    } 
} 

Edit: Rejestracja użycie Interlocked.CompareExchange do niejawnego wykonywania ulotnych odczytów i zapisów spowodowało pewne zamieszanie, zamiast tego publikuję poniżej kod równoważny z wywołania Thread.MemoryBarrier.

public class NonLockingCollection 
{ 
    private List<string> collection; 

    public NonLockingCollection() 
    { 
     // Initialize global collection through a volatile write. 
     collection = new List<string>(); 
     Thread.MemoryBarrier(); 
    } 

    public void AddString(string s) 
    { 
     while (true) 
     { 
      // Fresh volatile read of global collection. 
      Thread.MemoryBarrier(); 
      var original = collection; 
      Thread.MemoryBarrier(); 

      // Add new string to a local copy. 
      var copy = original.ToList(); 
      copy.Add(s); 

      // Swap local copy with global collection, 
      // unless outraced by another thread. 
      var result = Interlocked.CompareExchange(ref collection, copy, original); 
      if (result == original) 
       break; 
     } 
    } 

    public override string ToString() 
    { 
     // Fresh volatile read of global collection. 
     Thread.MemoryBarrier(); 
     var original = collection; 
     Thread.MemoryBarrier(); 

     // Since content of global collection will never be modified, 
     // we may read it directly. 
     return string.Join(",", original); 
    } 
} 

Answer 3

Najprostszym rozwiązaniem jest o pole typu string[]. Ilekroć dzwoniący chce dodać ciąg, utwórz nową tablicę z dodanym nowym elementem i zamień go na stary.

Ten model nie wymaga synchronizacji. Nie toleruje pisarzy współbieżnych, ale pozwala na równoczesne czytanie.

Answer 4

Na podstawie tego pytania powinieneś być w stanie dodać kolekcję współbieżną wewnątrz obiektu, która spełni wymagania dotyczące bezpieczeństwa nici dla ciebie. Nie określono, jakiego typu kolekcja wewnętrzna ma być używana.

Powinieneś być w stanie zaimplementować jedną z kolekcji z przestrzeni nazw concurrentcollection i osiągnąć to.

http://msdn.microsoft.com/en-us/library/system.collections.concurrent.aspx

Answer 5

Moje rozwiązanie. Zasadniczo mimiczne blokowanie za pomocą Interlocked.Exchange i AutoResetEvents. Wykonał kilka prostych testów i wydaje się, że działa.

public class SharedStringClass 
    { 
     private static readonly int TRUE = 1; 
     private static readonly int FALSE = 0; 

     private static int allowEntry; 

     private static AutoResetEvent autoResetEvent; 

     private IList<string> internalCollection; 

     public SharedStringClass() 
     { 
      internalCollection = new List<string>(); 
      autoResetEvent = new AutoResetEvent(false); 
      allowEntry = TRUE; 
     } 

     public void AddString(string strToAdd) 
     { 
      CheckAllowEntry(); 

      internalCollection.Add(strToAdd); 

      // set allowEntry to TRUE atomically 
      Interlocked.Exchange(ref allowEntry, TRUE); 
      autoResetEvent.Set(); 
     } 

     public string ToString() 
     { 
      CheckAllowEntry(); 

      // access the shared resource 
      string result = string.Join(",", internalCollection); 

      // set allowEntry to TRUE atomically 
      Interlocked.Exchange(ref allowEntry, TRUE); 
      autoResetEvent.Set(); 
      return result; 
     } 

     private void CheckAllowEntry() 
     { 
      while (true) 
      { 
       // compare allowEntry with TRUE, if it is, set it to FALSE (these are done atomically!!) 
       if (Interlocked.CompareExchange(ref allowEntry, FALSE, TRUE) == FALSE) 
       { 
        autoResetEvent.WaitOne(); 
       } 
       else 
       { 
        break; 
       } 
      } 
     } 
    }