OS-做一个简单的shell

北航面向对象与程序设计第二单元课程作业，电梯调度器ElevatorDispatcher 1.0。
主要涉及多线程程序设计，设计模式的使用。

hw5_log

前置知识-多线程

• IDEA多线程调试，试过，感觉报用，感觉还是print输出的方法最能模拟这个多线程的运行时的状态。
  • 其实如果可以，去实现一个debug模式，输入一个标志进入debug模式（还可以有不同的debug模式），运行时输出自己想要的信息。（要不然还得自己一行一行的注释，累死，而且容易出问题，忘删了交上去浪费一次机会！
• t1.yield(), t1.sleep(), t2.join(), o.wait(), o.notifiy()都是调度策略，不要轮询
• 如果共享对象不发出调度指令，我们需要线程互斥控制，synchronized关键字，每一个同步控制块都有一把锁，拿到锁的线程才能进控制块。
  • 对于这里，如果刚刚学多线程，会有点迷惑，这个块有什么用，我觉得可以带着这个疑问看下去，理会区分类和线程之间的差别。
  • static于非static的区别，锁对象和锁类的区别。
  • 方法级的同步控制与obj的局部代码的同步块，其实是一样的，只是说把synchronized块放到方法上的话，同步块就是一整个方法。
• 直接调用run与线程调度执行run的区别，阅读Thread类的源码与Runable的源码，发现Runable十分简单粗暴的留了个run的方法，所以区别在于，直接调用run方法其实只相当于执行了一个函数，并没有创建一个线程，创建线程需要Thread类的start方法。所以一般不要去直接调用run方法。
• 生产者模式，观察者模式，这是两种比较典型的多线程设计模式，这个可以后面说。
  • 我们的电梯其实是一种很明显的生产消费的模式，输入线程是需求的生产者，电梯是需求的消费者，是一种一对多的服务，当然没那么简单，这个后面再说。

需求分析

• 需要实现一个电梯调度的系统（电梯的属性固定），尽可能快的完成乘客的请求
• 电梯可以有可以捎带策略，基准是ALS调度策略
  • 但是我选择大家的选择LOOK策略，因为我觉得这个方法更加能够灵活应对增加的请求，同时用户等待时间也会比较短。

• 队列和楼层之间的关系是否需要更便捷的管理？

  • 我选择分楼层管理请求队列，方便查询。

• 注意可能上了就下的极端情况（后续迭代，但是好像没有，预测失败。。。

可能用到的设计模式

• 生产者消费者模式：输入类作为生产者，任务表作为托盘，电梯作为消费者（其实并不是
• 观察者模式：（后续迭代可能会有，比如说乘客突然改变想法，但是也没有，再次预测失败呜呜呜
• 工厂模式：考虑到后续自定义电梯的实现
• 状态模式：电梯可以有好几种状态，上行下行，开门关门，满员，（故障，预测成功！！！
• 策略模式：主要考虑到，电梯策略的选择，与分派器策略的选择
• 单例模式
• 责任链模式
• master-worker模式

具体实现

• 生产消费模型：

  • 实现输入接口
  • 建立请求表类
    • 建立请求类（即passenger）
  • 建立调度器类（这个不是必须的，但是后续迭代中逐渐变得必须了起来
  • 建立电梯的类
  • 实现输出接口

• 设置策略类

  • 电梯策略
  • 调度器策略

• 为了统一代码的风格，提高效率，我这里提前对代码进行几点规定：

  • 设锁的房内只提供对共享资源读写的能力，其余不设锁
  • 只在取不到需求的时候wait，而且是在需求表的方法中wait，所以在Dispatcher与Elevator的类中不需要wait，让共享对象自己来做好自己的管理
  • 只在需求表这一个共享对象中设锁（其实电梯也是共享对象，但综合考虑下来，不设锁的效率更优。

• 在类的设置上，我遵循开闭原则，面向于接口编程，而不是面向于实现，这样能够让我轻松的迭代，所以我采取Strategy、Evaluation两个接口实现（采取策略模式，同时又方便我随时转换调度器评价方式与电梯运行策略

  • 第一次作业就先不利用Elevator接口了，后面有横向电梯再用（但是没有，呜呜呜。。。

• 上面是任务清单，可能比较的模糊，可以看下面的架构~

