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

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

3 評(píng)判原理
    對(duì)程序編譯與運(yùn)行過(guò)程中出現(xiàn)的錯(cuò)誤，系統(tǒng)會(huì)根據(jù)錯(cuò)誤的不同給出相應(yīng)的提示,例如是編譯錯(cuò)誤或者是運(yùn)行錯(cuò)誤。如果編譯和運(yùn)行都正確，系統(tǒng)將進(jìn)一步通過(guò)相應(yīng)的題目要求、對(duì)程序要求給出的輸入和程序輸出的結(jié)果，來(lái)判斷該程序是否正確。
    在進(jìn)行程序評(píng)判時(shí)，先啟動(dòng)服務(wù)器評(píng)測(cè)進(jìn)程，在偵聽(tīng)到有提交記錄時(shí),系統(tǒng)立即對(duì)提交記錄的相關(guān)題目進(jìn)行評(píng)判。每個(gè)問(wèn)題均對(duì)應(yīng)一組數(shù)據(jù)(輸入和輸出文件)，系統(tǒng)設(shè)計(jì)時(shí)采用Linux管道(pipe(int filedes[3])）來(lái)處理，評(píng)判進(jìn)程啟動(dòng)一個(gè)子進(jìn)程(fork())來(lái)編譯運(yùn)行用戶提交的程序，讀入該題目的輸入數(shù)據(jù)，評(píng)判程序每次從管道讀入一個(gè)字符與標(biāo)準(zhǔn)輸出數(shù)據(jù)比較，如果兩個(gè)文件完全一樣，則表示程序正確；如發(fā)現(xiàn)只是相差空格、Tab、回車，則給出該程序?yàn)檩敵龈袷藉e(cuò)誤信號(hào)(Presentation Error)；如果發(fā)現(xiàn)其他字符的不匹配，則立即中止該程序，則給出該程序?yàn)榻Y(jié)果錯(cuò)誤的信號(hào)Wrong Answer。從程序運(yùn)行時(shí)刻開(kāi)始計(jì)時(shí)，在時(shí)間允許范圍之內(nèi)，得到了正確答案，則此提交程序符合題目要求并通過(guò)系統(tǒng)時(shí)間和內(nèi)存的限制，給出接受的信號(hào)(Accepted)。反之，如果答案錯(cuò)、或者表達(dá)錯(cuò)、運(yùn)行錯(cuò)等，則向該進(jìn)程發(fā)出SIGKILL信號(hào)，強(qiáng)行中止該進(jìn)程，對(duì)數(shù)據(jù)庫(kù)記錄進(jìn)行相應(yīng)的修改。運(yùn)行流程如圖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í)行時(shí)間的總和。其結(jié)構(gòu)都為timeval結(jié)構(gòu)。
    ru_minflt成員指不需要I/O的頁(yè)缺失數(shù)。頁(yè)缺失發(fā)生在內(nèi)核需要得到一個(gè)內(nèi)存頁(yè)以供進(jìn)程訪問(wèn)。
    ru_majflt值指需要I/O的頁(yè)缺失數(shù)。頁(yè)缺失發(fā)生在內(nèi)核需要得到一個(gè)內(nèi)存頁(yè)以供進(jìn)程訪問(wèn)時(shí)。
    有時(shí)，一個(gè)進(jìn)程會(huì)被調(diào)出內(nèi)存，以提供空間給其他進(jìn)程使用。ru_nswap指的就是一個(gè)進(jìn)程被調(diào)出內(nèi)存的次數(shù)。
    通過(guò)該結(jié)構(gòu)體就可以統(tǒng)計(jì)出各用戶程序?qū)Y源的占用情況，通過(guò)調(diào)用函數(shù)int getrusage(int who, struct rusage *rusage)對(duì)用戶程序運(yùn)行時(shí)間和內(nèi)存占用情況進(jìn)行分析統(tǒng)計(jì)。
    統(tǒng)計(jì)程序運(yùn)行時(shí)間：
    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)計(jì)程序所占內(nèi)存的開(kāi)銷： 
    usedMemory = usage.ru_minflt*4
    通過(guò)統(tǒng)計(jì)該兩項(xiàng)，能計(jì)算出程序運(yùn)行時(shí)間和內(nèi)存使用情況的數(shù)據(jù)，為結(jié)果排序做準(zhǔn)備。
