基于Web的ACM/ICPC自動評測系統(tǒng)的設計與實現(xiàn)

摘要:針對現(xiàn)有ACM程序設計競賽評判系統(tǒng)存在的缺陷，采用了新的架構模式，設計了用于大學生程序設計訓練和競賽的自動評測系統(tǒng)，實現(xiàn)了對用戶提交的程序源代碼進行自動編譯、連接、運行、測試、評審等過程并返回測試結果，采用了多進程的并發(fā)處理、信號處理、進程通信、文件管理等技術，使得該自動測評系統(tǒng)在實際應用過程中發(fā)揮良好的性能，完成了日常編程訓練和各類網(wǎng)上程序設計競賽活動，體現(xiàn)了競賽過程的自動化、高效率、公正性等特性。

關鍵詞:ACM;程序設計;在線評測;競賽;進程

中圖分類號:TP311文獻標識碼:A文章編號:1009-3044(2009)35-9974-03

Design and Implementation of ACM/ICPC Automatic Test and Judgement System Based on Web

HAN Li-mao， XU Xiu-fang，SHI Shun

(School of Information Engineering， Yancheng Institute of Technology， Yancheng 224051， China)

Abstract: Considering the shortcomings of the current ACM programming contest evaluation system， a new framework is adopted. An automatic evaluation system for the collegiate programming contest is designed. Automatic interpretation of source code submitted by the user， linking， runing， testing， appraisal process and returning the test results are realized. A multi-process， concurrent processing， signal processing， process communication， document management and other technologies are used. Consequently， the said automatic evaluation system has good performance in the practical application， completing a routine program of training and various types of online programming contest and realizing the automation of competition process， high efficiency， fairness and other features.

Key words: association for computing machinery; program design; online judgment; competition; process

美國計算機協(xié)會(ACM)組織的國際大學生程序設計競賽(ICPC)是目前世界上規(guī)模最大的計算機學科賽事。該項賽事發(fā)起于1977年，其宗旨是為高等學校的大學生提供一個展示自己在計算機編程解題方面才能的機會。為了提高競技水平，迫切需要一套完備的自動化系統(tǒng)輔助競賽的日常訓練和模擬競賽[1]。ACM國際大學生程序設計競賽所應用的競賽平臺稱為ACM Online Judge，競賽過程中參賽選手只需提交源代碼即可。目前，官方?jīng)]有提供因特網(wǎng)版平臺，但由各大高校獨立完成。國內(nèi)主要以北京大學和浙江大學等所提供的平臺為主，均采用Windows系統(tǒng)，開發(fā)容易，但是安全性和效率方面不是很理想。因此開發(fā)一套安全性和效率都有保證的競賽測試平臺很有必要。

1 自動測評系統(tǒng)總體框架

1.1 系統(tǒng)基本架構

自動評測系統(tǒng)采用MVC三層模型，利用Struts框架搭建[2]。三層結構的劃分，使邏輯上更加獨立，每個功能模塊的任務更加清晰。在視圖層客戶通過Web瀏覽器向控制層的應用服務器發(fā)出HTTP請求，應用服務器通過對客戶端的請求進行身份驗證，然后對于合法的用戶請求進行處理并與數(shù)據(jù)庫進行連接進而獲取或保存數(shù)據(jù)并將從數(shù)據(jù)庫獲得的數(shù)據(jù)返回到客戶端瀏覽器?？蛻舳耸钦嬲摹笆菘蛻舳恕?，而且通過與Web網(wǎng)絡相連接使其具有跨區(qū)域的特點?？刂茖邮荕VC結構的核心，它主要完成對業(yè)務規(guī)則的控制和對數(shù)據(jù)庫的訪問等工作。模型層，即數(shù)據(jù)庫訪問層，負責數(shù)據(jù)的定義、查詢、更新和刪除等操作并維護數(shù)據(jù)庫的安全性和完整性。系統(tǒng)基本架構如圖1所示。

1.2 系統(tǒng)總體結構

