說明

部落格

摘要

排列方式：

<< 第一頁 < 上一頁下一頁 > 最後一頁 >>

7 April

基于Linux的实时系统

developerWorks 中国 > Linux >

基于Linux的实时系统

文档选项

		将此页作为电子邮件发送
		未显示需要 JavaScript 的文档选项

最新推荐

Java 应用开发源动力－下载免费软件，快速启动开发

级别: 初级

张焕强, 博士, 中科院软件研究所多媒体通信和网络工程研究中心

2003 年 10 月 11 日

越来越多的开发者在基于Linux系统构造嵌入式实时应用，他们迫切地需要一份基于Linux系统构造嵌入式实时系统的指南性的文章。考虑到这种需求，本文在介绍了几种基本的实时进程调度算法的基础上，研究了普通的Linux操作系统的进程调度，并十分全面地调查了各种实时Linux系统为了支持实时特性对普通Linux系统所做的改进。文章分析了将Linux操作系统应用于实时领域中时所出现的一些问题，并总结了各种实时Linux是如何解决这些问题的，最后对于如何将这些已有的研究成果应用与实际的研究和开发工作中作了很好的建议。

第一部分：实时调度算法介绍

对于什么是实时系统，POSIX 1003.b作了这样的定义：指系统能够在限定的响应时间内提供所需水平的服务。而一个由Donald Gillies提出的更加为大家接受的定义是：一个实时系统是指计算的正确性不仅取决于程序的逻辑正确性，也取决于结果产生的时间，如果系统的时间约束条件得不到满足，将会发生系统出错。

实时系统根据其对于实时性要求的不同，可以分为软实时和硬实时两种类型。硬实时系统指系统要有确保的最坏情况下的服务时间，即对于事件的响应时间的截止期限是无论如何都必须得到满足。比如航天中的宇宙飞船的控制等就是现实中这样的系统。其他的所有有实时特性的系统都可以称之为软实时系统。如果明确地来说，软实时系统就是那些从统计的角度来说，一个任务（在下面的论述中，我们将对任务和进程不作区分）能够得到有确保的处理时间，到达系统的事件也能够在截止期限到来之前得到处理，但违反截止期限并不会带来致命的错误，像实时多媒体系统就是一种软实时系统。

一个计算机系统为了提供对于实时性的支持，它的操作系统必须对于CPU和其他资源进行有效的调度和管理。在多任务实时系统中，资源的调度和管理更加复杂。本文下面将先从分类的角度对各种实时任务调度算法进行讨论，然后研究普通的Linux操作系统的进程调度以及各种实时Linux系统为了支持实时特性对普通Linux系统所做的改进。最后分析了将Linux操作系统应用于实时领域中时所出现的一些问题，并总结了各种实时Linux是如何解决这些问题的。

1. 实时CPU调度算法分类

各种实时操作系统的实时调度算法可以分为如下三种类别[Wang99][Gopalan01]：基于优先级的调度算法（Priority-driven scheduling-PD）、基于CPU使用比例的共享式的调度算法（Share-driven scheduling-SD）、以及基于时间的进程调度算法（Time-driven scheduling-TD），下面对这三种调度算法逐一进行介绍。

1.1. 基于优先级的调度算法

基于优先级的调度算法给每个进程分配一个优先级，在每次进程调度时，调度器总是调度那个具有最高优先级的任务来执行。根据不同的优先级分配方法，基于优先级的调度算法可以分为如下两种类型[Krishna01][Wang99]：

静态优先级调度算法：
这种调度算法给那些系统中得到运行的所有进程都静态地分配一个优先级。静态优先级的分配可以根据应用的属性来进行，比如任务的周期，用户优先级，或者其它的预先确定的策略。RM（Rate-Monotonic）调度算法是一种典型的静态优先级调度算法，它根据任务的执行周期的长短来决定调度优先级，那些具有小的执行周期的任务具有较高的优先级。
动态优先级调度算法：
这种调度算法根据任务的资源需求来动态地分配任务的优先级，其目的就是在资源分配和调度时有更大的灵活性。非实时系统中就有很多这种调度算法，比如短作业优先的调度算法。在实时调度算法中，EDF算法是使用最多的一种动态优先级调度算法，该算法给就绪队列中的各个任务根据它们的截止期限（Deadline）来分配优先级，具有最近的截止期限的任务具有最高的优先级。

1.2. 基于比例共享调度算法

虽然基于优先级的调度算法简单而有效，但这种调度算法提供的是一种硬实时的调度，在很多情况下并不适合使用这种调度算法：比如象实时多媒体会议系统这样的软实时应用。对于这种软实时应用，使用一种比例共享式的资源调度算法（SD算法）更为适合。

比例共享调度算法指基于CPU使用比例的共享式的调度算法，其基本思想就是按照一定的权重（比例）对一组需要调度的任务进行调度，让它们的执行时间与它们的权重完全成正比。

我们可以通过两种方法来实现比例共享调度算法[Nieh01]：第一种方法是调节各个就绪进程出现在调度队列队首的频率，并调度队首的进程执行；第二种做法就是逐次调度就绪队列中的各个进程投入运行，但根据分配的权重调节分配个每个进程的运行时间片。

比例共享调度算法可以分为以下几个类别：轮转法、公平共享、公平队列、彩票调度法（Lottery）等。

比例共享调度算法的一个问题就是它没有定义任何优先级的概念；所有的任务都根据它们申请的比例共享CPU资源，当系统处于过载状态时，所有的任务的执行都会按比例地变慢。所以为了保证系统中实时进程能够获得一定的CPU处理时间，一般采用一种动态调节进程权重的方法。

1.3. 基于时间的进程调度算法

对于那些具有稳定、已知输入的简单系统，可以使用时间驱动（Time-driven:TD）的调度算法，它能够为数据处理提供很好的预测性。这种调度算法本质上是一种设计时就确定下来的离线的静态调度方法。在系统的设计阶段，在明确系统中所有的处理情况下，对于各个任务的开始、切换、以及结束时间等就事先做出明确的安排和设计。这种调度算法适合于那些很小的嵌入式系统、自控系统、传感器等应用环境。

这种调度算法的优点是任务的执行有很好的可预测性，但最大的缺点是缺乏灵活性，并且会出现有任务需要被执行而CPU却保持空闲的情况。

2. 通用Linux系统中的CPU调度

通用Linux系统支持实时和非实时两种进程，实时进程相对于普通进程具有绝对的优先级。对应地，实时进程采用SCHED_FIFO或者SCHED_RR调度策略，普通的进程采用SCHED_OTHER调度策略。

在调度算法的实现上，Linux中的每个任务有四个与调度相关的参数，它们是rt_priority、policy、priority（nice）、counter。调度程序根据这四个参数进行进程调度。

