实时嵌入式操作系统设计论文

毕业设计（论文）第 PAGEII页毕业设计（论文）设计（论文）题目：实时嵌入式操作系统的设计学生姓名学生学号 专业班级 指导老师 年5月29日实时嵌入式操作系统的设计摘要随着微处理器的发展，种类繁多、价格低廉、结构小巧的CPU和外设连接，提供了稳定、可靠的硬件架构。现在嵌入式系统发展的瓶颈在软件方面，尤其是操作系统的“嵌入式”化。由于Linux源码的开放性、简练、多任务、易移植、成本低等特性，成为诸多研究与应用选择的对象。随着2.6内核的发布，Linux向现有主流的实时操作系统提出了更大的挑战，势必能成为更优秀的嵌入式操作系统。本人一直以来都对Linux操作系统很感兴趣，并结合本专业，对Linux应用于嵌入式实时环境进行了一定的研究。深入探讨了面向嵌入式实时环境的Linux系统的体系结构。论文首先概述了嵌入式系统及实时系统的发展情况，然后介绍Linux在实时领域的相关研究，其次讲述了嵌入式Linux系统的构造，最后描述了系统测试的策略，并就下一步可继续进行的工作进行了展望。关键词： Linux；进程；实时系统；嵌入式系统。

DesignontheKernelofEmbeddedOperatingSystemAbstractWithmicroprocessordevelopment,awiderangeoflowprice,compactstructureoftheCPUandperipheralsandprovideastable,reliablehardwarearchitecture.Embeddedsystemdevelopmentisnowthebottleneckinthesoftware,especiallyoperatingsystems,"embedded"change.Duetotheopen-sourceLinux,concise,multi-task,multi-taskandeasytotransplant,andlowcostcharacteristics,asmanyresearchandapplicationofchoicetarget.Withrelease2.6ofthekernel,Linuxtothemainstreamoftheexistingreal-timeoperatingsystemproviders,thegreaterthechallenge,isboundtobecomemoreoutstandingEmbeddedoperatingsystem.IgotinterestwithLinuxoperatingsystemseveralyearsago.Combinationmyspecialty,ThenIdidsomeresearchforreal-timeLinux.Basedonthesefacts,thisthesisdemonstratesarchitectureandinternalsofLinuxsystemusedonembeddedsystems.Thepaperoutlinedthesystemsandembeddedreal-timesystemdevelopment,Thenreal-timeLinuxinthefieldofresearch,followedbyaboutembeddedLinuxsysteminthestructure,Descriptionofthefinalsystemtestingstrategies,andonthenextstepstocontinuetheworkforward.Keywords：RealTimeSystem,EmbeddedSystem,process,Linux目录1嵌入式实时系统概况 11.1嵌入式系统概况 11.1.1关于嵌入式系统 11.1.2嵌入式系统的基本特征 21.1.3典型的嵌入式系统 21.2实时嵌入式系统概况 31.2.1什么是实时嵌入式系统 31.2.2实时嵌入式操作系统 42Linux作为实时系统的分析 62.1Linux内核体系结构 62.2Linux进程管理 72.2.1进程描述符 82.2.2进程调度 132.2.2抢占 162.2.3调度器的实时性能 183构造嵌入式Linux系统 203.1uClinux结局方案 203.2构造潜入式Linux系统 213.2.1构建嵌入式Linux系统的几个关键问题 213.2.1构建嵌入式Linux系统的关键步骤 243.3uClinux在ARMulator的移植 254测试方案 28总结 29致谢 30参考文献 311嵌入式实时系统概况1.1嵌入式系统概况1.1.1关于嵌入式系统嵌入式系统在现代人的日常生活中已经无处不在（如图1-1），而且正在越来越深地介入我们的生活、工作甚至娱乐。图1-1日常生活中的嵌入式系统从几十年前出现的计算机开始，人们身边出现了越来越多的嵌入式系统，而Intel公司第一款处理其4004的主要应用就是计算器。电话是影响人们生活方式的重要发明成果之一，作为其核心设备的存储程序控制（SPC）电话交换机早在上个世纪中后期就已经出现，电话交换机就是一类典型的实时嵌入式系统。除通讯、国防、航空航天和医疗领域以外，汽车工业也是嵌入式系统使用最早的行业之一。当今的每部中高档汽车上都至少有几套甚至几十套嵌入式系统在协调工作，控制着汽车的转向、液压、制动、空调、ABS等等一系列功能，其中大多数都是实时系统。今年来，嵌入式系统以消费电子设备的形态大量进入人们的生活：移动电话、数码相机、数字摄像机、游戏机、电子辞典、PDA（PersonalDigitalAssistant，个人数字助理）、MP3播放器、微波炉、空调、数字电视、DVD播放机、传真机等[1]。Internet是近年来对人们生活方式影响最大的技术成果。但为大多数人所忽略的是，Internet实际上是有史以来世界上最大的嵌入式系统集合。Internet上的高端路由器、ATM交换机、以太网交换机、网关等核心设备都是实时处理能力很强的嵌入式系统。1.1.2嵌入式系统的基本特征从以上那些耳熟能详的嵌入式设备中（其中某些是实时嵌入式设备），我们应该能感觉到嵌入式系统的一些基本特征：嵌入式系统由智能单元（即微处理器，有时存在多个）控制，因而是计算机系统。但因形态多样，多数情况下此特征为人们所忽略。嵌入式系统所提供的功能通常带有针对性，大多是专用系统。与桌面系统不同，嵌入式系统一般不对用户提供再开发环境，用户与系统交互的唯一端口就是系统提供给用户的最终应用。针对某些特殊应用，如航天飞机、卫星、飞机等，嵌入式系统常常需要很高的可靠性和长时间无人值守的工作能力。这一点对操作系统得要求至关重要。紧凑性要求明显（因系统而异）。基于成本、体积、功耗和性价比等因素考虑，许多嵌入式系统通常不追求高速而功耗大的处理器，采用尽可能少（但够用）的存储器。他的软件（或固件/Firmware）和数据通常保存在系统的非易失存储器上（如Flash）。这些都对操作系统的处理性能和可裁减性有特殊要求。实时性需求。在给定硬件环境条件下，系统实时性主要依靠操作系统和应用软件保障。1.1.3典型的嵌入式系统信息家电商机引发全球嵌入式操作系统平台大战，全球4大操作系统阵营WinCE、PalmOS、EPOC和Linux展开规格战，各拥有软件及硬件合作厂商逐鹿信息家电市场的份额。微软窗口操作系统拥有在个人电脑上的操作系统占有率的优势，使WinCE拥有强大的窗口资源支援。不过PalmOS操作系统拥有全球PDA产品70％的市场占有率；同时获得3COM、IBM和索尼等跨国公司的支持。EPOC是发展自欧洲的操作系统、是由世界上最大的3家移动电话厂商诺基亚、爱立信和摩托罗拉所共同开发、整合组成新公司，开发出来的新操作系统；在3大电话厂商的合作下，EPOC市场潜力很大，且占有率高，但应用功能以手机为主，目前并不开放授权。此外，在3大主流操作系统品牌外，Linux也将是今后一股强劲的力量；由于Linux开放源码，经过这些年的发展，已经成为一个健壮的可靠的高性能的操作系统。愈来愈多的嵌入式系统设计员发现Linux可以成为一个优秀的嵌入式操作系统。而Linux的最大的优势还在于它是一个开放的操作系统。由于Linux开放源码，操作系统的一切对用户都是透明的，用户可以最大限度地控制系统开发的进度和造价。在开发过程中遇到的各种各样的硬件设备，可以方便地在网上找到这些设备的驱动程序，得到支持。Linux内置网络支持，用户可以轻松地使自己的嵌入式具有网络功能。Linux是模块化的操作系统，提供了优秀的可缩放功能，用户可以方便地删除不需要的模块，大多数嵌入式系统对操作系统的体积非常敏感，Linux的可以根据自己的需要，选择特定的功能模块，自主地搭建嵌入式操作系统。Linux支持绝大多数CPU，包括Intel、MIPS、ASIC、ALPHA、68K、POWERPC等。这使Linux几乎可以嵌入到各种硬件设备上。成为各家厂商极力发展的操作系统，加上其核心小，潜力可观。1.2实时嵌入式系统概况1.2.1什么是实时嵌入式系统嵌入式系统不都是实时系统。比如掌上电脑、电子辞典等，它们具备嵌入式系统的基本特征，但基本没有实时性要求。而实时性系统也不都是嵌入式系统。当我们将个人电脑装上实时操作系统并用于工业生产线实时控制时，该系统并不具备被嵌入式特征，因此我们可以说实时嵌入式系统是嵌入式系统与实时系统的交集（如图1-2）。但一般而言，嵌入式系统中有相当大的比例是实时系统。[2]图1-2嵌入式实时系统的边界与非实时系统不同之处在于，实时系统对外部事件的响应有时间要求，即要在给定时间内完成事件的识别、处理，并给出正确结果。外部事件可分为两类，即同步时间（SynchronousEvents）和异步事件（AsynchronousEvents）。同步事件是周期性的，系统可以预见下一次同类事件发生的时刻；异步事件是非周期的，事件发生的事件不可预测。实时操作系统必须有能力处理这两类事件。Deadline是实时系统追求的最重要的指标。但不同的实时系统得Deadline的要求不同，并据此将实时系统分为两类：HardReal-time(硬实时)和SoftReal-time(软实时)。1.2.2实时嵌入式操作系统同样作为操作系统，实时嵌入式操作系统与通常意义上的操作系统在基本功能方面应该是一致的，但必然存在明显差异。首先，实时嵌入式操作系统负责实时嵌入式系统的所有软硬件资源的分配、调度工作、控制和协调并发活动，如任务调度、内存管理、同步机制、异常和中段处理、任务间通信等，具有一般操作系统的基本功能:同时它也必须具有其实时处理和嵌入式系统特征。与通用操作系统相比，实时嵌入式操作系统具有如下一些特点[3]:实时性。大多数嵌入式系统工作在实时性要求很高的环境中，对外部事件的响应，包括数据的获取、处理和数据的输出都必须在deadline规定时间内完成。这就要求实时嵌入式操作系统必须将实时性作为一个重要指标。小型化、可裁减。嵌入式系统所能提供的资源有限，所以实时嵌入式操作系统必须做得小巧，以满足前入式系统的硬件限制，同时必须能够根据应用的要求进行裁减，去除多余的部分，或者简化相应得模块。强稳定性。与桌面系统不同，大多数嵌入式系统一旦开始运行就不需要人过多的干预。在这种条件下，要求作为系统资源总管的操作系统具有较高的稳定性。固化代码。在嵌入式系统中，操作系统与应用软件代码通常被固化在嵌入式系统的ROM中。目前辅助存储器（如磁盘）在嵌入式系统中很少使用，因此，实时嵌入式操作系统的文件管理功能应该能够很容易裁减，取而代之的是各种内存文件系统。弱交互性。除消费类电子设备以外，大多数嵌入式系统的工作过程不需要人的干预。因此多数实时嵌入式操作系统所提供给用户操作的接口相对简单，主要通过系统调用命令向用户程序提供服务。专业化强。每一种实时嵌入式操作系统通常面向特定类型或几种相近类型应用。某些操作系统会根据不同的应用对象采用不同的模块搭配。有些操作系统甚至是自行研发的内部产品。值得注意的是，随着各种各样的实时嵌入式操作系统的出现，人们有必要对实时嵌入式系统提供的借口进行约定，从而为嵌入式应用软件的设计者提供统一的服务借口，例如POSIX（PortableOperationSystemInterface，可移植操作系统接口）有可移植性和平台无关性。[4]通过上面的叙述，我们知道实时性能使评价实时嵌入式操作系统的重要指标，但不是唯一的指标。完善的操作系统应提供完善的功能和丰富的开发工具，如文件管理、设备支持、网络支持、人机交互、GUI、API丰富度、硬件无关设计，以及编译环境、调试环境、多种处理器支持、稳定度、可裁减性、可扩充性、开放接口以及维护等诸多方面。而Linux操作系统在这些方面都有相当出色的表现。2Linux作为实时系统的分析Linux可以说是世界上变化最快的操作系统，几乎每个月都会有新的内核升级版本问世，这也是Linux进步如此神速的主要原因。根据功能不同，Linux内核的模块可基本划分为进程管理、内存管理、网络管理、文件系统与进程通信几部分。实时可靠性是嵌入式应用较为普遍的要求,尽管Linux已发展到2.6版本，但它仍不是一个真正的实时操作系统，但其改进的特性能够满足响应需求。Linux2.6已经在内核主体中加入了提高中断性能和调度响应时间的改进,其中有三个最显著的改进:采用可抢占内核、更加有效的调度算法以及同步性的提高[5]。2.1Linux内核体系结构Linux内核主要由五个子系统组成：进程调度，内存管理，虚拟文件系统，网络接口，进程间通信。[6]1进程调度（SCHED）:控制进程对CPU的访问。当需要选择下一个进程运行时，由调度程序选择最值得运行的进程。可运行进程实际上是仅等待CPU资源的进程，如果某个进程在等待其它资源，则该进程是不可运行进程。Linux使用了比较简单的基于优先级的进程调度算法选择新的进程。2内存管理（MM）允许多个进程安全的共享主内存区域。Linux的内存管理支持虚拟内存，即在计算机中运行的程序，其代码，数据，堆栈的总量可以超过实际内存的大小，只是把当前使用的程序块保留在内存中，其余的程序块则保留在中。必要时，操作系统负责在磁盘和内存间交换程序块。内存管理从逻辑上分为无关部分和硬件有关部分。硬件无关部分提供了进程的映射和逻辑内存的对换；硬件相关的部分为内存管理硬件提供了虚拟接口[10]。3虚拟文件系统（VirtualFileSystem,VFS）隐藏了各种硬件的具体细节，为所有的设备提供了统一的接口，VFS提供了多达数十种不同的文件系统。虚拟文件系统可以分为逻辑文件系统和设备程序。逻辑文件系统指Linux所支持的文件系统，如ext2,fat等，设备驱动程序指为每一种硬件控制器所编写的设备驱动程序模块。4网络接口（NET）提供了对各种网络标准的存取和各种网络硬件的支持。网络接口可分为网络协议和网络驱动程序。网络协议部分负责实现每一种可能的网络传输协议。网络设备驱动程序负责与硬件设备通讯，每一种可能的硬件设备都有相应的设备驱动程序。5进程间通讯(IPC)支持进程间各种通信机制。图2-1Linux内核的五个子系统如图2-1处于中心位置的进程调度，所有其它的子系统都依赖它，因为每个子系统都需要挂起或恢复进程。一般情况下，当一个进程等待硬件操作完成时，它被挂起；当操作真正完成时，进程被恢复执行。例如，当一个进程通过网络发送一条消息时，网络接口需要挂起发送进程，直到硬件成功地完成消息的发送，当消息被成功的发送出去以后，网络接口给进程返回一个代码，表示操作的成功或失败。其他子系统以相似的理由依赖于进程调度。2.2Linux进程管理如果说操作系统是开发者所依赖的框架，那么，进程就是由这个框架所承担和管理的基本或从单元。进程是一个动态的实用系统资源、处于活动状态的程序。Linux是一个多任务操作程序，程序调度器使用合适的调用算法来调用进程。Linux进程管理由进程控制块、进程调度、中断处理、任务队列、定时器、bottomhalf队列、系统调用、进程通信等部分组成。[7]一个程序可启动多次，它的每个运行副本都有自己的进程。进程的生命周期分为进程的产生、执行和结束三个部分。2.2.1进程描述符在内核中，进程描述符是一个名为task_struct的结构体，用于保存进程的属性和其他信息，我们可以在这个结构体中找到与进程有关的所有内核信息。在其生命周期内，进程要与内核的方方面面，“诸如内存管理和调度”等打交道，因此，除了UNIX进程的标准属性外，进程描述符也保存了在上述交互过程中的相关信息。内核用循环双向链表task_list存放所有进程描述符，同时借助全局变量current保存当前运行进程的task_struct。数组task包含指向系统中所有task_struct结构的指针。系统中的最大进程数目受task数组大小的限制，默认值一般为512。创建新进程时，Linux将从系统内存中分配一个task_struct结构，并将其加入task数组。操作系统初始化后，建立init进程，它创建第一个task_struct数据结构INIT_TASK。当前运行进程的结构用current指针来表示。在进程生命周期中，进程描述符必须保存的信息的类型有[8]：进程的属性进程间的关系进程的内存空间文件管理信号量管理进程的可信度资源限制与调度相关的域下面我们来了解一些Task_struct结构中与嵌入式开发相关的域。进程状态（volatilelongstate）进程状态定义有如下几种：//正在运行的进程或在Running队列中准备运行的进程#defineTASK_RUNNING 0//处于等待队列中的进程，等资源有效时唤醒进入就绪队列run-queue#defineTASK_INTERRUPTIBLE 1//处于等待队列中的进程，等资源有效时唤醒，但不可被其他进程中断#defineTASK_UNINTERRUPTIBLE 2//进程暂停，通过其他进程才能唤醒#defineTASK_STOPPED 4//进程已经被杀死，但父进程还没有调用sys_wait()#defineTASK_ZOMBIE 8//僵死状态的进程，进程已经结束运行且释放大部分资源，但未释放其进程块#defineTASK_DEAD 16进程状态转换如图2-2所示，用户进程由do_fork()函数创建，它也是fork系统调用的执行者。do_fork()创建一个新的进程，继承父进程现有资源，初始化进程时钟、信号、时间等数据。完成子进程初始化后，父进程将它挂到就绪队列run-queue，返回子进程的pid。图2.2Linux进程状态转换图进程创建时的状态为TASK_UNINTERRUPTIBLE，在do_fork()结束前被父进程唤醒后，变为TASK_RUNNING。处于TASK_RUNNING状态的进程被移到run-queue队列中，在适当时候由schedule()按CPU调度算法选中，获得CPU。获得CPU而正在运行的进程若申请不到某个资源，则调用sleep_on()或interruptible_sleep_on()睡眠，其task_struct挂到相应的waitqueue。如果调用sleep_on()睡眠，则其状态变为TASK_UNINTERRUPTIBLE。或者，如果调用interruptible_sleep_on()睡眠，则其状态变为TASK_INTERRUPTIBLE。sleep_on()或interruptible_sleep_on()将调用schedule()函数把睡眠进程释放的CPU分配给run-queue队列的某个就绪进程。状态为TASK_INTERRUPTIBLE的睡眠进程当它申请的资源有效时被唤醒（如wake_up_interruptible()），也可以由信号(signal)或定时中断唤醒。而状态为TASK_UNINTERRUPTIBLE的睡眠进程只有当它申请的资源有效时被唤醒（如wake_up()），不能被信号(signal)、定时中断唤醒。唤醒后，进程状态改为TASK_RUNNING，并进入run-queue队列。进程执行系统调用sys_exit()或收到SIG_KILL信号而调用do_exit()时，进程状态变为TASK_ZOMBIE，释放所申请资源。同时启动schedule()把CPU分配给run-queue队列中其它就绪进程。若进程通过系统调用设置PF_SYSTRACE，则在系统调用返回前，进入syscall_trace()，状态变为TASK_STOPPED，CPU分配给run-queue队列中其它就绪进程。只有通过其它进程发送SIG_KILL或SIG_CONT，才能把TASK_STOPPED进程唤醒。重新进入run-queue队列。进程优先级

