BUAAOO第二单元总结之电梯问题

时间:2024-10-09 23:36:03

---恢复内容开始---

Homework1 傻瓜电梯

程序架构

BUAAOO第二单元总结之电梯问题

第一次题目非常简单,思考也非常简单,一部电梯傻瓜调度。将命令入公共的队列,电梯从公共队列中取命令即可,其中只需要使用ArrayBlockingQueue就可以使线程安全,并不需要加上锁,因为只有这个队列需要公共访问修改,使用阻塞队列即可。

同步控制

第一次作业结构简单,只需要使用ArrayBlockingQueue就可以实现同步控制。

BUG的出现

1.使用电梯取队列命令时,若也使用阻塞取,就可能使整个线程阻塞而无法退出,因此我是用poll进行取。

2.程序退出不能仅仅判定输入为NULL,还得注意命令队列是否为空,不然将导致命令还没执行完就退出。

Homework2 捎带电梯

程序架构

BUAAOO第二单元总结之电梯问题

这一次作业对电梯的架构做了很大的调整。它与第一次是完全不同的,因为第一次过于傻瓜,其实整个电梯类并不是电梯,而是一个运算器,对from和to两个floor进行运算时间即可,本质上并不是电梯。

所以首先我得明确什么是捎带,什么是电梯,捎带就是电梯仍然就是这么去接人,只不过接人的路上可能可以捎带上别人,它的接人方向和放人方向始终没有任何变化,因此我就将电梯的属性做了很大的调整,楼层的概念变得没那么重要,而方向作为主要属性,接人方向,放人方向和接人的极限层(即从接人任务结束的那一层)作为电梯每次开始运作的基础,然后每一层再给它分配任务,而不对这三个属性做任何变化。

比起第一次的傻瓜电梯,多加了一个调度器类,同时将请求队列放在了调度器中(调度器并不是一个线程,只是一个普通类,在电梯要调用时调用)。电梯多了outelelist和inelelist两个数组,用于存储在电梯外等候的人和在电梯里的人。电梯以pick和put为一次流程,每一次流程给电梯设置pick的方向和put的方向,以及pick的楼层,然后电梯开始运行,每当运行到一个楼层(初始层也算),就给电梯分配可以捎带的任务并且加入到电梯的outelelist,并且检索outelelist是否有可以进入电梯的,有就加入inelelist(等于人进电梯),并检索inelellist检索是否有达到楼层的,有就从inelellist移除(等于人出电梯),这些操作就完成了这一层的任务,并继续运行直到pick和put结束。

同步控制

虽然第二次设计复杂了很多,但是其实被线程共享的数据只有主请求队列,而电梯内部的两个接人放人数组都是私有的,只为电梯线程使用,因此不需要控制,所以我主请求队列仍然使用阻塞队列即可。

BUG的出现

1.起初我数组遍历使用下标从小到大进行遍历并且检索到就用数组的remove,这就会导致当我remove一个元素之后使size变化而下标i继续增长,某些元素无法检索到,解决办法就是从大到小遍历。

2.在调度器每次给电梯设置pickdirection时,将正确的direction传递给电梯,然而调度器内部记录的direction没有变化,导致会增加一些不能经过的捎带任务,从而使电梯不断爬楼却无法到达捎带楼层而无限爬楼。

Homework3 捎带电梯+多部不同的电梯

程序架构

BUAAOO第二单元总结之电梯问题

BUAAOO第二单元总结之电梯问题

BUAAOO第二单元总结之电梯问题

复杂度控制还行

BUAAOO第二单元总结之电梯问题

电梯类

BUAAOO第二单元总结之电梯问题

电梯和调度器的时序图

类的数量并没有变化,依然是电梯类,调度器类,输入类,和主类。电梯完全可以复用,只要设置上升下降速度,载客量,可停靠楼层,开关门时间就可以将多部电梯一样操作。

多部电梯和任务的关系是竞争关系,电梯去竞争任务而不是靠调度器调度任务,对调度器加锁,每次只有一部电梯可以进行调度,其他电梯就得等待。

对于载客量的限制,只要调度器每次判定电梯的总任务数量是否超过载客量(包括电梯内的和电梯外的),只要超过就不派发。

对于楼层问题,直达楼层就如作业二一样,并没有任何变化。而对于不直达楼层,我们需要对其进行分割,将其分成两个可以直达的任务,即分割第一任务和分割第二任务,这就需要解决以下几个任务:1.何时分割。我在Input类就进行了分割操作,一输入并不马上加入任务队列,而是先进行分割操作。2.如何保证先做完分割出的第一任务,再执行第二任务(即先送到中转楼层,再去接他到目的楼层,不然会造成去接但是人还没到的情况),因此我在调度器中加入了waitqueue和wastequeue,waitqueue存储的就是分割出来的第二任务,而wastequeue是电梯inelelist中被remove的元素。每次调用调度器,就检索整个wastequeue,查找其中是否有和waitqueue中相同的id(因为中转的是同一个人),有就把waitqueue中的请求加入主请求队列等待电梯竞争,没有就找下一个,并且把wastequeue的元素都清空。这样就可以保证时间的先后性,但是多次的循环检索可能会造成计算时间过长。

同步控制

新增的waitqueue和wastequeue都为多线程共享,因此我将其都调用线程安全类,使用ArrayBlockingQueue和ConcurrentHashMap两个类,保证其线程安全,同时在使用调度器的代码块加上锁,从而保证每次只有一部电梯调用调度器。这样就完成了整个同步控制流程。

BUG的出现

这次最严重的bug就是时间问题,CPU常常超出所规定的时间,原本我采用第二次作业的版式,只在电梯类的最后加入一条sleep()指令来完成暂时的休眠,然而第三次作业的调度器类太过于臃肿,其中循环检索太多使CPU运行时间过长,所以我就在每次调用调度器就notifyall并wait,并且在调度器内部也穿插了sleep,然而这就会导致另一个问题,当另外两个电梯结束线程后,就会使最后一个电梯永远停留在wait状态,于是我就使用wait(time),当wait超过time的时间就自动唤醒,从而解决了一个电梯运行的无限等待问题。

查找BUG策略

对于自身BUG查找,使用print法,在每次线程调度的开头和结尾都使用print,并且使用部分模拟数据来测试。

对于查找他人BUG,并没有很好的办法。

三次作业总结

这三次作业,让我对于多线程编程有了更加深刻的认识。它和单线程有着很大的差别,对我们的编程能力有着很大的考验,这就需要我们严谨的架构能力和对线程安全的重视。 我的架构能力确实有所提升,第二三次作业都是使用同一个架构。然而我对同步控制仍然还有很大缺陷和漏洞,我仅仅使用简单的线程安全类和一把锁,锁的范围过大也导致了某部分代码块需要运行过久时间,对notify和wait的使用也仍然生疏,这还需要多加练习。