嵌入式操作系统原理与设计实现 课件 第4章 嵌入式实时内核数据结构

嵌入式实时内核数据结构

数据结构注册表双向链表任务控制块操作系统操作系统数据结构处理器的管理存储管理网络和通信的管理I/O设备管理文件管理任务管理任务表存储分配表文件目录设备表

总之，需要一大堆表数据结构（数组）数组1.同一数据类型数据的集合；2.占用连续内存空间；3.其中的所有元素名称都相同，但每个元素都有一个编号；4.元素名去掉编号（下标），得到的是数组名，数组名是个指针。inta[10]a[0]a[1]a[2]a[3]a[9]aa+1使用上的特点：1.分类存放；2.检索速度快且恒定；3.缺点：占用连续空间大……a+2a+3a+9应用：记录同类事物的表数据结构（位图）位图是数组的一种特殊应用a[10]（可以记录80个事物的状态）a[0]a[1]a[2]a[3]a[9]aa+1……a+2a+3a+9应用：登记表1/0D7D6D5D4D3D2D1D0双向链表数据结构（结构）1。不同数据类型数据的集合；2。占用连续内存空间；structStudent{intage;char*name;charsex;};使用上的特点：1。不分类存放，但用来描述同一事物；2。检索速度快且恒定；应用：通讯录中的一条记录、工具箱、厨房等等nextnext两个元素的链表数据结构（链表）structStudent{Student*nextintage;char*name;charsex;};1。同数据类型数据的集合；2。不占用连续内存空间。使用上的特点：1。分类存放，但空间上不连续（不需要大量的连续存储空间）；2。检索速度慢，且耗费的时间不固定；应用：存放大量的较大的表，类似档案柜数据结构（队列）按照先进先出的规则组织的数据结构可以用数组也可以用链表来实现主要用于对象的排队数据结构（堆栈）按照先进后出规则组织的数据结构主要用数组来实现主要用于程序模块的嵌套运行差分时间链

原队列插入37之后插入188793687936879-3=63637-8-7-9-3-6=4418-8-7=3任务控制块什么是多任务系统简单地说，就是能用一个处理器并发（注意，不是同时！）地运行多个程序的计算机管理系统。并发：由同一个处理器轮换地运行多个程序。或者说是由多个程序轮班地占用处理器这个资源。且在占用这个资源期间，并不一定能够把程序运行完毕。并发过程示意图处理器如何进行程序的切换？程序的切换（两句话）处理器是个傻瓜，PC让它干啥，它就干啥。PC是个指路器，它指向哪儿，处理器就去哪儿。从此可以知道，哪个程序占有了PC，哪个程序就占有了处理器。

=PC深刻地理解PC是理解系统进行程序切换动作的关键。所谓切换就是：PC目标地址如何操作PC指令：不同的计算机类型的指令是不同的。数据传送指令子程序返回指令（由堆栈弹出）中断服务程序返回指令（由堆栈弹出）任务代码任务堆栈内存处理器PCSP任务运行时与处理器之间的关系处理器通过两个指针寄存器（PC和SP）来与任务代码和任务堆栈建立联系并运行它寄存器组程序运行环境运行环境包括了两部分：处理器中的运行环境和内存中的运行环境任务代码任务堆栈内存处理器PCSP多任务时的问题任务代码任务堆栈内存任务代码任务堆栈内存？当有多个任务时，处理器中的运行环境应该怎么办？寄存器组程序运行环境程序

虚拟处理器PCSP

虚拟处理器PCSP

虚拟处理器PCSP

