趙 健

?

基于Windows內核的在線評測系統(tǒng)的設計與實現(xiàn)

趙 健

（長治學院，山西 長治 046011）

在線評測系統(tǒng)是一種廣泛應用在教學和編程比賽中的在線系統(tǒng)。該系統(tǒng)可以接受用戶在線提交的源代碼并在線編譯、運行，利用事先提供好的測試數(shù)據進行正確性判定。針對教學過程中的實際需要，本文提出了一種基于Windows內核的在線評測系統(tǒng)的設計方案，其中，Web前臺使用了SSM框架（Spring+SpringMVC+MyBatis），判題內核用C語言開發(fā)。為了保證系統(tǒng)多任務和安全性，判題內核使用了沙箱技術并設計了判題隊列。經測試，該系統(tǒng)能夠滿足一般的教學和編程比賽需要。

OJ系統(tǒng)；SSM；Windows API編程；沙箱

0 引言

在線評測系統(tǒng)（Online Judge，縮寫OJ）是一種廣泛應用在教學和編程比賽中的在線系統(tǒng)。該系統(tǒng)可以接受用戶在線提交的源代碼并在線編譯、運行，利用事先提供好的測試數(shù)據進行正確性判定[1]。用戶提交的源碼可以是各種語言寫就的，如C/C++，Java，Python等。

最早的在線評測系統(tǒng)是西班牙的巴亞多利德大學1995年開發(fā)的（UVAOJ）。目前比較流行的OJ有西班牙的UVAOJ、俄羅斯的SGU、Timus、波蘭的SPOJ、美國的TopCoder等。我國也有一些出色的OJ系統(tǒng)，如北京大學的POJ、浙江大學的ZOJ、杭州電子科技大學的HDOJ等[2]。

OJ可以應用在在線作業(yè)練習和算法類編程競賽的訓練上，能夠極大地提高編程語言類教學科目的教學管理效率[3]。筆者在教學過程中深感OJ系統(tǒng)的必要性，但目前筆者所在的學校還沒有成熟的OJ系統(tǒng)。目前流行的OJ系統(tǒng)大多使用Linux平臺，鑒于Windows 平臺在管理上較為方便的特點，以及考慮到目前學生大量的編程實踐都運行在Windows平臺，開發(fā)一個基于Windows內核的在線評測系統(tǒng)勢在必行。

本文基于Windows內核提供了一個可行的OJ系統(tǒng)解決方案，實現(xiàn)了一個B/S模式的在線評測系統(tǒng)。經測試，該系統(tǒng)可以在Windows環(huán)境下安全穩(wěn)定地運行，滿足日常的教學和編程練習需要。

1 總體設計

本系統(tǒng)搭建在Windows平臺上，Windows Server 2008系統(tǒng)及以上，Web服務器使用Apache Tomcat6及以上，數(shù)據庫使用MySQL5.1以上，Java JDK5.1以上。

本系統(tǒng)最核心的是兩部分：1Web端與數(shù)據庫服務（前臺）、2判題核心（后臺服務）。其數(shù)據庫中除存儲一般網站中的信息如用戶表、權限表之外，最重要的是存儲了題目相關信息：題目信息表存儲編程題目的基本信息如題目id、輸入/輸出描述等，代碼表存儲了用戶提交的源代碼。將題目信息和源代碼分離存儲是為了減輕通信負擔。此外，判題結果狀態(tài)也存儲在數(shù)據庫中。

前臺的開發(fā)為用戶提供了系統(tǒng)界面，此部分當下流行的開發(fā)框架均可勝任，如PHP、Python的Django框架、Java中SpringMVC等。前臺可以與數(shù)據庫服務通信以提交代碼到數(shù)據庫中，也可從數(shù)據庫中提取判題結果并將之顯示到系統(tǒng)界面上。

判題核心是OJ系統(tǒng)最關鍵的部分。它主要根據代碼ID從數(shù)據庫中取出具體代碼并對之進行后續(xù)處理，包括編譯、運行、判時（判斷運行時間）、比對（與測試數(shù)據比對）等步驟。此外，判題核心也負責將運行的狀態(tài)結果存到數(shù)據庫中，以便前臺進行評測結果顯示。系統(tǒng)整體結構如圖1所示。

圖1 系統(tǒng)整體結構圖

2 關鍵技術

2.1 Web前臺

Web端主要負責系統(tǒng)界面的展示以及與內核的通信，其中界面簡單實用即可，因此本系統(tǒng)使用了目前最流行的SSM框架（Spring+SpringMVC+My-Batis）[4]，以便進行快速開發(fā)。

2.2 判題內核

