buaaoo_second_assignment

 远瞧忽忽悠悠,近瞧飘飘摇摇,走近点留神看,原来是,电梯被测爆


(一)基于多线程的设计分析

  (1)傻瓜电梯

    第一次电梯本来想用多线程去写,但是当时对于线程的理解还不够充分(甚至把人当成了线程去找电梯,然后写的焦头烂额),最后成功的改成了单线程傻瓜电梯,一次就送一个人,也就是FAFS,写起来也十分的简单,所以觉得并没有什么分析的必要。

  (2)LOOK电梯

    显然第二次电梯直接用傻瓜会被测成傻瓜,于是在比较了指导书推荐的ALS和网上有的优化电梯来看,最后选择了最容易书写,性能也还可以的LOOK电梯(确实有想过优化,这里暂且不提)。

    在LOOK电梯书写部分,我采用了将调度器与电梯extends为Thread来做,这是一种比较中规中矩的办法,通过采用一个共享队列来存储数据,然后一个个放到电梯里就行(不用考虑容量的话确实很舒服)。这里值得一提的是,在书写程序的时候最好并称高内聚,低耦合的设计思路来写,而且一定要避免采用硬编码,同时把每个类的作用梳理清楚,不要把功能过多的掺杂在一起。比如说,在我的Main类中,仅包含了线程的初始化以及启动,余下的分派给其它的类来做。同时我设了一个Person类,用来存储PersonRequest(在第二次作业中其实并无必要,但是秉承着要解耦的原则,我就没有直接用PersonRequest,而这样的设计在第三次电梯中有了很大的优势,甚至可以两个小时左右就把第二次修改成第三次)。

    还有一个问题是,线程应该什么时候结束,由于我把调度器和输入放在了一起,所以最开始的时候,输入结束会直接导致我的调度结束,也就是会有部分乘客的请求无法得到满足,所以我通过一个容器来存储是否完成:

            if (request == null) {
                try {
                    synchronized (arr) {
                        arr.notify();
                    }
                    judge.add("done");
                    elevatorInput.close();
                }
                catch (Exception e) {
                    e.printStackTrace();
                }
                break;
            }

    也就是上面的那个judge,这里是不能只通过共享字符串或者整型等数据格式来判断的,应该是和java的数据存储机制有关。

    而电梯也是需要通过judge的状态以及存储队列中人员是否全部送达才可以判断是否需要停止的,代码如下:

            if (!judge.isEmpty()) {
                if (judge.get(0).equals("done")) {
                    count = 0;
                    for (Person p : arr) {
                        if (p.getstatus() == 2) {
                            count++;
                        }
                    }
                    if (count == arr.size()) {
                        break;
                    }
                }
            }

    显然,本次作业通过将方法分别分配给所需要线程,可以很大程度上解耦,比如,Person类中有进电梯出电梯的方法,Elevator有电梯上下移动的方法,判断是否需要转向的方法等,之后通过共享队列的分发,在每个线程中使用synchronized,以保证线程安全,便可以很容易的书写完毕,并且很方便继承到第三次作业当中去。

  (3)层数、人数限制的三电梯

    可以说到了这次作业,才能逐渐体会到多线程具体应该是怎么样操作的了,经过继承第二次电梯,第三次电梯我也采用的是LOOK算法,只不过比之前多开了两个电梯线程,又加入了换乘调度器线程。具体思路是这样的,由于有层数限制,所以通过数组存储ABC电梯分别可以停靠的楼层,通过数组下标表示楼层,存1表示可以停靠,存0表示不能停靠,可以大大简化判断楼层的繁琐。之后对于人数限制,我仅仅在之前所写的电梯类中,加入了max做标记,如果超过了,便无法再进入电梯(这里有一个小技巧,也是遵循现实来的,就是先下后上好公德:),事实证明,有的电梯如果不首先下,有可能会因为满员停靠,先上后下而爆炸)。最后是换乘问题,之所以通过一个换乘调度器来解决这个问题,是因为放到输入线程或者电梯线程中,不光代码书写十分麻烦,耦合也严重,给这两个线程增多了不属于他们的操作。同样的,这次我用了五个队列,三个电梯每个电梯一个队列存放乘客请求,直接通过输入的调度器分别判断哪个乘客在哪个电梯可以直达,然后放进去,如果不能直达,就存入可以进入的电梯队列。之后通过一个change队列代表换乘,在Person类中设置标记为记录乘客是否需要换乘。在前半部分把乘客分别送到一楼或者十五楼(通过判断电梯运动距离来存放),之后存入change队列,由换成调度器判断可以放入哪个电梯。最后是一个total队列,其功效为判断是否需要停止,停止的条件为,total队列中所有请求都已经完成,并且输入已经结束。

    最开始写第三次电梯的时候,使用synchronized嵌套写出了死锁,这里记录一下,代码如下: 

        synchronized (arr1) {
                synchronized (change) {
                    Iterator<Person> iterator = change.iterator();
                    while (iterator.hasNext()) {
                        Person p = iterator.next();
                        if (elevator1[p.getfrom() + 3] == 1
                                && elevator1[p.getto() + 3] == 1 && arr1.size() < 10) {
                            if (p.getstatus() != 1 && p.getstatus() != 2) {
                                arr1.add(p);
                                iterator.remove();
                            }
                        }
                    }
                }
            }
            synchronized (arr2) {
                synchronized (change) {
                    Iterator<Person> iterator = change.iterator();
                    while (iterator.hasNext()) {
                        Person p = iterator.next();
                        if (elevator2[p.getfrom() + 3] == 1
                                && elevator2[p.getto() + 3] == 1 && arr2.size() < 12) {
                            if (p.getstatus() != 1 && p.getstatus() != 2) {
                                arr2.add(p);
                                iterator.remove();
                            }
                        }
                    }
                }
            }
            synchronized (arr3) {
                synchronized (change) {
                    Iterator<Person> iterator = change.iterator();
                    while (iterator.hasNext()) {
                        Person p = iterator.next();
                        if (elevator3[p.getfrom() + 3] == 1
                                && elevator3[p.getto() + 3] == 1 && arr3.size() < 11) {
                            if (p.getstatus() != 1 && p.getstatus() != 2) {
                                arr3.add(p);
                                iterator.remove();
                            }
                        }
                    }
                }
            }    

     这段代码是在换乘调度器中,将已经完成前半部分运送的乘客请求送入后半部分,但之前我是通过一整个的synchronized(change)嵌套在外面,里面是分别三个电梯的队列,但在电梯的代码中:

            synchronized (arr) {
                flag = 0;
                for (Person p : arr) {
                    if (p.getto() == nowfloor && p.getstatus() == 1) {
                        open();
                        flag = 1;
                        break;
                    }
                }
                if (flag == 0 && passanger < max) {
                    for (Person p : arr) {
                        if (p.getfrom() == nowfloor && p.getstatus() == 0) {
                            open();
                            flag = 1;
                            break;
                        }
                    }
                }
                if (flag == 1) {
                    Iterator<Person> iter = arr.iterator();
                    while (iter.hasNext()) {
                        Person item = iter.next();
                        if (item.getto() == nowfloor && item.getstatus() == 1) {
                            TimableOutput.println(item.getout() + "-" + id);
                            passanger--;
                            if (item.getchange() == 1) {
                                synchronized (total) {
                                    item.changelevator();
                                    item.changefloor();
                                }
                                synchronized (change) {
                                    change.add(item);
                                }
                            }
                            iter.remove();
                        }
                    }
                    for (Person p : arr) {
                        if (p.getfrom() == nowfloor && p.getstatus() == 0
                                && passanger < max) {
                            TimableOutput.println(p.getin() + "-" + id);
                            passanger++;
                            if (passanger == max) {
                                break;
                            }
                        }
                    }
                    close();
                }
                detect();
            }
            wheretogo();

    可以看到我是通过锁住每个电梯队列的请求,之后在里面判断是否完成前半部分换乘的,所以会和第四次上机的题目一样,出现死锁,具体原因就是当电梯获取了arr锁的时候,换乘调度器获取了change锁,然后形成了互相等待对方释放的局面,而这里又无法通过使用wait(),notify()语句来解锁,所以我将换乘调度器中的锁的嵌套换了个顺序,之后就是线程安全的啦。