在SCHED_OTHER调度策略中，调度器总是选择那个priority+counter值最大的进程来调度执行。从逻辑上分析，SCHED_OTHER调度策略存在着调度周期（epoch），在每一个调度周期中，一个进程的priority和counter值的大小影响了当前时刻应该调度哪一个进程来执行，其中priority是一个固定不变的值，在进程创建时就已经确定，它代表了该进程的优先级，也代表这该进程在每一个调度周期中能够得到的时间片的多少；counter是一个动态变化的值，它反映了一个进程在当前的调度周期中还剩下的时间片。在每一个调度周期的开始，priority的值被赋给counter，然后每次该进程被调度执行时，counter值都减少。当counter值为零时，该进程用完自己在本调度周期中的时间片，不再参与本调度周期的进程调度。当所有进程的时间片都用完时，一个调度周期结束，然后周而复始。另外可以看出Linux系统中的调度周期不是静态的，它是一个动态变化的量，比如处于可运行状态的进程的多少和它们priority值都可以影响一个epoch的长短。值得注意的一点是，在2.4以上的内核中，priority被nice所取代，但二者作用类似。

可见SCHED_OTHER调度策略本质上是一种比例共享的调度策略，它的这种设计方法能够保证进程调度时的公平性--一个低优先级的进程在每一个epoch中也会得到自己应得的那些CPU执行时间，另外它也提供了不同进程的优先级区分，具有高priority值的进程能够获得更多的执行时间。

对于实时进程来说，它们使用的是基于实时优先级rt_priority的优先级调度策略，但根据不同的调度策略，同一实时优先级的进程之间的调度方法有所不同：

SCHED_FIFO：不同的进程根据静态优先级进行排队，然后在同一优先级的队列中，谁先准备好运行就先调度谁，并且正在运行的进程不会被终止直到以下情况发生：1.被有更高优先级的进程所强占CPU；2.自己因为资源请求而阻塞；3.自己主动放弃CPU（调用sched_yield）；
SCHED_RR：这种调度策略跟上面的SCHED_FIFO一模一样，除了它给每个进程分配一个时间片，时间片到了正在执行的进程就放弃执行；时间片的长度可以通过sched_rr_get_interval调用得到；

由于Linux系统本身是一个面向桌面的系统，所以将它应用于实时应用中时存在如下的一些问题：

Linux系统中的调度单位为10ms，所以它不能够提供精确的定时；
当一个进程调用系统调用进入内核态运行时，它是不可被抢占的；
Linux内核实现中使用了大量的封中断操作会造成中断的丢失；
由于使用虚拟内存技术，当发生页出错时，需要从硬盘中读取交换数据，但硬盘读写由于存储位置的随机性会导致随机的读写时间，这在某些情况下会影响一些实时任务的截止期限；
虽然Linux进程调度也支持实时优先级，但缺乏有效的实时任务的调度机制和调度算法；它的网络子系统的协议处理和其它设备的中断处理都没有与它对应的进程的调度关联起来，并且它们自身也没有明确的调度机制；

3. 各种实时Linux系统

3.1. RT-Linux和RTAI

RT-Linux是新墨西哥科技大学（New Mexico Institute of Technology）的研究成果[RTLinuxWeb][Barabanov97]。它的基本思想是，为了在Linux系统中提供对于硬实时的支持，它实现了一个微内核的小的实时操作系统（我们也称之为RT-Linux的实时子系统），而将普通Linux系统作为一个该操作系统中的一个低优先级的任务来运行。另外普通Linux系统中的任务可以通过FIFO和实时任务进行通信。RT-Linux的框架如图 1所示：

图 1 RT-Linux结构

RT-Linux的关键技术是通过软件来模拟硬件的中断控制器。当Linux系统要封锁CPU的中断时时，RT-Linux中的实时子系统会截取到这个请求，把它记录下来，而实际上并不真正封锁硬件中断，这样就避免了由于封中断所造成的系统在一段时间没有响应的情况，从而提高了实时性。当有硬件中断到来时，RT-Linux截取该中断，并判断是否有实时子系统中的中断例程来处理还是传递给普通的Linux内核进行处理。另外，普通Linux系统中的最小定时精度由系统中的实时时钟的频率决定，一般Linux系统将该时钟设置为每秒来100个时钟中断，所以Linux系统中一般的定时精度为 10ms，即时钟周期是10ms，而RT-Linux通过将系统的实时时钟设置为单次触发状态，可以提供十几个微秒级的调度粒度。

RT-Linux实时子系统中的任务调度可以采用RM、EDF等优先级驱动的算法，也可以采用其他调度算法。

RT-Linux对于那些在重负荷下工作的专有系统来说，确实是一个不错的选择，但他仅仅提供了对于CPU资源的调度；并且实时系统和普通Linux系统关系不是十分密切，这样的话，开发人员不能充分利用Linux系统中已经实现的功能，如协议栈等。所以RT-Linux适合与工业控制等实时任务功能简单，并且有硬实时要求的环境中，但如果要应用与多媒体处理中还需要做大量的工作。

意大利的RTAI( Real-Time Application Interface )源于RT-Linux，它在设计思想上和RT-Linux完全相同。它当初设计目的是为了解决RT-Linux难于在不同Linux版本之间难于移植的问题，为此，RTAI在 Linux 上定义了一个实时硬件抽象层，实时任务通过这个抽象层提供的接口和Linux系统进行交互，这样在给Linux内核中增加实时支持时可以尽可能少地修改Linux的内核源代码。

3.2. Kurt-Linux

Kurt-Linux由Kansas大学开发，它可以提供微秒级的实时精度[KurtWeb] [Srinivasan]。不同于RT-Linux单独实现一个实时内核的做法，Kurt -Linux是在通用Linux系统的基础上实现的，它也是第一个可以使用普通Linux系统调用的基于Linux的实时系统。

Kurt-Linux将系统分为三种状态：正常态、实时态和混合态，在正常态时它采用普通的Linux的调度策略，在实时态只运行实时任务，在混合态实时和非实时任务都可以执行；实时态可以用于对于实时性要求比较严格的情况。

为了提高Linux系统的实时特性，必须提高系统所支持的时钟精度。但如果仅仅简单地提高时钟频率，会引起调度负载的增加，从而严重降低系统的性能。为了解决这个矛盾， Kurt-Linux采用UTIME所使用的提高Linux系统中的时钟精度的方法[UTIMEWeb]：它将时钟芯片设置为单次触发状态（One shot mode），即每次给时钟芯片设置一个超时时间，然后到该超时事件发生时在时钟中断处理程序中再次根据需要给时钟芯片设置一个超时时间。它的基本思想是一个精确的定时意味着我们需要时钟中断在我们需要的一个比较精确的时间发生，但并非一定需要系统时钟频率达到此精度。它利用CPU的时钟计数器TSC(Time Stamp Counter)来提供精度可达CPU主频的时间精度。

对于实时任务的调度，Kurt-Linux采用基于时间（TD）的静态的实时CPU调度算法。实时任务在设计阶段就需要明确地说明它们实时事件要发生的时间。这种调度算法对于那些循环执行的任务能够取得较好的调度效果。

Kurt-Linux相对于RT-Linux的一个优点就是可以使用Linux系统自身的系统调用，它本来被设计用于提供对硬实时的支持，但由于它在实现上只是简单的将Linux调度器用一个简单的时间驱动的调度器所取代，所以它的实时进程的调度很容易受到其它非实时任务的影响，从而在有的情况下会发生实时任务的截止期限不能满足的情况，所以也被称作严格实时系统（Firm Real-time）。目前基于Kurt-Linux的应用有：ARTS（ATM Reference Traffic System）、多媒体播放软件等。另外Kurt-Linux所采用的这种方法需要频繁地对时钟芯片进行编程设置。

