基于嵌入式操作系统的任务调度算法及Internet协议栈研究

1、上海交通大学硕士学位论文基于嵌入式操作系统的任务调度算法及Internet协议栈研究姓名：张乐宾申请学位级别：硕士专业：计算机应用技术指导教师：谢康林2003.1.1上海交通大学硕士学位论文基于嵌入式操作系统的任务调度算法及Internet协议栈研究摘要随着嵌入式系统和Internet的不断发展在很多嵌入式系统中TCP/IP协议是嵌入式操作系统必须实现的功能以一个源码公开的实时嵌入式操作系统uCOS-II为基础法的函数进行一定的修改并根据标准TCP/IP协议构建出一个基于uCOS-II的网络协议栈模型号量可能设置一些信在一定程度上避免死锁发生的对其任务调度算传输控制协议死锁I上海交通大学硕士学

2、位论文Research Of Scheduling Algorithms andInternet Protocol Stack Based onEmbedded Operation SystemAbstractWith the development of Embedded System and Internet, theapplication about networks is very popular now. In most embeddedsystems, it is necessary to implement TCP/IP protocol in embedded OS.In th

3、is article, based on an operation system named “uCOS-II”whose source code is opened, we have modified the task-schedulingalgorithm. We have combined the priority scheduling with round-robinscheduling. In addition, we have built a system module to implementfunction of networks based on standard TCP/I

4、P and our actual hardwareenvironment. Also, we have set some semaphores to control the resourceand avoid deadlock in some degree.Key WordsEmbedded OSScheduling AlgorithmIIShanghai Jiaotong UniversityJan.2003上海交通大学学位论文原创性声明本人郑重声明是本人在导师的指导下除文中已经注明引用的内容外对本文的研究做出重要贡献的个人和集体本人完全意识到本声明的法律结果由本人承担张乐宾日期上海交通大学

5、学位论文版权使用授权书本学位论文作者完全了解学校有关保留同意学校保留并向国家有关部门或机构送交论文的复印件和电子版本人授权上海交通大学可以将本学位论文的全部或部分内容编入有关数据库进行检索缩印或扫描等复制手段保存和汇编本学位论文本学位论文属于不保密指导教师签名年月日日期上海交通大学硕士学位论文特别是随着大规模集成电路产生而出现的微型计算机给人类生活带来了根本性的改变那么可以毫不夸张的说在微型计算机中微处理器是现代信息技术的组成的系统就是可以嵌入到任何微型或小型仪器嵌入式系统则被定义为以计算机技术为基础适应应用系统可靠性体积嵌入式系统是将先进的计算机技术电子技术和各个行业的具体应用相结合后的产物

6、资金密集不断创新的知识集成系统在一台通用计算机的外部设备中就包含了多个嵌入式微处理器鼠标硬盘显示器声卡扫描仪嵌入式计算机主要应用在制造工业通讯仪表船舶航天由嵌入式微控制器嵌入式系统是面向用户则会失去 市场能力间竞争的热点面向应用的体积可靠性处理这些也是各个半导体厂商之嵌入式系统的硬件和软件都必须高效率地设计去除冗余这样才能在具体应用对处理器的选择面前更具有竞争力对芯片配置进行裁剪和添加才能达到理想的性能因此不同的处理器面向的用户是不一样的行业用户或单一用户特别是与Internet和无线网络的结合基于知识的嵌入式系统也将是一个发展方向嵌入式系统的硬件系统体积越来越小功能越来越强嵌入式系统应用将越

7、来越多样化它不仅广泛应用于信息家电农业服务业等各行业小型嵌入式系统通常分为实时或者非实时的两类上海交通大学硕士学位论文不但要求任务能完成而非实时系统在这方面的要求相应低一些体现嵌入式操作系统的实时性在很多实时系统中配不同的优先级先级的顺序运行例如单调执行率调度法给每个任务分并且各个进程严格按照优Linux的非实时内核在网络服务环境下由于Internet服务进程的特点并且它们之间没有优先权的高低之分对每个进程分配一定的时间片各个进程轮流得到调度对每个任务分配不同的优先权是实现实时调度的基本必要条件又要提供一定的Internet服务需要按照优先级不同顺序完成则希望它们轮流执行指定相应的调度策略就显

8、得比较重要在嵌入式操作系统中的有限往往内存资源都非常对于系统中的资源笔者针对以上的要求根据其内核优先权分配的特点将任务优先权调度和时间片轮转在一定程度上作适当的结合结合实际系统的大小和应用情况进行适当的裁剪同时利用操作系统的进程间通信方法对系统的资源作一定的控制最后对操作系统在单片上的移植方法提出一个大致的方案包括内核和网络协议代码另外在运行中需要大约32K的RAM容量1.2 论文内容安排整篇论文采取了以如下方式进行组织第一章第二章特点任务调度算法本章简要的介绍了一下嵌入式系统的概念和应用发展情况本章主要介绍了实时嵌入式系统的一些第三章笔者在本文中就是以uCOS-II嵌入式操作系统内核作为基础

