• 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

单元2总结了同步块的设置和锁的选择。调度器设计架构模式程序的bug,发现别人bug的策略经验。

unit 2 总结

OO第二单元的主要任务是模拟一个多线程电梯运行的基本场景。基于“生产者-消费者模式”实现了满足不同电梯调度和运行策略的电梯,以满足用户上下楼和换乘的要求。

不得不说,对比之前的博客,可以看出今年的助教还是不干了。让我们在本单元的编程充实快乐但又不失必要的痛苦中体验多线程的独特魅力,对此我深表感谢(doge)。

由于本单元中的一些问题是常见的,主要集中在线程安全上,所以本次作业将不采用子作业分析的形式,而是使用按点总结

同步块的设置和锁的选择

在HW 5和HW 6中,我只采用了实验中给出的同步控制方式:

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

requests.add(请求);

notify all();

}

公共同步请求getOneRequest() {

if (requests.isEmpty()) {

尝试{

wait();

} catch (InterruptedException e) {

e . printstacktrace();

}

}

if (requests.isEmpty()) {

notify all();

返回null

}

/*=====balabala=====*/

notify all();

return/*=====balabala=====*/;

}

为了保证线程安全,synchronized修改了添加和取出请求的方法,使得同一时间只有一个线程可以访问共享队列(dispatcher到总请求队列/dispatcher到楼层或楼层的队列/电梯到楼层或楼层的队列)。

当elevwaitor或dispatcher请求时,如果队列为空,此时如果isEnd()为真,则直接终止线程,否则通过setEnd()方法通知后终止线程或者通过addRequest()方法通知后处理请求,这样电梯和dispatcher就可以在没有请求到来时一直等待,避免轮询。

在这个单元的作业中,作者把共享队列上的每一个操作都做成了独立的,方法上没有相互调用,因为怕写出来莫名其妙的死锁。后来,我发现java中线程获得对象的锁是以线程为单位的,同一个线程对同一个对象锁是可重入的,同一个线程可以获取同一把锁多次,也就是可以多次重入.有多好,它大大减少了我们的死锁情况,或者说写一个死锁说明我们的逻辑太好了。

但是,同步修改方法限制了读写操作,这在一定程度上降低了程序的效率。这是我们不希望的,所以我在维护Dijkstra算法的图时使用了HW 7中ReentrantLock的读写锁机制:

public int[][] getSpath() {

int[][]updated path;

rlock . lock();

尝试{

updatedPath=spath

}最后{

rlock . unlock();

}

返回updatedPath

}

public void initial() {

wlock . lock();

尝试{

/*=====balabala=====*/

}最后{

wlock . unlock();

}

}

在作者的算法中,每一个请求都需要使用Dijkstra得到的最短路径数组来得到最短路径,而这个数组只需要在增加水平电梯的时候改变。使用同步装饰会明显互相阻碍,所以采用读写锁机制进行控制。不能边看边写,不能边写边看,平时可以同时看,提高效率。

调度器设计

HW 5

g>:
  • 由于HW 5的每个楼座只有一部电梯,实际上并没有涉及到调度策略,调度器仅仅是识别请求并分发,性能分主要取决于电梯本身的运行策略。笔者开了一个Schedule线类用于从总请求队列识别相应的请求并将其添加到到对应楼座的等待队列中。

HW 6

  • HW 6中,由于同一楼层和楼座之间可能有多部电梯,涉及到多部电梯会共享一个楼座队列的情况。这里我采用了线程安全的平均分配策略。笔者建立了两层级的调度器结构,首先第一层总调度器Schedule从总的请求队列中识别请求的归属楼座,将该请求分配到第二层级调度器楼座的队列中,再由楼座的队列根据均分算法分配到每个电梯的waitQueue中,这样每部电梯事先就在调度层面被安排好了要接取的乘客,不会出现多部电梯争抢的情况,胜在线程安全。
  • 但是由于是事先安排,电梯是“懒汉式”的,即有需求才会动,与共享队列中争抢的“饿汉式”相比,平均分配更多的等待意味着更少的概率在中途捎带上乘客,意味着电梯的性能效率偏低,因此笔者在HW 7中采取了共享队列的写法。
class Building extends Thread {
    private ArrayList<Elevator> elevators;
	/*=====利用count计数实现均分=====*/
    if (request instanceof PersonRequest) {
        elevators.get(count).addOutRequest((PersonRequest) request);
		count = (count + 1) % num;
    }
}

