現代軟體工程 結對程式設計 (II) 電梯排程

Pair Project II: Elevator Scheduler

怎樣設計API?  怎樣從不同角度考慮需求?  怎樣對不同的設計進行評估? 

怎樣做設計一個測試架構來測試衆多解決方案?  如何驅動這樣的測試架構?

怎樣和夥伴合作,  快速有效地完成這些挑戰?

這就是我們這次小項目要練習的。

Design and implement an Elevator Scheduler to aim for both correctness and performance, in managed code.

Skills to practice:

a)Requirement Analysis

    需求分析   

b)High level design (interface, information hiding, loose coupling)

    程式API 設計,  資訊隐藏, 耦合

c) Test Framework Design

    設計測試架構, 模拟測試資料

d)Implementation skills

    設計的實作

e)Algorithm design

    算法設計

Imagine we’re building a tall office building,   We need to have design an efficient elevator system to carry people to their destinations.    the following is a example of the configuration about elevators:

The Building has 21 floors, 4 elevators, many passengers use these elevators everyday (passenger weight: average 70kg. max 120kg, min 40g).

Other constant data: Elevator speed, door open/close time, passenger time for going in/out of the elevator. We can make reasonable assumptions about these.

The building has 21 floors, from floor 0, 1, ... to 20. Floor 0 is the underground parking level, floor 1 is the lobby level. Most people come in/out the building via these 2 floors.

Elevator name

Service floor list

Passenger limit

Weight limit

1

All floors

10

800 kg

2

floor 1..10

3

floor 0,1,2..10

20

1600 kg

4

floor 0,1, 11-20

2000 kg

*note: in our test program, the configuration of elevators can be changed,  the scheduler need to read the configuraiton at the initialization time via the API.

2.1Each pair of students will design a set of interface and class definition so that an algorithm provider can provide his/her implementation to the “elevator scheduler” class.

2.2 We will discuss the student’s submission in the class,  pick the best design.

2.3 after the API is decided,  we will focus on the design of test framework

2.4  1-2 volunteers will implment a “test framework” app,  and the rest student pairs will each pair will focus on the implementation of the “elevator scheduler” program.

consideration for the API:

a) how to keep it simple.

b) how to provide enough info for the scheduler to finish the scheduling work,  without knowing too much info?

c) which component is actually driving the elevator?

d) how to regulate proper passenger behavor?  (e.g. if a passenger needs to go to floor 3 from floor 20, but the current elevator can’t go there directly, what should the passenger do?)

consideration for the test framework:

a) how to make sure it generates the same result for the same test cases on a given scheduler?

b) how to check the correctness of the scheduler?

c) how to prevent “cheating” by the scheduler? 

d) how to emulate the “real world” efficiently?  (e.g. if 2 passengers are 30 minutes away, does the test framework need to wait for 30 minutes?)

TA will come up with a consistent testing model to test your program according to the “rush hour” scenario (see below), and record the total travel time of all passengers.

You (student pair) have:

1)A set of API

2)A simple solution (Bus program)

3)A set of test cases to run

2.5Explanation of BUS program:

We can have a worst case algorithm called “bus”.This algorithm treats an elevator as a bus,it goes from bottom to top,stops at every floor, open the door, to let people in and out,then close the door and move on.After it reaches the top floor, it will go down.This algorithm can serve all requests, but it’s apparently not the fastest algorithm.

Your code is required to be managed code (C#, managed C++, etc).

It has to be correct,  all passengers can reach their destinations

It should be as fast as possible. 

It should not have randomness in scheduling (this is to avoid randomness in testing).

Score guideline:TA will evaluate the “average total travel time” for all passengers in the same test case, the lower, the better. If your performance is lower than “bus” solution, you get 0 points; if your program can’t deliver any passenger to the correct destination, you get 0 points.

One hint about elevator scheduling: When total weight is within 40 kg of the max limit, or the number of passengers is already at maximum, the elevator doesn’t need to stop for more external requests.

The elevator scheduler program doesn’t know how many passengers are waiting on each floor,it doesn’t know how many passengers will show up either.This is the same with the real world situation.

TA will simulate a “rush hour” test.The “rush hour” test is to simulate the come-to-work and leave-work scenario in a business building, which has the following 2 parts (they can be run next to each other).

1)Simple test.20 passengers