虚拟处理器PCSP调度器多任务时任务与处理器之间关系的处理程序处理器PCSP在内存中为每个任务创建一个虚拟的处理器（处理器部分的运行环境由操作系统的调度器按某种规则来进行这两个复制工作复制当需要运行某个任务时就把该任务的虚拟处理器复制到实际处理器中复制当需要中止当前任务时，则把任务对应的虚拟处理器复制到内存复制再把另一个需要运行的任务的虚拟处理器复制到实际处理器中寄存器组寄存器组也就是说，任务的切换是任务运行环境的切换虚拟处理器虚拟处理器应该存储的主要信息：1。程序的断点地址（PC）2。任务堆栈指针（SP）3。程序状态字寄存器（PSW）4。通用寄存器内容5。函数调用信息（已存在于堆栈）另外再用一个数据结构保存任务堆栈指针（SP），这个数据结构叫做任务控制块，它除了保存任务堆栈指针之外还要负责保存任务其他信息。这些内容通常保存在任务堆栈中，这些内容也常叫做任务的上下文。任务控制块是由操作系统另行构造的一个数据结构，每个任务都有一个。任务控制块结构的主要成员typedefstructos_tcb{

OS_STK*OSTCBStkPtr; //指向任务堆栈栈顶的指针

……

INT8U OSTCBStat; //任务的当前状态标志

INT8U OSTCBPrio; //任务的优先级别

……}OS_TCB;

任务代码任务堆栈内存任务控制块其实，程序切换的关键是把程序的私有堆栈指针赋予处理器的堆栈指针SP实质上系统是通过SP的切换来实现程序的切换的。要建立一个概念：具有控制块的程序才是一个可以被系统所运行的任务。程序代码、私有堆栈、任务控制块是任务的三要件。任务控制块提供了运行环境的存储位置。把一个大型任务分解成多个小任务，然后在计算机中通过运行这些小任务，最终达到完成大任务的目的。在μC/OS-II中，与上述那些小任务对应的程序实体就叫做“任务”（实质上是一个线程），μC/OS-II就是一个能对这些小任务的运行进行管理和调度的多任务操作系统。

从应用程序设计的角度来看，μC/OS-II的任务就是一个用户编写的C函数和与之相关联的一些数据结构而构成的一个实体。

任务代码任务堆栈内存在内存中应该存有任务的代码和与该任务配套的堆栈任务切换过程获得待运行任务的任务控制块恢复待运行任务的运行环境处理器的PC=任务堆栈中的断点地址处理器的SP=任务块中保存的SP如何获得待运行任务的任务控制块？小结一个完整的任务应该有如下三部分：任务代码（程序）任务的私有堆栈（用以保护运行环境）任务控制块（提供私有堆栈也是虚拟处理器的位置）这些都是任务方应该提供的基本信息。注册表优先级位图算法OSRdyGrp:优先级就绪组OSRdyTbl:优先级就绪表35:00100011charOSRdyGrp;charOSRdyTbl[8];下标二进制值000000001100000010200000100300001000400010000500100000601000000710000000优先级映射表charOSMapTbl[8]={0x01,0x02,0x04,0x08,0x10,0x20,0x40,0x80};OSMapTbl的数组元素的下标与任务优先级的高三位或低三位相对应。OSMapTbl的数组元素对应的二进制值中，位为1的位表示OSRdyGrp或是OSRdyTbl[]的对应位也为1。

35:00100011优先级判定表charOSUnMapTbl[256];以OSRdyGrp或是OSRdyTbl[]数组元素的值为索引，获取该值对应二进制表示中1出现的最低二进制位的序号（0-7）。

任务进入就绪态OSRdyGrp|=OSMapTbl[priority>>3];OSRdyTbl[priority>>3]|=OSMapTbl[priority&0x07];35:00100011OSRdyGrp765432101514131211109823222120191817163130292827262524393837363534333247464554434241405554535251504948636261605958575676543210OSRdyTblOSRdyTbl[0]OSRdyTbl[1]OSRdyTbl[2]OSRdyTbl[3]OSRdyTbl[4]OSRdyTbl[5]OSRdyTbl[6]OSRdyTbl[7]

00010000

00001000任务退出就绪态

if((OSRdyTbl[priority>>3]&=~OSMapTbl[priority&0x07])==0) OSRdyGrp&=~OSMapTbl[priority>>3];

35:00100011OSRdyGrp765432101514131211109823222120191817163130292827262524393837363534333247464554434241405554535251504948636261605958575676543210OSRdyTbl