整体架构与uml“类”类图

• 在总体上，我实现了以生产者消费者模型为主体的架构，架构示意图大体如下（仅表意，不是严格的类图）：
  

整体架构模式

• 我们可以看到，输入线程和dispatch线程共享一个Request的对象（我们后续称之为总表），这是一个生产消费的模型。而且dispatch线程又分别和每一个电梯的运行线程共享一个Request的对象（称为分表），这也分别是生产消费的模型。dispatch线程既是总表的消费者，又是分表的生产者。
  
• 然后我们可以看到，在课上有同学提到的master-worker模型，在这里也有体现，我们可以看到，dispatcher统一管理所有的电梯，它是master将任务分派给不同的worker，像是一个分布式的计算集群（当然我们这里是服务处理集群）。
• 但这里需要重点辨析的一点是，在这里电梯对象存在线程不安全的问题，是一个由check-then-act引起的读取不到最新结果的问题，因为dispather需要对每部电梯的运行状态进行评估分派，所以需要读电梯的数据，但与此同时，电梯的数据是在改变的，所以线程不安全。也就是说，这里电梯这个类的对象，是电梯线程和dispatch线程的共享对象！！！
  • 说到这就不得不提一嘴线程和类之间的关系了，这一点助教在课上有提过一下，我的理解是线程并不属于类，类里面的run方法只是一个线程的入口，像main也是一个入口而已。所以类可以被自己创造的线程访问，在我们这，电梯是一个共享对象，它被dispatch行为的线程和elevate行为的线程给共享访问了。
  • 我怎么解决这个问题呢，嘿嘿，我第一作业没有解决这个问题（摆手，因为我觉得给电梯加锁的行为不太可取，它会显式的阻塞电梯线程的运行，会拖慢我的速度，而且我也是第二次作业才发现这个问题）
    • 剧透一点，在第二次迭代的博客里，我会重点介绍一些歪门邪道，能够解决这个问题。

再剧透一点，这其实很适用于第二次的迭代，因为电梯要maintain把请求放回去，其实也就是电梯线程也变成了总表的生产者（图中标为new的曲线），这又增加了一层生产消费的模型。

策略模式的应用

• 我们直观上来看，有两个地方需要用到策略：分派策略，运行策略。
• 所以我们可以使用策略模式，策略模式中，需要用到策略的对象拥有一个策略的属性，这个属性是一个策略的接口，然后具体的策略我们只需要用一个策略类去实现这样一个接口，而且我们注意到，这个接口甚至只需要一个方法，就是getStrategy(...)。后续需要变更方法或者增量开发的时候只需要将接口的实现切换就行。
• 与之对比的是，用不同具体方法的分派器的类去继承分派器的类，读者可以自行体会一下这两者之间的差异，体会一下面向接口编程的优点。
• 如下图，在我们这次作业中电梯可以有运行策略，分派器可以有分派策略：
  

所以你甚至可以设想给不同的电梯装载不同的策略，然后调度的时候结合不同的策略的特点来调度。或者说在不同的情况下，应用分派器相应的不同的分派策略。十分的灵活十分的好玩，而且迭代加功能的时候，面向接口有不同的实现就行了。（但是我没有实现，懒orz）

电梯运行策略的选择——LOOK

• 这里主要用的是LOOK的策略
  • LOOK需要考虑前面的请求也是和运行同一方向的
  • 但其实其他同学（包括往届学长的博客里对LOOK的策略解读的比较的全面了，所以我就不对具体策略进行解读了，下面是伪代码的实现（我觉得这样可能更加直观，每走一步获取一下strategy

public class LookStrategy implements Strategy {
    @Override
    public Status getStrategy(Elevator elevator) {
        //判断电梯是否需要开门
        if (canOpenForIn() || canOpenForOut())
            return OPEN;
        //判断电梯是否有人·
        if (!elevator.isEmpty()) {
            return MOVE;
        } else {
            //请求队列中是否有人
            if (!passengerQueue.isEmpty()) {
                //人在原方向还是反方向
                if (pasInSameDir())
                    return MOVE;
                else
                    return REVERSE;
            } else {
                //请求队列输入是否结束
                if (passengerQueue.isEnd())
                    return END;
                else
                    return WAIT;
            }

        }
    }
}

