OO 第二单元总结

本文为OO 第二单元电梯作业总结，本单元主要是掌握多线程和线程安全。三次作业总的架构类似，可分为输入线程、调度线程、电梯线程。三次作业的增量迭代如下

第五次作业
- 六部电梯
第六次作业
- 可选择增加电梯，电梯的初始属性可变
- 维修电梯，将维修电梯的乘客重新安排
第七次作业
- 新增电梯增加可达性、
- 信号量的使用

一、同步块和锁

由于我的架构还算完善，所以每次增量较为容易，在第五次作业中使用的java语言特性synchronized，所以在后续中并没有使用读写锁等更符合本单元作业的方法。

1.同步块和锁的选择

我选择的是修饰方法，这样避免修饰代码块从而效率更高。同步块出现的原因是因为不同线程可能同时对一个对象进行读写，因此判断哪些代码需要放到同步块中，只需看一下不同线程对哪些共有对象进行了读写。有以下三种情况：

读读
- 一定不会造成线程安全
读写
- 具体分析
  - 调度器线程模拟电梯运行的时候，需要读取电梯当前楼层状态不需要加锁，避免了当前电梯所在线程在sleep从而被阻塞
  - 总的请求表WaitQueue的getEnd和setEnd是需要加锁的，避免了调度器线程读到没有结束但同时输入线程刚好结束，造成调度器一直等待没有被唤醒
写写
- 一定要加锁

由上图和上述策略，我们知道同步重点在总的请求表和各个电梯的请求表，也就是对象锁

2. 避免死锁、轮询、无效notify

死锁的出现是由于下列情况造成，当然在我的架构中只需要判断同步方法中是否又调用了其他对象的同步方法即可（并不存在）

public class A{
   public synchronized void aMethod(){
       b.bMethod();
   }
}
public class B{
   public synchronized void bMethod(){
       a.aMethod();
   }
}

在本单元作业中出现CTLE的原因可能是轮询和死循环，要注意线程的终止条件和wait条件，避免出现如下

public class A{
   public synchronized void a1Method(){
      try{
          wait();
      }catch(){
          
      }
       notifyAll();
   }
   public synchronized void a2Method(){
      try{
          wait();
      }catch(){
          
      }
       notifyAll();
   }
}

避免无效notify，例如，WaitQueue在等待时，只有加请求和setEnd的时候notify

二、调度

在往届性能评定中并没有电量这一指标，也就是说只要能把人越快送到越好。在考虑到电量之后就需要调度器的设计。以第七次作业为例调度器的中心工作：从总表中读取请求并处理，如果是乘客请求进行模拟，通过策略选择要把此请求放到哪个电梯

1.调度器模拟

对于一个请求，我们把它分别放到每一个电梯中，并模拟这种情况的耗时，只需要把原来电梯中所有的sleep换成time++即可，次过程在NightElelvator类中night方法返回把当前表中所有乘客送完总耗时，假如有6部电梯，我们一共需要模拟12次，6（电梯数量）* 2（加此请求和不加此请求）。

前两次作业中，为了加快模拟速度，我为每一部电梯模拟加此请求和不加此请求开了一个线程，但是在第七次作业却报了OutOfMeomory线程开太多了，虽然RAM用的远远少于限制，第八次作业我又改成了并行化

2.调度器策略

本质都是贪心思想，仅作出在当前情况下的最优解

第五次作业我用的是电梯运送此乘客所花费的最小值，这样考虑的是用电量和运送时间，即模拟把这个请求加到此电梯队列中所花费的时间减去不加此请求所花费的时间
第六次第七次我用的是所有电梯结束的最短时间，考虑的是乘客等待时间和电梯总体运行时间，即模拟把此请求放到某一部电梯，它和其他电梯运行的结束时间，然后去最短的结束时间
第七次中我用了迪杰斯塔拉算法，把11层看成11个点，然后求最短路径，然后从这条路径从后往前找到第一个能从起点直达终点的中间点，用图做的话，可以自定义距离，比如我有一个请求从1楼到4楼，无法直达，可选1-2-4或1-3-4，但1-3和3-4的电梯数量更多，因此选择第二条路径，然后用第二种策略模拟。本次作业距离定义：$ dis = $

在第五第六次作业性能分中这两种策略差不多，第七次中应该是第二种更好。

三、架构

1.UML类图(以第三次为例)

classDiagram
Main --> InputThread : start
Main --> Schedule : start
Main --> ElevatorThread : start

