• 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

一、同步块的设置和锁的选择:

关于 synchronized :

有两种使用方法。

同步(这){

//同步代码方法块

}

同步void方法(){

//方法具体实现

}

关于 lock :

关于接口的用法和实现类:

ReentrantLock,ReentrantReadWriteLock。ReadLock,ReentrantReadWriteLock。写锁

锁定锁定=.

lock . lock();

尝试{

//处理任务

}catch(Exception ex){

}最后{

lock . unlock();//释放锁定

}

我的理解:

Synchronized关键字相当于整个锁对象中只有一个条件实例,所有线程都注册在它上面。这可能会导致效率问题。就像在hw7中,有些同学因为notifyall()唤醒太多,导致一些意想不到的bug。

Await()可以理解为wait()方法。Signalall()可以理解为notifyall()方法。

从更高级的需求来看:

尽管同步方法和语句的作用域机制使得使用监视器锁进行编程更加容易,并且有助于避免许多涉及锁的常见编程错误,但有时我们需要以更灵活的方式处理锁。

比如我们想限制它是只读还是只写,或者想按顺序执行一些同步代码的时候。此时,synchronized要实现上述功能是相当困难的。

锁的选择:

在这个任务中:我使用了同步锁。

在hw7中,我其实是想用锁机制的,但是想了想,我的代码设计,读写操作,访问共享变量都比较简单。没有synchonized很难实现的要求,也不会造成太大的性能影响,所以我没有使用lock锁。

锁与同步块中处理语句之间的关系:

在线程开始执行同步代码块之前,它必须首先获得同步代码块的锁。并且在任何时候只有一个线程可以获得同步监视器的锁。当执行同步代码块时,线程将释放同步监视器的锁。

同步代码块在锁的监督下是原子的和顺序的。

1.对于同步锁,当一个线程进入同步锁时,其他线程不能再次进入同步锁。只有在线程执行了同步锁中的代码之后,下一个线程才会进入同步锁。

2.对于刚从同步锁出来的线程,还是会进入新一轮的线程抢占同步锁。

在该作业中,所有同步块都是基于请求队列的同时读写来设置的。所以我在RequestQueue类中写了几个同步的方法。

记得老师在课堂上说过,要尽量保持run方法的简洁,所以我在实现的时候,没有在run方法中使用同步代码块,而是尽可能把同步逻辑放到共享变量类方法中:

同步(这){

//同步代码方法块

}

在类中设计一个安全的方法。方法是安全的,考虑到run方法中调用多个同步方法时是否会出现bug,那么我们就可以保证run方法的安全性,比如:

//一种同步方法:

