（计算机科学与技术专业论文）可扩展操作系统任务无关调度模型的研究与实现.pdf

国防科学技术人学研究生院学位论文 摘要 传统操作系统的调度模型和框架都是基于任务类型的特殊要求进行设计的，它们在高 效支持特定任务类型的同时，也牺牲了其他类型任务的性能。任务特定的调度逻辑作为内 核的一部分，与内核其他代码紧密耦合，导致整个系统缺乏良好的通用性、可移植性和可 扩展性。鉴于现有调度模型的这些不足，根据可扩展操作系统垂直体系结构的总体要求， 本文提出了一种新的调度模型可扩展的公平调度模型，模型中的调度器被分成两个层 次：任务无关层和任务相关层。任务相关层根据任务的特性提出相应的调度要求，经准入 控制后由任务无关层通过调度执行保证其特定的调度要求。 在维持一个基本内核的同时，任务相关的调度要求以下载到核内运行的方式保证调度 的效率。论文首先介绍了任务无关调度模型的总体框架，并分别从任务无关和任务相关两 个层次，分别讨论了调度模型的设计与实现。然后分析了准入控制在模型中的作用及工作 过程。并从可扩展性、公平性、安全性、q o s 的保证及效率方面对调度模型作了较深入 的探讨，并提出了进一步的研究工作。 关键词：可扩展操作系统，调度，准入控制 国防科学技术大学研究生院学位论文 a b s t r a c t a l lt h es c h e d u l i n gm o d e l sa n df r a m e w o r k so ft r a d i t i o n a lo p e r a t i n gs y s t e m sa r ed e s i g n e d b a s e do nt h es p e c i a lr e q u i r e m e n to fd i f f e r e n tt a s k s a l t h o u g hs u p p l y i n gt h es p e c i f i e dt a s k sw i t h h i 曲e f f i c i e n c y ，t h e ys a c r i f i c et h ep e r f o r m a n c eo ft h eo t h e r s t h em a i nr e a s o n i st h a tt h e t a s k s p e c i f i e ds c h e d u l i n gl o g i ci sac o m p o n e n to ft h ek e r n e la n d i st i g h t l yc o n n e c t e dw i t ho t h e r c o d e s t h u s ，t h ew h o l es y s t e mi sl a c ko fg e n e r a l i t y , p o r t a b i l i t ya n de x t e n s i b i l i t y a st h es h o r t c o m i n g so ft h es c h e d u l i n gm o d e l ，t h i sp a p e rp r e s e n t sak i n do fb r a n d - n e w s c h e d u l i n gf r a m e w o r k ，a c c o r d i n gt o t h er e q u i r e m e n to ft h ee x t e n s i b l eo p e r a t i n gs y s t e mi n o r t h o g o n a la r c h i t e c t u r e t h ef r a m e w o r ki sat a s k i n d e p e n d e n ta n df a i rs c h e d u l i n gm o d e l ，w h i c h i sd i v i d e di n t ot w ol a y e r s ：t a s k - d e p e n d e n tl a y e ra n dt a s k i n d e p e m e n tl a y e r t h et a s k d e p e n d e n t l a y e rb r i n g sf o r w a r dt h ec o r r e s p o n d i n gr e q u e s t s a f t e rt h ea d m i s s i o nc o n t r o l ，t a s k - i n d e p e n d e n t l a y e rg u a r a n t e e st h es p e c i f i e ds c h e d u l i n gr e q u i r e m e n tb ys c h e d u l i n gp r o c e s s e s w h i l e k e e p i n gab a s ek e r n e l ，t h ec o d eo ft a s k d e p e n d e n t s c h e d u l i n gi sd o w n l o a d e di n t ot h ek e r n e lt o p r o v i d et h ep e r f o m a a n c eo fs c h e d u l i n g a tf i r s t ，t h ep a p e ri n t r o d u c e st h et o t a lf r a m e w o r ko ft a s k i n d e p e n d e n ts c h e d u l i n gm o d e l a n df r o mt w ol a y e r so ft a s k i n d e p e n d e n ta n dt a s k d e p e n d e n t ，w ed i s c u s st h e d e s i g na n d i m p l e m e n t a t i o no ft h es c h e d u l i n gm o d e l t h e n ，w ea n a l y z et h ef u n c t i o n so fa d m i s s i o nc o n t r o l a n di t sp r o c e s so f w o r k i n g i nt h em g d e l m o r e o v e r , w ee x p l o r et h es c h e d u l i n gm o d e ld e e p l yo n t h ea s p e c t so fe x t e n s i b i l i t y ，f a i r n e s s ，s a f e t y , g u a r a n t e eo fq o sa n de f f i c i e n c y , e t c a tl a s t ，w e c a r r yo u tt h ef u r t h e rw o r ki np r o g r e s s k e y w o r d s ：e x t e n sb eo p e r a tin gs y s t e m s c h e d uiin g a d m is sio rc o n t r o ：= = 圣圣坠兰垒查查兰翌塑生堕兰竺堡苎 图目录 图2 1u n i x 时钟中断处理程序的算法6 图2 2u n i x 系统进程描述符结构图7 图2 34 4 b s d 系统进程结构图7 图2 4o p e n b s d 进程组数据结构图 9 图25o p e n b s d 信号量及其相关数据结构1 2 图2 6 基于h s f q 的层次c p u 调度框架1 5 图2 7 基于h s f q 的层次c p u 调度框架1 7 图2 8y z k e r n e l 总体结构图1 9 图31 系统调度框架示意图2 2 图32y z k e r n e l 中时钟中断服务程序算法示意图2 4 罾33 任务无关调度程序s c h e d j i s 的算法2 4 图34 准入控制的算法示意图2 6 图3 5 传统的进程状态转换圈，2 7 图3 6y z k e r n e 的进程状卷转换图2 8 图3 7m o d u l e 的主要数据结构2 9 图3 8c a p a b i l i y 数据结构2 9 图3 9 任务无关调度框架工作示意图一。3 0 图3 1 0 任务无关调度框架工作示意图：二 一3 1 图3 nh a r d c l o c k 与s o f t c l o c k 的关系 ，3 4 图41w a k e u p 算法 图5 1 调度周期变短可能引发的性能降低 + 3 8 4 6 国防科学技术大学研究生院学位论文 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论又题目： 互芷庭攫佳歪箕堡盎垂差塑鏖搓型曲煎巍生塞丑 学位论文作者签名：j l ：l 盈型8日期：。v 年，2 月，产丑 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阀；可以将学位论文的全部或部分内容编八有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存。汇编学位论文 ( 保密学位论文在解密后适用本授权书。) 学位论文题目： 宴芷匮握住亟红壁盘垂基塑鏖丝型曲盟童兰塞堡l 一 学位论文作者签名：j 堇叠1 8 日期：和口啦年，- 月，卜日 作者指导教师签名：1 l ；i 日期：m f 年，j 月，啦日 国防科学技术大学研究生院学位论文 第一章绪论 1 1 课题研究背景 操作系统的形成已有四十多年的历史，经过6 0 年代、7 0 年代的大发展时期，到8 0 年代已经趋于成熟。但随着v l s i 和计算机体系结构的发展，它仍在继续发展【lj 。操作系 统作为裸机与应用之间的桥梁，为了适应不同的计算机体系结构并满足不同类型应用的需 求，从最早的单道批处理系统到后来的分时系统、实时系统、嵌入式操作系统和网络操作 系统，目前的操作系统已经是五花八门，种类繁多。 但是，贯穿计算机科学的历史，有一个永久的观点，就是当酊的操作系统是不充分的 【34 5 6 9 ，叫。很多文献都使用了一些典型的例子来说明操作系统充斥着不恰当、低效的抽 象f 2 3 ，7 ，8 3 0 , n ，坨1 。而事实上也正是这样，作为虚拟机和资源管理器的操作系统【l 引，一直 处在硬件条件和应用需求的矛盾之中。现有的操作系统无论是u n i x 、 w i n d o w s 9 8 2 0 0 0 x p n t 还是l i n u x ，总是能适应一些体系结构和应用却又对另一些应用 无能为力。 从系统的角度来看，面对不断发展的体系结构和不断出现的应用需求，赢得市u n i x 内核常常引入新的补丁，其内核不断膨胀i 。微软的w i n d o w s 操作系统则想为所有的用 户构建一个一劳永逸的平台，又要使用简便、界面美观，所以越来越复杂，而其正在开发 的下一代操作系统l o n g h o r n 因为采用了新的通讯架构，并引入了新的图像显示引擎和新 的文件搜索系统，导致惊入的资源要求，主频4 g - - 6 g h z 的c p u 、2 g b 的超级内存和 1 t b 的超级硬盘成为它的基本配置【1 ”。而另一方面，不断拓展的应用领域又要求操作系 统在目前有限的硬件条件上满足各种特别的需求，多媒体应用要求计算机系统提供一定的 实时和带宽的保证，电子政务领域更强调系统的安全性，远程专家系统要求提供数据和程 序的高效远程共享，网络游戏服务则要求能支持更多的在线用户连接，正是这些不断变化 的应用需求推动着计算机科学的不断发展。 这种现状与应用的差距，促使人们不断从体系统结构上来对操作系统进行全面的反 思，面对应用与需求都在不断变化的情况，操作系统能否尽可能做到以不变应万变，在经 历过单内核、微内核、面向对象操作系统的研究以后，构建一个在资源和应用上都具有高 度灵活性和可扩展性的操作系统成为一部分人的梦想，也是激发本课题开展的源动力。 最近的十多年犀，出现了相当数量的可扩展操作系统原型，其风格各异，性能和结构 参羞不齐，其中也不乏优秀者，如n e m e s i s 、s p i n 、e x o k e r n e l 等。这些不同的尝试及新 技术的大量使用，使可扩展操作系统从体系结构到实现机制等各个方面，都与传统的操作 系统有了很大的差别。从总体上来看，这些已有的实验系统有的只具有可扩展操作系统的 部分特征，有的只是为了某一类的特定应用而丌发，总是存在着这样那样的不足。但f 第1 页 国防科学技术大学研究生院学位论文 是这些典型的实验系统，为可扩展操作系统在理论上和实践上，作好了各方面的准备和铺 垫，才使本文能够在前人研究的基础上充分利用操作系统设计方面的新技术，以降低资 源抽象、分离资源管理的策略和机制，构建一个全新的能运行的安全的可扩展操作系统内 核y z k e r n e l 。 1 2 课题研究内容 本课题是可扩展操作系统内核y z k e m e i 项目的一部分，主要内容是以可扩展操作系 统的要求来实现c p u 资源管理，即在可扩展操作系统的垂直体系结构框架下，最大可能 地向应用暴露资源，设计并实现一个具有高度可扩展性的高效的调度模型。主要工作包括： 分析解剖o p e n b s d 3 5 阿核中与时钟及进程管理、调度相关的代码。 对具有代表性的实时调度技术和分时调度技术作深入的研究。 在对现有操作系统作综合分析的基础上，研究分析可扩展操作系统的基本思想及 其c p u 管理的主要问题及其解决办法。 研究e x o k e r n e l 系统关于降低资源抽象的思想，根据策略与机制分离的理念，实 现任务无关的公平调度模型的接口及内核实现。 初步实现一个动态下载任务相关调度器代码的接口函数。 采用基于份额的准入控制策略来实现内核的调度安全和任务q o s 的保障。 对实现的调度模型从可扩展性、公平性、安全和作了必要的分析和讨论。 1 3 论文结构 本文是对课题研究工作的总结，其主要章节有绪论、可扩展操作系统及其调度问题、 任务无关的公平调度模型、调度模型的安全设计、性能分析和改进及结束语等共六章。 论文首先简单介绍了课题的研究背景，给出了本课题组的总体研究目标及本文的研究 内容。并在回顾了可扩展操作系统发展背景及现有c p u 调度器技术发展状况的同时，讨 论了现有c p u 调度器相关的时间片策略、进程管理及调度策略，重点分析了几个典型的 调度模型的实现以及它们的局限性。 论文着重介绍了任务无关的公平调度框架的总体结构，详细讨论了任务无关层和任务 相关层的调度框架及其实现，阐述了准入控制的过程及其在公平性方面的作用，给出了实 现时的有关问题的解决办法。并从调度器自身的安全和调度行为的安全着手讨论了有关的 安全问题，介绍了本课题中安全问题的考虑。然后文章就本调度模型在可扩展性、q o s 任务的支持、安全性及可能存在的问题方面作了一些分析和讨论。 最后总结了本课题的主要工作，提出了下一步的研究方向。 第2 页 国防科学技术火学研究生院学位论文 第二章课题关键技术研究 计算机科学的发展过程是一个不断追求完美、不断创新的过程，各种新的体系结构 和大量新技术的引入，使现在的操作系统具有多样性的特色，然而，在目前已有的系统中， 很多优秀的操作系统不是受制于硬件条件，就是受制于应用的特点，很难能够为多种的硬 件条件和应用提供一种通用而又高效的系统。然而，现有的系统及其它们已经成功采用的 技术和机制，是今天乃至以后所有研究操作系统者宝贵的财富。 2 1 可扩展操作系统概况 近几十年来，为了解决操作系统性能和可扩展性方面，人们直进行着不懈的努力和 探索，比较有影响的是面向对象操作系统和微内核操作系统的提出。 面向对象操作系统更多的是指一种框架1 4 “，如t h ef l u xo s k i t 和c h o i c e s 等。t h ef l u x o s k i t 包含一个启动步骤、个最小的p o s i x 环境，内存管理和d e b u g 支持，每个组件都 可由设计者修改。而c h o i c e s 则把各部分都当作一个子系统，如内存管理、进程管理、文 件存储，异常等都直接由面向对象的框架而来，系统的资源、机制策略都当作一个类中的 实例通过类的继承来实现。应用的调整通过类的动态加载来实现。 微内核系统将部分应用相关的策略从内核抽取到应用层，并且在管理上为内核与应用 之间及应用与应用之间定义了固定的高层接口，其特点是维持一个尽可能小的核，系统的 服务都运行在用户级。内核通过u p c a l l 来调用这些服务。但是不可避免的是，微内核系统 中的应用存在大量的用户层和核心层之间、以及地址空间之间的跨越，这些域的跨越引起 了上下文的频繁切换，严重影响了系统的整体性能。另外，微内核的应用在域的跨越中可 能导致调页错误或是t l b 越界，严重影响系统性能。 上世纪九十年代人们又提出了可扩展操作系统( e x t e n s i b l eo p e r a t i n gs y s t e m ) 的概 念。可扩展操作系统定义为：一个可扩展操作系统提供一组机制和接口使得应用能按照其 特定的需求裁剪系统行为口8 1 。也可以理解为能够动态增加新的服务或者调整已有的服务 行为，不会对系统的错误隔离造成影响的操作系统【3 6 】。可扩展操作系统一般包括三个部 分： 一个基本的系统，提供最基本的服务： 一个可扩展的机制，允许在基本系统上定义新的应用和服务； 一个模块的集合，可以通过可扩展机制添加到基本的系统上去，一般称之为扩展 ( e x t e n s i o n ) 。 为了保护整个系统的正确性、可靠性和安全性，可扩展操作系统对扩展部分进行了强 制性的约束： 第3 页 国防科学技术人学研究生院学位论文 易增性：对系统行为的修改只能影响到少量代码的变动； 正确性：某个应用提供的扩展不能危及整个系统的完整性； 有效性：对扩展潜在的要求是不能有较大的额外开销。使用一个扩展带来的开销 应当取决于扩展代码本身，而不是支持扩展的底层机制【37 ，3 引。 从目前已有的可扩展操作系统来看，目前有以下几种主要的扩展实现方法。 v i n o l 3 9 1 ，单内核的基本系统，它提供了完整的伯克利版本的u n i x 内核，允许 把用c + + 书写的扩展代码下载到内核，支持基于软件隔离的保护。v i n o 内核由 一组对象集合构成，通过替换和重载特定对象的方法实现扩展，扩展具有一定的 生命周期并仅限于过程化扩展。 s p i n t 4 0 1 ，微内核结构的基本系统，它的扩展代码用一种安全类型语- 言( m o d u l a - 3 ) 所写，并在线程创建时下载到内核，一旦创建，线程就能为它所感兴趣并赋予权 限的任何内核事件安装处理程序，扩展具有一定的内核生命周期，并受限于那些 提供特定服务的域所给的接口。 s o l a r i s 4 ”，传统的操作系统模式。它提供三种的扩展方式：内核的编译时配置、运 行时下载和运行时调度行为的修正。但其所有的扩展行为都必须由超级用户来 做，并且在一个内核生命周期内有效。 e x o k e m e l t m l ，库操作系统。它把高级抽象从内核剥离，只实现最基本的功能用于 向应用暴露资源的底层接口，传统的内核抽象由用户级的库来实现。e x o k e m e l 用两种方法实现扩展性：一种是修改用户级实现系统抽象的库，因为是在用户级， 所以可以任意修改，并仅限于进程内有效，其行为由硬件提供保护，但并不允许 扩展去直接控制物理资源；第二种扩展方法是直接把代码下载到内核，这种扩展 允许受限的过程扩展，并由安全类型语言和软件错误隔离来保证代码的安全性。 从几种可扩展操作系统的简单概括来看，库操作系统性质的e x o k e m e l 的理念最贴近 可扩展操作系统的实质。并且用下载代码库的方法能够大大降低跨域的通信，提供高效的 服务，与本文的总体目标的整体框架也最为接近。 2 2 1 时间片策略 2 2 调度有关的内核技术 1 时钟中断 计算机处理的很多活动都是由定时测量( t i m i n gm e a s u r e m e n t ) 来驱动的f j 4 】。与驱动 c p u 的由晶体振荡器产生的时钟不同，计算机般采用一个或多个可编程定时器 ( p r o g r a m m a b l ei n t e r v a lt i m e r , p i t ) 以内核确定的固定频率向i r q 0 发出时钟中断，两个时钟 第4 页 国防科学技术大学研究生院学位论文 中断的时间间隔，称作一个拍( t i c k ) ，内核分配c p u 给进程，是以t i c k 作为c p u 资源 的时间粒度，也就是内核分配c p u 时的最小单位。时钟中断通知内核一个时间段过去了， 下一个时间段为谁服务由内核决定。操作系统都对时钟中断的频率作了定义，通常在内核 中都用h z 来定义。对大多数系统，这个值一般是1 0 0 ，即每秒发出1 0 0 个时钟中断，但 不同的系统在不同的硬件条件下有所不同，如l i n u x 系统在康柏的a l p h a 版本下这个值为 1 0 2 4 。 2 时间片 c p u 的时间粒度是t i c k ，但操作系统每次分给进程( 或应用) 的并非只是一个t i c k ， 因为每次进程切换都会导致上下文切换等比较费时的操作，为了增加程序执行的连续性， 提高c p u 工作效率，一般让进程运行几个t i c k 才把c p u 让给其他的进程。时间片的取值 是由各个系统自己决定的，不同的系统其时间片的t i c k 数不同，b s d 4 4 中是4 个t i c k ”， 而u n i x 则建议时间片取1 0 0 毫秒，l i n u x 在时钟中断频率1 0 0 的情况下是2 0 个节拍， 即2 1 0 毫秒【1 4 1 ，o p e n b s d 3 5 中也是4 个t i c k 。 3 与内核有关的几个时钟 不管何种操作系统，内核必须与几种时钟打交道：实时时钟( r e a lt i m ec l o c k ，r t c ) ， 时间标记计数i 器( t i m es t a m pc o u n t e r , t s c ) 及可编程间隔定时器。尽管在不同的操作系统 中其名称可能有所不同，但总的功能是相近的。 实时时钟( r t c ) r t c 独立于c p u 和其他芯片，由电池供电，经常是一个 m o t o r o l a l 4 6 8 1 8 或其他等价的芯片，它能在i r q 8 上以2 8 1 9 2 h z 的频率发出周 期性的中断，一般用它来获得时间和日期，内核也可以能过0 x 7 0 和0 x 7 1 i o 存 取r t c ，配置或更改时间。有的系统也可以通过对r t c 编程用作定时器，当r t c 到达某个值时激活i r q 8 线，产生一个定时器中断。 时间标记计数器( t s c ) 从p e n t i u m 以后的8 0 x 8 6 微处理器都包含了一个6 4 位 的时闻标记计数器( t s c ) ，并且可以通过汇编语言指令r d t s c 读取这个寄存器， 它在每个时钟信号到来时加l ，它的值是初始化以来经过的时钟信号的节拍数， 操作系统可以用它来获得更精确的时间测量，用于统计资源的使用情况。 可编程间隔定时器( p i t ) 上文已经提到，此处不再赘述。 3 时钟中断服务程序 在操作系统初始化完成以后( 即i r q o 的初始化完成以后) ，每个时钟中断都会引发 一系列的操作，这些操作主要完成以下功能： 重新启动时钟，为下一次中断作准备。 按内部定时器调用有关内核函数。特别是那些c a l l o u t 表中有定时要求的函数。 第5 页 国防科学技术大学研究生院学位论文 更新时问、同期及资源使用统计数。 对进程提供运行直方图分析的能力。 在有软时钟中断请求时，向进程发送定时软中断信号。 执行进程的调度工作。 一个典型的u n i x 下的时钟中断处理程序的算法如图2 1 所示【1 7 】。 算法c l o c k 输入：无 输出：无 重新肩动时钟；，使在下一个t i c k 时能再次中断 i f ( c a l l o u 浓非空1 ( 修改c a l l o u t l 问； 如果时川已刮。安排确度c a l l o u t 函数； 】 r ( 区与图分折己打 ：) 记下中斯时刻的p c 值： 收集系统统汁信息； 收集本进程统计信息； i f ( 自上拢执行此浯旬米已经阍过一秒，而中断不足在临界代码区 ) f o r ( 系统中所有进程1 ( 如祟济动的话修改闹钟时问t 修改c p u 的使用量： l fd 韭程枉用户奄执行) 修改进年芏优先数； j ) 图2 1u n i x 时钟中断处理程序的算法 在o p e n b s d 3 5 下，时钟中断处理的主要工作由s y s k e r n k e mh a r d c l o c k o 来实现并且用专门的资源时钟来统计资源利用情况，其频率用p r o t h z 表示，而进程所 用资源情况则用s t a t c l o c k 0 来负责统计，其频率用s t a t h z 表示，调度器每秒钟的调度频率 用s c h e d h z 表示，一个进程每次被调度到时分配到的t i c k 数相当于h z s c h e d h z ，可近似地 看作是时间片的长度。 2 2 2 进程管理 1 进程结构 进程是对f 在运行的程序的一种抽象t 1 3 】，它包含自己的程序计数器、寄存器和变量 的当前值。操作系统维持个数据结构称作进程描述荷，一般是一个t a s ks t r u c t 类型结构， 它包含了与一个进程相关的所有信息，通常包括很多有关进程的有关信息以及一些指向子 结构的指针，常见的子结构有进程组标识、用户认证、内存管理、信号操作等。不同的操 第6 页 国防科学技术大学研究生院学位论文 作系统其进程描述符并不完全相同。以u n i x 为例，它的进程描述符由两部分组成：进程 表项和u 区，其中进程表中的域是内核可存取的，而u 区中的域只能由正在运行的进程来 存取，且只有在创建一个进程时，内核才为其分配u 区空间。较为完整的u n i x 的进程描 述符如图2 2 所示。 图2 2u n i x 系统进程描述符结构图 在4 4 b s d ( 参见附录) 系统中，进程结构与u n i x 略有不同，为支持多线程共享一 个地址空问及其他资源，它把进程表项和用户结构中保存的部分进程状态移出到一些单独 的按状念类型归类的子结构中，甚至把系统调用参数和错误返回也移了出来，去掉用户空 间中的所有的全局变量，进程结构本身缩短到其原来大小的四分之左右。这样做的原因 是想把对每个线程都需要分配的空间缩减至最小【1 8 j ，以降低线程管理的开销。4 4 b s d 系 统中的进程结构如图2 3 所示。 进程标识 一子结构引用叫进程组+ _ 刮 会话 调度信息 一子结构8 i 用叫 进程认证+ _ 叫 用户认证 进程状杏 一子结构引用叫 空闻_ 一r e s i 曲1 1t 信号状志一子结构引用1 文件描述符+ _ 1 空件 躁踪信息 子结构引用刊 瓷源跟翻 机器状态 统计 定时器 j 信号攥作 进程内按拽 2 进程状念、队列和进程组 用户结构 图2 34 4 b s d 系统进程结构图 第7 页 国防科学技术大学研究生院学位论文 进程表项中的进程状态域标识着进程的当前状态。从理论上说，所有进程都有三种状 念：即运行念、就绪态和阻塞态a 但实际系统上进程状态域的值不止三个，以4 4 b s d 为 例，进程状态分为五种，见表2 1 。 表2 - 14 4 b s d 进程状态取值及描述 状态值描述 s i d l 进程创建时的中间状态 s r u n 可运行状态 s s l e e p 等待事件 s s t o p 进程暂停或被跟踪 s z o m b 进程终止时的中间状态 为提高内核查找进程的效率，操作系统使用多个链表或队列来帮助定位进程，这些 链表或队列有：z o m b p r o c 、a l l p r o c 、r u nq u e u e 、s l e e pq u e u e 、p _ _ p g l i s t 、p _ p p t r 、p _ c h i l d r e n 、 ps i b l i n g s 等等。其中与进程状态有关的是z o m b p r o c 、a l l p r o c 、r u nq u e u e 、s l e e pq u e u e 。 z o m b p r o c 与a l l p r o c 链表是完全互斥的，进程状态值为s z o m b 的进程放到z o m b p r o c 。否 则放在a l l p r o c 里：最重要的两个队列是r u nq u e u e 和s l e e pq u e u e ，只有状态值为s r u n 的 可运行进程爿+ 放在r u nq u e u e 队列里，状态值为s s l e e p 的被阻塞等待事件的里程放在 s l e e pq u e u e 队列里，暂停却不等待事件的进程则不属于任何一个队列，这两个队列也是互 斥的，但这两个队列的数据结构不同，m i l lq u e u e 的t 4 y , l 顷序取决于进程的执行优先级， 而s l e e pq u e u e 则是一个散列表，只有放在r u nq u e u e 队列里的进程才可能被调度运行。 链表p _ p p t r 、p _ c h i l d r e n 、p _ s i b l i n g s 分别用来表示父进程、子进程和兄弟进程的回溯 和递推关系，系统通过这些链表关系直接找到与此进程相关的进程，而不必去搜索所有的 进程。 在o p e n b s d 3 ，5 和l i n u x 中，都用p i d h a s h 散列表来提高进程查找速度，散列表的元 素个数相当于系统允许的最大进程数，表项中包含指向进程控制块的指针。为处理散列冲 突，又将对应散列表中同表项的所有进程的p i d 组成一个双向链表。内核同时提供函 数在散列表中进行插入或删除操作。 为快速寻址当前运行的进程，l i n u x 提供了c u r r e n t 宏，并用c u r r e n t - p i d 语句返回当 前i _ f 在执行进程的p i d ，在o p e n b g d 中则直接用e u r p r o c 宏表示当前正在执行进程的p i d 。 系统中相关联的进程用进程组的形式组织起来，所有这些相关联的进程都有同一个 进程组号g p i d ，g p i d 的值就是创立该进程组的首个进程的p i d 号，当一个新的进程组 创建时，内核分配一个进程组子结构，并加入到p g r p h a s h 散列表中。在进程组创建时， 4 ，4 b s d 通过s e t p u i d 调用将进程组编号设成本进程的p i d ，其他进程可用s e t p g i d 调用来 加入一个已经存在的进程组：而o p e n b s d 则是通过e n t e r p g r p 来创建或加入一个进程组。 o p e n b s d 中进程组c 语言的结构定义见图2 , 4 示。 第8 页 国防科学技术人学研究生院学位论文 s t r u c t p g r p ( l i s te n t r y ( p g r p ) p l h a s h ； ，+ l l a s b 链衷+ l i s th e a d ( ，p r e t ) p g _ m e m b e r s ； ，+ 指向进程组成员的指针， s t r u c t s e s s i o n + p g _ s e 站i o n ；严指向s c s s i o o 结构的指刳， p i d - tp g i d ；进程组号， i n t p e , a 2 b c ； ，相关的作业控制罕段+ 图2 4o p e n b s d 进程组数据结构图 3 优先级和上下文切换 现代操作系统经常通过赋予进程不同的优先级来区分任务的紧迫性和执行顺序。优 先级管理也成为进程管理的一个重要部分，大多数的多道程序操作系统的进程表项中都有 一个或几个字段表示进程的优先级。通常在开始时赋予优先级n i c e 一个初值，并在系统 运行过程中，根据已经使用的c p u 时间或者该进程已经等待的时间，按照一定的方法， 动态改变其优先级。这种改变优先级的方法，与系统具体采用的进程调度算法有关。 在4 4 b s d 及o p e n b s d 3 5 系统中，进程的调度优先级p - u s r p r i 由进程结构中的 pe s t c p u ( 最近该进程的c p u 使用时间) 和pn i c e ( 即用户定义的进程n i c e 值) 通过公 式3 1 每隔4 个t i c k s 计算一次。 p u s e r p r i = p u s e r + 盼一e s t c p u ) 4 + 2 。p n i c e ( 公式2 1 ) 其中p u s e r 是一个用户进程的基准优先级。 分时系统的c p u 在不同迸程问切换，不可避免地要对进程的上下文进行保护。u n i x 系统中，进程的上下文由它的用户级上下文、寄存存器上下文以及系统级上下文组成。 进程i 日j 的上下文切换可以分为主动( v o l u n t a r y ) 和非主动( i n v o l u n t a r y ) 两种，当进程需 要等待不可用资源时，通过s l e e p ( ) 或t s l e e p 0 进行初始化，定义一个下次唤醒时的优先级 和一个等待信道( w a i tc h a n n e l ) ，进程主动放弃c p u ，进入睡眠状态，进程同时被放入休 眠队列，直到等待的事件出现，由w a k e u p 0 唤醒，重新被调度执行。非主动的上下文切 换主要发生在进程用完了分给的时间片或是被更高优先级的进程所中断。这种切换主要通 过s w i t c h ( ) 矛l ：ls e t r u n n a b l e 0 来进行强制切换。 4 进程的创建与终止 进程执行的第一步首先是创建进程，现代u n i x 系统提供系统调用c l o n e ( ) 、f o r k ( 1 和v f o r k o 来创建进程。l i n u x 利用c l o n e ( ) 来创建轻量级进程，4 4 b s d 只采用f o r k ( ) 和 v f o r k o 来创建进程，而o p e n b s d 3 5 则支持f o r k ( ) 、v f o r k ( ) 年 1r f o r k 0 来创建进程。 f o r k 系统调用通过复制进程的地址空间来刨建一个相同的子进程( 1 8 】。f o r k 调用一般 实现下列工作： 为子进程保留虚拟地址空间。 为子进程丌辟一个进程入口。 第9 页 国防科学技术人学研究生院学位论文 将父进程的有关信息如：进程组、认证信息、文件描述符权限及信号操作拷贝到 子进程。 创建用户区域，复制父进程的用户区数据作为其初始化数据。 创建一个v m s p a c e 结构。 用写时复制( c o p y - o n w r i t e ) 拷贝父进程的v mm a p e n t r y 结构，以此束复制地址 空间。 函数自身在子进程中返回0 ，以此来区分对父进程的返回值，对父进程的返回值 是新进程的p i d 。 v f o r k 主要用在父进程与子进程不必同时运行，只需要一个地址空间的情况下，它也 使用写时复制技术实现，但它并没有为子进程复制地址空间，只是简单地把父进程的地址 空州传给子进程，并挂起父进程。子进程只分配新进程和用户结构，其他的都从父进程继 承。与f o r k 不同的是v f o r k 保证在子进程调用e x e c 或者e x i t 系统调用前，父进程不会继 续运行。其结构上的缺点是子进程得到控制权后，可以修改父进程的内容和地址空间的大 小。 o p e n b s d 和f r e e b s d 中还引入了r f o r k ，它允许创建的子进程共享父进程的文件描 述符表。这种方法是以使用不完全的进程创建方式创建共享数掘空间的进程，类似于 l i n u x 下的c l o n e ( ) ，这种方式是l i n u x 的基本线程处理方式，b s d 下可以使用l i n u x t h r e a d 的兼容库来实现这种线程。 在实际应用中，进程通过f o r k 系统调用( 或v f o r k 、r f o r k ) 创建。f o r k 后一般跟着 个e x e c 系统调用，用文件系统中的可执行程序映像来覆盖新建子进程的地址空间，然后 就丌始运行。 e x e c 系统调用是一个函数调用族，经常包括e x e c l ，e x e c v ，e x e c l e ，e x e c v e 等多种形 式，但只是调用时所使用的参数不同，底层都是调用e x e c v e 函数来实现，在o p e n b s d 3 5 下，是调用k e m _ e x e c ，c 中的s y s _ e x e c v e 0 来实现e x e c 的功能。 运行中的进程能够用e x i t ( ) 调用白行结束，也可能被信号强制终止。进程终止时都会 有一个状态码返回给父进程( 如果存在父进程) ，父进程通过w a i t 4 系统调用来等待子进 程f 勺返回。e x i t ( ) 执行时，进程状态将从s r u n 变为s z o m b ，释放所有分配给这个进程 的资源，并被从a t t p r o c 饿表中删除，放入z o m b p r o c 僵尸进程链表，统计有关资源使用情 况，有关数据放入相应的统计子结构，并通知终止进程的父进程。 5 线程 线程又称作轻量进程。越来越多的操作系统支持线程，s o l a r i s 等系统支持多个线程。 线程又可分用户级线程和内核支持的线程。用户级线程仅存在于用户级中。对于这种线程 的创建、撤消和切换，都不通过系统调用来实现，这种线程与内核无关，如i n f o r m i x 数据 库就使用了大量的用户级线程技术。内核支持线程则依赖于内核，无论是在用户进程中的 第1 0 页 国防科学技术大学研究生院学位论文 内核线程还是系统进程中的线程，它的创建、撤消和切换都由内核实i j r l 1 1 。s o l a r i s 支持 这两种线程，o s 2 和m a c h 则实现内核支持的线程。有的操作系统常把些系统进程如 页面交换、网络等任务委托给内核线程，以避免不必要的用户态上下文切换。 引入线程后，进程成为了资源拥有的基本单位，而线程成为c p u 调度和分配的基本 单位，这使传统进程的两个角色分成了两个，从而能显著提高系统的并发程度，同时，线 程自身不拥有资源，但它可以访问其隶属进程的资源。一个进程的代码段，数据段等资源 可能供同一进程的多个线程共享。进程切换时要考虑当前进程c p u 环境的保存以及新进 程的环境的设置，而进程切换只须保存和设置少量寄存器内容，并不涉及存储器管理方面 的操作，系统丌销远远降低。 o p e n b s d 3 5 提供了对内核线程的支持，内核代码中的k e m 程的建立、运行及退出的有关程序。而r f e r k 系统调用也从一定程度上支持了用户级线程 的实现。 6 进程同步 在支持多道程序的系统中，系统中经常存在多个进程，进程间可能存在资源共享或者 相互等待结果的现象，对于那些临界资源，进程必须互斥地访问才能确保数据的一致性和 正确性。进程f 刚同步控制就是为了保证进程互斥地进入自己的临界区。公认地，同步机制 应该遵循四个原则【1 1 ： 空闲让进 当无进程处于临界区时，即资源空闲时，应该允许一个请求进入临界 区的进程立即进入。 忙则等待 当已有进程进入临界区时，则所有试图进入临界区的进程必须等待， 以保证进程互斥地访问临界资源。 有限等待应该保证进程能在有效时间内进入自己的临界区。 让权等待 当进程不能进入自己的临界区时，应立即放弃c p u ，让给其他进程。 为实现同步控制，可以用软件方法也可以用硬件方法来