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

毕业设计（论文） 第 31页

毕业设计（论文）

设计（论文）题目： 实时嵌入式操作系统的设计
学生姓名
学生学号
专业班级
指导老师
院长 (系主任) 平

年5月29日

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

关键词： Linux；进程；实时系统；嵌入式系统。

Design on the Kernel of Embedded Operating System

Abstract
With microprocessor development, a wide range of low price, compact structure of the CPU and peripherals and provide a stable, reliable hardware architecture. Embedded system development is now the bottleneck in the software, especially operating systems, "embedded" change. Due to the open-source Linux, concise, multi-task, multi-task and easy to transplant, and low cost characteristics, as many research and application of choice target. With release 2.6 of the kernel, Linux to the mainstream of the existing real-time operating system providers, the greater the challenge, is bound to become more outstanding Embedded operating system.
I got interest with Linux operating system several years ago. Combination my specialty, Then I did some research for real-time Linux. Based on these facts, this thesis demonstrates architecture and internals of Linux system used on embedded systems. The paper outlined the systems and embedded real-time system development, Then real-time Linux in the field of research, followed by about embedded Linux system in the structure, Description of the final system testing strategies, and on the next steps to continue the work forward.

Key words： Real Time System, Embedded System, process, Linux

目录
1嵌入式实时系统概况 1
1.1 嵌入式系统概况 1
1.1.1 关于嵌入式系统 1
1.1.2 嵌入式系统的基本特征 2
1.1.3 典型的嵌入式系统 2
1.2 实时嵌入式系统概况 3
1.2.1 什么是实时嵌入式系统 3
1.2.2 实时嵌入式操作系统 4
2 Linux作为实时系统的分析 6
2.1 Linux内核体系结构 6
2.2 Linux进程管理 7
2.2.1进程描述符 8
2.2.2进程调度 13
2.2.2抢占 16
2.2.3调度器的实时性能 18
3构造嵌入式Linux系统 20
3.1 uClinux结局方案 20
3.2构造潜入式Linux系统 21
3.2.1 构建嵌入式Linux系统的几个关键问题 21
3.2.1 构建嵌入式Linux系统的关键步骤 24
3.3 uClinux在ARMulator的移植 25
4测试方案 28
总结 29
致谢 30
参考文献 31

1嵌入式实时系统概况
1.1 嵌入式系统概况
1.1.1 关于嵌入式系统
嵌入式系统在现代人的日常生活中已经无处不在（如图1-1），而且正在越来越深地介入我们的生活、工作甚至娱乐。