00001000->11110111

00010000->11101111OSRdyTbl[0]OSRdyTbl[1]OSRdyTbl[2]OSRdyTbl[3]OSRdyTbl[4]OSRdyTbl[5]OSRdyTbl[6]OSRdyTbl[7]获取进入就绪态的最高优先级high3Bit=OSUnMapTbl[OSRdyGrp];low3Bit=OSUnMapTbl[OSRdyTbl[high3Bit]]; priority=(high3Bit<<3)+low3Bit;

35:00100011OSRdyGrp7654321015141312111098232221201918171631302928272625241000100047464554434241405554535251504948636261605958575601010000OSRdyTbl

0x60->4/high3Bit

0x88->3/low3Bit

ucOS中，任务按优先级进行组织，以优先级为数组元素下标，通过OSTCBPrioTbl[]即可找到相应的TCB。OSRdyTbl[0]OSRdyTbl[1]OSRdyTbl[2]OSRdyTbl[3]OSRdyTbl[4]OSRdyTbl[5]OSRdyTbl[6]OSRdyTbl[7]第四章嵌入式实时内核基础任务任务进程:有自己的内存空间线程:有自己的堆栈和硬件寄存器任务:抽象概念,一个无限循环任务划分的例子IP任务,telnet任务，COM口任务，OSPF任务，BGP任务，UDP/TCP任务例子起始任务Task0Task1Task0Task0Task1Task1t0t1t2t3t4t5t6t7t8

图1-1（1）系统经历一系列的初始化过程后进入boot_card()函数，在其中调用ucBsp_init()进行板级初始化后，调用main（）函数；（2）main（）函数调用OSInit()函数对µC/OS-II内核进行初始化，调用OSTaskCreate创建起始任务TaskStart；（3）main（）函数调用函数OSStart()启动µC/OS-II内核的运行，开始多任务的调度，执行当前优先级最高的就绪任务TaskStart；（4）TaskStart完成如下工作：a、安装时钟中断并初始化时钟，创建2个应用任务；b、挂起自己(不再被其它任务唤醒)，系统切换到当前优先级最高的就绪任务Task0。操作系统配置配置的方法为修改uC_OS-II源代码目录中的OS_CFG.h文件

#defineOS_MAX_EVENTS10/*最多可以有10个事件*/#defineOS_MAX_FLAGS5/*最多可以有5个事件标志*/#defineOS_MAX_MEM_PART5/*最多可以划分5个内存块*/#defineOS_MAX_QS2/*最多可以使用2个队列*/#defineOS_MAX_TASKS3/*最多可以创建3个任务*/#defineOS_LOWEST_PRIO14/*任务优先级不可以大于14*/#defineOS_TASK_IDLE_STK_SIZE1024/*空闲任务堆栈大小*/#defineOS_TASK_STAT_EN1/*是否允许使用统计任务*/#defineOS_TASK_STAT_STK_SIZE1024/*统计任务堆栈大小*/。。。。C-OSSampleCodevoidmain(void){

/*PerformInitializations*/...OSInit();...

/*CreateatleastonetaskbycallingOSTaskCreate()*/OSStart();}OSTaskCreate(TaskStart,(void*)0,&TaskStartStk[TASK_STK_SIZE-1],4);TaskStart任务

TaskStart任务负责安装操作系统的时钟中断服务例程、初始化操作系统时钟，并创建所有的应用任务： ucos_x86_idt_set_handler(0x20,(void*)OSTickISR,0x8e00);/*InstalluC/OS-II'sclocktickISR*/ ucos_timer_init();/*Timer初始化*/

TaskStartCreateTasks();

