Online Judge System 设计与实现

Online Judge System 设计与实现

摘要

电子计算机自产生之日起就体现了其强大的生命力，短短几十年的时间，计算机已经逐渐渗透到了我们这个社会工作和生活的各个领域，并且发挥着越来越重要作用，成为人们工作、学习、科学研究的得力助手。它在教育领域同样发挥着相当重要的应用，过去传统的ftp, email方式提交学生程序作业并进行手工评判的方法，其繁重的工作量在我们今天看来是无法想象的。在高等院校的教学中，计算机方面的课程，特别是程序设计语言课程，具有实践性特别强的特点。它要求学生不仅仅要学习理论知识，还必须进行大量的实践，才能真正掌握知识，在实践应用中发挥作用。而在目前的教育、考核方式下，却不能真正考核出学生的真实水平，特别是在实践方面的水平，也不能引导学生以有效的方式来学习这些课程。各种强大的软件系统伴随着计算机硬件的飞速发展而发展，使得今天我们利用计算机来实现智能在线评判的想法可以得以实现。

本文针对现行的Online Judge系统进行了分析，综合了各系统的功能特点，提出了系统的设计方案和开发原理，实现了程序设计竞赛评判过程的自动化，标准化，以实时的方式反馈回学生评判结果，用户使用方便等功能特色。

本系统前台开发基于Apache + PHP + MySQL，后台开发基于Qt工具包。详细地介绍了程序评判流程（提交，编译，运行，测试等），程序运行的原理及程序运行时资源的管理，对系统模块的划分和后台的设计进行了详尽的说明。

本文结构清晰，首先简明的阐述了评判系统的开发背景，研究现状，目的和意义，然后针对系统的目标进行了总体的构架设计，最后根据设计思想提供了各个模块的设计细节。通过全面的论述得出该系统在各个方面的性能分析。

关键词：在线评判系统；进程管理；多线程；模型

The Design and Implementation of Online Judge System Abstract

Computer shows its strong vitality since it has invented, and within few decades time, computer has gradually infiltrated into our society in all spheres of work and life, and is playing an increasingly important role in people’s work, study and research. It also plays an important application in the field of education. The traditional ftp, email submission of student assignments and then judge them by hand one by one, now this method shows its heavy workload and is unimaginable. In teaching of high schools, many computer courses are demanded with strong practical capability, especially some programming language courses. It requires that students study not only theory knowledge but also lots of practice so that they master knowledge factly and bring into use in actual applications. However, on the way of today’s teaching and examining, the student’s genuine level would not be estimated properly, in particular, in practicing aspects. Of course, it can not lead students to learn these courses efficiently. Various powerful computer software systems come along whih the rapid development of hardware make it possible to achieve the thought of the intelligent judging online.

This thesis analysis several current Online Judge System, and synthesizes the functional features of each system, then raise the principles of the system design and development, and achieve the programming contest judging process automation, standardisation, returning real-time results to students, convenience of use and other functional features.

The development of the front-end of this system based on Apache, PHP and MySQL, the back-end development based on Qt development toolkit. There are detail presentations of the programming judging procedure: ssubmit the programming source code, compile, run and test the answer, etc., the program running principles and the runtime resources management. And explains the system modules division and the back-end designs.

In this paper the structure clear. First concisly states the background of the Online Judge System, its current researches, purpose and meaning. Then focus on the overall framework design to the system’s goals. Finally shows the design details of each module according to the design ideas, and obtained

the various aspects of performance analysis information through comprehensive exposition of the system. Keywords: online judge system; process management; multi-thread; model

前言

1 课题背景

ACM/ICPC(ACM International Collegiate Programming Contest, 国际大学生程序设计竞赛)是由国际计算机界历史悠久、颇具权威性的组织 ACM（Association for Computing Machinery，国际计算机协会）主办的，世界上公认的规模最大、水平最高的国际大学生程序设计竞赛，其目的旨在使大学生运用计算机来充分展示自己分析问题和解决问题的能力。该项竞赛从1970年开始举办，一直受到国际各知名大学的重视，并受到全世界各著名计算机公司的高度关注，在过去十几年中 APPLE、AT&T、MICROSOFT 和 IBM 等世界著名信息企业分别担任了竞赛的赞助商。可以说，ACM 国际大学生程序设计竞赛已成为世界各国大学生最具影响力的国际级计算机类的赛事， 是广大爱好计算机编程的大学生展示才华的舞台，是著名大学计算机教育成果的直接体现，是信息企业与世界顶尖计算机人才对话的最好机会。