图 1-1 日常生活中的嵌入式系统
从几十年前出现的计算机开始，人们身边出现了越来越多的嵌入式系统，而Intel公司第一款处理其4004的主要应用就是计算器。电话是影响人们生活方式的重要发明成果之一，作为其核心设备的存储程序控制（SPC）电话交换机早在上个世纪中后期就已经出现，电话交换机就是一类典型的实时嵌入式系统。除通讯、国防、航空航天和医疗领域以外，汽车工业也是嵌入式系统使用最早的行业之一。当今的每部中高档汽车上都至少有几套甚至几十套嵌入式系统在协调工作，控制着汽车的转向、液压、制动、空调、ABS等等一系列功能，其中大多数都是实时系统。今年来，嵌入式系统以消费电子设备的形态大量进入人们的生活：移动电话、数码相机、数字摄像机、游戏机、电子辞典、PDA（Personal Digital Assistant，个人数字助理）、MP3播放器、微波炉、空调、数字电视、DVD播放机、传真机等[1]。
Internet是近年来对人们生活方式影响最大的技术成果。但为大多数人所忽略的是，Internet实际上是有史以来世界上最大的嵌入式系统集合。Internet上的高端路由器、ATM交换机、以太网交换机、网关等核心设备都是实时处理能力很强的嵌入式系统。
1.1.2 嵌入式系统的基本特征
从以上那些耳熟能详的嵌入式设备中（其中某些是实时嵌入式设备），我们应该能感觉到嵌入式系统的一些基本特征：
1. 嵌入式系统由智能单元（即微处理器，有时存在多个）控制，因而是计算机系统。但因形态多样，多数情况下此特征为人们所忽略。
2. 嵌入式系统所提供的功能通常带有针对性，大多是专用系统。
3. 与桌面系统不同，嵌入式系统一般不对用户提供再开发环境，用户与系统交互的唯一端口就是系统提供给用户的最终应用。
4. 针对某些特殊应用，如航天飞机、卫星、飞机等，嵌入式系统常常需要很高的可靠性和长时间无人值守的工作能力。这一点对操作系统得要求至关重要。
5. 紧凑性要求明显（因系统而异）。基于成本、体积、功耗和性价比等因素考虑，许多嵌入式系统通常不追求高速而功耗大的处理器，采用尽可能少（但够用）的存储器。他的软件（或固件/Firmware）和数据通常保存在系统的非易失存储器上（如Flash）。这些都对操作系统的处理性能和可裁减性有特殊要求。
6. 实时性需求。在给定硬件环境条件下，系统实时性主要依靠操作系统和应用软件保障。
1.1.3 典型的嵌入式系统
信息家电商机引发全球嵌入式操作系统平台大战，全球4大操作系统阵营WinCE、Palm OS、EPOC和Linux展开规格战，各拥有软件及硬件合作厂商逐鹿信息家电市场的份额。
微软窗口操作系统拥有在个人电脑上的操作系统占有率的优势，使WinCE拥有强大的窗口资源支援。不过Palm OS操作系统拥有全球PDA产品70％的市场占有率；同时获得3COM、IBM和索尼等跨国公司的支持。EPOC是发展自欧洲的操作系统、是由世界上最大的3家移动电话厂商诺基亚、爱立信和摩托罗拉所共同开发、整合组成新公司，开发出来的新操作系统；在3大电话厂商的合作下，EPOC市场潜力很大，且占有率高，但应用功能以手机为主，目前并不开放授权。
此外，在3大主流操作系统品牌外，Linux也将是今后一股强劲的力量；由于Linux开放源码，经过这些年的发展，已经成为一个健壮的可靠的高性能的操作系统。愈来愈多的嵌入式系统设计员发现Linux可以成为一个优秀的嵌入式操作系统。而Linux的最大的优势还在于它是一个开放的操作系统。由于Linux开放源码，操作系统的一切对用户都是透明的，用户可以最大限度地控制系统开发的进度和造价。在开发过程中遇到的各种各样的硬件设备，可以方便地在网上找到这些设备的驱动程序，得到支持。Linux内置网络支持，用户可以轻松地使自己的嵌入式具有网络功能。Linux是模块化的操作系统，提供了优秀的可缩放功能，用户可以方便地删除不需要的模块，大多数嵌入式系统对操作系统的体积非常敏感，Linux的可以根据自己的需要，选择特定的功能模块，自主地搭建嵌入式操作系统。Linux支持绝大多数CPU，包括Intel、MIPS、ASIC、ALPHA、68K、POWER PC等。这使Linux几乎可以嵌入到各种硬件设备上。成为各家厂商极力发展的操作系统，加上其核心小，潜力可观。

1.2 实时嵌入式系统概况
1.2.1 什么是实时嵌入式系统
嵌入式系统不都是实时系统。比如掌上电脑、电子辞典等，它们具备嵌入式系统的基本特征，但基本没有实时性要求。而实时性系统也不都是嵌入式系统。当我们将个人电脑装上实时操作系统并用于工业生产线实时控制时，该系统并不具备被嵌入式特征，因此我们可以说实时嵌入式系统是嵌入式系统与实时系统的交集（如图1-2）。但一般而言，嵌入式系统中有相当大的比例是实时系统。[2]

