嵌入式系统的基本知识.ppt

《嵌入式系统的基本知识.ppt》由会员分享，可在线阅读，更多相关《嵌入式系统的基本知识.ppt（217页珍藏版）》请在三一办公上搜索。

1、嵌入式系统设计与实例开发基于ARM微处理器与实时操作系统第二讲 嵌入式系统的基本知识,本节提要,1,3,2,4,嵌入式系统硬件基础,嵌入式系统软件基础,嵌入式操作系统,嵌入式系统设计方法,冯诺依曼体系结构和哈佛体系结构CISC与RISCIP 核流水线存储器系统,嵌入式系统硬件基础,冯诺依曼体系结构模型,指令寄存器,控制器,数据通道,输入,输出,中央处理器,存储器,程序,指令0,指令1,指令2,指令3,指令4,数据,数据0,数据1,数据2,哈佛体系结构,指令寄存器,控制器,数据通道,输入,输出,中央处理器,程序存储器,指令0,指令1,指令2,数据存储器,数据0,数据1,数据2,地址,指令,地址,

2、数据,CISC和RISC,CISC：复杂指令集（Complex Instruction Set Computer）具有大量的指令和寻址方式8/2原则：80%的程序只使用20%的指令大多数程序只使用少量的指令就能够运行。,RISC：精简指令集（Reduced Instruction Set Computer)在通道中只包含最有用的指令确保数据通道快速执行每一条指令使CPU硬件结构设计变得更为简单,CISC与RISC的数据通道,IF,ID,REG,ALU,MEM,开始,退出,IF,ID,ALU,MEM,REG,微操作通道,开始,退出,单通数据通道,CISC的背景和特点,背景:存储资源紧缺,强调编译

3、优化增强指令功能，设置一些功能复杂的指令，把一些原来由软件实现的、常用的功能改用硬件的（微程序）指令系统来实现为节省存储空间，强调高代码密度，指令格式不固定，指令可长可短，操作数可多可少寻址方式复杂多样，操作数可来自寄存器，也可来自存储器采用微程序控制，执行每条指令均需完成一个微指令序列（微程序）CPI，指令越复杂，CPI越大。,CISC的主要缺点,指令使用频度不均衡。高频度使用的指令占据了绝大部分的执行时间，扩充的复杂指令往往是低频度指令。大量复杂指令的控制逻辑不规整，不适于VLSI工艺VLSI的出现，使单芯片处理机希望采用规整的硬联逻辑实现，而不希望用微程序，因为微程序的使用反而制约了速度

4、提高。(微码的存控速度比CPU慢5-10倍)。软硬功能分配复杂指令增加硬件的复杂度，使指令执行周期大大加长，直接访存次数增多，降低了CPU性能。不利于先进指令级并行技术的采用流水线技术,RISC基本设计思想,减小CPI:CPUtime=Instr_Count*CPI*Clock_cycle精简指令集：保留最基本的,去掉复杂、使用频度不高的指令采用Load/Store结构，有助于减少指令格式，统一存储器访问方式采用硬接线控制代替微程序控制,典型的高性能RISC处理器,SUN公司的SPARC(1987)MIPS公司的SGI:MIPS(1986)HP公司的PA-RISC,IBM,Motorola公司

5、的PowerPCDEC、Compac公司的Alpha AXPIBM的RS6000(1990)第一台Superscalar RISC机,CISC与RISC的对比,for(i=0;i 10000;+i)/*各种算术运算操作*/实验平台：桌面Intel Pentium4，带硬件浮点支持OperatorTimeOperatorTime+(int)1+(double)5*(int)5*(double)5/(int)12/(double)10(int)2sin48,小实验1,实验平台：400MHz Intel PXA250 Xscale(ARM)处理器OperatorTimeOperatorTime+(i

6、nt)1+(double)140*(int)1*(double)110/(int)7/(double)220(int)1sin3300,小实验2,知识产权核(IP核,intellectual property),知识产权(IP)电路或核是设计好并经过验证的集成电路功能单元IP复用意味着设计代价降低（时间，价格）IP核的类别:微处理器微处理器:ARM,PowerPC;存储器存储器:RAM,memory controller;外设:PCI,DMA controller;多媒体处理:MPEG/JPEG;encoder/decoder;数字信号处理器(DSP)通信:Ethernet controlle

