Ｌｉｎｕｘ２．６内核对ＳＭＰ系统支持的研究

李兰英　温现杰

摘要：首先简要介绍了SMP系统的体系结构，接着重点分析了SMP系统中进程调度、同步机制和负载平衡三个方面的实现细节，最后给出Cache一致性问题的解决方案。

关键词：同步机制；负载平衡

引言。SMP系统的并行处理技术，不仅提高处理器的运算能力和处理能力，而且对操作系统实时性改进也提供了一个新的途径。

1Linux内核对SMP系统的支持

2.6内核包含更好的SMP系统支持，关键在于能在可用CPU之间进行负载平衡，同时维持亲合性以提高缓存效率。对称多处理器系统中，每一个CPU都将维护一个自己的就绪队列，并且每个就绪队列都有一个自旋锁，这样允许所有的CPU都可以对任务进行调度，而不会与其他CPU产生竞争[1]。

1.1SMP系统的进程调度

2.6内核中就绪队列定义为复杂得多的数据结构struct runqueue，首先分析一下其结构中关于SMP系统的定义。

(1) prio_array_t *active, *expired, arrays[2]

runqueue中最关键的数据结构。每个CPU的就绪队列按时间片是否用完分为两部分，分别通过active指针和expired指针访问，前者指向时间片没用完、当前可被调度的就绪进程，后者指向时间片已用完的就绪进程。

(2)spinlock_t lock

就绪队列的自旋锁，只影响一个CPU上的就绪队列。

(3) unsigned long nr_uninterruptible

记录本CPU尚处于TASK_UNINTERRUPTIBLE状态的进程数，和负载信息有关。

(4) unsigned long timestamp_last_tick

本就绪队列最近一次发生调度事件的时间，在负载平衡的时候会用到。

还有几个数据项，这里不做介绍了。

我们先来总结一下调度器的结构，每个CPU都有一个运行队列，其中包含了140个优先级列表，它们是按照先进先出的顺序进行服务的。被调度执行的任务都会被添加到各自运行队列优先级列表的末尾。每个任务都有一个时间片，运行队列的前100个优先级列表保留给实时任务使用，后40个用于用户任务。除了CPU的运行队列之外，还有一个过期运行队列。当活动运行队列中的一个任务用光自己的时间片之后，它就被移动到过期运行队列中。在移动过程中，会对其时间片重新进行计算。如果活动运行队列中已经没有某个给定优先级的任务了，那么指向活动运行队列和过期运行队列的指针就会交换，这样就可以让过期优先级列表变成活动优先级的列表。

调度器的工作:在优先级最高的队列中选择一个任务来执行。为使这个过程的效率更高，内核使用了一个位图来定义给定优先级列表上何时存在任务。因此，在大部分体系架构上，会使用一条find-first-bit-set指令在5个32位的字中哪一位的优先级最高。查找一个任务来执行所需要的时间并不依赖于活动任务的个数，而是依赖于优先级的数量，这使得2.6内核的调度器复杂度为O(1)。

1.2 SMP系统中同步机制

只有在MP情况下存在真正的并行，因为线程是同时执行的，其中每个处理器中共享相同数据的线程同时执行。

自旋锁(spinlock)是使用忙等待锁来确保互斥锁的一种特殊方法。如果锁可用，则获取锁，执行互斥锁动作，然后释放锁。如果锁不可用，线程将忙等待该锁，直到其可用为止。在可抢占内核和SMP情况下对共享资源的同步问题，一般地一个任务对共享资源的访问是非常短暂的，如果两个任务竞争一个共享的资源时，没有得到资源的任务将自旋以等待另一个任务使用完该共享资源。与原子操作、信号量、读写、大内核锁、读写锁相比，这种锁机制也是非常高效的。

初始化自旋锁x是通过宏DEFINE_SPINLOCK(x)实现的，自旋锁在真正使用前必须先初始化，该宏用于动态初始化。自旋锁有完全锁和读写锁两种形式。在SMP系统中主要用的是完全锁，这种锁机制的过程：

首先通过一个简单的声明创建一个新的自旋锁。

spinlock_t my_spinlock = SPIN_LOCK_UNLOCKED;

…

DEFINE_SPINLOCK(my_spinlock);

…

spin_lock_init(&my_spinlock);

