欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

BUAA_OO_2020_UNIT2

程序员文章站 2022-03-03 10:40:41
BUAA_OO_2020_UNIT2 一、程序结构分析 + 第五次作业 UML & Mertrics ​电梯的调度问题,实质上就是任务的请求与分配问题,笔者在第五次作业中采用简单的“生产者 消费者”模型,建立了 线程作为生产者解析输入并增加运载请求,建立 线程进行输出,待处理数据由主控类 维护,并 ......

buaa_oo_2020_unit2

一、程序结构分析

  • 第五次作业

    uml & mertrics

    BUAA_OO_2020_UNIT2

    BUAA_OO_2020_UNIT2BUAA_OO_2020_UNIT2

    ​ 电梯的调度问题,实质上就是任务的请求与分配问题,笔者在第五次作业中采用简单的“生产者-消费者”模型,建立了din线程作为生产者解析输入并增加运载请求,建立elev线程进行输出,待处理数据由主控类ctrl维护,并作为电梯“调度器”,前两者的操作由线程安全的ctrl负责,后两次作业也延续这样的架构,事实是无需重构也应付得了本次迭代。但笔者请求队列与调度器一体化,且只有一级调度,导致主控类异常臃肿。

  • 第六次作业

    uml & mertrics

    BUAA_OO_2020_UNIT2

    BUAA_OO_2020_UNIT2BUAA_OO_2020_UNIT2

    ​ 仍是老三样,第六次作业中扩展功能比较容易实现,进行相关类的方法扩写,主要是实现多电梯线程,笔者ctrl类的处理不是很好,下一次重写了ctrl

  • 第七次作业

    uml & mertrics

    BUAA_OO_2020_UNIT2

    BUAA_OO_2020_UNIT2BUAA_OO_2020_UNIT2

    ​ 架构上没有大的改动,为实现换乘功能,笔者建立了myreq类存储personrequst与乘客现处楼号,并面向过程根据换乘地图为各型电梯建立了楼层映射机制

二、bug分析

  • 第五次作业中主要遇到的是多线程初见的线程调度bug,主要是笔者当时没有找到精准的notify()条件,居然唤起了runnalbe的线程,由于ctrl是共享的,导致输入被电梯线程阻塞,好在最终确定了进入wait()的条件。
  • 第六次作业笔者体会到了线程安全问题在本单元的重要性,在处理电梯数目输入时,笔者竟然没用输入文档的elevatorinput.getelevatornum(),而是用(new scanner(system.in)).nextint(),system.in被输入接口与scanner共享,导致输入缓冲区线程不安全,笔者这次属实垮台了,直接一波愉悦送走
  • 第七次作业又出现了恶性bug,当c型电梯上的乘客想去楼4时,笔者直接给他送到楼3,但楼3只有c能去,b接不到,这次强测也是差点翻车了,不过三次作业笔者的整体结构还是可以的,通过严格控制synchronized语句块的分布与使用,三次作业除了这些bug也没有出现过死锁或是数据冒险啥的难以复现的bug

三、互测策略

  • 第五次作业功能比较简单,只要保证简单的线程调度就只用考虑单电梯调度问题,可以输入30条从底楼到顶楼的数据测试他人是否完成了捎带
  • 第六次没进互测,不过笔者认为可以从电梯超载与输入指令数最大化这两方面进行hack
  • 第七次重点在于线程安全与换乘,可以输入仅1条需要换乘的指令,测试他人是否在换乘完成前相关电梯线程已退出,更可以围绕换乘问题,观察三类电梯楼号的定义域可以发现1,3,15是最特殊的3个换乘点,也可以枚举所有请求后排除直达请求进行换乘的完备hack

四、对象创建模式

  • 第五次作业只建立了输入线程din,电梯线程elev,看到一些朋友把调度器也整成线程我是没想到的,din负责向ctrl输入数据,并在输入及结束后唤醒所有waitingelevelev的结束条件是没有待调度请求并且din在结束后设置了无输入的全局变量。具体调度策略方面,选用look算法,但无论scan还是look,都损失了一个方向上的请求信息,总感觉不太好。于是之后笔者就真香greedy了,打造了纯贪心的电梯调度与电梯间调度策略

  • 第六次作业改动不多,主要是改变了ctrl中的数据结构适配多部电梯,另外的重头戏就是电梯间调度,笔者在本次将单电梯改为贪心电梯,与同学交流中有的是用平均分配、随机分配来分派任务到各个电梯,但笔者还是采用了电梯间*地贪心竞争策略。原因是,设想有两架elev,一台空载,一台载有乘客,从同一楼号出发,对于某一请求而言,载人elev因为电梯内请求而停靠或转向的平均概率更高,空载更有可能抢到请求。实际上载客越少越能直接相应电梯外请求,这有效减小某些电梯一直空转的几率,从而自动实现了优先级任务分配,提高了elev并行率,每次上一个人也可以thread.sleep(5)提高并行率。还有就是这样不用写二级调度了

  • 第七次作业,鉴于要实现换乘,有必要维护需要换乘乘客的当前楼号,于是笔者新建了myreq类改进personrequst,对于上文二、notify了运行线程的bug,笔者也找到了安全方便的方案

    for (int i = 0; i < elevnum; i++) {
                if (elevs.get(i).getstate().equals(thread.state.valueof("waiting"))) {
                    synchronized (elevs.get(i)) {
                        elevs.get(i).notifyall();
                    }
                }
            }//先判断是在wait()再notifyall();
    

    同时要注意线程安全的坑,笔者是保证所有elev最后一起dead的,防止要换乘的电梯早退

    解决线程设计后,烦人的换乘问题来了,各型电梯的楼号定义域a = [-3, 1] ∪ [15, 20],b = [-2, 15] - {3}c = [1, 8] * 2 - 1,找到换乘点(a ∩ b) ∪ (a ∩ c) ∪ (b ∩ c) = c ∪ {-1, -2},笔者并不想写二级调度,就建立了地址转换,考虑elevmyreq的解析,我们只要在电梯a-c下完成myreq在电梯内和在电梯外的楼号转换就行,实际上完成前者就行,若电梯内gettofloor()非法,就将目的地改为换乘路径最短的换乘点。电梯外的话,先假设上电梯,转换后若目标就是当前楼层,就保留原本目的地,否则上电梯。笔者真是懒死了,这类特定情境问题还是最好画图分析或打表,别像笔者败在细节。

五、心得体会

​ 笔者本单元的作业效果并不理想,还是对于线程安全的理解不深,以及没有注重多线程程序设计中的细节问题导致bug,笔者还是对自己的调度器耿耿于怀,笔者理应实现队列,调度分离的,这样的调度器耦合度太高了。