• 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

第五次作业

代码架构

image

我的代码设计了两种线程,电梯线程和InputThread。

每个电梯线程和输入线程之间有一个独立的共享对象RequestQueue,避免了两个线程直接交互带来的线程安全问题。

输入线程和等待队列之间采用观察者模式。输入线程是被观察者,等待队列是观察者。收到请求后,通知所有观察者获取请求。观察者根据自己的条件判断是否可以处理,然后得到可以处理的请求。

类图如下:

image

同步块的设置和锁的选择

这个作业的共享对象只有RequestQueue,所以对等待队列的访问是同步的。

在这个赋值中,电梯和LookStrategy都需要访问共享对象请求,其中LookStrategy需要获取请求信息,然后分析并告诉电梯如何到达下一步,接谁。电梯需要从队列中删除完成的请求,这两个操作都需要被锁定。

但是,InputThread对共享对象的访问也被修改,它需要向请求队列添加请求,因此它也需要被锁定。

调度器设计

在这个分配中没有显式的调度器,但是RequestQueue相当于输入分配器,负责这个建筑中电梯的运输请求,LookStrategy相当于电梯调度器,负责告诉电梯下一步的行动。

队列有以下方法:

Remove(PersonRequest pr):负责删除已完成的请求。

GetFloorWaiting(int floorID):获取当前楼层的等待队列。

Boolean isEmpty():确定队列是否为空。

Boolean isInputAlive():输入线程是否已经结束,及时通知电梯结束,防止程序被终止。

无效聘用(人员请求pr):加入请求。

Void update(PersonRequest pr):一种重写观察者接口的方法,负责在被观察人状态更新时决定是否需要添加这个请求。

LookStrategy有以下方法:

GeneratePickUpList(.):生成要接的人员列表。

接下来(.):告诉电梯接下来怎么走。

线程协同架构

按如下方式绘制时序图:

顺序图

参与者M作为主要参与者

参与者I作为输入线程

参与者R作为请求队列

参与者E作为电梯

参与者的外观策略

激活M

Opt初始化阶段

M- I:创建启动输入线程

激活I

M- R:创建5个请求队列。

激活R

M- E:创建并启动五个电梯线程,并绑定到InputThread,RequestQueue。

激活E

E- S:电梯自创策略类。

目标

Opt处理请求

I-R:添加请求添加请求

E- R:获取请求队列

R-e:返回到请求队列

E-E:开门

E-E:下车

E- S:学生

成要接送的请求列表 S->>+R: 获取请求队列 R->>-S: 返回请求队列 S->>-E: 返回乘客列表 E->>E: 上客 E->>R: 从请求队列中删除已上乘客请求 E->>E: 关门 E->>+S: 请求下一步行动方向 S->>+R: 获取请求队列 R->>-S: 返回请求队列 S->>-E: 返回下一步行动方向 end opt 线程结束 I->>R: 传递输入结束信号 deactivate I R->>E: 传递输入结束信号 deactivate R E->>E: 待当前所有请求处理完毕后结束 deactivate E end deactivate M

性能分策略

性能上使用 LOOK 算法,而不是课程组的基准策略ALS,LOOK的思想如下:

如果电梯没人:

  • 如果没请求,则等待
  • 如果有请求,去接那个请求,如果必要就调头

如果电梯有人:

  • 判断当前是否需要开门
  • 如果不用开门,则沿原方向前进

另外的一些优化策略:

  • 在电梯只需要开门之后保证400毫秒后关门即可,这段时间可以随时接上来的请求
  • 对所有的请求进行排序,尽可能使得上电梯的人的目的地均匀

Bug 分析

3个Bug均在强测中被发现,互测房间非常安静

Bug 所在类 所在方法 原因
电梯会上7个人 LookStrategy generatePickUpList 考虑不周,判断条件写错了
在每层楼接人的时候会接上反方向的请求 LookStrategy generatePickUpList 考虑不周,误以为这样的优化可以提高效率
没有封装安全输出类,输出可能时间戳不是递增的 所有需要输出的位置 println 没有仔细思考输出线程不安全导致的问题
  • 第一个Bug直接导致强测一无所有,其实只是在生成接人列表的循环语句中
if (handleReqCount >= elevatorCapacity) {
	break;
}

