ACM在线测评体系评测法度设计与python实现
添加时间:2013-5-14 点击量:
写此文目标:
- 让门外汉懂得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://zh.wikipedia.org/wiki/ACM国际大学生法度设计比赛
- ACM国际大学生法度设计比赛指南:http://xinxi.100 xuexi.com/view/trend/20120328/47133.html
什么是ACM测评体系?
为了让同窗们拥有一个操练和比赛的景象,须要一套体系来供给办事。
体系要供给如下功能:
- 用户经管
- 题目经管
- 比赛经管
- 评测法度
典范的ACM评测体系有两种
- 一种是C/S模式,典范代表是PC^2。首要用在省赛,区初赛,国际赛等大型比赛中。官网:http://www.ecs.csus.edu/pc2/
- 另一种是B/S模式,国表里有几十个类似网站,首要用于通俗操练和教授教化等。国内斗劲风行的OJ有:
- 杭州电子科技大学:http://acm.hdu.edu.cn/
- 北京大学:http://poj.org/
- 浙江大学:http://acm.zju.edu.cn/onlinejudge/
- 山东理工大学: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队列:
#初始化队列
q = Queue(config.queue_size)
如何有效得从数据库获取数据?
这里我们以mysql为例进行申明。python稀有据库相干的模块,应用起来很便利。这里我们须要推敲异常处理惩罚。
有可能呈现的题目是数据库重启了或者无意断开了不克不及正常连接,这时辰就须要络续测验测验从头连接直到连接成功。然后断定参数,若是是字符串就申明是sql语句,直接履行,若是是列表则依次履行所有的语句,若是履行时代呈现错误,则封闭连接,返回错误信息。不然返回sql语句履行成果。
下面这个函数专门来处理惩罚数据库相干操纵
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语句传递进去,履行成果经由过程yield反馈回来。如许听起来很好,然则有个题目轻易被忽视,那就是yield在不支撑多线程,多个线程同时向yield发送数据,yield接管谁?yield返回一个数据,谁去接管?如许yield就会报错,然后停止履行。当然可以应用特别办法对yield进行加锁,包管每次都只有一个线程发送数据。
经由过程测试发明,应用yield并不克不及进步评测效力,而每次连接数据库也并不慢,毕竟?成果如今办事器机能都很高。所以应用上方的每次连接数据库的办法还是斗劲好的。
还有一个题目,当多线程同时对数据库进行操纵的时辰,也轻易呈现一些莫名其妙的错误,好是对数据库操纵加锁:
#创建数据库锁,包管一个时候只能一个法度都写数据库
dblock = threading.Lock()
# 读写数据库之前加锁
dblock.acquire()
# 履行数据库操纵
runsql()
# 履行完毕解锁
dblock.release()
临盆者如何去实现?
为了隐蔽办事器信息,包管办事器安然,所有的SQL语句都用五个#庖代。
临盆者就是一个while死轮回,络续扫描数据库,扫描到之后就向任务队列添加任务。
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占领率
花费者如何实现?
根蒂根基是遵守上方说的来的,先获取任务,然后处理惩罚任务,最后标识表记标帜任务处理惩罚完成。
def 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()
_result(result)
dblock.release()
#标识表记标帜一个任务完成
q.task_done()
如何启动多个评测线程?
def start_work_thread():
开启工作线程
for i in range(config.count_thread):
t = threading.Thread(target=worker)
t.deamon = True
t.start()
这里要重视t.deamon=True
,这句的感化是当主线程退出的时辰,评测线程也一块退出,不在后台持续履行。
花费者获取任务后须要做什么处理惩罚?
因为代码保存在数据库,所以起首要将代码从数据库取出来,按文件类型定名后保存到响应的评判目次下。然后在评判目次下对代码进行编译,若是编译错误则将错误信息保存到数据库,返回编译错误。编译经由过程则运行法度,检测法度履行时候和内存,评判法度履行成果。
如何编译代码?
按照不合的编程说话,选择不合的编译器。我的评测法度支撑多种编程说话。编译实际上就是调用外部编译器对代码进行编译,我们须要获取编译信息,若是编译错误,须要将错误信息保存到数据库。
调用外部法度可以应用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
说话也值得一学,描述高等数据成果也很便利。感爱好的可以尝尝。
我的评测法度是可以扩大的,若是想再加其他编程说话,只要知道编译参数,知道如何履行,设备好编译器和运行时景象,在评测法度里面加上就能编译和评测。
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 main.go,
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 = p.communicate()#获取编译错误信息
if p.returncode == 0: #返回值为0,编译成功
return True
dblock.acquire()
_compile_info(solution_id,err+out) #编译失败,更新题目标编译错误信息
dblock.release()
return False
用户代码在履行过程中是如何进行评判的(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
直接说不免有些空洞,做了张流程图:
若是你获得了其他信息,比如System error
,则申明办事器端可能出题目了,我们技巧人员会设法解决。若是看到waiting
,申明守候评测的代码斗劲多,你须要稍作守候,直到代码被评测。若是你获得了Judging
成果,申明你的代码正在评测,若是长时候一向是Judging
,则申明评测法度在评测过程中可能出题目了,没有评判出成果就停止了。技巧人员会为你重判的。
ACMer们能按照上方的评测流程,在看到本身的评判成果的时辰,可以或许解析出你离AC还有多远,以及如何改进你的代码才干AC。
评判答案的那项目组源码:
def judge_result(problem_id,solution_id,data_num):
对输出数据进行评测
currect_result = os.path.join(config.data_dir,str(problem_id),data%s.out%data_num)
user_result = os.path.join(config.work_dir,str(solution_id),out%s.txt%data_num)
try:
curr = file(currect_result).read().replace(\r,).rstrip()#删除\r,删除行末的空格和换行
user = file(user_result).read().replace(\r,).rstrip()
except:
return False
if curr == user: #完全雷同:AC
return Accepted
if curr.split() == user.split(): #除去空格,tab,换行雷同:PE
return Presentation Error
if curr in user: #输出多了
return Output limit
return Wrong Answer #其他WA
重视一下,代码中有个replace(\r,)
办法,它的感化就是将\r
调换成空字符串。为什么要做这个调换呢?因为在windows下,文本的换行是\r\n
,而在Linux下是\n
。因为不克不及断定测试数据起原与windows还是Linux,增长一个\r
,就是增长一个字符,若是不删除的话,两个文本就是不一样的,就会造成wrong answer
成果。或许你曾经碰到过在windows下用记事本打开一个纯文本文件,格局全乱了,所有文本都在一行内,很是影响浏览。你可以经由过程用写字板打开来解决这个题目。据说\r\n
起原于斗劲古老的打印机,每打印完一行,都要先“回车(\r)”
,再“换行”(\n)
。同样一个C说话的printf(\n)
函数,在windows下将生成\r\n
,而在Linux下生成\n
,因为评测法度为你主动处理惩罚了,是以你就不必存眷这些细节的器材了。
评测法度是如何检测你的法度的履行时候和内存的?
这个题目困扰了我好久,也查了很多多少材料。
用户的法度要在办事器上履行,起首不克不及让用户的法度无穷申请内存,不然轻易造成死机现象,须要将法度的内存限制在题目规定的最大内存内。其次要限制用户法度的履行时候,不克不及让用户的法度无穷制运行。
一般解决规划是:在用户的法度履行前,先做好资料限制,限制法度能应用的最大内存和CPU占用,当用户的法度一旦超出限制就主动终止了。还有个斗劲首要的题目是如何获取法度履行时代的最大内存占用率。用户的代码在履行前须要申请内存,履行时代还能动态申请和开释内存,履行完毕开释内存。法度履行时还有可能应用指针等底层操纵,这无疑给检测内存造成更大的艰苦。在windows下,法度履行停止后,可以调用体系函数获取法度履行时代的最大内存,貌似在Linux下没用现成的函数可以调用。
在Linux下,我们可以应用ps
或top
号令来获取或把守在某个时刻应用法度的内存占用率,要获取法度的最大履行内存,就要络续去检测,络续去斗劲,直到法度停止,获取最大值就是用户法度履行时代的最大内存。按照这个假想,我写了一个法度来实现这个设法:
def get_max_mem(pid):
获取过程号为pid的法度的最大内存
glan = psutil.Process(pid)
max = 0
while True:
try:
rss,vms = glan.get_memory_info()
if rss > max:
max = rss
except:
print max rss = %s%max
return max
def run(problem_id,solution_id,language,data_count,user_id):
获取法度履行时候和内存
time_limit = (time_limit+10)/1000.0
mem_limit = mem_limit 1024
max_rss = 0
max_vms = 0
total_time = 0
for i in range(data_count):
依次测试各组测试数据
args = shlex.split(cmd)
p = subprocess.Popen(args,env={PATH:/nonexistent},cwd=work_dir,stdout=output_data,stdin=input_data,stderr=run_err_data)
start = time.time()
pid = p.pid
glan = psutil.Process(pid)
while True:
time_to_now = time.time()-start + total_time
if psutil.pid_exists(pid) is False:
program_info[take_time] = time_to_now1000
program_info[take_memory] = max_rss/1024.0
program_info[result] = result_code[Runtime Error]
return program_info
rss,vms = glan.get_memory_info()
if p.poll() == 0:
end = time.time()
break
if max_rss < rss:
max_rss = rss
print max_rss=%s%max_rss
if max_vms < vms:
max_vms = vms
if time_to_now > time_limit:
program_info[take_time] = time_to_now1000
program_info[take_memory] = max_rss/1024.0
program_info[result] = result_code[Time Limit Exceeded]
glan.terminate()
return program_info
if max_rss > mem_limit:
program_info[take_time] = time_to_now1000
program_info[take_memory] = max_rss/1024.0
program_info[result] =result_code[Memory Limit Exceeded]
glan.terminate()
return program_info
logging.debug(max_rss = %s%max_rss)
# print max_rss=,max_rss
logging.debug(max_vms = %s%max_vms)
# logging.debug(take time = %s%(end - start))
program_info[take_time] = total_time1000
program_info[take_memory] = max_rss/1024.0
program_info[result] = result_code[program_info[result]]
return program_info
上方的法度用到了一些过程把握的一些常识,简单申明一下。
法度的基起原根蒂根基理是:先用多过程库subprocess的Popen函数去创建一个新的过程,获取其过程号(pid),然后用主线程去监测这个过程,主如果监测及时的内存信息。经由过程斗劲函数,获得法度的履行时代的最大内存。什么时辰停止呢?有四种景象:
- 法度运行完正常停止。这个我们可以经由过程 subprocess.Popen里面的poll办法来检测,若是为0,则代表法度正常停止。
- 法度履行时候跨越了规定的最大履行时候,用terminate办法强迫法度终止
- 法度履行内存跨越了规定的最大内存,terminate强迫终止。
- 法度履行时代呈现错误,异常退出了,这时辰我们经由过程搜检这个pid的时辰就会发明不存在。
还有一点是值得重视的:上文提到在编译法度的时辰,调用subprocess.Popen
,是经由过程shell体式格式调用的,然则这里没有应用这种体式格式,为什么呢?这两种体式格式有什么差别?大差别就是返回的过程的pid,以shell体式格式履行,返回的pid并不是子过程的真正pid,而是shell的pid,去搜检这个pid的内存应用率的时辰获得的并不是用户过程的pid!不经由过程shell体式格式去调用外部法度则是直接返回真处死度的pid,而不消去调用shell。官方文档是这么说的:if shell is true, the specified command will be executed through the shell.
若是不消shell体式格式去履行号令的话,传递参数的时辰就不克不及直接将字符串传递畴昔,例如ls -l
这个号令ls
和参数-l
,当shell=False
时,须要将号令和参数变成一个列表[ls,-l]
传递畴昔。当参数斗劲错杂的时辰,将号令分隔成列表就斗劲麻烦,幸好python为我们供给了shlex
模块,里面的split办法就是专门用来做这个的,官方文档是这么说的:Split the string s using shell-like syntax.
,好不要本身去转换,有可能会导致错误而不克不及履行。
上方的检测内存和时候的办法靠谱吗?
不靠谱,相当不靠谱!(当然学学python如何对过程把握也没坏处哈!)为什么呢?有点经验的都知道,C说话的运行效力比python高啊!履行速度比python快!这会造成什么结果?一个简单的hello world
小法度,C说话“刹时”就履行完了,还没等我的python法度开端检测就履行完了,我的评测法度什么都没检测到,然后返回0,再小的法度内存也不成能是0啊!在OJ上显示内存为0相当不科学!
那怎么办?能不克不及让C说话的法度履行速度慢下来?CPU的频率是固定的,我们没法专门是一个法度的占用的CPU频率降落,在windows下倒是有变速齿轮
这款软件可以让软件履行速度变慢
,不知道在Linux
下有没有。还有没有其他办法?聪慧的你也许会想到gdb
调试,我也曾经想用这种办法,用gdb调试可以使法度单步履行,然后法度履行一步,我检测一次,多好,多完美!研究了好一阵子gdb,发明并不是那么简单。起首,我们以前用gdb调试C/C++的时辰,在编译的时辰要加上一个-g
参数,然后履行的时辰可以单步履行,此外,还有设置断点什么的。有几个题目:
- 其他说话如何调试?比如java,申明履行的,直接调试java虚拟机吗?
- 如何经由过程python对gdb进行把握?还有获取履行状况等信息。
这些题目都不是很好解决。
那上方的办法测量的时候准吗?不准!为什么?我们说的法度的履行时候,严格来说是占用CPU的时候。因为CPU采取的是轮转时候片机制,在某个时刻,CPU在忙此外法度。上方的办法用法度履行的停止时候减去开端时候,获得的时候必然比它实际履行的时候要大。若是法度履行速度过快,不到1毫秒,评测法度也不克不及检测出来,直接返回0了。
如何解决时候和内存的测量题目?
后来在v2ex
上发了一个帖子提问,获得高人指导,应用lorun
。lorun
是github上的一个开源项目,项目地址:https://github.com/lodevil/Lo-runner,这是用C说话写的一个python扩大模块,让法度在一个类似沙盒的景象下履行,然后精准的获取法度的履行时候和内存,还能对法度进行限制,限制法度的体系调用。原文是这么说的:We use this python-c library to run program in a sandbox-like environment. With it, we can accurately known the resource using of the program and limit its resource using including system-call interrupt.
。安装应用都很是便利。我首要用它来测量履行时候和内存,后期代码搜检还是用我的法度。
感爱好的同窗可以将这个模块下来,作为本地测试应用,可以预师长教师成一些测试数据,然后测量你的代码的履行时候和内存,比对你的答案是否正确。
不合编程说话时候内存如何限制?
一般来说,假设C/C++说话的标程是时候限制:1000ms,内存限制32768K,那么java的时候和内存限制都是标准限制的2倍,即2000ms,65536K。
因为后来我再OJ增长了很多多少其他说话,我是如许规定的:编译型的说话和速度较快的申明型说话的时候和内存限制和C/C++是一样的,如许的说话包含:C、C++、go、haskell、lua、pascal
,其他速度稍慢的申明履行的说话和JAVA是一样的,包含:java、python2、python3、ruby、perl
。毕竟?成果应用除C,C++,JAVA外的说话的伴侣毕竟?成果是少数,若是限制太严格的话可以按照实际景象对其他编程说话放宽限制。
多组测试数据的题目时候和内存如何测算?
多组测试数据是一组一组依次履行,时候和内存取各组的最大值,一旦某组测试数据时候和内存超出限制,则终止代码履行,返回超时或超内存错误信息。
如何防止恶意代码破损体系?
我们可以应用以下技巧来对用户法度进行限制:
lorun
模块本身就有限制,防止外部调用
- 降落法度的履行权限。在Linux下,目次权限一般为
755
,也就是说,若是换成一个此外用户,只要不是所有者,就没有批改和删除的权限。python里面可以应用os.setuid(int(os.popen(id -u %s%nobody).read()))
来将法度以nobody
用户的身份履行
- 设置沙盒景象,将用户履行景象和外部隔离。Linux下的chroot号令可以实现,python也有相干办法,然则须要提前搭建沙盒景象。用
jailkit
可以快速构建沙盒景象,感爱好的伴侣可以看看
- 应用
ACL接见把握列表
进行具体把握,让nobody
用户只有对某个文件夹的读写权限,其他文件夹禁止接见
- 评判机和办事器分别,找零丁的机械,只负责评判
- 对用户提交的代码预先搜检,发明恶意代码直接返回
Runtime Error
- 禁止评测办事器连接外网,或者经由过程防火墙限制收集接见
如何启动和停止评测法度以及如何记录错误日记?
启动很简单,只要用python履行protect.py
就行了。
若是须要后台履行的话可以应用Linux下的nohup
号令。
为了防止同时开启多个评测法度,须要将以前开启的评测法度封闭。
为了便利启动,我写了如许一个启动脚本:
#!/bin/bash
sudo kill `ps aux | egrep ^nobody .? protect.py | cut -d -f4`
sudo nohup python protect.py &
第一条号令就是杀死多余的评测过程,第二条是启动评测法度。
在法度里面应用了logging模块,是专门用来记录日记的,这么模块很好用,也很强大,可定制性很强,对我们解析法度履行状况有很大帮助。下面是一些示例:
2013-03-07 18:19:04,855 --- 321880 result 1
2013-03-07 18:19:04,857 --- judging 321882
2013-03-07 18:19:04,881 --- judging 321883
2013-03-07 18:19:04,899 --- judging 321884
2013-03-07 18:19:04,924 --- 321867 result 1
2013-03-07 18:19:04,950 --- 321883 result 7
2013-03-07 18:19:04,973 --- 321881 result 1
2013-03-07 18:19:05,007 --- 321884 result 1
2013-03-07 18:19:05,012 --- 321882 result 4
2013-03-07 18:19:05,148 --- judging 321885
2013-03-07 18:19:05,267 --- judging 321886
2013-03-07 18:19:05,297 --- judging 321887
2013-03-07 18:19:05,356 --- judging 321888
2013-03-07 18:19:05,386 --- judging 321889
2013-03-07 18:19:05,485 --- 321885 result 1
python的设备文件如何编写?
最简单有效的体式格式就是建树一个config.py
文件,里面写上设备的内容,就像下面一样:
#!/usr/bin/env python
#coding=utf-8
#开启评测线程数量
count_thread = 4
#评测法度队列容量
queue_size = 4
#数据库地址
db_host = localhost
#数据库用户名
db_user = user
#数据库暗码
db_password = password
#数据库名字
db_name = db_name
应用的时辰只须要将这个文件导入,然后直接config.queue_size
就可以接见设备文件里面的内容,很便利的。
评测法度的评测效力如何?
自从办事器启用新的评测法度之后,已经经验了两次大的比赛和几次大型测验,在几百小我的比赛和测验中,评测根蒂根基没用守候现象,用户提交的代码根蒂根基都能立即评测出来。大体测了一下,单办事器均匀每秒能判6个题目阁下(包含获庖代码,编译,运行,检测,数据库写入成果等流程)。评测法度今朝已经稳定运行了几个月,没有呈现大的题目,应当说技巧斗劲成熟了。
评测法度还能持续改进吗?
当时思维估计是被驴踢了,居然应用多线程来评测!有经验的python法度猿都知道,python有个全局GIL
锁,这个锁会将python的多个线法度列化,在一个时刻只容许一个线程履行,无论你的机械有几许个CPU,只能应用一个!这就明显影响评测速度!若是换成多过程体式格式,一个评测过程占用一个CPU核心,评测速度将会是几倍几十倍的机能提拔!到时辰弄个上千人的比赛估计题目也不大,最起码评测速度能包管。
此外,还可以构建一个分布式的评测办事器集群,大体假想了一下可以如许实现:
起首,可以选一台办事器A专门和数据库交互,包含从数据库中获取评测任务以及评测停止将成果写回数据库。然后选择N台通俗策画机作为评测机,评测机只和数据库A打交道,也就是从办事器A获取任务,在通俗机械上评测,评测完后将成果反馈到办事器A,再由A将成果写入到数据库。办事器A在这里就充当一个任务经管和分派的角色,调和各个评测机去评测。如许可以削减对数据库的操纵,评测机就不消去一遍一遍扫数据库了。评测的速度和安然性可以获得进一步提拔。
其他
- 附在线简历一份:http://ma6174.github.io/#show/me,筹办练习,大牛指导
- 项目地址:https://github.com/ma6174/acmjudger
- 原文链接:http://www.cnblogs.com/ma6174/archive/2013/05/12/3074034.html
- 上方的法度和办法仅供进修和研究用,严禁任何不法用处
- 本人学识有限,如有错误迎接批驳斧正
所有随风而逝的都属于昨天的,所有历经风雨留下来的才是面向未来的。—— 玛格丽特·米切尔 《飘》
写此文目标:
- 让门外汉懂得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://zh.wikipedia.org/wiki/ACM国际大学生法度设计比赛
- ACM国际大学生法度设计比赛指南:http://xinxi.100 xuexi.com/view/trend/20120328/47133.html
什么是ACM测评体系?
为了让同窗们拥有一个操练和比赛的景象,须要一套体系来供给办事。
体系要供给如下功能:
- 用户经管
- 题目经管
- 比赛经管
- 评测法度
典范的ACM评测体系有两种
- 一种是C/S模式,典范代表是PC^2。首要用在省赛,区初赛,国际赛等大型比赛中。官网:http://www.ecs.csus.edu/pc2/
- 另一种是B/S模式,国表里有几十个类似网站,首要用于通俗操练和教授教化等。国内斗劲风行的OJ有:
- 杭州电子科技大学:http://acm.hdu.edu.cn/
- 北京大学:http://poj.org/
- 浙江大学:http://acm.zju.edu.cn/onlinejudge/
- 山东理工大学: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队列:
#初始化队列
q = Queue(config.queue_size)
如何有效得从数据库获取数据?
这里我们以mysql为例进行申明。python稀有据库相干的模块,应用起来很便利。这里我们须要推敲异常处理惩罚。
有可能呈现的题目是数据库重启了或者无意断开了不克不及正常连接,这时辰就须要络续测验测验从头连接直到连接成功。然后断定参数,若是是字符串就申明是sql语句,直接履行,若是是列表则依次履行所有的语句,若是履行时代呈现错误,则封闭连接,返回错误信息。不然返回sql语句履行成果。
下面这个函数专门来处理惩罚数据库相干操纵
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语句传递进去,履行成果经由过程yield反馈回来。如许听起来很好,然则有个题目轻易被忽视,那就是yield在不支撑多线程,多个线程同时向yield发送数据,yield接管谁?yield返回一个数据,谁去接管?如许yield就会报错,然后停止履行。当然可以应用特别办法对yield进行加锁,包管每次都只有一个线程发送数据。
经由过程测试发明,应用yield并不克不及进步评测效力,而每次连接数据库也并不慢,毕竟?成果如今办事器机能都很高。所以应用上方的每次连接数据库的办法还是斗劲好的。
还有一个题目,当多线程同时对数据库进行操纵的时辰,也轻易呈现一些莫名其妙的错误,好是对数据库操纵加锁:
#创建数据库锁,包管一个时候只能一个法度都写数据库
dblock = threading.Lock()
# 读写数据库之前加锁
dblock.acquire()
# 履行数据库操纵
runsql()
# 履行完毕解锁
dblock.release()
临盆者如何去实现?
为了隐蔽办事器信息,包管办事器安然,所有的SQL语句都用五个#庖代。
临盆者就是一个while死轮回,络续扫描数据库,扫描到之后就向任务队列添加任务。
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占领率
花费者如何实现?
根蒂根基是遵守上方说的来的,先获取任务,然后处理惩罚任务,最后标识表记标帜任务处理惩罚完成。
def 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()
_result(result)
dblock.release()
#标识表记标帜一个任务完成
q.task_done()
如何启动多个评测线程?
def start_work_thread():
开启工作线程
for i in range(config.count_thread):
t = threading.Thread(target=worker)
t.deamon = True
t.start()
这里要重视t.deamon=True
,这句的感化是当主线程退出的时辰,评测线程也一块退出,不在后台持续履行。
花费者获取任务后须要做什么处理惩罚?
因为代码保存在数据库,所以起首要将代码从数据库取出来,按文件类型定名后保存到响应的评判目次下。然后在评判目次下对代码进行编译,若是编译错误则将错误信息保存到数据库,返回编译错误。编译经由过程则运行法度,检测法度履行时候和内存,评判法度履行成果。
如何编译代码?
按照不合的编程说话,选择不合的编译器。我的评测法度支撑多种编程说话。编译实际上就是调用外部编译器对代码进行编译,我们须要获取编译信息,若是编译错误,须要将错误信息保存到数据库。
调用外部法度可以应用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
说话也值得一学,描述高等数据成果也很便利。感爱好的可以尝尝。
我的评测法度是可以扩大的,若是想再加其他编程说话,只要知道编译参数,知道如何履行,设备好编译器和运行时景象,在评测法度里面加上就能编译和评测。
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 main.go,
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 = p.communicate()#获取编译错误信息
if p.returncode == 0: #返回值为0,编译成功
return True
dblock.acquire()
_compile_info(solution_id,err+out) #编译失败,更新题目标编译错误信息
dblock.release()
return False
用户代码在履行过程中是如何进行评判的(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
直接说不免有些空洞,做了张流程图:
若是你获得了其他信息,比如System error
,则申明办事器端可能出题目了,我们技巧人员会设法解决。若是看到waiting
,申明守候评测的代码斗劲多,你须要稍作守候,直到代码被评测。若是你获得了Judging
成果,申明你的代码正在评测,若是长时候一向是Judging
,则申明评测法度在评测过程中可能出题目了,没有评判出成果就停止了。技巧人员会为你重判的。
ACMer们能按照上方的评测流程,在看到本身的评判成果的时辰,可以或许解析出你离AC还有多远,以及如何改进你的代码才干AC。
评判答案的那项目组源码:
def judge_result(problem_id,solution_id,data_num):
对输出数据进行评测
currect_result = os.path.join(config.data_dir,str(problem_id),data%s.out%data_num)
user_result = os.path.join(config.work_dir,str(solution_id),out%s.txt%data_num)
try:
curr = file(currect_result).read().replace(\r,).rstrip()#删除\r,删除行末的空格和换行
user = file(user_result).read().replace(\r,).rstrip()
except:
return False
if curr == user: #完全雷同:AC
return Accepted
if curr.split() == user.split(): #除去空格,tab,换行雷同:PE
return Presentation Error
if curr in user: #输出多了
return Output limit
return Wrong Answer #其他WA
重视一下,代码中有个replace(\r,)
办法,它的感化就是将\r
调换成空字符串。为什么要做这个调换呢?因为在windows下,文本的换行是\r\n
,而在Linux下是\n
。因为不克不及断定测试数据起原与windows还是Linux,增长一个\r
,就是增长一个字符,若是不删除的话,两个文本就是不一样的,就会造成wrong answer
成果。或许你曾经碰到过在windows下用记事本打开一个纯文本文件,格局全乱了,所有文本都在一行内,很是影响浏览。你可以经由过程用写字板打开来解决这个题目。据说\r\n
起原于斗劲古老的打印机,每打印完一行,都要先“回车(\r)”
,再“换行”(\n)
。同样一个C说话的printf(\n)
函数,在windows下将生成\r\n
,而在Linux下生成\n
,因为评测法度为你主动处理惩罚了,是以你就不必存眷这些细节的器材了。
评测法度是如何检测你的法度的履行时候和内存的?
这个题目困扰了我好久,也查了很多多少材料。
用户的法度要在办事器上履行,起首不克不及让用户的法度无穷申请内存,不然轻易造成死机现象,须要将法度的内存限制在题目规定的最大内存内。其次要限制用户法度的履行时候,不克不及让用户的法度无穷制运行。
一般解决规划是:在用户的法度履行前,先做好资料限制,限制法度能应用的最大内存和CPU占用,当用户的法度一旦超出限制就主动终止了。还有个斗劲首要的题目是如何获取法度履行时代的最大内存占用率。用户的代码在履行前须要申请内存,履行时代还能动态申请和开释内存,履行完毕开释内存。法度履行时还有可能应用指针等底层操纵,这无疑给检测内存造成更大的艰苦。在windows下,法度履行停止后,可以调用体系函数获取法度履行时代的最大内存,貌似在Linux下没用现成的函数可以调用。
在Linux下,我们可以应用ps
或top
号令来获取或把守在某个时刻应用法度的内存占用率,要获取法度的最大履行内存,就要络续去检测,络续去斗劲,直到法度停止,获取最大值就是用户法度履行时代的最大内存。按照这个假想,我写了一个法度来实现这个设法:
def get_max_mem(pid):
获取过程号为pid的法度的最大内存
glan = psutil.Process(pid)
max = 0
while True:
try:
rss,vms = glan.get_memory_info()
if rss > max:
max = rss
except:
print max rss = %s%max
return max
def run(problem_id,solution_id,language,data_count,user_id):
获取法度履行时候和内存
time_limit = (time_limit+10)/1000.0
mem_limit = mem_limit 1024
max_rss = 0
max_vms = 0
total_time = 0
for i in range(data_count):
依次测试各组测试数据
args = shlex.split(cmd)
p = subprocess.Popen(args,env={PATH:/nonexistent},cwd=work_dir,stdout=output_data,stdin=input_data,stderr=run_err_data)
start = time.time()
pid = p.pid
glan = psutil.Process(pid)
while True:
time_to_now = time.time()-start + total_time
if psutil.pid_exists(pid) is False:
program_info[take_time] = time_to_now1000
program_info[take_memory] = max_rss/1024.0
program_info[result] = result_code[Runtime Error]
return program_info
rss,vms = glan.get_memory_info()
if p.poll() == 0:
end = time.time()
break
if max_rss < rss:
max_rss = rss
print max_rss=%s%max_rss
if max_vms < vms:
max_vms = vms
if time_to_now > time_limit:
program_info[take_time] = time_to_now1000
program_info[take_memory] = max_rss/1024.0
program_info[result] = result_code[Time Limit Exceeded]
glan.terminate()
return program_info
if max_rss > mem_limit:
program_info[take_time] = time_to_now1000
program_info[take_memory] = max_rss/1024.0
program_info[result] =result_code[Memory Limit Exceeded]
glan.terminate()
return program_info
logging.debug(max_rss = %s%max_rss)
# print max_rss=,max_rss
logging.debug(max_vms = %s%max_vms)
# logging.debug(take time = %s%(end - start))
program_info[take_time] = total_time1000
program_info[take_memory] = max_rss/1024.0
program_info[result] = result_code[program_info[result]]
return program_info
上方的法度用到了一些过程把握的一些常识,简单申明一下。
法度的基起原根蒂根基理是:先用多过程库subprocess的Popen函数去创建一个新的过程,获取其过程号(pid),然后用主线程去监测这个过程,主如果监测及时的内存信息。经由过程斗劲函数,获得法度的履行时代的最大内存。什么时辰停止呢?有四种景象:
- 法度运行完正常停止。这个我们可以经由过程 subprocess.Popen里面的poll办法来检测,若是为0,则代表法度正常停止。
- 法度履行时候跨越了规定的最大履行时候,用terminate办法强迫法度终止
- 法度履行内存跨越了规定的最大内存,terminate强迫终止。
- 法度履行时代呈现错误,异常退出了,这时辰我们经由过程搜检这个pid的时辰就会发明不存在。
还有一点是值得重视的:上文提到在编译法度的时辰,调用subprocess.Popen
,是经由过程shell体式格式调用的,然则这里没有应用这种体式格式,为什么呢?这两种体式格式有什么差别?大差别就是返回的过程的pid,以shell体式格式履行,返回的pid并不是子过程的真正pid,而是shell的pid,去搜检这个pid的内存应用率的时辰获得的并不是用户过程的pid!不经由过程shell体式格式去调用外部法度则是直接返回真处死度的pid,而不消去调用shell。官方文档是这么说的:if shell is true, the specified command will be executed through the shell.
若是不消shell体式格式去履行号令的话,传递参数的时辰就不克不及直接将字符串传递畴昔,例如ls -l
这个号令ls
和参数-l
,当shell=False
时,须要将号令和参数变成一个列表[ls,-l]
传递畴昔。当参数斗劲错杂的时辰,将号令分隔成列表就斗劲麻烦,幸好python为我们供给了shlex
模块,里面的split办法就是专门用来做这个的,官方文档是这么说的:Split the string s using shell-like syntax.
,好不要本身去转换,有可能会导致错误而不克不及履行。
上方的检测内存和时候的办法靠谱吗?
不靠谱,相当不靠谱!(当然学学python如何对过程把握也没坏处哈!)为什么呢?有点经验的都知道,C说话的运行效力比python高啊!履行速度比python快!这会造成什么结果?一个简单的hello world
小法度,C说话“刹时”就履行完了,还没等我的python法度开端检测就履行完了,我的评测法度什么都没检测到,然后返回0,再小的法度内存也不成能是0啊!在OJ上显示内存为0相当不科学!
那怎么办?能不克不及让C说话的法度履行速度慢下来?CPU的频率是固定的,我们没法专门是一个法度的占用的CPU频率降落,在windows下倒是有变速齿轮
这款软件可以让软件履行速度变慢
,不知道在Linux
下有没有。还有没有其他办法?聪慧的你也许会想到gdb
调试,我也曾经想用这种办法,用gdb调试可以使法度单步履行,然后法度履行一步,我检测一次,多好,多完美!研究了好一阵子gdb,发明并不是那么简单。起首,我们以前用gdb调试C/C++的时辰,在编译的时辰要加上一个-g
参数,然后履行的时辰可以单步履行,此外,还有设置断点什么的。有几个题目:
- 其他说话如何调试?比如java,申明履行的,直接调试java虚拟机吗?
- 如何经由过程python对gdb进行把握?还有获取履行状况等信息。
这些题目都不是很好解决。
那上方的办法测量的时候准吗?不准!为什么?我们说的法度的履行时候,严格来说是占用CPU的时候。因为CPU采取的是轮转时候片机制,在某个时刻,CPU在忙此外法度。上方的办法用法度履行的停止时候减去开端时候,获得的时候必然比它实际履行的时候要大。若是法度履行速度过快,不到1毫秒,评测法度也不克不及检测出来,直接返回0了。
如何解决时候和内存的测量题目?
后来在v2ex
上发了一个帖子提问,获得高人指导,应用lorun
。lorun
是github上的一个开源项目,项目地址:https://github.com/lodevil/Lo-runner,这是用C说话写的一个python扩大模块,让法度在一个类似沙盒的景象下履行,然后精准的获取法度的履行时候和内存,还能对法度进行限制,限制法度的体系调用。原文是这么说的:We use this python-c library to run program in a sandbox-like environment. With it, we can accurately known the resource using of the program and limit its resource using including system-call interrupt.
。安装应用都很是便利。我首要用它来测量履行时候和内存,后期代码搜检还是用我的法度。
感爱好的同窗可以将这个模块下来,作为本地测试应用,可以预师长教师成一些测试数据,然后测量你的代码的履行时候和内存,比对你的答案是否正确。
不合编程说话时候内存如何限制?
一般来说,假设C/C++说话的标程是时候限制:1000ms,内存限制32768K,那么java的时候和内存限制都是标准限制的2倍,即2000ms,65536K。
因为后来我再OJ增长了很多多少其他说话,我是如许规定的:编译型的说话和速度较快的申明型说话的时候和内存限制和C/C++是一样的,如许的说话包含:C、C++、go、haskell、lua、pascal
,其他速度稍慢的申明履行的说话和JAVA是一样的,包含:java、python2、python3、ruby、perl
。毕竟?成果应用除C,C++,JAVA外的说话的伴侣毕竟?成果是少数,若是限制太严格的话可以按照实际景象对其他编程说话放宽限制。
多组测试数据的题目时候和内存如何测算?
多组测试数据是一组一组依次履行,时候和内存取各组的最大值,一旦某组测试数据时候和内存超出限制,则终止代码履行,返回超时或超内存错误信息。
如何防止恶意代码破损体系?
我们可以应用以下技巧来对用户法度进行限制:
lorun
模块本身就有限制,防止外部调用- 降落法度的履行权限。在Linux下,目次权限一般为
755
,也就是说,若是换成一个此外用户,只要不是所有者,就没有批改和删除的权限。python里面可以应用os.setuid(int(os.popen(id -u %s%nobody).read()))
来将法度以nobody
用户的身份履行 - 设置沙盒景象,将用户履行景象和外部隔离。Linux下的chroot号令可以实现,python也有相干办法,然则须要提前搭建沙盒景象。用
jailkit
可以快速构建沙盒景象,感爱好的伴侣可以看看 - 应用
ACL接见把握列表
进行具体把握,让nobody
用户只有对某个文件夹的读写权限,其他文件夹禁止接见 - 评判机和办事器分别,找零丁的机械,只负责评判
- 对用户提交的代码预先搜检,发明恶意代码直接返回
Runtime Error
- 禁止评测办事器连接外网,或者经由过程防火墙限制收集接见
如何启动和停止评测法度以及如何记录错误日记?
启动很简单,只要用python履行protect.py
就行了。
若是须要后台履行的话可以应用Linux下的nohup
号令。
为了防止同时开启多个评测法度,须要将以前开启的评测法度封闭。
为了便利启动,我写了如许一个启动脚本:
#!/bin/bash
sudo kill `ps aux | egrep ^nobody .? protect.py | cut -d -f4`
sudo nohup python protect.py &
第一条号令就是杀死多余的评测过程,第二条是启动评测法度。
在法度里面应用了logging模块,是专门用来记录日记的,这么模块很好用,也很强大,可定制性很强,对我们解析法度履行状况有很大帮助。下面是一些示例:
2013-03-07 18:19:04,855 --- 321880 result 1
2013-03-07 18:19:04,857 --- judging 321882
2013-03-07 18:19:04,881 --- judging 321883
2013-03-07 18:19:04,899 --- judging 321884
2013-03-07 18:19:04,924 --- 321867 result 1
2013-03-07 18:19:04,950 --- 321883 result 7
2013-03-07 18:19:04,973 --- 321881 result 1
2013-03-07 18:19:05,007 --- 321884 result 1
2013-03-07 18:19:05,012 --- 321882 result 4
2013-03-07 18:19:05,148 --- judging 321885
2013-03-07 18:19:05,267 --- judging 321886
2013-03-07 18:19:05,297 --- judging 321887
2013-03-07 18:19:05,356 --- judging 321888
2013-03-07 18:19:05,386 --- judging 321889
2013-03-07 18:19:05,485 --- 321885 result 1
python的设备文件如何编写?
最简单有效的体式格式就是建树一个config.py
文件,里面写上设备的内容,就像下面一样:
#!/usr/bin/env python
#coding=utf-8
#开启评测线程数量
count_thread = 4
#评测法度队列容量
queue_size = 4
#数据库地址
db_host = localhost
#数据库用户名
db_user = user
#数据库暗码
db_password = password
#数据库名字
db_name = db_name
应用的时辰只须要将这个文件导入,然后直接config.queue_size
就可以接见设备文件里面的内容,很便利的。
评测法度的评测效力如何?
自从办事器启用新的评测法度之后,已经经验了两次大的比赛和几次大型测验,在几百小我的比赛和测验中,评测根蒂根基没用守候现象,用户提交的代码根蒂根基都能立即评测出来。大体测了一下,单办事器均匀每秒能判6个题目阁下(包含获庖代码,编译,运行,检测,数据库写入成果等流程)。评测法度今朝已经稳定运行了几个月,没有呈现大的题目,应当说技巧斗劲成熟了。
评测法度还能持续改进吗?
当时思维估计是被驴踢了,居然应用多线程来评测!有经验的python法度猿都知道,python有个全局GIL
锁,这个锁会将python的多个线法度列化,在一个时刻只容许一个线程履行,无论你的机械有几许个CPU,只能应用一个!这就明显影响评测速度!若是换成多过程体式格式,一个评测过程占用一个CPU核心,评测速度将会是几倍几十倍的机能提拔!到时辰弄个上千人的比赛估计题目也不大,最起码评测速度能包管。
此外,还可以构建一个分布式的评测办事器集群,大体假想了一下可以如许实现:
起首,可以选一台办事器A专门和数据库交互,包含从数据库中获取评测任务以及评测停止将成果写回数据库。然后选择N台通俗策画机作为评测机,评测机只和数据库A打交道,也就是从办事器A获取任务,在通俗机械上评测,评测完后将成果反馈到办事器A,再由A将成果写入到数据库。办事器A在这里就充当一个任务经管和分派的角色,调和各个评测机去评测。如许可以削减对数据库的操纵,评测机就不消去一遍一遍扫数据库了。评测的速度和安然性可以获得进一步提拔。
其他
- 附在线简历一份:http://ma6174.github.io/#show/me,筹办练习,大牛指导
- 项目地址:https://github.com/ma6174/acmjudger
- 原文链接:http://www.cnblogs.com/ma6174/archive/2013/05/12/3074034.html
- 上方的法度和办法仅供进修和研究用,严禁任何不法用处
- 本人学识有限,如有错误迎接批驳斧正