該系統(tǒng)分為前臺信息子系統(tǒng)和后臺管理子系統(tǒng)[3]。前臺信息子系統(tǒng)主要包括信息瀏覽、用戶登錄、用戶信息修改和提交題目。在前臺信息子系統(tǒng)中，用戶必須注冊為本系統(tǒng)的用戶，并且登錄后才能完成用戶信息修改、提交題目等功能。后臺管理子系統(tǒng)主要負責對整個系統(tǒng)的管理，包括題庫中卷的管理、題目的管理，以及各類競賽的創(chuàng)建等。后臺管理子系統(tǒng)還負責對前臺用戶所提交的代碼進行運行處理，并向前臺返回狀態(tài)信息。在線評測系統(tǒng)可分為用戶管理、問題管理、評測流程、論壇管理、郵件管理、競賽管理、競賽評測等7個大的功能模塊。用戶管理模塊包括注冊、登錄、權限控制等功能以及管理員的管理用戶信息等功能;問題管理模塊可以為管理員提供增加問題、修改評測數(shù)據(jù)等功能;評測流程模塊為系統(tǒng)的主要處理流程，維護幾個評測進程，提供評測功能的實現(xiàn);論壇管理和郵件管理模塊是系統(tǒng)的交流平臺，用戶可以在論壇內(nèi)留言或者給其他用戶發(fā)郵件;競賽管理模塊提供競賽管理功能，管理員通過競賽管理模塊來增加和控制競賽;競賽評測流程基于評測流程模塊，但是又獨立于評測流程模塊，可以單獨開啟或者關閉，主要用來完成在線評測系統(tǒng)競賽中的評測功能的實現(xiàn)，系統(tǒng)總體結構如圖2所示。

2 系統(tǒng)設計

2.1 數(shù)據(jù)庫設計

系統(tǒng)中的數(shù)據(jù)表主要有:用戶信息表、題目信息表、競賽信息表、競賽題目信息表、競賽用戶信息表、競賽提交信息表、登錄信息表、系統(tǒng)評測信息表、論壇留言信息表、論壇主題信息表、郵件信息表等。其中重要的有問題信息表和競賽提交信息表，如表1和表2所示。

2.2 系統(tǒng)前臺設計

2.2.1 用戶管理設計

用戶管理模塊包括注冊、用戶信息修改、權限控制、登錄和登出等功能，管理員額外可以使用用戶權限修改和用戶控制功能。注冊主要為用戶提供注冊，其中包括用戶名、密碼、昵稱、郵箱、簽名的輸入，并進行相應的驗證。用戶信息修改提供給用戶修改自己的信息，可以修改密碼、昵稱和簽名。權限控制貫穿于整個系統(tǒng)之中，系統(tǒng)為普通用戶和管理員提供不同的接口，實現(xiàn)不同的功能。登錄和登出用來管理用戶的會話信息，登錄時系統(tǒng)在會話中保留用戶的基本信息，包括用戶ID、用戶名、權限等。登出時會清除。用戶權限修改為管理員管理用戶權限所用，管理員可以管理所有人的權限，包括提升或者取消其他的管理員權限。用戶控制為管理員管理用戶登錄、發(fā)帖等動作所用，管理員可以禁止其他用戶登錄或發(fā)帖。

2.2.2 評測流程設計

競賽評測流程與普通評測流程類似，但獨立于普通評測流程，其中包括查看競賽題目、提交競賽代碼、查看排名、查看競賽狀態(tài)、下載成績Excel等功能。全部功能提供給注冊用戶使用。查看競賽題目與查看題目稍有不同，查看競賽題目只能在競賽進行中查看，而且應與普通題目的顯示有明顯區(qū)別。提交為用戶提交競賽代碼所用，其中代碼會被提交給競賽評測進程評測，之后會計入用戶的競賽成績。查看排名是系統(tǒng)在對所有用戶進行排名之后，會生成所有用戶的排名具體信息。其中應包括提交次數(shù)，通過題數(shù)等信息。查看競賽狀態(tài)是指用戶可以對競賽的狀態(tài)有所了解，包括競賽何時開始，何時結束，剩余時間等。下載成績Excel是在查看排名之后可以下載此排名信息為Excel文件進行保存或者打印。

2.3 系統(tǒng)后臺設計

2.3.1 問題管理設計

問題管理包括新增問題、修改問題、管理測試數(shù)據(jù)等功能，全部只有管理員才能使用。新增問題向系統(tǒng)中新增一個問題，其中需要輸入問題的內(nèi)容，包括標題、描述、輸入輸出說明、輸入輸出樣例等，還需要增加輸入問題的限制條件，包括時間限制、內(nèi)存限制、輸出限制等。修改問題是修改系統(tǒng)中已存在的問題。其中可以修改除問題ID以外的所有數(shù)據(jù)，也可以開啟和關閉問題。管理測試數(shù)據(jù)對應問題的輸入輸出數(shù)據(jù)，其中可以刪除、新增和修改輸入和輸出數(shù)據(jù)。

2.3.2 競賽管理設計

競賽管理包括新建競賽、修改競賽、管理競賽題目、競賽控制等功能。這些功能只向管理員開放。新建競賽是管理員可以建立新的競賽，其中需要輸入競賽的日期時間、持續(xù)時間、標題等。新建的競賽不可以刪除。修改競賽是管理員可以修改已存在的競賽，修改的內(nèi)容包括除了競賽ID外的所有內(nèi)容。注意，競賽一旦開始，所有內(nèi)容就不能修改了。管理競賽題目是管理員可以管理競賽的題目。其中包括增加、刪除、修改等等。這些題目需要預先在系統(tǒng)中存在，可以為啟用或者為未啟用狀態(tài)。競賽控制是管理員可以開始、暫停、繼續(xù)、結束競賽，也可以重置競賽時間，恢復競賽的評測進程。