图 1-2 嵌入式实时系统的边界
与非实时系统不同之处在于，实时系统对外部事件的响应有时间要求，即要在给定时间内完成事件的识别、处理，并给出正确结果。外部事件可分为两类，即同步时间（Synchronous Events）和异步事件（Asynchronous Events）。同步事件是周期性的，系统可以预见下一次同类事件发生的时刻；异步事件是非周期的，事件发生的事件不可预测。实时操作系统必须有能力处理这两类事件。
Deadline是实时系统追求的最重要的指标。但不同的实时系统得Deadline的要求不同，并据此将实时系统分为两类：Hard Real-time(硬实时)和Soft Real-time(软实时)。
1.2.2 实时嵌入式操作系统
同样作为操作系统，实时嵌入式操作系统与通常意义上的操作系统在基本功能方面应该是一致的，但必然存在明显差异。首先，实时嵌入式操作系统负责实时嵌入式系统的所有软硬件资源的分配、调度工作、控制和协调并发活动，如任务调度、内存管理、同步机制、异常和中段处理、任务间通信等，具有一般操作系统的基本功能:同时它也必须具有其实时处理和嵌入式系统特征。与通用操作系统相比，实时嵌入式操作系统具有如下一些特点[3]:
1. 实时性。大多数嵌入式系统工作在实时性要求很高的环境中，对外部事件的响应，包括数据的获取、处理和数据的输出都必须在deadline规定时间内完成。这就要求实时嵌入式操作系统必须将实时性作为一个重要指标。
2. 小型化、可裁减。嵌入式系统所能提供的资源有限，所以实时嵌入式操作系统必须做得小巧，以满足前入式系统的硬件限制，同时必须能够根据应用的要求进行裁减，去除多余的部分，或者简化相应得模块。
3. 强稳定性。与桌面系统不同，大多数嵌入式系统一旦开始运行就不需要人过多的干预。在这种条件下，要求作为系统资源总管的操作系统具有较高的稳定性。
4. 固化代码。在嵌入式系统中，操作系统与应用软件代码通常被固化在嵌入式系统的ROM中。目前辅助存储器（如磁盘）在嵌入式系统中很少使用，因此，实时嵌入式操作系统的文件管理功能应该能够很容易裁减，取而代之的是各种内存文件系统。
5. 弱交互性。除消费类电子设备以外，大多数嵌入式系统的工作过程不需要人的干预。因此多数实时嵌入式操作系统所提供给用户操作的接口相对简单，主要通过系统调用命令向用户程序提供服务。
6. 专业化强。每一种实时嵌入式操作系统通常面向特定类型或几种相近类型应用。某些操作系统会根据不同的应用对象采用不同的模块搭配。有些操作系统甚至是自行研发的内部产品。
值得注意的是，随着各种各样的实时嵌入式操作系统的出现，人们有必要对实时嵌入式系统提供的借口进行约定，从而为嵌入式应用软件的设计者提供统一的服务借口，例如POSIX（Portable Operation System Interface，可移植操作系统接口）有可移植性和平台无关性。[4]
通过上面的叙述，我们知道实时性能使评价实时嵌入式操作系统的重要指标，但不是唯一的指标。完善的操作系统应提供完善的功能和丰富的开发工具，如文件管理、设备支持、网络支持、人机交互、GUI、API丰富度、硬件无关设计，以及编译环境、调试环境、多种处理器支持、稳定度、可裁减性、可扩充性、开放接口以及维护等诸多方面。而Linux操作系统在这些方面都有相当出色的表现。
2 Linux作为实时系统的分析
Linux可以说是世界上变化最快的操作系统，几乎每个月都会有新的内核升级版本问世，这也是Linux进步如此神速的主要原因。根据功能不同，Linux内核的模块可基本划分为进程管理、内存管理、网络管理、文件系统与进程通信几部分。实时可靠性是嵌入式应用较为普遍的要求,尽管Linux 已发展到2.6版本，但它仍不是一个真正的实时操作系统，但其改进的特性能够满足响应需求。Linux 2.6 已经在内核主体中加入了提高中断性能和调度响应时间的改进,其中有三个最显著的改进:采用可抢占内核、更加有效的调度算法以及同步性的提高[5]。
2.1 Linux内核体系结构
Linux内核主要由五个子系统组成：进程调度，内存管理，虚拟文件系统，网络接口，进程间通信。[6]
1进程调度（SCHED）:控制进程对CPU的访问。当需要选择下一个进程运行时，由调度程序选择最值得运行的进程。可运行进程实际上是仅等待CPU资源的进程，如果某个进程在等待其它资源，则该进程是不可运行进程。Linux使用了比较简单的基于优先级的进程调度算法选择新的进程。
2内存管理（MM）允许多个进程安全的共享主内存区域。Linux 的内存管理支持虚拟内存，即在计算机中运行的程序，其代码，数据，堆栈的总量可以超过实际内存的大小，只是把当前使用的程序块保留在内存中，其余的程序块则保留在中。必要时，操作系统负责在磁盘和内存间交换程序块。内存管理从逻辑上分为无关部分和硬件有关部分。硬件无关部分提供了进程的映射和逻辑内存的对换；硬件相关的部分为内存管理硬件提供了虚拟接口[10]。
3虚拟文件系统（Virtual File System,VFS）隐藏了各种硬件的具体细节，为所有的设备提供了统一的接口，VFS提供了多达数十种不同的文件系统。虚拟文件系统可以分为逻辑文件系统和设备程序。逻辑文件系统指Linux所支持的文件系统，如ext2,fat等，设备驱动程序指为每一种硬件控制器所编写的设备驱动程序模块。
4网络接口（NET）提供了对各种网络标准的存取和各种网络硬件的支持。网络接口可分为网络协议和网络驱动程序。网络协议部分负责实现每一种可能的网络传输协议。网络设备驱动程序负责与硬件设备通讯，每一种可能的硬件设备都有相应的设备驱动程序。
5进程间通讯(IPC) 支持进程间各种通信机制。

