本科生畢業(yè)設(shè)計文獻綜述

本科生畢業(yè)設(shè)計（論文）文獻綜述（2012屆）論文題目多類在線程序評判系統(tǒng)分析與實時測試學生姓名石兆斌學號0804011010專業(yè)計算機班級計081指導教師陳根方職稱副教授杭州國際服務(wù)工程學院（信息科學與工程學院）教學部制文獻綜述基本要求一、文獻綜述含本選題國內(nèi)外研究現(xiàn)狀、研究主要成果、發(fā)展趨勢、存在問題等內(nèi)容，字數(shù)不少于3000字，力求內(nèi)容切題，具綜合歸納性二、查閱中外文獻資料目錄所查閱的中外文獻資料不得少于10篇，含作者、書名或論文題目、出版社或刊名、出版年月或期號及頁碼等，未經(jīng)本人查閱的文獻資料目錄不得列上指導教師意見：該同學認真學習了廣泛使用的ACM/ICPC程序設(shè)計競賽及其的發(fā)展與在線評測系統(tǒng)測應(yīng)用，分析和總結(jié)了常用的在線評測系統(tǒng)的功能和特點，分析了它們的設(shè)計思路和方法，為以后的工作打下了良好的基礎(chǔ)。指導教師簽名：年月日

一、文獻綜述引言 在線評測系統(tǒng)（OnlineJudgeSystem，一般簡稱OJ），是一個為程序設(shè)計競賽愛好者和ACM/ICPC（國際大學生程序設(shè)計競賽）訓練隊伍提供訓練及交流的平臺，同時也可以為程序設(shè)計語言、數(shù)據(jù)結(jié)構(gòu)、算法等課程提供作業(yè)練習、實現(xiàn)及檢測的平臺，對每個由評測系統(tǒng)展示的題目接收用戶提交的源代碼，在編譯執(zhí)行后將用戶程序的輸出與系統(tǒng)的標準輸出進行比較，并給出用戶程序運行和比較的結(jié)果，從而判斷用戶提交的源代碼是否正確。目前國內(nèi)外已有類似網(wǎng)上評測系統(tǒng)，其中國外著名的網(wǎng)上評測系統(tǒng)有西班牙的UVAOnlineJudge、俄羅斯的TimusOnlineJudge，國內(nèi)著名的網(wǎng)上評測系統(tǒng)有PKUOnlineJudge（北京大學）和ZJUOnlineJudge（浙江大學）。 國內(nèi)計算機專業(yè)培養(yǎng)的學生理論功底一般會很好，但實踐能力總是略顯不足，從而無法在科研學術(shù)領(lǐng)域及工業(yè)界有較強的競爭能力。OnlineJudge正式設(shè)計用來改變這一現(xiàn)象，鞏固學生的數(shù)據(jù)結(jié)構(gòu)知識和算法設(shè)計能力。提高學生對計算機的認識。ACM/ICPC（國際大學生程序設(shè)計競賽）簡介 ACM國際大學生程序設(shè)計競賽（ACMInternationalCollegiateProgrammingContestorACM-ICPC）是由美國計算機協(xié)會（ACM）主辦的，一項旨在展示大學生創(chuàng)新能力、團隊精神和在壓力下編寫程序、分析和解決問題能力的年度競賽。經(jīng)過近30多年的發(fā)展，ACM國際大學生程序設(shè)計競賽已經(jīng)發(fā)展成為最具影響力的大學生計算機競賽。賽事目前由IBM公司贊助。 ACM-ICPC以團隊的形式代表各學校參賽，每隊由3名隊員組成。每位隊員必須是在校學生，有一定的年齡限制，并且最多可以參加2次全球總決賽和5次區(qū)域選拔賽。 比賽期間，每隊使用1臺電腦需要在5個小時內(nèi)使用C、C++或Java中的一種編寫程序解決7到10個問題。程序完成之后提交裁判運行，運行的結(jié)果會判定為正確或錯誤兩種并及時通知參賽隊。而且有趣的是每隊在正確完成一題后，組織者將在其位置上升起一只代表該題顏色的氣球。 最后的獲勝者為正確解答題目最多且總用時最少的隊伍。每道試題用時將從競賽開始到試題解答被判定為正確為止，其間每一次提交運行結(jié)果被判錯誤的話將被加罰20分鐘時間，未正確解答的試題不記時。例如：A、B兩隊都正確完成兩道題目，其中A隊提交這兩題的時間分別是比賽開始后1:00和2:45，B隊為1:20和2:00，但B隊有一題提交了2次。這樣A隊的總用時為1:00+2:45=3:45而B隊為1:20+2:00+0:20=3:40，所以B隊以總用時少而獲勝。 與其它計算機程序競賽（例如國際信息學奧林匹克，IOI）相比，ACM-ICPC的特點在于其題量大，每隊需要5小時內(nèi)完成8道題目，甚至更多。另外一支隊伍3名隊員卻只有1臺電腦，使得時間顯得更為緊張。因此除了扎實的編程能力，良好的團隊協(xié)作和心理素質(zhì)同樣是獲勝的關(guān)鍵。 賽事由各大洲區(qū)域預賽和全球總決賽兩個階段組成。各預賽區(qū)第一名自動獲得參加全球總決賽的資格。決賽安排在每年的3-4月舉行，而區(qū)域預賽一般安排在上一年的9-12月舉行。一個大學可以有多支隊伍參加區(qū)域預賽，但只能有一支隊伍參加全球總決賽。 全球總決賽第一名將獲得獎杯一座。另外，成績靠前的參賽隊伍也將獲得金、銀和銅牌。而解題數(shù)在中等以下的隊伍會得到確認但不會進行排名。 網(wǎng)址/icpc/ 除ACM-ICPC程序設(shè)計競賽外，還有Google?CodeJam、TopCoder、百度之星程序設(shè)計大賽、＂英特爾杯＂全國計算機多核程序設(shè)計大賽、ImagineCup微軟全球大賽、ICFP程序設(shè)計競賽等程序設(shè)計競賽，這些競賽都采取類似的評判機制，各有各的特點。源代碼評測簡介 程序設(shè)計競賽平臺采用源代碼評測技術(shù).源代碼評測一般分為手工評測、和自動評測，后者又可分為在線評測和離線評測兩種。 當手工評測只能離線完成時，自動評測能夠離線或者在線評測。在最后期限之前，一個離線自動評分機將獲取提交，否則什么都不做。當最后期限到達，它將開始檢查所有收到的提交，并且產(chǎn)生這些提交的判斷報告。相反，在最后期限前，在線自動評測會獲取提交并且立即產(chǎn)生判斷報告，允許學生決定他們是否希望對這個問題有其它的嘗試以獲得更好的分數(shù)。源代碼評測機制 通常情況下的實現(xiàn)方式是服務(wù)器后臺運行守候程序，每一個時間間隔查詢一次數(shù)據(jù)庫，如發(fā)現(xiàn)有提交紀錄，則啟動評判進程，進行相關(guān)題目的評判。每道題目均對應(yīng)的數(shù)據(jù)輸入輸出文件，開始時評判進程啟動一個子進程編譯運行用戶提交上來的程序，當程序啟動時計時，在時間允許范圍之內(nèi)，如果其得到了正確答案，則修改數(shù)據(jù)庫，令其status為Accepted；如果答案錯，令其status為WrongAnswer；如果運行異常等，則向該進程發(fā)出SIGKILL信號，強行中止該進程，把數(shù)據(jù)庫記錄進行相應(yīng)的修改。流程圖如下： 在另外一些系統(tǒng)上（如POJ，ZOJ）采用了事件驅(qū)動的方式，當有用戶提交源代碼到服務(wù)器上后，就啟動一個進程/線程去按照如上流程圖所示的方式進行測評。評測系統(tǒng)的實現(xiàn) 早期的一些測評系統(tǒng)幾乎都是在Linux平臺下實現(xiàn)的，如浙江大學的ZOJ，哈爾濱工業(yè)大學的HITOJ，武漢大學的WOJ等均是在Linux下使用C語言編程開發(fā)讀取系統(tǒng)表獲取進程資源占用信息，這類系統(tǒng)中大多數(shù)還需要使用Perl和SHELL編寫一些系統(tǒng)命令配合使用。 大多數(shù)采用這樣的架構(gòu)：Linux+MySQL+GCC+Apache+PHP 然而特別的是國內(nèi)著名的在線判題系統(tǒng)POJ（北京大學ACM在線判題系統(tǒng)）是在Windows下實現(xiàn)的，它的實現(xiàn)方式后端采用C++利用Win32API獲取進程資源占用信息。在前端用戶界面部分使用JSP實現(xiàn)。 類似的，近年開始紅火的HDOJ（杭州電子科技大學ACM在線判題系統(tǒng)）也是在Windows下利用Win32API實現(xiàn)，技術(shù)路線為：Windows2003+MySQL++GCC+Apache+PHP 一般情況下采用JAVA來實現(xiàn)也可以完成整個系統(tǒng)的開發(fā)，更便于平臺的移植，但是JAVA的讀取效率不佳是影響該系統(tǒng)運行的主要因素。類似的今年來頻繁出現(xiàn)的在.NET框架下的實現(xiàn)也遇到了類似的問題，但總的來說不管是JAVA還是.NET都簡化了類似系統(tǒng)的實現(xiàn)方法。 除了以上實現(xiàn)方式外，筆者還看到過使用Python實現(xiàn)的系統(tǒng)以及使用Qt實現(xiàn)的系統(tǒng)，總的來說無論在何種語言框架開發(fā)下實現(xiàn)類似系統(tǒng)的思路都是一樣的，但語言的選擇在能夠幫助程序員減輕編寫代碼的負擔方面占據(jù)著很大的比重。 相對于一些經(jīng)常更換平臺的系統(tǒng)來說，在線測評系統(tǒng)并不需要頻繁的更換平臺；相反的，它一般是長期駐留在同一個平臺上，相對于平臺的選擇來說后期系統(tǒng)維護成本才是考慮的重點。常見源代碼評測系統(tǒng)簡介PKUOnlineJudge PKUJudgeOnlinefreeversion是由北京大學開發(fā)的ACM判題系統(tǒng)公開版，它是北大系統(tǒng)的精簡版，主要是去除了對JAVA語言的支持和取消了一些WEB界面的功能。該版本是國內(nèi)最早公開發(fā)行的在線判題系統(tǒng)。目前一些高校和中學均選用北大系統(tǒng)作為程序設(shè)計訓練及考試解決方案平臺。 北大的這套平臺采用Win32API開發(fā)測評部分，JSP開發(fā)用戶界面，MySQL作為數(shù)據(jù)庫，Tomcat作為Web服務(wù)器。相對于其它的一些B/S架構(gòu)判題系統(tǒng)，北大的系統(tǒng)安裝部署是較簡潔的，沒有太多的復雜設(shè)置，更好的是它運行在Windows平臺下，很容易普及，缺點是不開放源代碼，定制性較弱。CelizJudgeSystem Celiz是一個開源評價系統(tǒng)。這個軟件用于奧林匹克信息學競賽（OI），也可以用于ACM-ICPC國際大學編程競賽。該平臺采用C,C++開發(fā)，運行于Linux之上。目前該系統(tǒng)已經(jīng)停止開發(fā)，最后一版發(fā)布日期為2004年7月30日。DOMjudge DOMjudge是一款專門用于競賽的自動判題系統(tǒng)。它同樣運行于Linux之上，采用PHP作為用戶界面開發(fā)語言，使用MySQL數(shù)據(jù)庫，支持用戶添加自己需要的支持語言。同時支持命令行提交方式，是一套較成熟的競賽系統(tǒng)。該系統(tǒng)目前仍在開發(fā)，最近版本為3.3.2，發(fā)布日期2012年1月25日。PC2 PC2是由美國加利福尼亞大學為國際大學生編程競賽開發(fā)研制的競賽控制系統(tǒng)。目前主要用于ACM/ICPC等國際編程競賽。PC2最新的版本是9.2，系統(tǒng)采用JAVA語言編寫，可以運行在任何支持JAVA的平臺(windows系列以及Solaris/Linux/FreeBSD等)，網(wǎng)絡(luò)模式為C/S，競賽語言可以選用絕大多數(shù)的編程語言。PC2系統(tǒng)提供編程競賽控制，閱卷，記分等功能。在使用PC2系統(tǒng)過程中我們發(fā)現(xiàn)它可以極大的提高在諸如競賽或者學校考試過程中教師的工作效率。由于PC2系統(tǒng)不依賴于硬件和軟件系統(tǒng)，使得PC2系統(tǒng)幾乎可以適用于任何的機器環(huán)境。C語言競賽作為可以實際發(fā)揮學生編程能力、擴展學生視野、提高學生上機動手能力的競賽正日益受到越來越多的人的重視。Cena評測系統(tǒng) Cena是一款國產(chǎn)開放源程序的信息學競賽評測系統(tǒng)，能滿足大多數(shù)的評測需求。它也采用C/S模式工作，通過局域網(wǎng)自動收取選手程序。它能夠自動選用對應(yīng)的編譯器來編譯選手程序，也能使用解釋器或直接評測可執(zhí)行文件。能準確測出選手程序的運行時間和內(nèi)存使用量，并可加入對運行時間和內(nèi)存使用的限制。自動比較選手程序的輸出和標準輸出的差異，并能將兩者出現(xiàn)差異的具體位置告訴評測者。支持使用自定義校驗器，可評測有多解的試題。可對評測結(jié)果進行統(tǒng)計分析?？蓪⒃u測結(jié)果以各種樣式打印或?qū)С?。評測系統(tǒng)發(fā)展趨勢 隨著參加ACM/ICPC的同學越來越多，隨著提交量的增加，原始的單服務(wù)器模式越來越不能承受多用戶同時訪問時的壓力，表現(xiàn)在Web的響應(yīng)速度無法跟上用戶的大面積訪問，以及判題服務(wù)的響應(yīng)時間慢于用戶提交新程序的時間，從而進入無法提供服務(wù)給新登錄用戶，且已登錄用戶的服務(wù)也會變得無法響應(yīng)的惡性循環(huán)。近兩年國內(nèi)ACM/ICPC舉行的亞洲區(qū)各賽點的網(wǎng)絡(luò)預選賽充分暴露了這一問題。特別是競賽的時候涌入的龐大數(shù)據(jù)量，單一的服務(wù)器測評已經(jīng)不能滿足要求。在線測評系統(tǒng)迫切需要提升自身處理能力，除了升級服務(wù)器硬件配置外，分布式處理，云計算都是未來的發(fā)展方向?？煞植际讲渴鸬脑诰€評測系統(tǒng)是一個運用B/S與C/S模式的綜合性可分布式部署應(yīng)用系統(tǒng)。本系統(tǒng)不僅支持傳統(tǒng)在線評測系統(tǒng)的動態(tài)Web（B/S模式）的訪問，同時支持使用客戶端（C/S模式）訪問?？煞植际讲渴鸬脑诰€評測系統(tǒng)分為Web服務(wù)模塊、用戶終端模塊、中心服務(wù)模塊、評測模塊、數(shù)據(jù)接口模塊等五個大的功能模塊。其中，Web服務(wù)模塊和用戶終端模塊提供和用戶的交互接口，中心服務(wù)模塊負責整個系統(tǒng)的處理邏輯和數(shù)據(jù)導向，評測模塊對用戶提交的源代碼進行評測，數(shù)據(jù)接口模塊負責所有數(shù)據(jù)的存儲與查詢。 下圖是該系統(tǒng)的分布式架構(gòu)模型： 在應(yīng)用分布式系統(tǒng)方面，目前國內(nèi)的武漢大學的WOJ和浙江大學的ZOJ均處于國內(nèi)前列，武漢大學的相關(guān)開發(fā)者完成了分布式在線評測系統(tǒng)的開發(fā)與測試工作，并取得了好的成績。更值得慶祝的是浙江大學的新在線評測系統(tǒng)已經(jīng)采用分布式部署，給國內(nèi)該系統(tǒng)研究者提供了不少可以借鑒的資料。 采用可分布式部署，將原始的單服務(wù)器模式轉(zhuǎn)換為由一個中心服務(wù)模塊作為系統(tǒng)核心組件，一個底層數(shù)據(jù)庫服務(wù)模塊提供數(shù)據(jù)支持，多個Web服務(wù)模塊和多個評測判題服務(wù)模塊組成的服務(wù)集群，本集群中的任何一個部件均可部署在不同的服務(wù)器上，且負載高峰期可以用普通PC臨時替代，由局域網(wǎng)或高速Internet負責連接，從而大大減輕單個服務(wù)器的壓力并提升整個集群的服務(wù)性能。

