• 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

综述

本单元的任务是模拟多线程实时电梯系统,主要考察多线程操作和交互的实现。在这三次运行的迭代中,第一次运行只涉及几部电梯的运行和电梯与调度员的竞争;第二项工作允许同一楼层或同一座位的多部电梯运行。因为自由竞争策略,涉及到多部电梯竞争同一个等待队列。第三次分配,增加了换乘策略,增加了电梯的请求传输交互。通过三个作业的迭代,更加清晰地理解了同步块、生产者-消费者模型等多线程概念,了解了wait-notify机制的具体实现和内涵,使用同步块解决线程安全问题,学会了从请求输入到请求结束的分层设计和分析。

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

在同步块的设置上,同步设置在主线程和调度器线程共享的等待队列类上,以及电梯和分析类之间调度器共享的每个楼层或座位的等待队列上。在多线程操作中,主线程读取请求并将其添加到WaitQueue,而调度器线程从WaitQueue中取出请求并对其进行调度。两者存在读写竞争,需要设置WaitQueue的put和get方法来同步锁定WaitQueue对象,这样join请求和take-out请求就不会同时执行。类似地,电梯和调度员共享的分析中每个楼层或座位的等待队列的put和get方法应该被锁定。

但是对于电梯之间的竞争,由于电梯共享分析类,且分析类中电梯的get方法已经同步,所以最多只有一部电梯进入等待队列取出乘客,同层或同座的其余电梯线程需要等待这部电梯取出所有符合条件的乘客请求或进入等待状态,才能进入分析对象取出乘客请求。所以多部电梯会逐一接乘客,不会出现一个乘客进两部电梯等不安全的情况。

在锁的选择上,由于我的put和get方法是在与共享对象相同的类中实现的,所以我只使用设置put和get方法的同步块的方法来锁定和限制单个进程进入共享对象。

二、 调度器设计

我为这个单元作业的调度程序启动了一个单独的线程。这个实现在第一个作业中并没有表现出优势,但是在第二个和第三个作业中,因为调度器线程的存在,我在整理调度逻辑的时候非常清晰。

在调度器的设计中,我在scheduler类中设置了等待调度的用户请求队列waitQueue,以及存储各层水平等待队列和垂直等待队列的两个HashMap,其中键为整数或字符,值为乘客请求ArrayList。

在前两次操作中,因为没有换乘,要么出发楼层与终点楼层相同,要么出发座位与终点楼层相同,所以调度员的策略是从WaitQueue中提取一个乘客请求PersonRequest。如果起始楼层与结束楼层相同,则该请求应该由水平电梯处理,并且应该被添加到该楼层的水平等待请求队列中。如果起始楼层与结束楼层相同,则该请求应该由垂直电梯处理,并且应该将其添加到该座位的垂直等待请求中。在第三次分配中,增加了换乘策略,一个乘客请求由多个纵向和横向请求组成。所以不再是乘客请求本身的判断,而是乘客请求被拆分的第一阶段的判断,从而调度到正确的位置。

调度程序的交互包括与等待队列和电梯的交互。方法锁被添加到共享对象中,以实现对共享对象的唯一线程访问。

为了避免轮询,当waitQueue中的乘客请求队列为空且输入未完成时,调度器线程将等待,直到waitQueue添加新请求或输入完成,然后唤醒调度器线程进行调度或完成。

三、 三次作业架构迭代及协作

第一次作业

第一个任务的UML类图如下

mcllyenhjwc3271.png

第一次操作涉及五部独立电梯的操作。在该作业的框架中,MainClass mainclass用于初始化队列并启动线程,WaitQueue类用于存储等待调度的乘客请求,main thread类MainAnalysis用于读入输入并将其添加到WaitQueue,Scheduler线程类schedule用于将WaitQueue中的请求调度到相应的等待队列。

在电梯实现中,每个电梯对应一个等待队列和一个分析类,分析类存储该电梯等待队列的所有请求。每个楼层对应等待队列HashMap(等待列表),结束标志isEnd和电梯目的地destination。我采用了类似状态机运行电梯的策略,设置了枚举类Status,将电梯状态分为五种状态:空等停、上行、下行、上行、上行等待、下行_等待。在停止状态下,如果请求的总请求队列为空,等待避免轮询,直到put或setEnd的notifyAll,当请求不为0时,根据电梯调度策略判断接机乘客和下一个状态。在UP和DOWN状态下,如果有外出请求,就必须进入等待状态;否则,判断电梯所在楼层的等待请求队列中是否有满足搭乘条件的请求。

