研究基于ACM程序设计竞赛在线评测系统解决方案

　　引言

    ACM国际大学生程序设计竞赛标志ACM国际大学生程序设计竞赛（英文全称：ACM International Collegiate Programming Contest（ACM-ICPC或ICPC）是由美国计算机协会（ACM）主办的，一项旨在展示大学生创新能力、团队精神和在压力下编写程序、分析和解决问题能力的年度竞赛。竞赛规模的迅速扩大对阅卷工作的自动化、高效性、合理性和公正性提出了更高的要求，建立一套准确、高效的程序评测系统成为非常迫切的需求。本文给出了一种网络自动化的程序性能分析评价系统——ACM国际大学生程序设计竞赛在线评测系统的实现方案。

　　1 评测系统简介

　　本系统提供了对C、C++、Java三种语言所编写的程序进行处理的功能。用户按照竞赛题目的要求，通过对问题的分析并给出解决方案后，就可以向系统提交解决问题的源代码程序。系统可以根据用户提供的源代码，采取相应的程序语言环境编译、运行。在编译与运行正常以后，系统按照题目要求来判断该程序结果否正确，同时给出程序的运行时间、内存的开销等情况，根据程序性能信息表来判断各个用户的得分情况。

　　系统运行于Linux操作系统，借助Linux操作系统所提供的多任务、多线程功能及其稳定的性能和开源的内核，从而大大减少程序员书写系统代码的工作量，也提高了系统的运行效率。代码是用C语言编写的，通过自己编写函数或调用C语言内部函数来访问系统所使用的资源。

　　2 评测系统的体系结构

　　评测系统网络体系结构采用先进的B/S模式的三层架构，如图1所示，这种结构符合面向服务（SOA）的模块设计，模块耦合性低，使得业务逻辑的添加、修改较为容易，并且网络通信安全性能方面也大为提高。用户通过浏览器连接评测系统，表示层UI 是系统呈现给用户的使用界面，用户通过 UI 进行登录、浏览、提交代码等操作。业务逻辑层BL负责实现根据性能信息表数据评分等除测试部分以外的各模块的功能。本系统将评测部分（主要是黑盒测试）从业务逻辑层中独立了出来，成为一个专门的测试模块，这种做法的优点是对测试模块的修改、增删都很容易进行。数据库DB主要用来存储用户提交的程序性能信息表及用户信息表等，程序性能信息表中主要包括程序的各种性能信息，例如是否通过编译、是否超出时间、是否正常结束、语言类别、结果是否正确、代码运行时间、内存开销、CPU占用量、代码长度等。测试模块从数据库取得未测试代码，进行评测，将程序性能信息表中相关项的评测结果返回给数据库，业务逻辑则从数据库取得程序性能信息表，并根据表中各项数据评分，对于未通过编译、超出时间、非正常结束、结果不正确的程序按不合格处理，对于上面各项都合格的则按程序性能信息表中其余项进行综合评分。

　　3 评判原理

　　对程序编译与运行过程中出现的错误，系统会根据错误的不同给出相应的提示，例如是编译错误或者是运行错误。如果编译和运行都正确，系统将进一步通过相应的题目要求、对程序要求给出的输入和程序输出的结果，来判断该程序是否正确。

　　在进行程序评判时，先启动服务器评测进程，在侦听到有提交记录时，系统立即对提交记录的相关题目进行评判。每个问题均对应一组数据，系统设计时采用Linux管道来处理，评判进程启动一个子进程来编译运行用户提交的程序，读入该题目的输入数据，评判程序每次从管道读入一个字符与标准输出数据比较，如果两个文件完全一样，则表示程序正确；如发现只是相差空格、Tab、回车，则给出该程序为输出格式错误信号；如果发现其他字符的不匹配，则立即中止该程序，则给出该程序为结果错误的信号Wrong Answer。从程序运行时刻开始计时，在时间允许范围之内，得到了正确答案，则此提交程序符合题目要求并通过系统时间和内存的限制，给出接受的信号。反之，如果答案错、或者表达错、运行错等，则向该进程发出SIGKILL信号，强行中止该进程，对数据库记录进行相应的修改。运行流程如图2所示。

　　4 程序内容分析

　　为了能有效地解决和判断用户程序对系统资源的使用情况，系统定义了rusage结构体。该结构体具体信息为：

　　struct rusage {

　　struct timeval ru_utime;             

　　struct timeval ru_stime;           

　　long ru_minflt;                           

　　long ru_majflt;                           

　　};

　　ru_utime和ru_stime成员变量包含了在用户模式和系统模式中执行时间的总和。其结构都为timeval结构。

　　ru_minflt成员指不需要I/O的页缺失数。

　　ru_majflt值指需要I/O的页缺失数。

　　有时，一个进程会被调出内存，以提供空间给其他进程使用。ru_nswap指的就是一个进程被调出内存的次数。

　　通过该结构体就可以统计出各用户程序对资源的占用情况，通过调用函数int getrusage（int who, struct rusage *rusage）对用户程序运行时间和内存占用情况进行分析统计。

　　统计程序运行时间：

　　passtime=usage.ru_utime.tv_sec+usage.ru_stime.tv_sec+（float）（usage.ru_stime.tv_usec+usage.ru_utime.tv_usec）/1000000;

　　统计程序所占内存的开销：

　　usedMemory = usage.ru_minflt*4

　　通过统计该两项，能计算出程序运行时间和内存使用情况的数据，为结果排序做准备。

　　5 系统安全处理

　　用户提交的程序在服务器上运行，为了保证系统安全运行、减少或杜绝故障的发生，在解决安全故障方面主要有以下几个方面。

　　（1） 文件操作

　　为了让用户提交上来的程序不破坏本机的文件系统，本设计采用了管道技术，在执行用户程序之前，先把输入流定向到标准输入文件，然后使用chroot命令改变用户程序的执行目录，让其只能在一个临时文件夹下面做操作。

　　（2） 网络操作

　　为了不让用户程序影响评判系统的设置，保证评判系统的公正性，必须禁止用户对网络的访问。系统通过对用户实行权限限制机制，判断系统在用户程序运行之前，通过调用Linux系统中setuid（99） 和 setgid（99）两个函数，让用户程序的拥有者权限降到，达到防止用户对网络使用的目的。

　　（3） 资源管理

　　资源管理的作用是对客户进程所使用的资源进行管理，Linux系统提供的资源限制函数setrlimit（），可以避免用户进程在运行的过程中过多地占用系统资源，以影响服务器系统的稳定性，终有可能导致系统的崩溃。

　　为了防止用户进程占用过多的资源，影响服务器系统的稳定，对用户进程在占用资源方面进行限制，主要考虑程序运行时间和内存占用两个方面，在程序运行之前，通过调用系统函数setrlimit（）来限制程序对系统资源的占用。函数setrlimit（ RLIMIT_AS,&memlim）和setrlimit（ RLIMIT_CPU,&timlim）分别用来限制用户程序对CPU和内存的占用情况，如果某用户的程序超过了系统对CPU和内存的设置值，该进程就会被自动中止，标志用户的程序不满足比赛要求。

    总结

　　通过对基于ACM国际大学生程序设计竞赛在线评测系统的分析研究，设计了相应的ACM测试软件，习题的测试难度可由指导老师自己设计。该软件也可以作为计算机学生算法测试工具，通过对该测试系统的使用，经过一定题量的练习，可以增强学生在算法方面设计的技能，为学生奠定雄厚的编程基础。相信该软件可以在学校的学生机中广泛应用。