对,就是少写了一个等于号,仅此而已

  • 第二个Bug会导致性能出现问题,会导致强测超时
  • 第三个Bug强测互测并没有体现出来

没有做足测试,就会导致出现很多致命的Bug,因此自动化测试,包括数据生成器和SPJ,重要性显著

Hack 策略

因为处于清明假期中,为了偷懒没有写评测机,也没有写Special Judge,只能随便造几组数据交上去hack,可能是互测房间水平不高,竟然可以一次hack好几个人

第六次作业

代码架构

image

由于上一次作业成绩惨不忍睹,再加上这次的题目要求有了较大变化,我对整体架构做了较大的重构

根据上次作业的Bug修复来看,”电梯-策略类“这一个模块没有什么问题,因此这一部分代码直接保留到了这次作业中,这次主要对上层的请求输入与分发系统进行了重构

本次我加入了调度器,负责管理本栋楼或本层楼的电梯(因为电梯可以动态增加),同时负责接收属于本栋楼或本层楼的请求,并把请求分派到电梯去

这次,我对横向和纵向两种不同的电梯采用了不同的分配方式,纵向电梯依然采用自由竞争的方式,调度器接收本栋楼的请求,并放入本栋楼的请求队列中,电梯之间自由竞争这些请求;对于横向电梯,我才用作业指导书中的平均分配的方式,每个电梯都有属于自己的请求队列,调度器负责接收请求,同时把这些请求平均分配到各个电梯的等待队列中

本次作业的线程依然只有两类,输入线程和电梯线程,调度器并不是单独的线程

类图如下:

image

注:LookStrategy的类图方法与第5次作业相同,故省略

同步块与锁分析

这一次作业和上一次作业几乎没什么差别,所以我也几乎没有对同步块进行修改,唯一的修改是根据周四上机实验的参考代码,把RequestQueue改的更加规范,但是由于没有理解生产者-消费者模式中的notifyAll()的用法,也没有搞清楚线程之间交互的细节,包括什么时候为什么需要唤醒这个线程,修改过程中错误的添加了若干处notifyAll(),从而导致了本次作业出现了线程间交替唤醒出现,大量占用CPU资源的情况,结果本次作业的强测也是惨不忍睹

关于加锁,我是这样考虑的:

  • 首先作为共享变量,RequestQueue中的所有操作均应当是原子的,因此都需要加锁,保证在添加、删除、筛选等待队列的某些元素、获取等待队列所有元素,这些操作都应当不被中途打断,因此需要加锁
  • 然后是调度器,调度器只会调用向队列中添加新的请求addRequest()方法,这一方法本身已经加锁,因此在调度器中无需重复加锁
  • 其次是电梯,电梯在pickUp()方法中,当乘客上电梯时,需要从等待队列中删除这一请求,表示请求已接收,为了安全起见,我把整个pickUp()方法中的上客循环作为一个同步块
  • 最后是LookStrategy,在策略类中,我们需要根据当前等待队列中的请求类型和分布决定下一步的动向,因此需要进行获取等待队列所有元素这一操作,同样为了保证获取到的元素的时效性(即不会出现当前获取到了请求,然后后序又会有请求加入),我同样会在generatePickUpList()nextMove()整个方法上锁住
  • 由于生成接送请求的列表和真正进行pickUp()操作并不是在一个同步块中,因此可能出现一人上多个电梯的情况,我选择在pickUp()的同步块里面再进行一次过滤操作,滤除所有已经不在请求队列中的请求

调度器分析

这次新加入了调度器,同时调度器就是观察者,观察输入线程的变化,然后接收自己可以处理的请求,其主要方法如下:

  • void addElevator(ElevatorRequest er):添加一个新的电梯
  • void update(Request request):相应输入线程得到的新请求,首先看是否属于自己,然后拿到之后判断是加电梯还是加乘客,如果是加乘客,就根据分配策略(平均分配或者自由竞争)放入电梯等待队列中,如果加电梯
  • void stop():输入线程利用这个函数通知各个电梯输入结束,让它们处理完队列内请求后直接结束

线程协同架构

画出时序图如下:

sequenceDiagram participant M as Main participant I as InputThread Participant SC as Scheduler Participant R as RequestQueue participant E as Elevator participant S as LookStrategy activate M opt 初始化阶段 M->>I: 创建启动输入线程 activate I M->>SC: 创建5个楼栋调度器,10个楼层调度器 activate SC end opt 添加电梯 I->>SC: 接收添加电梯的请求 SC->>+R: 建立相应电梯的等待队列 activate R SC->>E: 创建启动相应电梯线程,同时与RequestQueue绑定 activate E E->>S: 电梯创建自己的策略类 end opt 处理请求 I->>SC: 添加乘客请求 SC->>R: 将请求按照分配策略放入等待队列中 E->>+R: 获取请求队列 R->>-E: 返回请求队列 E->>E: 开门 E->>E: 下客 E->>+S: 生成要接送的请求列表 S->>+R: 获取请求队列 R->>-S: 返回请求队列 S->>-E: 返回乘客列表 E->>E: 上客 E->>R: 从请求队列中删除已上乘客请求 E->>E: 关门 E->>+S: 请求下一步行动方向 S->>+R: 获取请求队列 R->>-S: 返回请求队列 S->>-E: 返回下一步行动方向 end opt 线程结束 I->>SC: 传递输入结束信号 deactivate I SC->>R: 传递输入结束信号 deactivate SC R->>E: 将结束信号传递给电梯 deactivate R E->>E: 待当前所有请求处理完毕后结束 deactivate E end deactivate M

性能分策略

纵向电梯

  • 沿用了第五次作业的做法,自由竞争+LOOK策略

横向电梯

  • 分配上使用了作业指导书中的基准平均分配策略,电梯运行上采用了一种魔改版的LOOK策略

  • 如果电梯没人:

    • 如果没请求,则等待
    • 如果有请求,走最近的环形路程去接那个请求,这时无论是否是否同向,都接上这个请求

    如果电梯有人:

    • 判断当前是否需要开门
    • 如果不用开门,则沿原方向前进
  • 简单来说,就是捎带时,如果电梯没人,并且没有同向请求,就把反向请求接上,其余部分跟纵向的LOOK算法一样

  • 同样也使用了第五次作业中的电梯开关门和排序两种优化

Bug 分析

一个Bug在强测中被发现,导致根本没能进入互测

Bug 所在类 所在方法 原因
电梯线程被等待队列反复唤醒,占用CPU资源导致CTLE RequestQueue isEmpty()isInputAlive() 没有理解生产者-消费者模式之间的线程交互模式
  • 这一次吸取了上一次作业出现功能性Bug的教训,用Python写了一个评测机,利用状态机模拟电梯的运行,基本上支持课程网站评测中能检测出来的所有问题,然后也完成了一个简易的随机数据生成器,用作测试使用

  • 因此这次作业没有出现功能性Bug,但是线程安全Bug依旧让我一无所有

  • 这次的线程安全Bug的罪魁祸首在下面

public synchronized boolean isInputAlive() {
    // notifyAll();
    return isInputAlive;
}
public synchronized boolean isEmpty() {
    // notifyAll();
    return requests.isEmpty();
}

对,就是上面两句被注释掉的notifyAll(),导致在JProfiler调试器内就会偶现这样的场景

image

进一步,我们发现是下面两个方法占用的时间最多(这里程序相当于卡死,可以看到其实已经运行了超过100秒,但是根本没有任何输出)

image

然后继续就可以发现,问题出现在notifyAll()上面,删除上面两句即回归正常,但是为什么会出现这种结果呢?

一种可能的解释如下:

  • 电梯线程中的while循环每次开头都会检测isEmpty()
  • 而我写的isEmpty()每一次都会notifyAll()所有的电梯线程
  • 电梯线程被notifyAll()唤醒,发现无事可做,会再次调用isEmpty(),判断能否进入wait()状态
  • 这样反复电梯线程被不断唤醒,占用大量CPU资源
  • 而这样甚至导致我的InputThread被不断阻塞(上图中的红色部分),导致程序无法继续运行,卡死

由此,我们也可以总结出多线程程序的调试步骤

  • 首先检测功能性Bug,即设计能否正确完成所需功能
  • 其次检测线程安全Bug,使用JProfiler这种可以看到锁和线程状态的调试工具,用一组较强的数据多运行几次,看CPU时间和线程状态,正常来说不应当出现很多的红色(代表线程处于block状态),CPU时间也不应过长
  • 当然,最好的方法还是从逻辑上对代码的线程安全进行验证,在逻辑上正确则肯定不会出现问题,合理的使用编程范式(比如生产者-消费者模式)

