• 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 Unit-2 Summary

第一次作业

同步块的设置和锁的选择

在本单元的作业中,我选择了JVM实现的synchronized作为锁。用生产者和消费者模式对应本单元的作业,可以发现共享的“托盘”只有电梯的等待队列。一方面,输入处理线程必须将新的请求放入等待队列,另一方面,电梯继续读取和处理队列中的请求。所以借鉴实验性的写法,在作业中把队列拆分成一个线程安全的类,使用synchronized修饰类方法,这样每个类方法的锁本身就是一个不同的队列对象。另外,共享队列被封装到一个线程安全的类中,它的写、读等方法可以在其他线程中直接安全调用,不需要使用同步语句块。

调度设计以及线程交互

线程的交互

严格来说,我在本单元的作业中实现的调度器并不是传统的调度器,而更像是一个分流装置,输入线程将请求不断放入输入线程和调度器共享访问的mainQueue,而调度器则根据不同请求的楼座区别,将请求放入不同的等待队列,等待队列调度器与电梯线程共享访问.其实这个任务也可以直接由输入线程来完成,但是采用这个设置是为了功能清晰。相对于其他同学可能会把调度器设计成一个线程来决定电梯的方向,我把决定电梯方向的功能放在电梯的线程里,更像是一个有自主决策功能的电梯。

另一个线程的交互是唤醒和结束的交互.当一个线程对共享队列的访问得不到请求时,为了避免CPU轮换,线程会进入等待状态,等待一个线程放入一个请求或信号来标志结束。例如,当调度程序访问主队列时,主队列为空,调度程序线程将进入等待状态,直到输入线程对主队列提出新的请求或标记主队列的结束符号,调度程序线程将再次运行。同样,调度员和电梯也涉及上述流程。另外,队列类中的结束标志是判断线程结束的重要标准。

电梯调度策略

我在电梯的线程里写了调度策略,类似于Look算法的设计,就是电梯每次运行,都是同一个方向能走多远就走多远。我在垂直电梯的设计中设置了maxFloor、minFloor、direction和nowFloor的属性值,根据调度策略给出的方向更新nowFloor的值(电梯只会在1和-1运行),判断是否达到maxFloor或minFloor的目的楼层的极值。如果达到极值,会将当前运行方向反转为0,即停止运行。这种设计的好处是电梯不会出现“逃天”的bug。

当电梯中没有请求且运行方向未确定时,访问等待队列中的第一个请求,由第一个请求确定电梯的运行方向和目标楼层的极值,判断是否在各楼层进行捎带,并根据捎带乘客更新和维护目标楼层的极值;当电梯内有乘客或无乘客,但方向已确定时,只需按照当前运行方向输送各楼层乘客即可。

UML类图及时序图

vzcg44rb3uo4627.jpg

ctwsj3cvutr4628.png

第二次作业

调度设计以及线程交互

对于第二次分配,引入了几部相同楼层的电梯或楼层和环形电梯,因此调度策略涉及如何将相同楼层和楼层的请求合理地分配给电梯。课程的指导书给出了基于ALS的轮换分配的调度方法,但轮换分配需要调度人员统一管理所有电梯。但是基于前辈们前几年的经验,我们可以利用多线程的思想和JVM自身的调度,采用一种自由竞争的调度方式,即一层楼一栋楼只有一个等待列表,多个电梯线程共享这个等待列表的访问和维护。

在这个作业中,因为对线程交互的理解还不够清晰,在互测中被黑了一个bug。同步语句块中notifyAll语句的作用是通知唤醒进入等待状态,因为资源即将被释放。

程参与竞争资源,在第一次作业中,分析可以得出,只有当线程向共享对象写入新请求或标志结束时,才需要通知唤醒等待访问共享对象的线程,但由于我在共享对象的类方法中几乎全都加上了notifyAll。导致一个电梯线程在访问一个随意的队列类方法时,会唤醒另一个电梯线程,但此时可能由于长时间调度器没有给等待队列放入新的请求,所以两个电梯线程轮流唤醒对方,但又没有实质性地处理输入,也就是近似轮询空转。

再写一个很简单但也思考得很久的事

横向电梯在我的设计中,如果是A->B->C....,则为正方向,direction为1,如果是A->E->D....,则direction为-1,设计之初,一直在思索,如何不通过遍历的方式确定横向请求的运行方式。最终,想到一个方法,分别计算正、负方向的到目的地的距离,比较两个距离,通过比较较小值的方式来确定方向。距离计算的方式:

clockwise = (curToBuilding - curFromBuilding + 5) % 5;  // 正方向计算公式
anticlockwise = (curFromBuilding - curToBuilding + 5) % 5; //反方向计算公式

UML类图及时序图

mn5uis0und34629.jpg

eb15ajbwhcc4630.png

第三次作业

调度设计以及线程交互

电梯调度策略

第三次作业难点在于如何进行换乘请求的调度以及如何安全地结束线程避免死锁、轮询空转。