求,若有则WAIT,无则根据电梯内的请求与整体的等待队列进一步判断下一步状态。在WAIT状态必有开关门。在电梯进人的策略中,本次作业我首先在开门前将符合搭载条件的乘客加入至preToAdd等待加入队列中,若preToAdd不为空,则开门迎客,由于“量子电梯”的设定,在关门0.2s结束后我继续加入满足条件的搭载请求,并判断下一步状态,之后再输出关门信息。

  电梯调度策略选用look算法,即当请求方向上以及电梯没有请求再调转方向。该算法与ALS算法相比,可以在一次上下楼中搭载尽可能多的乘客,在随机数据中性能较好。

  扩展能力:设计电梯的策略时并没有特别仔细地考虑多电梯竞争的问题,可扩展性较弱。而设置了WaitQueue和调度器Schedule两类,使得调度逻辑更加清晰,未来改动更加方便,这部分的扩展性较强。

 

第二次作业

  第二次作业的UML类图如下

 cbcdgd5iesk3272.png

  本次作业添加了横向电梯与多电梯的要求。针对横向电梯,新增了横向电梯类FloorElevator和其队列分析类FloorAnalysis,横向电梯的运行与纵向电梯几乎相同,只是在方向上规定UP为(楼座+1)%5,DOWN为(楼座-1+5)%5。而关于横向电梯的调度策略,一开始我使用的是一种类似于纵向电梯的look算法,但经过实践后发现了一些不可避免的问题,如无限循环,逻辑混乱等,于是最终采用了基准的类ALS算法。同时,调度器新增floorAnalysisHashmap存储各层的横向电梯等待队列。

  针对多电梯竞争同层或同座队列的情况,首先是每个电梯的目的地有可能是不同的,因此将destination从Analysis移至Elevator中。针对多部电梯竞争同一队列的情况,我将电梯的进人策略修改为先判断是否开门(ifOpen()),开门后再进人。针对多部电梯同时到达一层而其中的人可以只被一个电梯就可以接完的情况,我会使得其他的电梯不开门去接其它层或其它座的人,因此在每个队列分析类中设置status,当第一个访问等待队列的电梯发现所有该层的人都可以被搭载,则将status置1,其它队列再调用ifOpen时会直接返回false。当第一个到的电梯载完所在层的人后再将status置0,这样可以使电梯分散接客,不用在一层中全都开门,效率更高。

  扩展能力:在实现换乘时只需要改变其请求类型即可,扩展能力较强。

 

第三次作业

  第三次作业的UML类图如下

 rowcc1p34w33273.png

 

  第三次作业新增乘客换乘与电梯的个性化定制要求。电梯的个性化定制有容量,速度和经停楼座信息。容量和速度只需要对所有涉及容量和到达楼层时间替换为电梯属性capacity和time即可。而针对经停楼座信息,本次作业采用掩码形式存储,横向电梯可以在满足((M >> (X-'A')) & 1) == 1(1)的楼层X上开关门,且搭载起点座为P、终点座为Q的乘客请求满足的条件为((M >> (P -'A')) & 1) + ((M >> (Q -'A')) & 1) == 2(2)。因此在电梯运行和进人策略中,若运行时不满足条件(1)则电梯运行状态不变,进人过程只判断满足条件(2)的乘客。

  由于出现乘客换乘,乘客的请求有可能需要多个纵向或横向请求的组合,因此设置RequestStage存储单个横向或纵向请求的起点和终点层座,设置RequestList表示一个乘客请求,内存有RequestStage队列,将所有涉及乘客请求的PersonRequest替换为RequestList。针对乘客请求拆分,我在主线程MainAnalysis中设置了getRequestList和resolveRequest方法用于拆分PersonRequest请求并返回一个RequestList,读入一个输入请求即进行拆分。但这么做,当某一输入请求在等待的过程中出现更好的换乘层时,请求无法被改变。因此还有一个想法是在电梯到达一层或一座时再将请求拆分,这么做可以优化这种情况,但由于时间问题没有实施。拆分策略与指导书一致。

  由于换乘的出现,WaitQueue中等待调度的请求来源不再只是输入主线程MainAnalysis,还增加了所有电梯,每部电梯新增waitQueue。因此,程序的结束标志改变为输入主线程结束且输入主线程的请求数preNum等于请求的完成数finishNum。电梯和调度器在读取乘客请求信息时,只读取RequestList中第一个RequestStage信息。当电梯处理完乘客请求的一个stage时,判断此时RequestList中是否只有一个阶段,若是,则释放,并让WaitQueue中的finishNum加1。若不是,则删除第一阶段,重新将请求投入WaitQueue中。

 

