2020北航OO第二单元电梯系列

设计策略与分析

第一次作业——单部可捎带电梯

我觉得第一次作业是这三次作业中最艰难的一次作业，从0到1还是比从1到2难一些哇(●'◡'●)

今年的第一次作业实则为去年的第二次作业，既需要了解与应用多线程，又要研究电梯的调度策略，开始时让人觉得有些不知道该从哪儿思考。

设计策略

  • 类：Person（请求）、Passengers（输入）、Elevator（电梯）、Channel（调度器、采用单例模式）
public class Channel {
    private static volatile Channel channel;
    
    private Channel() {
        ......
    }
    
    public static Channel getChannel() {
        if (channel == null) {
            synchronized (Channel.class) {
                if (channel == null) {
                    channel = new Channel();
                }
            }
        }
        return channel;
    }
  • 模式：生产者消费者模式
  • 线程：输入线程Passengers（生产者），电梯线程Elevator（消费者）
  • 方案：输入线程向调度器推送请求，电梯线程向调度器索要请求，调度器的addRequest方法与getRequest方法通过sychronized加锁。
  • 捎带策略：采用ALS策略（现在看来，采用LOOK性能更好，第六次作业改为LOOK）

程序UML图

规模分析

枚举Direction：

public enum Direction {
    UP, DOWN, STOP
}

Person类：50行

属性 含义
private int id 请求的ID
private int from 请求的出发楼层
private int to 请求的到达楼层
private Direction direction 请求中的方向，由 (from-to) 的正负性决定
private boolean in 乘客是否在电梯里

方法

public Person(int id, int from, int to); //构造方法
public int getId();
public int getTo();
public int getFrom();
public boolean getIn();
public boolean hasSameDir(Direction direction); //判断该请求的方向与direction是否相同

Passengers类：40行

属性 含义
private Channel channel 共享对象：调度器

方法

public void run();

Channel类：99行

属性 含义
private static volatile Channel channel; 实现单例模式
private ArrayList waitQueue; 等待队列
private boolean end; 输入线程结束输出的标志

方法

private Channel();
public static Channel getChannel();
public void setEnd();
public boolean isEnd(); //Channel类是否完成了所有工作，即end属性为true且waitQueue中没有元素
public void endElevator(); //Passengers类调用，防止死锁，Passengers结束时唤醒电梯
public synchronized void addRequest(Person person);  //向等待队列中添加请求，并notifyAll()
public synchronized Person chooseMainReq(int floor); //从等待队列中选择主请求，如果waitQueue中没有请求，就wait()
public synchronized boolean isPeopleIn(int floor, Direction direction); //此层楼是否有人需要进入电梯
public synchronized ArrayList<Person> getPeopleIn(int floor, Direction direction);//得到此层楼进入电梯的乘客们并将其从等待队列中删除

Elevator类：200行

属性 含义
static final int movetime 电梯移动一层楼所需时间
static final int doortime 电梯开门或关门所需时间
private Channel channel 调度器
private int floor 电梯所在楼层
private Person mainReq 电梯当前主请求
private ArrayList servedPeople 电梯中的乘客
private Direction direction 电梯的方向
private boolean end 调度器channel是否完成了所有工作

方法

public Elevator();
public void setMainReq(); //按照ALS规则设置主请求
private void move(); //移动一层并打印到达信息
private boolean needOpen(); //检查门是否需要打开，即有没有乘客需要出去，有没有乘客进来
private void letPeopleOut();//让在此层楼需要出去的乘客出去并打印信息
private void letPeopleIn();//让电梯外能进来的小朋友进来并打印信息
private void openDoor(); //打印开门信息->letPeopleOut()-> sleep
private void closeDoor();//sleep->letPeopleIn()-> 打印关门信息
public void run();

采用ALS策略的run方法如下：

public void run() {
    TimableOutput.initStartTimestamp();
    //如果队列中没有乘客且channel完成任务，就结束
    while (!(channel.isEnd() == true && servedPeople.size() == 0)) {
        setMainReq();  //否则设置主请求
        if (mainReq != null) {
            pick(mainReq);
            while (servedPeople.size() != 0) {
            	move();
            	if (needOpen()) {
                	this.openDoor();
                	this.closeDoor();
                	if (servedPeople.size() != 0) {
                 		this.setMainReq();
                	}
            	}
        	}
		}
    }
}

//如果主请求不在电梯里，需要去pick他
private void pick(Person person) {
	if (channel.isEnd() == true && servedPeople.size() == 0) {
        return;
    }
    //如果这个乘客没上过电梯（不在电梯里），需要先去pick他
    if (person.getIn() == false) {
       //出发接人
        if (floor < person.getFrom()) {
            direction = Direction.UP;
        } else if (floor > person.getFrom()) {
            direction = Direction.DOWN;
        } else {
            direction = Direction.STOP;
        }
            
        while (floor != person.getFrom()) {
            move();
        }
        //到达小朋友所在楼层啦，准备去送小朋友
        if (person.getFrom() < person.getTo()) {
            direction = Direction.UP;
        } else {
            direction = Direction.DOWN;
        }
        this.openDoor();
        this.closeDoor();
    }
}

度量分析

Method ev(G) iv(G) v(G)
Elevator.run() 1 7 7
Elevator.move() 3 5 5
Elevator.pick(Person) 2 5 8
Channel.getPeopleIn(int,Direction) 1 5 5
Channel.isPeopleIn(int,Direction) 3 4 5
Passengers.run() 3 4 4
Channel.chooseMainReq(int) 1 3 5
Elevator.letPeopleIn() 1 3 3
Elevator.letPeopleOut() 1 3 3
Elevator.setMainReq() 1 3 4
Elevator.needOpen() 4 2 4
Channel.isEnd() 1 2 2
Elevator.closeDoor() 1 2 2
Elevator.getEnd() 1 2 2
Elevator.openDoor() 1 2 2
Channel.Channel() 1 1 1
Channel.addRequest(Person) 1 1 1
Channel.endElevator() 1 1 1
Channel.getChannel() 1 1 3
Channel.setEnd() 1 1 1
Elevator.Elevator() 1 1 1
MainClass.main(String[]) 1 1 1
Passengers.Passengers() 1 1 1
Person.Person(int,int,int) 1 1 2
Person.getFrom() 1 1 1
Person.getId() 1 1 1
Person.getIn() 1 1 1
Person.getTo() 1 1 1
Person.hasSameDir(Direction) 1 1 1
Person.setIn() 1 1 1
Person.toString() 1 1 1

从表格中我们可以看出，程序的复杂度和耦合性尚可忍受，我对于这次作业除调度策略以外的架构设计还比较满意。程序的可扩展性也还不错，第二次作业与第三次作业的扩展工作量与第一单元相比减少了不少。

时序图

BUG分析

我在强测中WA了一个点，原因是电梯完成任务的时间过长。也就是调度策略不佳……经过分析，我发现我的方法会出现一种尴尬情况。

例如，如果输入数据为

1-FROM-5-TO-1
2-FROM-6-TO-1
3-FROM-7-TO-1
4-FROM-8-TO-1
5-FROM-9-TO-1
6-FROM-10-TO-1

我的算法将先去五楼接乘客1然后下到一楼，再去六楼接乘客2然后下到一楼，再去七楼接乘客3然后下到一楼……总而言之因为调度算法设计的问题，电梯性能8过关，强测只拿了81分，原地爆炸。在BUG修复中，我将电梯运行策略改为了LOOK。

LOOK策略可概括为：当电梯向上（下）运行时，电梯内所有乘客都已经到达目的地，但上面（下面）楼层仍有请求，电梯仍需继续向上（下）运行。

改动后的Channel类如下：

属性 含义
private static volatile Channel channel; 实现单例模式
private ArrayList waitQueue; 等待队列
private boolean end; 输入线程结束输出的标志

方法

private Channel();
public static Channel getChannel();
public void setEnd();
public boolean isEnd(); //Channel类是否完成了所有工作，即end属性为true且waitQueue中没有元素
public void endElevator(); //Passengers类调用，防止死锁，Passengers结束时唤醒电梯
public synchronized void addRequest(Person person);  //向等待队列中添加请求，并notifyAll()
public synchronized boolean isPeopleIn(int floor, Direction direction); //此层楼是否有人需要进入电梯
public synchronized ArrayList<Person> getPeopleIn(int floor, Direction direction);//得到此层楼进入电梯的乘客们并将其从等待队列中删除
public synchronized Direction getDirection(int floor); //当电梯内没有乘客时，得到电梯的运行方向
public boolean hasPassenger(Direction direction, int floor); //判断在电梯运行方向direction上是否还有请求

Elevator中采用LOOK策略的run方法如下：

