• 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

2022-OO-Unit2

mashiroly

1. 总体思路

本单元的要求是模拟多部电梯的调度,重点是设计一个多线程的安全并发协作架构。基本思路还是“生产者-消费者”模式,把“生产者”和“消费者”固定下来,为不同的功能构造不同的“盘子”。电梯运营策略经历了从ALS策略到LOOK策略的迭代。在此基础上,通过线程安全的精心设计,弱化调度,强调自由竞争,从而提高面对不真实场景(数据或随机或有针对性的构造,毫无特色可言)时的性能。

2. 架构迭代

2. 1 第1次作业

思路概述

在得到标题之初,我就想着设计一个“单实例集中式神调度器”。电梯只是一个无情的工具人,知道他要去哪里就够了,调度员完全负责生成这个方向信息。

但是仔细考虑一下实现:在一次循环,调度程序应该完成1。取出一个或所有输入请求;2.根据电梯状态完成了派遣。可能出现的问题如下:1。将线程类设计成另一个线程属性是不合理的,这需要分离“电梯状态”(用于共享)与“电梯线程”; 2。看起来“调度”和“请求输入”是同步的,调度器没有必要作为线程;3.所有的复杂性都交给了调度器,调度器在循环中花费很长时间,并且不能及时调度请求。三个问题叠加后总觉得这个结构不够具体,还是回到经典的“生产者-消费者”模型吧。

在我的理解中,请求输入-调度、调度-电梯行为都是异步关系,两组关系中的前者并不关心后者的状态和如何处理。参照训练代码,构造两组“生产者-消费者”。图示如下。

流程图LR

子图生成器

输入线程

调度程序

目标

子图托盘

等待队列

进程列表

g[进程队列1]

h[进程队列5]

K[.]

目标

子图消费者

b[调度程序]

I[电梯线程1]

升降线5

目标

这是。-K

A - W - B

C - F -。- G - I

这是。-H - J

架构说明

类图:

yb5r3kdit104834.png

描述:

RequestQueue:需求队列,PersonRequest的聚合。共享waitQueue和processQueue都是RequestQueue。

要处理的processQueue是按电梯和楼层划分的(在本次操作中两者是相同的)。从上图也可以看出,在“按电梯划分”,每个电梯线程都有一个进程队列。

processQueue的聚合进程列表由调度程序直接管理。

Scheduler:调度程序。其实所谓的“调度”只是根据电梯ID将输入请求分配给共享对象processQueue,也叫“Dispatcher”。

ElevatorThread:电梯负责打开和关闭门dealIO()、选择运行方向selectStatus()和运行move(),以便尽可能地协调从属于电梯的行为。因为PersonRequest的处理是“当一个人进入电梯时,会从processQueue中删除,所以也需要用waitTable保存电梯中的人。

另外,当dealIO()需要遍历processQueue时,将其删除。获取信息和讨论区,采矿

用迭代器可以完美解决。
调度策略

本次作业采用基准策略ALS,根据指导书描述实现。指导书对ALS的描述看起来很奇怪,其实只有两部分:1. 确定主请求,方向(moveStatus∈{UP, DOWN, STOP})由主请求决定;2. dealIO()时判断稍带。

        if (iter.getFromFloor() == nowFloor
                && !waitTable.containsKey(iter.getPersonId())
                && (getRequestDirection(iter).equals(moveStatus)
                || getRequestDirection(iter).equals("STOP")
                || moveStatus.equals("STOP"))
                && !this.isFull()) {
            //PersonIn
        }
线程安全问题

本次作业还是比较严格的”生产者-消费者“,线程安全问题主要出现在对共享对象的互斥操作。在共享对象类RequestQueue中,对所有读写方法(我的实现中,所有方法都是)设置synchronized同步块,加方法锁。

对于互斥操作涉及多个方法和复杂逻辑(典型如需要遍历processQueuedealIO()),自然是同步块加对象锁保证互斥。

线程不安全的官方输出需要加方法锁,封装成类,保证调用的互斥。

轮询问题

同步块内wait-notify用于避免轮询。具体而言,如果所有处理未结束,则Scheduler中使用synchronized同步块对waitQueue上对象锁,如果为空则wait()ElevatorThreadProcessQueue上锁,如果和waitTalbe均为空则wait()

只有putRequest()setEnd()可以notifyAll(),前者是有请求输入,后者是输入结束,以提醒各个线程处理完成后退出。也就是说,只出现两个notifyAll(),保证正确而极大减少轮询。

2.2 第2次作业

思路概述