9、主要讲述了操作系统的任务控制块任务调度算法时钟控制等方面第四章上海交通大学硕士学位论文第四时系统的特点和两章是本文的重点笔者结合嵌入式实Internet的应用对原有内核中死锁控制和任务调度提出了一种新的将原有的优先权调度和时间片轮转方法相结合以实现基于Internet应用的合理优化设置了相应的信号量和算法对嵌入式系统中的有限资源进行控制Internet协议栈4.4FreeBSD的Internet协议栈模型主要的数据结构和数据报处理流程第六章本章总结了论文所做的工作应用的嵌入式操作系统提出了一个基于并列出了基于Internet上海交通大学硕士学位论文如果逻辑和时序出现偏差将会引起严重后果的系统软

10、实时和硬实时系统硬实时系统必须是对及时的事件做出反应在硬实时系统中如果出现了这样的情况就意味着巨大的损失和灾难对堆芯过热做出及时的处理允许发生错过而软实时系统是指如果没有deadline的情况而且不会造成太大的危害硬实时系统和软实时系统的实现区别主要是在选择调度算法上而且可以提供高速的响应和大的系统吞吐率需要使用的算法就应该是调度方式简单大多数实时系统是二者的结合多数实时系统又是嵌入式的个计算机在系统里面而用户看不到有就需要引入实时内核的概念它的使用使得实时应用程序的设计和扩展变得很容易RTOS的引入随着嵌入式系统中软件比重不断上升对开发人员程序档案的组织管理成为一个大的课题对于开发单位和开发

11、人员都是一个提高RTOS使得应用程序的设计过程大为简化它的基本功能包括任务管理存储器管理事件管理消息管理旗语管理等也就是RTOS的APIËùÓÐʱ¼äÒªÇó¿Á¿ÌµÄʼþ¶¼µÃµ½Á˾¡¿ÉÄÜ¿ì

12、9;Ýͨ¹ýÓÐЧµÄ·þÎñÓÊÏäÑÓʱRTOS使得资源得到更好的利用的应用是和前面所述的应用复杂化直接相关的采取一个主循环和几个顺序调用的子程序模块即可满足要求可以适应应用复杂化这一要求随着应用的复杂化要求有实时响应各个任务之间有多种信息传递一是中断可能上海交通大学硕士学位论文处理时间过长通信方面则会降低系统整体的信息流量也多降低软件可靠性对于网络要考虑的

13、各种可能RTOS是实时嵌入式系统在启动之后运行的一段背景程序RTOS根据各个任务的要求包括存储器的管理任务调度在RTOS支持的系统中RTOS根据各个任务的优先级来动态的切换各个任务这种体系结构简化了编程结构从性能上讲在实时计算中从这个角度上看定或者确定的时间内完成系统功能和对外部或内部实时一个能够在实现指具有较高的可移植性一些成熟的通用程序可以作为专家库函数产品推向社会产品化能够促进行业交流以及社会分工专业化提高知识创新的效率实时多任务操作系统进入嵌入式工业对嵌入式软件的标准化和加速知识创新是一个里程碑(1) (2)(3)系统响应时间任务切换时间中断延迟时间并完成进入中断服务程序的时间时代的产

14、物议栈必然会作为开发嵌入式系统中必要考虑的问题上网络应用程序的接口应用系列当然信息电器是网络嵌入一个网络协通过网络协议栈提供对嵌入式系统如TCP/IP协议以及相应的授权的功能提高了开发成本应该考虑使用实时内核内核的价格以及2%到4%的CPU额外负荷在一些低成本的应用中在网络协议栈的开发过程中选用高性能稳定的软件平台尽量降低开发成本上海交通大学硕士学位论文内核负责管理各个任务并且负责任务之间的通信用实时内核可以大大简化应用系统的设计由实时内核来管理它们代码空间增加之所以使ROM的用量而且更这是相当可观的容量实时内核根据CPU控制权的分配方法加主要的是不同2.2.1非占先式内核内核要求每个任务自我

15、放弃CPU的所有权cooperative multitasking各个任务彼此合作共享一个CPUÖжϷþÎñ¿ÉÒÔʹһ¸ö¸ßÓÅÏȼ¶µÄÈÎÎñÓɹÒÆð״̬

16、±äΪ¾ÍÐ÷״ֱ̬µ½¸ÃÈÎÎñÖ÷¶¯·ÅÆúCPU的使用权时非占先式内核的一个优点式响应中断快非占先式内核允许使用不可重入函数而不必担心其他任务可能正在使用该函数因为每个任务要运行到完成时才释放CPU的控制权使用非占先式内核时级响应时间取决于最长的任务执行时间此时的任务非占先式某种情

