寫此文目的：

• 讓外行人了解ACM，重視ACM。
• 讓ACMer了解評測程序評測原理以便更好得做題。
• 讓pythoner了解如何使用更好的使用python。

在講解之前，先給外行人補充一些關(guān)于ACM的知識。

什么是ACM？

我們平常指的ACM是ACM/ICPC（國際大學生程序設(shè)計競賽），這是由ACM（Association for Computing Machinery，美國計算機協(xié)會）組織的年度性競賽，始于1970年，是全球大學生計算機程序能力競賽活動中最有影響的一項賽事。被譽為計算機界奧林匹克。

了解更多關(guān)于ACM的信息可以參考：

• 百度百科：http://baike.baidu.com/view/201684.htm?
• 維基百科：http://zh.wikipedia.org/wiki/ACM國際大學生程序設(shè)計競賽
• ACM國際大學生程序設(shè)計競賽指南:http://xinxi.100xuexi.com/view/trend/20120328/47133.html

什么是ACM測評系統(tǒng)？

為了讓同學們擁有一個練習和比賽的環(huán)境，需要一套系統(tǒng)來提供服務(wù)。

系統(tǒng)要提供如下功能：

• 用戶管理
• 題目管理
• 比賽管理
• 評測程序

典型的ACM評測系統(tǒng)有兩種

• 一種是C/S模式，典型代表是PC^2。主要用在省賽，區(qū)預(yù)賽，國際賽等大型比賽中。官網(wǎng)：http://www.ecs.csus.edu/pc2/
• 另一種是B/S模式，國內(nèi)外有幾十個類似網(wǎng)站，主要用于平常練習和教學等。國內(nèi)比較流行的OJ有：
  • 杭州電子科技大學：http://acm.hdu.edu.cn/
  • 北京大學：http://poj.org/
  • 浙江大學：http://acm.zju.edu.cn/onlinejudge/
  • 山東理工大學：http://acm.sdut.edu.cn/sdutoj/index.php

評測程序是做什么的？

評測程序就是對用戶提交的代碼進行編譯，然后執(zhí)行，將執(zhí)行結(jié)果和OJ后臺正確的測試數(shù)據(jù)進行比較，如果答案和后臺數(shù)據(jù)完全相同就是AC(Accept)，也就是你的程序是正確的。否則返回錯誤信息，稍后會詳細講解。

ACM在線測評系統(tǒng)整體架構(gòu)

為了做到低耦合，我們以數(shù)據(jù)庫為中心，前臺頁面從數(shù)據(jù)庫獲取題目、比賽列表在瀏覽器上顯示，用戶通過瀏覽器提交的代碼直接保存到數(shù)據(jù)庫。

評測程序負責從數(shù)據(jù)庫中取出用戶剛剛提交的代碼，保存到文件，然后編譯，執(zhí)行，評判，最后將評判結(jié)果寫回數(shù)據(jù)庫。

評測程序架構(gòu)

評測程序要不斷掃描數(shù)據(jù)庫，一旦出現(xiàn)沒有評判的題目要立即進行評判。為了減少頻繁讀寫數(shù)據(jù)庫造成的內(nèi)存和CPU以及硬盤開銷，可以每隔0.5秒掃描一次。為了提高評測速度，可以開啟幾個進程或線程共同評測。由于多線程/進程會競爭資源，對于掃描出來的一個題目，如果多個評測進程同時去評測，可能會造成死鎖，為了防止這種現(xiàn)象，可以使用了生產(chǎn)者-消費者模式，也就是建立一個待評測題目的任務(wù)隊列，這個隊列的生產(chǎn)者作用就是掃描數(shù)據(jù)庫，將數(shù)據(jù)庫中沒有評測的題目列表增加到任務(wù)隊列里面。消費者作用就是從隊列中取出要評測的數(shù)據(jù)進行評測。

為什么任務(wù)隊列能防止出現(xiàn)資源競爭和死鎖現(xiàn)象？

python里面有個模塊叫Queue，我們可以使用這個模塊建立三種類型的隊列：

• FIFO：先進先出隊列
• LIFO：后進先出隊列
• 優(yōu)先隊列

這里我們用到的是先進先出隊列，也就是先被添加到隊列的代碼先被評測，保持比賽的公平性。

隊列可以設(shè)置大小，默認是無限大。