intprio，优先级，在0～(MAX_PRIO)-1之间取值（MAX_PRIO定义为140），其中0～(MAX_RT_PRIO)-1(MAX_RT_PRIO定义为100)属于实时进程范围。在内核2.6版本中，动态优先级独立计算，通过priority_array结构按优先级排序，存储在进程的task_struct中。

intstatic_prio，静态优先级，与Linux2.4的nice值意义相同，但转换到与prio相同的取值区间。nice值沿用Linux的传统，在-20～19之间变动，数值越大，进程的优先级越低。nice是用户可维护的，但仅影响非实时进程的优先级。Linux2.6内核中不再存储nice值，而代之以static_prio。进程初始时间片的大小仅取决于进程的静态优先级，这一点无论是实时进程还是非实时进程都一样，不过实时进程的static_prio不参与优先级计算。

nice与static_prio之间的关系如下：

static_prio=MAX_RT_PRIO+nice+20prio_array_t*array

它是优先级数组，它将进程优先级为序号组成数组。它也是runqueue结构的关键数据结构。实时优先级

rt_priority给出实时进程的优先级，而rt_priority+1000则表示每次获得CPU后，可使用的时间（按jiffy计算）。实时进程的优先级可通过系统调用sys_sched_setschedule()改变，实际的工作是由setscheduler()完成得。

