23年春面向对象第二单元分析与总结

概述

OO第二单元主要围绕着java多线程编程展开。在理论部分，课程简要介绍了JVM的内存机制，介绍了几种实用的同步控制手段和实用的设计模式；在实践部分，第二单元的任务仍然分为三次层层递进的作业，这里简要介绍背景如下：

HW5:实现一个多线程实时电梯系统的模型，能够做到将所有乘客正确的从出发地接取并送至目的地
HW6:实现了增加电梯数量的请求和电梯维护的请求
HW7:实现了电梯在有可达性限制和开关门限制的情况下对电梯路径进行静态规划

第二单元的内容并没有在OOPre中得到训练，但总体上来说，第二单元的难度要比第一单元下降不少。这主要归功于java强大的多线程编程能力。java为多线程编程提供了种类丰富，花样繁多的API，使得我们并不很着重与对线程安全的考量，而可以将精力主要放在业务逻辑的实现和调度的优化上。虽然笔者在第六、七次作业中均出现了一些bug，但是均不是因为线程安全的原因产生的，而根本上是因为对java线程机制不熟悉产生的。

JVM基础

理论课上对于JVM的介绍不可说不简略。恰恰相反的是，我觉得这部分反而应该是本单元最重要的内容（

笔者因此多去查找了一些资料，这一部分的论述可以看做是学习笔记。

JVM简介

JVM(java virtual machine)是java代码运行的必要环境支撑。本质原因在于，.java文件经过编译后生成的是字节码，而非可以直接在对应硬件上执行的机器码，由字节码到机器码的转换，需要依赖于环境中的JVM来实现。也就是说：
java source code -> byte code -> java virtual machine -> machine code
JVM并不是与java源代码(.java)绑定的，而是按照java字节码的规范读取字节码文件(.class文件)，解释并执行字节码。这种源代码不与环境相挂钩的特性赋予了java语言强大的跨平台能力。

JVM的内存结构^引用自

Java 虚拟机的内存结构可以分为公有和私有两部分。公有指的是所有线程都共享的部分，指的是 Java 堆、方法区、常量池。私有指的是每个线程的私有数据，包括：PC寄存器、Java 虚拟机栈、本地方法栈。

JVM memory structre

公有部分：Java堆、方法区、常量池

Java 堆指的是从 JVM 划分出来的一块区域，这块区域专门用于 Java 实例对象的内存分配，几乎所有实例对象都在会这里进行内存的分配。

Java 堆根据对象存活时间的不同，Java 堆还被分为年轻代、老年代两个区域，年轻代还被进一步划分为 Eden 区、From Survivor 0、To Survivor 1 区。

当有对象需要分配时，一个对象永远优先被分配在年轻代的 Eden 区，等到 Eden 区域内存不够时，Java 虚拟机会启动垃圾回收。此时 Eden 区中没有被引用的对象的内存就会被回收，而一些存活时间较长的对象则会进入到老年代。
这样做可以区分开存活时间较长的对象和存活时间较短的对象，对不同区域的对象施行不同的垃圾回收策略，可以提高垃圾回收策略的效率

方法区指的是存储 Java 类字节码数据的一块区域，它存储了每一个类的结构信息，例如运行时常量池、字段和方法数据、构造方法等。常量池也是放在方法区当中的，但是从等级上来讲，常量池和方法区是同级的。
私有部分：PC寄存器、Java 虚拟机栈、本地方法栈

Java 虚拟机栈，这个栈与线程同时创建，用来存储栈帧，即存储局部变量与一些过程结果的地方。栈帧存储的数据包括：局部变量表、操作数栈。
当 Java 虚拟机使用其他语言（例如 C 语言）来实现指令集解释器时，也会使用到本地方法栈。

java类的加载机制

