• 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

一、第二单元电梯作业设计思路

第一次接触多线程的时候,一开始对作业的设计思路很迷茫。后来看了计算机实验的代码,觉得采用“生产者-消费者”模式比较合适。于是我模仿实验的思路,设计了InputHandler、Schedule和RequestQueue来实时处理和调度输入数据。事实证明,这种架构模式的设计是安全的,也是方便扩展的,因为我没有三次重构作业,只是在原代码的基础上修改和添加了代码。

1.调度器的设计:

这三个任务都是按照“生产者-消费者”的模式进行调度的。为了实现多线程调度,我们设计了InputHandler类、Schedule类、RequestQueue类、Building类和Circle类。Building类和Circle类分别封装了同一楼层(大楼)的RequestQueue和ArraylistElevator电梯。

RequestQueue类的实例化:1 waitQueue对象作为InputHandler、Schedule和所有电梯可以共享的对象。五个buildingQueue对象由每个建筑物中的调度和电梯共享。circleQueue这10个对象被用作可以由每个圆圈中的调度和电梯共享的对象。

调度程序的具体层次结构如下:

1rcgxxpcn0t3854.png

这种设计的好处是:通过一个调度作为中间层,将输入的请求进行分类,分配到每层楼(每栋楼)的requestQueue中。之后电梯运行时只需要读取其所在楼层(构建块)的requestQueue的内容,不需要判断请求。这个判断已经在调度层前面做了。它使我们的架构更加清晰,减少了电梯的代码量和复杂度,使电梯能够专注于自身的载客功能。

2.电梯运行策略设计

这三个作业都使用了LOOK调度算法。编写了策略接口,并将其实现为两个策略类:HorizontalLOOK和VerticalLOOK。电梯电梯不分垂直电梯和水平电梯,而是可以选择搭载垂直和水平LOOK算法。这种设计可以方便后续实现更多的调度算法或交换调度算法。以下面的单垂直电梯外观算法为例:

(1)策略类与Elevator的交互:

该类只需要向电梯提供三条信息:curDirection、ifOpen和Arraylistperson personToPick。有三种curDirection值:1(向上),0(保持静止),-1(向下)。所以设计了三个方法:flushMoveDirection,ifOpen,pickUpList。

电梯运行时间和策略之间的交互如下图所示:

owkimbxnrco3855.png

(2)LOOK策略的实现思路:

1.pickUpList:遍历requestQueue。如果有可以被接走的乘客(乘客离开的方向与电梯运行的方向一致),将他添加到personToPick中。2.ifOpen:如果有可以接的乘客(乘客去的方向与电梯运行方向一致),或者有乘客到达目的地,则返回true否则,返回false。3.flushMoveDirection:如果电梯内有乘客,保持当前运行方向。

;如果没有乘客,先检查requestQueue中是否有request。如果没有,则Elevator在requestQueue中进行wait(),Elevator线程让出CPU资源,等待notifyAll;如果有,那么分为两种情况:1.curDirection!=0,就检测当前电梯运行方向上是否还有request,如果有则保持前进方向,否则反向。2.curDirection==0,就选择前往离电梯最近的request的方向(或者电梯所在楼层有request时,选择当前request的方向)作为方向。

kebfm21r2ah3856.png

(3)多电梯自由竞争策略:

采用自由竞争的竞争策略。即所有同层(同楼)的电梯都共享一个requestQueue队列(层次结构可以参见上面的图),都可以访问和获取requestQueue中的请求,进行自由竞争,这样可能会在电梯运行时占用较多的输出资源,但是在性能上并不差,而且易于实现(懒)。 其他多电梯调度策略,比如有基准策略里使用的平均分配(请求编号mod(电梯数)),还有模拟策略。模拟策略就是先对运行时间进行模拟,找到一个最优的策略。但是如果采用模拟法的话,对于一个静态的请求集合可能能找出最优的策略,但是对于一个动态增加的请求队列来说,可能也只是局部最优解,无法找到全局最优解,因为要全局最优必须能“预知未来”,但是未来不可能预知。所以一个绝对最优的策略是不存在的,采用自由竞争策略也不失为一个好的办法。

