下载
加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 VxWorks SMP内核调度、信号量和中断机制的设计与实现

VxWorks SMP内核调度、信号量和中断机制的设计与实现.doc

VxWorks SMP内核调度、信号量和中断机制的设计与实现

屲裡旳孩孓13
2017-11-30 0人阅读 举报 0 0 暂无简介

简介:本文档为《VxWorks SMP内核调度、信号量和中断机制的设计与实现doc》,可适用于生产运营领域

VxWorksSMP内核调度、信号量和中断机制的设计与实现国防科学技术大学硕士学位论文VxWorksSMP内核调度、信号量和中断机制的设计与实现姓名:任强申请学位级别:硕士专业:计算机技术指导教师:吴家铸国防科学技术大学研究牛院:稃硕十学位论文摘要随着集成电路工艺的不断进步以及处理器体系结构的发展,同构多核处理器在嵌入式领域中得到了广泛的应用。但是,与硬件的飞速发展相比,同构多核处理器的基础软件特别是嵌入式操作系统研究却比较落后。同构多核处理器的嵌入式操作系统的开发难度大,不发效率低。本文首先对对称多处理架构进行分析,剖析了架构与架构的区别,并对架构的先进技术做了简要说明。详细分析了系统,为系统的设计提供了参考。深入分析了内核的运行机制,主要是对内核的整体结构、任务调度模块、信号量模块、中断管理模块进行了详细分析,明确了模块之间的调用关系,为后面的多核化设计打好基础。本文在对各个模块设计过程中面临的关键问题进行分析的基础上,针对架构特点,提出了支持架构的内核机制的设计方案,给出了合理的解决思路。在任务调度方面,提出了基于全局队列的任务分配算法,该算法较好实现了任务调度,调度开销跟就绪任务个数无关,在系统负载重的情况下也能平滑工作,提高了实时性和可预测性在同步互斥机制方面,提出了自旋锁机制来实现新的信号量机制,该机制较好的实现了的同步与互斥,解决了死锁等问题,使内核的同步互斥更加简单高效在中断管理方面,提出了中断动态路由算法,该算法允许多个核同时处理不同的中断请求,相对于单核系统,减少了中断延时,提高了系统的响应性。本文在模拟器测试平台上验证了基于全局队列的调度算法、自旋锁、中断算法功能的正确性,并与单核版本的内核机制运行效果做了对比,得到了满意的结果。基于架构的调度、信号量、中断机制的设计及其初步实现,对当前嵌入式操作系统支持多核技术的发展具有一定的现实意义和理论意义。主题词:,,调度,信号量,中断第页同防科学技术人学研究生院科硕十学倚论文,,,,,,,,,,,,,,,,,,,,,,,:,,,,第页国防科学技术大学研究牛院一:稃硕十学位论文表目录表任务状态说明表能够被调用的函数第页国防科学技术人学研究生院样硕十学位论文图目录图经典的多核处理器结构图典型双处理器的结构图图工作原理图工作原理图的任务就绪队列图的任务就绪队列图使用锁来防止优先级反转图系统中的中断分发示意图图内核总体处理流程图图内核核心函数及其封装的关系图任务的状态转换图基于优先级的任务抢占图指令所处的层次图微内核的抢占过程图优先级被反转图优先级被反转图局部调度带来的多次任务切换图查找未分配处理器核的线程图模块的选取过程图获取信号量的流程图释放信号量的流程图等待信号量的任务队列图中断服务程序的连接图中断请求与处理器核绑定策略造成中断延时过大图中断动念路由算法图多核系统中断控制器的框图图实现中断动态路由算法的中断处理过程图任务调度算法初始化测试图任务调度算法有效性测试图任务调度算法正确性测试图改造前系统信号量机制测试图改造后系统信号量机制测试第页国防科学技术大学研究生院一:样硕十学何论文图算法运:半均时、日的比较图算法运行值的比较第页独创性声明本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研究成果尽我所知,除了文中特别加以标注和致谢的地方外,论文中不包含其他人已经发表和撰写过的研究成果,也不包含为获得国防科学技术大学或其它教育机构的学位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意学位论文题目:兰三鳖墨墨壁凼趑凋廑:焦曼量垄生断扭剑数遮让生塞理日期:学位论文作者签名:每龌,年月吕日学位论文版权使用授权书本人完全了解国防科学技术大学有关保留,使用学位论文的规定本人授权国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档。允许论文被查阅和借阅可以将学位论文的全部或部分内容编入有关数据库进行检索,可以采用影印缩印或扫描等复制手段保存,汇编学位论文保密学位论文在解密后适用本授权书学位论文题目:兰坠垒璺螋应挞通廑:焦曼量塑主匦扭剑数遮进复塞理日期:。年伦月了日日期:。年月日国防科学技术人学研究生院科硕十学位论文第一章弟一早绪论三百匕课题研究的背景近几年,国内自主知识产权的处理器得到了迅速的发展,比如年,清华大学自主研发了位微处理器芯片年位龙芯增强型处理器芯片通过科技部验收。但是,这些处理器并没有得到广泛的应用。主要的一个制约因素是在各个应用领域,这些处理器都没有得到相应的成熟操作系统的支持。在嵌入式应用领域,国内自主产权处理器就缺乏优秀的嵌入式操作系统如的支持。嵌入式操作系统是一种支持嵌入式系统应用的操作系统软件。它是嵌入式系统包括硬、软件系统极为重要的组成部分,通常包括与硬件相关的底层驱动软件、系统内核、设备驱动接口、通信协议、图形界面、标准化浏览器等。嵌入式操作系统具有通用操作系统的基本特点,如能够有效管理越来越复杂的系统资源能够把硬件虚拟化,使得开发人员从繁忙的驱动程序移植和维护中解脱出来能够提供库函数、标准设备驱动程序以及工具集等。与通用操作系统相比较,嵌入式操作系统在系统实时高效性、硬件的相关依赖性、软件固态化以及应用的专用性等方面具有较为突出的特点【】。操作系统是美国公司于年设计开发的一种嵌入式实时操作系统,,是嵌入式开发环境的关键组成部分。良好的持续发展能力、高性能的内核以及友好的用户开发环境和软件支持,使其在嵌入式实时操作系统领域占据一席之地。它因良好的可靠性和卓越的实时性被广泛地应用在通信、军事、航空、航天等高精尖技术及实时性要求极高的领域中,如卫星通讯、军事演习、弹道制导、飞机导航等【】。随着现代应用对计算机性能要求的不断提高,单核处理器性能的提升已经满足不了需求。对于单核处理器来说,提高性能的主要途径便是优化逻辑结构、扩大缓存以及提高芯片频率。但芯片的逻辑架构一般有、年的生命周期,一旦设计稳定就很难从根本上对其做出改变,这样扩大缓存容量和提高频率就成为单核处理器提升性能的主要手段。提高缓存容量虽然能够小幅的提高性能,但付出的代价相当高:处理器的缓存都是使用静态随机存储器件,速度极快、可晶体管利用率很低,容量缓存就与要消耗万左右的晶体管我们可以看到,无论在、还是处理器中,二级缓存占据的芯片面积普遍超过,如果不断提升缓存容量,无疑将对芯片的制造成本与芯片面积三次方成正比带来严重的影响。与之类似,提高工作频率能够一定程度上提高芯片的性能,但会导致运行功耗大增,现在芯片运行在风冷条件之下已经第页国防科学技术大学石究牛院:稃硕十学位论文接近极限【。的出现就很好的解决了硬件系统性能提升的瓶颈问题。所谓就是紧耦合共享内存对称式多处理器,在系统中,由一种操作系统控制所有处理器,该操作系统可协调每个相似的处理器上同时发生的活动。由于这些紧耦合处理器所访问的是一个公共内存区,所以它们必须通过一种基于低延时共享内存的通信机制来实现相互之的同步。那么基于单核版本的能不能对,尤其是调度机制方面提供高效的管理机制呢,答案是否定的【】。改变了传统的单机版多任务、基于优先权的编程模式,这体现在允许多个线程被并行执行,而这是建立在单个操作系统运行于拥有多个核的处理器,或运行于多个处理器相互连接成为拥有多个处理单元的逻辑处理器背景上的。我们常说在某个非的多任务环境中,多个线程可以“同时运行”,可实际上处理器一次只能执行一个线程处理器依靠操作系统任务调度器以及中断机制来运行不同的线程。由于这一差异,除非在代码的设计和执行即将系统作为立足点,否则从传统的多任务系统向系统转移代码是行不通的。正因为单核版本的不能应用于的硬件平台上,所以我们要对内核的各个模块进行重新设计,本文着重对版本的内核机制进行分析,在此基础上对如何支持进行了设计。国内外研究现状在多核处理器如火如荼地发展,硬件制造商不断推出新产品之际,相应的操作系统和应用程序开发却已经滞后。多核处理器的优势只有在软件能够充分利用其特性时,才能体现出来。桌面系统业界各大主要操作系统厂商已经推出相应的操作系统,例如、和发行版,以及。其中有些操作系统还将包括支持专门应公司的用的优化程序,以充分发挥多核的优势,从而改善一系列应用的性能。在嵌入式操作系统方面,多核处理器的应用相对缓慢,其中支持多核处理器的嵌入式实时操作系统主要有公司的、软件系统有限公司的、以及由发展而来的等少数操作系统。硬件平台的发展对嵌入式实时操作系统提出了新的挑战,因此,对于支持架构的嵌入式操作系统的研究也成为当今的热点。文献【研究了架构下的任务调度问题。它重点强调在多处理器片上系统中,的利用对于系统性能的提高和降低功耗具有重要意义。它假设将一个循环拆成多个线程,然后计算拆分后的线程的共享程度,将有共享数据的线程先后调度在同一个核上,而将不共享数据的线程调度到不同的核。此方法不仅充分利用了的第页国防科学技术入学研究生院科硕十学位论文性能,而且利,了多核的并二计算能力。在系统性能方面,文献提出,二级缓存的不命中要比一级缓存不命中和流水线的冲突造成更大的影响。它指出,通过合理的调度来减少线程对二级缓存的访问,可以提高系统的吞吐量。在降低功耗方面,文献【】提出了一个结构一个极端细粒度的线程结构,通过在编译时显示地标记方式来实现并行执行。它认为某些程序利用在顺序执行的处理器上执行比程序直接在乱序执行的处理器上执行消耗更少的能耗。等人提出了一个调度算法,此算法通过调节多个处理器核的频率和电压方法,达到同时满足时间和能耗的要求的目的。文献【讨论了在任务时间约束的情况下如何降低系统的功耗,提出了两个新颖的实时循环调度算法和。为了能更好的支持硬件平台的应用,各大嵌入式操作系统厂商都分别推出了支持硬件平台的操作系统,并对其进行了有针对性的升级,尤其是在调度算法和同步机制的改进方面比较大。目前支持的操作系统中,的技术比较成熟。年来自美国嵌入式操作系统开发联盟的提出了基于总线锁的多核调度算法,该算法解决了系统和系统中总线抢占的问题,也对以后多核操作系统中的信号量机制的研究起到了重要的推动作用【叭。中国航空计算技术研究所在年提出了一种基于实时性考虑的对称多处理机任务调度策略的设计,这也填补了国内对于在嵌入式领域应用创新的空白。这也为以后的我国近几年载人航天工程中的嵌入式操作系统的改造和个性化提供了理论基础。本课题组年提出的针对子任务排队问题的调度算法以及中断分配策略算法【】也为架构下的优化提供了有效的途径。本文主要工作任何一个采用模式进行多核化改造的操作系统,它的实现都必须解决以下三个主要问题:系统完整性、性能和外部编程模型】。系统完整性意味着正确协调好处理器核间的并行活动,从而避免危害到内核的数据结构。在保证系统完整性的基础上,系统应尽可能地获得最大的性能。外部编程模型决定了系统调用接口对应用程序的影响。如果系统调用接口与原操作系统的系统调用接口不一致,那么许多为原操作系统编写的应用程序就得改写。因为重新编写程序的代价很高,所以大多数支持的操作系统的实现都选择了保持原有的接口不变的实现策略。由于第页国防科学技术人学研究生院‘:程硕十学位论文是一个实时操作系统,凶此多核化的设计还必须考虑实寸性和叮预测性。为此本文深入研究了操作系统的内核源代码。以模块为单位对内核源代码进行分析。通过对每个模块的修改历史、所使用数据结构、主要函数流程、函数接口进行详细分析,明确了模块之间的调用关系【。详细的描述内核的工作流程和运转机制在此基础上,对内核部分模块进行了设计和修改以支持设计完毕后,编译操作系统境像文件在本课题所基于的硬件平台上进行测试验证。在实现对的支持过程中,本文主要做了以下工作:、在任务调度管理机制方面,本文提出并实现了基于全局队列的任务分配算法。、在内核的同步互斥机制方面,本文提出并实现了基于两种自旋锁的信号量机制。、在中断管理方面,本文提出并实现了了中断动态路由算法。在外部编程模型方面,本文选择了保持原有的接口不变的实现策略,尽可能地兼容原有应用程序。最后,本文在一个基于开发的同构多核处理器的模拟器上对系统的下确性和性能进行了测试验证。论文结构全文共分为六章,各章内容如下:第一章绪论对嵌入式操作系统和做概要性介绍,并对的发展做了详细介绍。在此基础上,引出了本文研究的目的、内容和要求,说明了研究背景。第二章对称多处理技术综述介绍了与本文设计研究内容相关的一些技术背景内容,包括架构的需求背景和关键技术,以及架构与的比较介绍。此外,本章也分析了系统实现原理,为后续对的研究与实现做铺挚。最后对架构的先进技术进行概述。第三章内核调度与信号量机制设计深入分析了内核的调度机制和信号量机制。明确提出了在架构下内核的调度机制和信号量机制所面临的问题,并根据需要对内核调度机制和信号量机制进行设计,最后给出内核调度机制和信号量机制的代码实现。第四章内核中断机制设计笫页国防科学技术人学研究生院门卑硕学位论文深入分析了内核的中断机制。明确提出了在架构卜内核的中断管理机制所面临的问题,并根据需要对内核中断管理机制进行设计,最后给出内核中断管理机制的代码实现。第五章测试验证在指令模拟器上测试了基于全局队列的调度算法、自旋锁、中断动态路由算法功能的正确性,并与单核版本的内核机制运行效果做了对比。第六章结束语对本文研究的内容进行总结,并对需要继续开展的工作进行了陈述。第页国防科学技术大学研究牛院:科硕十学位论文第二章对称多处理技术综述在设计系统之前,我们首先要对“对称多处理技术”进行深入研究。搞清对称多处理架构的设计原理,并结合非对称多处理器架构找出其设计特点,这是后面针对架构进行设计与实现的前提条件。并且,对其他实现架构比较成熟的嵌入式操作系统如的设计原理进行分析,为后面针对此架构进行设计与实现提供了思路。对称多处理架构概述摩尔定律【】是指在单个硅芯片中集成的晶体管数目每至个月大约翻一番。几十年来,处理器生产厂商一直在提高时钟频率这条跑道上竞争,各行业对计算能力的需求推动了处理器计算能力的提高,而摩尔定律在过去数十年罩展现出惊人的准确性。然而,最近几年来处理器的功耗和节能问题愈来愈成为人们关注的焦点。仅靠提高主频来改进处理器性能的做法遇到了瓶颈,因为主频的提高导致处理器的功耗和发热量剧增,反过来制约了处理器性能的进一步提高。于是,人们开始把研究重点转向将多个执行内核集成到单个芯片上,通过任务在处理器核上并行运行的方式来提高,从而提高性能。一直以来,人们通过各项手段来提高系统的并行处理能力,以此达到提高整体性能的目的。年,为了提高线程的并行能力,单芯片多处理器体系结构被提出【,也就是平时所说的多核技术。所谓,是指在一个芯片上集成多个微处理器核从实质上说,每个微处理器核都是一个相对简单的单线程微处理器,而且这多个核之间联系非常紧密,甚至共享一级缓存或二级缓存,核间通过高速总线连接在一起,如图所示。如果中的多个微处理器核是同构的,则可以看作是的一种实现形式。在此之前,为了提高计算机的并行处理能力,文献【中首次提出了对称多处理结构,。卿蛹政‘、‘斗。。图经典的多核处理器结构第页同防科学技术人学研究乍院:稗硕十学何论文“对称多处理”是指在一个计算机上汇集了一组处理器多处理器,各处理器之间共享内存子系统以及总线结构。它是相对非对称多处理技术而言的、应用十分广泛的并行技术。在这种架构中,一台电脑不再由单个处理器组成,而同时由多个处理器运行一种操作系统,并共享内存和计算机的其他资源。虽然同时使用多个处理器,但是从管理的角度来看,它们的表现就像一台单机一样。系统将任务队列对称地分布于多个处理器之上,从而极大地提高了整个系统的数据处理能力。所有的处理器都可以平等地访问内存、和外部中断。在对称多处理系统中,系统资源被系统中所有处理器共享,工作负载能够均匀地分配到所有可用处理器之上。本文的目标测试平台指令模拟器就是同构多核结构的。图就是一个典型的双处理器的结构。囝申申图典型双处理器的结构图对称多处理与非对称多处理的区别目『,支持多核体系的操作系统模式主要有两种:对称多处理,模式和非对称多处理,模式。这两种方式在操作系统的占有,程序和数据区的分配等方面有很大的不同。系统是实现各处理器对存储器和所有设备的共享各需实现操作系统内的重要协作,以防止对共享资源的并行存取。在配置中,各操作系统大多会对硬件资源进行划分,以便合作仅限于使用共享存储器的情况。由于合作程度不同,系统有时被称作“紧耦合多处理’’系统,而则被称为“松耦合多处理”系统。第页围防科学技术大学研究生院科硕十学位论文:潆弓执行缕执仃操作系统、、刀瞳执::垂’:植谴,执行:谴写执打卜谴写执打:谗譬执、‖卜:罅扭谴’、执完全共享内存图作原理假设我们的处理器采用的是操作系统。在如图所示在配置中,各处理器共享整个物理存储器空间。该存储器被用来存储单一镜像该存储器亦被用来存储在系统运行过程中创建的实时进程或称用户任务。由于系统的两个处理器都有可能读出、写入或执行任何存储单元,两个处理器中的任一个都能执行各项内核任务或用户任务所属任务。卜墟写,执打:、读写,执行卜、读写执、:读写,执行卜:读写部分共享内存读写‖图上作原理而在如图在配置中,每个处理器存储有一份操作系统镜像,且该镜像只能被拥有它的处理器存取。由于这一点,不可能执行存储器内的内核任务,反之亦然。相同的情况亦适用于用户任务例如,当创建某个用户任务时,该用户任务只能被创建它的操作系统读取和执行。在配置中,存储器会被部分共享这种共享通常仅限于数据读出和写入,这与在两个操作系统间进行信息传递的情况相同。实现原理从版本开始增加对于的支持,最初的实现较为简单,以后随着版本更新,的实现也逐步趋于完善。支持的的逐步完善过程中所积累的经验及成果,无论在理论上还是实践上,都为本文的研究工作提供了很好的借鉴作用。因此,深入分析系统的实现原理,对后续的研究与实现能够提供理论支持和实践依据。第页国防科。字:技术人学彬究生院稃硕十学位论文以,的内核,是在用户级实现,内核本身并能凶有多个处理器核而得到加速。而在内核以后,在内核级实现,使用多处理器核可以加快内核的处理速度。目前的有以下优点:采用时间复杂度为的调度算法【,调度器开销恒定,与当前系统负载无关,实时性能更好锁粒度大幅度减小优化了计算密集型的批处理作业的调度系统负载重的情况下,调度器也能发挥良好的性能。这些使得系统性能和实时性都有了很大的改善。下面将对支持的关键模块及技术进行分析。调度机制的调度机制的特点主要有两个:内核不可抢占以及调度算法简单高效。在中,内核是不可抢占的,即进程在内核态执行时,它不能被任意挂起,也不能被另一个进程代替,除非进程自己放弃处理器。一个最典型的例子就是内核进程中如果出现死循环并且进程不调用进行任务切换,系统就会失去响应。此时尽管各种中断包括时钟中断仍然在响应,但却不会发生调度,其他进程包括内核进程都没有机会运行。操作系统内核中负责进程调度的具体函数是,它按照不同的调度策略对实时进程和非实时进程进行不同的调度处理。它主要完成两项工作:遍历就绪队列中的所有进程,调用函数计算每一个进程的权值,从中选择权值最大的进程投入运行。如果整个运行队列中的所有进程的时问片都耗尽,重新分配时间片。的进程用结构体表示。如图所示,系统中的所有进程被组织到以初始化任务为表头的双向链表中,该链表是全系统唯一的,每个处理器核都分别对应了一个,它们的指针被组织到宏访问这些数组中,调度器通过也在其中,但除外,调度器总是从中选取最适合调度的进程投入运行。图的任务就绪队列由于所有处理器核共享一个运行队列,需要使用一个运行队列锁来保证互斥访问,因此,在系统中,一个核处理器从运行队列选择任务就会阻止其他第页为表头的链表记录了所有处于就绪态的进程当前正在运行的进程进程。以国防科学技术人学研究生院‘科硕十学何论文核操作这个队列。结果足,空闲处理器核需要等待这个处理器核释放运行队列锁,这样会造成效率的降低。在的基础上做出了很大的改进,它能够更好地发挥的性能。首先,它改变了中多个处理器核共享一个运行队列的做法,而是每个处理器核都有自己的运行队列,这样就允许同一时刻多个处理器核进行任务调度,而且系统根据所有处理器核的负载进行负载平衡。负载平衡程序由函数实现,只要当前的就绪队列为空,它就会被调用,此外,在系统空闲时每隔毫秒调用一次,而其他情况下每隔毫秒调用一次,以便重新分配任务负载,维持核间的负载平衡。但是由于负载平衡程序的执行开销较大,而且执行时间具有不确定性,所以一定程度上影响了的实时性和可预测性。其次,内核使用了新的调度算法,其时间复杂度为。新调度器在高负载的情况下执行得非常出色,并在有多个处理器核时能够很好地扩展。在的调度器中,时间片重算算法【】要求在所有的进程都用尽它们的时间片后,新的时间片才会被重新计算和分配。这样就造成一些弊端:可能会耗费相当长的时间。最坏情况下,在有个进程的系统中,其时间复杂度可能达到由于在重算过程中要对任务队锁来保证互斥访问,因此加剧了对锁的竞争,影响的效率时问片重算的时机是不确定的。这影响了系统的实时性。此外,当空闲处理器核开始执行那些时问片尚未用尽的、处于等待状态的进程时,有可能导致进程在处理器之间“跳跃。当一个高优先级进程或交互式进程发生跳跃时,整个系统的性能就会受到影响。新调度器解决上述问题的方法是,基于每个处理器核来分布时间片,并取消全局同步和重算循环。新调度器让每个核维护两个优先级数组,即活动数组和过期数组。活动数组中包含所有映射到当前核且时间片尚未用尽的任务,过期数组中包含时间片已经用尽的所有任务的有序列表。当一个任务用完自己的时间片后,就会被重新计算并赋予新的时间片,然后从活动数组中删除,插入到过期数组中。如果所有活动任务的时间片都已用尽,那么指向这两个数组的指针互换,包含时间片用尽的任务的过期数组成为活动数组,而已变为空的活动数组就成为新的过期数组。为了使调度效率更高,内核使用了一个位图来辅助查找运行队列中优先级最高的进程,对它支持的每一种体系结构都提供了对应的快速查找算法,以保证对位图的快速查找。提供该功能的函数叫,它会在个位的字个优先级中查找哪一位的优先级最高。查找时间并不依赖于活动任务的个数,而是依赖于优先级的数量。第页国防科学技术人学研究生院‘:程硕十学位论文的滔功效组躺过绛救组寅时经务的优先缀翊户任务魄优先缀厂图的任务就绪队列信号量机制读写锁众所周知,为了保护共享数据,需要一些同步互斥机制,如读写锁。读写锁的引入是为了增加内核的并发能力。只要没有内核控制路径对数据结构进行修改,读写锁就允许多个内核控制路径同时读取同一个数据结构。如果一个内核控制路径想对这结构进行写操作,那么它必须获得读写锁的写锁,写锁授权独占访问这个资源。它使用起来非常简单,而且是一种很有效的同步机制,在系统和系统中得到广泛的使用。但是,随着计算机硬件的快速发展,获得这种锁的开销相对于处理器的速度在成倍地增加。原因很简单,处理器的速度与访问内存的速度差距越来越大,而这种锁使用了原子操作指令,它需要原子地访问内存,也就说获得锁的开销与访存速度相关。另外,在大部分非架构上获取锁使用了内存栅,这会导致处理器流水线停滞或刷新,因此它的开销相对于处理器速度而言就更大。读拷贝更新内核引进了新的锁机制。顾名思义,就是读一拷贝更新。允许多个读者和写者并发执行,对于被保护的共享数据结构,读者不需要获得任何锁就可以访问它,但写者在访问它时首先拷贝一个副本,然后对副本进行修改,最后使用一个回调机制在适当的时机把指向原来数据的指针重新指向新的被修改的数据。这个时机就是所有引用该数据的处理器核都退出对共享数据的操作。并没有使用锁,也就是它不使用被所有处理器核共享的锁或者计数器,这与读写锁有很大区别,所以死锁问题就不需要考虑了。尽管相对于读写锁具有更大的优势,但是这个优势是基于以下两个限制第页国防科学技术大学研究生院:稃硕十学何论文的:首先,只保护被动态分配并通过指针引川的数抛结构其次,在被保护的临界区中,任何内核控制路径都不能休眠。这也就要求读者在被切换出处理器核以及开始到用户态执行之前要执行放弃对共享数据结构的引用。对于,由于读者几乎不做任何事情来防止竞争条件的出现,所以写者的同步不销比较大,它需要延迟数据结构的释放,复制被修改的数据结构,它也必须使用某种锁机制同步与其并行的其它写者的修改操作。读者通过调用释放或修改的时机。有一个专门的垃圾收集器来探测读者的信号,一旦所有的读者都已经发送信号告知它们都不再使用被保护的数据结构,垃圾收集器就调用回调函数完成最后的数据释放或修改操作。与的不同之处是:它既允许多个读者同时访问被保护的数据,又允许多个读者和多个写者同时访问被保护的数据注意:是否可以有多个写者并行访问取决于写者之间使用的同步机制。读者没有任何同步不销,而写者的同步不销则取决于使用的写者间同步机制。但不能替代,因为如果写者比较多时,对读者的性能提高不能弥补写者导致的损失。在应用方面,这种锁机制的使用范围比较窄,只适用于读多写少的情况,主要应用在网络层和虚拟文件系统中,如网络路由表的查询更新、设备状态表的维护、数据结构的延迟释放以及设备的维护等。锁过去的版一般都采用比较单纯的读写锁来实现临界区机制,然而读写锁是没有优先级继承功能的,这样就有可能发生优先级反转现象:如图,任务优先级为:,任务发出系统调用,访问临界区时,任务也发出了访问要求。这时任务只能等待。此时如果优先级比高的任务进入就绪状态,则就抢占,而此时由于迎执行比任务优先级低的任务,任务需要等待更长的时间,响应延时也就加大。为了缩短延时时间,软件公司用锁替换了读写锁,从而实现了优先级继承功能。如图,对于任务正访问的临界区,如果优先级较高的任务想要访问,功能将把任务的优先级提高至与任务相同。由此避免因任务的抢占而发生的优先级反转现象,同时减少任务的响应延时而且在挂起任务的这段时间,可以去运行其他任务,这也提高了运行效率。第页函数提供一个信号给写者以便写者能够确定数据可以被安全地同防科学技术人学,删二院『科硕。学位论文”,“‘’”一‖呷一:峥嗍牌。强一篇黜。创使锁米防忧先绒反转中断机制传统的单核处理器都采用中断控制器。一般向言,的作用是提供多个外部中断源与单一处理器之问的连接。如果结构『还是采用中断控制器那就只能静态地把所有的外部中断源划分成苦干组,分别把每一组都连接到一个,而则与处理器核有一对一勺连接。然而,这样就达不到动态地分配中断请求的目的。因此,为处理器设训了一种更为通用的中断控制器,称为“高级可编程中断控制器”缩写成。另一方面,考虑到核问中断请求的需要,每个处理器核实际卜都需要有个自己的,因为一个核常常要有目标地向系统中的其他核发出中断请求。所以,就在每个核内部集成了一个本地,成为简称。但是,在上,主板上有一个至少一个,有的主板有多个,用来更好地分发中断信号全局的,它负责接收外设的中断信号,再分发到处理器拨上,这个全局的被称作,如图所乐。幽系统中的中断分发示意图最大的作用在于中断分发它根据其内部的第页国防科学技术人学研究生院一:稃硕十学何论文表,格式化出‘条中断消息,发送剑某个或多个处理器核的上,再由通知处理器核进行处理。目前典型的具有个中断管脚,每个管脚对应一个,表项。与普不同的是,的管脚没有优先通的级,也就是说,连接在管脚上的设备是平等的。但这并不意味着多系统中没有硬件优先级。设备的中断优先级由它对应的中断向量决定的,将优先级控制的功能放到中。当某个管脚接收到中断信号后,会根据该管脚对应的,格式化出一条中断消息,发送给某个或多个处理器核的。支持多种中断分发策略。可以通过对中字段进行设置,实现某个中断请求由固定的单个或多个处理器核进行处理。或者使用优先级策略,每个处理器核都有自己的优先级,会把中断请求分发到优先级最低的处理器核上。用户可以通过对进行编程从而实现策略的选择以及一些特殊的需求。在系统上,除了处理处理器核异常、外部设备中断之外,还要处理核间中断。当一个处理器核想对另一个处理器核发送中断信号时,就在自己的的寄存器,中断命令寄存器中存放其中断向量和目标核拥有的的标识,触发中断。核间中断信号经由总线传递到目标,目标就向自己所属的核发送一个中断。架构先进技术概述对多线程程序能够提供较高的性能,但是对于单线程应用的性能反而不高。采用硬件动态提取线程是一种办法,但编译器要担负起自动并行化的工作,即将串行程序自动的转换为等价的多线程并行代码,使用户不担心迭代空间划分、数据共享、线程调度和同步等细节。更重要的是多线程优化编译技术包括线程并发机制的实现、线程调度、线程级前瞻执行等技术,多核之间的任务调度是充分利用多处理器性能的关键。为满足实时处理的要求,均衡各处理器负载,需要研究的任务调度机制有分布式实时任务调度算法,动态任务迁移技术等。分布式实时任务调度算法近年来,单芯片多核心处理器,体系结构的研究已逐渐成熟,在一些并行系统中已开始采用多核处理器,例如最新的高性能集群服务器就是采用了多核处理器的一种并行系统。在单芯片多核心系统中,用户任务数一般都多于处理器数、这将导致它们互相争夺处理器。另外,系统任务也同样需要使用处理器。这就要求任务调度程序按一定的策略,动态地把处理器分配给第页国防科学技术人学研究生院科硕十学位论文处十就绪队列叶的某一个任务,以使之执行。其设计策略也严格遵照分御式的原则。尽管目前对单芯片多核心处理器上的分布式实时任务调度技术开展了一些研究,然而并没有明确的针对单芯片多核心系统中实时任务调度的标准和规范。基于单芯片多核心处理器系统的分布式实时任务调度技术还是一个不成熟的领域,还需要我们不断的研究和探索。动态任务迁移技术动态任务迁移技术是单芯片多核心系统调度机制研究的一个热点,指的是任务在多核环境下的重定位,主要用于解决在特殊环境下某个运算核心失效的问题。多核系统通过动态任务迁移技术可以极大的提高系统的容错能力与可靠性。与分布式实时任务调度技术一样,动态任务迁移技术的研究同样也很不完备,有很广阔的研究前景。本章小结本章介绍了与本文设计研究内容相关的一些技术背景内容,包括架构的需求背景和关键技术,以及架构与的比较介绍。此外,本章也分析了系统实现原理,包括任务的调度和同步机制以及中断机制。对实现原理的分析为后续的研究与实现提供了重要的参考。最后对架构的先进技术进行概述。第页国防科学技术人学研究生院。程硕学位论文内核调度与信号量机制设计第三章在对实时操作系统内核机制进行多核化设计与实现之前,我们必须对的整体结构及本文需要设计的模块进行深入的分析。深入分析及理解的实现原理是多核化研究与实现得以顺利进行的前提条件,这也为的多核化设计作理论上的准备。因此,本章将对的体系结构进行剖析,深入分析内核的结构和任务调度以及信号量模块。并根据其实现原理对内核调度模块以及信号量模块进行多核化的设计与实现。内核结构内核是其运行环境的核心,包括多任务内核、任务抢占调度、任务间通信和中断处理机制等,整个内核的运转流程任务视角如图所示。在系统不始的时候,由任务管理模块创建了一些任务,然后调度模块负责调度任务到处理器上,任务不始执行。任务执行时,可能直接执行完毕,退出也可能访问和处理资源,之后可能继续执行,也可能被阻塞,进而引起任务调度模块重新调度任务执行任务可能通过任务管理模块创建或销毁任务也可能有外部中断和时钟中断发生,导致任务调度模块重新进行调度同时,任务也可能处理或产生中断和异常。图内核总体处理流程图实时性强是操作系统非常突出的一个特点。为了提高系统的实时性,大多数操作系统都提供了各种机制,如可抢占的内核、中断的后半段处理等。第页刊坊科学技术大学研究牛院:群硕十学何论文为了提岛实时性,构造成了一个带自‘微内核的层次结构。在计算机的早期,操作系统大部分是一个统一的实体。在这样的系统中,提供不同功能的模块是独立考虑的,如处理器管理、内存管理、文件管理等,较少考虑模块间的关系。这样的操作系统结构清晰,构造简单,但是由于操作系统本身很复杂,在这种大粒度的操作系统中难以划分可抢占部分和不可抢占部分的边界,难以避免有冗余的操作在操作系统的不可抢占部分中执行,造成系统的实时性比较差,不适合实时应用环境。而带有微内核的层次结构的操作系统则较好的解决了这个问题。在这样的操作系统中,以内核作为层次结构的起点,每一层功能对较低层进行封装。内核仅需要包含最重要的操作指令,提供高层软件与下层硬件的抽象层,形成操作系统其它部分所需的最小操作集。这样就可以比较容易的精确确定可抢占部分与不可抢占部分的边界,减少了需要在内核不可抢占部分执行的操作,有利于实现更快的内核抢占,提高系统的实时性。的内核就是这样的一个有利于构造层次结构的微内核,它由、、、、、、、、等库组成的。库有底层的最基本、最核心的函数,也有在最基本最核心函数上进行封装给应用程序提供的调用。内核中主要函数及其封装的关系如图所示。图中箭头表示封装和调用关系。在这样的内核中,容易实现很强的实时性而对内核高层次的封装则使得用户在开发的应用程序时,只需要调用顶层的函数,不必关心底层的实现,程序设计也很方便。。上上事、。“““。艘、、~斛、一纠一赢蕊一:图内核核心函数及其封装的关系任务调度机制设计第页防科学拄术人学研究生院栏硕十学位论文任务状态的转换和上下文切换,、目雠、一一嚏“,圈任务的状态转换在任务的整个,存周期,任务的状态小断的转换,如图所示。各种状态的含义见表所示四。表任务状态说明状态说明执打任务“宵处理器资撑运行,可“看作种特殊的就绪志。就绪任并仅等待处理器资源阻塞任务田等待独一资源而不能被阑度运行唾眠处睡眠状态捧起任务刚刚创建戚是罔为调试的原因被择起既处睡眠义被丰起的状态既处阻塞义被拌起的状态带超时的阻塞状卷十带超时,义处阻塞,同时被挂起的状态在状态转换图中,箭头表示任务被创建,进入状态。箭头袤示任务被或辙活,进入就绪态。箭头表示任务因为调试蟓凶被挂起。箭头表示在执行些代码以后,去获取独占资源并且独占资源已经被其它任务占用,任务转向了阻塞态,比如会触发这个状态转换。在占用独占资源的任务释放独占资源后,任务可能获符了该资源,就会从阻塞态转换到就绪卷,如箭头所示。箭头标识了一个从就绪忐到睡眠悉的转换,如会触发这种变化。箭头说明任务从睡眠态转到了就绪态出现这种状态转换的原倒是睡眠时问到或者调用了晒数。箭头表示了一个从阻塞忐转换到挂起态的变化箭头表示了从睡眠态到挂起志的转换,第页囝防科学技术人学研究生院:释硕十学位论文这两种转换和箭头的转换一样,鄙是任务凶为调试原凶被挂起。箭头和箭头表示任务被解除了挂起。每当任务从就绪念转换到执行态,就会发生上下文切换。所谓上下文切换,是指改变的上下文信息。的上下文信息包括、、通用寄存器等。上下文进行切换时,主要完成两项工作:第一,将目前执行任务的上下文保存进任务的第二,将新的任务的上下文从任务的移到的相应寄存器中。上下文切换有同步切换和异步切换两种。同步上下文切换的原因是在任务执行过程中发生的,如任务阻塞、延时、挂起等当有中断到来时发生异步上下文切换。基于优先级的抢占式调度是一种强实时操作系统,但和当前其它成熟的操作系统一样,并不是“硬实时”的操作系统。所谓“硬实时”是指当某种事件发生时,系统必须在预定时间之内,或者说在限期之前做出反应,否则就会造成灾难性的后果。具有这一特征的操作系统要做到对于所提交的每一项作业及其时间要求,或者做出承诺,或者立即拒绝以使提交者可以考虑采取其他措施,对于做出的承诺则保证其实现。提交给硬实时系统的作业也可以是不带时间要求的,但是对这些作业的承诺当然也就不包含时间的因素,那将当作后台作业来对待瞄】。并没有使用基于时间限的调度算法,也就是不接受任何作业提交的时间要求。为了提高实时性,目前采用的方法都是优先级抢占式调度,使得高优先级的任务的到优先执行。这样,在一定计算资源前提下,通过恰当的任务划分和设定任务优先级可以满足实时性的要求。的内核实现基于优先级的抢占式调度。内核划分优先级为级~。优先级为最高优先级,优先级为最低。当任务被创建时,系统根据给定值分配任务优先级。优先级也可以是动态的,它们能在系统运行时被用户使用系统调用来加以改变,但不能在运行时被操作系统所改变。没有处于阻塞、挂起或者睡眠态的最高优先级任务占有处理器资源运行。内核一旦发现队列中有一个比现在运行的任务的优先级高的任务在运行,就立即保存当前任务的上下文,切换到高优先级的任务运行,这个过程称为任务抢占。系统调用和中断如时钟中断都会导致任务抢占的发生,图示意了任务抢占的过程【,该图中,任务、轮换执行,任务抢占了任务后执行,执行完毕主动放弃处理器后任务继续运行。第页囝防科学技术人学研究牛院:稗硕十学何论文高优先级优先级注释:任务中止任务执行时问图基于优先级的任务抢々从上面的分析可以看到,是采用了基于优先级抢占的调度方式,具有非常强的实时性。对的核心代码进行更深入的分析,可以确认,的内核也是可抢占的。下面对此予以分析。在文献【中,将硬件访问保护作为操作系统的内核与非内核的分界点。在这个意义下,对于一般的操作系统而言,指令和数据存放的地址范围成为划分内核与非内核的标准。但是,对于嵌入式系统而言,地址并不是连续的,指令和地址的加载位置也不是固定的,而是由系统设计人员根据地址情况指定的,很难再以地址范围作为划分内核与非内核的标准,只能以指令在操作系统中所处的逻辑地位来判断指令的执行是否在内核中。基于这个标准,本文将中所有的代码划分成三个层次,如图所示。层层层图指令所处的层次在图中,最核心的是在为时才能执行的操作,借用处理器结构中的术语,本文将这一层称为层。只有在层,指令才可以读写最核心的数据结构,如访问就绪队列,这时完成的是最基本、最核心的功能。但是,应用软件开发人员并不需要访问最核心的数据结构,比如创建一个任务,应用软件开发人员只需要调用库提供的函数即可,而不用关心任务会被挂接在哪一个核心队列中。用户应用逻辑层层与完成核心功能的第页国防科学技术人学研究生院:稗硕十学位论文函数层层的划分以函数是台处于操作系统核心库如、、等为标准。这样可以比较合理的划分出图中系统的层次。将层和层统称为内核。对于一个操作系统来说,如果一个诈在执行内核中的指令时可以被高优先级任务抢占,则认为该操作系统拥有可抢占内核。我们通过分析源代码后确定,对于正在执行内核中的指令的任务,是可以被抢占的。下面以图来说明。图所示的是这样一个场景下的抢占过程:系统中运行两个任务任务和任务任务的优先级比任务的优先级高,任务在运行过程中需要获取信号量,任务在运行过程中需要获取信号量,中断、的服务程序分别释放信号量、。图微内核的抢占过程在开始运行后,任务、被创建,分别因获取信号量和信号量被阻塞。在某个时刻,中断先产生,中断服务程序运行,信号量被释放,任务解除阻塞,任务重调度后任务开始运行。任务运行一些指令后,重新去获取信号量。图对任务获取信号量的过程图左虚线方框内部分放大进行观察。在获取信号量的过程中,为了操作核心数据结构,需要设置为。可以认为此时进行的是核心态的工作。在工作进行过程中,中断产生,中断第页国防科学技术人学研究生院程硕十学位论文的运行时会释放信弓量,但凶此时为,也就是说层被其他工作占用,释放信号量的工作将不能进行,而是被延期。之后系统又一次进行任务调度。此时,因为信号量并没有被释放,任务没有解除阻塞,任务重新开始运行。待任务进行完核心态的工作以后,退出内核,虽然此时任务获取信号量的工作并没有完成。在任务退出核心态以后,系统首先调用处理所有被延期的工作,此时信号量才被释放,任务被放入就绪队列。系统将再一次进行任务重调度。在这个时候,虽然任务也是处于就绪态,但因为任务的优先级更高,而且也处于就绪态,任务将运行。在任务运行一些指令后,重新去获得信号量,再一次被阻塞。系统进行新的重调度,任务运行,继续被打断的获取信号量的工作。从前面这个场景的运行过程可以看出,任务在获取了核心以后设置为,即使有利于高优先级任务的中断发生了,却没有导致任务被抢占,任务继续完成核心的工作。但当核心的工作完成时设置为,虽然任务还没有退出内核,却因为任务在放弃核心后信号量的释放工作被完成,并进行了任务的重调度,任务开始运行。从这个分析可以看出,如果将内核定义为完成核心功能的函数集合层和层,的内核的确是一个可抢占的内核。在基于优先级的抢占式调度中,会出现这样一种情况:一个任务等待比它优先级低的任务占有的资源而被阻塞,如果这时有中等优先级的任务就绪,阻塞会进一步恶化,超过任务的最后期限。如图所示,在时刻,优先级最低的任务运行条件得到满足,开始运行。

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/33

VxWorks SMP内核调度、信号量和中断机制的设计与实现

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利