• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

北航OO第二单元作业(Retake) 总结博客

开发技术 开发技术 3周前 (04-22) 9次浏览

前言:我在第一次接触多线程后的第12个月写下这篇博客。经过两次OO课程以及操作系统相关知识的学习,我对多线程方面的知识有了更深入的认知。我发现我之前的很多理解存在影响整体实现过程的问题,在与同学们进一步交流之后,这些问题也得以解决。去年因为疫情原因,加之我本身消息比较闭塞,不太善于利用现有资源,我错过了很多提升的机会,因此这让我更加确信地意识到及时分享问题是十分重要的。


作业架构

本单元的三次作业我采取了类似的架构,故在此一并分析。

1.整体设计模式

根据以往设计的经验以及实验的启发,我采用了经典的生产——消费者设计模式。模式整体可以抽象为:生产者和消费者线程共享一个托盘,其中涉及到托盘的操作需要加锁。在本单元的作业中,必要的线程包括输入器InputDevice和电梯Elevator,显然可以抽象为生产者和消费者。而托盘则可以使用调度器Manager来实现。

除了模式包含的线程之外,主线程的作用也不可忽视。我以往的习惯是把主类中的main方法作为主线程,但后来我意识到由于该方法为静态方法,在需要引用主类中的其他实例或方法时存在很多不便之处。因此,本单元作业中我的main方法仅有一个作用——创建单例主线程类AppRunner(虽然我不知道这个模式叫什么,但是我经常见到),在该类中完成生产、消费者线程的初始化。

另外,在第二、三次作业中涉及到电梯的加入,也就是新建线程的操作。我去年的设计是该操作直接在生产者中完成,当时的考虑是生产者读入并分析请求就可以直接创建,但这种模式会导致不同类的方法互相耦合,违背“低耦合、高内局”的设计原则,同时在不同类中创建电梯也不便于管理。因此本单元作业我采用了观察者模式,当请求加入电梯时输入器告知主线程,这样电梯的创建仍然在主线程中执行。

2.锁与同步块的设置

本单元作业中,我的所有同步都是通过对象锁来处理。依据我设计的经验,统一锁的类型既方便整体设计,同时也能降低出现线程安全问题的概率。由于我设计的大部分需要同步的方法都包含无需同步的语句,因此我为需要同步的语句块加上对象锁,不需同步的语句可以并行执行,从而提高运行的效率。

在生产——消费者模式中,生产者和消费者对托盘进行写操作时需要对托盘进行加锁,其余操作不需要加锁。在确保线程安全的前提下,减少锁的数量可以提高程序运行的效率。

3.调度器设计

第一次作业中,调度器包含的属性有请求队列、输入器是否停止以及输入模式。调度器与电梯及输入器的交互采用经典的生产————消费者模式,输入器和电梯共享一个调度器对象,并分别在调度器的请求队列加入和取出请求,输入模式和是否停止输入仅可由输入器改变。调度器本身的方法无需加锁(线程中调用它们时加锁)。在输入模式为随机的调度时,我采用的是LOOK算法,大致分为以下几个步骤:

  1. 电梯停在底层,等待第一个请求
  2. 调度器获取第一个请求时,将上升目标楼层high设为该请求起始楼层,同时开始上升。上升的同时扫描调度器的其余请求,若出现起始楼层高于high的请求,则更新high(若电梯内的某乘客目标楼层高于high,同样更新)。若当前楼层等于某请求的起始楼层,则捎带(至少留一个空位用于最高楼层请求),同时若到达某请求的目的地,则该乘客离开电梯。
  3. 电梯到达high,乘客进出。
  4. 以类似的方法,前往最低楼层low
  5. 电梯内无人且无新的请求,电梯停止

当乘客到达模式为Night时,使用这种LOOK算法同样能够取得较好的性能。当到达模式为Morning时,再用这种LOOK算法就有些不妥。此时我采取的策略是:电梯停在一楼,直到满员或者无新请求才出发。这种模式虽然在某些极端的数据下表现不佳(例如乘客到达时间间隔较长且前往楼层较低),但由于强测数据完全随机,所以采用该策略也能取得比较好的效果。

