Posted on 2012-08-20 00:35
Onway 閱讀(1999)
評論(1) 編輯 收藏 引用 所屬分類:
碼兒快跑
@import url(http://m.shnenglu.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/
（僅是給出一個鏈接，我的設計和實現都沒參考過這個項目的任何文檔，
事實上我是在修改的過程中發現這個項目，我所做的僅是將它的代碼里面的一些實現技術進行過對比，
這么羅嗦是因為不想碰到這個項目里提到的一個抄襲案例）