(二)基于度量的程序结构分析

  (1)傻瓜电梯

    UML类图: 

 buaaoo_second_assignment

    复杂度分析:

      buaaoo_second_assignment

      buaaoo_second_assignment

    可以看出第一次电梯由于使用了单线程的缘故,并没有特别值得分析的地方,类也十分的少,之间的依赖也不是很多。

  (2)LOOK电梯

    UML类图:

buaaoo_second_assignment

    复杂度分析:

      buaaoo_second_assignment

      buaaoo_second_assignment

    此次作业中,电梯与调度器均是线程,两者之间通过一个arraylist来进行通信,可以很好的完成所需要的功能,并且每一个类只负责自己需要负责的部分,耦合度比较低,对于每个类的内部功能,也都有层次的分成各种方法,可以说本次设计还是比较成功的。

    SRP:

      每个类或者方法只有一个明确的职责,通过类图的分析可以得知,这个原则实现还是比较完善的。

    OCP:

      由于我的第三次作业是完全继承下来第二次作业,仅做了少量修改,所以说这个原则实现也比较完善。

    LSP:

      除了extends Thread的run()方法,其余地方并没有使用继承,所以这个原则体现并不明显。

    ISP:

      并没有使用接口,所以这个原则体现并不明显。

    DIP:

      类与类之间的依赖比较简单,所以这个原则体现并不明显。

  (3)层数、人数限制的三电梯

    UML类图:     buaaoo_second_assignment

    复杂度分析:

      buaaoo_second_assignment

      buaaoo_second_assignment

    此次电梯的设计完全继承第二次电梯,可以直观的从类图中看出与第二次的相似之处,实现方法比较中规中矩,没有使用特别多的优化,调度也使用的是傻瓜调度,我个人觉得唯一的优点就是对于各个类的职责分工十分明确,较好的完成了高内聚低耦合的设计要求。

    SRP:

      每个类或者方法只有一个明确的职责,通过类图的分析可以得知,这个原则实现还是比较完善的。

    OCP:

      由于我的第三次作业是完全继承下来第二次作业,仅做了少量修改,所以说这个原则实现也比较完善。

    LSP:

      除了extends Thread的run()方法,其余地方并没有使用继承,所以这个原则体现并不明显。

    ISP:

      并没有使用接口,所以这个原则体现并不明显。

    DIP:

      类与类之间的依赖比较简单,所以这个原则体现并不明显。

 (三)基于bug的程序分析

  (1)傻瓜电梯

    我最后改成了单线程实现此电梯,就是为了防止某些愚蠢的bug,不过最开始的时候,使用人、输入、电梯同时作为线程来写,发现逻辑很复杂,最后放弃了,现在想想,如果只把输入和电梯作为线程,实现起来比较简单也不容易错。

  (2)LOOK电梯

    这个电梯我在实现的时候确实有bug,就是使用了LOOK电梯算法,是基于SCAN算法的改进,即如果运动方向上没有多余请求,则改变方向。但我最开始书写的时候,把判断的条件漏写了,导致了我的电梯如果向下行驶,上方来了新的请求会直接返回上方,导致重复运动,性能分归零。所以仅需要在判断上下的时候,加入当前方向的判断即可很好的解决这个bug。这个bug是与线程无关的,仅仅是在电梯的运动上出现了错误,所以很容易改。

  (3)层数、人数限制的三电梯

    本次电梯由于发现了第二次电梯的bug,所以写起来十分的舒服,仅仅花了两个多小时就完成了(不过愚蠢的我忘记修改输出格式,交上去全WA)。虽然自己的电梯在线程安全上并不会出现问题,也没有其它运动的bug,但是确实因为没有优化好,而失去了比较多的性能分,之后还应该考虑如何去优化,这里暂且不提。