3 關鍵技術的設計與實現(xiàn)

3.1 自動評測的設計

自動評測的主要工作是接收客戶端IE瀏覽器通過中間層的CGI程序提交到數(shù)據(jù)庫的數(shù)據(jù)，選擇適當?shù)臄?shù)據(jù)投入自動測評的全過程，包括:編譯、鏈接、運行、測試、評審、返回結果等一系列操作[4]。自動評測進程在未接到工作任務時，處于睡眠狀態(tài)，等待相關用戶請求進程發(fā)送消息信號，喚醒后轉(zhuǎn)入運行狀態(tài)。

3.1.1數(shù)據(jù)/信號的發(fā)送和接收

數(shù)據(jù)/信號的發(fā)送使用Linux系統(tǒng)進程間通信VIPC的消息隊列的方式，由中間層應用服務器的CGI程序把用戶提交的源程序代碼、編號、語言等信息寫入系統(tǒng)VIPC的消息隊列;使用Linux操作系統(tǒng)的信號處理方式，由中間層的CGI程序向客戶端的自動評測程序發(fā)送一個用戶信號，以喚醒處于睡眠狀態(tài)的進程投入運行，執(zhí)行相關的處理。數(shù)據(jù)/信號的接收同樣使用VIPC的消息隊列的方式，由服務端的自動評測進程從已存在的消息隊列中讀取一條消息。

3.1.2 編譯與鏈接

自動評測進程使用系統(tǒng)的函數(shù)調(diào)用，調(diào)用GNU編譯器對源程序代碼執(zhí)行自動編譯，并通過系統(tǒng)調(diào)用的返回值，捕捉系統(tǒng)調(diào)用的編譯命令是否成功，否則保存編譯錯誤的信息，同時中斷以后的執(zhí)行。經(jīng)過編譯成功之后，自動評測進程繼續(xù)使用系統(tǒng)調(diào)用對編譯生成的二進制代碼執(zhí)行自動鏈接，產(chǎn)生對應的可執(zhí)行的二進制代碼供下一步操作使用。

3.1.3 運行與測試

把鏈接生成的可執(zhí)行程序投入自動運行。同時，在程序運行的過程中，通過Linux系統(tǒng)捕捉系統(tǒng)信號，檢查程序的運行過程中是否出現(xiàn)超時、棧溢出、段錯誤等非法情況。另外，運行時還要完成測試數(shù)據(jù)的輸入和輸出的轉(zhuǎn)換，通過系統(tǒng)函數(shù)把數(shù)據(jù)的文件輸入重定向到標準輸入，把數(shù)據(jù)的標準輸出重定向到文件輸出，從而使得程序運行的結果保存為一個臨時的文本文件，交給下一步操作進行評審。

3.1.4 評審與返回結果

經(jīng)過編譯、鏈接、運行他和測試后，轉(zhuǎn)入運行結果的階段，對保存在臨時文件中的輸出數(shù)據(jù)進行檢查，與標準數(shù)據(jù)進行一致性的對比。

3.2 評測核心技術的實現(xiàn)

3.2.1 查找問題

查找問題有4種方式，第一種是直接在問題列表中點擊鏈接，第二種是在按問題標題查找，第三種是按問題號查找，第四種是隨機選題。所有的查找都可以向用戶顯示一個問題的詳細界面。按標題查找和按問題號查找使用了關鍵字技術，用戶需要輸入查找的關鍵字。其中按標題查找為模糊查找方式，而按問題號查找則為精確查找方式。隨機選題的流程:先使用隨機種子在所有問題號范圍內(nèi)查找一個問題的問題號，再判斷用戶是否已經(jīng)通過該問題，如果用戶通過該問題則放棄此次查找，繼續(xù)隨機查找下一道問題，直到找到一道用戶沒有通過的問題，但是出于負載考慮，隨機選題默認的最大次數(shù)定義為100，即隨機100次之后，就會拋出找不到問題的異常。

3.2.2 提交問題

提交問題是整個評測系統(tǒng)的核心。用戶可以按照問題的輸入輸出說明編寫代碼，然后將代碼提交給評測系統(tǒng)，提交代碼的語言可以選擇C、C++或者Java。提交之后，系統(tǒng)在數(shù)據(jù)庫中記錄用戶的提交信息，在服務器端將提交代碼生成對應的程序源文件，并把提交事件記錄進評測循環(huán)隊列[6]。評測開始后評測進程首先對生成的程序源文件進行編譯，如果程序存在語法錯誤，則編譯會不通過并且返回編譯錯誤信息。如果編譯通過，則評測進程會在服務器端運行生成的可執(zhí)行文件，在此可執(zhí)行文件運行的過程中，對系統(tǒng)資源進行嚴格限制，包括時間限制、內(nèi)存限制、輸出限制等。在程序運行正常結束后，系統(tǒng)將運行時捕捉的輸出信息同預先存放的測試輸出文件進行比較，如果比較的結果正確，則更新用戶的通過數(shù)量、排名信息、以及問題的通過數(shù)量等。整個流程圖如圖3所示。

