Luis Guerrero Hablando de .NET, Silverlight, WPF, Windows Phone 7 y depuración

23May/091

Como implementar un Singleton concurrente

Bajo este título se encuentra una de los clásicos problemas de concurrencia que seguramente más de uno se haya enfrentado en su vida de programador. En este artículo repasaremos las posibles implementaciones correctas e incorrectas de este patrón de manera concurrente.

Implementación sin concurrencia.

   1: public class Singleton<T> where T : new()
   2: {
   3:     private static T instance = new T();
   4:     public static T Instance
   5:     {
   6:         get
   7:         {
   8:             return instance;
   9:         }
  10:     }
  11: }
  12: public class SingletonV2<T> where T : new()
  13: {
  14:     private static T instance;
  15:     public static T Instance
  16:     {
  17:         get
  18:         {
  19:             if (instance == null)
  20:             {
  21:                 instance = new T();
  22:             }
  23:             return instance;
  24:         }
  25:     }
  26: }
  27: public class CacheManager
  28: {
  29:     private static CacheManager instance = new CacheManager();
  30:     public static CacheManager Instance
  31:     {
  32:         get
  33:         {
  34:             return instance;
  35:         }
  36:     }
  37:     private CacheManager()
  38:     {
  39:
  40:     }
  41: }

Como se puede ver esta es la implementación para una clase cualquiera y de una manera genérica, en la que el único requisito que pedimos es que sea una referencia y se pueda construir una instancia.

El problema de estas dos implementaciones es que cuando se construye el tipo se inicializa el valor del Singleton, lo que puede resultar en una degradación del rendimiento y solamente se desea implementar cuando se vaya a acceder al valor de la instancia. Para solucionar ese problema se puede implementar un Singleton perezoso que solamente cuando se accede la primera vez se inicializa.

   1: public class CacheManagerV2
   2: {
   3:     private static CacheManagerV2 instance;
   4:     public static CacheManagerV2 Instance
   5:     {
   6:         get
   7:         {
   8:             if (instance == null)
   9:             {
  10:                 instance = new CacheManagerV2();
  11:             }
  12:             return instance;
  13:         }
  14:     }
  15:     private CacheManagerV2()
  16:     {
  17:
  18:     }
  19: }

Pero llegado a este punto nos encontramos con un problema muy importante, que pasa si dos Threads a la vez intenta acceder al valor de la instancia de cualquiera de nuestros Singletones, el resultado puede ser catastrófico, porque se puede iniciar más de una instancia de la clase o cada uno de los Threas se puede llevar una referencia distinta del singleton haciendo que trabajen con instancias diferentes.

¿Cómo se puede solucionar este problema?

Hay varias maneras de solucionarlo, la primera de todas sería usar un bloqueo para sincronizar el acceso a este recurso. Vamos a ver una serie de ejemplos y porque estos ejemplos están bien o mal implementados.

Utilizando bloqueos

   1: public class BadCacheManager
   2: {
   3:   private static BadCacheManager instance;
   4:   private static object syncRoot = new object();
   5:   public static BadCacheManager Instance
   6:   {
   7:       get
   8:       {
   9:           S0
  10:           if (instance == null)
  11:           {
  12:               S1
  13:               lock (syncRoot)
  14:               {
  15:                   instance = new BadCacheManager();
  16:               }
  17:           }
  18:           return instance;
  19:       }
  20:   }
  21:   private BadCacheManager()
  22:   {
  23:
  24:   }
  25: }

BadCacheManager: Mal

