概述

本单元主要学习了JAVA对象的运行机制和多线程的实现以及设计模式的知识，共有三次作业。第一次作业要求实现模拟单部多线程傻瓜调度电梯的运行，由于只是单部电梯且为傻瓜调度，一次只执行一个请求，和单线程区别不是很大，所以主要涉及的知识点为线程创建、线程运行和线程交互。第二次作业要求实现模拟单部多线程可捎带电梯的运行，虽然还是单部电梯，但是加入了可捎带的功能，这就意味着电梯这个线程也要大量访问队列共享对象，从而就衍生了线程访问的安全问题，主要涉及的知识点为线程的安全设计。第三次作业要求实现模拟多部多线程智能电梯的运行，这次作业虽然是多部电梯，但是主要还是由单部电梯扩展而来，但是多部电梯线程的管理比较复杂，因此引进了设计模式的概念，主要涉及的知识点为线程的设计模式。

三次作业知识点回顾

线程创建、运行和交互

JAVA语言提供了对象化线程支持，可以通过继承Thread类或者实现Runnable接口，实例化可运行线程的对象，就完成了线程的创建。

//extends the Thread Classpublic class Elevator extends Thread{  public void run(){  //the entry of Thread,like the main function of java progress           this.go();   }}//implement the Runnable interface public class Elevator implements Runnable{  public void run(){     this.go();  }  }

完成线程执行入口方法后，实例化线程对象，再通过调用start方法即可实现线程的运行。

//extends the Thread ClassThread t = new Elevator(...);//or Elevator t = new Elevator(...);t.start();//implement the Runnable interfaceThread t = new Thread(new Elevator(...));t.start();//因为这个仅仅是实现了接口函数，并不是继承Thread类，所以要构建线程对象

在多线程中不可避免的要产生交互如调度交互和数据交互。调度交互有直接调度交互，如启动start、结束stop、睡眠sleep、暂停yield，以及间接调度交互，即通过共享对象实现wait、notify、notifyAll。同时当多个线程同时访问共享资源时，就产生了数据交互，进而衍生出共享对象的访问控制问题。

其中值得注意的是wait是指一个已经得到同步锁的线程，自己暂时让出该同步锁，以便其他正在等待此锁的线程能够得到同步锁继续运行。而只有其他线程调用了notify方法（notify方法不释放锁，只是告知调用过wait方法的线程可以重新参与锁的竞争，得到锁之后从wait的下一条语句继续执行），可以理解成wait会释放锁，而notify不会释放锁，而是让其他调用wait方法的线程参与锁的竞争，另外wait是指一个已经得到同步锁的线程的潜台词是，wait和notifyAll方法必须包含在一个synchronized之中或者必须得到锁，否则会出现难以预料的错误。这样就不难理解为什么多个线程想调用synchronized method(){...wait();..}时，不会因为wait()产生的死等待问题了。

在多线程中，线程通过构造器获得与其他线程的共享对象。而对于共享数据的访问控制，一般采取互斥控制，即任何时刻只能有一个线程获得访问或执行共享数据的权限，可以采取两种方式synchronized(obj) {…} ：任意时刻只允许一个线程对对象obj进行操作，synchronized method(…){…}，任意时刻只允许一个线程调用方法method。

线程安全的设计

由于线程的调度和执行具有不确定性，在多个线程访问共享对象时，很容易出现线程安全问题。

一般来说，线程不安全是因为存在竞争条件，即一个计算的正确性依赖于多个线程之间的相对执行次序。常见的计算模式有Read-modify-write和check-then-act，很容易出现线程安全问题，因为这两种模式的计算过程需要多步完成，无法保证计算的原子性。此时我们可以通过同步控制来避免多个线程共享对象而产生的计算结果被覆盖、读取过时的结果、相互等待——死锁、对象状态被破坏、计算结果不能被其他线程及时获得等问题。

同时，对象发布也可能会造成线程不安全的问题。如果需要访问对象，必须处在严密监控之中。

