（计算机软件与理论专业论文）基于Minicore操作系统的跟踪调试环境的设计与实现.pdf

摘要 跟踪调试是定位程序中的错误并修正其错误的过程，是软件开发中必不可少 而耗时甚大的环节。 从上层看，操作系统是一个功能的集合，其中跟踪调试环境是为上层应用 程序提供的一组功能接口，用于查看和调整系统资源的分配情况。 跟踪调试环境的搭建对于构建一个完整的操作系统是是十分重要的。它既 是编程用户完成应用软件开发的必备工具，也是帮助系统设计人员查找系统漏 洞分析系统瓶颈的重要手段。 本论文的工作即是针对实验室设计开发出的一种基于服务体执行流模型的 操作系统设计并实现相应的跟踪和调试环境。 本文首先阐述了跟踪调试环境对于开发一个完整操作系统的重要作用，然 后对比进程线程模型详细阐述了服务体执行流模型及其相关的一些基本概念 如：端口、小端口以及服务体间通信等。在此基础上，论文针对跟踪调试环境 的设计和实现进行了如下工作： 1 服务体执行流模型下跟踪调试模型的建立。首先分析进程线程模型下 的进程跟踪抽象出进程跟踪模型，然后参考陔模型提出了服务体执行流 模型下的任务跟踪模型； 2 服务体执行流模型下相关调试原语的定义。首先总结出跟踪调试环境下 的一系列调试原语，再结合服务体执行流的概念，对服务体执行流模型 下的调试原语定义出相应的语义解释： 3 跟踪调试环境的详细设计。在上述工作的基础上，结合具体的跟踪调试 过程详细设计了跟踪调试的每一个环节，确定了所需要的所有结构和功 能： 4 跟踪调试环境在m i n i c o r e 操作系统上的实现。在m i n i c o r e 第三版原型 系统上设计并实现了该操作系统的跟踪调试环境。 5 最后通过测试用例对所设计的跟踪调试环境进行了检验。 本文的主要特色体现在以下两个方面： 1 针对服务体地址空间彼此隔离的特征，实现了多地址空间的跟踪。 2 消除了内核级调试和用户级调试的差异，能根据需要方便得进行模型变 换。比如针对嵌入式的需要，只要在服务体通讯中加入远程通讯协议就 变换成了远程调试模型。 本论文所介绍的跟踪调试环境己被集成于m i n i c o r ev 3 0 操作系统中。 关键词：服务体执行流任务跟踪调试 摘要 a b s t r a c t t r a c k i n ga n dd e b u gi su s e dt of i n da n dt oc o r r e c tt h em i s t a k e so fp r o g r a m s i ti s i n d i s p e n s a b l ea n dv e r ye x p e n s i v ei nt i m ef o rs o f t w a r ed e v e l o p m e n t o p e r a t i o ns y s t e m ( o s 、i sr e g a r d e da st h es e to ff u n c t i o n si nh i g hl e v e l a st h e i m p o r t a n tf u n c t i o n ，t h et r a c k i n ga n dd e b u ge n v i r o n m e n t ，i su s e dt op r o v i d ef u n c t i o n a l i n t e r f a c et oa p p l i c a t i o np r o g r a m s t h ea i mo ft r a c k i n ga n dd e b u gc a nb ea b s t r a c t e d t h ee x a m i n a t i o na n dm o d i f i c a t i o no f s y s t e mr e s o u r c e s sd i s t r i b u t i o n t h eb u i l d i n go f e n v i r o n m e n tf o rt r a c k i n ga n dd e b u gi sn e c e s s a r ya n do b l i g a t o r y t oac o n t a c to p e r a t i o ns y s t e m f r o mo n eh a n d ，i ti si n t e g r a n tc o n d i t i o nf o rs o f t w a r e d e v e l o p e r t of i n ds y s t e m 。sb u ga n dt oa n a l y s i ss y s t e m 。sb o t t l e n e c k t h i st h e s i se x p l a i nf i r s t l yt h ei m p o r t a n c eo ft r a c k i n ga n dd e b u g i n ge n v i r o n m e n t f o rai n t a c to p e r a t i o ns y s t e m t h e ne x p o u n da m p l yt h es e r v a n ta n de x e c u t i o nf l o w m o d e i ( s e f m ) a n di t se l e m e n t a r yc o n c e p t ，l i k ep o r t ，s u b p o r ta n dc o m m u n i c a t i o n b e t w e e ns e r v a n t b a s e do nt h i st h e o r y , t h ew o r k sw ed i di nt h i st h e s i sa r ea sb e l o w s ： 1 b u i l d i n g t h e t r a c k i n g m o d e lf o rs e r v a n ta n de x e c u t i o nf l o w m o d e l f i r s tw eb u i l tp r o c e s st r a c k i n gm o d e lb yr e s e a r c h i n gp r o c e s s t h r e a d m o d e l ，t h e nw eb u i l tt a s kt r a c k i n g m o d e lb a s e do ns e r v e n t b o d ya n d e x e c u t i o nf l o wm o d e l 2 t h ed e f i n i t i o no fd e b u gp r i m i t i v ef o rs e f mi sp r e s e n t e d f i r s ts u mu pt h e d e b u gp r i m i t i v e f o r p r o c e s st r a c k i n g ，t h e n n e wd e b u gp r i m i t i v ea r e p r e s e n t e d 3 t h ed e s i g no ft r a c k i n ga n dd e b u g i n ge n v i r o n m e n t a l ls t r u c t u r e sa n d f u n c t i o n sa r ep r o p o s e di nd e t a i lf o rt h ei m p l e m e n t a t i o no f t r a c ka n dd e b u g 4 a n t r a c k i n ga n dd e b u g i n ge n v i r o n m e n to nm i n i c o r eo p e r a t i o ns y s t e mi s i m p l e m e n t e d 5 a tl a s t , s o m ee x a m p l e st ot e s tt h en e wt r a c k i n ga n dd e b u g i n g e n v i r o n m e n ta r ed e s i g n e da n du s e dt ot e s tt h ee n v i r o n m e n t t h em a i nc h a r a c t e r i s t i c so f t h et h e s i sa l e ： 1 i nv i e wo ft h ef e a t h e rt h a tt h ea d d r e s ss p a c e so fd i f f e r e n ts e r v a n t sa r e i s o l a t e de a c h o t h e r ，t h e t r a c k t h r o u g hm u l t i - a d d r e s ss p a c ei s i m p l e m e n t e d 2 t h ed i f f e r e n c eb e t w e e nk e r n e ld e b u ga n du s e rd e b u gi sd i s p e l e d ，s ot h e 2 摘要 a l t e r n a t i o no fm o d e lc a nb ee a s i l yf o rd i f f e r e n tn e e d s i fw ew a n to u r m o d e ls a t i s f yt h ee m b e d d e da p p l i c a t i o n ，w ej u s tn e e da d dar e m o t e c o m m u n i c a t i o np r o t o c o lt ot h es e r v a n tc o m m u n i c a t i o n t h et r a c k i n ga n dd e b u g i n ge n v i r o n m e n tp r e s e n t e di nt h i st h e s i sh a sb e e ni n t e g r a t e d i nm i n i c o r eo sv e r s i o n3 k e y w o r d ：s e r v e n t b o d y , e x e c u t i v ef l o w , t a s k , t r a c k i n g d e b u g 3 参考文献 文中图和表格的目录 图2 1 进程线程模型示意图 图2 2 执行流模型示意图 图2 3r a m 文件进程空间关系图 图2 - 4r a m 文件进程空间关系图 图2 5 执行流服务体模型 图2 6 服务体组织分布图 图2 7 服务体、端口、小端口关系示意图 图2 8 服务体端口变换 图2 9 消息传递 图2 - 1 0m i n i c o r e 3 结构 图3 1 进程状态转换图 图3 2 进程的生命周期 图3 3 进程跟踪模型 图3 - 4 任务状态转换图 图3 5 任务树 图3 - 6 任务管理的功能实现 图3 7 任务间消息通讯 图3 8 任务间地址空间的共享读写 图3 - 9 任务跟踪模型 图3 1 0 调试接口设计图 图4 1 全局任务队列 表格4 1t a s k 结构 表格4 2 全局任务队列指针 表格4 3 l a s h 表结构指针 表格4 - 4 任务访问服务体数组 表格4 5 局部任务列表 表格4 - 6 测试结果一 表格4 7 测试结果二 5 6 心m佗d”m”加”幻巧勰如砣强驼 甜铊钙钉钇 中国科学技术大学学位论文相关声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究 工作所取得的成果。除已特别加以标注和致谢的地方外，论文中 不包含任何他人已经发表或撰写过的研究成果。与我一同工作的 同志对本研究所做的贡献均己在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权， 即：学校有权按有关规定向国家有关部门或机构送交论文的复印 件和电子版，允许论文被查阅和借阅，可以将学位论文编入有关 数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名： 主生重 幺p o7 年g 月，与日 致谢 致谢 在本文完成之际，首先要衷心感谢我的导师龚育昌教授。在该论文的选题、 研究和撰写过程中，龚老师悉心指导，并提供了优越的学习工作条件。在三年 的研究生生活里，龚老师多次细心的指导我在求学的道路上前进，传授给我许 多宝贵的知识和经验。龚老师不仅在学习上耳提面命，在生活上也给与了无微 不至的关怀。龚老师认真、严谨地工作作风，不断追求创新的治学理念，宽容、 和蔼的为人深深的影响和教育了我，必将成为我终生受益的宝贵财富。她渊博 的学科知识及敏锐的科学洞察力在我心里树立起无比尊敬的地位。 在三年的研究生学习期间，信息处理实验室的各位老师和同学给了我很多的 帮助和支持。同学之间坦诚直率，团结迸取，经常互相交流讨论的学习氛围让 我获益良多。感谢周学海教授、李曦教授对我的帮助和支持。感谢已经迈入工 作岗位的李宏，吴明桥，汪文俊，朱建民，王立刚、齐冀、朱洲同学，他们先 前的研究和指导对于我的成长和学习起了很大的帮助。感谢陈香兰同学在学习 和生活上对我的指导。感谢张晔、时正、贾永泉、唐玲、张敏、乔磊、毛熠璐、 吴吴、马宏星，刘海峰，韩春晓，周志鹏，冯小天等同学在学习过程中给了我 许多中肯的帮助与合作，感谢他们让我看到自己的不足。 特别感谢我的父母，他们身在千里之外的家黾仍然不忘定期电话督促自己珍 惜在科大的学习时光。 最后，感谢计算机系所有的老师，谢谢你们对我们学生的关怀和爱护。 第一章绪论 1 1 研究背景 第1 章绪论 1 1 1 跟踪调试环境和操作系统的关系 操作系统从结构上可以抽象为运行模型和存储模型两部分，前者描述了物 理c p u 运算能力的使用方式，后者描述了内存、外存的组织方式。操作系统的 发展经历了一个由无到有，由小变大的“进化”过程的。最初只有一台裸机， 紧接着有了b i o s 管理相应的硬件单元，后来有人编写了自己的程序取代b i o s 的作用，再后来有人编写了实现其它高级功能的程序，最后演变成为我们今天 看到的功能强大的软件集合。可见，操作系统是软件开发过程中的产物。同时 如今软件的开发又离不开操作系统提供开发平台，所以操作系统和软件开发是 相互依存的关系。 跟踪调试是定位程序中的错误并修正其错误的过程，是软件开发中必不可少 同时又占用时间比例最大的环节。 环境一词是针对操作系统的用户来说的，是指操作系统提供给用户的一组 功能的集合。如：运行环境、网络环境、编程环境等。是系统功能完整性的必 要组成部分，是衡量系统可用性的标志。 跟踪调试环境作为用户编程环境的核心组成部分，是指操作系统为了实现 用户在自己系统上完成软件开发而向用户提供的一组功能接口。 由于跟踪调试的对象应该是操作系统中运行着的某个抽象实体，包括一个 应用软件，一个进程，一次网络会话，甚至是一个操作系统等等。所以跟踪调 试环境的设计依赖于揉作系统，特别是依赖于操作系统的运行模型。 同时，操作系统又是一种比较特殊的软件，它的设计开发过程之中既需要 依赖开发平台的调试环境，又需要设计适合自己平台的丌发调试环境。 可以说，跟踪调试环境的搭建是实现系统平台上应用程序丌发和完善系统 自身功能的前提工作。 1 1 2m i n i c o r e 操作系统对跟踪调试环境的需要 进程，线程模型是目前使用最普遍的运行模型。凡是以进程线程抽象作为运 行模型的操作系统都必然存在系统级和用户级这样的两级划分。位于系统级的 代码和功能的集合称为系统内核，位于用户级的代码和功能的集合称为用户级 进程。程序( 代码和数据的集合) 在系统内核里是以执行流( 数据流驱动代码 流) 的形式运行的，在系统内核外面则是以进程线程抽象的形式运行的。 ： 墨二垩丝堡 一 这种进程线程抽象显然是为了满足用户级程序的并发需要所提出的，但同 时为了维护这种抽象需要花费巨大的系统开销。为了平衡这种开销实验室设计 开发出了m i n i c o r e 操作系统，该操作系统取消了进程线程的运行抽象，打破了 系统内核与用户级程序间的分隔，按照系统实现功能的不同抽象出不同的服务 体对象，整个系统只有执行流一种运行模型。运行模型的改变决定了我们必须 重新设计实现操作系统的跟踪调试环境才能实现系统平台上的软件开发。一个 高效的调试环境不仅可以加快上层应用程序的开发，也是帮助操作系统自身变 得稳定，便于移植，便于裁剪的重要保证。 1 2 跟踪调试技术 1 2 1 跟踪调试的发展 由于跟踪调试与操作系统有密不可分的联系，所以操作系统的发展也促使 着跟踪调试技术的进步。 1 2 1 1 单内核操作系统上的跟踪调试 单内核操作系统是指具有一个很大的内核，内核为系统内所有的进程所共 享。系统服务如文件、网络、内存管理、设备管理以及运行所需要的关键数掘 等均放在内核中，用户程序不能直接对其进行访问和操作。内核为用户提供了 入口点，定义了功能规范和参数传递规范。 单内核操作系统出现得很早，u n i x 1 , 2 , 3 , 4 , 5 】以及各种变体均采用这种技术， 系统的耦合程度很大，系统的内核部分以执行流方式运行，用户程序使用进程 线程方式运行。单内核系统上，在进行用户程序开发调试时，跟踪调试的对象 是用户级进程，采用调试进程监控被调试进程的传统方式。对于内核系统的开 发调试，跟踪调试的对象是系统内核，调试的方法普遍采用远程调试【6 , 7 , 8 】即： 通过在被调试机器的系统内核里插入s t u b 桩代码，用另一台机器通过远程协议 进行调试。 1 2 1 2 微内核操作系统上的跟踪调试 在单内核操作系统之后产生了微内核操作系统。与单内核操作系统相比， 微内核操作系统在结构上也有一个为所有进程所共享的内核，不同的是几乎所 有的系统服务都从内核中移出，使用核外的用户级进程实现。 微内核的运行模型和单内核相似，核内使用执行流模型，核外使用进程l 线 程模型。微内核系统上，用户程序的开发调试依然是调试进程监控被调试进程 第一章绪论 的方式即可完成。对于微内核系统的开发调试，由于大部分系统服务都以用户 级进程的形式存在，所以其地址空间相互隔离，这势必将给我们调试时错误的 定位带来一些麻烦，但一旦完成了错误的定位，是属于系统服务的就按照传统 进程调试进行，是内核代码错误，就采用远程调试。 1 2 1 3 分布式操作系统上的跟踪调试 如果把微内核的系统服务从单机分散到多台机器组成的网络中去，各个网 络节点管理着各自的机器资源，但不提供任何独立的功能接口，整个网络表现 出一个操作系统的性质，有全局的文件系统、设备管理、网络通信等系统服务， 这样就构成了分布式操作系统。分布式操作系统上运行的程序称为分布式程序， 其对应的程序进程是在网络中不断迁移的，不同的时刻将处于不同的节点上， 但由于各个节点共享它们的资源，又提供着完全相同的功能接口，所以不会影 响程序的执行。 分布式操作系统由于它的复杂性和不可重现性，使得对于分布式程序的调 试十分困难，是目前研究的热点和难点，一般的开发调试都只有依靠在各个节 点上建立比较完善的目志服务【9 , i o , i u 2 ，记录下各个节点的变化情况，再通过同 志重现先前的运行过程，对运行过的程序完成调试。另外也有通过动态插装代 码实现动态交互调试的技术【】”，但动态插入代码会影响到程序运行的性能以及 给程序的运行过程带来更多的不确定性，所以该技术还处于进一步研究之中。 1 2 1 4 嵌入式操作系统上的跟踪调试 随着大量嵌入式设备的发明和使用，嵌入式操作系统也迅速发展，嵌入式 系统的程序调试也是目前研究的热点，由于嵌入式操作系统的硬件资源都十分 有限，所以其调试程序都往往无法直接在系统上运行，常采用的调试手段有：1 ) 设计调试开发板针对具体处理器类型上嵌入式系统的丌发。2 ) 使用虚拟机技术 模拟嵌入式操作系统开发环境i1 4 ，”，1 6 】。3 ) 在调试主机与被调试机问加入j t a g ( 边界扫描测试电路板) 实现调试1 1 7 , 1 9 】。 1 2 1 5 针对网络应用的跟踪调试 随着网络的发展，以及网络操作系统的产生，使得网络跟踪的对象变得相 当的丰富。在有线网络里，针对网络入侵、网络攻击，为了跟踪到攻击节点主 机产生了一系列的网络跟踪模型和网络跟踪技术【1 9 在无线传感网络里，跟踪 目标主机移动情况是重要的研究内容【2 4 】。另外还出现了大量网络协议的跟踪和 调试技术2 0 2 1 0 2 ，2 3 1 。 第一章绪论 1 2 2 跟踪调试的分类 调试按照调试代码插入的时间不同可以分为静态调试和动态调试。静态调 试是在被调试程序编译执行前向程序内码里加入调试语句实现查看和控制程序 的执行；动态调试是在程序执行过程中对程序进行控制和运行信息的查看。静 态调试对调试对象的运行效率影响小，但交互性弱，调试效率低：动态调试交 互性好，但对调试对象运行效率影响大，对于具有不可再现性的程序调试效果 差。 调试按照调试对象代码的形式不同可以分为源代码级调试和二进制级调 试。前者是直接在程序的高级语言代码上进行调试，后者是对源代码编译生成 的二进制代码进行跟踪调试。源代码级调试更便于程序员使用些，系统要实现 源代码级的调试必须首先建立一个二进制代码和源代码之问一一映射的符号表 【2 6 1 。 调试按照调试目的的不同可以分为逻辑调试和性能调试。前者是用于判断 程序的逻辑正确性的。后者是用于帮助用户分析程序执行的瓶颈的。一般串行 程序的调试只要求逻辑调试。对于并行程序，不仅要求逻辑调试还要求性能调 试，因为人们采用并行的方法进行计算是为了提供程序的性能的，所以需要性 能调试把并行程序在同步、负载平衡、通讯以及不完全并行方面的丌销情况统 计给用户，帮助用户理解和提供并行程序的性能。 1 2 3 跟踪调试的对象 跟踪调试的对象大致可以分成三类：硬件，固件和软件。硬件方面既可能 是系统组成里的某一设备也可能是网络中某一节点机。固件多指嵌入式系统的 片上调试【”】。软件则可细分成对系统内核的调试以及对用户级程序的调试。 1 2 4 软件调试的实现形式 由于目前的操作系统普遍以进程线程作为软件程序的运行抽象，所以目前 的软件调试都是指对进程、线程的调试i2 9 1 。目前的操作系统对进程的调试一般 提供两种形式的支持：一是提供一组调试用的函数接1 2 1 ，比如l i u n x 提供的p t r a c e 系统调用 3 0 1 ：一是提供一个与进程对应的文件系统，比如l i n u x 提供的p r o e 文 件系统【2 7 2 8 l 。 1 3 小结 无论跟踪调试技术怎么发展，它都必须依据操作系统平台提供的跟踪调试 环境开发的，无论操作系统怎么变化，它的跟踪调试环境都是围绕着系统的运 第一章绪论 行模型搭建起来的。尽管现在的操作系统种类繁多，调试开发技术复杂多变， 但运行模型还是以进程线程模型为主，跟踪和调试的本质还是针对进程的跟踪 调试。跟踪调试的基本命令依然都是单步执行、设置断点、断点查看等。 本论文相关工作展开的原因就是运行模型发生了变化，所以相应的跟踪调 试环境需要重新设计，工作的重心在跟踪模型的设计上，新的模型在既继承了 进程线程模型跟踪的部分特点的同时又具有新的功能特点。相信此工作一定能 促进m i n i c o r e 操作系统的完善工作。同时也指明了跟踪调试技术发展的一个新 方向。 1 4 论文组织 本论文的研究目标是为一种建立在新运行模型下的操作系统m i n i c o r e 操作系统搭建相应的跟踪调试环境。从而保证m i n i c o r e 操作系统能向用户层提 供完整的开发平台。加快系统应用程序的开发，方便系统内部错误的诊断。 本项目组提出了一种基于服务体执行流模型的新型操作系统构造方式 【4 4 , 5 2 , 5 7 】，该系统同时表现出单内核和微内核操作系统的特点，在确保一定的效 率的同时又降低了系统功能的耦合程度，既可以作为单机系统使用又能满足分 布式网络应用的要求。 本文对如何设计和实现基于服务体执行流模型的跟踪调试环境的关键技 术进行了研究，包括跟踪调试原语的定义，跟踪调试流程的设计，跟踪调试环 境的设计以及最后在m i n i c o r e 操作系统上的实现。具体内容安排如下： 第一章绪论。本章介绍了研究背景和研究现状。在明确了跟踪调试环境在操作 系统中的位置和作用后，认识到跟踪调试的设计对操作系统运行环境的 依赖。通过对各种跟踪调试技术的研究总结出跟踪调试中的基本需求。 第二章服务体执行流模型。本章介绍本实验室提出的一种新型的操作系统构 造模型服务体执行流模型。该模型对操作系统做了新的抽象，以 服务体作为操作系统的存储模型，以执行流作为操作系统的运行模型。 服务体作为构造操作系统模块的基本单元和同类资源管理的集合，取代 传统操作系统中的进程概念。执行流作为描述系统运行情况的逻辑抽 象，更加接近机器实现的物理本质。 第三章执行流模型下的跟踪调试环境的设计。本章提出了与执行流运行模型相 应的跟踪模型，并详细描述了相关的跟踪调试语义和具体的模型架构。 第一章绪论 该章首先通过分析传统进程线程运行模型下的跟踪调试抽象出一般的 跟踪模型。然后针对执行流模型重新构造了新的跟踪模型，定义了新的 跟踪调试原语。最后针对编程用户的应用设计了相应的跟踪调试接口和 使用规范。 第四章m i l l i c o r e 操作系统上跟踪调试环境的实现。在第三章工作的基础上， 我们对m i n i c o r e 第三版的代码进行了修改和扩充，增加相应的标志位， 结构体和函数接口。最后我们以进程线程作为运行模型的m i n i c o r e 第 二版和以服务体执行流作为模型的m i n i c o r e 第三版进行对比测试，衡 量跟踪调试环境的实现情况。 第五章结论。本文研究工作的总结以及进一步工作展望。 第二章难务体，执行流模型 第2 章服务体执行流模型 本章介绍本实验室提出的一种新型的操作系统构造模型服务体执行 流模型【“j 。该模型对操作系统做了新的抽象，以服务体作为操作系统的资源占 有和运彳亍环境的单位，以执行流作为操作系统的运行实体。传统的分配资源和 等待运行调度的单位进程被分成资源和运行两个概念，分别放到服务体和 执行流里。 操作系统的构造方式对系统的性能有很大影响。操作系统的功能可分为四 类：资源管理、数据计算、数据存储和输入输出。其中数据计算和数据存储是 核心功能。数据计算功能主要由c p u 提供。数据存储功能主要由内存和外存提 供。对c p u 资源和内存、外存资源的利用对应出一个操作系统的运行模型和存 储模型，两者相互制约，又相互配合，共同决定了系统的性能。 2 1 运行模型 在计算机系统中c p u 提供了运行动力，这种推动力最直接的体现在指令寄 存器的改变上。当计算机上电后，复位逻辑电路将一个固定的地址写入指令寄 存器中，c p u 从该地址处读取并执行指令。在指令的执行过程中c p u 硬件逻辑 根据所取到的指令完成状态的改变，这种改变由两部分组成：( 1 ) c p u 自身状 态的改变，包括指令寄存器、通用寄存器、状态寄存器以及控制寄存等的改变； ( 2 ) 内存内容的改变。指令寄存器的更新也就是通常所说的“指令地址加一 或“转移地址生成”，系统运行的推动力正是由这种自动更新所形成的。在这种 力的推动下c p u 按顺序在指令序列上移动，我们称之为“执行流”。在执行流 的流动过程中c p u 不断的改变自身和外部的状态，这就是我们通常所说的“程 序的运行”。 用户可以通过指令对执行流的流动轨迹进行控制，除此之外中断和异常也 可以改变执行流的轨迹。为了形成一种统一的视图，由中断和异常造成的执行 流轨迹的改变可以等价的看成由系统硬件向代码序列中插入跳转指令而造成 的：执行流所转向的位置由系统默认或通过事先的设定而决定。从执行流的角 度来说，程序代码的意义实际上是在于引导执行流在代码序列上进行流动并在 流动的过程中改变系统的状态。 在计算机操作系统中，如何设计灵活、高效的运行模型一直是非常活跃也 是非常重要的研究领域，对操作系统体系结构和运行效率有重要的影响。从早 第二章服务体执行流模型 期的单道程序模型、多道单线程并发程序模型到近代的线程轻量级进程、用户 态线程、续体( c o n t i n u e s ) 、轨迹容器( l o c i c o n t a i n e r ) 、主动消息( a c t i v e m e s s a g e ) 、 线程迁移等，无不是研究如何有效的使用硬件平台提供的计算能力设计高效灵 活的运行模型，提高系统的运行效率、扩展能力和并发度。 2 1 1 进程线程模型 目前主流的操作系统模型是进程线程模型，大部分操作系统如u n i x ， l i n u x ，w i n o d w s ，m a c h 3 1 ，3 2 ，3 3 ，c h o r e s 3 4 ，3 5 ，s p r i n g 3 6 ，3 7 ，3 8 ， a m o e b a 3 9 ，4 0 ，4 1 ，l 4 都采用该模型。进程是程序的一次执行过程。是系统进 行调度和资源分配的一个独立单位。早期的进程既是资源拥有的单位也是调度 的单位，为更好的使用多处理器平台所提供的计算能力提高程序的并发度，引 入了线程作为调度的基本单位。从逻辑上看每一个线程代表了一个虚拟c p u ， 这种虚拟c p u 与物理c p u 具有相同用户级指令和寄存器集合。内核按照时问 片规则将执行流分派给每个虚拟c p u 以充当其运行的动力，这种分派的过程也 就是通常所说的线程调度。由于是虚拟的概念，用户可以对线程动态的进行包 括创建、挂起、阻塞、唤醒、睡眠、删除等在内的复杂操作。线程的创建操作 相当于虚拟c p u 的上电复位，复位地址为所指定的线程入口地址。 进程 内存集合 线程 进程问共享内 节点 节点 节点 图2 - 1 进程线程模型示意图 进程线程模型在隐藏了具体物理平台结构，提供了便利清晰的编程模型的 同时也具有明显的缺点： 线程之间的通讯是异步的。每一个线程通过检查和改变共享内存的值来决 定自身或其它线程的动作。这种特性不可避免的带来信息处理的延时或丢失， 通常这种延时不具备确定性因此降低了系统的实时性。为了避免轮询所带来的 第二章服务体执行流模型 昂贵开销，现有操作系统使用了“事件”机制。线程平时睡眠在某个“事件”( 一 个共享变量) 上，当“事件发生”( 共享变量的值发生预期的变化) 时被唤醒。 由于通讯是异步的，所以线程在处理事件的时候无法感知到该事件再次激活从 而造成事件的丢失或延迟处理。在进程线程模型下解决这个问题非常困难，往 往使得系统结构晦涩难懂，不易证明、调试和维护。过多的辅助线程还会增大 系统的运行开销。 进程线程模型忽略了线程之间的本原关系。线程是虚拟c p u ，无论系统中 有多少线程都是由物理c p u 提供的执行流来完成的。线程模型完全隐藏了这一 点，从用户的角度看线程完全是异步、独立的实体，只能通过共享内存进行数 据共享。这种抽象的结果给系统造成了很多不必要的睡眠、唤醒以及调度等操 作，增加了运行开销。所谓线程间的异步关系很多情况下是假设的，而为了这 个假设不得不浪费大量的计算资源。 进程线程模型屏蔽了底层信息，不利于编写高效的程序。线程是虚拟c p u ， 运行的时候调度到物理c p u 上从而获得执行流。线程机制为用户隐藏了物理 c p u 的信息，用户编程的时候不必考虑系统中真实处理器的数量，可以透明的 获得对多处理器的支持。但这种透明性也使得用户丧失了对线程调度的参与机 会，线程与物理c p u 的对应关系只能在调度器预测的基础上决定。由于调度器 是系统频繁使用的部件，复杂的算法将带来可观的系统丌销而失去实际使用的 可能。 2 1 2 执行流模型 执行流代表了c p u 对机器码的执行。计算机系统从上电刀= 始到关机结束， c p u 一直进行取指、执行、取指、执行的系列动作，c p u 进行的这种沿指令代 码流动的轨迹称之为执行流( e x e c u t i o nf l o w ) 。系统中每个c p u 提供一个执行 流，如果采用超线程( h y p e r - t h r e a d ) 技术则每个c p u 可以提供一个以上执行 流。执行流是一个连续的概念，不会被阻塞，挂起，停止或撤销，开机时从处 理器的上电复位地址产生到关机时消失。 进程线程模型的提出是为了向编程用户提供一个清晰的编程模型，从而将 底层执行流的概念给隐藏掉了。由此也带来的了巨大的系统开销。为了减少带 来的这些开销，我们很容易便想到使执行流概念面向编程用户，用执行流模型 替代进程，线程模型作为系统的运行模型。 第二章服务体，执行流模型 执行流 冈 i! ! 竺 图2 - 2 执行流模型示意图 执行流模型的结构框架比较接近真实的物理模型，可以说是机器指令流的抽 象形式。由上面示意图可以看到，执行流模型上，软件程序的概念会有所变化， 操作系统和用户程序之间区别很小，甚至没有任何区别，都是加载到r a m 里 的代码和数据，在物理c p u 的推动下，不停的从r a m 中取出，完成指令计算 后又存回到r a m 中。 执行流模型在消除进程线程模型缺点的同时也给用户编程带来了新的挑 战，进程线程模型下各进程具有各自私有的地址空间，而执行流模型下不同程 序的地址空间是采用统一地址空间还是采用某些手段进行相互地址空间的隔 离，这些都是相应提出了服务体模型作为存储抽象的原因。 2 2 存储模型 计算机存储系统是按层次组织的，自上而下依次为c a c h e 、r a m 、本地外 存，网络外存等，访问速度越来越低，存储容量越来越大。从所存储的数掘的生 命期来看c a c h e r a m 是易失性的，本地外存网络外存具有持久性；从管理的角 度看，c a c h e 与r a m 之间是从属关系。c a c h e 内容是r a m 内容的一个子集，二 者之间的数据交换由硬件完成，软件只能对c a c h e 中的内容进行有限的操作， 如锁定、刷新、冲洗等等。r a m 、本地外存、网络外存之间的数据交换由软件 完成，不同的算法实现了不同的策略，相应的也就形成了不同的存储模型。 第二章服务体执行流模型 同运行模型一样，存储模型对操作系统的体系结构、运行效率有重大的影 响，关系到用户程序模型，文件、设备以及虚存管理等方方面面。另一方面操 作系统的存储模型和运行模型紧密相关，二者配合才能最大限度提高系统性能。 由于且前操作系统普遍采用进程线程作为运行抽象，因此存储模型不可避免的 受到该框架的制约。 2 2 1 私有多地址空间存储模型 与进程线程抽象对应的存储模型就是私有多地址空间存储模型，不同的进 程拥有自己私有的进程空间。u n i x 、l i n u x 3 0 , 4 2 1 、w i n d o w s n t 等都采用该模型 来构造存储系统。采用这种模型的操作系统维护地址空间和文件两种不同的抽 象，通过这两种抽象将内存、本地外存和网络外存等实体联系起来。本地外存 和网络外存被视为平行的地位，操作系统把它们组织成文件为程序员提供的数 据的持久存储。地址空间的抽象是在硬件的支持下实现的，不同地址空间相互 隔离。地址空间的内容由文件来提供，一个地址空间通常依赖于多个文件的内 容。对文件的访问即可以通过传统的文件读写方式进行，也可以通过文件映射 机制转换为对内存的访问。地址空间、文件空间相互独立，程序员必须显式的 在二者之间进行数掘传递。这种传输通常比较复杂，相同的对象在二者之中的 存储格式也可能有较大的差别，这一切都要由程序员编程实现。 图2 3 表示了私有多地址空间中r a m ，本地外存、网络外存之问的关系。 从图中可以看出，系统存储层次可以分为两层：地址空问和文件，r a m 可以看 成二者之间的c a c h e 。操作系统负责这种c a c h e 的维护，这个过程就是通常所说 的页面交换。 r a m 文件 “ 垂圃 豆固 图2 - 3r a m 文件进程空间关系图 私有多地址空间模型的优点是具有很高的运行效率。由于具有硬件的支持， 这种模型在有效性检查方面开销很低。但是当数据包含内嵌指针等复杂数据结 构时( 如链表、树、图) 该模型在数据共享方面面临很大的困难，因此不同的 第二章服务体执行流模型 空间之间只能共享一些简单的数据。 2 2 2 单地址空间存储模型 与私有多地址空间存储模型相对的是单地址空间存储模型，在单地址空问 操作系统中，例如g r a s s h o p p e r l 4 3 1 、m u n g i t “4 5 i 、t e x a s 4 6 】、s o m b r e r o 4 7 , 4 8 1 等， 所有应用程序运行在同一个地址空间中，不同应用程序的数据在地址空间的不 同区域。该地址空间在系统启动时创建关机时消亡，具有永久性。因此较传统 操作系统，单地址空间操作系统更加容易实现存储系统的持久化。 单地址空间操作系统具有许多优点：( 1 ) 可以在不同的进程之间共享指针 类型的数据【4 9 , 5 0 , 5 11 ；( 2 ) 方便了进程之间对复杂数据结构的共享；( 3 ) 可以高 效的使用基于虚存的c a c h e 【3 1 3 2 ，3 3 】；( 4 ) 容易实现数据存储的永久性【5 2 ，5 3 ，5 4 , 5 5 t 5 6 1 ： ( 5 ) 通过共享空间传递数据从而提高了进程通信的效率【4 2 】，降低了上下文切 换的开销等等。单地址空间操作系统的主要缺陷是：( 1 ) 程序员不能使用绝对 地址编程；( 2 ) 难于实现传统操作系统( 如u n i x ) 仿真器以兼容现有应用程序 【4 2 ，”j ；( 3 ) 由于所有对象全部存放在同一个地址空间中，系统虚存的分配和回 收算法很复杂，算法的时间复杂性和空间复杂性都很高【5 8 , 5 9 , 6 0 , 3 6 , 3 7 , 3 8 , 6 1 】；( 4 ) 存 储保护机制不仅很复杂，效率也不高【3 5 ，3 9 ，4 0 】；( 5 ) 需要6 4 位处理机的支持，3 2 】； ( 6 ) 分布环境下的效率不高等。 图2 - 4 r a m 文件进程空间关系图 给稗” 二 二 二二至堕亘 r a m 它件 o 型巫丑 豆巫丑 同私有多地址空间模型类似，单地址空间模型中仍然维护了文件和地址空 间两个数据存储抽象，r a m ，本地外存、网络外存之间的关系与私有多地址空 间模型相似，如图1 - 6 所示。二者之间的不同之处是： ( 1 ) 单地址空间操作系统中只维护一个地址空间对象，所有的程序均使用该地址 空间运行。 ( 2 ) 用户程序对文件的访问只通过内存映射完成。 口 第二章服务体，执行流模型 2 2 3 服务体模型 虽然与执行流接近硬件本质特点相对应的是单地址空间存储，但由于单地 址空间存储模型有对处理器硬件的要求及会对用户编程带来巨大影响，所以执 行流模型不太可能选择单地址空问存储作为存储模型。 进程线程模型下地址空间是以进程为单位划分的，不同进程拥有不同的地 址空间。执行流模型下没有了进程的概念，又需要多地址空间管理，结合模块 化的思想，我们提出了服务体模型。 服务体模型主要由执行流，服务体和端口几个部分构成，执行流和服务体是 服务体模型的两个基本抽象。执行流是c p u 执行能力的抽象，服务体作为系统 存储能力的抽象，是代码和数据的集合体。执行流的流向由服务体的代码指引， 服务体由执行流推动执行。执行流和服务体的管理由核心服务体实现。其示意 图如下： f i 罨，逶溅删饕。 图2 - 5 执行流服务体模型 服务体是系统的静态组成部分，是具有通信功能和拥有地址空间、安全控 制等资源和属性的能够完成某种功能的代码和数据集合。服务体是一种静态的 概念，其生命周期不依赖执行流，具有持久性。服务体拥有一系列端口，端口 又包含一系列小端口，服务体问通过给端口发送消息进行通信，在执行流的推动 下进行消息处理。 采用服务体模型后，操作系统不再有传统的内核概念，传统内核的基本功 能由核心服务体实现，提供服务体问通信机制、并发机制、中断异常管理等。 核心服务体是系统的一个关键模块，逻辑上相当于传统操作系统的内核，但是 它不要求运行在内核态。核心服务体主要提供服务体间通信机制、执行流和服 务体的管理、中断和异常等基础服务，以及维护关键抽象的数据结构。 除核心服务体之外，其他系统模块也以服务体的形式存在，如内存管理服 务体、虚存服务体、文件系统服务体、网络系统服务体、运行环境服务体等都 第二章服务体执行流模型 是独立的服务体。用户开发的程序有两种存在方式，一种是以独立的服务体形 式存在，如服务器程序和驱动程序。另一种是以运行环境服务体的用户态部分 存在，如一般的客户程序。运行环境服务体用来兼容现有操作系统的语义或者