OO第二单元博客作业

阳光穿透心脏的1/2处 2021-12-10 10:25 201阅读 0赞

本单元的三次作业均为多线程相关的电梯调度问题。三次作业依次为单电梯FCFS调度、单电梯ALS调度和三电梯任意调度。其中第三次作业中的三部电梯相比前两次作业多了电梯容量限制和可停靠楼层限制。

本文将从**多线程的协同和同步控制**、**基于度量分析程序结构**、**分析程序bug**、**发现他人bug所采用的策略**对三次作业分别进行分析。

--------------------

*  ### 第一次作业 ###
    
     *  #### 多线程的协同和同步控制 ####
        
        第一次作业是单电梯FCFS调度，调度器作用不大。实际上我三次作业都没有调度器，只有请求队列。在总结课上才发现调度器的骚操作，相关部分将放在第二次作业中详述，毕竟那是它最骚的部分。
        
        在第一次作业中我一共有两个线程，**请求输入线程**和**电梯线程**。这两个线程共享**请求队列**，构成一个两级的生产消费者模型。
        
         *  **共享对象**
            
            共享对象成员变量为请求队列。
            
            同时为了操作方便，且看起来较为直观，将线程调度相关方法也封装进共享对象内。
            
            由于当时对于多线程的了解还较为浅显，于是为了线程的绝对安全，所有的锁均无脑加载了方法上。
            
            （J3的门不是我关的，不我不是我没有QAQ）
         *  **请求输入线程**
            
            负责轮循读入请求。
            
            每读入一个请求，notifyAll一次，将电梯唤醒（快起床干活）。
            
            同时为了平稳结束，在请求输入结束，即personRequest == null时产生inputStopped信号，传递给共享对象。共享对象inputStopped成员变量置位，并notifyAll。
         *  **电梯线程**
            
            负责接客接送乘客。
            
            在整个请求队列为空的时候陷入wait，等待被唤醒。
            
            电梯线程被唤醒有两种可能，一种是请求输入线程已经结束，此时电梯执行完共享队列里现有的请求就可以跪安了。
            
            另外一种是有请求进入队列了，这时应该获取这个请求并执行。
     *  #### 基于度量分析程序结构 ####
        
        第一次作业我一共有四个类：
        
         *  **Main类**
            
            初始化时间戳；创建共享对象和线程并启动线程。
         *  **Controller共享对象类**
            
            包括对共享队列的操作和线程调度。
         *  **Requests请求输入类**
            
            轮询读入请求。
         *  **Elevator电梯类**
            
            执行上下楼，开关门，进出人的操作，并输出。
            
            ![1615671-20190422215218256-1740745096.png][]
            
            **类图**
            
            ![1615671-20190422215240094-1416914934.png][]
            
            **Method metrics**
            
            ![1615671-20190422215302003-1443371603.png][]
            
            **Class metrics**
            
            面向对象程序设计有五项原则，并称为SOLID原则，以下是一波科普：
            
            >  *  **Single Responsibility Principle 单一功能原则**
            >     
            >     认为对象应该仅具有一种单一功能的概念。
            >  *  **Open Close Principle 开闭原则**
            >     
            >     认为软件体应该是对于扩展开放的，但是对于修改封闭的。
            >  *  **Liskov Substitution Principle 里氏替换原则**
            >     
            >     认为程序中的对象应该是可以在不改变程序正确性的前提下被它的子类所替换的。
            >  *  **Interface Segregation Principle 接口隔离原则**
            >     
            >     认为多个特定的客户端接口要好于一个宽泛用途的接口。
            >  *  **Dependency Inversion Principle 依赖反转原则**
            >     
            >     认为一个方法应该遵从依赖于抽象而不是一个实例。
            
            本次作业结构较为简单，故仅涉及前两项原则。其中单一功能原则可以满足，而开闭原则有所欠缺，程序扩展性不足，这也是后两次作业均存在的问题。
     *  #### 分析程序bug ####
        
        本次作业的最初版本不能平稳停止，在修改之后可以平稳停止了但是会出现电梯罢工的问题，即请求队列不为空，但电梯线程已经结束。
        
        问题出在请求获取方法：
        
            public synchronized PersonRequest pop() { while (arrayList.isEmpty() & !inputStopped) { try { wait(); } catch (InterruptedException e) { e.printStackTrace(); } } if (!arrayList.isEmpty()) { return arrayList.remove(0); } else { return null; } }
        
        while循环外部原先的写法是：
        
            if (inputStopped) { return null; } else { return arrayList.remove(0); }
        
        就很菜，菜到抠脚。
     *  #### 发现他人bug所采用的策略 ####
        
        今晚是个平安夜。