20 people going thru random floors within 5 minutes.

2)Come-to-work. 1000 total passengers,  duration: 60 minutes

a)80% of them goes from floor 0 and 1 to all other floors, the destination is distributed evenly. The time each passenger arrives at the elevator can be emulated as a normal distribution.

b)20% of them are going between any 2 floors of [2, 20], very few people travel between 2 adjacent floors (e.g. from floor 5 to 4). Other than this, the distribution is also even.

3)Leave-work. 1000 total passengers, duration: 45 minutes

a)90% of them go from other floors to floor 1 or floor 0.

b)10% of them travel between floors [2, 20], again, very few people travel between 2 adjacent floors.

電梯作業的挑戰和參考

這道題目在過去的10年中給不少同學造成了麻煩，一些助教也覺得不好改這個作業，下面是我對這個作業的一些認識，給學生/助教/老師做參考。

首先對于這個作業，有四種角色，她們的需求未必一緻：

-       老師：希望作業能真正鍛煉同學們的軟體工程能力

-       助教：希望作業好改，容易厘清好學生和差學生，很容易抓到抄襲

-       學生：希望作業容易，打分公平，有意思，能學到一些有用的技能

-       其他讀者：希望能給自己的教學/工作/學習有一些參考

前三類角色的需求是這個作業的重點。這個作業就是要學生寫一個“電梯排程程式”， 助教寫一個“電梯排程程式的測試架構”。流程如下：

老師宣布作業，講解作業的背景，要求，軟體工程的相關理論。

助教把技術文檔交給學生，把測試架構連同簡單的測試資料也交給學生

學生閱讀技術文檔，試運作測試架構，寫自己的排程程式，上交自己的排程程式給助教。

助教設計各種新的測試資料，測試學生的排程程式能否滿足

基本要求：所有乘客最後都能送到目的地

效能要求：測試程式的KPI,

            并以a) b) 的結果給學生作業排序。

        5. 學生可以做進一步作業（例如實作一個GUI 的電梯運作顯示界面），寫部落格描述自己程式的特點以及學到的軟體工程技能。

        6. 助教給學生打分，并通過部落格留言等方式交流。

        7. 老師總結并讓同學互相交流

這個作業對學生和助教有什麼挑戰呢？ 下面一一說來：

挑戰1.  什麼是好的排程算法？

當然第一是所有的乘客最後都到了目的地

第二，效率最高：

    -       等候時間最短？

    -       在電梯裡的時間最短？

    -       …?

建議：電梯排程有幾種極端的情況：

    -       公共汽車（bus）： 像公共汽車一樣，每站都停，到頭了，就向反方向走. 

    -       計程車模式（taxi）: 隻接受一個請求，然後就直奔目标，中途順路的請求都一概不理。

    -       正常的電梯：比計程車能接受更多順路請求，但是不像公共汽車每站都停，來回奔忙。

經過幾次的讨論，大家都認為是“所有乘客的平均旅行時間（包括等待電梯，在電梯内的旅行時間）”是一個最合适的KPI。

挑戰2. 測試架構給學生的接口是什麼？

電梯排程程式隻是電梯+乘客系統的一部分， 那麼同學要完成這一部分的工作，這部分的工作怎麼和其他部分整合呢？是寫一個 .cpp 檔案去實作某一些類，還是…?

建議：第一步，可以是和語言有關的， 例如老師提供了一個 bus 模式的實作，用CPP 完成，然後學生改寫其中的類的實作，規定不能改變 .h 或其他的子產品。

第二步，可以是和語言無關的接口。

挑戰3. 排程子產品能做什麼？

