【BUAA OO】关于多线程的一些问题

本文为我在进行U2单元第一次作业时和初次接触多线程编程的过程中遇到的一些问题，将其中的原理和我的一些个人理解记录下来，势必会有不准确的地方，还望大家多多包涵，批评指正！

在开始之前，我先将我的设计思路阐述一下，后面某些问题的背景与此相关。首先观察到此次作业官方包中声明了Request接口并有PersonRequest作为具体实现，基于此处的线索和生活经验，我猜测后续迭代中会出现货物请求，即电梯运载货物，同时还要考虑到后续不再为乘客指定电梯。综合以上因素，我决定在此次作业中将请求转化为乘客这一过程解耦为请求-请求分配-乘客这样的过程，具体实现体现在除了输入装置和电梯进程外，添加一个调度器进程，负责将输入装置输入的请求进行分配。

可以认为输入装置和调度器构成一组生产者-消费者关系，而调度器和每一台电梯构成一组生产者-消费者关系，注意到在同一个共享对象下生产者和消费者都只有一位。

锁、sleep与wait-notify机制

这部分内容在初次接触多线程时让人感到疑惑，引用吴老师课件上的关系图。

锁

锁负责的是上半部分，也就是RUNNABLE、RUNNING、BLOCKED之间的转化，具体在代码中的实现便是synchronized同步块。某个进程获得了锁，才能执行同步块中的代码。

锁的监视对象

锁是基于对象创建的，锁通过监视该对象来实现同步。锁监视的对象取决于synchronized修饰的内容。synchronized修饰方法时，根据方法的不同监视对象不同：静态方法的监视对象为.class,动态方法的监视对象为this。而synchronized修饰代码块时，监视对象则是可以自行指定的。因此，以下的写法是等价的：

1. 实例方法的等价写法

   //第一种写法
   public class Counter {
       private int count = 0;
       public synchronized void increment() {
           count++;
       }
   }
   //第二种写法，显式锁定this
   public class Counter {
       private int count = 0;
       public void increment() {
           synchronized (this) {
               count++;
           }
       }
   }

2. 静态方法的等价写法

   //第一种同步静态方法
   public class Logger {
       private static int logCount = 0;
       public static synchronized void log(String message) {
           logCount++;
           System.out.println(message);
       }
   }
   //第二种显式锁定Class对象
   public class Logger {
       private static int logCount = 0;
       public static void log(String message) {
           synchronized (Logger.class) {
               logCount++;
               System.out.println(message);
           }
       }
   }

当然同步代码块也可以锁定自行创建的对象。
我认为搞清楚这些写法并不像孔乙己写茴字一样无聊迂腐，而是能帮助我们更好地理解如何去判断进程与进程之间共享的是哪一把锁，锁的监视对象是谁，是很重要的。

锁的获得与释放

锁的获得与释放，是对于进程来说的。锁的释放很容易判断，在进程正常运行情况下，锁在synchronized修饰的代码块执行完毕后即可释放。但是锁的获得则与锁的类型有关，在本次作业中采用的synchronized为一种“非公平锁”，也就是说锁释放后其余等待锁的进程会抢夺锁的使用权，这就可能导致某些需要频繁获得锁的进程能够一直获得锁，从而产生随机性。例如：

public void in() {
    String floor = floor2String(currentFloor);
    synchronized (waitingTable) {
        while (getCurrentNum() < 6) {
            Request request = null;
            //位置二：synchronized (waitingTable) {
            在候乘表中获得请求
            }
        }
    }
}

这里当前进程A将锁交出后，如果进程B获得了锁可能会导致进程B阻塞住，无法将锁释放（具体原因后面解释，这里先给出这样的设定）。synchronized (waitingTable)的两种位置可能在运行结果方面看不到差异，这便是因为如果按照位置二的写法，每个循环之后都会将锁释放掉，但是由于锁非公平，导致当前进程能够频繁获得锁，不会因为锁被进程B获得而导致循环被阻塞住。但是这样的结果是随机的，如果进程B获得了锁就会导致结果大相径庭。

sleep与wait-notify机制

