（计算机系统结构专业论文）视频点播分布式操作系统中任务调度的设计与实现.pdf

0 说频点播分布- 橼佧采境中住箍诮瞧的碰计| i 。啦睨 摘要 ；6 3 8 3 7 珥：i 专业：计算机系统结构 论文题目： 视频点播分布式操作系统中任务调度的设计与实现 硕士生：范明惠导师：刘心松教授 随着计算机技术的广泛应用，对分布式操作系统的需求越来越大，分析当前 国内操作系统的发展趋势，我们迫切需要开发一种属于自己的操作系统。考察信 息h j 代的市场，可以发现v o d ( 视频点播) 具有广阔的应用前景。因此，本课 题以具有开放源码的免费l i n u x 操作系统为基础，对它进行改进，针对视频点播 的特性丌发分布式操作系统，并在分布式操作系统的基础上进一步开发视频点播 服务器系统。 1 本文首先介绍了视频点播分布式操作系统的设计思想，并进一步对分布式任 、 务调度进行分析研究，设计适用于视频点播系统的分柿式调度算法：以系统中进 砟队列的长度为负载的基本标准，根据各节点负载的不同，把节点分为三种状态 ( 发送者，接收者，正常) ，定时收集系统信息，更新状态队列，调度时根据本 常点的系统信息作出决策，响应时间较小。接下来对调度算法的实现过程做了详 细的介绍。最后从通信开销、响应时间、负载平衡方差三个方面对系统性能进行 评 i 。视频点播系统其有容错功能，系统高度可靠：r 哭键间：分布式调度负载稳定的发送者发起算法通信开销响应时问 o。0。二=隧瞄瞄耍；膏，oj 、 “! i 型坐型坌塑竖丝丝丝型丝堂堡丝 a b s t r a c t m a j o r ：c o m p u t e ro r g a n i z a t i o n a n da r c h i t e c t u r e s u b j e c t ： d e s i g n & i m p l e m e n t a t i o n o ft a s ks c h e d u l i n gi nv o d d i s t r i b u t e do p e r a t i n gs y s t e m m a s t e r ：f a nm i n g h u l a d v i s o r ：p r o f l i ux i n s o n g w i t ht h ed e v e l o p m e n ta n du s i n go fc o m p u t e r , t h en e e do f d i s t r i b u t e do p e r a t i n g s y s t e mh i g h l yi n c r e a s e s a c c o r d i n gt oa n a l y z et h ep r o g r e s s d i r e c t i o ni n l a n d ，w en e e d t od e v e l o pa no p e r a t i n gs y s t e mo fo u t su r g e n t l y o nt h eo t h e rs i d e ，v o d ( v i d e oo n d e m a n d ) s y s t e mh a v eaw i d ef o r e g r o u n d , s ow ed e v e l o p ad i s t r i b u t e do p e r a t i n g s y s t e mb a s e d o n m o d i f y i n g t h el i n u x ，a n dd e v e l o pi ti n t 0 4 av o d s e r v e rs y s t e mm o r e i nt h i sp a p e r , w ef i r s t l yi n t r o d u c et h ed e s i g ni d e ao fv o d d i s t r i b u t e do p e r a t i n g s y s t e m ，s t u d yd i s t r i b u t e dt a s ks c h e d u l i n g ，a n dd e s i g nt h ea l g o r i t h m o f t a s ks c h e d u l i n g f o rv o d s y s t e m ：t a k i n gt h et a s kq u e u ea st h eb e a rs t a n d a r d ，a s s i g n i n gt h en o d ei n t o t h r e es t a t eq u e u e s ( s e n d e r , r e c e i v e r , o k ) b a s e do nt h e i rh e t l r ，g a t h e r i n gs y s t e mi n f oo n t i m ea n du p d a t i n gt h es t a t eq u e u e s ，g i v i n gt h ed e c i s i o n - m a k i n ga c c o r d i n gt ot h es t a t e q u e u e sw h e n t a s ks c h e d u l i n g i t sr e s p o n s et i m ei sv e r ys m a l l s e c o n d l yw e e x p l a i nt h e 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 ga l g o r i t h mi nd e t a i l a n da t l a s tw ea n a l y z et h e c a p a b i l i t yo fs c h e d u l i n gs y s t e mf r o mc o m m u n i c a t i o no v e r h e a d ，r e s p o n s et i m ea n d b e a rb a l a n c i n gc o v a r i a n e e t h ev o d s y s t e mh a sh i g hr e l i a b i l i t ya n dp o s s e s s e st h e f u n c t i o no f f a u l tt o l e r a n c e k e yw o r d s ：d i s t r i b u t e ds c h e d u l i n g 、l o a d 、as t a b l es e n d e r - i n i t i a t e da l g o r i t h m 、 c o m m u n i c a t i o n o v e r h e a d 、r e s p o n s et i m e 2 税凝点插静森武操作表绞中扭静弧撞的漤| ，凄地 1 l 丹! j舀 随着时代的发展，计算机技术在各行各业得到广泛的应用，操作系统作为各 种应用软件的底层平台，有着十分重要的作用和地位。操作系统的稳定性、安全 件和效率直接影响了应用软件的使用。 目前常用的商业操作系统有微软的d o s 、w i n d o w s9 8 、w i n d o w s n t ，s c o 公司的s c o u n i x ，s u n 公司的s o l a r i s o s ，苹果公司的m a c o s 等等。虽然它 们都是比较成熟的产品，而且稳定性都有保证，但是它们都是国外的产品，我们 国家不了解产品的技术细节，因此，当使用这些操作系统的计算机系统与i n t e r a c t 相连接时，我们不能保证是否会泄露一些重要的信息，也不能保证系统是否会存 在安全漏洞。有报道披露，微软的w i n d o w s 系列操作系统都为美国国家安全局 提供了“后门”。这些事情让人们开始重视自己正在使用的系统的安全性问题。 我们国家已经要求某些政府重要部门的连网机器不能使用微软的操作系统，其原 因是这些国外的商业操作系统在我们看来就像一个庞大的黑箱子。在这种情况 下，符合g n u 、g p l 的l i n u x 操作系统公开的源码对我们说来无疑是个很好的 系统，因为我们可以通过源码了解l i n u x 操作系统的实现机制从而保证它没有安 全“后门”的存在，也因为在该操作系统上已经有了很多成熟的应用能够方便地 使用。近几年，国内系统软件对l i n u x 的开发热情逐渐膨胀起来，中文化的l i n u x 有了t u r b ol i n u x 、红旗l i n u x 等等，并且它们的使用范围也在逐渐扩展。我们 研究室作为研究计算机系统结构的研究室，有必要对l i n u x 的内核结构进行一些 剖析，以便跟上社会和时代的需求。 现在是信息高速公路发展的时代，信息高速公路铺到家门口只是个时间问 题。通向家庭的信息高速公路将会改变人们的生活模式，而它最基础的应用就是 v o d ( 视频点播) 。v o d 是多媒体交互业务的统称，而不仅限于电影点播，交互 式广告、交互式视频游戏、网上交互式购物及协同工作会议系统等都属于v o d 的范畴。电影点播是v o d 业务当前最有前途、最实用的一种业务。利用v o d 系统，用户可以坐在家里的电视机前，通过遥控器和菜单，选择自己喜欢的节目， 再也不用受广告的骚扰，随意跳过或重复某些剧情，一切主动权都掌握在自己手 s i 疋税颧点播分布式撮仔最缝中往舔谤睦构礓| | 口实鼬 第一章分布式操作系统概述 1 1 操作系统简介 计算机由硬件和软件两部分组成。操作系统是直接与硬件接触的第一层软 件，可以看作是对计算机硬件系统的第一次扩充。几乎所有计算机的应用程序都 是在某一种操作系统平台之上运行的，在运行的过程中它们都或多或少地调用了 操作系统提供的一些功能。所以，操作系统在一个计算机系统中占据了特殊重要 的地位。操作系统可以定义为一组控制和管理计算机硬件和软件资源、合理对各 类作业进行调度的程序集合口o 1 2 “。 操作系统的主要功能有三个： 用户和计算机硬件系统之间的接口 管理计算机系统的资源 扩充计算机硬件的功能 根据操作系统允许支持用户数目的不同，它可以分为单用户操作系统和多用 户操作系统两类。单用户操作系统的例子有m s d o s ，g r m d o w s 9 5 等等：多用户 操作系统有s u ns o l a r i so s ，a t & tu n i x ，s c o u n i x ，l i n u xo s 等。根据操作 系统某个时刻内存中支持任务数目不同，它又可以分为单任务操作系统和多任务 操作系统。m s d o s 是典型的单任务操作系统，而w i n d o w s 9 5 是多任务操作系统， 通常，现代的多用户操作系统都是多任务系统。 在多任务操作系统中，根据对任务的调度方式的不同，还可以分为分时操作 系统和实时操作系统两大类。多数u n i x 类操作系统和m a co s 2 都属于分时系 统，分时系统能够保证每个任务都能比较公平地获得系统处理机资源，同时具有 很好的交互特征。常见的实时操作系统有i n t e g r a t e d 公司的p s o s ，m i c r o t e c r e s e a r c h 公司的v r t x ，i n t e l 公司的i r m k 以及我校微机所c e s d 的c r t o s ， 它们能在一定程度上保证任务处理的实时性。 一个操作系统，特别是多任务操作系统对计算机系统的资源管理十分重要。 7 汜迁视频点播仔稚式强 _ 最统中任务秘瞧的l 韭“| f 唼魁 ；型兰管理工作包括处理机的管理、存储管理、1 1 0 设备的管理以及作业的管理。 彩仃务操作系统中，进程是作为系统资源分配和独立运行的基本单位。进程可以 f ? 定义勾可并发执行的程序在一个数据集合上的运行过程1 2 i l 。在本文中，我们主 一，；【0 沦的是任务的调度机制，与进程调度紧密相关，进程调度是操作系统处理机 i ；理的主要内容。 操作系统处理机的管理功能主要包括进程的控制、进程的同步、进程间通讯 l ： 及进程的调度。当一个作业经过作业调度进入内存后，操作系统为它分配它所 需要的资源、建立相应的进程并把进程挂到就绪队列中等待处理机执行。当某个 进程因为等待i 0 完成或其它原因放弃处理机时，需要进行进程调度，将处理机 分配给进程就绪队列中一个合适的进程，并且让它执行。因此，进程调度可以理 解为操作系统中用于指定进程( 任务) 在系统中执行顺序的一组策略和机制。 1 一分布式计算机系统的概念及特点 t 2 1 分布式计算机系统的定义 自1 9 4 5 年计算机出现到1 9 8 5 年前后，计算机一直是庞大且昂贵的，而且各 秆类型的计算机都只能独立运行，2 0 世纪8 0 年代中期，功能强大的微处理机和 高速计算机网络开始出现，从而可以将大量c p u 组成的计算系统通过网络连接 产一起，相对于以前包括单个c p u 、存储器、外设和一些终端在内的集中式系 垆，它们通常被称为分布式系统( d i s t r i b u t e ds y s t e m s ) 。 “一个分布式计算机系统是一些独立的计算机的集合，但是对这个系统的用 户束说，系统就象一台计算机一样。”，这个定义有两方面的含义：第一，从硬件 角度来讲，每台计算机都是自主的：第二，从软件角度来讲，用户将整个系统看 作是一台计算机1 。 t 2 2 分布式计算机系统相对于集中式系统的优点 分布式计算机系统的特点在于系统中具有多台计算机且所有计算机地位平 f i _ _ ! h p2 税凝点撬静布式操作f , z l 中任务挑睦的砬i 1 | f 睡髓 十。以r 举例说明。 一个集中式的办公室中有5 个工作人员，一个办公室主任管理办公室所有事 h i ，f 属的4 个工作人员各任一职，如果某天办公室主任因事未来上班，恰恰此 j 宵事情需要他处理，则显然由于他的未上班该事情不能得到处理，因为办公室 其他人员没有权限和能力处理这件事情。 如果该办公室采取分布式管理方式，则5 个工作人员的地位是完全一样的， 每个人都有权限和能力处理办公室的事情，任意一个人不上班都不会影响办公室 的i e 常运作，即使4 个人都有事没来，仍有一个人可以处理所有的事情，当然只 是会比较繁忙而已。 由分布式计算机系统的特点可以知道，与传统的集中式系统相比，分布式计 算机系统具备许多优越的性能： 性价比：多个计算机的集合不仅能产生比单个大型主机更好的性价比， 而且还能产生单个大型主机无论如何都不能达到的绝对性能； 分布性：由于其固有的分布性，正好适应了那些涉及到空间上分散的应 用： 可靠性：它通过把工作负载分散到众多的机器上，单个芯片故障最多只 会使一台机器停机，而其他机器不会受任何影响： 渐增性：渐增式的增长方式也是分布式系统优于集中式的一个潜在的重 要原因。 1 2 3 分布式计算机系统对软件的要求 根据分布式计算机系统的定义可以知道，真正的分布式计算机系统中应该是 硬件松耦合软件紧耦合【l 】，本文谈到的分布式计算机系统是针对同构型的网络而 言的，即系统中所有的主机都是p c 机，但其c p u 、内存等可能不一样，从而对 软件有如下要求。 首先，必须有一个单一的、全局的进程问的通信机制，从而使任何进程 都可以和其他进程进行通信。在不同的计算机之间不应有不同的机制， 本地通信和远程通信也不应有不同的机制。 9 伸ji 仑正 弛颧点播兮奄l 授佧系统中任务讷噎的碰9 螟趣 其次，进程管理也必须处处相同。进程如何建立、撤消、启动、停止都 不能因机器不同而不同。 再次，在任何地方，文件系统也必须看起来是相同的。同时，每个文件 应该是在所有地方都是可见的。当然，这必须遵守保护和安全性约束的 限制。 最后，在系统的所有地方都应该使用相同的系统调用接口 1 3 设计分布式操作系统需要注意的问题 设计一个性能比较好的分布式操作系统，有几点必须注意。首先是透明性 ( 对用户甚至应用程序隐藏所有的分布特性) ；其次是灵活性，这方面微内核优 于单内核；另外还有可靠性、性能和可收缩性，以下分别做简单介绍。 i 透明性 分布式操作系统对用户应该是透明的，即由多个节点组成的分布式系统在用 户眼里只是一个节点，在一个分布式系统中有如下5 种透明性。 种类含义 位置透明用户不知道资源位于何处 迁移透明资源可以不改名的随意移动 复制透明用户不知道有多少个拷贝存在 并发透明多个用户可以自动的共享资源 并行透明系统活动可以在用户没有感觉的情况下并行发生 位置透明指分布式操作系统中的分布式文件系统具有全局目录，用户看到的 文件目录如同一台计算机上的内容，实际则是存储在多台计算机上。 复制透明指分布式操作系统中的分布式文件系统具有副本管理功能，系统可 以根据文件访问率自动增加或减少副本数，而副本的个数用户是不知道的。 迁移透明指瓷源无须更名就可自由的从一地迁移到另一地，其中包含了进程 迁移的概念。真正的性能完善的分布式操作系统应该具备进程迁移的功能，即系 统中某节点突然故障后，应能够把该节点上正在运行的进程转移到其他正常节 点，这样才能在用户不知道的情况下完成系统故障处理，做到系统中即使只剩一 1 0 i i p0 桃颧 捕， 4 , a j 豫佧最氇t 扣任务城嘘i 型 i | i 窑避 1 、| j 一xm 皇山能保证系统的1 f 常运行，这也就是迁移透i 刿的功能。到日i ) i 为l l ：， j j 】外刘进程迂移做的晟好也只能实现无通信量情况下的迁移( 电子科技人学 1 0 研究室9 0 年代初丌发实现) 。本文所讲系统针对特定的v o d 服务以任务迁 移| t l 勺形式实现了进程迁移的功能。 2 灵活性 火多数分布式系统采用微内核，微内核具有很高的灵活性，它一般只提供四 种最小的服务：进程间通信机制、某些内存管理功能、少量的低层进程管理和调 度、低层输) k 输出服务。微内核和单内核的不同在于，它不提供对文件系统、 日录系统、整个进程管理或许多系统调用的处理，许多其他的操作系统服务都作 为用户级服务器实现。 3 可靠性 建立分布式系统的目的之一就是提高系统的可靠性，基本思想是，如果一台 机器坏了，其他机器能够接替它进行工作。高可靠性的分布式系统必须有高可用 性和高安全性，另外还应该有容错功能，即一个节点出了故障，很快修复后应该 能够恢复到应有的正常状态。 4 性能 一个分布式系统的性能在某些情况下可能比单一的计算机性能略差，这是因 为分柿式系统的性能和系统中的通信紧密相关，如果通信质量很差，则系统性能 相应会很差。任务调度计算节点负载的同时必须考虑通信开销，这样才能保证系 统性能。 5 可伸缩性 可伸缩性指系统具有很好的扩展能力，可大可小。设计分布式系统时应尽力 避免导致系统瓶颈的问题，如集中的部件、表和算法等。 魁4 醯点播9 和i t 撵纷采缱a ，f t | 秘 毡f t 汁| - 啦| 豫 1 4 本章小结 本尊首先就操作系统的概念及当前市场上各种操作系统的特点作了简单介 m ，j i 出进程调度的概念，然后分析了分布式计算机系统的概念、特点以及分布 汁算机系统列软件设计的要求，最后就设计分布式计算机系统需要注意的问题 1 丁简单介绍，为以后章节作铺垫。 1 2 髓顿点接竹夺，撵停最统中任务馘琏的碰i | ，唼i 第二章任务调度的理论基础 靛掘分却式系统的定义可以知道，分布式系统由多个节点组成，这些处理机 | _ | j 纠钐l 形式可能是工作站集合、一个公共的处理机池、或是某种混合的形式。无 论足哪种形式，都要有一种算法来决定在哪台机器上运行哪个进程，这就是分布 式任务调度。对于视频点播系统，面对的是工作站或p c 机，问题主要是何时在 本地运行一个进程以及何时去寻找一个空闲的计算机运行进程。 2 1 任务调度算法概述 2 1 1 任务调度算法的分类 任务调度算法可以分为两大类：一类是不可迁移的，另一类是可迁移的。在 不可迁移的算法中，当创建一个进程时，系统就决定为该进程分配哪个节点，一 旦分配完毕，进程将一直在这个节点上运行，直至结束，无论这个节点负载有多 么严重，也不管其他节点有多空闲，它都不能迁移到别的节点上继续运行。相反， 在可迁移的算法中，可以将已经开始运行的进程迁移到别的节点上继续运行。可 迁移策略能够提供更好的负载平衡，但同时也增加了系统的复杂性，并对系统的 设计有很大的影响。视频点播系统考虑视频点播的特性，只实现了故障情况下的 任务迁移。 2 1 2 任务调度的设计目标 我们设计任务调度算法时，总是对它进行优化，希望它效率很高。不同的系 统对任务调度算法的要求也不相同，综合各种系统，对调度算法大致有以下几个 要求。 充分利用c p u ：通过任务调度，使c p u 的利用率最大化。即，每小时中， 使实际运行用户任务的c p u 周期最大，也即尽可能的减少c p u 的空闲时间，让 每个c p u 都在运行。 最小化平均响应时间：调度合适的进程到合适的节点以降低平均响应时间。 如表2 - 1 所示，有两个处理机和两个进程。如果进程1 分配到处理机1 ，进程2 分配到处理机2 ，则两个进程处理完所需平均响应时间为( 1 0 + 8 ) 2 = 9 秒。如果 进程1 分配到处理机2 ，迸程2 分配到处理机l ，则两个进程处理完所需平均响 应时间为( 3 6 + 4 ) ，2 = 2 0 秒。显然，第一种方案在平均响应时间上优于第二种方 案。 表2 - 1 ：在两个处理机中两个进程的响应时间 处理机1 处理机2 运行速度 2 0 m i p s1 0 0 m i p s 进程1 的响应时间 1 0 秒4 秒 进程2 的响应时间3 6 秒8 秒 最小化响应率：响应率是指一个进程在一台机器上的运行时间除以它在一 个无负载的标准处理机上的运行时间。比如，一个一秒的任务花了5 秒时间完 成，而一个1 分钟的任务花了7 0 秒时间运行，显然后者的响应率7 0 6 0 远远小 于前者的响应率5 1 。 2 1 3 任务调度算法的设计问题 本文主要从以下5 个角度探讨算法的设计问题。 1 确定性和启发性( 试探性) 算法 确定性算法适用于当进程的所有行为都是预先可知的情况。如果我们能够 事先知道一个任务的计算需求、文件需求、通信需求等等，有了这些信 息，我们就能设计一个完美的调度方案。 但事实上，系统的负载并不是我们能够预测的，工作请求视用户的行为而 定，并且每小时甚至每分钟都可能发生很大的变化。本文设计采用了启发式的 算法。 2 集中式和分布式算法 1 4 魁蝴毒撩分肌橼n 最镜巾任备构j l 蹙舱醺i | ，唼i 懿 9 m i 檗- fr 式算法，就是把所有信息收集到一个地点便1 二作出更好的决定，这 1 l ! 僻系统不够健壮，而且容易造成瓶颈。本文设计中采用了分印式算法。 3 坡优汞1 次优算法 渊度过程中，我们可以调度一个最优节点也可以调度一个次优节点( 虽然不 是最优节点，但是足以完成任务) 。调度一个最优节点必须收集比调度一个次优 节点更多的信息，并需要进行更全面的处理，通常付出的代价远大于得到的回报， 故本文设计采用次优算法。 4 本地和全局算法 当一个任务到达时，系统要决定是否让这个任务在接收它的机器上运行。如 果那台机器太忙，这个新的任务应该被转移到别的机器上去运行。这时就要决定 是否只根据本地的信息来决定转移策略。 本地算法主张：如果本机的负载低于某个门槛值，就让该进程在这台机器上 运行，否则转移。全局算法则主张：在判断本机是否太忙以前，先收集一些全局 信息，看一看别处的负载，再决定是否在本机执行该迸程。本地算法实现简单， 但难以达到最优，而全局算法又会因为收集信息付出更大代价，可能会得不偿失。 视频点播分布式系统采用了两种算法结合的方案，一个任务到达时只根据本 节点已有信息作出判断，但系统同时又在定期收集系统全局信息，这样在调度中 既考虑了全局状态信息又不会增加算法的复杂度。 5 发送者发起算法和接收者发起算法 一旦决定要将一个进程转移，那么定位策略就要决定将进程发送到何处。它 需要其他节点的负载信息来对进程传输到何处作出明智的决定。这个信息可以用 两种方法来传递：一种是发送者发起，一种是接收者来启动。本文设计中采用了 发送者发起算法。 ，i _ j ! l 论业 观额点播分布武操作系统中任务谶蝗虢设计i ，央脱 发送者是要转移任务到其他主机上的，是负载过重的节点；接收者是可以 接收填他主机上任务的，是负载较轻的节点。在发送者发起算法中，负载平衡活 动i i t 发送者发起，发送者试图将某个任务发送到负载较轻的节点。发送者发起算 泼和接收者发起算法的不同可由图2 - i 形象的看出。不论是发送者发起的还是接 收者发起的情况，不同的算法有不同的策略来决定由谁来搜集信息，及搜集多长 时州，和怎样处理结果1 1 删。 2 2 常见算法的分析 按算法决定接收者的方式，可以把算法分为确定式算法和启发式算法。确定 式算法往往是集中式的，如图论确定法( g r a p h t h e o r e t i cd e t e r m i n i s t i c a l g o r i t h m ) 和u p d o w n 算法( u p d o w na l g o r i t h m ) ，这种算法最后总是由固定的计算机做 决定。而启发式算法往往是分布式的，也可能有部分集中，如m i c r o s ( w m i ea n d v a nt i l b o r g ，1 9 8 0 ) 就是部分集中的( 分级领导方式) 。大多数启发式算法可以根 掘调度发起者的不同分为发送者发起式、接收者发起式和混合式( 两者都可发起) 等几种算法。 由于集中式算法中最后的决定者往往成为系统中的单一故障点和瓶颈，所以 不选用这种方式。下面主要讨论现有的启发式算法，包括发送者发起算法、接收 1 6 桃额点播分寿式操作系统中任务谶慢的啦汁l ，实耀 肖发起算法、混合算法和稳定的发送者发起算法 任务调度算法主要涉及四个方面：可完成指定任务的计算机集的确定，被转 移f e 务的选择，目的主机的选择和信息收集，以下就从这几个方面说明各种算法 的原理”。 2 2 1 发送者发起算法 可接收任务的计算机：按照当前系统的负载情况，设置限值t r a i n 和t m a x ， t 可以是节点任务队列的长度。当某节点的任务队列的长度小于t m i n 时，可以 接收来自其他主机的任务。当其任务队列的长度大于t m a x 时则变为发送者。 被转移的任务：被转移的任务可以是新来的任务，这种方式是非剥夺式的( 选 取还未开始执行的任务进行转移) ，也可以是正在执行的任务，这种方式是剥夺 式的，实现起来比较复杂。 目的主机的选择：发送者有任务要迁移时，随机选择一台主机做探测，如果 该主机能完成任务则选择这台主机，结束；否则在其余主机中随机选择一台继续 探测，直到有主机可以接收任务或达到某个探测限值。如果达到探测限值则表明 所有的主机都不能完成此任务，就在本机完成。 信息收集：只在发送者要调度时进行探测，不进行专门的信息收集。 这种算法的优点是简单，易于实现。缺点是要确定一个目的主机可能需要多 次探测，通信量大，延迟大，尤其在系统负载很重时，可能要探测全部的主机才 会结束，从而给本来就繁忙的系统增加了更大的负担。 另外种目的主机的选择方式是一次性向所有主机发送探测报文，选择第一 个( 或任个) 可以完成任务的主机作为目的主机同时谢绝其他主机。改进方向 足减少不必要的探测。 2 2 2 接收者发起算法 可接收任务的计算机：同发送者发起算法。 被转移的任务：同发送者发起算法。 1 7 m l 龄址税钡点播， 布代搬佧系统中任务诮瞳的i k 谴| | 奠- j l # | ：_ j 的主机的选择：当某节点有进程终止时，该节点将检查自己的负载情况， 如粜笈现自己的负载小于t m i n ( 即成为接收者) 则发起调度。随机选择系统中 的一台主机，并发送探测信息，询问该主机是否有任务要迁移出。如果被探测者 有任务要迁移出，则会响应并迁入任务，否则继续随机询问其他主机，直到得到 任务或达到询问限值。如果没有任何任务要迁入则进入睡眠，等待一定时间后继 续询问。 算法的另外一种实现方式是同时询问系统所有其他主机，选择任一个响应的 主机作目的主机，同时谢绝其他主机。 信息收集：只在接收者发起调度时进行探测，不进行专门的信息收集。 这种调度算法的优点是算法简单，易于实现，并且在系统负载繁重时仍然运 行很好，因为如果系统负载繁重则不会有接收者进行询问。缺点是调度效率不高， 有可能出现某节点有任务需要迁移却久久得不到接收者询问的情况，从而延迟很 ，c 。 2 2 3 混合算法 混合算法的思想是综合上面两种算法的优点，采用发送者和接收者都可以发 起调度的方式。 混合算法主要在选择目的主机的方式上与上面两种算法稍有不同。 每台主机维护三个队列，即接收者队列、o k 队列和发送者队列。一台主机 当其任务量小于t m i n 时，为接收者，当其任务量大于t m a x 时为发送者，其余 时候为o k 者。初始时每台主机都处在其他主机的接收者队列中。 当一个在发送者队列中的主机有新任务到达时，它取接收者队列队尾节点为 第一个询问者( 尽量一次询问成功) ，等待响应。如果对方回答可以接收则结束， 否则根据被询问者的返回状态移动被询问者到相应的队列尾部，然后再取接收者 队列队尾，如果接收队列已没有主机则任务就在本机执行，否则继续询问。被询 问者收到请求信息后首先计算接受任务后的状态，如果仍处于接收者或o k 状态 则接收任务，否则返回当前的状态。 如果某台主机有任务结束并且处于接收状态，则取发送者队列的队尾为第一 1 8 ml 沧业抛频点播仔布式操作系统中任务诮谴的醴“| i 唼脱 个洵问者。如果该节点回答有任务要发送则结束，否则根据被询问者的返回状态 移动被潮问者到相应队列，并继续取发送者队尾做询问，直到找到任务或发送队 州，逝空。 这个算法的优点是每个任务都能及时找到可执行者，并且减少了询问量。但 样县有发送者发起算法的弊端在系统任务繁重时不稳定，并且增加了算法 的短杂度。 2 2 4 稳定的发送者发起算法 稳定的发送者发起算法与混合算法类似，也要维护三个队列，唯一的区别是 当某台主机变为接收者时，它只向其他所有主机广播自己的状态，而不进行调度。 只有发送者才有发起调度的权利。 这个算法在系统负载很重时依然稳定，原因是此时发送者的接收队列节点很 少或为空，询问不能进行，从而也就不会给系统增加负载，同时这个算法具有调 度适时的优点。视频点播系统采用此算法原理。 2 3l i n u x 进程调度机谁l j 1 7 视频点播分布式操作系统是基于l m x 开发的，故需要对l i n u x 进程调度机 制有所了解。 l i n u x 是多进程的操作系统，每个进程运行在自己的虚拟地址空间中，只有 通过核心提供的i p c ( 进程间通信) 机制才能与其它进程进行通信。在l i n u x 中， 进程也通常称为任务( t a s k ) 。 2 3 1l i n u x 进程描述 在l i n u x 中，每个进程由一个t a s k _ s t r u c t 数据结构来描述。系统中定义了t a s k 指针数组( 即进程p c b 表) ，数组的每一元素指向一个t a s e _ s t r u c t 数据结构，系 统中进程的最大数由p c b 的长度决定，其值是n r _ t a s k s ，约定值是5 1 2 。每 当创建一个进程时，从系统中分配一个t a s k _ s t r u c t 结构，并放入进程p c b 表中。 1 9 雠频点播牡布j c 攘竹磊境中任务埘垃的没滓l ，宴憷 c u r r c l l t 指针指向当前运行进程。l i n u x 还支持实时进程的概念，对实时进程的反 j 越嘤比普通进程快。其调度算法采用先进先出算法( f i f o ) 或轮转法( r o u n d r o b i n ) ，分实时和非实时两种形式。 t a s ks t r u c t 数据结构在s r c i n c l u d e l i n u x l s c h e d h 中定义，这个数据结构比较复 杂，其字段包括了众多与进程相关的信息：进程状态信息、标识符信息、进程调 度信息、进程间通信信息、时间相关信息、进程间连接关系信息、虚拟存储管理 1 肯息、文件管理信息等等，下面主要介绍进程状态信息。 进程执行过程中会进行状态转换，l i n u x 中进程有如下几种状态( 值在 s c h e d h 中定义) ： 运行：t a s kr u n n i n g ，表示该进程正在运行或者是处于就绪状态( 等待 c p u ) 。 等待：t a s ki n t e r r u p t i b l e 和t a s ku n i m r e r r u p t i b l e ，表示该进 程萨在等待某事件的发生或等待某一种系统资源。由其值可以看出有两种等待 状态i n t e r r u p t i b l e 和u n i n t e r r u p t i b l e 。状态为i n t e r r u p t i b l e 表示该等待进程可以被信 号中断；而u n i n t e r r u p f i b l e 表示该进程等待某种硬件条件的发生且不可被中断。 僵死：t a s kz o m b i e ，表示该进程已经终止，但还在t a s k 数组中占一个 t a s ks t r u c t 表项。 停止：t a s ks t o p p e d ，表示该进程被停止，通常是由于接受到信号。这 1 - l f f 状态一般用于调试进程。 对换：t a s ks w a p p i n g ，表示该进程正在被对换。 进程自被创建进入就绪队列起，到执行完毕退出进入僵死状态，中间由于信 号、资源等问题，可能进入等待，挂起等状态【5 1 1 6 1 7 】【8 1 。 2 3 2l i n u x 进程调度 l i n u x 是一个分时的操作系统，其进程调度策略是给每个进程分一时间片 ( t i m e _ s l i c e ) 当进程的时间片用尽时，调度程序( s c h e d u l e 0 ) 从就绪队列( 该 队列中进程的状态为t a s k _ r u n n i n g ) 中根据优先级等参数，选取一个进程来 运行。 竺! 堡兰 丝丝生丝坌i 型塑笙墨竺塑望型型塑丝生! ! ! 丝 在l i n u x 中，进程可以运行在用户态，也可以运行在核心态( 即系统态，s y s t e m 。、o d e ) 。进程通过调用系统调用进入核心态。进程运行过程中有可能需要等待某 事件的发生，例如等待进程读、写设备，那么进程放弃处理器，调度程序选取 乓他进程运行。 一个可运行的进程的状态为t a s kr u n n i n g ，表示该进程获得c p u 资源 就可以运行了。l i n u x 使用简单而合理的调度算法来选择进程运行。为了公平的 分配c p u 时间，进程的t a s k _ s t r u c t 结构中有下列调度信息： p o l i c y ：这个成员指定进程的调度策略。目前有四个值：s c h e d _ 0 t h e r ， s c h e d _ f i f o s c h e d _ r r , s c h e d _ y i e l d 。l i n u x 进程有普通进程和实时进程 两种类型。实时进程比其他进程的优先级高。如果就绪队列中有实时进程，通常 会最先运行。实时进程有两种调度策略，循环调度( r o u n dr o b i n ) 和先进先出调 度( f i r s ti n 缶s t o u t ) 。循环调度方式( p o l i c y 为s c h e d _ r r ) 中，所有具有相同 优先级的实时进程获得同等的c p u 时间，并将轮流运行。先进先出调度方式 ( p o l i c y 为s c h e d _ f i f o ) 中，实时进程将按排列在运行队列的顺序依次执行， 而且这个顺序不会改变。非实时进程的调度策略为s c h e do t h e r 。p o l i c y 值为 s c h e dy i e l d 表示该进程主动放弃c p u 。 p r i o r i t y ：进程的优先级。也是当进程占领c p u 时的运行时间长短。 r t _ p r i o r i t y ：实时进程优先级。在l i n u x 中，实时进程的p r i o r i t y 的值一般是 r t p r i o r i t y 加1 0 0 0 。可见实时进程的p r i o r i t y 通常比起非实时进程要大得多。 e o u t e r ：进程被调度运行时将运行的时间长短( 即进程运行的时间片大小) 。 进程第一次运行时，p r i o r i t y 设为c o u t e r 值的大小。系统时钟每滴答一次c o u t e r 值都将减小。 传统的u n i x 的o # 进程在完成系统初始化的工作后成为调度进程，负责操 作系统的进程调度。l i n u x 中，0 # 进程并不负责完成这项任务，而是用核心提供 的函数s c h e d u l e ( ) 来实现任务调度。s c h e d u l e o 的原形在文件k e m e l s c h e d c 中。 s c h e d u l e ( ) 在多种情况下都会被调用 1 嘣进程运行时。 2 1 税额囊臻谤布式撩纷系统中任寺 谴慢的啦； | ，实现 2 将当前运行进程放到等待队列中后。 3 系统调用结束时，即在进程从核心态返回到用户态之前。 4 t a s ks t r u c t 的c o u n t e r 为0 ，即进程本次时间片用完时。 s c h e d u l e ( ) 所作工作如下： 1 通用的核一l , t 作。调用函数d o _ b o t t o m _ h a l f 0 ( k e m e l s o i l i r q c ) 。即运行 l i n “中的b o t t o mh a l f h a n d l e r 。b o t t o mh a l f h a n d e r 是核心提供的种机制，用来 将并不急于完成的工作排列在b o t t o mh a l fh a n d l e r 队列中，而在调度程序中运行 该队列中的工作。 2 处理当前进程。在调度其他进程到c p u 中运行之前，必须对当前运行进 程进行一些处理。 如果当前进程调度策略是循环调度，即p o l i c y 值为s c h e dr r ，则进程被 放到运行进程队列的队尾。 如果进程状态是t a s k _ i n t e r r u p t i b l e 而且最后一次被调度后已接受到 一个信号，则进程状态改变为t a s kr u n n i n g 。 如果当前进程时间片完，其状态置为t a s kr u n n i n g 。 如果进程状态为t a s k _ r u n n n g ，保持不变。 如果进程状态不是t a s kr u n n i n g 或t a s k1 n t e r r u p t b l e ，进程从 运行队列取出。 3 选择进程。调度程序从运行队列中的所有进程中选取一个最值得运行的 进程来运行。利用每个t a s k _ s t r u c t 中p o l i c y , p r i o r i t y , r t _ p r i o r i t y 和c o u n t e r ，计算出 一个w e i g h t 值，w e i g h t 最大的就是将调度运行的进程。 4 切换进程。如果最值得运行的进程不是当前运行进程，则当前进程挂起 而让所选进程运行。这就需要进行进程切换，保存当前进程的上下文( 寄存器， 堆栈等信息) ，载入所选进程的上下文，开始运行新进程。 2 4 本章小结 分布式任务调度是指如何决定在哪台机器上运行哪个任务的问题，根据任务 ic e 辽 税额点播 4 y a t - g 佧系统中壬斋询墟的殴i l ，实避 的状态滴度算法可以分为两类：可迁移的和不可迁移的。可迁移的调度算法指调 j 边n 0 任务对象可以是正在执行的任务，不可迁移的调度算法则只能对还没有执行 的任务进行调度。一般都希望任务调度算法能达n - - 个目标：c p u 利用率最大 化、平均响应时间最小化、响应率最小化。设计任务调度算法时，首先需要决定 算法的性质：确定性与启发性算法、集中式与分布式算法、最优与次优算法、本 地与全局算法、发送者发起与接收者发起算法。 通过对不同性质算法的分析，本文所谈的视频点播分布式操作系统所采用的 算法应该是启发性的、分布式的、次优的、本地与全局相结合的、发送者发起算 法。 本章第二部分主要对当前国内外流行的几种的分布式调度算法进行了分析， 包括发送者发起算法、接收者发起算法、混合算法、稳定的发送者发起算法，并 决定了本文麝该采用稳定的发送者发起算法的思想。 由于视频点播分布式操作系统基于l i n u x 进行开发，故本章第三部分对 l i n u x 中的进程调度机制作了简单介绍。 竺i 苎型! 坠! 塑坌垒塑竺! 堕! 堑堑塑竺盟丝堡! ! ! 丝 第三章系统设计及实现 不同的应用实例对分布式操作系统的要求也不同，设计一个可以满足各种应 j h 实例要求的分布式操作系统难度很大，本文提到的分布式操作系统是针对视频 点播系统开发的。 3 1 视频点播系统介绍 3 1 1 概念及系统结构 在国际上，从8 0 年代开始就有了v o d ( v i d e oo nd e m a n d ，即视频点播)