Benutzer:MovGP0/Parallel/Locking

Locking

Performance

Locks block other threads. Try to avoid them.

Execution Speed:

No Synchronization (immutable classes)
Interlocked methods
lock-Keyword or Monitor-class
asynchronous locks
something else

Lock object

blocks access by other threads
never lock on public objects
- other objects could try to lock the same object
never lock on complex objects that lock another object
- could cause a deadlock
- prefer a simple object instance
don't lock on MarshalByRefObject, string, or value types
- MarshalByRefObject proxy object that protects the object
- string are shared internally
- value types would be boxed, thus preventing a lock
lock object needs additional memory
- use other methods when requiring flyweight objects

False

Correct

var _lock = new object();
var masterList = new List<long>();
const int NumTasks = 8;

public void Foo()
{
    var tasks = new Task[NumTasks];
    
    for(var i = 0; i < NumTasks; i++)
    {
        tasks[i] = Task.Factory.StartNew(() => 
        {
            
            for(var j = 0; j < 5000000; j++)
            {
                lock(_lock) // locking every time
                {
                    masterList.Add(j);
                }
            }
        });
    }
}

var _lock = new object();
var masterList = new List<long>();
const int NumTasks = 8;

public void Foo()
{
    var tasks = new Task[NumTasks];
    
    for(var i = 0; i < NumTasks; i++)
    {
        tasks[i] = Task.Factory.StartNew(() => 
        {
            var localList = new List<long>();
            for(var j = 0; j < 5000000; j++)
            {
                localList.Add(j);
            }
            lock(_lock) // locking only once
            {
                masterList.AddRange(localList);
            }
        });
    }
}

`volatile`-Keyword

Processor might reorder code for faster execution
x86/x64 processor reorder only certain instructions, while ARM reorders everything without special instruction
- the CLR abstracts specifics, so usually there is no need to care about specifics
use of volatile, the Interlocked-methods, and lock prevents reordering of the code

False

Correct

private bool isComplete = false;
private object _lock = new object();

private void Complete()
{
    if(!isComplete)
    {
        lock(_lock)
        {
            if(!isComplete)
            {
                DoCompleteionWork();
                isComplete = true;
            }
        }
    }
}

private volatile bool isComplete = false;
private object _lock = new object();

private void Complete()
{
    if(!isComplete)
    {
        lock(_lock)
        {
            if(!isComplete)
            {
                DoCompletetionWork();
                isComplete = true;
            }
        }
    }
}

Interlocked

Methods from the static Interlocked class are considered atomic

Important Interlocked-Methods

Add
CompareAndExchange
Increment
Decrement
Exchange

Examples

Increment

CompareAndExchange

private int isComplete = 0;

private void Complete()
{
    if(Interlocked.Increment(ref isComplete) == 1)
    {
        DoCompletetionWork();
    }
}

enum State
{
    Executing, 
    Done
}

private int state = (int)State.Executing;

private void Complete()
{
    // might get called multiple times, but execute only once
    if(Interlocked.CompareAndExchange(ref state, (int)State.Done, (int)State.Executing) == (int)State.Executing)
    {
        DoCompletetionWork();
    }
}

Thread-save collections

repeating operation until executed correct
- uses while(true) loop
slower than lock, wenn experiencing concurrent calls
hard to implement correct
hard to make it perfom better than locks

class LockFreeStack<T>
{
   private class Node
   {
      public T Value; 
      public Node Next;
   }
   
   private Node head;
   
   public void Push(T value)
   {
      var newNode = new Node
      {
         Value = value;
      }
      
      while(true)
      {
         newNode.Next = this.head;
         if(Interlocked.CompareExchange(ref head, newNode, newNode.Next) == newNode.Next)
         {
            return;
         }
      }
   }

   public void T Pop()
   {
      while(true)
      {
         var node = head;
         
         if(node == null)
         {
            return default(T);
         }
         
         if(Interlocked.CompareExchange(ref head, node.Next, node))
         {
            return node.Value;
         }
      }
   }
}

Monitor

equivalent to lock keyword
optimal for short contention
retries for a given time to aquire the lock
- gives up when a lock is not possible

Enter

TryEnter

var _lock = new object();
bool taken = false;

private void Foo()
{
    try
    {
        // taken is set to true when lock is possible 
        Monitor.Enter(_lock, ref taken); 

        // do something
    }
    finally
    {
        if(taken)
        {
            Monitor.Exit(_lock);
        }
    }
}

var _lock = new object();
bool taken = false; 

private void Foo()
{
    try
    {
        Monitor.TryEnter(_lock, ref taken); 
        
        if(taken)
        {
           // do something
        }
        else
        {
           // do something else
        }
    }
    finally
    {
        if(taken)
        {
            Monitor.Exit(_lock);
        }
    }
}

Async Lock / Semaphore

requires .NET 4.5
avoids locking
requires the creation of a new task

Sync

Async

class Program
{
   const int Size = 256;
   static int[] array = new int[Size];
   static int length = 0;
   static SemaphoreSlim semaphore = new SemaphoreSlim(1); // only one thread at a time

