Lazy initialization and double-checked locking

Lazy initialization

在程序设计中，惰性初始是一种拖延战术。在第一次需求出现以前，先延迟创建物件、计算值或其他昂贵程序。

import java.util.*;
 
public class Fruit
{
    private static final Map<String,Fruit> types = new HashMap<String,Fruit>();
    private final String type;
 
    // using a private constructor to force use of the factory method.
    private Fruit(String type) {
      this.type = type;
    }
 
    /**
     * Lazy Factory method, gets the Fruit instance associated with a
     * certain type. Instantiates new ones as needed.
     * @param type Any string that describes a fruit type, e.g. "apple"
     * @return The Fruit instance associated with that type.
     */
    public static synchronized Fruit getFruit(String type) {
      if(!types.containsKey(type))
        types.put(type, new Fruit(type)); // Lazy initialization
      return types.get(type);
    }
}

class Fruit:
    def __init__(self, type):
        self.type = type
 
class Fruits:
    def __init__(self):
        self.types = {}
 
    def get_fruit(self, type):
        if type not in self.types:
            self.types[type] = Fruit(type)
 
        return self.types[type]
 
if __name__ == '__main__':
    fruits = Fruits()
    print fruits.get_fruit('Apple')
    print fruits.get_fruit('Lime’)

Double-checked locking

In software engineering, double-checked locking (also known as “double-checked locking optimization”) is a software design pattern used to reduce the overhead of acquiring a lock by first testing the locking criterion (the “lock hint”) without actually acquiring the lock. Only if the locking criterion check indicates that locking is required does the actual locking logic proceed.

It is typically used to reduce locking overhead when implementing “lazy initialization” in a multi-threaded environment, especially as part of the Singleton pattern. Lazy initialization avoids initializing a value until the first time it is accessed.

// Single-threaded version
class Foo {
    private Helper helper;
    public Helper getHelper() {
        if (helper == null) {
            helper = new Helper();
        }
        return helper;
    }
 
    // other functions and members...
}

多线程情况下上述例子就无法工作了。这时候可以通过加锁来处理。

// Correct but possibly expensive multithreaded version
class Foo {
    private Helper helper;
    public synchronized Helper getHelper() {
        if (helper == null) {
            helper = new Helper();
        }
        return helper;
    }
 
    // other functions and members...
}

但每次调用方法的时候都要请求和释放锁，这看起来没必要，而且会很大程度的降低性能。许多开发者尝试用下面的方法来优化这个问题：

检查变量是否初始化（没有用到锁哦），如果初始化了，立即返回。
获得锁
双重检查变量是否已经被初始化：如果另外一个线程首先初始化，它可能已经完成了初始化。如果是这样，返回初始化后的变量。
反之，初始化然后返回变量

// Broken multithreaded version
// "Double-Checked Locking" idiom
class Foo {
    private Helper helper;
    public Helper getHelper() {
        if (helper == null) {
            synchronized(this) {
                if (helper == null) {
                    helper = new Helper();
                }
            }
        }
        return helper;
    }
 
    // other functions and members...
}

直觉上，这个算法看起来像是该问题的有效解决方案。然而，这一技术还有许多需要避免的细微问题。例如，考虑下面的事件序列：

线程A发现变量没有被初始化, 然后它获取锁并开始变量的初始化。
由于某些编程语言的语义，编译器生成的代码允许在线程A执行完变量的初始化之前，更新变量并将其指向部分初始化的对象。
线程B发现共享变量已经被初始化，并返回变量。由于线程B确信变量已被初始化，它没有获取锁。如果在A完成初始化之前共享变量对B可见（这是由于A没有完成初始化或者因为一些初始化的值还没有穿过B使用的内存(缓存一致性)），程序很可能会崩溃。

在J2SE 1.4或更早的版本中使用双重检查锁有潜在的危险，有时会正常工作：区分正确实现和有小问题的实现是很困难的。取决于编译器，线程的调度和其他并发系统活动，不正确的实现双重检查锁导致的异常结果可能会间歇性出现。重现异常是十分困难的。

在J2SE 5.0中，这一问题被修正了。volatile关键字保证多个线程可以正确处理单件实例。描述了这一新的语言特性:

// Works with acquire/release semantics for volatile
// Broken under Java 1.4 and earlier semantics for volatile
class Foo {
    private volatile Helper helper = null;
    public Helper getHelper() {
        Helper result = helper;
        if (result == null) {
            synchronized(this) {
                result = helper;
                if (result == null) {
                    helper = result = new Helper();
                }
            }
        }
        return result;
    }
 
    // other functions and members...
}

注意局部变量result的使用看起来是不必要的。对于某些版本的Java虚拟机，这会使代码提速25%，而对其他的版本则无关痛痒。

如果helper对象是静态的(每个类只有一个), 可以使用双重检查锁的替代模式惰性初始化模式。

// Correct lazy initialization in Java
@ThreadSafe
class Foo {
    private static class HelperHolder {
       public static Helper helper = new Helper();
    }
 
    public static Helper getHelper() {
        return HelperHolder.helper;
    }
}

这是因为内部类直到他们被引用时才会加载。

Java 5中的final语义可以不使用volatile关键字实现安全的创建对象:

public class FinalWrapper<T> {
    public final T value;
    public FinalWrapper(T value) {
        this.value = value;
    }
}
 
public class Foo {
   private FinalWrapper<Helper> helperWrapper = null;
 
   public Helper getHelper() {
      FinalWrapper<Helper> wrapper = helperWrapper;
 
      if (wrapper == null) {
          synchronized(this) {
              if (helperWrapper == null) {
                  helperWrapper = new FinalWrapper<Helper>(new Helper());
              }
              wrapper = helperWrapper;
          }
      }
      return wrapper.value;
   }
}

为了正确性，局部变量wrapper是必须的。这一实现的性能不一定比使用volatile的性能更高。

Effective Java中第48条：对共享可变数据的同步访问

synchronized关键字可以保证在同一时刻，只有一个线程在执行一条语句，或者一段代码块。

同步不仅可以阻止一个线程看到对象处于不一致的状态中，它还可以保证通过一系列看似顺序执行的状态转变序列，对象从一种一致的状态变迁到另一种一致的状态。

Java语言保证读或者写一个变量是原子的（atomic），除非这个变量的类型为long或double。换句话说，读入一个非long或double类型的变量，可以保证返回的值一定是某个线程保存在该变量中的，即使多个线程在没有同步的情况下并发地改变这个变量，也是如此。

为了提高性能，在读或写原子数据的时候，如果避免使用同步，这是非常危险的。

为了在线程之间可靠地通信，以及为了互斥访问，同步时需要的。

volatile修饰符可以保证任何一个线程在读取一个域的时候都将会看到最近刚刚写入的值。

使用延迟初始化的双重检查

// The double-check idiom for lazy initialization - broken
private static Foo foo = null;

public static Foo getFoo(){
     if(foo == null) {
          sychronized(Foo.class) {
               if (foo == null)
                    foo = new Foo();
          }
     }
     return foo;
}

该模式的思想是：在域被初始化后，再要访问该域时无需同步，从而避免多数情形下的同步开销。同步只是被用来避免多个线程对该域做初始化。这种模式保证了该域将至多被初始化一次，所有调用getFoo的线程都将会得到正确的对象引用值。不幸的是，该对象引用并不能保证可以正常地工作。如果一个线程在不使用同步的情况下读入该引用，并调用该对象上的方法，那么这个方法可能会看到对象被部分初始化的状态，从而导致灾难性的失败。

一般情况下，双重检查模型并不能正确地工作。

下面有几种方法来修正这个问题。最容易的办法是完全省区迟缓初始化：

// Normal static initialization (not lazy)
private static final Foo foo = new Foo();

public static Foo getFoo(){
     return foo;
}

//Properly synchronised lay initialization
private static Foo foo = null;

public static sychronized Foo getFoo() {
     if (foo == null)
          foo = new Foo();
     return foo;
}

这个方法可以保证正常工作，但是它会招致在每个调用上的同步开销。

如果一个静态域的初始化非常昂贵，并且它也不见得会被调用到，但一旦需要则会被充分地使用，那么，在这样的情况下，按需初始化容器类（initialize-on-demand holder class）模式是非常合适的。下面的代码演示了这种模式：

// The initialize-on-demand holder class idiom
private static class FooHolder {
     static final Foo foo = new Foo();
}

public static Foo getFoo(){
     return FooHolder.foo;
}

该模式充分利用了Java语言中“只有当一个类被用到的时候它才被初始化”。

这种模式的缺点在于，它不能用于实例域，只能用于静态域。

简而言之，无论何时当多个线程共享可变数据的时候，每个读或写数据的线程必须获得一把锁。

非原子的64位操作

当线程在没有同步的情况下读取变量时，可能会得到一个失效值，但至少这个值是由之前某个线程设置的值，而不是一个随机值。这种安全性保证称为最低安全性（out-of-thin-air-safety)。

