首页 > 其他 > 详细

面向对象第二单元博客总结

时间:2019-04-24 20:11:18      阅读:115      评论:0      收藏:0      [点我收藏+]

面向对象第二单元博客总结

前言

第二单元的学习也就这么结束了,相比第一单元的多项式求导,第二单元的电梯则显得更加贴近生活实际,在问题不那么抽象的同时却又增加了问题的复杂程度。在这个单元的学习过程中,我遇到了许多问题,并也为没能及时解决而付出了血的教训。回顾上一单元的博客内容,不免有些单薄,本单元遇到的诸多问题,也希望能借助此次博客一一总结反思,让血泪史能够被铭记。

第五次作业

程序分析与度量

程序基本结构

第五次作业要求实现一个先来先服务(FAFS)的傻瓜电梯,虽然要求以多线程的方式实现,但是实际上并未涉及到非常复杂的线程间的同步问题,每个线程相对而言较为独立。程序结构如下图所示:

技术分享图片

程序由最为基本的五个类构成:InputHandler类负责读取控制台的输入,Scheduler类负责将InputHandler读取的输入依次送往电梯,Elevator类负责执行调度器分配给自己的任务,三个类间传递任务的方式都是通过公共类RequestList来完成的,最终,由MainClass作为整个程序的入口。

复杂度分析

各个类的复杂度分析如下表所示:

class OCavg WMC Cyclic Dcy Dcy* Dpt Dpt*
Elevator 2.0 12.0 0.0 1.0 1.0 1.0 1.0
InputHandler 2.0 4.0 0.0 1.0 1.0 1.0 1.0
MainClass 1.0 1.0 0.0 4.0 4.0 0.0 0.0
RequestList 1.5 6.0 0.0 0.0 0.0 4.0 4.0
Scheduler 2.0 6.0 0.0 1.0 1.0 1.0 1.0
Total 29.0
Average 1.8125 5.8 0.0 1.4 1.4 1.4 1.4

可以看出,第五次作业由于功能较为单一,各类中的循环复杂度也都控制的较好,最为复杂的可能是电梯类,因为实现的电梯相关功能较其他类相对复杂。各类间也基本不存在太过复杂的依赖关系,基本做到了低耦合。各方法的复杂度如下表所示:

method ev(G) iv(G) v(G)
Elevator.close() 1.0 2.0 2.0
Elevator.dealMainRequest() 2.0 4.0 4.0
Elevator.Elevator(RequestList,int) 1.0 1.0 1.0
Elevator.move() 1.0 2.0 3.0
Elevator.open() 1.0 1.0 1.0
Elevator.run() 3.0 2.0 3.0
InputHandler.InputHandler(RequestList) 1.0 1.0 1.0
InputHandler.run() 3.0 4.0 4.0
MainClass.main(String[]) 1.0 1.0 1.0
RequestList.addRequest(PersonRequest) 1.0 1.0 1.0
RequestList.getRequest() 2.0 5.0 5.0
RequestList.RequestList() 1.0 1.0 1.0
RequestList.setStopSig() 1.0 1.0 1.0
Scheduler.assignRequest() 2.0 2.0 2.0
Scheduler.run() 3.0 3.0 3.0
Scheduler.Scheduler(RequestList,RequestList) 1.0 1.0 1.0
Total 25.0 32.0 34.0

相较之前几次作业,本次没有出现特别复杂的方法,整体控制的比较好。

时序分析

本次的时序图如下:

技术分享图片

可以看出,输入处理、调度器和电梯之间的交互都是只通过对Requestlist的添加与读取实现的,在一定程度上体现了高内聚低耦合的思想。而线程之间的关系模式则是最为经典的“生产者-消费者”模式,其中作为托盘的RequestList不仅要保证线程安全,还提供了空时等待的机制,使CPU时间不至于过长。

本次作业的一个难点在于如何让所有进程在完成全部任务之后主动退出,使程序不会一直运行至超时。个人的做法是在RequestList类中设置一个结束标志,当InputHandler读完所有输入之后,将与调度器共享的队列中的这个标志置true并退出,调度器在分配完全部任务且该标志为真时将与电梯共享的队列中的结束标志置true并退出,电梯同样在运行完后检查标志并退出。

