基于物联网驱动的Linux系统的研究与改进.docx

基于物联网驱动的1.inUX系统的研究与改进徐高峰摘要物联网作为一种正处于蓬勃发展阶段的新兴技术，越来越受到人们的关注。物联网是“物与物相连构成的互联网络”，也可以理解为嵌入式智能终端的网络化形式。因此它的发展给其环境下的嵌入式系统、无线传感网络等核心技术带来了新的机遇。嵌入式技术作为物联网产业发展的核心推动力，它的灵魂是嵌入式操作系统。嵌入式操作系统中，1.inUX凭借自身的模块化设计、可剪裁等特点成为了目前使用最为广泛的系统之一，但由于1.inux一直以来是以通用分时系统的角色存在的，所以如果将其直接用在物联网的嵌入式系统中是不能满足物联网技术中对实时性的要求的。针对这个问题，本文研究了已成功的1.inUX实时化方案，指出了它们的优点及不足。并基于标准的2.6内核，对调度算法中与实时性相关的源代码进行了深入分析。在实时化改进方面的主要研究及改进成果有：1）标准内核实时性不足的原因：实时任务的动态优先级一经设定是不会改变的，即实际上是“静态”的，没有实现真正意义上的动态调度。2）对动态调度算法RM（RateMonotonicAnalysis）EDF（EarliestDeadlineFirst）以及1.1.F（1.eaSt1.aXityFirst,基于EDF的改进算法）的介绍及优缺点分析。3）针对1.1.F算法在调度过程中存在的“颠簸”问题，本论文提出了基于变更期的1.1.F算法，并在标准的2.6内核中进行了实现。核心思想是：在进程切换时，把当前进程的裕度值更新为1,且在变更期内生效。这样不但大大地减少了原1.1.F算法中由于频繁切换而导致的资源浪费，而且还保证了新系统的可抢占性，能有效地提升系统的实时性能。物联网环境下的Zigbee技术，是无线传感网络中使用的最重要技术。目前.，在物联网的应用中，使用该技术一般都是采用Zigbee模块的形式。Zigbee模块是商家通过专用硬件以及软件开发平台为用户的再次开发提供的一套完整开发环境。它的优点是使用起来简单、方便，且花费的时间也较短；缺点是功能单一。虽然其暂时拥有了市场、赢得了利益，但从长远的角度分析，伴随着物联网的发展，嵌入式应用领域会变得越来越复杂、多变，单靠其单一的功能，其在未来的物联网市场上必将失去核心竞争力。基于以上分析，为了体现在具有Zigbee无线通信能力的同时，又能更好地发挥1.inux操作系统在物联网中的重要作用，实现一个基于Zigbee技术的专用1.inux内核将成为未来发展趋势，所以本课题提出了在1.inux系统中实现Zigbee协议栈的想法。该内核在具有1.inUX系统强大功能的同时又具有了Zigbee无线通信的能力。这方面的研究内容及成果有：1）分析了Zigbee协议栈的分层结构，并且对各层的工作做了详细的概述。2）分析了1.inux系统中实现Zigbee协议栈的可行性。3）提出了在1.inUX系统中实现Zigbee协议栈的想法,并给出了1.inUX_Zigbee的网络体系框架。4）基于提出的想法，给出了部分关键数据结构的实现。在论文的最后一个章节，对实时性的改造部分进行了实验，并和原系统进行了数据的对比，结果表明，引入基于变更期的1.1.F算法后的内核在对实时任务的响应上有所增强。关键字：1.inUX操作系统，嵌入式实时系统，物联网，ZigBee无线技术1前言12物联网及1.inux系统概述22.1物联网简介22.2Zigbee无线通信技术32.3Zigbee技术应用现状42.4嵌入式操作系统52. 5实时Iinux系统研究进展631.inux调度算法实时性分析与改进73. 11.inux2.6进程调度分析与研究73.1.1进程调度基本过程73.1.2三种调度策略及不足113.2实时系统调度算法123. 2.1RM倜度算124. 2.2EDF调度算法125. 2.31.1.F调度算法123. 3基于变更期的1.1.F算法的设计及实现133. 3.1taskstruct的扩展144. 3.2j145. 3.3scheduler_tick156. 3.4任务切换函数157. 3.5基于变更期的1.1.F算法的设计168. 1.inux系统中Zigbee协议栈的构建184. 1Zigbee协议栈分析184. 2可行性分析204. 31.inux内核网络结构204. 3.1各层功能分析214. 3.2网络结构特点254. 41.inux_Zigbee网络体系的设计264. 5关键数据结构305实验与分析325. 1实时性能评价指标325.2系统内核构建325.3测试工具介绍335.4测试及讨论345.4.1基于变更期的1.1.F算法性能测试355.4.2中断延迟测试365.4.3调度延迟测试366总结39i.40致谢421前言物联网技术是把人和人间的信息交换扩展到了人和人、人和物、物和物之间，它的目标是要实现信息空间、人类社会及物理世界的融合和连通，它引领着未来网络技术的发展趋势，被认为是信息领域的又一次重大发展及机遇。同时，它必将促进人和自然的和谐发展，为信息产业提供一个巨大的发展空间。伴随物联网的发展，对嵌入式系统的要求也越来越高。1.inUX操作系统因具有廉价、稳定、开源等众多优势，使得其在嵌入式领域一直受到很多开发者的青睐。且凭借自身的优势一直以来都被作为嵌入式操作系统的首要选择，所以物联网的发展一方而要求1.inUX系统在实时性方面不断提高；另一方面，无线通信技术作为物联网中另一个关键技术，在市场上主要以无线模块的形式存在，其大都功能单一，因此无线通信模块有待于进一步提升，才能跟上物联网的发展，应对未来复杂的应用。首先，2.6内核是基于静态优先级调度策略的，不支持动态实时优先级调度。而面对物联网应用中的多变环境，单一的静态优先级方法将无法满足物联网嵌入式应用中强实时需求。所以，在2.6内核中引入实时进程的动态优先级调度方法成为必要，即进程的优先级不再是静态值，而是随着某些变化而变化，从而增强内核的实时性能。其次，针对市场上无线通信模块功能的单化问题，考虑在1.inUX系统中引入Zigbee（协议栈），引入该协议栈后系统不但能够满足无线通信的功能而且还能够具有标准内核管理的强大功能，这个基于Zigbee的嵌入式操作系统软件平台将能满足物联网未来发展中的复杂需求。本课题是基于物联网驱动的1.inux操作系统的研究与改进，关键就是针对1.inux操作系统在嵌入式系统应用中存在的实时性方面的不足，进行的研究与改进，具体操作是引入了新的调度算法；同时，又通过分析1.inUX操作系统的网络架构，结合Zigbee协议栈的框架提出了在1.inux操作系统中实现Zigbee协议栈的构想。总之，对1.inUX操作系统在实时性能方面的改进，及在网络结构方面的想法，不仅具有理论价值，而且从实用价值看，也必将推动嵌入式系统的发展，从而带动物联网技术走向产业化，从整体上推动我国物联网产业的发展，还会带动一批新的服务行业的产生和发展，社会效益显著。2物联网及1.inUX系统概述2.1 物联网简介物联网可以说是物和物、人和物之间的信息传递和控制。在物联网应用中最关键的三项技术是：(1)无线传感网络WSN(WirelessSensorNetworks)是大量的静止或移动的传感器以自组织和多跳的方式构成的无线网络。使用过程中，用户端根据需要通过管理站点发送相关的指令从而可达到对传感器网络的管理，如发布监测命令从而收集监测到的数据。其体系结构如图2.1所示：图27无线传感器网络体系结构图图2-1中的普通节点一般是个具有简单的存储、处理、通信能力的嵌入式系统，同时该系统还有感知环境数据的能力。从网络的角度分析，每一个传感器节点有着普通节点与路由的双重身份，即不但要收集本地数据和进行数据的处理，还要对其它节点派送过来的数据进行处理，与此同时，还能协作其它节点共同完成某些特定工作。网关设备以无线方式与传感器网络连接，再通过有线方式或者无线方式连接到Internet等外部网络，即实现两种不同通信协议栈的转换。它不但可以发布一些对基站的检测任务，还可以把采集到的数据转发到外部网络中。(2)无线射频技术RFID(RadioFrequencyIdentificationDevices)»是一种自动无线识别及数据获取技术。RFID标签就是将无线射频技术及嵌入式技术融合为一体的技术，且能适应于恶劣的环境中，因此它在物品物流管理、自动识别等领域有着广阔的应用前景。(3)嵌入式系统技术。该技术综合了传感器技术、计算机软硬件、电子应用技术、集成电路技术为一体的复杂技术。从结构上看，物联网有感知层、网络层、应用层。技术架构图如图2-2所示：应用层智能家居城市管理工业监控环境监测智能交通绿色农业网络层云平台2G网络管理中心3G网络(T)64G网络感知层RFID读写器/标签M2M终端、传感器/摄像头传感器网关传感器网络传感器网关传感器网络图2-2物联网技术架构图2.2Zigbee无线通信技术在物联网这个巨大网络中，传感设备与网络间的通信是通过有线或者无线的方式进行的。但是从系统建设、维护、投资等几个方面考虑，无线传输技术显然具有更大优势。而物联网应用领域中要想成功地发挥无线传感器网络之强大功能，Zigbee技术是再合适不过的技术了581.作为一种新兴技术，Zigbee凭其著多优点被广泛应用。Zigbee技术与常用无线通信技术的对比如图2-3所示：主要技术应用范围优势缺点成本蓝牙遥感勘测、数字电子设备、工业控制、智能化建筑、家庭和办公自动化、无线公文包等替代有线，应用较多、成本较低且方便使用以移动电话为中心，每网最多8个节点低于5美元Wi-FiWeb/Emai!/Video等相关应用使用现有网络、高速率、组网以活高功耗、协议开销大、需要接入点约20美元Zigbee家庭、楼宇自动化等可靠、安全、组网方便等缺少安全性规范和完善的标准50美分左右图2-3常用无线技术对比图Zigbee技术特点网有数据传输速率低、功耗低、安全、网络容量大、时延短等优点。因此，把Zigbee无线网络传输技术应用于物联网中是最为可靠、经济的手段之一，基于Zigbee技术的优点，本课题提出了在1.inUX系统中实现Zigbee协议的想法。2.3Zigbee技术应用现状智能家居、工业监控、智能交通、绿色农业等都是物联网的典型应用领域,实现过程中Zigbee节点的硬件结构如图2-4所示：图2-4Zigbee节点硬件结构图而Zigbee技术在物联网中具体的应用方案，有两种方式可供选择：第一种：选择芯片。选择Zigbee芯片后要根据自己的需要进行Zigbee应用设计，这种方式需要对软件及Zigbee协议栈非常了解，还需要有高频设计的相关知识和经验，开发周期将会比较长。第二种：选择Zigbee模块。Zigbee无线通信模块，是已经包含了所有外围电路及完整Zigbee协议栈的且随时能够使用的产品。解决了用户方案设计的难题，使用时只需将Zigbee模块作为一个透明的元器件，也可以直接将模块焊接到相关设备的线路板上以达到无线通讯的功能。所以这种方法只需把重点放在设计解决方案上，花费的时间较短，且应用起来也显得容易了很多。Zigbee无线通信作为物联网应用中的关键技术，不管是选择Zigbee芯片还是选择Zigbee模块，都有其不足之处。选择Zigbee芯片开发周期长，且要对协议栈足够的了解，一定程度了增加了复杂度；而选择模块的缺点有：首先，硬件上使用的都是单片机，与ARM芯片存在着一定的差距，主要体现在ARM芯片属于微处理器而单片机只能叫做微控制器。其次，软件上，由于是基于单片机实现的功能，所以只有针对无线通信的技术内容。因此随着嵌入式系统的不断发展，嵌入式应用的复杂度的不断提高，现在基于单片机开发的Zigbee无线通信技术将不能胜任物联网应用的发展。所以在嵌入式1.inUX系统中引入Zigbee（协议栈）将成为未来的主流技术，也就是说它不但能满足无线通信的功能而且还能够有1.inUX内核的存储、任务、中断管理等强大功能，即所谓的Zigbee嵌入式操作系统软件平台，就能满足物联网应用中的复杂需求。另外，还可以在这个软件平台上根据具体的应用开发出不同的Zigbee控制器，使节点的应用更加方便、直接。通过上述分析可知，嵌入式1.inux系统中引入Zigbee将有绝对的必要性和市场竞争力，必将是未来发展的趋势。2. 4嵌入式操作系统嵌入式的发展经历了由简单到复杂的过程。嵌入式系统的硬件和软件资源也在不断的庞大，因此系统中引入管理系统资源的软件成为必要，即嵌入式操作系统。目前较为流行的主要嵌入式操作系统有VXWOrks,PalmOS,WindowsCE,QNX等。首先它们都是商业性的嵌入式操作系统，使用它们要承担昂贵的费用。其次，这些系统的内核源码并不公开，对开发者来说要去深入理解它、改动它就相当的困难。所以这些问题在一定程度上阻碍了嵌入式技术的发展。而1.ilWX的存在，使得其在嵌入式系统方面大放光芒HOJe1.imIX作为嵌入式操作系统实时性能不足的主要原因有U比（1）实时调度：传统的1.inUX操作系统为使进程能公平的使用资源，采用的是分时策略，也因此系统的实时响应能力有所下降。虽然后来的1.inUX版本针对此问题做了一些实时改进，如2.6内核有了抢占式内核、有了O（I）调度算法等改进，但内核并没有实现动态优先级调度。物联网应用中嵌入式的应用环境是千差万别的，特别是调度算法应该满足动态优先级的要求，所以原来的静态优先级策略是不能满足嵌入式系统对实时性的要求的。（2）内存管理机制：1.inux用的是虚拟内存管理机制，包括有交换、请求分页等技术。即内核在创建进程时，不是一次性分配给进程内存，而是通过虚拟内存分配。且页表不是全部装入内存，而只保留当前用的那部分页面，其它的要到实际运行的时候，通过产生缺页中断，才调入需要的页面。而物联网应用中，嵌入式系统将会有频繁的访问且响应时间要及时，所以1.inux的内存机制在嵌入式系统的实时应用中存在着不足。（3）中断机制：在1.inUX的系统调用中，中断处理后为了保护临界区资源，用的是关中断方法，也就是说系统在关中断这段时间内，是无法响应任务的，即使有实时任务进来，也要等到中断处理之后才能得到响应，所以从嵌入式实时系统的角度来看，就削减了系统的实时性。3. 5实时IinUX系统研究进展鉴于1.inux对嵌入式系统发展的重要性，许多机构或者个人都在为应用于嵌入式领域的1.inUX实时性改进而努力，并做了大量的研究工作，但主要围绕双核技术和修改内核代码两种形式进行，下面是对改进后的实时1.inux系统成果的分析H2网(1)双核技术是指系统中的内核是用两个不同职责的内核来实现的，一个负责实时任务的处理，另一个负责非实时任务的处理，相互配合完成系统的功能。这种方法在保持了原有1.inUX内核的独立性，避免了对原内核的大幅度改动，同时也保持了RT-1.inux其他部分对传统1.inux系统的兼容性。由于RT-1.inux不但有标准1.inUX的强大功能，而且还支持硬实时，所以已经成功地应用于航天飞机等高科技领域。双核技术的RT-1.inux虽然已很好地满足了嵌入式系统的硬实时要求，但还是有不足之处。一方面，针对RT-1.inux实时任务的开发只是基于实时内核的，而不是面向传统1.inUX的。因此，由此导致了传统1.inUX成熟的技术和资源没有被充分地利用。另一方面，RT-1.inUX的实时进程存在内存安全隐患。由于实时任务的处理位置，即系统的核心层，是没有内存保护功能的。所以如果实时任务出现了错误，及有可能引起系统问题。(2)进程调度是关系系统实时性能的主要因素。对调度策略的优化主要是引入新的调度策略，来提高系统的实时性能。有基于优先级的、基于时间驱动的或者基于比例共享的策略等。但从已经成功的案例看，主要体现在对单调速率(RM)算法以及最早期限优先(EDF)算法的引进或者优化。第一种主要用于静态周期任务的调度；第二种主要用于动态优先的调度。另外也有一些是重新编写一个实时调度器，但这样做需要涉及的东西较多，改动较大，会破坏标准1.inux系统的某些特性。所以通常都是采用引入新的调度算法来提高系统的实时性。31.inUX调度算法实时性分析与改进本章将基于内核中与实时性能相关的源代码，首先讨论1.inux2.6调度策略的不足；其次介绍经典的RM算法和EDF算法，分析各个算法中的不足，并针对不足之处进行研究和改进；最后，将改进后的算法引入到内核的调度算法中，以提高内核的实时性能。4. 11.inux2.6进程调度分析与研究1.inUX内核作为1.inUX系统的核心，它由进程调度、虚拟文件系统、内存管理、进程间的通信和网络接口五个子系统构成，其内核模块依赖图如图31所示1,71o首先调度器的选择，一是关系到系统是否有较高的系统吞吐量和较短的响应时间；二是关系到候选进程的选取，找到候选进程并将其投入运行。其次调度算法的优劣直接决定了资源分配能不能达到最优化的问题。可见，基于成功的调度器，调度算法的好坏直接关系到系统尤其是实时系统的性能。3.1.1进程调度基本过程2.4内核中调度算法较简单，且是基于优先级的，该算法中，只有一个表头为HlnqUeue_head的全局运行队列，选择下一个进程时，schedule。函数就会遍历整个队列，找出next进程并投入运行。同时，该算法中也仅使用一个全局的自旋锁实现对运行队列的保护，所以这就导致了各个处理器之间的等待延迟。与2.4内核相比，2.6内核的亮点在于引进了O(I)调度算法且实现了可抢占的调度方式。2.6调度算法中增加了运行队列结构runqueue,每个CPU都将维护自己的runqueue结构的运行队列，大大减少了处理机之间的竞争。该队列中涉及到的核心数据结构包括prio_array_t*active,*eapired以及arrays0结构体中数组queue表示就绪队列,它的下标就是进程的优先级(共140级)，优先级为i的进程都存放在queuei中。调度的过程中先找优先级i再寻找active数组中相对应的元素，最后将该元素中的队首元素作为侯选next进程。每个CPU的运行队歹胆9侬如图32所示：图3-2CPU的运行队列图2.6内核的调度算法是基于优先级，选取侯选进程的过程就是寻找系统就绪队列中优先级权值最高的那个进程。内核优先级标度如图3-3所示：高优先级-2019实时优先级普通优先级099100139图3-3内核优先级标度(1) )static_priostatic_prio相当于2.4内核中的nice值(代表一个进程的谦让程度,缺省为0,范围大小是-19到20),只是nice的值被映射到新的取值区间，从数值范围理解,它们之间的关系表示为：static_prio=MAX_RT_PRIO+nice+20=nice+120。StatijPrio代表分配给进程的时间片，进程创建时与time_slice的值相同，随着程序的执行，StatiC_prio的不变，time_slice不断减小。(2) prio动态优先级的计算由函数effectiVJPrio()完成，它的运算分散在各个进程的运行过程中，即只要进程有所变化，内核便会计算它的值。它的变化主要涉及到的进程属性值有：sleep_avg(进程平均等待时间)、静态优先级。sleep_avg的大小等于进程的等待时间和运行时间之间的差值，值越大，得出的动态优先级也就越大。(3) rt_priority实时优先级rt_priority指明rt_priority权值较高的进程总是先于低rt_priority权值的进程。当进程为非实时进程时，rjpriority的值为0,因此，实时进程总会先于非实时进程执行。它是在函数SetSChedUIer()中设置的，且一经设定就不会再改变。(4) SchecIuleO2.6内核调度器与之前2.4内核相比，最大的优点在于工作量上的简化，主要表现在优先级的计算上不再集中计算而是分散计算。调度器的工作流程可以概括为五个步骤：清理当前任务、选择next进程、设置进程next运行环境、上下文切换以及后期处理。其中，函数SChedUle()是主要的调度器函数-2%下面是该函数的关键部分代码分析：数组active与expired的切换查找next进程时，如果active数组为空，则切换active与expired两个数组，进入新一轮调度。查找next进程优先级数组prio_array设计巧妙，所以2.6内核选择候选进程next的过程简单、高效。首先，查找优先级位图bitmap中第一个值为1的位置；idx=sche_find_frist_bit(array->bitmap);其次，找到对应优先级队列的队列头；queue=array->queue÷idx;然后，找到该队列的队首元素即调度的下一个元素；next=list_entry(queue->next,task_t,run_list);以上侯选进程的查找过程如图3-4所示：ScheduleO如图所示，每个优先级队列对应位图bitmapBITMAP_SIZE上的一个位。最初，所有位上的值都为0,表示没有就绪进程。当一个优先级为i的任务从其它状态变为就绪态，也就意味着它将被插入到queuen队列中，这时位图的第i位被置为1。随着程序的执行，当queuen变为空队列时，该位图位又重新置为0。也就是说，查找侯选进程的过程就是找寻位图中第一个值是1的位。如果存在进程，它们的优先级相同，则依照FlFo办法。因此，next进程的查找就是队列队首元素的查找。位图数组代表了140个优先级，查找next的时间恒定不变，即时间复杂度为确定值0(1)，这也是O(I)调度算法的来历。最后，schedule。函数选取侯选进程next的执行流程如图3-5所示：图3-5SChedUIe()函数的执行流程3.1.2三种调度策略及不足从以上分析可知，2.6内核在实时调度方面上有了一定的提高，如O(I)调度算法及可抢占调度方式的引入。一定程度上，这种方法使内核对实时进程的响应有了可预知性，但当面对严格的嵌入式实时应用环境，这种本质上的静态优先级调度，使内核在实时性方面还是存在着不足,阳。2.6内核使用由函数SetSChedUler()设定的静态优先级调度策略。因此必需在2.6内核中引入动态优先级实时调度方法，使任务的优先级不再是一成不变，而是随着某些因素的变化而变化，从而加强系统的实时性能。3. 2实时系统调度算法4. 2.1RM调度算法RM算法国,是针对周期任务的静态优先级调度策略，由1.iU及其同事1.ayIand提出，经过学者们对其不断的研究与改进，现已是用于实时操作系统中最适时可靠的优秀调度算法。调度任务的优先级由任务的周期决定，任务的周期越短，赋予的优先级就越高；任务的周期越长，赋予的优先级越低。且任务的优先级一旦确定，在整个生命周期中将是不变的。RM算法在高负载的环境下也可以保持良好的性能，所以被广泛采用。但是，在调用该算法时，首先要对任务进行可行性检查，看该算法是否可以对这类任务集产生合理调度。检查的条件为：RM算法必须在单处理机环境下执行，且要求进程具有周期性。 调度时不考虑任务的上下文切换时间，只关心数据的处理时间。 进程之间相互独立，没有依赖关系。 任务的最后截止期须在其周期的结束点上。从这四个前提条件可以看出，RM算法是从简化系统复杂度的角度出发的，而面对实际应用环境的复杂多变，很多任务是不能满足这些可被调度的充分条件的，如第四个条件的时限要求。因此RM算法只是在任务周期等同于时限的同步实时系统中为最优算法。3.2.2EDF调度算法EDF是基于动态优先级的调度算法，也被称作死线驱动算法，且被广泛应用，该算法规定任务的最后截止期限决定任务的优先级大小，截止期限越近的进程，其优先级权值越高【2%可见，该算法中进程的优先级大小是由进程的截止期限唯一决定的。它的优点为：由于是基于动态优先级的，所以适应性比较好。它的缺点为：当某个进程在其截止期限前被调度并运行，但是却没有足够的时间执行完，那么之前该进程所占用的处理器时间就被浪费掉了。同时，被浪费掉的这段宝贵时间很可能就导致了其它等待中的进程也没有足够的时间在截止时限前完成。这样就形成了一种恶性循环，这种现象就叫做“多米诺骨牌”，即个别进程错过了最终截止时限，很有可能导致后续的其它进程也不能在最后截止时间前执行完成。3.2.31.1.F调度算法最小裕度1.1.F算法是针对EDF算法“多米诺骨牌”现象的改进。提出了“裕度”的概念，定义为系统的当前时刻与进程最终截止时刻间的时间差。假设当前的系统时间是T,进程的绝对截止时间是D,进程的剩余执行时间是R,则“裕度”值M表示如下：M=D-(T+R)(3-1)“裕度”是1.1.F算法的亮点及优点，但也正是由于这一点导致了该算法的不足，“颠簸”现象。1.1.F算法是基于进程“裕度”值的动态优先级，也就是说就绪队列中进程“裕度”的大小是随着时间而变小的。如果队列中存在两个进程Pl和P2,它们的“裕度”值相同或者相近，当进程Pl被选取占用处理机后，进程P2的优先级就会随着“裕度”值的变小而变变大，到高于当前进程，之后发生切换。进程P2占用处理机后，它的“裕度”值保持不变，优先级权值也就保持不变，但刚刚切换下来的进程PI的优先级却随着“裕度”值的变小而变大，到超过当前进程P2的优先级，系统再次出现切换。这样两个或者多个进程在较短时间内频繁切换的现象就是所谓该算法的“颠簸”现象。即1.1.F算法降低系统效率的不足之处。3.3基于变更期的1.1.F算法的设计及实现针对1.1.F算法在短时间内出现的频繁切换现象，现有的解决方法是在任务切换后，“锁住”这段时间。即在任务被切换后的一段时间内(也称“阈值期”)，利用自旋锁的方法，把内核改为不可抢占。当过了这个“阈值期”后，内核再次恢复为可抢占一定程度上，“阈值期”的思想解决了算法中的频繁切换问题，但同时也导致了新问题的出现，且该问题不容忽视。具体为：内核在“阈值期”期间，处理机是不可抢占的，即便有进程的优先级权值高于当前进程，也要等到“阈值期”结束后才能抢占处理机。即自旋锁的引入使得处理机不可抢占，处理机不可抢占又使得一些进程因不能获得处理机而夭折。基于以上分析，本文提出一种基于变更期的1.1.F算法，该算法在解决频繁切换问题的同时，又不会导致过多进程因错过绝对截止期而夭折。改进后的算法仍然基于动态优先级可抢占的最小“裕度”算法思想，“裕度”值越小，任务的优先级就越高；“裕度”值越大，任务的优先级就越低。改进点为：任务切换后，在某个时间范围内，给刚获得处理机的进程赋予一个新的较高优先级，可以理解为当前进程是仅次于零的“次高优先级”；随着时间的推进，有些进程的“裕度”值将趋于零，即达到拥有“最高优先级”的状态，也就有了抢占处理机的机会。换句话说就是，当前进程在某个时间范围内被赋予的“次高优先级”仍可以被就绪队列中“裕度”值接近零的进程所抢占。这样不但解决了处理机被频繁抢占的问题，而且也避免了绝对不可抢占的缺陷。超过这段时间后，再使当前任务恢复到之前的优先级权值，即恢复任务间自由竞争处理机的状态。本文是基于标准1.inIIX2.6内核的调度结构，引入了基于变更期的1.1.F算法。实现过程及重要数据结构改进如下13。-3他3.3.1task_struct的扩展在数据结构task_struct中添加实时进程的裕度属性:R'ime(剩余执行时间)、D_time(相对截止期)、S_time(任务提交时间)、1._time(裕度值)、1.B_time(备份裕度值变量)。由公式3-1可得：1._time=(S_time+D_time)-T-R_time(3-2)其中，T为系统当前时间；(S_time+Dime)为绝对截止期。另外，进程与裕度相关的属性值在时钟滴答函数SChedUIeJtiCk中进行更新。结构体task_struct扩展的具体过程是：首先，将所需的相关裕度属性放在结构体1.SF_struct中；然后，在结构体task_struct中添加1.SF_struct结构体的指针;最后，指针的初始化放到宏定义INn1.TASK中。struct1.1.F_structunsignedlongR_time;unsignedlongD_time;unsignedlongS_time;unsignedlong1._time;unsignedlong1.B_time;intalter;)；#define1.SFINrr(ISfdef)Isfdef=0,0,0,0,0,0)struct1.SF_structIsfinit;1.SFINIT(Isfinit);structtask_structstruct1.SF_struct*1Sf1.Params;)；#defineINIT_TASK(tsk)(,lsf1.params:&lsfinit,13.3.2插入函数2.6内核插入进程的函数叫做enquequejasks()1,它的原理是：根据进程的优先级prio,在其对应优先级的就绪队列末尾直接插入。鉴于原系统的不足，改进后的算法基于标准2.6系统的O(I)特性，保持了运行队列的结构及侯选进程的选取方法。实时进程插入函数enqueue_rt_task按照裕度值大小完成将实时进程插入到优先级队列中，实现代码是(/kernel/SChed.c目录下)：staticvoidenqueue_rt_task(structtask_struct*p,prio_array_t*array)(structlist_head*t;structtask_struct*q;t=array->queue÷p->prio;if(t)q=list_entry(t,task_t,run_list);while(p->1.time>q->1.time)prev=t;t=t->next;q=list_entry(t,task_t,run_list);)_list_add(&p->run_list,prev,t);elselist_add_tail(&p->run_list,t);_set_bit(p->prio,array->bitmap);array->nr_active+;p->array=array;的优先级数组指针指向所插入的优先级数组。3.3.3SChedlller_tick原系统中进程关于时间属性的更新，由滴答函数SCheduleoick完成。引入新的算法后，由于实时进程增加了裕度相关的属性，所以滴答函数需要做相应的修改，以满足新算法对实时进程的支持。根据改进算法的原理，SChedulejtick函数需要增加更新裕度值和处理裕度更改期限变量的相关操作。根据改进的算法可得，当前进程随着时钟滴答数的推进，RJime是不断减小的，1._time是不变的；相反，就绪队列中的进程随着时钟滴答数的推进，1._time是不断减小的，RJim是不变的。另外，还要有裕度更改期限值的更新，通过判断更改期限值是大于零还是等于零，决定是不恢复还是恢复当前进程之前的裕度值。3.3.4任务切换函数改进后算法中重置裕度值并在设定的时钟滴答个数内保持不变的实现原理是：在进程切换的过程中，如果侯选的next进程是实时进程且裕度值大于1.就将其裕度值进行备份，然后重置它的裕度值为1,这样该进程就有了比原优先级更高的优先级，且这种较高的优先级状态将会保持在设定好的某个时间内。这样不但避免了频繁切换的次数，而且也保证了就绪队列中即将错过绝对截止期限的进程抢占处理机的可能性。因此，需要在进程切换函数中进行相应的判断及初始化。进程切换由函数ConteXJSWitCh完成。根据新算法思想，实时任务切换后要重置进程的裕度值，所以需要在该函数中添加更改期限值的处理，如裕度值的备份、更改期限内新裕度值的初始化等。增加的代码是(/kernel/Sehed.c目录下)：staticinlinetask_t*context_switch(runqueue_t*rq,task-t*prev,task_t*next)(if(rt_task(next)&&1._time>1)(next->1.B_time=next->1._time;next->1._time=A1.TER_PRIO;/*A1.TER_PRIO是定义的更改期限内的裕度值*/next->alter=A1.TER_TIME;*A1.TER.TIME是定义的更改期限的时钟滴答数*/)从步骤2可知，更改期限的更新是在滴答中断函数SChedUlertiCk()中进行的，该函数中更新的内容包括更改期限的递减、当前进程的剩余运行时间的累减、就绪队列中进程裕度值的累减等。当更改期限值递减为零时，表示更改期结束，需要恢复当前运行进程之前的裕度值，然后判断就绪队列中是否存在高于当前进程优先级的进程，如果有则进行处理机的抢占。3.3.5基于变更期的1.1.F算法的设计标准2.6内核中，SChedUIe()调度函数是把就绪队列的第一个进程作为侯选进程。引入基于变更期的1.1.F算法后，新内核在原基础上添加了裕度的筛选条件。对于裕度值小于零的实时进程，即使把处理机分配给它们，它们也无法在截止期之前完成任务的执行。所以只有当实时进程的裕度值大于等于零时才能够作为合格的候选next进程，否则必须将其夭折并重新选取侯选进程。而非实时进程的选取过程保持标准内核的策略。引入基于变更期的1.1.F算法后，函数SChedUIe()选取侯选进程的流程如图3-6所示：图3-6引入基于变更期的1.1.F算法后调度器的执行流程41.inux系统中Zigbee协议栈的构建物联网的规模发展，需要政府部门和相关行业的推动。Zigbee无线通信技术作为推动物联网行业发展的核心技术，其重要性越发显现出来。为了能够适应物联网发展的步伐，结合Zigbee无线通信技术实现一款基于Zigbee技术的专用1.inux内核必将是下一阶段的发展趋势。本章节从实现基于Zigbee技术专用内核的角度出发，提出了1.inUX_Zigbee网络体系架构。接下来将重点讨论Zigbee协议栈和1.i