JVM structure
这张图展示了java程序运行时的层次关系。
一个java类想要在JVM上执行，首先需要经过编译，形成.class文件，然后再由ClassLoader将class文件加载到内存中。ClassLoader会将这些.class文件中的二进制数据读入到内存中，并对数据进行校验，解析和初始化。最终，每一个类都会在方法区保存一份它的元数据，在堆中创建一个与之对应的Class对象。

类的加载分为五个阶段：加载、验证、准备、解析、初始化

加载
加载阶段是类加载过程的第一个阶段。在这个阶段，JVM 的主要目的是将字节码从各个位置（网络、磁盘等）转化为二进制字节流加载到内存中，接着会为这个类在 JVM 的方法区创建一个对应的 Class 对象，这个 Class 对象就是这个类各种数据的访问入口。
验证
当 JVM 加载完 Class 字节码文件并在方法区创建对应的 Class 对象之后，JVM 便会启动对该字节码流的校验，只有符合 JVM 字节码规范的文件才能被 JVM 正确执行。
准备
当完成字节码文件的校验之后，JVM 便会开始为类变量分配内存并初始化。这里需要注意：
- 内存分配的对象：Java 中的变量有类变量和类成员变量两种类型，类变量指的是被 static 修饰的变量，而其他所有类型的变量都属于类成员变量。在准备阶段，JVM 只会为类变量分配内存，而不会为类成员变量分配内存。类成员变量的内存分配需要等到初始化阶段才开始。
- 初始化的类型：在准备阶段，JVM 会为类变量分配内存，并为其初始化。但是这里的初始化指的是为变量赋予 Java 语言中该数据类型的零值，而不是用户代码里初始化的值。而常量(被 static final 修饰的变量)则会在准备阶段就被赋值为代码里初始化的值。
解析
初始化
到了初始化阶段，用户定义的 Java 程序代码才真正开始执行。在这个阶段，JVM 会根据语句执行顺序对类对象进行初始化，一般来说当 JVM 遇到下面 5 种情况的时候会触发初始化：
- 遇到 new、getstatic、putstatic、invokestatic 这四条字节码指令时，如果类没有进行过初始化，则需要先触发其初始化。生成这4条指令的最常见的Java代码场景是：使用new关键字实例化对象的时候、读取或设置一个类的静态字段（被final修饰、已在编译器把结果放入常量池的静态字段除外）的时候，以及调用一个类的静态方法的时候。
- 使用 java.lang.reflect 包的方法对类进行反射调用的时候，如果类没有进行过初始化，则需要先触发其初始化。
- 当初始化一个类的时候，如果发现其父类还没有进行过初始化，则需要先触发其父类的初始化。
- 当虚拟机启动时，用户需要指定一个要执行的主类（包含main()方法的那个类），虚拟机会先初始化这个主类。
- 当使用 JDK1.7 动态语言支持时，如果一个 java.lang.invoke.MethodHandle实例最后的解析结果 REF_getstatic,REF_putstatic,REF_invokeStatic 的方法句柄，并且这个方法句柄所对应的类没有进行初始化，则需要先出触发其初始化。
类初始化时，编译器会按照其出现顺序，收集类变量的赋值语句、静态代码块( static 修饰的代码块)，最终组成类初始化方法。类初始化方法一般在类初始化的时候执行。
经过类初始化后，如果想要获得这个类的一个实例，则还需要经过一个对象初始化的阶段。对象初始化时，编译器会按照其出现顺序，收集成员变量的赋值语句、普通代码块，最后收集构造函数的代码，最终组成对象初始化方法。对象初始化方法一般在实例化类对象的时候执行。

JVM结构与多线程的关联

以上搬运了这么多大佬的博客（笑，最终还是要落实到JVM与多线程的关联上。理解为什么会产生数据相关，为什么需要同步控制，对于理解java的多线程机制和完成任务都有很大的帮助。
根据JVM的内存结构，我们知道，类的加载和对象的加载是分开来进行的，它们所在的内存空间也有所不同：类被加载到方法区中，而对象被加载到java堆中。这样也就决定了变量的三个储存位置：方法区存储类变量， java堆存储类成员变量，栈帧存储临时变量。其中堆是由所有线程所共享的，而栈帧是由单个线程持有的。这也就决定了我们在实现线程间交互和通信时一般都需要进行同步控制，如果不满足伯恩斯坦条件，程序的执行就不能如我们所预期的那样进行。