SOLID原则分析

  • SRP:每个类分工都简单明确
  • OCP:调度器后续只需新增加调度方式,但电梯则不能继续依次处理每个任务,需要重写一个状态机,不是很好
  • LSP:后续电梯与调度器之间传递了更多的信息,可以用RequestList的子类代替
  • ISP:未实现接口类
  • DIP:三个线程间没有之间依赖关系,都通过共享的RequestList来交互

BUG分析

这次作业似乎风平浪静,没有出什么BUG。由于FCFS是来一个任务解决一个,几乎不太可能出现什么问题,此处不再赘述。

作业小结

第五次作业实现的电梯较为基础,但是却让我们对多线程编程拥有了初步的认识与了解,这次作业写出的架构可扩展性较强,后续大体的三线程两队列架构也一直沿用到最后,可以说是一个比较清晰的开始。

第六次作业

写在前面

第六次作业可以算的上是大学学习以来,栽的最惨痛的一次了,但这并不是因为这次作业有多么的复杂,相对于第七次作业,本次作业其实只需要进行一部分改动,就可以完成要求。然而,由于设计思路失误以及安排时间不够合理,在强测时付出了血的代价。因此,对于这次作业的总结有别于其他两次作业,首先我会先对于最终提交到强测版本的代码进行架构分析与BUG分析,然后再对我在强测之后重写的一个版本进行一个完整的分析与度量。

初版架构设计与BUG分析

程序架构分析

第六次作业在第五次的基础上增加了捎带与地下楼层的需求。为处理捎带,在电梯中设置了主请求与捎带队列的概念。为增加对地下楼层的支持,在下行经过1楼与上行经过-1楼时实现了特判。程序整体架构如图所示:

技术分享图片

可以看到,第六次作业代码沿用了第五次的基本架构,仍然是三个线程两个队列完成通信。改动主要在两个地方,一是在电梯之中实现一个状态机,到每一层时转换到对应的状态,以便对捎带队列中可以处理的请求进行处理;二是在调度器中获取电梯的主请求MainReq,并根据电梯的其他信息来判断是否应当把当前任务加入电梯的捎带序列,如果不能捎带,则将其加入电梯中的等待队列,再电梯为FREE状态时将任务传回requestList,由调度器重新分配。核心的捎带逻辑则为:与电梯当前运行方向相同且进入电梯楼层小于当前主请求的入/出楼层(由是否到达主任务起始楼层决定)的请求,判定为可以捎带,加入电梯的捎带队列。

电梯在这个架构下完全不需要考虑请求是怎么来的,需要以什么样的顺序去执行任务,它只需要在每一层楼检查是否有人上下,并把出电梯的请求踢出队列,这是一个把调度器当作自己大脑的傻瓜电梯。而调度器则不仅要分配任务,它还需要保证自己分出去的任务能够被电梯正确的执行,堪称是电梯的保姆。在这个架构下,似乎人人各司其职,世界美满和谐,一切都十分的理想。

BUG分析

