• 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

第一次作业

设计思路

基本结构是生产消费者模型,有输入线程生产请求和电梯消费请求。我在第一次作业中遇到了两个困难。一个是调度策略,另一个是如何得到对电梯的请求的设计。

在调度策略上,一开始看了look但没有完全理解,导致写作过程困难,最后写出来也不对。按照我的写法,电梯在某一层(电梯是空的)放下所有乘客后,会选择上方或下方最近的请求作为目标,但真正的样子应该是判断原方向是否有请求,如果有,就继续原方向。这个问题在第一次作业中没有体现出来(强测成绩不错),却导致了第二次作业的成绩很差。

由于我在第一次任务中对多线程的了解有限,这让我困惑了很长时间,当时如何获得电梯的请求。我的困惑在于:电梯需要得到每层楼的请求,但如果等待队列(盘)是空的,就需要等待,但如果电梯里有人,就不需要等待。这个问题现在看来确实有点傻,只需要多加一个判断条件就可以解决,但当时还是很混乱的。这时候又出现了一个困惑:在获取请求的时候,是应该把电梯的信息传递给等待队列所在的班(盘)呢,还是应该把等待队列里的请求都拿出来,选择合适的请求,再写回等待队列。最后我选择了后者。为了防止不同的电梯因为需要访问同一个等待队列而相互影响,我为每一部电梯都设置了一个等待队列。

最终的设计思路如下:

MainClass:构造五个等待队列,启动五个电梯,启动输入线程。

InputThread:获取输入,并根据楼层将其分配给不同的等待队列。

电梯:从对应的等待队列中获取所有请求,处理可以处理的请求,将剩余的请求写回等待队列。使用类似于look的调度算法。

Request:表示请求,包括:id、方向等信息。

SecureTimableOutput:安全输出线程类。

UML类图

b23u1rzln4y5277.png

同步块的设计

在这个作业中,共享对象是requestQueue,所有对requestQueue资源的访问都需要被锁定。我使用synchronized来实现锁定机制。

首先,requestQueue类内部的所有方法都是锁定的,这确保了我们的类是线程安全的。

公共同步void addRequest(请求request) {

waitRequests.add(请求);

notify all();

}

public synchronized ArrayListRequest get requests(){

返回等待请求;

}

公共同步void set requests(ArrayListRequest请求){

this.waitRequests=requests

}

公共同步void setEnd(布尔isEnd) {

this.isEnd=isEnd

notify all();

}

公共同步布尔isEnd() {

返回isEnd

}