如果要确保线程安全，可以使用不可变对象，如使用final强制限制对属性成员的更改。使用可变对象时，要保证操作的原子性，以及作为共享对象时要严密监控，也要注意读写访问的互斥控制。

共享对象访问的关键问题是读写访问冲突和状态更新延迟。可以通过锁机制解决共享对象的访问问题。线程安全的本质就是对一块内存空间的访问受限或者受到控制，确保不会出现安全问题。synchronized是一种控制访问机制。JAVA为每个对象默认提供了锁机制，可以控制线程的共享访问行为。常见的synchronized的方式有：

//同步普通方法public class Bank{    private int money;    private String name;    public Bank(String name, int money){        this.name = name;        this.money = money;          }          public synchronized void deposit (int m){        money += m;    }    public synchronized void boolean withdraw(int m){        if(money > m){             money -=m;             return true;                   }else{             return false;         }    }    public String getName(){        return name;    }}//同步静态方法public class StaticBank{    private int money;    private String name;    public StaticBank(String name, int money){        this.name = name;        this.money = money;          }          public synchronized static void deposit (int m){        money += m;    }    public synchronized static boolean withdraw(int m){        if(money > m){             money -=m;             return true;                   }else{             return false;         }    }    public String getName(){        return name;    }}

对于以上的Bank类和StaticBank类，如果我们分别实例化Bank bank1,bank2;以及StaticBank staticbank1,staticbank2;并把bank1和bank2放在t1和t2线程中使用，staticbank1和staticbank2放在st1和st2线程中使用。当bank1和bank2同时想调用withdraw方法时，是不会互斥的，而staticbank1和staticbank2想同时调用withdraw方法时，会产生互斥，只能由一个线程使用。也就是说，synchronized如果只同步普通方法，那么在不同线程的不同实例中，线程可调用对应的实例的方法而不互斥，但是synchronized同步静态方法的话，在不同线程的不同实例中，线程调用对应的实例的方法会产生互斥，一次只能由一个线程调用。事实上，同步普通方法锁只能作用于一个实例，不同实例拥有独自的锁，因此同步普通方法应用于单例模式。同步静态方法作用于这个类产生的所有实例，所有实例都拥有共同的一个锁，不管有多少实例，一次只能有一个线程调用该方法。

//同步类，和同步静态方法一样,例如上述的StaticBank的方法可以写成如下public void deposit(int m){    synchronized(this.getClass){    //synchronized(StaticBank.class)        money += m;      }}

//同步this实例，表示锁住整个当前的对象实例，例如上面Bank同步普通方法可以写成如下public void deposit(int m){    synchronized(this){        money += m;    }}public boolean withdraw(int m){    synchronized(this){        if(money > m){            money -= m;            return true;        }else{            return false;        }    }}

如果锁住银行对象的话，和上述锁住方法一样，都是一个客户在deposit的时候，另一个客户想withdraw只能等前一个客户deposit完毕释放对象锁。因为synchronized锁住方法实际上是锁住调用该方法的对象。

//同步对象实例,上述同步this实例是同步这个类构造的实例对象，而同步对象实例可以同步除这个类以外的其他对象，比如在这个银行的例子中可以同步moneypublic boolean withdraw(int m){    synchronized(money){        if(money > m){            money -= m;            return true;        }else{             return false;        }    }}public void deposit(int m){    synchronized(money){        money += m;    }}

在这里锁住money对象其效果和上述锁住this对象相同。

说了那么多，总结起来就是，如果是单例共享对象模式下，对每一个方法加上synchronized即同步普通方法是线程安全的。

线程设计模式：Producer-Consumer and WorkerThread

