花开花落

Lock-free 算法通常比基于锁的算法要好：

• 从其定义来看，它们是 wait-free 的，可以确保线程永远不会阻塞。
• 状态转变是原子性的，以至于在任何点失败都不会恶化数据结构。
• 因为线程永远不会阻塞，所以当同步的细粒度是单一原子写或比较交换时，它们通常可以带来更高的吞吐量。
• 在某些情况下，lock-free 算法会有更少的同步写操作（比如 interlocked 操作），因此纯粹从性能来看，它可能更便宜。

但是 lock-freedom 并不是万能药。下面是一些很明显的不利因素：

• 乐观的并发使用会对 hot data structures 导致 livelock。
• 代码需要大量困难的测试。通常其正确性取决于对目标机器内存模型的正确解释。
• 基于众多原因，lock-free 代码很难编写和维护。

预备知识

任何支持多线程的系统都需要一个规范来描述多线程交互时如何精确的访问内存数据状态，我们称其为内存模型(Memory Model)。最简单的模型就是图1所展示的序列一致性内存模型(Sequential Consistency Memory Model)。在这个模型中，内存独立于任何使用它们的进程(线程)。内存通过内存控制器连接到每个线程，而内存控制器则会反馈每个线程的读写请求。来自单线程的读写请求会精确的按照线程的指定次序到达内存，然而它们也可能会和其他线程的读写请求按照一个未指定的方式交错进行。

图1 Sequential Consistency Memory Model

在图1所示的例子中，Value变量需要初始化，而Inited标志则用来表明其是否已被初始化。Value和Inited首先都被设置为0。线程1首先初始化Value(Value被设置成5)，然后设置Inited为1表明Value已被初始化了。线程2把这些值读进寄存器Rv和Ri。在一个依赖于顺序的(sequential)程序中，不可能会有当Ri为1(说明Value已被初始化了)时，Rv还是0(Value未初始化)的情况发生。这归因于Sequential Consistency Memory Model。图2中的表格枚举了序列一致性内存所允许的所有6种合法排列，从中我们可以看出Ri和Rv最终的值是什么。没有一种情况当Ri非零时，Rv为零。

图2 Possible Permutations of Memory Requests

如前面的例子所示，序列一致性是很容易想到的一种模型。依赖于顺序的程序的一些概念都可以在其上应用。坦白说，它也很自然的在单处理器机器上获得实现。大多数程序员都对这种内存模型相当熟悉。不幸的是，对于真正的多处理器机器，通过内存硬件来高效的实现这种模型，非常受限制。并且，没有商业多处理器机器符合这种模型。

典型的多处理器机器内存系统看起来很像图3。每一个处理器都有一个相关的非常快速的小型缓存来记忆最近访问的数据。除此之外，所有从处理器到内存的写操作都会有一个缓冲区，以便处理器可以在数据刷到以及缓存前可以继续下一个指令。我们可以在图3看到每个处理器至少会有一级或更多级的缓存。这些缓存每一级都会比前一级容量更大，但是速度更慢。最终数据会到达内存，这样数据就可以被其他处理器共享。这种架构会加速处理器，而且也意味着不再会有单一内存视图。现在一个处理器会在各级缓存针对特定内存位置存储一个值，同时其他处理器也缓存了相同内存位置的数据，但是这个数据可能是过期的老的数据。这就可能导致处理器的缓存内容不一致。

图3 Realistic Memory System

上述情况肯定不符合需要。如果我们拿它来用于线程间通信铁定引发问题。但是如果我们刷新每一个线程的缓存数据来作为通信机制的一部分，系统就会可靠了。这样的系统是高效的，因为保持缓存同步的开销只会在线程使用内存通信时才会产生，这只占所有内存访问的很小的一部分。

图3所示的就是真实的内存系统，它并不符合序列一致性内存模型。因此我们就要创建一种内存模型来解决这样的内存系统所带来的问题。我们要做的就是让处理器互相“看到”所有移动内存存取。

图4 Initial Memory State

举个例子，考虑下Inited-Value示例运行在如图4所示的多处理器机器上会发生什么。注意，这里的缓存是简化的。在这个版本的系统里，主内存内的两个变量初始值都是0。处理器1的缓存现在是空的，而处理器2则已经读取Value的值(Inited还没读)到了它的本地缓存。如果我们以前读取过程序的其他数据，而Value又紧挨着这个数据的话，就有可能发生上述情况。

