第二次电梯的架构设计与调度策略
[TOC]
第八周研讨课，笔者依旧准备了讲稿和分享，但是没有选上，在这里和大家分享。
Part 0 第一次电梯架构与调度基础
第一次作业中，ABCDE座各有纵向电梯一部，乘客需求只有纵向。
在这次作业，我们核心设计采用生产者-消费者模型，大致结构如下：
其中，我们的InputHandler维护所有请求的一个大Dispatcher，其中储存所有楼座的待分发请求，并由大Dispatcher分发给五个楼座的小Dispatcher，各电梯只需和自己楼座的Dispatcher交互即可。
对于多个请求，综合实际性能和实现难度，采取LOOK算法，尽可能同方向捎带。
在上述设计中，我们的线程只有输入线程和五个电梯线程，秉持精简和易维护的架构设计理念，我们尽可能减少线程之间复杂的交互关系。
Part 1 迭代架构设计
在上述第一次电梯的基础上，我们迭代到第二次电梯架构设计。
新需求分析
第二次作业的变化主要包括：增加横向电梯种类并支持在同楼层不同座之间的乘客需求和支持动态增加（纵向和横向）电梯数量。
对于第一个需求，我们秉持开闭原则，增设Elevator父类，纵向电梯ElevatorCol和横向电梯ElevatorRow分别继承它，只需在子类重写run方法即可。
对于第二个需求，我们采用工厂模式，通过ElevatorFactory生产具有我们需要的功能的电梯。
请求群
对于同楼座（层），我们首先定义请求群的概念，一个请求群内的所有请求对该群内的所有电梯均可视（即电梯都有接到该请求的能力），群内所有电梯都可接待所有请求。
类虚拟空间
同时，为了简化调度负担及结构复杂度，我们借用OS中虚拟空间的思路。
对于群内的电梯，其可视所有请求，并且不认为有其他电梯，这样即可不更改第一次电梯中的LOOK策略，并便于应用自由竞争的调度策略，这将在下一部分简述。同时，通过类物理空间的理念，我们通过请求是否被真实满足来避免产生冲突，保证了架构的安全性。
Part 2 基于LOOK和自由竞争的调度策略
设计的核心理念
正确性、易维护性和可迭代性是我们架构设计的核心思想，秉持less is more的思路，我们尽可能在逻辑上简化调度策略，在实现难度和迭代维护难度与性能方面做取舍平衡，最终选择LOOK和自由竞争的策略。
LOOK
纵向LOOK：
当电梯有乘客时，以乘客中目标楼层距离当前楼层最远的请求为主请求确定目标楼层
当电梯没有乘客时，首先按照原方向，寻找距离当前楼层最远的有请求的楼层，找到则确定为目标楼层，这次寻找最终结果有可能会是当前层。如果寻找无果（沿方向的所有层包括本层都没有请求）则改变方向，继续寻找。若最后没有找到，则可以返回一个标志结束的值表示电梯进入空闲。
横向LOOK：
当电梯有乘客时，依然希望寻找其中目标楼座距离当前楼座最远的请求为主请求，但是这里的距离不应该是简单的加减法，可以加上模运算（注意若出现负数直接取模不符合我们的要求）：
1
dis = (target - nowBuilding + 5) % 5;
当电梯没有乘客时，原则上仍然按照第一次的方法寻找，只是如果第一次向上的尽头是10层，这一次顺时针尽头应该变为
(now + 2) % 5；向下的尽头是1层，这一次逆时针尽头应该变为(now - 2 + 5) % 5。
LOOK的性能在随机大数据中有较好的表现，同时易于实现。
自由竞争
在Part 1中，我们介绍了请求群和虚拟空间的想法，在这基础上，我们介绍自由竞争的具体实现。
对于每台电梯（无论横纵），其均按照自己的LOOK进行调度运行；当其在访问本请求群内的请求时，不会考虑别的电梯是否正在前往其中某个请求，而只考虑是否满足自己的调度来运行。这样，我们只需要在电梯arrive每层的时候访问请求群内的请求即可，若其接到了请求，则在请求群内移除；若某格请求被其他电梯接走，而其事实上是使本电梯运行的动力，那么至多付出一层的代价，本电梯就会重新访问请求群并基于LOOK获得新的运行方向。
上述设计较为精简，在面对大数据时表现均衡；同时，省去了中央调度的设计，类分布式的思路使得电梯自行运动而无需被指派任务；并且对电梯数量没有任何限制，覆盖了作业要求的15部要求。
读写锁
在上述介绍中，电梯们对于所属请求群内的候乘表读相比写更频繁，可以采用读写锁来进一步优化提升性能。
Part 3 未来需求预测与预迭代设计
上面两个Part简介了第一次电梯设计并着重分析了第一次到第二次的迭代设计和开发，为了进一步说明我们设计的易维护性和可迭代性，我们预测下一次作业需求并简要介绍预迭代设计思路。
未来需求预测
满足不同座不同层的需求，如E4->A2。
预迭代设计
基于第二次电梯的设计，我们只需在架构上做如下迭代开发：
拆解需求
对于不同座不同层的需求，我们根据横向和纵向电梯数量与两个作业群的需求数量选择两种正交分解方式（先纵向后横向与先横向后纵向）中的一种，拆解为两个步骤。
分段满足
对于拆解后的需求，我们采用类Experiment4中的操作，实现如果当前电梯处理完的请求并没有完全满足该请求，则制作新请求并传递给大Dispatcher，进一步由大Dispatcher分发给小Dispatcher。同时，修改isEnd()信号，使得所有请求（分段和不分段）都满足后所有电梯线程才可结束。
This is copyright.