在Linux2.6内核中，候选进程是直接按算法排序的优先级队列数组中选取出来的，而优先级的计算分散到多出进行。进程在适当的时机就会计算动态优先级。同时，影响动态优先级的因素集中反映在sleep_avg变量上。只要进程状态发生改变，内核就有可能计算并设置进程的动态优先级。activated

activated表示进程由于某种原因进入就绪态，这一原因会影响到调度优先级的计算。activated有四个值：-1，进程从TASK_UNINTERRUPTIBLE状态被唤醒0，默认值，进程原本就处于就绪态1，进程从TASK_INTERRUPTIBLE状态被唤醒，且不在中断上下文中2，进程从TASK_INTERRUPTIBLE状态被唤醒，且在中断上下文中activated初值为0，在两个地方修改：一个是在schedule()中，被恢复为0；另一个就是activate_task()，这个函数由try_to_wake_up()函数调用，用于激活休眠状态。sleep_avg

进程的平均等待时间（以nanosecond为计算单位），在0到NS_MAX_SLEEP_AVG之间取值，初值为0，相当于进程等待时间与运行时间的差值。sleep_avg所代表的含义比较丰富，既可用于评价该进程的“交互程度”，又可用于表示该进程需要运行的紧迫度。这个值是动态优先级计算的关键因子，sleep_avg越大，计算出来的进程优先级也越高（数值越小）。