 	public void run() {
        //如果电梯中没有乘客且channel完成任务，就结束
        while (!(channel.isEnd() == true && servedPeople.size() == 0)) {
            if (direction == Direction.STOP) {
                while (servedPeople.size() == 0 &&
                        !channel.hasPassenger(Direction.STOP, floor, parkFloors)) {
                    synchronized (this) {
                        if (channel.isEnd() && servedPeople.size() == 0) {
                            return;
                        }
                        try {
                            this.wait(5L);
                        } catch (InterruptedException e) {
                            e.printStackTrace();
                        }
                    }
                }
                direction = channel.getDirection(floor, parkFloors);
            }
            else {
                if (needOpen()) {
                    openDoor();
                    closeDoor();
                }
                //上面或者下面还有人吗
                if (servedPeople.size() != 0) {
                    move();
                } else if (channel.hasPassenger(direction, floor, parkFloors)
                            && servedPeople.size() < capcity) {
                    move();
                } else {
                    direction = Direction.STOP;
                }
            }
        }
    }

hack情况

人工劳作，dbq我依然没有评测机，但房间中两个同学出现了死锁现象。以及一名同学与我的调度策略类似而导致的WA。

第二次作业——多部相同可捎带电梯

开始时可以运行1-5台电梯，增加了电梯容量的限制。

设计策略

与上次作业相比，仅在Elevator类中增加了容量限制，并在InputThread类中启动多部电梯。