HW 7:

  • 笔者在HW 7中改用了共享队列的调度策略将HW 6中的两层调度器改为一层,所有的请求由Schedule类统一分发到对应的楼座 / 楼层,同时将Schedule类设计为饿汉式的单例模式供其他类通过getInstance()方法调用向内增加等待分发的请求,如:输入类InputThread和电梯类Elevator完成一个阶段的请求后。
  • 在调度器类Schedule接到请求后,通过识别第一阶段的任务确定其应被投喂的楼层 / 楼座,并将请求加入到对应楼座的等待队列中,电梯线程在识别到有能搭载的乘客时就会前往迎接。又由于采用synchronized对拿取请求的过程约束,保证了电梯按序拿取,避免竞争。
public class Schedule extends Thread {
    private static final Schedule SCHEDULE = new Schedule();
    
    public static Schedule getInstance() {
        return SCHEDULE;
    }
    
    public void initial() {
        /*=====对调度器各项数据进行初始化=====*/
    }
    
    public synchronized void addRequest(RequestTable requestTable) {
        this.waitQueue.addRequest(requestTable);
        notifyAll();
    }
}

架构模式

HW 5

  • 仅有输入线程、电梯线程以及一个总的调度器
  • 请求传递:
    • 调度器负责从总的等待队列拿取请求,并将其分发给每个电梯的等待队列,采用生产者-消费者模式。
  • 信息交互:
    • 调度器接受InputThread的结束信号并通过setEnd方法结束电梯线程。

pctpa3z2xzr3599.png

HW 6

  • 迭代:
    • 实现了要求的增加电梯请求与横向电梯,与HW 5相比增加了一层调度器用于实现“平均分配”的策略。
  • 请求传递:
    • Schedule调度器在从总等待队列拿取请求后分派给对应楼座的调度器,楼座调度器根据当前计数值count决定均分给哪一部电梯。
  • 信息交互:
    • 由InputThread线程结束开始,逐级对调度器调用setEnd方法,逐级关停线程。

adjl1jtalwk3600.png

HW 7

  • 迭代(大改):
    • 新建一个类Graph用于维护电梯和能到达的地点组成的50 * 50的图,利用迪杰斯特拉(dijkstra)算法计算点与点之间的最短路径用于请求分解
    • 新建了一个RequestTable类用于对Request进行一层封装,利用迪杰斯特拉求得的最短路径将当前请求拆分为单楼座/单楼层的独立请求,并对请求计数。
    • 新建了一个RequestCounter类用于计数请求数与已完成的请求数,用于输入结束后结束电梯线程。
    • 将二级调度器改回一级调度器,采用共享队列的调度算法。
  • 信息交互:
    • 当输入线程结束后,启动RequestCounter线程,该线程重复循环直到统计到已完成请求数与总请求数相等时调用电梯的setEnd方法以结束电梯线程。

qp1o0hq2jhc3601.png

UML协作图:

gebzb2otnud3602.png

程序的bug

HW 5:

  • 在本次作业的本地测试、系统强测未发现bug。但是在互测中被hack了一刀RTLE,程序没有正常结束,本地尝试复现未果,应该是测评机线程调度的问题,笔者推测在线程安全上没有维护好。

HW 6:

  • 本次作业笔者采用了平均分配的调度策略,以牺牲了部分性能分为代价保证了线程的安全,再加上电梯的运行逻辑并无差错,最终本地测试并没有发现bug,强测、互测都没有被hack到,平安度过。

HW 7:

  • 本次作业因为受好友蛊惑为了拉满性能分,笔者改用了电梯自由竞争的策略。但是由于是多部电梯竞争抢乘客搭载,会涉及到对于楼座的等待队列的线程安全维护的问题。
  • 在一开始完成HW 7的时候,笔者在请求队列内isEnd()isEmpty()方法中均像实验一写了notifyAll,导致了同一楼座的多部电梯在没有请求到来时本来应该等待,却又因为其他的电梯在调用队列的isEndisEmpty方法判断线程是否结束时而被唤醒,如此相互唤醒导致轮询。并且这一轮询bug并不会影响实际的运行时间,导致笔者在用HW 6的强测点测试的时候才发现。笔者在思索后发现,过多的notifyAll反而是画蛇添足。其实当目前的操作并没有改变队列成员状态的时候我们没必要通知其他的等待线程,因此笔者将返回值为null和isEnd()isEmpty()两个方法内的notifyAll语句删除,得以通过HW 6的强测,解决了该bug。
  • 但是非常遗憾,共享队列还是有bug……由于横向电梯具有可达性的特点,笔者在写横向电梯拿取乘客时传入了switchInfo参数,会导致电梯由于可达性返回为null而啥事不干直接进入下一层循环,导致轮询。目前的解决办法笔者想到了两种:
    • 摆烂策略:让电梯“没事走两步”,使横向电梯向一个方向保持运动,能接客就接。虽然电梯一直在运行,但是其实是经历一次循环后进入了move的状态睡了speed * 1000,相当于在这段时间内只进行了一次循环,避免了轮询。而且“没事走两步”有其效率的合理性——投喂的请求在哪一楼座是概率均等的,让电梯保持运动的状态有概率在乘客请求到来时出现在距离更近的地方。因此在bug修复时笔者发现“没事走两步”的代码与之前性能上不相上下,在部分点上甚至远优于前一版。
    • 正经策略:在setMoveType()(设定电梯下一步行动状态的方法)中加入如下判定:当电梯内没有乘客时遍历等待队列,如果没有可供搭载的乘客即wait,如此避免轮询。