sleep_avg反映了调度系统的两种策略：交互式进程优先与分时系统的公平共享。time_slice

time_slice变量表示进程的运行时间片剩余大小。进程默认时间片与进程的静态优先级相关。在进程创建时，它与父进程平分时间片，在运行过程中递减，一旦归零，则按static_prio静态优先级值重新赋予基准值，并请求调度。时间片的递减和重置在时钟中断中进行(scheduler_tick())，除此之外，time_slice值主要在进程创建和进程退出的过程中变化。policy

policy可以决定进程的类型，不同类型的进程运行时的调度策略也不同（例如，分时进程和实时进程的调度策略不同）。进程的类型及大影响到其调度优先级。2.2.2进程调度在linux2.6中，采用O（1）调度算法，调度器开销恒定，与当前系统负载无关，实时性能更好。Linux2.4中的就绪队列是一个简单的以runqueue_head为头的双向链表，而在Linux2.6中，每个CPU都将维护一个自己的runqueue结构的就绪队列，这将大大减少竞争。每个CPU的就绪队列按时间片是否用完分为两部分，分别通过active指针和expired指针访问。[9]Acrive指向时间片没有用完的、当前可被调度的就绪进程；expired指向时间片已经用完的就绪进程。active中的进程一旦用完了自己的时间片，就被转移到expired中，并设置好新的初始时间片；而当actived为空时，则表示当前所有进程的时间片都消耗完了，此时，active和expired进行一次对调，重新开始下一轮的时间片递减过程。而runqueue就是调度程序操作的对象。进程在初始化并放入运行队列后，在某个时刻，它应该获得对CPU的访问。负责把CPU的控制权传递到不同的两个函数是schedule()和scheduler_tick()。scheduler_tick()是一个由内核周期性调用的系统定时器，它把进程标记为需重新调度。一般定时事件发生时，当前的进程就被保存起来，Linux内核接管对CPU的控制，而当定时事件完成后，Linux内核通常把控制权传回被保存的进程。然而，当所保存的进程被标记成需重新调度时，并不一定选择内核接管控制前正在执行的那个进程，而是内核调用schedule()来选择需要激活哪一个进程。图2-3调度过程图2-3说明随着时间的推移，如何在不同的进程之间传递CPU。我们看到，进程A最先拥有CPU的控制权并正在执行。系统定时scheduler_tick()执行，从A获取对CPU的控制权，此时scheduler_tick()把A标记为需要重新调度。Linux内核调用scheduler()，scheduler()选择进程B，因此CPU的控制权被交给B。进程B执行一会儿，然后自动放弃CPU。这通常发生在进程等待资源的时候。进程B调用scheduler()，scheduler()选择进程C继续执行。进程C执行，直到scheduler_tick()发生，scheduler_tick()不把进程C标记为需要调度。这导致了scheduler()不被调用，因此，进程C再次获得CPU的控制权。通过调用scheduler()，进程C放弃CPU，scheduler()决定进程A应该获得CPU的控制权，进程A再次开始执行。我们首先分析scheduler()，Linux内核利用它决定哪个进程接下来要执行，然后，在分析scheduler_tick()，内核利用它决定哪个进程必须让出CPU。这两个函数组合的结果说明了调度程序的控制流程[10]。函数schedule分析在include/Linux/sched.h中有调度策略定义如图2-4：图2-4Linux进程状态定义策略进程的task_struct结构中成员policy是进程的调度策略，它的值为上述三种策略之一，进程分为实时进程和普通进程，实时进程优先于普通进程运行。rt_priority是实时进程的优先级，它比普通进程的priority高。当系统中有一个实时进程运行时，则SCHED_NORMAL进程不能在任何CPU运行，只有root用户能够用系统调用sched_setscheduler来修改当前进程的优先级。[10]函数schedule的功能是选择一个合适的进程在CPU上运行，它的基本流程分为五个操作步骤：清理当前运行中的进程。选择下一个投入运行的进程。设置新进程的运行环境执行进程上下文切换。后期处理。进程调度有直接启动调度和被动启动调动两种方式，在不同的方式下调度执行的步骤是不一样的。直接启动调度

