一、介绍
1.1 背景
作业调度是操作系统中一个关键的概念,它涉及到有效地分配和管理计算资源以执行任务。 作业调度算法在这一过程中起到关键作用,影响系统的性能和响应时间。
1.2 目的
本篇博客旨在深入了解三种常见的作业调度算法以及C++实现:先来先服务算法(FCFS)
、短作业优先算法(SJN)
和优先比算法
。
1.3 作业调度算法简介
作业调度算法是操作系统中的一个关键组成部分,它负责确定哪个作业应该在何时执行。这些算法的选择会直接影响系统的性能和用户体验。本博客将深入研究并分析三种经典的作业调度算法,为读者提供对这一主题的全面理解。在这之前,先需要了解作业调度中几个参数:提交时刻、执行时间、开始时刻、周转时间、周转系数等。设作业
J
i
(
i
=
1
,
2
,
.
.
.
,
n
)
J_i(i=1,2,…,n)
Ji(i=1,2,…,n)的提交时刻为
t
s
i
t_{si}
tsi,执行时间为
t
r
i
t_{ri}
tri,作业完成时刻为
t
o
i
t_{oi}
toi。
- 作业的周转时间
T
i
T_i
T
i
=
t
o
i
−
t
s
i
,
i
=
1
,
2
,
.
.
.
,
n
T_i=t_{oi}-t_{si},i=1,2,…,n
- 作业的周转系数
W
i
W_i
W
i
=
T
i
/
t
r
i
,
i
=
1
,
2
,
.
.
.
,
n
W_i=T_i/t_{ri},i=1,2,…,n
- n个作业的平均周转时间T为:
T
=
1
n
∑
i
=
1
n
T
i
T=frac{1}nsum_{i=1}^{n}T_i
- n个作业的平均周转系数W为:
W
=
1
n
∑
i
=
1
n
W
i
W=frac{1}nsum_{i=1}^{n}W_i
二、代码概览
2.1 结构体定义
在代码的起始部分,我们定义了一个结构体 content
用于存储作业的关键信息,包括提交时刻、执行时间等。这个结构体在整个代码中被广泛使用。
struct content
{
float s;
float j;
float k;
float v;
float z;
float d;
};
2.2 输出函数prt
prt
函数负责计算并输出平均周转时间和平均带权周转时间,同时以表格形式展示每个作业的提交、执行、开始、完成、周转和带权周转时间。
void prt(struct content a[],int n)
{
int i;
a[0].k=a[0].s;
a[0].v=a[0].k+a[0].j;
a[0].z=a[0].v-a[0].s;
a[0].d=a[0].z/a[0].j;
float sum=a[0].z,add=a[0].d;
for(i=1;i<n;i++)
{
if(a[i].s<=a[i-1].v) a[i].k=a[i-1].v;
else a[i].k=a[i].s;
a[i].v=a[i].k+a[i].j;
a[i].z=a[i].v-a[i].s;
a[i].d=a[i].z/a[i].j;
sum+=a[i].z;
add+=a[i].d;
}
printf("--------------------------------------------------");
printf("n平均周转时间:%.4f",sum/n);
printf("n平均带权周转时间:%.4fn",add/n);
printf("提交t执行t开始t完成t周转t带权周转n");
for(i=0;i<n;i++)
{
printf("%.2ft%.2ft%.2ft%.2ft%.2ft%.2fn",a[i].s,a[i].j,a[i].k,a[i].v,a[i].z,a[i].d);
}
printf("--------------------------------------------------");
printf("nn请输入接下来的操作:n");
}
2.3 调度算法函数fun1,fun2,fun3
代码实现了三种不同的作业调度算法,分别是先来先服务算法(fun1
)、短作业优先算法(fun2
)和优先比算法(fun3
)。这些函数接受作业数组和作业数量作为参数,并按照相应的算法进行排序和调度。
先来先服务算法是一种简单而直观的作业调度算法。 它按照作业提交的顺序执行,即先提交的作业先执行。在 fun1 函数中,我们按照作业提交时刻的先后顺序对作业数组进行排序,然后计算并输出相应的周转时间和带权周转时间。
void fun1(struct content a[],int n)
{
int i,j;
for(i=0;i<n-1;i++)
{
for(j=0;j<n-1-i;j++)
{
if(a[j].s>a[j+1].s)
{
float temp=a[j].s;
a[j].s=a[j+1].s;
a[j+1].s=temp;
temp=a[j].j;
a[j].j=a[j+1].j;
a[j+1].j=temp;
}
}
}
prt(a,n);
}
短作业优先算法是一种以执行时间为依据的调度算法,优先执行执行时间最短的作业。在 fun2 函数中,我们首先按照提交时刻对作业进行排序,然后再按照执行时间进行第二轮排序。最终,计算并输出各项时间指标。
void fun2(struct content a[],int n)
{
int i,j;
for(i=0;i<n-1;i++)
{
for(j=0;j<n-1-i;j++)
{
if(a[j].s>a[j+1].s)
{
float temp=a[j].s;
a[j].s=a[j+1].s;
a[j+1].s=temp;
temp=a[j].j;
a[j].j=a[j+1].j;
a[j+1].j=temp;
}
}
}
for(i=1;i<n-1;i++)
{
for(j=1;j<n-i;j++)
{
if(a[j].j>a[j+1].j)
{
float temp=a[j].s;
a[j].s=a[j+1].s;
a[j+1].s=temp;
temp=a[j].j;
a[j].j=a[j+1].j;
a[j+1].j=temp;
}
}
}
prt(a,n);
}
优先比算法是一种考虑优先级的调度算法,它计算每个作业的优先比,然后按照优先比的大小进行调度。在 fun3 函数中,我们首先按照提交时刻排序,然后计算每个作业的优先比,并按照优先比进行第二轮排序。最后,输出相关的时间指标。
R
P
(
响应比
)
=
1
+
t
o
i
−
s
i
t
r
i
RP(响应比)=1+frac{t_{oi}-{si}}{t_ri}
RP(响应比)=1+tritoi−si
void fun3(struct content a[],int n)
{
int i,j;
for(i=0;i<n-1;i++)
{
for(j=0;j<n-1-i;j++)
{
if(a[j].s>a[j+1].s)
{
float temp=a[j].s;
a[j].s=a[j+1].s;
a[j+1].s=temp;
temp=a[j].j;
a[j].j=a[j+1].j;
a[j+1].j=temp;
}
}
}
a[0].v=a[0].s+a[0].j;
for(i=1;i<n-1;i++)
{
for(j=1;j<n-i;j++)
{
if(((a[j].j-a[j].s+a[0].v)/a[j].j)<((a[j+1].j-a[j+1].s+a[0].v)/a[j+1].j))
{
float temp=a[j].s;
a[j].s=a[j+1].s;
a[j+1].s=temp;
temp=a[j].j;
a[j].j=a[j+1].j;
a[j+1].j=temp;
}
}
}
prt(a,n);
}
2.4 辅助函数 markzhu和 marks
这两个辅助函数用于用户交互。markzhu
用于主菜单,允许用户选择开始输入数据或退出程序。marks
则用于选择调度算法,提供用户选择先来先服务、短作业优先、优先比算法或返回上一级菜单的选项。
int markzhu()
{
int pd;
printf("1.开始输入数据n2.退出程序n");
while(1)
{
scanf("%d",&pd);
if(pd<1||pd>2) printf("n输入错误,请重新输入:");
else break;
}
return pd;
}
int marks()
{
int pd;
printf("请选择算法(输入序号):n1.先来先服务算法n2.短作业优先n3.优先比算法n4.返回n");
while(1)
{
scanf("%d",&pd);
if(pd<1||pd>4) printf("n输入错误,请重新输入:");
else break;
}
return pd;
}
2.5 main函数
int main()
{
while(1)
{
int pd=markzhu();
if(pd==1)
{
while(1)
{
struct content a[20];
int pd=marks(),i=0;
if(pd==4) break;
printf("输入0,0结束n");
do
{
printf("请输入第%d组数据(提交时刻,执行时间):",(i+1));
scanf("%f,%f",&a[i].s,&a[i].j);
i++;
}while(a[i-1].s!=0&&a[i-1].j!=0);
if(pd==1)
{
fun1(a,i-1);
break;
}
if(pd==2)
{
fun2(a,i-1);
break;
}
if(pd==3)
{
fun3(a,i-1);
break;
}
}
}
if(pd==2) break;
}
}
四、数据输入和测试
原文地址:https://blog.csdn.net/m0_73589720/article/details/135596857
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_56172.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!