然而,上述架构大概也只能活在理想里,它是绝对不可靠并且问题十足的一个架构。下面从几个方面去分析可能会出现的问题:

  1. 描述电梯当前状态的参数过多,调度器无法简洁的确定捎带逻辑,容易出错:调度器在判断是否能够捎带当前请求时需要对当前主请求、当前运行方向、当前是否是去接主请求、当前运行楼层、当前电梯运行状态等一系列的电梯参数。不提同步的问题,这个判定逻辑已经因为电梯设计的原因变的异常复杂,设计者在思路不清晰的时候,出错的可能性也极高。比如,在捎带时,主请求是5->1,然而电梯需要先到五楼去接这个任务,此时如果有2->6的请求,调度器会因为满足前述捎带逻辑分配出这个请求,导致电梯去做一个不应该出现的开门动作。

  2. 不能捎带的任务如何处理的问题:最初遇到无法分配的任务,会将其塞回requestList里,然后一直轮询到可以分配为止,但是这样很显然会超出CPU时间限制,于是我在电梯中开了一个存放不能分配的任务的队列,在电梯捎带队列运行结束之后,将这部分请求回传给requestList,这样就避免了调度器无味的轮询,时序图如下图所示。

    技术分享图片

    但是,这样实现的缺点就在于,不能捎带的任务可能相互之间有捎带关系,但是这种来回反复的传递方式可能在打一个时间差的同时,就错过了捎带的机会,更关键的是,输入可能在此时早已经结束,程序也很可能因为这个回传的间隙错误的判断结束时机,导致在错误的时间点结束。

  3. 电梯过于信任调度器所维护的等待序列,在每次判断开关门时都是进行无脑判断,然而在上述分析中已然说明了调度器实现的不严谨性,因此这种不加防备的心态无疑会使电梯在运行过程之中酿下大错。

上面几点分析着实说明了此次架构设计的不合理,由于电梯与调度器分享信息的唯一途径只有共享的请求队列,而调度器又依赖于电梯的多项属性,这就导致了调度器也许不能拿到完全匹配的电梯信息,也就可能会做出不正确的决断,为了不将整体架构推倒重来,维持各部分之间的低耦合性,我将整个电梯与调度器此次作业增加的部分重新规划,改为了如下的设计。

改版程序分析与度量

整体程序架构变动不大,结构如图所示:

技术分享图片

可以看到,重构后的架构中,电梯明显变得更加复杂,而调度器则被砍掉了绝大部分的功能,变为了一个简单的分发器。虽然让电梯类维护更多的功能违背了SRP的设计原则,但是这却能在整体大框架不变的情况下,减少多次反复传递任务所导致的线程不稳定的情形。

更改后的设计中,电梯内部通过维护一个电梯内部有序的捎带队列与一个电梯外部的等待队列,实现了对于不同请求执行状态的清晰划分。此外,为了统一处理电梯内外的请求,我取消了显式的主请求mainReq属性,隐式的默认乘客队列的第一个请求为当前主请求。此外,我也修复了原来捎带逻辑中的逻辑漏洞,使用aimFloor属性清晰明确的代替了mainReqtoMain两个属性,并且考虑到电梯在处理完当前方向的请求时会静止不动,将原来二元的布尔型方向属性改为了三元的整型方向属性,避免了潜在的重复开关门浪费时间的问题。

复杂度分析

Class OCavg WMC
Elevator 4 64
Elevator.Status n/a 0
InputHandler 2 4
MainClass 1 1
PendingList 1 1
RequestList 1.43 10
Scheduler 2 6
Total 86.0
Average 2.867 12.28

由于插件在运算依赖矩阵时崩溃了,此处只记录循环复杂度。不出意料,电梯的复杂程度远高于其他类,内聚到了一种极致也许就成了一种臃肿。具体到方法我们有

Method ev(G) iv(G) v(G)
Elevator.Elevator(PendingList,int,int) 1 1 1
Elevator.addPassenger(PersonRequest) 7 9 9
Elevator.checkAssignList() 1 3 3
Elevator.close() 1 1 1
Elevator.elevatorFsm() 2 2 5
Elevator.elevatorFsmFree() 1 4 4
Elevator.elevatorFsmMoving() 1 2 2
Elevator.elevatorFsmWaiting() 8 12 15
Elevator.inPerson() 1 4 4
Elevator.move() 1 2 5
Elevator.open() 1 1 1
Elevator.outPerson() 1 3 3
Elevator.passenAllOut() 3 2 3
Elevator.piggyBack(PersonRequest,boolean) 6 2 11
Elevator.run() 3 4 5
Elevator.waitClose() 1 2 2
InputHandler.InputHandler(RequestList) 1 1 1
InputHandler.run() 3 4 4
MainClass.main(String[]) 1 1 1
PendingList.PendingList(int) 1 1 1
RequestList.RequestList() 1 1 1
RequestList.addRequest(PersonRequest) 1 1 1
RequestList.getInputStop() 1 1 1
RequestList.getRequest() 4 5 7
RequestList.isListEmpty() 1 1 1
RequestList.setInputStop() 1 1 1
RequestList.setStopSig() 1 1 1
Scheduler.Scheduler(RequestList,PendingList) 1 1 1
Scheduler.assignRequest() 1 2 2
Scheduler.run() 3 2 3
Total 60.0 77.0 100.0
Average 2.0 2.56 3.333

