Linux的Spinlock在MIPS多核处理器中的设计与实现

Linux的Spinlock在MIPS多核处理器中的设计与实现

2008年08月03日 16:00 来源：ChinaUnix文档频道 作者：HonestQiao 编辑：周荣茂

级别： 初级

赵 昊翔 ([e-mail]), 工程师

2008 年 8 月 04 日

Spinlock 在 Linux 中被广泛应用于解决多核处理器之间访问共享资源的互斥问题，本文以 MIPS 多核处理器为例，介绍了 Spinlock 的设计与实现，以及 Spinlock 的不足与扩展。

引言

随着科技的发展，尤其是在嵌入式领域，高性能、低功耗的处理器成为众多厂商追逐的目标，但是由于技术和工艺的瓶颈，试图在单核处理器上达到这样的目标变得越发困难，于是人们提出了多核处理器的概念。多核处理器的核心思想是一个处理器中包含若干个核（或线程），所有核（或线程）之间共享 IO、Cache、内存等资源，对于这些资源的使用和分配由硬件来完成，用户无需关注细节，因此每个核（或线程）对于用户来说就好像一个独立的虚拟 CPU，从用户角度来看，这个虚拟 CPU 独占所有的外设资源。

目前比较流行的多核处理器的架构有下面几种：

（1）SMP（Symmetric Multi-Processor）

这种架构的处理器由多个核组成，每个核有自己独立的 Cache，所有核共享内存和 IO。

（2）SMT（Symmetric Multi-Thread）

这种架构的处理器的每个核由多个线程组成（此处的线程指的硬件线程，而不是我们所说的操作系统的线程概念），每个核下的所有线程共享寄存器、ALU（CPU 运算单元）、Cache、内存、IO 等资源，线程之于用户也像一个虚拟的 CPU。这种架构的最大优势在于线程和线程之间的切换很快，通常一个时钟周期内就能完成。

（3）NUMA（Non-Uniform Memory Access）

这种架构和前面两种的区别在于它不是简单的一个处理器，而是一个由多个处理器组成的系统，每个处理器作为一个结点在该系统中存在。对于内存、IO 等资源所有结点也是共享的。

目前比较流行的处理器架构大多都推出了多核处理器的产品，比如 Intel 的 X86 双核处理器、Freescale 的 PPC 多核处理器、SUN 的 SPARC 多核处理器、RMI 和 Cavium 的 MIPS 多核处理器等。

MIPS 这种架构诞生于 Standford 大学，它的名字含义有双重意义，一是 “Microcomputer without Inter-locked Pipeline Stages”，另一种是 “Millions of Instructions Per Second”，它设计思想的核心是采用多级指令流水线技术达到高效的处理速度，目前比较常用的 MIPS 采用5级流水线的技术。因其性能高效、结构简单，MIPS 被誉为 RISC（Reduced Instruction Set Computing） 家族中最优美的一款处理器架构。基于 MIPS 的多核处理器因为其低功耗、高性能从而在嵌入式市场得到了广泛的应用。

针对上述这些多核处理器的特点，Linux 提出了 Multi-Processing 的概念，它的调度器可以将操作系统的线程均分到各个核（或硬件线程）上去执行，以此达到并行计算的目的，从而也可以极大地提高系统的性能。

Spinlock 的思想

Linux 在推出了 Multi-Processing 之后，多核处理器的并行处理的能力得到了极大的发挥，但是这同时也带来了一个问题，并行执行势必就存在多个核同时访问共享资源的情况，如何能够保证一个核在访问共享资源时，该共享资源不会被其它核所改写呢？

我们没有方法去控制对共享资源访问的有序性，但是我们有能力对共享资源采用锁的保护机制，当某个共享资源被锁住时，只有获取该锁的 CPU 核能够操作共享资源，其余试图访问共享资源的 CPU 核只能够等待这个锁的释放，这就是在 Linux 中被称为 Spinlock 的自旋锁保护机制。

