引言

    ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽標(biāo)志ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽（英文全稱：ACM International Collegiate Programming Contest（ACM-ICPC或ICPC）是由美國(guó)計(jì)算機(jī)協(xié)會(huì)（ACM）主辦的，一項(xiàng)旨在展示大學(xué)生創(chuàng)新能力、團(tuán)隊(duì)精神和在壓力下編寫(xiě)程序、分析和解決問(wèn)題能力的年度競(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ǔ)言所編寫(xiě)的程序進(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ù)程序性能信息表來(lái)判斷各個(gè)用戶的得分情況。

　　系統(tǒng)運(yùn)行于Linux操作系統(tǒng)，借助Linux操作系統(tǒng)所提供的多任務(wù)、多線程功能及其穩(wěn)定的性能和開(kāi)源的內(nèi)核，從而大大減少程序員書(shū)寫(xiě)系統(tǒng)代碼的工作量，也提高了系統(tǒng)的運(yùn)行效率。代碼是用C語(yǔ)言編寫(xiě)的，通過(guò)自己編寫(xiě)函數(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管道來(lái)處理，評(píng)判進(jìn)程啟動(dòng)一個(gè)子進(jìn)程來(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)；如果發(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)。反之，如果答案錯(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;             

　　struct timeval ru_stime;           

　　long ru_minflt;                           

　　long ru_majflt;                           

　　};

　　ru_utime和ru_stime成員變量包含了在用戶模式和系統(tǒng)模式中執(zhí)行時(shí)間的總和。其結(jié)構(gòu)都為timeval結(jié)構(gòu)。

　　ru_minflt成員指不需要I/O的頁(yè)缺失數(shù)。

　　ru_majflt值指需要I/O的頁(yè)缺失數(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ù)，讓用戶程序的擁有者權(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)志用戶的程序不滿足比賽要求。

    總結(jié)

　　通過(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ī)學(xué)生算法測(cè)試工具，通過(guò)對(duì)該測(cè)試系統(tǒng)的使用，經(jīng)過(guò)一定題量的練習(xí)，可以增強(qiáng)學(xué)生在算法方面設(shè)計(jì)的技能，為學(xué)生奠定雄厚的編程基礎(chǔ)。相信該軟件可以在學(xué)校的學(xué)生機(jī)中廣泛應(yīng)用。