Online judge system 是基于该背景下提出的一个程序设计竞赛评判系统，它对用户提交的程序源文件进行编译，运行，评判，给出用户的答题反馈信息，对用户答题情况进行统计排名等。

2 课题的提出

在实现计算机运用和信息网络化的今天，效率的大幅提高以及信息交换的深入和扩大, 使人类的生活越来越离不开数字化、信息化。信息决定着我们的生存，这已是不争的事实。以多媒体计算机技术和网络通讯技术为主要标志的信息技术，对当代社会产生着重大的影响，改变着我们的工作方式、学习方式和生活方式。信息技术在教育领域的运用是导致教育领域彻底变革的决定性因素，它必将导致教学内容、手段、方法、模式甚至教学思想、观念、理论以及体制的根本变革。

随着信息化进程的飞速发展以及计算机技术的普及，高等院校开设了越来越多的计算机课程。和传统的课程比较，计算机课程具有实践性很强的特点。学生要学好这些课程不但要认真学习理论知识，还需要大量的实践训练。例如，C 语言课程的学习，就需要编写大量的程序，才能够积累足够的经验，真正掌握程序设计的方法，编写出正确、高效的程序。对传统课程的考核多采用笔试的方式，但是，对于计算机方面的课程，特别是程序设计语言类课程这是不够的，因为它并不能促使学生在平时的学习中加强实践的锻炼。如何对这些课程进行有效的考核，成为一个长期工作在第一线的计算机教育工作者反复思考和不断探索的问题。

在目前的教学方式中，多数高等院校基本上还是采用基于传统方式的笔试来考核学生的计算机课程水平，然后在此基础上稍作补充。在上机实践考试中，学生采用FTP，Email，甚至手写的方式提交编程作业，老师需要对他们的作业进行一一批阅，相当多的时候，任课教师从学生处得到的是一些低效的，甚至不能运行通过的源代码，可是却要花费不少时间来判断分析学生程序到底在什么地方出错，然后给出相应的得分。这需要老师和学生花费很多的精力，效果也不是很好。学生更无法得知自己所编写的程序存在哪方面的问题，因而不能有效及时地进行更正。而Online Judge可以自动批阅作业并给出成绩，并且直接统计学生作业的提交情况，以及成绩的登记。这给老师带来了很大的方便，同时学生也可以通过Online Judge直接查询答题状况。

3 研究现状

现在已有不少学校采用由计算机进行编程作业评判的方式来对学生的作业进行考核。但更多的情况下是学生的编程作业通过FTP，Email等方式提交给老师后，由老师直接对程序以及程序的相关文档进行阅读，采用计算机对程序直接进行评判还不是很普遍。总的来说，在对编程作业的提交进行后处理方面已经有了一定程度的研究，而且与此课题相关的一些技术，像对程序的后处理在ACM等领域已经普遍运用。已有相当多的高校建立了题库和平台。大部分平台是基于 ACM 程序设计竞赛规则而开发的，有的平台是基于程序设计题目中的“得分点”而设计的。

国内目前已有很多学校开发了自主的评判系统，如：http://acm.zju.edu.cn/ 、http://acm.pku.edu.cn/JudgeOnline/ 。并且北京大学提供了 free version of Judge Online.

4 课题研究的目的和意义

采用 Online Judge 后，老师可以通过对参数进行设置，限制学生提交的编程作业的类型、文件大小、运行时间长短和空间大小。学生在提交编程作业时能够很快的得到作业是否正确的反馈。一方面，Online Judge 可以对作业进行自动编译，检查出程序是否存在语法错误；另一方面，它还能验证程序是否能得到正确结果，以及所花费的代价（时间和空间上的）。根据后处理的结果与相应的参数设置，Online Judge 能自动给出学生此次编程作业的成绩。这大大地减小了学生提交错误程序的概率，还能给出与程序相应的成绩。当然老师也可以进行再

次审查，对学生的作业提出评语，修改成绩等。这种方式完全模拟了使用程序设计语言解决实际问题的过程，编写程序、不断测试修改、根据结果反馈修改程序。这样的考试方式对学生的学习过程具有很好的指导作用。与此同时，还消除了老师在检查作业的过程中的主观因素，增加了学生之间的公平性。