从本质上来说，这两种模式没什么区别。它们的架构分别如图

 

 从这两个图中我们可以看到，这两种设计模式的架构是十分类似的，clientThread相当于producer,workerThread相当于customer。但是worker thread的channel中多了一个threadPool属性和startWorkers方法，也就是说相比于Producer-Customer模式，worker thread模式中的channel类多了管控worker线程的功能。也就是说在P-C模式中，生产者是生产者，消费者是消费者，生产者可以不断生产而不考虑消费者的情况，而消费者可以随时消费，有产品就消费，无产品就撤退，也不用怎么管生产者的生产情况，二者几乎独立。但是在W-T模式中，Channel会根据委托人线程的情况决定是否调用工人线程，工人必须得在有请求的情况下才进行调用，无请求时则停止工作，两种线程之间具有联系。

三次作业分析

第一次作业

架构分析

本次作业主要有四个类：

Main：包含main函数，为程序入口

Request：生产者，用来从标准输入中读取请求信息和请求终止信息，并放到共享队列中。

PerQueue：共享对象，用来存储请求队列和请求终止标志。

Elevator：消费者，用来从共享队列中提取请求并执行。

实现细节

本次作业我采用了生产者和消费者的模式。

生产者线程Request不断向请求队列中放入请求信息，当读完请求信息时设置hasRequest标志为false。

共享对象PerQueue包含两个属性perQueue（ArrayBlockingQueue）和hasRequest（boolean），perQueue用来存储请求信息，更多地对应put和take方法，由于ArrayBlockingQueue是阻塞队列，在使用take方法时如果队列为空会产生阻塞，由于在写第一次作业时不甚理解ArrayBlocking的具体实现以及使用wait、notifyAll等线程交互的方法，所以在电梯线程中，我采用了轮询的方式，判断队列不为空时才使用take方法取请求运行，避免阻塞；hasRequest用来判断还有无输入，如果没有输入且请求队列为空的话让电梯线程终止。

消费者线程Elevator采用轮询的方式，判断如果队列不空就取请求，如果队列为空且输入已经结束则退出线程。

BUG分析

本次作业比较简单，自己的并未出现BUG，但是互测屋内有人的电梯会因为线程控制不当出现提前终止的BUG。

SOLID分析

Single Responsibility Principle

 由于本次作业比较简单，实现了每个类或方法都有一个明确的职责。

Open Close Principle

由于这是第一次作业，所以未考虑过多的扩展功能，导致在第二次作业的时候很多地方进行了改正。

Liskov Substitution Principle

本次作业未使用过多的继承，较好地实现了LSP

Interface Segregation Principle

本次作业未使用接口。

Dependency Inversion Principle

依赖倒置没问题。

第二次作业

架构分析

本次作业和第一次作业总体上架构差别不大，主要有四个类：

Main：包含main函数，为程序入口

Request：生产者，用来从标准输入中读取请求信息和请求终止信息，并放到共享队列中。

PerQueue：共享对象，用来存储请求队列和请求终止标志。

Elevator：消费者，用来从共享队列中提取请求并执行。

实现细节

第二次作业和第一次作业在实现上多了一些细节。其中最重要的是，由于本次作业不能暴力轮询，得使用wait和nitifyAll方法进行线程的交互，所以相比于第一次作业，对于电梯线程，当请求队列为空时，wait。对于请求产生线程，当执行add或者setHasRequest操作时，执行notifyAll。这样当电梯取不到请求时会进入阻塞状态，而当产生请求时电梯唤醒执行请求，当请求终止输入时，唤醒电梯线程关闭线程。

其次，由于本次作业要求电梯能够捎带人，且增加了负数楼层，电梯的运行细节增加了许多。比如增加了Vector<PersonRequest>passenger模拟当前电梯乘坐人员，增加boolean doorStatus来判断当前电梯门的状态避免重复开关。以及在moveFloor时，如果碰到0层要再加1层或者减1层。其中电梯运行增加的最重要的细节便是捎带功能，要实现捎带功能，电梯增加了上下行的状态status，然后还得判断请求队列中的请求的运行方向是否符合当前电梯的运行状态，如果符合，在到达from楼层时就把人塞进电梯，到达to楼层时就把人丢出电梯即可。同时电梯增加了捎带要求而增加上下行状态后，上下行状态的改变也值得注意，否则会出现上不去下不来等情况。

