一种机载嵌入式对称多处理机系统互斥策略

李 娟，任晓瑞

(1.中国航空工业计算技术研究所十八室，陕西西安 710068;2.中国航空工业计算技术研究所三室，陕西西安 710068)

随着航空电子系统高度综合化、模块化的发展，航电计算机处理子系统将承担更多、更复杂的任务，这对计算机系统的处理和运算能力提出了更高的要求。为满足新一代飞机对计算机系统性能的需求，在现有机载嵌入式实时操作系统的基础上设计SMP操作系统，以提高计算机系统的运行速度。

在商用计算机领域，SMP操作系统作为一种有效提升计算机系统处理和运算速度的手段被广泛应用。MontaVista Linux是Linux 2.4内核的派生产品，内带一个完全抢占调度器。Wind River的VxWorks采用同步原语，该同步原语基础是各节点上运行的不同VxWorks之间的消息传递接口，但由于其技术保密，无法获知其技术细节。QNX支持操作系统为微核结构而非整体结构的SMP设计。其内核自身支持一组核心服务，而其它服务则以单独的进程方式运行［1－2］。

虽然SMP技术不能使系统性能成倍增长，但它的确用最小的代价提高了系统数据处理能力、实现了负载均衡。SMP操作系统要充分利用多个处理器的运算能力，良好地支持任务并行工作，首先要解决的问题是多个任务，以及任务和中断之间的互斥。但传统的单机操作系统互斥共享资源的方法在多个CPU同时运行的条件下完全失效，SMP的互斥策略需要重新设计［3－4］。

本文针对机载计算机系统中处理器数量少、系统实时性和确定性要求高的特点，在自主版权机载单机操作系统ACoreOS上设计SMP操作系统的互斥策略。

1 互斥策略

1.1 单机操作系统的互斥

任何多任务操作系统，或带中断的操作系统都会遇到对共享资源的保护问题。第一种情况为多个任务竞争同一个资源，第二种情况为任务占有资源期间外部中断请求该资源。根据任务对资源需求的时间长度，又可以将第一种情况分为短期互斥和长期互斥。

(1)短期互斥。是指在短期临界区中防止竞争条件发生。通常这些临界区是更新内核数据的代码。由于所有执行任务共享内核数据结构，当两个以上任务同时访问同一段数据时可能出现竞争条件。单机系统中每个时刻只有一个任务执行，竞争条件只可能发生在任务被抢占的情况下。为此，在内核模式下采用非抢占方式调度任务。只有在内核允许的情况下，任务之间的上下文切换才会发生。

(2)长期互斥。是指避免在对硬件资源或文件系统等需要长时间操作时出现竞争条件。在单机操作系统可以采用信号量，确定时间内只有获得信号量的任务可以访问资源，其他任务都处于等待状态，当信号量被释放后，等待任务具有竞争信号量的权利，根据一定的算法互斥占有资源。

(3)带中断的互斥。任务访问数据允许中断访问也会产生竞争条件。单机操作系统提供了关闭中断的功能，因而，任务在访问和中断共享的数据结构之前通过关闭中断避免这种竞争条件的出现，任务退出时开启中断实现了对这种资源保护的互斥。

1.2 现有SMP操作系统互斥技术

单机系统中短期互斥成立的前提条件是内核任务调度的不抢占策略。可是，在多机系统中多个处理器并发执行内核程序，破坏了这种条件的成立。当多个处理器并发执行内核程序时，竞争条件出现会破坏内核数据结构。带中断的互斥在多机系统中也不能正常运行。每个处理器禁止中断只能影响本机，并不能影响其他处理器。单机中的长期互斥策略在多机中也不适用。因为长期互斥采用的信号量不是原子操作，多个处理器可能同时对其操作造成错误，这种方法不能在多机系统中应用。

1.2.1 QNX

QNX是完全可抢占式系统，对多处理器支持仅限于微内核，外围服务进程无需任何改动即可在SMP系统上适用。任何时候高优先级的任务都有权利立即剥夺低优先级任务的CPU资源。为控制任务访问共享数据，使用POSIX互斥原语－互斥、条件变量、信号灯等。在多处理器系统中中断可以抢占任务，但任务不可以抢占中断。采用两种方法保护共享数据:(1)将任务绑定到特定的处理器。(2)在任务和中断之间利用新的互斥自旋锁变量－中断锁。