判題內核是OJ系統(tǒng)最關鍵的部分，在系統(tǒng)的整個運行期間都由其為系統(tǒng)提供題目的評測服務，它設計的好壞直接影響了系統(tǒng)的速度、安全性和穩(wěn)定性。該部分使用C語言開發(fā)，內核通過Socket技術與Web端通信[5]。

本系統(tǒng)的判題內核大量使用了WinAPI編程技術。最主要的是以下兩個線程：

（1）監(jiān)聽線程：該線程負責監(jiān)聽Web端提交的代碼。當接受到代碼ID后，會將代碼ID壓入隊列。

（2）調度處理線程：判斷監(jiān)聽線程產生的隊列是否為空，當隊列非空時取出隊列中的代碼ID，進行處理（編譯運行判時比對）。

圖2為內核的線程交互圖。

3 關鍵技術實現(xiàn)

3.1 Web前臺

在Web端本OJ系統(tǒng)與其他普通網站相比并沒有太多特殊之處，主要是為用戶提供交互界面，界面簡潔，滿足功能即可。所以我們系統(tǒng)的Web端采用了SSM（Spring+SpringMVC+Mybatis）開發(fā)框架。SSM框架使用了MVC架構，技術成熟，配置方便，相關插件和開發(fā)工具完備，運行穩(wěn)定。其中，Web前端使用了Jquery 和 Ajax技術。對于代碼的編輯界面，有一些開源的插件如Syntaxhighlight、CKEditor等[6]。為了增強交互性，前端還可以使用HTML批注技術[7-8]。

圖2 內核線程交互圖

本系統(tǒng)的Web端實現(xiàn)了練習模塊、競賽模塊、通信模塊、搜索模塊等主要模塊。

3.2 判題內核

3.2.1 監(jiān)聽線程

該線程主要負責與接受web端提交過來的題目ID。這里引入了判題隊列，web端提交的ID會按照監(jiān)聽線程接受的順序依次壓倒隊列中，調度處理線程則從該隊列中取題目ID以便后續(xù)處理。socket監(jiān)聽和判題隊列的引入使得系統(tǒng)可以處理多任務，即web端多個用戶同時提交代碼不會導致判題失敗[9]。

該線程的偽代碼如下：

unsigned _stdcall listenThread(*LPVOID lpPara-meter)

{

init();//做一些初始化工作如初始化socket，建立緩沖區(qū)等

while(True)

{

accept(); //接受socket建好的連接

recvData();//從socket接受數(shù)據，主要接受problem_id即題目ID

push();//將題目id壓入隊列，即圖中的隊列

sleep(1);

}

closesocket();

return 0;

}

3.2.2 調度處理線程

本線程實現(xiàn)了判題內核的最核心內容：首先判斷判題隊列是否為空，若非空則取出隊列頭存儲的題目ID，根據此ID從數(shù)據庫中得到用戶提交的源代碼，然后就可以執(zhí)行編譯和運行過程。在此過程中，調度處理內核可以得到用戶的運行時間、編譯錯誤信息和運行時錯誤信息（RE）。若進程通過了編譯運行，再根據實現(xiàn)準備好的若干組測試數(shù)據和運行結果進行比對，全部匹配成功則認為用戶提交的代碼正確。

該進程的偽代碼如下：

void DispatchProcessingThread()

{

pop(ID);//從判題隊列中取出題目ID

SQL_getSource(ID);//根據題目ID從數(shù)據庫中獲得源代碼

if(False == CompileProc()) //編譯

{

錯誤處理;

SQL_UpdateCompileInfo(); //將編譯信息插入到數(shù)據庫中

}

BeginThreadex(RunProcess);//新開一個線程以執(zhí)行編譯好的程序

}

void RunProcess()

{

CreatePipe(); //創(chuàng)建匿名管道

handle hSandBox = CreateSandBox();//創(chuàng)建沙箱

handle hProcess = CreateProcess();//創(chuàng)建進程，該進程的主線程以暫停的狀態(tài)被創(chuàng)建

if(True == AssignProcessToSandBox(hPro-cess, hSandBox))//將進程放進沙箱中

{

ResumeThread(); //恢復暫停態(tài)的進程繼續(xù)執(zhí)行

計時開始;

PipeInputRead();//

PipeOutputWriteToFile();

計時結束;

GetProcessMemoryInfo();//獲得進程所占用的內存狀態(tài)

GetExitCodeProcess(); //獲取進程退出碼，得到運行時錯誤信息

MatchResult();//用事先提供好的測試數(shù)據做匹配，所有數(shù)據都匹配才認為判題成功

}

}

上面?zhèn)未a中所描述的調度處理線程需要完成的核心子功能有：

（1）編譯

