劉振超 孫娜 黃建昌

摘 要：目前計(jì)算機(jī)編程課程考試都是基于OJ系統(tǒng)的，評(píng)價(jià)一個(gè)OJ系統(tǒng)性能的標(biāo)準(zhǔn)，主要看它的判題效率及準(zhǔn)確性。本文在對(duì)判題端的設(shè)計(jì)中，使用python來(lái)編寫判題邏輯，通過(guò)增加判題節(jié)點(diǎn)來(lái)提高判題效率，并將預(yù)先設(shè)計(jì)好的測(cè)試數(shù)據(jù)存儲(chǔ)到利用PostgreSQL和Redis構(gòu)建的后臺(tái)數(shù)據(jù)庫(kù)中，用于測(cè)試用戶程序的正確性。

關(guān)鍵詞：OJ系統(tǒng)；判題邏輯；Python；PostgreSQL

隨著教育信息化的發(fā)展，OJ系統(tǒng)通常被用作練習(xí)編程和考試的平臺(tái)。它的出現(xiàn)增加了學(xué)習(xí)的靈活性，提高了學(xué)生的學(xué)習(xí)效率，減輕了教師的工作負(fù)擔(dān)。評(píng)價(jià)一個(gè)OJ系統(tǒng)性能的好壞，最關(guān)鍵的性能指標(biāo)就是判題效率及準(zhǔn)確性，所以在OJ系統(tǒng)的開(kāi)發(fā)過(guò)程中，判題端的設(shè)計(jì)和開(kāi)發(fā)顯得尤為重要。在判題端的設(shè)計(jì)部分，本文基于python來(lái)編寫判題邏輯，并對(duì)用戶程序的運(yùn)行時(shí)間、占用內(nèi)存進(jìn)行了限制。還將預(yù)先設(shè)計(jì)好的測(cè)試數(shù)據(jù)存儲(chǔ)到了利用PostgreSQL和Redis提前構(gòu)建好的后臺(tái)數(shù)據(jù)庫(kù)中，用于測(cè)試用戶程序的正確性，并通過(guò)增加判題節(jié)點(diǎn)的方法提高了判題效率。

一、 概述

OJ系統(tǒng)是通過(guò)對(duì)代碼進(jìn)行編譯執(zhí)行，使用預(yù)設(shè)數(shù)據(jù)進(jìn)行測(cè)試，從而分析出用戶所提交代碼正確性的系統(tǒng)。它整體可以分為兩部分——web部分和judge部分。其中，judge就是判題機(jī)，它的核心被稱為judge-server，也就是判題邏輯。當(dāng)用戶提交了源代碼后，判題程序會(huì)對(duì)該源代碼進(jìn)行編譯、運(yùn)行。用戶程序執(zhí)行的結(jié)果會(huì)被捕捉并保存，然后轉(zhuǎn)交給一個(gè)裁判程序。該裁判程序會(huì)調(diào)用題目對(duì)應(yīng)文件夾內(nèi)的輸入輸出數(shù)據(jù)與用戶程序的輸出數(shù)據(jù)進(jìn)行比較，然后由系統(tǒng)返回給用戶一個(gè)狀態(tài)和程序占用內(nèi)存、運(yùn)行時(shí)間等信息。

二、 判題邏輯

本文使用python對(duì)判題邏輯進(jìn)行了編寫，它就是一個(gè)能夠去編譯和運(yùn)行用戶提交上來(lái)的源代碼的程序。它將啟動(dòng)兩個(gè)進(jìn)程來(lái)實(shí)現(xiàn)判題功能。其中judged是服務(wù)進(jìn)程，負(fù)責(zé)輪詢solution表（存放在后臺(tái)數(shù)據(jù)庫(kù)中），然后獲取判題隊(duì)列；judge_client進(jìn)程負(fù)責(zé)準(zhǔn)備運(yùn)行環(huán)境、判斷運(yùn)行結(jié)果、監(jiān)測(cè)時(shí)間和空間受限。

每個(gè)題目會(huì)生成一個(gè)相應(yīng)的文件夾，文件夾中存放著測(cè)試數(shù)據(jù)。其中.in文件保存的是測(cè)試用的輸入數(shù)據(jù)，比如1 1這樣的測(cè)試數(shù)據(jù)。.out文件是輸出數(shù)據(jù)，比如2，對(duì)應(yīng)的程序就是1+1=2。

此外，判題程序還需要對(duì)用戶程序的運(yùn)行時(shí)間、占用內(nèi)存進(jìn)行限制。