3.3. RED-Linux

RED-Linux是加州大学Irvine分校开发的实时Linux系统[REDWeb][ Wang99]，它将对实时调度的支持和Linux很好地实现在同一个操作系统内核中。它同时支持三种类型的调度算法，即：Time-Driven、Priority-Dirven、Share-Driven。

为了提高系统的调度粒度，RED-Linux从RT-Linux那儿借鉴了软件模拟中断管理器的机制，并且提高了时钟中断频率。当有硬件中断到来时，RED-Linux的中断模拟程序仅仅是简单地将到来的中断放到一个队列中进行排队，并不执行真正的中断处理程序。

另外为了解决Linux进程在内核态不能被抢占的问题， RED-Linux在Linux内核的很多函数中插入了抢占点原语，使得进程在内核态时，也可以在一定程度上被抢占。通过这种方法提高了内核的实时特性。

RED-Linux的设计目标就是提供一个可以支持各种调度算法的通用的调度框架，该系统给每个任务增加了如下几项属性，并将它们作为进程调度的依据：

Priority：作业的优先级；
Start-Time：作业的开始时间；
Finish-Time：作业的结束时间；
Budget：作业在运行期间所要使用的资源的多少；

通过调整这些属性的取值及调度程序按照什么样的优先顺序来使用这些属性值，几乎可以实现所有的调度算法。这样的话，可以将三种不同的调度算法无缝、统一地结合到了一起。

RED-Linux调度程序的框架结构如图 2所示：

图 2 RED-Linux调度框架

RED-Linux的调度程序由两部分组成，其中Schedule Allocator初始化到来的job中的属性值；Schedule Dispatcher根据job的属性值选择一个job进行执行；

3.4. Linux/RK

Linux/RK由卡内基梅隆大学实时和多媒体系统实验室所开发[RKWeb][ Oikawa98]。它是该实验室资源内核（Resource Kernel）[Rajkumar98]思想在Linux系统中的具体实现。他们最先在RT-MACH中实现了资源内核的思想，后来又用资源内核的思想对Linux进行了修改。资源内核的概念是网络中资源预留思想在操作系统领域的扩展，应用程序先向操作系统请求预留资源，而操作系统内核在给应用进行资源预留，并能给应用提供有及时的、保证的资源访问。

资源内核中有两个基本的概念：资源预留和资源集。一个资源预留代表一份计算资源，这个资源可以是CPU、内存、磁盘、网络带宽等。在内核中，一个资源预留有对应的描述它的数据结构，而一个资源集指一组资源预留的集合。一般情况下我们将某一个应用程序所请求的所有资源预留组合在一起组成一个资源集，这样方便管理和分配。

Linux/RK增强了普通Linux内核的功能，从而使Linux内核可以提供对于系统中各种计算资源的准入控制、资源预留和统计管理。Linux/RK由两部分组成：普通的Linux内核以及可移植的资源内核；这两个部分之间通过回调钩子函数（Callback hooks）进行交互。类似于RT-Linux，为了防止Linux内核中的封中操作以及提高调度精度，Linux/RK也截取系统中的中断，并提高了系统时钟频率，只有在需要的时侯才将中断送给Linux内核。另外它使用Proc文件系统来显示资源预留和使用的情况；

3.5. Qlinux

Qlinux是由AT&T、德州大学分布式多媒体计算实验室和马萨诸塞大学高级系统软件实验室联合开发出来的一种软实时(soft real-time)核心[QLinuxWeb]。它能够为实时多媒体应用提供QoS支持。

QLinux实现了近年来操作系统领域内一些最新的研究成果，包括：

- H-SFQ资源调度算法（Hierarchical Start-time Fair Queuing）[Goyal96]；

- 网络包的延迟处理技术（Lazy Receiver Processing:LRP）[Druschel96]；

- Cello磁盘调度算法[Shenoy98]；

图 3 QLinux系统结构

H-SFQ资源调度算法由由德州大学的Pawan Goyal等人提出，它采用了一种分级调度的思想，先将资源在不同的应用类别之间进行按比例分配，并在应用类别之间提供对于资源使用的隔离，同时在每一个应用类别中还可以使用不同的资源调度算法。这样做的目的是为了在多媒体系统中提供QoS支持。

LRP技术是一种新颖的设计OS网络子系统的思想，它由Rice大学计算机系的Peter Druschel等人提出，其目的是为了解决普通Unix和类Unix系统中网络包接收的问题。

传统的Unix系统没有对到来的网络包的协议处理的显式调度，它们一般采用中断驱动的机制。当网卡有中断时，CPU就立刻进行一系列由网卡中断程序启动的包接收和协议处理操作，将最终的数据送给等待接收的进程，并唤醒该进程。但这种处理方式会影响应用程序资源调度的性能，并在系统处于过载状态时可能会引起一些应用层任务的饥饿，降低网络吞吐率，甚至会让系统没有响应。为了解决这些问题，LRP的核心思想就是每一个Socket有一个IP包的队列，只有当上层应用程序请求数据时才进行协议处理，同时对协议处理操作以请求数据的应用的优先级进行显式的调度。通过这种途径增强了资源调度的公平性，能够提供一定程度的流量隔离，同时能够提高系统过载状态时的吞吐量。

Cello磁盘调度算法由德州大学Prashant J. Shenoy等人提出。它能够支持多种应用类别，比如：交互式尽力而为应用、大吞吐量尽力而为应用、以及软实时应用等类别，并公平地给各个类别的应用分配磁盘访问带宽。

在结构上Cello磁盘调度采用的是一种两级式的调度方式，它由多个与应用类别相关的调度器以及一个与应用类别无关的调度器组成（如图 4所示）。

图 4 Cello磁盘调度

Cello调度算法中应用类别无关的调度器管理时间上粗粒度的磁盘的调度，而应用相关的调度器控制着小粒度上磁盘调度。如上图中有n个应用类别，Cello使用一个应用无关的调度器C和n个类别相关的调度器，系统中有n+1个调度队列。类别无关的调度器C决定你了何时以及多少磁盘请求被从等待队列（pending queue）移到调度队列（scheduled queue）；类别相关的调度器Si对等待队列中的请求进行排序，并根据调度队列的状态来决定磁盘请求被插入到调度队列的什么位置。

3.6. Linux-SRT

Linux-SRT是剑桥大学David Ingram的博士论文项目[SRTWeb][Ingram00]，基本上是一个实验性的东西，自从Ingram在2000年从剑桥毕业以后，该项目就再没有人维护。跟QLinux一样，Linux-SRT属于软实时的Linux。

在Linux-SRT中可以给一个任务分配一定百分比的CPU时间，它通过RM算法实现了一种基于速率的调度机制来保证给所有多媒体应用的QoS需求；另外由于CPU并非唯一影响多媒体应用的资源，对于那些做图形显示的应用，X服务器中的资源调度也十分关键，所以Linux-SRT对XFree86最了扩展，让X服务器可以对来自不同X客户的图形显示请求进行优先级排序；另外为了方便用户管理各个进程的CPU分配情况，Linux-SRT提供了一个图形界面的程序。下面对于Linux-SRT对于普通Linux所作的修改做一具体说明。