考慮到編譯環(huán)境的不確定性，如果將編譯命令直接寫到內核代碼中，會極大地降低系統(tǒng)穩(wěn)定性，提高系統(tǒng)維護成本[10]。另外，不同類型語言的編譯命令和參數(shù)都不一樣，在代碼級別也很難對之精確描述。于此同時，也不利于系統(tǒng)的可擴展性（如動態(tài)添加/刪除編譯語言等）。為此，本系統(tǒng)將運行環(huán)境和編譯的命令預先存在配置文件Config.ini中，有效解決了這一問題。該文件對在線處理用戶提交代碼的環(huán)境做了一些配置，如支持的語言、編譯命令和路徑、編譯后可執(zhí)行文件的格式、運行命令等。需要使用這些信息時，可以由內核通過調用Windows API對Config.ini文件進行操作：

GetPrivateProfileInt函數(shù)：讀取配置文件中的數(shù)字。

GetPrivateProfileString函數(shù)：讀取配置文件中的字符串。

WritePrivateProfileString函數(shù)：將配置信息寫入配置文件中。

本系統(tǒng)支持C/C++，Java，Python等主流編程語言，配置文件中相關的配置命令如下（見表1）：

表1 部分語言的編譯命令行表

Tab.1 Compiling command line table of partical language

（2）運行

在程序的運行環(huán)節(jié)，除了完成調用相關命令運行程序外，還應考慮運行的安全性問題。在運行程序時，可能有多種操作危及到系統(tǒng)的安全，輕則導致判題內核無法正常運作，重則危及整個系統(tǒng)的安全。比如當用戶提交攜帶有死循環(huán)的代碼時，會導致執(zhí)行進程無休止地占用內核資源；又如用戶提交的代碼可能含有一些危險操作如系統(tǒng)重啟、刪除系統(tǒng)文件等[11]。對這些危險操作事先加以限制也是判題內核的核心工作。為此我們引入了判時模塊和沙箱[12]。判時模塊可以計算程序運行所消耗的時間以及內存占用情況，以便當程序運行異常時加以干預。沙箱則可以讓一個進程獨立運行，并限制其可以做什么，不可以做什么。

（3）判時模塊

系統(tǒng)每運行一個用戶提交的用例都會計算其運行時間：使用clock()函數(shù)，用程序結束運行的時間減去開始運行的時間即為本次測試用例的耗時。

系統(tǒng)還可以統(tǒng)計測試用例的內存占用情況：通過WindowsAPI中的GetProcessMemoryInfo函數(shù)即可獲取內存的使用情況。

（4）沙箱

系統(tǒng)使用了沙箱，每個用戶提交的代碼經編譯后，要放到沙箱中運行，一般地，OJ的一個沙箱中只能運行一個進程，沙箱能夠對進程的運行時間、消耗內存、訪問文件權限等做限制，進而保證程序運行時的安全性。

我們這里的沙箱使用了Windows的作業(yè)內核對象生成，用到的主要API有[13]：

CreateJobObject函數(shù)：創(chuàng)建工作對象。

SetInformationJobObject函數(shù)：可以對工作對象中的進程加以限制，通過設置其參數(shù)，可以對進程數(shù)、進程數(shù)量、進程耗時限額以及消耗內存限額、UI和安全等加以限制。

CreateProcess函數(shù)啟動進程，本系統(tǒng)的進程都是以CREATE_SUSPENDED方式啟動。

AssignProcessToJobObject函數(shù)：將進程放到工作對象中。

ResumeThread函數(shù)恢復CreateProcess中暫停的進程。

QueryInformationJobObject函數(shù)獲取工作對象的最終狀態(tài)。

運行時錯誤是程序在運行過程中因堆棧溢出、數(shù)組越界等原因造成的程序異常中斷或崩潰。Windows API函數(shù)GetExitCodeProcess即可獲取退出碼。

TerminateJobObject函數(shù)結束當前的工作對象。

本系統(tǒng)能得到常見的運行時錯誤如堆棧溢出、除零錯誤、運行超時、內存超限、輸出超限等。

（5）內核與文件的I/O

用戶提交的代碼運行時默認從標準輸入讀入數(shù)據并將結果輸出到標準輸出，但OJ的比對環(huán)節(jié)需要讀取預先設計好的測試數(shù)據集并與運行結果進行匹配，這里讀取測試數(shù)據使用了匿名管道技術。

計算機的管道可以實現(xiàn)數(shù)據流的重定向，管道技術分為命名管道和匿名管道。我們這里使用匿名管道技術，運行測試代碼時，主進程會創(chuàng)建數(shù)據輸入管道和數(shù)據輸出管道，用來代替程序的標準輸入輸出，數(shù)據輸入管道可以從文件中獲取數(shù)據，數(shù)據輸出管道可以將結果數(shù)據輸出到文件中。

常用的函數(shù)有：CreatePipe函數(shù)創(chuàng)建管道，ReadFile和WriteFile函數(shù)分別實現(xiàn)了從管道中讀取數(shù)據和向管道寫入數(shù)據，CloseHandle函數(shù)關閉管道。

