• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

OO 第二单元总结

第二单元的任务是设计电梯调度方案,要求我们设计调度方式,在相对较短的时间内将乘客送到目的地。应用多线程的主要知识,包括多线程中的同步和互斥,避免死锁。了解线程如何相互通信以及如何保持通信安全,已经完成了本单元的大部分任务。

第一次作业

作业思路

我认为第一个作业是三个作业中最难的。第一次用多线程编程,需要选择一个合适的模式。参考课程的计算机内容,选择生产者-消费者模型。根据老师理论课的介绍,这种模型可以解决大部分工业问题,可见其优势。

在第一次分配中,添加了调度类计划。这部分在第一次分配中并没有起到明显的作用,而是按照楼层来分配乘客。关键类是客户队列和电梯。CustomerQueue类是生产者和消费者的集中表达,其中使用notifyAll和wait进行通信。电梯是运送乘客的核心类,判断什么时候加入乘客,什么时候释放乘客。通过分离这三个类,程序的策略更具可扩展性。无论应用什么策略,电梯部分的产出都是符合股票规律的。策略主要有ALS、LOOK等算法,每种算法都有自己的优势类型,可以进一步优化以获得更高的性能。

类说明

|- Mainclass:主类

|-schedule:Scheduler,它对读取的乘客请求进行分类,并将它们添加到相应的等待队列中。

|- InputThread:读入线程,负责从控制台读取请求,并将乘客加入等待队列。

|- Elevator: elevator线程是一个消费者角色,从等待队列中获取请求进行处理。

|- PeopleOn:电梯乘客集合并管理电梯上的人员。

|-客户:乘客级别

|- CustomerQueue: Waiting queue线程,负责管理不上电梯的人,是一个关键类。

多线程设计

这个作业中有三个线程,InputThread、Shedule和Elevator。这三个线程共享一个线程安全对象CustomerQueue。客户是这个工作中唯一锁定的类,也是生产者-消费者模型的关键部分。这个类的主要功能是从输入中读取乘客请求,并将其添加到等待队列中。同时提供电梯接送乘客,是一个线程安全的类。

当没有请求时,每个线程进入等待状态,当有请求加入时,notifyAll唤醒这些线程。在电梯内部,执行Thread.sleep来模拟电梯的开关门和升降楼层。在此期间,乘客会加入进来。这种方式容易控制和理解,不关门也不会出现上下车乘客的问题。同时也容易扩大后续电梯停站时间变更的问题。

调度器设计

第一个作业由schedule类调度,这次主要是根据不同乘客的出发楼层来分配乘客请求,分配到各个楼层电梯对应的请求队列中。的实现相对简单,但这部分是为了后续工作的展开而添加的。

调度策略

已选择LOOK算法来调度此作业。首先,电梯里的乘客被运送到目的地。如果在运行过程中有同方向的请求,将会接载乘客。电梯空了之后,继续搜索同方向是否有乘客请求。如果有,继续往这个方向跑,否则,换个方向。LOOK算法没有“先到先得”的规则,只是根据电梯状态和乘客要求进行调度,更符合正常的思维模式。

类图与时序图

i0ykvwkze4a4869.jpg

40237-1197910593.jpg" width="370"/>

 

 

第二次作业

作业思路

在大体框架上第二次作业相对于第一次作业没有很大的变化,仍然采用的是生产者消费者模式,在调度器部分,仍然是判断乘客做横向电梯还是竖向电梯,将其分配到相对应的电梯等待队列之中。但第二次又存在每一层有多个电梯的情况,这里的分配策略就是那个等待队列人少就将乘客加入其中。

采用的调度策略仍然是LOOK算法,改变在于增加了横向电梯的类,横向电梯的类与竖向电梯类似,只是在应用LOOK算法时要考虑循环的情况,”最高层“是根据当前楼层改变的,实现的时候要小心考虑,否则会出现死循环的问题,这一部分在Bug分析部分进一步详述。

调度器设计

这一部分与第一次作业相类似,唯一改变的是调度策略。

调度策略
这次作业实现的是每一个电梯都对应一个等待队列。在分配时,同一层或者同一栋中哪一个队列中的人少就将新的乘客加入其中。这样实现相对来说能够让每一个电梯都处于运作状态,更加充分的运用了资源。

在设计的时候,也考虑过应用自由竞争的策略,但是遇到了CPU的tle问题。当时没能够发现问题的原因,就为采用这一中方式。后来明白是不适当的加入了notifyAll导致出现轮询问题。但从评测来看,这两种方法的性能没有相差很多。