Online Judge 的实现，能很快地运用到现实的学习生活中去，有效的考核学生的真实水平，促使学生更好的学习计算机知识，强化学生的实践能力，给学生和老师带来立竿见影的效果；极大地提高了学生和老师双方面的效率，减轻了老师在教学管理上的负担；还使学生将来能更好地适应快速发展的信息化时代；进一步发挥出计算机网络对当今教育领域甚至其他行业的突出贡献。

系统分析

1 现行在线评判系统分析

通过对国内大多数在线评判系统的研究，提取其优点总结其中的不足之处。很多系统功能不全，使用不方便。有的服务器响应速度很慢，评判信息不够精确，详细；有的不能支持现行流行的各种编程语言；有的系统维护管理机制繁琐，不易扩展与升级等。因此开发一个全功能，使用简单方便，易于扩展升级维护的在线评判系统很有必要。

2 可行性研究

对现有系统的功能进行分析后，下面就本着减少不必要的投入过多的人力物力的原则，对系统的开发进行可行性分析。一是可能性，二是必要性。通过可行性研究，可避免盲目投资。下面从三方面来讨论：

1. 经济可行性。经济可行性是指开发系统的费用，主要是指一个新的系统开发所需要的成本费用和人员费用，并与估计的新系统收益进行比较，看是否有利。本系统所需的软件和工具包均无需购买，apache + php + mysql 和 Qt 都有开源版本，现有的计算机硬件就可以满足要求，因此，在经济上是可行的。

2. 应用可行性。由于现在大部分大中专学校缺乏在线评判系统，或是有的系统使用不便，功能不全面。教师对程序设计作业评判工作越来越繁重，因而一个可以实现自动评判的软件必不可少，而现有的软件还不能满足教师的需要，此外现在校园网络发达，基于这些原因，我开发的在线评判系统是可行的，这样不仅减轻教师的负担，而且评判结果更具公平性、客观性，能够准确地反映教学质量，有利于选拔人才，促进教学改革。

3. 技术可行性。技术可行性是指利用现有的设备，软件及技术人员，新系统的目标能否达到。本系统使用的 php 适应性好，mysql 速度快而且跨平台，Qt 作为后台开发，我能熟练应用它们。因此，在技术上是完全可行的。

3 竞赛规则

参赛队员以小组的形式参赛，每小组 3 人，由队长及 2 名队员组成，并为每组取一队名。比赛时间一般为 5 小时，6 至9 个题目，每个参赛队员共用一台电脑答题。

参赛队伍首先根据解题数目进行排名。在决定获奖队伍时，如果多支队伍解题数量相同，则根据总用时进行排名。总用时由每道解答正确的用时的和。每道题目的用时将从竞赛开始到题目解答被判定为正确为止，其间每一次评判未通过将被加罚 20 分钟的时间，未正确解答的题目不记时。

参赛队员在比赛场地在自已的电脑上答题，然后将源代码复制到提交页面的代码文本框中，选择相应的编译选项后，提交给服务器进行评判。服务器根据用户答题情况返回评判结果反馈信息，具体说明如下：

Waiting: The judge is so busy that it can't judge your submit at the moment, usually you just need to wait a minute and your submit will be judged. Judging: The judge is juging your problem now. Accepted: OK! Your program is correct!

Presentation Error: Your output format is not exactly the same as the judge's output, although your answer to the problem is correct. Check your output for spaces, blank lines, etc. against the problem output specification.

Wrong Answer: Correct solution not reached for the inputs. The inputs and outputs that we use to test the programs are not public (it is recommendable to get accustomed to a true contest dynamic). Runtime Error: Your program failed during the execution (illegal file access, stack overflow, pointer reference out of range, floating point exception, divided by zero, etc.). Time Limit Exceeded: Your program tried to run during too much time.

Memory Limit Exceeded: Your program tried to use more memory than the judge default settings. Compile Error: The compiler could not compile your program. Of course, warning messages are not

error messages. Click the link at the judge reply to see the actual error message.

No Such Problem: Either you have submitted a wrong problem ID or the problem is unavailable. Out Of Contest Time: This message can only appear during a contest, if a program is submitted out of contest time.

Restricted Function: Your program tried to call restricted functions. For example, maybe you have tried to open a file which is forbidden.

4 系统功能分析