增加横向电梯?不过是体力劳动罢了。(逃)
同一楼座多部电梯的协作是这次作业的主要问题。为了避免过于复杂的调度器类和调度方法,导致奇怪bug太多、互斥同步复杂,最终还是选择自由竞争,把Request分配给同一楼座的所有电梯、抢不到人就消除请求,就只需解决同步问题了。为此增加了新的共享对象outPassengers.

flowchart LR subgraph Producer A[InputThread] C[Scheduler] L[Scheduler] end subgraph Tray W[waitQueue] F[processList] G[processQueue1] H[processQueue5] K[...] M[outPassengers] end subgraph Consumer B[Scheduler] I[ElevatorThread1] J[ElevatorThread5] N[ElevatorThread1..n] end F-.->K A---> W --->B C ---> F -.-> G-->I F -.->H-->J L --> M M --> N

此外,上周的ALS策略性能不妙,本周改写了LOOK策略。

架构说明

类图:
5kbbunh15ud4835.png

说明:

整体上变化不大。

  1. ProcessTree类:和上一次作业的processList功能相同,都是待处理队列的聚合。由于自由竞争需要检索同一楼座的所有电梯,涉及遍历,这个类目的就在于构建多级索引减少遍历次数。(后来才发现最多只有15部电梯,直接遍历可能还更快吧)
  2. ExPersonRequest:拓展的需求类。
  3. Scheduler:负责分配载人请求和直接处理增加电梯请求。(仅一个方法,没必要再加一个电梯管理类)
  4. ElevatorThread:横纵电梯集成在一个类,由type切换模式。纯粹是方便拓展横纵可切换的电梯。”按电梯划分“processQueue的优点在这里体现出来了,每部电梯对请求的处理独立,无需手动阻塞避免冲突。
  5. OutPassengers:处于电梯外的人。”电梯外“针对全局而非某一楼座,也因此共享对象outPassengers是所有电梯和调度器共享的。和”按楼座划分电梯外的人“相比,全局的“电梯外”牺牲的是访问共享对象时会阻塞所有线程,换来的是避免大量复杂的线程控制,以及方便拓展”换乘“。而“牺牲”可以通过读写锁缓解。
调度策略

纵向:LOOK策略,主请求定方向,记录楼层极值,到当前极值后停下/转向;

横向:类LOOK策略,主请求定方向(最短路径方向),记录目标楼座,到达后停下/转向;

线程安全问题

仍是通过synchronized同步块实现对共享对象outPassengers的互斥读写。

2.3 第3次作业

思路概述

横向电梯新增可达性约束,电梯需要参数化,真的很麻烦呢。

增加换乘需求是主要问题。将所有PersonRequest划分为“纵-横-纵”三阶段,用状态机更新PersonRequest本身,如果未完成则放回waitQueue中。

flowchart LR subgraph Producer A[InputThread] C[Scheduler] L[Scheduler] O[ElevatorThread1..n] end subgraph Tray W[waitQueue] F[processList] G[processQueue1] H[processQueue5] K[...] M[outPassengers] end subgraph Consumer B[Scheduler] I[ElevatorThread1] J[ElevatorThread5] N[ElevatorThread1..n] end F-.->K A---> W --->B C ---> F -.-> G-->I F -.->H-->J L --> M M --> N O --> W

仍采取自由竞争+LOOK策略。

架构说明

类图:
qvdqocb4hqg4836.png

顺序图:

mdvmtulibb14837.png

说明:

其实可以发现,waitQueueprocessQueue虽然都是RequestQueue类的对象,但两者的行为、在架构中的位置已然分道扬镳,完全可以再加一层封装或采用多态,各自实现的方法。时间所限没有这样做。

  1. requestQueue新增属性count及相应的加减方法,供waitQueue使用,表示请求未完成的人数。如果没有这一计数,电梯线程将提前被调度器调用的setEndAll()终止。
  2. ExPersonRequest内部实现状态机,根据“纵-横-纵”三阶段划分,对外暴露当前阶段的起终点。被电梯线程处理时直接更新本体,放回waitQueue的也是本体。也就是说需求的数量是不变的,变的只有对外暴露的”接口“。
  3. Scheduler:由于可信赖的自由竞争,调度器最终也没有实现一开始规划的复杂”调度“任务。不如就叫DIspatcher吧。
  4. ElevatorThread:最终也没有出现斜向电梯和类型可变电梯。集成两种类型的电梯就当减少类图工作量吧。
调度策略

中转楼层的选择根据官方策略,遍历所有楼层取有可达电梯的最近楼层。

”按电梯划分“ProcessQueue依然非常适合自由竞争。

线程安全问题和轮询问题