1.2.2 MontaVista Linux

MontaVista Linux内核引进两种锁机制RCU和MUTEX改进Linux 2.4的性能。RCU(Read－Copy－Update)是读－拷贝－更新，允许多个读写者并发执行，对于被RCU保护的共享数据结构，读者不需要获得任何锁就可以访问它，但写者在访问它时首先拷贝一个副本，然后对副本进行修改，最后使用一个回调机制在适当的时机把指向原来数据的指针重新指向新的被修改的数据。这个时机就是所有引用该数据的处理器核都退出对共享数据的操作。RCU对读者多而写者少共享资源保护非常有效。RCU没有使用锁，因此不存在死锁问题。但RCU应用条件非常苛刻，它只适用于空间动态分配的数据结构，且数组共享数据空间会带来额外的计算量和时间消耗，不适合作为操作系统内核的互斥方法。

MUTEX锁代替读写锁，实现了优先级继承功能。当高优先级的任务请求共享数据时，升高占有共享数据的任务优先级，避免了低优先级的任务抢占CPU资源发生优先级翻转，有效提高了系统的响应时间，是机载多处理器操作系统保护共享数据短期互斥可借鉴的一种方法。

2 互斥策略的设计

设计的基础是自主版权的机载单机操作系统ACoreOS，通过修改其内核实现对SMP系统的支持。ACoreOS采用层次化结构，分为模块支持层、操作系统核心层、和应用层。除了和硬件相关的同步原语在模块支持层实现，其他互斥机制都在操作系统核心层完成。

考虑机载嵌入式系统高实时性的要求，本文设计的原则是维护系统内核完整性，正确的协调好CPU的并行活动，避免危害到内核的数据结构;保证系统高性能运行，采用有效的同步原语，自旋锁时间合理地短，避免CPU等待时间过长。主要解决SMP操作系统互斥设计的3个关键问题:(1)自旋锁设计。包括自旋锁数据结构和锁粒度两个方面，数据结构能体现自旋锁设计理念，是互斥策略的基础;自旋锁粒度根据系统处理器数量和期望应用设计，既要避免锁过大造成系统响应时间偏长，又要防止锁过小导致系统复杂度和计算开销急剧上升。(2)中断、任务切换、和长期互斥方法失效的问题。需要新的机制完成共享资源保护的功能。(3)死锁问题。自旋锁的引入带来了锁互持和多锁嵌套问题，竞争条件更易发生，死锁条件的预防是SMP互斥的一个重要问题。

2.1 自旋锁的设计

单机操作系统互斥的前提条件是单条指令能够完成的操作是“原子操作”，而在多机操作系统中多个CPU同时运行，单条指令若由多个“微操作”组成，“原子性”就不能够保证。多处理器系统中总线是每个CPU访问内存必经之路，所以在SMP操作系统中采用锁总线的方法实现对CPU对内存操作的原子性。

以PPC系列为例，提供一对专有的存取指令lwarx和stwcx来构建内存的原子操作。通过这两个指令的配合实现同步原语。自旋锁的设计不仅包括功能方面的考虑，还应包括性能方面的考虑。分析自旋锁的操作，共享资源的读操作和写操作对互斥的要求不同，多个读操作可以并行访问共享资源，而写操作和其他操作只能串行执行。因此，在自旋锁的设计时，加入对访问资源操作类型区分，从而达到提高访问资源并行度，优化自旋锁性能的目的。同时，为避免优先级反转，锁设计借鉴MUTEX锁的设计方法，实现优先级继承功能，并结合前面对锁操作类型的划分，降低系统计算开销。

2.1.1 自旋锁结构

自旋锁实质上是内存中的一个变量，变量的值表示锁的状态。自旋锁的获取和释放是通过同步原语修改变量的值。如果要区分读锁和写锁，在锁数据结构中应该体现锁操作的类型，因此，需要增加一个变量记录是读操作还是写操作。修改后的锁数据结构为

