• 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

BUAA_OO_2022 Unit2 总结

一、第五次作业

  1、同步块的设置和锁的选择

这是第一次写多线程程序,还不熟悉,所以从计算机代码中学到了很多,也懒的回避了一些问题。线程分为输入线程、电梯线程和调度线程。在我的第一个工作中,输入线程和调度器线程共享一个通用请求队列,调度器和五个电梯共享五个请求队列。因为我在第一份工作中不太懂同步块和锁,所以我暴力地给所有共享对象的方法加了锁。也是因为对同步块不熟悉,所以我让每个电梯把请求拿出来存储在自己里面,尽量避免冲突,为下一个作业增加工作量。

但是,虽然我尽力让线程独立,还是有一个问题:3354,输出时线程不安全,时间戳没有严格增加。虽然说明书上有说明,多线程调用时要保证输出包的逻辑性,但我当时对多线程的粗浅了解,还不足以让我理解调用输出包会出现什么问题。直到在讨论区看到帖子才知道,对于输出的过程,可能会出现A获取时间戳,B获取并输出,A最终输出的情况。只有雾化这个过程,才能保证在一个输出过程中,另一个输出不会临时插队。

  2、调度策略

在第五个作业中,调度器没有起到任何实质性的作用,只是从总请求队列中获取请求,并将其添加到相应建筑的请求队列中。请求的处理完全取决于电梯本身。电梯会在开关门和运行的间隔时间检查共享队列中是否有请求,如果有,就取出来保存在自己的队列中。对于它自己的内部请求,它将被分为上车和等待。在请求的处理中,采用“出进”的策略,而电梯的运动完全依赖于一个获取方向的函数。每打开一次电梯门,增加一次请求,就会判断一次下一次运行方向。如果电梯中的请求需要向前移动,或者在移动方向上有请求等待,电梯将继续向前移动。如果所有的请求都没有得到满足和处理,运行方向就会改变,按照同样的逻辑进行判断。这是把请求交给电梯自己处理,后续操作还会继续使用。

  3、UML类图

hpqkitbln5a5213.png

在第五个作业中,InputThread和Schedule共享一个通用请求队列,由InputThread接收和添加,由Schedule取出和分发。调度还与各电梯共享请求队列,实现请求的分配。

  4、bug分析

这个赋值有两个bug,一个是不安全线程的问题,是同步块和锁的陌生性造成的,一个是逻辑问题。当我得到电梯的运行方向时,即使满了,内部乘客的目标楼层是反方向的,当有移动方向的请求时(电梯满了时,等候队列中的请求应该忽略),移动方向不会改变,但当我到了请求的楼层,没有人下,也没有人上,这就导致了电梯突破1~10层的限制的可能性。不经意的考虑,再加上在测量满载时为了省事没有更改所请求的目标楼层,导致无法发现这个明显的bug。只能说测试一定要更全面。

在黑别人的时候,黑主要是针对线程不安全。具体来说,大量的请求以固定的时间间隔被同时放入,以最大化时间戳不会增加的可能性。

二、第六次作业

  1、同步块的设置和锁的选择

在第六个作业中,第一个作业中同步的冗余首先被删除。然后,在第二份工作中,我选择了一种电梯共享一个请求队列并对其进行访问,而不是每台电梯单独有一个请求队列,所以我在处理进出乘客时锁定了请求队列,但在判断是否需要开关门和获取电梯方向时没有同步。这样,同一楼层或楼层的电梯在面对大量请求时,可以节省一些时间。只有请求队列被锁定,因为所有的更改都发生在请求队列上,所以您只需要锁定请求队列。即使当一个新的请求被添加到请求队列中时,该队列也会被锁定。

  2、调度策略

在第六个作业中,调度器仍然没有发挥任何实质性的作用,它仍然只是分配请求。刚开始我也考虑过要不要写平均分,但是想了想,我觉得让电梯自己竞争请求是一个简单高效的方法,只是要小心冲突的发生。如果调度策略简单,平分秋色,虽然没有冲突,但其效率在很多情况下不如自由竞争。但如果获取电梯状态,计算分配请求状态,虽然理论上更快,但容易出现问题,所以综合考虑后选择自由竞争的策略。

  3、UML类图

alxbqh4szdz5214.png

这个分配主要是增加水平电梯,每个和每个楼层可以有多部电梯。的整体框架不变,仍然使用共享请求队列分别连接输入和调度器、电梯和调度器。对于新增加的内容