秉持锁最小化的思路,尽量缩减同步块的范围,并避免嵌套,至少绝对不出现:

synchronized(A) {
	synchronized(B){
	notifyAll()
    }
notifyAll()
}

针对不同情况的wait后能正确被唤醒, 在RequestQueue类的subCount()方法增加了第三个notifyAll(),与setEnd()方法的notifyAll()功能完全相同。

3. 度量分析

直接看第3次作业的度量分析。

method Cogc ev(G) iv(G) v(G)
Scheduler.addPersonRequest(ExPersonRequest) 16.0 6.0 6.0 7.0
ElevatorThread.checkIn(ExPersonRequest) 6.0 3.0 6.0 7.0
ElevatorThread.lookUpdown() 13.0 2.0 6.0 8.0
InputThread.run() 10.0 3.0 6.0 6.0
ElevatorThread.run() 15.0 5.0 8.0 10.0
Scheduler.run() 15.0 4.0 9.0 10.0
ElevatorThread.dealIO() 27.0 4.0 12.0 12.0
Total 186.0 87.0 136.0 164.0
Average 3.0 1.40 2.19 2.64

除了run()方法,look策略、dealIO均有遍历并操作,addRequest有多级索引检索,dealIO、checkIn/Out涉及复杂的判断、分支,因此复杂度较高。

class OCavg Ocmax WMC
SafeOutput 1.0 1.0 1.0
RequestQueue 1.0 1.0 13.0
ProcessTree 1.625 4.0 13.0
OutPassengers 1.125 2.0 9.0
MainClass 2.0 2.0 2.0
InputThread 3.0 5.0 6.0
ExPersonRequest 1.84 5.0 24.0
ElevatorThread 4.91 9.0 59.0
Scheduler 4.25 7.0 17.0
Total 144.0
Average 2.32 4.0 16.0

ElecatorThread的复杂符合设计预期。Scheduler的复杂度来自一次循环对多个共享对象操作、反复进行多级索引检索。

4. Bug分析

本单元手工构造数据只能覆盖几种明显的边界情况,主要依靠随机数据生成,参考讨论区和自己的理解造了简陋的评测机。只要开多个终端,我也实现多进程评测了对吧。(雾)

第1次作业的bug是输出线程不安全,输出时间戳顺序不递增。用线程安全的SafeOutput类封装输出解决。

第2次作业的bug是电梯线程对outPassengers的访问涉及两步两个方法,没有加锁,导致线程安全问题。

第3次作业的bug真是欲哭无泪。直接贴修复文档吧。只能说第2次作业的开门逻辑拓展性太差,第3次没多想直接沿用就爆炸了。

修改了电梯在自由竞争中的开门逻辑问题。

  1. 横向电梯接人时只考虑起点能开门,没有考虑终点也需要能开门。

    举例说明:对某换乘Request选择中转层时,依据某层起终点均可达的电梯Ele 1;但自由竞争中,可能出现中转层另一部电梯Ele 2,对该Request起终点不可达却成功接人。

    修改方案:加上对终点的判断条件。

  2. 自由竞争时,未被电梯接走的人用共享对象outPassengers保存。但有关该共享对象的分支和修改放在了if(checkin)分支内,即:先确定能进入,再确定有无此人,如果没有则说明其他电梯接走了,删除Request。

    在hw6中,由于Request不可变,即使某部电梯已接走人,同层(座)其他电梯总能进入if(checkin)并正确删除。

    在本次作业中,我的实现是修改Request本身,而非继续将Request作为不可变对象、new新的Request加入调度。因此,当”building”请求变为“floor”请求(或相反),电梯再也不能进入if(checkin),该Request始终无法删除,电梯陷入死循环。

    修改方案:调整if(checkin)和查询outPassengers的顺序。

5. 心得体会

纵观三次作业,迭代拓展主要体现在增加实现新功能”共享对象“,经典的”生产者-消费者“模式一招鲜吃遍天下。可以说,想明白了”共享对象“后才真正感觉设计掌握在自己手中。对于outPassengers,可以采用”读者-写者“模式优化。

感觉对比往年作业,今年弱化了调度、强调多线程设计的正确性。为什么这么说呢?因为既没有要求多策略切换,请求集合也没有贴近现实场景的”特征“(也许数据有,但题目中从未提及),实在很难找到某种调度策略应对如此随机和针对性的数据(就好像分支预测永远失败的CPU) ,看似摆烂的自由竞争成为挺不错的选择。在”调度优化“和”多线程设计“两种培养目标的权衡之间,至少我觉得重点放在”多线程设计“体验还不错。

Link to comment
Share on other sites