UML协作图

  协作图如下

 lee5kelh0t43274.png

 

四、 分析自己程序的bug

  本次作业表现并不理想,bug较多,尤其是第二次作业。

  第一次作业只有一个bug。没有考虑清楚输出线程不安全问题,直接使用官方包输出,导致出现后序时间小于前序时间的问题。解决方法为新增Output类封装输出方法并加锁,使得同时刻只有一个线程调用输出方法,保证了时间的有序性。

  第二次作业翻了小车。本次作业的中测、强测和互测我的横向电梯使用了类look算法策略,不仅写得痛苦写得麻烦,还出现了很多错误。如无限循环问题,look算法要求不断判断其运行方向上有无乘客,因此当电梯判断的运行方向上一直有与其运行方向相反的乘客时,电梯会一直在这一方向上无限循环且不接客,针对这一问题加了对判断次数的限制。

  此外,轮询问题也是这次作业出现的重要问题,其中一处轮询是由于对wait-notify机制理解不够,所有加锁方法的结尾均加了notifyall导致两个共享队列的线程等待时出现无限互相唤醒的情况,解决方法为只在改变队列状态时notifyall。另一处轮询是下一步状态判断错误,修复了下一步状态的逻辑解决该问题。

  在改完后,横向电梯的类look算法已经面目全非,无法有效保证其正确性,因此在bug修复完成后,将横向电梯的调度策略全面更换为指导书中的类ALS算法。

  第三次作业,在自己测试时发现自己的容量判断与经停判断并未设计完善,缺少对乘客请求终点座经停的判断。修复方法为将所有之前的容量6替换为电梯容量capacity,更改乘客请求判断条件为指导书中所说的((M >> (P -'A')) & 1) + ((M >> (Q -'A')) & 1) == 2。其他官方测试未发现bug。

五、 分析自己发现别人程序bug所采用的策略

  对在做作业的过程中自己发现的一些坑点构造数据和自己自测时出现bug的数据,用这些数据测试他人的程序。如无限循环问题,乘客请求楼层数相同但没有直达楼座的电梯时会不会出现卡死现象等。

  本单元测试策略与第一单元相比多了线程安全的保证问题,可能会出现输出顺序不正确,一人进两梯,一人自始至终不进电梯,轮询等问题,针对这些线程不安全的潜在现象构造数据进行测试。

六、 心得体会

  本单元的作业一开始做得挺别扭。对于生产者消费者模型、多线程运行与竞争以及线程安全的保证的理解都没有很透彻。在一点一点打磨、构建和debug的过程中对这些问题有了更深入的理解。下面是我的几点收获:

  1. 对方法块加synchronized关键字,其限制对象为this,只需要对线程所用的共享对象中的方法使用该关键字即可保证大部分的线程安全问题,不需要额外的赘余操作。
  2. notifyAll只用于唤醒wait中的等待进程,被synchronized关键字阻塞的进程不是wait等待进程,不需要时时唤醒,只需要在共享对象属性发生改变时再notifyAll。
  3. 层次化设计的理解更深刻。从输入到调度到电梯接入,层层递进。线程之间的交互与竞争使用synchronized关键字保证。
  4. 本单元作业对于一些必要的继承没有实现。如电梯的重复属性和重复方法等,应该有一个父类电梯和子类纵向和横向电梯。在做作业时应该大致画出结构图,使用必要的继承处理公共属性与方法,提升代码的可读性与简洁性。不断学习优秀架构,向更加优秀的代码迈进。
  5. 正确性为王。对判断条件等细节的把控要更加精益求精。
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