摘 要: 分析了一種基于ACM程序設計競賽在線評測系統的基本原理及系統的構成,重點闡述了程序性能評判原理及實現方法。對通信安全、資源占用等關鍵問題給出了相應的解決方案，主要模塊給出了相應代碼。
關鍵詞：評測系統；ACM；程序性能

    ACM國際大學生程序設計競賽 (ACM/ICPC或ICPC) 是由美國計算機協會 (ACM) 主辦、旨在展示大學生創新能力、團隊精神和在壓力下編寫程序、分析和解決問題能力的年度競賽。經過近 30 年的發展，ACM 國際大學生程序設計競賽已經發展成為最具影響力的大學生計算機競賽。競賽規模的迅速擴大對閱卷工作的自動化、高效性、合理性和公正性提出了更高的要求，建立一套準確、高效的程序評測系統成為非常迫切的需求?；谝陨显?，本文給出了一種網絡自動化的程序性能分析評價系統——ACM國際大學生程序設計競賽在線評測系統的實現方案。
1 評測系統簡介
    本系統提供了對C、C++、Java三種語言所編寫的程序進行處理的功能。用戶按照競賽題目的要求，通過對問題的分析并給出解決方案后，就可以向系統提交解決問題的源代碼程序。系統可以根據用戶提供的源代碼，采取相應的程序語言環境編譯、運行。在編譯與運行正常以后,系統按照題目要求來判斷該程序結果否正確,同時給出程序的運行時間、內存的開銷等情況，根據程序性能信息表[1-2]來判斷各個用戶的得分情況。
    系統運行于Linux操作系統，借助Linux操作系統所提供的多任務、多線程功能及其穩定的性能和免費開源的內核，從而大大減少程序員書寫系統代碼的工作量,也提高了系統的運行效率。代碼是用C語言編寫的,通過自己編寫函數或調用C語言內部函數來訪問系統所使用的資源。
2 評測系統的體系結構
    評測系統網絡體系結構采用先進的B/S模式的三層架構，如圖1所示，這種結構符合面向服務（SOA）的模塊設計，模塊耦合性低，使得業務邏輯的添加、修改較為容易，并且網絡通信安全性能方面也大為提高。用戶通過瀏覽器連接評測系統，表示層UI 是系統呈現給用戶的使用界面，用戶通過 UI 進行登錄、瀏覽、提交代碼等操作。業務邏輯層BL負責實現根據性能信息表數據評分等除測試部分以外的各模塊的功能。本系統將評測部分（主要是黑盒測試）從業務邏輯層中獨立了出來，成為一個專門的測試模塊，這種做法的優點是對測試模塊的修改、增刪都很容易進行。數據庫DB主要用來存儲用戶提交的程序性能信息表及用戶信息表等，程序性能信息表中主要包括程序的各種性能信息，例如是否通過編譯、是否超出最大時間、是否正常結束、語言類別、結果是否正確、代碼運行時間、內存開銷、CPU占用量、代碼長度等。測試模塊從數據庫取得未測試代碼，進行評測，將程序性能信息表中相關項的評測結果返回給數據庫，業務邏輯則從數據庫取得程序性能信息表，并根據表中各項數據評分，對于未通過編譯、超出最大時間、非正常結束、結果不正確的程序按不合格處理，對于上面各項都合格的則按程序性能信息表中其余項進行綜合評分。

