（计算机软件与理论专业论文）分布式联合虚拟参考咨询系统非实时咨询调度功能的研究与实现.pdf

硕 i : 论文分布式联合虚拟参考咨询系 统i t 实时咨询调度功能的研究i 实现 ab s t r a c t v i r t u a l r e f e r e n c e s e r v i c e ( v r s ) i s a v e ry i m p o r t a n t f u n c t i o n o f l i b r a ry . t h e l e v e l o f v r s i n c a rn a t e s a li b r a ry s s t r e n g t h a n d s e r v i c e q u a l i t y . v r s i s a v e ry i m p o r t a n t s u b s y s te m o f d i g it a l l i b r a ry . t h i s k i n d o f s o f t w a r e p r o v i d e s l i b r a r i e s w it h t o o l s t o i n t e r a c t w it h u s e r s i n m u l t i p le w a y s i n c l u d i n g s y n c h r o n o u s w a y a n d a s y n c h r o n o u s w a y . s y n c h r o n o u s w a y i s r e a l i z e d b y c h a t - o n l in e , p a g e p u s h , v o i p , c o o p e r a t i v e b r o w s e t e c h n o l o g y a n d s o o n . a s y n c h r o n o u s w a y i s r e a l i z e d b y e es m a i l ,w e b - f o r m a n d s o o n . p e r f e c t v i r tu a l r e f e r e n c e s e r v i c e c a n a l l o w s r e a d e r s a p p l y t h e ir q u e s t i o n s a t a n y m o m e n t a n d e v e r y w h e re .t h e a n s w e r f o r d i ff i c u l t q u e s t i o n s c a n b e s e a r c h e d o v e r t h e c o u n t r y w i d e r a n g e . a s i n g l e l i b r a r y w a s re s t r i c t e d勿 it s r e s o u r c e a n d t e a c h e r s , s o i t c a n n o t a n s w e r a l l k i n d s o f q u e s t i o n s . c a l i s d i g it a l l i b r a ry s y s te m t r i e s t o c o m b i n e t h e re s o u r c e o f o n e h u n d r e d n a t i o n a l k e y u n i v e r s it i e s i n o r d e r t o p r o v i d e p e r f e c t p r o f e s s i o n a l r e f e r e n c e s e r v i c e w it h h i g h q u a l i ty . s o t h e t a s k b e c o m e c o l l a b o r a t i v e c o n s u lt a t io n , a n d t h e t a s k n e e d t o b e t r a n s f e r r e d a n d s c h e d u l e d f o r m o n e l i b r a ry t o a n o t h e r . t h e s c h e d u l i n g o f c o n s u l t a t i o n t a s k i s a v e ry i m p o r t a n t p a r t o f c o l l a b o r a t i v e r e f e r e n c e s e r v i c e . w i t h t h e i n c r e a s i n g d e v e l o p m e n t c o m p u t e r n e t w o r k a n d d a t a b a s e t e c h n o l o g y , t h e d i s t r i b u t e d c o m p u t i n g h a s b e c o m e a n e w t r e n d a n d m o d e l o f c o m p u t e r a p p l i c a t i o n . i n t h i s s y s t e m i n t e r o p e r a b i l i ty i s a v e ry i m p o r t a n t s u b j e c t . i n t e r o p e r a b i l i ty i n g e n e r a l i n c l u d e s t h e c o m m u n i c a t i o n c o n t r o l a n d t r a n s f e r b e t w e e n d i ff e r e n t s y s t e m . i n t e r o p e r a b i l i ty n a m e l y i s t h e a c c e s s i n g b e t w e e n s y s t e m s i n f u n c t i o n a n d d a t e l e v e l . t h e t a s k o f d i s t r i b u t e d s y s t e m i s r e a l i z e d b y i n t e r o p e r a b i l i t y .s o i n t e r o p e r a b i l i ty w a s t h e i m p o rt a n t s u p p o rt f o r d i s t r i b u t e d s y s t e m s . c o l l a b o r a t i v e v ir t u a l r e f e r e n c e s e r v i c e ( c v r s ) i s a k i n d o f t y p i c a l d i s t r ib u t e d s y s t e m . i n t h i s p a p e r , w e d o r e s e a r c h f o r a s y n c h r o n o u s s c h e d u l i n g p r o b l e m s i n c v r s . s o m e i m p o r t a n t t e c h n o l o g y a r e s t u d i e d a n d a n a l y z e d a s f o l l o w s : t h e c o m m u n i c a t i o n a n d i n t e r o p e r a b i l i ty p r o b l e m i n d i s t r i b u t e s y s t e m t h e a s y n c h r o n o u s i n t e r o p e r a b i l i t y p r o b l e m o v e r w e b s e r v ic e t h e re l i a b i l i ty o f m e s s a g e t r a n s f e r s k e y w o r d s : v i r t u a l r e f e r e n c e s e r v i c e we b s e r v i c e i n t e r o p e r a b i l i ty me s s a g e q u e u e t r a n s a c t i o n o f s p r in g 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人己经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同 工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 - -t礁 研究生签名:摊匕 炸 ) 月 s日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的部分或全部内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的部分或全部内容。对 于保密论文，按保密的有关规定和程序处理。 研 究 生 签 名 : .1 -0 - -p 刀 8 日 硕_ 卜 论文分布式联合虚拟参考咨询系统非实时咨询调度功能的 研究与 实现 1绪论 1 . 1前言 人类进入2 0 世纪后半期， 特别是最后的2 0 年， 科学技术飞速发展。 以 计算机技 术、多媒体技术、 卫星通信技术等为 代表的现代信息技术，尤其以i n t e r n e t 为 代表 的国际互联网的建成， 极大的改变了全人类的生活、 学习、 工作方式。 人类社会以前 所未有的速度向信息化、网络化方向迈进。 作为人类精神财富和文化遗产的重要集藏场所的图书馆， 也受到信息化浪潮的强 烈冲击。随着计算机在图书馆的 应用以 及光盘检索技术、网络通信技术的日 益成熟， 图书馆的构成要素、馆藏内容、工作方式、服务手段等都发生了很大的变化. 传统图书馆正向数字化、网络化、 虚拟化、 无墙图书馆的美好前景努力。 作为图 书馆文献、 信息服务的重要内容之一， 并承担着发挥图书馆情报职能和教育职能的参 考咨询工作也在发生着变化。 电子化、 网络化信息资源的增加和资源共享的实现， 使 得咨询服务能以高效率提供实时解答、专题检索、文献验证、 研究顾问、馆际互借、 全文传递等各种服务。 参考咨询服务是高校图书馆为教学和科研服务的一项主要工作。 它作为图书馆全 部服务集( e n t i r e r e f e r e n c e c o l l e c t i o n ) 中的一个主要的、 读者使用频繁的服务子 集 ( r e a d y r e f e r e n c e c o l l e c t i o n ) ， 一 直 数 字 图 书 馆 建 设 的 重 点 0 。 针 对 网 络 环 境 下 人们对信息需求的变化， 传统的参考咨询服务在服务形式、 服务内容及服务人员的参 与方式等方面都发生了 许多 变化。 基于 w e b 的虚拟参考咨询服务( v i r t u a l r e f e r e n c e s e r v i c e ) 也叫数字参考咨询服务，是在如何提供高品质的参考服务理念下应运而生 的， 它在提高服务质量和效率的基础上将传统的到馆咨询服务搬到虚拟环境中来， 通 过常见问题解答数据库、电子邮件、w e b 表格、在线聊天、共同浏览等形式满足读者 的各种信息需求。目 前 虚拟参考咨 询服务有着相当良 好的发展态势， 美国s y r a c u s e 大学信息学院的虚拟参考服务台计划主持人r . d a v i d l a n d e s 就他们的调查结果 ( 9 7 . 3 % 的学术图书馆拥有自己的网站， 4 4 . 7 % 提供虚拟化参考服务) 指出: “ 虚拟参考 服务已成为目前图书馆界会议中最热门的议题之一， 现在正是运用科技发展软件， 确 立 品 质 标 准 ， 以 将 虚 拟 参 考 服 务 组 织 化 的 大 好 时 机 2 ) 。 在 我 国 ， 真 正 意 义 上 的 数 字 化参考咨询服务尚未普及， 在时代的背景下， 我们有必要对这种新兴的参考咨询服务 形式给予足够的重视， 并且加快进度、 加大投入， 针对我国目 前 信息用户的需求特点 和服务环境来对虚拟参考咨询系统进行研究和开发。 硕 : 论文分布式联合虚拟参x , 咨询系 统1 犷 实时咨询 调度功能的 研究与 实现 1 .2虚拟参考咨询系统国外发展状况 1 9 8 4年美国马里兰大学的健康服务图书馆推出“ 参考服务的电子化访问”( t h e e l e c t r o n i c a c c e s s t o r e f e r e n c e s e r v i c e e a r s )最早引 入t e - m a i l的服务方式， 揭 开 了 数 字 化 虚 拟 参 考 咨 询( ( v r s ) ) 工 作 的 序 幕 。 c tl 初 期 的 服 务 形 式 为 常 见 问 题 解 答( f a q ) 。随着网络技术的不断发展，v r s出现了电子邮件、电 子表单以及留言簿等 各种形式。自1 9 9 5 年起，国外一些图书馆开始应用c h a t 技术， 使用一些即时通讯软 件，比如 a o l , i n s t a n t m e s s e n g e r ，在网上开展实时参考咨 询， 现已 成为网络环境 下 图 书 馆 参 考 咨 询 服 务 的 发 展 趋 势 。 闭 ( 一) 基于i n t e n r e t 和人工干预的参考服务 一v r d . v i r t u a l r e f e r e n c e d e s k ( v r d ) 是美国 教育部1 9 9 9 年发 起并由白 宫科学技术政 策办公室支持的一个项目， 由美国教育部所属的教育资 源信息中 心( e r i c ) 开发。 2 0 0 0 年1 月开始运行， 其目的是致力于现有数字参考服务的进一步改善， 充分保证创建和 运 行 人 工 协 调 的 、 基 于 网 络 的 信 息 服 务 的 成 功 性 。 o l lfi l 71 ( 二)基于w e b 合作的数字参考服务 一从c d r s 到q u e s t i o n p o i n t . 2 0 0 0年1 1 月美国国会图书馆联合1 6 家图书馆共同开发“ 联合数字参考咨询服务” ( c o l l a b o r a t i v e d i g i t a l r e f e r e n c e s e r v i c e , c d r s , c d r s 项目 是基于 “ 图书 馆一 图 书馆 l i b r a r y t o l i b r a r y ) ” 之间 运行的星型服务网 络， 服务是免费的。 次年又同 o c l c 合作对 c d r s 进行了二次开发， 成为世界上规模最大、 最成功的分布式实时合作咨询服 务系统，并改名系统为q u e s t i o n p o i n t 。其目 标是建成一个由 专家库( 各地咨询成员 属性) 、知识库( 问答档案) 和资源库( 全球书目和全文数据库) 组成的全球性联合数字 参考咨询服务系统， 通过世界各地图书馆的共同 参与， 实现数字资源和智力资源的共 享。 8 l 9 l ( 三) 基于实时交互的数字参考服务一c u - s e e m e 网络会议 美国m i c h i g a n 大学s h a p i r o 学院图书馆在1 9 9 5 年秋季开始实施免费网 络会议平 台 计划来提供实时参考服务。这一计划利用c u - s e e m e 软件为同一大学不同校区的用 户服务。利用c u - s e e m e 软件和廉价照相机， 不同 校区的 学生和学院图 书馆的咨 询馆 员进行面对面的交流。 利用视频系统， 咨询馆员能为用户回答参考咨询问题， 培训学 生 如 何 使 用 新 的 光 盘 和 网 上 资 源 等 。 。 在 c u - s e e m e 网 络 会 议 中 如 何 利 用 c u - s e e m e 软件是技术关键。 咨询双方通过浏览器交流， 可以 相互传输文字， 传输图片， 推送网 页等。 若是用户的问题过于复杂或模棱两可， 咨询馆员可以通过e - m a i l 或电话得到有 关问 题的更多信息， 再将问 题传送到咨 询知识库和学科专家以保证2 4 小时内给用户答 案。 硕 士 论文分布式联合虚拟参考咨询系统非实时咨 询调度功能的 研究与 实现 可见国外的虚拟参考咨询服务形式都是依赖于网络技术、 计算机技术和通信技术 的发 展，以网 络上所有文献信息中 心的数字资源为 依托，由 单个系统走向 协作支持， 由 异步的非实时咨询走向 实时的在线咨询， 服务手段更加多样化， 依靠馆间 协作， 使 得服务质量更加有保障。 1 . 3虚拟参考咨询系统国内发展状况 国内虚拟参考咨询服务的起步较晚，当前各个图书馆采用的服务手段还比较简 单， 通常是通过 e m a i l , b b s 、留言 板等方式进行咨询， 而且明 显缺乏馆与馆之间的 资源共享与协作，与国外图书馆还有较大差距. 另外在我国 现有特殊情况下， 各地的数字图书馆发展客观上存在着不平衡性， 如 何平衡这种师资和资源不平衡的矛盾， 丰富咨询服务手段， 加强多个图书馆间的合作 和资源共享，成为当前各个图书馆的热门研究课题。 1 . 4课题背景、研究内容和意义 本课题的背景是上海交通大学2 1 1 基金和9 8 5 基金共建项目 一 “ 联合虚拟参考 咨询平台( c a l i s d i s t r i b u t e d c o l l a b o r a t i v e v i r t u a l r e f e r e n c e s y s t e m ，简称 c v r s ) ” 它是中国高等教育文献保障系统( c h i n a a c a d e m i c l i b r a r y 而后者由于其存储/ 转发机 制， 和功能的复杂性， 使得其性能较差， 但却可以利用其中间件的优势来提供多种消 息控制策略， 满足不同的复合需求。 本文采用程序方法级的模型， 从而使得系统性能 比较高，并在消息处理中加入了中间件思想的持久化存储/ 转发机制，从而提高了系 统传输的可靠性。 l 本文的组织结构 第一章 对课题的意义、背景、研究的内容和目 标及本人工作进行了概述. 第二章 对非实时调度功能在本系统的重要地位及实现中面临的主要问题进行了 详细的阐述。 第三章 给出非实时调度功能的模型和调度算法并对调度性能和调度效率运用排 队论理论进行了讨论。 第四章 对非实时调度功能中的通信和分布式互操作技术进行深入研究并给出 其 实现 第五章 对w e b 服务的异步通信机制进行研究并给出在非实时调度功能的实现。 第六章 借鉴消息中间件思想详细的讨论了非实时调度功能中消息传输的可靠性 问题。 第七章 给出了非实时调度功能的实现效果及算法评估。 第八章 总结与展望。 硕士论文分布式联合虚拟参x , 咨询 系统非实时咨询调 度功能的研究与 实现 2 c v r s 系统非实时调度功能设计及技术难点分析 2 . 1 c u r s系统目 标和架构 c v r s系统旨 在利用利用分布式计算技术构建一个中国高等教育分布式联合虚拟 参考咨询平台， 建立有多馆参加的、 具有实际服务能力的、 可持续发展的分布式联合 虚拟参考咨询服务体系。 c v r s 系统以 本地化运作为主，结合分布式、 协作式的运作， 实现知识库、学习中心共享共建的目的。 c v r s系统提供的虚拟参考咨询平台是沟通咨 询馆员与读者的桥梁， 通过此平台 的建立， 将能真正实时地解答读者在使用数字图书馆中 第一时间所发生的问 题。 咨 询 员可不受时间、地点的限制，在网上解答读者的疑问。从而为实现2 4 / 7 的理想服务 模式解决技术上的问题。 如图2 . 1 所示， 本系统由中心级咨询系统和本地级咨询系统两级架构组成。 中心 咨询系统由总虚拟咨询台与中心调度系统、 中心知识库、 学习中心等模块组成; 本地 级咨询系统由成员馆本地虚拟咨询台、 各馆本地知识库组成. 这种架构方式既能充分 发挥各个成员馆独特的咨询服务作用， 也能通过中心调度系统实现各成员馆的咨询任 务分派与调度。 达到优势互补， 协同 工作的目 的， 从而为咨询的 读者提供更加及时 有 效的咨询服务。 一 二 :、 一亘鱼一 嘛 -4 -11-. t 1) ., c t i ) f- - - c v r s 分中 心 蓝暴词 c v r s 中 心咨询系 统， 中心、 资源仓库扩 c v r s 本地系 统 ( 参 建馆n 卜 c v x s 本地系统 参建馆 ” 图2 . 1 c v r s系统两层分布式架构 硕士论文分布式联合虚拟参考咨询系 统7 r 实时ma 度功能的研究与 实现 2 . 2 c u r s 系统的主要功能模块简介 广c v r s 甲 心 系 统 总 咨 询 台 同步咨询服务 异 步 齐 询服 务 档 案 馆 成 员馆 学 科 专家 v 调 度 系统 知 识库八 享 问 趁 转 发 ， 让 者 转 移 本地咨询台 同步 齐 询服 务 异 步 齐 询 服 务 )调度 系 统 c vr s 本地 系统 档 案馆 成 的馆 学 科 一 专家 图2 . 2 c v r s 系统功能结构图 1 )咨询服务子系统 咨 询服务 子系统向 读者提供咨询服务， 是整个系统的 核心功能所在。 提供的咨询 服务主要包括:实时的咨询服务和非实时的咨询服务.实时咨询利用各类交互工具 ( c h a t t i n g 、 页 面推 送( p a g e p u s h i n g ) 、白 板等 技 术) 实时与 用户交换信息， 从而引 导用户找到问题的答案。 非实时咨询服务: 用户通过提问表单向系统寻求帮助。 同时 还可以通过问题征答区使所有用户都可以 对问题进行回答. 2 )调度子系统 如果系统在提供实时或非实时咨询服务的过程中， 遇到解决不了的问题， 便可以 通过调度子系 统将问 题调度到认为可以 解决该问题的 协作馆寻求协助解决此问 题， 协 作馆回答完问 题后可以将答案返回给问题转发馆。 该子系统根据各种系统预先设置的 调度策略或者管理员手工设置的调度策略， 选择档案库中相匹配的协作馆或咨询专家 对用户的非实时或者实时的咨询请求进行调度， 从而使用户能够及时的获取最有效的 服务。 3 )档案库子系统 档案库存储的是协作馆提供协作服务的地址和咨 询专家的基本信息， 这些信息 可以说是调度功能的参数信息， 档案库子系统为调度系统提供了丰富详细可选的调度 方案。 通过咨询系统的推广运行， 将会积累宝贵的成员馆和咨询专家的档案资料， 这 些资料一方面使咨 询参考服务更加有效， 另一方面还能够为其他系统提供信息检索服 务， 使全国的图书馆资源和人力资源得到统一的组织， 使各成员馆最好的资源为社会 所用. 4 )知识库子系统 存 储 的 是 经 过 整 理 的 历 史 的 问 题 表 单 和 解 答 记 录 和 对 实 时 咨 询 问 答 的 整 理 随 着 硕士论文分布式联合虚拟参考咨询系统非实时咨询调度功能的研究与实现 c v r s 系统的运行，将会在知识库中沉淀越来越多的非常有用的知识，并且这些知识 还将越来越完善， 既避免了咨询过程中的错误回答， 也使咨询的过程更加快捷、 高效。 从以上的系统功能介绍和分析中可以看到咨询服务子系统提供了系统的核心功 其服务质量的好坏直接关系着系统的整体性能、 实际服务能力的和可持续发展战 而调度子系统为咨询服务子系统提供高质量服务在方法和手段上提供了的强有力 能略 的支持。 通过调度子系统可以实现馆与馆之间协作， 使得资源共享， 优势互补， 互通 有无，大大提高了问题解答的质量和问题解决的及时性。 2 . 3 c v r s 非实时调度功能 非实时调度功能主要用来处理读者提交的表单问题， 系统为读者提供了透明的问 题咨询环境， 读者只要填好固定格式的问 题表单后直接点击提交， 本地系统管理员会 把问 题按照某种算法， 如涉及到的学科， 咨询员的 特长方向等将问题分派给最可能提 供满意答案的咨询员。 如果该咨询员对自己的回答不满意， 或者咨询问 题和所需资源 非本馆优势需要其他图书馆的协作， 则通过非实时的调度系统将问题表单调度给其他 的协作馆请求协作， 协作馆可以将问题回答完成后返回答案给问题调度馆， 也可以对 问题进行再调度， 问题调度馆可以把问题和答案整理放进知识库， 以备类似问题的解 答。 由 此可见在读者提问问题的背后有一个分布、 协作的系统在为读者服务， 而这一 切对读者来说是透明的， 对咨询员来说， 这种协作机制有效解决了 单个咨询系统由 于 资源限 制，咨询服务质量低的问题， 有力的保证了问题回答的质量和解答的及时性， 提高了 服务的质量。 其功能如图2 .3 所示: 咨询用户 in i u ii 填写we b 表单 ixia ， 电子邮件回复 可以解井 本地系统 j a ” 识 ” 孟 小能解书 气、 一 一 、调度了系统 、 _ 色氛沪 t ftaa=ntv 图2 . 3 异步调度功能流程图 硕士论文 分布式联合虚拟参考咨询系统非实时咨询调度功能的研究i ; 实现 2 . 4 c v r s 非实时调度功能实现中的主要难点 1 )调度机制与调度算法 资源的分配与调度可以被视为一个优化的问 题， 优化目 标，例如最小化服务相应时间 ( m i n i m a l 包括 s e r v i c e r e s p o n s e t i m e ) 、 最 大 化吞 吐量 ( m a x i m a l t h o u g h p u t )以 及最小花费 等。 资源和任务的参数化特征， 例如分别 有多少资源和任务、 执行某个任务需要哪些 资源以及对应的花费等等。 约束条件，例如任务的截止日期等 调度机制要根据资源和任务的各个参数特征， 在满足约束条件的前提下， 保证优 化目 标的实施. 如何设计一个切实可行的调度机制， 采用何种调度算法， 直接关系到 系统的性能和效率，是设计系统最先考虑的问题之一 2 )协作系统通信与互操作机制研究 随着计算机应用的发展， 多计算机协同工作变得越来越重要。 这种多计算机协同 工作的应用系统， 数据与处理系统均可位于不同的计算机上。 各处理系统通过计算机 网 络实现透明的通信与数据存取。 这类计算机应用就称为分布式计算( d i s t r i b u t e d c o m p u t i n g ) 或 网 络 计 算 (n e t w o r k c o m p u t i n g ) 。 36 )n e t w o r k c o m p u t i n g ) . 互操作性 ( 工 n t e r o p e r a b i l i t y ) 一般是指异质( 构) 系统间的 通信、 控制及数据传 输， 即系统间在功能和数据层次上的相互访问。 分布式计算系统中的各子系统间的协 同就是一种互操作， 系统任务是通过各子系统间的互操作实现的， 因此， 互操作是分 布 式 计 算 的 支 撑。 a 9 联合分布虚拟参考咨询系统采用两级架构， 分布协作的模式建立， 当协作馆之间 依托网络环境要协作解决某一问题时， 协作馆之间的通信与互操作便是系统能够运行 的基础。 3 )消息传输的可靠性技术研究 如果一个分布式系统， 在失败发生、 异步操作、 并发操作等情况下， 它的行为仍 然是可预测的， 我们就称这个系统是可靠的. 在通常的网络会话中， 可能产生会话中 断、 消息重复甚至消息发送的目 标系统出现故障或不稳定状态。 可靠的消息参考模型 必须确保消息发送方发出的消息保证被消息的接收方正确接收。 消息传输的可靠性问 题直接关系着系统的稳定性也是本文需要解决的问题。 2 . 5 本章小结 本 章 首 先 概 要 介 绍了c v r s 系 统 的目 标 、 架 构 及 主 要 功能 ，分析了各主要功能在 g 硕士论文分布式联合虚拟参考咨 询系统北实时咨 询调度功能的研究与 实现 系统中的地位作用， 指出了 调度功能在系统中核心功能的 地位。 然后着重介绍了 本文 工作实现的非实时调度系统的功能和实现上的技术难点， 为接下来的工作指明了研究 方向。 硕 士论 文 分布式联合虚拟参考咨询 系统非实时咨询调度功能的研究 ， 实现 3调度机制和调度算法研究 3 . 1资源调度问题综述 调度问题 ( s c h e d u l i n g p r o b l e m ) 是一类组合优化问题，所谓组合( 最) 优化 ( c o m b i n a t o r i a l o p t i m i z a t i o n ) 又称离散优 化( d i s c r e t e o p t i m i z a t i o n ) ， 它是 通过数 学方 法去 寻找离散事件的最 优编 排， 分 组， 次序或筛选等， 在计算机及通信等许多 领域 有着广泛的应用，在理论上又与算法设计、复杂性理论关系密切， 因而引起了许多学 者 的 研 究 兴 趣一 7 7 ( 19 1 对 于 组合 优 化问 题 ， 我 们 关 心的 一 般 不 是 最 优 解 的 存 在 性 和 唯 一性， 而是如 何找到有效的算法求得一 个最优解。调度问 题在计算机领域一直是 一个 经典的问题。 1 ) 单机系统的 进程调度问题 进程管 理是 操作系统四大功能 模块( 进程管理、 存储器管理、 设各管理和文 件管 理) 最重要的 一个模块， 而调度算法 研究又 是进程管理的 主要内容， 它的优劣关系到 整个系统的性能。 一个好的 调度算法应该考虑很多方面: 公平、 有效、 响应时间、 周 转时间、 吞吐量 等等， 但是这些因素 之间又 是相互矛盾的， 最终的 取舍根据系统要 达到 的 目 标 而 定 。 阁 目前，国内外众多学者对该领域已进行了多年广泛的研究， 提出了很多种调度算 法。 其中 经典算 法如先来 先服务调度算法 f c f s 、最短作业( 进程) 优先调度算法、时 间片 轮转调度算 法、 优先级调度算法、多 级反 馈队列调度算法 等。 2 )传 统 并 行 计 算 和 分 布 式 计 算 调 度 问 题 g e l 2 17 在并行分布计算中，调度系统的复杂度主要是主要指调度算法 ( s c h e d l i n g a lg o ri th m ) 的 时 间 复 杂 度 . 调 度 问 题一 般 都 具 有n p 完 全 难 度， 各 种 取 得 最 优 或 近 似 最优的 调度算法必 须具有多 项式时间复杂 度刁 是 有效的 算法。 下面给出 并行分布式计 算中调 度问 题的一 些基本 特征和相应分类。 a )静态调度与 动态调 度 按照何时决定每个任务的执行处理器号， 并行分布计算中的任务调度主要可分为 静态调 度 ( s t a t i c s c h e d u l i n g并行程序编 译时就决定每个任务的 执行处理器及 执行 时序) ， 动态调 度 ( d y n a m i c s c h e d u l i n g并行 程序 运行过程中， 根据当 前任务调 度机 系统执行情况，临时决定每个任务的执行处理器及起始执行时刻) ，和混合调度 ( h y b r i d s c h e d u l i n g )是介 于静态调度和动态调度两者之间的调度方法，它在 编译 时先静态调 度部分 任务， 而剩余时间则采用 动态调度的 方法在系 统运行过程中来 给他 硕 士 论 文分布式联合虚拟参考咨询系统非实时咨询调度功能的研究与实现 们分配处理器。 b )最优调度和启发式调 度 按照调度目 标的实 现要求来划分，并行分布计算中的任务调度可分为最优调度 ( o p t i m a l s c h e d u l i n g )和 近似最优调度 ( s u b - o p t i m a l s c h e d u l i n g ) ， 后者 也经常 称为启发式调度 ( h e u r i s t i c s c h e d u l i n g ) 如果一个调度算法能在多项 式复杂 度的 时 间内 获得最佳调度效果， 那么称 之为 有效的最优调 度算法。 但是只有在 极少数 情况下 才 存 在 有 效 的 最 优 调 度 算 法 19 ， 大 部 分 调 度 算 法 所 需 要 的 执 行 时 间 随 任 务 术 或 处 理 器的 数目 的增加而呈指数 增长。 因 此， 经常 采用启发式任务调度方法来 把各任务调度 分配到各处理器上，它虽然不能确保获得最优解，但可以获得最优调度的近似解。 c ) 集中式调度和分布式调度 按照调度程序的 结构或调度程序所收 集调度信息的范围， 并行分布 计算的 任务调 度方法可划分为集中式调度和分布式调度两大类。在集中式调度 ( c e n t r a l i z e d s c h e d u l i n g ) 方法中， 由 一个叫做中心调 度器的处理器来收集全局调度 信息， 其它处 理器把它们的状态信息传送给中 心调度器， 并由 中 心调度器做出 调度决定。 而分布式 调度 ( d i s t r i b u t e d s c h e d u l i n g ) 则是由 各处理单元的调 度程序 根据局 部范围的 一些 调度信息来进行调度任务， 它的最 大优点 在于具 有良 好的可扩放性。 集中 式调 度的 主 要优点在于实现比价简单， 但在节点数较多的大规模并行分布系统中，由于各节点与 调度服务器的通信成为瓶颈， 所以 调度开 销比 较大。 d )可中 断调度和不可中 断调度 按照是否允许任务中 断执行， 可分为中 断调度 ( 又称为抢占 式调度， p r e e m p t i v e s c h e d u l i n g ) 和不可中断 调度 ( n o n - p r e e m p t i v e s c h e d u l i n g ) 即 按任务执行中 是否 允许被中断执行。 e )共享存储结构调度和分布储 存结 构调度 按照并行分布计算模型的存储器结构，即并行的环境，主要可分为基于共享存储 的任务 调度和基于 分布存储的 任务调 度这两大类。 综上所述调度问 题的 基本元素有三 个， 即资源集( r e s o u r c e s e t ) ,消费者集 ( c o n s u m e r s e t ) 及这些资 源为这些消费 者服务所依 据的 一定规则( r u l e s ) ，调度问题 就是 在满足资源集和消费 者集约束条 件的基础上， 设计一个有效的调度系统来管理消 费者如 何高 效地使用这些 资源， 并使得 一些系统 性能 指标达到最优或近似最优。 调度问题 在不同的领域有许多不同的描述方法.一般地，构成调度性能和调度 效 率 是 评 价 一 个 调 度 系 统 优 劣 程 度 的 两 个 方 面 。 a l 每 个 调 度 问 题 都 有 自 己 特 定 的 一 些性能 测试指标( 有时 也称为 系统性能 指标) ， 如生产车间的产品 产量、 并 行分布计 算 中一 个并行应用程序的 执行时间、 多 用户系统下 作业的平均响应时间( r e s p o n s e t i m e ) 或系 统吞吐率( s y s t e m t h r o u g h p u t ) 等， 作为调 度系 统它的目 标就是要尽 量优化 这些 硕 士 论 文分 布式联合虚 拟参考咨 询系 统非实时咨询调 度功能的 研究与实 现 指标， 调度性能( s c h e d u l i n g p e r f o r m a n c e ) 也 就是通过这些指标的取值来反映， 它直 接体现了 调度结 果的 好坏。 调度效率( s c h e d u l i n g e f i c i e n c y ) 主要指调度系 统本身的 复杂度， 如果两 个不同 的调度系 统产生相同的调 度结 果， 那么复杂度小、 简 单明了 的 调度系统较优。 3 . 2 c v r s中的调度问题 消 费 者 集 ( 读 者 问 题) 产-鸣 调 度系统 一 一 、弩_ _ 严 竺 产 洲 资 源 集 ( 咨 询 员.在 线专 家) 图3 . 1 c v r s 调度问题 本系统的调度问题也可 抽象 成上 述的 模型: 资源集( 主要是负责回答读者 提交 上 来的问 题表单的咨询员 和在线专家)消费 者集 ( 提交的问 题) . 如图3 . 1 所示。 本系统调度问题是研究如何将读者提交的表单按照一定的算法调度到最合适解 答该问 题的 系统， 使得问 题可以 得到及时有效 的解答， 从而达到最小的 相应时间 和最 大的系统吞吐量。 综述中的调度问题基本上是在满足作业的时间约束、 操作的顺序约束、资源的相 容约束基础上的调度，已 经证明是 个n p 完全问 题， 迄今还没有算法在多 项式时间 给 以 解决， 现在研究热点 是各种启发式算法的应 用。 例如遗传算法。模拟退火算法等。 本系统调度目 标很明确即在最短的时 间内 将令读者满意的问题的 答案返回给读 者， 使 得系统的咨询服务质量达到很 好的 水平。 没有上文综述中调度问题的各种约束。 另一方面c v r s 系 统中， 不同 资源的计算能 力 ( 每个咨询员 有擅长的学科) 明显不同， 而在问题表单 和咨 询员间建立联系对系统 来说也是相 对来说比 较困 难的问题。 因为对 类似的问题由于 每个读者对问 题的表述不同 可能会使调度系统调 度结果不一样， 很难 确保调度质量， 所以 最好的办法是采用 人工干预的办法， 即由 管理员来统一调度， 采 用先来先 服务的 算法， 这样一 方面山 于管理员的 经验， 可以 最大程度的 保证问题 及时 准确地解答，另一方面也降低了系统实现的复杂度，提高了系统的性能。 3 . 3 c v r s调度机制 调度机制可以 分为集中式 ( c e n t r a l i z e d ) 和分布式 ( d e c e n t r a l i z e ) 两种。 在 集中 式调度中， 所有的 调度由 一个总的调 度引 擎完成， 要求该调 度引擎能获得当 前网 络 环境中 ， 所有与调 度任务有关的信息。 而分 布式调度中， 调 度由多个调度引 擎共同 完 成， 每 个调 度引 擎仅知道局部环 境的 信息， 调度引擎通 过相互间的 信息交流进行协 1 2 硕 1论文分布式联合虚拟参x , 咨询系统1 r 实时咨询 调度功能的研究 j 实现 调。 本系统采用集中调度与分布式调度相结合的调度机制， 结合了 集中调度和分布式 调度机制的优点， 一方面， 如果本地调度引擎知道任务解答的目 的馆， 则由本地馆直 接分派出去而不经过总馆的调度引擎， 如果本地的调度引擎不知道任务解答哪个馆可 以 解答， 则可以直接分派到总咨询台，由总咨询台 统一调度。 这样一方面降低了中心 系统的压力，有利于总体系统的负载均衡，另一方面有提高了问题准确回答的概率， 其调度机制如图3 . 2 所示: 全国咨询网络 尹 ， 一 、 区城咨询网络 区城咨询网络 0 咨 询 台 . 调 度 系 统 区城咨询网络 图3 . 2 c v r s 系统的调 度机制 虚拟参考咨询系统通过以 下环节实现上述资源协调与调度机制 1 )通过协作感知机制， 使得管理员知道当前 本地馆读者提交的任务队列，队列 里面既有本地馆提交的问 题，也有协作馆调度过来的问题，管理员此时可以 将咨询问题分派给本馆咨询员。 2 )接收到任务的咨询员可以回答问 题， 此时问题可以 被完全回答， 如果咨询员 回答不了该问 题， 或感觉回答不完全， 想征求一下别的咨询员的意见， 可以 通过w e b 服务提供的调度系统按照一定的调度策略调度给别的协作馆. 3 )基于面向服务的体系结构实现对协作任务相关资源的普适访问，系统通过 w e b 服务支持任务调度的透明操作，咨询员登陆后又系统自 动推送任务，不 必关心任务的具体来源。 c v r s 通过任务调度机制将广域分布的咨询员资源协调起来解决一个大协作任务， 在任务队列信息的收集，转发、 解答返回答案等环节采用w e b 服务实现。 硕上论文分布式联合虚拟参考咨询系统非实时咨询调 度功能的研究与 实现 3 . 4 c u r s 调度模型和调度算法 c v r s 的任务调度模型如图 所示， 每个协作馆节点上的咨询问题可以 抽象为一 个作 业队列，队列按照f i f o 原则存放读者提交的问题。任务调度过程就是遵循一定策略 从作业队列中选取一份待评阅的作业，并通过作业传送服务推送给咨 询员.