很多學生一開始就想自己實作所有電梯的子產品，然後排程子產品直接修改各個電梯的位置，直到所有乘客都到達目的地。

老師問：那如果子產品有bug，電梯運作速度超過合理範圍，助教如何發現呢？

學生答：嗯… 助教寫一個分析程式，分析各種log，找到不合理的地方。

老師問：那不同的學生的排程邏輯都不同，助教怎麼能有足夠的知識和判斷在事後寫程式來分析呢？

學生：反正這樣我比較爽，其他人我不管。

老師: …

建議：

測試架構要管理整個電梯系統的運作，和乘客子產品的互動，以及各種計時和統計。

電梯排程子產品能知道目前各個電梯的位置，以及系統的情況。排程子產品輸出的，是給各個電梯發出的運作指令。

挑戰4. 如何模拟資料？

電梯系統的資料：

        樓層的情況，電梯的數量，每個電梯運作速度，載客重量和人數的上限，電梯能到達的樓層

乘客資料：準備一個資料檔案，每個資料有下面的格式：

乘客ID，乘客體重，乘客出現的樓層，乘客的目的地樓層，乘客源樓層的時間。

那麼，電梯排程子產品能讀這個資料檔案麼？

很多同學覺得這樣很簡單，讓電梯排程子產品讀檔案就好了！  但是這樣的話，電梯排程子產品就能預先知道“将來會發生什麼事情”， 例如，排程子產品能知道下一分鐘有多少人出現在哪些樓層， 她們的目的地是哪裡， 排程子產品就能預先指揮電梯到相應樓層準備。 這是不符合實際情況的！

測試架構應該處理這個檔案， 做必要的資訊隐藏，讓排程子產品隻知道目前在系統中的乘客的情況。

挑戰5. 如何處理時間的流動？

考慮這個情況：一個乘客A是上午8點鐘出現，從一樓到十樓，  下一個乘客B是上午9點鐘出現，從五樓到九樓。

如果在告知排程子產品乘客A的情況後，馬上告知乘客B 的情況， 就會出現時間的錯亂，排程子產品可以讓同一部電梯五樓停下接乘客B， 但是乘客B是一小時後才按請求電梯的電鈕！

很多同學的反應就是把這個測試架構做成一個實時系統， 有一個嚴格的時鐘，各個部件按照時鐘運作。 那麼，那麼， 這個系統要等待一個小時，才告知排程子產品乘客B 的資訊麼？

建議：考慮 “事件驅動的模型”，  在沒有任何事件的情況下，時鐘就可以向前撥！  注意，有些優秀的排程算法會這樣設計：

    當目前這一批乘客都送到目的地後兩分鐘，如果沒有乘客來， 就把電梯排到某個位置。

    或者，在 8 點鐘把所有電梯都派到一樓等待。

這個事件驅動的模型要能夠支援這樣的算法

挑戰 6.  如何處理不同電梯到達不同樓層所帶來的特例

假設電梯1 隻停靠1層，15 - 25 層， 電梯2 停靠1 - 15 層。  乘客在1層，要上20層。電梯2到了，開了門，乘客要上去麼？在現實生活中，乘客一般就上去，到15 層出來，再換乘電梯2.  那麼，誰來負責實作這個邏輯呢？

挑戰 7. 如何寫程式生成大量測試資料

我們的電梯要模拟高峰時刻的人流， 上午 7 - 8 點有一千人上班，大部分是從一樓到各個樓層，同時有一半左右的人從各個樓層去 3 層（食堂）吃飯，還有少部分是在各個樓層來回旅行。 助教要手動準備這些資料，還是可以寫一個程式生成各種各樣的資料？

挑戰8. 如何讓這個測試架構和 GUI 界面結合起來，可以實時看到電梯運作的效率？

本文轉自SoftwareTeacher部落格園部落格，原文連結：http://www.cnblogs.com/xinz/archive/2011/03/20/1989662.html，如需轉載請自行聯系原作者