/*Createalltheapplicationtasks*/OSTaskSuspend(OS_PRIO_SELF);staticvoidTaskStartCreateTasks(void){INT8Ui;for(i=0;i<N_TASKS;i++){/*CreateN_TASKSidenticaltasks*/ TaskData[i]=i;/*Eachtaskwilldisplayitsownletter*/}OSTaskCreate(Task0,(void*)&TaskData[i],&TaskStk[i][TASK_STK_SIZE-1],5);OSTaskCreate(Task1,(void*)&TaskData[i],&TaskStk[1][TASK_STK_SIZE-1],6);}应用任务1voidTask0(void*pdata){INT8Ui;INT8Uerr;i=*(int*)pdata;

for(;;){

……/*此处为输出信息,显示任务运行的状态*/ err=OSTaskSuspend(5);/*suspenditself*/}}应用任务2voidTask1(void*pdata){ INT8Ui;INT8Uerr;i=*(int*)pdata;

for(;;){OSTimeDly(150);

……/*此处为输出信息,显示任务运行的状态*/OSTimeDly(150);err=OSTaskResume(5);/*resumetask0*/ }}运行结果在μC/OS-Ⅱ中，当一个运行着的任务使一个比它优先级高的任务进入了就绪态，当前任务的CPU使用权就会被抢占，高优先级任务会立刻得到CPU的控制权（在系统允许调度和任务切换的前提下）练习系统初始化，之后进入main函数；在main函数中创建TaskStart任务，由TaskStart任务创建所有的应用任务（TA0、TA1、TA2）。优先级较高的任务TA0、TA1先延时若干个时钟节拍，以便低优先级任务TA2运行。任务调度1.调度算法---非抢占式图1所示为非抢占式内核程序流程：①低优先级任务（LPT）执行；②低优先级任务被中断；③执行中断服务例程，使高优先级任务（HPT）就绪；④中断服务例程返回到被中断的低优先级任务；⑤低优先级任务继续执行；⑥低优先级任务放弃CPU；⑦高优先级任务运行。调度算法---抢占式图2所示为抢占式内核程序流程：①低优先级任务执行；②异步事件使任务中断；③响应异步事件，运行中断服务例程，使高优先级任务就绪；④中断服务例程返回到高优先级任务；⑤高优先级任务执行，直到它被中断转向执行优先级更高的任务；⑥高优先级任务结束，内核切换到低优先级任务；⑦低优先级任务继续执行。2.可抢占内核就绪态运行态等待态获得CPU被高优先级任务抢占或超时获得资源需要资源任务状态变迁任务1任务2任务3调度程序05101520253035404550运行等待就绪三个任务进行状态转换的过程

包含三个任务和一个调度程序。调度程序用来确定下一个需要投入运行的任务，因此调度程序本身也需要占用一定的处理时间。Ucos任务的程序实现

（一）TaskstatesandtransitionofucOS空闲任务whichisexecutedwhennoneoftheothertasksisreadytorun.Theidletaskisalwayssettothelowestpriority.Theidletaskcanneverbedeletedbyapplicationsoftware.typedefstructos_tcb{

OS_STK*OSTCBStkPtr;

/*Pointertocurrenttopofstack

*/#ifOS_TASK_CREATE_EXT_EN>0void*OSTCBExtPtr;

/*PointertouserdefinabledataforTCBextension*/OS_STK*OSTCBStkBottom;/*Pointertobottomofstack

*/INT32UOSTCBStkSize;/*Sizeoftaskstack(innumberofstackelements)*/INT16UOSTCBOpt;/*TaskoptionsaspassedbyOSTaskCreateExt()*/INT16UOSTCBId;/*TaskID(0..65535)*/#endifstructos_tcb*OSTCBNext;/*PointertonextTCBintheTCBlist

*/structos_tcb*OSTCBPrev;/*PointertopreviousTCBintheTCBlist*/#if((OS_Q_EN>0)&&(OS_MAX_QS>0))||(OS_MBOX_EN>0)||(OS_SEM_EN>0)||(OS_MUTEX_EN>0)OS_EVENT*OSTCBEventPtr;/*Pointertoeventcontrolblock

*/#endif#if((OS_Q_EN>0)&&(OS_MAX_QS>0))||(OS_MBOX_EN>0)void*OSTCBMsg;/*M