图5 Incoherent Caches

如果两个处理器均运行该程序的话，状态变化就如图5所示。不要考虑图5了，联系图4，现在我们把在主内存的数据Value设置成5，Inited则设置1。然而，由于缓存的原因，处理器2的内容不是我们所期望看到的。当处理器2读取Inited时，它没有在缓存中发现Inited的值，然后它看到其在主内存的值(Inited = 1)。当处理器2读取Value时，它在缓存中发现其值为过期的0。这其实是处理器2在早期读取的Value。这跟运行在序列一致性内存模型上的下列代码有着相同的行为：

CacheTemp = Inited
Rv = Value
Ri = CacheTemp

写操作跟读操作类似。

这种技术有三个优点。首先，它相对简单，不需要精确的详细描述硬件细节。其次，它可以让源代码回退到一个很简单易懂的风格。缓存读取可以比其真正需要时才读取更早的把值载入到一个临时变量。缓存写入则比写入最终位置要晚。最后，它可以应用于编译器优化中。

很明显，这种任意移动内存访问的能力会导致混乱。所以所有的实际内存模型有以下三个基本原则：

1. 当线程隔离运行时，行为不会改变。它的意思是，指定线程到指定位置的读或写操作不会通过相同的线程到相同位置的写操作。
2. 读操作在获得锁时，数据不能移动。
3. 写操作在释放锁时，数据不能移动。

这就是锁协议实际的意义。这个协议确保了当持有相关锁时，所有的线程共享，读/写内存访问。

有了这三个原则就使得所有遵循锁协议的程序在任何内存模型都有相同的行为。这是一个极有价值的属性。没有这些关于编译器或内存系统能重新排序读写的必要思考，我们要写一个正确的并发程序将会非常困难。

遵循锁协议的程序不必思考这些。一旦你不想遵循锁协议，那么就必须详细说明和考虑硬件或编译器的读写变换。

较宽松的模型：ECMA

你现在已经明白序列一致性内存模型非常受限，因为它不允许任何交互的读写操作。在Section 12, Partition I of the .NET Framework ECMA standard描述了一个较宽松的模型。这个模型把内存访问操作划分成原始内存访问和那些特别标记为“volatile”的访问。Volatile内存访问不能创建，删除或移动。原始内存访问不止受限于三个基本原则，同时也要遵循以下两个原则：

1. 在volatile读前，读操作和写操作都不能移动数据。
2. 在volatile写后，读操作和写操作都不能移动数据。

这给了编译器和硬件相当的优化自由。它们只需要关心通过锁和Volatile访问的边界格式。对于没有使用锁或Volatile的程序片段，可以做任意的合法优化。这也意味着内存系统只需要在锁或Volatile访问时做相关的昂贵缓存失效，然后刷新即可。这个模型非常高效，但是需要程序在使用Low-Lock技术时，遵循锁协议或显式标记volatile。

健壮模型 1： x86 行为

不幸的是，正确遵循锁协议的程序还有更多例外。当设计基于x86架构的多处理器系统时，设计者需要一个内存模型来使得大多数程序可以正常工作，同时也允许硬件合理有效。规范需要单处理器写操作相对其他写操作保持有序，而读操作则不受限。

不幸的是，如果读操作不受限，写操作有序的保证等于什么也不做。因此，x86架构没有提供比ECMA模型更强的保证。

然而，我相信，x86实际实现的内存模型和文档上描述的有些微不同。因为在我的试验中正确预测行为这个模型从未失败，而且它跟公开已知的硬件如何工作完全一致，但是却不是官方规范。新的处理器可能会打破该规范。在这个模型中，除了三个基本内存模型规则，这些规则也起作用：

1. A write can only move later in time.
2. A write cannot move past another write from the same thread.
3. A write cannot move past a read from the same thread to the same location.
4. A read can only move by going later in time to stay after a write to keep from breaking rule 3 as that write moves later in time.

这个模型对于带有写缓冲队列和窥探读操作的系统很有效。写数据到内存时，不是立即写到内存，而是按序放入队列里。这些写操作或许会延迟，但是却保持了有序。高效率的读操作不会移动数据，除非允许窥探写操作队列。每一个读操作都会窥探写缓冲区来查看是否处理器最近写进了要读取的值，如果发现就会使用写缓冲区的值。因为逻辑上讲写缓冲区的写操作只在实体在刷到主内存时才会发生，高效率的读取操作也会延迟到那时才会获取其值。规则4特别允许了这种行为。