1. 用户操作界面。这是用户与系统交互的手段，因此要做到人机界面友好化，操作方便，并有相应的操作信息提示。

2. 编译模块。应该支持各种常用程序设计语言，如 C, C++, Java, Pascal 等。使用户真正体会到程序设计竞赛的灵魂是算法的设计与实现，给予竞赛队员更大的发挥空间。

3. 程序运行与测试。这是该系统的核心，主要是监控程序的运行状态，运行的时间空间消耗，运行的权限管理，以及运行结果的评判，尽量给出用户确切详细的信息。

4. 管理员赛事管理。主要是参赛队员的管理，赛题管理，赛事例程管理。

5．用户管理。系统做出来是要给用户使用的，既然有用户就得对其进行管理。用户管理听起来好像简单，实际上涉及到的内容却很复杂。包括以下几个方面：

（1）用户登陆。此系统要有一定的加密功能。因为程序设计竞赛是用来选拔学生用的，竞赛开始之前必须要保密，否则将影响竞赛结果的真实性，公平性。鉴于此原因，每位使用该系统的用户都必须通过自己的用户名和密码进行登陆后，才能正常使用。另外，为了防止有人恶意破译密码，必须采用验证码机制。

（２）修改密码。既然每位用户都有自己的密码，而同一个密码如果用的时间太长，就有可能被别人记住，为了加强系统的安全性，应该定期修改密码，这就要求系统具有修改密码的功能。

（３）用户权限。使用此系统的用户很多，但为了增加系统的安全性，就应该对每位用户指定权限，否则如果每个人都有对数据库的操作权限，很难保证对数据库不了解的用户对数据库进行误操作，或通过非法访问数据库获取机密信息。

（４）添加用户。为了动态维护和管理用户，即用户数量不是一成不变的，可能会有所增加，因此系统还需要具有添加用户的功能。另外， 每一轮的竞赛都将会有新成员的加入。

（５）删除用户。如前所说，用户不是固定的，由于人事变动等原因，有的用户名可能不再使用了，所以系统还应该有删除用户的功能。

5 系统设计的目标

准确。能够正确评测出用户程序的结果。特别是以下几个小的方面：给出正确的 Compile Error 信息。Presentation Error 和 Wrong Answer 的区分。如何准确测量用户程序的执行时间。如何准确测量用户程序执行时所用的内存数量。

稳定。一方面体现在网站的架设上，要求访问页面快速；另外体现在判题的速度上。同样程序多次重复提交时结论相同，参数（运行时间和内存）基本一致。对于大量并发访问具有很强的伸缩性。

安全。由于 Online Judge System 系统的特殊性，在通常网站安全设置的基础上，由于可以执行用户程序，还要在安全上作更多的考虑。如：防止用户将题目测试数据外传。如通过网络将输入数据传走。防止用户通过程序获取服务器内部信息。如 passwd 文件。防止由于用户有意破坏系统。如用户程序执行 system(”reboot”)，或者最经典的while(1) fork(); 代码。防止无意的系统破坏。如由于缓冲区溢出造成的错误。

6 主要研究内容

这次课题主要是完整的开发整个程序设计竞赛平台，实现竞赛评判的自动化，标准化。在用户提交源程序时，能自动地进行编译，运行和测试，并给出详细确切的评判结果。本次课题的主要研究内容包括： （1）实现编译模块对各种编程语言的支持；

（2）在运行器中，通过调用系统的进程参数信息，以达到对程序运行时的时间，内存消耗精确的测量，能够给出准确的运行时错误信息；

（3）测试器中，要能准确的区分 Presentation Error 和 Wrong Answer； （4）实现对提交的程序作业快速的评判，及时响应用户的操作； （5）做到界面友好化，方便用户使用，方便管理员维护； （6）对各类用户进行严格的操作权限控制；

在实现以上内容的基础上，软件设计采用基于面向对象的思想，各模块定义标准的接口，方便模块间的复用，使得系统功能更易扩展，维护。

7 开发工具的选择

7.1 Apache + PHP + MySQL