第二次作业中有多部电梯,同时增加了电梯动态加入,但每部电梯完全相同且可以到达所有楼层。在这种情况下,我采用的分配原则是:电梯请求的hashcode对电梯数量取模,得到进入电梯的编号。由于hashcode相对随机,因此可以保证在电梯人数较多时乘客数量分配比较平衡;同时,相对于直接取随机数,hashcode的结果固定,方便调试以及结果复现。

第三次作业中出现了不同类型电梯可到达楼层不同,运行速度以及容量不同,需要合理分配才能最大化地利用电梯资源。由于个人的原因,这次作业我没能够花很多时间去写,为了保证线程的安全性,我没有采取换乘策略(去年我采用换乘就出现了线程安全问题)。对于不换乘的策略,我采用了“按剩余容量比例调度”,即在保证满足要求的乘客进入速度最快的电梯的同时,保证其他类型的电梯利用率不会过低。在全随机的数据模式下,这种调度方式也获得了不错的效果。

UML图

第一次作业的UML类图和顺序图:
北航OO第二单元作业(Retake) 总结博客
北航OO第二单元作业(Retake) 总结博客

第二次作业的UML类图:
北航OO第二单元作业(Retake) 总结博客

第三次作业的UML类图:
北航OO第二单元作业(Retake) 总结博客

第二、三次作业架构相似,顺序图相同:
北航OO第二单元作业(Retake) 总结博客

如果对第三次作业进行扩展,我认为扩展换乘策略是十分方便的。依据我去年的经验,可以自定义请求类(包含两个原有请求类的实例),当输入器读到请求时可以将该请求经过路径规划转变为最快的换乘方式。路径规划可以转变为加权图的最短路径问题,权值即为不同电梯的运行速度。

BUG分析

1.分析自身程序的bug

在第一次作业实现的过程中,出现了不少关于线程安全的bug,当时出现bug的主要原因是我太久没写关于多线程的程序,很多细节早已忘记(例如等待需要在while循环中、同步方法需要notifyAll)。后来经过对照课件以及我之前写的程序,我逐一解决了这些问题,后来的设计中也没有出现明显的问题,最终在三次作业的强测和互测阶段没有出现bug

2.分析他人程序bug策略

本单元和上一单元的测试最大的区别就是需要实现定时投放。在第一次作业中,我学习了周围同学去年实现评测机的思路,并尝试调整了评测机使之能应用于本单元的评测。评测机实现的核心思路为使用管道(shell)输入输出。首先在python环境中随机产生测试数据,然后在shell中实现重定向输入输出,将测试数据定时投放到待测试的jar包中,产生的输出重定向到文件中,然后分析运行逻辑的正确性。

在具体bug分析过程中,我发现对于运行逻辑的分析并不简单,最终评测机也只停留在定时输入输出阶段,最终第一次作业没能发现其他人的bug。后面由于时间的局限,没能实现完整的评测机,也没有找到其他人的bug。不过,评测机的实现思路让我学习到了关于shell的新知识,同时最终互测结果表明,除第二次作业以外我所在互测屋并不存在什么bug,因此也没有留下什么遗憾。

心得体会

本次重修多线程单元还是有比较多的心得体会的。

首先,架构设计的过程让我进一步体会到一个好的架构层次是多么重要。前人在设计过程中总结出的一些经典设计模式必有其可圈可点之处,以我目前的代码能力,尝试尽可能遵循经典的设计模式是很好的选择,如果为了追求一点方便或者性能打破设计好的架构,必然会降低代码整体的可扩展性,增加出bug的可能性。一定要在保证正确性的前提下进行扩展,提高代码的性能。

其次,对于线程安全问题,一定要保证思考方面的全面。线程安全绝对不是强行添加synchronized就能解决的,要能理解多线程运行以及锁的根本运行机制,否则,一旦出现了bug,将难以找到修复bug的有效途径,很可能会引入新的bug。与上一单元相比,本单元作业对于知识理解的要求显然更高。

多线程模块无论是在之后的工作面试还是在具体项目的设计都会经常涉及到,本次重修我得以系统性地重新学习这一模块,不管是作业分数还是知识的理解都有很大的改观,可以说是收获颇丰的一单元。


程序员灯塔
转载请注明原文链接:北航OO第二单元作业(Retake) 总结博客
喜欢 (0)