• 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

第二单元博客作业

第五次作业

UML类图:

bmmm0h0jfs05065.png

架构思路:

本次作业只有5台固定垂直电梯,处理的请求相互独立,处理起来相对简单。线程设计基于生产者-消费者模式,输入通过一个线程临时存储在缓冲区请求队列中。五部电梯中的每一部都有一个线程(可以设置在主线程中)来模拟电梯的自主运行,同时分别维护自己的等待队列和电梯中的人的队列,然后构造一个调度器线程将缓冲区中的请求分配给相应楼层的电梯。

在这个架构中,输入线程和调度线程共享请求队列缓冲区,调度线程和每个电梯线程共享一个等待队列。为了方便起见,我封装了一个基本的线程安全请求队列类来实现这些共享队列。除了在电梯类中遍历队列等一些复杂的操作外,还需要锁定队列类实例,以保证一系列操作的原子性。其他添加请求的地方只需要调用queue类中的线程安全方法,不需要加锁。

为了避免轮询,使用了等待通知机制。当试图从队列中获取请求时,如果队列为空并且没有收到输入终止信号,您可以等待队列实例,释放占用并等待新的请求加入。相应的,添加一个请求或者写一个输入终止信号,可以更新队列实例的状态,需要及时执行notifyAll,唤醒等待的进程,让它处理新的请求或者终止。

关于电梯的运行策略,我采用了说明书上标准的ALS策略,为了便于实现修改了一点逻辑。

UML时序图:

ay3qi0b3x3c5066.png

可以看出,输入线程和调度线程依靠共享队列缓冲区传递消息,调度线程和电梯线程依靠共享等待队列传递消息;大多数情况下,每个线程独立运行,每个线程执行自己的功能。

第六次作业

UML类图:

dlis0jylrkn5067.png

架构思路:

与上次作业相比,本次作业增加了对水平运输的要求和对动力电梯的要求。乍一看很复杂,但是稍微分析一下就会发现,横向请求是纯粹的,实际上完全可以和纵向请求独立分开处理。

模仿垂直电梯的实现,很容易认识到水平电梯类负责处理水平运输请求。对于输入的请求,调度员可以根据它们的类型将它们分配给相应的电梯。好像电梯数量只比之前的运行增加了。

另外,由于需要动态添加电梯,不像上一次操作一栋楼只有一部电梯的情况,可以简单的在主线程中打开,需要建立新的数据管理结构。我的方法是分别对楼层和楼层建模,每个楼层实例管理相应的垂直电梯列表,每个楼层实例管理相应的水平电梯列表。在这两个类中,分别实现了添加电梯的方法,这样当调度程序检测到添加电梯的请求时,就可以通过调用对应实例的这个方法来完成请求。

对于单个电梯的运行策略,垂直电梯遵循之前的ALS策略,水平电梯同样实现说明书上的捎带策略。当同一栋楼或楼层有多台电梯运行时,调度器通过调用其调度方法将请求传递给该楼(层)实例,在调度方法中,请求被分配给“最不忙”电梯的等待队列。这里的“最闲”是用电梯排队人数加上电梯内人数之和来衡量的。金额越小,越闲置。这种测量方法虽然看起来简单粗暴,但确实可以最大程度的避免部分电梯的“钓鱼”,所以整体表现尚可。

UML时序图:

与第五个作业相比,第六个作业主要在数据管理结构上比较复杂,消息协作的性质基本没有大的变化,所以没有给出序列图。

第七次作业

UML类图:

rn25lzbljgt5068.png

架构思路:

这种分配增加了电梯速度、容量以及水平电梯的开门和关门信息的定制。同时,乘客的要求不一定是单纯的垂直或水平运输就能解决的,需要换乘。

/p>

对于速度容量以及开关门信息这些电梯属性,直接在电梯类中修改即可,较为简单(不过需要注意横向电梯运行时,在不能开门的楼座不能停下更新载人状态);不过换乘的实现就较为复杂了,为了充分利用之前的架构,我选择在我看来比较自然的动态换乘方法:调度器接收请求后根据请求所处位置与请求最终目标位置为请求选择一个合适的暂时目标位置,并将其投入相应的楼座(层),由某部电梯送达暂时目标位置,之后电梯判断送达的请求位置是否与请求的最终目标位置重合,若是,申报请求处理结束,否则,将请求重新投回,可以证明,每个请求至多通过三部电梯运送必能到达目的地。

在不是很考虑性能问题的前提下,难点在于请求如何再次投入,以及由于再次投入带来的无法简单根据输入线程取到空行设置结束符的问题(因为即使外界不再输入请求,由于换乘需要,电梯会反馈新的请求),我的解决方案是首先将之前输入线程与调度器线程共享的缓冲区buffer包装成单例模式,这样在电梯线程中重投请求就变得十分简单;判断输入结束方面,我利用单例模式建立了一个请求计数器来记录已完成但未查收的请求个数,初始计数为0,代表已完成0个请求,计数器类中有两个重要方法,一个是release方法,是计数加一(同时需要notifyAll),代表完成一个请求,由电梯线程将请求送至最终目标时调用;一个是acquire方法,若计数大于零令计数减一,计数为零则wait,代表查收一个完成的请求,由输入线程在输入结束后调用等同于输入乘客请求个数的次数,表示查收所有输入的请求。这样通过让输入线程在没有查收到所有请求已完成时等待,最后再设置输入结束标志就可以解决所有问题。

UML时序图:

大致的消息传递结构不变,区别有如下几点:

Buffer利用单例模式作为全局变量,增加从电梯线程向Buffer的请求传递(由于换乘);

设置RequestCounter类管理输入线程的终止,电梯线程完成请求时调用release向其传递消息,输入线程记录外部请求数量,调用require查收完所有请求再setEnd。

锁的选择以及调度器的设计:

在本单元我仅仅使用了synchronized关键字来实现互斥锁的功能,并未使用一些更复杂的自定义锁(主要是怕出错),但是已经足够了。在我看来,最优的加锁方式是包装线程安全类,对常用方法本身加锁,这样可以避免外部调用时繁杂的加锁问题,不过需要注意,除非线程安全类的方法设计的十分完美,当出现例如外部的循环中调用方法时,为了保证整体操作的原子性还是需要整体加锁的。关于锁什么对象,比较简单且符合直觉的方法就是对共享对象加锁,保证对共享对象的访问是互斥的。

调度器的话每个人的实现可能区别很大,甚至很有可能没有一个明显的调度器类。至于我的实现(主要指后两次作业),创建了一个调度线程,负责从缓冲区取请求放到合适的楼座(层)(实际上就是选择调用谁的调度方法),而具体分配到哪部电梯通过调用楼座(层)类中的调度方法进行分配。

BUG分析

第五次作业我犯了很多人犯的错误,忘了对输出方法进行线程安全的封装,导致互测被hack;

第六次作业没有发现bug;

第七次作业发现了一个性能上的bug(其实是五六次作业沿用过来的),导致电梯不能在空乘后快速接取下一个乘客,于是强测有一个点些微超时。

总的来说,本单元没有出现什么大的逻辑错误,我自己还是比较满意的。

心得体会:

本单元我接触到了java的多线程编程,这种编程的方式对我来说完全是一种崭新的视角。虽然一开始有点难理解(更难调试),但是随着理解的深入,越发感受到多线程编程技巧的一些巧妙之处:无论是生产者消费者模式、流水线模式等设计模式,还是SOLID设计思想,都引发了我的不少思考。当然最令人高兴的还是自己的代码能够依照自己的想法正确运行,bug逐渐减少的过程。

Link to comment
Share on other sites