OO-U2


OO第二单元电梯调度

0 前言

最近读到张嘉佳的《云边有个小卖部》,让我感到一种灵魂的无比契合。在这本书里看到了自己在电梯单元经历的巨大的失败,希望总是会在突如其来的强测和互测中逐渐暗淡。

作业简介

本次作业的目标是模拟多线程实时电梯系统,熟悉线程的创建、运行等基本操作,熟悉多线程程序的设计方法。同时对于电梯调度的运行时间和响应时间以及运行时的电量做了要求。

在这个快节奏的时代,多线程似乎已经成为了我们生活的常态。我们在同一时间处理多项任务,试图在复杂的信息洪流中寻找自己的节奏。正如面向对象设计与构造课程的第二单元所展示的那样,多线程编程不仅是一种技术挑战,更是一种思维方式的转变。

电梯,这个看似简单的日常工具,却成为了我们探索并发世界的舞台。在这个单元中,我们不仅仅是编写代码,我们是在设计一个个微型的社会系统,每个线程都是其中的一个成员,它们需要协同工作,却又独立运行,随时准备响应各种未知的请求。

我曾以为,电梯月将是一场激烈的头脑风暴,是一场与bug的殊死较量。然而,当真正身处其中,我却发现,这更像是是一场内心的修行。在每一次的锁与等待中,我学会了耐心;在每一次的死锁与轮询中,我学会了冷静。我开始理解,编程不仅仅是为了解决问题,更是为了在这个过程中,学会与问题共存,甚至是欣赏问题本身。

虽然我不再像U1时那样充满斗志,但这并不意味着我在退步。相反,我正在学习如何在复杂中寻找简单,在不确定中寻找确定。我正在学习如何在不完美的世界中,寻找属于自己的最优解。

电梯月过去了,留给我的是对多线程编程的深刻理解,以及对未来更多挑战的期待。我将继续在这个充满变数和可能性的领域探索,不断优化我的设计,提升我的技能。因为我知道,无论电梯如何上升下降,我的编程之旅,永远在路上。

本次作业主要是多线程设计以及其中生产者消费者模式的使用, 本次作业难度不低,一般来说完成一个项目的难度主要来自于架构设计和debug的难度,架构设计上对于共享对象的选择和设计是难点之一,不合理的共享对象设置会让后绪的代码更难写下去。debug的难度在于多线程的难以复现性。

1 架构设计体验心得

最终架构如下:

这里是代码的主要的几个共享对象。

  • RequestCounter:主要是为了解决可能出现的无法正确结束的问题。

    如果还是使用最开始的架构,比如当前输入已经结束,waitTable已经被设置为end,但是电梯有一个reset请求,需要将电梯中的人全部放出去。那么我这里的处理是将所有请求再次放到waitTable中,那么由于Dispatcher在得到waitTable的endFlag后,会给每个dispatchTable设置为end后然后结束run(),那么reset出来的那些请求就无法得到正确处理。

    于是这里可以添加一个RequesetCounter来计算当前未完成的请求数,当请求数为0而且waitTable已经end时,Dispatcher就可以结束run()

  • RequestTable:这个是请求的容器。其中包括两个小的List,分别是PersonRequestTableResetRequestTablePersonRequestTable是用来存放PersonRequest的,ResetRequestTable是用来存放ResetRequest的。

这里主要是两个策略类:

  • 一个是电梯分派策略。这里使用的调参策略
  • 一个是电梯运行策略。这里使用的是Look策略。

这里是几个主要的进程:

  • 输入进程
  • 调度器进程
  • 电梯进程

这三个进程形成了两个生产者和消费者模式,其中的Dispathcer是一个中间商。

  • 整体上是两个生产者消费者模式:

    一个是InputHandler作为生产者,Dispatcher作为消费者。其共享容器为waitTable

    另一个是Dispatcher作为生产者,Elevator作为消费者。其共享容器为dispatchTable

  • 同时这两种生产者消费者模式也构成一种层次化结构。

  • 从代码架构的角度,我这里用到了DispatchStrategyRunStrategy两个接口。分别用于实现电梯分派策略和电梯运行策略。

    这里的分派策略在尝试过程中用到了random策略,调参策略,random+调参的策略。最终用到的是调参策略。

    电梯运行策略用到的直接就是使用Look策略。Look策略在实际运行中表现良好,能够有效的减少电梯的运行时间。同时在工程中也有很高的使用率,可见Look策略在的实现的简单性和效果性达到了一个很好的平衡,是一个很好的选择。

1.1 第一次作业架构

