北航OO第二单元作业总结(2.1~2.3)

时间:2022-09-06 11:15:10

  在经过第一单元初步认识面向对象编程思想后,本蒟蒻开始了第二单元——多线程部分的学习。本单元的作业是构造符合条件的“目的选层电梯”模型,自行设计调度算法,进行合理调度,完成所有乘客的需求。由于电梯请求与运行均为实时操作,因此需要采用多线程设计。


第一次作业

1.构造阶段

  本次作业的需求是设计单部可捎带的目的选层电梯,电梯楼层为1~15层,捎带策略可自行设计,电梯容量没有限制。我在综合比较多种电梯调度算法后,采取了以下的调度策略:当电梯内无人时,采用LOOK算法;当电梯内有人时,采用指导书所给的ALS捎带策略进行捎带,这种调度算法总体来说实现起来比较容易,同时性能也能保证。

  对于类的构造,我主要构造了两个线程类:InputterElevator,并构造了控制器类Controller,负责进行人员的调度。InputterElevator采用经典的生产者——消费者模型,共享Controller对象,在访问Controller时使用同步方法。另外,由于多次用到LOOK算法,因此我构造了工具类LOOK用于计算。关于线程停止的问题,其中Inputter在输入接口中有明确的停止条件,当Inputter停止时告知控制器。对于电梯线程,当电梯内已经无人时向控制器获取主请求,此时有三种情况:

1.请求队列非空,则直接将队首请求加入电梯

2.请求队列为空,但输入器未停止,则进行wait

3.请求队列为空,且输入器已停止,则获取的请求返回null,表示电梯线程停止。

  类图如下图所示:

北航OO第二单元作业总结(2.1~2.3)

复杂度分析:

北航OO第二单元作业总结(2.1~2.3)

复杂度较高的方法大多是进行了算法的分析,其余方法圈复杂度较低,关键算法的耦合度仍然较高。

2.评测阶段

强测阶段:

  由于一开始电梯捎带算法设计得不科学,很多可以捎带的请求被拒绝捎带,导致最终个别数据点因调度时间过长被直接判错,而正确的数据点性能分也很低。

互测阶段:

  由于本次电梯构造整体较为简单,不容易出现运行逻辑的bug,因此互测阶段我没有被发现bug。我利用自动生成数据程序提交了几个测试数据,但没有hack到别人。

3.反思与总结

  本次作业是三次作业中得分最低的一次。虽然第一次作业是最基本的,但由于第一周多线程的知识我理解得很不到位,导致我在写程序阶段花费了大量的时间才通过中测,没有过多的去进行优化,导致程序性能很差。因此在以后学习新内容时一定要从一开始就理解透彻,这样能省下很多功夫。

第二次作业

1.构造阶段

  本次作业在第一次作业的基础上,增加了多部电梯的设定,电梯数量从一开始就确定下来。同时,增加了电梯限乘人数的设定,运行楼层也扩展了地下室(-1~-3层)。从整体上来看,本次作业需要扩展的内容并不多,因此我在第一次作业的基础上,从一个电梯线程变为多个电梯线程。为了减少扩展量,增加可迭代性,我在一开始就将电梯队列请求按不同的电梯严格分开来,当收到请求时通过某种算法将请求加入某部电梯的请求队列,不可改变。在设计分配算法时,我综合电梯人数平均,同时不容易被极端数据影响性能的原则,采用了随机数分配,同时考虑当前队列以及电梯内人数,调整随机数产生区间的频率(例如当前A电梯等待人数及电梯内人数较多,则相应减少分配给A电梯的频率),这种分配方式通过调整随机数产生算法很容易实现。

  对于单部电梯的调度算法和第一次作业基本相同,捎带策略只需加上的人数的限制。本次作业还需注意的一点是,因为电梯数量需要根据输入线程的第一行输入确定,而输入线程为单独的一个线程,因此为了减少线程之间的交互,保证线程安全性,电梯线程的建立由输入器线程完成,主线程仅实现建立控制器以及输入器线程,控制器的初始化(等待队列的建立)也在输入器线程中完成。

  类图如图所示:

北航OO第二单元作业总结(2.1~2.3)

复杂度分析:

北航OO第二单元作业总结(2.1~2.3)

  复杂度和上次作业差不多,主要是两次作业的相似度较高。

北航OO第二单元作业总结(2.1~2.3)

2.评测阶段

强测阶段:

  本次作业由于我采用了相对较好的分配算法,因此性能分比上次作业有较大提升。但是由于在构造时出现了重大纰漏——电梯容量判断时出现问题,导致我强测直接挂了3个点,分数仍然较低。

互测阶段:

  如上述所说,由于代码本身的bug,我被hack了两次,好在属于同质bug,一次合并修复解决。另外,我通过自动测试数据生成程序提交了多个数据,hack到同屋人的两个bug。

3.反思与总结

  本次作业最大的问题是本地测试不到位,数据强度不够,过于依赖中测结果,因此没有发现重大bug。在以后的测试中,我会尽可能考虑可能导致错误的测试数据,构造更有针对性的测试样例,增加发现bug的可能性。

第三次作业

1.构造阶段

  本次作业在上一次作业的基础上,增加了电梯种类的设定,不同种类的电梯拥有不同的载客量,可停靠楼层也不同。同时,本次作业还加入了电梯数量动态变化的设定,初始拥有三台电梯,中途可以启用新的电梯。输入接口也有一定的变化,请求分为运载请求以及增加电梯请求。

  电梯分类,可停靠楼层不同导致的一个非常普遍的问题就是有些请求不能通过一次电梯运行满足(部分楼层不可停靠),需要换乘。因此,继续采用输出接口中的PersonRequest类作为基本请求类已经不合适。在本次作业中,我构造了一个自定义MyRequest类。由于不存在一次换乘无法到达的情况,MyRequest类包含两个PersonRequest对象,分别代表换乘前和换乘后的两个请求(均为原子请求,可一次到达)。如果没有换乘,则后者设为null。MyRequest的关键方法convert代表换乘,将换乘后的请求赋给换乘前请求,自身设为null,这样就可以满足换乘需求。另外,我在产生Myrequest的时候采用工厂模式,在输入器输入一个原始请求后就计算好换乘路线,避免在电梯线程内产生过多的计算。

  本次作业中线程安全问题的处理难度有很大的提升,主要是由于除了输入器会产生请求外,电梯本身也会产生请求(即电梯既是消费者又是生产者),线程交互的复杂性提升较大。另外,线程安全、正确地停止也是本次作业的一个难点。由于电梯本身会产生请求,因此若采用上次作业的设计,将输入器停止以及电梯自身为空作为电梯停止条件,会造成部分乘客不能到达目的地的情况。上一次作业各电梯线程完全独立,一部电梯的停止不影响其他电梯,而本次作业电梯线程有交互。因此,本次作业我采用了“输入器停止且所有电梯闲置”作为电梯同时停止的条件。

  电梯闲置指的是电梯无人且没有新请求。由于电梯闲置和输入器停止有所不同(输入器停止为永久状态,停止后不会再开启,而电梯闲置是动态变化的),因此我采用了“观察者模式”,控制器充当监听者的角色,电梯每处理一个请求就更新自身状态,并告知监听者,监听者再更新电梯状态。由于某部电梯只能从控制器获取其他电梯的状态,因此获取状态以及更新状态的方法必须是同步方法。

  类图如图所示(由于本次作业方法较多,内部方法不在类图中显示):

北航OO第二单元作业总结(2.1~2.3)

复杂度分析(方法过多,仅贴出部分复杂度较高的方法):

北航OO第二单元作业总结(2.1~2.3)

2.评测阶段

强测阶段:

  本次作业我吸取了前两次作业的教训,认真进行了多次评测,在强测中没有出现bug,但总体性能分较低。

