简介
进程调度器是操作系统的一部分，决定了何时运行什么进程。它通常能够暂停一个运行中的进程，将它放回到运行队列当中，并运行一个新进程，我们把这样的调度器叫做抢占调度器。否则，它就是协同调度器。
不同环境的调度算法目标不同，因此需要针对不同环境来讨论调度算法。
短作业优先调度算法模拟
预期目标和分析
短作业优先，顾名思义，会按估计运行时间最短的顺序进行调度，当多个进程竞争资源时，我们会让需要运行时间最短的进程优先，如果有多个耗时最短的进程，那我们就运行最早进入的那一个。
在单处理机系统中，根据题目要求，我们需要预先输入各个进程的状态，例如名称、到达时间、需要时间、已用CPU时间等，随后我们根据给定的信息，求出执行的先后顺序、各个进程的到达运行开始顺序、周转时间等相关信息。
由于一个进程中存储了名称、运行时间等不同类型的信息，我们决定还是将其封装成一个单独的对象处理起来会更加直观一些。
此外，短作业优先调度虽然原理很简单，但是却不能用较为简单的排序一次做出答案，每个进程的执行顺序和其进程的开始时间、耗时都有关系，而且无法直接通过两两比较来确定优先。例如有三个进程其开始时间和耗时分别为：[0, 10], [3, 7], [9, 1]，在第一个任务运行期间第二第三个任务分别进入等待列表，但是当一号任务结束时，却是三号任务被优先执行，虽然二号先进入，但是仍然无法获得分配，如果此类事件再叠加嵌套问题就更复杂了，单纯的比较耗时和开始时间是无法解决这类问题的。所以我们最后还是选择使用模拟的方式来解决问题，维护一个优先队列，每当上一个任务执行完毕，我们就根据时间戳将等待着的任务加入队列，并从中取出最符合目标的进程对象，随后重复上述步骤。
为了避免处理下标，也为了符合先来后到的顺序，我们可以直接将所以任务以队列的形式存储，每次更新curTime后按照时间顺序，向优先队列中存入正在等待的任务。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
| package com.company;
import java.util.*;
public class sjf {
static class process {
String name;
int startTime;
int costTime;
public process(String name, int startTime, int costTime) {
this.name = name;
this.startTime = startTime;
this.costTime = costTime;
}
@Override
public String toString() {
return "process{" +
"name='" + name + '\'' +
", startTime=" + startTime +
", costTime=" + costTime +
'}';
}
}
public process[] getInput(Scanner scanner) {
System.out.println("需要添加的进程数量：");
int n = scanner.nextInt();
process[] list = new process[n];
System.out.println("接下请输入进程名称、开始时间、耗时。\n e.g. a 1 3");
for (int i = 1; i <= n; i++) {
System.out.println("请输入第" + i + "个进程相关信息");
String name = scanner.next();
int startTime = scanner.nextInt();
int costTime = scanner.nextInt();
list[i - 1] = new process(name, startTime, costTime);
}
return list;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
process[] list = new sjf().getInput(scanner);
Queue<process> queue = new ArrayDeque<>();
for (process x : list) queue.offer(x);
Arrays.sort(list, Comparator.comparingInt(o -> o.startTime));
PriorityQueue<process> pq = new PriorityQueue<>((o1, o2) -> o1.costTime == o2.costTime ? o1.startTime - o2.startTime : o1.costTime - o2.costTime);
int curTime = 0;
while (!pq.isEmpty() || !queue.isEmpty()) {
while (!queue.isEmpty() && queue.peek().startTime <= curTime) {
pq.offer(queue.poll());
}
if (pq.isEmpty()) {
curTime = queue.peek().startTime;
while (!queue.isEmpty() && queue.peek().startTime == curTime) {
pq.offer(queue.poll());
}
}
process curProcess = pq.poll();
System.out.println("处理任务：" + curProcess.name + "，开始时间：" + curTime + "，完成时间：" + (curTime + curProcess.costTime));
System.out.println(curProcess);
curTime += curProcess.costTime;
}
}
}
|
具体执行结果如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| 需要添加的进程数量：
4
接下请输入进程名称、开始时间、耗时。
e.g. a 1 3
请输入第1个进程相关信息
a 0 10
请输入第2个进程相关信息
b 1 3
请输入第3个进程相关信息
c 9 1
请输入第4个进程相关信息
d 100 200
处理任务：a，开始时间：0，完成时间：10
process{name='a', startTime=0, costTime=10}
处理任务：c，开始时间：10，完成时间：11
process{name='c', startTime=9, costTime=1}
处理任务：b，开始时间：11，完成时间：14
process{name='b', startTime=1, costTime=3}
处理任务：d，开始时间：100，完成时间：300
process{name='d', startTime=100, costTime=200}
|
时间片调度算法模拟
预期目标和分析
很容易的看出来，时间片调度算法就是当进程消耗完了时间片，就搁置当前任务，并进入到队列的下一个任务，我们可以直接将当前任务放到队尾，以便下次分配时间片，同时也保证了公平。总的来看，队列这一数据结构就很符合我们的需要。但是同时我们也要注意到随着任务的消化，仍然会有新的任务加入进来，所以要注意顺序。
代码
代码就更加简单了，如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
| package com.company;
import java.util.*;
public class timeSlice {
static class process{
String name;
int startTime;
int costTime;
int remainTime;
int times = 0;
public process(String name, int startTime, int costTime){
this.name = name;
this.startTime = startTime;
this.costTime = costTime;
remainTime = costTime;
times = 0;
}
}
public process[] getInput(Scanner scanner) {
System.out.println("需要添加的进程数量：");
int n = scanner.nextInt();
process[] list = new process[n];
System.out.println("接下请输入进程名称、开始时间、耗时。\n e.g. a 1 3");
for (int i = 1; i <= n; i++) {
System.out.println("请输入第" + i + "个进程相关信息");
String name = scanner.next();
int startTime = scanner.nextInt();
int costTime = scanner.nextInt();
list[i - 1] = new process(name, startTime, costTime);
}
return list;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
process[] list = new timeSlice().getInput(scanner);
System.out.println("请指定时间片的长度：");
int slice = scanner.nextInt();
Arrays.sort(list, Comparator.comparingInt(o -> o.startTime));
Queue<process> queue = new ArrayDeque<>();
for(process x: list) queue.offer(x);
Queue<process> taskQueue = new ArrayDeque<>();
int curTime = 0;
while(!queue.isEmpty() || !taskQueue.isEmpty()){
if(taskQueue.isEmpty()){
curTime = queue.peek().startTime;
while(!queue.isEmpty() && curTime == queue.peek().startTime){
taskQueue.offer(queue.poll());
}
}
process curProcess = taskQueue.poll();
curProcess.remainTime = curProcess.remainTime > slice? curProcess.remainTime - slice: 0;
curProcess.times++;
System.out.println("第" + curProcess.times + "次处理任务" + curProcess.name + "，开始时间：" + curTime +
"，结束时间：" + (curTime + Math.min(curProcess.remainTime, slice)) + "，目前还需时间：" + curProcess.remainTime);
curTime += Math.min(curProcess.remainTime, slice);
while(!queue.isEmpty() && queue.peek().startTime <= curTime){
taskQueue.offer(queue.poll());
}
if(curProcess.remainTime > 0) taskQueue.offer(curProcess);
}
}
}
|
执行情况如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 需要添加的进程数量：
2
接下请输入进程名称、开始时间、耗时。
e.g. a 1 3
请输入第1个进程相关信息
a 100 100
请输入第2个进程相关信息
b 130 100
请指定时间片的长度：
50
第1次处理任务a，开始时间：100，结束时间：150，目前还需时间：50
第1次处理任务b，开始时间：150，结束时间：200，目前还需时间：50
第2次处理任务a，开始时间：200，结束时间：200，目前还需时间：0
第2次处理任务b，开始时间：200，结束时间：200，目前还需时间：0
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 需要添加的进程数量：
2
接下请输入进程名称、开始时间、耗时。
e.g. a 1 3
请输入第1个进程相关信息
a 100 100
请输入第2个进程相关信息
b 300 100
请指定时间片的长度：
50
第1次处理任务a，开始时间：100，结束时间：150，目前还需时间：50
第2次处理任务a，开始时间：150，结束时间：150，目前还需时间：0
第1次处理任务b，开始时间：300，结束时间：350，目前还需时间：50
第2次处理任务b，开始时间：350，结束时间：350，目前还需时间：0
Process finished with exit code 0
|
总结
遇到类似问题，在时间充裕的情况下还是使用模拟会更加好一些。
在本文中，我使用了Java语言配合优先队列完成了SJF的调度策略，随后利用了队列自身的特性完成了时间片调度的实现，相关策略本身实现并不难，但是如果在执行任务的过程中不断有新的任务的加入，相关的处理逻辑就会更加复杂一些，尤其是部分操作的先后顺序需要把握好。此外如果单纯使用按照刻度的最小划分一秒一秒的去刷新检查模拟，对资源是一种巨大的浪费，虽然可以简化逻辑，但是不应当被使用。我们还是需要利用区间自带的开始结束时间，有选择的进行跳跃。
