Posted on 2012-08-20 00:35
Onway 阅读(1948)
评论(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/
（仅是给出一个链接，我的设计和实现都没参考过这个项目的任何文档，
事实上我是在修改的过程中发现这个项目，我所做的仅是将它的代码里面的一些实现技术进行过对比，
这么罗嗦是因为不想碰到这个项目里提到的一个抄袭案例）