架构

总的架构上来说，笔者采用生产者-消费者模型 + 调度器的架构。这样的架构其实相当奇葩奇特，究其原因在于笔者的调度器与数据流是完全没有耦合关系的。也就是说，调度器的主要指责是查看当前系统中是否存在电梯与乘客失配的情况，并且将闲置的电梯调配到正等待的乘客处。实现上下客逻辑和对共享对象的维护则一概不在调度器的职责范围之内。
调度器本质上是在轮询整个电梯系统，在轮询的过程中 look & set 。look 指的是调度器通过读取系统中各个组成暴露出来的方法以了解当前系统运行的状态， set 指的是调度器通过给系统中的各个组成置位来指导电梯系统的运作。这样做的特点有：

调度器能够容忍所读到的数据并非为最新数据，因此可以大大减少调度器的同步控制。
调度器通过置位来影响电梯的运行，以及电梯的运行依赖于调度器的置位，这样减少了系统的不确定性，实际上是对自由竞争机制的改良。
调度器的调度是按照楼层而非人员来进行的，即：人员并非为调度的单位，楼层中人员的数量才是调度的依据。可以在自由竞争的局部最优和全局最优之间求得一个相对平衡的点。
电梯的逻辑相对简单，其只需要重复执行运动、检测、上下客的逻辑。
容易出现未知的bug，同步控制的量大大减少了，但并不意味着不需要同步控制，调度器在运行过程中，系统状态会发生变化，会出现数组越界等情况。

电梯

电梯运行逻辑如下图所示：

elevator
电梯的休眠是必要的，是整个架构中必不可少的一部分。一方面，这个架构中仍然存在自由竞争的部分，在一个请求真正进入某个电梯之前无法预知该请求到底会进入哪个电梯，因此调度器无法精确地notify某一电梯，需要按照实际情况，使先到达且符合条件的电梯获得请求。另一方面，为了抑制高涨的CPU时间，减少电梯空转的消耗，也需要使电梯不那么频繁地试图开始运行。虽然方法看上去比较笨拙，但是使电梯休眠一段时间却是能够达到上述目的。至于电梯休眠时间的长短倒是一个值得商榷的问题，笔者在这里采用了电梯运行一层楼所消耗的时间作为休眠时间，过短会导致CPU时间的上涨，过长则会导致总时间的上涨，需要权衡取值。

调度器

调度器的运行逻辑如下：

scheduler
调度器的主要思想是：调度器并不应该精确的将某个人分配到某电梯当中，而是应该解决当前系统当中电梯资源和电梯请求失配的问题。如果所有电梯都处在忙的状态，调度器不应该干预电梯的运行，如果有电梯处在空闲状态，那么应该将其分配到请求比较多的楼层。这是一种既不谋求等待时间最短，也不考虑电量最少的策略，但是倒也惊奇的能够拿到大多数点的满分。笔者想，这一方面与课程组给出了评价体系有关；另一方面在于，无论是何种的主动调度，都会存在某些情况下某些电梯负载高，某些电梯负载低乃至于没有负载的情况下，这个调度器实际上抬高了这个下限，使得大多数时候系统内的资源得到了比较充分的利用。

类图分析

UML
UML图如上。本单元任务中，一共有一个输入线程 + 一个调度器线程 + N个电梯线程。其中输入线程，请求列表，电梯线程组成了生产者消费者模式，调度器则通过笔者称之为 look & set 模式对整个系统施加影响。而主线程，笔者并没有在上述UML中呈现，原因在于笔者的主线程只起到了初始化的作用。实际上主线程在完成了系统的初始化之后就已经结束，在之后系统的运行当中，系统状态是由系统自身来维护的。