Esta implementacion no funcionaría porque puede darse la casualizad de que durante la primera comprobación (S0) y justo antes de que se instancie la clase (S1) puede haber una instrucción y puede darse la casualidad de que se interrumpa el thread (t0) justo en ese instante, lo que otro thread (t1) evaluaria S0 (true, es nulo) adquiriría el bloqueo pero esperaría (t1) porque el otro thread (t0) lo tiene asignado, así que t0 se despertaría crearia el objeto, después t1 haría lo mismo dando como resultado dos instancias. Además de todo esto no se sincroniza el almacenamiento de la variable instance con un memory barrier (fence) marcando la variable como volatile o usando Thread.MemoryBarrier().

   1: public class DoubleLockVolatileCacheManager
   2: {
   3:     private static volatile DoubleLockVolatileCacheManager instance;
   4:     private static object syncRoot = new object();
   5:     public static DoubleLockVolatileCacheManager Instance
   6:     {
   7:         get
   8:         {
   9:             if (instance == null)
  10:             {
  11:                 lock (syncRoot)
  12:                 {
  13:                     if (instance == null)
  14:                     {
  15:                         instance = new DoubleLockVolatileCacheManager();
  16:                     }
  17:                 }
  18:             }
  19:             return instance;
  20:         }
  21:     }
  22:     private DoubleLockVolatileCacheManager()
  23:     {
  24:
  25:     }
  26: }

DoubleLockVolatileCacheManager: Bien *

Esta implementación esta bien pero a medias, en la implementacion de .NET el CLR se asegura que independientemente del tipo de reordenacion del procesador, del modelo de memoria y de la atomicidad de las lecturas y escrituras siempre funciona, de hecho es lo que .net utiliza internamente para asegurarse que el constructor estatico (cctor) de un tipo solamente se ejecute una vez. Pero el modelo de memoria de .NET permite reordenaciones de lectura/escritura de variables no volatiles, así que habría que haber marcado la instancia como volatie o insertar un Thread.MemoryBarrier, aquí tenemos la implementacion correcta.

   1: public class DoubleLockCacheManager
   2: {
   3:    private static DoubleLockCacheManager instance;
   4:    private static object syncRoot = new object();
   5:    public static DoubleLockCacheManager Instance
   6:    {
   7:        get
   8:        {
   9:            if (instance == null)
  10:            {
  11:                lock (syncRoot)
  12:                {
  13:                    if (instance == null)
  14:                    {
  15:                        DoubleLockCacheManager tmp = new DoubleLockCacheManager();
  16:                        Thread.MemoryBarrier();
  17:                        instance = tmp;
  18:                    }
  19:                }
  20:            }
  21:            return instance;
  22:        }
  23:    }
  24:    private DoubleLockCacheManager()
  25:    {
  26:
  27:    }
  28: }
   1: public class BadLazy<T>
   2: {
   3:   private T internalValue;
   4:   private bool isInitialized;
   5:   private object syncRoot = new object();
   6:   private Func<T> factory;
   7:
   8:
   9:   public BadLazy(Func<T> factory)
  10:   {
  11:       this.factory = factory;
  12:   }
  13:
  14:   public T Value
  15:   {
  16:       get
  17:       {
  18:           lock (syncRoot)
  19:           {
  20:               if (!isInitialized)
  21:               {
  22:                   internalValue = factory();
  23:                   isInitialized = true;
  24:               }
  25:           }
  26:           return internalValue;
  27:       }
  28:   }
  29: }

Todos los ejemplos que hemos utilizado aquí utilizan lock (aka Monitor.Enter) para implementar un sistema de bloqueo en los recursos compartidos del Singleton, pero lo ideal para casi todos los casos es no utilizar bloqueos.

¿Cómo se puede implementar un algoritmo libre de bloqueos?, la respuesta está en la granularidad de la concurrencia, gruesa o fina. Nosotros queremos granularidad fina para hacer que los Threads estén el menos tiempo en un bloqueo haciendo así que todo el sistema responda mucho mejor. Una granularidad fina es mucho más complicada de implementar pero tiene un mejor rendimiento y respuesta del sistema porque hay menos contención.

Ahora vamos a ver como sería el Singleton perezoso sin bloqueos.

   1: public class Lazy<T> where T : class, new()
   2: {
   3:    private T value;
   4:    public T Value
   5:    {
   6:        get
   7:        {
   8:            if (value == null)
   9:            {
  10:                Interlocked.CompareExchange(ref value, new T(), null);
  11:            }
  12:            return value;
  13:        }
  14:    }
  15: }