17、况下号量先式内核几乎不需要使用信号量来保护共享数据而不必担心被别的任务抢占在处理共享I/O设备时仍需要使用互斥型信在打印机的使用上如图2.1所示为非占高优先级的任务已经进入就绪与不知道什么时候态也许要等很长时间前后系统一样最高优先级的任务才能拿到CPU控制权目前商业软件中几乎没有非占先式内核上海交通大学硕士学位论文要使用抢占式内核uCOS-II以及绝大多数商业上销售的实时内核都是占先式内核总能得到CPU的控制权当前任务的CPU使用权就被剥夺了高优先级的任务立刻得到了CPU的控制权中断完成时使用占先式内核的控制权时可知的那个可以得到CPU使用占先式内核时调用不可重入型函数要满足互斥条件如果调用不

18、可重入型函数时不可重入型函数中的数据有可能被破坏占先式内核总是让就绪态的高优先级任务先运行到中断服务完成时不一定是那个被中断了的任务任务级系统响应时间得到了最优化uCOS-II属于占先式内核上海交通大学硕士学位论文使高优先级任务就绪¾ÍÊǾö¶¨¸ÃÂÖµ½ÄĸöÈÎÎñÔËÐÐÁËÿ

19、4;öÈÎÎñ¸ù¾ÝÆäÖØÒª³Ì¶ÈµÄ²»Í¬±»¸³ÓèÒ»¶¨µÄÓÅÏȼ¶CPU总是让处在就绪态的优先级最高的任务先运行究竟何时让高优先级任务掌握CPU的

20、使用权这要看用的是什么类型的内核也称dispatcher一个良好的任务调度算法应该主要体现在以下几个方面保证每个进程得到合理的CPU时间使CPU保持忙碌状态l 响应时间l 周转时间l 吞吐量很显然这几个目标不可能同时达到操作系统会在这几个方面中做出相应的取舍的处理机调度算法有FCFSSJF不同的常用上海交通大学硕士学位论文使高优先级任务就绪¾ÍÊǾö¶¨¸ÃÂÖµ½ÄĸöÈÎÎ

21、41;ÔËÐÐÁËÿ¸öÈÎÎñ¸ù¾ÝÆäÖØÒª³Ì¶ÈµÄ²»Í¬±»¸³ÓèÒ»¶¨µÄÓÅÏ

22、00;¼¶CPU总是让处在就绪态的优先级最高的任务先运行究竟何时让高优先级任务掌握CPU的使用权这要看用的是什么类型的内核也称dispatcher一个良好的任务调度算法应该主要体现在以下几个方面保证每个进程得到合理的CPU时间使CPU保持忙碌状态l 响应时间l 周转时间l 吞吐量很显然这几个目标不可能同时达到操作系统会在这几个方面中做出相应的取舍的处理机调度算法有FCFSSJF不同的常用上海交通大学硕士学位论文FCFSÐò½øÐе÷¶ÈÐÐÊ&

23、#177;¼äµÄ³¤¶ÌSJF把CPU分给需要运行时间最短的进程¼´°´½ø³Ìµ½À´µÄÏȺó´Î¶ø²»¹ÜÆäËùÐèÔËSJF算法一般根据进程的某些特性永久性地把各个

24、进程分别链入其中某一个队列中此外通常采用固定优先级的抢占式调度各个队列的优先级自上而下降低队列4中的进程才可以运行如果队列1中进入了一个就绪进程多级反馈队列法允许进程在各队列间移动如果一个进程要使用很长的CPU时间这种方式把I/O繁忙型和交互式进程放在较高优先级的队列中在低优先级队列中长时间等待的进程可以移到较高优先级队列中2.3.1时间片轮转调度法当两个或两个以上任务有同样优先级叫做时间额度调度就绪态的任务也叫做时间片把CPU控制权交给下一个任务l 当前任务在时间片还没结束时已经完成了其中时间片是一个重要的参数通常为10至100ms数量级CPU调度程序轮流地把CPU分给就绪队列中地每个进程L

25、inux操作系统就是采用时间片轮转的调度算法所以给任务定优先级是不容易的并非所有的任务都至关重要大多综合了软实时和硬实时这两种需求并不要求在某一特定时间内完成实时系统任务不但要执行无误一项有意思的技术称之为单调执行率调度法RMSÕâÖÖ·½·¨»ùÓÚÄĸöÈÎÎñÖ´ÐеĴÎÊý×

26、îƵ·±RMS做了一系列假设上海交通大学硕士学位论文u 所有的任务都是周期性的没有共享资源u CPU必须总是执行那个优先级最高且处于就绪态的任务要使用占先式调度法要使所有的任务满足硬实时条件这就是RMS定理Ti是任务i的执行周期是任务i所需的CPU时间极限值是ln2或0.693Ei/Tin是系统中的任务数»ùÓÚRMSËùÓÐÓÐʱ¼äÌõ¼þÒ

