基于ARM-Linux平台IEEE_802.16_MAC层实现方法研究.doc

学士学位论文基于ARM-Linux平台IEEE 802.16 MAC层实现方法研究Research on the Realization ofIEEE 802.16 MAC Layer Operationon ARM-Linux Platform作 者：籍汉超学 号：08211065班 级：通信0803导 师：刘颖北京交通大学二零一二年五月A、封面；B、毕业设计（论文）成绩评议；C、毕业设计（论文）任务书；D、毕业设计（论文）开题报告；E、指导教师评阅意见；F、评阅教师评阅意见；G、答辩小组评阅意见；北京交通大学学士学位论文基于ARM-Linux平台IEEE 802.16 MAC层实现方法研究Research on the Realization of IEEE 802.16 MAC Layer Operation on ARM-Linux Platform作者姓名：籍汉超 学 号：08211065导师姓名：刘颖 职 称：教授学位类别：工学 级 别：学士 学科专业：通信工程 班 级：通信0803北京交通大学2012年5月60致谢本论文的工作是在我的导师刘颖教授和李旭教授的悉心指导下完成的，刘颖教授严谨的治学态度给了我极大的影响；李旭教授在通信领域的渊博知识及其科学的工作方法给了我极大的帮助。在此衷心感谢一年来刘颖老师和李旭老师对我的关心和指导。两位教授悉心指导我完成了实验室的科研工作，在学习上和生活上都给予了我很大的关心和帮助，在此向两位老师表示由衷的谢意。在实验室工作及撰写论文期间，李世杰、韩宗佑、顾晨、王韵琪等同学对我论文中相关的研究工作给予了许多有用的指导和建议；朱昊清、谢云婷、屈海洋等同学为我提供了热情的帮助；在此向他们表达我真挚的感激之情。另外也感谢家人，他们的理解和支持使我能够在学校专心完成我的学业。北京交通大学学士学位论文 中文摘要中文摘要摘要：无线Mesh网络是一种高容量高速率的自组网技术，因其广覆盖、高可靠、自配置和自愈合等特点，越来越受到研究者和客户的重视。IEEE 802系列多个标准都针对Mesh模式制定了相关协议，本文所研究的内容即基于IEEE 802.16中Mesh网络MAC层的相关标准。经过十数年世界各公司、大学等研究机构对无线Mesh网络终端的研究，现已具备相当成熟的开发硬件平台方案。在建立数据传输的底三层中，网络层、MAC层、物理层功能一般分别在ARM、DSP和FPGA芯片上实现。但通用DSP处理器功耗过大，为开发便携式无线设备提出了不小的挑战，但其强大的计算功能却没有得到充分的利用。本文提出了将MAC层功能移植到ARM处理器的可行方案，以替代DSP处理器，解决功耗难题。本文通过对ARM处理器、Linux操作系统以及MAC层功能的充分分析，设计了一套建立在ARM-FPGA平台的无线Mesh终端硬件架构解决方案，并对架构中各模块做了具体阐释和分析。原MAC层程序庞大而繁杂，极不利于移植工作的进行。为在实际测试中探索在ARM-Linux平台上MAC功能的实现方案，本文提供了约700行的源代码，创建了共包含62.6KB源文件、31.9KB头文件的工程进行测试。本文提出的无线终端硬件实现方案，为改善现有的Mesh网络MAC层硬件单元的功耗等性能具有重要的实用参考价值。关键词： IEEE 802.16；无线Mesh网络；MAC层；ARM-Linux平台北京交通大学学士学位论文 目录ABSTRACTABSTRACT: Wireless Mesh Network is a kind of self-organizing network of high capacity and high transmission speed. In the meantime, WMN is concerned by a large number of scholars and organizations, because its advantage of wide coverage, high reliability, self-configuring, self-healing and high efficiency. A number of standard organizations which are related to IEEE 802 have made corresponding protocols about Mesh. The MAC protocol refered in this paper is based on IEEE 802.16 Standard.After More than 10 years of studying, a mature hardware platform solution of Mesh terminal is developed, according which the NET Layer, the MAC Layer and the PHY Layer are respectively built upon ARM, DSP and FPGA. However, this solution doesnt fit portable personal device well, because of the large power of DSP. In this paper, a new solution is studied. In the new solution, MAC Layer is built upon ARM along with NET Layer, and the DSP is cut off. Consequently the power problem can be solved.After the full study on the ARM, Linux and MAC standard, a WMN hardware solution which is based on ARM-FPGA platform was developed. Moreover, the details of the solution is analysed and discussed in this paper.The old MAC Layer project is so enomous and complicated that its very difficult to adapt the new platform. As a result, author write about 700 lines of codes and build a project including 62.6KB source files as well as 31.9KB header files, to test the practicality of the new solution.The new platform developed in this paper can be helpful for improving power dissipation of Mesh terminal.KEYWORDS：IEEE 802.16; Wireless Mesh Network; MAC Layer; ARM- Linux Platform目 录中文摘要iiiABSTRACTiv目 录v1 综述11.1 引言11.2 IEEE 802.16 无线mesh网络简介21.3 ARM嵌入式处理器及Linux操作系统简介41.4 无线mesh网络终端硬件平台应用现状61.5 本文的主要工作及组织结构62 软硬件平台简介及相关探究92.1 软硬件平台简介92.1.1 UT6410BV04开发板92.1.2 Linux操作系统112.2 实时和非实时操作系统详解122.3 Linux中断机制详解142.3.1 中断上半部152.3.2 中断下半部163 基于IEEE 802.16的MAC层的平台移植思路173.1 IEEE 802.16 无线mesh网络MAC层规范173.2 无线mesh网络终端硬件平台成熟方案193.2.1 通用网无线终端硬件架构193.2.2 专用网无线终端硬件架构213.3 原硬件平台方案及其MAC层程序架构223.4 新硬件平台方案MAC层程序设计思路264 MAC层在ARM-Linux平台上的架构设计294.1 硬件平台架构整体介绍294.2 MAC层程序处理流程介绍304.3 架构各模块细节分析与探讨324.3.1 物理层324.3.2 MAC-PHY接口334.3.3 硬件中断处理334.3.4 MAC层内部接口缓存374.3.5 软中断tasklet394.3.6 MAC-NET接口404.3.7 网络层405 模拟平台运行测试结果415.1 MAC层模拟平台测试说明415.2 MAC层处理时间测试425.3 MAC层处理对其他进程处理效率的影响425.4 MAC层处理稳定性测试435.5 测试总结436总结与展望44英文文献翻译45文献原文（不计空格10278个字符）45中文翻译52参考文献56北京交通大学学士学位论文 综述1 综述1.1 引言IEEE 802.111，IEEE 802.152，IEEE 802.163，以及IEEE 802.204系列标准是国际电子与电气工程师协会（Institute of Electrical and Electronics Engineers，IEEE）陆续发布的为新的个域网、局域网、城域网和广域网量身定做的无线通信标准，提供更高的传输速率，更广的业务覆盖，更廉价的网络服务。IEEE 802.11系列标准为无线局域网系统定制，典型传输范围在300m范围内，在处于楼宇和墙壁遮挡的非视距传输的位置则范围更小5。为了满足城域或广域范围的无线宽带接入技术要求，IEEE又颁布了802.15，802.16，802.20等系列标准。其中，IEEE 802.16系列标准为无线宽带城域网设计了一套完善的空中接口方案，被WiMAX组织（World Interoperability for Microwave Access，全球微波互操作性）所支持，也被称为WiMAX标准6。IEEE 802.16-2004标准设计最大系统覆盖范围50km，最大数据传输率70Mbps，对于客户要求具有很强的适应能力7。IEEE 802.16等技术标准将无线通信带入一个新的时代，但其发展却颇有波折。IEEE 802.16等技术标准的市场化进程触动的是传统电信设备制造商、运营商的利益，面临巨大的竞争压力。在新兴的诸多宽带无线网络技术中，无线mesh网络技术正逐渐兴起并迅速发展，开始发挥巨大的作用并占领市场。无线mesh网络（Wireless Mesh Network，WMN）由传统军用Ad Hoc网络8演进而来，也称作无线网状网，是一种新兴的宽带无线接入网络技术。无线Mesh网络具有自组织、自配置、自修复等特点，因其覆盖广、成本低、可靠性高、建设和维护简便以及自组织自配置等优势，越来越受到各Internet业务提供商、政府部门和其他无线终端客户的青睐9。无线mesh网络中，MAC层面向需要完成控制节点接入、为上层提供可靠数据链路等功能，因此整个无线mesh网的网络建立和资源调度很大一部分在MAC层实现10。另一方面，MAC层还是数据在无线信道上发送和接收的直接控制者，所以是无线mesh网络中非常重要的一部分，直接决定了网络性能和稳定性。无线Mesh网络具有多跳性，不仅会受到相邻路径的干扰，也会受到环境噪声和干扰的影响，这对MAC协议中资源管理、调度机制等方面都提出了更高的要求。本文所研究的课题正是基于某无线终端客户的无线mesh网络项目要求，主要探讨了MAC层功能在不同于传统的硬件平台ARM-Linux平台上的实现的可能性，还对基于此实现的无线mesh网络（网络层-MAC层-物理层）整体硬件方案进行了设计。本文中涉及的MAC层功能正是基于IEEE 802.16-2004 Mesh模式的MAC协议标准。一方面为应国家对自主知识产权的号召，另一方面为满足客户的个性化要求，本项目所采用MAC层协议并不完全照搬IEEE 802.16-2004标准，而是根据实际需要进行了适当增删和修改，当然主要功能机制仍参照标准。1.2 IEEE 802.16 无线mesh网络简介IEEE 802.16定义了两种网络拓扑结构，一种是点到多点（Point to Multi-point，PMP）结构，另一种是网状网（Mesh）结构。两种模式可各有优势， PMP模式下，通信仅发生在用户站和基站之间，资源调度方便，性能稳定。Mesh模式可下，通信还可以在用户站之间发生，实现多跳通信。相对于PMP模式，Mesh模式具有更低的建网成本，更广的覆盖范围，但管理机制也更加复杂11。PMP模式（图1-1）类似于蜂窝网结构。基站（Base Station，BS）协调和中继网络中的所有通信，在基站的管理下，所有用户站（Subscriber Station，SS）与其他用户站进行通信之前，必须经过基站中继。Mesh模式（图1-2）则灵活得多，用户站可以通过多跳通信链路直接进行通信。根据不同的传输协议算法，可以令基站具有更高的优先权，即集中式调度，也可以令所有节点具有平等的优先级别，即分布式调度，也可以采用两者的结合。图1-1 PMP模式Fig.1-1 PMP Mode图1-2 Mesh模式Fig.1-2 Mesh Mode具体来讲，IEEE 802.16协议定义了Mesh模式的如下3种调度机制：1) 集中式调度集中式调度中，资源以比较集中的方式被授予。基站作为树形结构【3】的树根在一定跳数范围内收集所有用户站的资源请求，而后决定网络中每条链路所授予的资源总数，再将授权结果通知各用户站。各用户站在接收到授权消息后根据基站调度发送数据。2) 协调分布式调度在分布式调度中，所有的节点地位平等。源节点和目的节点之间需要通信时，通过“请求-授权-确认”的三次握手机制来进行数据调度。在协调分布式调度中，各节点的请求和授权消息占用帧的控制时隙发送，发送和接收数据的节点间通过请求授权消息的交互过程来计算彼此发送请求或授权消息的具体时间。3) 非协调分布式调度有区别于协调分布式调度的是，非协调模式中，节点占用数据时隙发送请求或授权消息，但需要保证这些消息不会和其他控制消息或数据微时隙发生碰撞。1.3 ARM嵌入式处理器及Linux操作系统简介ARM微处理器为ARM（Advanced RISC Machine）公司授权生产的一系列微处理器的总称。其主要特点有：（1）支持Thumb（16位）/ARM（32位）双指令集，兼容8位/16位器件；（2）大量使用寄存器，指令执行速度快；（3）大多数数据操作在寄存器中完成；（4）寻址方式灵活简单，执行效率高；（5）采用精简指令集（RISC），指令长度固定。比较其他嵌入式微处理器，ARM系列微处理器具有明显的低功耗和低成本两大优势，也因此覆盖了微处理器应用的每一个领域。从成本低廉的嵌入式微控制器，到要求非常高的手机等消费娱乐应用的多核处理器，都可以看到ARM的身影。ARM公司共开发了六套体系架构版本，版本号从16，具体不在此赘述12。通用ARM处理器共分为ARM7、ARM9、ARM9E、ARM10和ARM11等系列，其中ARM9以上版本的最大的进步即在ARM7架构中加入了MMU（Memory Management Unit，内存管理单元）。MMU一方面作用是将虚拟地址与物理地址相互进行映射，另一方面还提供了硬件机制的内存访问授权，从真正意义上支持现代多进程多用户操作系统，如Windows CE、Linux、Palm OS等。ARM10、ARM11等系列主要在旧有系列上在浮点运算、媒体处理能力、数据安全等方面做了进一步优化。随着技术的发展，人们对电子产品处理性能要求也越来越高。在个人消费类电子产品领域，越来越多随身携带的电子设备“PC化”趋势明显，要求完成电脑能完成的许多日常工作；在工业控制领域，系统级芯片（System on Chip，SoC）以低廉的价格提供了丰富的功能，使得一个嵌入式系统可以同时完成多个控制功能。嵌入式操作系统可以为多种多样的处理请求灵活分配系统资源、调度多个应用程序，实现任务的并行处理，也因此得到了广泛的应用。嵌入式领域可供选择的操作系统很多，比如VxWorks、Windows CE，Linux等。Linux因其低成本无需交纳许可费用、强大可裁剪能力开放源码和模块化驱动、以及优秀的兼容性从全面的硬件驱动到各类免费应用，成为实际应用最为广泛的嵌入式操作系统14。Linux是一种类Unix操作系统，兼容POSIX标准并包含了UNIX System V与BSD的大部分特征。它支持多工处理、多用户处理，并采用保护模式的方式执行各个进程，个别的进程失控不会造成系统死机。Linux系统将系统状态分为用户状态、系统状态和硬件中断状态，将硬件中断作为独立于系统外的最高优先级处理。Linux使用虚拟内存，但需在硬盘上规划一块区域作置换用的交换区。Linux对内存采用灵活的页管理方式，多个程序初始共用一块内存区域，但当某个程序尝试写入内存的话，该页会拷贝至其他位置，作为该程序独有的内存页。Linux的最大缺点在于实时性，2.6版本虽然做了比较大的改进，但仍无法称之为实时操作系统。有不少变种Linux在实时性方面做了优化，比如RT Linux做到了硬实时，TimeSys Linux一定程度上提高了实时性，但由于仍是在Linux基础上进行改动，实际使用时还是有诸多问题，因此并没有得到广泛应用16。1.4 无线mesh网络终端硬件平台应用现状国际标准化组织ISO 于1981年正式推荐了一个标准网络系统结构-七层参考模型，称其为开放系统互连模型(Open System Interconnection，OSI)17。OSI 参考模型将整个网络通信的功能划分为七个层次，由低到高分别是物理层、数据链路层、网络层、传输层、会议层、表示层、应用层。第四层到第七层主要负责互操作性，而第一层到第三层则用于创建网络设备间的数据链路连接。对于无线终端硬件平台来说，首要考虑无线数据传输网络的建立，所以在此仅讨论物理层、数据链路层、网络层三层功能实现的平台。目前成熟的无线终端硬件平台架构主要分为两大类：一类是以高通、MTK等公司开发产品为代表的通用网无线终端硬件架构；另一类则是专用网无线终端硬件架构。后文将对两种架构进行详细介绍。无论通用网无线终端，或是专用网无线终端，现有成熟方案都以ARM-DSP-FPGA架构为基础。即网络层在ARM处理器上实现，数据链路层在DSP处理器上实现，物理层在FPAG芯片上实现。在通用网无线终端中，DSP作为一个模块被集成到ARM处理器中，所以表面上是ARM-FPGA架构，事实上还是基于ARM-DSP-FPGA架构的。1.5 本文的主要工作及组织结构本课题源于笔者所在实验组的一个项目。原有无线mesh终端硬件终端为ARM-DSP-FPGA架构，适用于地面站点或车载站点，客户要求开发个人便携式平台，并指出DSP功耗过大，无线终端续航能力不能保证。如果将MAC层移植到ARM处理器上实现，DSP处理器便可以被裁剪去，功耗问题就可以得到解决。但原方案中ARM处理器上运行的操作系统为非实时操作系统Linux，而MAC层功能对实时性有一定要求，因此笔者被指定对MAC层功能在ARM-Linux平台上的实现做探索性的实验。本课题的研究基于四方面的知识基础：（1）IEEE 802.16 无线mesh网络MAC层协议；（2）MAC层功能机制实现的程序代码；（3）ARM处理器的特性；（4）Linux操作系统的特性。本课题面临的最大挑战是资料的匮乏。要将MAC层程序移植到ARM处理器上，并且在非实时操作系统平台上实现，此方面的资料少之又少，更找不到相关方案的研究。笔者能参考的，只有书籍上和网络上的一些关于提高Linux实时性的阐述和探讨。本文的工作主要体现在以下两个方面：1) MAC层程序架构的设计和整体硬件平台架构的设计由于没有现成方案可供参考，也没有相关研究资料，笔者只能通过对Linux内部机制和MAC层程序功能进行充分地了解，并在一步步尝试和探索中总结出可行思路，设计出适合平台的MAC层程序架构。由于MAC层架构的改变，势必也会影响到整体硬件平台架构，因此本文也对此部分进行了一些探讨。2) MAC层测试程序的编写和运行测试现有MAC层程序庞大而繁杂，各功能块之间界限模糊不清。但探索过程中发现MAC层程序必须进行清晰的模块化处理，才有可能移植成功。于是，笔者通过对IEEE 802.16 无线mesh网络MAC层协议进行学习，参考现有程序，独立编写共计约700行源代码。整个工程包含62.6KB源文件、31.9KB头文件，并且成功在ARM-Linux平台上编译加载成功，进行了MAC消息自发自收的功能模拟，完成了测试。本文的组织结构如下：第一章简要对本文涉及的各知识点：802.16标准、无线Mesh网络、ARM处理器、Linux操作系统的基础知识进行了简要介绍，对无线Mesh网络终端研究现状进行了概述，阐述了论文的主要研究内容及论文的组织结构。第二章对本课题开发软硬件平台ARM6410-Linux2.6平台作了较详细的介绍，并根据学习和测试过程中的所得，对其中一些关键性问题进行了深入探讨和研究。第三章对现有成熟Mesh终端硬件平台方案进行了详细说明和总结，并对802.16 MAC层标准和原MAC层程序构架进行了描述，阐释了平台移植工作的中心思路。第四章是本文的核心部分，介绍了笔者设计的平台移植方案，描述了MAC层功能实现流程，并依次对方案中每个模块的细节问题进行了深入探究和讨论。第五章为实现上述平台方案的MAC层工程在ARM开发板上模拟运行的情况。根据测试结果，虽然不能推断出平台的具体性能指标，但可以对平台的可行性作初步估计。第六章对文章的内容进行了总结，强调了课题研究的重要意义，并对此方案发展前景进行了展望。北京交通大学学士学位论文 软硬件平台简介及相关探究2 软硬件平台简介及相关探究2.1 软硬件平台简介本文中，采用S3C6410 ARM处理器与Linux2.6.28嵌入式开发平台为基础，下面对其特性，尤其是项目相关部分做简要介绍。2.1.1 UT6410BV04开发板本方案使用的硬件平台为UT6410BV04开发板，由深圳市友坚恒天科技有限公司提供。UT6410BV04是一款功能全面、性价比高的ARM11处理器开发板；开发版采用核心板加底板的设计方式，支持多种不同尺寸的液晶显示屏，支持多个主流嵌入式操作系统。此开发板主要面向消费类电子、工控、车载导航、人机界面等电子产品的开发，主要供广大企业用户进行产品前期软硬件性能评估验证、设计参考使用。开发板使用S3C6410XH-66为CPU，此芯片以ARM1176JZF-S为内核，是32位RISC架构微处理器，专为手机等消费电子提供低成本、低功耗、高性能的解决方案。芯片内部包含AXI、AHB与APB构成的64/32位内部总线架构，可提供高性能的2.5G或3G通信服务。其还集成多个专用硬件加速器，用以完成视频处理、音频处理、图像处理和显示输出等功能。为减少系统总体成本，S3C6410XH-66还集成了多种多样的硬件外设，包括：摄像头接口、TFT 24位真彩色LCD接口、电源管理器、4路UART接口、32路DMA接口、5路32位定时器、2路PWM输出、I2S总线接口、I2C总线接口和USB接口等等。S3C6410XH-66对外存接口进行了优化，双外存接口可支持DDR、DDR、SDRAM、NOR FLASH、NAND FLASH、OneNAND、CF和ROM存储格式的设备。核心处理器总体框图如图（图2-1）。图2-1 S3C6410X 模块框图Fig.2-1 S3C6410X Block Diagram整套开发板基本功能特性如下： 支持667MHz主频上稳定工作，DDR数据传输速率266Mbs； 配套WinCE6.0 R2/R3和Linux2.6.28、Ubuntu9.04、Android0.9、Android1.5操作系统； 内部128MB RAM； 外部4GB NAND FLASH，1MB NOR FLASH； 支持SD/MMC/SDIO接口存储卡； 支持NAND FLASH、SD卡、NOR FLASH启动 共20路外部中断输入。2.1.2 Linux操作系统Linux是一个性能稳定、功能强大、效率级高的操作系统。作为一种开放源码的类Unix操作系统，Linux包括了现代Unix操作系统的全部特点，诸如虚存，虚拟文件系统，轻量级进程，SVR4进程间通信，支持对称多处理器（Symmetric Multiprocessor，SMP）系统等。它在2.2版本后试图与IEEE POSIX标准兼容，因此可以编译和运行目前大多数Unix程序。比较其他操作系统，Linux操作系统有着如下特点： Linux属于单内核系统。简单地说，它就是一个庞大、复杂的DIY程序，由逻辑上不同的几个部分组成。运行时不同部分间的通讯是通过直接调用相应函数实现的，而不是消息传递。 大部分现代操作系统内核可以模块化地动态装载和卸载部分内核代码，如设备驱动程序等，但传统Unix内核只能以静态的方式编译和连接。Linux对动态模块的支持非常成熟和完善。因为可选的功能和驱动可以利用模块的形式进行加载，支持模块的最大优势是基本内核镜像可以尽可能的小。动态加载模块还有利于开发人员进行调试。 Linux定义了自己的轻量级进程（Lightweight Process，LWP）版本，这些进程有共同的地址空间、共同的物理内存页、共同的打开的文件等等。若干轻量级进程或进程组成多线程用户程序，因而系统可以用共享应用程序的大部分数据结构的相对独立的执行流来设计用户程序。 Linux利用虚拟文件系统（Virtual File System，VFS）为用户空间程序提供文件系统相关接口。系统中所有文件依赖VFS共存，并且依赖VFS系统协同工作。通过VFS，程序可以利用标准系统调用对不同介质上的不同文件系统进行读写操作。 Linux内核采用页式存储管理，虚拟地址空间划分成固定大小的页面，由MMU 在运行时将虚拟地址“映射”成某个物理内存页面中的地址。页面的换入换出增加了系统花销，但为用户提供了更大的存储空间。 Linux具备完备的硬件内存保护机制，其硬件强制执行性保证了系统中各个进程互不干扰。其一方面隔离进程与进程，另一方面隔离用户空间和内核空间，还提供了必要的访问控制机制。 Linux内核的所有部分都是可裁剪可定制的，只要拥有通用公共许可证（General Public License，GPL），就可以自由地阅读、修改内核和所有系统程序的源代码。Linux操作系统以其多平台兼容性，多用户、多任务、多处理器支持，强大的可裁剪性，良好的用户体验，稳定的性能表现，再加之完全免费的使用定制权限，受到越来越多客户的推崇，得到越来越广泛的应用。2.2 实时和非实时操作系统详解操作系统按工作方式分类可大致分为四大类，单道处理系统，多道处理系统，分时处理系统和实时操作系统。单道处理系统是早期的操作系统处理方式。任务只能按一定顺序装入内存并顺序执行，用户不能干预任务处理过程，任务出错则中止并进行下一任务。在单道处理系统，内存中始终只有最多一项任务，当前任务执行完毕后才装入下一项。当前任务暂停时，系统进入等待状态。多道操作系统更进一步允许在内存中装入多个任务，用户可以利用系统的各种功能，在不同的任务等待队列中放置任务。系统通过一定算法将任务转入内存。在一个任务完成或暂停时，可以自动转入下一任务执行，各个任务交替执行。这样，有任务不断进入内存，也有任务不断调出内存，形成源源不断的任务流，大大提高了系统的吞吐量。多道操作系统一方面需要判断调入内存的任务顺序，另一方面也需要判断任务的执行顺序，因此需要具备一定的进程调度机制。早期操作系统的优势在于系统资源利用率高，操作系统本身的开销小。缺点即任务周转周期长，不能及时地响应用户任务，与用户的交互能力也非常有限。分时操作系统较前两者进步许多，它基于主从式多终端计算机，一台性能强大的计算机可以为多个终端用户进行服务。分时操作系统基本原理是：将CPU系统资源分为一个个长度基本相同的时间片，然后轮流将这些时间片分配给各终端的不同任务。这样，虽然只有一台主机，多个任务可以同时得到处理。分时操作系统的时间片长度是一个非常重要的问题，直接关系到系统资源利用率和任务响应速度。时间片配置过长，任务等待时间就会变长，严重影响用户的使用体验；时间片配置过短，又会造成系统频繁在各任务之间进行调度，对系统资源是很大的浪费。分时操作系统虽然一定程度上浪费了一些系统资源，但它具有的优势是其他操作系统无法比拟的。它可以保证所有的任务都可以在某种意义上及时地得到响应，多个任务可以互不影响地同时得到处理，更重要的是，用户可以及时地与任务处理进行交互操作。因此，当前几乎所有的通用操作系统都是基于分时操作系统发展而来的。但随着操作系统越来越大，功能越来越强，调度机制也越来越复杂，这就引发了很重要的一个问题实时性。分时操作系统注重的是所有的任务都一定程度上得到及时的处理，它关注的是所有任务平均响应时间，而不关注个别任务响应时间，对于单个任务来说，它注重的是平均每次响应时间，而不是特定某次任务执行的响应时间。因此，它重视的是系统整体的性能表现，而微观上来讲是不够可靠的。某种意义上讲，实时操作系统是为弥补分时操作系统可靠性不足而设计的。在系统运行时，难免有一些任务比其他任务更需要及时地被响应，而且需要在一定时间内处理完毕。尤其在一些特殊领域，如工业生产、武器制导、交通控制等等，对实时性有非常严格的要求。这些任务可能不要求很高的处理速度，但对可靠性要求是十分严格的，分时操作系统则很难为其做出保证。针对这些任务设计的实时操作系统的原则就是：通过各种策略和机制，始终保证系统响应任务的可预测性和可靠性，即：在任何情况下，系统都能为各抢占资源的各任务合理分配时间，以满足不同任务的实时性要求。这种分配是可预测的，而且一定是绝对可靠的。事实上，实时操作系统着眼于各有实时性要求的任务在最坏的情况下是否及时被处理，而将系统整体表现放在了次要的位置。保证实时性并不代表将实时任务放至优先级最高的位置，而只要保证每个实时任务在任何情况都能得到及时的处理即可。比如在Linux系统中，硬件中断的优先级别高于其他一切进程。虽然可以保证所有硬件中断可以得到及时的响应，但硬件中断是外部触发的，其触发时间是不可预测的，这就造成了系统整个行为的不可预测性，在微观上，整个系统就是不可靠的。实时操作系统必须要保证系统每一刻的状态都是确定的，非实时操作系统是不可能做到这一点的。举例来说，通用操作系统一般采用虚拟缓存技术，调用一个实时性任务最差的情况是每次执行都需要进行内存页的重新调用，这个任务的实时性就很难得到保障。2.3 Linux中断机制详解本文探究的核心即探究如何在非实时操作系统上实现一些实时性任务的方案，最基本思路即采用Linux的中断机制完成这些实时性要求较高的任务。因此，笔者基于对其机制的探究以及测试的结果，在此对Linux中断机制做一个比较详细的介绍。中断本质上是一个特殊的电信号，由硬件设备生成并发向处理器。处理器接收到中断信号后，便中断当前工作并处理中断，然后通知操作系统已产生中断。这样，操作系统就可以对中断进行适当处理。中断一般都有一个唯一的数字标识。在响应某一个特定中断时，操作系统的内核就会执行某一个特定的函数，称为中断处理程序。在Linux系统中，操作系统的工作状态分为三种：用户状态、内核状态、硬件中断状态。也就说Linux将中断处理程序放到了凌驾于其他一切处理任务之上的位置上。但硬件中断是由外部硬件触发的，是随时都有可能发生的，因此中断处理程序也就随时可能被调用。对于系统来说，一方面要求对硬件中断进行尽可能快的响应，因为对硬件而言，迅速对其进行服务非常重要；另一方面，对系统其它处理任务（包括其它硬件中断）而言，让中断处理程序尽可能快地执行也非常重要，以保证系统正常的调度工作。既希望程序运行得快，又想让程序完成得多，Linux 系统为了协调两者之间的矛盾，将中断处理分为两个部分，分别称为上半部和下半部。系统在接收到一个硬件中断后，马上开始执行上半部函数，但在其中只做有严格时间限制且处理极快的任务。容许稍后完成的工作会推迟到下半部函数中。在响应完上半部函数之后，下半部会被操作系统安排在某个合适的时机执行。2.3.1 中断上半部中断处理上半部即通常所说的中断服务程序。Linux的硬件中断优先级最高，因此很大程度上中断服务程序的响应时间取决于硬件能力。在笔者使用的S3C6410-Linux2.6平台上，实测从中断触发到中断服务程序响应时间约为810us，从中断服务程序完毕到系统状态恢复约46us。可知其实Linux操作系统响应硬件中断的速度并不很慢，并且可响应中断的频率也与Linux操作系统关系不大，只要中断周期大于“中断响应时间+程序执行时间+系统恢复时间”，系统就可以承受。当然，因为中断响应时间和系统恢复时间是基本一定的，也就是说每进入一次硬件中断，就要有15us左右的时间被内核消耗。中断频率越快，浪费的系统资源就越多，这是实际应用不得不考虑的问题。Linux操作系统为中断分了多种类型，但按优先级的方法分类的话，只分为两种：非屏蔽性中断和屏蔽性中断。非屏蔽性中断可以被其他中断打断，并相互嵌套。而屏蔽性中断一般是比较重要且执行比较快速的一些任务，如时钟计数等。在屏蔽性中断运行时，一切其他中断都不能响应。Linux2.6系统内部大约有284个屏蔽性中断，当然在实际应用时很可能只调用其中的一小部分。用户同样可以通过加载驱动模块申请自己的屏蔽性中断，但要保证屏蔽性中断尽量小地对系统正常运行产生不利影响。屏蔽性中断的存在使得Linux操作系统的可靠性变得更差。更严重的是，无论Linux2.6系统还是S3C6410芯片，都没有提供任何中断挂起机制。也就意味着一个硬件中断如果没有得到及时响应，它将被直接丢弃而系统接收不到任何信号。这一点成为本文工作的难度最大的解决问题之一，后面将会详述。2.3.2 中断下半部中断服务程序有最高的优先级别，也有其局限性： 中断以异步方式执行，可能打断了系统正在做的重要事情； 中断往往跟硬件操作直接相关，有较高的时限要求； 中断执行时间过长可能导致过多中断嵌套，引发内核栈溢出； 中断不能在进程上下文中进行，不能被阻塞，因此功能受限。因此，中断服务程序中对时间要求比较宽松的操作应当被推后到系统认为合适的时间执行，这就是中断下半部的任务。中断下半部有很多机制可供选择：软中断、tasklet和工作队列，其中tasklet是通过软中断实现的，而工作队列原理与另两者完全不同。软中断是三种方式中优先级最高的机制，但非常不常用。因为：首先，Linux系统内部的软中断的个数是有限的，只有32个；其次，软中断是不可抢占的，软中断服务程序只能被硬件中断打断却不能相互嵌套；并且，软中断使用方法也较为复杂。tasklet机制是下半部运用最多的机制，它有以下特点： tasklet通过软中断实现，事实上就是一类优先级较低的软中断； tasklet没有数量限制； tasklet使用方便，只需要初始化一个20byte的全局结构体变量，然后在需要挂起时调用挂起函数； 一次挂起多个tasklet，系统按照调度顺序执行，与挂起先后无关； tasklet在调用前可以被多次挂起，但最终只执行一次； 一般情况下，在没有内存页调用或其他高优先级任务打断时，tasklet响应时间在5us之内。工作队列是另外一种将工作延后的形式，它将工作交由一个内核线程执行这个下半部在进程上下文中执行。因而采用此种方式的下半部是容许重新调度甚至睡眠的。当然，工作队列也是三种之中优先级最低的，实时性也最差。在此只对Linux中断机制进行探讨，对于中断内核调度过程乃至执行代码，可以参考相关书籍等资料。北京交通大学学士学位论文 基于IEEE 802.16的MAC层的平台移植思路3 基于IEEE 802.16的MAC层的平台移植思路3.1 IEEE 802.16 无线mesh网络MAC层规范因为本文涉及到的MAC层协议仅包含基本的消息发送和资源调度，并没有涉及复杂的网络容量机制、网络调度机制或功率控制机制等等，所以在此不对系统调度细节进行描述，对于冲突避免、拥塞控制、自适应控制等等算法也不作讨论。IEEE 802.16协议规定了Mesh模式特定的帧格式，包括控制子帧和数据子帧。控制子帧又分为网络控制子帧和调度控制子帧两类，分别完成创建保持系统互联性和数据传送调度的功能。控制子帧长度固定，为MSH-CTRL-LEN7个OFDM符号（MSH-CTRL-LEN指示网络控制子帧长度，在MAC层网络描述信息单元中声明）。数据子帧由数据突发（Burst）组成，每个突发长度可变。数据突发由两个OFDM符号长度的长导频开始，后面为MAC层PDU数据。MAC层对于帧的计数还包括复帧、超帧等量级，其详细帧结构如图（图3-1）。图3-1 Mesh帧结构Fig.3-1 Mesh Frame Structure在MAC层，规定了5种控制消息（表3-1），分别实现接入、配置和调度等功能：表3-1 IEEE 802.16定义的MAC层五种控制消息Table 3-1 Five Control Message Types Defined by IEEE 802.16MSH-NCFGMesh Network Configuration Message网络配置消息MSH-NENTMesh Network Entry Message网络接入消息MSH-DSCHMesh Distributed Scheduling Message分布式调度消息MSH-CSCHMesh Centralized Scheduling Message集中式调度消息MSH-CSCFMesh Centralized Scheduling Configuration Message集中式配置消息1) MSH-NCFG：MSH-NCFG消息提供了邻近网络节点间的基本通信级，其中包含当前网络的基本拓扑信息、资源状况、调度策略等信息。IEEE 802.16协议规定，所有活跃节点（包括入网和非入网）都需要周期性地广播网络描述消息MSH-NCFG。2) MSH-NENT：MSH-NENT消息在新节点入网时使用，为新节点提供同步、授权请求等支持。3) MSH-DSCH：MSH-DSCH是实现分布式调度策略的核心控制消息，负责传递资源请求和授予消息。在协调分布式调度策略中，所有节点以一定时间间隔发送MSH-DSCH消息来通知邻居节点传输调度状况。4) MSH-CSCH：集中式调度中，基站生成的资源调度消息。其中包含网络各条链路所授权分配的网络资源。5) MSH-CSCF：集中式调度中，用户站生成的资源请求消息。用户站根据自身请求向基站发出资源请求，等待基站分配资源。MAC层在发送消息时，具有特定的消息格式（图3-2）：图3-2 MAC层消息格式Fig.3-2 Message Format Carried in MAC Layer1) 通用MAC头：6字节。声明消息长度、是否加密、是否校验等信息。2) Mesh子头：2字节。声明目的节点号。3) 分包子头：2字节。在发送数据消息，标明数据是否分包、如果分包是哪一个分包等信息。控制消息不使用。4) 净荷：消息主体。净荷的最大长度取决于由信道条件决定的调制方式。例如控制消息采用QPSK 1/2调制方式，消息长度最大为768bit，即96字节，净荷长度最大为84字节。采用越高阶的调制方式，可发送的净荷长度就越大。5) CRC校验：4字节。CRC循环冗余校验，为接收节点了解信道条件提供参考。可以根据实际情况决定是否使用。3.2 无线mesh网络终端硬件平台成熟方案现有成熟方案主要有通用网无线终端和专用网无线终端两大类，下面分别举例详细解析。3.2.1 通用网无线终端硬件架构通用网无线终端即指平时所说的手机，主要面对蜂窝移动通信系统，包括目前普及的GSM（Global System for Mobile Communication）系统以及新兴的CDMA2000（Code Division Multiple Access 2000）、WCDMA（Wideband Code Division Multiple Access）、TD-SCDMA（Time Division-Synchronous Code Division Multiple Access）等系统MTK（MediaTek，中国台湾联发科技多媒体芯片提供商）采用Turnkey Solution模式（将芯片与手机开发所需的软件平台乃至第三方软件捆绑销售）提供了较为健全的多媒体平台解决方案，使国产手机厂商在很大程