操作系统课设 - 信号量机制 - 交通信号灯模拟
2017-08-08 本文已影响508人
谢小帅
Android 交通信号灯模拟 - Shuai-Xie - Github
Java 交通信号灯模拟 - Shuai-Xie - Githu
一、题目重述
-
目的：了解信号量机制，了解并掌握进程同步和互斥机制，熟悉信号量的操作函数，利用信号量实现对共享资源的控制。
-
设计要求：编程模拟交通信号灯的控制。
-
问题描述：一个十字路口，共有四组红绿灯，每个路口的车辆都遵循 红灯停，绿灯行的原则：红灯停，该路汽车进程设置为阻塞状态；绿灯行，该路汽车进程设置为就绪状态。假设将每一台汽车都作为一个进程，请设计良好的机制，展示出合理的“十字路口交通管理”情况。
-
车辆通行设定：路口宽度不限，对一个路口而言，只有当一辆车通过路口（越过对面路口的交通灯后），其后续车辆才能继续通过交通灯，车辆通过路口的时间可以固定（设计成固定为1），可以自行计算。
-
进程的互斥：交通灯进程实际上是互斥的，即不能同时为红或者同时为绿。
但是同一条路的交通灯可以设置为相同颜色，南向和北向在同一条路上，南向和北向的车同时经过道路不会有冲突，东向和西向同理，但是南北向和东西向的颜色互斥。 -
进程的消息通信或其通信方式：对车辆进程而言，每一个车辆在通过路口前，必须确认前面的车辆已经通过了路口。
-
进程的调度：停留在一个路口的车辆，决定其前进或等候的因素是交通灯和前面车辆的状态，需要设计一个良好的进程调度机制来控制所有车辆的通行。
二、设计思想
交通灯问题中的共享资源是十字路口的道路，在设计交通灯时，南北向和东西向的交通灯交替变化为绿色，所以南北行驶的汽车与东西向行驶的汽车不会有冲突，但是当同一方向出现了同时到达十字路口的汽车时，就出现冲突了，某一时刻道路资源设置为互斥信号量，当一辆车使用道路资源时，剩下的这一时刻出现的汽车（可能多辆）必须等待，当该汽车通过路口时，剩下的车辆仍然采用互斥的方式使用路口资源，按顺序通过十字路口，此时时间递增。
在模拟该问题情景时，要自定义交通灯和车辆信息。
- 南北向和东西向的交通灯
- 在随机时间出现在路口的汽车
主要影响调度的特征：汽车行驶方向（direction）和汽车出现时间（showtime）
- 首先，根据汽车的 showTime 对所有的汽车进行排序，按 showTime 从小到大的顺序排列，showTime 相同的汽车之间的先后顺序任意均可；
- 其次，根据汽车的 directon 对汽车分成东西南北四类汽车，将分好类的汽车对象按出现顺序由先到后存储到4个队列中：
northCarsQueue 存储北向汽车信息，southCarsQueue 存储南向汽车信息，westCarsQueue 存储西向汽车信息，eastCarsQueue 存储东向汽车信息。 - 然后，每隔一定的时间（lightGreenSeconds），南北向和东西向的汽车交替通过路口，汽车对象出队列，此时根据 汽车出现时间 showTime，信号量数组 roadMutex，计时器 timeCounter 三者之间的关系 计算出汽车实际通过路口的时间 getActualPassTime。
三、数据结构
3.1 交通灯Light类
交通灯的特征：
- 所在方向（direction ∈ {North, South, West, East} ）
- 显示时间（seconds）
- 显示颜色（color∈{Red, Green}）
/**
* Created by shuai
* on 2017/3/5.
*/
public class Light {
private int direction; // 灯的方向：东西，南北
private int color; // 灯的颜色：红，绿
private int seconds; // 交通灯持续时间
public Light(int direction, int color, int seconds) {
this.direction = direction;
this.color = color;
this.seconds = seconds;
}
public int getDirection() {
return direction;
}
public int getColor() {
return color;
}
public void setColor(int color) {
this.color = color;
}
public String toString() {
return "交通灯方向：" + direction + "\t" + "状态：" + color + "\t" + "颜色持续时间：" + seconds;
}
}
3.2 汽车Car类
汽车包含的特征有：
- 车牌号（id）Java 随机生成 String 汽车车牌号
- 行驶方向（direction ∈ {North, South, West, East} ）
- 车辆出现在十字路口的时间（showTime）
import java.util.Random;
/**
* Created by shuai
* on 2017/3/5.
*/
public class Car {
private String id; // 车牌号
private int direction; // 行驶方向
private int showTime; // 出现时间，到达十字路口的时间
public Car(int direction, int showTime) {
this.id = generateCarID(); // Car内自带的随机生成车牌号的方法，随着车辆初始化随机生成一个车牌号
this.direction = direction;
this.showTime = showTime;
}
public String getId() {
return id;
}
public int getDirection() {
return direction;
}
public int getShowTime() {
return showTime;
}
// 重载toString方法，打印车辆信息
public String toString() {
String direct;
switch (direction) {
case 0:
direct = "North";
break;
case 1:
direct = "South";
break;
case 2:
direct = "West";
break;
case 3:
direct = "East";
break;
default:
direct = "";
}
return id + "\t" + direct + "\t" + showTime;
}
// 车牌号的组成一般为：省份+地区代码+5位数字/字母
private static String generateCarID() {
char[] provinceAbbr = { // 省份简称 4+22+5+3
'京', '津', '沪', '渝',
'冀', '豫', '云', '辽', '黑', '湘', '皖', '鲁', '苏', '浙', '赣',
'鄂', '甘', '晋', '陕', '吉', '闽', '贵', '粤', '青', '川', '琼',
'宁', '新', '藏', '桂', '蒙',
'港', '澳', '台'
};
String alphas = "QWERTYUIOPASDFGHJKLZXCVBNM1234567890"; // 26个字母 + 10个数字
Random random = new Random();
String carID = "";
// 省份+地区代码+· 如 湘A·
carID += provinceAbbr[random.nextInt(34)]; // 注意：分开加，因为加的是2个char
carID += alphas.charAt(random.nextInt(26)) + "·";
// 5位数字/字母
for (int i = 0; i < 5; i++) {
carID += alphas.charAt(random.nextInt(36));
}
return carID;
}
}
四、算法设计
4.1 创建问题情景
设置南北向和东西向的交通灯，再随机生成任意数量的汽车。
// 南北向和东西向各设置一个交通灯就可以
Light northLight = new Light(North, Green, 0); // 方向，颜色，时间
Light eastLight = new Light(East, Red, 0); // 时间不用指定，因为后面有timeCounter
// 随机生成车辆信息
Car[] cars = new Car[carNumber];
Random random = new Random();
for (int i = 0; i < carNumber; i++) { // foreach不行，因为是数组初始化
cars[i] = new Car(random.nextInt(4), random.nextInt(timeRange) + 1);
// new Car(int direction, int showTime) 随机生成车辆朝向和出现时间，时间范围[1, timeRange]
// 在Car构造函数内部随机生成了车辆ID，即车牌号
}
4.2. 数据预处理
将汽车按照 direction 存入到 4 个方向队列中，存储顺序按照汽车出现时间 showTime 由小到大，稳定不稳定的排序都可以，因为同时到达路口的汽车没有时间上先后之分，而这些同时到达的汽车正是我们需要调度的对象。
- 汽车对象按照出现时间排序，因为出现时间是随机指定的。
// cars数组按车辆出现时间排序的
sortCarsByShowTime(cars);
private void sortCarsByShowTime(Car cars[]) {
// copy车辆信息
Car[] tmpCars = new Car[carNumber];
System.arraycopy(cars, 0, tmpCars, 0, cars.length);
// 对车辆信息按照出现时间排序
int index = 0; // 遍历cars数组
for (int i = 1; i <= timeRange; i++) { // showTime递增
for (Car c : tmpCars) { // 遍历tmpCars
if (c.getShowTime() == i) { // 找到showTime=i的车辆
cars[index] = c;
index++;
}
}
}
}
- 汽车按照 direction 进入 4 个方向队列。
// 车辆信息进队列
Queue<Car> northCarsQueue = new LinkedBlockingQueue<>();
Queue<Car> southCarsQueue = new LinkedBlockingQueue<>();
Queue<Car> westCarsQueue = new LinkedBlockingQueue<>();
Queue<Car> eastCarsQueue = new LinkedBlockingQueue<>();
for (Car c : cars) {
switch (c.getDirection()) {
case North:
northCarsQueue.add(c);
break;
case South:
southCarsQueue.add(c);
break;
case West:
westCarsQueue.add(c);
break;
case East:
eastCarsQueue.add(c);
break;
default:
break;
}
}
// 集合方式遍历，元素不会被移除
System.out.println("生成的车辆信息");
for (Car c : northCarsQueue) System.out.println(c);
for (Car c : southCarsQueue) System.out.println(c);
for (Car c : westCarsQueue) System.out.println(c);
for (Car c : eastCarsQueue) System.out.println(c);
System.out.println();
4.3 信号量机制
某一时刻的道路作为互斥信号量，影响体现在汽车实际通过十字路口的时间。
实际经过时间 >= 到达路口时间
互斥信号量定义
// 一条路双向车道，设置2个信互斥信号量集
int[] northMutex = new int[100];
int[] southMutex = new int[100];
int[] westMutex = new int[100];
int[] eastMutex = new int[100];
/**
* 获取车辆实际经过十字路口的时间
*
* @param roadMutex 道路互斥信号量集
* @param showTime 汽车出现时间
* @param timeCounter 计时器
* @return actualPassTime 车辆实际通过路口的时间
*/
private int getActualPassTime(int[] roadMutex, int showTime, int timeCounter) {
// timeCounter-1 确保timeLower落在正确范围内，取商运算
int timeLower = (timeCounter - 1) / lightGreenSeconds * lightGreenSeconds + 1; // 时间下界
// 汽车出现时间 < timeLower 重置出现时间，说明汽车等待到下一个绿灯
if (showTime <= timeLower) showTime = timeLower;
if (roadMutex[showTime] == 0) { // 该时刻的道路资源未被占用，可通过，直接返回showTime，并将roadMutex[showTime]置1
roadMutex[showTime] = 1;
return showTime;
} else { // 这一时刻的道路资源已被占用了，不可通过
int sum = 0;
for (int i = showTime; i <= timeCounter; i++) { // 查询roadMutex数组，看自己排在队列的第几位
if (roadMutex[i] == 1) { // =1 表示showTime之后的时刻的道路资源被占用
sum++;
}
}
roadMutex[showTime + sum] = 1; // 表示该车占用该一时刻的道路资源
return showTime + sum; // 返回实际通过时间
}
}
- 通过 timeCounter 求得绿灯刚开始亮的时间 timeLower（边界值划限）；
- 如果 showTime <= timeLower，说明汽车已经等到这一个绿灯了，即该汽车没有在其出现时间所在的绿灯时间范围内通过路口，所以更新其 showTime 为 timeLower，这种情况下会使很多不同 showTime 的车辆出现时间都设为 timeLower，不过有两个原因可以证明这也是合理的：
① 上一个交通灯没有通过的车陆陆续续（即 showTime 不同）到达路口，因为都在这个路口等，所以到下一个交通灯的时候 showTime 就一样了；
② showTime 一样不会影响其先后关系，因为车辆已经入队列了，先后关系确定了。 - roadMutex[showTime] == 0 说明这一时段的道路未被占用，可以通过，该车辆通过的时候，设置 roadMutex[showTime] = 1，其他车辆在这一时刻不可同过，除非是反向的车辆，因为是双向车道，比如东向车在走，西向的也可以走；
- roadMutex[showTime] != 0 说明这一时段的道路已被占用，此时查询 roadMutex 数组，看自己排在队列的第几位，然后得到实际通过时间。
4.4 解决问题
- 南北向为绿灯时，东西向为红灯，南北向的汽车开始调度时，东西向的汽车等待，南北向的汽车出队列；
- 东西向为绿灯时，南北向为红灯，南北向的汽车停止出队列，东西向的汽车开始调度；
- 这个过程循环进行，直到所有的车辆通过了十字路口。
int lightGreen; // 绿灯持续时间，用这个变量，是因为绿灯持续时间是慢慢减少为0的
int timeCounter = 0; // 时间计数器，与车辆实际通过路口的时间有关
// 一条路双向车道，设置2个互斥信号量集
int[] northMutex = new int[100];
int[] southMutex = new int[100];
int[] westMutex = new int[100];
int[] eastMutex = new int[100];
// 4个String存储不同方向的车辆通过信息
String northPassInfo = "";
String southPassInfo = "";
String westPassInfo = "";
String eastPassInfo = "";
// 只要还有车，队列就执行
while (!northCarsQueue.isEmpty() || !southCarsQueue.isEmpty() ||
!westCarsQueue.isEmpty() || !eastCarsQueue.isEmpty()) {
// 打印时间段信息 如 1----10s
System.out.print((timeCounter + 1) + "----" + (timeCounter + lightGreenSeconds) + "s\t");
// 调度车辆
if (northLight.getColor() == Green) { // 南北向车辆通过十字路口
System.out.println("南北向绿灯亮\n");
lightGreen = lightGreenSeconds;
while (lightGreen-- > 0) { // 每经过一辆车花费时间为1，每花费1的时间最多通过2辆车，因为是双向的
timeCounter++; // timeCounter与车辆实际通过路口的时间有关
northPassInfo += passOneCarInfo(northCarsQueue, northMutex, timeCounter);
southPassInfo += passOneCarInfo(southCarsQueue, southMutex, timeCounter);
}
// 打印南北向车辆通过信息
System.out.println(northPassInfo);
System.out.println(southPassInfo);
northPassInfo = ""; // 重置String，循环使用
southPassInfo = "";
northLight.setColor(Red); // 交通灯颜色转换
eastLight.setColor(Green);
} else { // 东西向车辆通过十字路口
System.out.println("东西向绿灯亮\n");
lightGreen = lightGreenSeconds;
while (lightGreen-- > 0) { // 每经过一辆车花费时间为1
timeCounter++;
westPassInfo += passOneCarInfo(westCarsQueue, westMutex, timeCounter);
eastPassInfo += passOneCarInfo(eastCarsQueue, eastMutex, timeCounter);
}
// 打印东西向车辆通过信息
System.out.println(westPassInfo);
System.out.println(eastPassInfo);
westPassInfo = ""; // 重置String，循环使用
eastPassInfo = "";
eastLight.setColor(Red); // 交通灯颜色转换
northLight.setColor(Green);
}
}
通过一辆车 passOneCarInfo
- 输出该车辆的信息和实际通过时间
- 该车辆出队列
// String存储一辆车的经过信息，便于后面结果的显示
private static String passOneCarInfo(Queue<Car> carsQueue, int[] roadMutex, int timeCounter) {
String passInfo = "";
if (!carsQueue.isEmpty()) {
Car car = carsQueue.peek();
if (car.getShowTime() <= timeCounter) { // 假定提前到了，在这一次绿灯亮一定可以穿行
passInfo = car.toString() + "----" + getActualPassTime(roadMutex, car.getShowTime(), timeCounter) + "\n";
carsQueue.remove(); // 满足条件，放行一辆车
}
}
return passInfo; // 车辆出现信息 + 车辆经过时间
}
4.5 测试
设定条件
private static final int timeRange = 20; // 模拟总时长
private static final int carNumber = 20; // 车辆总数
private static final int lightGreenSeconds = 10; // 交通灯显示绿色的时长
生成的车辆信息
车牌号 朝向 出现时间
湘U·EM7P6 North 3
赣T·5EYJA North 13
蒙A·2KX51 South 1
黑M·LPHN8 South 7
赣L·5TSL3 South 11
闽P·EWZMH South 11
津G·X1J69 West 2
青F·PXF6N West 12
苏C·L6Z7A West 12
宁A·NTC5J West 13
藏H·6VRJT West 15
浙W·FYWU7 West 15
皖V·2NPLA West 17
川U·LJSYS East 10
桂F·EJEYK East 12
赣S·GMB8C East 15
港J·08QVC East 16
港O·SR58D East 16
台E·1H5IJ East 18
蒙Y·YV5LD East 18
调度结果
1----10s 南北向绿灯亮
湘U·EM7P6 North 3----3
蒙A·2KX51 South 1----1
黑M·LPHN8 South 7----7
11----20s 东西向绿灯亮
津G·X1J69 West 2----11
青F·PXF6N West 12----12
苏C·L6Z7A West 12----13
宁A·NTC5J West 13----14
藏H·6VRJT West 15----15
浙W·FYWU7 West 15----16
皖V·2NPLA West 17----17
川U·LJSYS East 10----11
桂F·EJEYK East 12----12
赣S·GMB8C East 15----15
港J·08QVC East 16----16
港O·SR58D East 16----17
台E·1H5IJ East 18----18
蒙Y·YV5LD East 18----19
21----30s 南北向绿灯亮
赣T·5EYJA North 13----21
赣L·5TSL3 South 11----21
闽P·EWZMH South 11----22
五、界面设计
5.1 题目展示界面
5.2 交通信号灯模拟界面
动画设计：
-
车辆通过路口动画
控制图上蓝色和橙色矩形的移动表示车辆经过了十字路口，
矩形的内容用一个整数对（integer1, integer2）表示：
integer1：车辆出现在路口的时间（showTime）
integer2：车辆实际通过路口的时间（actualPassTime） -
交通灯颜色更迭动画
根据问题情景中设置的绿灯时间，东西向交通灯和南北向交通灯交替变为绿色。 -
时间计数动画
Start 左侧的按钮记录模拟时间的变化。
5.3 调度结果界面
