ACM在线测评系统评测程序设计与实现

# ACM在线测评系统评测程序设计与实现 ### 写此文目的 - 让外行人了解ACM，重视ACM - 让ACMer了解评测程序评测原理以便更好得做题 - 让pythoner了解如何使用更好的使用python 在讲解之前，先给外行人补充一些关于ACM的知识。 ### 什么是ACM？ 我们平常指的ACM是`ACM/ICPC`（国际大学生程序设计竞赛），这是由ACM（Association for Computing Machinery，美国计算机协会）组织的年度性竞赛，始于1970年，是全球大学生计算机程序能力竞赛活动中最有影响的一项赛事。被誉为计算机界奥林匹克。 了解更多关于ACM的信息可以参考： - 百度百科：[http://baike.baidu.com/view/201684.htm](http://baike.baidu.com/view/201684.htm) - 维基百科：[http://zh.wikipedia.org/wiki/ACM国际大学生程序设计竞赛](http://zh.wikipedia.org/wiki/ACM国际大学生程序设计竞赛) - ACM国际大学生程序设计竞赛指南:[http://xinxi.100xuexi.com/view/trend/20120328/47133.html](http://xinxi.100xuexi.com/view/trend/20120328/47133.html) ### 什么是ACM测评系统？ 为了让同学们拥有一个练习和比赛的环境，需要一套系统来提供服务。 系统要提供如下功能： - 用户管理 - 题目管理 - 比赛管理 - 评测程序 典型的ACM评测系统有两种 - 一种是C/S模式，典型代表是PC^2。主要用在省赛，区预赛，国际赛等大型比赛中。官网：[http://www.ecs.csus.edu/pc2/](http://www.ecs.csus.edu/pc2/) - 另一种是B/S模式，国内外有几十个类似网站，主要用于平常练习和教学等。国内比较流行的OJ有： - 杭州电子科技大学：[http://acm.hdu.edu.cn/](http://acm.hdu.edu.cn/) - 北京大学：[http://poj.org/](http://poj.org/) - 浙江大学：[http://acm.zju.edu.cn/onlinejudge/](http://acm.zju.edu.cn/onlinejudge/) - 山东理工大学：[http://acm.sdut.edu.cn/sdutoj/index.php](http://acm.sdut.edu.cn/sdutoj/index.php) ### 评测程序是做什么的？ 评测程序就是对用户提交的代码进行编译，然后执行，将执行结果和OJ后台正确的测试数据进行比较，如果答案和后台数据完全相同就是AC(Accept)，也就是你的程序是正确的。否则返回错误信息，稍后会详细讲解。 ### ACM在线测评系统整体架构 为了做到低耦合，我们以数据库为中心，前台页面从数据库获取题目、比赛列表在浏览器上显示，用户通过浏览器提交的代码直接保存到数据库。 评测程序负责从数据库中取出用户刚刚提交的代码，保存到文件，然后编译，执行，评判，最后将评判结果写回数据库。 ### 评测程序架构 评测程序要不断扫描数据库，一旦出现没有评判的题目要立即进行评判。为了减少频繁读写数据库造成的内存和CPU以及硬盘开销，可以每隔0.5秒扫描一次。为了提高评测速度，可以开启几个进程或线程共同评测。由于多线程/进程会竞争资源，对于扫描出来的一个题目，如果多个评测进程同时去评测，可能会造成死锁，为了防止这种现象，可以使用了`生产者-消费者`模式，也就是建立一个待评测题目的任务队列，这个队列的`生产者`作用就是扫描数据库，将数据库中没有评测的题目列表增加到任务队列里面。消费者作用就是从队列中取出要评测的数据进行评测。 ### 为什么任务队列能防止出现资源竞争和死锁现象？ python里面有个模块叫`Queue`，我们可以使用这个模块建立三种类型的队列： - FIFO：先进先出队列 - LIFO：后进先出队列 - 优先队列 这里我们用到的是先进先出队列，也就是先被添加到队列的代码先被评测，保持比赛的公平性。 队列可以设置大小，默认是无限大。 生产者发现数据库中存在没有评测的题目之后，使用put()方法将任务添加到队列中。这时候如果队列设置大小并且已经满了的话，就不能再往里面放了，这时候生产者就进入了等待状态，直到可以继续往里面放任务为止。在等待状态的之后生产者线程已经被阻塞了，也就是说不再去扫描数据库，因此适当设置队列的大小可以减少对数据库的读写次数。 消费者需要从任务队列获取任务，使用`get()`方法，一旦某个线程从队列`get`得到某个任务之后，其他线程就不能再次得到这个任务，这样可以防止多个评测线程同时评测同一个程序而造成死锁。如果任务队列为空的话，get()方法不能获得任务，这时候评线程序就会阻塞，等待任务的到来。在被阻塞的时候评测程序可以被看做停止运行了，可以明显减少系统资源消耗。 队列还有两个方法： 一个是`task_done()`，这个方法是用来标记队列中的某个任务已经处理完毕。 另一个是`join()`方法，join方法会阻塞程序直到所有的项目被删除和处理为止，也就是调用`task_done()`方法。 这两个方法有什么作用呢？因为评测也需要时间，一个任务从队列中取出来了，并不意味着这个任务被处理完了。如果没有处理完，代码的状态还是未评判，那么生产者会再次将这个代码从数据库取出加到任务队列里面，这将造成代码重复评测，浪费系统资源，影响评测速度。这时候我们需要合理用这两个方法，保证每个代码都被评测并且写回数据库之后才开始下一轮的扫描。后面有代码示例。 我们使用如下代码创建一个FIFO队列： ```python #初始化队列 q = Queue(config.queue_size) ``` ### 如何有效得从数据库获取数据？ 这里我们以mysql为例进行说明。python有数据库相关的模块，使用起来很方便。这里我们需要考虑异常处理。 有可能出现的问题是数据库重启了或者偶尔断开了不能正常连接，这时候就需要不断尝试重新连接直到连接成功。然后判断参数，如果是字符串就说明是sql语句，直接执行，如果是列表则依次执行所有的语句，如果执行期间出现错误，则关闭连接，返回错误信息。否则返回sql语句执行结果。 下面这个函数专门来处理数据库相关操作 ```python def run_sql(sql): '''执行sql语句,并返回结果''' con = None while True: try: con = MySQLdb.connect(config.db_host,config.db_user,config.db_password, config.db_name,charset=config.db_charset) break except: logging.error('Cannot connect to database,trying again') time.sleep(1) cur = con.cursor() try: if type(sql) == types.StringType: cur.execute(sql) elif type(sql) == types.ListType: for i in sql: cur.execute(i) except MySQLdb.OperationalError,e: logging.error(e) cur.close() con.close() return False con.commit() data = cur.fetchall() cur.close() con.close() return data ``` 需要注意的是这里我们每次执行sql语句都要重新连接数据库，能否一次连接，多次操作数据库？答案是肯定的。但是，这里我们需要考虑的问题是如何将数据库的连接共享？可以设置一个全局变量。但是如果数据库的连接突然断开了，在多线程程序里面，问题就比较麻烦了，你需要在每个程序里面去判断是否连接成功，失败的话还要重新连接，多线程情况下如何控制重新连接？这些问题如果在每个sql语句执行的时候都去检查的话太麻烦了。 有一种方法可以实现一次连接，多次操作数据库，还能方便的进行数据库重连，那就是使用yield生成器，连接成功之后，通过yield将sql语句传递