这三次作业采用了主线程获取请求，多级调度器逐级分派，电梯模拟运行的策略。具体来说，主线程实例化elevatorinput类，通过阻塞读取方式获得请求request，之后将请求分配给调度器scheduler，调度器负责处理请求（既可以自己处理，也可以分配给其他子调度器处理），每一个电梯与一个elevatorscheduler绑定，用于具体的调度、睡眠控制、打印输出。
本次作业的难点主要有以下几点：
如何控制调度器、电梯线程的终止：简单的生产者-消费者模型中，生产者不断生产，消费者不断消费，不存在线程终止现象；现实中的电梯，一天24小时运行，没有异常情况也不会终止。但是更多的多线程问题是需要考虑线程终止的。这三次作业也是如此：主线程将所有请求都发送给调度器后，告知调度器准备结束，调度器处理完自己队列中剩余请求后，结束线程。
这种一般性的线程生命周期可以用这个比喻来说明：假如你是一个员工，在上班的时候你可能在干活，也可能闲着，但即使闲着，也不能回家；到了下班时间后，如果你的任务还没有完成，那就继续工作（加班），如果完成了，就可以回家了。于是，我们可以抽象出两个因素：是否空闲（idle），是否到达下班时间（在电梯的问题中是输入是否结束，可用inputend变量表示）。是否空闲是可以自己判断的，而是否到达下班时间则需要外界的通知。以下讨论这种通知输入结束机制。
一种比较容易想到的方法是采用interrupt机制
我要评论while (true) {
request request = elevatorinput.nextrequest();
if (request == null) {
scheduler.interrupt();
} else {
// pass
}
}
但是这种方法并不能实现精确控制：我们希望的是，如果调度器在等待下一个输入（wait()函数中），就打断；而如果它在执行别的任务，比如sleep(100)，或者是其他的同步任务，就不打断。虽然在这一单元的作业中没有出现这种情况，但是多做这种考虑也是合情合理的。
另一种方法是专门设定一个setinputend()方法，由主线程调用，告知调度器输入结束。
class scheduler {
boolean inputend = false;
queue<request> requestqueue;
public synchronized void setinputend() {
this.inputend = true;
notifyall();
}
public synchronized void addrequest() {}
public synchronized void getrequest() {
while (requestqueue.isempty()) {
wait();
}
return requestqueue.poll();
}
}
我在作业中采用的是这种方法，但是后来发现，其实还可以用一种更加简洁的方法解决：建立一个terminationrequest类。
interface request {}
class personrequest implements request {}
class elevatorrequest implements request {}
class terminationrequest implements request {}
这样，通过归一化处理，可以用一个队列来统一管理（更一般的来说，是把所有线程关心的状态改变的通知都放到统一的容器中管理，对外用同样的接口，对内采取不同的处理策略）。同时，这种归一化也方便了线程安全容器的使用。
区分两种获取请求的模式：在简单的生产者-消费者模式中，消费者在没有商品的情况下总是会在共享区中的wait函数中等待，但是在实际生活的很多情况下，这种情况是不可接受的——消费者可能还有其他事情要完成，使用wait函数等待并释放cpu资源固然是一种进步，但这种方案同时也制约了消费者进行其他活动的自由。回到本单元作业，每一个电梯在行为上都需要实现：获取新的请求，决定电梯的行为（开门、关门、上行、下行等）。但是这两种行为并不是时时刻刻都需要进行的：如果电梯局部队列为空，电梯内部没有乘客，则电梯处于空闲状态，此时不需要频繁决定电梯的行为，只需要等待下一个请求的到来。因此，当电梯空闲时，应当阻塞地读取请求，即在请求处等待下一个请求；而当电梯忙碌时，则只需要查看并更新请求即可，没有新请求也不阻塞。
这两种不同的模式，可以自己解决，如：
class elevatorscheduler {
private queue<request> queue;
private queue<request> localqueue;
private synchronized request getrequest(boolean quickretreat) {
if (quickretreat) {
return queue.poll(); // if the queue is empty, return null
} else {
while (queue.isempty()) {
wait();
}
return queue.poll();
}
}
}
也可以采用java内置的blockingqueue来解决：
private blockingqueue<request> queue;
private void update() {
if (idle) {
localqueue.add(queue.take());
}
queue.drainto(localqueue);
}
灵活的分配器：第一次作业只有一个电梯；第二次作业有多个电梯，但只有一种型号；第三次作业有不同型号的电梯，每一种电梯型号下的电梯数是不同的。可以这样认为，第一次作业的电梯只需要一级调度器（直接指挥电梯的调度器），第二次作业的电梯是两级调度（一级负责电梯见的负载均衡，另一级负责直接指挥电梯），第三次作业的电梯是三级调度（一级总调度器负责换乘相关管理，一级负责同一个类型的电梯的负载均衡，一级负责直接指挥电梯）。如下图：
为了使得分配更加灵活，给这些scheduler设计一个统一的接口requestreceiver即可，至于内部的处理，或分配或自行指挥电梯，请求提供者都不必关心。
interface requestreceiver {
void addrequest (request r);
}
class centralscheduler implements requestreceiver {}
class scheduler implements requestreceiver {}
class elevatorscheduler implements requestreceiver {}
反馈和闭环控制：在实际多线程编程中，反馈和闭环控制也是十分常见的。本单元作业也不例外：换乘需要进行请求的反馈，即电梯运行一部分请求后，由另一个电梯继续完成另一部分请求。既然电梯是逐级控制的，电梯处理完自己应该处理的那一部分请求后，需要将请求反馈给上级调度器，由上级调度器进行二次分配。另一方面，调度算法在进行调度时，也需要考虑各电梯的负载均衡问题，因而电梯也要上报自身的负载情况。
这几次作业中，可以通过相应线程类提供反馈接口，进行逐级反馈状态：
interface feedbackreceiver {
void offerfeedback (feedback fb);
void offerrequestfeedback (collection<personrequest> requests);
}
class centralscheduler implements requestreceiver, feedbackreceiver {}
class scheduler implements requestreceiver, feedbackreceiver {}
在反馈反向传播的时候，每一级scheduler也可以对反馈进行处理，比如作业3中的负载，每一类电梯的负载可以取这一类所有电梯中负载最小的电梯的负载。
楼层映射：这个问题其实并没有什么面向对象的困难，主要是一个小技巧。每个电梯调度器（直接指挥电梯进行运动的调度器，它实现了调度算法）有一个映射，实现楼层到楼层下标的快速转换。
与其通过数学方法实现（分段函数）：
int flr_to_ind (int flr) {
if (/* some conditions */) {
// do something
} else if (/* ... */) {
// do something
} else {
// pass
}
}
不如用java自带的方法：
list<integer> flrs = arrays.aslist(-3, -2, -1, 1, 2, 3); index = flrs.indexof(flr); flr = flrs.get(index);
假如我的第三次作业真正实现了第一部分中所叙述的思想和方法，那么再进行扩展也不会很复杂了。但事实上我的第三次作业并没有完全实现这些方法和技巧——程序的主题部分是第五次作业时构建的，之后只做了些小修小补。但是毕竟结构是类似的，也可以做一些分析：
request接口下增加一个紧急制动请求的实现，调度器将这一请求分派到对应电梯。电梯到达下一个停靠点时，通过反馈渠道反馈所有的未完成请求，由上层调度器二次分配，同时电梯线程结束运行。从solid角度看：
elevatorscheduler类的职责部分重叠，耦合过高。在一开始的设计中，电梯的职能被规定为负责输出和睡眠（因为这两方面相对固定，可以与易变的elevatorscheduler分离，但是在之后的迭代开发中，逐渐职能扩充。requestreceiver、feedbackreceiver、runnable方法，也算是有一点isp的意思了。main函数线程只依赖requestreceiver接口，也有一点dip的意思了（虽然没有实现）。考虑到三次作业结构一脉相承，每次迭代又没有什么重大改动，就只分析最后一次作业了。
uml图：
这里只实现了二级分派结构，其中persontransfer是课程组提供的personrequest类的子类，表示需要换乘的乘客请求。二级分派结构可以解决这三次作业的问题，main函数获取请求，再由高级调度器分派给低级调度器，低级调度器与电梯类协作，实现look电梯调度算法。在算法的实现过程中，需要管理楼层信息、管理用户请求信息，这些管理由building类和floor类处理，同时设置floornumbermanager类，提供一些静态方法管理楼层映射、可达性查询等服务。
这种结构的主要问题是没有处理好电梯类elevator和电梯调度器类elevatorscheduler之间的关系。电梯调度器类只拥有一个电梯，负责这个电梯更细致的调度管理，如每一个时间节点，决定电梯上行、下行、开门、关门等动作，主要实现了算法。但同时，电梯类不仅负责输出、睡眠，还负责管理电梯内部人员，检查到达目的地的乘客，反馈电梯内部乘客信息等。在具体实现中，电梯类又将自身容器暴露给电梯管理类，使得两个类之间耦合度较高。
此外，电梯类elevator并没有成为一个独立的线程，所以在电梯睡眠时，实际上时是在elevatorscheduler线程中睡眠，导致电梯睡眠和电梯调度算法运行无法并行，降低效率。
复杂度：
可以看出，调度器是比较复杂的类，而调度器中负责算法的方法又是调度器中比较复杂的方法。但是除了调度器之外，电梯类也比较复杂，这是与设计初衷不符的。原因在上文也提到过，主要是随着代码实现的推进，电梯类的职能不断扩充，与调度类有所交叠，没有很好处理这一问题。
协作图：
这一单元的作业主要容易出bug的地方包括：
我在三次作业的强测和互测中均没有发现bug，但是我的第一次作业（整个课程的第五次作业）有一个非常严重的错误（强测和互测，由于测试机制固定，都没有检测出来）：如果所有输入结束后没有立刻提供输入结束信号，程序将会进入死锁，无法终止。部分代码如下：
// methods of elevatorscheduler
public synchronized void setinputend() {
this.inputend = true;
notifyall();
}
private synchronized void update(boolean quickretreat) {
if ( (inputend || quickretreat) && buffer.isempty() ) {
return;
}
while (buffer.isempty()) {
try {
wait();
/* when the thread is notified, it's still in the while loop */
} catch (interruptedexception e) {
return;
}
}
// some updates here
}
可见，虽然程序退出了wait()函数，但还是会再次进入wait()函数，导致死锁。一个简单的修复是在while循环上增加一个条件；设计上的修复我在第一部分已经提到过，线程检测到terminationrequest后就不再调用update函数，把这个问题在线程内部解决。
另一个问题是没有处理好cpu资源的让出，表现在轮询所导致的cpu_tle。一般来说，线程空闲时需要等待，可使用wait()函数，一旦线程需要被唤醒，相应锁的notifyall()函数必须被调用。我在第一次电梯作业的互测中用类似以下数据的数据点发现了两个a屋的solid bug：
[5.0]1-from-2-to-3 [150.0]2-from-14-to-5
本单元测试程序主要考虑自己的使用，包括三部分：
输入文件的时间映射器，将带时间的文件输入映射到时间轴上，实现定时输入。具体代码见：https://github.com/yushengzhao/buaa_oo_elevator_input_mapper
电梯仿真器，模拟电梯的真实运行，在运行过程中检查相关问题。主要思路是：将电梯请求和被测程序输出转化成若干电梯指令，按照时间排序，在仿真器上模拟运行，在运行过程中记录参数、检查行为，最终可以给出性能报告。
请求指令生成器，可以定制若干段请求序列，每一段可以设置参数，可参考以下代码：
def generator(size=10, timescale=10, id_start=1, time_shift=1):
# generate one segment of requests
pass
def generate():
periods = [12,19,8,4,13]
sizes = [8,4,10,13,16]
s = []
id = 1
time_shift = 0.3
for i, period in enumerate(periods):
s += generator(size=sizes[i],timescale=period,
id_start=id,time_shift=time_shift)
id += (sizes[i]+1)
time_shift += (period+0.1)
将这些组件连接起来就可以生成测评机了，但是考虑到自身实际需求，就没有具体实现了。
一个值得注意的地方：许多同学采用python脚本进行时间映射，我在参考了之前一些学长的博客之后发现，这种方法容易产生时间偏差，时间控制不是很精确，而将时间映射器内嵌到java语言内部则可以实现更精确的控制。同时，这样也便于调试。
关于请求生成策略：实际应用中可能会出现不同时段负载不同的情况，我在测评机中按段生成请求，可以模拟这种情况。在进行几次到几十次测试后（总请求量1e2量级），一般没有什么显著问题；进行大量测试（1e3,1e4量级的测试）也许可以发现一些问题，但考虑到每一个测试所消耗的时间成本，就没有过多测试了。真正实际应用中，大量的测试肯定是必要的。
这一单元的调试和测试与上一单元相比，主要是多了时间因素，在测试时要考虑输入随时间分布的不同特征，如在一个时间点大量输入，在一段时间内没有输入，等等。而在调试时，由于不能使用断点调试法，我普遍采用了日志记录的方法，增加一个可插拔的logger：
private static final boolean logger = true;
private static final boolean assertion = true;
public static void log(string msg) {
if (logger) {
system.out.println(msg);
}
}
public static void ast(boolean condition, string msg) { // ast == assert
if (assertion && !condition) {
system.out.println("assertion failed: "+msg);
}
}
或者实现一个带level的不同重要性的日志输出：
private static final int level = 5;
public static void log(int level, string msg) {
if (level >= level) {
system.out.println(msg);
}
}
当然，java也有相应自带的日志记录机制，不过考虑到这一单元作业并不需要复杂的日志，就没有使用了。
多线程方面，我在做电梯第一次作业时花了比较长的时间（甚至一度以为自己就要止步于此了），当时有许多问题想不清楚，最后实现的代码也有许多逻辑混乱的地方。多线程之所以容易出现各种安全问题，归根结底还是线程自身行为逻辑复杂，比如，简单的生产者-消费者模型，基本不会有人写出线程安全的问题，但是复杂一些的生产者-消费者模型（如消费者在没有产品时不调用wait函数，而是进行其他活动），就容易产生线程安全问题了。因此，根据需求建立简单通用的线程模型非常重要——简单的逻辑往往不容易出错。比如观察者模式，构建了一个线程发布消息，若干线程接收消息的模型；反过来，又有时也需要若干线程发送消息，某一个线程接收消息的情况，这时便可以采用消息队列：
class scheduler {
private queue<message> messagequeue;
public synchronized void addmsg() {/*some code here*/}
public synchronized message getmsg() {/*some code here*/}
}
interface message {}
class feedback implements message {}
interface request extends message {}
所有需要通知scheduler的消息，都通过addmsg方法传入，无论其具体内容，之后再由其他函数分别处理。因此，当scheduler处理完剩余任务后，便可以直接在getmsg方法内等待。
设计原则方面，我在完成第一次电梯作业时，并没有太多的设计原则方面的意识，而由于后两次作业都沿用第一次作业的结构，所有后两次作业也没有体现多少设计原则，这是遗憾的。
代码重构方面，我从这一单元开始坚定了能不重构就不重构的态度。从计组到现在，在各种需要迭代开发的工程中，我总是感觉之前写的不够好，想要重构，但又经常忽视了重构的风险以及不重构的可能性。实际开发中，重构肯定是要尽量避免的，在原来的代码（可能是看似比较乱的代码）上修改其实才是常态。事实上，看似乱糟糟的代码其实可能并没有想象中那么差。我在第二次电梯作业时曾经尝试了重构，但是等到真正动手写重构代码的时候才发现，如果重构，很多代码都是差不多的，原来很多设计上的考虑都是很有道理的。
算法方面，这一单元的作业给算法留出了很大的空间。不过想拿高分并不需要很复杂的算法。最基本的look算法，在强测不出现错误的情况下，基本就可以达到95分以上了。后两次作业再加一些负载均衡的考虑，如果没有错误，基本也能拿到95分以上。尽管如此，讨论一些算法也是没有坏处的：
当然这些算法都是我没有实现的，毕竟课程的主要目的也不是算法。
其他：
building，给每一个building安排若干floor，并提供“向上的按钮”和“向下的按钮”接口，就像现实生活中的电梯一样。电梯不知道一个楼层有多少人，只知道某一楼层有没有人想上楼、有没有人想下楼。
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
【开源】使用Angular9和TypeScript开发RPG游戏(补充了Buffer技能)
网友评论