直接启动调度发生在当前进程因等待资源而需要进入被阻塞状态时，调度程序执行的步骤如下：把当前进程（全局变量current指向task_struct变量）放到适当的等待队列里；把当前进程的state设为TASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE调用schedule()，准备让新的进程掌握CPU；检查当前进程所需的资源是否可用，如果是，则把当前进程从等待队列里删除，否则会到步骤b被动调度

通过在当前进程的need_resched设为1来实现被动调度，每次调入一个用户太进程之前，这个变量的值都会被检查，来决定是否调用函数schedule（）来实现调度。具体执行方式为：当当前进程用完了它的CPU时间片，update_process_times()重新进行计算。当一个进程被唤醒，而且他的优先级比当前进程高。Wake_up_process()调用reschedule_idle()，设置当前进程的need_resched，使被唤醒的进程尽快掌握CPU当sched_setscheduler()或sched_yield()系统调用被调用的进程函数scheduler_tick分析通过调用schedule（）可使进程自动放弃CPU。在向要睡眠或等待信号发生的内核代码及设备驱动中。这个函数用得非常普遍。若其他进程想要连续的使用CPU，系统定时器必须告诉它们让出CPU。Linux内核定时地夺取CPU，然后执行基于定时器的许多任务。其中，这些任务之一就是scheduler_tick()，它是内核强迫一个进程放弃CPU的函数。首先scheduler_tick先收集CPU的统计，然后查看当前进程是否不再活跃。如果进程已经过期，调度程序设置进程的重新调度标志，并跳转到scheduler_tick()函数的结尾。如果得知当前进程正在运行，调度程序就先为剥夺CPU控制权而申请运行队列锁。先考虑最简单的情况。如果当前进程是实时进程，由于实时进程总是拥有比其他任何进程都搞得优先级，当该进程是FIFO进程并且正在运行，进程应该继续它的操作，因此，我们跳转到函数的末尾并释放运行队列锁。如果当前进程是时间片轮转实时进程，我们就减小其时间片，然后调度另一个轮转实时进程，当前进程通过task_timeslice()计算其新的时间按片，最后通过从运行队列的活跃数组删除进程并把其添加回活跃数组，进程被放到轮转实时进程链表的末尾，最后释放运行队列锁。通过了上面的尝试，如果调度程序发现当前并非实时进程。它减小进程的时间片，如果时间片被耗尽。调度程序从活跃数组删除进程并设置它的需要重新调度标志。重新计算进程的优先级并重置它的时间片。最后一种情况，就是进程正在运行并且还有剩余时间片可运行。调度程序必须确保拥有大时间片的进程不会独占CPU。如果进程是交互式的，拥有多余TIMESLICE_GRANULARITY的时间片，而且是活跃的，调度程序就将它从活跃队列中删除。然后，重新调度标志置位，重新计算它的优先级后被放回运行队列的活跃数组，这确保了拥有大时间片的某个优先权的进程不会饿死同等优先权的其它进程。2.2.2抢占抢占指一个进程到另一个进程的切换。前面介绍了schedule()和scheduler_tick()是如何决定接下来要切换哪一个进程的，但没有提及Linux内核是如何决定何时进行切换的。2.6内核引入了内核抢占，这意味着用户空间的程序和内核空间的程序能够在各种时刻被切换。下面将从显式和隐式分别对内核与用户抢占进行描述。[11]显式内核抢占这种情况发生内核调用schedule()时的内核空间，内核代码可以用两种方式调用schedule()：直接调用schedule()或者通过阻塞调用。当显式地抢占内核时，例如，在wait_queue等待队列中设备驱动程序在等待时，控制权被简单地传递到调度程序，从而新的进程被选中执行。隐式用户抢占当内核处理完内核空间的进程并准备把控制权传递到用户空间的进程时，它首先查看应该把控制权传递到哪一个用户空间的进程。而这个进程也许不是传递其控制权到内核的那个用户空间进程。例如，如果进程A调用了系统调用，系统调用完成之后，内核可能把系统的控制权传递给进程B。出现这种情况的主要原因是系统中的每一个进程有一个“必须重新调度”标志，在进程应该被重新调度的任何时候设置它。当内核正在向用户空间返回时，如同schedule()和scheduler_tick()中描述的那样，它选择一个进程，并把控制权传递给该进程。尽管scheduler_tick()能够把进程标记为需要重新调度，但是只有schedule()能够对这个标记进行操作。schedule()反复选择一个新进程来执行，直到新选择的进程不需要被重新调度。schedule()完成后，新进程拥有对CPU的控制权。因此，当进程正在运行时，系统定时器引起一个触发scheduler_tick()的中断。scheduler_tick()能够标记哪个任务需要重新调度，并能把它移动至到期数组。在内核操作完成之后，scheduler_tick()的后面可能紧接着其他中断，内核将继续拥有对处理器的控制权。调用schedule()选择下一个要运行的进程。这样看来，scheduler_tick()标记进程并重排队列，而schedule()选择下一个进程并传递CPU的控制权。隐式内核抢占Linux2.6中新增了隐式内核抢占的实现。当一个内核进程拥有对CPU的控制权时，仅当其当前没有持有任何锁时，这个内核进程才能被另一个内核进程所抢占。每个进程有一个域preempt_count，它标记进程是否可以抢占。每当进程获得一个锁时，则该计数增加，每当进程释放一个锁时减少。当一个进程仍然有一个正的preempt_count值，就把CPU控制权返回给当前进程。如果当前进程没有锁，因为preempt_count是0且中断请求是激活的，这样该进程就可能会被抢占。[10]2.2.3调度器的实时性能Linux2.6对实时性能的改进