readers是增加的变量，表示读操作者的数目。修改锁结构后的自旋锁获取和释放区分了访问临界资源的类型，流程如下:

(1)读自旋锁获取。首先判断锁状态，0x1表示锁被写者占有不能获取;0x0表示锁没有占有者或被读者占有，可以获取;成功获取锁后不修改锁状态，依然为0x0，只是将readers值加1，表示读者数目增加。

(2)读自旋锁释放。readers值减1，表示读者数目减少。

(3)写自旋锁获取。判断锁状态，锁值为0x0且readers值为0x0，表示锁没有占有者，可以获取，获取成功将锁状态置为0x1;否则锁不能获取。

(4)写自旋锁释放。将锁状态设置为0x0。

自旋锁的基本操作和数据结构设计完成后，考虑解决优先级反转的问题。MUTEX锁利用优先级继承的方法成功避免了低优先级任务占有自旋锁而高优先级任务等待的情况。本文将MUTEX锁引入SMP的设计，并对该锁进行优化，优化后的锁称为PRI锁，增加锁访问者对临界资源操作类型的区分，从而达到降低系统开销的目的。

如图1所示，将锁持有和请求分为4种情况。在锁持有和请求者都为读操作时，由于前面锁的设计允许同时操作临界区，因而不提升占有锁任务的优先级，在读操作频繁执行的环境中能够极大降低系统提升优先级的开销。

图1 SMP锁操作流程图

2.1.2 自旋锁粒度

目前系统考虑处理器数量少的情况，因此系统中锁的粒度不需要很细。基于系统时间和空间代价综合考虑，对频繁访问，对系统实时性影响高的对象采用细粒度锁，其他对象采用粗粒度锁。经过分析系统中对响应时间和任务切换时间影响大的资源包括:线程控制块、信号量、扩展链、就绪队列，对它们每个资源采用一个自旋锁。

(1)线程控制块锁。实现对每个线程控制块的互斥操作。在线程的挂起，停止，删除，启动等操作中需要获取该锁。

(2)信号量锁。信号量是频繁访问的对象，对它单独用一个自旋锁保护。

(3)扩展锁。所有扩展都挂在一个扩展链上，为避免多个线程同时操作扩展链造成错误，在线程操作扩展链之前必须获得扩展锁。

(4)就绪队列锁。就绪队列是所有处理器访问最频繁的资源，为提高访问速度采用优先级映像表，因此，对优先级映像表和就绪队列合用一个自旋锁——就绪队列锁进行保护。

2.2 长期互斥、中断、任务切换

(1)长期互斥。采用原子信号量，该原语能够解决单机长期互斥不是原子操作的问题，并且在任务得不到锁的条件下允许挂起而不占用处理器资源。

信号量的状态由一个有符号整数表示。操作系统通过两个原子操作改变整数值。P(s)操作给信号量值减1，如果操作后的值＜0则阻塞任务;如果操作后的值≥0，任务继续执行。V(s)操作给信号量值加1，如果新值≤0，为等待该信号量的一个任务解除阻塞。阻塞在某个信号量上的任务队列和信号量值组成整个信号量。当信号量值为负，它的绝对值表示这个队列上任务的数目。原子PV操作不仅决定一个任务是否应该被挂起，同时执行任务的挂起操作。既然信号量记录了相关状态，为保证对其操作的原子性，PV操作都需要加自旋锁保证每次只有一个CPU对其操作。

(2)中断。ACoreOS为避免在访问同一个全局共享资源的任务和中断句柄之间出现潜在竞争条件，当一个任务正在执行其临界区代码时，该任务会暂时禁止各种中断。然而在一个多处理器系统中，仅禁止中断并不足以避免出现竞争条件。

为避免在SMP系统中的任务和中断服务程序之间出现竞争条件，引入中断锁的概念，任务和中断服务程序必须获得一个中断锁才能访问其临界区所用到的共享资源。如果中断服务程序发现已有其他程序在使用旋转锁，那么它将在空转中等待其他任务或中断服务程序释放该旋转锁。这对中断延时以及整个系统对外部事件的响应均有影响。因此，任务尽量避免和中断服务程序共享资源，如果无法避免，共享资源必须足够短，不能对中断响应时间影响太大。