  • 类：Person（请求）、InputThread（输入）、Elevator（电梯）、Channel（调度器）
  • 模式：生产者消费者模式
  • 线程：InputThread（生产者），n个电梯线程Elevator（消费者）
  • 方案：输入线程向调度器推送请求，电梯线程向调度器索要请求，调度器的addRequest方法与getRequest方法通过sychronized加锁。
  • 捎带策略：加入容量限制的LOOK策略
  • 请求分派策略：负责按要求启动多部电梯，多部电梯自力更生、自由竞争。唯一的问题是乘客比较吃香，当乘客比较少时，多部电梯会朝着同一名乘客狂奔。但性能还说得过去。

程序UML图

规模分析

各个类与第一次作业差别不大，各个类的规模尚算合理。

Person类：43行

属性 含义
private int id 请求的ID
private int from 请求的出发楼层
private int to 请求的到达楼层
private Direction direction 请求中的方向，由 (from-to) 的正负性决定

方法

public Person(int id, int from, int to); //构造方法
public int getId();
public int getTo();
public int getFrom();
public boolean hasSameDir(Direction direction); //判断该请求的方向与direction是否相同

InputThread类：42行

属性 含义
private Channel channel 共享对象：调度器

方法

public void run(); //负责读取电梯数目与读取请求

在输入类中实现电梯的开启：

numOfElevator = elevatorInput.getElevatorNum();
for (int i = 1; i <= numOfElevator; i++) {
	Elevator elevator = new Elevator(i);
	elevator.start();
}

Channel类：136行

属性 含义
private static volatile Channel channel; 实现单例模式
private ArrayList waitQueue; 等待队列
private boolean end; 输入线程结束输出的标志

方法

与第一次作业的区别在于isPeopleIn()与getPeopleIn()方法增加了表示电梯剩余容量的参数leftseat。

private Channel();
public static Channel getChannel();
public void setEnd();
public boolean isEnd(); //Channel类是否完成了所有工作，即end属性为true且waitQueue中没有元素
public void endElevator(); //Passengers类调用，防止死锁，Passengers结束时唤醒电梯
public synchronized void addRequest(Person person);  //向等待队列中添加请求，并notifyAll()
public synchronized boolean isPeopleIn(int floor, Direction direction, int leftseat); //此层楼是否有人需要进入电梯,leftseat表示电梯里的空位
public synchronized ArrayList<Person> getPeopleIn(int floor, Direction direction, int leftseat);//得到此层楼进入电梯的乘客们并将其从等待队列中删除
public synchronized Direction getDirection(int floor); //当电梯内没有乘客时，得到电梯的运行方向
public boolean hasPassenger(Direction direction, int floor); //判断在电梯运行方向direction上是否还有请求

Elevator类：166行

属性 含义
static final int movetime 电梯移动一层楼所需时间
static final int doortime 电梯开门或关门所需时间
private Channel channel 调度器
private int floor 电梯所在楼层
private String name 电梯的名称
private ArrayList servedPeople 电梯中的乘客
private Direction direction 电梯的方向
static final int capacity 电梯的容量

方法

public Elevator(String name);
private void move(); //移动一层并打印到达信息
private boolean needOpen(); //检查门是否需要打开，即有没有乘客需要出去，有没有乘客进来
private void letPeopleOut();//让在此层楼需要出去的乘客出去并打印信息
private void letPeopleIn();//让电梯外能进来的小朋友进来并打印信息
private void openDoor(); //打印开门信息->letPeopleOut()-> sleep
private void closeDoor();//sleep->letPeopleIn()-> 打印关门信息
public void run();

度量分析

Method ev(G) iv(G) v(G)
Channel.Channel() 1 1 1
Channel.addRequest(Person) 1 1 1
Channel.endElevator() 1 1 1
Channel.getChannel() 1 1 3
Channel.getDirection(int) 3 6 10
Channel.getPeopleIn(int,Direction,int) 3 6 7
Channel.hasPassenger(Direction,int) 7 5 7
Channel.isEnd() 1 2 2
Channel.isPeopleIn(int,Direction) 3 4 5
Channel.setEnd() 1 1 1
Elevator.Elevator(int) 2 2 7
Elevator.closeDoor() 1 2 2
Elevator.letPeopleIn() 1 3 3
Elevator.letPeopleOut() 1 3 3
Elevator.move() 3 5 7
Elevator.needOpen() 2 3 6
Elevator.openDoor() 1 2 2
Elevator.run() 1 8 8
InputThread.InputThread() 1 1 1
InputThread.getNumOfElevator() 1 1 1
InputThread.run() 3 7 7
MainClass.main(String[]) 1 1 1
Person.Person(int,int,int) 1 1 2
Person.getDirection() 1 1 1
Person.getFrom() 1 1 1
Person.getId() 1 1 1
Person.getIn() 1 1 1
Person.getTo() 1 1 1
Person.hasSameDir(Direction) 1 1 1
Person.setIn() 1 1 1
Person.toString() 1 1 1

BUG分析

本次作业强测与互测均未发现bug。

hack策略

room中仅有一名同学中刀，在执行完指令后线程没有自行结束。由于是线程安全问题，提交两次才成功hack一次。

第三次作业——多部不同可捎带电梯

可以动态开电梯，几部电梯的属性不同，且停靠楼层不同。

设计策略

