操作系统进程调度算法（先来先服务，短作业优先算法（SJF））linux下（附源码）

先来先服务算法（FCFS）

FCFS是最简单的调度算法，既可以用作作业调度，也可以用作进程调度

这种算法优先考虑系统中等待时间最长的作业（进程），而不管作业所需执行时间长短，

做法是从后备队列中选择几个最先进入该队列的作业，将它们调入内存，为它们分配资源和创建进程，然后放入就绪队列

进程调度中使用此算法时，每次都从就绪的进程队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行，该进程会一直运行到完成或者因发生某事件而阻塞后，进程调度程序才会把处理机分配给其他进程

先来先服务(FCFS)调度算法是一种最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。
­­­­短作业优先算法（SJF），
由于在实际情况中短作业（进程）所占比例很大，为了让它们比长作业优先执行，就有了此算法。
SJF顾名思义以作业长短来确定优先级，作业越短优先级越高，作业的长短用作业所需的运行时间来衡量，此算法一样也可以用做进程调度，它将从外存的作业后备队列中选择若干个估计运行时间最短的作业，优先将它们调入内存运行。
SJF调度算法也存在不容忽视的缺点：该算法对长作业不利，如作业C的周转时间由10增至16，其带权周转时间由2增至3.1。更严重的是，如果有一长作业(进程)进入系统的后备队列(就绪队列)，由于调度程序总是优先调度那些(即使是后进来的)短作业(进程)，将导致长作业(进程)长期不被调度。该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业(进程)会被及时处理。由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
struct Node {
 char name;
 int Tarrive;//到达时间
 int Tservice;//服务时间
 int Tsurplus;//剩余时间
 int Tstart;//开始时间
 int Taccomplish;//完成时间
 int prio;//优先级---数字越大优先级越高
 int if_finish;//进程是否完成
 int num;//进程个数
}job[10];
//按到达时间排序
void Arrive_sort(int num)
{
 int temp1, temp2, temp3;
 for (int i = 0; i < num; i++)
 {
  for (int j = i + 1; j < num; j++)
  {
   if (job[i].Tarrive > job[j].Tarrive)
   {
    temp1 = job[j].name;
    job[j].name = job[i].name;
    job[i].name = temp1;
    temp2 = job[j].Tarrive;
    job[j].Tarrive = job[i].Tarrive;
    job[i].Tarrive = temp2;
    temp3 = job[j].Tservice;
    job[j].Tservice = job[i].Tservice;
    job[i].Tservice = temp3;
   }
  }
 }
}
//按服务时间排序
void Service_sort(int num)
{
 int temp1, temp2, temp3;
 for (int i = 1; i < num; i++)
 {
  for (int j = i + 1; j < num; j++)
  {
   if (job[i].Tservice > job[j].Tservice)
   {
    temp1 = job[j].name;
    job[j].name = job[i].name;
    job[i].name = temp1;
    temp2 = job[j].Tarrive;
    job[j].Tarrive = job[i].Tarrive;
    job[i].Tarrive = temp2;
    temp3 = job[j].Tservice;
    job[j].Tservice = job[i].Tservice;
    job[i].Tservice = temp3;
   }
  }
 }
}
//按优先级排序
void Priority_sort(int num)//按优先级减小排序
{
 int temp1, temp2, temp3, temp4;
 for (int i = 1; i < num; i++)
 {
  for (int j = i + 1; j < num; j++)
  {
   if (job[i].prio < job[j].prio)
   {
    temp1 = job[j].name;
    job[j].name = job[i].name;
    job[i].name = temp1;
    temp2 = job[j].Tarrive;
    job[j].Tarrive = job[i].Tarrive;
    job[i].Tarrive = temp2;
    temp3 = job[j].Tservice;
    job[j].Tservice = job[i].Tservice;
    job[i].Tservice = temp3;
    temp4 = job[j].prio;
    job[j].prio = job[i].prio;
    job[i].prio = temp3;
   }
  }
 }
}
//如果到达时间相等，服务时间按从小到大排序
void Arrive_Short_sort(int num)
{
 int temp1, temp2, temp3;
 for (int i = 0; i < num; i++)
 {
  for (int j = i + 1; j < num; j++)
  {
   if (job[i].Tarrive >= job[j].Tarrive)
   {
    if (job[i].Tarrive > job[j].Tarrive)
    {
     temp1 = job[j].name;
     job[j].name = job[i].name;
     job[i].name = temp1;
     temp2 = job[j].Tarrive;
     job[j].Tarrive = job[i].Tarrive;
     job[i].Tarrive = temp2;
     temp3 = job[j].Tservice;
     job[j].Tservice = job[i].Tservice;
     job[i].Tservice = temp3;
    }
    else
    {
     if (job[i].Tservice > job[j].Tservice)
     {
      temp1 = job[j].name;
      job[j].name = job[i].name;
      job[i].name = temp1;
      temp2 = job[j].Tarrive;
      job[j].Tarrive = job[i].Tarrive;
      job[i].Tarrive = temp2;
      temp3 = job[j].Tservice;
      job[j].Tservice = job[i].Tservice;
      job[i].Tservice = temp3;
     }
    }
   }
  }
 }
}
void fcfs(int num)//先来先服务
{
 for (int i = 0; i < num; i++)
 {
  job[i].Tstart = job[i - 1].Taccomplish;//上一个作业结束时间
  if (job[i].Tstart < job[i].Tarrive)
  {
   job[i].Tstart = job[i].Tarrive;
  }
  else
  {
   job[i].Tstart = job[i - 1].Taccomplish;
  }
  job[i].Taccomplish = job[i].Tstart + job[i].Tservice;
 }
}
void sjf(int num)//短作业优先
{
 Service_sort(num);
 for (int i = 0; i < num; i++)
 {
  job[i].Tstart = job[i - 1].Taccomplish;//上一个作业结束时间
  if (job[i].Tstart < job[i].Tarrive)//该作业的开始时间小于到达时间
  {
   job[i].Tstart = job[i].Tarrive;
  }
  else
  {
   job[i].Tstart = job[i - 1].Taccomplish;
  }
  job[i].Taccomplish = job[i].Tstart + job[i].Tservice;
 }
}
void RR(int num)//RR算法
{
 int q;
 cout << "请输入时间片长度：" << endl;
 cin >> q;
 int flag = 1;//标志队列中是否还有进程
 int finish_pro = 0;//完成的进程数
 cout << "进程名称\t" << "开始时间\t" << "运行时间\t" << "剩余服务时间\t" << "结束时间\t" << endl;
 int time;//记录当前时刻时间
 int c = 0;
 while (finish_pro < num)
 {
  flag = 0;//就绪队列里没进程
  for (int i = c; i < num; i++)
  {
   Arrive_sort(num);
   job[i].Tsurplus = job[i].Tservice;
   job[i].Tstart = job[i - 1].Taccomplish;//上一个作业结束时间
   if (job[i].Tstart < job[i].Tarrive)//该作业的开始时间小于到达时间
   {
    job[i].Tstart = job[i].Tarrive;
   }
   else
   {
    job[i].Tstart = job[i - 1].Taccomplish;
   }
   time = job[i].Tstart;
   if (job[i].if_finish == 1) continue;//该进程已完成
   else
   {
    if (job[i].Tsurplus <= q && time >= job[i].Tarrive)//未完成且少于一个时间片
    {
     flag = 1;
     time = time + job[i].Tsurplus;
     job[i].if_finish = 1;//该进程完成
     job[i].Taccomplish = time;
     cout  << job[i].name << "\t\t" << job[i].Taccomplish - job[i].Tsurplus << "\t\t" << job[i].Tsurplus << "\t\t" << 0 << "\t\t" << job[i].Taccomplish << endl;
     job[i].Tsurplus = 0;
    }
    else if (job[i].Tsurplus > q && time >= job[i].Tarrive)
    {
     flag = 1;
     time = time + q;
     job[i].Tsurplus -= q;
     job[i].Taccomplish = time;
     cout << job[i].name << "\t\t" << time - q << "\t\t" << q << "\t\t" << job[i].Tsurplus << "\t\t" << job[i].Taccomplish << endl;
     job[num].name = job[i].name;
     job[num].Tarrive = time;
     job[num].Tservice = job[i].Tsurplus;
     num++;
    }
    if (job[i].if_finish == 1) finish_pro++;//一个进程完成加一
   }
   c++;
  }break;
  if (flag == 0 && finish_pro < num)//没执行完且没进入就绪队列
  {
   for (int i = 0; i < num; i++)
   {
    if (job[i].if_finish == 0)
    {
     time = job[i].Tarrive;
     break;
    }
   }
  }
 } 
}
//输出
void print(int num)
{
 cout << "进程名" << "\t" << "到达时间" << "\t" << "服务时间" << "\t" << "完成时间" << endl;
 
 for (int i = 0; i < num; i++)
 {
  cout << job[i].name << "\t" << job[i].Tarrive << "\t\t" << job[i].Tservice << "\t\t" << job[i].Taccomplish << endl;
 }
}
void display(int num)
{
 int ch = 0;
 cout << "—————————————————————————" << endl;
 cout << "——————————1、FCFS算法 —————————" << endl;
 cout << "——————————2、SJF算法——————————" << endl;
 cout << "——————————3、RR算法 ——————————" << endl;
 cout << "——————————4、优先级算法 ————————" << endl;
 cout << "——————————5、退出 ———————————" << endl;
 cout << "—————————————————————————" << endl;
 do {
  cout << "请选择你想要的算法：" << endl;
  cin >> ch;
  switch (ch) {
  case 1:
   Arrive_sort(num);
   fcfs(num);
   print(num);
   break;
  case 2:
   //Arrive_Short_sort(num);
   sjf(num);
   print(num);
   break;
  case 3:
   RR(num);
   break;
  case 4:
   print(num);
   break;
  case 5:
   exit;
  default:
   cout << "输入错误，请重新输入！" << endl;
   break;
  }
 } while (ch != 5);
}
int main()
{
 int num;
 char jname;
 int arrive;
 int service;
 int accomplish;
 cout << "请输入进程个数：" << endl;
 cin >> num;
 for (int i = 0; i < num; i++)
 {
  cout << "请输入进程名、到达时间、服务时间" << endl;
  cin >> jname;
  job[i].name = jname;
  cin >> arrive;
  job[i].Tarrive = arrive;
  cin >> service;
  job[i].Tservice = service;
 }
 display(num);
 return 0;
}
  

 

  
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
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
  