我对于换乘设计,类似于“递归”的想法,因为换乘无非就是现在所处的位置仅凭搭乘一次横向和纵向电梯都无法到达,必须先纵向到达某一个楼层,所以可以把“换乘请求”普通请求 归一化为一个决定下一运行目的地的方法(作为Person类的一个类方法),也就是说,我们忽略中转楼层等概念,只根据目前所在楼层、楼层和目的楼层、楼座决定接下去的目的楼层、楼座,这就将中转递归成了多次求目的楼层、楼座。同时也大大简化了调度器的分流难度,调度器分流只需要根据目前的所在和计算出的目的地楼层楼座,将请求放入对应的等待队列。

public void updateToDirection(SwitchTable switchTable) {
        if (curFromBuilding == toBuilding) {
            curToBuilding = toBuilding;
            curToFloor = toFloor;
        } else if (curFromFloor == toFloor) {
            if (switchTable.canArrive(curFromFloor,curFromBuilding,toBuilding)) {
                curToBuilding = toBuilding;
                curToFloor = toFloor;
            } else {
                curToBuilding = curFromBuilding;
                curToFloor = switchTable.getTransferFloor1(curFromBuilding,toBuilding,toFloor);
            }
        } else {
            if(switchTable.getTransferFloor2(curFromBuilding,toBuilding,curFromFloor,
                    toFloor) == curFromFloor) {
                curToBuilding = toBuilding;
                curToFloor = curFromFloor;
            } else {
                curToBuilding = curFromBuilding;
                curToFloor = switchTable.getTransferFloor2(curFromBuilding,toBuilding,curFromFloor,
                        toFloor);
            }
        }
    }

线程交互

如何结束线程

第三次作业的调度设计会带来一个调度器分流线程错误结束的问题,在之前两次的作业中,由于每个请求只需分流一次,所以当输入线程结束后,调度器分流也就结束了,并通知每个电梯线程“输入已经结束,处理完当前已有请求即可结束线程”。但是,这一次作业中,一个换乘请求会多次进入调度器线程,若不改变调度器逻辑,可能导致换乘请求重新进入调度器进行分流时,调度器线程已经结束或者应该搭乘的电梯也已经结束线程。

个人感觉,本单元的实验都十分有用,我在线程的交互上的设计基本模仿实验,同样,第三次作业的如何结束进程也参考了第三次作业中计数器的设计。

计数器的设计在于当输入线程向调度器放入一个新请求时,计数器总数+1;而当电梯线程完成一次请求后,后判断该请求是否已到达最终目的地,如果是,则计数器总数-1。

调度器线程在输入线程结束并完成分流当前所有等到分流的请求后,会进行一次访问,如果计数器不为0,则说明当前仍有请求在电梯内,可能会重新进入调度器,所以,调度器并不会直接结束,而是进入wait状态,等待放入换乘请求再次唤醒调度器。

if (RequestCounter.getInstance().getCount() == 0) {
                    for (Integer id : buildingEleWaitQueues.keySet()) {
                        buildingEleWaitQueues.get(id).setEnd(true);
                    }
                    for (Integer id : floorEleWaitQueues.keySet()) {
                        floorEleWaitQueues.get(id).setEnd(true);
                    }
                    return;
                } else {
                    synchronized (mainQueue) {
                        mainQueue.setIsAsleep(true);
                        try {
                            mainQueue.wait();
                        } catch (InterruptedException e) {
                            e.printStackTrace();
                        }
                        mainQueue.setIsAsleep(false);
                    }
                }
改进后带来一些问题

调度器在电梯中仍有乘客的情况下会进入wait状态,之后,会被换乘请求唤醒,这一逻辑基本正确。但如果电梯中的乘客不需要换乘,出电梯即可到达最终目的地;或者试想,最后一次位于电梯内的请求是不是肯定不需要换乘。此时,调度器线程无法被唤醒,无法结束,电梯线程也无法结束。

对此,我的解决方案是,在调度器线程进入wait状态时,标记一个sleep的标志符,当电梯线程在完成所有请求后判断此次是否没有将换乘请求放入调度器中,如果是并且输入线程的sleep的标志符为真,则唤醒调度器线程。

 if (mainQueue.isAsleep()) {
                synchronized (mainQueue) {
                    mainQueue.notifyAll();
                }
            }

另外值得注意思考是,该设计会不会导致死锁,及电梯线程已经完成了notifyAll操作后,但是由于多线程随机轮转线程等问题,调度器线程由于指令执行的先后顺序问题再次进入wait状态,导致死锁。对此,我之后思考的结果为,虽然,多线程的指令顺序是随机的,但是同一线程内的逻辑,必然是符合逻辑顺序的。也就是,电梯线程需要在notiAll()之前,再完成对计数器的减一操作;如果能保证这一先后顺序,一定能够保证,在最后一个运送完最后一个请求时,电梯线程notifyAll唤醒调度器线程之时,计数器计数已经为0,调度器线程因为计数器为0,可以正确地计数自己的线程以及给所有电梯线程的结束符置1。

横向电梯避免轮询的问题