Linux-SRT也提高了系统的定时精度。但它并没有采用惯用的将时钟芯片置于单次触发模式的做法，而是简单地修改了Linux内核中HZ的定义，将Linux的时钟频率由每秒100次提高到了1024。

另外Linux-SRT在原有的Linux系统中的SCHED_OTHER、SCHED_FIFO、SCHED_RR这三个调度策略的基础上，给Linux增加了一些新的调度策略：SCHED_PAUSE、SCHED_IDLE、SCHED_QOS、SCHED_VAR；策略为SCHED_PAUSE的进程在调度时被调度程序忽略，不参与调度执行；使用SCHED_QOS调度策略的进程能够得到有保证的CPU执行时间；使用SCHED_IDLE策略的进程优先级最低，它被分配给那些只在系统空闲时才能够被调度执行的进程，比如一些批处理程序；SCHED_VAR是一个可变优先级的策略，它被用于解决由于临界资源访问时所产生的优先级倒置问题，即一个高优先级的任务等待低优先级任务占用的某种临界资源，但低优先级任务又得不到CPU处理时间所造成的死锁问题；这时通过该调度策略将低优先级任务的优先级置为等待资源的高优先级任务的优先级（优先级继承）来解决死锁问题。

对于使用SCHED_QOS调度策略的实时任务，采用RM静态优先级调度算法进行调度；另外在进行调度时，它还采用了一种双调度策略的方案，即当一个实时任务在当前的调度周期中用完自己所有的时间片之后，在下次调度周期到来之前，并非简单地不调度执行它，而是使用它进程属性中的Fallback policy所定义的调度策略来调度它，让它以该策略参与本轮的剩余时间的调度。

Linux-SRT按照POSIX推荐的方式扩展了传统的几个用户设置进程调度属性的系统调度，让用户或者编程人员可以在后向兼容的情况下使用这些新添加的调度特性。另外为了使用的方便，它还提出了reserve的概念，一个reserve在/proc文件系统中有一个结点，它包含有关资源分配的情况；reserve独立与进程，一个进程可以通过新增加的reserve相关的系统调用申请加入（使用）或退出一个reserve。

3.7. Hard-hat Linux

Hardhat Linux是MontaVista公司所发布的一款主要面向各种嵌入式应用的Linux发布[HardHatWeb][Morgan01]。Hard-hat Linux最大的贡献在于：为了解决Linux在内核态不可被抢占的问题，它开发了一种抢占式（Preemptible）的内核，有人认为它的这种方法充其量也就是一种能够被抢占（Preemptable）的内核。

其基本思想就是让调度程序获得更多的执行机会，从而减少了从一个事件发生到调度程序被执行的时间间隔。可抢占内核的补丁包修改了spinlock的宏定义以及中断返回处理代码，当当前进程可以被"安全"地抢占并且有一个等待处理的重新调度请求，系统就会调用调度程序进行进程调度。

那么什么情况下可以认为一个进程可以被"安全"地抢占？最早的Linux内核代码认为，一旦进入内核态执行，不管是由于陷入（trap）还是中断处理，当前执行进程都不会被切换，直到内核认为可以安全地进行重新调度为止。这种思想可以使得内核代码对一些数据结构进行操作时比较简单，即不需要使用互斥原语（比如旋转锁spinlock）进行数据的修改保护就可以安全地存取数据。但随着内核源代码的发展，不使用保护机制的内核数据访问代码越来越少，所以在抢占式内核中，认为如果内核不是在一个中断处理程序中，并且不再spinlock保护的代码中，就认为可以"安全"地进行进程切换。

抢占式内核对普通Linux内核作了如下的一些修改：

抢占式内核给task struct数据结构增加了一个数据项：preempt_count。该数据项由宏preempt_disable()、preempt_enable()、以及preempt_enable_no_resched()所使用。preempt_disable对preempt_count计数进行递增，preempt_enable对preempt_count进行递减。preempt_enable宏查看当前进程的preempt_count和need_resched域的内容，如果 preempt_count为0并且need_resched为1，则调用preempt_schedule()函数。该函数将给当前进程的preempt_count项增加一个很大的值（比如让preempt_counter=preempt_counter + 0x4000000），然后调用进程调度函数schedule()，在schedule函数返回后从该进程preempt_count中再减去该值。可抢占内核也修改了schedule函数，它检测进程的preempt_counter是否很大（这是为了屏蔽一些普通调度流程中对于抢占式调度来说是冗余的那些操作），然后执行抢占式调度。
抢占式内核补丁也修改了spinlock的代码。在spin_lock()和spin_try_lock中增加了对于preempt_disable的调用，在spin_unlock()中增加了对于preempt_enable的调用。
另外抢占式内核补丁还修改了中断返回的代码，在其中增加了对于preempt_enable的调用。

所以我们根据上面的三个修改可以看出，内核的抢占式调度发生在如下情况：在释放spinlock时，或者当中断返回时，如果当前执行进程的need_resched被标记，则进行抢占式调度。

3.8. SILK

SILK代表SCOUT In Linux Kernel，它是普林斯顿大学支持PATH调度的垂直结构操作系统SCOUT在Linux中的一个实现[SILKWeb][Bavier01]。它将SCOUT操作系统作为Linux的一个模块来实现。

SILK系统的主要目的就是为一些网络QoS提供支持，它支持对于网络包处理的显式的调度，并且这个调度是以PATH为单位进行的。PATH概念的新颖之处在于，不像传统的基于任务的调度方式，它从另外一个角度进行系统的资源调度，即以网络的数据流及其处理为单位进行调度。详细来说，一个PATH由一串当数据流流经系统时进行数据处理或者数据转换的代码模块组成，并且对应的数据流所消耗的资源也归该PATH。研究表明，PATH这种体系结构特别适用于有QoS要求的分布式多媒体系统以及软件路由设备中。下图对于什么是PATH作了一个图示，它说明了一个TCP PATH：

图 5 一个TCP PATH

在实现上，SILK系统将Linux系统中的网络子系统替换成了自己的协议栈。Linux应用程序通过Socket来创建和使用PATHs，几乎不用对应用程序本身作任何修改。

图 6说明了SILK系统的结构。在图的左半部分，SILK模块和网络设备驱动、SOCKET接口层、以及包过滤接口netfilter通过标准的方式交换数据。SILK还修改了Linux任务的调度参数，以便影响Linux进程调度程序的调度决策。图的右半部分示意了SILK中的两个PATH。SILK模块有自己的CPU调度器，它和Linux系统中的CPU调度器进行合作和协调。这个合作由图中的Linux thread代表，通过执行这个线程，SILK将控制转给Linux调度程序。

图 6 SILK系统结构示意图

SILK在操作系统中提供了一个新的SOCKET协议族以便上层应用程序调用下层的SCOUT PATH。为了在Linux进行网络包处理之前截获IP包，SILK通过Linux 2.4内核的netfilter接口插入了一个netfilter hook，所有到来的IP包会被重定向到该hook上，如果SILK找到一个对应于该网络包的PATH，就让Linux内核丢弃该包，而由SILK对包进行处理。