Como se puede observar se ha simplificado mucho el código y ahora lo único que tenemos es un Interlocked.CompareExchange, en el que se compara el valor de primer argumento con el del último argumento y si son iguales entonces se establece en el primer argumento el valor de segundo parámetro, así que si nuestra instancia es nula entonces se crea la instancia y se establece. Lo interesante de esta forma de implementarlo es que no tenemos que preocuparnos por el modelo de memoria de .net por la reordenación de instrucciones ni por nada, ya que el Interlocked.CompareExchange es atómica a nivel de hardware, es decir nuestro procesador nos asegura que sea instrucción CMPXCHG es atómica.

Como se puede observar la granularidad de este algoritmo es muy fina porque solamente se bloquea en el momento justo de establecer la variable.

Un ejemplo de una granularidad fina en el uso de los bloqueos la podemos observar en la implementación de este diccionario concurrente.

   1: public class ConcurrentDictionary<TKey, TValue> : IDictionary<TKey, TValue>, ICollection<KeyValuePair<TKey, TValue>>, IEnumerable<KeyValuePair<TKey, TValue>>
   2: {
   3:     private ReaderWriterLock rw = new ReaderWriterLock();
   4:     private Dictionary<TKey, TValue> dic = new Dictionary<TKey, TValue>();
   5:     private int timeout = -1;
   6:     public void Add(TKey key, TValue value)
   7:     {
   8:         rw.AcquireWriterLock(timeout);
   9:         try
  10:         {
  11:             if (!dic.ContainsKey(key))
  12:             {
  13:                 dic.Add(key, value);
  14:             }
  15:         }
  16:         finally
  17:         {
  18:             rw.ReleaseWriterLock();
  19:         }
  20:     }
  21:
  22:     public bool ContainsKey(TKey key)
  23:     {
  24:         bool res = false;
  25:         rw.AcquireReaderLock(timeout);
  26:         try
  27:         {
  28:             res = dic.ContainsKey(key);
  29:         }
  30:         finally
  31:         {
  32:             rw.ReleaseReaderLock();
  33:         }
  34:         return res;
  35:     }
  36:
  37:     public ICollection<TKey> Keys
  38:     {
  39:         get
  40:         {
  41:             ICollection<TKey> res = null;
  42:             rw.AcquireReaderLock(timeout);
  43:             try
  44:             {
  45:                 Dictionary<TKey, TValue> tmp = new Dictionary<TKey, TValue>(dic);
  46:                 res = tmp.Keys;
  47:             }
  48:             finally
  49:             {
  50:                 rw.ReleaseReaderLock();
  51:             }
  52:             return res;
  53:         }
  54:     }
  55:
  56:     public bool Remove(TKey key)
  57:     {
  58:         bool res = false;
  59:         rw.AcquireWriterLock(timeout);
  60:         try
  61:         {
  62:             res = dic.Remove(key);
  63:         }
  64:         finally
  65:         {
  66:             rw.ReleaseWriterLock();
  67:         }
  68:         return res;
  69:     }
  70:
  71:     public bool TryGetValue(TKey key, out TValue value)
  72:     {
  73:         bool res = false;
  74:         rw.AcquireWriterLock(timeout);
  75:         try
  76:         {
  77:             res = dic.TryGetValue(key, out value);
  78:         }
  79:         finally
  80:         {
  81:             rw.ReleaseWriterLock();
  82:         }
  83:         return res;
  84:     }
  85:
  86:     public ICollection<TValue> Values
  87:     {
  88:         get
  89:         {
  90:             ICollection<TValue> res = null;
  91:             rw.AcquireReaderLock(timeout);
  92:             try
  93:             {
  94:                 Dictionary<TKey, TValue> tmp = new Dictionary<TKey, TValue>(dic);
  95:                 res = tmp.Values;
  96:             }
  97:             finally
  98:             {
  99:                 rw.ReleaseReaderLock();
 100:             }
 101:             return res;
 102:         }
 103:     }
 104:
 105:     public TValue this[TKey key]
 106:     {
 107:         get
 108:         {
 109:             TValue res = default(TValue);
 110:             rw.AcquireReaderLock(timeout);
 111:             try
 112:             {
 113:                 if (dic.ContainsKey(key))
 114:                 {
 115:                     res = dic[key];
 116:                 }
 117:             }
 118:             finally
 119:             {
 120:                 rw.ReleaseWriterLock();
 121:             }
 122:             return res;
 123:         }
 124:         set
 125:         {
 126:             if (ContainsKey(key))
 127:             {
 128:                 rw.AcquireWriterLock(timeout);
 129:                 try
 130:                 {
 131:                     dic[key] = value;
 132:                 }
 133:                 finally
 134:                 {
 135:                     rw.ReleaseWriterLock();
 136:                 }
 137:             }
 138:         }
 139:     }
 140:
 141:
 142:
 143:     public void Add(KeyValuePair<TKey, TValue> item)
 144:     {
 145:         Add(item.Key, item.Value);
 146:     }
 147:
 148:     public void Clear()
 149:     {
 150:         rw.AcquireWriterLock(timeout);
 151:         try
 152:         {
 153:             dic.Clear();
 154:         }
 155:         finally
 156:         {
 157:             rw.ReleaseWriterLock();
 158:         }
 159:     }
 160:
 161:     public bool Contains(KeyValuePair<TKey, TValue> item)
 162:     {
 163:         return ContainsKey(item.Key);
 164:     }
 165:
 166:     public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
 167:     {
 168:         throw new NotImplementedException();
 169:     }
 170:
 171:     public int Count
 172:     {
 173:         get
 174:         {
 175:             int count = -1;
 176:             rw.AcquireReaderLock(timeout);
 177:             try
 178:             {
 179:                 count = dic.Count;
 180:             }
 181:             finally
 182:             {
 183:                 rw.ReleaseReaderLock();
 184:             }
 185:             return count;
 186:         }
 187:     }
 188:
 189:     public bool IsReadOnly
 190:     {
 191:         get { return false; }
 192:     }
 193:
 194:     public bool Remove(KeyValuePair<TKey, TValue> item)
 195:     {
 196:         bool res = false;
 197:         if (ContainsKey(item.Key))
 198:         {
 199:             Remove(item.Key);
 200:         }
 201:         return res;
 202:     }
 203:
 204:
 205:
 206:     public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
 207:     {
 208:         IEnumerator<KeyValuePair<TKey, TValue>> res = null;
 209:         rw.AcquireReaderLock(timeout);
 210:         try
 211:         {
 212:             Dictionary<TKey, TValue> tmp = new Dictionary<TKey, TValue>(dic);
 213:             res = tmp.GetEnumerator();
 214:         }
 215:         finally
 216:         {
 217:             rw.ReleaseReaderLock();
 218:         }
 219:         return res;
 220:     }
 221:
 222:
 223:
 224:     IEnumerator IEnumerable.GetEnumerator()
 225:     {
 226:         return null;
 227:     }
 228:
 229:
 230:
 231:     IEnumerator<KeyValuePair<TKey, TValue>> IEnumerable<KeyValuePair<TKey, TValue>>.GetEnumerator()
 232:     {
 233:         return null;
 234:     }
 235:
 236:
 237: }

En el que únicamente cuando se realizan operaciones en el diccionario se intenta bloquear lo menos posible además de que no se utiliza lock (aka Monitor.Enter) sino ReaderWriterLock que permite tener varios lectores y un solo escritor concurrentemente. Se podría haber utilizado ReaderWriterLockSlim que mejora sensiblemente el rendimiento pero esta implementación era para .NET 2.0 y ReaderWriterLockSlim solo funciona con .NET 3.5 además de que en Windows Vista se ha mejorado la implantación nativa.

Os podeis descargar el codigo de ejemplo de aquí

http://www.luisguerrero.net/downloads/Singleton.zip

Espero que os sirva de ayuda.

Saludos. Luis.

¿Te ha gustado este artículo?

¡Considera subscribirte al RSS para estar al día!

Tagged as: , , , Leave a comment