4 驗證評估

4.1 源代碼語法正確的測試

提交語法正確的源代碼，在“提交狀態(tài)”頁面中，狀態(tài)字段顯示為“Accepted”。

4.2 源代碼語法錯誤的測試

提交語法錯誤的源代碼，在“提交狀態(tài)”頁面中，狀態(tài)字段顯示為“Compilation Error”。

4.3 答案匹配測試

提交答案匹配正確的源代碼，在“提交狀態(tài)”頁面中，狀態(tài)字段顯示為“Accepted”。

提交答案錯誤的源代碼，在“提交狀態(tài)”頁面中，狀態(tài)字段顯示為‘Wrong Answer on test 1’。

圖3 源代碼語法正確結果圖

圖4 源代碼語法正確結果圖

圖5 答案匹配正確結果圖

圖6 答案匹配錯誤結果圖

5 結論

本系統(tǒng)在筆者所在班級進行了數(shù)次測試運行，期間運行穩(wěn)定。經測試，該系統(tǒng)能夠滿足日常的教學及學生練習需要，其中競賽模塊曾承擔64位同學同時在線提交代碼，網站無異常，能夠正確穩(wěn)定地進行判題服務。

[1] Andy Kurnina, Andrew Lim, Bernda Cheang. Online Judge[J]. Computers Education, 2001, 4(36): 2-3.

[2] 晏燕. 在線編程評測系統(tǒng)設計與實現(xiàn)[D]. 吉林大學, 2017: 3-4.

[3] 苗桂君, 劉勇, 許南山, 等. 在線評測系統(tǒng)在程序設計類教學中的應用研究[J]. 計算機教育, 2016(09): 157-162.

[4] 李洋. SSM框架在Web應用開發(fā)中的設計與實現(xiàn)[J]. 計算機技術與發(fā)展, 2016, 26(12): 190-194.

[5] 譚文, 陳銘霖. Windows內核安全與驅動開發(fā)[M]. 北京: 電子工業(yè)出版社; 2015: 81-85

[6] 張睿, 文福安. 基于web的試題編輯技術的研究與實現(xiàn)[J]. 軟件, 2015, 36(9): 21-24.

[7] 梁瑞仕, 魏錚淑, 陳光琳. 高校在線教學與評測平臺的設計與實現(xiàn)[J]. 中國教育信息化, 2017(11): 83-85.

[8] 黃曉華, 沈健, 常晉義, 等. 基于Online Judge與HTML批注技術的實驗教學平臺設計[J]. 計算機與現(xiàn)代化, 2014(11): 117-121.

[9] 黃洪波, 宋鴻陟, 彭紅星, 等. 大規(guī)模程序評判系統(tǒng)的設計與實現(xiàn)[J]. 計算機工程與設計, 2016, 37(03): 825-831.

[10] 刁銘智, 周淵李, 舟軍, 等. 基于Wine的Windows安全機制模擬及沙箱系統(tǒng)實現(xiàn)[J]. 計算機科學, 2017, 44(11): 246-252+267.

[11] 肖紅玉, 賀輝, 陳紅順. 在線評測教學輔助系統(tǒng)設計[J]. 計算機技術與發(fā)展, 2017, 27(11): 141-145.

[12] 李定才, 瞿紹軍, 胡爭, 等. 基于Windows的在線判題系統(tǒng)的安全性研究[J]. 計算機技術與發(fā)展, 2011, 21(09): 204-207.

[13] 王險峰, 劉寶宏. Windows環(huán)境下的多線程編程原理與應用[M]. 北京: 清華大學出版社; 2002: 52-84.

Design and Implementation of Online Evaluation System Based on Windows Kernel

ZHAO Jian

(Changzhi College, Changzhi, Shanxi 046011)

Online evaluation system is an system widely applied in teaching and programming competitions, which can accept, compile and run source code submitted by users online, and determine correctness based on test data provided in advance. In view of practical needs of teaching process, the article proposes an online evaluation system design scheme based on Windows kernel, with SSM framework (Spring+SpringMVC+MyBatis) of Web frontend, and C language development of marking kernel. To ensure multitask and security of system, sandbox technology and queue was designed for marking kernel. After testing, the system can meet needs of general teaching and programming competitions.

OJ system; SSM; Windows API programming; Sandbox

TP313

A

10.3969/j.issn.1003-6970.2018.09.039

趙健(1986-)，男，碩士，助教，主要研究方向：軟件工程及數(shù)據分析，基于SSM的J2EE應用系統(tǒng)自主開發(fā)。

本文著錄格式：趙健. 基于Windows內核的在線評測系統(tǒng)的設計與實現(xiàn)[J]. 軟件，2018，39（9）：194-199