互测阶段:

  本次互测阶段我生存了下来。当然,佛系的我也没有发现别人的bug,甚至没有下载别人的代码。

3.反思与总结

  本次作业主要的问题是强测性能分过低,不少测试点性能分为0。对比前两次作业,主要是因为我在设计换乘算法时没有花足够功夫,或者说,就是相关算法不会。我采用类似于调度算法的“随机数换乘算法”,但本次作业这样做显然不妥,一是因为每种电梯运行速度不同,应尽量使用运行速度快的电梯,二是因为随机数产生的换乘楼层可能会白白运行一些楼层(比如从3到9,结果随机数产生15,导致换乘路径为3→15→9,显然不合理),当然可能还有其它原因。本次作业换乘设计实际与数据结构的知识有关,因此我今后会巩固数据结构知识,多学习算法知识,在细节上做得更好。

延展性思考

  电梯在生活中是一个使用非常广泛的工具,可能会因为各种各样的需求来扩展功能,可以在代码扩展时实现。分析本单元设计的电梯,可以发现一定的不合理性。比如,电梯仅仅以完成所有乘客请求为目标,而没有考虑满足需求的先后顺序。在现实中,如果一部电梯经常让一个先来的乘客等待过久的话,那么它一定不会被使用者认可。因此,在扩展时也许能从性能上出发,将乘客的等待时间作为性能分的一部分,而每个乘客的等待时间与性能的降低呈非线性关系(乘客的耐心程度往往随着等待时间的增加急剧下降)。同时,为不同乘客设置优先级,不同优先级的乘客等待相同时间对于性能影响是不同的。

  本单元电梯采用的是简单的载客人数限制,而现实情况是电梯载客量和乘客体重有关,在输入时给出乘客体重。另外,在现实中乘客在进入电梯前体重是无法知晓的,因此必须进行更为合理的调度,减少因体重问题导致浪费时间开关门,影响性能。


单元总结

  多线程设计是程序设计中经常遇到的问题,在本单元的学习中,我学习了JAVA实现多线程的方式以及线程调度的原理,并学习了经典的“生产者——消费者模型”、“观察者模型”等架构,使我的程序设计能力得到进一步提升。线程安全问题是多线程设计中需要处理的一个重要问题,我在这方面的处理还有所欠缺,我会继续巩固相关知识,达到熟练运用多线程设计的程度。

北航OO第二单元作业总结(2.1~2.3)的更多相关文章

  1. 2020北航OO第二单元总结

    2020北航OO第二单元总结 前言 本单元考察基于多线程的电梯调度问题,成功让我从一个多线程小白到了基本掌握了使用锁来控制线程安全的能力,收获颇多(充分体验了迷茫地de一个又一个死锁bug的痛苦). ...

  2. 【OO学习】OO第二单元作业总结

    OO第二单元作业总结 在第二单元作业中,我们通过多线程的手段实现了电梯调度,前两次作业是单电梯调度,第三次作业是多电梯调度.这个单元中的性能分要求是完成所有请求的时间最短,因此在简单实现电梯调度的基础 ...

  3. 电梯也能无为而治——oo第二单元作业总结

    oo第二单元作业总结 一.设计策略与质量分析 第一次作业 设计策略 在第一次作业之前,我首先确定了生产者--消费者模式的大体架构,即由输入线程(可与主线程合并)充当生产者,电梯线程充当消费者,二者不直 ...

  4. oo第二单元作业总结

    oo第二单元博客总结 在第一单元求导结束后,迎来了第二单元的多线程电梯的问题,在本单元前两次作业中个人主要应用两个线程,采用“生产者-消费者”模式和共享数据变量的方式解决问题.在第三次作业中加入多个电 ...

  5. OO第二单元作业总结【自我反思与审视】

    第二单元作业的完成史,就是一部心酸的血泪史…… 多线程的出现为我(们)打开一片广阔的天地,我也在这方天地摸爬滚打,不断成长!如果说第一单元之前还对Java语法有所了解的话,那么这单元学习多线程则完全是 ...

  6. 北航OO第一单元作业总结(1.1~1.3)

    经过了三次作业之后,OO第一单元告一段落,作为一个蒟蒻,我初步了解了面向对象的编程思想,并将所学内容用于实践. 一.第一次作业 1.架构分析 本次作业需要完成的任务为简单多项式导函数的求解.表达式仅支 ...

  7. OO第二单元作业小结

    前言 转眼已是第九周,第二单元的电梯系列作业已经结束,终于体验了一番多线程电梯之旅. 第一次作业是单电梯的傻瓜调度,虽然是第一次写多线程,但在课程PPT的指引下,写起来还是非常容易:第二次作业是单电梯 ...

  8. 电梯模拟系统——BUAA OO第二单元作业总结

    需求分析 官方需求 本次作业需要模拟一个多线程实时多电梯系统,从标准输入中输入请求信息,程序进行接收和处理,模拟电梯运行,将必要的运行信息通过输出接口进行输出. 本次作业电梯系统具有的功能为:上下行, ...

  9. OO第二单元作业分析

    前言 这一单元关于线程安全的作业结束了,在助教提供的接口的帮助以及老师提供的设计模型的指导下,这三次作业还是相对轻松地完成了,中间也没有出现什么bug,可能就是因为简单的逻辑不容易出错吧,可惜两次都由 ...

