（计算机软件与理论专业论文）基于linux的软硬件任务混合调度机制的设计与实现.pdfVIP

，。 jj_1 ； v。，、，。j ， at h e s i si nc o m p u t e rs o f t w a r ea n dt h e o r y 删 y 1 8 4 4 j c ：j i 坩 d e s i g na n di m p l e m e n t a t i o no f l i n u x - - b a s e d s o f t w a r ea n dh a r d w a r et a s k sh y b r i d s c h e d u l i n gm e c h a n i s m b yn iz h i c h e n g s u p e r v i s o r ：p r o f e s s o rd e n gq i n g x u n o r t h e a s t e r nu n i v e r s i t y j u n e 2 0 0 9 l kr i li-卜 独创性声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得 的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过 的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢 二f t ： 思0 学位论文作者签名：f 乳玄、藏 日期：2 o o7 7 、 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 作者和导师同意网上交流的时间为作者获得学位后： 半年口一年0一年半口两年口 学位论文作者签名：彳弛恝成导师签名：及? 友气篇 签字日期： 矽呵、1 、6签字日期：少矿八7 、b ， ， 小h ，时 东北大学硕士学位论文 摘要 基于l i n u x 的软硬件任务混合调度机制的设计与实现 摘要 随着可编程逻辑门阵列f p g a 器件成为嵌入式系统设计领域的研究热点，基于 f p g a 器件的新型动态局部重构技术受到学术界广泛的关注。可重构技术兼顾了系统的 性能和设计的灵活性，大大改进了传统嵌入式系统的设计方法。 可重构系统在动态局部重构技术的支持下，可以对f p g a 器件上的指定计算资源进 行动态地配置，而不影响器件上其余部分的执行。硬件任务作为一种对可重构资源的抽 象，在系统的运行过程中动态创建和销毁。在这个过程中，恰当地调度硬件任务可有效 地提高系统的整体性能和资源利用率。 本文在具有可重构功能的硬件平台上，实现了支持硬件任务实时调度的操作系统。 该操作系统以l i n u x 系统为原型，在系统中添加代理进程来表示硬件任务，通过管理代 理进程来实现控制硬件任务运行的目的。本系统的调度器在l i n u x 原有调度器的机制和 策略的基础上进行扩展，不但支持代理进程的实时调度，同时也支持周期进程的实时调 度。为了验证调度器功能的正确性，本文创建了目标板开发环境。实验表明，系统中的 代理进程和周期进程都可以被正确调度。 关键词：f p g a ；可重构技术；硬件任务；调度：代理进程；周期进程 n ， 东北大学硕士学位论文a b s t r a c t d e s i g n a n di m p l e m e n t a t i o no fl i n u x - - b a s e d s o f t w a r ea n d h a r d w a r et a s k sh y b r i d s c h e d u l i n gm e c h a n i s m a b s t r a c t a sf i e l dp r o g r a m m a b l eg a t ea r r a y s ( f p g a s ) a r ev e r yp o p u l a ri nt h ef i e l do fe m b e d d e d s y s t e m sd e s i g n ，an o v e lt e c h n i q u ed y n a m i cp a r t i a lr e c o n f i g u r a t i o n ( d p r ) b a s e do nf p g ai s p a i da t t e n t i o nb yt h ea c a d e m i a r e c o n f i g u r a b l et e c h n o l o g yt a k e si n t oa c c o u n tb o t hs y s t e m p e r f o r m a n c ea n dd e s i g nf l e x i b i l i t y , a n dg r e a t l yi m p r o v e st h et r a d i t i o n a ld e s i g nm e t h o do f e m b e d d e ds y s t e m s i ns u p p o r to fd p r ，ar e c o n f i g u r a b l es y s t e mc a ni n d e p e n d e n t l yc o n f i g u r eap o r t i o no f s p e c i f cc o m p u t i n gr e s o u r c e si nr e c o n f i g u r a b l ed e v i c e sw i t h o u ta f f e c t i n gt h ee x e c u t i o no f o t h e rp a r t s a sa na b s t r a c t i o no fr e c o n f i g u r a b l er e s o u r c e s ，h a r d w a r et a s k sa r ec r e a t e da n d r e m o v e dd y n a m i c a l l ya tr u n t i m ei nar e c o n f i g u r a b l es y s t e m i nt h i s p r o c e s s ，p r o p e r s c h e d u l i n go fh a r d w a r et a s k sc o u l dg r e a t l yi m p r o v et h eo v e r a l lp e r f o r m a n c eo fs y s t e ma n d g a i nb e r e rr e s o u r c eu t i l i z a t i o n i nt h i st h e s i s ，w ec o n s t r u c ta no p e r a t i n gs y s t e mt h a ts u p p o r t sr e a l t i m es c h e d u l i n go f h a r d w a r et a s k sb a s e do nah a r d w a r ep l a t f o r mw i t hr e c o n f i g u r a b l ef u n c t i o n s t h i so p e r a t i n g s y s t e mi s ap r o t o t y p eo fl i n u x ，a n di nt h es y s t e mw ea d dd e l e g a t ep r o c e s s e st oi n d i c a t e h a r d w a r et a s k s ，b yw h i c hw ea r ea b l et oc o n t r o lt h er u n n i n go fh a r d w a r et a s k s t h es c h e d u l e r i nt h es y s t e mi se x t e n d e do nt h eb a s i so ft h em e c h a n i s m sa n ds t r a t e g i e so ft h eo r i g i n a l s c h e d u l e ri nl i n u x ，a n dt h es c h e d u l e rs u p p o r t sn o to n l yt h er e a l t i m es c h e d u l i n go ft h e d e l e g a t ep r o c e s s e s ，b u ta l s o t h a to ft h ep e r i o d i cp r o c e s s e s w ec r e a t et h ed e v e l o p m e n t e n v i r o n m e n to nt h et a r g e tb o a r dt ov e r i f yt h ec o r r e c t n e s so ft h es c h e d u l i n gf u n c t i o n s t h e e x p e r i m e n t ss h o wt h a tt h ed e l e g a t ep r o c e s s e sa n dt h ep e r i o d i cp r o c e s s e si nt h es y s t e mc o u l d b es c h e d u l e dc r o r r e c t l y k e yw o r d s ：f p g a ；r e c o n f i g u r a b l et e c h n o l o g y ；h a r d w a r et a s k ；s c h e d u l i n g ；d e l e g a t ep r o c e s s ； p e r i o d i cp r o c e s s ， 訇k 东北大学硕士学位论文 目录 目录 独创性声明“i 摘要”i i a b s t r a c t 1 1 1 第1 章引言1 1 1 课题背景”1 1 2 可重构计算及相关问题2 1 3 研究目的和意义3 1 4 论文结构3 第2 章相关工作5 2 1 实时调度基本理论5 2 1 1 实时系统“5 2 1 2 实时调度”5 2 1 3 周期任务模型”6 2 2 可重构系统原型及相关研究”6 2 2 1 原型系统“6 2 2 2 相关研究工作7 2 3l i n u x 调度器9 2 3 1l i n u x 的特性一9 2 3 2 调度器的功能1 0 2 3 3 调度器的发展1o 2 3 4 调度器的修改1 2 2 4 本章小结12 第3 章混合调度系统的设计1 3 3 1 总体设计1 3 3 2 混合调度1 4 3 2 1 调度类1 4 东北大学硕士学位论文 目录 3 2 2 进程类型15 3 2 3 进程的优先级16 3 2 4 进程的抢占性16 3 2 5r e a d y 队列17 3 2 6 调度模式17 3 3 代理进程18 3 3 1 代理进程的含义18 3 3 2 代理进程的状态转换19 3 4 周期进程2 0 3 5 混合调度算法2l 3 5 1 算法的基本设计21 3 5 2 代理进程的调度算法2 2 3 5 3 周期进程的调度算法2 4 3 6 本章小结2 5 第4 章混合调度系统的实现2 7 4 1 核心数据结构2 7 4 1 1 调度类2 7 4 1 2 调度插件。2 8 4 2 修改内核3 0 4 2 1s c h e d h 3 0 4 2 2f o r k c 3 0 4 2 3s c h e d c 31 4 3 代理进程3 2 4 3 1d e l e g a t e 结构体3 2 4 3 2d e l e g a t e d o m a i n t 结构体”3 4 4 3 3 阻塞队列3 4 4 3 4 空闲队列3 8 4 4 周期进程4 1 4 4 1p e r i o d i c 结构体4 1 v 东北大学硕士学位论文 目录 4 4 2p e r i o d i cd o m a i nt 结构体“4 2 4 4 3 周期任务的释放4 3 4 5 系统实现的其它问题4 3 4 5 1 进程跃迁4 3 4 5 2 优先级的管理4 5 4 5 3p r o c 文件系统4 6 4 6 本章小结4 7 第5 章实验结果及分析4 9 5 1 开发平台的创建4 9 5 1 1 开发环境和工具4 9 5 1 2 移植内核5 0 5 1 3 创建a c e 文件一5 1 5 1 4 移植文件系统5 2 5 2 代理进程5 3 5 2 1 模拟实验的设计5 3 5 2 2 可调度性测试5 4 5 3 周期进程5 6 5 3 1 单个进程的执行过程5 6 5 3 2 多个线程的执行过程5 7 5 3 3 任务执行时间的测量5 8 5 3 4 可调度性测试“5 8 5 4 本章小结6 1 第6 章结论与展望6 3 6 1 结论6 3 6 2 展望6 3 参考文献6 5 致谢6 9 科研项目和论文发表情况7 1 v i 东北大学硕士学位论文第1 章引言 1 1 课题背景 第1 章引言 嵌入式系统( e m b e d d e ds y s t e m s ) 是以应用为中心，以计算技术为基础，软件硬件 可剪裁的适应应用系统对功能、可靠性、成本、体积、功耗等严格综合性要求的专用计 算机系统【l 】。它是一个技术密集，资金密集，高度分散，不断创新的基于硅片的知识集 成系统。随着嵌入式系统的发展，嵌入式系统已经逐步渗透到社会领域的各个方面。今 天的嵌入式系统已普遍应用于国防电子、数字家庭、工业自动化、汽车电子、医学科技、 消费电子、无线通讯、电力系统等国民经济的主要行业【2 j 。 信息时代和数字时代的到来，为嵌入式系统的发展提供了巨大的机遇，同时也对嵌 入式系统设备厂商及开发人员提出了新的挑战。在众多挑战中，嵌入式系统的性能日益 受到关注，在诸如数据通信、图像处理、语音识别以及多媒体应用方面，计算密集型任 务越来越多，要求嵌入系统的处理能力更为强大以便保证应用的需要。同时，嵌入式系 统的开发又需要保持较强的设计灵活性。由于它运用的领域极其广泛，尽可能地降低由 领域变化或需求调整所带来的重新设计和重新实现的时间和成本开销，成为嵌入式系统 设计者需要重点考虑的问题。所以，在保证性能的同时，系统的灵活性也是嵌入式系统 设计者追求的一个重要指标。 在不断权衡系统的性能和设计灵活性的过程中，嵌入式系统开发者们探索出两种开 发途径。 第一种途径是通过开发专用用途的硬件电路来处理某种单一的功能任务，比如众多 的a s i c ( a p p l i c a t i o ns p e c i f i ci n t e g r a t e dc i r c u i t ) 芯片已经在嵌入式系统中广泛使用。面 向功能的硬件电路能极大提高系统的性能，但是使系统的灵活性大大降低，一旦硬件电 路设计完成，便不易进行更改。如果再次更改，就需要大量重新设计的开销，硬件电路 的重设计会影响项目中软件程序的设计，并大大影响整个项目的开发进度。 第二种途径是使用通用用途处理器来增加系统的灵活性，系统的各种功能可以以软 件的方式在通用处理器上得以实现，系统功能的变更只是依赖于软件代码的变更，大大 减少了重新开发整个系统的耗费，尤其是开发硬件系统所带来的开销。但是系统的所有 功能不能都依赖于软件来完成，在高实时和高计算密度的领域，软件处理往往不能满足 系统的时限要求和服务质量，必须依赖于硬件电路的加速。 东北大学硕士学位论文第1 章引言 1 2 可重构计算及相关问题 可重构计算( c o n f i g u r a b l ec o m p u t i n g ) 技术的出现和快速发展，为上述问题带来了 全新的解决方案。可重构计算技术是指在软件的控制下，利用系统中的可重用资源( 如 f p g a 等可重构逻辑器件) ，根据应用的需要重新构造一个新的计算平台，达到接近专 用硬件设计的高性能。它避免了微处理器计算模式因为取指、译码等步骤导致的性能损 失，同时也消除了专用集成电路( a s i c ) 计算模式因为前期设计制造的复杂过程带来的 高代价和不可重用等缺陷。可重构计算技术结合了通用处理器和a s i c 两者的优点，能 够提供硬件功能的效率和软件的可编程性。其核心突破就是能够动态进行硬件电路配 置，这种配置方式灵活而高效，通过硬件描述语言h d l ( h a r d w a r ed e s c r i p t i o nl a n g u a g e ) 以可编程的方式来完成并实现电路的构型3 1 。通过引入可重构计算技术，整个嵌入式系 统既保持了设计灵活性，同时也获得了专有用途硬件电路的等价性能。 f p g a ( f i e l dp r o g r a m m a b l eg a t ea r r a y s ) 是可重配置计算技术中最具代表性且使用 最为广泛的器件之一。它的出现及快速发展，为可重构计算技术的快速发展提供了便利。 它允许多个硬件任务同时运行【4 】，并有两种配置方式：完全可重配置和部分可重配置。 完全可重配置必须对整个f p g a 进行重新配置才能改变运行逻辑；部分可重配置是指在 f p g a 的一部分逻辑单元正在运行的同时，可以对另一部分的逻辑单元进行配置，而对 正在运行的部分没有影响。这种机制就是运行时局部可重配置技术( p r t r ，p a r t i a l r u n t i m er e c o n f i g u r a t i o n ) ，也称为动态局部可重配置技术。这就意味着整个f p g a 区域 成为了一个可以不断复用的硬件资源池，不但可以在运行的过程中动态改变逻辑功能， 使不同的任务复用f p g a 中同一区域，而且还可以把整个f p g a 区域划分成若干个子区 域，使得多个不同的任务可以在同一时间的不同区域中得以运行。部分可重配置具有灵 活而高效的配置特点，符合可重构计算的思想，用它来完成并实现电路的构建，可以达 到现代嵌入式实时系统的高性能和任务动态执行的要求。 在这种背景下，硬件任务( h wt a s k ) 的概念就随之产生了。所谓硬件任务，就是以 硬件电路的方式完成特定功能的模块单元。对于给定的输入，经过传统的软件程序处理 而得到的结果与功能等效的硬件电路处理的结果应该是完全相同的，即软件和硬件在逻 辑功能上存在完全等效的性质。硬件任务是一个可以进行局部重配置的配置文件( 或者 称为局部比特流) ，它以模块的形式在f p g a 中加以配置，并得到执行。 随着s o c 技术的发展，已经出现了一种新的设计观点，即采用统一的多任务( 多线 程) 模式处理软件任务和硬件任务。c p u f p g a 混合的软硬件平台( 以下简称“c p u f p g a 混合平台 ) 系统模型的提出，不但体系结构方面进行了创新，而且对运行在其上的传 2 o 东北大学硕士学位论文第1 章引言 统的操作系统提出了新的问题。对操作系统在传统的功能方面也有了新的概念延伸，即 运行在c p u f p g a 混合平台上的新的操作系统既能够支持传统意义上的软件任务，还要 支持对硬件任务的管理，以及软、硬件任务之间的通信，有效的存储管理等。同时，该 操作系统需要对上层的应用开发人员提供统一的接口和编程模型。这种混合平台及其上 的操作系统的研究成为当今可重构领域的热点和难点之一。 1 3 研究目的和意义 随着基于可重构计算技术的f p g a 器件等的快速发展和使用，可重构计算系统已成 为工业界关注的热点。嵌入式系统开发人员已经充分认识到可重构计算对计算密集型的 高性能计算应用的巨大潜在价值，但是可重构计算资源应用编程的复杂性和传统的软硬 件对其支持的局限性，极大地限制了这种具有极大应用前景的技术的普及应用。由于可 重构器件既有硬件电路高效计算的优良性能，也具有多次编程、易于修改的灵活性，因 此可重构计算系统迫切需要操作系统能够支持动态可重构资源的实时混合调度。 在c p u f p g a 的混合平台上，操作系统既要进行软件任务的管理，也需要进行硬件 任务的动态管理。传统实时操作系统中的调度算法并不支持可重配置器件中的硬件任务 调度，重配置硬件作为硬件加速器，由应用系统根据自身需要直接使用，所以会造成资 源利用不充分、可移植性差、开发效率低下等缺点。因此需要开发新型的混合调度操作 系统，利用f p g a 高效的计算特性来提高整个系统的性能。 项目将根据这一巨大需求，构建研究支持可重构计算的混合系统原型，研究基于动 态可重构计算系统的软硬件任务的混合调度机制。通过改进现有操作系统内核，开发支 持动态可重构计算资源管理的混合操作系统，该系统能够统一管理系统中软硬件任务所 用到的资源，并为系统的上层开发人员提供必要的开发环境和编程接口，为可重构计算 技术在高性能计算领域和嵌入式系统应用领域的推广应用突破瓶颈。 项目开发基于c p u f p g a 的混合平台，主要工作体现在以下两个方面： ( 1 ) 对标准的l i n u x 内核进行修改，使之具备调度硬件任务的功能；同时扩展内核对 软件实时任务的调度功能，在本系统中实现了对周期任务的调度功能。 ( 2 ) 将修改之后的l i n u x 内核移植到可重构硬件平台，即项目的开发平台x i l i n x v i r t e x i ip r o 开发板。 1 4 论文结构 本文以国家8 6 3 项目“面向可重构计算系统的实时调度问题与操作系统技术的研究” 3 东北大学硕士学位论文第1 章引言 为基础，对基于l i n u x 操作系统的软硬件任务混合调度机制进行探索和研究。全文共分 六章，内容安排如下： 第一章为引言。介绍了课题研究的背景、可重构计算及其相关问题，然后叙述本文 研究的目的和意义，并给出本文研究的主要工作。 第二章介绍本文的相关工作。首先，介绍实时调度的基本理论，包括实时系统、实 时调度及周期任务的基本概念和相关术语。接着，介绍可重构系统的原型和支持混合调 度的操作系统，并叙述了当前可重构系统的相关研究工作。最后，分析了l i n u x 的特性， 并介绍其调度器的功能、发展及针对调度器的修改工作。 第三章是混合调度系统的设计部分。首先，给出系统的总体设计及本系统中硬件任 务的概念。接着，分析混合调度相关的问题，包括调度类、进程类型、进程的优先级和 抢占性、r e a d y 队列及调度模式等。然后，在混合调度系统中引入代理进程的概念，并 分析了代理进程和周期进程状态转换问题。最后，介绍了混合调度算法总体设计，并对 代理进程和周期进程的调度算法进行详细的分析。 第四章是混合调度系统的实现部分。首先，介绍了实现混合调度系统的两个重要的 数据结构，即调度类和调度插件。其次，介绍了修改l i n u x 内核的具体工作及实现代理 进程和周期进程的数据结构和算法。最后，介绍实现系统的其它问题，即进程跃迁、优 先级管理及p r o c 文件系统。 第五章是实验部分。首先，介绍了开发平台的创建过程，包括系统的开发环境和工 具、l i n u x 内核的移植、a c e 文件的创建及文件系统的移植。接着，介绍验证代理进程 调度正确性的模拟实验，用系统调用的方式来模拟中断的产生，并给出模拟实验的设计 与结果。最后，介绍了验证周期进程调度正确性的实验，依次设计了单个进程和多个线 程的执行过程，并设计出任务执行时间的测量方法，然后，通过两组实验来验证周期进 程调度的正确性。 第六章对整篇论文进行总结，叙述本文完成的主要工作，并且指出系统在实现过程 中尚存在的一些不足之处，这有待于在后续的工作中进行完善。 4 东北大学硕士学位论文 第2 章相关工作 第2 章相关工作 本章首先介绍实时调度的基本理论，包括实时系统、实时调度及周期任务的基本概 念和相关术语。接着，介绍可重构系统的原型和支持混合调度的操作系统，并叙述了当 前可重构系统的相关研究工作。最后，分析了l i n u x 的特性，并介绍其调度器的功能、 发展及相关的修改工作。 2 1 实时调度基本理论 2 1 1 实时系统 “实时系统( r e a l t i m es y s t e m ) ”，是指能够在指定的或者确定的时间间隔内( 往 往是毫秒甚至微秒级) 完成特定功能并对外部或内部做出同步或异步响应的系统，系统 的正确性不仅依赖于计算的逻辑结果，而且依赖于结果产生的时间顺序。 “硬实时系统( h a r dr e a l t i m es y s t e m ) ，是指系统中所有的截止期限必须被严格 的保证，否则将导致灾难性的后果。 “软实时系统( s o f tr e a l t i m es y s t e m ) ”，在截止期限被错过的情况下，只造成系统 性能下降而不会带来严重恶果。 2 1 2 实时调度 “可抢占式调度( p r e e m t i v es c h e d u l i n g ) ，是指当前正在运行的任务可以随时让位 给优先级更高的处于就绪态的其它任务。 “不可抢占式调度( n o n p r e e m t i v es c h e d u l i n g ) ，是指一个任务一旦获得c p u 就独 占c p u 运行，除非由于某种原因，它决定放弃c p u 的使用权。 “优先级驱动调度( p r i o r i t y d r i v e ns c h e d u l i n g ) ”指按照任务优先级的高低确定任务 的高低确定任务的执行顺序”】。 “静态优先级调度( s t a t i cp r i o r i t y d r i v e ns c h e d u l i n g ) ”是指任务的优先级分配好之 后，在任务的运行过程中，优先级不会发生改变。 “动态优先级调度( d y n a m i cp r i o r i t y d r i v e ns c h e d u l i n g ) ”是指任务的优先级可以随 着时间或系统状态的变化而发生变化。 5 东北大学硕士学位论文 第2 章相关工作 2 1 3 周期任务模型 一般来说，周期任务具有以下任务模型的特征： “释放时间( r e l e a s et i m e ) ”或者称为“到达时间( a r r i v a lt i m e ) ”，是指任务准备 好被执行的时刻。 “起始时间( s t a r tt i m e ) ，是指任务开始执行的时刻。 “完成时间( f i n i s h i n gt i m e ) ，是指任务完成执行的时刻。 “执行时间( e x e c u t i n gt i m e ) ，是指任务在不被中断的情况下，占用处理器的时 间。 “截止时间( d e a d l i n e ) ，是指任务必须完成的时刻。 “延迟( l a t e n e s s ) ”，是指任务的完成时间相对于截止时间的时延。 2 2 可重构系统原型及相关研究 2 2 1 原型系统 图2 1c p u f p g a 混合系统结构 f i g 2 1c p u f p g ah y b r i da r c h i t e c t u r e 通常来说，可重构系统是c p u f p g a 的混合平台。s t e i g e r 等j k 在文献【6 】中给出了系 统的体系结构，如图2 1 所示。通过两个双向通道，一个局部可重构f p g a 和一个主c p u 耦合。一个通道是配置和回读端口( c 爪) ，它使得主c p u 完全控制重构设备的配置，也 就是说全局或局部的配置信息可以下载到器件中，还有器件的状态信息可以回读给主 c p u 。另一个是通信端口( c o m m ) ，它提供主c p u 和可重构设备之间的信号交互。这 个端口连接映射道c p u 和可重构设备上的操作系统的功能。c p u 和可重构器件( r c ) 都 和一些外围设备c i 相连，这些外设包括r a m 、n a n df l a s h 、u a r t 等。图2 1 的体系结 构可以由独立的c p u 和可重构器件或是一个完整的c p u 和可重构器件的可配置片上系 统来实现。 6 东北大学硕士学位论文 笫2 章相关工作 在c p u f p g a 混合平台中，所有软、硬件任务得到协同调度。c p u 作为软件任务的 通用处理器，可以运行传统的操作系统以及软件应用程序；这个由c p u 和操作系统构成 的执行环境，可以在软件层面上支持多任务( 多进程或多线程) 的并发执行。f p g a 可 以看做是一个能够同时容纳很多硬件任务的并行处理器，通过对其中逻辑资源和电路进 行局部配置来实现不同逻辑功能，完成相应的计算任务。 i 亘亘j - 蓬遁j ： 刁o m m u n i c a t o r ) i l = f 一一一卜一一一i_ l l i - 1- f p g a 图2 2 支持混合调度的操作系统 f i g 2 2o p e r a t i n gs y s t e mf o rh y b r i ds c h e d u l i n g 运行在c p u 之上的操作系统，除了具备对原有系统的软、硬件资源进行管理之外， 还必须能同时管理f p g a 的运行，具体地说，是对运行在f p g a 上的硬件任务的管理。如 图2 2 所示，支持混合调度的操作系统除了具备传统的调度器、内存管理等功能之外，还 有管理硬件任务的调度器、放置器及下载器等。调度器按照一定的调度策略，从硬件任 务的r e a d y 队列中选择下一个在f p g a 上运行的硬件任务；放置器根据硬件任务的所需要 的f p g a 计算资源的面积，确定硬件任务放置在f p g a 上的具体位置；下载器则将准备在 f p g a 上投入运行的硬件任务的比特流文件下载至i j f p g a 上相应的位置。调度器和放置器 之间需要协同工作，才能为一组硬件任务安排恰当的调度时机和区域中的放置位置。调 度器和放置器成为支持可重构操作系统中最为重要的部件，其也为操作系统带来了关于 硬件任务的调度算法和空间管理策略的种种问题。此外，在支持混合调度的操作系统内 部，还需要解决系统中软硬件任务间的通信和数据传输等问题。 2 2 2 相关研究工作 在设计c p u f p g a 混合平台上的调度系统时，本文查阅了大量在可重配置系统中已 经进行的相关工作。 w a l d e r 和p l a t z n e d 生 7 1 中，以自顶向下的方法提出了可充配置硬件操作系统的原型。 7 东北大学硕士学位论文笫2 章相关工作 他们设计了一个基于c p u f p g a 的可重配置系统，分别从操作系统和可重配置资源两个 层面提出了许多概念。文中给出了一个具体的实例，以x i n l i xv i r t e x x c v - 8 0 0 作为开发平 台来加以实现，但是文中并没有描述很多关键的技术细节。b a s k a r a n 和s r i k a n t h a n 在【8 】中 较详细的提出了运行时可重配置的基本结构，并描述了h o p e s ( h a r d w a r eo p e r a t i n g s y s t e m ) 实现的一些具体技术。 k o s c i u s z k i e w i c z e t 等在一j 中，提出在已有的l i n u x 内核之上构建系统，并且试图用软 件进程的模型来构建硬件进程。对于操作系统内核，在f p g a 上执行的硬件进程就如普 通的软件进程。但是，已有的实现仅局限于使用f i f o 的进程间通信；由于没有开发细粒 度的并行化的f p g a ，执行中的硬件任务仅能映射到某个处理器。x i e 等在【l o 】中提出一个 类似于包含多个处理器软核的异构多处理机系统。在该系统中，l i n u x 操作系统的服务 一起综合至i j f p g a 中。b e r g m a n n 等在t l l 】中提出用软件封装程序来封装任意的硬件电路， 以此为内核和其它进程的交互提供一个透明的接口。他们的方法包含在软硬件进程之间 共享相同的地址空间，因此使用进程而不是线程来封装硬件模块。 s o 和b r o d e r s e n 在【1 2 】【1 3 1 中提出的b o r p h 系统是一个基于f p g a 的可重构计算机的操 作系统，该系统通过修改标准的l i n u x 内核，来实现操作系统管理硬件任务的接口。文 中提出了硬件任务执行正常的u n i x 以获得标准的o s 服务遵循、使用标准统一的u n i x 访 问接口、以e l f 为基本格式的硬件任务文件，并且实现了硬件进程的概念。b o r p h 系统 对构造基于l i n u x 内核的可重构系统具有一定的参考价值。 l u b b e r s 和p l a n n e r 在【1 4 】【1 5 1 中，提出的r e c o n o s 是一个使用单一且统一的编程模型、 同时支持软硬件线程的操作系统。r e c o n o s 是基于e c o s ( 一个被广泛使用的实时操作系 统) 而设计的，系统中的所有线程共享相同的物理内存空间，这样，硬件线程可以直接 访问系统中任意位置的内存。但是，r e c o n o s 并不支持动态、局部的可充配置技术，所 有的硬件线程被静态地配置到f p g a 中去。 p e c k 、a n d s o n 及a g r o n 等人在【1 6 】【1 7 】中，提出的c p u f p g a 混合系统平台将协同调度 器、中断处理等传统操作系统重要构件以硬件电路的形式在f p g a 中加以实现。这样， c p u 仅仅是一个管理软件任务的平台，这使得系统整体的效率大大提高，以硬件方式实 现的调度器首次实现了软硬件任务的统一。 v u l e t i c 在【1 8 】【1 9 】【2 0 】中，在传统的操作系统之上提出软硬件任务统一的虚拟内存、平台 无关的接口及多线程的执行；对硬件任务的虚拟内存支持，文中提出了自己新颖的观点。 d a n n e 在中，提出了基于f p g a 计算系统的操作系统及其内存管理方法；针对f p g a 中运行的任务，文中提出了类似于传统操作系统中的虚拟地址映射、动态内存分配以及 8 东北大学硕士学位论文 第2 章相关工作 多任务在访问物理内存时，基于优先权的访问方法。d a n n e 等在2 3 1 中，还提出了一个动 态使用可重构设备来执行实时周期任务的原型系统；文中设计的全硬件运行时系统，在 系统架构上提出了时钟、调度器、任务管理、m m u 等模块；此外，提出了调度器的数 据结构、调度周期等概念。 2 3lin u x 调度器 2 3 1lin u x 的特性 嵌入式操作系统所具有的实时、高可靠性、低功耗等特性是嵌入式系统开发选用操 作系统的一些基本要求。除此之外，嵌入式操作系统的选取还有另外一些需要考虑的因 素，例如可移植性和兼容性、开发进度、实时性等【2 4 】。 运行在c p u f p g a 混合平台中操作系统，除了能够管理传统的软件任务之外，还必 须能够管理硬件任务。由本章“相关系统介绍 一节中描述的系统可知，在现实世界中， 不存在一个可以直接使用而无需任何修改的可重构操作系统。开发一个全新的完整操作 系统去支持软硬件任务协同调度是非常困难的，而且完全没有必要的。因为软件任务的 所有运作机制与原先相同，而且传统的软件操作系统开发难度极大，这在项目开发过程 中绝对是不切实际的。因此，对操作系统的构建和开发可以以现有的某种操作系统为基 础进行修改，选择当前开放源代码的操作系统是构建软硬件协同调度操作系统的基本原 则。 l i n u x 是一个免费且开源的操作系统内核，运行在具有m m u ( m e m o r ym a n a g i n g u n i t ) 的体系结构上，能够支持当今大多数主流的体系结构，女【i i a 3 2 、a r m 、p o w e r p c 、 m i p s 等，因此特别适用于大多数主流的嵌入式处理器或者s o c 。 该系统支持内核模块的动态加载和调试，有诸如v i 、e m a c s 等开发环境和基于g c c 的交叉工具链。l i n u x 为核源代码组织合理，能够较方便地完成内核代码的修改和开发。 同时