3 評判原理
    對程序編譯與運行過程中出現的錯誤，系統會根據錯誤的不同給出相應的提示,例如是編譯錯誤或者是運行錯誤。如果編譯和運行都正確，系統將進一步通過相應的題目要求、對程序要求給出的輸入和程序輸出的結果，來判斷該程序是否正確。
    在進行程序評判時，先啟動服務器評測進程，在偵聽到有提交記錄時,系統立即對提交記錄的相關題目進行評判。每個問題均對應一組數據(輸入和輸出文件)，系統設計時采用Linux管道(pipe(int filedes[3])）來處理，評判進程啟動一個子進程(fork())來編譯運行用戶提交的程序，讀入該題目的輸入數據，評判程序每次從管道讀入一個字符與標準輸出數據比較，如果兩個文件完全一樣，則表示程序正確；如發現只是相差空格、Tab、回車，則給出該程序為輸出格式錯誤信號(Presentation Error)；如果發現其他字符的不匹配，則立即中止該程序，則給出該程序為結果錯誤的信號Wrong Answer。從程序運行時刻開始計時，在時間允許范圍之內，得到了正確答案，則此提交程序符合題目要求并通過系統時間和內存的限制，給出接受的信號(Accepted)。反之，如果答案錯、或者表達錯、運行錯等，則向該進程發出SIGKILL信號，強行中止該進程，對數據庫記錄進行相應的修改。運行流程如圖2所示。

4 程序核心內容分析
    為了能有效地解決和判斷用戶程序對系統資源的使用情況，系統定義了rusage結構體。該結構體具體信息為：
    struct rusage {
    struct timeval ru_utime;              /* user time used */
    struct timeval ru_stime;            /* system time used */
    long ru_minflt;                            /* page reclaims */
    long ru_majflt;                               /* page faults */
    };
    ru_utime和ru_stime成員變量包含了在用戶模式和系統模式中執行時間的總和。其結構都為timeval結構。
    ru_minflt成員指不需要I/O的頁缺失數。頁缺失發生在內核需要得到一個內存頁以供進程訪問。
    ru_majflt值指需要I/O的頁缺失數。頁缺失發生在內核需要得到一個內存頁以供進程訪問時。
    有時，一個進程會被調出內存，以提供空間給其他進程使用。ru_nswap指的就是一個進程被調出內存的次數。
    通過該結構體就可以統計出各用戶程序對資源的占用情況，通過調用函數int getrusage(int who, struct rusage *rusage)對用戶程序運行時間和內存占用情況進行分析統計。
    統計程序運行時間：
    passtime=usage.ru_utime.tv_sec+usage.ru_stime.tv_sec+(float)(usage.ru_stime.tv_usec+usage.ru_utime.tv_usec)/1000000;
    統計程序所占內存的開銷： 
    usedMemory = usage.ru_minflt*4
    通過統計該兩項，能計算出程序運行時間和內存使用情況的數據，為結果排序做準備。
5 系統安全處理
    用戶提交的程序在服務器上運行，為了保證系統安全運行、減少或杜絕故障的發生，在解決安全故障方面主要有以下幾個方面。
    （1） 文件操作
　　為了讓用戶提交上來的程序不破壞本機的文件系統，本設計采用了管道技術，在執行用戶程序之前，先把輸入流定向到標準輸入文件，然后使用chroot命令改變用戶程序的執行目錄，讓其只能在一個臨時文件夾下面做操作。
    （2） 網絡操作
　　為了不讓用戶程序影響評判系統的設置，保證評判系統的公正性，必須禁止用戶對網絡的訪問。系統通過對用戶實行權限限制機制，判斷系統在用戶程序運行之前，通過調用Linux系統中setuid(99) 和 setgid(99)兩個函數[4]，讓用戶程序的擁有者權限降到最低，達到防止用戶對網絡使用的目的。
    （3） 資源管理
    資源管理的作用是對客戶進程所使用的資源進行管理，Linux系統提供的資源限制函數setrlimit(),可以避免用戶進程在運行的過程中過多地占用系統資源，以影響服務器系統的穩定性,最終有可能導致系統的崩潰。
    為了防止用戶進程占用過多的資源，影響服務器系統的穩定，對用戶進程在占用資源方面進行限制，主要考慮程序運行時間和內存占用兩個方面，在程序運行之前，通過調用系統函數setrlimit()來限制程序對系統資源的占用。函數setrlimit( RLIMIT_AS,&memlim)和setrlimit( RLIMIT_CPU,&timlim)分別用來限制用戶程序對CPU和內存的占用情況，如果某用戶的程序超過了系統對CPU和內存的最大設置值，該進程就會被自動中止，標志用戶的程序不滿足比賽要求。
    通過對基于ACM國際大學生程序設計競賽在線評測系統的分析研究，設計了相應的ACM測試軟件，習題的測試難度可由指導老師自己設計。該軟件也可以作為計算機專業學生算法測試工具，通過對該測試系統的使用，經過一定題量的練習，可以增強學生在算法方面設計的技能，為學生奠定雄厚的編程基礎。
參考文獻
[1] ESPINOSA A, MARGALEF T, LUQUE E. Automatic performance evaluation of parallel programs. The Sixth Euromicro Workshop on Parallel and Distribued Processing, 1998(21):43-49.
[2] ESPINOSA A, MARGALEF T, LUQUE E. Automatic detection of parallel program performance problems. Lecture Notes in Computer Science 1999(1573):365-377.
[3] STEVENS W R, RAGO S A著.UNIX環境高級編程（第2 版）[M] . 尤晉元，張來英，戚正偉，譯.北京：人民郵電出版社，2006.
[4] SARWAR S M, KORETSKY R, SARWAR S A著. Linux教程[M].李善平，施韋，林欣，譯.北京：清華大學出版社，2005.