现代软件工程 结对编程 (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，如需转载请自行联系原作者