Microsoft Word - 系统建设1.doc

Transcription

1 1 Online Judge 系 统 的 优 化 庄 奇 东 1,3, 王 键 闻 2, 张 楠 1,3, 张 爽 4, 任 娜 1 ( 沈 阳 工 程 学 院 信 息 工 程 系, 沈 阳 ) 2 ( 沈 阳 工 程 学 院 基 础 部, 沈 阳 ) 3 ( 沈 阳 工 程 学 院 电 力 系 统 信 息 安 全 重 点 实 验 室, 沈 阳 ) 4 ( 昌 兴 建 筑 工 程 有 限 公 司 ERP 软 件 事 业 部, 东 莞 ) 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 , China) 2 (Dept. of Fundamental Sciences, Shenyang Institute of Engineering, Shenyang , China) 3 (Key Lab of Information Security for Power System, Shenyang Institute of Engineering, Shenyang , China) 4 (ERP Software Division, Changxing Construction Engineering Co., Ltd, Dongguan , 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 的 一 个 核 心 部 分 [2] 近 年 来, 随 着 ACM/ICPC 竞 赛 体 制 在 国 内 的 普 及, 众 多 定 位 各 异 的 OJ 系 统 也 雨 后 春 笋 般 地 出 现 基 金 项 目 : 辽 宁 省 自 然 科 学 基 金 ( ); 沈 阳 市 重 点 实 验 室 建 设 资 助 项 目 ( ); 沈 阳 工 程 学 院 院 内 基 金 理 工 类 ( ) 收 稿 时 间 : ; 收 到 修 改 稿 时 间 : Research and Development 研 究 开 发 115

2 计 算 机 系 统 应 用 年 第 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 约 / /0.014 IIS7 约 / /0.029 Nginx0.8 约 / /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 多 核 评 测 单 核 单 线 程 环 境 下 的 时 间 测 量 Linux 和 Windows 以 及 Java 下 都 有 系 统 函 数 调 用 可 以 获 取 当 前 进 程 / 线 程 的 运 行 时 间 不 过 不 同 的 系 统 实 现 都 不 用, 而 且 用 法 也 不 同 [4] 从 测 试 程 序 段 所 在 位 置 上 讲, 可 分 为 在 待 测 任 务 中 插 入 测 试 代 码 和 通 过 另 外 一 个 程 序 测 试 两 种 ; 从 测 试 效 果 上 讲, 可 分 为 间 隔 计 数 ( 各 运 行 态 累 计 得 到 CPU 时 间 片 之 和 ) 和 周 期 计 数 ( 累 计 经 过 时 钟 周 期 数, 即 结 束 和 起 始 时 间 之 差 ) 两 种, 从 应 用 层 次 上 讲, 可 分 为 用 系 统 API 测 量 和 用 低 级 语 言 直 接 访 问 CPU 内 的 8254 计 数 器 测 量 两 种 图 3 单 核 系 统 下 的 物 理 时 间 图 1 多 核 评 测 的 系 统 架 构 但 是, 在 现 代 的 计 算 机 系 统 中 根 本 不 可 能 精 确 测 116 研 究 开 发 Research and Development

3 量 某 一 个 程 序 运 行 的 确 切 时 间 因 为 操 作 系 统 的 进 程 和 线 程 的 分 配 和 调 度 CPU 的 指 令 流 水 线 处 理 等 对 于 程 序 和 用 户 来 说 都 是 透 明 的 在 真 实 情 况 下 计 算 机 并 不 是 只 运 行 一 个 程 序 的, 待 测 进 程 的 优 先 级 调 度 策 略 系 统 负 载 同 步 或 线 程 切 换 各 种 中 断 共 享 的 多 用 户 网 络 流 量 高 速 缓 存 的 访 问 转 移 预 测 等, 都 会 对 计 时 产 生 影 响 例 如, 现 在 的 Linux 和 Windows 等 操 作 系 统 对 线 程 进 行 抢 占 式 调 度, 用 户 线 程 会 因 为 时 间 片 用 完 等 原 因 而 被 中 断 系 统 会 从 用 户 态 转 入 核 心 态, 即 使 在 线 程 队 列 上 没 有 其 他 线 程, 这 种 切 换 也 会 使 用 户 线 程 的 运 行 时 间 明 显 增 加 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

4 计 算 机 系 统 应 用 年 第 20 卷 第 8 期 猜 想 造 成 这 个 结 果 的 原 因 是 最 后 一 个 CPU 核 心 较 为 空 闲, 即 使 被 测 用 户 进 程 时 间 片 用 完 或 被 中 断, 也 在 很 短 时 间 内 被 重 新 调 度 而 获 得 CPU 时 间 片, 缓 存 指 令 管 线 等 资 源 并 未 丢 失 且 多 次 评 测 在 相 同 条 件 下, 从 而 得 到 了 较 强 的 一 致 性 文 献 [10] 说 明 了 多 CPU 系 统 中, 在 未 指 定 处 理 器 亲 和 性 的 情 况 下, 处 理 已 有 指 派 任 务 时, 外 部 的 中 断 往 往 被 操 作 系 统 全 部 交 与 第 一 个 CPU 即 CPU0 来 处 理, 这 也 在 一 个 侧 面 支 持 了 上 述 猜 测 文 献 [11] 提 出 了 The K-Best Measurement Scheme 的 测 量 方 法, 其 中 有 一 点 是 减 少 高 速 缓 存 不 命 中 给 我 们 程 序 执 行 时 间 带 来 的 影 响, 即 在 测 试 之 前 先 执 行 一 遍 程 序, 让 指 令 高 速 缓 存 和 数 据 高 速 缓 存 都 得 到 预 热 该 文 献 也 指 出, 任 何 一 次 单 独 的 测 量 都 无 法 精 确 获 得 进 程 运 行 时 间, 只 有 在 多 次 运 行 后 取 最 小 的 重 复 出 现 的 若 干 个 数 据 才 能 得 到 较 为 精 确 的 值 然 而 这 在 高 并 发 的 OJ 系 统 中 是 不 可 取 的 但 上 述 实 验 说 明, 在 多 核 系 统 中, 通 过 指 定 处 理 器 亲 和 性, 便 可 一 次 就 能 获 得 比 较 精 确 的 测 量 结 果 多 核 评 测 模 式 考 虑 使 用 一 台 多 核 评 测 机, 指 定 操 作 系 统 的 内 核 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 理 论 分 析 和 进 一 步 优 化 图 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 模 型 不 难 算 出 此 系 统 的 其 他 性 能 指 标, 如 表 研 究 开 发 Research and Development

5 表 3 假 设 下 各 种 不 同 的 模 型 的 性 能 指 标 4 评 测 机 4 队 4 评 测 机 单 队 6 评 测 机 6 队 6 评 测 机 单 队 服 务 强 度 ρ 平 均 队 长 Ls 平 均 等 待 队 列 长 Lq 平 均 逗 留 时 间 Ws 平 均 等 待 时 间 Wq 系 统 空 闲 概 率 P 等 待 时 间 小 于 5s 的 概 率 P(tq<5) 逗 留 时 间 小 于 10s 的 概 率 P(ts<10) 通 过 生 成 服 从 特 定 分 布 的 序 列 作 离 散 事 件 模 拟 得 出 的 结 果 也 与 表 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

6 计 算 机 系 统 应 用 年 第 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: 研 究 开 发 Research and Development

7 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, 康 海 燕, 樊 孝 忠, 汤 世 平. 基 于 J2EE 的 在 线 测 评 系 统 的 研 究 与 设 计. 计 算 机 工 程,2004,13: 何 静 雯.ACM/ICPC 评 测 系 统 综 述. 计 算 技 术 与 自 动 化, 2005,4: 王 辉, 胡 新 华, 张 广 泉. 集 群 式 程 序 设 计 竞 赛 评 测 系 统 设 计 与 开 发. 计 算 机 应 用 与 软 件,2009,9: 李 哲. 在 线 程 序 竞 赛 评 判 系 统 的 设 计 与 实 现 [ 硕 士 学 位 论 文 ]. 大 连 : 大 连 理 工 大 学, 周 伟 明. 多 核 计 算 与 程 序 设 计. 武 汉 : 华 中 科 技 大 学 出 版 社, 董 昊.Linux 在 多 核 处 理 器 上 的 负 载 均 衡 原 理. 淘 宝 核 心 系 统 团 队 博 客. [ ]. = Wikipedia. Processor Affinity. [ ]. 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: Hollinger D.Time Measurement. [ ]. 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, 张 胜, 洪 明. 基 于 Pocket PC 的 IDE 设 计 与 实 现. 计 算 机 系 统 应 用,2008,17(11): Reinders J. Intel Threading Building Blocks: Outfitting C++ for Multi-core Processor Parallelism. O Reily, Grune D. The software and text similarity tester SIM. [ ]. ( 上 接 第 75 页 ) 证 明, 基 于 概 念 的 向 量 空 间 模 型 比 基 于 词 语 的 向 量 空 间 模 型 的 聚 类 分 析 性 能 更 好 本 文 中 还 有 很 多 值 得 进 一 步 研 究 的 地 方 对 于 情 感 词 概 念 的 选 取, 本 文 直 接 选 用 了 第 一 义 项, 没 有 具 体 的 概 念 排 歧 工 作 在 使 用 k-means 算 法 进 行 聚 类 分 析 时, 每 次 随 机 选 取 的 簇 中 心 不 一 样, 使 得 聚 类 的 结 果 不 稳 定 今 后 需 要 在 情 感 词 概 念 提 取 以 及 算 法 优 化 方 面 加 强 研 究, 使 聚 类 结 果 性 能 更 好 参 考 文 献 1 杨 勇 涛.Web 舆 情 观 点 挖 掘 关 键 技 术 研 究. 成 都 : 电 子 科 技 大 学, 董 振 东, 董 强.HowNet s HomePage. com, 夏 天, 樊 孝 忠, 刘 林. 利 用 JNI 实 现 ICTCLAS 系 统 的 Java 调 用. 计 算 机 应 用,2004,24(12): 胡 静, 蒋 外 文, 朱 华.Web 文 本 挖 掘 中 数 据 预 处 理 技 术 研 究. 现 代 计 算 机 ( 专 业 版 ),2009,(3): 陈 龙, 范 瑞 霞, 高 琪. 基 于 概 念 的 文 本 表 示 模 型. 计 算 机 工 程 与 应 用,2008,44(20): 刘 金 岭. 基 于 语 义 的 高 质 量 中 文 短 信 文 本 聚 类 算 法. 计 算 机 工 程,2009,35(10): 廖 浩, 李 志 蜀, 王 秋 野 等. 基 于 词 语 关 联 的 文 本 特 征 词 提 取 方 法. 计 算 机 应 用,2007,27(12): Liu B. Web Data Mining. Chicago: Springer Press, 游 春 晖. 基 于 语 义 情 感 倾 向 的 文 本 相 似 度 计 算. 西 安 : 电 子 科 技 大 学, 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, Research and Development 研 究 开 发 121