Linux2.6内核调度系统对调度的实时性作了改进，它体现了内核抢占和O(1)调度，这加快了实时进程的响应。但Linux2.6调度系统仅提供了对CPU资源的剥夺能力，因此它的实时性并没有得到根本改观。所以Linux2.6只能作为软实时操作系统。实时进程的优先级

在Linux2.4中，实时进程的优先级通过rt_priority值表示，与非实时进程不同。Linux2.6在静态优先级之外引入了动态优先级属性，并用它同时表示实时进程和非实时进程的优先级。进程的静态优先级是计算进程初始时间片的基础，动态优先级则决定了进程的实际调度优先顺序。因为实时进程的动态优先级在setscheduler()中设置，并不随进程的运行而改变。所以实时进程的静态优先级仅用于计算时间片，而动态优先级则相当于静态。实时调度

linux2.4种的SCHED_RR和SCHED_FIFO两种实时调度策略在Linux2.6中未做改变，两类实时进程都回保持在active就绪队列中运行，只是因为Linux2.6内核是可抢占的，实时进程（特别是核心级的实时进程）更能迅速地对环境的改变（比如出现更高优先级进程）作出反应。[11]3构造嵌入式Linux系统Linux作为一种通用操作系统，其最初的设计是用于桌面系统或者小型服务器。在将Linux用于嵌入式系统中时，由于受到嵌入式软/硬件环境的制约，需要对Linux内核做一些改进，使它能更好地为嵌入式系统服务。在这些改进中，进程管理是相当重要的一环。从芯片到外围电路再到人机接口，嵌入式系统的这些硬件设备与普通PC是截然不同的。由于降低成本和功耗，嵌入式系统CPU可能不带MMU（存储器管理单元），使用的存储设备ROM、Flash及RAM的容量较小，这些因素决定了须改变Linux进程管理，以适应存储系统方面的变化。[11]3.1uClinux结局方案Lineo公司的uClinux就是专门针对无MMU处理器的嵌入式设备的Linux变种。由于uClinux没有MMU，在实现多进程时（fork调用产生子进程）须实现数据保护。由于uClinux的多进程管理是通过vfork来实现的，因此fork等于vfork。这意味着uClinux系统fork调用完成后，或者子进程代替父进程执行（此时父进程已经sleep），直到子进程调用exit推出；或者调用exec执行一个新进程，此时将产生执行文件加载，即使这个进程只是父进程的拷贝，这个过程也是不可避免的。当子进程执行exit或exec后，子进程使用wakeup把父进程唤醒，使父进程继续往下执行。uClinux的这种多进程实现机制与它的内存管理紧密相关。uClinux针对没有MMU的处理器开发，所以须使用一种flat方式的内存管理模式。在启动新的应用程序时，系统必须为应用程序分配存储空间。uClinux本身并没于关注实时问题，它并不时为了Linux的实时性而提出的。因此若将uClinux用于实时性要求较高的场合，则需要对其内核做必要的改进。嵌入式Linux的另一个版本RT-Linux关注实时问题。RT-linux把普通Linux的内核当成一个任务运行，同时还管理了实时进程，而非实时进程则交给普通Linux内核处理。这种方法已广泛应用于增强操作系统得实时性，包括一些商业版Unix系统和WindowNT等等。这种方法的优点是：实现简单，且实时性能容易检验；非实时系统运行于标准Linux系统，与其他Linux商用版本之间保持了很好的兼容性；可支持硬实时时钟的应用。uClinux可使用RT-linux的patch，从而增强uClinux的实时性，使得uClinux可应用于工业标准、进程控制等一些实时要求较高的场合。在普通PC中，外部存储介质一般都是使用IDE硬盘等传统的外存设备；而在嵌入式系统中，各种特殊应用目的对存储设备提出了各种各样的要求，所以在不同的场合，需要因地制宜地选择存储设备。目前，Flash存储设备由于其安全性高，存储密度大，体积小，价格相对低廉，成为嵌入式领域中最受欢迎的一类存储器。在嵌入式系统中使用Flash存储器，可只进行只读访问，再将内核与文件系统写到Flash上之后，不需要再对Flash进行写操作。在这种情况下，只需要将Flash作为普通ROM来使用，或辅以romfs和cramfs等，即可满足要求。在运行时，系统会把需要操作的文件和目录提取到内存中进行操作。由于不能再Flash上写数据，所以运行时的欣喜都不可保存于Flash存储设备中。所以对Flash存储设备的管理非常简单，与普通的ROM没有什么区别。uClinux系统采用romfs(romfilesystem)文件系统。Romfs是一种只读文件系统。起初，设计它的目的是在启动盘等场合下，提供一个比普通文件系统（如功能强大的ext2）更加节省空间的文件系统。空间的节省来自于两个方面：首先，内核支持romfs文件系统比支持ext2文件系统需要更少的代码；其次，romfs文件系统相对简单，在建立文件系统超级块（Superglock）时，需要更少的存储空间。romfs文件系统不支持动态擦写保存，对于系统需要动态保存的数据，可采用虚拟RAM盘的方法处理（RAM盘将采用ext2文件系统）。3.2构造潜入式Linux系统3.2.1构建嵌入式Linux系统的几个关键问题一个小型的嵌入式Linux系统需要具备3个基本元素：引导工具、Linux微内核（由内存管理、进程管理和实物处理构成）及初始化进程。若想让它做些什么且继续保持小型化，还须具备：硬件驱动程序，提供所需要功能的一个或多个应用程序。若需要增加功能，或许需要：一个文件系统（也许在ROM或RAM中）、TCP/IP网络协议栈及一个磁盘，用于存放半易失数据和提供交换能力。由此可见，构造一个嵌入式Linux系统，关键是解决以下几个问题。如何引导