加粗部分即idea插件标红的复杂程度超标的部分,主要有添加乘客并维护乘客队列有序的addPassenger,处理开关门与乘客上下的状态机函数elevatorFsmWaiting,以及捎带的判断函数piggyBack。这几部分由于需要判断的东西比较多,因此复杂程度较高,可以考虑再细化拆分为更小的单元。

时序分析

时序图如下:

技术分享图片

不难看出该时序图与第五次作业的时序图逻辑非常相似,在把调度器功能削减之后,线程间需要传递的信息量也大幅下降,出错的概率也大大降低。

SOLID原则分析

  • SRP:电梯类的功能相对而言较多,内部存在一定的调度功能或许可以外包给一个小调度器
  • OCP:相对后续作业而言可扩展性较好,只需要增加调度器分发任务的方式即可实现多电梯协作
  • LSP:RequestList出现的地方都可以用RequestList的子类代替
  • ISP:未实现接口类
  • DIP:三个线程间没有之间依赖关系,都通过共享的RequestList来交互

作业小结

第六次作业真的被自己的怠惰与智商不够坑的很惨,最开始自己只是希望能够继续维护一个高内聚低耦合各司其职分工明确的一个电梯系统,然而自己似乎并没有get到多线程编程的精髓,在线程间的同步中屡屡碰壁。最为致命的一点是自己弱测第一次提交时评测机显示我全部ac,我改掉一个代码风格的问题之后再次提交却各种崩盘。这种以为只是小问题的谜之错觉真的可怕,最后时间有限只能拆东墙补西墙改的让人在风中凌乱,结果也自然只能在风中凌乱...希望这次能够给我敲响警钟吧,未来不要最后一天再去de这么致命的错误。

第七次作业

经历了第六次作业的风波,第七次作业在第六次作业重构之后也显得不难么令人为难了。本次作业主要增加了多电梯结构,不同电梯间具有不同的运行速度、停靠楼层、电梯容量。其实核心的内容只有两点:一是如何合理分配任务,而是如何将不能分配的任务拆分并阻塞。

程序分析与度量

程序基本结构

SS电梯相比ALS电梯而言,整体的结构并没有什么显著变化,依旧是三种线程与两种请求队列,程序结构如图所示。

技术分享图片

毫无疑问这次每个类都比之前复杂很多,在Scheduler中加入了对于任务类型与具体如何分配的判断,以及如果任务为需拆分的类型,应当以怎样的逻辑拆分。Elevator类中则加入了一种将孪生任务回传的机制,保证了拆分出的任务时间上的先后。具体一些实现机制会在后文中详细分析。

复杂度分析

Class OCavg WMC
Elevator 3.94 71
Elevator.Status n/a 0
InputHandler 2 4
MainClass 1 1
PendingList 1.2 12
RequestList 1.43 10
Scheduler 5.29 37
Scheduler.ReqType n/a 0
Total 135.0
Average 3.0 16.875

这次调度器和电梯一起集体阵亡,复杂程度都超标了,具体到每个方法有

