给⼤家分享⼀篇ACM在线测评系统评测程序设计与python实现
写此⽂⽬的：
让外⾏⼈了解ACM，重视ACM。
让ACMer了解评测程序评测原理以便更好得做题。
让pythoner了解如何使⽤更好的使⽤python。
在讲解之前，先给外⾏⼈补充⼀些关于ACM的知识。
什么是ACM？
我们平常指的ACM是ACM/ICPC（国际⼤学⽣程序设计竞赛），这是由ACM（Association for Computing Machinery，美国计算机协会）组织的年度性竞赛，始于1970年，是全球⼤学⽣计算机程序能⼒竞赛活动中最有影响的⼀项赛事。被誉为计算机界奥林匹克。
了解更多关于ACM的信息可以参考：
百度百科：
：国际⼤学⽣程序设计竞赛
ACM国际⼤学⽣程序设计竞赛指南:
什么是ACM测评系统？
为了让同学们拥有⼀个练习和⽐赛的环境，需要⼀套系统来提供服务。
系统要提供如下功能：
⽤户管理
题⽬管理
⽐赛管理
评测程序
典型的ACM评测系统有两种
⼀种是C/S模式，典型代表是PC^2。主要⽤在省赛，区预赛，国际赛等⼤型⽐赛中。官⽹：
另⼀种是B/S模式，国内外有⼏⼗个类似⽹站，主要⽤于平常练习和教学等。国内⽐较流⾏的OJ有：
杭州电⼦科技⼤学：
北京⼤学：
浙江⼤学：
⼭东理⼯⼤学：
评测程序是做什么的？
评测程序就是对⽤户提交的代码进⾏编译，然后执⾏，将执⾏结果和OJ后台正确的测试数据进⾏⽐较，如果答案和后台数据完全相同就是AC(Accept)，也就是你的程序是正确的。否则返回错误信息，稍后会详细讲解。
ACM在线测评系统整体架构
为了做到低耦合，我们以数据库为中⼼，前台页⾯从数据库获取题⽬、⽐赛列表在浏览器上显⽰，⽤户通过浏览器提交的代码直接保存到数据库。
评测程序负责从数据库中取出⽤户刚刚提交的代码，保存到⽂件，然后编译，执⾏，评判，最后将评判结果写回数据库。
评测程序架构
评测程序要不断扫描数据库，⼀旦出现没有评判的题⽬要⽴即进⾏评判。为了减少频繁读写数据库造成的内存和CPU以及硬盘开销，可以每隔0.5秒扫描⼀次。为了提⾼评测速度，可以开启⼏个进程或线程共同评测。由于多线程/进程会竞争资源，对于扫描出来的⼀个题⽬，如果多个评测进程同时去评测，可能会造成死锁，为了防⽌这种现象，可以使⽤了⽣产者-消费者模式，也就是建⽴⼀个待评测题⽬的任务队列，这个队列的⽣产者作⽤就是扫描数据库，将数据库中没有评测的题⽬列表增加到任务队列⾥⾯。消费者作⽤就是从队列中取出要评测的数据进⾏评测。
为什么任务队列能防⽌出现资源竞争和死锁现象？python⾥⾯有个模块叫Queue，我们可以使⽤这个模块建⽴三种类型的队列：FIFO：先进先出队列LIFO：后进先出队列
优先队列在线代码运行器
这⾥我们⽤到的是先进先出队列，也就是先被添加到队列的代码先被评测，保持⽐赛的公平性。
队列可以设置⼤⼩，默认是⽆限⼤。
⽣产者发现数据库中存在没有评测的题⽬之后，使⽤put()⽅法将任务添加到队列中。这时候如果队列设置⼤⼩并且已经满了的话，就不能再往⾥⾯放了，这时候⽣产者就进⼊了等待状态，直到可以继续往⾥⾯放任务为⽌。在等待状态的之后⽣产者线程已经被阻塞了，也就是说不再去扫描数据库，因此适当设置队列的⼤⼩可以减少对数据库的读写次数。
消费者需要从任务队列获取任务，使⽤get()⽅法，⼀旦某个线程从队列get得到某个任务之后，其他线程就不能再次得到这个任务，这样可以防⽌多个评测线程同时评测同⼀个程序⽽造成死锁。如果任务队列为空的话，get()⽅法不能获得任务，这时候评线程序就会阻塞，等待任务的到来。在被阻塞的时候评测程序可以被看做停⽌运⾏了，可以明显减少系统资源消耗。
队列还有两个⽅法：
⼀个是task_done()，这个⽅法是⽤来标记队列中的某个任务已经处理完毕。
另⼀个是join()⽅法，join⽅法会阻塞程序直到所有的项⽬被删除和处理为⽌，也就是调⽤task_done()⽅法。
这两个⽅法有什么作⽤呢？因为评测也需要时间，⼀个任务从队列中取出来了，并不意味着这个任务被处理完了。如果没有处理完，代码的状态还是未评判，那么⽣产者会再次将这个代码从数据库取出
加到任务队列⾥⾯，这将造成代码重复评测，浪费系统资源，影响评测速度。这时候我们需要合理⽤这两个⽅法，保证每个代码都被评测并且写回数据库之后才开始下⼀轮的扫描。后⾯有代码⽰例。
我们使⽤如下代码创建⼀个FIFO队列：
如何有效得从数据库获取数据？
这⾥我们以mysql为例进⾏说明。python有数据库相关的模块，使⽤起来很⽅便。这⾥我们需要考虑异常处理。
有可能出现的问题是数据库重启了或者偶尔断开了不能正常连接，这时候就需要不断尝试重新连接直到连接成功。然后判断参数，如果是字符串就说明是sql语句，直接执⾏，如果是列表则依次执⾏所有的语句，如果执⾏期间出现错误，则关闭连接，返回错误信息。否则返回sql 语句执⾏结果。
下⾯这个函数专门来处理数据库相关操作#初始化队列q = Queue(config.queue_size)
1
2
需要注意的是这⾥我们每次执⾏sql语句都要重新连接数据库，能否⼀次连接，多次操作数据库？答案是肯定的。但是，这⾥我们需要考虑的问题是如何将数据库的连接共享？可以设置⼀个全局变量。但是如果数据库的连接突然断开了，在多线程程序⾥⾯，问题就⽐较⿇烦了，你需要在每个程序⾥⾯去判断是否连接成功，失败的话还要重新连接，多线程情况下如何控制重新连接？这些问题如果在每个sql语句执⾏的时候都去检查的话太⿇烦了。
有⼀种⽅法可以实现⼀次连接，多次操作数据库，还能⽅便的进⾏数据库重连，那就是使⽤yield⽣成器，连接成功之后，通过yield将sql语句传递进去，执⾏结果通过yield反馈回来。这样听起来很好，但是有个问题容易被忽略，那就是yield在不⽀持多线程，多个线程同时向yield发送数据，yield接收谁？yield返回⼀个数据，谁去接收？这样yield就会报错，然后停⽌执⾏。当然可以使⽤特殊⽅法对yield进⾏加锁，保证每次都只有⼀个线程发送数据。
通过测试发现，使⽤yield并不能提⾼评测效率，⽽每次连接数据库也并不慢，毕竟现在服务器性能都很⾼。所以使⽤上⾯的每次连接数据库的⽅法还是⽐较好的。
还有⼀个问题，当多线程同时对数据库进⾏操作的时候，也容易出现⼀些莫名其妙的错误，最好是对数据库操作加锁：
⽣产者如何去实现？
为了隐藏服务器信息，保证服务器安全，所有的SQL语句都⽤五个#代替。
⽣产者就是⼀个while死循环，不断扫描数据库，扫描到之后就向任务队列添加任务。def run_sql (sql): '''执⾏sql 语句，并返回结果''' con = None while True : try : con = t(config.db_host,config.db_user,config.db_password, config.db_name,charset=config.db_charset) break except : ('Cannot connect to database,trying again') time.sleep(1) cur = con.cursor() try : if type(sql) == types.StringType: ute(sql) elif type(sql) == types.ListType: for i in sql: ute(i) except MySQLdb.OperationalError,e: (e) cur.close() con.close() return False conmit() data = cur.fetchall() cur.close() con.close() return data
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28#创建数据库锁，保证⼀个时间只能⼀个程序都写数据库dblock = threading.Lock()# 读写数据库之前加锁dblock.acquire()# 执⾏数据库操作runsql()# 执⾏完毕解锁lease()
1
2
3
4
5
6
7
8
消费者如何实现？
基本是按照上⾯说的来的，先获取任务，然后处理任务，最后标记任务处理完成。
这⾥要注意t.deamon=True，这句的作⽤是当主线程退出的时候，评测线程也⼀块退出，不在后台继续执⾏。
消费者获取任务后需要做什么处理？
因为代码保存在数据库，所以⾸先要将代码从数据库取出来，按⽂件类型命名后保存到相应的评判⽬录下。然后在评判⽬录下对代码进⾏编译，如果编译错误则将错误信息保存到数据库，返回编译错误。编译通过则运⾏程序，检测程序执⾏时间和内存，评判程序执⾏结果。如何编译代码？
根据不同的编程语⾔，选择不同的编译器。我的评测程序⽀持多种编程语⾔。编译实际上就是调⽤外部编译器对代码进⾏编译，我们需要获取编译信息，如果编译错误，需要将错误信息保存到数据库。def put_task_into_queue (): '''循环扫描数据库，将任务添加到队列''' while True : q.join() #阻塞安程序，直到队列⾥⾯的任务全部完成 sql = ">" data = run_sql(sql) for i in data: solution_id,problem_id,user_id,contest_id,pro_lang = i task = { "solution_id":solution_id, "problem_id":problem_id, "contest_id":contest_id, "user_id":user_id, "pro_lang":pro_lang, } q.put(task) time.sleep(0.5) #每次扫⾯完后等待0.5秒，减少CPU 占有率
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17def worker (): '''⼯作线程，循环扫描队列，获得评判任务并执⾏''' while True : #获取任务，如果队列为空则阻塞 task = q.get() #获取题⽬信息 solution_id = task['solution_id'] problem_id = task['problem_id'] language = task['pro_lang'] user_id = task['user_id'] # 评测 result=run(problem_id,solution_id,language,data_count,user_id) #将结果写⼊数据库 dblock.acquire() update_result(result) lease() #标记⼀个任务完成 q.task_done() 如何启动多个评测线程？def start_work_thread (): '''开启⼯作线程''' for i in unt_thread): t = threading.Thread(target=worker) t.deamon = True t.start()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
调⽤外部程序可以使⽤python的subprocess模块，这个模块⾮常强⼤，⽐os.system()什么的⽜逼多了。⾥⾯有个Popen⽅法，执⾏外部程序。设置shell=True我们就能以shell⽅式去执⾏命令。可以使⽤cwd指定⼯作⽬录，获取程序的外部输出可以使⽤管道PIPE，调⽤communicate()⽅法可以可以获取外部程序的输出信息，也就是编译错误信息。
可以根据编译程序的返回值来判断编译是否成功，⼀般来说，返回值为0表⽰编译成功。
有些语⾔，⽐如ruby和perl是解释型语⾔，不提供编译选项，因此在这⾥仅仅加上-c参数做简单的代码检查。
python，lua，java等可以编译成⼆进制⽂件然后解释执⾏。
ACMer们着重看⼀下gcc和g++和pascal的编译参数，以后写程序可以以这个参数进⾏编译，只要在本地编译通过⼀般在服务器上编译就不会出现编译错误问题。
可能有些朋友会有疑问：为什么加这么多语⾔？正式ACM⽐赛只让⽤C,C++和JAVA语⾔啊！对这个问题，我只想说，做为⼀个在线测评系统，不能仅仅局限在ACM上。如果能让初学者⽤这个平台来练习编程语⾔不是也很好？做ACM是有趣的，⽤⼀门新的语⾔去做ACM题⽬也是有趣的，快乐的去学习⼀门语⾔不是学得很快？我承认，有好多语⾔不太适合做ACM，因为ACM对时间和内存要求⽐较严格，好多解释执⾏的语⾔可能占内存⽐较⼤，运⾏速度⽐较慢，只要抱着⼀种学习编程语⾔的⼼态去刷题就好了。此外，对于新兴的go语⾔，我认为是⾮常适合⽤来做ACM的。⽜逼的haskell语⾔也值得⼀学，描述⾼级数据结果也很⽅便。感兴趣的可以试试。
我的评测程序是可以扩展的，如果想再加其他编程语⾔，只要知道编译参数，知道如何执⾏，配置好编译器和运⾏时环境，在评测程序⾥⾯加上就能编译和评测。
⽤户代码在执⾏过程中是如何进⾏评判的（ACMer必看）？
前⾯说了，如果出现编译错误(Compile Error)，是不会执⾏的。每个题⽬都有⼀个标准的时间和内存限制，例如时间1000ms，内存65536K，程序在执⾏的时候会实时检查其花费时间和使⽤内存信息，如果出现超时和超内存将会分别返回Time Limit Exceeded和
Memory Limit Exceeded错误信息，如果程序执⾏时出现错误，⽐如⾮法指针，数组越界等，将会返回Runtime Error信息。如果你的程序没有出现上⾯的信息，说明程序顺利执⾏结束了。接下来，就是
对你的程序的输出也就是运⾏结果进⾏检查，如果你的执⾏结果和我们的标准答案完全⼀样，则返回Accepted，也就说明你这个题⽬做对了。如果除去空格，换⾏，tab外完全相同，则说明你的代码格式错误，将返回Presentation Error，如果你输出的内容有⼀部分和标准答案完全⼀样，但是还输出了⼀些其他内容，则说明你多输出了，这时候将返回Output Limit Exceeded错误信息，出现其他情况，就说明你的输出结果和标准答案不⼀样，就是Wrong Answer了。
总结⼀下错误的出现顺序：
Compile Error -> Memory Limit Exceeded = Time Limit Exceeded = Runtime Error -> Wrong Answer -> Output Limit Exceeded ->Presentation Error -> Accepted def compile (solution_id,language): '''将程序编译成可执⾏⽂件''' build_cmd = { "gcc" : "gcc main.c -o main -Wall -lm -O2 -std=c99 --static -DONLINE_JUDGE", "g++" : "g++ main.cpp -O2 -Wall -lm --static -DONLINE_JUDGE -o main", "java" : "javac Main.java", "ruby" : "ruby -c main.rb", "perl" : "perl -c main.pl", "pascal" : 'fpc main.pas -O2 -Co -Ct -Ci', "go" : '/opt/golang/bin/go build -ldflags "-s -w" ', "lua" : 'luac -o main main.lua', "python2": 'python2 -m py_compile main.py', "python3": 'python3 -m py_compile main.py', "haskell": "ghc -o main main.hs", } p = subprocess.Popen(build_cmd[language],shell=True ,cwd=dir_work,stdout=subprocess.PIPE,stderr=subprocess.PIPE) out,err = pmunicate()#获取
编译错误信息 if p.returncode == 0: #返回值为0，编译成功 return True dblock.acquire() update_compile_info(solution_id,err+out) #编译失败，更新题⽬的编译错误信息 lease() return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
在线制作图片浏览器(代码生成器)
« 上一篇
Matlab在线实验系统关键技术的研究与实现
下一篇 »
发表评论