Linux 以其安全可靠、代码开放、低成本和丰富的第三方软件，受到网站设计人员的青睐，其中 Apache＋MySQL＋PHP 更是引人注目，再加上 Mod―Auth―MySQL、phpMyAdmin 等模块的支持，使网站开发人员更是如虎添翼。其中 Apache 是网站服务程序，功能类似于微软的 IIS 信息服务器；MySQL 是一种多用户、多线程的数据库服务器，它以简单易用而著称，即使你对数据库了解不深也没关系，但你千万别担心它的功能和安全问题；PHP 是一种新兴的编程语言，语法上类似于 C 语言，功能很强；phpMyAdmin 就是用 PHP 编写的用于 MySQL 数据库管理的免费软件；Mod―Auth―MySQL 是 Apache 用于用户身份认证的第三方模块。由此，我选择 Apache＋MySQL＋PHP 来开发这个前台系统。 1．PHP 简介

PHP 是一种功能强大的语言和解释器，无论是作为模块方式包含到 web 服务器里安装的还是作为单独的 CGI 程序程序安装的，都能访问文件、执行命令或者在服务器上打开链接。PHP 是特意设计成一种比用 Perl 或 C 语言所编写的 CGI 程序要安全的语言。而且 PHP 是免费的，他和免费的 MySQL, Apache 搭配被称作黄金组合，而且 PHP是开放源代码的，跨平台是 asp.net 不能抗衡的。在服务器领域大概有85%是用 Linux 做系统，很少有企业用 Windows，第一安全性差，第二成本高。因此 php 被广泛使用。 2．MySQL 简介

目前市场上数据库的主流厂商及产品有 Microsoft SQL SERVER 2000、ORACLE 9i、MySQL 等，SQL SERVER 只适用于 Windows 平台，而且购买昂贵，ORACLE 9i 虽然功能很强，但操作复杂，不易学习，而且更昂贵，MySQL 对 Linux 和 Windows 系统的服务器兼容性都很好，而且免费，学习也比较简单。 7.2 Qt

Qt 是基于标准 C++ 构架的高性能，跨平台的软件开发工具包。除了可扩展的 C++ 类库，Qt 还包含了使开发程序根快更直接的工具集。Qt 的跨平台能力和国际化支持使得 Qt 应用达到最大可能的市场。

自从 1995 年，Qt 的 C++ 框架一直是商业应用程序的核心。使用 Qt 的公司和组织各种各样，如 Adobe, Boeing, IBM, Motorola, NASA, Skype, 还有很多的较小的公司和组织。在增加更强大功能的同时，Qt 4 设计得比以前版本更容易使用。Qt 的类都是完美并提供一致的接口,以协助学习，减少开发工作量，提高程序员的生产力。Qt 一向是完全面向对象。

系统设计

系统架构采用分离可缩放结构。前端服务器负责 Web 访问，后端 Judge 服务器负责编译，运行和测试程序。双方通过数据库耦合。Judge 服务器与 Internet 没有连接，彻底保证测试数据不被外泄。

前端设计基于 B/S 模式模式进行 Web 服务器设计，后端 Judge 服务器采用多线程，多进程并发处理机制，在保证系统稳定性的同时极大地提高系统的响应速度。整个系统采用面向对象的思想进行设计。

1 设计原则

1．可靠性 系统中的软/硬件及信息资源应满足可靠性设计要求，并能保证系统长期安全的运行； 2．安全性 系统应具有必要的安全保护和保密措施；

3．容错性 系统应具有较高的容错能力，有较强的抗干扰性，对各类用户的误操作应有提示或自动消除的能力；

4．可扩充性 系统的软件应具有扩充升级的余地，可灵活地进行功能的扩充，不可因软/硬件扩充升级或改型而使原有系统失去作用； 5．实用性 注重采用成熟而实用的技术，使系统建设的投入产出比最高，能产生良好的社会效益和经济效益； 6．易操作性 坚持最终面向用户的原则，建立友好的用户界面，使用户操作简单直观，易于学习掌握。

2 评判过程

系统评判过程完全符合程序设计解决实际问题的过程。用户先在自己的计算机上编写好程序，经过运行，测试后，将程序源代码提交到在线评判服务器。在服务器端，系统按照一定的规则从缓冲区中选取一个题目进行评判。首先对源程序进行编译，如果程序存在语法错误，则返回语法错误信息（警告信息不算错误信息），否则，评判系统将运行编译通过后的可执行程序，在用户程序运行过程中，对程序运行所需的系统资源进行严格的限制，防止恶意程序的攻击。在程序运行正常结束后，对运行的结果进行测试，如果是结果正确，则更新用户的排名信