图 2-1 Linux内核的五个子系统
如图2-1处于中心位置的进程调度，所有其它的子系统都依赖它，因为每个子系统都需要挂起或恢复进程。一般情况下，当一个进程等待硬件操作完成时，它被挂起；当操作真正完成时，进程被恢复执行。例如，当一个进程通过网络发送一条消息时，网络接口需要挂起发送进程，直到硬件成功地完成消息的发送，当消息被成功的发送出去以后，网络接口给进程返回一个代码，表示操作的成功或失败。其他子系统以相似的理由依赖于进程调度。
2.2 Linux进程管理
如果说操作系统是开发者所依赖的框架，那么，进程就是由这个框架所承担和管理的基本或从单元。进程是一个动态的实用系统资源、处于活动状态的程序。Linux是一个多任务操作程序，程序调度器使用合适的调用算法来调用进程。Linux进程管理由进程控制块、进程调度、中断处理、任务队列、定时器、bottom half队列、系统调用、进程通信等部分组成。[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]：
l 进程的属性
l 进程间的关系
l 进程的内存空间
l 文件管理
l 信号量管理
l 进程的可信度
l 资源限制
l 与调度相关的域
下面我们来了解一些Task_struct结构中与嵌入式开发相关的域。
1. 进程状态（volatile long state）
进程状态定义有如下几种：
//正在运行的进程或在Running队列中准备运行的进程
#define TASK_RUNNING 0
//处于等待队列中的进程，等资源有效时唤醒进入就绪队列run-queue
#define TASK_INTERRUPTIBLE 1
//处于等待队列中的进程，等资源有效时唤醒，但不可被其他进程中断
#define TASK_UNINTERRUPTIBLE 2
//进程暂停，通过其他进程才能唤醒
#define TASK_STOPPED 4
//进程已经被杀死，但父进程还没有调用sys_wait()
#define TASK_ZOMBIE 8
//僵死状态的进程，进程已经结束运行且释放大部分资源，但未释放其进程块
#define TASK_DEAD 16
进程状态转换如图2-2所示，用户进程由do_fork()函数创建，它也是fork系统调用的执行者。do_fork()创建一个新的进程，继承父进程现有资源，初始化进程时钟、信号、时间等数据。完成子进程初始化后，父进程将它挂到就绪队列run-queue，返回子进程的pid。

图 2.2 Linux进程状态转换图
进程创建时的状态为TASK_UNINTERRUPTIBLE，在do_fork() 结束前被父进程唤醒后，变为TASK_RUNNING。处于TASK_RUNNING状态的进程被移到run-queue队列中，在适当时候由schedule()按CPU调度算法选中，获得CPU。
获得CPU而正在运行的进程若申请不到某个资源，则调用sleep_on( )或interruptible_sleep_on()睡眠，其task_struct挂到相应的wait queue。如果调用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队列。
2. 进程优先级
int prio，优先级，在0～(MAX_PRIO)-1之间取值（MAX_PRIO定义为140），其中0～(MAX_RT_PRIO)-1 (MAX_RT_PRIO定义为100)属于实时进程范围。在内核2.6版本中，动态优先级独立计算，通过priority_array结构按优先级排序，存储在进程的task_struct中。
int static_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+20
3. prio_array_t *array
它是优先级数组，它将进程优先级为序号组成数组。它也是runqueue结构的关键数据结构。
4. 实时优先级
rt_priority给出实时进程的优先级，而rt_priority+1000则表示每次获得CPU后，可使用的时间（按jiffy计算）。实时进程的优先级可通过系统调用sys_sched_setschedule()改变，实际的工作是由setscheduler()完成得。
在Linux2.6内核中，候选进程是直接按算法排序的优先级队列数组中选取出来的，而优先级的计算分散到多出进行。进程在适当的时机就会计算动态优先级。同时，影响动态优先级的因素集中反映在sleep_avg变量上。只要进程状态发生改变，内核就有可能计算并设置进程的动态优先级。
5. activated
activated表示进程由于某种原因进入就绪态，这一原因会影响到调度优先级的计算。activated有四个值：
a) -1，进程从TASK_UNINTERRUPTIBLE状态被唤醒
b) 0 ，默认值，进程原本就处于就绪态
c) 1 ，进程从TASK_INTERRUPTIBLE状态被唤醒，且不在中断上下文中
d) 2 ，进程从TASK_INTERRUPTIBLE状态被唤醒，且在中断上下文中
activated初值为0，在两个地方修改：一个是在schedule()中，被恢复为0；另一个就是activate_task()，这个函数由try_to_wake_up()函数调用，用于激活休眠状态。
6. sleep_avg
进程的平均等待时间（以nanosecond为计算单位），在0到NS_MAX_SLEEP_AVG之间取值，初值为0，相当于进程等待时间与运行时间的差值。sleep_avg所代表的含义比较丰富，既可用于评价该进程的“交互程度”，又可用于表示该进程需要运行的紧迫度。这个值是动态优先级计算的关键因子，sleep_avg越大，计算出来的进程优先级也越高（数值越小）。
sleep_avg反映了调度系统的两种策略：交互式进程优先与分时系统的公平共享。
7. time_slice
time_slice变量表示进程的运行时间片剩余大小。进程默认时间片与进程的静态优先级相关。在进程创建时，它与父进程平分时间片，在运行过程中递减，一旦归零，则按static_prio静态优先级值重新赋予基准值，并请求调度。时间片的递减和重置在时钟中断中进行(scheduler_tick())，除此之外，time_slice值主要在进程创建和进程退出的过程中变化。
8. 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]。
2.2.2.1函数schedule分析
在include/Linux/sched.h中有调度策略定义如图2-4：