--------------------

*  ### 第二次作业 ###
    
    大型翻车现场。看不透当时是谁给的我自信，拿着自己写的大bug就往评测机上撞。
    
    泣血立下flag，再不好好测试就提交我食shi。
    
     *  #### 多线程的协同和同步控制 ####
        
        线程间的关系以及协同控制和第一次作业一样，仅修改了Elevator类中电梯的运行方法。
        
        在总结课上才发现控制器的妙处。请求输入线程和请求队列这一层生产消费关系中，请求队列中的请求是按到达时间排列的。如果引入控制器，就可以通过一个简单的排序，调整队列中请求的顺序，将fromFloor相同的请求放在一起，这对于可以捎带且没有容量限制的电梯可以说是非常快乐了。
     *  #### 基于度量分析程序结构 ####
        
        >  *  **Main类**
        >     
        >     初始化时间戳；创建共享对象和线程并启动线程。
        >  *  **Controller共享对象类**
        >     
        >     包括对共享队列的操作和线程调度。
        >  *  **Requests请求输入类**
        >     
        >     轮询读入请求。
        >  *  **Elevator电梯类**
        >     
        >     执行上下楼，开关门，进出人的操作，并输出。
        
        以上内容摘自《OO第二单元博客作业》，第一次作业，基于度量分析程序结构部分。(这两次作业真的没什么差啊)
        
        ![1615671-20190422215340878-1390202428.png][]
        
        **第二次作业类图**
        
        ![1615671-20190422215407839-386732787.png][]
        
        **Method metrics**
        
        ![1615671-20190422215426773-561493289.png][]
        
        **Class metrics**
        
        本次作业满足了S原则，但没有满足O原则，同时Elevator类中的travel方法过于复杂，应该考虑进行拆分。这个方法也正是强测和互测中的大礼包。
     *  #### 分析程序bug ####
        
        w无脑bug出在电梯调度上，与线程安全无关。
        
        一共被测出两个bug。
        
        一个是在同向捎带的时候，在更改主请求的时候，没有考虑到如果在当前楼层电梯里的人全部出去了，那电梯的方向可以是任意的，等第一个人进去之后才固定下来。
        
        另一个同样是与电梯换向相关。我的电梯只有在电梯为空且请求队列中无可捎带请求时才会返回到run中的while重新获取一轮主请求。也就是说在一次执行travel的过程中电梯可能上楼也可能下楼。然而当时我在Elevator类的travel方法中是用两个独立的while判断上楼和下楼的，这样就会导致电梯无法顺利换向到达目的地。实际上应该写为外层while判断当前楼层是否与目标楼层相等，然后中间是两个if语句分别判断此时应该上楼还是下楼。
     *  #### 发现他人bug所采用的策略 ####
        
        由于自己过菜导致稳C。随机数据一刀穿，对拍器将在第三次作业中详细介绍。

--------------------

