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

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

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

4 程序核心內(nèi)容分析
    為了能有效地解決和判斷用戶程序?qū)ο到y(tǒng)資源的使用情況，系統(tǒng)定義了rusage結(jié)構(gòu)體。該結(jié)構(gòu)體具體信息為：
    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成員變量包含了在用戶模式和系統(tǒng)模式中執(zhí)行時間的總和。其結(jié)構(gòu)都為timeval結(jié)構(gòu)。
    ru_minflt成員指不需要I/O的頁缺失數(shù)。頁缺失發(fā)生在內(nèi)核需要得到一個內(nèi)存頁以供進(jìn)程訪問。
    ru_majflt值指需要I/O的頁缺失數(shù)。頁缺失發(fā)生在內(nèi)核需要得到一個內(nèi)存頁以供進(jìn)程訪問時。
    有時，一個進(jìn)程會被調(diào)出內(nèi)存，以提供空間給其他進(jìn)程使用。ru_nswap指的就是一個進(jìn)程被調(diào)出內(nèi)存的次數(shù)。
    通過該結(jié)構(gòu)體就可以統(tǒng)計出各用戶程序?qū)Y源的占用情況，通過調(diào)用函數(shù)int getrusage(int who, struct rusage *rusage)對用戶程序運行時間和內(nèi)存占用情況進(jìn)行分析統(tǒng)計。
    統(tǒng)計程序運行時間：
    passtime=usage.ru_utime.tv_sec+usage.ru_stime.tv_sec+(float)(usage.ru_stime.tv_usec+usage.ru_utime.tv_usec)/1000000;
    統(tǒng)計程序所占內(nèi)存的開銷： 
    usedMemory = usage.ru_minflt*4
    通過統(tǒng)計該兩項，能計算出程序運行時間和內(nèi)存使用情況的數(shù)據(jù)，為結(jié)果排序做準(zhǔn)備。
5 系統(tǒng)安全處理
    用戶提交的程序在服務(wù)器上運行，為了保證系統(tǒng)安全運行、減少或杜絕故障的發(fā)生，在解決安全故障方面主要有以下幾個方面。
    （1） 文件操作
　　為了讓用戶提交上來的程序不破壞本機(jī)的文件系統(tǒng)，本設(shè)計采用了管道技術(shù)，在執(zhí)行用戶程序之前，先把輸入流定向到標(biāo)準(zhǔn)輸入文件，然后使用chroot命令改變用戶程序的執(zhí)行目錄，讓其只能在一個臨時文件夾下面做操作。
    （2） 網(wǎng)絡(luò)操作
　　為了不讓用戶程序影響評判系統(tǒng)的設(shè)置，保證評判系統(tǒng)的公正性，必須禁止用戶對網(wǎng)絡(luò)的訪問。系統(tǒng)通過對用戶實行權(quán)限限制機(jī)制，判斷系統(tǒng)在用戶程序運行之前，通過調(diào)用Linux系統(tǒng)中setuid(99) 和 setgid(99)兩個函數(shù)[4]，讓用戶程序的擁有者權(quán)限降到最低，達(dá)到防止用戶對網(wǎng)絡(luò)使用的目的。
    （3） 資源管理
    資源管理的作用是對客戶進(jìn)程所使用的資源進(jìn)行管理，Linux系統(tǒng)提供的資源限制函數(shù)setrlimit(),可以避免用戶進(jìn)程在運行的過程中過多地占用系統(tǒng)資源，以影響服務(wù)器系統(tǒng)的穩(wěn)定性,最終有可能導(dǎo)致系統(tǒng)的崩潰。
    為了防止用戶進(jìn)程占用過多的資源，影響服務(wù)器系統(tǒng)的穩(wěn)定，對用戶進(jìn)程在占用資源方面進(jìn)行限制，主要考慮程序運行時間和內(nèi)存占用兩個方面，在程序運行之前，通過調(diào)用系統(tǒng)函數(shù)setrlimit()來限制程序?qū)ο到y(tǒng)資源的占用。函數(shù)setrlimit( RLIMIT_AS,&memlim)和setrlimit( RLIMIT_CPU,&timlim)分別用來限制用戶程序?qū)PU和內(nèi)存的占用情況，如果某用戶的程序超過了系統(tǒng)對CPU和內(nèi)存的最大設(shè)置值，該進(jìn)程就會被自動中止，標(biāo)志用戶的程序不滿足比賽要求。
    通過對基于ACM國際大學(xué)生程序設(shè)計競賽在線評測系統(tǒng)的分析研究，設(shè)計了相應(yīng)的ACM測試軟件，習(xí)題的測試難度可由指導(dǎo)老師自己設(shè)計。該軟件也可以作為計算機(jī)專業(yè)學(xué)生算法測試工具，通過對該測試系統(tǒng)的使用，經(jīng)過一定題量的練習(xí)，可以增強(qiáng)學(xué)生在算法方面設(shè)計的技能，為學(xué)生奠定雄厚的編程基礎(chǔ)。
參考文獻(xiàn)
[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環(huán)境高級編程（第2 版）[M] . 尤晉元，張來英，戚正偉，譯.北京：人民郵電出版社，2006.
[4] SARWAR S M, KORETSKY R, SARWAR S A著. Linux教程[M].李善平，施韋，林欣，譯.北京：清華大學(xué)出版社，2005.