27、0;ÇóµÄÈÎÎñi×ܵÄCPU时间应小于70%ÕâÀïÊÇÖ¸ÓÐʱ¼äÌõ¼þÒªÇóµÄÈÎÎñʹµÃCPU的利用率达到100%Ò

28、42;ΪÄÇÑùµÄ»°³ÌÐò¾ÍûÓÐÁËÐ޸ĵÄÓàµØµÄÒ»ÌõÔ-ÔòRMS认为最高执行率的任务具有最高的优先级行率的任务并非是最重要的任务有什么优先级分配可以讨论了有意

29、思的起点最高执也就没RMS无疑是一个×÷ΪϵͳÉè¼Æ上海交通大学硕士学位论文2.4死锁的控制死锁是若干进程因使用系统资源不当而造成的带有全局危害性的现象系统发生死锁现象不仅浪费大量的系统资源带来灾难性的后果在多道程序系统中就叫死锁进程如果从广义角度理解资源和死锁问题在日常生活环境中也会出现过一条独木桥那么当两个人从桥上两端同时上桥这样两个人就只能在桥上相对而立过桥人就相当于进程准备走过的桥相当于要申请的资源如果两人中有一个人能够退回到桥的一端用操作系统的术语来说rol

30、lback显然而不管对方是否有人在桥上保证过桥不出现死锁的唯一办法是每个过桥的人都要遵守一下协议先看一下对方是否有人在桥上他就可以过桥他就要等对方过桥后再过桥2.4.1死锁的产生条件根据以上的分析可以知道(1) 相互排斥即再一个时刻只能有一个进程可用该资源所以这种资源的使用方式是独占性的必然存在这样的进程而后者当前被另外的进程占有资源不可以被抢占而通常这是在该进程完成它的任务之后执行的必然存在一组等待进程P0,P1,PnP1等待P2占有的资源Pn1等待Pn占有的资源应该强调指出最后一条更为重要上海交通大学硕士学位论文为它往往含有其它两条的意思个条件同时出现的情况要设法破坏上述四通常有两种处理死

31、锁问题的方法证系统从来也不会进入死锁状态设法发现并克服它发现死锁是很困难的出现死锁必须具备四个条件么就破坏了死锁产生的条件提出预防措施例如另一方面包含在死锁之中只读文件一直等待下去保然后因此那我们分别根据那四个条件从而他们不会若干进程如果同时打开进程从来也不会在共享资源上一般来说2. 破坏占有且等待的条件为了使系统中从来不会出现这种条件一种办法是资源的静态分配个进程开始执行之前就申请并分到所需的全部资源由于预先就为它把所需资源都准备好了在实现时在一另外一种办法是程可能要申请并使用某些资源当前分到的全部资源我们考虑有一个进程把盘文件排序申请读卡机行式打印机和磁带驱动器尽管它只是在最后才用到磁带机

32、一个进必须先释放它并复制到磁盘上那么该进程最初就必须它把信息从读卡机上复制到磁盘打印机以后该进程必须申请盘文件和行式把二者都释放上海交通大学硕士学位论文为它往往含有其它两条的意思个条件同时出现的情况要设法破坏上述四通常有两种处理死锁问题的方法证系统从来也不会进入死锁状态设法发现并克服它发现死锁是很困难的出现死锁必须具备四个条件么就破坏了死锁产生的条件提出预防措施例如另一方面包含在死锁之中只读文件一直等待下去保然后因此那我们分别根据那四个条件从而他们不会若干进程如果同时打开进程从来也不会在共享资源上一般来说2. 破坏占有且等待的条件为了使系统中从来不会出现这种条件一种办法是资源的静态分配个进程开

33、始执行之前就申请并分到所需的全部资源由于预先就为它把所需资源都准备好了在实现时在一另外一种办法是程可能要申请并使用某些资源当前分到的全部资源我们考虑有一个进程把盘文件排序申请读卡机行式打印机和磁带驱动器尽管它只是在最后才用到磁带机一个进必须先释放它并复制到磁盘上那么该进程最初就必须它把信息从读卡机上复制到磁盘打印机以后该进程必须申请盘文件和行式把二者都释放上海交通大学硕士学位论文磁带机这两种方法存在两个主要缺点配了的状况饿死然要无限期地等待下去3. 破坏非抢占式的条件随后就释放这两个资源因为又很多资源被分(2) 可能出现有的进程总得不到运行紧俏它就必源产生死锁的第三个必要条件是对已分配资源的非

34、抢占式再分配可采用下述方式它还要申请另外的资不能立即分配给它那么就是说被剥夺的资源加到该进程正在等待的资源表中它才能重新启动若一个进程申请某些资源如果可用如果它们不可用是否把它们已分给另外某个正等待附加资源的进程就把所需资源从等待进程那儿抢占过来如果该资源不可用那么申请进程必须等待它的某些资源可被抢占过去仅当一个进程分到它所需的新资源并且恢复了在它等待其间被抢占去的所有资源时这些办法常用于资源状态易于保留和回复的环境中这些办法一般不能用于如打印机4. 破坏循环等待的条件为了使循环等待的条件从不出现一类资源都有唯一的一个整数值中是否一个资源先于另一个令R=r1,r2,rm®®