Spinlock 的设计思想是基于一种被称为 Test-and-Set 的机制，它的操作分为三部分：

（1）INIT

初始化 lock 值。示例如下：

lock := CLEAR; 

（2）LOCK

这个流程包括两部分：首先 CPU 核反复轮询 lock 值直到它处于空闲状态为止，然后利用 Test-and-Set 方式尝试设置该 lock 值，Test-and-Set 的操作可以描述成三步：

（a）读取 lock 值；

（b）设置 lock 值；

（c）检查 lock 值是否设置成功，如果在步骤 （a） 之后还存在别的对 lock 值的操作，说明存在有并发访问 lock 值的情况，则步骤 （b） 的 lock 值将不能设置成功，还需要回到步骤 （a） 重新执行这个流程。

示例如下：

while ((lock == BUSY) || (TestAndSet(lock) == BUSY));

（3）UNLOCK

释放 lock 值。示例如下：

lock := CLEAR;

MIPS 中 Spinlock 的实现

传统的 C 语言是无法实现 Test-and-Set 的机制的，因为它无法在多核之间建立一个交互的机制，因此 Test-and-Set 需要处理器给以相应的支持。以 MIPS 为例，它提供了 LL（Load Linked Word） 和 SC（Store Conditional Word） 这两个汇编指令来实现对共享资源的保护。

LL 指令的功能是从内存中读取一个字，以实现接下来的 RMW（Read-Modify-Write） 操作；SC 指令的功能是向内存中写入一个字，以完成前面的 RMW 操作。LL/SC 指令的独特之处在于，它们不是一个简单的内存读取/写入的函数，当使用 LL 指令从内存中读取一个字之后，比如 LL d, off(b)，处理器会记住 LL 指令的这次操作（会在 CPU 的寄存器中设置一个不可见的 bit 位），同时 LL 指令读取的地址 off(b) 也会保存在处理器的寄存器中。接下来的 SC 指令，比如 SC t, off(b)，会检查上次 LL 指令执行后的 RMW 操作是否是原子操作（即不存在其它对这个地址的操作），如果是原子操作，则 t 的值将会被更新至内存中，同时 t 的值也会变为1，表示操作成功；反之，如果 RMW 的操作不是原子操作（即存在其它对这个地址的访问冲突），则 t 的值不会被更新至内存中，且 t 的值也会变为0，表示操作失败。

SC 指令执行失败的原因有两种：

（1）在 LL/SC 操作序列的过程中，发生了一个异常（或中断），这些异常（或中断）可能会打乱 RMW 操作的原子性。

（2）在多核处理器中，一个核在进行 RMW 操作时，别的核试图对同样的地址也进行操作，这会导致 SC 指令执行的失败。

采用 LL/SC 指令实现 Spin_Lock/Spin_Unlock 的范例如下。

MIPS 的 Spin_Lock

对于 MIPS 的 Spin_Lock 操作，可以用如下的方式实现：

表1. Spin_Lock

1    Spin_Lock(lockkey)
2    1:
3        ll t0, lockkey
4        bnez t0, 1b
5        li t0, 1
6        sc t0, lockkey
7        beqz t0, 1b
8        sync

Line 1：

lockKey 是共享资源锁，这是块能被多核所共享的内存地址，该值为0表示锁处于空闲状态，为1表示锁已经被某个核所获取，其余核若想获取它只能等待，以下对于 lockKey 的定义相同。

Line 3：

将 lockKey 读入t0寄存器中。

Line 4：

比较 lockKey 是否空闲，如果该锁不可用的话则跳转到 Line 1。

Line 5：

给 t0 寄存器赋值为1。

Line 6：

将 t0 寄存器的值保存入 lockKey 中，并返回操作结果于 t0 寄存器中。

Line 7：

判断 t0 寄存器的值是否为0，如果为0表示 Line 5 中的操作失败，则返回 Line 1 重新开始；如果为1表示 Line 5 中的操作成功。

Line 8：