   static void Main()
   {
      var writerTask = Task.Factory.StartNew(WriterFunc);
      var readerTask = TaskFactory.StartNew(ReaderFunc);

      Console.WriteLine("Press any key to exit");
      Console.ReadKey();
   }

   static void WriterFunc()
   {
      while(true)
      {
         semaphore.Wait(); // wait for other threads to release semaphore 
         Console.WriteLine("Writer: obtain");

         for(int i = length; i < array.Length; i++)
         {
            array[i] = i * 2;
         }
         
         Console.WriteLine("Writer: release");
         semaphore.Release();
      }
   }

   static void ReaderFunc()
   {
      while(true)
      {
         semaphore.Wait(); // wait for other threads to release semaphore 
         Console.WriteLine("Reader: obtain");
         
         for(int i = length; i >= 0; i--)
         {
            array[i] = 0;
         }
         
         Console.WriteLine("Reader: release");
         semaphore.Release();
      }
   }
}

class Program
{
   const int Size = 256;
   static int[] array = new int[Size];
   static int length = 0;
   static SemaphoreSlim semaphore = new SemaphoreSlim(1); // only one thread at a time

   static void Main()
   {
      var writerTask = Task.Factory.StartNew(WriterFunc);
      var readerTask = TaskFactory.StartNew(ReaderFunc);

      Console.WriteLine("Press any key to exit");
      Console.ReadKey();
   }

   static void WriterFuncAsync()
   {
      semaphore.WaitAsync().ContinueWith(_ =>
      {
         Console.WriteLine("Writer: obtain");

         for(int i = length; i < array.Length; i++)
         {
            array[i] = i * 2;
         }
         
         Console.WriteLine("Writer: release");
         semaphore.Release();
      }).ContinueWith(_ => WriterFuncAsync()); // loop; creates a new task (overhead)
   }

   static void ReaderFunc()
   {
      semaphore.WaitAsync().ContinueWith(_ =>
      {
         Console.WriteLine("Reader: obtain");
         
         for(int i = length; i >= 0; i--)
         {
            array[i] = 0;
         }
         
         Console.WriteLine("Reader: release");
         semaphore.Release();
      }).ContinueWith(_ => WriterFuncAsync()); // loop; creates a new task (overhead)
   }
}

Spin Lock

optimal for very short lived locks
prefer *Slim synchonization objects, because they implement spin locks

private var spinLock = new SpinLock();

private void DoWork()
{
   bool isSpinLockTaken = false;
   try
   {
      spinLock.Enter(ref isSpinLockTaken);
      
      // ...
   }
   finally
   {
      if(isSpinLockTaken)
      {
         spinLock.Exit();
      }
   }
}

ReaderWriterLock

DEPRECATED! DO NOT USE!

Mutex

can be shared between multiple processes
more expensive than Monitor
identified by a name

using (var mutex = new Mutex (false, "MyMutexName"))
{
   // try to get a lock within three seconds
   if (!mutex.WaitOne (TimeSpan.FromSeconds(3), false))
   {
     // ...
   }
}

Concurrent Collections

may harm performance, because every access causes locking
use non-locking collection when reading/writing multiple values at once; use locking at higher level
prefer non-locking algorithms

`ConcurrentBag<T>`	unordered collection
`ConcurrentDictionary<TKey, TValue>`	key/value pairs
`ConcurrentQueue<T>`	FIFO
`ConcurrentStack<T>`	LIFO

Higher-Level Abstractions

Replace Entire Collection

use when access is mostly read-only
use ImmutableCollections to minimize garbage
clients may need to store object in a local variable to have a fixed reference

// volatile ensures that reads from multiple threads have latest version
// by preventing code reordering 
private volatile Dictionary<string, MyComplexObject> _data = new Dictionary<string, MyComplexObject();

public Dictionary<string, MyComplexObject> Data
{
   get
   {
      return _data;
   }
}

private void UpdateData()
{
   var newData = new Dictionary<string, MyComplexObject>();
   newData["Foo"] = new MyComplexObject();
   // ...
   data = newData;
}

Copy Resource Per-Thread

only for lightweight class
for classes that are non-thread save
simply add [ThreadStatic] attribute
always assume that it might not be initialized at first within the current thread context

[ThreadStatic]
static Random _safeRand;

static void Main()
{
   var results = new int[100];
   
   Parallel.For(0, 5000, i => 
   {
      if(saveRand == null)
      {
         _safeRand = new Random();
      }
      
      var randomNumber = _safeRand.Next(100);
      Interlocked.Increment(ref results[randomNumber]); 
   });
}

Benutzer:MovGP0/Parallel/Locking

Locking

Performance

Lock object

volatile-Keyword

Interlocked

Thread-save collections

Monitor

Async Lock / Semaphore

Spin Lock

ReaderWriterLock

Mutex

Concurrent Collections

Higher-Level Abstractions

Replace Entire Collection

Copy Resource Per-Thread

`volatile`-Keyword