35、F(R)=N´Å´ø»ú读卡机1ÀýÈ纯ÊýF可定义如下磁盘机5磁带机7打印机12即每确定在给定顺序®®®÷ÎÒÃÇ×÷ÈçÏÂÔ¼¶¨¼´Ò»¸ö½ø³Ì×

36、8;³õ¿ÉÉêÇëÈκÎÀàÐ͵Ä×ÊÔ´以申请一个新资源rj例如此后该进程可一个期望同时使用读卡机和打印机的进程必须首先申请读卡机另一种申请办法也很简单它应释放任何上海交通大学硕士学位论文满足F(ri)F(rj)关系的资源ri»·Â·µÈ´ýÌõ¼þ&

37、#190;ͱ»ÅųýÁË´æÔÚÑ-»·µÈ´ýri´Ó¶øpn等待p0占有的资源从而存在F(ri)<F(ri+1)Èô¼Ù¶¨这里pi等待pi+1占有的资源由于pi+1占有的资源riÓÚÊǾÍÓÐÕ

38、;âÊDz»¿ÉÄܵÄӦעÒâµ½Òò¶øÓÐF<F¼´ÔÚÕâÖÖÔ¼¶¨ÏÂÀýÈç½ø³ÌµÄ

39、;ÓÅÏȼ¶·ÖÅä·½·¨ÈÝÊDZ¾ÎĵÄÀíÂÛ»ù´¡°üÀ¨Äں˵ÄÌصãÕâЩ

40、;ÄÚ上海交通大学硕士学位论文第三章 uCOS-II嵌入式操作系统目前主要的嵌入式操作系统有VxWorkspSOSQNXLYNX和Linux等占用过多内存为了提高执行速度和系统可靠性而不是存储于磁盘等载体中如何压缩系统的规模也是一个非常重要的方面减少了内存的占用就能降低系统的成本占先式内核的提供了实时系统所需的基本功能而且由于uCOS-II是可裁剪的非常短小精悍务调度时间管理没有提供输入输出管理网络之类的额外服务用户可以自己添加所需的各种服务它只包含了任绪条件下优先级最高的任务优先级必须不同重要性是相同的务在处理完成后必须进入等待或挂起状态系统通过两种方法进行任务调度系统会

41、调用函数OSIntCtxSw()执行切换功能这时系统通过发软中断命令或依靠处理器执行陷阱指令来完成任务切换即它总是执行处于就uCOS-II规定所有任务的即使两个任务的这也就意味着高优先级的任最多可以管理64个任务在目前的版本中的任务uCOS-II提供了任务管理的各种函数调用删除任务挂起和恢复任务等一是空闲任务OSTaskIdle()该任务只是不停地给一个32位的整型变量加一它的优先级为OS_LOWEST_PRIO-1¶ÔÓÚÒ»¸ö¶àÈÎÎñ²

42、Ù×÷ϵͳÀ´ËµuCOS-II提供了四种同步对象邮箱通过邮箱和消息队列还可以进行任务间的通信等待但这些对象一旦创建就不能删除也可以根据系统的实际需要选择使用合适的同步对象只有与处理器硬件相关的一上海交通大学硕士学位论文部分代码用汇编语言编写32位微处理器可以在绝大多数8位uCOS-II的移植并不复杂由于本文涉及的系统内核的修改主要是在进程调度和进程间通信这两方面的内容下面对这几个方面先做一定的介绍这里不再赘述OS_TCBÒ»µ©½

43、¨Á¢ÈÎÎñÈÎÎñ¿ØÖÆ¿éÊÇÒ»¸öÊý¾Ý½á¹¹用它来保存该任务的状态任务从中断的那一点丝毫不差的执行下去任务建立的时候要成员变量自己的栈它task control blockuCOS-II任务控制块会确保以下为uCOS-II任务控制块中的主uCOS-II允许每个任务有每个任

44、务的栈的容量可以是任意的除非用户写一个复杂的接口函数改变当各任务需要的栈空间不同时l OSTCBStkBottom时指向任务栈底的指针即栈存储器从高地址向低地址方向分配类似地则OSTCBStkBottom指向任务可以使用的栈空间的最高地址ByteÒ²¾ÍÊÇ˵ÿ¸öµØÖ·µÄ¿í¶ÈÊÇ32位的同样是1000个入口地址则总栈容量有2000字节该链表在时

45、钟节拍函数中使用每个任务的任务控制块OS_TCB在任务建立的时候被链接到链表中双重链接的链表使得任一成员都能被快速插入或者删除l OSTCBMsg是指向传给任务的消息的指针或者需要把任务挂起一段时间以等待某事件的发生在这种情况下如果这个变量为0»òÕß±íʾµÈ´ýʼþ·¢ÉúµÄʱ¼äûÓ