第一次作业不需要进行电梯调度,已经指定了是哪个电梯,因此只需要对于电梯的运行进行处理。这里还是直接使用的简单的Look策略,没有使用过多的优化。

1.2 第二次作业架构

这一次作业架构应该是最复杂的一次,我尝试实现了使用影子电梯电梯调度策略和random策略,分别作为两个类来实现了DispatchStrategy接口,然而影子电梯策略由于实现的问题,出现了一些难以解决的bug,于是放弃了(x

同时这里尝试实现了量子电梯,我发现在我的实现中,量子电梯没有什么优化,为了简洁性(主要是因为有其他bug,没有将处理中心放在这里,最终还是没有使用这个量子电梯。

2 同步块和锁

对于共享对象,我们可以通过设置同步块来是的这个共享对象是一个线程安全的类。比如我的两个共享对象RequestCounterRequestTable

以下是两个简单的代码示例。

public class RequestCounter {
    private int count = 0;

    public synchronized void add() {
        count++;
        notifyAll();
    }

    public synchronized void sub() {
        count--;
        notifyAll();
    }

    public synchronized int get() {
        notifyAll();
        return count;
    }
}
public class RequestTable {
    private List<PersonRequest> personRequestTable;
    private List<ResetRequest> resetRequestTable;

    public RequestTable() {
        personRequestTable = new ArrayList<>();
        resetRequestTable = new ArrayList<>();
    }

    public synchronized void addPersonRequest(PersonRequest personRequest) {
        personRequestTable.add(personRequest);
    }

    public synchronized void addResetRequest(ResetRequest resetRequest) {
        notifyAll();
        resetRequestTable.add(resetRequest);
    }

    public synchronized PersonRequest getPersonRequest() {
        notifyAll();
        return personRequestTable.remove(0);
    }

    public synchronized ResetRequest getResetRequest() {
        notifyAll();
        return resetRequestTable.remove(0);
    }
}

这样基本上可以确保一个线程安全。但是还是并不是说所有的共享对象就是无脑加锁就可以w完全确保线程安全的。还需要分析这几个方法的逻辑,是否会出行啊死锁的情况,同时也要分析这个共享对象的使用情况,是否会出现并发问题。

当然考虑实现的优雅性,我们可以使用ReentrantLock来实现锁。

以下是一个简单的代码示例。

public class RequestCounter {
    private int count = 0;
    private final Lock lock = new ReentrantLock();
    private final Condition condition = lock.newCondition();

    public void add() {
        lock.lock();
        try {
            count++;
            condition.signalAll();
        } finally {
            lock.unlock();
        }
    }

    public void sub() {
        lock.lock();
        try {
            count--;
            condition.signalAll();
        } finally {
            lock.unlock();
        }
    }

    public int get() {
        lock.lock();
        try {
            condition.signalAll();
            return count;
        } finally {
            lock.unlock();
        }
    }
}

当然也可以选择设置读写锁来提高效率。

public class RequestCounter {
    private int count = 0;
    private final ReadWriteLock lock = new ReentrantReadWriteLock();
    private final Lock readLock = lock.readLock();
    private final Lock writeLock = lock.writeLock();

    public void add() {
        writeLock.lock();
        try {
            count++;
        } finally {
            writeLock.unlock();
        }
    }

    public void sub() {
        writeLock.lock();
        try {
            count--;
        } finally {
            writeLock.unlock();
        }
    }

    public int get() {
        readLock.lock();
        try {
            return count;
        } finally {
            readLock.unlock();
        }
    }
}

同时在这里还可以使用Condition来实现更加复杂的同步。

public class RequestCounter {
    private int count = 0;
    private final Lock lock = new ReentrantLock();
    private final Condition condition = lock.newCondition();

    public void add() {
        lock.lock();
        try {
            count++;
            condition.signalAll();
        } finally {
            lock.unlock();
        }
    }

    public void sub() {
        lock.lock();
        try {
            count--;
            condition.signalAll();
        } finally {
            lock.unlock();
        }
    }

    public int get() {
        lock.lock();
        try {
            condition.signalAll();
            return count;
        } finally {
            lock.unlock();
        }
    }

    public void await() throws InterruptedException {
        lock.lock();
        try {
            condition.await();
        } finally {
            lock.unlock();
        }
    }
}

实际上这些锁的实现在实际测试发现效率其实差不多,(无脑synchronized哈哈哈)

另一方面,除了对于共享对象的同步中可以使用锁来确保外界的访问是线程安全的,在对两个线程进行通信的时候可以手动设置一个Lock类来确保线程的通信是线程安全的。比如在实现双轿厢电梯时就可以使用这么一个锁。

public class Lock {
    private boolean lock;

    public Lock() {
        this.lock = false;
    }

    public synchronized void lock() {
        while (lock) {
            try {
                wait();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        lock = true;
    }

    public synchronized void unlock() {
        lock = false;
        notifyAll();
    }

    public synchronized boolean isLock() {
        return lock;
    }
}

3 线程与对象设计

3.1 线程协同性

今天听戚发韧院士的讲座,讲到了一起协同努力,推动中国航天进步!!!

首先是主线程启动其余几个线程,这里是InputHandlerDispatcher 以及Elevator

InputHandler中,主要是读取输入,然后将输入放到waitTable中。同时会在最后将waitTable设置为end

在调度器Dispatcher中,主要是从waitTable中取出请求,然后根据策略分派给电梯。同时会在最后将dispatchTable设置为end。如果waitTable为空那么就等待,如果waitTable已经end了,而且requestCounter也end,那么才设置为结束run()

在电梯Elevator中,主要是从dispatchTable中取出请求,然后根据策略运行电梯。这里用到的是Look策略,这里用到一个RunStrategy类,每次从RunStrategy得到一个Advice,电梯根据Advice进行相应的操作。

3.2 代码稳定性与易变形分析

在三次作业中,主要变化的内容其实都在Elevator类中,电梯每次增加一种行为,电梯里面就要去实现这种操作。同时也需要添加更多的属性来完成这些请求。比如最开始我们设置minFloormaxFloor,因为这个是固定的,但是由于双轿厢电梯的出现使得我需要对这个进行调整,同时Look策略中也需要进行调整。

还有一个就是共享对象需要不断调整,比如在第三次作业中,我增加了RequestCounter来解决可能出现的无法正确结束的问题。同时还有RequestTable中需要添加不同的请求来进行处理。虽然可以使用更加合适的继承来处理,但是我总认为在外层使用instanceof来判断是不是这个类型是一种不太好的设计,所以我尽量避免使用这个方法,而是使用了两个List来存放不同的请求。当然也可以自己将request中的内容实现一下,使得更加符合自己的需求。

同时这里巧妙的实现接口,使得可以方便尝试不同的调度策略和运行策略。这也是之后代码主要可以修改和优化的地方。但是苦于自己时间优先,在优先尝试相对简单的策略后,其他策略并没有进行尝试了。或者有一些尝试了但是半途而废了。

3.3 处理双轿厢电梯

我直接一开始就是实现12个电梯,然后只需要在调度时设置如果一个电梯不是双轿厢而且$id \ge 7$那么就不会分配给这个电梯。这样解决了双轿厢电梯调度的问题。

对于具体运行时,通过设置maxFloorminFloor可以解决运行的问题。

但是对于双轿厢电梯碰撞的问题,我们可以增加一个Lock的共享对象,通过这个共享对象的状态设置来告诉对方该电梯是否在换乘层,进行相应的wait操作。同时,对于每个电梯,在换乘层完成开门操作后,马上移动到换乘层旁边的一层,避免出现某一个电梯一直占据着换乘层,而另一个电梯一直在wait的情况。

4 bug分析

bug这东西分析分析就行了,de不出来的😢

4.1 print大法

首先是打印中间变量的方法:

我写了一个Print的类,专门用来打印中间变量。

import com.oocourse.elevator3.PersonRequest;
import com.oocourse.elevator3.TimableOutput;

public class Print {
    private static boolean DEBUG = true;

    public static void printElse(Object obj) {
        if (DEBUG) {
            System.out.println(obj);
        }
    }

    public static void printAns(Object obj, Object obj2) {

        if (DEBUG) {
            if (obj2 instanceof Integer) {
                if ((int) obj2 != 0) {
                    TimableOutput.println(obj);
                }
            } else if (obj2 instanceof PersonRequest) {
                TimableOutput.println(obj);
            }
        } else {
            TimableOutput.println(obj);
        }
    }

    public static void printAns(Object obj) {
        TimableOutput.println(obj);
    }
}

对于正常的选择调用Print.printAns()即可,当我们需要debug时将DEBUG设置为true即可。

4.2 断点

虽然断点在多线程中不太合适,但是对于一些RTLE的bug还是很好的。

我觉得可能是在debug模式的时候,我们知道idea会自动调用对象的toString()方法,说明开启了别的线程进行操作,那么就更加方便的复现评测机上由于有多个java线程而出现RTLE的概率大大提高的现象了。

相对更加容易复现

而且也能够知道RTLE时各个线程wait在哪里了

断点的策略性使用:在多线程编程中,我学会了如何策略性地使用断点。尤其是在分析复杂逻辑或追踪特定线程的行为时,合理地设置断点可以帮助我快速定位问题。

  • 输出日志的巧妙应用:我经常使用System.out.println()来输出关键信息,这不仅帮助我理解程序的运行流程,还能够在不干扰多线程执行的前提下,定位问题所在。通过输出日志,我能够实时监控程序的状态和线程的交互。
  • 自动化测试的充分利用:为了确保代码的健壮性,我充分利用评测机的自动化测试功能。自动化测试不仅帮助我发现错误,还能够确保我的修复是有效的,并且能够在不同的场景下验证程序的正确性。
  • 代码审查的互助合作:与同学一起进行代码审查是非常有效的debug方法。通过互相审查代码,我们能够互相发现潜在的问题,并提供改进的建议。这种合作学习的方式不仅能够提高代码质量,还能够加深对多线程编程的理解。
  • 锁的可视化分析:可以使用jdk自带的分析工具jvisualvm等进行分析。尤其是死锁基本上都能分析出来。
  • 边界条件的充分考虑:在多线程编程中,我学会了不仅要考虑常规情况,还要特别关注边界条件和异常情况。通过充分测试边界条件,我能够发现并修复潜在的问题,提高程序的稳定性和正确性。

4.3 我咋就这么多bug😢

首先是线程安全,由于一些共享对象的设置,动不动就叫不醒了。

后来是通过将PersonRequestTableResetRequestTable两个类合并为一个类才处理好。然后RequestCounter由于有三类线程对其进行操作,出现的问题大大增加。

然后是出现6个reset时会出现问题,睡一睡就好了。

还有巨大的hack数据,分配是因为调参不够全面,全都塞到一个电梯去了,添加几个参数就可以了。

还有CTLE问题,检查每个while(true)都还不知道为什么的话,睡一睡就好了。睡了也不行,那就多多print,看到底是哪里搁那轮询。当然也可以开启debug模式,看停在哪里。

至于更多的问题,能跑就行。

如果还有问题,那就好办,要么退学要么退休。

5 心得体会

面向对象设计与构造课程的第二单元,是一次深入多线程编程的探险。在这个过程中,我深刻体会到了线程安全和层次化设计的重要性,也在实践中逐渐领悟了如何在复杂的多线程环境中构建稳健的软件系统。

在三次作业的磨砺中,我意识到线程安全是构建可靠多线程程序的基础。我学会了在适当的时机使用锁,保护临界区,确保数据的一致性。同时,我也认识到了过度锁定的危害,它可能导致死锁或者降低程序的性能。因此,我学会了在设计时考虑每个模块的职责,通过合理的抽象和封装,减少共享数据,从而降低线程间的耦合,提高系统的可靠性。

层次化设计在这个单元中显得尤为重要。我学会了如何将复杂的系统分解为多个层次,每个层次都有明确的职责和接口。这样的设计不仅使得代码更加清晰,也便于单元测试和维护。在层次化设计中,我还学会了如何处理层次间的数据流动,如何通过方法调用和数据传递,实现层次间的协作。

在实践中,我也遇到了许多挑战。多线程程序的不可预测性让我在调试时倍感困扰。有时,一个看似微小的改动,就会导致程序的行为大变。这让我深刻理解了多线程环境下测试的重要性。我学会了使用各种工具和技术,如日志记录、断言和单元测试,来确保程序的稳定性和正确性。

虽然这一单元的学习过程充满了艰辛,但我认为这是非常宝贵的经验。我不仅掌握了多线程编程的技术,更重要的是,我学会了如何在面对复杂问题时,保持冷静和系统性的思考。我相信,这些经验和技能将对我未来的职业生涯产生深远的影响。

最后,我要感谢所有在这一单元中给予我帮助的人。感谢那些无私分享经验的学长学姐,感谢那些一起讨论问题的同学,感谢那些在讨论区中提供宝贵意见的网友们,还要感谢助教和课程团队的支持和指导。正是因为有了你们,我才能在这一单元中学到如此之多。

总结这一单元的学习,我深感自己在线程安全和层次化设计方面有了质的飞跃。虽然前方的路还很长,但我相信,只要我继续努力,不断学习和实践,我一定能够在面向对象设计与构造的道路上走得更远。

还是加点碎碎念。

看到很多朋友说自己天赋不在代码上,害,哥们又何尝不是呢。看到很多同学说,为了这个OO熬了很多夜,害,我可不觉得整个六系还有谁比我熬夜更多,肝得越多肝越少。害,最终成绩还烂的一批,凭心而论,习惯了就好了。

唉,什么时候才能长大


文章作者: hugo
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 hugo !
  目录