定义了自旋锁之后，就可以使用大量的锁变量了。每个变量用于不同的上下文。spin_lock和spin_unlock变量。这是一个最简单的变量，它不会执行中断禁用，但是包含全部的内存壁垒。这个变量假定中断处理程序和该锁之间没有交互。

spin_lock(&my_spinlock);

…

spin_unlock(&my_spinlock);

接下来是irqsave和irqrestore对，前者需要自旋锁，并且在本地处理器上禁用中断。后者释放自旋锁，并且(通过flags参数)恢复中断。

spin_lock_irqsave(&my_spinlock, flags);

…

spin_unlock_irqrestore(&my_spinlock, flags);

最后，如果内核线程通过低半方式共享数据，那么可以使用自旋锁的另一个变体。

spin_lock_bh(&my_spinlock);

…

spin_unlock_bh(&my_spinlock);

读写锁主要应用在读取数据比写入数据更常见情况下。这种模型中允许多个线程同时访问相同数据，但同一时刻只允许一个线程写入数据。如果执行写操作的线程持有此锁，则临界段不能由其他线程读取。如果一个执行读操作的线程持有此锁，那么多个读线程都可以进入临界段。

1.3 负载平衡

在Linux支持的多处理机系统中，每个处理器维护一个进程就绪队列runqueue，并独立的对自己的就绪队列进行调度操作。由于存在多个就绪进程队列runqueue,可能存在多个队列之间负载的不平衡状况。函数rebalance_tick()（单个CPU时，此函数是不起作用的空函数）当有多个CPU时，在每个CPU上的每个定时器的tick时刻得到调用，检查每个调度域，在一定的时间间隔时调用函数load_balance()进行负载平衡。该函数在两种情况下被调用：schedule( )在当前runqueue为空时调用或者在系统空闲时由定时器每1ms调用一次，而在系统忙时则由定时器每200ms调用一次。

Linux 2.6内核调度系统采用相对集中的负载均衡方案，有"拉"和"推"两种操作。在load_balance函数及idle_balance函数中调用pull_task函数来实现"拉"操作，在migration_thread函数中实现"推"操作。

(1)“拉”操作

“拉”是指系统从重载CPU上“拉”进程过来到轻载CPU上，函数load_balance根据当前CPU是否空闲状态分为“忙平衡”和“空闲平衡”。每tick时钟中断会启动一次函数rebalance_tick来计算合适的时间间隔，启动函数load_balance平衡负载。另外，在调度器schedule中，本CPU的就绪队列为空，就调用idle_balance函数进行“空闲平衡”。函数pull_task实现“拉”进程的具体动作，并更新进程的timestamp属性，如果被“拉”进程的优先级比本CPU正运行的进程高，则当前进程被抢占。

(2)“推”操作

线程migration_thread执行“推”操作。该进程在系统启动时自动加载，并将自己设为SCHED_FIFO的实时进程，然后检查runqueue:migration_queue中是否有请求等待处理，若没有，则将自己休眠，直至被唤醒后再次检查。

2SMP 结构中的Cache一致性问题

给SMP系统增加高速缓存能够利用局部引用特性的优点提高性能，但也会带来保持高速缓存一致性的问题。当多个处理器存取和修改共享数据时，会出现SMP高速缓存一致性的主要问题。这种问题可以通过使用无高速缓存的操作，以及有选择的冲洗共享数据来管理共享数据解决。高速缓存与内存一致性问题基本上是由硬件完成的，Intel在Pentum CPU中为已经转入高速缓存的数据提供了一种自动与内存保持一直的机制，即“窥探”(snooping)机制。这种机制通过监视系统总线对内存的操作，用废弃缓冲栈方法来重新装载高速缓存，因而SMP结构中的高速缓存与内存的数据一致性问题是软件透明的[2]。

3结束语。最新的2.6内核对多处理器体系架构的更好支持，使整个系统更接近于多桌面和实时系统。然而也有一些不进入人意的地方，例如自旋锁是在保持自旋锁期间将失效抢占，这意味着抢占延迟将增加，而且抢占延迟也是不确定的。这也成为linux在实时性应用方面的一个障碍。

参考文献

[1]Daniel P.深入理解LINUX内核[M].陈莉君译.北京:中国电力出版社,2007.P84-107.

[2]Schinmmel,C.现代体系结构上的UNIX系统:内核程序员的SMP和Caching技术[M].张 辉译.北京:人民邮电出版社,2003.P217-227.