先说一下,我在这一次作业中如何处理横向电梯的请求分配。这次作业可能出现,同一层中的多个横向电梯,可以到达各不相同的楼座,所以怎么分配不同的横向请求,比较棘手。我最先想到的方法是给每层中可到达楼座信息不同的电梯各分配一个等待队列,这样,电梯在处理请求时的逻辑就比较简单,与前两次作业一致。但实际上,却需要一个全局的容器来存储所有楼层中所有电梯的可到达信息以及对应的等待队列地址,操作看似简单,实际上也挺复杂。当时临近中测的DDL已经不到24小时,所以我想到的是尽可能减少重构和扩展。所以,还是打算在第二次作业的基础上采用 自由竞争的策略,即同一个楼层、一个楼座只有一个等待队列。在前文中,已经指出,可能同一个楼层有多部可到达信息不同的电梯,比如在同时5楼,有一部只可在A、C楼座来回的电梯7和一部只可在B、D楼座来回的电梯8,考虑极端情况,在电梯创建后,所在5楼的请求都是从A、C的,但是由于队列是共享的,电梯8也可以一直访问其无法运送的请求,但却不能处理,相当于一直在轮询等待队列,所以这里会产生轮询的问题,所以相比于纵向电梯访问请求队列方法只需对队列为空进行处理,横向电梯访问方法还需要处理队列中的请求都不能到达的情况,处理方法仍是进入wait状态。

public synchronized  Person visitFloorFirstRequest(int info) {
        if (requestPeople.isEmpty() && !this.isEnd) {
            try {
                wait();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        if (requestPeople.isEmpty()) {
            return null;
        }
        while (!requestPeople.isEmpty()) {
            for (Person person : requestPeople) {
                if (((info >> person.getCurFromBuilding()) & 1) +
                        ((info >> person.getCurToBuilding()) & 1) == 2) {
                    return person;
                }
            }
            try {
                wait();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        return null;
    }

这里需要值得注意的是,此处修改会不会使电梯线程由于一直处于wait状态而无法唤醒,仔细思考,这就和怎么调度器进程与电梯之间的交互有关系了,在前两次作业中,都是调度器线程处理完输入,给电梯线程结束输入标志符置1(即setEnd);在第三次作业中其实还是一个道理,只不过是需要计数器为0,调度器才为电梯线程输入结束标志符置1,setEnd方法有notifyAll语句,能够唤醒等待中的电梯线程。所以这一处多加的wait所起到的效果仍和队列为空,电梯进入wait状态一致,也就是都可以通过最后收尾阶段,调度器线程给电梯线程setEnd来唤醒。

UML类图及时序图

mu3ax1iw3u44631.jpg

hvotnstrzsg4632.png

心得体会

在这单元的作业中,一开始难以下手,不清楚如何写多线程,与其说是不理解如何写多线程,更准确地说是没有理解本次作业多线程应用的本质是一个类似流水线的电梯搭载请求处理器,以及调度策略也难以下手。看到第一次的实验代码后,可以说是有一种"拨开云雾见月明"的感觉,理解了多线程各个类之间如何各司其职以及协作交互处理请求。捋清思路之后,难点就只在于如何写调度策略了。

理论课上多次强调地如何维护线程的安全,如何保证读写共享对象这一操作的原子性,一开始也是懵懵懂懂,维护线程安全,个人那时候的理解就是把涉及多个线程访问的共享对象全都用锁锁起来就没问题了,细化到操作就是用synchronized关键词加一个自定义锁来写一个同步块实现。直到,我见识了实验的代码,把共享对象封装成了线程安全类,在调用方法,改变对象时,也无需再次调用同步块语句。这一方法确实很方便,非常适合初学者入门多线程,对于初学者来说,用sychronized语句锁共享对象的方法,属于是一劳永逸。但对比显式锁,可能并不是一个高效的办法。但确实挺有效的,我在三次作业中,没有出现线程安全的bug。

至于死锁等问题,这单元作业中,加锁的逻辑还较为简单,没有多重锁的设计,我就没犯死锁的错误。

关于读写锁至今还存在疑问

在第二次作业中,尝试过研究读写锁的在代码中的应用。读写锁上锁和释放锁相对简单,无需讨论。在使用一般显式锁的情况下,线程可以调用显示锁的await方法和signalAll方法,来使线程进入等待或唤醒线程,从await到唤醒都是同一个显式锁,逻辑也比较清晰。但是如果使用读写锁分开后,试想一个场景,电梯线程拿到队列的读锁,但因为队列为空,交出读锁,通过读锁进入await状态;调度器线程拿到写锁,写入完毕后,通过写锁的唤醒,但是通过写锁的唤醒应该唤醒不了一个因为通过读锁进入await的电梯线程。之后咨询了一位去年使用读写锁的大牛学长,学长的处理方式似乎也没有太好的选择,读取共享对象先通过读锁读取,如果读取队列为空,加写锁,在写锁中实现await操作,此时等待另一个写入方法的写锁唤醒电梯线程。

因为读写锁在书写过程中难以理清其加锁逻辑和结构,即时捋清,如同大牛学长般的操作也比较复杂。所以,由于本人能力实在不足,无奈下,也就放弃了读写锁的应用。

Link to comment
Share on other sites