• 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

同步块的设置

该单元的基本结构由以下三个主要部分组成:

Inputhander:用于接收和排序输入,是一个线程。

控制器:用于处理输入,完成处理,是一个共享对象。

电梯,输送机:电梯本身,用来接乘客的,就是线。

为了输出线程的安全,增加了一个Outputer的singleton对象来处理所有的输出。

因此,可以通过在共享对象(即控制器和输出器)的数据读写方法中加入同步修改来实现线程安全。

调度器设计

look算法

使用look算法。基本逻辑如下:

检查门是否需要打开。如有必要,开门接送客人。

检查电梯上的所有人和电梯所在的候梯队列中的所有乘客,看是否有电梯运行方向前方的乘客要求上/下车。如果是,保持原来的方向。如果没有,转过身去。

在第二步之后的方向上前进一级,并返回到第一步。

look算法的小bug

但在第二次作业中,引入自由竞争后,会出现bug,比如:

1号电梯和2号电梯在A座一层,此时有一名乘客进入A座1层,1号电梯和2号电梯都随机开门抢班。让我们设定1号电梯去抓乘客。此时,对于电梯2,在look算法的第二步中,如果发现没有来自上面的请求,电梯将改变方向向下。于是第三步,我们进入了0层。

解决方法是对“底层下行”和“顶层上行”进行特殊判断,防止电梯上10层和11层。

架构模式

采用的基本结构可以称为生产者-消费者模型。

第一次作业

类图如下:

sh5bgfdeeb23174.jpg

大意是:把PersonRequest类当做乘客本身。当输入PersonRequest时,InputHandler将访问hashmap字符,控制器的ArrayList PersonRequest映射,并将PersonRequest放入相应建筑的ArrayList中。而电梯则定时去找控制器,寻找其对应楼层的数组列表来判断是否开门载客,是否调头。当电梯需要搭载乘客时,从控制器的数组列表中删除PersonRequest,并将其添加到电梯中的数组列表Person Request乘客中。当你需要开门让客人下车时,遍历你的ArrayListPerson请求乘客,删除请求的目的楼层与当前楼层相同的请求,并相应输出。

此时,考虑到将来会增加电梯,将等待的乘客放在共享对象控制器中而不是电梯中,将电梯内的乘客放在电梯类中,这是为自由竞争机制做的准备。

第二次作业

对于垂直电梯,采取自由竞争的策略。

类图如下:

kzwrw31laxh3175.jpg

为了充分利用前面的代码,将水平电梯设置为一个新的传送机类,重用了hashmap字符、ArrayListPerson请求映射,并将水平电梯的键设置为其所在楼层对应的字符。原理差不多。

优化

作者尝试在水平电梯中使用look算法,设置机制如下:

检查门是否需要打开。如有必要,开门接送客人。

检查电梯里所有的人

电梯所在的等待队列中的所有乘客,看电梯运行方向的 前方的两个座是否有接/放客的请求。若有,则保持原方向。若无,则调转方向。 沿着第二步处理过后的方向,前进一层,并回到第一步。

由此实现了横向电梯的伪look算法。

第三次作业

受到第四次课上实验_第二部分的启示,采用了流水线模式。

对于需要处理成多段请求的人,设计为了一个Person类,然后对Person进行删除请求、获取请求的操作。

类图如下:

q5sc2inkwpg3176.jpg

优化

设想一种情况:有一位需要多次换乘的乘客,若他第一程下电梯后,下一程的电梯能提前来接他,那耗时一定能压缩到最小。

基于这一想法,考虑实现让电梯提前来接乘客,方法就是:每输入一个乘客,就在需要换乘的上电梯处放置一个0号虚空请求(根据题设,乘客id必须>0,所以id==0的请求视为虚空请求就再合适不过了),让电梯前往换乘点。

            PersonRequest p2 = new PersonRequest(floor, floor, 
                request.getFromBuilding(), request.getToBuilding(),
                    request.getPersonId());
            PersonRequest p02 = new PersonRequest(floor, floor,
                request.getFromBuilding(), request.getToBuilding(),
                    0);
            map.get((char) (floor + '0')).add(p02);
            person.addRequest(p2);
            if (request.getToFloor() != floor) {
                PersonRequest p3 = new PersonRequest(floor,
                    request.getToFloor(), request.getToBuilding(),
                        request.getToBuilding(), request.getPersonId());
                PersonRequest p03 = new PersonRequest(floor, 
                    request.getToFloor(), request.getToBuilding(),
                        request.getToBuilding(), 0);
                person.addRequest(p3);
                map.get(request.getToBuilding()).add(p03);
            }

由于0号请求的存在,电梯会将其当成一般的请求处理,在一定情况下,会提前抵达0号请求所在的楼层/楼座。只需要在原先的getRequest电梯/传送带检查正在等待的PersonRequestArrayList中,加入如下代码:

            if (map.get(name).get(i).getPersonId() == 0 
                && floor == map.get(name).get(i).getFromFloor()) {
                map.get(name).remove(i);
                i--;
            }

