·562· 北京科技大学学报 2004年第5期 表示，它们的占有程度由位置的标识(marking)表 队列，它的容量限定为b.s表示资源j的变迁，它 示.允许变迁的实施条件用变迁的可实施谓词规 的实施速率为4，实施速率表现为资源的处理能 定，当谓词条件不能满足时，变迁不能实施.模型 力.它对任务，的服务时间表达为r4,任务r既代 中的标记表示请求或资源，不同类型的请求或资 表了任务类型，又表示了服务时间要求的权重， 源使用不同颜色的标记表示， 变迁4可以联系各种各样的可实施谓词和随 本文中使用随机高级Peti网对社区公共服 机开关，它们取决资源调度方案的选取，考虑如 务网格体系中的资源调度建立模型，首先假设所 下三种资源调度方案的模型设计： 考虑的社区服务网格环境可接受类任务请求， (I)轮转(Round-Robin,RR)方案.在这种方案 即任务具有n个优先级（每一类就是一个优先 中，用户任务循环分配给所发现资源集合中的一 级)，在资源发现阶段可查找到m个可用资源. 个资源，亦即，该资源集合中的每一个资源获得 资源调度算法描述中所定义的符号如下 任务的机会均等，这种方案既没有考虑每个资源 (1≤j≤m): 的队列状态，也没有考虑任务的服务时间. (1)系统包含m个在资源发现阶段查找到的 变迁d的可实施谓词y表示为M(g水b.变 资源，接受n类任务.其中，第i类请求记作r,第 迁d的随机开关(Mq)表示为： j个资源记作S. (2)每个服务器包含一个缓冲队列.S的队列 &Mg》=RR(M if jErr(M 1 0, otherwise 由标识符9表示，其缓冲空间的容量为b 其中，RR(0={Mqb}. (3)任一类任务的到达为泊松(Poisson)过程. (2)最少任务优先(Least Job First,LJF).这种 任务r,到达速率为，r可以被分配到m个资源队 方案选择当前资源集合中任务最少的资源作为 列中的任一队列.当所有接纳任务的m个队列容 到达任务的分配目的地，亦即，集合中只有等待 量都满时，任务的到达过程中断. 队列最短的资源才有获得任务的机会， (4)每个服务器服务不同请求可有不同的服 变迁d的可实施谓词y表示为：Mq水b,人 务时间.$的服务速率为4，服务速率是独立的、 (for Vk+j,(Mg)sMgV(Mg)=b).变迁d,的随 指数分布的.图2给出了网格资源调度方案的随 机开关g(Mq》表示为： 机高级Petri网模型 8Mg》=iFwo研，if jELJF(w 0, otherwise 其中，LJF(0={4Mq)=min(Mq),Mq),,Mq)》 and Mq)<b). (3)最小期望等待时间(Shortest Expected De- lay,SED).这种方案选择具有最小期望等待时间 的资源作为到达任务的分配目的地.定义： 图2随机高级Petri网资源调度模型 f(k)-EMq.r)x(r/u.) Fig.2 Scheduling model of stochastic high-level petri net 变迁d的可实施谓词y表示为Mg)bA(for 在图2的SHLPN模型中，变迁和位置的含义 k*j,(U)sf)V(Mg=b).变迁4的随机开 描述如下(1s≤m,1≤isn):c,表示i类任务r,到来 关gMq》表示为： 的时间变迁，它有实施速率.变迁c所联系的可 实施谓词表示为： 8Mg》=ISED0 if jESED(M 0, otherwise 乞MqKb, 其中，SED(M0={Mfk)=min(f1),f2),,f八m)and f表示判断的位置，它瞬时保留到来的任务， Mq)<b:). 根据d联系的可实施谓词或随机开关以决定到 RR不考虑请求的类型及QoS需求，方案最简 来的任务放入哪一个资源等待队列.d表示分配 单，具有良好的公平性能，每一个资源获得任务 执行的瞬时变迁，分配方案可由其所联系的可实 的机会均等.但不支持高优先级请求的Q0S要 施谓词和随机开关表示.9表示资源j接收任务的 求；既没有考虑每种资源的队列状态，也没有考虑北 京 科 技 大 学 学 报 年 第 期 表 示 ， 它们 的 占有 程 度 由位 置 的标 识 表 示 允许 变迁 的实施 条件用 变迁 的可 实施 谓 词规 定 ， 当谓 词条件 不 能满足 时 ， 变迁 不 能 实施 模 型 中的标 记表示 请求或 资源 ， 不 同类 型 的请 求或 资 源 使用 不 同颜 色 的标 记 表 示 本 文 中使用 随机 高 级 网对 社 区 公共 服 务 网格体 系 中的资源 调 度建立模 型 ， 首 先假 设 所 考 虑 的社 区 服 务 网格环 境 可 接 受 类 任 务请 求 ， 即任 务具 有 个优 先 级 每一 类 就 是 一 个 优 先 级 ， 在 资源 发现 阶段 可 查 找 到 个 可 用 资源 资 源 调 度 算 法 描 述 中 所 定 义 的 符 号 如 下 习‘ 系 统包 含 个 在 资源 发现 阶段 查 找 到 的 资源 ， 接 受 类任 务 其 中 ， 第 类 请求 记 作乙， 第 个 资源 记 作衍 每 个 服 务器 包 含 一个缓冲 队列 匀的 队列 由标 识 符场表 示 ， 其 缓冲 空 间 的容量 为 任 一类 任 务 的到达 为 泊松 过程 任 务乙 到达 速 率 为凡 ， 乙可 以被 分配 到 个 资源 队 列 中 的任 一 队列 当所 有接 纳任 务 的 个 队列容 量 都满 时 ， 任 务 的到达 过程 中断 每个 服 务 器 服 务 不 同请 求 可 有 不 同的服 务时 间 的服 务速 率为肠 ， 服 务速 率 是 独 立 的 、 指 数 分布 的 图 给 出 了网格 资源 调 度 方 案 的随 机 高级 网 模 型 队列 ， 它 的容 量 限定 为 母表 示 资源 的变迁 ， 它 的实施 速 率 为肠 ， 实施速 率表 现 为资源 的处 理 能 力 它 对任 务乙 的服 务 时 间表 达 为乙俩 ， 任 务乙 既代 表 了任 务类 型 ， 又 表 示 了服 务 时间要 求 的权 重 变迁可可 以联 系各种各样 的可 实施 谓词和 随 机 开 关 ， 它 们 取 决 资源 调度 方 案 的选 取 考 虑如 下三 种 资源 调 度 方案 的模 型 设计 轮转 一 ， 方 案 在 这 种方 案 中 ， 用 户任 务循环 分 配给 所 发现 资源 集合 中的一 个 资源 ， 亦 即 ， 该 资源 集合 中的每一 个 资源 获得 任 务 的机会 均 等 这 种方 案 既没有考虑每个 资源 的 队列 状 态 ， 也 没 有考 虑 任 务 的服 务 时 间 变迁 诱的可 实施 谓 词 另 表 示 为 斌场 变 迁礴的 随机 开 关 以斌妇 表 示 为 婀 。 一 谕 ， ， ， 任 动 刃 其 中 夕 动 二 川斌妇 瓦 最 少任 务优 先 ， 这种 方 案选 择 当前 资源 集 合 中任 务 最 少 的 资源 作 为 到达 任 务 的分 配 目的地 ， 亦 即 ， 集 合 中只 有 等待 队列最 短 的 资源 才 有 获得 任 务 的机 会 变 迁 踌的 可 实 施 谓 词 表 示 为 斌妇 九八 羊 ， 斌妇‘ 斌妇 域妇 二 变迁踌的随 机 开 关以域 表 示 为 。 一 谕 ，卜 ， 任 劝 刃 其 中 ， 侧 叫斌叮 斌叮 ， 斌叮 ，… ， 斌 。 斌 丹 最 小 期 望 等待 时 间 ， 这 种 方案选择 具有 最 小期 望等待 时间 的 资源 作 为到 达 任 务 的分配 目的地 定义 图 随机 高级 网资 源 调 度模型 妙一 在 图 的 模 型 中 ， 变迁 和 位 置 的含 义 描述 如 下 匀‘ ， 百‘ 。 表 示 类任 务 ‘ 到来 的 时 间变迁 ， 它有 实施速 率儿 变迁 所联 系 的可 实施 谓 词 表 示 为 一 务斌 ， ， 变 迁铸的 可 实 施 谓 词必 表 示 为斌亿 八 对 ， 口切 ‘ 八 斌妇 二 变 迁 铸 的 随 机 开 关以斌 表 示 为 · 卜 咖 ， “ · …网 ， 艺斌 ‘ 艺 ‘ 扮】 件 表 示判 断 的位 置 ， 它瞬 时保 留到来 的任 务 ， 根 据 联 系 的可 实施 谓 词 或 随机 开 关 以决 定 到 来 的任 务放 入 哪 一 个 资源 等待 队列 踌表 示 分配 执行 的瞬 时变迁 ， 分配 方 案可 由其所 联系 的可 实 施 谓词和 随机 开关表 示 表 示 资源少接收任务 的 其 中 ， 润 二 抓 ， ， … ， 斌妇 不考虑 请求 的类 型及 需求 ，方案最 简 单 ， 具 有 良好 的公 平 性 能 ， 每 一 个 资源 获得任 务 的机会 均等 但 不 支 持 高优 先 级 请 求 的 要 求 既没 有考虑 每种 资源 的队列状态 ，也没有考虑