Method ev(G) iv(G) v(G)
Elevator.Elevator(PendingList,RequestList,int,int,char,int) 1 1 1
Elevator.addPassenger(PersonRequest) 7 9 9
Elevator.checkAssignList() 1 3 3
Elevator.close() 1 1 1
Elevator.elevatorFsm() 2 2 5
Elevator.elevatorFsmFree() 1 4 4
Elevator.elevatorFsmMoving() 1 2 2
Elevator.elevatorFsmWaiting() 8 13 16
Elevator.handleBuffer(PersonRequest) 3 4 4
Elevator.inPerson() 1 5 5
Elevator.move() 1 2 5
Elevator.notFull() 3 3 4
Elevator.open() 1 1 1
Elevator.outPerson() 1 3 3
Elevator.passenAllOut() 3 2 3
Elevator.piggyBack(PersonRequest,boolean) 6 2 11
Elevator.run() 3 4 5
Elevator.waitClose() 1 2 2
InputHandler.InputHandler(RequestList) 1 1 1
InputHandler.run() 3 4 4
MainClass.main(String[]) 1 1 1
PendingList.PendingList(int) 1 1 1
PendingList.addBuffer(PersonRequest) 1 2 2
PendingList.getBuffer() 2 2 2
PendingList.getWaitingNum() 1 1 1
PendingList.isEmpty() 1 1 2
PendingList.isFull() 1 1 1
PendingList.remainDec() 1 1 1
PendingList.remainInc() 1 1 1
PendingList.waitDec() 1 1 1
PendingList.waitInc() 1 1 1
RequestList.RequestList() 1 1 1
RequestList.addRequest(PersonRequest) 1 1 1
RequestList.getInputStop() 1 1 1
RequestList.getRequest() 4 5 7
RequestList.isListEmpty() 1 1 1
RequestList.setInputStop() 1 1 1
RequestList.setStopSig() 1 1 1
Scheduler.Scheduler(RequestList,PendingList,PendingList,PendingList) 1 1 1
Scheduler.assignRequest() 1 6 8
Scheduler.distribute(PersonRequest) 2 4 15
Scheduler.distributeTwo(PersonRequest,PersonRequest) 1 2 7
Scheduler.judgeReqType(PersonRequest) 4 8 15
Scheduler.run() 3 3 3
Scheduler.splitRequest(PersonRequest) 1 1 7

加粗部分即idea插件标红的复杂程度超标的部分,addPassengerelevatorFsmWaitingpiggyBack都是上一次革命已经牺牲的老同志了,由于架构没有本质变化,这次他们依然慷慨赴死,这次为革命牺牲的还有调度器中的一些新方法,即判断任务类型的judgeReqType方法与根据不同任务类型完成任务分配的distribute方法。他们当中前者运用了大量的if-else判断,后者整个函数是一个大型的switch-case结构,由于任务类型区分的比较细致而讨论的相对较冗余,仍然有进一步改进的区间。

时序分析

本次作业的时序图如下:

技术分享图片

可以看出,基本的时序大框架没有变,只是调度器在分发任务之前,要做的准备工作变多了,并且是向三个等待队列里分发。

SOLID原则分析

  • SRP:电梯类的功能相对而言较多,内部存在一定的调度功能或许可以外包给一个小调度器
  • OCP:多电梯协作大体框架与之前基本相符
  • LSP:RequestList出现的地方都可以用RequestList的子类代替
  • ISP:未实现接口类
  • DIP:三个线程间没有之间依赖关系,都通过共享的RequestList来交互

随笔杂记

第七次作业其实有很多值得进一步去探讨的地方,比如分发任务的方式,程序终止的逻辑等等,下面把我能想到的一些与这次作业有关的杂七杂八的思路大致记录一下:

首先,大致可以得到如下的电梯楼层图,结合图片我们可以更为直观的进行分析。