Hack 策略

这次有了评测机,但是根本没进互测(

根本没有Hack机会,更谈不上Hack策略(

第七次作业

代码架构

image

为了处理换乘问题,这次作业我设计了三种线程,InputThread是输入线程,Controller总控制器单独作为线程,此外就是每个电梯为电梯线程

同样。从上次作业来看,我的调度器-等待队列-电梯这一部分系统是没有问题的,因此这次作业选择直接沿用,而主要改变了输入的分发逻辑,因为输入的来源发生了改变,可能输入来自InputThread的控制台输入,也可能来自换乘的请求重新输入,所以我设计了InputQueue,电梯和InputThread都可以向InputQueue中放置请求,也就是说电梯+输入线程与总控制器线程之间又构成了一个生产者-消费者模式

类图如下:

image

为了处理换乘,我定义了自定义的换乘乘客类,把包中给出的PersonRequest进行了包装,对需要换乘的请求进行拆分,同时SwitchPersonRequest类继承了PersonRequest类,可以进行向上转型,因此电梯类无需修改,就可以处理换乘请求

同步块与锁分析

这一次为了防止再次出现线程安全问题,我关于共享变量全部采用了设计模式,电梯+输入线程与总控制器线程之间构成了一个生产者-消费者模式,楼层/楼栋调度器与电梯线程之间构成了一个生产者-消费者模式,两者之间使用线程安全对象等待队列进行交互

这一模式经过了上两次作业的迭代和Bug修复,已经可以认为没有问题,因此这次也没有对锁块做什么修改

着重分析一下新加入的InputQueue

  • 所有对队列的删除、修改和查询都是原子操作
  • InputThreadElevatorInputQueue修改时,也都加上锁

还有一个关键问题是线程如何正常结束:

  • InputDispatcher中维护两个静态变量,一个表示已接受请求数,另一个表示已完成请求数
  • InputDispatcher的守护条件是:输入队列为空、输入线程未结束或者已接受请求未全部完成,这时候应当进入wait()状态
  • InputDispatcher的结束条件是:输入队列为空,并且输入线程结束,并且已接受请求全部完成

调度器分析

主要分析本次新增加的InputDispatcher

  • 作为一个线程,其在一个run()循环中需要完成:接受请求,对请求进行分类,拆分需要换乘的请求,分发请求
  • 此外还需要维护已接受请求数和已完成请求数,判断请求是否全部完成,在合适的时候结束程序

线程协同架构

画出时序图如下:

sequenceDiagram participant M as Main participant I as InputThread participant IQ as InputQueue participant C as InputDispatcher Participant SC as Scheduler Participant R as RequestQueue participant E as Elevator participant S as LookStrategy activate M opt 初始化阶段 M->>I: 创建启动输入线程 activate I M->>IQ: 创建启动输入队列 activate IQ M->>C: 创建主调度器 activate C C->>SC: 创建5个楼栋调度器,10个楼层调度器 activate SC end opt 添加电梯 I->>IQ: 接收添加电梯的请求 IQ->>C: 传递添加电梯请求 C->>SC: 让相应调度器添加电梯 SC->>+R: 建立相应电梯的等待队列 activate R SC->>E: 创建启动相应电梯线程,同时与RequestQueue绑定 activate E E->>S: 电梯创建自己的策略类 end opt 处理请求 I->>IQ: 添加乘客请求 IQ->>C: 传递乘客请求 C->>SC: 分配请求 SC->>R: 将请求按照分配策略放入等待队列中 E->>+R: 获取请求队列 R->>-E: 返回请求队列 E->>E: 开门 E->>E: 下客 E->>+S: 生成要接送的请求列表 S->>+R: 获取请求队列 R->>-S: 返回请求队列 S->>-E: 返回乘客列表 E->>E: 上客 E->>R: 从请求队列中删除已上乘客请求 E->>E: 关门 E->>+S: 请求下一步行动方向 S->>+R: 获取请求队列 R->>-S: 返回请求队列 S->>-E: 返回下一步行动方向 end opt 处理换乘 E->>E: 开门 E->>E: 下客 E->>E: 关门 E->>+IQ: 把换乘请求发回输入队列 IQ->>-C: 传递乘客请求 C->>SC: 分配请求 SC->>R: 将请求按照分配策略放入等待队列中 end opt 线程结束 I->>IQ: 传递输入结束信号 deactivate I IQ->>C: 告诉主控制器输入结束 C->>C: 接收电梯换乘请求,等待所有请求处理完毕 E->>IQ: 告诉等待队列请求全部处理完毕 deactivate E C->>SC: 发出结束信号 deactivate C deactivate IQ SC->>R: 传递结束信号 deactivate SC deactivate R end deactivate M

性能分策略

关于性能分上,采取了保守策略,主要是因为不敢写了:(

  • 关于调度:沿用了第六次作业的策略,横向纵向都使用LOOK策略

  • 关于分配:沿用了第六次作业的策略,横向采用均匀分配,纵向采用电梯间自由竞争策略

  • 关于换乘:采用静态拆分,把可换乘的请求拆分成三段,分别进行处理

Bug 分析

自测时发现一个Bug,强测中未被发现Bug,互测时被发现一个Bug

Bug 所在类 所在方法 原因
当出现无直达电梯的横向请求时,不会进行拆分 InputDispatcher inputProcess() 考虑不周
输入[2.3]1-FROM-A-2-tO-C-2时,会发生请求未被处理完成的情况 InputDispatcher run() 线程结束问题考虑不全面
  • 第二个Bug在互测时被发现,原因在于在电梯发出换乘请求之前,由于接受请求数和完成请求数均为0,输入线程又已经结束,因此总控制器提前结束,导致换乘请求无法被处理
  • 解决方案有两种,第一种直接判断时加上请求数不能是0,仅需修改一行,第二种需要改变判断条件和位置
  • 考虑到Bug修复的方便,我使用了第一种做法

Hack 策略

这次有了评测机,hack策略就是随机数据狂轰滥炸,定位到错误原因之后缩小范围然后提交

总结反思与心得体会

关于线程安全

三次作业中我全部都使用了生产者-消费者模式,因此共享对象都是生产者和消费者之间的等待队列,为了线程安全性的考虑,共享对象类的所有方法都设置为同步块

锁的选择:简单起见,三次作业均使用synchronized的可重入锁,简单粗暴,并没有使用更加高级的读写锁等

关于架构设计

个人认为本次作业的迭代开发特征是非常明显的,首先第五次作业完成了电梯线程-电梯策略部分,第六次作业在第五次作业的基础添加修改了请求分发逻辑,第七次作业在第六次的基础上添加了调度器,实现了换乘请求再分发逻辑

我的架构不能说尽善尽美,但是可以实现:

  • 如果电梯有新的类型(比如像大运村公寓的电梯那样只能停在奇数/偶数楼层),我可以很方便的继承Elevator类,写一个新的电梯,然后利用解耦的策略接口实现新的策略
  • 如果请求分成不同场景(比如早上大家都从高层下一楼赶早八),我可以写一个新的调度分配器,就可以处理不同的场景的请求

关于测试

分析自己采用了什么策略来发现线程安全相关的问题?

并没有什么好的方法,首先肯定是从源头上逻辑分析同步块和锁的设置是否合理,但是这种方法需要一定的经验和多线程调试基础

所以我有发现了新的工具,用JProfile软件+IDEA插件去监测方法的运行时间和锁的竞争过程,然后还可以检测CPU时间

像下图就可以看哪一个线程获取到了某一个对象的锁

image

下图就是线程的执行状态图(像下面这样就出现了问题)

image

然后还可以看到CPU运行时间,以及每个方法占用的CPU时间(这里就CTLE了)

image

所以找一组较强的数据,然后在Jprofiler下多测试几次,就可以看出是否有线程安全问题了

分析本单元的测试策略与第一单元测试策略的差异之处?

本地运行没出现问题,不代表没有问题

本地运行出现一次问题,就一定存在问题

第一单元测试时,更主要是关注考虑不周带来的功能上的缺陷,检测时是数据——结果

第二单元测试时,更主要关注的是线程间的协同工作是否正常,检测时是动态的运行过程是否正常,而不能仅仅靠结果判断

而且对于错误数据,第一单元测试出问题必定复现,而第二单元首先不一定会出问题,而且很难复现,所以第二单元需要靠一组数据运行多次进行调试

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