源問題地址：http://www.cnblogs.com/xinz/archive/2011/03/20/1989662.html
問題背景
在一座高樓中，我們需要設計一個電梯系統。這個電梯系統中的電梯數量以及電梯的各種參數都是可配置的，同時，電梯的運行也會存在一些限制：比如有些電梯只能從1層運行到10層，不能到更高的20層。已知了電梯的配置后，我們就可以讓這個多電梯系統按照我們設計的調度算法去運行，這個調度算法要盡可能高效地運送乘客們，并且調度必須考慮電梯的限制條件。例如，當一輛電梯就要超載的時候，在梯內乘客走出前，調度器不可再安排乘客進入。
電梯系統是需要學生好好構思設計一番的，但實際情況中，電梯系統的測試同樣是個需要好好思考的問題。本文所要解決的主要問題就是怎樣為電梯項目構建一個自動化測試系統，所以本文的讀者主要是需要測試學生項目的助教們，希望本文能帶給你們一些靈感:)。
問題分析
在設計開始之前，我們先來分析一下不同角色對于這個測試程序的不同需求。從助教的角度來看，他們可能比較希望測試程序可以達到這三點標準：
- 自動評測。測試系統應當能做到自動測試學生項目，并能記錄學生得到的分數。
- 保證公平。測試系統不能被偽造的電梯項目所欺騙，同時要甄別學生的作弊行為，并能給出一定的判斷依據。
- 部署簡單且方便。如果測試系統是通過讓學生上傳代碼的方式進行測試，那它應當能夠使得助教在部署時非常方便；如果是通過讓學生下載測試程序的方式進行測試，那么該測試系統應當能簡單方便地部署在學生的計算機上。
而從學生的角度考慮，他們則更可能希望測試可以做到這樣四點：
- 直觀。在測試完成后，學生能直觀地看到自己的測試結果。
- 快速。運行測試的時間不宜過長，學生能快速得到測試反饋。
- 小開銷。測試程序盡量不要為學生的開發引入額外的負擔。
- 多語言支持。考慮到學生們擅長的語言不盡相同，為了方便他們的開發，測試程序最好不會對學生所使用的編程語言有過多限制。
綜合考慮雙方的需求，本文為電梯系統設計了一套語言無關的自動測試框架，希望它能完美解決問題中提到的幾個挑戰，同時盡可能地滿足兩方需求。實際上，這個測試框架并非是與電梯項目緊密耦合的。測試者只要定義好數據接口，也完全可以在自己的測試工程外套上這樣一層語言無關的自動測試框架，以實現上述需求。
傳統測試
要想搭建一個自動的測試框架，首先應分析一下傳統測試該是怎樣的一個流程。仔細分析一下，其實電梯項目需要外界提供的數據只有這么兩項：電梯的配置信息與乘客的請求數據。
在傳統測試的流程中，助教可以把電梯的配置信息存儲在文件中，要求學生的電梯項目讀取固定文件加載該配置信息；也可以將乘客的請求數據也存在一個文件中，約定好數據格式后，要求學生的電梯項目按行讀取解析并調度。助教在測試時只需要提供這兩個文件，使用相應的運行環境運行學生的可執行文件即可。當然，助教也可以要求學生的電梯項目在運行中也可以交互，助教把乘客請求數據從交互界面逐個傳給電梯項目，這樣對實際情況的建模更加真實，但也就要耗費更長的測試時間。
上述流程存在著怎樣的缺陷呢？從上面的測試流程中我們不難發現：所有項目都是在助教的計算機環境中進行測試的，所以助教需在自己的電腦上安裝所有電梯項目的運行環境。如果助教希望能支持上面我們提到的學生需求中的【多語言特性，那么他將可能要為此付出不一般的代價：安裝若干種不同編程語言不同版本的運行環境，這將給助教的測試帶來巨大的困難。舉個例子，去年北航軟工結對編程環境要求做一個帶UI的項目，一共有10個項目需要測試，編程語言限制在C++/C#，但因為各個組在開發UI時使用了不同的依賴庫，而他們沒有把庫上傳到源代碼倉庫中，導致我在測試時非常苦惱。
同時，由于傳統測試是助教收集到所有項目后才會統一測試，只有在評分的環節學生才能知道自己的項目問題所在，學生在項目開發的過程中無法得到任何反饋。若是需求明確的小程序，只在評分環節進行一次測試是合理的，因為要鍛煉學生的測試能力。但若是像電梯項目這樣的一個復雜系統，教師團隊應當在學生開發的過程中提供一些反饋，讓他們確認對項目的需求理解無誤。
自動測試
自動測試需要克服上述傳統測試帶來的缺點，這就要求它既要能支持多編程語言的測試，又要能夠作為服務供學生多次測試，還得在測試結束后給出一定反饋。其難點主要也就是這三點，下面讓我們來挨個解決，第一個問題就是：如何讓自動測試程序支持多編程語言呢？
多語言支持
我們使用C#編寫了電梯的測試程序，現在需要它能測試其他語言編寫的項目。考慮到不同語言編譯后產生的可執行文件的格式不同，運行所需的環境也不同，如果想讓這個測試程序對于所有的語言都通用，就不能直接在編程語言層面支持，而要通過一些更加底層的組件如進程，系統或網絡來支持。
Web API
首先考慮的測試框架是B/S架構(瀏覽器/服務器模型)：助教把測試框架部署在服務器上，利用Web API作為信息傳輸的接口，學生的程序通過不斷地向服務器發包以獲取數據，助教則可以在測試程序記錄一些日志來記錄學生程序的正確性。使用Web API方式測試的好處在于：
- 能夠在測試程序記錄接收到數據包，自動驗證學生程序的正確性。
- 對被測試程序而言，只要求其能夠收發數據包即可，對運行平臺和編程語言沒有具體限制。
但是Web API因其公開性也有幾個不可避免的缺點：
- 相比傳統的測試程序，部署Web應用的時間成本與開銷較大，尤其是需要測試框架安裝一些額外依賴。
- 自動驗證存在漏洞，如果只從被測試程序發送的數據包中獲取作者信息，有可能會有“移花接木”的情況出現。例如，A同學將數據包中的作者信息改為B，就可以輕輕松松地幫B同學交作業。
- 考慮到程序本身是給高校教師使用的，一般會部署在內網服務器上以供學生訪問。部署在內網服務器上，缺乏有效的安全保護措施，很容易被死程序（比如不斷發送數據包的程序）攻擊，使得其他數據包無法及時得到響應。
Socket
既然B/S架構的方式行不通，我們考慮使用C/S的方式來實現。C/S的方式其實就是將學生的程序作為電梯程序，助教給學生下發一個可執行文件——也就是我們的測試程序作為測試程序，兩個程序通過進程間通信的方式進行交互以完成測試。
上面我們分析了公開性帶來的一些弊端，為了解決這個問題，我們需要讓測試框架在學生的計算機上運行。同時，我們不希望開銷和依賴過多，所以需要采用一個簡單可行,在原有測試程序基礎上擴展成本較小的通信方案，而基于Socket的多進程通信機制正好符合我們的要求：Socket屬于基礎網絡通信，一般的編程語言基本上都有用于Socket連接與通信的基礎庫函數，不會為開發者帶來額外的依賴，開發的成本也比較小。
服務
使用Socket可以解決多編程語言支持的問題，下面來解決第二個問題：如何把電梯測試程序作為服務啟動，以供學生多次測試呢？結合上文所說的Socket通信方案，解決第二個問題其實就等價于解決兩個子問題：
- 如何編程Socket通信，讓其可以發布成服務？
- 如何設計數據接口，讓測試程序與電梯程序進行數據交互？
服務的發布
要想讓測試程序作為一個服務運行在學生的電腦上，我們需要給學生下發一個這樣的可執行程序：當學生在本地啟動該程序后，它會監聽本地網絡的特定端口，對不同的請求做出不同的響應。整個測試程序的邏輯可用下述偽代碼描述：
ListenOnPort();//監聽特定端口
while(true){
AcceptDataFromClient();//電梯項目發送數據
RecordDataAndGenResponse();//記錄電梯項目本次發送的數據,并根據本次數據產生返回數據
ResponseToClient();//將產生的響應數據返回給電梯項目
}這里我們采用C#編程電梯測試程序，編譯得到的可執行文件可以直接在Windows系統中運行。
監聽端口
Socket通信中測試程序監聽部分的關鍵代碼如下
int port = 8989;
IPAddress localAddr = IPAddress.Parse("127.0.0.1");
var tcpListener = new TcpListener(localAddr, port);
Console.WriteLine($"Server >> Start Listening in {tcpListener.LocalEndpoint}");
tcpListener.Start();接受電梯程序數據
var buffer = new byte[8192];
var tcpClient = tcpListener.AcceptTcpClient();
using (var networkStream = tcpClient.GetStream())
{
//數據未準備好，切換到其他線程
while (!networkStream.DataAvailable)
{
Thread.Sleep(100);
}
//開始讀取Stream中的內容
int byteCount = buffer.Length;
StringBuilder builder = new StringBuilder();
while (byteCount == buffer.Length)
{
byteCount = networkStream.Read(buffer, 0, buffer.Length);
builder.Append(Encoding.UTF8.GetString(buffer, 0, byteCount));
Array.Clear(buffer, 0, buffer.Length);
}
//request是電梯程序發送的數據
var request = builder.ToString();
}響應電梯程序數據
//調用自己的函數產生對電梯程序的應答,返回的是字符串類型
string serverResponse = GenerateResponse();
byte[] serverResponseBytes = Encoding.UTF8.GetBytes(serverResponse);
//將數據回復給電梯程序
networkStream.Write(serverResponseBytes, 0, serverResponseBytes.Length);
networkStream.Flush();
Console.WriteLine($"Server >> Response : {serverResponse}");
Array.Clear(buffer, 0, buffer.Length);本文假設了學生使用的是Windows系統，如果想讓測試程序也支持Linux/MacOS系統，可以用C++重寫電梯測試程序，將GCC++編譯后的可執行程序下發。
在本項目中，測試程序的流程如下所示：
- 測試程序監聽本地的8989端口，等待著電梯程序發送請求數據。
- 電梯程序按照約定的數據接口向本地8989端口發送請求數據，接收返回的響應數據。
- 返回數據即電梯項目所需要的數據，包括電梯配置與乘客請求。
數據接口設計
在搞定服務的發布后，就需要考慮測試程序與電梯程序之間的數據接口了。整個測試都是由測試程序發出乘客請求，以驅動電梯程序的調度器運轉，這也就意味著：測試程序既要給出足夠的信息以驅動調度器，但又必須隱藏一部分以免超前調度。
這里所說的超前調度指的是電梯在時刻t時已經知曉時刻t+n時的乘客信息，并根據該信息調整自己的調度策略。這種超前調度算法跟操作系統頁置換中的最優置換算法類似，只是一種理想算法，并不能用于實際調度。
時鐘設計
為了達到不讓電梯調度器知曉未來的目的，測試程序需要將乘客數據按照時間順序分開發送。
物理時鐘
既然是按照時間順序，那我們自然就會有這樣的想法：用物理時鐘來驅動測試程序，當物理時鐘走到某條乘客請求的發送時刻時，測試程序主動向電梯程序發送乘客數據。
這種依賴于物理時鐘的做法簡單又直接，但在實際測試中，它卻并非是一個好的數據接口方案。使用物理時鐘來驅動測試程序發送請求，不論時鐘的基本單位有多小，測試程序在大部分時間內都是“空轉”的。同時，與物理時鐘的綁定導致測試所消耗的時間正比于測試數據中的時間跨度，大大延遲了測試的時長。
邏輯時鐘
所以在本項目中，我們的測試程序維護一個全局邏輯時鐘，電梯程序可以從測試程序返回的數據中找到下一個有效的邏輯時刻，并以此作為下一次請求的參數。這里所說的有效指的是存在乘客請求的時刻，在測試程序中我們將跳過不存在乘客請求的時間段以提升測試的效率。同時，由于請求是由電梯程序主動發起的，所以測試程序不會限制電梯程序的時鐘實現。電梯程序使用邏輯時鐘或物理時鐘均可，只要與測試程序的邏輯時鐘存在映射即可。
接口約定
在確定測試程序使用邏輯時鐘的方法響應請求數據后，我們就要具體定義電梯程序發送的數據包格式與測試程序的響應格式。根據上文中的分析我們知道電梯程序需要兩種數據：電梯的配置與乘客的請求。在本項目中，電梯的配置由學生自行指定，但因評分需求，電梯程序需要把電梯配置發送給測試程序，它的發送也作為測試的開始。數據接口涉及到請求主要分為兩種：一種是配置電梯的請求，另一種是獲取某時刻t時乘客數據的請求。
數據的傳輸需要序列化協議約束，本項目采用的是JSON序列化協議。一個簡單的JSON數據包示例如下所示,其中
{}是字典，每個鍵都映射到一個值[]是列表，存儲了若干個值
{
"employees": [
{
"firstName":"Bill" ,
"lastName":"Gates"
},
{
"firstName":"George" ,
"lastName":"Bush"
},
{
"firstName":"Thomas" ,
"lastName":"Carter"
}
]
}電梯配置接口
在測試程序正式開始測試前，電梯程序需要將其使用的電梯配置以下述數據格式發送給測試程序。
{
"User":"Student",
"Elevators":[
{
"ID": 1,
"Capability": 1500,
"FloorMax": 25,
"FloorHeight": 10,
"InitHeight": 20
}
],
"TaskID":"1",
"Operation":"CONFIG"
}成功配置后，測試程序將返回Config OK的消息。
獲取請求接口
在電梯程序配置好電梯信息后，即可按照下面的數據格式發送請求來獲取乘客的請求數據。
- Tick 是指電梯程序需要時刻為25時的乘客請求數據。測試程序默認第一個有效時刻為0，所以在初次使用這一接口時，電梯程序需要請求的時刻為0。
- FinishRequests 是指電梯程序從上一個有效時刻至時刻25期間所完成的請求。
- Operation 是固定值，它充當了Web API中路由的角色，告知測試程序電梯程序所需要調用的接口。
{
"Tick":25,
"FinishRequests":[
{
"PassengerName":"Sen_1",
"FinishTime":20,
"ElevatorID":1
}
],
"Operation":"GETREQS"
}當電梯程序成功發送請求后，測試程序會返回兩個參數
- NextTick 是下一個有效時刻。如果當前已經是最后一個有效時刻，NextTick會被置為 -1。
- Passengers 是發送請求中Tick時刻的乘客請求，以列表形式返回，列表中的每一個元素都是一個請求
- Sen_1 是乘客姓名
- 15 是乘客出發樓層
- 12 是乘客目的樓層
- 60 是乘客的體重
{
"NextTick":-1,
"Passengers":[
"Sen_1,15,12,60",
]
}反饋與自動評分
那么現在剩下最后一個問題需要解決：測試程序怎樣給出反饋并自動評分？同樣地，我們把這個問題拆分成兩個問題來分別解決：給出反饋與自動評分。
結果反饋
在本項目中，結果的反饋直接放置在最后一次請求的響應數據包中。當電梯程序向測試程序發送的【獲取乘客數據】請求中NextTick參數設置為-1，即意味著測試開始運行，測試程序會將測試結果打包成如下格式返回給電梯程序。
{
"Basic":100,
"Performance":100,
"User":"Student"
}自動評分
那么測試程序如何實現對電梯程序的自動評分呢？在電梯項目中，本文把評分分為兩點，一是對電梯運行正確性的評價，二是對電梯運行效率的評價。
對于電梯運行正確性的判斷，本項目采取以下做法：
- 在數據交互完成后，測試程序可以收集到所有請求完成的時間與所在的電梯。
- 在得到這樣的完成列表后，我們可以通過每個請求完成時的狀態逆向推出每個電梯各個時刻的狀態。
- 遍歷邏輯時刻的最小單位，并檢查每一個時刻電梯內的人數是否超過限制，同時檢查由不同請求推斷出的電梯狀態是否產生矛盾。
舉個例子，比如由請求【1】的完成狀態我們推斷出電梯【2】在時刻20在樓層3，而由請求【2】的完成狀態卻推斷出電梯【2】在時刻20時在樓層5，這樣就產生了矛盾，即可說明電梯程序的實現是有誤的。
對于電梯運行效率的判斷，由于電梯的配置參數不固定性，以及學生的調度算法的不固定性，故本項目采取對比測試的方法評價。我們在測試程序中實現了一個基本調度器，用于仿真一般情況下電梯的效果。在數據交互階段結束后，我們會運行自己的電梯仿真程序，得到一個標準調度時間，再與電梯程序的實際調度時間進行對比以評價電梯程序的效率。
目前僅考慮了平均調度時間作為唯一評價標準，實際上我們還可以加入更多的評價指標。博主認為好的調度算法應當具有下面幾個特性：
- 乘客的平均等待時間較低
- 乘客等待時間的最大值較低
- 大部分情況下，先發出需求的乘客要比后來的乘客更早地被服務
- 負載均衡，平衡電梯的“運動量”
加密保存
在給予學生反饋與完成自動評分后，測試環節還需要額外的一步：將自動評分的結果加密保存在學生本地，加密保存的意義在于防止學生篡改評分結果。
本項目中，加密的部分使用RSA算法生成公鑰跟秘鑰，秘鑰只有助教可見。當學生運行測試程序產生加密的自動評分結果后，將其上傳到Github統一的項目倉庫中。助教在評分時，將該倉庫下載下來，使用秘鑰解密文件，即可得知每個學生的成績。
自動測試小結
本文詳細講述了使用Socket通信 + 序列化協議 + 加密協議來完成自動測試的步驟與流程。其中Socket通信用于進程間的通信，可以簡單方便地發布成服務供學生使用；序列化協議協助電梯程序和測試程序更優雅地定義數據接口；加密協議部分使用了RSA算法，防止學生對測試結果文件“自作主張”，保證自動驗證的有效性。
源代碼
Github 源代碼地址：https://github.com/SivilTaram/EleAutoTest
文章列表
留言列表