（一） 時(shí)間限制

當(dāng)setitimer定時(shí)器計(jì)時(shí)結(jié)束時(shí)，系統(tǒng)就會(huì)給進(jìn)程發(fā)送一個(gè)信號(hào)。進(jìn)程實(shí)際運(yùn)行時(shí)間計(jì)數(shù)器（ITIMER_REAL）計(jì)時(shí)結(jié)束時(shí)會(huì)發(fā)送SIGALRM信號(hào)，進(jìn)程CPU時(shí)間計(jì)數(shù)器（ITIMER_VIRTUAL）計(jì)時(shí)結(jié)束時(shí)會(huì)發(fā)送SIGVTALRM信號(hào)。I我們?cè)O(shè)置好定時(shí)器之后，如果捕獲到了對(duì)應(yīng)的信號(hào)，說(shuō)明當(dāng)前進(jìn)程運(yùn)行超時(shí)。

（二） 占用內(nèi)存限制

開(kāi)發(fā)OJ的在線判題功能，需要一個(gè)子進(jìn)程在沙箱中進(jìn)行代碼的編譯、運(yùn)行并計(jì)算使用的cpu資源和內(nèi)存資源，對(duì)于子進(jìn)程的資源管理，在Linux系統(tǒng)下，我們選擇使用RLimit。

其中有兩個(gè)重要的函數(shù)：

int getrlimit（int resource， struct rlimit *rlptr）；

int setrlimit（int resource， const struct rlimit *rlptr）；

getrlimit（ ）用于獲取當(dāng)前進(jìn)程的RLimit，；setrlimit（ ）則用于設(shè)置當(dāng)前進(jìn)程的RLimit。傳入不同的resource值，便是對(duì)當(dāng)前進(jìn)程的不同運(yùn)行資源設(shè)定限制。resource值中的RLIMIT_AS用來(lái)限制進(jìn)程的最大內(nèi)存地址空間，如果超過(guò)這個(gè)地址空間，內(nèi)存將不能分配成功。

三、 判題節(jié)點(diǎn)

判題部分是整個(gè)OJ系統(tǒng)的核心所在，所以提高判題端的工作效率對(duì)于提高整個(gè)系統(tǒng)的性能而言是至關(guān)重要的。對(duì)于提高judge的判題效率，采取了增加判題節(jié)點(diǎn)的方法，具體思路是：通過(guò)Web端發(fā)送判題的請(qǐng)求給RabbitMQ消息隊(duì)列，每當(dāng)有一個(gè)新任務(wù)，就啟用一個(gè)judge_client進(jìn)程，每個(gè)判題請(qǐng)求擁有一個(gè)自己的ID（即一個(gè)判題節(jié)點(diǎn)），每個(gè)ID對(duì)應(yīng)著一個(gè)judge_client進(jìn)程，這樣就可以使多組測(cè)試數(shù)據(jù)同時(shí)去檢測(cè)，從而加快判題速度。如圖1所示是判題過(guò)程。

圖1 判題過(guò)程示意圖

四、 結(jié)語(yǔ)

本系統(tǒng)的判題端目前可以用來(lái)檢測(cè)C，C++，JAVA代碼的正確性，以及代碼運(yùn)行的時(shí)間和占用的內(nèi)存是否超出限制。今后，我們準(zhǔn)備在“如何支持更多類型題目的提交”“如何在提交記錄里顯示分?jǐn)?shù)”“怎樣增加交互式判題功能”三方面進(jìn)一步完善該系統(tǒng)。

（通訊作者：劉宇）

參考文獻(xiàn)：

[1]李偉光，陳希.GOJ系統(tǒng)的研究與實(shí)現(xiàn)[N].科技創(chuàng)新導(dǎo)報(bào).

[2]馮潞潞.基于偶然性正確測(cè)試用例發(fā)現(xiàn)的軟件錯(cuò)誤定位方法[D].杭州：浙江理工大學(xué)，2014.

[3]翟偉翔.WorldFIP現(xiàn)場(chǎng)總線分布式控制系統(tǒng)的研究與開(kāi)發(fā)[D].北京：華北電力大學(xué)，2008.

[4]趙濤.面向SDN的軟件定義硬件計(jì)數(shù)器研究[D].長(zhǎng)沙：國(guó)防科學(xué)技術(shù)大學(xué)，2014.

作者簡(jiǎn)介：

劉振超，孫娜，黃建昌，河北省黃驥市，河北農(nóng)業(yè)大學(xué)理工學(xué)院。