• 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

第二单元博客

目录

I .同步块和锁

1.1同步读/写

1.2输出

1.3管道架构模式

第二,调度程序设计

2.1第五次作业

2.2第六次操作

2.3第七次作业

第三,架构模型

3.1设计模式

3.1.1生产者-消费者模式

主从模式

管道模式

单例模式

3.2三个业务架构设计的渐变

第五项任务

第六次任务

第七项任务

3.3线程之间的协作

第五项任务

第六次任务

第七项任务

第四,bug分析

4.1第五项任务

4.2第六次任务

4.3第七项任务

动词(verb的缩写)经验和体会

I .同步块和锁

在本单元的作业中,有三个地方需要上锁。

1.1同步读/写

我选择将请求分配给电梯,然后电梯将处理请求。因此,对于每一部电梯来说,其等待队列processingQueue都面临着同时读写的可能。因此,所有涉及请求队列的处理,无论是读还是写,都必须使用synchronized关键字来锁定该方法。因此,在这三个操作中,对于电梯类,所有与processingQueue修改相关的方法都需要用synchronized关键字修饰。对于请求队列的RequestQueue类,修改中涉及的所有方法都需要用synchronized关键字修饰。

1.2输出

这个unit官方包提供的TimableOutput.println()方法是线程不安全的,所以需要用类包装,用synchronized关键字修饰。

1.3管道架构模式

在流水线架构模式下,结束的判断不能只通过读取InputThread中的一个null请求来判断,而是要在输入完成的同时完成所有的请求。因此,在输入结束时,需要唤醒所有等待的电梯,并通知它们该结束了。在唤醒过程中,需要锁定每个电梯的队列。

第二,调度程序设计

2.1第五次作业

在第五次运行中,因为没有换乘,没有水平电梯,每个座位只有一部电梯,所以调度器的设计极其简单,只需要把每层楼的请求分配给每层楼对应的电梯。

2.2第六次操作

第六个操作比第五个操作多了两点:水平电梯多,每层电梯多。我没有让电梯自由竞争,而是选择了主调度员来分配。具体的分配策略其实挺简单的:对于每个请求,考虑所有能把ta送到目的地的电梯,分配给哪个人少的电梯。

2.3第七次作业

