操作系统对多处理器的支持实现[文献综述][转发]

关键词：FreeBSD Linux POSIX 多核 操作系统 内核

摘要

在最新的计算机技术中，多处理器(Multi Processor)技术方兴未艾。作为计算机系统软件的最基本部分，操作系统(Operation System)对多处理器的支持，是非常重要的。本文对从设计实现角度出发，对主流的类UNIX操作系统支持多处理器的实现进行了初步分析和综述。

目前，类Unix操作系统对多处理器支持较好的，主要有Linux和FreeBSD。下面主要针对这两种操作系统进行阐述。

1.1. 主流类UNIX操作系统对多处理器支持的现状

1.1.1 多处理器系统概述

多处理器系统(Multi-processor System)源起于20世纪50年代的超级计算机。从1999年开始，随着Intel XEON处理器的推出，多处理器系统逐渐在基于x86体系结构的计算机中被使用。但是，当时的主流桌面操作系统对多处理器的支持尚不完善，因此并不能充分发挥多处理器的性能。

在计算机处理器主频进入GHz时代的今天，几何级数增长的计算需求与算术级数增长的处理器主频之间的矛盾，已经日益凸显。由于主频的上升，在同样的半导体工艺下，为了使得数字信号的波形上升沿和下降沿更加锋利，需要提升处理器核心电压以保证稳定。由于数字电路的功耗正比于电压的平方，且随时钟频率线性增加，因此，如果单一地使用提升主频的方法来提升处理器性能，功耗和散热将是严重的瓶颈。在这样的背景下，多核处理器就是处理器厂商克服功耗瓶颈，解决这一矛盾的方案。

操作系统作为体系结构/总线/输入输出硬件之上，对于软件提供系统服务接口的抽象层，对多核处理器的支持，从根本上决定了多核处理器能否发挥出最高效率。

1.1.2 Linux对多处理器的支持

Linux从2.0版本开始支持对称多处理器SMP(Symmetric Multi-Processing)，但仅仅是用一个锁来让各处理器串行地访问系统资源，并不能充分发挥多处理器的并行性能。直到Linux 2.6版本，才引入了实用的SMP系统下任务调度算法，其时间复杂度为常数O(1)。^[1]

为了提高调度效率，Linux可以将某个进程或线程绑定在特定的处理器上，也可以将中断定向至某个特定的处理器上。后者需要特定硬件的支持。^[2]

1.1.3 FreeBSD对多处理器的支持

FreeBSD从3.x版本开始，类似Linux地，使用一个巨型锁(Giant Lock)，来防止多个处理器同时进入内核。从FreeBSD 5.3开始，在内核的网络协议栈部分，支持无互锁地多处理器并行。FreeBSD从6.0开始支持多处理器安全(MP-Safe)的虚拟文件系统(VFS)。在FreeBSD 7.0新增的特性SMPng中，几乎完全去除了Giant Lock，这使得8个以上处理器的SMP系统，其性能几乎与处理器数目线性正相关。^[3][4]

1.2 操作系统支持多处理器的软件接口

为了支持多处理器，操作系统需要提供一系列的接口供上层软件使用。这些接口包括以下几类：

1.2.1 原子操作

在并行编程中，如果一个操作是不可中断的，瞬间完成的，那么，它被称为原子操作^[5]。类Unix系统提供的原子操作接口应当符合POSIX规约。

GNU提供了一系列原子操作，如以下的取-操作系列原语：

__sync_fetch_and_add ()

__sync_fetch_and_sub ()

__sync_fetch_and_or ()

__sync_fetch_and_and ()

__sync_fetch_and_xor ()

__sync_fetch_and_nand ()

这些原语虽然在GLIBC等链接库或头文件中以inline函数的方式实现，但是，它们仍然是操作系统并发同步机制的不可或缺的部分。^[6]

1.2.2 内存屏障

除原子操作外，内存屏障也是一个很重要的为并行编程提供的特性。为了提升执行性能，有的时候CPU会将指令打乱顺序执行，即所谓的乱序执行。对于并发编程中的一些情况，这种乱序执行可能会导致不期望的后果。为了避免这种情况的发生，内存屏障就是一个解决方案。

内存屏障的作用一言以蔽之：保证内存屏障之后的指令，一定在内存屏障之前的指令执行完毕后再执行。^[7]

1.2.3 锁