BUG分析

本次作业较第一次作业多了一个捎带的要求，架构方面变动不大，只是在电梯运行的时候要增加一些方法。只要架构正确且线程安全，加上捎带算法正确的话，就不会出现BUG。但是优化算法太差的话会产生REAL_TIME_ERROR。我这次作业依然没有BUG，互测屋里面出现的BUG都是捎带算法不太合理而导致的超时。

SOLID分析

Single Responsibility Principle

 这次作业大致上实现了SRP原则，只有Elevator类里面的运行方法还比较臃肿，可以把更改方向的代码段另开一个功能方法setStatus()（第三次作业改进了）。

public void run(PersonRequest request) throws InterruptedException {        // TimableOutput.println("run ele");        int from = request.getFromFloor();        int to = request.getToFloor();        this.setStatus(this.curFloor, from);        boolean getMain = false;        while (true) {            this.pickUp();//接到主请求之前和之后的pick            if (this.curFloor == request.getFromFloor() && !getMain) {                openDoor();                getMain = true;                personIn(request.getPersonId());                this.setStatus(from, to);                this.passenger.add(request);                this.pickUp();//在主请求楼层的pick            }            //TimableOutput.println(this.status);            Iterator
     
       iterator = this.passenger.iterator();            while (iterator.hasNext()) {                PersonRequest outperson = iterator.next();                if (outperson.getToFloor() == this.curFloor) {                    openDoor();                    personOut(outperson.getPersonId());                    iterator.remove();                }            }            //出人            closeDoor();            //电梯内有人才看一下有没有必要更改方向            boolean dirChange = true;            if (!this.passenger.isEmpty()) {                if (this.status == Up) {                    iterator = this.passenger.iterator();                    while (iterator.hasNext()) {                        PersonRequest request1 = iterator.next();                        if (request1.getToFloor() > this.curFloor) {                            dirChange = false;                        }                    }                } else if (this.status == Down) {                    iterator = this.passenger.iterator();                    while (iterator.hasNext()) {                        PersonRequest request1 = iterator.next();                        if (request1.getToFloor() < this.curFloor) {                            dirChange = false;                        }                    }                }                if (dirChange) {                    this.status = -this.status;                }            }            if (this.passenger.isEmpty() && getMain) {                // TimableOutput.println("break runele");                return;            }            moveFloor();        }    }
     

 

Open Close Principle

这次作业在第一次作业的基础上，Elevator对象增加了运行状态status和电梯门状态doorStatus和电梯内乘客passenger属性，使对象更加完整。以及由于添加了负数楼层moveFloor方法进行了改写。还因为实现捎带功能扩展了pickUp方法。

//第一次作业     private PerQueue perQueue;    private int curFloor;    private static final long openTime = 250;    private static final long closeTime = 250;    private static final long runTime = 500;//第二次作业    private PerQueue perQueue;    private int curFloor;    private int status;    private Vector
     
       passenger;    private boolean doorStatus;    private static final long openTime = 200;    private static final long closeTime = 200;    private static final long runTime = 400;    private static final int Up = 1;    private static final int Down = -1;    private static final int Static = 0;
     

 

Liskov Substitution Principle

本次作业未使用过多的继承，较好地实现了LSP

Interface Segregation Principle

本次作业未使用接口。

Dependency Inversion Principle

依赖倒置没问题。

第三次作业

架构分析

本次作业和第二次作业相比，主要增加了多部电梯的实现以及电梯能到达楼层的限制以及换乘的需求，由于不是很熟悉worker thread模式以及本次作业仍可以使用P-C模式实现，所以我并未采取W-T模式，主要有五个类：

Main：包含main函数，为程序入口

Request：生产者，用来从标准输入中读取请求信息和请求终止信息，并放到共享队列中。

Person：生产和消费的对象，因为本次作业要求换乘，便重写了请求类，经分析发现，本次作业一个人最多只用换乘一次就能到达目的地，所以Person对象包含id和第一次乘坐请求和第二次乘坐请求的属性，当第二次乘坐请求都为0时即为该乘客不用换乘的标志。

PerQueue：共享对象，用来存储请求队列和请求终止标志。

Elevator：消费者，用来从共享队列中提取请求并执行。

实现细节

第三次作业和第二次作业相比多了换乘的请求以及多部电梯的实现。

首先在请求产生的线程中，我定义了一个parseRequest的函数重新构造Person类，在暴力分析了506种电梯请求后，手工为每种请求分配了乘坐方案，把一个请求分成两种，一种是一个电梯可以自己跑的，也就是fromFloor和toFloor都是某部电梯能到达的楼层，一种是要两个电梯的，toFloor和fromFloor分属两部电梯，比如2到3就需要B和C。对于前一种，电梯自己抢，对于第二种，把该请求分成两步，例如2-1,1-3，这样又变成第一种的情况，让电梯自己抢。于是就把电梯请求设计成 Person{ id; firstToFloor; secondToFloor; firstFromFloor; secondFromFloor; } 再暴力分析23*22 = 506种情况，parse输入的请求变成上面这个person即可。

其次对于共享对象来说，增加了runCount和pickUpCount属性，分别用来计算当前电梯运行的数量和需要捎带的请求的数量，用来作为电梯线程结束的信号，为三个电梯提供通讯，当runCount == 0 且pickUpCount == 0 且请求输入终止时，向电梯输入null作为结束标志。然后，在共享对象的take方法中，要增加电梯合法楼层的判断，即电梯想从请求队列中获取请求，共享对象肩负起调度器的功能，比对电梯合法楼层和请求的楼层，如果匹配就把该请求划分给电梯。

最后对于电梯线程来说，由于每部电梯的运行时间和名字和合法楼层不一样，所以相对于第二次作业，把一些不变的私有属性更抽象出来，作为可变属性使用。然后其他方法较第二次作业来说变动不大。

总的来说，第三次作业比第二次作业更难的点在于电梯线程之间的通讯，由于我没有构造调度器类，所以我是通过共享对象来说实现的。

BUG分析

 本次作业只要线程安全而且调度算法不差，基本也不会产生BUG。在互测屋中，有人被hack了一次是因为暴力轮询问题，我hack别人一次是因为他的代码线程的终止出现了错误。所以在多线程问题中，线程安全应该是最值得注意的。

SOLID分析

Single Responsibility Principle

第三次作业的SRP在第二次作业的基础上有了改进，但是Elevator的运行还可以进一步分离出outPerson方法

public void run(Person request) throws InterruptedException {                this.perQueue.countAdd();                int from = request.getFirstFromFloor();        int to = request.getFirstToFloor();        this.setStatus(this.curFloor, from);        boolean getMain = false;               while (true) {            this.pickUp();//接到主请求之前和之后的pick            if (this.curFloor == from && !getMain                    && passenger.size() < passenger.capacity()) { //保证主请求未满                openDoor();                getMain = true;                personIn(request.getPersonId());                this.setStatus(from, to);                this.passenger.add(request);                this.pickUp();//在主请求楼层的pick            }                       Iterator
     
       iterator = this.passenger.iterator();            while (iterator.hasNext()) {                Person outperson = iterator.next();                if (outperson.getFirstToFloor() == curFloor && this.isLegal()) {                    openDoor();                    personOut(outperson.getPersonId());                    if (outperson.getSecondFromFloor() != 0) {                        this.perQueue.add(new Person(outperson.getPersonId(),                                outperson.getSecondFromFloor(),                                outperson.getSecondToFloor(), 0, 0));                        this.perQueue.pickUpCountSub();                    }                    iterator.remove();                }            }
     

Open Close Principle

本次作业在第二次作业的基础上，Elevator对象增加了name和legalFloor和runTime属性，以适应不同电梯的构造需求。其他的相比于第二次作业变化不大，首先在输入请求的时候构造了新的Person对象，以及在取请求时增加了判断请求是否“合法”，即能被该电梯运达，以及在出电梯的时候判断该人是否需要换乘，如果需要则重新构造Person对象放入请求队列。

Liskov Substitution Principle

无。

Interface Segregation Principle

无。

Dependency Inversion Principle

无。

分析自己程序的BUG

第二单元的三次作业无论是本地测试还是中测强测还是互测，都没有出现BUG。不过在写代码的过程中出现了BUG的状况。

第一次作业

第一次作业在写代码时，使用了ArrayBlockingQueue阻塞队列的阻塞方法take(),即如果队列为空执行take操作时会阻塞，此时就造成一开始为空队列为空而产生阻塞时，ctrl + D不会唤醒阻塞，导致RUN_TIME_ERROR。解决方法是在take之前判断了队列非空，但是造成了轮询。（后面会了wait和notifyAll方法后就改变了这种状况）

第二次作业

第二次作业在写代码时，使用了wait和notifyAll方法，但是一开始未注意将二者放在锁中，造成了难以预料的错误。以及更改了判断电梯线程结束的方式。

第三次作业

第三次作业在写代码时，需要实现几个线程之间的通讯，否则容易出现线程提前退出的情况。我采用了在共享对象PerQueue增加信号量runCount判断当前正在运行的电梯线程的数量，如果当前有电梯在运行，电梯线程不会退出，而只有当请求队列为空，请求输入终止，没有电梯运行才退出电梯线程。但由于我保留了前两次作业的电梯退出代码，导致在中测测试的时候，由于线程调度的不确定性，有些点绕过了我前面叙述的检查条件而从之前的退出代码退出，造成了提前终止，后去掉祖传代码即可。

发现别人BUG的策略

由于多线程难以单步调试以及随着作业难度的增加，一次作业的代码量很大，采用之前的阅读代码的方式效率低而且收效不大。我是使用课下写作业时自己构造的测试样例去测试别人的程序以求发现bug的方式，没有使用对拍器和自动生成测试数据。本单元的作业由于课程组已经提供了输入输出接口，所以就没有WF这种BUG的测试，而最容易出现BUG的地方就是线程安全方面的BUG，所以我构造测试数据的时候一方面构造极限数据进行压力测试，一方面构造很多需要线程交互的数据来测试线程安全。

心得体会

写本单元的第一次作业时，懵懵懂懂地按照课件上介绍的P-C模式写出来了初步的代码，并查阅资料使用了JAVA提供的线程安全的ArrayBlockingQueue作为共享对象。但是当时还不是很理解多线程的运行机制，总会出莫名其妙的BUG，比如在某一处卡住运行不下去，以及线程无法终止等。解决方法是查阅了大量资料，包括阅读ArrayBlockingQueue的源码，从底层理解线程安全队列的实现方式，以及采用原始的Printf的DEBUG方法锁定出现BUG的区域，进行更改测试，最后勉勉强强地写完了第一次作业。

在写第二次单元时，由于老师讲了线程安全的设计的课，对多线程有了进一步的理解，但第二次作业要求使用wait和notifyAll避免轮询，此时还不是很理解这两个方法的实现，花了一番功夫去理解后也实现了。

第三次作业在第二次作业的基础上，要求实现线程之间的信息的交互，这个也思考了很久，经过和同学交流讨论之后，了解了可以通过共享对象（类似调度器）进行线程之前的交互和信息传递，也比较顺利的完成了作业。

总的来说，通过本单元的学习，我学会了锁机制的知识，和通过wait与notifyAll方法进行线程交互的策略，也学习到了P-C和W-T设计模式，了解了SOLID设计原则，对多线程也由一开始的完全不懂到逐渐理解。