随机推荐

  1. Mysql InnoDB 共享表空间和独立表空间

    前言:学习mysql的时候总是习惯性的和oracle数据库进行比较.在学习mysql InnoDB的存储结构的时候也免不了跟oracle进行比较.Oracle的数据存储有表空间.段.区.块.数据文件: ...

  2. Linux文件与进程的Capability简介

    UID这种权限机制颗粒太粗,容易引起权利过剩(溢出),Linux引入了Capability:每个Capability系统内以一位Bit代表,OS内部使用64bit存储. 下面是android的capa ...

  3. Spring--通过注解来配置bean

    Spring通过注解配置bean 基于注解配置bean 基于注解来配置bean的属性 在classpath中扫描组件 组件扫描(component scanning):Spring能够从classpa ...

  4. Node.js快速入门

    Node.js是什么? Node.js是建立在谷歌Chrome的JavaScript引擎(V8引擎)的Web应用程序框架. 它的最新版本是:v0.12.7(在编写本教程时的版本).Node.js在官方 ...

  5. 艰辛五天:Ubuntu14.04+显卡驱动+cuda+Theano环境安装过程

    题记:从一开始不知道显卡就是GPU(虽然是学计算机的,但是我真的不知道…脑残如我也是醉了),到搞好所有这些环境前后弄了5天时间,前面的买显卡.装显卡和装双系统见另一篇博客装显卡.双系统,这篇主要记录我 ...

  6. Mybatis插件机制以及PageHelper插件的原理

    首先现在已经有很多Mybatis源码分析的文章,之所以重复造*,只是为了督促自己更好的理解源码. 1.先看一段PageHelper拦截器的配置,在mybatis的配置文件<configurat ...

  7. 开启Tomcat的manager页面访问

    如何进入Tomcat的manager页面 一张图解决! 找到conf目录下的tomcat-users.xml文件,打开. <role rolename="admin-gui" ...

  8. Java在Service层异常封装

    dao层不需要抛出异常,应该在service层抛出异常,可以是自定义的异常,也可以包装异常,然后在controller中定义exception handler统一处理或者单独处理. 参考: https ...

  9. html5 meta标签的认知储备

    在开发移动或者PC端的时候除了'<meta charset="UTF-8">'这个设置编码格式的meta标签,还有一些其他方面的设置 一.<meta name=& ...

  10. react-native ios打包 、设置图标 启动图片

    在这里只记录xcode 打包操作,申请证书操作,之前已经记录过了. https://www.cnblogs.com/hellovoidworld/p/4127576.html  参考了这篇文章,只是可 ...