ElevatorThread --> Elevator : run
InputThread --> WaitQueue : addRequest
Schedule --> WaitQueue : getRequest
Schedule --> RequestTable : dispatch
Elevator --> RequestTable : getRequest
RequestTable --> CusRequest : contain
Elevator --> Check : judge
class Main{
      +main()$
}
class InputThread{
      -WaitQueue waitQueue
      +run() void
}
class Schedule{
      -WaitQueue waitQueue
      -HashMap<Integer,Elevator> elevators
      -HashMap<Intrger,RequestTable> outRequestTables
      -HashMap<Integer,RequestTable> inRequestTables
      -HashMap<Integer,Check> checks
      +run() void
      +addEage() void
      +imitate() int
      +dispatch() void
}
class Elevator{
      -int id
      -int capacity
      -double speed
      -int access
      -String status
      -int floor
      -int lastTime
      -int direction
      -blooean isMaintain
      -HashMap<Integer,Check>checks
      -RequestTable outRequestTable
      -RequestTable inRequestTable
      -WaitQueue waitqueue
      -int[] accFloor
      +getAccess() boolean
      +setIsMaintain() void
      +getIsMaintain() boolean
      +updateDir() void
      +getStatus() String
      +setStatus() void
      +maintainAct() void
      +restAct() void
      +openAct() void
      +closeAct() void
      +moveAct() void
      +arriveAct() void
      +getOff() void
      +getOn() void
      +clone() NightElevator
}
class ElevatorThread{
      -Elevator elevator
      +run() void
}
class CusRequest{
      -int id
      -int start
      -int destination
      -int realDes
      +setRealDes() void
      +setDestination() void
      +getDestination() int
      +getStart() int
      +getDirection() int
}
class Check{
      -int mx
      -int nx
      -int nowMx
      -int nowNx
      +only() void
      +other() void
      +endOnly() void
      +endOther() void
}
class WaitQueue{
      -ArrayList<Request> requests
      -boolean isEnd
      -HashMap<Integer,Integer> cus
      -int maintainSum
      +addCus() void
      +remCus() void
      +isPerEnd() boolean
      +addPerRequest() void
      +addChange() void
      +addEleRequest() void
      +addMainRequest() void
      +addMaintain() void
      +subMaintain() void
      +getMaintainSum() int
      +getRequest() Rqeuest
      +setEnd() void
      +isEnd() boolean
      +isEmpty() boolean
      +getPos() int
      +addRequestTable() void
}
class RequestTable{
      -boolean isEnd
      -ArrayList<CusRequest> cusRequests
      +setEnd() void
      +isEnd() boolean
      +isEmpty() boolean
      +getSize() int
      +addInRequest() void
      +addOutRequest() void
      +getLastRequest() CusRequest
      +getOneRequest() CusRequest
      +remRequest() void
      +outWait() void
      +outNotify() void
      +isHaveOn() boolean
      +isHavaOff() boolean
      +getOnRequest() CusRequest
      +getOffRequest() CusRequest
      +getFetchStart() int
      +getInDirection() int
      +clone() RequestTable
      
}

2.UML协作图(第三次作业)

sequenceDiagram

participant M as Main
participant I as InputThread
participant S as Schedule
participant E as Elevator
M ->> I : start
M ->> S : start
M ->> E : start
I ->>+ S : addRequest
alt[is PerRequest]
S ->>+ E : dispatch and addRequest
E ->> E : not transfer and get off
E ->>- S : is tranfer and dispatch again
else[is AddElevator]
S ->>+ E : new Elevator and start
E -->>- S : ;
else[is Maintain]
S ->> + E : setIsMaintain
E -->>-S : put the passengers to schedule
end
S -->>- I: ;

I ->>+ S : setEnd
S ->>+ E : if empty && end then setEnd
E ->> E : if empty && end then turn end
E -->>- S : ;
S -->>- I : ;

3.架构与迭代

架构

第五次作业
- 输入线程将请求传入WaitQueue，Schedule读取并模拟加到电梯表中，电梯采取ALS策略
- 电梯有outRequestTable和inRequestTable，分别存放电梯外和电梯内的请求
- 电梯运行为有限状态机
- 结束条件
  - ThreadInput 当前请求为null
  - Schedule waitQueue.isEmpty() && waitQueue.isEnd()
  - Elevator outRequestTable.isEmpty() && inRequestTable.isEmpty() && outRequestTable.isEnd()