(3)任务切换。如图2所示，占有自旋锁的任务切换让出CPU资源但是不释放自旋锁，将导致后面请求该自旋锁的任务无法执行。因此，不能允许占有自旋锁的任务被切换，在设计上通过关本调度的方式完成，即不允许占有自旋锁的任务被切换，直到锁释放为止。

图2 SMP任务切换互斥原理示意图

2.3 死锁问题的避免

如图3所示，自旋锁的应用存在两种情况导致死锁:锁互持和锁多次获得。

图3 自旋锁死锁竞争条件示意图

锁互持源自任务在执行中需要获得多个自旋锁，例如:任务控制块锁，对象锁，扩展锁等。甲任务获得部分锁，乙任务获得部分锁，甲乙两个任务持有对方需要的锁，又需要对方占有的锁，互相僵持导致了死锁条件的产生。

将任务优先级的概念引入自旋锁设计中，系统中所有自旋锁地位是不平等的。每个锁都有一个固定优先级，任务获得多个自旋锁必须按照优先级从高到低的顺序获得。如图4所示，任务1和任务都需要获得任务控制块锁和信号量锁两个自旋锁，获锁顺序先任务控制块锁后信号量锁，从而在任务1持有任务控制块锁的条件下，任务2将不能获得任务锁处于等待状态，死锁条件避免。

图4 锁互持竞争条件避免示意图

图3(b)所示为同一个锁多次获得示意图，任务控制块锁已经被任务1占有，但在任务扩展中又需要再次获得，只能等待陷入死锁。针对该问题修改自旋锁结构，加入一项owner表示锁持有者身份，加入一项nest表示锁嵌套层次。

当锁的请求者和持有者相同时，锁请求者获得锁，锁状态不变，nest加0x1，表示锁获得的嵌套层次。锁释放只有在nest为0时，也就是锁持有者只获得锁一次的条件下，修改锁状态。否则，锁状态不变，只是nest数目减0x1。

3 验证

SMP操作系统是在ACoreOS的基础上设计和实现的，测试平台采用的CPU为MPC7410。ACoreOS运行的硬件平台和SMP操作系统相同，外部设备、底层驱动、内存管理等性能也没有差异。

对这两种操作系统的任务切换时间进行对比，经50 000次任务切换比较，单机操作系统和SMP操作系统的任务切换时间均值分别为23.4μs和23.6μs，切换时间代价增长为0.8%。采用优先级抢占调度策略，3个优先级分别为60，61，62的计算任务循环执行，取5次运行的均值。单机操作系统1 min执行1 275 964次循环，SMP操作系统执行2 483 756循环，处理能力提高94.6%。

4 结束语

本文在机载嵌入式操作系统的基础之上引入自旋锁机制，解决传统互斥方法被SMP多CPU并行工作破坏的问题，并对SMP操作系统的性能和开销代价做了初步测试，表明SMP系统在不影响实时性的前提下，有效提高了计算机系统的处理能力。下一步将设计更为复杂的任务测试系统性能，包括多个自旋锁申请和释放的程序、包括长期共享公共资源的程序，以及任务执行过程中出现中断的情况等。

［1］毛德操，胡希明.Linux内核源代码情景分析［M］.杭州:浙江大学出版社，2001.

［2］DOMINIK M.TopsySMP—a small multi－threaded microkernel for symmetrical multiprocessing hardware architectures［J］.Journal Article，1998(12):131 －138.

［3］BATAT A，FEITEL S D.Gang scheduling with memory consideration［C］.Cancun，Mexico:In Proceedings of the 14th IEEE International Parallel and Distributed Processing Symposium，2000:109－114.

［4］LIAO Weikeng，ALOK C，DONALD W，et al.Multi－ threaded design and implementation of parallel pipelined stap on parallel computers with smp nodes［J］.IEEE Transaction on Software，2011(9):1121－1132.