生產(chǎn)者發(fā)現(xiàn)數(shù)據(jù)庫中存在沒有評測的題目之后，使用put()方法將任務(wù)添加到隊列中。這時候如果隊列設(shè)置大小并且已經(jīng)滿了的話，就不能再往里面放了，這時候生產(chǎn)者就進入了等待狀態(tài)，直到可以繼續(xù)往里面放任務(wù)為止。在等待狀態(tài)的之后生產(chǎn)者線程已經(jīng)被阻塞了，也就是說不再去掃描數(shù)據(jù)庫，因此適當設(shè)置隊列的大小可以減少對數(shù)據(jù)庫的讀寫次數(shù)。

消費者需要從任務(wù)隊列獲取任務(wù)，使用get()方法，一旦某個線程從隊列g(shù)et得到某個任務(wù)之后，其他線程就不能再次得到這個任務(wù)，這樣可以防止多個評測線程同時評測同一個程序而造成死鎖。如果任務(wù)隊列為空的話，get()方法不能獲得任務(wù)，這時候評線程序就會阻塞，等待任務(wù)的到來。在被阻塞的時候評測程序可以被看做停止運行了，可以明顯減少系統(tǒng)資源消耗。

隊列還有兩個方法：

一個是task_done()，這個方法是用來標記隊列中的某個任務(wù)已經(jīng)處理完畢。

另一個是join()方法，join方法會阻塞程序直到所有的項目被刪除和處理為止，也就是調(diào)用task_done()方法。

這兩個方法有什么作用呢？因為評測也需要時間，一個任務(wù)從隊列中取出來了，并不意味著這個任務(wù)被處理完了。如果沒有處理完，代碼的狀態(tài)還是未評判，那么生產(chǎn)者會再次將這個代碼從數(shù)據(jù)庫取出加到任務(wù)隊列里面，這將造成代碼重復(fù)評測，浪費系統(tǒng)資源，影響評測速度。這時候我們需要合理用這兩個方法，保證每個代碼都被評測并且寫回數(shù)據(jù)庫之后才開始下一輪的掃描。后面有代碼示例。

我們使用如下代碼創(chuàng)建一個FIFO隊列：

#初始化隊列 q = Queue(config.queue_size)

如何有效得從數(shù)據(jù)庫獲取數(shù)據(jù)？

這里我們以mysql為例進行說明。python有數(shù)據(jù)庫相關(guān)的模塊，使用起來很方便。這里我們需要考慮異常處理。

有可能出現(xiàn)的問題是數(shù)據(jù)庫重啟了或者偶爾斷開了不能正常連接，這時候就需要不斷嘗試重新連接直到連接成功。然后判斷參數(shù)，如果是字符串就說明是sql語句，直接執(zhí)行，如果是列表則依次執(zhí)行所有的語句，如果執(zhí)行期間出現(xiàn)錯誤，則關(guān)閉連接，返回錯誤信息。否則返回sql語句執(zhí)行結(jié)果。

下面這個函數(shù)專門來處理數(shù)據(jù)庫相關(guān)操作

def run_sql(sql):'''執(zhí)行sql語句,并返回結(jié)果'''con = Nonewhile True:try:con = MySQLdb.connect(config.db_host,config.db_user,config.db_password,config.db_name,charset=config.db_charset)breakexcept: 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 Falsecon.commit()data = cur.fetchall()cur.close()con.close()return data

需要注意的是這里我們每次執(zhí)行sql語句都要重新連接數(shù)據(jù)庫，能否一次連接，多次操作數(shù)據(jù)庫？答案是肯定的。但是，這里我們需要考慮的問題是如何將數(shù)據(jù)庫的連接共享？可以設(shè)置一個全局變量。但是如果數(shù)據(jù)庫的連接突然斷開了，在多線程程序里面，問題就比較麻煩了，你需要在每個程序里面去判斷是否連接成功，失敗的話還要重新連接，多線程情況下如何控制重新連接？這些問題如果在每個sql語句執(zhí)行的時候都去檢查的話太麻煩了。