46、8;ÏÞÖƵ±OSTCBStat为0¿ÉÒÔ¸øOSTCBStat赋其它的值以表示任务的其它状态上海交通大学硕士学位论文l OSTCBPrio是任务优先级是说任务的优先级越高就绪态的过程或进入等待事件发生状态的过程也就用于加速任务进入这个数也是uCOS-II分配给用户程序的任务控制块OS_TCBs的最大数目在uCOS-II初始化的时候所有任务控制块OS_TCBs被链接成空任务控制块的单向链表空任务控制块指针OSTCBFreeList指向的任务控制块便赋给了该任务一旦任务被删

47、除OSTCBFreeList图空任务列表3.2 优先权调度管理方法uCOS-II最多可以管理64个任务在目前的版本中的任务每个任务的就绪态标志放在一个就绪表中在OSRdyGrp中8个任务为一组任务进入就绪态时为确定下次该哪个优先级的任务运行了和OSRdyTbl之间的关系是按以下规则给出的OSRdyG的rp第X位置1»¹¶¨ÒåÁËÁ½¸öÊý×éOSMapTbl和OSUnMapTbl256用于辅助计算OSUnMapTbl256称为优先级

48、判定表返回值在0到7之间上海交通大学硕士学位论文表3.1 OSMapTbl的值Table 3.1 The Value of OSMapTbl下标23467通过以上的结构定义例如如下所示位掩码0000010000001000000100000100000010000000从就绪表中删除一个任务于正常的任务状态变化时发生的调度为uCOS-II是占先式系统其中还调用了一些实际切换处理器环境的函数前者用因_任务调度函数OSSched()void OSSched (void)INT8U y;OS_ENTER_CRITICAL();if (OSLockNesting | OSIntNesting) = 0

49、)y = OSUnMapTblOSRdyGrp;OSPrioHighRdy = (INT8U)(y<<3) + OSUnMapTblOSUnMapTbly);上海交通大学硕士学位论文if (OSPrioHighRdy != OSPrioCur)OSTCBHighRdy = OSTCBPrioTblOSPrioHighRdy;OSCtxSwCtr+;OS_TASK_SW();OS_EXIT_CRITICAL();_脱离中断服务函数OSIntExit()void OSIntExit (void)OS_ENTER_CRITICAL();if (-OSLockNesting | OSInt

50、Nesting) = 0)OSIntExitY = OSUnMapTblOSRdyGrp;OSPrioHighRdy = (INT8U)( OSIntExitY << 3) +OSUnMapTblOSRdyTblOSIntExitY);if (OSPrioHighRdy != OSPrioCur)OSTCBHighRdy = OSTCBPrioTblOSPrioHighRdy;OSCtxSwCtr+;OSIntCtxSW();OS_EXIT_CRITICAL();_3.3 事件控制块结构在uCOS-II操作系统中ECBËùÓе&#

51、196;ÐźŶ¼±»¿´³ÉÊÇʼþÖ»ÓÐÈÎÎñ¿ÉÒԵȴýʼþ·¢Éú¶ÔÓÚ´¦Ó&#

52、218;µÈ´ý״̬µÄÈÎÎñÒÔ´ËÀ´·ÀÖ¹ÒòΪµÈ´ýµÄʼþûÓз¢Éú¶øÎ&#

53、222;ÏÞÆڵصÈÏÂÈ¥Èçͼ3.2B所有等待该事件的任务中准备执行当事件是一个信号量时可以是信号量也可以给他发送消息在这种情况下来向另外的任务发信号如图3.2A上海交通大学硕士学位论文AB图事件控制块的使用uCOS-II通过OS_EVENT数据结构来维护一个事件控制块的所有信息该结构中除了包含了事件本身的定义用于指向邮箱的指针还定义了等待该事件的所有任务的列表l OSEventPtr指针当所定义的事件是邮箱时而当所定义的事件

54、是消息队列时l OSEventTbl和OSEventGrp很像前面提到的任务调度中的OSRdyTbl和OSRdyGrp¶øºóÁ½Õß°üº¬µÄÊÇϵͳÖд¦ÓÚ¾ÍÐ÷״̬µÄÈÎÎñO

55、SEventCnt是用于信号量的计数器它可以是信号量OS_EVENT_TYPE_MBOXOS_EVENT_TYPR_QÓû§Òª¸ù¾Ý¸ÃÓòµÄ¾ßÌåÖµÀ´µ÷ÓÃÏàÓ¦µÄϵͳº¯&

56、#202;ýÔÚϵͳÖÐÓë¿ÕÏÐÈÎÎñ¿ØÖÆ¿éµÄ¹ÜÀíÒ»ÑùËùÓеÄʼþ¿ØÖÆ&