public synchronized boolean isEmpty(){

返回wait requests . isempty();

至于InputThread,需要将输入请求写入相应的等待队列,并在输入结束时设置等待队列的结束标志,所以我将两个操作作为一个整体进行锁定。

p>

在Elevator线程方面,在接人的时候需要先getRequests,再setRequests,因此需要对这两个操作整体上锁。电梯其他的查询等待队列信息(isEnd、isEmpty)的操作由于requestQueue内部已上锁则不需要再上锁。

调度器设计

在我的设计中并没有用到调度器,调度器的功能在elevator类的look()、inout()方法中已经实现。并且在接下来的每一次作业中都没有调度器的设计。

第二次作业

设计思路

第二次作业完全基于第一次作业进行增量开发。由于第二次作业中的请求只能是横向或竖向中的一种,因此需要改动的地方很少。

相较于第一次作业,主要的增加工作:增加了一种横向电梯(和竖向电梯整体框架完全一致,改变了调度算法移动方式),增加了10个等待队列,分别属于每一层。

由于有两种电梯,因此我定义了一个父类Elevator和两个子类VerticalElevator和TransverseElevator。由于本次作业可以通过指令增加电梯,因此我设计了一个单例模式的Factory类来实现工厂模式,增加了代码的可扩展性。

对于电梯之间的竞争问题,本次作业只涉及到横向与横向的竞争、纵向与纵向的竞争,而我采用的方法完全是自由竞争,即:每当请求来了所有电梯同时相应这个请求,至于最终哪个电梯能处理这个请求,完全交给CPU来决定。选择这个方法的主要原因是往届博客中表示这个方法跑出来的效果很好,并且这个方法实现极其简单——什么也不做。

UML类图

24ibtbuzi0b5278.png

 

 

同步块的设计

与第一次作业完全一样。

第三次作业

设计思路

第三次作业仍旧是在前两次作业的基础上,增加了一小部分功能而实现的。

第三次作业中增加了斜向的请求,我采用了一种静态分解的处理方法,即对于一个斜向的请求,获取它的时候就把它分解至多三个部分(只允许一次横向移动)。

一个请求可能被分为多个部分,并且需要多次处理,这一问题完全可以用流水线模式来处理,因此我的代码更改主要依赖于上机中的代码。流水线模式的使用引出了三个问题:

  • 原来的Request类已经不能完全表示一个请求了,对此我构造了一个Person类和一个MyRequest类,Person类记录了一个请求的原始信息并且管理了一个ArrayList<MyRequest>,MyRequest类与之前的Request类的功能一致,并且把原来的RequestQueue改为PeopleQueue。我把每一个原始的请求(InputThread读入的请求)当作一个人,一个人可以拥有多个横向或纵向的电梯能单次处理的请求。

  • 对于一个包含多个请求的person,当处理完某一个请求之后需要判断ArrayList<MyRequest>是否为空,若为空则表示到达,若不为空则需要处理下一个MyRequest,对此我的解决办法是创建一个单例模式的Controller类,InputThread读入的Request和未处理完的Person统统写入Controller,由Controller统一分配到各各PeopleQueue中。

  • 如何判断电梯线程何时结束?构造一个单例模式的RequestCounter类,类里面维护一个counter变量用来记录未处理完的请求,InputThread每读入一个请求counter++,每当有一个Person的ArrayList<MyRequest>为空,counter--,当counter为0且InputThread线程结束时为Controller设置end标志,最终电梯的结束条件为getWaitQueue().isEmpty() && getPas().isEmpty() && Controller.getInstance().getEndTag()

由于第二次作业的强测发现自己的调度算法有问题,在第三次作业中重写了竖向电梯的调度算法,改为真正的look算法。

UML类图

qgwbmlcpgjn5279.png

 

 

同步块的设计

由于新增加的Controller类中的end属性和RequestCounter类中的counter属性是共享资源,因此对这两个资源的访问操作都需要上锁。其它部分与第二次作业一致。

UML协作图

qoh4c4gdmop5280.png

 

 

BUG分析

个人BUG分析

前两次作业强测和互测中均未发现BUG,第三次作业中出现了CTLE和RTLE的bug,CTLE出现的原因是横向电梯wait的条件判断未考虑到是否可达的问题,而我的代码仅仅考虑了等待队列是否为空的情况,因此出现了轮询。RTLE的原因是在main函数中我先启动了InputThread再初始化了Controller,应该先初始化Controller,后启动输入线程,因为输入线程需要访问Controller。

HACK

本次我自己尝试写了一个简陋的数据生成器,因为第一单元的hack实在没有什么体验感(不想看代码又懒得手造数据)。hack的策略为黑盒测试。

第一次hack找到了一位同学的输出线程不安全的问题。第二次hack成功了一位同学RTLE。第三次hack到了两位跟我有一样问题的同学,都是横线电梯wait判断出现问题。

心得体会

这一单元给我的感受跟我之前所听到的“电梯月”完全不一样,我甚至觉得第一单元比第二单元还难,实际上第一单元所花费的时间确实比第二单元多(或许是我第二单元比别人少做了一部分什么吧)。

这一单元从逻辑角度来说没什么难度,主要是学习和使用多线程知识并且套用几个经典的设计模式(生产消费者模模式、工厂模式、流水线模式等)。作业重点在于如何处理线程之间的协作关系,而这个问题的根源就是共享对象,因此只需要重点考虑共享对象即可,在我们的作业中共享对象就是request,需要仔细检查与request有关的操作是否是线程安全的、访问request资源是否使用轮询、线程之间是否会发生死锁(我的设计中都是单层的synchronized块,因此好像不会出现这个问题)。

这一单元测试中的表现一般,第二次作业调度算法有问题,第三次作业出现wait判断的的bug,确实是自己的测试做的不够充分,希望在下一个单元能做好测试,好好表现。

Link to comment
Share on other sites