Online Judge System 设计与实现

Online Judge System 设计与实现摘要 电子计算机自产生之日起就体现了其强大的生命力，短短几十年的时间，计算机已经逐渐渗透到了我们这个社会工作和生活的各个领域，并且发挥着越来越重要作用，成为人们工作、学习、科学研究的得力助手。它在教育领域同样发挥着相当重要的应用，过去传统的ftp, email方式提交学生程序作业并进行手工评判的方法，其繁重的工作量在我们今天看来是无法想象的。在高等院校的教学中，计算机方面的课程，特别是程序设计语言课程，具有实践性特别强的特点。它要求学生不仅仅要学习理论知识，还必须进行大量的实践，才能真正掌握知识，在实践应用中发挥作用。而在目前的教育、考核方式下，却不能真正考核出学生的真实水平，特别是在实践方面的水平，也不能引导学生以有效的方式来学习这些课程。各种强大的软件系统伴随着计算机硬件的飞速发展而发展，使得今天我们利用计算机来实现智能在线评判的想法可以得以实现。 本文针对现行的Online Judge系统进行了分析，综合了各系统的功能特点，提出了系统的设计方案和开发原理，实现了程序设计竞赛评判过程的自动化，标准化，以实时的方式反馈回学生评判结果，用户使用方便等功能特色。 本系统前台开发基于Apache + PHP + MySQL，后台开发基于Qt工具包。详细地介绍了程序评判流程（提交，编译，运行，测试等），程序运行的原理及程序运行时资源的管理，对系统模块的划分和后台的设计进行了详尽的说明。 本文结构清晰，首先简明的阐述了评判系统的开发背景，研究现状，目的和意义，然后针对系统的目标进行了总体的构架设计，最后根据设计思想提供了各个模块的设计细节。通过全面的论述得出该系统在各个方面的性能分析。关键词：在线评判系统；进程管理；多线程；模型The Design and Implementation of Online Judge SystemAbstract 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 peoples 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 todays teaching and examining, the students 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 systems 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 程序设计竞赛规则而开发的，有的平台是基于程序设计题目中的“得分点”而设计的。 国内目前已有很多学校开发了自主的评判系统，如： 、 。并且北京大学提供了 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 cant 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 judges 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 以其安全可靠、代码开放、低成本和丰富的第三方软件，受到网站设计人员的青睐，其中 ApacheMySQLPHP 更是引人注目，再加上 ModAuthMySQL、phpMyAdmin 等模块的支持，使网站开发人员更是如虎添翼。其中 Apache 是网站服务程序，功能类似于微软的 IIS 信息服务器；MySQL 是一种多用户、多线程的数据库服务器，它以简单易用而著称，即使你对数据库了解不深也没关系，但你千万别担心它的功能和安全问题；PHP 是一种新兴的编程语言，语法上类似于 C 语言，功能很强；phpMyAdmin 就是用 PHP 编写的用于 MySQL 数据库管理的免费软件；ModAuthMySQL 是 Apache 用于用户身份认证的第三方模块。由此，我选择 ApacheMySQLPHP 来开发这个前台系统。 1PHP 简介 PHP 是一种功能强大的语言和解释器，无论是作为模块方式包含到 web 服务器里安装的还是作为单独的 CGI 程序程序安装的，都能访问文件、执行命令或者在服务器上打开链接。PHP 是特意设计成一种比用 Perl 或 C 语言所编写的 CGI 程序要安全的语言。而且 PHP 是免费的，他和免费的 MySQL, Apache 搭配被称作黄金组合，而且 PHP是开放源代码的，跨平台是 不能抗衡的。在服务器领域大概有85%是用 Linux 做系统，很少有企业用 Windows，第一安全性差，第二成本高。因此 php 被广泛使用。 2MySQL 简介 目前市场上数据库的主流厂商及产品有 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 评判过程系统评判过程完全符合程序设计解决实际问题的过程。用户先在自己的计算机上编写好程序，经过运行，测试后，将程序源代码提交到在线评判服务器。在服务器端，系统按照一定的规则从缓冲区中选取一个题目进行评判。首先对源程序进行编译，如果程序存在语法错误，则返回语法错误信息（警告信息不算错误信息），否则，评判系统将运行编译通过后的可执行程序，在用户程序运行过程中，对程序运行所需的系统资源进行严格的限制，防止恶意程序的攻击。在程序运行正常结束后，对运行的结果进行测试，如果是结果正确，则更新用户的排名信息、答题数量、答题时间、问题列表的答题统计信息等。 整个系统的大致工作过程如图3-1所示，其中图上省略了系统各阶段的数据库操作说明部分。图1 评判流程3 系统模块图图2 系统模块 后端 Judge 服务器模块包括：程序运行器、守护进程、编译接口、用例测试器。 前端 Web 服务器模块包括：系统管理员、用户验证、排名统计、问题浏览、提交、查看运行状态。 系统管理员模块 只提供给系统管理员对比赛日程计划的控制，题库录入，参赛队员信息管理，比赛期间系统管理员没有任何的操作控制权限。 用户验证 维护用户比赛过程中各个页面操作的权限控制，身份验证。 排名统计 根据竞赛规则（如前）对用户进行排名。 问题浏览，提交，查看运行状态 各种界面设计 程序运行器 程序运行器执行编译产生的可执行代码，并事先设置该程序的权限和运行限制，准备输入输出重定向，然后产生解答输出。 判断程序运行的状态。其中要保证被执行的程序不能危害系统的安全，不能访问非授权信息，不能占用超过规定量的资源。 程序运行器是实现自动评判和保证系统安全的关键模块。如何自动限制用户程序的资源占用，获取用户程序执行信息，以及防止恶意用户的破坏都是值得重视的问题。 守护进程 管理比赛例程，监控 Judge 服务器的运行状态，帮助程序运行器完成对用户进程的监控，必要时终止用户进程。守护进程还负责与数据库耦合，取出数据库中尚未评判的程序，然后将程序的评判结果信息写回数据库。 编译模块 用于统一多个编译器的编译调用过程，支持多种程序设计语言，负责检查用户提交的程序语法，并编译产生可执行代码。如果编译器发现源程序语法错误，需要立即指出，不再继续该题的评判工作。 用例测试器 用例测试器对产生的解答输出对比标准测试数据进行测试，给出评判结论。 用例测试器需要注意的一个重要问题是，如何合理区分结果错误和格式错误。通常认为，只是空白字符的不同，以及字母大小写的不同就是格式错误，其它的就是结果错误。 数据库 用户基本信息表、答题进度表、答题结果表，题目列表，测试数据等。4 前端 Web 系统模型 前端 Web 系统，即给每个用户使用的客户端，负责接受用户的命令，将程序提交给服务器，并将服务器返回的结果显示给用户。对于这种类型的应用来说，有两种模式可以选择，一为客户/服务器（C/S）模式，二为浏览器/服务器（B/S）模式。 C/S 模式有很多优点，比如能够实现更丰富的用户操作方式，给用户更加丰富的用户体验。但它也存在很根本的缺点，即非常不容易管理，需要在每一个客户端安装程序。相对来说，B/S 模式就要方便很多，只需要客户端有一个浏览器就行。在线评判系统的目标是要在校园网上开展大型的练习或竞赛，同时，用户的复杂性操作的需求不显著，所以 B/S 模式是在线评判系统的最佳选择，其系统模型如图3.3 所示。图3 前端 Web 系统模型5 后端 Judge 服务器系统模型 评判模块对用户提交的解答进行评判。在目前的设计中，包含了两大类的评判器： （1）本地评判器。本地评判器和评判系统框架执行在同一个机器上。 （2）远程评判器。远程评判器可以运行在不同的机器上，形成一个由多台计算机组成的集群，以大大提高系统的可伸缩性。 服务器在评判过程中，不管是编译阶段，程序运行阶段，还是用例测试阶段，其工作量是相当大的。特别是当程序提交数量很多时，可能会造成提交的问题需长时间的等待才能够给予评判，这不仅影响了评判进度，还会影响前端 Web 服务器的执行速度。解决该问题的一种方案是提升服务器的硬件性能指标，如使用工作站，甚至巨型机当服务器，或分布式系统计算机。另一种解决方案是利用基于网络的多服务器系统并行执行。不管采用哪一种方案，在 Judge 服务器设计过程中，应尽量提高评判过程中的并行执行特性，如多线程，多进程，多服务器，流水线系统结构等。图4 并行系统结构并行执行的系统结构 并行执行的系统结构是通过多线程，多进程或多 Judge 服务器并行执行一个程序评判的全过程。多个 Judge 服务器通过缓冲区与评判系统的前端 Web 服务器耦合。缓冲区是一个临界资源，必须采取相应的机制（信号量，互斥锁）使得多Judge服务器的同步与互斥。其参考模型如图3-4所示。 其中每台 Judge 服务器都相对独立的执行一个程序的评判全过程（即编译，运行和测试）。 流水线式系统结构 流水线式系统结构借鉴计算机组成原理中的流水线式系统设计模式。它是将一个任务分成相对独立的几个阶段，系统同时运行各个阶段，每个任务连续的从第一个阶段流向最后一个阶段完成一个任务的整体。 该评判系统后端Judge服务器分为两个阶段：编译系统模块，运行和测试系统模块。各个模块通过缓冲区衔接过度，其中个缓冲区也是临界资源。系统参考模型如图3-5所示。图5 流水线系统结构 从图中可以看出，每个系统相对独立地执行一个程序评判过程的相应阶段，但是一个题目的评判有可能编译或运行没有正常通过，因此并不一定流过该评判系统流水线的每一个阶段。6 数据库设计数据库是连接该系统前端Web服务器与后端Judge服务器的桥梁，因此良好的数据库设计至关重要。数据库中主要有用户注册信息表（userRegister），赛题表（problemLib），用户排名表（rankList），评判状态表（status）。各表的属性及表之间的联系如图3-6，图中每个加粗字体的属性为相应实体的主键。系统实现与测试1 数据库表结构数据库中表的名称：userRegister 主键：username数据库中表的名称：rankList 主键：rank数据库中表的名称：problemLib 主键：pid表4 状态表数据库中表的名称：status 主键：runID2 前端Web服务器 前端 web 服务器主要负责各种用户界面浏览和相关的数据库初始操作，它是用户进行比赛的环境。应该做到人性化的交互界面，操作简便安全，为用户提供友好的操作信息。 以下就各主要界面进行详细设计介绍，另附有相关测试图示。2.1 用户注册 填写用户注册信息 =确认后提交 =检查用户名是否合法、密码是否一致、及电话号码、邮箱是否符合格式 =注册成功，存入 userRegister 数据库并将 username 存入 rankList 表中的 team 字段。图1 用户注册界面2.2 用户登录 读取 userRegister 数据库中的 username 对应 password 字段与提交的 password 比较，进行身份验证。只有验证成功后，才能参与竞赛。图2 用户登录界面2.3 系统首页 主要显示比赛例程信息，几个主要链接，要求在比赛未开始之前不显示相关链接，以防止透露题目。图3 系统首页2.4 问题列表 读取数据库中的题库信息进行显示，包括相关的答题进度信息。图4 问题列表2.5 问题评判状态表 列出各个提交问题的评判结果，当结果为 Compile Error 时，返回编译的错误信息。按问题的提交时间逆序排列。图5 评判状态表2.6 竞赛排名表 该表每 30 秒刷新一次，以便获得实时的竞赛结果排名。首先根据答题数量逆序排列，答题数目相同的，再根据总时间升序排列。答题数目为零的不参与排名。图6 竞赛排名3 后端 judge 服务器 后端 judge 服务器评判流程图如图7。图7 后台 judge 数据流图3.1 编译模块 Gcc 编译器介绍 Linux 系统下的 Gcc（GNU C Compiler）是 GNU 推出的功能强大、性能优越的多平台编译器，是 GNU 的代表作品之一。Gcc 是可以在多种硬件平台上编译出可执行程序的超级编译器，其执行效率与一般的编译器相比平均效率要高20%30%。 Gcc 编译器能将 C、C+ 语言源程序、汇编程序和目标程序编译、连接成可执行文件。在Linux 系统中，可执行文件没有统一的后缀，系统从文件的属性来区分可执行文件和不可执行文件。而 gcc 则通过后缀来区别输入文件的类别。 Gcc 编译高级语言一般经历四个步骤：预处理(也称预编译，Preprocessing)、编译(Compilation)、汇编 (Assembly) 和连接 (Linking)。 Gcc 选项主要包括总体选项、告警和出错选项、优化选项和体系结构相关选项。表5 总体选项表6 告警和出错选项工作流程 进入当前环境，选取题目，设置编译选项（包括选择编译器，设置编译参数），编译，读取编译结果，判断编译结果（是否通过）。其主要代码如下： Class Compiler 的服务：图8 类 Compiler 的服务3.2 运行及测试器模块 程序与进程 进程（Process）是最初定义在 Unix 等多用户、多任务操作系统环境下用于表示应用程序在内存环境中基本执行单元的概念。以 Unix 操作系统为例，进程是 Unix 操作系统环境中的基本成分、是系统资源分配的基本单位。Unix 操作系统中完成的几乎所有用户管理和资源分配等工作都是通过操作系统对应用程序进程的控制来实现的。 C、C+、Java 等语言编写的源程序经相应的编译器编译成可执行文件后，提交给计算机处理器运行。这时，处在可执行状态中的应用程序称为进程。从用户角度来看，进程是应用程序的一个执行过程。从操作系统核心角度来看，进程代表的是操作系统分配的内存、CPU 时间片等资源的基本单位，是为正在运行的程序提供的运行环境。进程由四部分组成：PCB（进程控制块），正文段，数据段和用户堆栈。PCB 包括进程的编号、状态、优先级以及正文段和数据段中数据分布的大概情况。正文段存放该进程的可执行代码。数据段存放进程中静态产生的数据结构。用户堆栈存放进程中动态产生的数据结构。进程与应用程序的区别在于应用程序作为一个静态文件存储在计算机系统的硬盘等存储空间中，而进程则是处于动态条件下由操作系统维护的系统资源管理实体。 一个程序可以对应多个进程，而一个进程，只能对应一个程序。进程具有动态性，并发性，独立性等特点。 工作流程 选取题目，设置输入输出文件，运行，用例测试，判断结果。其中主要的代码如下： Class Executer 的服务：图9 类 Executer 的服务3.3 守护进程模块 通过使用两个线程并发地执行评判任务。类似于生产者消费者模型，其中 Daemon 是生产者，Starter 是消费者。可以是一个生产者，多个消费者，使得可以开启多个评判程序并行的执行任务，或是基于网络的多服务器相对独立的并行工作。必须采取相应的互斥访问机制以避免一个题目被重复的评判。 通过使用一个环形缓冲区将一个 Daemon 线程和一组 Starter 线程联系起来。只要缓冲区未满，Daemon 线程就可把从数据库中取出的未评判的问题号放入缓冲区中，同样，只要缓冲区未空，Starter 线程就可从缓冲区中取出题目进行评判。仅当缓冲区满时，Daemon线程被阻塞，类似地，仅当缓冲区空时，Starter 线程被阻塞。为了实现线程 Daemon 与 Starter 的同步与互斥，设置了两个私用信号量和一个公用信号量如下： * 公用信号量 mutex，初值为 1，表示没有进程进入临界区，它用于实现进城互斥。 * 私用信号量 freeBuffer，用于表示可用的缓冲区数，初值为 BufferSize。 * 私用信号量 usedBuffer，用于表示尚未评判的题目数量，初值为 0。 DaemonStarter 的线程描述如图10。图10 Daemon - Starter 线程描述 当答题状态为 Accepted 时，数据库表 rankList 的更新算法如图11。图11 数据库表 rankList 的更新算法 如果多次提交正确答案，则按照最后一次提交正确时进行参与评判统计。4 系统测试4.1 测试题目输入用例：输出用例：4.2 测试程序程序一：评判结果：Accepted程序二：评判结果：Compile Error./judge/src/2.c: In function main:./judge/src/2.c:8: error: syntax error at end of input程序三：评判结果：Presentation Error程序四：评判结果：Time Limit Exceeded程序五：评判结果：Wrong Answer程序六：评判结果：Runtime Error图6 E-R 图7 面向对象的系统设计 对于面向对象的软件系统来说，如何尽量提高系统的可维护性是一个核心的问题。实践证明，一个软件开发可能只需要半年的时间，而维护则需要花费很多年。一个软件项目在其生命周期之内花费在维护上的费用是花在原始开发上的费用的两倍甚至更多。 软件系统和硬件系统有很多不同之处。通常，硬件系统在开发完成之后，不会做太大的修改和扩展，其维护工作主要是保证硬件系统的正常运行，解决一些存在的错误和缺陷。但是，通常赋予软件系统的维护的含义却要大得多，软件的维护就是软件的再生。用户希望一个软件系统在其生命周期之内能够不断满足自己需求的变化。一个好的软件设计，必须能够允许新的设计要求以较为容易和平稳的方式加入到已有的系统中去，从而使这个系统能够不断焕发出青春。 什么样的系统设计才是好的系统设计？这个问题一直困扰着软件工程师们。一个好的系统设计应该满足的三条性质：可扩展性(extensibility)、灵活性(Flexibility)、可插入性(Pluggability)。这三条性质就是一个系统设计应当达到的目标。 （1）可扩展性。新的性能可以很容易的加入到系统当中去，就是可扩展性。 （2）灵活性。可以允许代码修改平稳的发生，而不会波及到其他模块，就是灵活性。 （3）可插入性。可以很容易的将一个类抽出去，同时将另一个有同样接口的类加入进来，就是可插入性。 那么，如何才能做出符合上述三项要求的设计呢？关键是恰当的提高软件的可维护性和可复用性。