基于Web的ACM/ICPC自動評測系統的設計與實現

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

關鍵詞: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

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

1 自動測評系統總體框架

1.1 系統基本架構

自動評測系統采用MVC三層模型，利用Struts框架搭建[2]。三層結構的劃分，使邏輯上更加獨立，每個功能模塊的任務更加清晰。在視圖層客戶通過Web瀏覽器向控制層的應用服務器發出HTTP請求，應用服務器通過對客戶端的請求進行身份驗證，然后對于合法的用戶請求進行處理并與數據庫進行連接進而獲取或保存數據并將從數據庫獲得的數據返回到客戶端瀏覽器。客戶端是真正的“瘦客戶端”，而且通過與Web網絡相連接使其具有跨區域的特點。控制層是MVC結構的核心，它主要完成對業務規則的控制和對數據庫的訪問等工作。模型層，即數據庫訪問層，負責數據的定義、查詢、更新和刪除等操作并維護數據庫的安全性和完整性。系統基本架構如圖1所示。

1.2 系統總體結構

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

2 系統設計

2.1 數據庫設計

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

2.2 系統前臺設計

2.2.1 用戶管理設計

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

2.2.2 評測流程設計

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

2.3 系統后臺設計

2.3.1 問題管理設計

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

2.3.2 競賽管理設計

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

3 關鍵技術的設計與實現

3.1 自動評測的設計

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

3.1.1數據/信號的發送和接收

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

3.1.2 編譯與鏈接

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

3.1.3 運行與測試

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

3.1.4 評審與返回結果

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

3.2 評測核心技術的實現

3.2.1 查找問題

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

3.2.2 提交問題

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

3.2.3 查看提交狀態

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

3.2.4 查看問題狀態

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

4 結束語

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

參考文獻:

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

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

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

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

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

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