技术分享图片

  • 请求分配篇

    从图中我们不难看出,输入的请求可以大致分为如下几种类型

    private enum ReqType {
      ELEA, ELEB, ELEC, ELEAB, ELEBC, ELEABC, SPLIT, BUFFER, NOTYPE
    }

    他们分别对应A电梯独占的-3,16-20层,B电梯独占的2,4,6,8,10,12,14层,C电梯独占的3层,AB共享的-1,-2层,BC共享的5,7,9,11,13层和ABC的公共楼层1与15层。这些类型之外还有一种任务,他们的起始与结束分别处在两部电梯的独有楼层,必须通过换乘才能到达。于是,在这种情况下,我们希望避免的情况是存在公共任务时的负载不均,即一个电梯埋头干,剩下两个吃干饭的奇妙场景。

    于是我采取了如下的分配策略

    • 独占任务直接丢给对应电梯
    • 在有公共任务时,优先给空闲的电梯;都不空闲时,优先给还没满的电梯;都满了的情况下,优先给等待队列人数少的电梯。

    但是,由于设计的原因,我无法在分配时预知分配到该电梯时,电梯的实际运行情况,因此,上述的判断电梯空与满的逻辑就成了判断等待队列与乘客队列人数是否达到容量上限的逻辑。开始时我取二者最大值来判断是否已满,但是通过实际测试证明这样判断效果不是特别好,因此我将评判标准收紧,改为判断两者的加和是否已达容量上限,结果稍微有一些改观,但是经过同学的强测分数,发现实际上还是不如直接拿来加权随机分配来的方便实用。

  • 请求拆分篇

    为了省事偷懒,我在任务拆分时尽量让两个孪生任务方向相同,除去魔幻现实主义的3楼之外,基本都能很轻松的拆开,代码如下。

    if (reqFrom > 15 || reqTo > 15) {
        req1 = new PersonRequest(reqFrom, 15, personId);
        req2 = new PersonRequest(15, reqTo, personId);
    }
    else if (reqFrom == -3 || reqTo == -3) {
        req1 = new PersonRequest(reqFrom, 1, personId);
        req2 = new PersonRequest(1, reqTo, personId);
    }
    else {
        if (reqFrom < 3 || reqTo < 3) {
            req1 = new PersonRequest(reqFrom, 1, personId);
            req2 = new PersonRequest(1, reqTo, personId);
        }
        else {
            req1 = new PersonRequest(reqFrom, 5, personId);
            req2 = new PersonRequest(5, reqTo, personId);
        }
    }

    根据前文电梯楼层图我们可以知道,换乘集中在上高层,下底层和去三层这三种设定之上,于是我们有了上高楼先到十五层,下底楼先去一层,去三楼请走楼梯...低于三楼去一层,高于三楼去五层。其实这么拆完全不是为了性能而是为了省事,而且由于任务拆分具有对称性,因而只要来去楼层有一个属于高、底层,一定会按前两种方式分,而剩下的情况一定属于魔幻三层,逻辑清楚,也降低出错概率。

  • 线程终止篇

    由于引入了孪生任务经过电梯后回传这个设定,就不免想到第六次作业的惨痛经历,但比第六次的混乱终止要好一点的是,这次我们不需要依靠电梯来发出终止信号,而是通过调度器存储孪生任务信息,在孪生任务全部终止之后结束线程。

    但是这样就不能让InputHandler来完成requestList终止信号的设置工作,潜在的风险则为如果没有孪生任务,即使在设置输入终止时notifyAll,在getRequest时会由于没有终止信号不能脱出while循环,一直等待不存在的后续输入。RequestListgetRequest相关代码如下:

    while (reqList.isEmpty() && !stopSig) {
        try {
            wait();
        }
        ...
    }

    于是,我通过设置一个布尔变量,在输入终止时及时脱出while循环,使程序得以正常结束。

    while (reqList.isEmpty() && !stopSig) {
        try {
            if (!init && inputStop) {
                init = true;
                break;
            }
            wait();
        }
        ...
    }
  • 杂记

    其实还有一些小trick最后没有用,比如在电梯空闲时稍微等一下,这样就不至于同一时刻来了可以捎带的请求但是电梯已经走了,在最后多出一大截往返接送。因为我把强测数据理解成到达时间也是线性随机的,就没做改动,只能略表遗憾。

作业小结

其实杂记里说了很多这次作业的一些思路,虽然不能说是最优的或者最高效的,但是确实是我在学习过程中的一些感悟与体会,就随手记录了下来。总而言之,这次作业相比前两次而言,难度还是略有提升的,但是这也应证了只要设计思路清晰,知道自己每一步在做什么,自己的程序才不容易出现问题,才能写出更加稳定的代码。

面向对象第二单元博客总结

原文:https://www.cnblogs.com/Kev7/p/ooBlog2.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!