1 Online Judge 系 统 的 优 化 庄 奇 东 1,3, 王 键 闻 2, 张 楠 1,3, 张 爽 4, 任 娜 1 ( 沈 阳 工 程 学 院 信 息 工 程 系, 沈 阳 110136) 2 ( 沈 阳 工 程 学 院 基 础 部, 沈 阳 110136) 3 ( 沈 阳 工 程 学 院 电 力 系 统 信 息 安 全 重 点 实 验 室, 沈 阳 110136) 4 ( 昌 兴 建 筑 工 程 有 限 公 司 ERP 软 件 事 业 部, 东 莞 523750) 1 摘 要 : 从 Web 页 面 和 数 据 库 缓 存 服 务 器 架 构 多 核 评 测 处 理 规 则 前 端 异 步 响 应 数 据 表 设 计 跨 平 台 支 持 源 代 码 抄 袭 检 测 测 试 用 例 自 动 生 成 等 方 面 优 化 了 Online Judge 系 统, 使 得 评 测 效 率 提 高 的 同 时 减 少 了 服 务 器 数 量, 节 约 了 运 行 成 本 最 后 讨 论 了 基 于 Online Judge 系 统 实 现 智 能 优 化 算 法 的 统 一 测 试 平 台 的 方 法 关 键 词 :Online Judge; 缓 存 ; 多 核 ; 处 理 器 亲 和 性 ; 排 队 论 ; 抄 袭 检 测 ; 测 试 用 例 自 动 生 成 Optimization of Online Judge Systems ZHUANG Qi-Dong 1,3, WANG Jian-Wen 2, ZHANG Nan 1,3, ZHANG Shuang 4, REN Na 1 1 (Dept. of Information Engineering, Shenyang Institute of Engineering, Shenyang 110136, China) 2 (Dept. of Fundamental Sciences, Shenyang Institute of Engineering, Shenyang 110136, China) 3 (Key Lab of Information Security for Power System, Shenyang Institute of Engineering, Shenyang 110136, China) 4 (ERP Software Division, Changxing Construction Engineering Co., Ltd, Dongguan 523750, China) Abstract: This paper describes the application and performance optimization of Online Judge Systems in terms of web page and database caching, server architecture, testing and processing rules in multi-core environment, front-end asynchronous response, data table design, cross-platform support, source code plagiarism detection, automatic generation of test cases, etc., which enhances the evaluation efficiency while reducing the number of servers, saving operating coses. And then, it discusses the general idea on the implementation of a unified test platform for intelligent optimization algorithms. Key words: online Judge; cache; multi-core; processor affinity; queuing theory; plagiarism detection; test case auto generation Online Judge 系 统 ( 简 称 OJ) 一 般 指 在 ACM/ICPC ( 国 际 大 学 生 程 序 设 计 竞 赛 ) 等 各 种 形 式 的 编 程 比 赛 中 用 来 评 测 参 赛 选 手 的 程 序 的 正 确 性 与 时 空 效 率 的 程 序 以 及 评 测 程 序 所 依 托 的 网 络 环 境 一 般 包 括 以 下 几 部 分 :Web 服 务 器 数 据 库 服 务 器 编 译 程 序 以 及 评 测 程 序 用 户 可 以 通 过 网 络 浏 览 服 务 器 上 的 网 页 来 选 择 题 目, 通 过 网 页 提 交 代 码, 由 服 务 器 端 调 用 编 译 程 序 对 用 户 提 交 的 程 序 进 行 编 译, 然 后 由 评 测 程 序 进 行 评 判 并 返 回 相 应 的 结 果 到 网 页 上 供 用 户 查 看 1 OJ 系 统 的 历 史 和 现 状 最 早 用 于 程 序 设 计 竞 赛 的 Judge 系 统 是 由 西 班 牙 Valladolid 大 学 的 Ciriaco García de Celis 于 1995 年 开 发, 用 于 为 该 校 参 加 ACM/ICPC 西 南 欧 区 域 赛 选 拔 队 员 [1] 十 余 年 来 经 过 数 人 的 合 作 开 发,UVa Online Judge 已 被 完 善 为 一 个 具 有 比 赛 实 时 评 判 能 力 的 功 能 强 大 界 面 友 好 统 计 数 据 齐 全 的 分 布 式 在 线 裁 判 系 统 现 在, 基 于 它 的 EduJudge 工 程, 亦 即 "Integrating Online Judge into effective e-learning", 已 成 为 欧 盟 委 员 会 基 金 支 持 下 的, 致 力 于 推 广 终 生 学 习 和 高 效 在 线 学 习 模 式 的 LifeLong Learning Programme 2007-2013 的 一 个 核 心 部 分 [2] 近 年 来, 随 着 ACM/ICPC 竞 赛 体 制 在 国 内 的 普 及, 众 多 定 位 各 异 的 OJ 系 统 也 雨 后 春 笋 般 地 出 现 2009 1 基 金 项 目 : 辽 宁 省 自 然 科 学 基 金 (20092045); 沈 阳 市 重 点 实 验 室 建 设 资 助 项 目 (1091244-1-00); 沈 阳 工 程 学 院 院 内 基 金 理 工 类 (2009009) 收 稿 时 间 :2010-12-12; 收 到 修 改 稿 时 间 :2011-01-27 Research and Development 研 究 开 发 115
计 算 机 系 统 应 用 http://www.c-s-a.org.cn 2011 年 第 20 卷 第 8 期 年 课 题 组 启 动 了 SIEOJ 项 目, 初 始 版 本 基 于 Windows 和.net framework, 后 迁 移 到 Linux 平 台 上 文 献 [3-6] 或 详 细 或 简 略 地 介 绍 了 OJ 系 统 的 设 计 与 实 现, 因 此 本 文 只 着 重 介 绍 SIEOJ 系 统 在 多 核 系 统 中 的 实 现 难 点 功 能 提 升 和 性 能 优 化 方 法, 以 及 由 OJ 系 统 实 现 智 能 优 化 算 法 的 统 一 测 试 平 台 的 思 路 2 性 能 优 化 2.1 前 端 异 步 响 应 平 时,OJ 系 统 的 访 问 量 并 不 大, 这 时 一 台 普 通 服 务 器 应 负 起 所 有 的 http 服 务 数 据 库 服 务 判 题 服 务 都 绰 绰 有 余 但 是 当 遇 到 承 办 大 型 竞 赛 尤 其 是 网 络 赛 时, 正 常 同 时 访 问 者 上 千 并 且 还 有 可 遭 遇 DDoS 等 形 式 的 黑 客 攻 击 的 巨 大 可 能, 所 以 需 要 服 务 器 具 有 强 大 的 并 发 处 理 能 力 这 样 一 般 要 把 Web 前 端 数 据 库 和 评 测 程 序 分 离, 即 至 少 置 三 台 服 务 器 处 理 大 量 连 接 时,Web 服 务 器 常 用 的 I/O 复 用 机 制 有 IOCP(Windows), epoll(linux), kqueue(freebsd) 等 模 型 虽 然 从 理 论 上 来 说,IOCP 是 纯 异 步 的, 阻 塞 程 度 最 低, 但 由 于 其 所 依 赖 的 Windows 系 统 的 文 件 系 统 性 能 的 局 限 性, 其 实 际 表 现 一 般 并 不 如 epoll 和 kqueue 表 1 显 示 了 基 于 Select 模 型 的 Apache 基 于 epoll 和 kqueue 模 型 的 Nginx 和 基 于 IOCP 模 型 的 IIS 的 实 测 对 比 ( 在 Intel Xeon 5520 双 CPU 4G RAM 上 测 试 ) 表 1 Apache IIS 和 Nginx 的 测 试 比 较 每 秒 处 理 简 单 静 态 页 面 请 求 数 / index.php 最 大 并 发 响 应 时 间 (s) 连 接 数 无 eaccelerator 有 eaccelerator Apache2 约 3000 3478/0.034 10917/0.014 IIS7 约 5000 3930/0.029 3891/0.029 Nginx0.8 约 55000 3779/0.028 14557/0.009 使 用 eaccelerator 作 为 PHP 脚 本 的 预 编 译 加 速 和 缓 存 器 其 内 存 缓 存 的 大 小 受 限 于 Linux 系 统 最 大 连 续 分 配 共 享 内 存 的 大 小, 所 以 可 以 根 据 实 际 情 况 修 改 系 统 的 /proc/sys/kernel/shmmax 来 改 变 缓 存 容 量 Web Server 的 前 端 置 一 台 同 样 基 于 epoll 模 型 的 Varnish 服 务 器, 经 测 试,Varnish 缓 存 服 务 器 还 可 减 少 约 90% 的 数 据 库 查 询 图 2 Varnish 的 http 请 求 状 态 图 2.2 前 端 异 步 响 应 SIEOJ 采 用 jquery 实 现 Ajax 技 术, 使 得 服 务 器 和 浏 览 器 之 间 交 换 的 数 据 减 少 到 只 有 原 来 的 30%-40%, 在 得 到 更 快 的 前 端 响 应 的 同 时 减 轻 了 服 务 器 负 荷 Nginx 的 配 置 也 可 告 诉 浏 览 器 缓 存 静 态 文 件 另 外, 由 于 使 用 了 Varnish 作 为 缓 存 服 务 器,jQuery 的 JavaScript 文 件 也 被 缓 存 到 了 内 存 中, 所 以 当 由 新 用 户 产 生 新 的 连 接 时, 也 不 会 造 成 服 务 器 频 繁 的 I/O 操 作 2.3 多 核 评 测 2.3.1 单 核 单 线 程 环 境 下 的 时 间 测 量 Linux 和 Windows 以 及 Java 下 都 有 系 统 函 数 调 用 可 以 获 取 当 前 进 程 / 线 程 的 运 行 时 间 不 过 不 同 的 系 统 实 现 都 不 用, 而 且 用 法 也 不 同 [4] 从 测 试 程 序 段 所 在 位 置 上 讲, 可 分 为 在 待 测 任 务 中 插 入 测 试 代 码 和 通 过 另 外 一 个 程 序 测 试 两 种 ; 从 测 试 效 果 上 讲, 可 分 为 间 隔 计 数 ( 各 运 行 态 累 计 得 到 CPU 时 间 片 之 和 ) 和 周 期 计 数 ( 累 计 经 过 时 钟 周 期 数, 即 结 束 和 起 始 时 间 之 差 ) 两 种, 从 应 用 层 次 上 讲, 可 分 为 用 系 统 API 测 量 和 用 低 级 语 言 直 接 访 问 CPU 内 的 8254 计 数 器 测 量 两 种 图 3 单 核 系 统 下 的 物 理 时 间 图 1 多 核 评 测 的 系 统 架 构 但 是, 在 现 代 的 计 算 机 系 统 中 根 本 不 可 能 精 确 测 116 研 究 开 发 Research and Development
量 某 一 个 程 序 运 行 的 确 切 时 间 因 为 操 作 系 统 的 进 程 和 线 程 的 分 配 和 调 度 CPU 的 指 令 流 水 线 处 理 等 对 于 程 序 和 用 户 来 说 都 是 透 明 的 在 真 实 情 况 下 计 算 机 并 不 是 只 运 行 一 个 程 序 的, 待 测 进 程 的 优 先 级 调 度 策 略 系 统 负 载 同 步 或 线 程 切 换 各 种 中 断 共 享 的 多 用 户 网 络 流 量 高 速 缓 存 的 访 问 转 移 预 测 等, 都 会 对 计 时 产 生 影 响 例 如, 现 在 的 Linux 和 Windows 等 操 作 系 统 对 线 程 进 行 抢 占 式 调 度, 用 户 线 程 会 因 为 时 间 片 用 完 等 原 因 而 被 中 断 系 统 会 从 用 户 态 转 入 核 心 态, 即 使 在 线 程 队 列 上 没 有 其 他 线 程, 这 种 切 换 也 会 使 用 户 线 程 的 运 行 时 间 明 显 增 加 2.3.2 CPU 亲 和 性 与 任 务 优 先 级 在 多 核 和 多 CPU 系 统 中, 情 况 更 为 复 杂 又 增 加 了 伪 共 享 的 问 题 以 及 同 一 进 程 / 线 程 在 不 同 CPU 核 间 切 换 的 问 题 图 4 多 CPU/ 多 核 系 统 下 的 物 理 时 间 CPU 读 取 Cache 时 是 以 行 为 单 位 读 取 的, 如 果 两 个 硬 件 线 程 的 两 块 不 同 内 存 位 于 同 一 Cache 行 里, 那 么 当 两 个 硬 件 线 程 同 时 在 对 各 自 的 内 存 进 行 写 操 作 时, 将 会 造 成 两 个 硬 件 线 程 写 同 一 Cache 行 的 问 题, 它 会 引 起 竞 争 [7], 造 成 程 序 效 率 的 成 倍 下 降 现 代 的 许 多 支 持 多 核 处 理 器 的 操 作 系 统, 往 往 都 有 一 种 机 制 来 维 持 各 个 CPU 核 心 上 的 负 载 均 衡 例 如, 在 2.6 版 的 Linux 内 核 中 便 采 用 了 一 种 简 单 方 法 使 用 软 中 断 来 调 整 多 核 CPU 上 的 压 力, 每 秒 一 次 其 大 致 基 本 原 则 是 : 从 最 繁 忙 的 CPU 核 上 挪 一 个 任 务 到 最 空 闲 的 CPU 核 上, 如 此 下 去 直 到 负 载 均 衡 [8] 对 于 伪 共 享 问 题, 需 要 自 己 编 写 内 存 分 配 和 管 理 的 算 法, 十 分 复 杂 对 于 核 间 切 换 的 问 题, 虽 然 系 统 中 其 中 还 有 一 些 优 化 算 法 尽 量 使 切 换 时 使 任 务 尽 量 分 配 在 同 一 个 Chip 上, 但 还 是 有 较 大 可 能 使 得 切 换 后 的 任 务 丧 失 原 来 的 指 令 和 数 据 缓 存 管 线 等 残 留 物, 甚 至 需 要 重 新 分 配 一 些 资 源, 造 成 额 外 的 时 间 开 销 在 多 核 OJ 系 统 中, 一 个 解 决 上 述 问 题 的 最 直 接 思 路 便 是 使 评 测 服 务 器 系 统 尽 量 不 运 行 除 评 测 任 务 外 的 其 他 任 务, 同 时 在 维 持 各 CPU 核 负 载 均 衡 的 前 提 下 尽 量 避 免 发 生 任 务 抢 占 和 任 务 在 不 同 核 间 的 切 换 处 理 器 亲 和 是 在 对 称 多 处 理 器 操 作 系 统 中 本 地 中 央 队 列 调 度 算 法 的 改 进 每 个 任 务 ( 无 论 是 进 程 还 是 线 程 ) 在 队 列 中 有 一 个 标 记, 标 明 其 首 选 / 亲 近 处 理 器 在 分 配 时, 每 个 任 务 分 配 优 先 于 其 他 处 理 器 分 配 给 其 亲 近 处 理 器 [9] 在 多 核 OJ 系 统 的 设 计 中, 考 虑 利 用 处 理 器 亲 和 性, 以 更 大 概 率 地 保 证 被 测 的 用 户 程 序 在 单 一 的 CPU 和 核 心 上 执 行, 避 免 伪 共 享 和 任 务 在 不 同 核 间 的 切 换, 从 而 保 证 对 用 户 程 序 执 行 时 间 测 试 的 精 确 性 表 2 不 同 操 作 系 统 下 实 现 处 理 器 亲 和 性 的 方 法 函 数 /API 命 令 行 /UI Windows SetThreadAffinityMask() 或 SetProcessAffinityMask() TaskManager Linux sched_setaffinity() taskset FreeBSD pthread_setaffinity_np() cpuset NetBSD pthread_setaffinity_np() psrset MacOS affinity API ---- 另 外, 被 测 用 户 程 序 的 优 先 级 也 会 影 响 评 测 结 果 的 准 确 性 如 果 太 高, 则 调 度 的 时 间 片 少, 因 为 操 作 系 统 的 时 间 片 轮 转 调 度, 一 个 运 行 时 间 大 于 调 度 时 间 片 的 线 程 会 被 中 断 ; 如 果 太 低, 则 因 为 操 作 系 统 的 优 先 级 调 度, 会 在 大 部 分 运 行 期 间 得 不 到 CPU 轮 转 的 时 间 片 为 确 定 采 用 哪 种 优 先 级 会 使 对 用 户 程 序 耗 时 的 测 量 最 准 确, 做 了 一 组 实 验 : 随 机 选 取 OJ 题 库 中 的 一 道 题 目, 将 用 户 程 序 和 多 核 系 统 的 最 后 一 个 CPU 核 心 建 立 处 理 器 亲 和, 并 将 待 测 进 程 设 置 为 不 同 的 优 先 级, 每 次 实 验 连 续 10 次 向 OJ 提 交 测 试 相 同 的 正 确 代 码, 最 后 得 到 时 间 值 测 试 结 果 表 明 : 采 用 最 高 的 优 先 级 运 行 程 序 得 到 的 时 间 值 最 为 稳 定 图 5 优 先 级 处 理 器 亲 和 性 与 进 程 运 行 时 间 Research and Development 研 究 开 发 117
计 算 机 系 统 应 用 http://www.c-s-a.org.cn 2011 年 第 20 卷 第 8 期 猜 想 造 成 这 个 结 果 的 原 因 是 最 后 一 个 CPU 核 心 较 为 空 闲, 即 使 被 测 用 户 进 程 时 间 片 用 完 或 被 中 断, 也 在 很 短 时 间 内 被 重 新 调 度 而 获 得 CPU 时 间 片, 缓 存 指 令 管 线 等 资 源 并 未 丢 失 且 多 次 评 测 在 相 同 条 件 下, 从 而 得 到 了 较 强 的 一 致 性 文 献 [10] 说 明 了 多 CPU 系 统 中, 在 未 指 定 处 理 器 亲 和 性 的 情 况 下, 处 理 已 有 指 派 任 务 时, 外 部 的 中 断 往 往 被 操 作 系 统 全 部 交 与 第 一 个 CPU 即 CPU0 来 处 理, 这 也 在 一 个 侧 面 支 持 了 上 述 猜 测 文 献 [11] 提 出 了 The K-Best Measurement Scheme 的 测 量 方 法, 其 中 有 一 点 是 减 少 高 速 缓 存 不 命 中 给 我 们 程 序 执 行 时 间 带 来 的 影 响, 即 在 测 试 之 前 先 执 行 一 遍 程 序, 让 指 令 高 速 缓 存 和 数 据 高 速 缓 存 都 得 到 预 热 该 文 献 也 指 出, 任 何 一 次 单 独 的 测 量 都 无 法 精 确 获 得 进 程 运 行 时 间, 只 有 在 多 次 运 行 后 取 最 小 的 重 复 出 现 的 若 干 个 数 据 才 能 得 到 较 为 精 确 的 值 然 而 这 在 高 并 发 的 OJ 系 统 中 是 不 可 取 的 但 上 述 实 验 说 明, 在 多 核 系 统 中, 通 过 指 定 处 理 器 亲 和 性, 便 可 一 次 就 能 获 得 比 较 精 确 的 测 量 结 果 2.3.3 多 核 评 测 模 式 考 虑 使 用 一 台 多 核 评 测 机, 指 定 操 作 系 统 的 内 核 judged 守 护 进 程 与 第 一 个 CPU 核 为 处 理 器 亲 和, 指 定 Soulution_ID 为 i 的 用 户 程 序 和 i mod (Total_CPU_core - 1) 的 CPU 核 亲 和, 并 使 judge_client 进 程 和 用 户 程 序 进 程 以 最 高 的 优 先 级 运 行 这 样 不 仅 尽 可 能 保 证 了 用 户 程 序 执 行 测 试 期 间 不 会 被 其 他 进 程 抢 占, 也 在 一 定 程 度 上 维 持 了 系 统 的 负 载 均 衡 对 于 支 持 超 线 程 的 CPU, 可 做 适 当 调 整, 即 把 Total_CPU_core 1 改 为 2(Total_Logical_CPU_core-1) 即 可 其 中 Soulution_ID 为 用 户 提 交 的 ID 号,Total_CPU_core 为 CPU 的 物 理 核 心 数,Total_Logical_CPU_core 为 CPU 的 逻 辑 核 心 数 这 些 值 可 在 OJ 的 配 置 文 件 中 设 定 图 6 多 CPU 多 核 超 线 程 系 统 上 的 可 能 瞬 态 对 于 高 性 能 的 多 CPU 多 核 超 线 程 的 服 务 器 且 有 双 工 模 式 的 外 存 储 设 备 如 SAS 硬 盘, 则 OJ 仅 需 要 一 台 服 务 器 : 一 个 CPU 上 运 行 缓 存 服 务 器 http 服 务 器 数 据 库 服 务 器, 同 样 用 处 理 器 亲 和 性 指 定 每 个 服 务 的 亲 和 CPU 核 心 ; 另 一 个 CPU 用 来 评 测, 规 则 如 上 对 于 大 内 存 的 64 位 机, 可 以 用 内 存 文 件 映 射 提 高 I/O 速 度, 还 可 将 比 赛 题 目 测 试 用 例 全 部 读 入 内 存 ( 或 内 存 虚 拟 硬 盘 的 方 法 ), 这 样 可 消 除 绝 大 部 分 I/O 大 量 测 试 表 明, 采 用 以 上 策 略, 在 多 核 系 统 中, 对 于 相 同 的 正 确 代 码,Linux 和 Windows 下 的 时 间 测 量 值 的 差 异 一 般 不 超 过 4ms 和 1ms 2.3.4 理 论 分 析 和 进 一 步 优 化 图 6 看 似 只 有 一 个 用 户 提 交 队 列, 但 其 实 是 模 6 同 余 的 ID 的 提 交 组 成 的 三 个 队 列, 这 可 看 成 是 一 个 多 队 多 服 务 台 的 排 队 模 型 大 量 的 实 际 数 据 表 明, 在 竞 赛 中, 用 户 的 提 交 事 件 近 似 为 泊 松 流 按 照 排 队 论, 若 输 入 过 程 服 从 泊 松 分 布, 采 用 单 队 多 服 务 台 的 排 队 规 则 比 采 用 多 队 多 服 务 台 的 工 作 效 率 高 改 进 : 设 法 变 成 多 评 测 机 单 队 列 模 型 增 加 一 布 尔 数 组 available[using_judge_core], 初 始 全 为 1, 当 从 待 测 队 列 中 取 出 一 条 记 录 时, 顺 序 搜 索 此 数 组, 若 无 非 零 值 则 等 待 一 小 段 时 间 再 搜 索, 若 有 为 1 的 值 则 记 住 该 下 标 i, 将 available[i] 改 为 0, 顺 次 启 动 编 译 跟 踪 评 判 程 序, 并 将 这 些 进 程 同 i 对 应 的 CPU 逻 辑 核 心 ( 下 标 不 一 定 为 i, 但 一 般 与 i 具 有 线 性 关 系 ) 建 立 处 理 器 亲 和 性, 评 测 完 成 后, 将 数 据 库 中 写 入 记 录 并 将 available[i] 改 回 1 另 外, 由 于 对 单 字 节 变 量 的 赋 值 只 对 应 一 条 汇 编 指 令, 具 有 原 子 性, 所 以 这 里 无 需 考 虑 共 享 变 量 的 互 斥 问 题 一 般 大 型 竞 赛 中 一 场 约 有 8000 次 提 交, 评 测 机 不 够 或 策 略 不 当 往 往 会 导 致 大 量 的 待 测 队 列 堆 积, 严 重 影 响 选 手 水 平 的 发 挥 如 2007 年 亚 洲 北 京 站 点 赛 就 产 生 了 最 高 20 分 钟 的 待 测 序 列 选 取 2008 年 ACM/ICPC 亚 洲 哈 尔 滨 站 点 赛 的 统 计 数 据, 由 于 不 能 获 得 具 体 的 提 交 和 评 测 情 况, 按 最 坏 的 假 设 估 计 各 种 类 型 提 交 所 需 要 的 评 判 时 间, 算 出 两 个 分 布 的 参 数 : 平 均 到 达 率 λ=0.433/s, 平 均 服 务 率 μ=0.128/s, 根 据 排 队 论 中 的 M/M/C 模 型 不 难 算 出 此 系 统 的 其 他 性 能 指 标, 如 表 3 118 研 究 开 发 Research and Development
表 3 假 设 下 各 种 不 同 的 模 型 的 性 能 指 标 4 评 测 机 4 队 4 评 测 机 单 队 6 评 测 机 6 队 6 评 测 机 单 队 服 务 强 度 ρ 0.846 0.846 0.564 0.564 平 均 队 长 Ls 21.937 7.119 6.776 3.586 平 均 等 待 队 列 长 Lq 18.554 3.736 4.373 0.203 平 均 逗 留 时 间 Ws 50.697 16.453 17.927 8.287 平 均 等 待 时 间 Wq 42.879 8.634 10.108 0.468 系 统 空 闲 概 率 P0 0.154 0.019 0.436 0.033 等 待 时 间 小 于 5s 的 0.234 0.541 0.573 0.971 概 率 P(tq<5) 逗 留 时 间 小 于 10s 的 概 率 P(ts<10) 0.179 0.409 0.428 0.698 通 过 生 成 服 从 特 定 分 布 的 序 列 作 离 散 事 件 模 拟 得 出 的 结 果 也 与 表 3 相 似 从 中 可 以 看 出, 采 用 多 机 单 队 评 测 正 是 通 过 提 高 系 统 的 利 用 率 来 减 少 了 等 待 队 列 长 度 和 等 待 时 间 此 外, 如 果 Web 等 其 他 服 务 器 也 是 多 核 的 且 有 计 算 资 源 剩 余, 则 也 可 用 上 述 方 法 利 用 其 剩 余 资 源 处 理 一 些 判 题 工 作 比 之 文 献 [5] 所 述 的 集 群 式 OJ, 上 述 设 计 也 极 大 地 节 省 了 硬 件 成 本 2.4 数 据 表 设 计 与 查 询 优 化 在 数 据 库 系 统 中, 采 用 外 键 能 够 保 证 数 据 库 的 数 据 完 整 性 然 而, 虽 然 在 大 型 比 赛 时 读 写 操 作 频 繁, 但 OJ 系 统 一 般 没 有 复 杂 的 强 约 束 性 事 务, 所 以 采 用 外 键 一 方 面 会 造 成 系 统 并 发 处 理 性 能 下 降, 另 一 方 面 会 使 得 系 统 遇 到 数 据 灾 难 时 恢 复 困 难 所 以 在 SIEOJ 数 据 库 设 计 中, 完 全 摒 弃 了 外 键 约 束, 关 键 的 几 条 完 整 性 约 束 由 外 部 的 C 和 PHP 语 言 程 序 来 控 制 在 大 型 比 赛 中, 用 户 的 提 交 队 列 数 据 表 的 访 问 时 最 关 键 且 最 频 繁 的, 但 一 般 而 言 这 个 表 通 常 都 是 临 时 表, 数 据 量 不 大 且 每 条 记 录 处 理 结 束 后 都 会 被 删 除 而 处 理 结 果 会 被 写 入 其 他 表 中 去 因 此, 用 memory 存 储 引 擎 把 此 表 建 在 了 内 存 上 OJ 中 还 有 一 些 数 据 表 的 数 据 量 较 大 而 读 操 作 比 较 频 繁, 因 此 在 关 键 的 列 上 建 立 了 Hash 或 B 树 索 引 2.5 安 全 性 保 障 由 于 需 要 执 行 用 户 提 交 的 代 码, 所 以 在 OJ 系 统 运 行 中 的 安 全 性 是 一 个 必 需 考 虑 的 因 素 目 前, 在 已 有 的 OJ 系 统 中, 常 用 到 的 安 全 策 略 有 :1) 敏 感 字 符 串 过 滤 [6], 如 对 于 while(1) fork(); system( shutdown ); 等 会 对 系 统 造 成 危 害 的 恶 意 代 码, 如 果 在 对 用 户 提 交 的 代 码 扫 描 后 检 测 出 来, 则 不 编 译 用 户 提 交 的 程 序, 数 据 库 中 亦 记 录 下 有 关 信 息 常 用 的 检 测 手 段 为 正 则 表 达 式 匹 配 ;2) 管 道 技 术, 在 Linux 系 统 下 为 了 让 用 户 提 交 上 来 的 程 序 不 破 坏 服 务 器 的 文 件 系 统, 在 执 行 用 户 程 序 之 前, 先 把 输 入 流 定 向 到 标 准 输 入 文 件, 然 后 使 用 chroot 改 变 用 户 程 序 的 执 行 目 录, 让 其 只 能 在 一 个 临 时 目 录 下 面 做 操 作 ;3) 沙 箱 技 术 [12], 使 用 户 程 序 在 创 建 的 Sandbox 环 境 中 运 行, 与 系 统 中 的 其 它 部 分 隔 离 开 来, 从 而 使 用 户 程 序 对 操 纵 系 统 编 译 器 与 其 它 服 务 器 组 件 等 做 的 更 改 在 程 序 结 束 后 完 全 无 效 但 是 对 于 方 法 1), 用 户 还 有 可 能 用 宏 定 义, 或 字 符 串 分 拆 后 拼 接 等 特 殊 手 段 突 破 字 符 串 过 滤 技 术, 工 作 量 大 且 对 程 序 员 要 求 高 对 于 方 法 2) 和 3), 容 易 被 突 破, 并 不 能 有 效 保 证 系 统 安 全 有 人 提 出 了 底 层 的 API Hook 方 法, 但 难 度 过 大 在 SIEOJ 的 实 现 中, 兼 用 了 字 符 串 过 滤 和 管 道 技 术, 并 增 加 了 跟 踪 用 户 程 序 的 方 法, 即 先 运 行 并 测 试 一 遍 用 户 程 序 (ptrace()), 如 果 遇 到 白 名 单 中 没 有 的 调 用, 则 强 行 终 止 用 户 程 序, 状 态 置 为 Runtime Error, 反 之 则 再 测 试 一 遍 用 户 程 序, 得 到 准 确 的 时 间 一 般 程 序 设 计 竞 赛 中 能 够 用 到 的 系 统 调 用 非 常 有 限, 所 以 白 名 单 的 创 建 也 较 为 简 单 这 样 做 还 可 以 预 热 高 速 缓 存 从 而 得 到 更 精 确 的 时 间, 第 二 次 测 试 时 也 可 省 去 许 多 处 理, 比 如 格 式 错 的 判 断 3 功 能 增 强 3.1 跨 平 台 支 持 前 台, 使 用 标 准 的 HTML, 使 得 在 不 同 浏 览 器 上 呈 现 出 一 致 的 效 果 为 了 使 使 用 智 能 手 持 式 终 端 设 备 的 用 户 也 能 够 访 问, 专 门 设 计 了 不 含 JavaScript 脚 本 且 节 省 流 量 的 wap 版 本, 同 时 提 供 了 gcc 编 译 器 的 移 植 版 本 及 其 IDE [13], 使 得 用 户 在 智 能 手 机 上 也 能 够 编 写 代 码 调 试 程 序 并 向 OJ 提 交 后 台, 为 了 能 够 充 分 利 用 老 版 本 基 于 Windows 和.net 的 OJ 中 的 题 目, 设 计 了 用 XML 文 件 自 动 导 入 和 导 出 题 目 的 方 法 OJ 内 核 评 测 模 块 也 很 好 地 处 理 了 如 何 跨 平 台 的 问 题, 比 如 不 同 系 统 下 时 间 测 量 单 位 不 同 的 问 题 和 测 试 用 例 文 件 格 式 的 问 题 因 为 Windows 和 各 种 类 Unix 系 统 对 于 线 程 的 处 理 机 制 不 同, 线 程 切 换 所 需 的 代 价 的 差 异 较 大 [14], 所 以 OJ 的 评 测 模 块 采 用 了 多 进 程 模 型 而 不 是 多 线 程 模 型 Research and Development 研 究 开 发 119
计 算 机 系 统 应 用 http://www.c-s-a.org.cn 2011 年 第 20 卷 第 8 期 法, 将 紧 缩 串 分 成 若 干 份, 每 份 到 另 一 个 紧 缩 串 中 进 行 匹 配, 匹 配 出 的 子 串 被 删 去, 直 到 不 能 再 发 现 匹 配 子 串 系 统 只 将 当 前 用 户 提 交 代 码 与 对 应 题 目 的 以 往 其 他 用 户 的 正 确 代 码 进 行 匹 配, 相 似 度 若 大 于 某 个 阈 值 则 在 数 据 库 中 留 下 相 关 记 录 该 功 能 为 可 选, 只 在 需 要 时 启 用, 大 型 比 赛 时 关 闭, 以 防 影 响 速 度 图 7 Web 和 数 据 库 服 务 器 为 在 Linux 下 也 能 够 支 持 C# 和 ASP.net, 使 用 了 开 源 项 目 mono 为 了 提 高 Windows 下 页 面 处 理 和 数 据 库 查 询 的 效 率, 实 现 类 似 于 Varnish 的 效 果,ASP.net 采 用 了 数 据 库 缓 存 依 赖 以 提 高 缓 存 命 中 率.net 下 利 用 了 微 软 的 C# 沙 箱 开 源 项 目 为 系 统 的 安 全 性 提 供 了 更 多 一 重 保 障 同 时 运 用 了 虚 拟 化 和 云 计 算 的 一 些 技 术, 比 如 使 用 VMware 的 免 费 软 件 ESXi, 在 一 台 服 务 器 上 同 时 支 持 多 个 异 构 的 操 作 系 统 来 提 供 服 务 3.2 测 试 用 例 自 动 生 成 比 赛 中 的 题 目 往 往 需 要 大 量 的 测 试 用 例, 而 且 往 往 需 要 某 些 特 殊 的 用 例, 能 够 将 可 解 区 域 覆 盖 均 匀 且 全 面 有 效 涵 盖 特 殊 边 界 或 能 很 好 地 测 试 出 用 户 考 虑 不 足 的 地 方 然 而, 即 使 知 道 一 道 题 目 的 正 确 解 法 和 正 确 代 码, 人 工 编 写 成 千 上 万 组 测 试 用 例 也 是 一 件 十 分 繁 重 的 工 作, 而 且 很 难 进 行 验 证 SIEOJ 基 于 俄 罗 斯 开 源 项 目 testlib 实 现 了 一 个 测 试 用 例 的 自 动 生 成 器, 用 类 似 于 正 则 表 达 式 的 语 言 描 述 数 据 特 征 和 规 则, 即 可 让 出 题 者 方 便 地 生 成 大 量 所 需 的 测 试 用 例 3.3 代 码 抄 袭 检 测 OJ 系 统 不 仅 用 于 竞 赛, 还 常 常 用 来 作 为 众 多 计 算 机 课 程 的 教 学 和 考 试 平 台, 因 此 在 这 些 应 用 背 景 下, 需 要 系 统 具 有 代 码 抄 袭 自 动 检 测 功 能 SIEOJ 在 实 现 代 码 抄 袭 功 能 时 选 用 了 开 源 项 目 sim2.26 [15], 先 通 过 Unix 的 lex 命 令 对 用 户 程 序 做 词 法 分 析, 将 程 序 源 代 码 表 示 为 另 一 种 紧 缩 的 格 式, 建 立 向 前 引 用 表, 再 采 用 一 种 检 测 DNA 序 列 相 似 性 的 算 4 由 OJ 实 现 智 能 优 化 算 法 的 统 一 测 试 平 台 近 年 来, 智 能 优 化 算 法 一 直 是 计 算 机 科 学 界 的 一 个 研 究 热 点, 每 年 都 有 许 多 学 者 发 表 许 多 有 关 的 论 文, 大 部 分 都 涉 及 对 一 些 算 法 解 决 某 类 问 题 的 改 进, 论 文 中 常 常 出 现 一 些 测 试 比 较 的 数 据 然 而 这 些 数 据 并 不 一 定 很 客 观, 因 为 不 同 的 结 果 有 可 能 不 是 在 相 同 或 相 似 条 件 下 测 得, 由 前 文 可 知 他 们 测 定 的 方 法 也 不 一 定 合 理 ( 如 通 常 只 取 两 个 时 间 值 相 减, 这 样 往 往 会 得 到 不 正 确 的 程 序 运 行 时 间 ), 论 文 作 者 也 有 可 能 对 测 试 结 果 做 一 些 人 为 的 筛 选 以 突 出 自 己 算 法 的 高 效 性 因 此, 建 立 一 个 智 能 优 化 算 法 的 统 一 测 试 平 台 很 有 必 要 不 同 于 通 常 OJ 中 的 题 目 的 正 确 程 序, 智 能 优 化 算 法 的 程 序 往 往 需 要 运 行 数 十 秒 数 分 钟 甚 至 数 小 时, 而 且 现 在 的 智 能 优 化 算 法 的 实 现 往 往 是 并 行 的 程 序, 因 此 需 要 有 针 对 性 地 改 进 OJ 系 统 首 先, 为 OJ 系 统 增 加 更 多 编 译 器 的 支 持, 如 支 持 OpenMP TBB 等 并 行 模 型 的 Intel C++ 和 Fortran 编 译 器 ( 两 者 的 Linux 版 本 都 是 免 费 的 ), 其 次, 限 制 OJ 同 一 时 间 只 能 评 测 一 个 用 户 程 序, 其 他 的 提 交 放 到 等 待 队 列 上, 再 次, 每 个 程 序 只 运 行 一 次, 无 需 预 热 因 为 世 界 各 地 从 事 智 能 优 化 算 法 研 究 的 高 校 和 科 研 机 构 有 众 多 的 测 试 用 例 提 供 下 载, 所 以 目 前 首 先 初 步 实 现 了 对 于 TSP 问 题 的 统 一 在 线 测 试 5 结 语 数 本 文 所 述 的 方 法 不 仅 适 用 于 OJ 系 统, 还 可 用 于 实 时 性 要 求 较 高 的 其 他 Web 服 务 和 编 译 应 用, 所 用 第 三 方 组 件 均 为 免 费 或 开 源 解 决 方 案, 而 且 实 现 方 法 简 单 易 行 有 效 参 考 文 献 1 Revilla M, Manzoor S, Liu RJ. Competitive learning in informatics: the UVa online judge experience. Olympiads in Informatics, 2008,2:131 148. 120 研 究 开 发 Research and Development
2 Luisa MR, Elena V, Juan PC, María ÁP, et al. A proposal of user interface for a distributed asynchronous remote evaluation system: An evolution of the QUESTOURnament tool. Proc. 9th IEEE Int l Conf. on Advanced Learning Technologies. Riga, 2009.75 77. 3 康 海 燕, 樊 孝 忠, 汤 世 平. 基 于 J2EE 的 在 线 测 评 系 统 的 研 究 与 设 计. 计 算 机 工 程,2004,13:169 171. 4 何 静 雯.ACM/ICPC 评 测 系 统 综 述. 计 算 技 术 与 自 动 化, 2005,4:405 409. 5 王 辉, 胡 新 华, 张 广 泉. 集 群 式 程 序 设 计 竞 赛 评 测 系 统 设 计 与 开 发. 计 算 机 应 用 与 软 件,2009,9:119 122. 6 李 哲. 在 线 程 序 竞 赛 评 判 系 统 的 设 计 与 实 现 [ 硕 士 学 位 论 文 ]. 大 连 : 大 连 理 工 大 学,2008. 7 周 伟 明. 多 核 计 算 与 程 序 设 计. 武 汉 : 华 中 科 技 大 学 出 版 社, 2009. 8 董 昊.Linux 在 多 核 处 理 器 上 的 负 载 均 衡 原 理. 淘 宝 核 心 系 统 团 队 博 客. [2010-11-11]. http://rdc.taobao.com/blog/cs/?p =379. 9 Wikipedia. Processor Affinity. [2010-11-11]. http://en. Wikipe dia.org/wiki/processor_affinity. 10 Foong A, Fung J, Newell D. An in-depth analysis of the impact of processor affinity on network performance. IEEE Transactions on Networks, 2004,1:244 250. 11 Hollinger D.Time Measurement. [2010-11-11]. http://www. cs.rpi.edu/~hollingd/comporg/notes/timing/timing.pdf. 12 Ahmed SA, Muhammad AR, Shusmita AS, et al. Secured programming contest system with online and real-time judgment capability. Proc. of the 8th Int l Conf. on Computer and Information Technology, 2005. 13 张 胜, 洪 明. 基 于 Pocket PC 的 IDE 设 计 与 实 现. 计 算 机 系 统 应 用,2008,17(11):14 19. 14 Reinders J. Intel Threading Building Blocks: Outfitting C++ for Multi-core Processor Parallelism. O Reily, 2007. 15 Grune D. The software and text similarity tester SIM. [2010-11-11]. http://www.few.vu.nl/~dick/sim.html. ( 上 接 第 75 页 ) 证 明, 基 于 概 念 的 向 量 空 间 模 型 比 基 于 词 语 的 向 量 空 间 模 型 的 聚 类 分 析 性 能 更 好 本 文 中 还 有 很 多 值 得 进 一 步 研 究 的 地 方 对 于 情 感 词 概 念 的 选 取, 本 文 直 接 选 用 了 第 一 义 项, 没 有 具 体 的 概 念 排 歧 工 作 在 使 用 k-means 算 法 进 行 聚 类 分 析 时, 每 次 随 机 选 取 的 簇 中 心 不 一 样, 使 得 聚 类 的 结 果 不 稳 定 今 后 需 要 在 情 感 词 概 念 提 取 以 及 算 法 优 化 方 面 加 强 研 究, 使 聚 类 结 果 性 能 更 好 参 考 文 献 1 杨 勇 涛.Web 舆 情 观 点 挖 掘 关 键 技 术 研 究. 成 都 : 电 子 科 技 大 学,2009. 2 董 振 东, 董 强.HowNet s HomePage.Http://www.keenage. com, 2010. 3 夏 天, 樊 孝 忠, 刘 林. 利 用 JNI 实 现 ICTCLAS 系 统 的 Java 调 用. 计 算 机 应 用,2004,24(12):177. 4 胡 静, 蒋 外 文, 朱 华.Web 文 本 挖 掘 中 数 据 预 处 理 技 术 研 究. 现 代 计 算 机 ( 专 业 版 ),2009,(3):48-50. 5 陈 龙, 范 瑞 霞, 高 琪. 基 于 概 念 的 文 本 表 示 模 型. 计 算 机 工 程 与 应 用,2008,44(20):162-164. 6 刘 金 岭. 基 于 语 义 的 高 质 量 中 文 短 信 文 本 聚 类 算 法. 计 算 机 工 程,2009,35(10):201-202. 7 廖 浩, 李 志 蜀, 王 秋 野 等. 基 于 词 语 关 联 的 文 本 特 征 词 提 取 方 法. 计 算 机 应 用,2007,27(12):3010. 8 Liu B. Web Data Mining. Chicago: Springer Press, 2006. 120-121. 9 游 春 晖. 基 于 语 义 情 感 倾 向 的 文 本 相 似 度 计 算. 西 安 : 电 子 科 技 大 学,2008. 10 Pang J, Xu DP, Feng S, et al. A Novel Clustering Approach Based on Graph Similarity for Chinese Blogs on Authors Sentiment. The 7th International Conference on Fuzzy Systems and Knowledge Discovery. Yantai: Yantai University Press, 2010. 2344-2348. Research and Development 研 究 开 发 121