Posted on 2012-08-20 00:35
Onway 閱讀(1981)
評(píng)論(1) 編輯 收藏 引用 所屬分類:
碼兒快跑
@import url(http://www.shnenglu.com/CuteSoft_Client/CuteEditor/Load.ashx?type=style&file=SyntaxHighlighter.css);@import url(/css/cuteeditor.css);
一：又是OJ?
網(wǎng)上的OJ平臺(tái)已經(jīng)很多了，GPL開源的HUSTOJ都有了，我再做這么個(gè)東西，又沒啥創(chuàng)新，其實(shí)都挺讓人費(fèi)解的。
你甚至都可以鄙視我重復(fù)造輪子，反正原因我是不解釋了，畢竟這個(gè)原因只是對(duì)我個(gè)人有意義。
二：實(shí)現(xiàn)技術(shù)
網(wǎng)上搜索一下可以發(fā)現(xiàn)不少這方面的論文和相關(guān)技術(shù)。這里簡(jiǎn)單說一下我的吧：
（基于linux系統(tǒng)，使用ptrace攔截系統(tǒng)調(diào)用和信號(hào)，使用wait3獲取資源使用）。
1.1 時(shí)間限制和獲取，這個(gè)實(shí)現(xiàn)起來應(yīng)該比較簡(jiǎn)單
a，監(jiān)測(cè)進(jìn)程設(shè)置超時(shí)鬧鐘，可以防止用戶程序的掛起和阻塞；
b，對(duì)用戶進(jìn)程進(jìn)行CPU時(shí)間限制，可以盡快的發(fā)現(xiàn)用戶程序超時(shí)，而且鬧鐘的計(jì)時(shí)畢竟是掛鐘時(shí)間。
（CPU限制時(shí)間應(yīng)該比檢測(cè)進(jìn)程的鬧鐘時(shí)間要短）
c，之所以說是盡快，是因?yàn)镃PU時(shí)間限制只能到達(dá)秒級(jí)。
解決方法是CPU時(shí)間限制相對(duì)寬松，在用戶進(jìn)程結(jié)束后，判斷其CPU時(shí)間使用。
（注意：fork到execve期間的花費(fèi)算入了子進(jìn)程的時(shí)間使用(struct rusage)，需要減去這個(gè)花費(fèi)；
setrlimit到execve期間的花費(fèi)應(yīng)該保證不會(huì)大于CPU時(shí)間限制的寬松值。
最好就是使CPU時(shí)間寬松值大于fork到execve的時(shí)間花費(fèi)。
1.2 存在的問題
a，在超出實(shí)際限時(shí)（如1500ms）而未到達(dá)CPU時(shí)間限制（2s）期間發(fā)生的錯(cuò)誤會(huì)比超時(shí)優(yōu)先返回。
于是你可能發(fā)現(xiàn)你第一次RE的程序改好了，再交上去就超時(shí)了。
2.1 內(nèi)存的限制和獲取，這個(gè)比較糾結(jié)
a，限制方面，是限制虛擬內(nèi)存，包括共享內(nèi)存，
在execve之后，以及有關(guān)虛擬內(nèi)存的系統(tǒng)調(diào)用成功以后，都讀取一次/proc/<pid>/statm的虛擬內(nèi)存值。
不是限制實(shí)際內(nèi)存使用的原因是考慮：
無法監(jiān)測(cè)rusage結(jié)構(gòu)的缺頁次數(shù)(ru_minflt字段)的每次改變，即使是輪詢/proc/<pid>/statm，輪詢間隔也是個(gè)問題。
b，內(nèi)存使用統(tǒng)計(jì)方面則是獲取實(shí)際內(nèi)存使用（struct rsuage的ru_minflt字段），
這樣考慮最主要的原因是，如果統(tǒng)計(jì)出來的是虛擬內(nèi)存使用，其數(shù)值很難讓人接受。
另外對(duì)系統(tǒng)的內(nèi)存管理真的不了解。跟其他OJ的實(shí)現(xiàn)可能有比較大的出入。
2.2 存在的問題
a，對(duì)比了POJ和HDOJ對(duì)gcc跑的A+B問題，它們最小的內(nèi)存使用是192KB，
我在ubuntu 11.10平臺(tái)使用gcc 4.6.1的靜態(tài)編譯，得到最小的內(nèi)存使用是200kb有多。當(dāng)然這問題不大。
b，像java，python，php這樣的解釋型語言，是否應(yīng)該包括解釋器的內(nèi)存使用呢？
我測(cè)試了一下java語言的A+B程序，最小也得11000KB有多，而網(wǎng)上的平臺(tái)看到最小可以幾百KB，這真不知道怎么做的。
3.1 輸出限制
使用setrlimit的RLIMIT_FSIZE限制一個(gè)臨時(shí)文件的輸出。
當(dāng)初以為使用管道能夠?qū)崿F(xiàn)，后來從網(wǎng)上的一篇文章看到，輸出超過管道容量之后，父子進(jìn)程都會(huì)阻塞，
后測(cè)試一下果然這樣，而且setrlimit似乎不能對(duì)管道起作用，無論管道是否是命名的。
4.1 答案對(duì)比
將臨時(shí)輸出文件和答案文件進(jìn)行內(nèi)存映射(mmap)，進(jìn)行兩次掃描對(duì)比，
第一次對(duì)比是判斷AC的，第二次是跳過空白字符對(duì)比，判斷PE的。
4.2 輸出的specail judge
這個(gè)也不難，將臨時(shí)輸出文件重定向到special judge程序的輸入，將special judge的輸出重定向到檢測(cè)程序創(chuàng)建的管道。
需要注意的是，special judge程序的出錯(cuò)，如無輸出或者輸出大于管道容量，這都可以通過鬧鐘超時(shí)解決。
5.1 多組測(cè)試
我的做法是，多次運(yùn)行用戶程序，其中一組出錯(cuò)即馬上返回。所有組都通過則返回資源使用最大的統(tǒng)計(jì)數(shù)值。
6.1 與runtime error相關(guān)
a，通過ptrace獲取系統(tǒng)調(diào)用號(hào)，不被允許的系統(tǒng)調(diào)用，則返回RE；
b，ptrace同樣攔截了用戶程序收到的信號(hào)，但不會(huì)遞送給用戶進(jìn)程，而是通過判斷其信號(hào)決定是否要RE。
6.2 存在的問題
a，/usr/include/syscall.h頭文件中包含的346個(gè)系統(tǒng)調(diào)用和/usr/include/signal.h中的30多個(gè)信號(hào)，
都還沒進(jìn)行詳細(xì)的規(guī)則限制。
b，網(wǎng)上看到的系統(tǒng)調(diào)用號(hào)怎么就只有270多個(gè)呢？當(dāng)然我的linux內(nèi)核是3.0.0的。
7.1 安全問題
像網(wǎng)上和論文里看來的一樣，都是使用ptrace攔截系統(tǒng)調(diào)用，降低用戶進(jìn)程的運(yùn)行權(quán)限。
但最后還是決定不使用chroot限制根目錄，因?yàn)槲也粫?huì)處理動(dòng)態(tài)庫依賴，頭文件限制等等問題。詳見后面的“問題”部分。
三：源碼編譯安裝和運(yùn)行/Files/Onway/anoj.tar.gz.rar（.tar.gz壓縮包，去掉.rar后綴）
1，ojdlck腳本程序：
輸入數(shù)據(jù)文件和答案文件（或者答案程序）必須放在同一個(gè)目錄里，如名為testdir，
輸入數(shù)據(jù)文件的后綴必須是.in，答案文件的后綴必須是.out，答案程序的文件必須是.exe且具有執(zhí)行權(quán)限。
然后執(zhí)行：ojdlck testdir
該腳本程序會(huì)在testdir目錄里生成一個(gè)data.conf的文件，其后的檢測(cè)程序會(huì)讀取該文件。
詳見源碼里帶上的doc/HowTo_ojdlck.txt說明文檔。
2，監(jiān)測(cè)程序的編譯安裝：
make
sudo make install
這個(gè)不解釋了吧，看makefile文件吧。
3，運(yùn)行監(jiān)測(cè)程序：
./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，時(shí)間限制，單位ms
-m，內(nèi)存限制，單位kb
-f，輸出限制，單位kb
--basedir，工作目錄
--datadir，存放輸入和答案文件的目錄，必須包含了ojdlck生成的data.conf文件
--who，運(yùn)行用戶程序的用戶ID和組ID，建議為系統(tǒng)的nobody用戶
--magic，用于在工作目錄產(chǎn)生輸出的文件名
--end，標(biāo)志所有的參數(shù)輸入完畢，接下來的參數(shù)都會(huì)視為用戶程序及其參數(shù)
例如：
./a.out -t 1000 -m 65536 -f 4096 --basedir /tmp --datadir /tmp/testdir --who 65534 --magic abc123 --end java Main
參數(shù)確實(shí)長(zhǎng)，但因?yàn)楸O(jiān)測(cè)程序本來設(shè)計(jì)就不是用于手工運(yùn)行的，另外也不希望它每次都讀取不變的配置文件，只能是羅嗦一點(diǎn)了。
四：希望得到大家?guī)椭哪壳坝龅降囊恍﹩栴}
（因?yàn)檫@些問題，實(shí)在沒信心也沒心思去做其他部分，測(cè)試和文檔也沒做，只能將代碼拿出來，聽聽大家意見。）
1，時(shí)間和內(nèi)存方面有沒有更好的策略？目前的做法還有什么可以改進(jìn)的？
2，攔截系統(tǒng)調(diào)用和信號(hào)，對(duì)java這些解析語言是否能起作用？
3，POJ,HDOJ對(duì)java代碼的內(nèi)存統(tǒng)計(jì)怎么能做到這么小？
先跑一個(gè)空程序得到它的內(nèi)存使用，以后再減去這個(gè)值？這好像有點(diǎn)那個(gè)了。。。
4，有沒必要向用戶程序遞送信號(hào)？
5，代碼編譯的時(shí)候，如何限制頭文件，標(biāo)準(zhǔn)庫，java可以使用的包？
6，如果使用chroot限制根目錄，則動(dòng)態(tài)庫依賴怎么解決？
7，其他問題和建議？
五：版權(quán)
暫無。
看了一下GPL版權(quán)的用法，各源文件加聲明，再拷貝一份版權(quán)說明，還是懶得做了。
反正沒啥技術(shù)含量的，也沒完成。希望別說我抄襲了別人的就行了。
六：參考文獻(xiàn)和鏈接
1，《針對(duì)ACM/ICPC的在線評(píng)測(cè)系統(tǒng)》作者：肖穎，劉禹
2，《基于Linux的ACM在線評(píng)測(cè)系統(tǒng)研究》作者：楊志偉，曾艷珊
3，《基于分布式系統(tǒng)的程序監(jiān)控技術(shù)研究及其應(yīng)用》作者：張正
4，http://code.google.com/p/hustoj/
（僅是給出一個(gè)鏈接，我的設(shè)計(jì)和實(shí)現(xiàn)都沒參考過這個(gè)項(xiàng)目的任何文檔，
事實(shí)上我是在修改的過程中發(fā)現(xiàn)這個(gè)項(xiàng)目，我所做的僅是將它的代碼里面的一些實(shí)現(xiàn)技術(shù)進(jìn)行過對(duì)比，
這么羅嗦是因?yàn)椴幌肱龅竭@個(gè)項(xiàng)目里提到的一個(gè)抄襲案例）