• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

OO第二单元总结

同步块与锁

多线程编程的目的是为了加快程序的运行速度,资源会在线程间共享,自然会出现类似流水线C PU中读写不一致的问题,所以需要正确锁死。

通过阅读培训课程和相关资料,我了解了原子操作的概念和各种锁定方法。虽然还有更高级的条件锁、读写锁等。它们不利于电梯性能的提升,更容易出错,所以我最后采用了最简单的同步锁。

接下来是同步模块的设计。通常,有两个地方涉及同步块:

一种是分享对象本身。因为每个引用都可能修改内部变量,所以除了构造函数以外的每个内部方法都需要锁定对象本身(JAVA的特性决定了在C语言中对象基本上是以“指针”的形式出现的,所以只需要传递参数并锁定即可)

二是在线程内操作共享对象的时候。虽然共享对象的内部方法已经被锁定,但是共享对象还是会被它的线程读写,其中的写操作显然需要被锁定,而如果读操作没有被锁定,其他线程可能会把改变后的状态写入其中,所以需要被锁定。这涉及到锁定的粒度。因为不是一个方法中的所有语句都涉及读写操作,所以我只锁定涉及读写的地方。这使得锁定更加灵活,同步块不会过于臃肿,在线程较多的情况下也能提高性能。

调度器设计以及与线程交互

因为我采用“自由竞争”模式,所以我的调度器没有复杂的算法,只涉及接受来自输入线程的请求,并根据它们的信息将它们分配到不同楼层和建筑物的等待队列中。

调度器充当输入线程和电梯线程之间的桥梁。调度程序通过总等待队列与输入线程交互,而电梯线程通过楼层队列与调度程序交互。

在第七份工作中,因为一个乘客的需求被拆分成不同的阶段,电梯也可能成为生产者。这时,我选择让请求进入总等待队列。

总结起来就是三个“生产者3354消费者”交互:输入——总等待队列3354调度器、调度器3354楼层等待队列3354电梯、电梯3354总等待队列3354调度器。可以看出,调度器是线程间交互的核心枢纽。

架构设计

第五次作业

UML类图

u0cd0znzwxc4272.png

UML协作图

q2gfretvurx4273.png

hw5的核心是建立多线程框架和wait - notifyAll编程模式。它的架构设计和配合比较简单,就是两对输入——总等待队列,3354调度器和3354楼层等待队列,3354电梯的生产者和消费者。所有线程都是由主线程启动的,一个线程的结束是由一些内部标志来判断的。为了防止输出时间戳减少,我锁定了输出类,以确保输出时间戳单调增加。

从可扩展性来说,虽然这个工作相对简单,不需要调度器,但是调度器更适合更大规模更复杂的设计,所以我第一次加入了调度器。

第六次作业

UML类图

wled1ydexcr4274.png

d-end-block md-heading">UML协作图

plbdwt2em4b4275.png

hw6相较于hw5,其一需要新增横向电梯类与横向电梯请求队列,其行为和属性与纵向电梯高度相似,比较简单;其二是在输入线程内部也可以新增电梯线程。

第七次作业

UML类图

voormc1koxj4276.png

UML协作图

wrwsq1h3h4q4277.png

hw7复杂度比hw6提高了不少。首先是电梯的“定制”,定制容量速度实现较为简单,而定制横向电梯可达楼层牵涉到的比较复杂。故我新增了一个策略类,其被输入线程、调度器线程共享。每当新增横向电梯时输入线程对策略类内部储存的可达性矩阵进行更新,而调度器线程内部使用策略类帮助新增乘客请求依据基准策略寻找换乘的楼层。

对于乘客请求需要分解的问题,我在乘客类内部新增变量stage用于标记当前乘客处于哪一段请求,依次为:第一段纵向乘坐、横向换乘、第二段纵向乘坐,并在电梯线程和调度器线程中根据乘客的信息对其进行修改以灵活调度。

