BUAA_OO 第二单元总结

目录

(1)同步块的设置和锁的选择,锁与同步块中处理语句直接的关系

  • 选择synchronized关键字封装代码块,在操作电梯列表、每个电梯内的等待队列、未到达人的列表时,需要synchronized一下。
  • 要做到输出安全,需要synchronized一个输出锁,然后再调用println(),否则会出现后面的输出比前面的输出时间戳更早的情况。
  • 如果当前电梯查询到队列里没人,就会wait(),直到调度器往队列里添加人,然后notify()将电梯唤醒。
  • 为了避免死锁,设计中避免了电梯线程同时synchronized两个锁的情况。

(2)调度器设计,调度器与程序中的线程交互

  • 第一次作业:调度器在电梯内。如果电梯内有人,会按照电梯内人的方向移动。

    如果电梯内没人,找到向上走的人所覆盖的楼层数,和向下走的人所覆盖的楼层数,取较大者决定电梯先送哪一部分请求。如果先送向上的请求,电梯会先去接最低端的向上请求的人。

    事实证明,这个调度策略的性能很烂,在强测中得到了不算高的性能分。

  • 第二次作业:采用分派器加调度器。分派器分发任务到每个电梯的请求队列里,然后每个电梯根据自己的请求队列运行。由于我比较懒,单电梯策略和第一次作业完全一样。

    分派器的策略是:如果运送的距离大于L,并且1号电梯的请求数量<P时,就扔到1号电梯。否则在其余电梯中选择请求数量最少的一部电梯。这样做主要是为了长距离请求会被集中在一个电梯内运行,并且1号电梯不会出现在长距离运送中为了短距离请求而折返的情况。但是因为这种设计,导致强测RTLE了一个点。

  • 第三次作业:还是采用分派器加调度器。采用静态拆分请求的方式。

    单电梯策略和第一次作业完全一样。

    分派器与拆分请求的方式:

    如果有多部电梯可以运送p请求,那么选压力最小(请求队列人数\(\times\)运行一层楼时间)的电梯。

    如果只有1号电梯能运送该请求,并且该请求的长度小于6,那么就放入1号电梯。

    否则拆分请求。

    如果运送距离比较长,就可以拆成s->3->18->t,3->18这一段扔给C类型电梯。

    如果B电梯比较空闲,可以让该请求的,两个端点加一或者减一变成奇数,请求中间那一段用B来运输。

    每个人的所有请求用一个list存储,当list[0]的子请求处理完毕后,就把该请求按照新的list[0]的请求分配给某一部电梯。

  • 用一个list存了一下当前未完成的请求,如果list为空,并且读入进程的结束标志位为真,那么就退出整个程序。

  • 不足:加入电梯后没有对当前指令再分配,导致最后加入的电梯可能没用到。