3.2.3 查看提交狀態(tài)

用戶提交之后會自動跳轉(zhuǎn)到查看提交狀態(tài)界面，用戶可以在此查看提交的結果。其中結果包括:1)Queuing:程序正在等待隊列中，等待編譯和執(zhí)行。2)Accepted:程序通過了所有的測試，最后的答案也是正確的。3)Presentation Error:格式錯誤。說明輸出是正確的，但是很遺憾，可能在什么地方多輸出了一個空行或者空格，這種情況一般只要再修改下輸出就可以了。4)Time Limit Exceed:時間超出。每道題目都有規(guī)定時間限制，程序沒有在規(guī)定時間執(zhí)行完，就會返回這個信息。一般需要修改輸入輸出的方式或者程序的算法才能通過這道題目的評測。5)Memory Limit Exceed:內(nèi)存超出。每道題目都有規(guī)定內(nèi)存限制，程序申請了過多的內(nèi)存，就會返回這個錯誤。6)Wrong Answer:錯誤結果。只是比較常見的錯誤信息。說明程序算法有問題，需要修改。如果發(fā)現(xiàn)這個信息返回在第二個或者之后的測試案例中，那么有可能沒有考慮到一些極端的情況。7)Compile Error:編譯錯誤。程序沒有通過編譯。一般系統(tǒng)會給出編譯錯誤信息，可以查找為什么沒有通過編譯。應該先在IDE中進行編譯測試之后再提交到評測系統(tǒng)中。8)Runtime Error:運行時錯誤。一般有這幾種情況:數(shù)組越界、除零、空指針、堆棧溢出。出現(xiàn)這個信息，表示程序中存在漏洞，需要仔細查找。9)Judging:程序正在評測中。10)System Error:系統(tǒng)級錯誤。

3.2.4 查看問題狀態(tài)

查看問題狀態(tài)是用戶可以查看此問題的提交狀態(tài)，包括通過的比例，最好的通過時間、耗費內(nèi)存大小等信息。此頁面用統(tǒng)計圖表的方式展現(xiàn)。讓用戶可以清楚地了解問題的提交結果。統(tǒng)計圖表部分使用了開源項目JfreeChart來實現(xiàn)，這是一個能在服務器端生成統(tǒng)計圖表圖片并顯示在客戶端的一個工具。在服務器端需要定義PieDataset對象，并將數(shù)據(jù)填充到此對象中，然后設置圖表的樣式，最后通過Servlet傳送到頁面進行顯示。

4 結束語

根據(jù)在線教育資源系統(tǒng)的現(xiàn)狀，分析歸納出原有相關系統(tǒng)存在的不足，提出了基于Web的分布式架構和分布式程序設計競賽系統(tǒng)的解決方案。實現(xiàn)了對用戶提交的程序源代碼進行自動編譯、連接、運行、測試、評審等過程并返回測試結果，采用多進程的并發(fā)處理、信號處理、進程通信、文件管理等技術，充分發(fā)揮了Linux操作系統(tǒng)的優(yōu)良特性，使得該自動測評系統(tǒng)在實際應用過程中發(fā)揮良好的性能，在該系統(tǒng)上舉辦過多次大型的網(wǎng)上公開競賽，吸引大批編程愛好者的參加，取得了令人滿意的效果，具有很好的推廣使用價值。

參考文獻:

[1] 陳宇，楊成虎，莊英杰.基于Linux的ACM程序設計競賽在線評判系統(tǒng)研究[J].民營科技，2008(2):26-88.

[2] 劉新.Java開發(fā)技術大全[M].北京:清華大學出版社，2009.

[3] 鄭傳生.基于B/S結構的程序設計競賽自動測評系統(tǒng)的設計[J].計算機與現(xiàn)代化，2007(12):109-111.

[4] 王卓威，尹寶林.一個基于網(wǎng)絡的程序自動評測系統(tǒng)[J].北京航空航天大學學報，2004，30(6):502-5050.

[5] 馮新翎.基于.NET平臺的網(wǎng)絡教學評測系統(tǒng)的設計[J].電腦知識與技術，2008，4(6):1531-1532.

[6] 惠敏順，朱國進.基于SOA的分布式程序設計競賽系統(tǒng)的研究[J].計算機技術與發(fā)展，2008，18(10):123-126.