有了对锁的理解，sleep与wait-notify机制就很容易理解了。

sleep()与wait()的区别

sleep和wait的差别就在于sleep()执行后锁仍然在当前进程中，只是sleep的过程中当前进程什么也不干，而wait()执行后会将锁交出，该进程冻结在wait的位置。想让该进程重新运行，需要两个有顺序的条件：

1. 该进程被notify()/notifyAll()唤醒，这时进程的状态为RUNNABLE。
2. 该进程获得锁，这时进程的状态变为RUNNING。
   这便是上面图中的下半部分。

   注意：wait后的进程重新变为RUNNING状态后，会在冻结的位置继续执行，也就是在wait()后的位置开始执行。

notify()与notifyAll()

notify()方法必须在synchronized块中，比如记notify()所在的代码块具有的锁为A，可以认为notify()唤醒的为因执行wait()而释放A锁的进程，这也就能说明为什么notify()必须在synchronized块中了。
而notify()和notifyAll()的区别也很简单了,如果有很多个释放A锁而wait的进程，那么notify()会随机唤醒一个，notifyAll()则会将他们全部唤醒，至于到底是谁执行，还要看唤醒后的进程谁能够抢到锁。
在此次作业中，由于同一共享对象下生产者和消费者各只有一位，因此notify()与notifyAll()没有区别。

而我们跳出此次作业，如果同一共享对象下有着多个wait的进程，考虑这样的情况，如果某个进程被唤醒并且抢到了锁，但是该进程接下来执行所需要的条件并不满足，或者会被阻塞，这种情况称之为虚假唤醒。我们应当对其是否具有执行条件做出检查：

public Request Poll() {
    synchronized (this) {
        while (requests.isEmpty() && !isInputEnd()) {
            try {
                wait();
            } catch (InterruptedException e) {
                throw new RuntimeException(e);
            }
        }
        if (requests.isEmpty()) {
            return null;
        }
        return requests.remove(0);
    }
}

这里while循环便是对条件的检查，至于为什么不用if而使用while，是因为之前提到的wait后的进程重新变为RUNNING状态后，会在冻结的位置继续执行，也就是在wait()后的位置开始执行，如果使用if的话，只会进行一次检查，考虑这样的情况：如果该进程再次被唤醒并获得锁，那么就不会进行检查了。

静态锁与实例锁

在第三次上机提供的代码中有这样一段：

@Override public void run() {
    while (true) {
        if (orderQueue.isEmpty() && orderQueue.isEnd()) {
            for (ProcessingQueue queue : queueMap.values()) {
                queue.setEnd();
                // 向厨师线程发出结束信号
  }
            System.out.println("DispatchThread ends");
            break;
        }
        Order order = orderQueue.poll();
        //从orderQueue中取出订单
  if (order == null) {
            continue;
        }
        dispatch(order);
    }
}

这里向厨师线程发出结束信号时，使用for循环对ProcessingQueue的各个实例分别设置结束信号，那么为什么不将结束信号作为一种静态属性呢？如果这样的话就需要静态锁对isEnd属性进行保护，也就是监视对象为ProcessingQueue.class，而该类中其他同步方法的锁监视对象均为this，使用不恰当可能就会出现竞态条件或者死锁的问题。

竞态条件

修改isEnd作为静态属性，并且将setEnd()和isEnd()方法修改为静态方法

public class ProcessingQueue {
    private final ArrayList<Order> takeAwayOrders = new ArrayList<>();
    private final ArrayList<Order> eatInOrders = new ArrayList<>();
    private static boolean isEnd = false;
    
    public synchronized Order poll(String type) {
        if (isEmpty() && !isEnd()) {
            try {
                wait();
            } catch (InterruptedException e) {
                throw new RuntimeException(e);
            }
        }
        notifyAll();
        //按照优先级取出需要处理的订单，在这里输出 working  if(!eatInOrders.isEmpty()) {
            Order order = eatInOrders.get(0);
            System.out.printf("working-%d-by-%s\n", order.getId(), type);
            return eatInOrders.remove(0);
        }
        else if(!takeAwayOrders.isEmpty()) {
            Order order = takeAwayOrders.get(0);
            System.out.printf("working-%d-by-%s\n", order.getId(), type);
            return takeAwayOrders.remove(0);
        }
        else {
            return null;
        }
    }

    public static synchronized void setEnd() {
        isEnd = true;
    }

    public static synchronized boolean isEnd() {
        return isEnd;
    }

    public synchronized boolean isEmpty() {
        notifyAll();
        return takeAwayOrders.isEmpty() && eatInOrders.isEmpty();
    }
}