锁(Lock)和互斥(Mutex)是防止多核同时访问临界资源的机制。Mutex会引起线程/进程睡眠，而Lock不会引起睡眠。POSIX规约中，Lock有以下几种：

自旋锁(Spin Lock)；读写锁(RWlock)；单次锁(TryLock)；

另外有的操作系统还实现了排队锁(Queue Lock)，可以避免在最坏的情况下，某个处理器一直获取不到锁的情况。^[8]

1.3. 操作系统支持多处理器所必需的硬件指令

传统的处理器指令中，虽然有inc这样的自加指令，但是，它并非一个“原子”指令。因为，如果是两个处理器同时执行这样的指令，那么，将产生一个竞争条件，不能保证两个或多个处理器并非同时访问一个地址。因此，在支持多处理器的CPU体系结构中，均引入了一系列硬件指令，来保证操作的原子性。

1.3.1 IA-32/IA-64架构

IA (Intel Architecture)中，有两类原子操作指令。一类是在指令前面加lock前缀。可以加Lock前缀的指令有：bt, bts, btr, btc; xchg, xadd; add, or, adc, sbb; and, sub, xor; not, neg, inc, dec这些指令。使用这个前缀可以使处理器暂时地锁定总线，使得其他处理器不能访问锁定的总线地址，直到指令执行完毕。另一类是特殊的指令，如cmpxchg，将比较和交换放在同一条指令中执行。特别地，这条指令用于实现自旋原子锁(spinlock)。^[9]

1.3.2 MIPS

MIPS的原子操作指令，是通过sc和ll指令配对来实现的。对于MIPS64，还有scd和lld处理8字节数(双字)。另外，在RMI的XLR多核处理器中也支持cmpxchg(比较后交换)指令。^[10]

1.3.3 PowerPC

PowerPC体系结构的原子操作，类似MIPS，通过条件加载/存储指令实现。如lwarx和stwcx的配对。^[11]

1.4 操作系统支持多处理器的实现

1.4.1 Linux

Linux对多处理器支持的实现在以下几个文件中：

kernel/smp.c

kernel/cpu.c

kernel/spinlock.c

其中，spinlock.c是用以实现线程互锁的，另外两个文件实现了任务在多处理器之间的相互调度。原子操作在gnu编译器自带的.h和GLIBC中实现。

1.4.2 FreeBSD

FreeBSD对多处理器支持的实现在以下几个文件中：

kern/kern_rwlock.c 实现读写锁

kern/kern_cpu.c 实现多处理器的初始化

另外源代码的根目录下，有各自体系结构下实现原子操作/自旋锁的功能的代码。

1.5. 小结

主流操作系统对多处理器的支持是一个逐渐完善的过程，也是以后发展的趋势。它的发展方向必然是想方设法减小多核协作的开销，将加速比尽量提升到与处理器数目一致。

参考文献：

[1] M.Tim.Jones, Linux and symmetric multiprocessing, [EB/OL].

http://www.ibm.com/developerworks/library/l-linux-smp/ .

[2] Robort Love 著；陈莉君，康华，张波 译. Linux内核设计与实现：第二版 [M]. 北京：机械工业出版社，2006：265.

[3] About FreeBSD's Technological Advances, [EB/OL] http://www.freebsd.org/features.html

[4] M.K.McKusick; George V.Nevile-Neil 著；张辉 译. FreeBSD操作系统设计与实现 [M]. 北京：人民邮电出版社，2006：177-178

[5] Linearizability [EB/OL]. http://en.wikipedia.org/wiki/Atomic_operation .

[6] Atomic [R]. http://gcc.gnu.org/wiki/Atomic .

[7] Simon C. Steely, Jr., Madhumitra Sharma, Kourosh Gharachorloo, Stephen R. Van Doren, Mechanism for Reducing Latency of Memory Barrier Operations on A Multiprocessor System. [P] 美国专利：6088771, 2000-07-11.

[8] 赵昊翔，Linux 的 Spinlock 在 MIPS 多核处理器中的设计与实现. [EB/OL] http://www.ibm.com/developerworks/cn/linux/l-cn-spinlock_mips/index.html

[9] Intel co.ltd Intel 64 and IA-32 Architectures Software Developer’s Manual [R]

[10] Dominic Sweetman, See MIPS Run (Second Edition), [M]. San Francisco, California: Morgan Kaufmann Publishers, Inc, 1999. 210-211.

[11] POWER ISA Manual, Version 2.06 [R] IBM co.ltd