Posted on 2012-08-20 00:35
Onway 阅读(1956)
评论(1) 编辑 收藏 引用 所属分类:
码儿快跑
@import url(http://www.cppblog.com/CuteSoft_Client/CuteEditor/Load.ashx?type=style&file=SyntaxHighlighter.css);@import url(/css/cuteeditor.css);
一:又是OJ?
网上的OJ平台已经很多了,GPL开源的HUSTOJ都有了,我再做这么个东西,又没啥创新,其实都挺让人费解的。
你甚至都可以鄙视我重复造轮子,反正原因我是不解释了,毕竟这个原因只是对我个人有意义。
二:实现技术
网上搜索一下可以发现不少这方面的论文和相关技术。这里简单说一下我的吧:
(基于linux系统,使用ptrace拦截系统调用和信号,使用wait3获取资源使用)。
1.1 时间限制和获取,这个实现起来应该比较简单
a,监测进程设置超时闹钟,可以防止用户程序的挂起和阻塞;
b,对用户进程进行CPU时间限制,可以尽快的发现用户程序超时,而且闹钟的计时毕竟是挂钟时间。
(CPU限制时间应该比检测进程的闹钟时间要短)
c,之所以说是尽快,是因为CPU时间限制只能到达秒级。
解决方法是CPU时间限制相对宽松,在用户进程结束后,判断其CPU时间使用。
(注意:fork到execve期间的花费算入了子进程的时间使用(struct rusage),需要减去这个花费;
setrlimit到execve期间的花费应该保证不会大于CPU时间限制的宽松值。
最好就是使CPU时间宽松值大于fork到execve的时间花费。
1.2 存在的问题
a,在超出实际限时(如1500ms)而未到达CPU时间限制(2s)期间发生的错误会比超时优先返回。
于是你可能发现你第一次RE的程序改好了,再交上去就超时了。
2.1 内存的限制和获取,这个比较纠结
a,限制方面,是限制虚拟内存,包括共享内存,
在execve之后,以及有关虚拟内存的系统调用成功以后,都读取一次/proc/<pid>/statm的虚拟内存值。
不是限制实际内存使用的原因是考虑:
无法监测rusage结构的缺页次数(ru_minflt字段)的每次改变,即使是轮询/proc/<pid>/statm,轮询间隔也是个问题。
b,内存使用统计方面则是获取实际内存使用(struct rsuage的ru_minflt字段),
这样考虑最主要的原因是,如果统计出来的是虚拟内存使用,其数值很难让人接受。
另外对系统的内存管理真的不了解。跟其他OJ的实现可能有比较大的出入。
2.2 存在的问题
a,对比了POJ和HDOJ对gcc跑的A+B问题,它们最小的内存使用是192KB,
我在ubuntu 11.10平台使用gcc 4.6.1的静态编译,得到最小的内存使用是200kb有多。当然这问题不大。
b,像java,python,php这样的解释型语言,是否应该包括解释器的内存使用呢?
我测试了一下java语言的A+B程序,最小也得11000KB有多,而网上的平台看到最小可以几百KB,这真不知道怎么做的。
3.1 输出限制
使用setrlimit的RLIMIT_FSIZE限制一个临时文件的输出。
当初以为使用管道能够实现,后来从网上的一篇文章看到,输出超过管道容量之后,父子进程都会阻塞,
后测试一下果然这样,而且setrlimit似乎不能对管道起作用,无论管道是否是命名的。
4.1 答案对比
将临时输出文件和答案文件进行内存映射(mmap),进行两次扫描对比,
第一次对比是判断AC的,第二次是跳过空白字符对比,判断PE的。
4.2 输出的specail judge
这个也不难,将临时输出文件重定向到special judge程序的输入,将special judge的输出重定向到检测程序创建的管道。
需要注意的是,special judge程序的出错,如无输出或者输出大于管道容量,这都可以通过闹钟超时解决。
5.1 多组测试
我的做法是,多次运行用户程序,其中一组出错即马上返回。所有组都通过则返回资源使用最大的统计数值。
6.1 与runtime error相关
a,通过ptrace获取系统调用号,不被允许的系统调用,则返回RE;
b,ptrace同样拦截了用户程序收到的信号,但不会递送给用户进程,而是通过判断其信号决定是否要RE。
6.2 存在的问题
a,/usr/include/syscall.h头文件中包含的346个系统调用和/usr/include/signal.h中的30多个信号,
都还没进行详细的规则限制。
b,网上看到的系统调用号怎么就只有270多个呢?当然我的linux内核是3.0.0的。
7.1 安全问题
像网上和论文里看来的一样,都是使用ptrace拦截系统调用,降低用户进程的运行权限。
但最后还是决定不使用chroot限制根目录,因为我不会处理动态库依赖,头文件限制等等问题。详见后面的“问题”部分。
三:源码编译安装和运行/Files/Onway/anoj.tar.gz.rar(.tar.gz压缩包,去掉.rar后缀)
1,ojdlck脚本程序:
输入数据文件和答案文件(或者答案程序)必须放在同一个目录里,如名为testdir,
输入数据文件的后缀必须是.in,答案文件的后缀必须是.out,答案程序的文件必须是.exe且具有执行权限。
然后执行:ojdlck testdir
该脚本程序会在testdir目录里生成一个data.conf的文件,其后的检测程序会读取该文件。
详见源码里带上的doc/HowTo_ojdlck.txt说明文档。
2,监测程序的编译安装:
make
sudo make install
这个不解释了吧,看makefile文件吧。
3,运行监测程序:
./a.out -t time -m memory -f fsize --basedir a_temp_working_directory --datadir input_answer_files_directory \
--who user_and_group_ID --magic a_random_string --end java Main
解释:
-t,时间限制,单位ms
-m,内存限制,单位kb
-f,输出限制,单位kb
--basedir,工作目录
--datadir,存放输入和答案文件的目录,必须包含了ojdlck生成的data.conf文件
--who,运行用户程序的用户ID和组ID,建议为系统的nobody用户
--magic,用于在工作目录产生输出的文件名
--end,标志所有的参数输入完毕,接下来的参数都会视为用户程序及其参数
例如:
./a.out -t 1000 -m 65536 -f 4096 --basedir /tmp --datadir /tmp/testdir --who 65534 --magic abc123 --end java Main
参数确实长,但因为监测程序本来设计就不是用于手工运行的,另外也不希望它每次都读取不变的配置文件,只能是罗嗦一点了。
四:希望得到大家帮助的目前遇到的一些问题
(因为这些问题,实在没信心也没心思去做其他部分,测试和文档也没做,只能将代码拿出来,听听大家意见。)
1,时间和内存方面有没有更好的策略?目前的做法还有什么可以改进的?
2,拦截系统调用和信号,对java这些解析语言是否能起作用?
3,POJ,HDOJ对java代码的内存统计怎么能做到这么小?
先跑一个空程序得到它的内存使用,以后再减去这个值?这好像有点那个了。。。
4,有没必要向用户程序递送信号?
5,代码编译的时候,如何限制头文件,标准库,java可以使用的包?
6,如果使用chroot限制根目录,则动态库依赖怎么解决?
7,其他问题和建议?
五:版权
暂无。
看了一下GPL版权的用法,各源文件加声明,再拷贝一份版权说明,还是懒得做了。
反正没啥技术含量的,也没完成。希望别说我抄袭了别人的就行了。
六:参考文献和链接
1,《针对ACM/ICPC的在线评测系统》作者:肖颖,刘禹
2,《基于Linux的ACM在线评测系统研究》作者:杨志伟,曾艳珊
3,《基于分布式系统的程序监控技术研究及其应用》作者:张正
4,http://code.google.com/p/hustoj/
(仅是给出一个链接,我的设计和实现都没参考过这个项目的任何文档,
事实上我是在修改的过程中发现这个项目,我所做的仅是将它的代码里面的一些实现技术进行过对比,
这么罗嗦是因为不想碰到这个项目里提到的一个抄袭案例)