即可防止0号乘客虚空上电梯,并悄悄地让电梯提前到了中转的楼层/楼座等待需要换乘的乘客。

但是,如果电梯正在运行当中,加入中转的0号请求,可能会导致电梯跑老了大老远结果是虚空接客,让这一优化成为负优化。于是,在乘客进入电梯的方法中,加入以下代码:

            if (p.getPersonId() == 0) {
                waitQueue.remove(i);
                i--;
                continue;
            }

这样写还有一个好处,就是可以防止:如果0号请求是在电梯getRequest之后、正式上客之前加入的,就有可能0号请求进入电梯的bug。

协作图

考虑到第三次作业完全覆盖了前两次作业的功能,不妨直接使用第三次作业的协作图表示该单元的总体的线程之间的协作关系。

协作图如下:

1qnsdgin1cy3177.jpg

结束机制

在第一、二次作业当中,电梯结束的方法为:如果电梯在访问自己的等待乘客列表时,发现输入结束、电梯为空且等待列表也为空,则结束电梯进程。

但是这一判断方式在第三次作业中会出问题,因为乘客请求在到达换乘的下一站之前,并不会及时出现在旅程中段电梯的等待列表中,电梯一旦空了,就会误以为自己以后已经没有任务而结束(事实上还有一个乘客在换乘中,在来搭电梯的路上)。于是线程结束的机制,索性改成:所有的Person都已完成即可。

程序bug

该单元的bug比之前要多了,由于整个电梯的框架还是很清晰的,所以哪里出问题了一看报错就能发现,很多都是一目了然的小问题。但bug的出现还是远多于与其,主要原因还是因为自己没有写评测机,对自己的电梯也只做了逻辑运行正确性上的测试,而没有在复杂的运行状态下做充分的测试造成的。

以下将对每次作业出的bug进行分析。

第一次作业

忘记在满员的情况下,电梯根本没必要再检查是否需要开门接客。例如电梯载满乘客从5楼走到1楼,期间每一层都有人在外面等电梯。我的电梯就会在到达的每一层都发现需要开门接客,于是就白白开门关门,徒增运行时间导致TLE。

修改也很简单,在开门前加一层判断,如果没有人要下电梯,且电梯满员,则不开门即可。

第二次作业

在调度器设计那一栏提到了第二次作业,对自由竞争导致的“在最底层向下走”和“最高层向上走”进行了特判,但是忘记把打印“ARRIVE”也加入特判当中了,导致出现了从1层arrive到1层的情况。这一点肉眼没法发现,评测机却会抓出来……

修改也很简单,如果发生了特判的情况,则不打印即可。

第三次作业

在共享对象controller里面放一个map,key为楼层,value为第二层map。

private HashMap<Integer, HashMap<Character, Boolean>> permits;

第二层map,key为楼座,value为记录这层的电梯可否在此座开门的boolean值。

每加入一个电梯,就获取它所在楼层的map,如果这个电梯能在楼座X开门,则将map中key为X的值置true。

乘客寻找需要在哪层换乘时,只需要看controller中每一层的map,看看目标楼座和出发楼座的value是否为true,若是,则该乘客在此层换乘。

问题

如果在同一层,出现两个横向电梯,分别允许在:

A B

A C

开门,则A/B/C的value会被置true,需要从B到C的乘客就会在这一层换乘,然而没有电梯能够从B走到C,于是没有电梯接收这一乘客。

修改方式

在共享对象controller里面的map,key仍为楼层,value为第二层map构成的ArrayList。

private HashMap<Integer, ArrayList<HashMap<Character, Boolean>>> permits;

而第二层map的含义,则变为key为楼座,value 为该电梯可在此楼座开门的标志boolean。

乘客寻找需要在哪层换乘时,改为看controller中每个楼层的ArrayList的每个map,在map当中同时满足目标楼座和出发楼座的value均为true,才选择在此座换乘。

心得体会

线程安全

电梯设计最大的收获大概就是第一次接触线程安全问题吧。不得不说直接使用synchronized是个很偷懒的方法,直接在两个线程的共享对象中,将所有方法用synchronized上锁,就能够保证每次只有一个线程在访问这一共享对象。

由于线程安全问题涉及到多个线程访问某一对象的先后问题,故架构设置得越简单,越有利于捋清线程安全的思路。

层次化设计

SRP: 类的职责应当单一。

OCP:尽量少地修改已有的实现,并通过增加方法、增加特判来实现新功能。

其他

还有一个最大的感受就是,要相信计算机的性能,具体体现在:该for循环就for循环,该遍历就遍历,哪怕经常要遍历ArrayList想着挺别扭。一开始的时候,总想着用HashMap做到O(1)的搜索,但是一顿尝试之后,发觉现代计算机的算力真的很强,遍历ArrayList慢不到哪去。哪怕有一堆线程在等某一线程对着共享对象一通遍历,但这也用不了多久,放心交给电脑,它算的很快。

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