57、#191;é±»Á´½Ó³ÉÒ»¸öµ¥ÏòÁ´±íÓÊÏä»òÕßÏûÏ¢¶ÓÁÐʱ²¢¶ÔËü½øÐÐ&

58、#179;õʼ»¯ÓÊÏäºÍÏûÏ¢¶ÓÁÐÒ»µ©½¨Á¢¾Í²»ÄÜɾ³ýÿ¸öµÈ´ýʼþ&

59、#183;¢ÉúµÄÈÎÎñ¶¼±»¼ÓÈëµ½¸Ãʼþ¿ØÖÆ¿éÖеĵȴýÈÎÎñÁбíÖÐ&

60、#177;äÁ¿Ç°ÃæµÄ是数据结构的一个域所有的等待该事件的任务的优先级被分成8组当某组中有任务处于等待该事件的状态时相应地说明该变量上海交通大学硕士学位论文当一个事件发生以后在.OSEventTbl中也即优先级代码最小的任务得到该事件也要用到OSMapTbl和OSUnMapTbl256这两个表用于查找这里不再赘述信号量可以根据系统的实际需要选择相应的通信方式了信号量用户只用到在系统中使一个任务进入就绪态OSEventTaskRdy()和使一个任务进入等待某事件发生状态OSEventTaskWait(

61、)²¢°Ñ¸ÃÈÎÎñÖÃÓÚ¾ÍÐ÷̬¶øºóÕßÓÃÓÚ½«µ±Ç°ÈÎÎñ´Ó¾ÍÐ÷ÈÎÎñ

62、;±íÖÐɾ³ýÔÚºóÃæ½²µ½µÄÓйضÔÐźÅÁ¿µÄ²Ù×÷º¯ÊýÖÐÐźÅÁ¿

63、;Ö÷ÒªÓÉÁ½¸ö²¿·Ö×é³ÉËüÊÇÒ»¸ö16位的无符号整数在使用一个信号量之前也即调用OSSemCreate()函数另外它们之间的关系如图3.3所示ISR中断和信号量之间的关系函数OSSemPend()用于等待一个信号量信号量的计数值大于0函数将信号量的计数值减1ÎÞ´íÈ&

64、#231;¹ûÕâʱÐźÅÁ¿ÎÞЧȻºóµ÷ÓÃOSEventTaskWait()将这个任务进入这个信号量的等待队列中注意即调用的时候中断嵌套数0为´ý¶ÓÁÐËü¼ì²éʼþ¿

65、;ØÖÆ¿éµÄÈÎÎñµÈ¾ÍÒªµ÷ÓÃOSEventTaskRdy()函数上海交通大学硕士学位论文其中的最高优先级任务从等待任务列表中删除并使它进入就绪状态上面是任务调用OSSemPost()的情况不会发生上面的任务切换任务切换要等到中断嵌套的最外层中断服务子程序调用OSIntExit函数后才能进行就是使一个操作系统的内核能在某个微处理器或微控制器上运行大部分的uCOS-II代码是

66、用C语言写的这是因为uCOS-II在读写处理器寄存器时只能通过汇编语言来实现处理器必须满足以下要求l 用C语言就可以打开和关闭中断并且能产生定时中断l 处理器有将堆栈指针和其他CPU寄存器读出和存储到堆栈或内存中的指令l 关中断函数OS_ENTER_CRITICAL()l 开始执行最高优先级任务函数OSStartHighRdy()l 中断返回运行切换函数OSIntCtxSw()开关中断函数可以通过处理器中的开关中断的汇编指令来直接实现可以使用cli和sti这两条汇编指令来实现先取得当前任务的堆栈指针最后调用汇编级的中断返回指令跳出对于OSCtxSw()和OSIntCtxSw()这两个环境切换函

67、数然后切换堆栈指针最后调用汇编级的中断返回指令返回新任务首先保存处理器当前环境具体实现和处理器架构有很大关系最后调用OSIntCtxSw()函数来进行中断返回上海交通大学硕士学位论文3.6 小结本章简要介绍了uCOS-II这个嵌入式实时操作系统任务调度管理方法方法和特点以及处理器移植的上海交通大学硕士学位论文第四章 对操作系统的内核改造小型嵌入式系统通常分为实时或者非实时的两类不但要求任务能完成而非实时系统在这方面的要求相应低一些体现嵌入式操作系统的实时性在很多实时系统中单调执行率调度法给每个任务分配不同的优先级并且各个进程严格按照优先级的顺序运行例如Linux的非实时内核4.1 Linux内

68、核的任务调度算法我们首先分析一下有关操作系统内核的进程调度算法内核进程调度时机主要是有一下几种进程终止¨ 可运行队列中增加一个进程时current->counter=0进程从系统调用返回到用户态时进程返回到用户态时policycounterÓÃ的优先级ÆäÖÐpriority是进程它的大小完全由priority决定¨ À´Çø·ÖÁ½ÖÖ½ø³Ì这是实时进程所特有的首先因