7、r,router,IP核的种类,Soft Cores(“code”)（软核）HDL语言描述灵活度高，可修改与工艺独立，可根据具体的加工工艺重新综合；IP很难保护Firm cores(“code+structure”)(固核）逻辑综合后的描述与工艺相关Hard cores(“physical”)(硬核）物理综合后的描述准备流片包含工艺相关的布局和时序信息IP很容易保护多数的处理器和存储器,IP核的商业模型,三种模式一、计者提供设计和工具的许可证DSP Group(Pine and Oak Cores),3Soft,ARM 提供包括HDL在内的模拟模型，工具或仿真器使用者负责设计制造二、核厂商设计

8、并制造集成电路芯片TI,Motorola,LucentVLSI,SSI,Cirrus,Adaptec三、核厂商卖核,负责为客户设计并制造芯片LSI logic,TI,Lucent,ARM的IP核,固化宏单元（硬核）ARM920TARM7TDMIARM720TARM1022E,可综合内核（软核）ARM926EJ-SARM7TDMI-SARM1026EJ-S,测试芯片ARM10200E,流水线技术,流水线技术：几个指令可以并行执行提高了CPU的运行效率内部信息流要求通畅流动,译码,取指,执行add,译码,取指,执行sub,译码,取指,执行cmp,时间,Add,Sub,Cmp,指令流水线以ARM为例

9、,为增加处理器指令流的速度，ARM7 系列使用3级流水线.允许多个操作同时处理，比逐条指令执行要快。PC指向正被取指的指令，而非正在执行的指令,Fetch,Decode,Execute,从存储器中读取指令,解码指令,寄存器读（从寄存器Bank）移位及ALU操作寄存器写（到寄存器Bank）,PCPC,PC-4PC-2,PC-8PC-4,ARMThumb,最佳流水线,该例中用6个时钟周期执行了6条指令所有的操作都在寄存器中（单周期执行）指令周期数(CPI)=1,操作,周期,1 2 3 45 6,Fetch,Decode,Execute,Fetch,Decode,Execute,Fetch,Deco

10、de,Execute,Fetch,Decode,Execute,Fetch,Decode,Execute,Decode,Execute,Fetch,Decode,Fetch,Fetch,LDR 流水线举例,该例中，用6周期执行了4条指令指令周期数(CPI)=1.5,周期,操作,123456,Fetch,Decode,Execute,Fetch,Decode,Execute,Fetch,Decode,Execute,Data,Writeback,Fetch,Decode,Execute,Fetch,Decode,Fetch,分支流水线举例,流水线被阻断注意:内核运行在ARM状态,周期,1 2 3

11、 4 5,地址 操作,Fetch,Decode,Execute,Fetch,Decode,Execute,Fetch,Decode,Fetch,Fetch,Decode,Execute,Linkret,Adjust,Fetch,Decode,Fetch,超标量执行,超标量执行：超标量CPU采用多条流水线结构,执行1,预取,指令CACHE,译码2,译码1,执行2,执行1,预取,译码2,译码1,执行2,流水线1,流水线2,数据,高速缓存（CACHE）,1、为什么采用高速缓存 微处理器的时钟频率比内存速度提高快得多，高速缓存可以提高内存的平均性能。2、高速缓存的工作原理 高速缓存是一种小型、快速的存

12、储器，它保存部分主存内容的拷贝。,CPU,高速缓存控制器,CACHE,主存,数据,数据,地址,常见的嵌入式处理器结构,总线和总线桥,存储器系统的层次结构,寄存器,高速缓存SRAM,主存储器DRAM,本地存储器 Flash、ROM、磁盘,网络存储器 Flash、ROM、磁盘,时钟周期,0,110,50100,20000000,存储器系统,RAM：随机存取存储器，SRAM：静态随机存储器，DRAM：动态随机存储器 1）SRAM比DRAM快 2）SRAM比DRAM耗电多 3）DRAM存储密度比SRAM高得多 4）DRM需要周期性刷新ROM：只读存储器FLASH：闪存,NOR技术,NOR技术闪速存储器

13、是最早出现的Flash Memory，目前仍是多数供应商支持的技术架构，它源于传统的EPROM器件。与其它Flash Memory技术相比，具有可靠性高、随机读取速度快的优势，但擦除和写的速度较NAND慢。在擦除和编程操作较少而直接执行代码的场合，尤其是代码（指令）存储的应用中广泛使用。由于NOR技术Flash Memory的擦除和编程速度较慢，而块尺寸又较大，因此擦除和编程操作所花费的时间很长，在纯数据存储和文件存储的应用中，NOR技术显得力不从心。,NAND技术,NAND技术 Flash Memory具有以下特点：以页为单位进行读和编程操作，1页为256或512字节；以块为单位进行擦除操作

14、，1块为4K、8K或16K字节。具有快编程和快擦除的功能，其块擦除时间是2ms；而NOR技术的块擦除时间达到几百ms。数据、地址采用同一总线，实现串行读取。随机读取速度慢且不能按字节随机编程。芯片尺寸小，引脚少，是位成本(bit cost)最低的固态存储器，突破了每兆字节0.1元的价格限制。芯片包含有失效块，其数目最大可达到335块（取决于存储器密度）。失效块不会影响有效块的性能，但设计者需要将失效块在地址映射表中屏蔽起来。基于NAND的存储器可以取代硬盘或其它块设备。,输入输出接口,I/OA/D、D/A键盘LCD存储器接口设备接口,本节提要,1,3,2,4,嵌入式系统硬件基础,嵌入式系统软件

15、基础,嵌入式操作系统,嵌入式系统设计方法,嵌入式软件体系结构,无操作系统的情形在嵌入式系统的发展初期，由于硬件的配置比较低，对于是否有系统软件的支持，要求还不是很强烈。在那个阶段，嵌入式软件的设计主要是以应用为核心，应用软件直接建立在硬件上，没有专门的操作系统。有操作系统的情形,无操作系统的情形,循环轮询系统：（Polling Loop）最简单的软件结构，程序依次检查系统的每个输入条件，一旦条件成立就进行相应的处理。Initialize();while(1)if(condition_1)action_1();if(condition_2)action_2();if(condition_n)ac

16、ition_n();,事件驱动系统：（Event-Driven system）事件驱动系统是能对外部事件直接响应的系统。它包括前后台、实时多任务、多处理器等，是嵌入式实时系统的主要形式。应用程序是一个无限循环，循环中调用相应的函数完成相应操作，这部分可以看成后台行为（background）。中断服务程序处理异步事件，这部分可看成前台行为（foreground)。后台也可以叫做任务级，前台也叫中断级。,例如，很多基于微处理器的产品采用前后台系统设计，如微波炉、电话机、玩具等。从省电的角度出发，平时微处理器处在停机状态，所有的事都靠中断服务来完成。,前后台系统（后台循环、前台中断）,ISR,ISR

17、,后台 前台,ISR,时间,有操作系统的情形,硬件,板级初始化,设备驱动层,以太网驱动,串口驱动,LCD驱动,键盘驱动,操作系统层,中间件层,应用软件层,TCP/IP网络系统,文件系统,内核,嵌入式GUI,嵌入式CORBA,嵌入式JAVA,嵌入式DCOM,面向领域的中间件,WWW浏览器,MP3播放器,电子邮件,为什么要有设备驱动程序？嵌入式硬件设备本身无法工作，需要软件来驱动，如初始化、控制、数据读写等。什么是设备驱动程序？直接与硬件打交道、对硬件进行控制和管理的软件。在一个嵌入式系统中，设备驱动程序是必不可少的。,设备驱动程序,设备驱动程序的主要功能,硬件启动（Startup）：在开机上电或

18、重启的时候，对硬件进行初始化；硬件关闭（Shutdown）：把硬件配置成关机状态；硬件停用（Disable）：暂停使用硬件；硬件启用（Enable）：重新启用硬件；硬件读操作（Read）：从硬件中读取数据；硬件写操作（Write）：往硬件中写数据；,嵌入式操作系统,嵌入式操作系统包括嵌入式内核、嵌入式TCP/IP网络系统、嵌入式文件系统、嵌入式GUI系统和电源管理等部分；嵌入式内核是基础和核心，其他部分要根据嵌入式系统的需要来确定。,嵌入式中间件,中间件（Middleware）：在OS内核、设备驱动程序和应用软件之外的所有系统软件；中间件的基本思路：把原本属于应用软件层的一些通用的功能模块抽取

19、出来，形成独立的一层软件，从而为运行在其上的各个应用软件提供一个灵活、安全、移植性好、相互通信、协同工作的平台；优点：实现软件的可重用，降低应用软件的复杂性，降低开发成本。,嵌入式C程序设计,“which of the following programming languageshave you used for embedded systems in the last12 months”C81%Assembly70%C+39%Visual Basic16%Java7%Source:“ESP:A 10-year retrospective”,EmbeddedSystems Programmi

20、ng,November,1998,嵌入式软件的目标,函数必须正确；源代码简洁、可读性好、可维护；实时性要求较高的代码能够运行得足够快；目标代码小且高效。总之，要优化对以下三种资源的使用：执行时间；存储空间；开发/维护时间。,数据类型与运算符,宏定义：用一个指定的标识符来代表一个字符串。#define 标识符 字符串如：#define PI 3.1415926，其作用是指定用标识符PI来代替“3.1415926”这个字符串，在编译预处理时，将程序中出现的所有PI都用“3.1415926”代替。,（1）宏定义,宏定义的基本思想是：一次定义，多次使用。其优点是：可以用简短的标识符来代替长的数据，减少

21、需要输入的字符数；用易于理解的标识符来代替那些不太好记的具体的数据，便于程序的理解和维护；有利于程序的修改和升级，当这个数据需要修改时，只需改动宏定义之处即可。,不用此法,一次定义,多次使用,（2）const常量,常量数据：整数（12）、字符（a）、字符串（“hello”）和实数（3.14）等；以变量的形式来定义的一个量，并且通 过使用关键字const，来表明这个变量的 值不能被改变。如：const int x=1。,（3）算术运算,整数的算术运算最快带有硬件支持的浮点运算较慢用软件来实现的浮点运算非常慢，快 sin,log,sqrt,etc慢,结论：尽量使用整数（char、short、int

22、和long）的加法和减法；如果没有硬件支持，尽量避免使用乘法；尽量避免使用除法；如果没有硬件支持，尽量避免使用浮点数；数学库函数使用得越少越好。,（4）位运算,C语言有很多位操作运算符：&与操作；|或操作；异或操作；取反操作；右移操作；左移操作。,a|=0 x4b&=0 x4c&=(1=2,/把第2位设置为1,/把第2位设置为0,/把第3位设置为0,/把第5位反转,/把 e 除以4,int x,num=99,count=0;x=num;while(x)count+;x=x,result:4,分支语句,if(a=1)ant();else if(a=2)bar();else if(a=3)cee(

23、);else if(a=4)due();else if(a=5)eat();else if(a=6)foo();,switch(a)case 1:ant();break;case 2:bar();break;case 3:cee();break;case 4:due();break;case 5:eat();break;case 6:foo();break;,Any Differences?,if-then-else语句的汇编代码,$L1:cmp dword ptrebp-4,1#把a与常量1进行比较 jne$L2#如果不相同，跳到$L2继续比较下一个值 call _ant#如果相同，调用an

24、t()函数 jmp$END#跳转到这段代码的末尾$L2:cmp dword ptrebp-4,2#把a与常量2进行比较 jne$L3#如果不相同，跳到$L3继续比较下一个值 call _bar#如果相同，调用bar()函数 jmp$END#跳转到这段代码的末尾$L3:.$END:,switch语句的汇编代码-1,JmpTable dword$L1,$L2,$L3,$L4,$L5,$L6 mov eax,dword ptr ebp-4#取出变量a的值 mov dword ptr ebp-8,eax#保存在临时变量中 mov ecx,dword ptr ebp-8#取出，放在ecx中 sub ec

25、x,1#减1 mov dword ptr ebp-8,ecx#保存回去 cmp dword ptr ebp-8,5#与5进行比较 ja$END#若大于5，结束 mov edx,dword ptr ebp-8#取出该值，放edx jmp dword ptr edx*4+JmpTable#跳转到相应的#case标记,switch语句的汇编代码-2,$L1:#case 1 call _ant jmp$END$L2:#case 2 call _bar jmp$END.$L5:#case 5 call _eat jmp$END$L6:#case 6 call _foo$END:,结论：假设a的取值个数为

26、n，对于if-then-else语句，时间复杂度为O(n)，而对于switch语句，时间复杂度为O(1)；如果n的值较小，两种语句均可；如果n的值较大，则switch语句更佳。,函数,函数原型main()函数调用 函数定义,函数的使用模式,声明该函数,定义一个函数,使用该函数,内存分布状况,全局变量区域,静态分配,栈,自动分配,堆,动态分配,主函数的执行过程,int z;void main()int x,y;x=1;y=2;z=x+y;,全局变量区域,栈帧(main),x=y=,程序,1,2,3,控制流与数据流,控制流：程序当前执行位置的流向；数据流：函数调用发生及结束时，数据在 函数之间流转

27、的过程。,当一个函数被调用时：在内存的栈空间当中为其分配一个栈帧，用来存放该函数的形参和局部变量；把实参变量的值复制到相应的形参变量；控制转移到该函数的起始位置；该函数开始执行；控制流和返回值返回到函数调用点。,函数调用过程,控制流的变化,void main()double x,y,z;y=6.0;x=Area(y/3.0);.z=3.4*Area(7.88);.,/*给定半径，计算一个圆的面积*/double Area(double r)return(3.14*r*r);,一个简单的例子,int Times2(int value);main()int number;printf(“请输入一个

28、整数：”);scanf(“%d”,int Times2(int value);main()int number;printf(“请输入一个整数：”);scanf(“%d”,main,number,3,Times2,value,Times2也得到一个栈帧,它的参数看成局部变量,int Times2(int value);main()int number;printf(“请输入一个整数：”);scanf(“%d”,main,number,3,Times2,value,3,“值传递”,把实参的值传给形参。,int Times2(int value);main()int number;printf(“

29、请输入一个整数：”);scanf(“%d”,main,3,把Times2的栈帧叠在主函数的栈帧之上，说明在执行Times2函数时，主函数中的变量是不可见的。,Times2,value,3,int Times2(int value);main()int number;printf(“请输入一个整数：”);scanf(“%d”,6,Times2函数的返回值被放在函数的调用位置上，然后，分配给Times2函数的堆栈区域被释放。,变量的存储与作用域,/*全局变量，固定地址，其他源文件可见*/int global_static;/*静态全局变量，固定地址，但只在本文件中可见*/static int fi

30、le_static;/*函数参数：位于栈帧当中，动态创建，动态释放*/int foo(int auto_param)/*静态局部变量，固定地址，只在本函数中可见*/static int func_static;/*普通局部变量，位于栈帧当中，只在本函数可见*/int auto_i,auto_a10;/*动态申请的内存空间，位于堆当中*/double*auto_d=malloc(sizeof(double)*5);return auto_i;,可重入函数-1,可以被一个以上的任务调用，而不必担心数据的破坏。可重入型函数任何时候都可以被中断，一段时间以后又可以运行，而相应数据不会丢失。可重入型函数

31、只使用局部变量，即变量保存在CPU寄存器或栈中。一个不可重入型函数的例子int temp;void swap(int*x,int*y)temp=*x;*x=*y;*y=temp;,可重入函数-2,一个可重入型函数的例子void swap(int*x,int*y)int temp;temp=*x;*x=*y;*y=temp;,不可重入函数被中断破坏,本节提要,1,3,2,4,嵌入式系统硬件基础,嵌入式系统软件基础,嵌入式操作系统,嵌入式系统设计方法,嵌入式操作系统概述,An Embedded Operating System(EOS)isan Operating System(OS)in an

32、Embedded System environment.,Being an OS means,系统软硬件资源的管理者：进程管理存储管理I/O设备管理文件管理,Being an EOS means,完成某一项或有限项功能，非通用型；在性能和实时性方面可能有严格限制；能源、成本和可靠性通常是影响设计的重要因素；占有资源少，适合在有限存储空间运行;系统功能可针对需求进行裁剪、调整，以便满足最终产品的设计要求。,按响应时间分类,嵌入式实时操作系统当事件/请求发生时，相应的任务应该在规定的时间内完成；分时操作系统基于公平性原则，各个进程分享处理器，获得大致相同的运行时间。当一个进程在进行I/O操作时，交

33、出处理器，让其他进程运行。,实时操作系统(RTOS)A real-time operating system(RTOS)is an operating system whose correctness includes its response time as well as its functional correctness.hard real time and soft real time,soft real time,hard real time,按软件结构分类,单体结构（Monolithic Structure）分层结构（Layered Structure）Out of date微内

34、核结构（Microkernel Model）,单体结构,最常用的组织结构；整个系统只有一个可执行文件，包含所有的操作系统组件；系统的结构就是无结构，由一组函数组成，相互之间可以随意地调用。,应用软件,文件I/O,存储管理,进程管理,I/O驱动,存储驱动,中断驱动,硬件,单体内核,分层结构,在分层结构（layered）中，一个操作系统被划分为若干个层次（0.N），各个层次之间的调用关系是单向的，即某一层次上的代码只能调用比它低层的代码。这种结构要求在每个层次上都要提供一组API接口函数，这就会带来额外的开销,微内核,设备驱动程序,微内核结构,操作系统内核只包含最少的功能，如存储管理和进程管理；其

35、他的操作系统组件以中间件的形式存在于内核之外；设备驱动程序完全从内核中剥离，独立成为一层。,中间件、应用软件,存储管理,进程管理,I/O驱动,存储驱动,中断驱动,硬件,VxWorksEmbedded LinuxuC/OS-II（重点）WinCEPalmOS,常见的嵌入式操作系统,多道程序技术,为了提高计算机系统中各种资源的利用率，现代操作系统广泛采用多道程序技术（multi-programming），使多个程序同时在系统中存在并运行。,CPU,I/O,单道程序：,多道程序：,CPU,I/O,作业甲（红黄）,作业乙（蓝绿）,进程、线程和任务,在多道程序系统中，各个程序之间是并发执行的，共享系统资

36、源。CPU需要在各个运行的程序之间来回地切换，这样的话，要想描述这些多道的并发活动过程就变得很困难。为此，操作系统设计者提出了进程的概念。,什么是进程？,A process a program in execution,一个进程应该包括：程序的代码；程序的数据；PC中的值，用来指示下一条将运行的指令；一组通用的寄存器的当前值，堆、栈；一组系统资源（如打开的文件）总之，进程包含了正在运行的一个程序的所有状态信息。,main().A().PROCESS,A program is C statements or commands静态的；A process is program+running con

37、text动态的.,main().A().PROGRAM,heap,StackA Main,Registers,PC,Process Program,进程的特性,动态性：程序的运行状态在变，PC、寄存器、堆和栈等；独立性：是一个独立的实体，是计算机系统资 源的使用单位。每个进程都有“自己”的PC和内部状态，运行时独立于其他 的进程（逻辑PC和物理PC）；并发性：从宏观上看各进程是同时独立运行的,四个进程在并发地运行,（本图摘自Andrew S.Tanenbaum：“Modern Operating Systems”）,什么是线程？,自从60年代提出进程概念以来，在操作系统中一直都是以进程作为独立

38、运行的基本单位，直到80年代中期，人们又提出了更小的能独立运行的基本单位 线程。,Why线程？,【案例】编写一个MP3播放软件。核心功能模块有三个：（1）从MP3音频文件当中读取数据；（2）对数据进行解压缩；（3）把解压缩后的音频数据播放出来。,单进程的实现方法,main()while(TRUE）Read();Decompress();Play();Read()Decompress()Play(),问题：播放出来的声音能 否连贯？各个函数之间不是 并发执行，影响资 源的使用效率；,多进程的实现方法,程序1main()while(TRUE）Read();Read(),问题：进程之间如何通信，共享

39、数据？,程序3main()while(TRUE）Play();Play(),程序2main()while(TRUE）Decompress();Decompress(),怎么办？,需要提出一种新的实体，满足以下特性：（1）实体之间可以并发地执行；（2）实体之间共享相同的地址空间；,这种实体就是：线程（Thread）,什么是线程？,Thread：A sequential execution stream within a process;A thread of execution;进程当中的一条执行流程。,从两个方面来理解进程：从资源组合的角度：进程把一组相关的 资源组合起来，构成了一个资源平台（

40、环境），包括地址空间（代码段、数据 段）、打开的文件等各种资源；从运行的角度：代码在这个资源平台上的 一条执行流程（线程）。,进程 线程 资源平台,优点：一个进程中可以同时存在多个线程；各个线程之间可以并发地执行；各个线程之间可以共享地址空间。,线程所需的资源,（本图摘自Silberschatz,Galvin and Gagne：“Operating System Concepts”）,什么是任务？,在许多嵌入式操作系统当中，一般把能够独立运行的实体称为“任务”（Task），那么这里所说的任务到底是进程还是线程呢？,任务的实现,在多道程序（多任务）的嵌入式操作系统中，任务之间的结构为层状结构，

41、存在着父子关系；当嵌入式内核刚刚启动时，只有一个任务存在，然后由该任务派生出所有其他的任务。,任务的层次结构,OS初始任务,任务,任务,任务,任务,任务,任务,任务,任务的创建,在嵌入式操作系统当中，任务的创建主要有两种模型：fork/exec和spawn；fork/exec：符合IEEE/ISO POSIX 1003.1标准，先用fork系统调用创建与父任务完全相同的一份内存空间，然后再用exec系统调用来移除父任务的内容，并调入子任务的程序代码。优点：允许继承；spawn：直接为子任务创建一个全新的地址空间，并装入其程序代码。,任务的描述,问题：如果让你来设计OS当中的任务机制，那么你将如

42、何来描述一个任务？,描述任务的数据结构：任务控制块（Task Control Block，TCB）。系统为每个任务都维护了一个TCB，用来保存与该任务有关的所有信息。,任务控制块的内容,任务ID、任务的状态、任务的优先级；CPU上下文信息：通用寄存器的值、PC寄存器的值、程序状态字、栈指针的值；如果在该OS中，任务描述的是进程，则还应包括其他的一些内容，如段表地址、页表地址等存储管理方面的信息；根目录、文件描述字等文件管理方面的信息。,任务的创建：为该任务生成一个TCB；任务的终止：回收它的TCB；任务的组织管理：通过对TCB的组织管理来实现。,系统用TCB来描述任务的基本情况以及运行变化的过

43、程，TCB是任务存在的唯一标志。,任务的状态,任务的三种基本状态：任务在生命结束前处于且仅处于三种基本状态之一不同系统设置的任务状态数目不同。,运行状态（Running）：任务占有CPU，并在CPU上运行。处于此状态的任务数目小于等于CPU的数目；就绪状态（Ready）：任务已经具备运行条件，但由于CPU忙暂时不能运行，只要分得CPU即可执行；阻塞/等待状态（Blocked/Waiting）：任务因等待某种事件的发生而暂时不能运行（如I/O操作或任务同步），此时即使CPU空闲，该任务也不能运行。,任务的状态及其转换,Running,Blocked,Ready,1 3 2,4,任务由于I/O操作

44、被阻塞；调度器选择了另一个任务；调度器选中该任务任务的I/O操作完成了。,两个任务的状态转换过程,状态队列,由操作系统来维护一组队列，用来表示系统当中所有任务的当前状态；不同的状态分别用不同的队列来表示（运行队列、就绪队列、各种类型的阻塞队列）；每个任务的TCB都根据它的状态加入到相应的队列当中，当一个任务的状态发生变化时，它的TCB从一个状态队列中脱离出来，加入到另外一个队列。,就绪队列和各种I/O队列,任务的调度,在操作系统中，负责去做这个选择的那部分程序，称为调度程序或调度器(scheduler)；调度程序在决策过程中所采用的算法，称为是调度算法；调度程序是CPU资源的管理者。,何时进行

45、调度？,当一个新的任务被创建时，是执行新任务还是继续执行父任务？当一个任务运行完毕时；当一个任务由于I/O、信号量或其他的某个原因被阻塞时；当一个I/O中断发生时，表明某个I/O操作已经完成，而等待该I/O操作的任务转入就绪状态；在分时系统中，当一个时钟中断发生时。,两种调度方式,不可抢占（non-preemptive）调度方式：一个进程若被选中就一直运行下去，直到它被阻塞（I/O，或正在等待其他进程），或主动地交出CPU。以上的情形13均可发生调度；可抢占（preemptive）调度方式：当一个进程在运行时，调度程序可以打断它。以上的情形15均可发生调度，另外，在其他一些情形下，如就绪队列中

46、有新进程的优先级高于当前正运行的进程，也可能立即进行调度。,嵌入式调度算法的评价指标,响应时间（response time）：调度器为一个就绪任务进行上下文切换的时间，以及任务在就绪队列中等待的时间；周转时间（turnaround time）：一个任务从提交到完成所经历的时间；调度开销（overhead）：调度算法在执行时所需要的时间和空间开销；公平（fairness）：大致相当的两个进程所得到的CPU时间也应是大致相同的，防止饥饿(starvation)；均衡：尽可能使整个系统的各部分（CPU、I/O）都忙起来，提高系统资源的使用效率；吞吐量（Throughput）：单位时间内完成的任务数。

47、,先来先服务调度算法,先来先服务（First Come First Served，FCFS；First In First Out，FIFO）：按照任务到达就绪队列的先后次序进行调度；不可抢占方式：当前任务占用CPU，直到执行完或被阻塞，才让出CPU给另外一个任务；在任务被唤醒后（如I/O完成），并不立即恢复执行，而是放在就绪队列的末尾；优点：简单、公平，易于理解也易于实现。现实生活中应用广泛：排队。,FCFS算法的问题,平均周转时间取决于各任务到达的顺序，若短任务位于长任务之后，将增大平均周转时间。,例如，三个任务A、B、C的运行时间为24、3、3,短作业优先调度算法,短作业优先（Shorte

48、st Job First，SJF），设计 目标是改进FCFS算法，减少平均周转时间；SJF算法要求任务在开始执行时预计执行时间，对预计执行时间短的任务优先分派处理器；两种实现方案：不可抢占方式：当前任务在运行时不会被打 断，只有运行完毕或阻塞时，才让出CPU；可抢占方式：如果一个新的短任务到来，其 运行时间小于当前正在运行任务的剩余时间，则抢占CPU运行，称为SRTF（Shortest Remaining Time First）。,可以证明：对于一组同时到达的任务，采用SJF 算法将得到一个最小的平均周转时间。,D,时间,A,C,a a+b a+b+c a+b+c+d,例如，考察4个任务A、B

49、、C、D，其运行时间分别为a、b、c、d,B,A、B、C、D的周转时间分别为a、a+b、a+b+c和a+b+c+d，因此平均周转时间为：(4a+3b+2c+d)/4显然，当a b c d时，平均周转时间最小。,时间片轮转调度算法,在时间片轮转算法（Round-Robin，RR）中，将 所有的就绪任务按照FCFS原则，排成一个队列；每次调度时将处理器分派给队首任务，让其执行 一小段CPU时间（时间片，time slice）；在一个时间片结束时，如果任务还没有执行完的 话，将发生时钟中断，在时钟中断中，调度程序 将暂停当前任务的执行，并将其送到就绪队列的 末尾，然后执行当前的队首任务；如果一个任务

50、在它的时间片用完之前就已结束或 被阻塞，那么立即让出CPU。,开始时，任务B位于队列之首，因此被调度执行。当它的时间片用完后，就把它送到就绪队列的末尾。同时，任务F成为新的队首，被调度运行。,Round robin,too.,时间片轮转法的特点,优点：公平性：各个就绪任务平均地分配CPU的使用 时间。假设有n个就绪任务，时间片大小为q，那么每个任务将得到1/n的CPU时间；活动性：每个任务最多等待(n-1)q时间就能够 再次得到CPU去运行；缺点：q的大小难以确定（一般在2050ms）。q太大：退化为FCFS算法，进程在一个时间片 内都执行完，响应时间长。如q=100ms；q太小：每个任务都需