(四)基于互测的程序分析

  (1)傻瓜电梯

    并没有发现bug

  (2)LOOK电梯

    自己写了一个对拍器,周四晚上才开始写,刚交了一个就截止了,十分难过了.......不过找bug的过程就是在写对拍器的时候可以体现出来。仅仅需要另一个程序模拟电梯正确运行方式,然后用命令行抓取互测同学的输出即可。读代码的话,比较容易出现bug的部分就是电梯的run中,判断电梯运动部分,重点查看这里,就比较容易发现bug。不过这里比较值得一提的是,某三电梯截流输出法的电梯真的惊到我了,我第二次作业只写了二百行,而那个神仙的有一千五百多行,这大概就是我菜的原因了吧。

  (3)层数、人数限制的三电梯

    由于比较懒,并没有再写对拍器,阅读也并没有读出同组同学的bug,想了一下原因,大概是本次作业大家都是继承的第二次电梯的思路,所以对于电梯的设计上bug的几率减少很多,而只需要在调度器中增加功能,比较难写出bug,而且此次时间限制十分宽泛(甚至以为三个傻瓜电梯都能跑),所以也就没有仔细去读。

(五)心得体会

  说实话,上一单元的表达式求导,疯狂使用面向过程的方法去写OO,体验十分不好,虽然容易debug,但是感觉和这个课的内容有很大的偏差。而此次电梯作业,一脉相承的使用了自己的代码,不光更好的体验到了OO的好处,同时也明白了多线程程序应该如何去写,如何保证线程安全,在研讨课上,各位大佬对于锁的讲解也让人耳目一新。我在设计的时候,其实是很偷懒的,说是牺牲性能的正确性保护法也不为过,锁只用了synchronized,简单粗暴,但是性能不好,听了大佬讲的读写锁,重入锁等,还需要进行进一步的研究,以此来增强自己对多线程的线程安全问题的理解。

  这次的观感与上一单元相比有了很大提升,不再硬编码,而是有逻辑的设计类与类的关系,方法与方法的关系,也从这样的设计中得到了很大的好处,节省了进阶作业的很多时间。总之,通过这单元的电梯作业,我才觉得自己在OO方面摸到了一些门路。


要我说,压力其实也没那么大.jpg

上一篇:FIT2076 Assignment


下一篇:SIT292 ASSIGNMENT