大家好，欢迎来到IT知识分享网。
先到先服务（FCFS）最短作业优先调度算法（SJF）
#include <iostream>
#include <queue>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 1000;//假设能够容纳的进程最多的个数
struct Process
{
int pos; //代表第几个输入的进程
char Process_name[50]; //进程名字，默认最长长度占用50字符
double Arrival_time; //进程到达时间
double Service_time; //服务时间 进程所需要的时间
double Start_time; //服务开始时间
double End_time; //服务结束的时间
double Turnaround_time; //周转时间 进程结束的时间-进程到达时间
double Weight_Turnaround_time; //带权周转时间 周转时间 / 服务时间
bool operator < (const Process &a)const
{
if(Service_time == a.Service_time)
return Arrival_time > a.Arrival_time;
return Service_time > a.Service_time;
}
}process[MAXN];
int n; //进程的数量！
bool cmp1(Process &a,Process &b)
{
return a.Arrival_time < b.Arrival_time;
}
void Init()
{
printf("请输入进程的数量：");
scanf("%d",&n);
for(int i = 0;i < n;i ++)
{
cout<<"请输入第"<<i+1<<"个进程的名字 到达时间 服务时间"<<endl;
scanf("%s",process[i].Process_name);
scanf("%lf",&process[i].Arrival_time);
scanf("%lf",&process[i].Service_time);
process[i].pos = i;
}
}
void Solve_FCFS()
{
/*
先到先服务算法：是第一个排队，谁就先被执行，在执行过程中，不会中断他，当别人想要进入内存被执行，那么只能在后面排队
*/
printf("先到先服务算法\n");
sort(process,process+n,cmp1);
printf("进程的运行顺序为:\n");
printf("%s",process[0].Process_name);
for(int i = 1;i < n;i ++)
printf("-->%s",process[i].Process_name);
printf("\n");
double time = max(0.0,process[0].Arrival_time);//记录总的时间！
for(int i = 0;i < n;i ++)
{
process[i].Start_time = time; //更新开始时间
process[i].End_time = time + process[i].Service_time; //更新结束时间
process[i].Turnaround_time = process[i].End_time - process[i].Arrival_time; //更新周转时间
process[i].Weight_Turnaround_time = process[i].Turnaround_time / process[i].Service_time; //更新带权周转时间
time += process[i].Service_time;
if(i != n-1) //当这时的结束时间小于下一个进程的到达时间的话，就要重新更新time
time = max(time,process[i+1].Arrival_time);
}
printf("name\tarrive_time\tservice_time\tstart_time\tend_time\tTA_time\tWTA_time\n");
for(int i= 0;i < n;i ++)
printf("%s\t%.2lf\t\t%.2lf\t\t%.2lf\t\t%.2lf\t\t%.2lf\t%.2lf\n",process[i].Process_name,process[i].Arrival_time,process[i].Service_time,process[i].Start_time,process[i].End_time,process[i].Turnaround_time,process[i].Weight_Turnaround_time);
// for(int i= 0;i < index;i ++)
// cout<<ans[i].Process_name<<"\t"<<ans[i].Arrival_time<<"\t\t"<<ans[i].Service_time<<"\t\t"<<ans[i].Start_time<<"\t\t"<<ans[i].End_time<<endl;
}
void Solve_SJF()
{
/*
最短作业优先调度算法：进程的时间长短作为优先级，进程时间越短，优先级越高
寻找就绪队列中，进程时间最短的先执行，当存在多个长度相同的短作业时，按照提交时间的先后顺序进行调度
*/
printf("最短作业优先调度算法:\n");
priority_queue<Process> que;
sort(process,process+n,cmp1);
bool vis[MAXN]; //表示这个进程有没有在完成，完成使用true表示
Process ans[MAXN];
double time = max(0.0,process[0].Arrival_time);int index = 0;
memset(vis,false,sizeof(vis));
//首先将第一个放到优先队列中！
que.push(process[0]);vis[process[0].pos] = 1;
for(int i = 0;i < n;i ++)
{
while(!que.empty())
{
Process temp = que.top(); que.pop();
temp.Start_time = time;temp.End_time = time + temp.Service_time;temp.Turnaround_time = temp.End_time - temp.Arrival_time;
temp.Weight_Turnaround_time = temp.Turnaround_time / temp.Service_time;
for(int j = 0;j< n;j ++)
if(!vis[process[j].pos] && process[j].Arrival_time <= temp.End_time)
{
vis[process[j].pos] = 1;
que.push(process[j]);
}
time += temp.Service_time; //这里面的时间都是有联系的，所以不用再次更新time
ans[index++] = temp; //将顺序存储到最终的答案序列中
}
bool flag = false; //判断是否所有的进程都已经完成
for(int j = 0;j < n;j ++)
if(!vis[process[j].pos])
{
que.push(process[j]);//将一个时间最靠前的添加到队列中
time = process[j].Arrival_time; //这里就要更新time了，因为这里的时间和上面的有些脱节！
flag = true;break;
}
if(!flag) break;
}
printf("进程的运行顺序为：\n");
printf("%s",ans[0].Process_name);
for(int i = 1;i < n;i ++)
printf("-->%s",ans[i].Process_name);
printf("\n");
printf("name\tarrive_time\tservice_time\tstart_time\tend_time\tTA_time\tWTA_time\n");
for(int i= 0;i < n;i ++)
printf("%s\t%.2lf\t\t%.2lf\t\t%.2lf\t\t%.2lf\t\t%.2lf\t%.2lf\n",ans[i].Process_name,ans[i].Arrival_time,ans[i].Service_time,ans[i].Start_time,ans[i].End_time,ans[i].Turnaround_time,ans[i].Weight_Turnaround_time);
// for(int i= 0;i < index;i ++)
// cout<<ans[i].Process_name<<"\t"<<ans[i].Arrival_time<<"\t\t"<<ans[i].Service_time<<"\t\t"<<ans[i].Start_time<<"\t\t"<<ans[i].End_time<<endl;
}
int main()
{
Init();
Solve_FCFS();
Solve_SJF();
return 0;
}
/*
3
a 1 4
b 5 2
c 2 5
4
a 0 7
b 2 4
c 4 1
d 5 4
*/
高响应比优先调度
#include <iostream>
#include <queue>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 1000;
int n;
struct Process
{
int pos; //代表第几个输入的进程
char Process_name[50]; //进程名字，默认最长长度占用50字符
double Arrival_time; //进程到达时间
double Service_time; //服务时间 进程所需要的时间
double Start_time; //服务开始时间
double End_time; //服务结束的时间
double Priority; //优先级
bool operator < (const Process &a)const
{
if(Priority == a.Priority)
return Arrival_time > a.Arrival_time;
return Priority < a.Priority;
}
}process[MAXN];
void Init()
{
printf("请输入进程的数量：");
scanf("%d",&n);
for(int i = 0;i < n;i ++)
{
cout<<"请输入第"<<i+1<<"个进程的名字 到达时间 服务时间"<<endl;
scanf("%s",process[i].Process_name);
scanf("%lf",&process[i].Arrival_time);
scanf("%lf",&process[i].Service_time);
process[i].pos = i;process[i].Priority = 0;
}
}
bool cmp1(Process &a,Process &b)
{
return a.Arrival_time < b.Arrival_time;
}
void Solve_HRRN()
{
/*
高响应比优先调度:每次都计算作业的优先级，随着作业等待时间的变长，优先级不断增加
优先级 = (作业已等待的时间+作业服务时间) / 作业服务时间
那么每完成一个任务，我们就要更新一次优先级
*/
printf("高响应比优先调度:\n");
priority_queue<Process> que;
sort(process,process+n,cmp1);
bool vis[MAXN]; //表示这个进程有没有在完成，完成使用true表示
Process ans[MAXN];
double time = max(0.0,process[0].Arrival_time);int index = 0;
memset(vis,false,sizeof(vis));
//首先将第一个放到优先队列中！
que.push(process[0]);vis[process[0].pos] = 1;
for(int i = 0;i < n;i ++)
{
while(!que.empty())
{
Process temp = que.top(); que.pop();
temp.Start_time = time;temp.End_time = time + temp.Service_time;
for(int j = 0;j < n;j ++)
if(!vis[process[j].pos] && process[j].Arrival_time <= temp.End_time)
{
vis[process[j].pos] = 1;
que.push(process[j]);
}
time += temp.Service_time; //这里面的时间都是有联系的，所以不用再次更新time
ans[index++] = temp; //将顺序存储到最终的答案序列中
Process need[MAXN];int tot = 0;
while(!que.empty()) //首先将进程转移的need数组中
{
temp = que.top();que.pop();need[tot++] = temp;
}
for(int j = 0;j < tot;j ++) //更新后面的Priority
{
need[j].Priority = (time - need[j].Arrival_time + need[j].Service_time)/ need[j].Service_time;
que.push(need[j]);
}
}
bool flag = false; //判断是否所有的进程都已经完成
for(int j = 0;j < n;j ++)
if(!vis[process[j].pos])
{
que.push(process[j]);//将一个时间最靠前的添加到队列中
time = process[j].Arrival_time; //这里就要更新time了，因为这里的时间和上面的有些脱节！
flag = true;break;
}
if(!flag) break;
}
printf("进程的运行顺序为：\n");
printf("%s",ans[0].Process_name);
for(int i = 1;i < n;i ++)
printf("-->%s",ans[i].Process_name);
printf("\n");
printf("name\tarrive_time\tservice_time\tstart_time\tend_time\n");
for(int i= 0;i < index;i ++)
printf("%s\t%.2lf\t\t%.2lf\t\t%.2lf\t\t%.2lf\n",ans[i].Process_name,ans[i].Arrival_time,ans[i].Service_time,ans[i].Start_time,ans[i].End_time);
// for(int i= 0;i < index;i ++)
// cout<<ans[i].Process_name<<"\t"<<ans[i].Arrival_time<<"\t\t"<<ans[i].Service_time<<"\t\t"<<ans[i].Start_time<<"\t\t"<<ans[i].End_time<<endl;
}
int main()
{
Init();
Solve_HRRN();
return 0;
}抢占式优先比调度算法
#include <iostream>
#include <queue>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 1000;
int n;
struct Process
{
int pos; //代表第几个输入的进程
char Process_name[50]; //进程名字，默认最长长度占用50字符
double Arrival_time; //进程到达时间
double Service_time; //服务时间 进程所需要的时间
double Start_time; //服务开始时间
double End_time; //服务结束的时间
double Priority; //优先权，这里面的优先级权是不能修改的！！！
bool operator < (const Process &a)const
{
if(Priority == a.Priority)
return Arrival_time > a.Arrival_time;
return Priority < a.Priority;
}
}process[MAXN];
void Init()
{
printf("请输入进程的数量：");
scanf("%d",&n);
for(int i = 0;i < n;i ++)
{
cout<<"请输入第"<<i+1<<"个进程的名字 到达时间 服务时间 优先权"<<endl;
scanf("%s",process[i].Process_name);
scanf("%lf",&process[i].Arrival_time);
scanf("%lf",&process[i].Service_time);
scanf("%lf",&process[i].Priority);
process[i].pos = i;
}
}
bool cmp1(Process &a,Process &b)
{
return a.Arrival_time < b.Arrival_time;
}
void Solve_PPS()
{
/*
抢占式优先权调度:如果当前进程在执行时，如果后面出现了一个优先级更高的进程，我们就要暂时停止这个进程，先执行优先权高的程序！！
*/
printf("抢占式优先权调度:\n");
priority_queue<Process> que;
sort(process,process+n,cmp1);
bool vis[MAXN]; //表示这个进程有没有在完成，完成使用true表示
Process ans[MAXN];
double time = max(0.0,process[0].Arrival_time);int index = 0;
memset(vis,false,sizeof(vis));
//首先将第一个放到优先队列中！
que.push(process[0]);vis[process[0].pos] = 1;
for(int i = 0;i < n;i ++)
{
while(!que.empty())
{
bool ok = false;
Process temp = que.top();que.pop();
//在temp的服务时间中，如果有新的优先权高的进程出现，那么就先执行优先权更高的进程，暂停这一段进程，并且更新这个进程所需要的时间等等
temp.Start_time = time;temp.End_time = time + temp.Service_time;
for(int j = 0;j < n;j ++)
{//在当前优先队列中的优先权永远是要小于当前执行的优先权的，那么我们只需要判断vis为false的就可以了！
if(!vis[process[j].pos] && process[j].Priority > temp.Priority && process[j].Arrival_time < temp.End_time)
{
ok = true;
vis[process[j].pos] = 1;
que.push(process[j]);
temp.End_time = process[j].Arrival_time;
ans[index++] = temp;
temp.Service_time = time + temp.Service_time - temp.End_time;//更新当前的服务时间
que.push(temp);
time = process[j].Arrival_time;
break;
}
}
for(int j = 0;j < n;j ++)//将这段时间内时间已经满足要求，但是优先权不是很高的添加到队列中！
{
if(!vis[process[j].pos] && process[j].Arrival_time <= temp.End_time)
{
vis[process[j].pos] = 1;
que.push(process[j]);
}
}
if(!ok) //表示这个执行过程中没有打断的其它进程到来
{
time += temp.Service_time;
ans[index++] = temp;
}
}
bool flag = false; //判断是否所有的进程都已经完成
for(int j = 0;j < n;j ++)
if(!vis[process[j].pos])
{
vis[process[j].pos] = 1;
que.push(process[j]);//将一个时间最靠前的添加到队列中
time = process[j].Arrival_time; //这里就要更新time了，因为这里的时间和上面的有些脱节！
flag = true;break;
}
if(!flag) break;
}
printf("进程的运行顺序为：\n");
printf("%s",ans[0].Process_name);
for(int i = 1;i < index;i ++)
printf("-->%s",ans[i].Process_name);
printf("\n");
printf("name\tarrive_time\tservice_time\tstart_time\tend_time\n");
for(int i= 0;i < index;i ++)
printf("%s\t%.2lf\t\t%.2lf\t\t%.2lf\t\t%.2lf\n",ans[i].Process_name,ans[i].Arrival_time,ans[i].Service_time,ans[i].Start_time,ans[i].End_time);
//for(int i= 0;i < index;i ++)
// cout<<ans[i].Process_name<<"\t"<<ans[i].Arrival_time<<"\t\t"<<ans[i].Service_time<<"\t\t"<<ans[i].Start_time<<"\t\t"<<ans[i].End_time<<endl;
}
int main()
{
Init();
Solve_PPS();
return 0;
}
/*
5
1 1 10 80
2 11 15 20
3 21 10 50
4 31 10 120
5 41 10 100
3
A 0 5 1
B 2 2 2
C 3 4 3
*/时间片轮转调度算法
#include <iostream>
#include <queue>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 1000;//假设能够容纳的进程最多的个数
struct Process
{
int pos; //代表第几个输入的进程
char Process_name[50]; //进程名字，默认最长长度占用50字符
double Arrival_time; //进程到达时间
double Service_time; //服务时间 进程所需要的时间
double Start_time; //服务开始时间
double End_time; //服务结束的时间
double Turnaround_time; //周转时间 进程结束的时间-进程到达时间
double Weight_Turnaround_time; //带权周转时间 周转时间 / 服务时间
}process[MAXN];
double every_time;
int n;
void Init()
{
printf("请输入时间片的时间:");
scanf("%lf",&every_time);
printf("请输入进程的数量：");
scanf("%d",&n);
for(int i = 0;i < n;i ++)
{
cout<<"请输入第"<<i+1<<"个进程的名字 到达时间 服务时间"<<endl;
scanf("%s",process[i].Process_name);
scanf("%lf",&process[i].Arrival_time);
scanf("%lf",&process[i].Service_time);
process[i].pos = i;
}
}
bool cmp1(const Process &a,const Process &b)
{
return a.Arrival_time < b.Arrival_time;
}
void Solve_TSRA()
{
/*
时间片轮转算法：
*/
printf("时间片轮转算法:\n");
queue<Process> que;
sort(process,process+n,cmp1);
bool vis[MAXN]; //表示这个进程有没有在完成，完成使用true表示
Process ans[MAXN];
double time = max(0.0,process[0].Arrival_time);int index = 0;
memset(vis,false,sizeof(vis));
que.push(process[0]);vis[process[0].pos] = 1;
for(int i = 0;i < n;i ++)
{
while(!que.empty())
{
Process temp = que.front(); que.pop();
temp.Start_time = time;
temp.End_time = temp.Service_time >= every_time ? time + every_time : time + temp.Service_time;
for(int j = 0;j < n;j ++)
if(!vis[process[j].pos] && process[j].Arrival_time <= temp.End_time)
{
vis[process[j].pos] = 1;
que.push(process[j]);
}
if(temp.Service_time > every_time)
{
temp.Service_time -= every_time;
que.push(temp);
time += every_time;
}
else
time += temp.Service_time; //这里面的时间都是有联系的，所以不用再次更新time
ans[index++] = temp; //将顺序存储到最终的答案序列中
}
bool flag = false; //判断是否所有的进程都已经完成
for(int j = 0;j < n;j ++)
if(!vis[process[j].pos])
{
que.push(process[j]);//将一个时间最靠前的添加到队列中
time = process[j].Arrival_time; //这里就要更新time了，因为这里的时间和上面的有些脱节！
flag = true;break;
}
if(!flag) break;
}
printf("进程的运行顺序为：\n");
printf("%s",ans[0].Process_name);
for(int i = 1;i < index;i ++)
printf("-->%s",ans[i].Process_name);
printf("\n");
printf("name\tarrive_time\tservice_time\tstart_time\tend_time\n");
for(int i= 0;i < index;i ++)
printf("%s\t%.2lf\t\t%.2lf\t\t%.2lf\t\t%.2lf\n",ans[i].Process_name,ans[i].Arrival_time,ans[i].Service_time,ans[i].Start_time,ans[i].End_time);
// for(int i= 0;i < index;i ++)
// cout<<ans[i].Process_name<<"\t"<<ans[i].Arrival_time<<"\t\t"<<ans[i].Service_time<<"\t\t"<<ans[i].Start_time<<"\t\t"<<ans[i].End_time<<endl;
}
int main()
{
Init();
Solve_TSRA();
return 0;
}写在后面
只是单纯的模拟实现，如果有错误，感谢大家的指正
一学期的操作系统实验，上机时间只有周六周天两天，写给我那三流院校计算机学院的樊院长，那剩下的只能在课下找时间完成，这个作为第一个题用了大约半天多的时间，主要是最短作业优先的写完了之后后面的都是和最短作业优先的方法很是类似了，只需要更改一下循环里面的函数就可以了
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/23062.html