对于结束线程的问题,由于可能存在乘客仍在换乘途中但输入已经结束、并且此时等待队列均为空的情况,此时若仍然采用前两次作业的判断条件会导致无法送达,故我在总等待队列类中增加了两个计数器分别记录总请求数与已经完成请求数,只有在二者相等且输入结束时才会终止线程。

bug分析

自身bug

第一次作业比较惨烈,原因有二:其一是加锁对象不对,直接对等待队列类中某一层的队列加锁,故导致其他线程此时仍可以读写请求;其二是判断终止条件不对,只判断输入结束没有判断楼层等待队列是否为空变提前终止线程,导致了有些乘客无法送到。

后两次作业互测与公测均无bug

他人bug

主要是结合常见问题与自动评测机结进行hack,如输出未加锁导致时间戳问题、等待条件设置错误导致轮询、策略有问题导致特殊数据死循环等等。此外,使用评测机可以更快地发现他人程序中的错误,之后再结合数据阅读代码可以更快地定位错误。

对于轮询问题,有两个好用的方法,一是测试时打开任务管理器,查看实时的CPU使用率,若过高则说明存在轮询问题;二是使用linux下命令行加入time指令,运行结束后可以直接查看程序的CPU时间

心得体会

线程安全

线程安全是多线程相较于单线程而言难度较大的地方。其存在三个问题:读写、死锁以及轮询。

对于读写,其有些类似于上学期计组课设流水线CPU设计。通过本单元的学习,我掌握了基本的确保线程安全的方式,学会了正确地加锁以及如何尽可能灵活地加锁(而不是一味地使用笨重的synchronized对整个方法加锁)

对于死锁,应该采用正确的wait--notifyAll方式编程,并回避循环引用

对于轮询,我设置了合理的等待条件,使得电梯以及调度器线程可以在合适的时候进入休眠,避免占用过多的CPU资源

层次化设计

层次化设计在应对较大规模的工程问题时十分重要,我们需要将较大的问题分解为几部分,再针对各个部分内部的任务进行完成,最后在各部分间的接口上完成连接,构成树形结构。

具体而言,对于本单元作业,大致有“输入——分配——完成”三个阶段,以乘客类为核心对象,针对三个阶段分别设计输入、调度器与电梯三个线程,并让他们通过共享队列进行交互。这样有利于迭代开发与扩展,也有利于在出现bug时有针对性地维护

反思自己的不足之处在于后期没有把训练中有用的知识加以运用。如单例模式、流水线模式都可以有效简化设计,但我仍然采用了之前的方法。虽然完成了作业,但显然不够优雅。面对实际工程规模的问题时,采用更合适的设计模式与层次化设计十分重要。

附:look算法

第一次作业由于出现bug强测只有78分,后两次虽然没使用任何bug,仅仅采用自由竞争与基准策略,但都得到了99分以上。简要分享一下自己的look策略

虽然教程上建议是ALS算法,但其需要计算“最早”的请求并设置住请求。为了追求一种更简洁和高效的设计,我采用比较常用的look算法并稍作修改。

具体而言,电梯相当于一个Mealy型状态机,它根据本身运行方向与楼座中乘客请求来决定此后运行方向

纵向电梯

运行状态

将电梯设置为上行、下行与静止三种状态。

关于设置静止状态:笔者认为,若只有上行与下行两种状态而让电梯一味停留在一楼或顶楼会使性能下降。从统计学角度而言,乘客请求出现在中间8层楼的概率是出现在顶楼底楼的4倍,故应该让其将所有乘客送达后停下。

运行策略

捎带

与ALS相同

方向改变

捎带策略意味着,若当前电梯内有人则其请求方向必然与电梯运行方向相同,故只有电梯为空时我才会改变电梯运行状态。

静止状态下:电梯初始处于静止状态,故电梯会扫描整栋楼,寻找并前往距离当前位置最近的请求。若当前位置新增乘客,则让其进入电梯并将方向设置为乘客请求方向。