这样某一进程在执行poll方法时，首先获取了实例锁，而进行条件判断时需要调用isEnd()静态方法，需要获取静态锁。这样实现是没有问题的，但是如果将isEnd()改为isEnd，将调用静态方法改为获取静态属性，就会出现多线程可见性的问题。
考虑这样的情况，进程A获取了静态锁通过setEnd()方法将isEnd属性修改，进程B获取了实例锁调用poll()方法，进程B可能看不到进程A将isEnd属性修改，会导致条件判断的错误：
时间线：

1. 线程B：检查 isEnd=false
2. 线程A：执行 setEnd() 设置 isEnd=true
3. 线程B：执行 wait() → 错误地进入等待

所以静态锁和实例锁混用很有可能因为操作的疏忽导致出现竞态条件，我认为不算是一种好的设计，不如将isEnd作为实例变量进行访问和修改。

死锁

考虑这样的情况：

class MixedLockExample {
    // 实例方法使用实例锁
    public synchronized void instanceMethod() {
        System.out.println("实例方法开始");
        try { Thread.sleep(100); } catch (InterruptedException e) {}
        
        // 调用静态方法（会尝试获取类锁）
        staticMethod();
        
        System.out.println("实例方法结束");
    }
    
    // 静态方法使用类锁
    public static synchronized void staticMethod() {
        System.out.println("静态方法开始");
        try { Thread.sleep(100); } catch (InterruptedException e) {}
        
        // 创建实例并调用实例方法（会尝试获取实例锁）
        new MixedLockExample().instanceMethod();
        
        System.out.println("静态方法结束");
    }
}

线程1执行：MixedLockExample.staticMethod(); # 获取类锁
线程2执行：new MixedLockExample().instanceMethod(); # 获取实例锁
出现了这样的情况，线程1持有类锁，等待实例锁，线程2持有实例锁，等待类锁。这就发生了死锁。
上面我们分析的poll方法，正是这样一种实例方法，如果我们的静态方法中需要调用实例方法，那么就会发生死锁，虽然并没有发生这样的情况，但是留下这样的风险我觉得仍然是非常危险的，毕竟孰能无过，随着迭代如果忘记了这里的风险，很容易出现死锁的错误。

结论

综合以上分析，我认为与其冒着这么大的风险将isEnd设置为静态属性，真不如老老实实作为实例属性，循环对实例属性进行修改。更不要耍小聪明，理所当然认为实例锁和静态锁没什么区别，想来哪个来哪个。

阻塞

我在此次作业中有这样的考虑，电梯开门的0.4s内如果有新的请求发出，那么趁着这个时间让其上电梯多好，不然这0.4s也是浪费。想法是好的，但是我在具体实现的过程中发现，我的实现会导致电梯一直开门，直到下一个请求发出才会关门。经过分析，发现归根到底，阻塞是由于官方包提供的输入方法导致的。于是我也没有实现我的设想，这里我对其中的原因进行分析，如果大家有好的实现方法欢迎提出！
为了实现开门期间可以接受新的请求，我在电梯进程执行时通过wait(400)将持有的候乘表锁交出，并在0.4s后自动唤醒。候乘表锁交出后，调度器进程获得候乘表锁，也就是可以向候乘表中添加请求，如果此时请求队列中没有请求，调度器通过wait交出请求队列锁，输入装置获得请求队列锁，也就是可以向请求队列中添加请求。

看图我们可以发现，想让电梯进程恢复，第一步需要请求装置将调度器进程唤醒并交出请求队列锁，请求装置进程执行代码如下：