  • 类：Person（请求）、InputThread（输入）、Elevator（电梯）、Channel（调度器）
  • 模式：生产者消费者模式
  • 线程：InputThread（生产者），n个电梯线程Elevator（既是生产者也是消费者）
  • 方案：输入线程向调度器推送请求，电梯线程向调度器索要请求，调度器的addRequest方法与getRequest方法通过sychronized加锁。
  • 捎带策略：加入容量限制的LOOK策略。
image-20200416202234976
  • 换乘策略：在Person类中引入transferFloor，如果不需要换乘，transferFloor等于from。首先，能不换乘就不换乘。并且，经过分析可得，1层与15层为万能楼层，并且所有乘客最多通过一次换乘即可到达目的地，根据乘客的from楼层与to楼层即可得到换乘楼层（1层、5层、15层）。
    • 以 (from>to) 的情况为例
from to transferFloor
20-16 2-14 15
4-14的偶数层 3 5
4-14的偶数层 -3 1
3 2、-1、-2、-3 1
2 -3 1

程序UML图

规模分析

Person类：122行

属性 含义
private int id 请求的ID
private int from 请求的出发楼层
private int to 请求的到达楼层
private Direction direction 请求中的方向，由 (from-to) 的正负性决定
private boolean transfer 是否需要换乘，默认为false
private int transferFloor 换乘楼层
private Direction directionBefore 换乘前的方向
private Direction directionAfter 换成后的方向

方法

public Person(int id, int from, int to); //构造方法
public int getId();
public int getTo();//返回此人最终目的地
public int getTarget();//返回此人现在的目的地，如果换乘前，为换乘楼层，否则为最终目标楼层
public int getFrom();
public boolean needTransfer(); //此人是否需要换乘
public Direction getDirection(); //此人现在的方向，如果换乘前，为directionBefore，换乘后为directionAfter
public boolean hasSameDir(Direction direction); //判断该请求的方向与direction是否相同
public void transferDone();//将换乘标志设置为false，from设置为transferFloor

InputThread类：45行

属性 含义
private Channel channel 共享对象：调度器

方法

public void run(); //负责读取电梯数目与读取请求

Channel类：139行

属性 含义
private static volatile Channel channel; 实现单例模式
private ArrayList waitQueue; 等待队列
private boolean end; 输入线程结束输出的标志
private ArrayList transferringQueue; 正处于换乘前半段的乘客

方法

与第二次作业的区别在于isPeopleIn()与getPeopleIn()方法增加了表示电梯可停靠楼层的参数parkFloors。并在一些方法中增加了当前楼层是否在parkFloors中，以及请求的from与当前目标楼层（to或者transferFloor）是否在parkFloors中的判断。

private Channel();
public static Channel getChannel();
public void setEnd();
public boolean isEnd(); //waitQueue与transferringQueue中均没有元素且end为true时标志着Channel类完成了工作。
public void endElevator(); //InputThread类调用，防止死锁，InputThread类结束时唤醒所有电梯
public synchronized void addRequest(Person person);  //InputThread类调用向等待队列中添加请求
public synchronized void addTransfer(Person person);  //Elevator类调用向等待队列waitQueue与换乘队列transferringQueue中添加请求
public synchronized boolean isPeopleIn(int floor, Direction direction, int leftseat, ArrayList<Integer> parkFloors); //此层楼是否有人需要进入电梯,leftseat表示电梯里的空位，parkFloors表示该电梯的停靠楼层
public synchronized ArrayList<Person> getPeopleIn(int floor, Direction direction, int leftseat, ArrayList<Integer> parkFloors);//得到此层楼进入电梯的乘客们并将其从等待队列中删除
public synchronized Direction getDirection(int floor, ArrayList<Integer> parkFloors); //当电梯内没有乘客时，得到电梯的运行方向
public boolean hasPassenger(Direction direction, int floor， ArrayList<Integer> parkFloors); //判断在电梯运行方向direction上是否还有请求

Elevator类：231行

属性 含义
private int movetime 电梯移动一层楼所需时间
private int doortime 电梯开门或关门所需时间
private Channel channel 调度器
private int floor 电梯所在楼层
private String name 电梯的名称
private ArrayList servedPeople 电梯中的乘客
private Direction direction 电梯的方向
private int capacity 电梯的容量
private ArrayList parkFloors 电梯的停靠楼层

方法

public Elevator(String type, String name);
private void move(); //移动一层并打印到达信息
private boolean needOpen(); //检查门是否需要打开，即有没有乘客需要出去，有没有乘客进来
private void letPeopleOut();//让在此层楼需要出去的乘客出去并打印信息
private void letPeopleIn();//让电梯外能进来的小朋友进来并打印信息
private void openDoor(); //打印开门信息->letPeopleOut()-> sleep
private void closeDoor();//sleep->letPeopleIn()-> 打印关门信息
public void run();

度量分析

Method ev(G) iv(G) v(G)
Channel.Channel() 1 1 1
Channel.addRequest(Person) 1 1 1
Channel.addTransfer(Person) 1 1 1
Channel.getChannel() 1 1 3
Channel.getDirection(int,ArrayList) 5 4 7
Channel.getPeopleIn(int,Direction,int,ArrayList) 3 7 8
Channel.hasPassenger(Direction,int,ArrayList) 9 11 14
Channel.isEnd() 1 3 3
Channel.isPeopleIn(int,Direction,ArrayList) 3 5 6
Channel.setEnd() 1 1 1
Elevator.Elevator(String,String) 2 2 5
Elevator.closeDoor() 1 2 2
Elevator.letPeopleIn() 1 3 3
Elevator.letPeopleOut() 1 6 6
Elevator.move() 3 5 7
Elevator.needOpen() 3 3 7
Elevator.openDoor() 1 2 2
Elevator.run() 5 12 13
InputThread.InputThread(String) 1 1 1
InputThread.run() 3 6 6
MainClass.main(String[]) 1 1 1
Person.Person(int,int,int) 1 1 36
Person.getDirection() 2 1 2
Person.getFrom() 1 1 1
Person.getId() 1 1 1
Person.getTarget() 1 1 2
Person.getTo() 1 1 1
Person.getTransferFloor() 1 1 1
Person.hasSameDir(Direction) 2 1 2
Person.needTransfer() 1 1 1
Person.transferDone() 1 1 1
SafeOutput.println(String) 1 1 1

虽然Channel的hasPassenger方法复杂度比较高，但逻辑还比较清晰