69、为实时进程和普通进程的调度是不同的实时进程应该先于普通进程运行对于同一类型的不同进程对于普通进程选择依据就是进程counter的数字大小优先级priority被赋一个初值就是说进程创建时二者是相等的counter不断减小以便在counter变成的时候对counter重新赋值才用priority对counter重新赋值这说明counter的减小给了其他进程得以运行的机会所以我们称之为动态优先级调度该函数综合了以上的四项上海交通大学硕士学位论文值函数主体如下作为衡量进程是否运行的唯一依据 */switch(p->policy)case SCHED_FIFO:case SCHED_RR: /*

70、 实时进程 */weight = 1000 + p->rt_priority;case SCHED_OTHER:/* 普通进程 */weight = p->counter;if (weight) if (p = prev)weight = weight + 1; /* 做细微的调整 */return weight;/* 返回权值作为进程调度的唯一依据就调度谁运行 */_Linux的调度程序从整体上分成三个部分Linux的调度算法是很简单的为了体现这种区别调度或调度正文暂且称之为进程进程调度正文_Linux/kernel/sched.cp = init_task.next_run;

71、/* 从可运行队列的头部开始遍历 */#define idle_task (&init_task);/* 注意可以在可运行队列中加入新的可运行进程 */int c;c = -1000;next = idle_task;while (p != &init_task)int weight = goodness(p,prev);if (weight > c)c = weight;next = p;p = p->next_run;/* 如果可运行队列中所有进程的时间片都用完了上海交通大学硕士学位论文p->counter = (p->counter >>

72、;1) + p->priority;_这个函数是相当简单的进程重新赋值从中选择一个权值最大的则要给系统中所有进程的时间片_Linux/kernel/sched.casmlinkage void schedule(void)struct task_struct *p;struct task_struct *prev, *next/* prev表示调度之前的当前进程当有中断运行时l 处理内核例程为下一个进程做好准备l 实现进程切换_根据以上伪代码可以看出用于在可运行队列中找出优先级最高的进程而进程调度函数中的其他部分实现进程切换和处理器的寄存器结构这些部分通常用汇编语言来实现在这里先不做讨论

73、4.2 问题的提出可以看出基于Internet的服务进程对相应时间要求不高片轮转调度算法时间片轮转的任务调度算法比较适合于每个普通的服务进程故适合采用时间并以此作为任务调度的依据然而在实时系统中如果一个实时的嵌入式操作系统既要处理某些对于实时任务对于非实时的服务进程因此实时的任务同时由于受到系统的限制要求操作系统的内核都非常的精炼操作系统内核需要进行统一的分配和调度RAM的容量只有32KÒª´óÁ¿Óõ½Ò»¸öNbuf结构用于在协议的各个层次之间传递数

74、据上海交通大学硕士学位论文同由于极为有限的内存资源不可能在系统中随意的分配新的Nbuf结构在系统初始化的时候将它们放在一个空闲队列中会频繁的使用Nbuf结构因此以上两个问题是本文的系统改进中的主要问题主要针对上述的两个问题在这里主要针对涉及进程调度的函数OSSched()和OSIntExit()以及涉及内部存储器缓存Nbuf分配和释放的函数nGet()和nFree()½øÐÐһЩ¾Ö²¿µÄÐÞ¸ÄÖ&

75、#247;ÒªÓÐÒÔϼ¸¸ö½ø³Ìµ÷¶Èʱ»ú½ø³ÌÖÕÖ¹¨ 可运行队列中增加一个进程时由中断返回时系统通过调用函数OSSched()实现进程调度系统通过调用函数OSIntExit()实现进程调度在这里¨¨ 取出8个优先权为Inter

76、net服务进程专用TCB控制块中增加一项counter作为任务调度的权值时钟中断处理函数中于Internet服务进程专用的任务如果该任务属¨ 在这里定义OS_PRIO_INTERNET为3ÔÚÕâ8个进程之间如果就绪队列中有优先级比这8个进程高的任务如果当前就绪队列中优先级最高的进程在第4组中将时间片最大的任务取出放到CPU上运行改造后的OSSched()和OSIntExit()函数代码大约增加几十行_改造后的OSSched()/* OSRdyTbl3的8个进程为Internet专用 */#define OS_PRIO_INTERNET3#de

77、fine OS_COUNTER20void OSSched (void)上海交通大学硕士学位论文INT8U x,y,z;INT8U c; /* 衡量Internet进程的权值 */OS_ENTER_CRITICAL();if (OSLockNesting | OSIntNesting) = 0)y = OSUnMapTblOSRdyGrp;x = OSUnMapTblOSRdyTbly;if (y != OS_PRIO_INTERNET)OSPrioHighRdy = (INT8U)(y<<3) + x);else c = 0;z = OSRdyTbly;while (z)if (OSTCBPrioTbl(INT