Sync 是内存操作同步指令，用来保证 sync 之前对于内存的操作能够在 sync 之后的指令开始之前完成。

MIPS 的 Spin_Unlock

对于 MIPS 的 Spin_Unlock 操作，可以用如下的方式实现：

表 2. Spin_Unlock

    Spin_Unlock(lockkey) 1      sync
2      sw zero, lockkey

Line 2：

给 lockKey 赋值为 0，表示这个锁被释放。

Spinlock 的不足和改进

Spinlock 在多核处理器中得到了广泛的运用，但是它也存在一些不足，特别是在对共享资源竞争很激烈的情况下，这种不足会带来很严重的后果。

（1）Spin_Lock 操作是不可重入的，在同一个核上如果在释放锁之前调用了多次 Spin_Lock，这将导致当前 CPU 核处于死锁状态，严重情况下会引起系统的崩溃。

（2）Spinlock 不能保证进程对共享资源访问的公平性和有序性，先申请锁的进程有可能反而在后申请锁的进程之后获取锁，严重时甚至可能导致某个进程长时间无法获取锁而处于饥饿状态。

（3）当 Spinlock 被用于保护共享内存时，对于并发读操作的保护是多余的，反而会降低系统性能。

为了解决 Spinlock 的上述不足，我们提出了以下的改进措施，有些措施已经在 Linux 中有所体现。

Spinlock 的可重入性

Spinlock 的设计初衷是为多核处理器所提供的，如果在一个核上调用多次 Spin_Lock，会发生什么样的事情呢？这个问题在 Linux 的多线程编程中是个值得考虑的问题。

比如 Thread A 在用 Spin_Lock 取得共享资源操作权限后，在 Spin_Unlock 之前，它的操作由于某种原因被打断了（比如说其它高优先级的线程 Thread B 抢占，中断或者异常的发生等），在新的线程、中断（或异常）的处理程序中如果再次调用了 Spin_Lock，这种后果可能是灾难性的。因为 Spin_Lock 采用的是如果无法取得锁就会无限等待的策略，因此一个核在没有释放锁的情况下多次调用 Spin_Lock 会引起当前 CPU 核性能低下，甚至导致系统崩溃。

针对这种情况，Linux 提供了对于共享资源保护的原则：

（1）如果是单核中的共享资源保护，采用 Semphore 的机制；

（2）如果是多核中的共享资源保护，采用 Spinlock 的机制。

同时需要注意的是，因为 Semphore 和 Spinlock 的策略都是循环等待锁释放，因此对于它们的使用需要小心，比如不能在中断处理函数中使用等。

针对上述原则，我们可以提供一种更安全的 Spinlock ——可重入的 Spinlock 机制，它的思想是，在入参中同时提供一个标志核 ID 的 Owner 字段，当某个 CPU 核获取锁后，Owner 字段就等于当前核的 ID。在申请锁时，首先判断 Owner 字段是否等于申请者的核 ID，如果相等，则跳过后面的检查流程直接操作共享资源，否则再进行 Spin_Lock 的操作。

改进后的可重入的 Reent_Spin_Lock 实现如下：

表3. Reent_Spin_Lock

Reent_Spin_Lock(lockkey, owner)
if (owner != currentCoreId)
{  Spin_Lock(lockkey);  owner = currentCoreId; }

改进后的可重入的 Reent_Spin_Unlock 实现如下：

表4. Reent_Spin_Unlock

Reent_Spin_Unlock(lockkey, owner)  Spin_Unlock(lockkey); owner = 0xFFFFFFFF;

Spinlock 的排队策略

Linux 在提出 Spinlock 的概念时，是没有考虑到如何保证等待中的进程有序地获取共享资源锁的问题的。设想一下，如果让先申请锁的进程眼睁睁地看着后来者得到锁，而它自己却迟迟得不到，这种饥饿状态是很不公平的。