public class InputHandler implements Runnable {
    @Override 
    public void run() {
    ElevatorInput elevatorInput = new ElevatorInput(System.in);
    while (true) {
        Request request = elevatorInput.nextRequest();
        if (request == null) {
            break;
        }
        if (request instanceof PersonRequest) {
            PersonRequest personRequest = (PersonRequest) request;
            requestQueue.addRequest(personRequest);
        }
    }
    try {
        elevatorInput.close();
        } catch (IOException e) {
        throw new RuntimeException(e);
        }
    requestQueue.setInputEnd();
    }
}
public class RequestQueue {
    public void addRequest(Request request) {
        synchronized (this) {
        requests.add(request);
        notify();
        }
    }
}

可以看出要完成第一步需要请求装置进程中执行完addRequest方法。但是根据实际情况可以分析得出，只有在下一条请求被投喂的时候才会完成这一步，而不是预想的0.4s内完成。
通过使用IDEA自带的IntelliJ Profiler工具(使用方法不再赘述，非常好用的工具)可以发现请求装置进程花费的时间主要在Request request = elevatorInput.nextRequest();这一行，这是官方包给出的获取请求投喂方法，于是我们分析官方包中方法的实现。

官方包中对nextRequest()方法的实现如下：

public Request nextRequest() {
    while(this.scanner.hasNextLine()) {
        String line = this.scanner.nextLine();
        if (PersonRequest.matches(line)) {
            try {
                PersonRequest request = PersonRequest.parse(line);
                if (this.existedPersonId.contains(request.getPersonId())) {
                    throw new DuplicatedIdException(line);
                }

                if (!this.existedElevatorId.contains(request.getElevatorId())) {
                    throw new InvalidElevatorIdException(line);
                }

                this.existedPersonId.add(request.getPersonId());
                return request;
            } catch (RequestException var3) {
                RequestException e = var3;
                e.printStackTrace(System.err);
            }
        } else {
            try {
                throw new InvalidRequestException("Illegal Request: " + line);
            } catch (InvalidRequestException var4) {
                InvalidRequestException e = var4;
                e.printStackTrace(System.err);
            }
        }
    }

    return null;
}

首先要判断this.scanner.hasNextLine()，而查看hasNextline()说明可以发现：

该方法可能会在等待输入时阻塞，这便能解释为什么要等到下一条指令被投喂时才能执行完nextRequest()方法。我们也就可以得知，官方包给出的接收请求投喂方法是阻塞的，没有请求投喂时会被阻塞在nextRequest()方法处，自然也就不能执行到addRequest方法处，完成唤醒调度器，传出请求队列锁等一系列操作。
官方包给出阻塞的接收方法是可以理解的，如果该接收方法不是阻塞的，那么每时每刻都要去判断有没有新的请求被输入，这就会导致轮询。
同时我也尝试是否可以在不对官方包进行修改的基础上中断scanner，这就需要在输入流上下手。

public void run() {
    long startTime = System.currentTimeMillis();
    InputStream nonBlockingInput = new BufferedInputStream(System.in) {
        @Override
        public int read() throws IOException {
            if (System.currentTimeMillis() - startTime > 400) {
                return -1; // 超时返回 
            }
            return super.read(); 
        }
    };
    ElevatorInput elevatorInput = new ElevatorInput(nonBlockingInput);
    while (true) {
        Request request = elevatorInput.nextRequest();
        if (request == null) {
            break;
        }
        if (request instanceof PersonRequest) {
            PersonRequest personRequest = (PersonRequest) request;
            requestQueue.addRequest(personRequest);
        }
    } 
    try { 
        elevatorInput.close(); 
    } catch (IOException e) {
        throw new RuntimeException(e); 
    } 
    requestQueue.setInputEnd(); } 
}

但是这样更改输入流会导致超时时输入EOF，导致scanner提前关闭。至此，我也不愿意再在这上面添加复杂的控制了，遂放弃。

总结

以上为我个人遇到的一些问题和理解，存在局限性，希望其中部分内容能帮到恰好遇到类似问题的同学，不正确不准确的地方还请大家多多批评指正。