关于CPU调度，SILK有着自己的CPU调度程序和线程包，它们和Linux系统的调度程序并存，在有SILK的Linux系统中，我们一般把由SILK调度的归属于某个PATH的处理叫做SILK线程（thread），而普通的由Linux调度程序调度的东西都叫做任务（task）；SILK在一个Linux内核任务的基础上实现它的线程调度，这个内核任务当SILK进行初始化的时候创建，并且将该内核任务的优先级设为优先级最高的实时任务，所以SILK的内核任务几乎是只要它就绪就可以投入运行，并且只有当该内核任务主动初让CPU时Linux系统中的其他普通任务才能够得以运行。SILK将CPU出让给普通的Linux任务是通过调度SILK thread中的一个叫做Linux thread的线程来实现的，该Linux thread本质上就是在SILK的调度空间中代表Linux的普通调度程序。SILK在调用Linux thread之后，代表SILK的内核任务就被Linux的进程调度程序设置为非就绪状态，直到它运行一个其他的进程之后，高优先级得SILK内核任务就又得到 CPU。所以这种实现机制可以让SILK在调度Linux thread时，Linux调度程序可以有机会调度一个其他的进程执行。

4. 实时Linux实现方案的总结

总结上述的各种实时Linux的实现，它们针对不同的设计目标，从不同的侧重点解决了通用Linux操作系统对实时性支持的问题。

针对Linux系统定时粒度过大的问题，一般的解决办法都是将实时时钟编程为单次触发的状态，然后利用CPU的时钟计数寄存器提供高达CPU时钟频率的定时精度。像RT-Linux和Kurt-Linux采用的就是这种方法。

对于Linux进程在进入内核态时不能被抢占的问题，目前的解决办法有RED-Linux在内核函数中插入抢占点的方法，另外Hardhat也通过修改spinlock的宏定义以及中断返回处理代码，实现了一种可抢占的内核；

对于Linux驱动程序中的封中断的方法，RT-Linux所使用的软件模拟中断控制器的方法可以有效地解决这个问题；

对于Linux系统中缺乏实时调度机制和调度算法的问题，目前有很多新颖的操作系统调度框架和调度算法都有Linux实现，比如RED-Linux所定义的一个通用的实时调度框架；QLinux所采用的分层式的CPU调度框架，及新颖的调度算法如H-SFQ，以及Cello磁盘调度算法等；SILK所使用的将对一个包的网络处理抽象成PATH，然后在PATH之间进行调度。

对于内核中协议处理以及中断处理的调度，解决办法基本上是一种延迟处理的技术，即到来的协议包在网卡中断处理中仅仅将它拷贝到一个队列中，只有当上层的应用程序请求数据包时才进行协议处理，并将对协议的处理时间记到对应的进程中。另外SILK对于那些网络路由结点，由于路由等的处理并没有对应的上层应用程序，所以SILK在内核的网络处理之间进行明确的调度。

所以，总的来说，从发展方向上来说，实时Linux的发展有如下四个思路：

提供对于硬实时的支持，具体办法有：提高时钟精度，解决封中断和内核态不能被抢占的问题，代表系统RT-Linux、Kurt-Linux，其实大部分实时Linux都使用了类似与RT-Linux的提高时钟精度和软件中断管理器的思想；总的来说，让内核支持硬实时和使用传统的Linux的丰富的系统调用之间存在着矛盾，以至于像RT-Linux就是单独实现了一个独立的小的硬实时操作系统；但由于软件模拟终端控制器、提高时钟精度、以及可抢占内核等思想的引入，这个矛盾慢慢地得到化解。
提供对于实时多媒体应用的支持，举措：引入新颖的调度算法（网络包调度，进程调度，磁盘调度），代表系统：QLinux、Linux-SRT；
引入新颖的调度框架以及资源管理思想以更好地支持网络系统中的QoS要求，比如SILK中的垂直结构的操作系统调度的思想，QLinux中的分级调度的思想，以及RED-Linux所提出来的一个通用的调度框架和Linux/RK中所使用的资源预留的思想；
方便的任务QoS管理接口函数和管理程序的实现，比如Linux/RK提出的操作系统中各种资源的资源预留的概念；Linux-SRT中为了用户方便地使用新增加的实时调度支持而增加了API，以及提出的reserve的概念等；

在实际的系统中，具体使用那种实时Linux技术，需要根据具体的系统需求而定。如果目标系统是像机床控制或者导弹飞行姿态控制这样的硬实时系统，那基于RT-Linux是一个不错的方案；如果一个系统对于实时性的要求不是那么严格，但又不是软实时系统，那么可以借鉴Kurt-Linux的想想以及一些为了提高Linux响应速度而提出的可抢占内核的想法；如果目标系统是一个像实时多媒体系统这样的软实时应用，或者一个希望能够在高负载状态下提供更好的吞吐率的服务器系统，那么QLinux和RED-Linux的思想提供了很好的参考；如果是将Linux应用于像路由器这样的网络结点中，可以借鉴SILK的实现思想。

回页首

参考资料