图2-4 Linux进程状态定义策略
进程的task_struct结构中成员policy是进程的调度策略，它的值为上述三种策略之一，进程分为实时进程和普通进程，实时进程优先于普通进程运行。rt_priority是实时进程的优先级，它比普通进程的priority高。当系统中有一个实时进程运行时，则SCHED_NORMAL进程不能在任何CPU运行，只有root用户能够用系统调用sched_setscheduler来修改当前进程的优先级。[10]
函数schedule的功能是选择一个合适的进程在CPU上运行，它的基本流程分为五个操作步骤：
l 清理当前运行中的进程。
l 选择下一个投入运行的进程。
l 设置新进程的运行环境
l 执行进程上下文切换。
l 后期处理。
进程调度有直接启动调度和被动启动调动两种方式，在不同的方式下调度执行的步骤是不一样的。
1. 直接启动调度
直接启动调度发生在当前进程因等待资源而需要进入被阻塞状态时，调度程序执行的步骤如下：
a) 把当前进程（全局变量current指向task_struct变量）放到适当的等待队列里；
b) 把当前进程的state设为TASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE
c) 调用schedule()，准备让新的进程掌握CPU；
d) 检查当前进程所需的资源是否可用，如果是，则把当前进程从等待队列里删除，否则会到步骤b
2. 被动调度
通过在当前进程的need_resched设为1来实现被动调度，每次调入一个用户太进程之前，这个变量的值都会被检查，来决定是否调用函数schedule（）来实现调度。具体执行方式为：
a) 当当前进程用完了它的CPU时间片，update_process_times()重新进行计算。
b) 当一个进程被唤醒，而且他的优先级比当前进程高。Wake_up_process()调用reschedule_idle()，设置当前进程的need_resched，使被唤醒的进程尽快掌握CPU
c) 当sched_setscheduler()或sched_yield()系统调用被调用的进程
2.2.2.2函数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]
2.2.3.1显式内核抢占
这种情况发生内核调用schedule()时的内核空间，内核代码可以用两种方式调用schedule()：直接调用schedule()或者通过阻塞调用。
当显式地抢占内核时，例如，在wait_queue等待队列中设备驱动程序在等待时，控制权被简单地传递到调度程序，从而新的进程被选中执行。
2.2.3.2隐式用户抢占
当内核处理完内核空间的进程并准备把控制权传递到用户空间的进程时，它首先查看应该把控制权传递到哪一个用户空间的进程。而这个进程也许不是传递其控制权到内核的那个用户空间进程。例如，如果进程A调用了系统调用，系统调用完成之后，内核可能把系统的控制权传递给进程B。
出现这种情况的主要原因是系统中的每一个进程有一个“必须重新调度”标志，在进程应该被重新调度的任何时候设置它。
当内核正在向用户空间返回时，如同schedule()和scheduler_tick()中描述的那样，它选择一个进程，并把控制权传递给该进程。尽管scheduler_tick()能够把进程标记为需要重新调度，但是只有schedule()能够对这个标记进行操作。schedule()反复选择一个新进程来执行，直到新选择的进程不需要被重新调度。schedule()完成后，新进程