当一个微处理器第一次启动时，它开始在预先设置的地址上执行指令。通常在那里有一些只读内存，包括初始化或引导代码。在PC上，这就是BIOS。BIOS首先执行一些低水平的CPU初始化其他硬件的配置，接着辨认哪个磁盘里有操作系统，把操作系统复制到RAM，并且转向它。在PC上运行的Linux就是依靠PC的BIOS来提供相关配置和加载OS功能的。

在一个嵌入式系统中，处于经济性、价格方面的考虑，通常没有BIOS。这就需要开发者自行提供完成这些工作所需要的程序，这就是所需要的开机启动代码。幸运的是，潜入式系统的启动代码不需要像PCBIOS引导程序那样灵活，因为它通常只须处理一些硬件的配置。因此启动代码只是一个指令清单，将固定的数字赛到硬件的寄存器中去。这个代码很简单，也很枯燥，然而却非常关键，因此这些数值要与硬件相符，而且要按照指定的顺序进行。嵌入式系统中启动代码通常放在Flash或EPROM芯片上。具体如何实现，要根据目标硬件和工具来定。一种常用的方法是，把Flash或EPROM芯片插入EPROM或Flash烧制器，把启动代码烧入芯片，然后将芯片插入目标板插座，这种方法要求目标上配有插座。另一种方法是通过JTAG界面，一些芯片有JTAG界面，可用来对芯片进行进行编程，这样芯片就可以被焊在主板上。是否需要虚拟内存

标准Linux采用虚拟存储器技术来管理内存，其优点是提供了比计算机系统实际物理内存大得多的内存空间。这样编程人员在编程时，勿需考虑计算机中物理内存的实际容量。当然它也存在缺点，虚拟内存管理需要通过内存管理单元MMU将虚拟地址转换为物理地址。其中的地址转换表和其他一些数据结构占据了内存空间，这样留给编程人员的内存空间就减少了；同时地址转换增加了每一条指令的执行时间。

在嵌入式系统中，虚拟内存管理并无用武之地；同时在嵌入式实时系统中，它可能会带来无法控制的时间问题。但明智的做法并不是消除内核中的虚拟内存代码，基于两点原因：一是消除它很费事；二是它支持共享代码，多个进程可以共享某一软件的同一拷贝。因此，可保留这段代码，同时只需将交换空间的大小简单地设置为零，就可以关掉虚拟内存的调用功能。此后，如果用户写的程序比实际内存大，系统就会当作用尽了交换空间来处理。这个程序将不会运行，或者malloc将会失灵。文件系统选择

许多嵌入式系统没有磁盘或者文件系统，Linux不需要它们也能运行。这种情况下，应用程序任务可与内核一起编写，并且在引导时作为一个映像加载。对于简单的系统来说，这足够了，但缺乏灵活性。实际上，许多商业性嵌入式操作系统提供文件系统作为选项。Linux提供MS-DOS-Compatible以及其他功能更强大的文家年系统。