(4)中转的策略:

第三次作业选择采用静态拆分的方法,在request刚进入InputHandler的时候进行拆分,所有的request必然能在3次运载内完成。所以可以按照运载次数将request分为3类:1次运载到达目的地,2次运载到达目的地,3次运载到达目的地。并计算出相应的midfloor。

在request类的基础之上,设计了MyRequest类,增加了workTime和workTurn属性,分别记录总需要的运载次数和当前运载的次数。当workTurn==workTime的时候,才会判定request执行完毕。而且MyRequest对外隐藏了midFloor,只是对外显示的fromFloor和toFloor会随着workTurn的改变而改变。

对于所有request的完成,参考了experiment4-2多线程设计的流水线模式,设计了一个信号量RequestCount用来标识request的完成,RequestCount采用了单例模式,是一个共享对象,由Main、Input Handler、Elevator共享。获得新的request时,counter++;完成一个reuest时counter--。当所有的request都完成的时候,总的线程才会结束。

RequestCounter与线程的交互如下图:

d3etncd3hml3857.png

3.线程安全——同步块与锁的设计:

三次作业中,采用前文所述的调度设计,可以得出我们的共享对象的类仅有RequestQueue、RequestCounter这两类,只需要对RequestQueue类、RequestCounter类进行加锁即可。

RequestQueue类主要有两个属性:boolean endSign(标识request的输入是否结束)、ArrayList<Person> requests(请求队列) 。这两个属性的状态均会被修改和查看。RequestCounter仅有int conter这一个属性,会被修改和查看。

根据课上所学共享对象的安全:对于共享对象中的属性,如果仅查看而不修改,可以由多个线程同时进行查看;如果要修改,只能有一个线程进行修改,且修改过程中不能有其他线程查看。也就是仅有以下两种情况正确:(1)n个线程查看,0个线程修改。(2)0个线程查看,1个线程修改。所以只需要将所有涉及到这三个属性的查看和修改的方法加上synchronized即可,而且在属性状态改变时使用notifyAll()唤醒其他等待的线程,实现wait-notify机制。

至于死锁问题,由于只有两个共享对象类,而且在俩共享对象中也没有出现获取锁去访问其他共享对象的地方。所以不会出现线程1访问A后访问B,线程2访问B后访问A这种互相等待对方释放锁的死锁现象。

二、整体架构展示和迭代开发过程:

1.第一次作业:

架构设计要点
  • 采用了“生产者-消费者”模式。Schedule类、InputHandler类处理请求,属于生产者。RequestQueue作为流水线。Elevator是消费者。

  • 电梯使用LOOK算法来进行调度。调度逻辑见上。

  • 重新设计了自己的Request类,方便在Request里添加一些内容。

  • 设计了Building类来容纳同一个楼座的多部电梯,为下一次迭代开发做准备。

  • 封装了OutputHandler,保证输出线程安全。

UML类图

gjnmbbswfd33858.png

2.第一次作业:

架构设计要点
  • 增加了Strategy接口,可以实现为HorizontalLOOK和VerticalLOOK两个类,分别指导纵向和横向电梯的运行。原有的LOOKStrategy重命名为VerticalLOOK,HorizontalLOOK仅需要在VerticalLOOK的基础上修改实现即可。

  • 增加了Circle类,实现和Building类类似,在addOneElevator的实现上有所不同,而且没有初始化电梯。

  • 电梯增加一个runModel属性,用来标识电梯是横向运行还是纵向运行,用来采取不同的策略和运行方式。

  • InputHandler可以调用Building、Circle增加电梯的方法。

  • Schedule可以将request分配给circleQueue。

UML类图

t4er11kdspn3859.png

3.第三次作业:

架构设计要点
  • 增加了RequstCounter类,作为控制信号量,使用单例模式,可由InputHandler调用accept()方法增加counter,可由Elevator调用release()方法减少counter,可由Main检查是否完成所有request。

  • 在InputHandler里进行静态拆分,使用private方法analyseRequest()将一个request拆分成几部分。

  • 在Request中增加了workTurn、workTime、midFloor属性对Request分步骤完成的过程进行描述。

  • 在Elevator中新增了canStay属性表示可以停靠的楼层,新增了moveTime属性可以定制移动时间,新增了waitQueue用来连接总的waitQueue可以在请求未完成时把它扔回到新请求队列中。

  • 在HorizontalLOOK策略类中增加了对canStay的判断。

UML类图

ezyye5ru0qo3860.png

4.UML协作图:

unw3ywlcoc43861.png

三、采用的设计模式

主要采用了单例模式和生产者消费者模式,模仿了一点exp4-2的工人模式。

单例模式是用于第三次作业的RequestCounter计数信号量,可以标识需要多次运载的请求的完成。

生产者消费者模式从第一次作业用到了第三次作业,就是设计了InputHandler、Schedule、waitQueue来进行请求的调度。

四、BUG分析

第一次作业:

1个bug,这个bug比较严重,因为我在搭载乘客时没有判断是否超过了电梯的运载量,导致电梯超载,因此在强测中挂掉了很多个点。我在Strategy中增加了对运载乘客数量的判断予以解决。

第二次作业:

1个bug,出现在横向调度算法中,因为我设置的是没有乘客时总是寻找最近的去运载,而忽略了在楼层可以接送的乘客的需求,导致在特殊数据点处横向电梯一直运行而不接客,造成RTLE。为了解决问题,我小修改了一下横向调度策略。

第三次作业:

2个bug,这两个bug都是比较隐蔽的bug。

其一,由于我在横向电梯的策略里面一开始思路是这样写的:如果等待队列没有人,就会wait,没有可以接到的人,那么就会保持在原地不动,但是不会wait,因此可能会轮询。因此,如果某层的等待队列中有人,但是某横向电梯又接不到人(不能在那开关门),就会造成电梯什么也不做但是也不wait,出现轮询现象,因此造成了bug! 这里改动比较大,主要在RequestQueue里在电梯进行获取等待队列时,如果等待队列不为空,需要加一个对是否等待队列里有可以运载的人的判断。

其二,由于没有考虑到一种情况:一个请求只在同一楼层中转移,在该楼层没有可以运载它的横向电梯,这时需要中转。但是我在写程序时,默认了以为所有的同楼层请求都可以不用中转而直接在该楼层运载。因此没有考虑到这种情况。因此,造成了RTLE错误。修改就是在InputHandler里进行静态拆分时,及时是同一层的运载请求也可以拆成3个阶段。

五、反思总结

1.好好听课可以事半功倍

初次接触多线程都是云里雾里的,实际上每次理论课都介绍了很多关于多线程的内容,认真听讲真的受益匪浅,包括轮询、死锁一些常见的多线程错误都有介绍,也从理论课上学到了关于多线程设计的基本思路,要抓住共享对象,给共享对象加锁保证线程安全,临界域要合适,不能过大或者过小。

2.实验的代码要仔细研读

每次实验的代码都是一个小的多线程模式的模板,比如exp3的生产者-消费者模式,exp4-1的主仆模式,exp4-2的工人模式。都很经典而且也比较短小精悍。所以可以从实验代码中学到很多多线程的知识。

3.一定要先设计、分析再写代码

第一次作业之前,头脑中要先设计好多线程的基本框架、想好要设计哪些类、哪些类是共享的、哪些是线程、各自负责什么功能。一个好的设计可以减少以后的重构,方便进行扩展。

4.要学会自测,构造数据

每次作业其实一些明显的bug是可以通过自己构造简单的测试数据来修掉的。起码每次再数据范围内的数据边界上的数据都要测试一遍,保证基本的功能不会出错,至于一些比较不明显的bug,可以通过随机生成数据来测试,当然数据的生成逻辑也要尽量覆盖到各种数据边界,不能只测一个地方。

Link to comment
Share on other sites