类图与时序图

skjbdw2tz444870.jpg

 

k1zpovdukgb4871.jpg

 

第三次作业

作业思路

本次作业结构仍没有很大的改动,只是在Shedule类中加入了一个容器存储所有的横向电梯,以便在调度的时候确定要中转选择的横向电梯。在增加横向电梯时要对这里进行处理。

同时在每个乘客类内部加入三组记录起始地址的变量,前两次都只是记录起始的和终止的,这一次加入中间状态。在Shedule进行乘客请求分配的时候,根据乘客的需求即是否需要换成将中间状态的两个变量进行赋值,LOOK算法进行分析时变为分析起始状态和中间状态。当一个乘客从电梯下来时,将其起始状态更改为当前位置对应的数值,判断这时起始和终止的状态是否相同,如果不相同将这个乘客继续加入到CustomerQueue等待队列进行继续的处理,直至这个乘客处理完成。

调度策略

总体的调度策略仍然是将乘客进行分配,对于需要换成的乘客,分析每一层的横向电梯,如果存在可以到达的电梯,就将乘客在这一层进行换乘。但这里我犯了一个大错误,就是对于换成,在分析哪一座楼层可以到达横向的目的时,考虑了每一个电梯能够到达的楼座。但是在将乘客加入横向电梯的时候,却没考虑这一点。如果一层横向电梯有两个,一个可到达,另一个不可,此时就会出现问题。

类图与时序图

jr4m2wwd2nc4872.jpg

 

25n5olq0zs44873.jpg

 

 

BUG分析

第二次作业

强测时没有发现问题,但是在互测是被hack,问题在应用LOOK算法的时候,没有考虑到底层是在时刻改变的,比如在此时电梯在E,但是在D,B,A,都有请求的时候,就出现了循环问题,因为电梯在D坐又要到B坐,然后又到A,如循环,导致超时。解决很简单,在LOOK判断加入一点判断即可。

第三次作业

如上所说,虽然在换成判断横向电梯的时候考虑了横向电梯呢能否到达的问题,但是在将乘客加入到横向电梯的时候,却没考虑这个横向电梯能否到达,出现问题,只需要在横向电梯加入乘客时候进行判断即可。

互测BUG分析

如下是一些自己构造的查找BUG的数据,每一次都能够有所收获。

判断电梯调度是否正确:

ADD-floor-10-3-4-0.6-18
ADD-floor-11-3-4-0.6-31
ADD-floor-13-3-4-0.6-24
1-FROM-B-5-TO-E-7
2-FROM-B-5-TO-E-7
3-FROM-B-5-TO-E-7
4-FROM-B-5-TO-E-7
5-FROM-B-5-TO-E-7
6-FROM-B-5-TO-E-7

判断电梯是否超载:

ADD-floor-10-3-4-0.6-18
1-FROM-B-5-TO-E-7
2-FROM-B-5-TO-E-7
3-FROM-B-5-TO-E-7
4-FROM-B-5-TO-E-7
5-FROM-B-5-TO-E-7
6-FROM-B-5-TO-E-7
7-FROM-B-5-TO-E-7
8-FROM-B-5-TO-E-7
9-FROM-B-5-TO-E-7

对于线程锁的一些理解

多线程很关键的一步就在于进行同步,这一单元的作业里主要是应用synchronized这一关键字,以下是一些我对锁的总结。

方法锁

这一部分里synchronized修饰类里面的方法,相当于锁这个类即this

public synchronized void method() {
}
代码块形式

如下的obj可以是类里面的某一变量或者是容器,锁住这个变量,以便不同线程间都能得到这个变量的最新值。

synchronized (obj) { 
}
类锁
public static synchronized void method() {
}

这种方式只要是这个类实例化出的对象都共有一个锁,无关乎是否有相同的对象名。

public synchronized void method() {
}

这种就只是锁住同一个对象。锁发挥的作用相对于上面要小很多。

心得体会

多线程应该是真正生活中应用很多的一种代码模式,感觉编写多线程,主要是考虑哪些对象要进行上锁即要时时同步,大抵可包括这两种,check then act ,read modify write。将正确的对象上锁,多线程就不会出现那些死锁等很难找到bug所在的问题。

虽然刚接触多线程感觉很难,但是在调试的时候越来越理解多线程的同步等问题。感觉还是很满足的。

这单元的作业相对于第一单元完成的很好,有很大的进步,希望在接下来的单元里能够继续的认真学习。

 

 

 

 

 

 

 

 

 

 

 

 

 



Link to comment
Share on other sites