文件系统可放在传统的磁盘驱动器、FlashMemory或其他类似的介质上。如果用于暂时保存文件，一个小RAM盘就足够了，FlashMemory通常是这样保存文件系统的：FlashMemory杯分割成块，其中有一块是党CPU启动运行时的引导块，里面存放Linux引导代码，剩余的Flash可用作文件系统。Linux内核有两种加载方式：一是把内核的可执行映像存储到Flash的一个独立部分，系统启动时，从Flash的某个地址开始逐句执行；另一种方式是把内核的压缩文件放在Flash上，系统启动时通过引导代码把内核压缩文件从Flash复制到RAM里，解压执行。因为RAM的存取速度高于Flash，所以后一种方式的运行速度更高一些，标准Linux就是采用这种方式。消除潜入式Linux系统对磁盘的依赖

标准Linux内核通常主流在内存中，每一个应用程序都是从磁盘运行到内存上执行。当程序结束后，它所占的内存被释放，程序就被卸载了。在一个嵌入式系统中，可能没有磁盘。有两条途径可以消除对磁盘的依赖，这要看系统的复杂性和硬件的设计如何：

在一个简单的系统中，当系统启动后，内核和所有的应用程序都在内存里。这是大多数传统潜入式系统的工作模式，它同样也被Linux支持。

有了Linux，就有了第二种可能性，因为Linux有能力加载和卸载程序，一个嵌入式系统可利用它来节省内存。在一个典型的具有FlashMemory的嵌入式系统中，FlashMemory上装有文件系统，所有的程序都以文件的形式存储在Flash文件中，需要时装入内存。这种动态的、根据需要加载的能力是支持其他一系列功能的重要特征。

它使初始化代码在系统引导后被释放。Linux有很多内核外运行的公用程序，这些程序通常在初始化时运行一次，以后不再运行；而且，这些公用程序可以它们共有的方式一个接一个地按顺序运行。这样，相同的内存空间可被反复使用，以“召入”每一个程序，达到节省内存空间的目的。

如果Linux可加载模块的功能包括在内核里，那么驱动程序和应用程序就都可以被加载。它可检查硬件环境，并且为硬件装上相应的软件，这就消除了用一个程序占用很多FlashMemory来处理多种硬件所引起的复杂性。

软件的升级更模块化。可在系统运行时，在Flash上升级应用程序和可加载的驱动程序。配置信息和运行时间参数可作为数据文件存储在Flash上。3.2.1构建嵌入式Linux系统的关键步骤嵌入式应用开发环境一般是由目标系统（硬件开发板）和宿主PC机构成。硬件开发板用于操作系统和目标系统应用软件的运行；而操作系统内核的编程、应用程序的开发和调试则须借助宿主PC机完成。双方一般通过串口建立连接通信。建立交叉开发环境

在软件开发环境建立方面，由于uClinux及相关工具集都是开放源码项目，所以大多数软件都可以从网站上下载获得。首先要在宿主机上安装标准Linux发行版，比如RedHatLinux，接下来就是建立交叉开发环境。安装交叉编译工具

uClinux编译工具中的交叉编译器可对源代码包括内核进行编译，以适应不同的嵌入式应用场合。编译工具包中除了交叉编译器，还有链接器、汇编器以及一些为了方便开发的二进制处理工具，包括生成静态库工具、二进制码察看工具及二进制格式转换工具。这些都要安装在宿主机上。安装uClinux内核

利用已安装的交叉编译器编译生成与运行目标机上的uClinux内核。与标准Linux相同的是，uClinux内核可以以配置的方式选择需要安装的模块，而增加系统的灵活性。安装应用程序

用交叉编译器编译uC-libc和uC-libm源码，声称libc.a应用程序库和libm.a数学库。安装其他工具

用GCC编译elf2flt源码，声称格式转换工具elf2flt。用GCC编译genromfs源码，得到生成romfs的工具genromfs。经过以上的准备工作之后，下面要针对特定应用所需要的设备编写或改造设备驱动程序。有如果用户对系统实时性，特别是对硬实时有特殊要求，uClinux可以加入RT-linux的实时模块。3.3uClinux在ARMulator的移植尽管uClinux很小，但它支持Linux2.6内核约定的全部的特性，包括内核优先级特性以及许多的文件系统，设备驱动。为Linux约定设备驱动端口是容易实现的。几乎所有的代码不需要改变就可以编译，除了从虚拟地址到物理的内存镜像外。

下面将介绍如何将uClinux2.6.5移植到基于GDB的ARMulator上。从uC站点上下载uClinux发布包

，本文以uClinux-dist.20040408.tar.gz为例。/download/linux-2.6.5-hsc2.patch.gz和/pub/linux/kernel/v2.6/linux-2.6.5.tar.bz2分别下载linux-2.6.5-hsc2.patch.gz和内核linux2.6.5的源文件。从站点上更新的ARM-ELF工具链来编译内核，本文以arm-elf-tools-20040427.sh为例。构造虚拟硬件环境ARMulator(ARM仿真)安装工具链。以root身份登陆宿主机下的Llinux系统，然后在终端中进入存放工具链的所在目录，然后输入/bin/sh

arm-elf-tools-20040427.sh解压uClinux发布包

并将linux2.6.5源文件和补丁解压到相同目录下。修改vendors/GDB/ARMulator目录下面的ARMulator默认的配置文件rc

修改后内容如下：hostnameGDB-ARMulator/bin/expand/etc/ramfs.img/dev/ram1mount-tprocproc/procmount-text2/dev/ram1/varmkdir/var/tmpmkdir/var/logmkdir/var/runmkdir/var/lockmkdir/var/emptycat/etc/m