OS-做一个简单的shell

北航面向对象与程序设计第二单元课程作业，电梯调度器ElevatorDispatcher 2.0。
为1.0的迭代，新增需求：

1. 动态增加自定义电梯。
2. 电梯日常维护请求。

hw6_log

新增需求

• 掌握线程安全知识并解决线程安全问题，同时在架构上围绕线程之间的协同设计层次架构。
• 默认有六部电梯，六部电梯参数固定，但是后续可以增加电梯（后续增加的电梯可以半自定义ID，起始楼层，满载人数，移动时间），电梯数量不超过12。
• 日常维护请求，即停掉电梯（在两次移动操作之内停下），保证不会再开启电梯，但下次迭代可能就指定维护时间了（又预测失败了，呜呜呜

坑点分析&需求实现

• 刚新增就维护的情况
• 一下增加几部电梯的情况
• 一下维护几部电梯的情况
• 输入结束了，但是电梯还在维护下客的过程中

• 考虑如果电梯太快了，然后我在分派里面派Maintain太慢了，它已经移动了两层怎么办捏（（

• 我们要考虑上述新增需求需要谁来做到，整体来说这一周的增量开发的幅度不大

  • 虽说幅度不大，但是我在实现maintain的过程中还是遇上了不少的线程安全的问题，在这些碰壁中加深了我对线程安全的理解。
  • 详细请看线程安全分析一节
• 增加电梯就直接在分派器里面操作就行了，然后自定义电梯的构造可以给出构造重载（也可以用工厂模式，但我个人感觉没必要
  • 有自定义量之后会有一个比较大的问题，分派策略需要发生变化，我的distanceEva可能需要增加更多的指标了
  • 有时间其实可以实现一下影子电梯（后面细说）。
• 关于日常维护，可以作为电梯的一种状态，这样既符合现实，又有利于迭代。
  • 维护的电梯不参与分派就好了。

具体实现

• 由于需求增量不大，据我后面的分析，我并不需要增加类，所以类图还是上一次的实现。
  

• 至于要如何将需求融合进上一次的架构，且听下面分解！

新增电梯实现

• 先初始化input类，按照不同的请求类型做不同的操作：

• 关于如何增加电梯请求与维护请求：我想到了两种实现。

  • 输入线程直接的操作
    • 输入线程直接对分派器增加请求，可以实时增加电梯。
    • 输入线程直接对电梯进行操作，实时maintain电梯。
  • RequestTable增加除了人请求之外的其他两个请求的ArrayList，dispatcher还是在它这取东西（我选择这个，这是一种归一化的处理。
• 然后在Elevator类中增加属性，并实行相应的默认值替换。
• 在Dispatcher类中，每一次run，需要判定三个东西，有没有maintainReq、有没有加电梯的指令、有没有人。如果有的话进行相应的处理就行（怎么实现maintain的处理，请看下文。

maintain的实现

• maintain通过在passengerQueue里实现增加请求来实现，即分派器在总表里面拿到maintain的请求，就把它放到分表里面，让elevator自行取请求（所以可以走两楼这个界限我还是别去碰了，这里本来就有延迟了

• Elevator MAINTAIN后意味着需要把人都送回requestTable，怎么界定访问，难道要在Elevator里加上总表的属性？

  • 这样其实也就相当于Elevator也是一个生产者了，合理的。！！！可以看下图示意：
    

• maintain之后还可以走两步，这两步是尽量要走完的，所以我加了一个maintain倒计时（为2），倒计时开始前先释放一波叭（等待队列里的超过两楼的都可以放掉），倒计时结束进入maintain函数，释放所有的等待队列及电梯上的乘客。

  • 可能从刚刚move完，到了maintain这一步，这样你就需要下客，感觉maintain之后走的这两步会引发不少问题，要不干脆别走了罢，直接放了省时省力。
• 但是我得想怎么把maintain的电梯停下来，以至于让他不轮询。
  • 简易的办法是直接return。
  • 怎么留下拓展性，这里我们可以考虑可能有两个增量的方法，一个就是可以输入维修时间，那简单，直接sleep就行，害有一种就是再次输入维修完成的请求，那就可以waitRequestTable来请求。（但是最后没有用到！！！

DistanceEva的更新

• 在DistanceEva中增加了fullPasNum, speed两项指标
• 最终的参数调整出来是这样的，如下：

return (int) ((33 - distance - pasReqNum * 2.5 - passengerNum * 2.5 + fullPasNum * 1.3 - speed * 17) / (speed * speed));

• 是不是很奇怪，但它确实是最快的！
• 有同学可能会疑惑，为啥speed除去了一次平方，还要减去一个呢？
  • 这里我的主要考虑是结合我的“不强扭瓜”的分派方式，根据得分是否低于0分来决定是不是合适的，如果不给减去speed的量，那么speed就不能改变正负，只能改变大小。所以需要减去一个，实测减去一个确实更优！

结束条件的改变