对任务要求的回答

三次作业架构设计的逐步变化和未来扩展能力画UML类图

三次作业中，我的架构均如上述UML图所示，没有发生架构设计上的变化。实际上，整个单元任务中我所做的迭代都十分的少，究其根本，就是将电梯的运行逻辑和调度策略进行了解耦合。与具体人员相关的逻辑和维护请求列表的功能由电梯自行实现，与整体资源调配和限制性逻辑（比如服务、只接人的数量，可达性）则由调度器在调度时予以考虑来实现。只要能够保证当前问题可解的情况下，这个架构是一定能够满足需求的。但是缺点就在于调度器缺乏精细粒度的控制，不能够在性能上做到最好。
画UML协作图(sequence diagram)来展示线程之间的协作关系（别忘记主线程）

（在这里课程组给定的要求不是很清楚，协作图是协作图，主要讲述的是数据依赖关系，侧重于关系；sequence diagram是流程图，明确的时间线是其特点，侧重于时序）
笔者在这里做了一份协作图（笔者的架构里时序是不确定的，电梯的运行和调度器的调度并发，系统状态随之改变）。
识别出三次作业稳定的内容和易变的内容，并加以分析

三次作业中稳定的在于架构，整体的架构，乃至 run() 方法都没有太大的变化，易变的部分主要在于具体函数的实现，比如电梯上下人方法在第七次作业中添加了信号量的请求和释放，请求列表捎带人的方法在添加了对可达性的判断，调度器的调度方法添加了有可达性限制下对电梯捎带策略的模拟。

bug分析

笔者在第二单元的第六、第七次作业中均出现了bug。
第六次作业中的bug出在了电梯退出逻辑上。在第五次作业中，只要输入结束并且请求列表为空就允许停止的电梯退出。但是在第七次作业中新增添的 maintain 指令会使得即使输入结束且请求列表为空的情况下只要有一部电梯没有停止，所有的电梯都不能退出。这是因为有可能出现某一电梯 maintain 放出梯内乘客，但整个系统中再无可用电梯的情况。针对这一问题，我将电梯的结束交由调度器来控制，因为调度器可以观察到全局状态，而电梯之间相互不能观察，通过调度器给电梯置位控制电梯退出的方式，修正了这一bug。
第七次作业中的bug则是因为同步控制的原因。前面已经提到过，look & set 模式没有严格的数据依赖，但是并不意味着没有同步控制。在调度器运行过程当中，有可能前半段还是旧的数据，运行到中途数据被修改，后半段读到的就是新的数据了。虽然数据新旧对于调度器来说并无大碍，但是需要额外的判断保证数组下标不会越界。第七次作业中的bug即源于此。使用 volatile 或者 atomic 类型容器可以对内容施加弱同步性限制（即可见性），也可解决这一问题。

总结

第二单元的任务结束了，但笔者知道，第二单元的任务设计的只是多线程编程的一点皮毛。无论是JVM的运行原理，还是java语言所提供的的各种同步锁，亦或是多线程编程的设计模式，这些都是复杂且深奥的内容。在本单元的学习中，笔者主要学习到了java多线程编程的基本原理，学会了使用 sychronized, semaphore 等进行同步控制，了解并运用了生产者和消费者的设计模式，同时对于多线程编程的 debug 有了一定的初步认识。
大运村楼下的桃花又开了，笔者从当初进校时的懵懂，到不觉大学生活已经快过半。每次笔者从楼下走过，都会觉得这桃花虽然娇艳，却也是无情之物，在我于课设中挣扎求生的时候，为什么偏偏你开得这么灿烂呢（笑。人生无非是一些记忆的重合，去年之桃花与今年之桃花恍恍惚重合在一起，鲜艳灿烂，绝于常物。我寻思再三，才知道是自己多情。桃花无主，为春光而开；移情风物，自觉嗟叹罢了。