最低安全性适用于绝大多数变量，但是存在一个例外：非volatile类型的64位数值变量（double和long）。Java内存模型要求，变量的读取操作和写入操作都必须是原子操作，但对于非volatile类型的long和double变量，JVM允许将64位的读操作或写操作分解为两个32位的操作。当读取一个非volatile类型的long变量时，如果对该变量的读操作和写操作在不同线程中执行，那么很可能会读取到某个值的高32位和另一个值的低32位。因此，即使不考虑实效数据问题，在多线程程序中使用共享且可变的long或double等类型的变量也是不安全的。除非用关键字volatile来声明它们，或者用锁保护起来。

Volatile变量

Java语言提供了一种稍弱的同步机制，即volatile变量，用来确保将变量的更新操作通知到其他线程。当把变量声明为volatile类型后，编译器与运行时都会注意到这个变量是共享的，因此不会将该变量上的操作与其他内存操作一起重排序。volatile变量不会被缓存在寄存器或者对其他处理器不可见的地方，因此在读取volatile类型的变量时总会返回最新写入的值。

在访问volatile变量时不会执行加锁操作，因此也就不会使执行线程阻塞，因此volatile变量时一种比synchronized关键字更轻量级的同步机制。

从内存可见性的角度来看，写入volatile变量相当于退出同步代码块，而不读取volatile变量相当于进入同步代码块。

仅当volatile变量能简化代码的实现以及对同步策略的验证时，才应该使用它们。如果在验证正确性时需要对可见性进行复杂的判断，那么就不要使用volatile变量。volatile变量的正确使用方式包括：确保它们自身状态的可见性，确保它们所引用对象的状态的可见性，以及标识一些重要的程序生命周期事件的发生（例如，初始化或关闭）。

加锁机制既可以确保可见性又可以确保原子性，而volatile变量只能确保可见性。

当且仅当满足以下所有条件时，才应该使用volatile变量：

当变量的写入操作不依赖变量的当前值，或者你能确保只有单个线程更新变量的值。
该变量不会与其他状态变量一起纳入不变性条件中
在访问变量时不需要加锁

Tornado中的double-checked locking

@staticmethod
def instance():
    """Returns a global `IOLoop` instance.
 
    Most applications have a single, global `IOLoop` running on the
    main thread.  Use this method to get this instance from
    another thread.  In most other cases, it is better to use `current()`
    to get the current thread's `IOLoop`.
    """
    if not hasattr(IOLoop, "_instance"):
        with IOLoop._instance_lock:
            if not hasattr(IOLoop, "_instance"):
                # New instance after double check
                IOLoop._instance = IOLoop()
    return IOLoop._instance