有一種方法可以實現(xiàn)一次連接，多次操作數(shù)據(jù)庫，還能方便的進行數(shù)據(jù)庫重連，那就是使用yield生成器，連接成功之后，通過yield將sql語句傳遞進去，執(zhí)行結(jié)果通過yield反饋回來。這樣聽起來很好，但是有個問題容易被忽略，那就是yield在不支持多線程，多個線程同時向yield發(fā)送數(shù)據(jù)，yield接收誰？yield返回一個數(shù)據(jù)，誰去接收？這樣yield就會報錯，然后停止執(zhí)行。當然可以使用特殊方法對yield進行加鎖，保證每次都只有一個線程發(fā)送數(shù)據(jù)。

通過測試發(fā)現(xiàn)，使用yield并不能提高評測效率，而每次連接數(shù)據(jù)庫也并不慢，畢竟現(xiàn)在服務(wù)器性能都很高。所以使用上面的每次連接數(shù)據(jù)庫的方法還是比較好的。

還有一個問題，當多線程同時對數(shù)據(jù)庫進行操作的時候，也容易出現(xiàn)一些莫名其妙的錯誤，最好是對數(shù)據(jù)庫操作加鎖：

#創(chuàng)建數(shù)據(jù)庫鎖，保證一個時間只能一個程序都寫數(shù)據(jù)庫 dblock = threading.Lock() # 讀寫數(shù)據(jù)庫之前加鎖 dblock.acquire() # 執(zhí)行數(shù)據(jù)庫操作 runsql() # 執(zhí)行完畢解鎖 dblock.release()

生產(chǎn)者如何去實現(xiàn)？

為了隱藏服務(wù)器信息，保證服務(wù)器安全，所有的SQL語句都用五個#代替。

生產(chǎn)者就是一個while死循環(huán)，不斷掃描數(shù)據(jù)庫，掃描到之后就向任務(wù)隊列添加任務(wù)。

def put_task_into_queue():'''循環(huán)掃描數(shù)據(jù)庫,將任務(wù)添加到隊列'''while True:q.join() #阻塞安程序,直到隊列里面的任務(wù)全部完成sql = "#####"data = run_sql(sql)for i in data:solution_id,problem_id,user_id,contest_id,pro_lang = itask = {"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占有率

消費者如何實現(xiàn)？

基本是按照上面說的來的，先獲取任務(wù)，然后處理任務(wù)，最后標記任務(wù)處理完成。

def worker():'''工作線程，循環(huán)掃描隊列，獲得評判任務(wù)并執(zhí)行'''while True:#獲取任務(wù)，如果隊列為空則阻塞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)#將結(jié)果寫入數(shù)據(jù)庫dblock.acquire()update_result(result) dblock.release()#標記一個任務(wù)完成q.task_done()

如何啟動多個評測線程？

def start_work_thread():'''開啟工作線程'''for i in range(config.count_thread):t = threading.Thread(target=worker)t.deamon = Truet.start()

這里要注意t.deamon=True，這句的作用是當主線程退出的時候，評測線程也一塊退出，不在后臺繼續(xù)執(zhí)行。

消費者獲取任務(wù)后需要做什么處理？

因為代碼保存在數(shù)據(jù)庫，所以首先要將代碼從數(shù)據(jù)庫取出來，按文件類型命名后保存到相應(yīng)的評判目錄下。然后在評判目錄下對代碼進行編譯，如果編譯錯誤則將錯誤信息保存到數(shù)據(jù)庫，返回編譯錯誤。編譯通過則運行程序，檢測程序執(zhí)行時間和內(nèi)存，評判程序執(zhí)行結(jié)果。

如何編譯代碼？

根據(jù)不同的編程語言，選擇不同的編譯器。我的評測程序支持多種編程語言。編譯實際上就是調(diào)用外部編譯器對代碼進行編譯，我們需要獲取編譯信息，如果編譯錯誤，需要將錯誤信息保存到數(shù)據(jù)庫。

調(diào)用外部程序可以使用python的subprocess模塊，這個模塊非常強大，比os.system()什么的牛逼多了。里面有個Popen方法，執(zhí)行外部程序。設(shè)置shell=True我們就能以shell方式去執(zhí)行命令。可以使用cwd指定工作目錄，獲取程序的外部輸出可以使用管道PIPE，調(diào)用communicate()方法可以可以獲取外部程序的輸出信息，也就是編譯錯誤信息。

可以根據(jù)編譯程序的返回值來判斷編譯是否成功，一般來說，返回值為0表示編譯成功。