第六次作业
- 调整电梯参数
- 结束条件
  - ThreadInput 当前请求为null
  - Schedule waitQueue.isEmpty() && waitQueue.isEnd()&& waitQueue.getMaintainSum() == 0 即需要判断电梯是否都响应了Maintain
  - Elevator outRequestTable.isEmpty() && inRequestTable.isEmpty() && outRequestTable.isEnd()或者维修
第七次作业
- 可达性在调度器已经谈过
- 结束条件 Schedule waitQueue.isEmpty() && waitQueue.isEnd()&& waitQueue.getMaintainSum() == 0 && cus.isEmpty()cus是<Integer,Integer> 的hashMap，存放所有乘客的id和目的地，当乘客到站后将其删除
- 同一楼层服务数量由Check类执行，实现了类似信号量的方法

电梯状态转换

参考CO有限状态机，将电梯的行为和状态分为: end, rest, move, arrive, open, close,maintain。这样处理会在电梯线程的run中很清晰，不同状态执行不同操作并进行状态转换。

4.作业中稳定的内容和易变的内容

整体的框架还是很完整，电梯线程变化的不多，加入了maintain新状态，在乘客下车时判断是否换乘

调度器变化最大，比如更换了策略类，Add和Maintain请求都是在调度器中处理；在第七次考虑可达性后，需要规划路线等等这些都是在调度器中完成。

四、bug和debug

bug

由于第五次我就使用了调度器，导致模拟的时候可能会出现真实电梯move状态floor++但是仍在move，导致影子电梯的状态转化出现错误出现了死循环；第六次作业问题是线程资源紧张导致无法申请新的线程，还有问题是应当优先处理maintain请求和addElevator请求，出现了维修后移动超过两层的情况；第七次作业暂时没找到bug

debug

大多数debug都是死循环的bug，这是由于线程一直在run没有结束，我使用JProfiler分析CPU时间从而定位出现问题的线程由于电梯运行是状态转移，因此也能轻松定位到出现问题的状态和方法。除此之外，线程无法结束我一般使用手工打断点，即在特定的语句出输出一些语句，这样可以判断是哪些线程没有结束，之后确定原因。

五、心得体会

1. 线程安全

如非必要，勿增实体

线程之间共享的对象实体越少越好，这也就是奥卡姆剃刀的应用

读写的具体判断

在上文中已经提到有的读写是必要互斥的，有的则不必要，不能一味synchronized，也不能一律都用读写锁

2.层次化设计

电梯线程的run

这样比写很多的分支语句要清晰的多，也很容易迭代开发

public void run() {
        while (true) {
            switch (elevator.getStatus()) {
                case "end":
                    return;
                case "rest":
                    elevator.restAct();
                    break;
                case "maintiain":
                    elevator.maintainAct();
                    break;
                case "open":
                    elevator.openAct();
                    break;
                case "close":
                    elevator.closeAct();
                    break;
                case "move":
                    elevator.moveAct();
                    break;
                case "arrive":
                    elevator.arriveAct();
                    break;
                default:
                    return;
            }
        }
    }

####线程和面向对象

我将电梯线程和电梯分开，线程只是为其拥有的属性提供了运行的栈空间，因此将线程和具体的事物分离是很正确的，但调取器和调度线程为了简洁合为一个。面向对象的思想进一步加深。

3. 写在最后

第五次作业为了死循环bug，最终甚至没进互测，无疑是对我的一次重大打击，bug虽小，但造成后果很严重。第五次作业投入的时间超过30小时，虽然分数不理想，但我对多线程的理解在其中也得到强化，第五次作业留下的良好架构让之后的作业少走了很多弯路（虽然之后两次还是有很长时间debug）。除此之外，debug能力也得到很大提升，通过错误数据以及断点设置，结合工具能够快速定位到问题代码，分析原因并修改。

还有一个很重要的问题，太过于依赖讨论区的评测机，在之后单元中，还是要自己写一些简易的评测机。软件的开发和测试都是尤为重要的环节，即使在未来不会从事软件行业，但测试还是一项很重要的内容。

体验失败，并战胜失败，愉快的面对每次作业

#OO #总结 #多线程

OO第二单元总结

https://etherialize.github.io/2023/04/17/OO第二单元总结/

作者

HZY

发布于

2023年4月17日

许可协议

OS-lab4 上一篇

OS-lab3 下一篇