    public synchronized boolean hasPassenger(Direction direction, int floor,ArrayList<Integer> parkFloors) {
        if (direction == Direction.UP) {
            for (Person person : waitQueue) {
                //如果上面还有人,且from楼层与target楼层可直达
                if (person.getFrom() > floor &&
                        parkFloors.contains(person.getTarget()) &&
                        parkFloors.contains(person.getFrom())) {
                    return true;
                }
            }
        }
        else if (direction == Direction.DOWN) {
            for (Person person : waitQueue) {
                //如果下面还有人，且from楼层与target楼层可直达
                if (person.getFrom() < floor &&
                        parkFloors.contains(person.getTarget()) &&
                        parkFloors.contains(person.getFrom())) {
                    return true;
                }
            }
        } else {
            for (Person person : waitQueue) {
                if (parkFloors.contains(person.getTarget()) &&
                        parkFloors.contains(person.getFrom())) {
                    return true;
                }
            }
        }
        return false;
    }

Person的构造方法复杂度较高主要是因为涉及到换乘楼层的设置，if-else语句块较多。

BUG分析

中测中因对轮询的理解不当造成CTLE，修改后通过。根本原因在于对多线程上锁的机制不理解。

本次作业强测与互测均未发现bug。

hack策略

找到了一位同学新增电梯无法顺利结束的bug。

SOLID原则分析