• 对满员状态的处理：应该不停，不要浪费时间
• 用ArrayList< ArrayList< Passenger > >来将所有楼层一样的乘客放到一起，在RequestTable中把同一fromFloor的乘客放在一起，在Elevator中，把toFloor一样的乘客放在一起。他们是同一类人，方便索引。

调度器的实现

• 我应该设置一个对全局展开调度的东西，毕竟我们是六个电梯共享相同的需求，为了用电量的考虑，我每个请求只能让一个电梯去动！
  • 感觉自由竞争调度不太妥当，会使其浪费电量，最后发现自由竞争其实可以拿到90+的分数，但是不会太高。
  • 所以我的策略是，在电梯和需求表之间插上一个Dispatcher，Dispatcher将一张大的需求表分成小部分分派给各个电梯，各个电梯之间独立运行（不知道其他电梯是个什么状态），
  • 调度器分配出去就不能反悔了（所以可以在总表中删除了，如果可以反悔，那不就是自由竞争嘛！）
• 初步调度策略是最近的一个，如果反向就加上距离
  • 但是有弊端，就是全都同一时间输入，更有甚者都在同一个楼层向上走，那会乱
    • 所以解决方法，必需加入对于人数的考虑，人满了就不接了，或者说哪个人少让哪个去
  • 然后还可以考虑等待队列的长度，等的人越多就分数低
  • 所以综合考虑下来，形成了我的DistanceEva的评价接口的实现。
  • 下面细说：

调度策略的选择——DistanceEva(自创偷懒评价)

• 与其说是一种Distance评价法，其实不如说是一种综合评价法，因为我后续加入了许许多多的指标，在调参之后，能够达到接近影子电梯（这个第二次博客有谈到）的水平。
• 我假设电梯是一个最高层（或者最底层）到它现在要到的最底层（或者最高层）的一个来回工作的圈，计算还要走多少楼，电梯才能接到这个乘客
  • 比如，我在7楼要下行，但是这个电梯现在在6楼下行到2楼，那它现在就需要先到2楼，再上行到11楼，再下行到7楼，才能接到我。算出来Distance是4+9+4=17。
• 然后考虑到几个会影响电梯的评分的指标，经过调参之后，最后评价方式变成了这样：

return (int) (22 - distance - elevator.getPassengerQueue().getPassengerNum() * 2.2 - elevator.getPassengerNum() * 2);

强扭的瓜不甜，你可以找到更好的(调度的考虑)

• 但是回到了最开始的一个的问题，如果一下子输入许许多多的请求，dispatcher就把它们全都分配出去了！然后发现随着电梯的运行，有些电梯装不下了，有的乘客可能一开始遇上的不是对的电梯。
  • 所以，强扭的瓜不甜。如果每个电梯的评价都不是很高，那我们就先不分配，让它留在总表里，等待分配的时机。
  • 然后，递归下去查另一个人的情况。
• 所以我们必须知道分配有没有成功，如果一个人都没分配出去，说明现在所有电梯都不适合增加任何一个请求。
  • 所以dispatch的方法需要带上返回值！
  • 然后如果返回false，需要阻塞，避免轮询。
    • 可以通过wait电梯的同步块的请求，但是我没有给电梯设同步块。
    • 所以我是简单的sleep，我发现sleep(50)的时候，效果最好。
• 下面是dispatch递归分配结构的伪代码实现

boolean dispatch() {
    Passenger passenger = requestTable.getAndRemovePas();
    if (passenger == null)
        return false;
    bestEle = getBestEle(passenger);
    //没有合适的就返回null,继续递归寻找下一个，return后再把现在那个给加回去
    if (bestEle == null) {
        isDisped = dispatch();
        requestTable.add(passenger);
        return isDised;
    }
    bestElePasQueue.add(passenger);
    return true;
}

最后最需要注意的——结束条件

• 第一次作业的结束条件还比较的简单，但后续几次迭代的时候，如果发现电梯死锁了，电梯有请求没有处理，分派器有请求没有分配出去等等问题，那就要好好思考一下是不是提早结束了，或者还没结束。
• 给请求队列加上passengerNum的属性，这样判断empty就不需要遍历了。

一些未实现的优化思路

• 单例模式实现一些东西（规范！
• 用读写锁灵活实现互斥与同步控制
• 增加调度及运行策略（灵活选择！