[BUAA-OS]第二单元（电梯）博客总结

1. 基本架构

1.1第一次作业

1.1.1 设计要求

实现单部可稍带电梯。

1.1.2 设计思路

整个过程主要有三个线程：读入信息、调度器、电梯运行。

读入信息单独开设一个线程，负责循环从终端读入请求信息，并将请求信息加入等待队列中。

调度器线程每次从等待队列中选出合适的请求加入本次即将上电梯的队列。

电梯运行线程每次从本次即将上电梯的队列中的请求加入到当前电梯中，并完成开关门、上下楼、上下电梯操作。

1.1.2.1 同步块设计

读入信息——人员分配

共享等待队列，在向等待队列加入和删除请求时需要加锁。在询问等待队列是否为空时不需要加锁。

人员分配——电梯运行

共享即将上电梯的队列，在分配上电梯的人和人员上电梯时需要加锁，在询问上电梯队列是否为空时必须加锁。

1.1.2.2 调度器设计

在第一次作业中，调度器只读取当前电梯楼层，然后对当前楼层分配可以上电梯的人。

1.2第二次作业

1.2.1 设计要求

实现多部电梯，能够动态增加电梯。

1.2.2 设计思路

在上述思路上，需要对相关线程进行修改。

读入信息线程：支持增加电梯的操作。

调度器线程：需要支持对不同电梯的操作。

电梯运行线程：有多个电梯运行线程同时运行。

1.2.2.1 同步块设计

读入信息——人员分配

共享等待队列，在向等待队列加入和删除请求时需要加锁。在询问等待队列是否为空时不需要加锁。

共享电梯运行线程，在增加电梯时需要对电梯运行线程队列加锁。

人员分配——电梯运行

共享即将上电梯的队列，在分配上电梯的人和人员上电梯时需要加锁，在询问上电梯队列是否为空时必须加锁。

1.2.2.2 调度器设计

本次作业中，调度器需要轮流询问每个电梯运行线程是否可以增加人员，注意避免产生轮询的情况。

1.3第三次作业

1.3.1 设计要求

实现多部电梯，能够动态增加电梯，每部电梯有不同的速度、承载人数、停靠楼层。

1.3.2 设计思路

需要修改调度器线程，保证每次上电梯的人是合法的。

1.3.2.1 同步块设计

读入信息——人员分配

共享等待队列，在向等待队列加入和删除请求时需要加锁。在询问等待队列是否为空时不需要加锁。

共享电梯运行线程，在增加电梯时需要对电梯运行线程队列加锁。

人员分配——电梯运行

共享即将上电梯的队列，在分配上电梯的人和人员上电梯时需要加锁，在询问上电梯队列是否为空时必须加锁。

1.3.2.2 调度器设计

本次作业中，调度器需要判断楼层是否可以停靠以及该电梯的资源利用率是否较高。

1.3.2.3 电梯运行策略

电梯沿某一方向行进：

1. 如果当前电梯内有人，则电梯的行进方向为电梯内的人的需求方向
2. 当电梯内无人时，查看电梯目前行进方向上是否还可以接到人，是否需要调转方向：
   1. 如果电梯向上：
      1. 上方楼层有人出发上行或下行，则继续向上
      2. 此层有人上行，则继续上行
      3. 否则反向
   2. 如果电梯向下：
      1. 下方楼层有人出发下行或上行，则继续向下
      2. 此层有人下行
      3. 否则反向

注意：

1. 电梯抵达某一楼层时，如果等待的人与电梯行进方向不一致，则不上电梯。
2. 电梯抵达某一层可能突然变空，此时可能涉及电梯的方向改变，需要先判断原方向是否可以继续行进和上人，然后判断是否换向，并查看新方向是否上人。

1.3.3可扩展性分析

由于采用继承模式，对于电梯种类的可扩展性较好。
利用专属队列将等待队列和电梯内对列隔离，可以较好地适应各类调度算法。

3. bug分析

3.1 个人bug总结

在本次作业中遇到的主要问题有：

1. 电梯卡死问题：当电梯空载、等待队列未空时，需要为电梯指定接下来的要接的人，此时，电梯的目标应当时此人的出发层而非到达层。由于此人的出发层和到达层可能正位于电梯当前位置的两侧，电梯则可能先取到达层接人，却一直接不到，造成电梯在某一楼层卡死，程序不能正常退出的情况。
2. 电梯接不到人问题：此类问题出现在电梯改变方向的过程中，由于抵达某一层时，电梯内部突然情况，此时不仅需要按照原方向判断是否上人，还需要判断接下来要接的人的方向，并查看新方向是否接到人。
3. 当前层被忽略问题：电梯突然换向时，可能忽略处于当前层、方向为原方向的人。
4. 电梯运行线程安全问题：在将新的电梯运行线程和专属等待队列加入宗队列时需要加锁，否则询该电梯的专属等待队列时会出现错误。
5. 轮询问题：电梯线程应当在无人时停止，避免轮询。
6. 死锁问题：在调度器和电梯运行线程中，均有需要同时拿到专属队列和等待队列的锁的情况，注意二者加锁顺序保持一致，避免出现死锁情况。

3.2 发现bug策略

1. 尝试极限数据（人数、电梯数目上限）
2. 加电梯操作在询问中途进行常常引发线程安全问题

本单元需要考虑时序性问题，这常常是出现bug的关键。

4. 心得体会

原来我对java一无所知

模块化思想的延申

多线程是模块化思想的延申，每个线程需要管理好自己的数据，执行自己的任务。如果没有任务，则等待。每个进程不需要也不应该过问其他进程。

线程交互依赖共享数据的交互

前面说到每个线程只关心自己的事，不关心其他，那么线程之间的交流也只依赖共享数据的交互。共享数据在任一线程使用的过程中，需要加锁。

加锁的顺序是十分重要的

线程*享数据的加锁嵌套顺序在各个线程中必须是一致，否则将出现死锁。