因此 Linux 的内核开发者 Nick Piggin 在 Linux 2.6.25 版本中提出了排队 Spinlock（FIFO Ticket Spinlock） 的概念，他的设计思路是将一个锁用 next 和 owner 两个字段来表示，并将申请锁的过程分为两个阶段，一个是初次申请阶段，另一个是重复申请阶段。当初次申请锁时，当前 CPU 核取 next 字段作为自己的 ticket，并且 next 字段增加1，同时判断 ticket 与 owner 字段是否相等，如果相等则获取锁成功；当重复申请锁时，只需要判断 ticket 与 owner 字段是否相等以决定锁是否申请成功即可。在释放锁时，将 owner 字段增加1。

排队 Spinlock 能够保证进程按照先来先到的原则有序地访问共享资源，从而保证了锁申请的公平性和有序性。

读写 Spinlock

对内存的访问分为读和写两部分，在用 Spinlock 保护共享内存时，内存的并发读、并发写以及并发读写是完全互斥的。事实上因为读操作不会修改内存，并发读中设置锁保护反而降低了性能，因此 Linux 专门提供了读写锁的机制用来保证并发写和并发读写的锁保护，同时也不影响并发读的效率，在对内存访问进行保护时，可以采用读写锁来代替传统的 Spinlock。

读写锁分为 4 部分：Read_Lock、Read_Unlock、Write_Lock、Write_Unlock。

表5. Read_Lock

Read_Lock(lockKey)
1:
  ll t0, lockKey
  bltz t0, 1b
  add t0, 1
  sc t0, lockKey
  beqz t0, 1b
  nop
  sync

对于 Read_Lock 操作，首先读取 lockKey 的值，判断该值是否小于0，如果小于0则表示当前锁被写操作所保护着，该锁无法被读操作所获取；否则给 lockKey 值加1，该值表示当前发生的读操作的次数。

表6. Read_Unlock

Read_Unlock(lockKey)
1:
   ll t0, lockKey
   sub t0, 1
   sc t0, lockKey
   beqz t0, 1b
    sync

对于 Read_Unlock 操作，首先读取 lockKey 的值，然后将该值减1，表示减少一次当前发生的读操作的次数。

表7. Write_Lock

Write_Lock(lockKey)
1:
     ll t0, lockKey
     bnez t0, 1b
     lui t0, 0x8000
     sc t0, lockKey
     beqz t0, 1b
      sync

对于 Write_Lock 操作，首先读取 lockKey 的值，判断该值是否为0，如果为0表示当前没有任何读操作或者写操作发生，然后获取该锁，并将 lockKey 赋值为0x80000000（一个负数），表示当前锁被写操作所占用。

表8. Write_Unlock

Write_Unlock(lockKey)
1:
  sync
  sw zero, lockKey

对于 Write_Unlock 操作，直接将 lockKey 赋值为0即可，表示该锁被释放。

还需要完善的地方

Spinlock 离完美还距离很远，随着多核处理器被越来越多地应用，更多的缺陷还有待完善，比如：

（1）虽然排队 Spinlock 解决了获取锁的有序性和公平性，但是进程优先级的概念无法体现，不能保证优先级高的进程优先获取锁。

（2）等待锁释放是一个循环等待的过程，如果等待时间很长的话是对系统资源的一种浪费，可以增加一些诸如超时一类的机制。

（3）在很多核同时竞争锁的情况下，系统负荷会比较重，从而影响系统的性能。

参考资料

《See MIPS Run》，Dominic Sweetman，这本书介绍了 Linux 如何在 MIPS 中运行。

《The Performance of Spin Lock Alternatives for Shared-Memory Multiprocessors》，Thomas E. Anderson，这篇文章介绍了 Spinlock 性能方面的问题。

《Linux 内核的排队自旋锁(FIFO Ticket Spinlock)》，林昊翔、秦君，这篇文章对排队自旋锁介绍了很详细。

关于作者

		赵昊翔，南京大学计算机系硕士毕业，目前从事嵌入式方面的开发工作，对 Linux 和 MIPS 多核处理器有浓厚的兴趣。