[Wang99]	Yu-Chung Wang and Kwei-Jay Lin, Implementing a General Real-Time Scheduling Framework in the RED-Linux Real-Time Kernel, IEEE Real-Time Systems Symposium, 1999
[Gopalan01]	Kartik Gopalan, Real-Time Support in General Purpose Operating Systems, Tech Report, 2001
[Krishna01]	C.M.Krishna, Kang G.Shin, Real-time Systems, Tsinghua Press, 2001
[Nieh01]	Jason Nieh, Chris Vaill, Hua Zhong, Virtual-Time Round-Robin: An O(1) Proportional Share Scheduler, Proceedings of the 2001 USENIX Annual Technical Conference, 2001
[RTLinuxWeb]	http://www.rtlinux.org/or http://fsmlabs.com/
[Barabanov97]	Michael Barabanov, A Linux-based Real-Time Operating System, A Master Thesis, New Mexico Institute of Mining and Technology, Socorro, New Mexico, 1997
[KurtWeb]	http://www.ittc.ku.edu/kurt/
[Srinivasan]	Balaji Srinivasan, A Firm Real-Time System Implementation using Commercial Off-The-Shelf Hardware and Free Software, Master Thesis, Department of Electrical Engineering and Computer Science, University of Kansas, Feb, 1998
[REDWeb]	http://linux.ece.uci.edu/RED-Linux/
[RKWeb]	http://www-2.cs.cmu.edu/~rajkumar/linux-rk.html
[Rajkumar98]	Raj Rajkumar, Kanaka Juvva, Anastasio Molano and Shui Oikawa, Resource Kernels: A Resource-Centric Approach to Real-Time Systems, In Proceedings of the SPIE/ACM Conference on Multimedia Computing and Networking January 1998
[Oikawa98]	Shui Oikawa and Raj Rajkumar, Linux/RK: A Portable Resource Kernel in Linux, In IEEE Real-Time Systems Symposium Work-In-Progress, Madrid, December 1998
[QLinuxWeb]	http://lass.cs.umass.edu/software/qlinux/
[Goyal96]	P. Goyal and X. Guo and H.M. Vin, A Hierarchical CPU Scheduler for Multimedia Operating Systems, Proceedings of 2nd Symposium on Operating System Design and Implementation (OSDI'96), Seattle, WA, pages 107-122, October 1996.
[Druschel96]	Peter Druschel, Gaurav Banga, Lazy Receiver Processing(LRP): A Network Subsystem Architecture for Server Systems, Proceedings of the 2nd Symposium on Operating System Design and Implementation (OSDI'96), Seattle, WA, Pages 261-275, October 1996
[Shenoy98]	P Shenoy and H M. Vin, Cello: A Disk Scheduling Framework for Next Generation Operating Systems, Proceedings of ACM SIGMETRICS Conference, Madison, WI, pages 44-55, June 1998.
[SRTWeb]	http://www.srcf.ucam.org/~dmi1000/linux-srt/
[Ingram00]	David Ingram, Integrated Quality of Service Management, Ph.D. Thesis, Jesus College, University of Cambridge, 2000
[HardHatWeb]	http://www.montavista.com/
[Morgan01]	Kevin Morgan, Preemptible Linux: A Reality Check, MontaVista White Paper, 2001
[SILKWeb]	http://www.cs.princeton.edu/nsg/scout/
[Bavier01]	Andy Bavier, Thiemo Voigt, Mike Wawrzoniak, Larry Peterson, SILK: Scout Paths in the Linux Kernel, Technical Report, Nov 2001
[UTIMEWeb]	http://www.ittc.ku.edu/utime/

回页首

关于作者


		张焕强，男，中国科学院软件研究所多媒体通信和网络工程研究中心博士，研究兴趣为家庭网络、实时系统、视频会议等。通过 zhq@iscas.ac.cn可以和他联系。

回页首

17:15 | 新增回應 | 永久連結 | 發佈至您的部落格 | Embed system / Linux

嵌入式操作系统的调试

developerWorks 中国 > Linux >

嵌入式操作系统的调试

文档选项

		将此页作为电子邮件发送
		未显示需要 JavaScript 的文档选项

Linux 2.4.x内核同步机制

developerWorks 中国 > Linux >

Linux 2.4.x内核同步机制

文档选项

		将此页作为电子邮件发送
		未显示需要 JavaScript 的文档选项

最新推荐

Java 应用开发源动力－下载免费软件，快速启动开发

级别: 初级

杨沙洲国防科技大学计算机学院

2002 年 6 月 01 日

本文将Linux内核中用于同步的几种机制集中起来分析，强调了它们之间在实现和使用上的不同。

同步通常是为了达到多线程协同的目的而设计的一种机制，通常包含异步信号机制和互斥机制作为其实现的底层。在Linux 2.4内核中也有相应的技术实现，包括信号量、自旋锁、原子操作和等待队列，其中原子操作和等待队列又是实现信号量的底层。

等待队列和异步信号

wait queue很早就作为一个基本的功能单位出现在Linux内核里了，它以队列为基础数据结构，与进程调度机制紧密结合，能够用于实现核心的异步事件通知机制。我们从它的使用范例着手，看看等待队列是如何实现异步信号功能的。

在核心运行过程中，经常会因为某些条件不满足而需要挂起当前线程，直至条件满足了才继续执行。在2.4内核中提供了一组新接口来实现这样的功能，下面的代码节选自kernel/printk.c：


    unsigned long log_size;
1:  DECLARE_WAIT_QUEUE_HEAD(log_wait);...
4:  spinlock_t console_lock = SPIN_LOCK_UNLOCKED;...
    int do_syslog(int type,char *buf,int len){
        ...
2:      error=wait_event_interruptible(log_wait,log_size);
        if(error)
             goto out;
        ...
5:      spin_lock_irq(&console_lock);
 ...
        log_size--;
        ...
6: spin_unlock_irq(&console_lock);
        ...
    }
    asmlinkage int printk(const char *fmt,...){
 ...
7: spin_lock_irqsave(&console_lock,flags);
        ...
        log_size++;...
8: spin_unlock_irqrestore(&console_lock,flags);
3:      wake_up_interruptible(&log_wait);
        ...
    }

这段代码实现了printk调用和syslog之间的同步，syslog需要等待printk送数据到缓冲区，因此，在2:处等待log_size非0；而printk一边传送数据，一边增加log_size的值，完成后唤醒在log_wait上等待的所有线程（这个线程不是用户空间的线程概念，而是核内的一个执行序列）。执行了3:的wake_up_interruptible()后，2:处的wait_event_interruptible()返回0，从而进入syslog的实际动作。

1:是定义log_wait全局变量的宏调用。

在实际操作log_size全局变量的时候，还使用了spin_lock自旋锁来实现互斥，关于自旋锁，这里暂不作解释，但从这段代码中已经可以清楚的知道它的使用方法了。

所有wait queue使用上的技巧体现在wait_event_interruptible()的实现上，代码位于include/linux/sched.h中，前置数字表示行号：


779 #define __wait_event_interruptible(wq, condition, ret)                  \
780 do {                                                                    \
781         wait_queue_t __wait;                                            \
782         init_waitqueue_entry(&__wait, current);                         \
783                                                                         \
784         add_wait_queue(&wq, &__wait);                                   \
785         for (;;) {                                                      \
786                 set_current_state(TASK_INTERRUPTIBLE);                  \
787                 if (condition)                                          \
788                         break;                                          \
789                 if (!signal_pending(current)) {                         \
790                         schedule();                                     \
791                         continue;                                       \
792                 }                                                       \
793                 ret = -ERESTARTSYS;                                     \
794                 break;                                                  \
795         }                                                               \
796         current->state = TASK_RUNNING;                                  \
797         remove_wait_queue(&wq, &__wait);                                \
798 } while (0)
799         
800 #define wait_event_interruptible(wq, condition)                         \
801 ({                                                                      \
802         int __ret = 0;                                                  \
803         if (!(condition))                                               \
804                 __wait_event_interruptible(wq, condition, __ret);       \
805         __ret;                                                          \
806 })

在wait_event_interruptible()中首先判断condition是不是已经满足，如果是则直接返回0，否则调用__wait_event_interruptible()，并用__ret来存放返回值。__wait_event_interruptible()首先定义并初始化一个wait_queue_t变量__wait，其中数据为当前进程结构current（struct task_struct），并把__wait入队。在无限循环中，__wait_event_interruptible()将本进程置为可中断的挂起状态，反复检查condition是否成立，如果成立则退出，如果不成立则继续休眠；条件满足后，即把本进程运行状态置为运行态，并将__wait从等待队列中清除掉，从而进程能够调度运行。如果进程当前有异步信号（POSIX的），则返回-ERESTARTSYS。

挂起的进程并不会自动转入运行的，因此，还需要一个唤醒动作，这个动作由wake_up_interruptible()完成，它将遍历作为参数传入的log_wait等待队列，将其中所有的元素（通常都是task_struct）置为运行态，从而可被调度到，执行__wait_event_interruptible()中的代码。

DECLARE_WAIT_QUEUE_HEAD(log_wait)经过宏展开后就是定义了一个log_wait等待队列头变量：


struct __wait_queue_head log_wait = {
 lock: SPIN_LOCK_UNLOCKED,
 task_list:      { &log_wait.task_list, &log_wait.task_list }
}

其中task_list是struct list_head变量，包括两个list_head指针，一个next、一个prev，这里把它们初始化为自身，属于队列实现上的技巧，其细节可以参阅关于内核list数据结构的讨论，add_wait_queue()和remove_wait_queue()就等同于list_add()和list_del()。

wait_queue_t结构在include/linux/wait.h中定义，关键元素即为一个struct task_struct变量表征当前进程。

除了wait_event_interruptible()/wake_up_interruptible()以外，与此相对应的还有wait_event()和wake_up()接口，interruptible是更安全、更常用的选择，因为可中断的等待可以接收信号，从而挂起的进程允许被外界kill。

wait_event*()接口是2.4内核引入并推荐使用的，在此之前，最常用的等待操作是interruptible_sleep_on(wait_queue_head_t *wq)，当然，与此配套的还有不可中断版本sleep_on()，另外，还有带有超时控制的*sleep_on_timeout()。sleep_on系列函数的语义比wait_event简单，没有条件判断功能，其余动作与wait_event完全相同，也就是说，我们可以用interruptible_sleep_on()来实现wait_event_interruptible()（仅作示意〉：


do{
 interruptible_sleep_on(&log_wait);
        if(condition)
  break;
}while(1);

相对而言，这种操作序列有反复的入队、出队动作，更加耗时，而很大一部分等待操作的确是需要判断一个条件是否满足的，因此2.4才推荐使用wait_event接口。

在wake_up系列接口中，还有一类wake_up_sync()和wake_up_interruptible_sync()接口，保证调度在wake_up返回之后进行。

回页首

原子操作和信号量

POSIX有信号量，SysV IPC有信号量，核内也有信号量，接口很简单，一个down()，一个up()，分别对应P操作和V操作，down()调用可能引起线程挂起，因此和sleep_on类似，也有interruptible系列接口。down意味着信号量减1，up意味着信号量加1，这两个操作显然需要互斥。在Linux 2.4中，并没有如想象中的用锁实现，而是使用了原子操作。

在include/asm/atomic.h中定义了一系列原子操作，包括原子读、原子写、原子加等等，大多是直接用汇编语句来实现的，这里就不详细解释。

我们从信号量数据结构开始，它定义在include/asm/semaphore.h中：


struct semaphore {
        atomic_t count;
        int sleepers;
        wait_queue_head_t wait;
}

down()操作可以理解为申请资源，up()操作可以理解为释放资源，因此，信号量实际表示的是资源的数量以及是否有进程正在等待。在semaphore结构中，count相当于资源计数，为正数或0时表示可用资源数，-1则表示没有空闲资源且有等待进程。而等待进程的数量并不关心。这种设计主要是考虑与信号量的原语相一致，当某个进程执行up()函数释放资源，点亮信号灯时，如果count恢复到0，则表示尚有进程在等待该资源，因此执行唤醒操作。一个典型的down()-up()流程是这样的：

down()-->count做原子减1操作，如果结果不小于0则表示成功申请，从down()中返回；
-->如果结果为负（实际上只可能是-1），则表示需要等待，则调用__down_fail()；
__down_fail()调用__down()，__down()用C代码实现，要求已不如down()和__down_fail()严格，在此作实际的等待（arch/i386/kernel/semaphore.c）：


void __down(struct semaphore * sem)
{
        struct task_struct *tsk = current;
        DECLARE_WAITQUEUE(wait, tsk);
        tsk->state = TASK_UNINTERRUPTIBLE;
        add_wait_queue_exclusive(&sem->wait, &wait);

        spin_lock_irq(&semaphore_lock);
        sem->sleepers++;
        for (;;) {
                int sleepers = sem->sleepers;

                /*
                 * Add "everybody else" into it. They aren't
                 * playing, because we own the spinlock.
                 */
                if (!atomic_add_negative(sleepers - 1, &sem->count)) {
                        sem->sleepers = 0;
                        break;
                }
                sem->sleepers = 1;      /* us - see -1 above */
                spin_unlock_irq(&semaphore_lock);

                schedule();
                tsk->state = TASK_UNINTERRUPTIBLE;
                spin_lock_irq(&semaphore_lock);
        }
        spin_unlock_irq(&semaphore_lock);
        remove_wait_queue(&sem->wait, &wait);
        tsk->state = TASK_RUNNING;
        wake_up(&sem->wait);
}

__down()-->当前进程进入wait等待队列，状态为不可中断的挂起，sleepers++，如果这是第一次申请失败，则sleepers值为1，否则为2--这个设置纯粹是为了下面这句原子加而安排的。

在真正进入休眠以前，__down()还是需要判断一下是不是确实没有资源可用，因为在spin_lock之前什么都可能发生。atomic_add_negative()将sleepers-1（只可能是0或者1，分别表示仅有一个等待进程或是多个）加到count（如果有多个进程申请资源失败进入__down()，count可能为-2、-3等）之上，这个加法完成后，结果为0只可能是在sleepers等于1的时候发生（因为如果sleepers等于2，表示有多个进程执行了down()，则count必然小于-1，因此sleepers-1+count必然小于0），表示count在此之前已经变为0了，也就是说已经有进程释放了资源，因此本进程不用休眠而是获得资源退出__down()，从而也从down()中返回；如果没有进程释放资源，那么在所有等待进程的这一加法完成后，count将等于-1。因此，从down()调用外面看（无论是在down()中休眠还是获得资源离开down()），count为负时只可能为-1（此时sleepers等于1），这么设计使得up()操作只需要对count加1，判断是否为0就可以知道是否有必要执行唤醒操作__up_wakeup()了。

获得了资源的进程将把sleepers设为0，并唤醒所有其他等待进程，这个操作实际上只是起到恢复count为-1，并使它们再次进入休眠的作用，因为第一个被唤醒的等待进程执行atomic_add_negative()操作后会将count恢复为-1，然后将sleepers置为1；以后的等待进程则会像往常一样重新休眠。

将down()操作设计得如此复杂的原因和结果就是up操作相当简单。up()利用汇编原子地将count加1，如果小于等于0表示有等待进程，则调用__up_wakeup()-->__up()唤醒wait；否则直接返回。

在down()中竞争获得资源的进程并不是按照优先级排序的，只是在up()操作完成后第一个被唤醒或者正在__down()中运行而暂未进入休眠的进程成功的可能性稍高一些。

尽管可以将信号量的count初始化为1从而实现一种互斥锁（mutex），但Linux并不保证这个count不会超过1，因为up操作并不考虑count的初值，所以只能依靠程序员自己来控制不要无谓的执行up()从而破坏mutex的语义。相关的初始化接口定义在include/asm/semaphore.h中，但一般程序员可以通过sema_init()接口来初始化信号量：


#define DECLARE_MUTEX(name) __DECLARE_SEMAPHORE_GENERIC(name,1)
#define DECLARE_MUTEX_LOCKED(name) __DECLARE_SEMAPHORE_GENERIC(name,0)
static inline void sema_init (struct semaphore *sem, int val)
static inline void init_MUTEX (struct semaphore *sem)
static inline void init_MUTEX_LOCKED (struct semaphore *sem)

除了down()以外，Linux还提供了一个down_interruptible()，操作序列与down()基本相同，仅在休眠状态为可中断和信号处理上有所不同。在标准的信号量以外，还有一套读写信号量，用于将资源的读写区分开来进行同步以提高效率，采用读写锁来实现，有兴趣的可以参阅文后列出的参考资料。

回页首

自旋锁

锁是一个概念，正如上面提到的mutex互斥锁仅仅是其中的一种。互斥锁被锁定时进入休眠，而系统还能正常运转，但有很多时候，锁应该不仅仅互斥访问，甚至应该让系统挂起，直至锁成功，也就是说在锁操作中"自旋"，这就是Linux中的spinlock机制。

从实现上来说，自旋锁比较简单，主要分为两部分，一部分是中断处理，一部分是自旋处理，最基础的部分在spin_lock_string和spin_unlock_string这两段汇编代码中：


#define spin_lock_string \
        "\n1:\t" \
        "lock ; decb %0\n\t" \
        "js 2f\n" \
        ".section .text.lock,\"ax\"\n" \
        "2:\t" \
        "cmpb $0,%0\n\t" \
        "rep;nop\n\t" \
        "jle 2b\n\t" \
        "jmp 1b\n" \
        ".previous"
#define spin_unlock_string \
        "movb $1,%0"

不详细解释这段汇编代码的语义，spin_lock_string对锁原子减1，循环检查锁值，直到锁值大于0；而spin_unlock_string则是对锁赋值1。spin_lock_string用于构成spin_lock()函数，spin_unlock_string用于构成spin_unlock()函数。

spin_lock()/spin_unlock()构成了自旋锁机制的基础，它们和关中断local_irq_disable()/开中断local_irq_enable()、关bh local_bh_disable()/开bh local_bh_enable()、关中断并保存状态字local_irq_save()/开中断并恢复状态字local_irq_restore()结合就形成了整套自旋锁机制，接口定义在include/linux/spinlock.h中，这里就不列举了。

实际上，以上提到的spin_lock()都是在CONFIG_SMP的前提下才会生成的，也就是说，在单处理机系统中，spin_lock()是一条空语句，因为在处理机执行它的语句时，不可能受到打扰，语句肯定是串行的。在这种简单情况下，spin_lock_irq()就只需要锁中断就可以完成任务了。在include/linux/spinlock.h中就用#ifdef CONFIG_SMP来区分两种不同的情况。

自旋锁有很多种，信号量也可以用来构成互斥锁，原子操作也有锁功能，而且还有与标准锁机制类似的读写锁变种，在不同的应用场合应该选择不同的锁，下一节就是介绍如何选择。

回页首

锁的使用

1.用户上下文之间

如果所访问的共享资源仅在用户上下文中使用，最高效的办法就是使用信号量。在net/core/netfilter.c中有一处使用信号量的例子：


static DECLARE_MUTEX(nf_sockopt_mutex);
int nf_register_sockopt(struct nf_sockopt_ops *reg)
{
...
        if (down_interruptible(&nf_sockopt_mutex) != 0)
                return -EINTR;
...
out:
        up(&nf_sockopt_mutex);
        return ret;
}

2.用户上下文与bottom half之间

此时有两种情况需要使用锁，一是用户上下文被bottom half中断，二是多个处理机同时进入一个临界段。一般情况下，使用spin_lock_bh()/spin_unlock_bh()可以满足要求，它将关闭当前CPU的bottom half，然后再获取锁，直至离开临界段再释放并对bottom half重新使能。

3.用户上下文与软中断（Tasklet）之间

tasklet与bottom half的实现机制是一样的，实际上spin_lock_bh()也同时关闭了tasklet的执行，因此，在这种情况下，用户上下文与tasklet之间的同步也使用spin_lock_bh()/spin_unlock_bh()。

4.bottom half之间

bottom half本身的机制就保证了不会有多于1个的bottom half同时处于运行态，即使对于SMP系统也是如此，因此，在设计共享数据的bottom half时无需考虑互斥。

5.tasklet之间

tasklet和bottom half类似，也是受到local_bh_disable()保护的，因此，同一个tasklet不会同时在两个CPU上运行；但不同的tasklet却有可能，因此，如果需要同步不同的tasklet访问共享数据的话，就应该使用spin_lock()/spin_unlock()。正如上面提到的，这种保护仅对SMP系统有意义，UP系统中tasklet的运行不会受到另一个tasklet（不论它是否与之相同）的打扰，因此也就没有必要上锁。

6.softirq之间

softirq是实现tasklet和bottom half的基础，限制较后二者都少，允许两个softirq同时运行于不同的CPU之上，而不论它们是否来自同一个softirq代码，因此，在这种情况下，都需要用spin_lock()/spin_unlock()来同步。

7.硬中断和软中断之间

硬中断是指硬件中断的处理程序上下文，软中断包括softirq和在它基础上实现的tasklet和bottom half等，此时，为了防止硬件中断软中断的运行，同步措施必须包括关闭硬件中断，spin_lock_irq()/spin_unlock_irq()就包括这个动作。还有一对API，spin_lock_irqsave()/spin_unlock_irqrestore()，不仅关闭中断，还保存机器状态字，并在打开中断时恢复。

8.其他注意事项

首先需要提醒的是"死锁"，这在操作系统原理的课本上都做过介绍，无论是使用信号量还是使用自旋锁，都有可能产生死锁，特别是自旋锁，如果死锁在spin_lock上，整个系统就会挂起。如何避免死锁是理论课的问题，这里就不多说了。

另外一点就是尽可能短时间的锁定，因此，"对数据上锁，而不是对代码上锁"就成了一个简单的原则；在有可能的情况下，使用读写锁，而不要总是使用互斥锁；对读写排序，使用原子操作，从而完全避免使用锁，也是一个不错的设计思想。

不要在锁定状态下调用可能引起休眠的操作，以下这些操作就是目前可能因此休眠的函数：

对用户内存的访问：copy_from_user()、copy_to_user()、get_user()、put_user()
kmalloc(GFP_KERNEL)
down_interruptible()和down()，如果需要在spinlock中使用信号量，可以选择down_trylock()，它不会引起挂起 printk()的灵巧设计使得它不会挂起，因此可以在任何上下文中使用。

回页首

参考资料

Linux Kernel Source Code 2.4.2
《Linux内核源代码情景分析》，毛德操、胡希明著，2001年9月浙江大学出版社
《Linux内核2.4版源代码分析大全》，李善平等著，2002年1月机械工业出版社
《Linux Device Drivers》，Alessandro Rubini & Jonathan Corbet，2001年8月 O'Reilly
Linux DocBook -- Unreliable Guide To Locking

回页首

关于作者


		杨沙洲，现为国防科技大学计算机学院博士生，主要研究领域为操作系统技术

13:05 | 新增回應 | 永久連結 | 發佈至您的部落格 | Embed system / Linux