对于第七次作业,与第六次作业相比,需要考虑的主要问题是:水平电梯的停靠和换乘。对于水平电梯,分配时要考虑的条件不仅是楼层,还有水平电梯是否能停在待定水平请求的起点/终点。除此之外,只需要根据当前请求的方向选择电梯,分配方式与第六次相同:哪部电梯人少就分配到哪部电梯。对于转,我选择只考虑一次转,以简化条件。所以对于每一个请求,最多只能分三步完成:乘坐起点的垂直电梯到中转层,乘坐中转层的水平电梯到目标座位,在目标座位从中转层到目标楼层。对于目标楼层的确定,选择目标楼层的策略与官方公式相同:设请求为FROM-P-X-TO-Q-Y,M为水平电梯的停靠信息,M为水平电梯所在楼层,然后满足M((M(P-

A '))1 ' A '))1)==1((M(Q-' A ')1)==1 1)==1)以及使|X-m| |Y-m|最小的值。同时,目标楼层确定后,每个请求可以用三位数字(flag)表示,0/1表示是否需要这一步,例如100(只需要乘坐一次垂直电梯,如从-a-5到-A-8),010(只需要乘坐一次水平电梯,如从-A-5到-c-c)。例如从-A-5到-C-1,换乘楼层为1层)、011(先乘水平电梯,再乘垂直电梯,如从-A-1到-C-5,换乘楼层为1层)、111(先乘垂直电梯,再乘水平电梯,最后乘垂直电梯)这种表示方法可以通过最高位确定当前请求是视为垂直请求还是水平请求,调度器可以根据这些信息进行分配。

第三,架构模型

3.1 设计模式

在本单元的作业中,主要用到了三种模式:生产者-消费者模式,master-slave模式,流水线模式。

3.1.1 生产者-消费者模式

在调度器和其他线程通信都是采用生产者-消费者模型。输入线程-调度器的通信中,调度器是消费者;在调度器-单个电梯的通信中,调度器是生产者。

3.1.2 master-slave模式

由于调度器要同时管理多个电梯,所以调度器-多个电梯又是master-slave模型,调度器是master,可以“看到”所有slave并给它们分配乘客;多个电梯每个都是slave,它只能看到它的上级master、不能看到其他的slave,运行结束时向调度器汇报。

3.1.3 流水线模式

由于第三次作业中乘客需要换乘,当前下电梯的乘客可能并未到达目的地,还需放回,因此调度器-单个电梯又是流水线模式中的Controller-Worker,调度器是Controller,是流水线中的“传送带”,流水线上每个worker干完了一步就放回传送带,由它送往下一步;电梯是Worker,worker干完了它这一步(即运输完一个乘客的当前请求)后判断一下此乘客是否已经到达最终目的地(flag是否等于0),如果没有到达就再将它放回传送带上,即放回调度器的请求队列。

3.1.4 单例模式

确切的说,这个模式只是流水线模式中必须采用的模式——因为流水线的调度器(Controller)只有一个。

3.2 三次作业架构设计的逐步变化

3.2.1 第五次作业

o2rfh4f2o1r4311.png

 

MainClass: 主函数,new所有线程并让所有线程启动。

InputThread: 输入线程,将输入的请求丢给调度器。

Schedule: 调度器,把每个请求分配给每个电梯。

Elevator: 电梯类,负责处理每个请求。

Request: 请求类,负责描述每个请求并用get()方法得到其信息。

RequestQueue: 请求队列类,负责存储请求,在第五次作业中有两种用途:Schedule(调度器)的待分配队列waitQueue,每个电梯的待处理队列processingQueue,对于两种用途在RequestQueue类中都有方法来处理。

SafeOutput: 如前文中提到的,将TimableOutput.println()方法包装,使其线程安全。

3.2.2 第六次作业

 mflnmhth1a44312.png

 

第六次作业相较第五次作业,进行的处理只是将Elevator类分成了ElevatorBuliding类(纵向电梯)、ElevatorFloor类(横向电梯)。同时在InputThread类中增加了请求判断(判断是乘客请求还是添加电梯请求)、电梯增加(判断是添加电梯请求后直接在InputThread类处理,减轻Schedule类压力),在Schedule类按前面所述的分配策略进行了修改。顺便,由于官方包中用Request表示请求,所以对于乘客请求由Request更名为MyRequest。

3.2.3 第七次作业

 dlp2i5wbonz4313.png

 

第七次作业,由于需要更换成流水线模式,所以对于程序整体修改较大,但核心没有变化。

MainClass: 主函数,对于Schedule类进行初始化,功能修改为只启动InputThread线程。

InputThread: 如前文所讲,增加了判断所有请求结束后给Schedule状态设为结束(EndTag)。

MyRequest: 增加了一个属性tempFloor,表示该请求的中转楼层。

RequestCounter: 每个请求结束后给这个类一个信号,这个类负责判断所有请求的结束。所有请求结束后,这个类才会从等待状态中唤醒。

3.3 线程之间的协作关系

3.2.1 第五次作业

 clf3otqbq1t4314.jpg

 

3.2.2 第六次作业

 e2g1aes00hp4315.jpg

 

3.2.3 第七次作业

 5twfxppsgpg4316.jpg

 

四、bug分析

4.1 第五次作业

第五次作业我遇到的主要问题集中在三方面。

第一,一开始我选择在实验代码的基础上进行修改开发,但是对实验代码没能完全理解,因此结束条件设置错误,导致出现CTLE。

第二,我一开始选择的策略是相对简单粗暴的Scan算法,选择每次都跑到头在转头判断。这种策略虽然实现极其简单,但是时间性能相较Look算法(或ALS算法)差的还是比较多,最终在强测RTLE。所以在第五次作业的bug修复中,我将程序改为Look算法,最终性能算是过了强测。

第三,就是输出的安全性。在最初我没有选择将官方包的println()方法进行包装,导致输出时线程不安全。

4.2 第六次作业

第六次作业我的bug相对比较蠢。如上文所述,多部电梯的分配策略是哪部电梯人少就将乘客分配给某座电梯。我的bug出现在比较最小值时初始值设置过小导致出现问题。

4.3 第七次作业

第七次作业我的bug出现在横向电梯的停靠上。我只考虑了乘客能够在终点座下电梯,忘记考虑乘客能否在起点座上电梯。

五、心得体会

在完成第二单元的代码过程中,我体会到许多。

第一,调度策略与性能优化。在第五次作业中,我一开始选择简单粗暴地实现Scan策略,但是经过强测数据后发现选择这样的策略会导致电梯在部分时间无意义运行,从而导致时间超过数据的最大运行时间Tmax。在将Scan策略换成Look策略过后,可以明显地感觉到程序无意义运行时间减少,整体性能提升。

第二,线程安全。在多线程运行的过程中,很多时候会出现对于某个对象,一边有写入的需求,另一边有读取的需求。如果不加以上锁使其原子化,将会出现非常严重的后果。输出的时间戳非递增也是线程不安全的体现。

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