有些語言，比如ruby和perl是解釋型語言，不提供編譯選項，因此在這里僅僅加上-c參數(shù)做簡單的代碼檢查。

python，lua，java等可以編譯成二進制文件然后解釋執(zhí)行。

ACMer們著重看一下gcc和g++和pascal的編譯參數(shù)，以后寫程序可以以這個參數(shù)進行編譯，只要在本地編譯通過一般在服務(wù)器上編譯就不會出現(xiàn)編譯錯誤問題。

可能有些朋友會有疑問：為什么加這么多語言？正式ACM比賽只讓用C,C++和JAVA語言啊！對這個問題，我只想說，做為一個在線測評系統(tǒng)，不能僅僅局限在ACM上。如果能讓初學者用這個平臺來練習編程語言不是也很好？做ACM是有趣的，用一門新的語言去做ACM題目也是有趣的，快樂的去學習一門語言不是學得很快？我承認，有好多語言不太適合做ACM，因為ACM對時間和內(nèi)存要求比較嚴格，好多解釋執(zhí)行的語言可能占內(nèi)存比較大，運行速度比較慢，只要抱著一種學習編程語言的心態(tài)去刷題就好了。此外，對于新興的go語言，我認為是非常適合用來做ACM的。牛逼的haskell語言也值得一學，描述高級數(shù)據(jù)結(jié)果也很方便。感興趣的可以試試。

我的評測程序是可以擴展的，如果想再加其他編程語言，只要知道編譯參數(shù)，知道如何執(zhí)行，配置好編譯器和運行時環(huán)境，在評測程序里面加上就能編譯和評測。

def compile(solution_id,language):'''將程序編譯成可執(zhí)行文件'''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 Truedblock.acquire()update_compile_info(solution_id,err+out) #編譯失敗,更新題目的編譯錯誤信息dblock.release()return False

用戶代碼在執(zhí)行過程中是如何進行評判的（ACMer必看）？

前面說了，如果出現(xiàn)編譯錯誤(Compile Error)，是不會執(zhí)行的。每個題目都有一個標準的時間和內(nèi)存限制，例如時間1000ms，內(nèi)存65536K，程序在執(zhí)行的時候會實時檢查其花費時間和使用內(nèi)存信息，如果出現(xiàn)超時和超內(nèi)存將會分別返回Time Limit Exceeded和Memory Limit Exceeded錯誤信息，如果程序執(zhí)行時出現(xiàn)錯誤，比如非法指針，數(shù)組越界等，將會返回Runtime Error信息。如果你的程序沒有出現(xiàn)上面的信息，說明程序順利執(zhí)行結(jié)束了。接下來，就是對你的程序的輸出也就是運行結(jié)果進行檢查，如果你的執(zhí)行結(jié)果和我們的標準答案完全一樣，則返回Accepted，也就說明你這個題目做對了。如果除去空格，換行，tab外完全相同，則說明你的代碼格式錯誤，將返回Presentation Error，如果你輸出的內(nèi)容有一部分和標準答案完全一樣，但是還輸出了一些其他內(nèi)容，則說明你多輸出了，這時候?qū)⒎祷豋utput Limit Exceeded錯誤信息，出現(xiàn)其他情況，就說明你的輸出結(jié)果和標準答案不一樣，就是Wrong Answer了。

總結(jié)一下錯誤的出現(xiàn)順序：

Compile Error?->?Memory Limit Exceeded?=?Time Limit Exceeded?=?Runtime Error?->?Wrong Answer?->?Output Limit Exceeded?->Presentation Error?->?Accepted

直接說難免有些空洞，做了張流程圖：

如果你得到了其他信息，比如System error，則說明服務(wù)器端可能出問題了，我們技術(shù)人員會想法解決。如果看到waiting，說明等待評測的代碼比較多，你需要稍作等待，直到代碼被評測。如果你得到了Judging結(jié)果，說明你的代碼正在評測，如果長時間一直是Judging，則說明評測程序在評測過程中可能出問題了，沒有評判出結(jié)果就停止了。技術(shù)人員會為你重判的。

希望ACMer們能根據(jù)上面的評測流程，在看到自己的評判結(jié)果的時候，能夠分析出你離AC還有多遠，以及如何改進你的代碼才能AC。

評判答案的那部分源碼：