*  ### 第三次作业 ###
    
     *  #### 多线程的协同和同步控制 ####
        
        第三次作业是有容量限制和停靠楼层限制的三电梯ALS调度。
        
        如果不考虑刻意优化，容量限制很好解决，只需要判断当前人数已达上限时不再有人进入即可。
        
        对于各电梯停靠楼层不同，我的解决方法是将可达楼层存入数组中传入各电梯对象中，然后在运行过程中判断是否可停靠。
        
        本次作业的线程也与前两次一样。指导书中提示的最短路优化被我用在了换乘电梯的可达性判断上捂脸。
        
        还是两级生产消费者模型，还是熟悉的味道，只不过二级消费者变成了三只。
        
         *  **共享对象**
            
            这次的共享对象中请求队列是ArrayList<ArrayList<PersonRequest>>类型。即将每个请求拆分成几个阶段请求，其中每一个阶段请求均为起点终点一部电梯可达。
         *  **请求输入线程**
            
            负责轮循读入请求。
            
            每读入一个请求，首先通过最短路算法（BFS）将请求进行划分，然后就是和之前两次作业同样的，有新请求进入队列，唤醒电梯线程；输入结束，唤醒提醒电梯线程也快下班了。
         *  **电梯线程**
            
            三个电梯线程均沿用第二次作业的调度方式。
            
            其中在获取捎带请求时，对于那些有两部电梯均可承担运送任务的请求，考虑到容量限制，我的电梯不是将所有可捎带请求全部分配给同一部电梯，而是每一次获取一个请求，然后让电梯线程自己抢锁。
     *  #### 基于度量分析程序结构 ####
        
        本次作业比前两次作业多了一个计算最短路的抽象类DeliverStrategy类，然后请求输入类Requests继承了这个抽象类，并在读入每个请求的时候将其拆分。
        
        ![1615671-20190422215451522-1007296698.png][]
        
        **第三次作业类图**
        
        ![1615671-20190422215510457-1369192310.png][]
        
        **Method metrics**
        
        ![1615671-20190422215527231-1119412581.png][]
        
        **Class metrics**
        
        这次作业的电梯类似乎可以继承上次，但是由于细微差别要重写的方法有点多，所以就没有继承，而是进行了修改，违背了O原则。
     *  #### 分析程序bug ####
        
        在最初版本中，我的电梯又双双罢工了。
        
        经过胡乱的尝试和缜密的思考，最终它长成这个样子：
        
            // Elevator.java @Override public void run() { while ((devidedRequeset = controller.getMainRequest(reachableFloor)) != null) { mainRequest = devidedRequeset.get(0); destFloor = mainRequest.getFromFloor(); if (destFloor == curFloor) { // at the same floor destFloor = mainRequest.getToFloor(); dir = destFloor - curFloor; openDoor(); } dir = destFloor - curFloor; // travel(); } } // Controller.java public synchronized ArrayList<PersonRequest> getMainRequest(int[] reachableFloor) { // if (noWorkToDo(reachableFloor)) { return null; } ArrayList<PersonRequest> requests; while ((requests = getExistMainRequest(reachableFloor)) == null) { try { this.wait(); if (noWorkToDo(reachableFloor)) { return null; } } catch (InterruptedException e) { e.printStackTrace(); } } // System.out.println(Thread.currentThread().getName() + requests); return requests; }
        
        为了避免电梯换乘途中人在还没有经过第一阶段就已经被第二阶段顺道带走了，请求队列中的请求是只显示拆分后的第一个请求。这样就存在当前请求在队列其他电梯的队列中，但之后可能会再次进入请求队列，形成一个环形生产消费模型。如果还按之前的方法，当请求队列为空并且请求输入线程停止时电梯队列结束，那又会失踪人口了。
     *  #### 发现他人bug所采用的策略 ####
        
        由于码力过弱外加肝不好，每次只有第三次作业才有完整的对拍QAQ。在线求拍友联盟啊啊啊。
        
        鉴于评测机是在第二次的基础上暴力Ctrl+C Ctrl+V的，代码极丑，复用率极低，就不在这丢人现眼了，就大概讲一下对拍的流程。
        
        一共py了三次，分别是**MakeRequests.py用于随机生成数据**、**TimeController.py用于精准投放**、**Check.py丑爆评测机**。
        
            #!/bin/bash
            
            data_count=1
            run_count=1
            AC_count=1
            WORK_DIR=/home/charj99/homework_7
            
            while(true)
            do
                while(true)
                do
                    # make requesets
                    # input a number n, stands for totally make n requests
                    echo $1 | python $WORK_DIR/MakeRequests.py      
            
                    # check wether data is legal
                    # if legal, print 'datacheck passed'
                    # else, make requesets again
                    data_check=`$WORK_DIR/datacheck_ubuntu_py_3_5_2 -i $WORK_DIR/datacheck_in.txt | grep -c 'Check Pass!'`
                    if [[ $data_check == "1" ]]
                    then
                        echo datacheck $data_count passed!
                        echo 
                        break
                    fi
                done
            
                data_count=$[data_count+1]
            
            
                    cd $WORK_DIR/XJJ/src/
            
                    python $WORK_DIR/TimeController.py | java -cp $CLASSPATH:$WORK_DIR/lib/timable-output-1.1-raw-jar-with-dependencies.jar:$WORK_DIR/lib/elevator-input-hw3-1.4-jar-with-dependencies.jar Main | tee output.txt
            
                    result=`python $WORK_DIR/Check.py`
            
                    echo XJJ: $result
                    echo run $run_count times
                    run_count=$[run_count+1]
                    if [[ $result == "ACC" ]]
                    then
                        # print the last line of output.txt
                        # sed '/^$/!h;$!d;g' output.txt 
                        echo AC $AC_count times
                        AC_count=$[AC_count+1]
                        echo 
                    else
                        echo input: >> bugs.txt
                        cat $WORK_DIR/datacheck_in.txt >> bugs.txt
                        echo output: >> bugs.txt
                        cat output.txt >> bugs.txt
                        echo   >> bugs.txt
                    fi
            done