健壮模型 2: .NET Framework 2.0

尽管.NET Framework的ECMA模型规范并不是那么健壮，但是运行于x86机器上的.NET Framework 1.x运行时的实现模型却跟x86模型非常接近（源于JIT或JIT编译器优化）。在版本2.0时，这个模型在Intel IA-64处理器上却遇到了问题。那些依赖于x86实现的客户程序在类似IA-64平台上运行时会有问题。结果就导致了.NET Framework 2.0运行时内存模型，它的规则如下：

1. All the rules that are contained in the ECMA model, in particular the three fundamental memory model rules as well as the ECMA rules for volatile.
2. Reads and writes cannot be introduced.
3. A read can only be removed if it is adjacent to another read to the same location from the same thread. A write can only be removed if it is adjacent to another write to the same location from the same thread. Rule 5 can be used to make reads or writes adjacent before applying this rule.
4. Writes cannot move past other writes from the same thread.
5. Reads can only move earlier in time, but never past a write to the same memory location from the same thread.

同x86模型一样的是写操作被严格限制了，不一样的则是读操作可以移动数据和可以被消除。因为重新在内存获取值和在low-lock代码内存中可以被改变，所以有了规则2.最后的规则似乎是多余的，但是如果允许通过写到相同位置就会改变要读取的值，这也就改变了序列行为。如果读取的值真正被使用了，这就会发生。这个规则更有技术性，而且它被特别添加进来是为了使得通用的延迟初始化模式在该模型中合法。

Lock-Free

对于编写lock-free代码来说，上面的描述并没有详细的涉及，下面我们来描述一下其规则：

1. Data dependence among loads and stores is never violated.
2. All stores have release semantics, i.e. no load or store may move after one.
3. All volatile loads are acquire, i.e. no load or store may move before one.
4. No loads and stores may ever cross a full-barrier (e.g. Thread.MemoryBarrier, lock acquire, Interlocked.Exchange, Interlocked.CompareExchange, etc.).
5. Loads and stores to the heap may never be introduced.
6. Loads and stores may only be deleted when coalescing adjacent loads and stores from/to the same location.

注意从定义来看，非易失性加载不需要请求拥有任何一种与其关联的内存屏障。所以加载可以被自由重新排序，写操作也可以在其后移动数据（由于规则2）。在这个模型里，如果你真的需要规则4所提供的完全内存屏障的话，就可以防止紧跟在易失性加载后重新排序。没有屏障，指令就会重新排序。

参考：

Understand the Impact of Low-Lock Techniques in Multithreaded Apps

Joe Duffy’s Weblog

Singularity是一个新的操作系统，它被用来开发成为更加可信赖系统和应用软件的基础平台。Singularity利用现代编程语言和工具的进步来创建一种环境，使得软件更容易被正确构建，使得程序行为更容易被验证，也能容忍运行时失败。

Singularity很关键的一方面是基于软件隔离进程（SIP）的扩展模型。SIP封装了程序或系统的一部分，并且提供了信息隐藏，失败隔离和强壮的接口。SIP贯穿于整个操作系统和应用程序软件中。我们相信，构建于这个抽象概念上的系统将会导致更加可信赖的软件平台。

SIP实际上就是Singularity操作系统的进程。所有内核之外的代码都运行在SIP中。SIP在许多方面都不同于常规操作系统的进程概念：

• SIP是封闭的对象空间，而不是地址空间。两个Singularity进程不能同时访问一个对象。进程间通信则互斥转移数据的所有权。
• SIP是封闭的代码空间。进程不能动态加载或生成代码。
• SIP并不依赖内存管理硬件来达到隔离的目的。多个SIP均在同一物理或虚拟地址空间中。
• SIP间通信是通过双向作用的，强类型的，高阶次序的管道来完成的。管道不仅说明了双方通信协议，还指出了传输的值和双方都是经过验证的。
• 创建SIP开销并不大，而且在SIP间通信也是低负载。低开销便会使得把SIP作为良好细粒度和扩展的机制可行。
• 我们通过操作系统来创建和结束SIP，这样在终止SIP时，SIP的资源也能被有效收回。
• SIP独立运行，即使有不同的数据布局，运行时系统和垃圾收集。

