（计算机科学与技术专业论文）基于智能传感器的实时系统任务调度分析.pdf

浙江大学硕士攀位论文 摘要 智能传燎器是一种可嵌入剐物理世界并大量散布于环境当中的资源受限的设各。尽管资 源十分商限，但是应阁于镪能传感器上的操作系绞仍然要拭霉j 二复杂的经务调度，并且簧支持 并发密集操作、满足实时约束条件、以及满足自适成性和可靠性要求。本文以熬于智能传感 器的蜜封控劐聚凌妁开发为鹜最，重点磅究了基予褰憩岱感器靛实时系统申靛任务调度分 辑。本文孵工搀主要嶷中在啦下瓣个方露： 分析了箕备实时性栽要求静智能传感嚣韵一般磁溺特点，分析了基于智熊传感器的实时 系统模型。礴究了寨时系统任务调液辅兼静璎论，包捂：任务调度，资源访闯控制协议， 基于c p u 利用率进行可调度性分析，藻于系统响应时间的可调度性分析。 2 对蒺予智能传感器的实对系绞的任务调度作了漂入的分析j i ：作，燕要饿了如下工作：建 立了一个基于智能传感器的实时系统任务集模型；在该任务模型丘分析了三! = 种任努调度 桃制，电括基= 线先缓的分缎调度槛制、混台捻f 与调度棼l 到、f c f s 调袭撬糍。实l l 搴系 统圣壬务调度秘究中最霆要的就是可调度性分辑磅究，本文逐对莱爝基于饯巍级斡分缝调 魔枫嘉翱灌金抢占溺疫挺藩l 辙了可调发往分析。 3 黠蓥于智能黄感嚣翡实时系统作了柽势缀容镌分祈，由于传感器鬈统资涮翦疆，囡褥基 于传感器的容错技术较难实现，冈此我们主要对采用时间冗余技术容忍短暂性错误做了 比较详细的分析。 4 对綦于智能传感器的察时系统的示例平台t i n y o s 和yo s 做了分析。对这两个智能传 感器平螽做了稳鼙介绍，蕊点介绍了鼹蠹职来熙的不圆的任务调度枫制。￥o s 燕饿挺 于8 6 3 项目“支持黄遁计算的操作系绕关键技术的研究”蛇，我g 自主开发的基于智能 搀感器翘撩捧系统，在y o s 系统中，g | 了分浆 壬务调痉撬糍。 关键字：餐能传感器、实对象统、萋予传惑器鹃实时系统、任务诵度、可调度幢分轿、 yo s i i i 浙托大学硕士学位论文 a b s t r a c t s m a r ts e n s o r sa r er e s o u r c er e s t r i c t e dd e v i c e sw h i c hc a ab ed e e p l ye m b e d d e di nt h ep h y s i c a lw o r l d o rs p r e a dt h r o u g h o u to u re n v i r o n m e n t a l t h o u g hs y s t e mr e s o u r c ei ss e r i o u s l yl i m i t e d ，o p e r a t i n g s y s t e ma p p l i e di ns m a r ts e n s o r sh a st oi m p l e m e n tc o m p l e xt a s k ss c h e d u l i n g , w h i c hs h o u l ds u p p o r t c o n c u r r e n to p e r a t i o n ，m a t - t i m ec o n s t r a i n t ，a d a p t a b i l i t ya n dr e l i a b i l i t y i nt h i sp a p e r , w es t u d yt h e r e a l t i m es y s t e mb a s e do ns m a r ts e n s o r s ，e s p e c i a l l ya n a l y z et h et a s ks c h e d u l i n gf o rt h er e a l - t i m e s y s t e mb a s e do ns m a r ts e n s o r s t h em a i nc o n t e n t sa n dc o n t r i b u t i o n so f t h ew o r ka r ea sf o l l o w s ： 1 a n a l y z et h ea p p l i c a t i o nc h a r a c t e r i s t i co f s m a r ts e n s o r sw h i c hh a v er e a l - t i m ec o n s t r a i n t s ，a n d a n a l y z et h em o d u l eo f r e a l - t i m es y s t e mb a s e do ns m a r ts e n s o r s s t u d yt h et h e o r yo f t a s k s c h e d u l i n gi nr e a l - t i m es y s t e m s ，w h i c hi n c l u d e st a s ks c h e d u l i n g ，r e s o u r c ea c c e s sc o n t r o l p r o t o c o l ，s c h e d u l a b i l i t ya n a l y s i sb a s e do nc p u u t i l i z a t i o na n ds c h e d u l a b i t i t ya n a l y s i sb a s e d o nc a l c u l a t i o no f t a s k s w o r s t c a s er e s p o n s et i m e d e e p l ys t u d yt h et a s ks c h e d u l i n gf o rr e a l - t i m es y s t e mb a s e do ns m a r ts e n s o r s s e tu pa 协s k s e tm o d u l ef o rs m a r ts e n s o rs y s t e m s a n dw ea r i a l y z et h r e et a s ks c h e d u l i n gs c h e m e sb a s e do n t h i st a s ks e tm o d u l e , w h i c hi n c l u d eh y b r i dp r e e m p t i v es c h e d u t i n g , p r i o r i t y - h a s e dg r o u p i n g s c h e d u l i n ga n df c f ss c h e d u l i n g b e c a u s et h es c h e d u l a b i l i t ya n a l y s i si st h em o s ti m p o r t a n t a m o n gt h es c h e d u l i n gt h e o r yf o rr e a l t i m e ，w ea n a l y z et h es c h e d u l a b i l i t yf o rh y b r i d p r e e m p t i v es c h e d u l i n ga n d 龄o r i l y - b a s e dg r o u p i n gs c h e d u l i n g 。 3 ，a n a l y z et a s k - l e v e lf a n l t - t o l e r a n c es c h e m e f o rr e a l t i m es y s t e mb a s e do ns m a r ts e n s o r s 。i ti s d i f f i c u l tt oi m p l e m e n tf a u l t - t o l e r a n c es c h e m ef o rs m a r ts e n s o r s ，b e c a u s eo f t h er e s t r i c t e d r e s o u r c e w em a i n l ya n a l y z et h et r a n s i e n tf a u l tt o l e r a n c eb ya p p l y i n gt i m er e d u n d a n c y 4 a n a l y z et h em i c r oo p e r a t i n gs y s t e mt i n y o sa n dyo s a se x a m p l ep l a t f o r m sf o rs m a r t s e o s o r s ，a n a l y z et h ec h a r a c t e r i s t i co f t h e s et w oo p e r a t i n gs y s t e m s e s p e c i a l l y , w ea n a l y z et h e d i f f e r e n c eo f t h et a s ks c h e d u l i n gs c h e m eo f t h e s et w os y s t e m s ￥o si sa l lm i c r oo p e r a t i n g s y s t e mt os u p p o ns m a r ts e n s o r , w h i c hi ss p o n s o r e db yt h en a t i o n a l8 6 3p r o g r a m - a n dt h e p r i o r i t y - b a s e dg r o u p i n gs c h e d u l i n gs c h e m ei sa p p l i e di nt h ev o s k e y w o r d s ：s m a r ts e n s o r s ，r e a l - t i m es y s t e m s ，s e n s o v b a s e dr e a l - t i m es y s t e m ，t a s ks c h e d u l i n g , s c h e d u l a b i l i t ya n a l y s i s ，yo s 浙江大学硕士学位论义 图表目录 图表1 籍靛传惑器示意蓉3 图表2 任务调度模型8 圈表3 独立簧感器系统 1 图表4 分布式多传感器系统j2 图表5 任务最大响应时间的构成1 8 援表6 经务l 翘芙链时蘩1 9 图表7 智能传感器行为过程一2 3 图表8 分组调度任务集分析2 5 鬻表9 分组调度任务集实锏2 7 图表l o 任务集实例分组调度2 7 夔衷ll 混合调度任务集分辑。2 9 图表1 2 混合调度任务集实例3 0 图表1 3 任务集实例混合调度3 0 强表 4 容镶蒎篾实铡+ 4 4 图表1 5t i n y o s 系统框架网4 5 图表1 6r o s 硬件结构图。4 8 圈表1 7 两级任务褥度梳翻5 0 v l i 浙江，( 学硕士学位论文 第一章综述 1 1 弓l 言 传感器技术是一项当今世界令人瞩目的迅猛发展起来的简新技术之一，也是 当代科学按零发展的一个羹要标志，它与通德技术、计算枫技术构成臻息产渡鳆 三大支柱之。如果说计算机是人类大脑的扩展，那么传感器就是人类五宙的延 枣，巍集成魄路、诗冀规按术飞速发鼹时，人们才逐步谈谈李蕊崽摄敬装鬟 镬感嚣没骞鼹上售感技术豹发展，薅擦呼“大脑发达、五囊不灵”。从八十年代 起，健懑器开始受翻替遮蘩褫，并逐步在1 楚舞范溷雨掀起了驻“传感嚣热”。 传感器技本餐有十分广阉静瘦弱前景，在军攀鼙防、。农簸、城市管壤、垒黪医 疗、环境盗测、抢险救灾、防恐反恐、危险区域远程擦制等许多领域都有重要的 科磷价值和巨大实用价值，当前，美阕、德凰、丑本的发达国家都将砖感器技术 视为关键技术、核心技术，各园对健感器的开发投资逐年升级。倍感器技术已经 弓l 起了世器诲多国家攀雾、学术爨和工业爨懿裹残重视，并戏淹送入2 0 0 0 年以 来公认鲍毅越翦沿热点磺究领域，拔认为是烬慰二一 世纪产生巨大影响力的技 术之一。 重纛智能终感器 七十年代以来，微处理器辑取的举世瞩遥的成就鬻来了飞速发展的数字识革 命。九十年代以来的廉拟仪器技术的( v x i ) 飞速发展，使以微型计算机为基础 的测掇系缀懿霞要传感器寒挝供羧以终出实瓣决繁戆数据。隧萋系统鑫动纯纛度 憋摁褰朗复热牲的煺翔，对使感器豹综合糟凄、稳寇霹靠蛙秘响应要求越来越崧。 蒋统的俦藻器瑷箕功筏单一、性镌不逶瘟、不能满避多稀测试要求，两j 篼入稍将 激处壤器智黥技术斑髑予传感器，特潮是a 十年代束潮醴朱，人们又褥微机械鸯羁 工技术应用割传感器，从而产生新概念传感嚣”s m a r ts e n s o r - - 智能传感器。 翻前，国际传感器领竣已对”s m a r ts e n s o r ”定义形成了旗奉共识，艇中文译法 尚未澎成定论。从萁功能来说，智能传感器是这样种器件：具有种或多种敏 浙江人学硕士学位论文 感功挠，畿够完残黻下帮分或卷全帮秘麓：僖号揉测、交羧处淫、逻辑判断、功 筢诗黪、双彝遥谖，内部霹实现螽梭、鑫棱、螽补偿、螽诊断功麓。扶便稿懿蹙 度，传感器的准确度、稳定性和可靠瞧是至关照要的。长期以来研究工作大都集 中在硬件方面，虽然太们不断翻用新材料研制敏感器件，改遗传感器蕊片的制造 工艺方法来提高芯片的质量以及通过外电路补偿方法来改善传感器的线性度、稳 定瞧窥浚爨漂移，毽砉器没有稷本狡静突酸。 镯能传艨器的出现使得原来对硬件性能的苛刻要求有所减轻，1 砥靠软件帮助 可以使传懑器豹性熊大幅废提高。智能传感器通常舆备如下几个功髓； 1 复合敏感功熊一我们观察周围的自然现象，常见的信号有声、光、电、 热、力、化攀等。敏感元件测量一般通过两种方式：直接和间接的测量。而智能 传感器具有复台功黢，够网时溅璧多穆物毽量积佬学量，绘出能够铰全瑟反映 物质运动规律的信息。如美圈加利弗尼亚大学研制的复合液体传感器，可同时测 量会痿夔漫浚、滚遮、压力蠲密度。羡餮e g & gi cs e n s o r s 公司疆铡鹣复合力学 传感器，可同时测量物体某一点的三维振动加速度、速度、位移，等等。 2 裔替偿和计算功能辩多簿来跌攀传感嚣研翻豹工程技术入员一赢为 传感器的温度漂移和输出非线性作大量的补偿工作，但都没有从檄本上解决问 题。而智能传感器的囱补偿和计算功髓为传感器的温度漂移和非线帔补偿开辟了 新的道路。这样，放宽传感器加工精密度要求，只鼹能保谩传感器憋重复投好， 利用微处理器对测试的信号通过软件计算，采用多次拟合和麓值计算方法对漂移 帮j 线性遘行李 偿，麸嚣莛竣褥较麓确静测餐结鬈。 3 自梭、自校、自诊断功能普通传感器肴 要定期检验和标定，以保证 它在正常筏耀霹是够豹准确度，这些工佟一般要求褥传感器扶使瘸魏场拆静送到 实验室或检验部门进行。对于在线测最传感器出现辩常则不能及时诊断。采用智 靛蒋感器情况刚大商改观，曾先自诊断功能在电源接通对进行鸯检，诊断测试以 确定组件有无故障。其次根据使用时间可以在线进行校正，微处理器利用存在 e p r o m 内的计量特性数据进行对比校对。 4 售惑存绪和赞辕隧羲全餐集教控铡系绞( s m a r t d i s t r i b u t e d s y s t e m ) 的飞速发展。对智能单元要求具备通信功能，用通信网络以数字形式进行双向通 售，这毽楚餐能簧感器关键标志之一。整麓传感器逶过溅试数据黄输或接渡揍令 2 浙江太举硕士学短论文 寒实瑗各颈功戆。麴臻益懿竣莲、 镄参数鹣设髯、痰硷参数设置、测试数据输 出嬉。 智能传感器般由电源、感知部件、嵌入式处理器、存储器、通信部件和 软传这几部分构成，妇图t 须示【l 】。电源为传感器援供正常王终爨毖罴筑黢涯。 感知部件用于感知、获取外界的信息，并将其转换为数字信号。处理部件负赁协 调繁点鑫帮分戆工穆，魏瓣感知部俘获取静信怠进行必要静楚瑾、绦存，控翻感 知部件和电源的工作模式等。通信部件负责与其他倦感器等的通信。软件则为传 薅嚣提供必葵翡软件支持，魏嵌入式操作系统、嵌入式数攒库系统等。 翻表 帮l 传感器苯意图 一般而言，单个传感器的功能魁非常有限的，但是当它们被大量地分布到物 瑾环境中，著维织成一个传感器网络，再配麓良好的系统软件平台，就可以究成 强大的实时跟踪、环境监测、建筑戏设备的状态监测等功能。随着微电子技术、 微缁加工技术、微机电系统m e m s ( m i c r oe l e c t r o m e c h a n i c a ls y s t e m ) 技术、技 术系统s o c ( s y s t e m o n c h i p ) 芯片设计技术、纳米孝考料与技术、瑷代售息遴讽 技术、计算机网络技术等的发展，正涌现出越来越多的网络化智能传感器。 当蔫，餐l 传感器在冬个领域懿应爱越来越广泛。这穆设备豹餐一令应惩是 在无人控制的环境中进行数据( 如自然储备、地震地质结构数据) 采集。对于比 较憨劣静环壤帮天举宜至l 运酌场辑蒋常逶鬻，眈如荒岛上酶环境帮象态篮控，濠 始森林的防火和动物活动情况监测、污染区域以及地震和火灾等突发灾难现场的 监羟。智能传感器也 可用于城市酶交通监测，大型车间原材料和仓库货物进出情 况的艇测，以及机场、大型工业园区的安全渡测。出于网络他的智熊传感器县有 可快速部署，可自组织和容错性高的特点，糊此也非常适合征军事环境监控上应 用，魄如逶避飞毒惩姆传感器一蛰点数攒在战场上，x 量化学武器懿使爱、羧方车辆纛 士兵的运动进行监测和报告，美军融经多次在实弹军事演习中进行了类似的试 浙江大学硕士学位论文 验，并磅铡了基于接感器嬲络系统熬褰麓缝雷系统等离辩教武器。 瓣疆，我们分缨了蟹能健感器豹功l 特点秘应爝领域，下露，我靛分绍下 智能倍感器豹应用特点： 资源受限 资源受限主要表现在以下几个方面：通信能力有限，智能传感器的通信带宽 窄露盈经常变铯，黧 罨在毒鼹逶蔷戆力豹条 串下高豢羹遮完成感知信惑匏簸壤与 传输，是面临的挑战之一；电源能量有限，锣能传感器的电源能量极其有限，由 予嘏源筢量豹漾阖传感器经常失效躐凌弃，电源髓量约束是阻碍传惑器溺络应用 的严夏问题：计算能力有限，智能传感器中通常都舆有嵌入式处理器和存储器， 这黧传感器郝具有计算能力，可以究成一些信息处瑷工作，但是，由于嵌入戏处 理器秘存储嚣的能力秘容量有限，传感器的计算能力十分鸯隈。 o 小尺寸和低功耗 尺寸霹咚源限期决定了鬻爱转薅器节点只戆其餐有疆豹计粪豢镶藐力窝短 距离通信能力。硬件设计的一个主要目标就赵减少和降低实现某个功能所要求的 尺寸鞫电源。疑系统层次看，由予硬件资添鹣有袋帮稀少，软释必须尽霹靛离效 的使用它们。 多样纯豹设计和便溺 无线网络传感器设各的设计倾向于针对爨体的成用，而不是通用蛇，它们其 集成应用所必须要求的硬件。对于任何一个麒体应用，要求不同的硬件组合时， 纛要葛度熬鳃l 牛骰：软传设计，戆够蓦誊容易缝疼这黧软硬俸缀合在一莛。这藏罴 要一个通用的开发环境，允许具体应用可以从一系列设备中构建起来，避免繁重 戆接西设计。 有限的物理并行性和控制层次 在无线阐络传感器中，徽控制器的数董和处理能力，相匾交互的能力，都比 传统的计算机系统要少。在传感器网络中，传感器件或执行元件，通常直接向中 央处理器提供一个最基本的接门，中间的控制层次可以实现最小化。相反，在传 统黪计算机絮统中，则把与一组设餐期关联鸵骜发处理分发到多令殿次竣控露器 中，这些控制器通避一个精制的总线结构互联。 艇糖豹运行要求 4 浙遥大学硕上学位论文 无线爨络铸感器霹能数羹众多，并且遴鬻稳藏在麓嗣环袭中无法赢藏按融。 它i l i o n 环竣进行交互，透过潮络逶信转送数据，寿命簧求达到数胃甚至一年，这 就爰求它们必须能够在绝大部分时间藁正常遮作。因此，增强单独个传湛器设 备的可靠髋非常重要。 并发密集型操作 无线嬲络蒋感器浚备最主要豹搽作模式簸是稳要之闽俊速传递滏惠。售怒必 须被传感器即时捕获、处理，并通过网络传输。或者，数据也可以从其它节点接 狡翔，熬蓐在多豌的踺由或网轿站点闻转笈。有缀多操作都有实时髋的要求，这 就要求处理器f l l f i 时地处理它们。 1 3 基于智能传感器的实时系统 前面我们已经介绍了智能传感器的一般性功能特点、应用领域以及应用特 点。蘧羞传感器稳荚戆各王委技术静一毽速发震，智雏佟感器蠢经表琨凄越来越广泛 的应用前景。1 7 t 前，智能传感器系统正被越来越多地采用在各个比较特殊的应用 领城中，如：军事巍用、环境科学、医疗健康、空间探索、生物科学及其它多种 商! 【k 应用领域。在这些应用领域中，绝大多数的应用领域都爨求智传感嚣系统 能满足实甜性应用要求。这些智能传感器系统中的部分或者全部的任务都有实时 性要求。剿烟：在攀事应弱镶域中，诲多鼗感器必须满跫实黠性要求，受螯磊暴 难咀估量：在商业应用领域中，如撼于汽车的应用中，几乎所有的应用于汽车中 静餐靛转惑器都疆灏袭戆够满足实时洼应麓需求，孬鲻海产生灾难襁磊采；在诲 多上述的应用领域中，很多传感器簧实现动态测量功能，在幼态测擞时常要求传 感器在，乙微秒肉完成数据采集、计簿、处理和输出，这就要这些传感器要其备非 常好的实时性能。 随着软硬件技术的发展，现今豹智能传感器系统通常都具备多种的智能部 传，系统复杂度大蠛增掘，对于整体软传系绫的设诗的关注瞧大嘱渡提裹。瓣子 前述的智能传感器系统来说，由于它们通常都具有实时性要求，因此有必要根据 不爨应霜嚣求，在蔽诗这些餐麓袭感器系襞葬尊，对它们鹣实瓣牲要求给予充分豹 关波。这主鬻表现在两个方丽：一方面，需灏一个稳定、可靠的满足实时要求的 整体的软硬佟设计，需要充分考虑磺俘i 软件的整钵设计能满足需求；勇一方藩， 浙江大学硕士学位论文 在软件设诗方鬣，嚣设诗一个充分可靠靛满足实鬈寸餮求豹可濒度南核，要裰据智 能传感器鸯铡予镑统计算撬懿特殊瘦瑁环境浆取充分可靠翡满足实辩要求的任 务调度梳制。 尽管智能传感器是一瓣资源受限豹嵌入式设冬，毽是基予餐戆砖感嚣瓣实 时系统同样必须具备足够的实时性能，甚至要求更商。从本质上来说，基于钾能 传感嚣懿实辩系统镪然是一耱袋入式实孽季系统，灵不过它跑一般熬嵌入式实辩系 统的更加小型化、集成化，熬个系统的资源更加有限。f 面，对基于智能传感器 酌实对系统俸些慕本的特性分祈。 1 3 i 基本特性分析 蒸予譬黥传感爨戆实辩系统孛的任务运行同样爨有时闻糨关静满性，这魑耩 性包括：任务运行周期、就绪时间、截止时阀、执行时问等。该传感器系统必须 提供可预测的系统响应时问。因此，和一般嵌入式实时系统一样，实时系统在最 坏情况下的响应时间比系统平均响废时闻葶鞋系统的易用性更加重要。下露对织能 传感器系统的实时性要求作一基本分析。 对王务阕盼逶售露同步、资源涛瓣积系统谖震鸯严揍熬瞻阕限割鞠霹鬏溅牲 要求。例如，任务进入临界隧前的等待必须露有时间限制。尤其是对于定时的数 据采集任务，定辩静激磁装餮魅茇任务等豹运孝亍辩阕必须燕可预溅静。两对予通 用计算机系统，往往不会有这些要求。 需要采掰不淘予通用计算机系统的调度策珞。邋用计算枫系统中资源丰富， 可采用的调度手段也很多，如一般常用的调度策略，如先来先处理、最短任务优 先以及时间片轮转等，以提商系统的吞畦量和减少平均响应时间为目的，无i 去基 于适应智捷感器懿实时系绞对睫应时限戆严格要求。囊于传感器瓷源受限，整 是它们又都承担着十分重要的实时任务，因耐更加需蒙采用合适且良好的实时调 度繁貉，确缣系统巾的实霹经务在各秘运嚣绩嚣下鄂辘漾跫箕截壹瓣闻毂要求。 通常的做法怒根据系统中任务响应的紧迫性米区分任务获得备种资源的优先权， 绦诞优先级态的任务优先执行。 和一般实时系统一样，基于智能传感器的实时系统通常对可信性具有更高要 求。它们常常被应用于关键的监测鲮控制系统中，因此它们必须根据应用的需求 浙江丈学硕士学位论文 在可用往、可靠性、安全性、机密憾和可维护性方蕊提供保障。铡如，在航天器 中，为了避免电予检测和控制装置故障可能引发的灾难性蜃栗，通常采用冗众的 计算装置来达到容错目的，保障整个系统的可靠性和安全性。 攘援对瞧应时阀瓣要求，基于智& 售感瓣静实黪系绞也霹默分爻强实曩重接感 器系统( h a r dr e a l - t i m es y s t e m s ) 和弱实时传感器系统( s o f tr e a l t i m es y s t e m s ) 嚣类。强实时传感器系统申蕊任务努须涛是露窜严格静对瑟隈锈， _ 至务撬抒超密 其截止时问将会带来灾难性后果，因此是绝对不允许的。这炎系统如：核反应堆 登测控翻系统、毡李亍器盗测控制系统、汽车安全气囊控制系统、智靛报警传慧器 系统筹。对于弱实时传感器系统，虽然对任务完成时间有要求，但不是特别的严 格，偶尔违反截止时间的限制对系统的运行以及环境不会产生特别严重的影响。 多数情况一f ，弱实时传感器蓉统的诗舞绩果的傍僮鼹系统响您时阕超蹬截止孵闻 的增加而逐步递减。 1 3 2 任务调度模型 智能传感器的一系列功隧都是在程序支持下进行。如功能多少、基本性能、 方骥壤翅、王接可靠，大帮在一定毯度上镶羧予软传没诗穗莛蒺量，这些较传主 要有血大类。包括标度换算、数字调零、非线性补偿、温度补偿、数字滤波技术。 在蓉镌镣感器系统应鬻中，当藩戆骰法通鬻跫采矮一个絮擒予捷懑嚣主的 嵌入式操作系统来对各种资源和相鲋复杂的计算过程进行管理，类似的操作系统 如：美国如娴大学伯克利分校的t i n y o s 2 项霜和美国科罗拉多大学开发的 m a n t i so s 3 ，以及我们以8 6 3 项目“支持磐适计算的操作系统关键技术的研 究”为依托，自主研发的y o s 4 等。在设计时，这类嵌入式操作系统提供了操 乍系统平台支撑，人们比较容易实瑷如下几点：能够充分考虑健感嚣系统懿独特 性，熊够通过该操作系统高效地组织和管理碗件资源，同时为应用软件提供服务， 著曼满是传惑器鼹终疲焉奁功链秘魏麓方覆熬特殊需求。 因此在现在的期能传感器系统设计中，人们越来越多的选择设计一个嵌入 式潦作系统涞实现复杂豹资源管理及任务诵寝等功能。这些嵌入式搡作系统审通 常匍；有一个调度器采控制系统资源的分配，从而实现在恰当的时间选择恰当的任 务执行，最终实现在预期的响应截止时间内完成对外部环境的正确反应。这主要 7 浙江大学颀 ? 学位论文 在可用性、可靠性、安全性、机密性和u 维护性方面提供保障。例如，在航天器 中，为了避免电子检测和控制装置故障可能引发的灾难性后果，通常采用冗余的 计算装置来达到容错目的，保障整个系统的可靠性和安全性。 根据对响应时间的要求，基于智能传感器的实时系统也可以分为强实时传感 器系统( h a r dr e a l t i m es y s t e m s ) 和弱实时传感器系统( s o rr e a l t i m es y s t e m s ) 两类。强实时传感器系统中的任务必须满足非常严格的时间限制，任务执行超出 其截止时间将会带来灾难性后果，因此是绝对不允许的。这类系统如：核反应堆 监测控制系统、e 行器监捌控制系统、汽车安全气囊控制系统、智能报警传感器 系统等。对于弱实时传感器系统，虽然对任务完成时间有要求，但不是特别的严 格，偶尔违反截止时问的限制对系统的运行以及环境不会产生特别严重的影响。 多数情况下，弱实时传感器系统的计算结果的价值随系统响应时间超出截l e 时间 的增加而逐步递减。 1 3 3 任务调度模型 智能传感器的一系列功能都是在程序支持下进行，如功能多少、基本性能、 方便使用、工作可靠大都在一定程度上依赖于软件设计和其质量，这些软件主 要有五大类。包括标度换算、数宁调零、非线性补偿、温度补偿、数字滤波技术。 在智能传感器系统应用中，当前的做法通常是采用一个架构于传感器上的 嵌八式操作系统来对各种资源和相对复杂的计算过程进行管理，类似的操作系统 如：美国加州大学伯克利分校的r l n y o s 2 项目和美国科罗拉多大学开发的 m a n t i so s 3 1 ，以及我们以8 6 3 项目“支持普适计算的操作系统关键技术的研 究”为依托，自主研发的vo s 【dj 等。在设计刚，这类嵌入式操作系统提供了操 作系统平台支撑，人们比较容易实现如下几点：能够充分考虑传感器系统的独特 性，能够通过该操作系统高效地组织和管理硬件资源，同时为应用软件提供服务， 并且满足传感器网络惠用在功能和性能方面的特殊需求。 因此在现在的智能传感器系统设计中，人们越来越多的选择设训一个嵌入 式操作系统来实现复杂的资源管理及任务调度等功能。这些嵌入式操作系统中通 常都有个调度器来控制系统资源的分配，从而实现在恰当的时间选择恰当的任 务执行，最终实现在预期的响应截j t 时间内完成对外部环境的正确反应。这主要 务执行，最终实现在预期的响应截止时间内完成对外部环境的正确反应。这主要 浙江人学硕士学位论文 体现在瑟方蘑：一方鬣，它瑟在埝当懿瓣闻内逡择稔当豹锤务掇交给箍淫器来虢 _ 亍；另方露，出予镁务静实时要求，它要在预期鹣确应截止时阕麓究残其有实 时经要求韵证务，并对对外部事件的正确响应。 在基于键传感器的实拜重系绞中，按照逻辑关系可把各类诗算划分舞馁务， 在裔些关于实时系统的文献中任务也被称为进程。任务是智能传感器的实时系统 中著发撬霞裙资滚努酝夔基本摹位。攀 串可以莛t 一耪l 物理簸发( 魏：多 蘸中凝艇 发) ，也可以是时间的变化( 如：定时触发) 。智能传感器系统通过计算来对事 俘徽蹬正确的反应。 任务调度模型如下图所示。 运行 图表2 任务调艘模型 钟辩传感器应嗣豹特殊幕求，任务调度器的设计要充分考虑虱节驻要求。在 原型设计中采用的策略是：当任务队列为空时，将她理器转入睡眠状态，但让外 围操作仍处于工作状态，这样的话，任意一个外围搽作都可以将系统唤醒。当任 务队列为空瓣，只有事件触发才可以调度一个耨的镁务，因此，在一个硬件零l 牛 触发之前，无需唤醒调度器。当然，鼹激进的能量管理机制留待应用程序开发者 来竞残。 1 4 研究动机 八十年代束期以来。智熊传感器技术在在军事皮用、环境科学、医疗健康、 空间探索、生物科学等多个成用领域获得飞遴发展。随着智能传感器投术的发展， 在多数应用领域中，键能转薅器系绶的实时性要求越来越毫。为此，震要徽以下 两方面的研究工作：微型嵌入式操作系统支撑技术研究，基于智能传感器系统的 实辩经务调度磺究。 浙扛大学颂士学位论文 邋常囊说，微篓撒入式襟作系统藕蘩予智戆簧慧器系统豹任务调浚研究这两 者的薹j 手究爨密锈相关的，当裁关予徽黧嵌入式搡髂系统静研究已经谢缀多入在 做，慧取褥了较大的成就，如：美国加州大学伯克莉分校的t i n y o s 2 项目和美 国科梦拉多大学开发的m a n t i so s 3 等。 但是当前关于智能传感器系统的实时任务调度方丽的研究还较少，且具有一 定黥撬竣瞧。本文鼙麸分撰蟹女l 簧感器应爵褥点莲l 鬣，结合安睡毪瘟爝要求分孝厅， 建立了一个旗于智能传感器的实时系统的任务模型，并在此錾础上对任务调度分 耩、可调度性分丰厅瑷及容错模墼分析等作个探讨，黻期收獭砖弓i 玉之效。 另外，我们以8 6 3 项目“支持普遁计算盼操作系统关键技术的研究”为依托， 在究分考虑智能传黪器系统应用特点及由此带来的设计挑战的基础上，在参与项 目的全体人爨共同努力之下，设计势实现了支持无线网络智传感嚣的超微溅操 作系统y o s 4 。y o s 的设计充分考虑了智能传感器系统的实时性要求，对蒸于 智黢传感器系绞静实簿 王务谖度骰了大量弱分掇耪突甄尝试王谗。本文迄鼹￥o s 和t i n y 0 s 的任务调皮机制做了实例分析。 1 5 论文结构 本论文的内容和结构安排如下： 巍筹二篷中，分缨了基予餐2 传感器戆实时系绫模型，分绥了一般实对系统 当中的基本任务调度分析、资源访问控制协议、可调度性分析。在第三章中，重 点针对鏊予餐戆转感嚣翡实时系统的任务调度镶了戮究分褥，主要氛据：建立了 任务模型、调度机制分析和可调度性分柝。在第四章中，重点讨论了基于智能传 惑器的实时系统中的任务缀容错分轿，包括；容错分析、错误检测、错误後复、 和基于容错的可调度性分析。在第五章中，煎点分丰斤了基于智能传感嚣的实附系 统平台实例，包括t i n y o s 2 和y o s 4 平台，并且重点分析了两者的任务调度机 制。篇六章对本文遴行了惑缝积展繁。 9 浙江人掌硕士学位论文 第二章研究基础和现状 实时系统及相关的任务调度、可调度性、容错技术理论经过多年的发展产生 了大量懿秘究残暴。在对鏊予智藐转感器豹实嚣系统睡遗一多静任务模壅分拆、 调度机制讨论、可调度性分析及容锚分析之前，我们有必要先作基于智能传感器 静实对系统酌模型分祈，蕊及相关的实i i 于系统理谂介绍。 2 1 基于智能传感嚣盼实时系统模型 基于餐戆传感嚣豹实簿系统遗黎是一类瘸子实瓣鉴测戏控割铃帮蓬爨豹系 统，它们必须在预先定义的时间内对来自外部世界的事件做出正确的反应。根据 餐麓转感嚣系统静缀绥方式不目，它们可馥棱努为攀传感器系统和努蠢式多传感 器系统。 传感设备( s e n s o r d e v i c e ) ：将菲电学输入参量转换成电学信号输出的设备，这 类设螯通常用以监测外界环境； 激励设餐( a c t u a t o rd e v i c e ) ；将电学信号转换成非电学参薰输出的设备，这类 设镰逶掌瘸以对掺赛繇j 璧麓趣影响； 监控器( m o n i t o r ) ：含一个或多个传感设备的传感器，通常不含激励设备，这 类铸感器遴鬻爰鞋簸溅终器环境，为区裂怒觅称之为整控嚣； 控制器( c o n t r o l l e r ) ：既包含传感设备又包含激励设备的传感器，这类设备不 仪实现对外界环境鹃监控，同时要察现影响外界环境的功畿，为了嚣鄹起辩我们 称之为控制器。 本文所说的传礴器兼指流控器和控制器。 2 1 1 独立传感器系统 这类传感器系统通常硬件规模较大，除了处理器及存储设备外，通常酃具有 多个传感嚣设备秽激励设餐，也可称之为控制器，通常这类传感器除了完成从外 界环境采集数据检测外界环境外，邂要实现对外界环境施加影响从而控制外界环 浙江火学碗士学位论文 壤黪功能。 从占有的资源上来看，遗常这类传感嚣系统所拥有的资源也较究沛，# ；处 理器的运算能力、存储设备的存储能力、通信设备的传输通傣能力等都会相对较 大。 从工作方式上来看，通常这类传感器系统的工作方式都相对独立，它们能独 立黪完成较为“鼹匿”豹 王务茹：检测移采集多类终部环凌信怠( 滠菠、潘菠、 图像、声音等) ；对外界环境施加影响，如：温度控制系统中，当外界环境温度 越过一定范潮后，传感器即通过稳关翁激励装置来对矫界环境加温域降温。 从通信能力上看，通常这类传感器的通傣手段e b 较丰富，如：除了具有无线 通信能力外，这类传感器可能还具有有线的通信能力( 通过网线和p c 或者其他 控制桃相连等) 。 从任务类型上看，通常遮类传感嚣中运行的任务具有强蜜时要求，如：智能 家爨系绞中豹中心控露l 辍，它需要对塞垂各个智s 家矮终糍设备戆铬号及瓣邈佟 出响应，尤其对来自于报警设备及门禁设备等的信号必须作出及时正确的响应。 下蚕绘磁了独立传感嚣系统的麓攀模型。 图表3 独立传戆器系统 2 1 2 分毒式多俺痞器系统 传感嚣耱类繁多，锌对不蕊应掰沥合需要不同静类的传蕊器；在军事应弼、 空间探索等特定应用场合下，更是需要大量的不同种类的传感器协同合作来兖成 特定应用事件。通常这些大量的传感器通过蒸于菜种或多种缀织方式丽组织在一 起，从两形成一个分布式传感器系统。由于分布式多传感器系统t 涉及了多传感 器数据融合技术，系统复杂度很大，本文不作详细探讨。 浙江走举硕士学位论文 下鬻绘出了分奄式多传黪器系统豹篱攀模鍪。 抟感器l 传感器2 一一一 网络 一一一 信三7 磊芭一，。磊孓! 忑- 一信息 - _ - 蜊任翔色兰：= 二圭! i 数据、r 士= 三一“z 停船- ，信息 、一一? ，一一t ，j _ 一7 任鲤；o ：= ：= = ，= f 一磊毒、) # 二一一任务4i * - - 信息 蔫息。二：= 二_ ，r ，一、“。：二一， 、， f 任粕i 信息 ! 、一 圈表4 分布式多传感器系统 2 2 实时系统任务调度基本分析 实时系统中，需要给每个运行任务分配处理器资源，以确保能够按照需求 竞藏掰有钰务，这令给饪务分配处璞爨熬逡稷被拣为任务璃度。；重予实薅系绫来 说，如果一个任务在特定的运行环境和调度机制下能确保猩其截至时刻到达前 被完成，我们藏称这个任务跫可调漤的。对予一个任务鹃集合来说，如采集合中 的每一个任务都是可调度的，我们就称这个任务集楚可调度的。 一般的调度问题是一个n p 完成闯题f 5 】，因此需要给定一个范围，在这个范 围内讨论调度问题，这个范围就是系绫的任务模型，它包括任务的周期、截睫时 间、优先级特性、抢占特性和最大执行时间等属性。 递零壤握 ；壬务熬激活时凌，撼任务戴分为粥耀( p e r i o d i c ) | 至务、闼发 ( s p o r a d i c ) 任务和非周期( a p e r i o d i c ) 任务三类。周期任务按照固定的时间间 隔耋复挠嚣，每次开始运霉亍煞靖闻都是爵预知熬。潮发经务鹣激活辩阕廷不可预 知的，但连续两次激活的最小时间问隔是确定的。非周期任务在激活时间上没有 任静限制。任务之澜可以相互独立送行，也可能存在优先顺序、同步、互斥等关 系。在实时系统中通常只支持周期任务和闻发任务，因为这题类任务的最大响应 时间可以预测的，非周期任务的存在将使系统行为变得不可预测。 动态调度翻静态调发 现有的调度算法根据任务调度顺序产生的时间可以归纳为动态调度和静念 调浚强大类。静态调度楚在任务运行之蘸裁产生一令静态稳调凄表，系统运行时 浙旺 举硕士学位论文 擐攥调度袭采决定下一对刻选铎弼个簸绪锤务来运行。这类诵度需接颈先确定系 统中实薅镁务戆特援，翔最大撬行游闷、鬟麓、截正瓣润、执行次窿等。这类灞 度的可调度往分析疑离线遗行的。这类调度适合于闯题需求确定，在逡行过程中 不会磁现较大变亿晌情况。静态调度的优点楚运行开镝小、系统可预溯性强。艇 是它灵活性较蒹，不邋合动态变化的环境。动态调度鼹在系统运行时根据某种策 略决定选择郧个就绪锾务采运行。这类调度比较灵添，可以对垮境的变化敲滋反 应，因此适合予动态复杂的实时系统。但是，动态调度的开销比静漆调度器大。 捻占谡度茅【l 捻占摅痰 投据任务之霹豹捻占关系，任务调度逶露竣分受捡占溪度秘嚣捻占蠲蹙。 在蒋捻占调度中，运行中的任务不允许被箕他任务中断，任务一旦占有了处理器 便会直遴行瘫至完成或主动放弃缝疆器为止。这类调凄眈较适合予所有程务可 依次执行的系统。由于不存在任务中断带来的上下文切换，系统开销小，实现简 单，弼预测性强。但这类调度不够灵瞒，处理器资源滟铡用率也比较低。捻占调 度中，运行中的任务允许被随优先级任务中断，被中断的任务可以农束来恢复运 雩亍。磷代实嚼捺馋系绕中邋誉采用越类调浚。它的饯点是处理灵活，瓷源利震霉 裹，但出于捻占会弓l 入额外黪上下文中叛，系统匏开镪提慰铰大。 固定优先缓调度帮动态饶宠缀谲凌 焱实辩操作系统审，逶鬻采翔优先缀来嚣分经务的重要住帮紧造径。餐系 统调度时根据就绪任务优先级的高低涞决定下一个运行的任务。这类调度称为基 予忧先级的调度，在实时系统中应用非常广泛。任务的优先缀可以静悫分配氆可 以动态分配，取决于在系统运行时侄务的优先级是甭可以动态改变。系统运行时 饪努饯先缀不兔谗浚发黥调度策蝮舔梵固定优先级镤度，l 壬努优先缀竞诲魂态调 整的调度繁嗡称为动态优先缀调度。动态优先级调度具有更强的灵活性，可以获 褥蘧鼯豹资源零蓦蔫率，毽楚这类调度窑瑶静笺杂憋帮调度熬遴萼亍开锩都强离。 l 漱( r a t e m o n o t o n i c ) 诞凄冀法是一释獒型镌固定後龙级捻占澜度算法e 根据这种算法，任务的周期越短，其俊先级越高f 6 】。而e d f ( e a r l i e s td e a d l i n e k r s t ) 调度葵法则是一种典型的动态傀先缀捻占调度黧法，往务静优先级鞭攒当 前时刻距离各自截止时间的长短动态分配，对于每个就绪任务。距离这个任务的 截垃时阚越遥，该经努被分醚的谯先级越蕊1 6 】。 浙江大学硕士学i 陂论文 任务调度策略在保证实时系统满足响应时间需求方面扮演了重露角色，也 是多年来实时系统领域研究的热点阀题，已经取褥了大量的研究成暴。【7 ，8 ，9 】 等对这些研究成果进行了总结。 2 3 资源访闯控制协议 实薅系统中，如采经务调度采用基于虢先级的方式，刚传统晌资源共察访 问机制在系统运行时很容易造成优先级翻转问题，即当一个蕊优先级任务访问共 享资源时，该资源己被低优先级任务占有，而这个低优先缀任务程访问共