81
  
82
  
83
  
84
  
85
  
86
  
87
  
88
  
89
  
90
  
91
  
92
  
93
  
94
  
95
  
96
  
97
  
98
  
99
  
100
  
101
  
102
  
103
  
104
  
105
  
106
  
107
  
108
  
109
  
110
  
111
  
112
  
113
  
114
  
115
  
116
  
117
  
118
  
119
  
120
  
121
  
122
  
123
  
124
  
125
  
126
  
127
  
128
  
129
  
130
  
131
  
132
  
133
  
134
  
135
  
136
  
137
  
138
  
139
  
140
  
141
  
142
  
143
  
144
  
145
  
146
  
147
  
148
  
149
  
150
  
151
  
152
  
153
  
154
  
155
  
156
  
157
  
158
  
159
  
160
  
161
  
162
  
163
  
164
  
165
  
166
  
167
  
168
  
169
  
170
  
171
  
172
  
173
  
174
  
175
  
176
  
177
  
178
  
179
  
180
  
181
  
182
  
183
  
184
  
185
  
186
  
187
  
188
  
189
  
190
  
191
  
192
  
193
  
194
  
195
  
196
  
197
  
198
  
199
  
200
  
201
  
202
  
203
  
204
  
205
  
206
  
207
  
208
  
209
  
210
  
211
  
212
  
213
  
214
  
215
  
216
  
217
  
218
  
219
  
220
  
221
  
222
  
223
  
224
  
225
  
226
  
227
  
228
  
229
  
230
  
231
  
232
  
233
  
234
  
235
  
236
  
237
  
238
  
239
  
240
  
241
  
242
  
243
  
244
  
245
  
246
  
247
  
248
  
249
  
250
  
251
  
252
  
253
  
254
  
255
  
256
  
257
  
258
  
259
  
260
  
261
  
262
  
263
  
264
  
265
  
266
  
267
  
268
  
269
  
270
  
271
  
272
  
273
  
274
  
275
  
276
  
277
  
278
  
279
  
280
  
281
  
282
  
283
  
284
  
285
  
286
  
287
  
288
  
289
  
290
  
291
  
292
  
293
  
294
  
295
  
296
  
297
  
298
 

文章来源: jianguo.blog.csdn.net，作者：坚果前端の博客，版权归原作者所有，如需转载，请联系作者。

原文链接：jianguo.blog.csdn.net/article/details/103678664