SIP不止可以用来封装应用程序扩展，还可以用来作为保护和扩展的单独机制，来替代常规的进程和动态代码加载双重机制。如此一来，Singularity就只需要一个错误恢复模型，一个通信机制，一个安全策略和一个编程模型，而不是当前系统的层层多余机制和政策。Singularity的一个很重要的实验就是使用SIP来构造整个操作系统以及证明这个系统比常规系统更加可信赖。

Singularity内核几乎全部由安全代码组成。其余的部分则运行在SIP中，只由经过验证的安全代码组成，包括所有的设备驱动，系统进程和应用程序。在所有非信任代码必须验证其安全的同时，部分Singularity内核和运行时系统（叫做trusted base，即信任基础）则没有验证其安全。语言安全性保护了来自于非信任代码的trusted base。

SIP的完整依赖于语言安全性和泛系统不变量，即进程不能引用另外一个进程的对象空间。

确保代码安全性是很明显的要点。就眼前来说，Singularity依赖于源代码和中间代码的编译器验证。未来，类型化汇编语言（Typed Assembly Language，即TAL）将允许Singularity来验证编译代码的安全性。TAL要求可运行的程序提供它类型安全性的凭据（这个对于安全语言来说，会通过编译器自动产生）。对于简单审核几千行代码来验证凭据是否正确，以及运行指令是否适合是一件非常简单的任务。那么这种端到端的验证策略便可以从Singularity的trusted base来剔除编译器。这个验证程序必须被仔细设计，实现和检验，但这些任务是可行的。这是由于它的尺寸和简易性。

独立于内存的不变量（the memory independence invariant，即禁止跨对象空间的指针）担当了几个用途。首先，通过隐藏实现的具体细节和预防指针指向已终结的进程，它增强了进程的数据抽象和失败隔离。其次，通过允许进程拥有不同的运行时系统和垃圾收集器，它减轻了运行无关的实现限制。再次，通过明确内存的进程所有权，它阐明了资源计数和回收。最后，通过消除操作多类型指针和地址空间的需要，它简化了内核接口。

该架构的主要难点在于通过消息传递的通信与直接共享数据相比缺乏灵活性。Singularity现在正通过有效的消息系统，编程语言扩展（基于管道的简洁明确的通信）和验证工具致力于解决这个问题。

欧几里德算法又称辗转相除法，它是用来求解最大公约数的。

今天有人问我辗转相除法，已经没有印象了，特意网络搜索了一番，纪念一番。

搜到的算法虽然正确，可惜做了不少无用功。现把其递归与非递归算法公布如下，其实其递归算法更加容易理解，而且是个尾递归，现代编译器都会对其做优化，跟非递归几乎没有差距，因为我们要求解的步骤并不多。

非递归算法

public long gcd(long a, long b)
{
    if( a < 0 ) a = -a;
    if( b < 0 ) b = -b; 

    if( b == 0) return a; 

    for( long c = a % b; c > 0; c = a % b)
    {
        a = b;
        b = c;
    }
    return b;
}

递归算法

public long gcd(long a, long b)
{
    if( a < 0 ) a = -a;
    if( b < 0 ) b = -b;
    if( b == 0) return a;
    else return gcd(b , a % b);
}

从目前掌握的资料来看,似乎只有D语言规范里稍稍提了一下D语言的内存模型,并没有深入描写.以下细节来自D 2.0语言运行时的实现代码,若以后运行时实现有所变更,请参考最新D运行时实现(所有代码均参考DMD的实现,GDC应该与其差别不大).

D主要有三种分配内存的途径.

• 静态数据,分配在默认数据段上.
• 堆栈数据,分配在线程堆栈上.
• 垃圾收集数据,动态分配在GC Heap上.

前面的两种与C/C++没什么区别.我们主要讨论第三种.

先来看看C/C++的内存管理模式.

1. 首先我们会为某个对象或类型分配内存.
2. 初始化上一步所得的内存.
3. 通过访问对象或类型成员来使用资源.
4. 销毁资源状态,执行资源清理工作.
5. 释放内存.

这种模式看起来相当的简单,但是却是导致很多问题的根源.想想有多少次我们忘记了释放无用的内存.想想有多少次调试的时候,内存问题是浪费我们时间的最大元凶.