的横向电梯,我将其方法写入了原本的电梯类中,通过isBuildingType()判断是否是横向电梯,在各种判断中利用这个函数选择调用哪种判断方式。因为电梯的类似,大部分的函数是可以共享的,减小了代码量。相比较第一次作业,我还将电梯线程的启动放入输入线程中,首先启动基本的电梯线程,之后在新增电梯时再新增线程,同时记录所有的线程以防需要删除电梯。

  4、bug分析

  在本次作业中,依然出现了电梯跑到不存在楼层的问题,这次的原因主要是因为我锁的范围比较小同时没有控制楼层的范围,而且在我的程序中,当进行完开关门后会进行一次移动。在最初我将判断开关门及一系列操作原子化,但是这样同一楼座的电梯在同一层会浪费比较多的时间,所以我最终只将进出乘客的部分同步,也因此会出现这样一种状况:A电梯正在第10层开门,此时没有上锁,且B电梯来到了这一层,B电梯可以访问请求队列发现有请求待处理于是开始开门,此过程中A电梯开始进出乘客并将请求队列清空,B电梯在A电梯释放锁后没有接到乘客,所以不会改变运行方向,但是因为B电梯进行了开关门,所以会有一次移动,从而会跑到第11层,我在修复时判断只有电梯内不空且等待队列不空才移动,修复了bug。这个bug只有在1或10层且不同电梯都进入处理过程中才会触发,比较难看出,所以在自行测试时没有发现。

  在hack别人时主要是针对自己写代码时发现的bug,最主要的是一个线程对共享对象进行遍历时另一个线程对共享对象进行修改从而导致的错误。

三、第七次作业

  1、同步块的设置和锁的选择

  本次作业的改变是电梯可以定制并且请求可以不同座不同层。因为先前作业的bug,所以这次我选择由调度器分发请求来减少冲突发生的可能性,所以需要锁住的地方就是添加以及删除请求的位置,此外就没有什么需要同步的地方了。

  2、调度策略

  在第三次作业中,调度器终于发挥了作用(可喜可贺),所有的请求都由调度器进行精细的分配。本次作业中,对于复杂请求的路线规划是最难处理的,我最终采用的办法是直接指定横向电梯,因为在动态选择的过程中出现了一些bug。对于一个请求,它会有当前目的地和最终目的地,电梯的判断都是基于当前目的地并在送达后将请求投回主请求队列,如果未抵达最终位置,则由调度器再次计算当前目的地并分配出去,分配时优先考虑速度快乘客少的电梯。电梯则根据自身的请求队列,按照之前作业的逻辑运行。

  3、UML类图及UML协作图

ypee1nvxby25215.png

23mrj11ufg15216.png

  本次作业的改变是定制电梯以及复杂的乘客请求,虽然需要更多的判断,但是整体框架依然没有改变,直接在上一次作业的基础上进行进一步的开发便完成了作业。主要的不同之处在于本次作业中让调度器首次发挥了作用,并且因为电梯也会新增请求改变了线程的终止条件。总体上是只进行了增加,以及少量的修改。

  4、bug分析

  本次作业在互测中被多个新增电梯请求后接一个单请求刀中,检查代码并在本地测试数十遍后仍未复现问题且在再次提交后通过该数据,推测可能是上锁的范围小了。

  在互测中发现有些同学对于电梯可达性的判断不够充分,只判断了可达目标楼座,忘记判断是否可达出发楼座。

四、hack策略及心得体会

  我的hack策略主要是根据自己编写程序时遇到的问题构造数据以此来hack。但是我并不能考虑到所有的情况,忽略的情况才是最容易hack别人的数据,所以对于共性的隐蔽错误我难以发现,只能尝试别人是否有我之前的错误。手动评测还有一个问题是有的错误可能需要跑多次才能出现,自己测试跑过一遍OK就换另一种可能的数据了,用随机测试不停测试却能发现问题。

  通过本单元的三次作业,我对多线程有了更深的认识,也对锁有了一定的了解,并深刻体会到了多线程并发时状态的多样性,对如何避免冲突也有了一些收获。在debug以及hack别人的过程中我认识到了对于这种有大量输出的程序而言自动评测的重要性,纯靠自己测试终究是有极限的。

  虽然在本单元出现了一些愚蠢的错误,但是都只是需要修复而非彻底重构(可能也是因为模拟电梯的框架比较固定),后两次作业都是在先前作业的基础上完成的,虽然第二次因为第一次的偷懒改了不少地方,不过整体思路并没有改变,而是延续了下去,所以实际上并没有花太多时间。

  总体而言这个单元确实是收获满满,电梯的调度是一个非常有意思的问题,但比较可惜的是最后一次动态规划路线时出锅了,为了保险最终还是直接敲死路线,还有就是下次一定要写自动测试,手动测试又痛苦又测不全,不能再重蹈覆辙了!

Link to comment
Share on other sites