public synchronized ArrayListNewRequest getNewCrossQueue(){

while(index==requests . size()cross elevator . get status()。等于(“等待”)

crossElevator.isVacancy()

crossElevator.getCrossSchedule()。noPassengers()) {

if (this.isEnd()) { this.setCorssElevetorEnd(); break; } try { wait(); //add request 以及 processingQueues.get(i).setend()也会唤醒它。 } catch (InterruptedException e) { e.printStackTrace(); } } ArrayList<NewRequest> newQueue = new ArrayList<>( requests.subList(index, requests.size())); //new 了一个变量并且返回。我没有改变任何东西。 this.index = requests.size(); //更新下标。 notifyAll(); return newQueue; }

二、调度器设计

hw5:

调度器设计:

在第5次作业中,我的调度器基本是采用训练类似的代码。当时由于刚接触多线程,感觉貌似在第5次作业中调度器没有什么作用,不过考虑到助教说,调度器作为线程来写是一个比较合理的架构,便保留了调度器(一个实际上并没有调度功能的调度器)。

功能:将请求加入对应楼座的等待队列中。仅仅通过 switch-case 即可实现。

线程交互:

  1. InputThread线程之间的交互:
    • InputThread线程在读入新的请求时,会调用waitQueue.addRequest()这个同步方法,向等待队列中加入一个新的请求。相应的,调度器会检测waitQueue是否为空,如果不为空,便调用waitQueue.getOneRequest();取出一个请求,并且删除这个请求。
    • 同时,InputThread还控制着调度器线程的结束。
      当调度器读入的当前请求为空时,便会调用同步方法:waitQueue.setEnd(true);,并且return,跳出自身的while循环,结束run方法。此方法的作用是与电梯之间进行线程交互
  2. Elevator线程之间的交互:
    • 当调度器检测到InputThread的End标志时,会调用同步方法:waitQueue.setEnd(true);。通知电梯,调度器已经结束了自身的线程。然后当电梯检测到 End 标志,并且电梯此时为空闲状态,便会结束当前线程
    • 同时,调度器还会向电梯分发请求。每次电梯运行的时候,都会通过调用getElevatorQueue()方法,来获取从调度器获得的请求,并且根据look策略决定是否在相应的楼层开门或者接人。

hw6:

调度器设计:

从本次作业开始,调度器作为一个线程的优越性就体现出来了。由于在hw5中,调度器采用了线程,因此在实现hw6的时候,调度器仅仅需要在hw5的基础上添加一点东西。

在hw6中,我没有采用自由竞争的策略,因为我在随机测试中发现自由竞争的策略不一定是最优的。而且如果采用了自由竞争的话,需要在hw5的架构里面加上很多读写锁,这不仅影响效率,而且还可能会导致出现难以预料的bug,采用此种策略,最终强测的性能分也达到了98分。我在调度器中采用分配的方式,把新来的需求尽可能以平均的方式分给电梯,具体伪代码如下:

int elevatorSize =elevatorsMap.get(newRequest.getFromBuilding() - 'A').size(); //当前座有多少个电梯。
int request_num;//这个新的请求是当前座的第几个请求。
processingQueues.get(newRequest.getFromBuilding() - 'A').
                    get((request_num % elevatorSize)).addRequest(NewRequest);

线程交互:

本次作业与hw5中的线程交互功能基本一致,在其基础上增加了横向电梯,其余功能与hw5一致。

CrossElevator线程之间的交互:

  • 当调度器检测到InputThreadEnd标志时,会调用同步方法:waitQueue.setEnd(true);。通知电梯,调度器已经结束了自身的线程。然后当电梯检测到 End 标志,并且电梯此时为空闲状态,便会结束当前线程
  • 同时,调度器还会采用取余的方法电梯分发请求。每次电梯运行的时候,都会通过调用getCrossElevatorQueue()方法,来获取从调度器获得的请求,并且根据look策略决定是否在相应的楼层开门或者接人。

hw7:

调度器设计:

本次作业由于乘客可能会换乘,因此对调度器的功能有了一个更高的要求。

于是,我在hw6的基础上新增了以下功能:统计每一个新请求是否目的楼层/楼座==当前楼层/楼座,如果符合条件,那么到达的人数就+1。

if (request.getFromBuilding() == request.getToBuilding()
                    && request.getFromFloor() == request.getToFloor()) {         //先处理特殊的情况。
                arrive_num++;

在判断线程是否结束时,也不能像之前那样简单的判断 End 标志了,需要增加一个判断条件,判断是否所有的人都到达了目的地,并且检测end标志,来确保线程结束:

if (waitQueue.isEmpty() && waitQueue.isEnd()&& arrive_num == waitQueue.getTotalQuest()) {
   setEnd();	// 结束电梯线程
   return;	// 结束调度器线程
}

线程交互(相对于之前新增的功能)

  1. InputThread之间的线程交互:

    • 这次作业还需要配置电梯的运行速度与容纳人数。并且将其传给调度器,由调度器负责读取请求并且创建一个新的电梯线程
    • InputThread需要统计一共要多少个新请求,并且传给调度器,由调度器最终负责判断当到达总人数==请求总数时,便可以结束相关线程
  2. Elevator 以及 CrossElevator之间的交互:

    • 向较于之前的作业,这次我选择在调度器里面新建电梯线程。因为题目要求会有增加可定制电梯的需求,所以我在调度器里面新建线程并且初始化开始时的6个电梯。

    • 由于需要换乘,所以电梯在结束一个请求的时候,会将其返回给调度器,由调度器判断这个人是否已经到达目的地,如果没有到达目的地,那么调度器会将这个请求更新目的楼层,目的楼座,并且将这个请求重新返回给电梯。

      也就是当乘客下电梯的时候,更新一下该请求的起始楼层、起始楼座。通过下面的指令,将其返回给调度器。

      NewRequest request =
      	new NewRequest(curFloor, personRequest.getToFloor()
                        , personRequest.getFromBuilding(), personRequest.getToBuilding()
                        , personRequest.getPersonId(), personRequest.getEndFloor()
                        , personRequest.getEndBuilding());
      waitQueue.addRequest(request);	// 返回给调度器
      

三、作业分析:

hw5:

时序图:

1tcv4hpw0ig4539.png

UML类图:

2m4dlb2xh414540.png

从架构图中可以看出,第一次在架构上主要是由MainClass来启动所有的线程。InnerSchedule作为电梯的运行策略类,而Schedule负责与InputThead协同工作,负责给电梯线程传输请求。由Input线程负责结束调度器线程,由调度器线程负责通知电梯处理完所有请求后应该结束线程。

策略类采用了look策略,实现相对简单,并且效果也非常不错。

hw6:

时序图:

owe5v2xt4yr4541.png

UML类图:

1s1bm2023kg4542.png

从UML类图和时序图可以看出:MainClass负责启动InputThread线程和Schedule线程,然后由Schedule负责启动相关电梯线程。这是相对于Hw5作业改动比较大的地方。

其余改动仅仅是将look策略新加入到横向电梯,以及创建横向电梯类及其策略类。整体来说并没有设计重构,架构进行了一下略微的调整。

hw7:

时序图:

y2lrmzww5l34543.png

UML类图:

h3ffcth11ir4544.png

第七次作业相较于第六次作业仅仅是增加了一些方法和属性,对架构并没有比较显著的改动。线程间的协同关系在第六次作业的基础上增加了一个Elevator类到Schedule类的addRequest调用,以便能完成换乘操作。

同时,由于乘客需要记录中转地,因此原先的PersonQuest类已经不满足条件,这时我们在其基础上引入NewQuest类,以便能实时更新乘客的位置。

同时,横向电梯需要增加相关的掩码机制。Schedule类需要增加一些方法,以判断乘客是否真正到达目的地或是仅仅进行换乘。

未来扩展分析:

我觉得如果对电梯扩展的话,可能会增加更多人性化的需求,更加贴近日常生活。比如不同的人进出电梯的速度不一样,再比如每一个PersonRequest类可以随机的主动按住电梯的开关门按钮,也就是人也可以控制电梯的开关门,而不仅仅是由电梯自身来决定开关门的信息。

四、bug分析:

此次作业互测与强测中仅出现一个bug,bug位于在hw5的作业中。在结束电梯线程时,程序出现了一些错误(见下方的代码)。导致最终电梯未能结束,运行时间超时。

原因还是对于多线程不够理解/(ㄒoㄒ)/。

当我判断是否结束电梯线程时,第一次写电梯的时候,由于对 wait() 机制不够清楚,以及不清楚什么时候需要wait() ,于是在进入while循环后,写了一个莫名其妙的wait(),可能是强行模仿了训练的代码,导致wait()唤醒后,又进入了一次wait()。所以没有线程来唤醒本次的wait(),最终线程无法正常结束。

while (index == requests.size() && crossElevator.getStatus().equals("WAIT")
        && crossElevator.isVacancy()
        && crossElevator.getCrossSchedule().noPassengers()) {
    
    //---------------产生bug的原因:
    //---------------修复方法:将其注释掉即可
    //	try {
    //   	wait(); 
    //	} catch (InterruptedException e) {
    //    	e.printStackTrace();
    //	}
    
    if (this.isEnd()) {
        this.setCorssElevetorEnd();
        break;
    }
    try {
        wait(); 
    } catch (InterruptedException e) {
        e.printStackTrace();
    }
}

五、测试策略与hack策略:

三次的思路基本一致,就拿最后一次作业举例。

因为写测评机不够熟练,所以本次作业仅是试着写了一下。按指导书的互测规范求生成请求即可,常量池有5个楼座和10层,利用rand函数随机选取。

在具体的测试与hack中,还是主要通过自行构造测试样例来进行测试的。

首先,在对自己的程序进行测试的时候,要对自己在程序中实现的基本功能进行一个覆盖性的测试,基本功能都正确的情况下,再去构造一些比较边界的数据去点构造数据针对死锁、轮询进行测试。下面是手搓的一些基本功能的测试样例:

检查abs是否最小策略
ADD-floor-电梯ID-楼层ID-容纳人数V1-运行速度V2-可开关门信息M
ADD-floor-8-7-4-0.6-18
ADD-floor-9-8-4-0.6-18
ADD-floor-10-3-4-0.6-18
ADD-floor-11-4-4-0.6-18
1-FROM-B-5-TO-E-10
检查同一楼层 A-D B-C/A-B B-C的情况。
9:A-D  24:D-E
ADD-floor-8-3-4-0.6-9
ADD-floor-9-3-4-0.6-24
1-FROM-A-3-TO-E-3
2-FROM-A-3-TO-D-3
3-FROM-D-3-TO-E-3
是否超载测试:
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
电梯调度策略测试:
ADD-floor-10-3-4-0.6-18
ADD-floor-15-3-4-0.6-18
ADD-floor-11-3-4-0.6-31
ADD-floor-12-3-4-0.6-31
ADD-floor-13-3-4-0.6-24
ADD-floor-14-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
......

Hack策略:

  • 是否超时:
    通过看对方的策略类写的是否有超时的可能,从而采用在最后一秒钟加大量集中数据的方法来hack其可能存在的超时问题
  • 基本功能是否正确:
    在第几次作业中,由于中测较弱,很多同学的基本功能可能出现了问题。比如横向电梯不能在本座开门却开门了等等
  • 线程安全角度测试:
    同一数据多次运行或者大量随机数据测试,大力出奇迹。并且构造一些比较边界的数据去点构造数据针对死锁、轮询进行测试。
  • 策略类是否正确:
    有些同学写的横向电梯look策略会导致电梯反复横跳,最终运行时间超时。

六、心得体会:

体会到了一个合理的架构的重要性。这次作业由于第一次认真思考了架构,并且将策略作为属性从电梯里分离出来。调度器只负责给出电梯行进的方向,hw6 和 hw7均没有重构,只在之前的基础上新增一些方法和属性便可实现新的需求。

对于多线程有了一个更深的理解。在刚接触多线程的时候,不太明白为什么一个进程需要很多个线程协同工作。在学习了synchronized()和wait()等机制后,对其有了更深的体会。多线程就是将原本线性执行的任务分开成若干个子任务同步执行,这样做的优点是防止线程“堵塞”,增强用户体验和程序的效率。

自学能力的重要性。老师上课的时间是有限的,只能给我们一个大致的框架。具体的多线程的知识还需要我们课下自行学习,学习能力也是一个程序员的基本素养~

关于层次化设计的心得体会:

在hw7中,层次化设计的优越性便可以显现出来。用一个集中控制的Schedule线程来创建电梯线程,并且电梯线程也会向调度器线程来反馈信息。调度器根据电梯反馈的信息做出进一步的处理。

面向对象编程主要是想教会我们如何实现好的架构,而不是对我们的算法有较高的要求。本次作业中,只要架构正确,采用较为基础的算办法也可以拿到很高的分数~

关于线程安全的心得体会

  1. 谈一谈对wait() 理解:首先只有不需要运行的时候才会wait()。在消费者生产者模型里面,当线程在有任务或需求队列有资源的时候是不需要wait()的 。所以每次程序wait() 的前面都需要加上一堆代码来判断一下是否需要wait()。

  2. 关于为什么需要同步保护:
    当我们的进程有很多线程的时候,并且有共享变量,就注定很多个线程可能同时对一个共享变量进行读写,那么就会发生读到的是旧的值,或者写覆盖等问题。此时,就需要java提供的锁机制来进行保护。

  3. 那么进入wait() 前判断什么呢?
    (1):当前进程是否需要继续处理任务
    (2):是否已经end了。如果我们使用 setend()的方法的话。那么进入wait() 可能就没法唤醒。这一点至关重要。也就是说需要保证,如果程序已经setend()了。那么这个电梯将永远不会进入wait(),具体的做法是可以在前面加上判断:

    if (this.isEnd()) {	//进入下一次wait().
                    this.setElevetorEnd();
                    break;
                }
                try {
                    wait();
    }
    

    而且setend : 往往还有作用,那就是在任务执行完之后切断电梯的任务。这样处理便不会出现电梯一致wait()的情况了。

  4. 关于避免轮询。一个线程里面至少需要有一个 wait() ,否则就会 由于run方法里面 while(true)的存在,那个线程就会一直执行,一致占用cpu资源。

  5. 关于notify() 。我们需要确保最后的时候,程序一定能及时结束,而不会卡在 wait() 的状态。所以需要setend()。当遇到这个,就结束进程,setend() 之后不能再进入协同线程run方法的下一次的while()

  6. 关于死锁,当多个线程访问多个共享变量,并且出现嵌套的时候,最后按相同的顺序来访问这些共享变量,这样就可以有效的避免死锁的产生。比如:

    线程1访问顺序: A B C
    线程2访问顺序: A B C
    
Link to comment
Share on other sites