def judge_result(problem_id,solution_id,data_num):'''對輸出數(shù)據(jù)進行評測'''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 Falseif curr == user: #完全相同:ACreturn "Accepted"if curr.split() == user.split(): #除去空格,tab,換行相同:PEreturn "Presentation Error"if curr in user: #輸出多了return "Output limit"return "Wrong Answer" #其他WA

注意一下，代碼中有個replace('\r','')方法，它的作用就是將\r替換成空字符串。為什么要做這個替換呢？因為在windows下，文本的換行是"\r\n",而在Linux下是"\n"。因為不能確定測試數(shù)據(jù)來源與windows還是Linux，增加一個\r，就是增加一個字符，如果不刪除的話，兩個文本就是不一樣的，就會造成wrong answer結(jié)果。或許你曾經(jīng)遇到過在windows下用記事本打開一個純文本文件，格式全亂了，所有文本都在一行內(nèi)，非常影響閱讀。你可以通過用寫字板打開來解決這個問題。據(jù)說"\r\n"來源于比較古老的打印機，每打印完一行，都要先“回車(\r)”，再“換行”(\n)。同樣一個C語言的printf("\n")函數(shù)，在windows下將生成"\r\n"，而在Linux下生成"\n"，因為評測程序為你自動處理了，因此你就不必關(guān)注這些細節(jié)的東西了。

評測程序是如何檢測你的程序的執(zhí)行時間和內(nèi)存的？

這個問題困擾了我好久，也查了好多資料。

用戶的程序要在服務(wù)器上執(zhí)行，首先不能讓用戶的程序無限申請內(nèi)存，否則容易造成死機現(xiàn)象，需要將程序的內(nèi)存限制在題目規(guī)定的最大內(nèi)存內(nèi)。其次要限制用戶程序的執(zhí)行時間，不能讓用戶的程序無限制運行。

一般解決方案是：在用戶的程序執(zhí)行前，先做好資源限制，限制程序能使用的最大內(nèi)存和CPU占用，當用戶的程序一旦超出限制就自動終止了。還有個比較重要的問題是如何獲取程序執(zhí)行期間的最大內(nèi)存占用率。用戶的代碼在執(zhí)行前需要申請內(nèi)存，執(zhí)行期間還能動態(tài)申請和釋放內(nèi)存，執(zhí)行完畢釋放內(nèi)存。程序執(zhí)行時還有可能使用指針等底層操作，這無疑給檢測內(nèi)存造成更大的困難。在windows下，程序執(zhí)行結(jié)束后，可以調(diào)用系統(tǒng)函數(shù)獲取程序執(zhí)行期間的最大內(nèi)存，貌似在Linux下沒用現(xiàn)成的函數(shù)可以調(diào)用。

在Linux下，我們可以使用ps或top命令來獲取或監(jiān)視在某個時刻應(yīng)用程序的內(nèi)存占用率，要獲取程序的最大執(zhí)行內(nèi)存，就要不斷去檢測，不斷去比較，直到程序結(jié)束，獲取最大值就是用戶程序執(zhí)行期間的最大內(nèi)存。根據(jù)這個設(shè)想，我寫了一個程序來實現(xiàn)這個想法：

def get_max_mem(pid):'''獲取進程號為pid的程序的最大內(nèi)存'''glan = psutil.Process(pid)max = 0while True:try:rss,vms = glan.get_memory_info()if rss > max:max = rssexcept:print "max rss = %s"%maxreturn maxdef run(problem_id,solution_id,language,data_count,user_id):'''獲取程序執(zhí)行時間和內(nèi)存'''time_limit = (time_limit+10)/1000.0mem_limit = mem_limit * 1024max_rss = 0max_vms = 0total_time = 0for i in range(data_count):'''依次測試各組測試數(shù)據(jù)'''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.pidglan = psutil.Process(pid)while True:time_to_now = time.time()-start + total_timeif psutil.pid_exists(pid) is False:program_info['take_time'] = time_to_now*1000program_info['take_memory'] = max_rss/1024.0program_info['result'] = result_code["Runtime Error"]return program_inforss,vms = glan.get_memory_info()if p.poll() == 0:end = time.time()breakif max_rss < rss:max_rss = rssprint 'max_rss=%s'%max_rssif max_vms < vms:max_vms = vmsif time_to_now > time_limit:program_info['take_time'] = time_to_now*1000program_info['take_memory'] = max_rss/1024.0program_info['result'] = result_code["Time Limit Exceeded"]glan.terminate()return program_infoif max_rss > mem_limit:program_info['take_time'] = time_to_now*1000program_info['take_memory'] = max_rss/1024.0program_info['result'] =result_code["Memory Limit Exceeded"]glan.terminate()return program_infologging.debug("max_rss = %s"%max_rss) # print "max_rss=",max_rsslogging.debug("max_vms = %s"%max_vms) # logging.debug("take time = %s"%(end - start))program_info['take_time'] = total_time*1000program_info['take_memory'] = max_rss/1024.0program_info['result'] = result_code[program_info['result']]return program_info