• 当电梯成为生产者，那总表的end就需要另外考虑了，可能最后一条指令mantian后，电梯给总表加了人，但是此时dispatcher停了！我们需要重新考虑结束的条件。
• 最后找到了一个方法，灵感源自zbygg提醒。想到反正电梯都可以访问到总表了，我可以维护一个maintain请求的数量，在maintain来到总表的时候++，在elevator完成maintain的最后—，这样就能够保证这整个周期外，电梯不会再放人。
  • 这样，dispatcher结束的标志就是requestTable.isPasEmpty() && requestTable.isInputEnd() && requestTable.MaintainFinish()
  • 可以保证满足上述条件之后，总表中不会有新请求。

线程安全的分析

• 在这一次的迭代中，虽然迭代的力度不大，但是电梯成为了总表的生产者，这个会引起一些问题。
  • 一个类线程安全就是多个线程访问一个类的次序不影响结果。

• 为了线程安全，我们尽量不能让dispatcher直接写elevator，得让它访问他们之间的共享对象passengerQueue，所以maintain传递的考虑就是这么来的。

• 不安全问题的表征：

  • 多个修改发生覆盖，Read-modify-write
  • 读取不到最新的结果，check-then-act
• 这两种不安全在作业里都有体现，因为dispatcher的评分需要读取elevator，所以elevator其实是一个共享对象，所以我们面临一个就是dispatch的评估在跑着，elevate也在跑，但是可能在取到数据评估的时候，elevate改变了elevator对象的属性，怎么保证得到的是最新的数据？
  • 电梯类的对象也是共享对象，这里我们就要理解线程和类之间的关系了，线程并不属于类，类里面的run方法只是一个线程的入口，比如main也是一个入口而已。所以类可以被自己创造的线程访问，在我们这，电梯是一个共享对象，它被dispatch行为的线程和elevate行为的线程给共享访问了。
    • 使用读写锁，来给写的时候的读的行为加锁（因为我认为可以去阻塞dispatcher，但是绝对不能阻塞elevator）。
    • 但是如果给elevator的同步块过大的话，也会出问题，因为这样dispatcher就要被迫等elevator很长的时间sleep的时候也得等。
    • 然后就是关于我需要等分派器给电梯评完分再动？难搞，为了最终的性能考虑，毕竟这种情况本身就是少数情况（因为评分的这个尺度与电梯运行的尺度相比，差距太小了），所以我还是选择不给电梯加锁，而选择双重验证的方法。具体请看
• 然后就是requestTable这一个共享的类，对于总表这一共享对象，一个Input和六个电梯是他的输入线程，然后由dispatcher访问。分表不多说。
  • 这个线程安全问题的解决可以用synchronized块，也可以用读写锁实现单写多读的灵活控制。

歪门邪道的优化策略

弹射起步

• 这一点是yt带我大开眼界，因为电梯运行时间是根据两个arrive之间的时间来考虑的。
• 所以每个电梯的第一个arrive，它没有参照物！！！它不需要sleep！！！

影子电梯

• 这应该算得上是效率最优的分派方式了，不同于我实现的distanceEva方法，影子电梯是一种全模拟。
• 虽然我没有实现，但是我大致构想了一下实现的思路，希望能提供一种参考。
  • 首先肯定不能让模拟电梯真的sleep，你只需要给一个时间参量，一次+400就行。
  • 然后就是关于怎么读取电梯的信息。
    • 一种方法就是深克隆，但是我总感觉代价太大了，因为深克隆电梯你还得深克隆请求队列啥的。
    • 另一种方法就是只提取有效信息，就是用一张表，记录下需要在哪一层停（为了接客和下客都不用管），然后来模拟运行。

双重验证

• 这是我为了不给电梯加锁来解决这次电梯类的线程不安全问题的一种折中的办法。（我不想给电梯加锁，因为我觉得还是有点怪的）
• 所以我考虑到，对于一部电梯而言，它状态改变的周期至少是200ms，而我dispatch线程中访问电梯属性的方法的执行肯定用不了200ms。
• 所以我在访问开始前存下来电梯在此时的状态，然后在评价完返回结果之前，判断一下，电梯现在的状态与开始的状态是否一致。若不一致，则再次评价。（而且我能保证，再次评价状态肯定不会有变化，因为电梯来不及变化）
• 大致示意如下：

int curFloor = elevator.getCurFloor();
int passengerNum = elevator.getPassengerNum();
int requestNum = ElePasQueues.getPassengerNum();
//评价中。。。。。
if (!isSameEle(elevator, curFloor, passengerNum, requestNum)) {
    score = eleEvaluation.getScore(elevator, passenger);
}
return score;

时间骗子（好像管这叫量子电梯

• 这才是真的歪门邪道哇！
• 就是说，根本不用像我上面那样纠结给电梯加锁还是双重验证了。
• 因为电梯的运行时间是通过arrive之间的时间，所以不需要老老实实的sleep(moveTime)
  • 我们可以在电梯里维护一个curTime的long值，在每个操作之前，利用System获取当前时间得到stepTime，刷新一下curTime。
  • 然后你就只需要sleep(moveTime - stepTime)了！！！
• 当然为了保险，你可以给stepTime一个处罚阈值，以防移动太快的wa。