  • 单一责任原则 (SRP）
    • 输入类仅负责读取输入并推送给调度器
    • 调度器仅负责接受输入类的请求并将请求按可捎带原则分给电梯
    • 电梯仅负责运行
  • 开放封闭原则 (OCP)
    • 程序扩展性还说得过去，从第一次作业到第二次作业再到第三次作业的迭代还算顺利。没有像第一单元那样几乎次次重构。
    • 但如果考虑到关闭一步电梯的扩展，我的架构可能无法很好解决。
  • 里氏替换原则(LSP)：未涉及继承
  • 接口分离原则(ISP)：仅有线程实现Runnable接口，或许可以考虑将多种电梯定义为同一接口Elevator。
  • 依赖倒置原则 (DIP)：未涉及继承或有意义的接口实现。

心得体会

线程安全

线程安全确实是一个大问题。首先第一次作业时，我在本地出现了死锁问题，若所有电梯都在等待新指令到来时直接^D，所有电梯都会处于wait状态。第三次作业时，轮询问题也造成了CTLE。何时结束线程也是一个非常值得考虑的问题。

设计模式

学习到了单例模式、生产者消费者模式，在实验课上学习了观察者模式和Worker-Thread模式。

个人反思

这一单元作业最让我不满意的地方就是第一次作业中的电梯调度策略，如果在编写代码之前能够与同学交流一下，性能一定能有所提升。但值得表扬的地方是，由于第一次作业的架构花了比较长的时间构思，这一单元的代码架构上的继承性比较好，后两次作业并没有特别大的改动。与同学多交流请教对作业的完成也有着非常大的帮助，感谢耐心解答问题的大佬们(●'◡'●)

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/houqingying/p/12717101.html