有同学寻找的是距离最远的请求,而我的观点是,我们的实时交互系统随时会投入新的乘客需求,故当前最优并不意味着绝对的最优,优先响应最近的请求可以让我们的电梯系统反应速度更快,进而提高性能。而在实际与对拍的过程中,对大量数据进行统计后我的也确实会快于同学类似的架构。

运行状态下:如前文,此时电梯内无人。若当前方向上有请求,则会继续前行(例如目前电梯处于5楼、上行并且电梯内无人,若6至10楼有请求,电梯就会继续上行);若没有请求,则会采取与静止状态相同的调度算法。解释如下:

纵向电梯为单程运输,若电梯反复改变方向会导致性能下降,故我们需要让电梯响应请求,在当前方向上运行得尽可能远,以实现性能最大化。

若当前方向上无请求后,起初我采取策略是检查反向。但实际上,电梯此时无论是折返还是静止,都与从静止状态下响应没有差别,故采用相同策略。

优化细节

为了尽可能最大化性能,还有如下的调度细节:在一个循环内,我会在电梯改变方向前和改变后各给乘客一次进入电梯的机会;通过设置标志位让电梯仅开一次门;同时在线程sleep400ms后再让乘客进电梯。

这样有三个优点:在电梯折返后可以接上之前没捎带的反向乘客:让电梯仅开一次门意味着在保障正确性的情况下,有相当大的概率可以减少0.4秒的等待时间:而关门前让乘客以“纸片人”的形式进入电梯意味着可以捎带此期间新增的通向乘客。

横向环形电梯

运行状态、捎带策略与优化细节类似,不在赘述。唯一区别在于方向改变:

在讨论改变方向前,首先看一下对于楼座和乘客请求方向的处理。

楼座和乘客请求方向

我没有直接采取A~E的表示。由于环形电梯的复杂性,直接采取字母可能会让人迷失在细节里。而实际上环形电梯与环形队列类似,都暗藏着“循环”的意思。故我采用了整数对5取模的算法,0~4对应A~E。这种实现更符合人的认知,也更便于进行电梯方向的设置和算法的调度。

uzogzhv43iv4278.png

在此基础上,乘客把自己距离最近的实现方法作为请求方向:(例如:对于A座出发的乘客,D、E为负方向,B、C为正方向),这样的好处不言而喻,可以直接缩短运行时间。

调度算法

横向电梯静止时调度与纵向类似:寻找最近的请求。

而在运行状态下,与纵向电梯不同的一点是,若只考虑前方是否有请求,而忽视其方向是否一致会出现死循环,例:

xel5r0ez2el4279.png

电梯首先相应B座请求,但其到B座后发现乘客方向相反,无法进电梯,会继续前进,形成电梯一直运行但无法进入乘客的死循环

对此,有的同学认为可以采用单方向运行的方法解决,但从统计学角度而言,有相当大概率会出现卡性能数据,这种调度算法虽然也可以完成,但性能严重下降。

综合以上因素,我对算法做了改进,改为判断当前方向上两个楼座的队列中是否有同方向请求,如果有则前进,否则采取静止时的策略。这样兼顾了正确性的同时,又最大化了性能。

多部电梯:自由竞争

从统计学意义上讲,按照算法分配和让电梯自由竞争都不是全局最优解。算法调度可能会存在极端数据性能下降、忽视特殊情况导致无法完成需求等状况,而自由竞争虽然对于特殊样例性能也会下降,却可以避免正确性问题,且实现比较简单。综合上述因素,我选择了比较简单的自由竞争

换乘:基准策略

最后,换乘采用的是基准策略。起初针对可能同一个楼层存在横向电梯换乘的现象,在自己的策略类里面建立了一个可达性图。但后来考虑到电梯开关门同样存在不小的时间代价,且这样设计有可能导致乘客无法乘坐换乘途中新增的直达电梯,故我最终还是换成了基准策略。

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now