上面的程序用到了一些進程控制的一些知識，簡單說明一下。

程序的基本原理是：先用多進程庫subprocess的Popen函數(shù)去創(chuàng)建一個新的進程，獲取其進程號(pid)，然后用主線程去監(jiān)測這個進程，主要是監(jiān)測實時的內(nèi)存信息。通過比較函數(shù)，獲得程序的執(zhí)行期間的最大內(nèi)存。什么時候停止呢？有四種情況：

程序運行完正常結(jié)束。這個我們可以通過 subprocess.Popen里面的poll方法來檢測，如果為0,則代表程序正常結(jié)束。

程序執(zhí)行時間超過了規(guī)定的最大執(zhí)行時間，用terminate方法強制程序終止

程序執(zhí)行內(nèi)存超過了規(guī)定的最大內(nèi)存，terminate強制終止。

程序執(zhí)行期間出現(xiàn)錯誤，異常退出了，這時候我們通過檢查這個pid的時候就會發(fā)現(xiàn)不存在。

還有一點是值得注意的：上文提到在編譯程序的時候，調(diào)用subprocess.Popen，是通過shell方式調(diào)用的，但是這里沒有使用這種方式，為什么呢？這兩種方式有什么區(qū)別？最大的區(qū)別就是返回的進程的pid，以shell方式執(zhí)行，返回的pid并不是子進程的真正pid，而是shell的pid，當我們?nèi)z查這個pid的內(nèi)存使用率的時候得到的并不是用戶進程的pid！不通過shell方式去調(diào)用外部程序則是直接返回真正程序的pid，而不用去調(diào)用shell。官方文檔是這么說的：if shell is true, the specified command will be executed through the shell.

如果不用shell方式去執(zhí)行命令的話，傳遞參數(shù)的時候就不能直接將字符串傳遞過去，例如ls -l這個命令ls和參數(shù)-l，當shell=False時，需要將命令和參數(shù)變成一個列表['ls','-l']傳遞過去。當參數(shù)比較復(fù)雜的時候，將命令分隔成列表就比較麻煩，幸好python為我們提供了shlex模塊，里面的split方法就是專門用來做這個的，官方文檔是這么說的：Split the string s using shell-like syntax.，最好不要自己去轉(zhuǎn)換，有可能會導致錯誤而不能執(zhí)行。

上面的檢測內(nèi)存和時間的方法靠譜嗎？

不靠譜，相當不靠譜！（當然學學python如何對進程控制也沒壞處哈！）為什么呢？有點經(jīng)驗的都知道，C語言的運行效率比python高啊！執(zhí)行速度比python快！這會造成什么后果？一個簡單的hello world小程序，C語言“瞬間”就執(zhí)行完了，還沒等我的python程序開始檢測就執(zhí)行完了，我的評測程序什么都沒檢測到，然后返回0，再小的程序內(nèi)存也不可能是0啊！在OJ上顯示內(nèi)存為0相當不科學！

那怎么辦？能不能讓C語言的程序執(zhí)行速度慢下來？CPU的頻率是固定的，我們沒法專門是一個程序的占用的CPU頻率降低，在windows下倒是有變速齒輪這款軟件可以讓軟件執(zhí)行速度變慢，不知道在Linux下有沒有。還有沒有其他辦法？聰明的你也許會想到gdb調(diào)試，我也曾經(jīng)想用這種方法，用gdb調(diào)試可以使程序單步執(zhí)行，然后程序執(zhí)行一步，我檢測一次，多好，多完美！研究了好一陣子gdb，發(fā)現(xiàn)并不是那么簡單。首先，我們以前用gdb調(diào)試C/C++的時候，在編譯的時候要加上一個-g參數(shù)，然后執(zhí)行的時候可以單步執(zhí)行，此外，還有設(shè)置斷點什么的。有幾個問題：