最后是本单元学习的心得体会了。

*  首先是**线程安全方面**。时常在同学面前开玩笑地自称锁王，其实还差的很远。说回正事，首先sychronize加的锁是加在对象上的，如果是锁方法，相当于锁了this对象。notifyAll()和wait()前一定要明确对象，即**对象.notifyAll**()和**对象.wait()**，并且对于某个对象的notifyAll()或wait()操作一定要在持有锁的情况下进行。对象.wait()是让当前获得该对象锁的线程wait，即本线程陷入阻塞；对象.notifyAll()是叫醒所有因为对象.wait()而陷入阻塞的线程，并且这些线程被唤醒后不会立刻执行，还是会通过争夺锁来微观上顺序执行。
    
    顺序锁可以解决死锁问题，与操作系统课上讲的不论程序需求什么资源，必须先争夺键盘，再争打印机等等，有异曲同工之妙。
    
    最后，没有什么是锁方法解决不了的，如果有，就锁上所有的方法（发出不要性能的声音）。
 *  然后是**设计原则方面**。发出SOLID大法好的声音（虽然还没有全部弄懂）。

转载于:https://www.cnblogs.com/weekends/p/10753348.html

[1615671-20190422215218256-1740745096.png]: /images/20211210/3d46a1ee63b64a48a71b8658bd0dce56.png
[1615671-20190422215240094-1416914934.png]: /images/20211210/b8c9bbb14a4147c6ac937d2f933f2deb.png
[1615671-20190422215302003-1443371603.png]: /images/20211210/8d8f24d1c09e49d7ab79f1f759ed14b5.png
[1615671-20190422215340878-1390202428.png]: /images/20211210/2afcc07816824140beaa8e101cc528ec.png
[1615671-20190422215407839-386732787.png]: /images/20211210/7bf764300eea4d8fad691439bc7349da.png
[1615671-20190422215426773-561493289.png]: /images/20211210/3183aaefbb1f4fb494184496b9c9eb01.png
[1615671-20190422215451522-1007296698.png]: /images/20211210/b9048e001a6a47b68d4c8e4aa5507a1b.png
[1615671-20190422215510457-1369192310.png]: /images/20211210/07b54d0effac4ddfa4bacc59d1bdc666.png
[1615671-20190422215527231-1119412581.png]: /images/20211210/ec4beb01b945406ebf877aac1200c259.png