• 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类图和顺序图如下:

vzapfddbabc3302.png

k3ditol50qi3303.png

因为第五个作业比较简单,所以这个作业没有太多迭代的考虑,采用的是标准的生产者-消费者模式。输入线程不断读入新数据并发送给调度器,调度器将满足相应楼层座位的请求发送给相应的电梯,剩下的交给电梯继续处理。

同步性控制:的第五个作业共享的数据较少,因此采用线程安全类进行同步控制。当两个线程传递请求时,它们都传递一类队列。发送方调用add函数发送信息,它将唤醒可能正在等待的接收方线程。接收方线程只能通过队列提供的get函数获取信息。如果没有信息,它将进入等待状态以避免轮询并释放锁。采用的锁是这个队列对象。

调度器策略:是一个非常简单的楼层调度。

电梯策略:'s经典LOOK算法,相信其他人的博客已经描述过了,就不再赘述了。

迭代性考虑:尚未被考虑。

BUG:电梯客满后,如果楼层有人还想上楼,电梯会不换人就开关门,导致性能变慢,被卡超时。后续实验中会修复。

 数据生成策略:数据生成程序是在第一次作业后制定的,不同的电梯策略之间存在明显的时间差,没有检查正确性。第一个老师做了一个A1-A10的基本请求,然后依次尝试生成三种类型的请求33601捎带请求。请求会在基本请求的电梯可能到达自身的时间段内的随机时间点发送捎带请求(因为上一层可能延迟400开闭门,所以时间范围是一个时间段),请求会随机发送几次。2.卡填充请求3360。该请求将在基本请求的同时被填充来自不同始发地的具有不同目的地的请求,以试图占据电梯群体。3.反向请求,在基本请求的目的地附近生成与基本请求相反方向的请求,以增加相反方向的请求。这些请求中的每一个都会像基本请求一样继续迭代几次,每一类的同类迭代次数会大大减少,迭代3-4次。当我用自己的LOOK算法对比以上数据和官方的时间包时,时间差最多能达到14%(标准流程的运行时间基本超过50s)。

由于本人第二次作业完全为了第三次作业考虑而 特地重构的架构,所以第二次第三次作业电梯的架构和线程交互模式完全一样,(也就是第二次作业已经可以支持换乘了,第三次仅仅是略微增加可定制),所以在此一并展示.

yo2i4lmyusy3304.png

qngtcrvxjms3305.png

整体的工作流程:

输入线程把得到的数据给中央控制器,那里的控制器有LIFT的自更新数据(也就是每次LIFT移动都会上报这部分来控制)。然后,控制器按照一定的算法将现有电梯的运行转化为一个50个节点的无向图。每个人都把这个图保存在自己身上,然后根据这个图算出自己下一步该往哪里走。控制器将根据这个人下一步要去的地方把它交给适当的电梯。电梯到达后,将被运送人的当前位置还原为目的地,然后返回给控制器。如果被管制员带走的人的起点等于最终目的地,说明人已经到了,这个人会被直接删除。新增一部电梯时,已经分配的人不会选择这部电梯,采取的方法是再次把所有人拿出来,重新抽签,重新分配。

同步控制:

这里的共享数据,只不过发送方在不同的线程中仍然采用线程安全类Queu。电梯自更新和所有新增加的电梯的重新分配将导致控制器中的消息和电梯内部的处理队列的共享。解决方法是使用高效的线程安全容器,也就是说,不锁很多会导致运行缓慢,不会导致不安全的线程。

调度器算法:

首先,如果有学弟偶然看到这篇文章,请不要轻易尝试使用这个算法。不仅容易出bug,性能也很神秘。建议另找自由竞赛架构学习!

算法

采用的是flyod全源最短路算法,复杂度n^3,由于这里n很小只有50,时间还可以接受,但是楼层更高的时候可能会很影响时间..首先建立一张完全不连通的图,然后去遍历所有电梯,给对应电梯能联通的节点的边赋值权重,大小通过电梯的信息用价值评估函数评估出来,这样全部电梯加入之后得到一个无向图,然后调用算法找到一条最短路,作为该乘客的换乘路线,这样也顺手解决了第三次作业横向电梯部分不可达的问题,不可达就不会建立边,最短路径当然不会那么走.

  算法好处就是,基于算法的乘客可以采取很多超出你想象力的策略移动,一些对于其他架构很难写的策略这个算法自然就做到了,比如连续多次换乘: 乘客1A-10到C-8 新增两台电梯 分别是10层AB电梯和9层BC电梯,乍一看的最优策略就是A10->B10->B9->C9->C8,实际运行出来乘客也是如此移动的.

  上述优点看起来很美好,但是存在很大的问题,没有考虑电梯所在的楼层,上述算法虽然做到了乘客占据电梯时间最短,乘客最快到达,却没有考虑电梯到达乘客需求的时间,实际我的程序跑上面的代码在ABC发送请求电梯都是从A1B1C1开始移动的,实际上非常非常慢,甚至远不如在1楼换乘.

  我们将数据分为两段,前端的大量数据和末端的一些数据,在处理前端大量数据时因为每个乘客占用电梯时间都是尽可能少,性能还是可以,但在处理最后的末端数据就可能使得缺点暴露的很明显.我的没有实现的想法是能否分段处理数据,最后一部分数据换一种算法让他们采取的策略是让电梯运行时间最短而不是自己路径最短,

  上述算法性能表现大概是92分,很多数据点要不然就是9899要不然就是85,我也在课下跟一位最终得分99.8的采取自由竞争的大佬对拍一下运行时间,比对中发现另一个问题:价值评估函数完全是凭自己连蒙带猜写出来的,不同参数有很大影响(参数可能过拟合),在一些数据点我更改参数之后性能比得分99.8的程序还要快出20%,但是另一些数据点这组参数表现就很差,会慢出15%左右,总而言之调参调的很玄学.

  最后如果有大佬采用的类似的算法并且最终性能表现得还不错还望不吝赐教

BUG:

  第二次作业并无bug,第三次作业由于打字错误 把fina打成from(都是f打头,自动补全的锅),导致一个隐蔽的bug没有被我测出来,交上去的时候挂了三个点被hack4次.我的电梯运行时不检查能否开关门,因为相信算法算出来的一定是符合可达性的要求(事实确实如此),但是由于打错变量导致一些不可达的请求错误的给了某个楼层从而导致横向电梯错误的开关门.把名字改回来就全部修复了.

  第二三次的数据生成器仅仅是增强了第一次的数据生成器的范围,并无做过多改进

 

心得体会

  这是第二次因为打字错误而不是程序内部或者线程安全导致的bug了啊啊啊,上一次是第三次作业,丢了这些分非常痛心,这告诉我数据生成一定要尽可能全面覆盖.本单元的多线程的实践也让算是让我对多线程有初步了解了,本单元没出现过因为线程安全而导致的bug.一些共享数据推荐封装入线程安全类中,这样能大大减少出问题概率.在处理轮询问题时,我并没有思考在那里去加wait,而是让这个线程去有意调用空的共享对象(不空他也不会wait)的get函数自然的陷入wait,并在之后的设计中再也没出现过轮询的问题.

 

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