GC正是为了解决该问题而产生的.它接管了上述步骤的第五步.对于一些本地资源(比如文件,数据库连接,套接字,同步对象,位图,图标等),通常在其对象的内存即将被回收时,必须执行一些资源清理工作.

下面来探讨一下D语言的GC内存分配和资源初始化.所有继承自Object的对象均在GC Heap上分配,此外还有动态数组.

D运行时内部有一个GC类.当应用程序的进程完成初始化后,GC也跟着初始化.GC内部会保留一块连续的地址空间,这段空间最初并不对应任何物理内存.该地址空间即为GC Heap.GC Heap上维护着一个指针,该指针表示下一个新建对象分配时在GC Heap中所处的位置.开始时,该指针被设置为保留地址空间的基地址.

当我们new一个对象时,D运行时会调用Object _d_newclass(ClassInfo ci)函数来创建一个新的对象.至于该函数实现细节,因为没有找到相关代码,所以无法具体描述.我们可以猜测其实现细节如下:

1. 计算类型所需要的字节数.此外,应该还有相关的一些额外开销所需要的字节数.这些额外开销应该包含有一个类型对象指针和一个同步索引块(该同步索引块会在后面详细解说).
2. D运行时检查保留地址空间是否满足分配新对象所需要的字节数.如果需要则commit物理内存.如果GC Heap中还有足够的剩余空间,那么对象将被分配在GC内部维护指针所指示的地方,并且所分配的地址空间中的字节被清零.接着,调用类型的实例构造器返回对象的内存地址(GC内部维护的指针会传递给this参数,而类型的静态构造函数会在main()函数前调用完毕).而在new返回对象的地址之前,GC内部维护的指针会越过对象所处的内存区域,并指示出下一个新建对象在GC Heap中的地址.

这与C运行时库中的堆分配内存有着本质的区别.这样的内存分配方式使得分配对象的速度相当快,几乎可以与在线程堆栈中分配对象一样快!

接下来我们来看一下D语言中GC是如何工作的.

每个应用程序都有一组root.当GC开始执行时,它假设GC Heap中所有的对象都是垃圾.这样GC会查找所有的root(比如静态字段,方法参数,局部变量,CPU寄存器).如果发现root引用了一个对象,那么就mark它.接着GC继续查找,如果GC试图将一个先前已经标记过的对象再次mark时,它会停止该对象标记的路径方向上的遍历活动.这种行为有两个目的.首先,可以避免GC多次遍历;其次,如果对象之间出现了循环引用,可以避免陷入无限循环.

GC一旦检查完所有的root,便会回收那些未被mark的对象内存.接下来就到了压缩阶段.GC可能会压缩内存,也可能不会.这取决于找到的内存块容量.当GC找到比较大的连续内存块时,会把内存中的一些非垃圾对象搬移到这些连续内存块以压缩GC Heap.

显然,搬移内存中的对象将使所有所有包含这些对象指针的变量和CPU寄存器变得无效.因此,GC需要重新访问所有的root,并修改他们以使其指向这些对象的新内存位置.另外,如果对象包含有指向另一移动过的对象的字段,那么GC也会负责矫正这些字段.在GC Heap中的内存被压缩之后,GC内部维护的指针将被设置为指向最后一个非垃圾对象之后.

垃圾收集会给应用程序带来相当的性能开销,这也是使用GC时主要的负面影响.所以,GC会有一些特殊的设计来大幅提高GC的性能.D语言的GC是个基于代的垃圾收集器.引入代的唯一目的就是为了提高GC的性能.

前面讲到在创建新对象时,会创建一个同步索引块.它的目的是为了线程同步.当我们使用synchronized来创建线程安全的程序时,D运行时会把通过该同步索引块关联到一个同步锁.Windows下会关联到一个CRITICAL_SECTION,Linux则关联到一个pthread_mutex_t.这个不能用于多进程同步.D语言的GC实现了多线程安全.

此外,D语言的析构函数不表示确定性析构,但是通过delete表达式却实现了确定性析构的效果.当一些昂贵的资源需要及时析构时,采取这种方式是有效的.大多数的资源交给GC来回收即可.

唯一担心的是这种方式的滥用,因为确定性析构很可能会造成应用程序性能的下降.这会加大GC的压力,使得GC频繁的进行垃圾回收.建议采用.NET的终结模式.