二、查閱中外文獻資料目錄[01]Kurnia，Andy；Lim，Andrew；Cheang，Brenda.OnlineJudge[J].ComputersandEducation，2001；36：299–315肖穎,劉禹.針對ACM/ICPC的在線評測系統(tǒng)[J].哈爾濱：哈爾濱工業(yè)大學，2003.鄧子睿,唐巧.北京師范大學ACM在線題庫[J].北京師范大學校，2007年9月5日：第3版王卓威，尹寶林.一個基于網(wǎng)絡(luò)的程序自動評測系統(tǒng)[J].北京航空航天大學學報，2004,30(6)：502-505LIUYu.InsideHITOnlineJudgeSystem[J].哈爾濱：哈爾濱工業(yè)大學，2005.BrendaCheang，AndyKurnia，AndrewLim，Wee-ChongOon.Onautomatedgradingofprogrammingassignmentsinanacademicinstitution[J].Computers&Education，2003；41：121–131SongwenXu，YamSanChee.AutomaticDiagnosisofStudentProgramsinProgrammingLearningEnvironments[J].ProceedingsoftheSixteenthInternationalJointConferenceonArtificialIntelligence，1999：1102–1107AdrianKosowski,Micha?Ma?afiejskiandTomaszNoiński.ApplicationofanOnlineJudge&ContesterSysteminAcademicTuition[J].AdvancesinWebBasedLearning–ICWL2007，2008；Volume4823：343-354DonColton,Lesl