其他語言如何調(diào)試？比如java，解釋執(zhí)行的，直接調(diào)試java虛擬機嗎？

如何通過python對gdb進行控制？還有獲取執(zhí)行狀態(tài)等信息。

這些問題都不是很好解決。

那上面的方法測量的時間準嗎？不準！為什么？我們說的程序的執(zhí)行時間，嚴格來說是占用CPU的時間。因為CPU采用的是輪轉(zhuǎn)時間片機制，在某個時刻，CPU在忙別的程序。上面的方法用程序執(zhí)行的結(jié)束時間減去開始時間，得到的時間一定比它實際執(zhí)行的時間要大。如果程序執(zhí)行速度過快，不到1毫秒，評測程序也不能檢測出來，直接返回0了。

如何解決時間和內(nèi)存的測量問題？

后來在v2ex上發(fā)了一個帖子提問，得到高人指點，使用lorun。lorun是github上的一個開源項目，項目地址：https://github.com/lodevil/Lo-runner，這是用C語言寫的一個python擴展模塊，讓程序在一個類似沙盒的環(huán)境下執(zhí)行，然后精準的獲取程序的執(zhí)行時間和內(nèi)存，還能對程序進行限制，限制程序的系統(tǒng)調(diào)用。原文是這么說的：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.。安裝使用都非常方便。我主要用它來測量執(zhí)行時間和內(nèi)存，后期代碼檢查還是用我的程序。

感興趣的同學可以將這個模塊下載下來，作為本地測試使用，可以預(yù)先生成一些測試數(shù)據(jù)，然后測量你的代碼的執(zhí)行時間和內(nèi)存，比對你的答案是否正確。

不同編程語言時間內(nèi)存如何限定？

一般來說，假設(shè)C/C++語言的標程是時間限制：1000ms,內(nèi)存限制32768K，那么java的時間和內(nèi)存限制都是標準限制的2倍，即2000ms，65536K。

由于后來我再OJ增加了好多其他語言，我是這樣規(guī)定的：編譯型的語言和速度較快的解釋型語言的時間和內(nèi)存限制和C/C++是一樣的，這樣的語言包括：C、C++、go、haskell、lua、pascal，其他速度稍慢的解釋執(zhí)行的語言和JAVA是一樣的，包括：java、python2、python3、ruby、perl。畢竟使用除C，C++，JAVA外的語言的朋友畢竟是少數(shù)，如果限制太嚴格的話可以根據(jù)實際情況對其他編程語言放寬限制。

多組測試數(shù)據(jù)的題目時間和內(nèi)存如何測算？

多組測試數(shù)據(jù)是一組一組依次執(zhí)行，時間和內(nèi)存取各組的最大值，一旦某組測試數(shù)據(jù)時間和內(nèi)存超出限制，則終止代碼執(zhí)行，返回超時或超內(nèi)存錯誤信息。

如何防止惡意代碼破壞系統(tǒng)？

我們可以使用以下技術(shù)來對用戶程序進行限制：

lorun模塊本身就有限制，防止外部調(diào)用

降低程序的執(zhí)行權(quán)限。在Linux下，目錄權(quán)限一般為755，也就是說，如果換成一個別的用戶，只要不是所有者，就沒有修改和刪除的權(quán)限。python里面可以使用os.setuid(int(os.popen("id -u %s"%"nobody").read()))來將程序以nobody用戶的身份執(zhí)行

設(shè)置沙盒環(huán)境，將用戶執(zhí)行環(huán)境和外部隔離。Linux下的chroot命令可以實現(xiàn)，python也有相關(guān)方法，但是需要提前搭建沙盒環(huán)境。用jailkit可以快速構(gòu)建沙盒環(huán)境，感興趣的朋友可以看看

使用ACL訪問控制列表進行詳細控制，讓nobody用戶只有對某個文件夾的讀寫權(quán)限，其他文件夾禁止訪問

評判機和服務(wù)器分離，找單獨的機器，只負責評判

對用戶提交的代碼預(yù)先檢查，發(fā)現(xiàn)惡意代碼直接返回Runtime Error