(3)架构设计与可扩展性。

  • 第三次作业

    • Source File Total Lines Source Code Lines
      Controller.java 181 136
      Elevator.java 396 252
      InputThread.java 39 35
      Person.java 142 113
      SynchronizedOutput.java 7 6
    • 类复杂度

      class OCavg OCmax WMC
      Controller 2.727272727272727 10.0 30.0
      Elevator 3.1176470588235294 13.0 53.0
      InputThread 5.0 5.0 5.0
      Person 1.8181818181818181 9.0 20.0
      Person.Event 1.0 1.0 4.0
      SynchronizedOutput 1.0 1.0 1.0
      Total 113.0
      Average 2.511111111111111 6.5 18.833333333333332
    • 方法复杂度

      method CogC ev(G) iv(G) v(G)
      Elevator.tryOpen() 31.0 1.0 24.0 25.0
      Controller.assign(Person) 25.0 4.0 11.0 14.0
      Elevator.getEmptyDir() 14.0 4.0 8.0 8.0
      Person.changeRoute(String) 14.0 1.0 8.0 9.0
      Elevator.run() 13.0 1.0 7.0 7.0
      Elevator.getDir() 11.0 7.0 4.0 10.0
      Controller.reAssign(Person) 10.0 4.0 5.0 8.0
      Controller.find(String) 6.0 3.0 3.0 5.0
      InputThread.run() 6.0 3.0 6.0 6.0
      Controller.main(String[]) 5.0 1.0 4.0 4.0
      Elevator.Elevator(String,String) 3.0 1.0 3.0 4.0
      Elevator.cal(int,int) 2.0 3.0 1.0 3.0
      Elevator.canGet(Person) 2.0 2.0 2.0 3.0
      Person.getDir() 2.0 2.0 1.0 2.0
      Total 144.0 68.0 118.0 139.0
      Average 3.2 1.511111111111111 2.6222222222222222 3.088888888888889

      tryOpen()和assign()两个函数的复杂度最高,一个是用于判断电梯是否开门,另一个是判断将请求分配给哪一个电梯。

    • UML类图

      BUAA_OO 第二单元总结

    • UML时序图

    BUAA_OO 第二单元总结

    • 第三次作业的可扩展性。
      • 没有设置策略类,导致电梯策略比较固定,新增一个模式时需要复杂地更改调度策略。
      • 采用拆分请求的方式,拆分请求的方式可以根据不同的情境改变。

(4)自己程序的bug

  • 第一次作业在强测和互测中没有被hack。
  • 第二次作业在互测中没有被hack,强测中被RTLE了一个点,strong_data_9。
  • strong_data_9是有5部电梯,30个请求是1->20,17个请求是20->1,全部在[180.0]到达。相当于给电梯的运行时间只有30s。我当时的分派器设计是,在没有超过人数限制的情况下,运送距离长的会优先扔到1号电梯。所以导致1号电梯运了好几趟,然后RTLE了。修复bug时就改了一下1号电梯的等待人数限制就过了。
  • 第三次作业在强测和互测中没有被hack。

(5) 别人程序的bug

  • 这次变得佛系起来了。前两次作业一共hack了三次,都没有hack成功。

  • 第三次作业交了一发大数据,hack了一个人,RTLE。

    模式是Random,所有人都从20楼到4楼,并且在最后加入两部C类型的电梯。

  • 同房间有一个人一发大数据hack了四个人,orz。

    分析了一下同房间几个被hack的同学的代码。

    Berserker是*竞争+没有拆请求,RTLE。

    Rider是按楼层分配请求给A/B/C类型的电梯+同类型的电梯*竞争+没有拆请求,RTLE。

(6)心得题会

  • 反思
    • 自己的电梯还有很多值得改进的地方。
    • 没有写模拟电梯,其实也不是太难写,把sleep的时间累加到sum里,就可以求出这个电梯的模拟运行时间,然后根据这个模拟运行时间判断把请求加在哪个电梯里。
    • 没有写*竞争。个人感觉*竞争比分派器+调度器更优。*竞争可以更好地避免有的电梯很忙有的电梯很闲这种情况,而我的分派器设计经常由于分派不均导致这种情况。
    • 没有针对特殊的模式使用优化,而是对于三种模式都用了Random模式的调度策略。
    • 对拍数据生成较为随机,主要采用了集中时间到达,分散时间到达,集中楼层到达,分散楼层到达,全部长距离运输等数据。由于电脑内存太小了233,最多只能同时开30个线程对拍,CPU占用率只有20%。尝试过将电梯的所有sleep时间调为0,并且将生成的数据集中在几秒内,就可以获得较大的CPU占用率。
  • 心得
    • 经过面向对象第二单元的三次作业和博客总结,经过三次的电梯迭代开发,我感受到程序架构的重要性,写一个可以支持扩展的架构在后期的迭代开发中至关重要。
    • 此外还学习了java多线程的使用,学习了如何设计多线程交互架构,学习了如何避免死锁的发生。
    • 总的来说,这一单元还是收获很大。
上一篇:1008 Elevator (20 分)


下一篇:[PAT A1008]Elevator(水题、数学问题)