/*===============横向电梯轮询bug时拿取请求的逻辑==================*/
public synchronized RequestTable getRowElevatorRequest(ArrayList<RequestTable> 		inElevator,char curBuilding, int capacity,char floorDes, int switchInfo) {
    if (requests.isEmpty()) {
        return null;
    }
    Iterator<RequestTable> iterator = requests.iterator();
    while (iterator.hasNext()) {
   		RequestTable request = iterator.next();  
        RequestTable tmp = request.readFirst();
        int check = (1 << (tmp.getFromBuilding() - 'A')) | (1 << (tmp.getToBuilding() - 'A'));
        /*=====判断条件:可达 + 楼座符合 + 容量没超=====*/
        if (tmp.getFromBuilding() == curBuilding && inElevator.size() < capacity &&
            ((check & switchInfo) == check)) {
                iterator.remove();
                notifyAll();
                return request;
            }
        }
        return null;
    }

发现他人bug的策略

与第一单元表达式作业相比不同的是,第二单元的电梯作业为对简单场景的模拟,侧重点在多线程的安全问题,电梯的运行逻辑非常简单,以至于基本不会出现运行逻辑正确性的问题。本单元的测试应当着重于有关线程安全的调度策略,即重点构造数据针对可能出现的死锁轮询进行测试。

测试策略以手搓构造数据为主、自动化测评为辅。笔者在这一单元第一次尝试写测评机,由于对Python代码十分不熟悉,因此写得磕磕绊绊。利用自动化测评,成功找到了同组一个数组越界的bug,推测是在增加电梯时对内部队列的初始化问题。

测评机逻辑

  • 数据生成器:
    • 按照给定要求生成请求即可,常量池非常简单,只涉及五个楼座和10层,利用rand函数随机选取即可。
  • 正确性检查
    • 逻辑判定:
      • 利用有限状态机判定Arrived, Open, Close, In, Out几种语句的输出顺序;
      • 判断乘客是否准确到达了目的地;
      • 判断电梯线程结束了是否还有乘客的请求没有完成;
      • 判断是否有人没有进电梯但是出去了……(其他电梯惊魂灵异事件);
    • 时间判定:
      • 利用Python的time函数获取程序的运行时间,再利用管道PIPE结合课程组提供的官方包进行标程运行时间获取,利用给定的时间最大时间判定公式判断是否RTLE。
      • 不足的是不会查询CPU的时间,部分轮询的状态无法检测到。

心得体会

OO真是太好玩辣!

实验的代码太香辣!

  • 线程安全角度:
    • 死锁的bug特别好找。
    • 轮询的bug非常难解决,需要对线程间相互协作的关系了解地非常彻底,慢慢跟着流程走一遍才好找bug。后来发现可以利用中间过程加信号量输出的办法,在所有的while(true)循环后面加上一句输出,亲测非常好找到对应的bug。
    • notifyAll没必要加太多,对于现状没有改变的过程没有必要,甚至是不应该使用notifyAll来唤醒其他的线程,以免出现轮询的现象。
  • 迭代的角度:
    • 每一次的作业都不能偷工减料,否则要么面临强测和互测被hack,要么因为架构问题在下一次的作业中要加倍补偿回来。
    • 均分策略与共享队列各有千秋,实际上没必要为了一点性能分迭代去追求共享队列,最后强测和互测被hack反而得不偿失。

“故天将降大任于是人也,必先苦其心志,劳其筋骨,饿其体肤,空乏其身,行拂乱其所为,所以动心忍性,曾益其所不能。” ——《孟子》

艰辛的第二单元多线程编程已经过去,不应该停滞不前,向前看吧,努力认真完成后面的作业,以这句话与诸君共勉。

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