禁止評測服務(wù)器連接外網(wǎng)，或者通過防火墻限制網(wǎng)絡(luò)訪問

如何啟動和停止評測程序以及如何記錄錯誤日志？

啟動很簡單，只要用python執(zhí)行protect.py就行了。

如果需要后臺執(zhí)行的話可以使用Linux下的nohup命令。

為了防止同時開啟多個評測程序，需要將以前開啟的評測程序關(guān)閉。

為了方便啟動，我寫了這樣一個啟動腳本：

#!/bin/bash sudo kill `ps aux | egrep "^nobody .*? protect.py" | cut -d " " -f4` sudo nohup python protect.py &

第一條命令就是殺死多余的評測進程，第二條是啟動評測程序。

在程序里面使用了logging模塊，是專門用來記錄日志的，這么模塊很好用，也很強大，可定制性很強，對我們分析程序執(zhí)行狀態(tài)有很大幫助。下面是一些示例：

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文件，里面寫上配置的內(nèi)容，就像下面一樣：

#!/usr/bin/env python #coding=utf-8 #開啟評測線程數(shù)目 count_thread = 4 #評測程序隊列容量 queue_size = 4 #數(shù)據(jù)庫地址 db_host = "localhost" #數(shù)據(jù)庫用戶名 db_user = "user" #數(shù)據(jù)庫密碼 db_password = "password" #數(shù)據(jù)庫名字 db_name = "db_name"

使用的時候只需要將這個文件導入，然后直接config.queue_size就可以訪問配置文件里面的內(nèi)容，很方便的。

評測程序的評測效率如何？

自從服務(wù)器啟用新的評測程序之后，已經(jīng)經(jīng)歷了兩次大的比賽和幾次大型考試，在幾百個人的比賽和考試中，評測基本沒用等待現(xiàn)象，用戶提交的代碼基本都能立即評測出來。大體測了一下，單服務(wù)器平均每秒能判6個題目左右（包括獲取代碼，編譯，運行，檢測，數(shù)據(jù)庫寫入結(jié)果等流程）。評測程序目前已經(jīng)穩(wěn)定運行了幾個月，沒有出現(xiàn)大的問題，應(yīng)該說技術(shù)比較成熟了。

評測程序還能繼續(xù)改進嗎？

當時腦子估計是被驢踢了，居然使用多線程來評測！有經(jīng)驗的python程序猿都知道，python有個全局GIL鎖，這個鎖會將python的多個線程序列化，在一個時刻只允許一個線程執(zhí)行，無論你的機器有多少個CPU，只能使用一個！這就明顯影響評測速度！如果換成多進程方式，一個評測進程占用一個CPU核心，評測速度將會是幾倍幾十倍的性能提升！到時候弄個上千人的比賽估計問題也不大，最起碼評測速度能保證。

此外，還可以構(gòu)建一個分布式的評測服務(wù)器集群，大體設(shè)想了一下可以這樣實現(xiàn)：

首先，可以選一臺服務(wù)器A專門和數(shù)據(jù)庫交互，包括從數(shù)據(jù)庫中獲取評測任務(wù)以及評測結(jié)束將結(jié)果寫回數(shù)據(jù)庫。然后選擇N臺普通計算機作為評測機，評測機只和數(shù)據(jù)庫A打交道，也就是從服務(wù)器A獲取任務(wù)，在普通機器上評測，評測完后將結(jié)果反饋到服務(wù)器A，再由A將結(jié)果寫入到數(shù)據(jù)庫。服務(wù)器A在這里就充當一個任務(wù)管理和分配的角色，協(xié)調(diào)各個評測機去評測。這樣可以減少對數(shù)據(jù)庫的操作，評測機就不用去一遍一遍掃數(shù)據(jù)庫了。評測的速度和安全性可以得到進一步提升。

其他

• 附在線簡歷一份：http://ma6174.github.io/#show/me，準備實習，希望大牛指點
• 項目地址：https://github.com/ma6174/acmjudger
• 原文鏈接：http://www.cnblogs.com/ma6174/archive/2013/05/12/3074034.html
• 上面的程序和方法僅供學習和研究用，嚴禁任何非法用途
• 本人學識有限，如有錯誤歡迎批評指正

總結(jié)

以上是生活随笔為你收集整理的ACM在线测评系统评测程序设计与python实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。