5 系統(tǒng)安全處理
    用戶提交的程序在服務(wù)器上運(yùn)行，為了保證系統(tǒng)安全運(yùn)行、減少或杜絕故障的發(fā)生，在解決安全故障方面主要有以下幾個(gè)方面。
    （1） 文件操作
　　為了讓用戶提交上來(lái)的程序不破壞本機(jī)的文件系統(tǒng)，本設(shè)計(jì)采用了管道技術(shù)，在執(zhí)行用戶程序之前，先把輸入流定向到標(biāo)準(zhǔn)輸入文件，然后使用chroot命令改變用戶程序的執(zhí)行目錄，讓其只能在一個(gè)臨時(shí)文件夾下面做操作。
    （2） 網(wǎng)絡(luò)操作
　　為了不讓用戶程序影響評(píng)判系統(tǒng)的設(shè)置，保證評(píng)判系統(tǒng)的公正性，必須禁止用戶對(duì)網(wǎng)絡(luò)的訪問(wèn)。系統(tǒng)通過(guò)對(duì)用戶實(shí)行權(quán)限限制機(jī)制，判斷系統(tǒng)在用戶程序運(yùn)行之前，通過(guò)調(diào)用Linux系統(tǒng)中setuid(99) 和 setgid(99)兩個(gè)函數(shù)[4]，讓用戶程序的擁有者權(quán)限降到最低，達(dá)到防止用戶對(duì)網(wǎng)絡(luò)使用的目的。
    （3） 資源管理
    資源管理的作用是對(duì)客戶進(jìn)程所使用的資源進(jìn)行管理，Linux系統(tǒng)提供的資源限制函數(shù)setrlimit(),可以避免用戶進(jìn)程在運(yùn)行的過(guò)程中過(guò)多地占用系統(tǒng)資源，以影響服務(wù)器系統(tǒng)的穩(wěn)定性,最終有可能導(dǎo)致系統(tǒng)的崩潰。
    為了防止用戶進(jìn)程占用過(guò)多的資源，影響服務(wù)器系統(tǒng)的穩(wěn)定，對(duì)用戶進(jìn)程在占用資源方面進(jìn)行限制，主要考慮程序運(yùn)行時(shí)間和內(nèi)存占用兩個(gè)方面，在程序運(yùn)行之前，通過(guò)調(diào)用系統(tǒng)函數(shù)setrlimit()來(lái)限制程序?qū)ο到y(tǒng)資源的占用。函數(shù)setrlimit( RLIMIT_AS,&memlim)和setrlimit( RLIMIT_CPU,&timlim)分別用來(lái)限制用戶程序?qū)PU和內(nèi)存的占用情況，如果某用戶的程序超過(guò)了系統(tǒng)對(duì)CPU和內(nèi)存的最大設(shè)置值，該進(jìn)程就會(huì)被自動(dòng)中止，標(biāo)志用戶的程序不滿足比賽要求。
    通過(guò)對(duì)基于ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽在線評(píng)測(cè)系統(tǒng)的分析研究，設(shè)計(jì)了相應(yīng)的ACM測(cè)試軟件，習(xí)題的測(cè)試難度可由指導(dǎo)老師自己設(shè)計(jì)。該軟件也可以作為計(jì)算機(jī)專業(yè)學(xué)生算法測(cè)試工具，通過(guò)對(duì)該測(cè)試系統(tǒng)的使用，經(jīng)過(guò)一定題量的練習(xí)，可以增強(qiáng)學(xué)生在算法方面設(shè)計(jì)的技能，為學(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)境高級(jí)編程（第2 版）[M] . 尤晉元，張來(lái)英，戚正偉，譯.北京：人民郵電出版社，2006.
[4] SARWAR S M, KORETSKY R, SARWAR S A著. Linux教程[M].李善平，施韋，林欣，譯.北京：清華大學(xué)出版社，2005.