【JobScheduling】C++调度算法详解与实现

本文介绍: 作业调度算法是操作系统中的一个关键组成部分，它负责确定哪个作业应该在何时执行。这些算法的选择会直接影响系统的性能和用户体验。本博客将深入研究并分析三种经典的作业调度算法，为读者提供对这一主题的全面理解。在这之前，先需要了解作业调度中几个参数：提交时刻、执行时间、开始时刻、周转时间、周转系数等。设作业Jii12nJii12…n的提交时刻为tsit_{si}tsi，执行时间为trit_{ri}tri，作业完成时刻为toit_{oi}toi。

一、介绍

1.1 背景

作业调度是操作系统中一个关键的概念，它涉及到有效地分配和管理计算资源以执行任务。 作业调度算法在这一过程中起到关键作用，影响系统的性能和响应时间。

1.2 目的

本篇博客旨在深入了解三种常见的作业调度算法以及C++实现：先来先服务算法（FCFS）、短作业优先算法（SJN）和优先比算法。

1.3 作业调度算法简介

作业调度算法是操作系统中的一个关键组成部分，它负责确定哪个作业应该在何时执行。这些算法的选择会直接影响系统的性能和用户体验。本博客将深入研究并分析三种经典的作业调度算法，为读者提供对这一主题的全面理解。在这之前，先需要了解作业调度中几个参数：提交时刻、执行时间、开始时刻、周转时间、周转系数等。设作业

J

i

(

i

=

1

,

2

,

.

.

.

,

n

)

J_i(i=1,2,…,n)

$J_{i} (i = 1, 2, \dots, n)$ 的提交时刻为

t

s

i

t_{si}

$t_{s i}$ ，执行时间为

t

r

i

t_{ri}

$t_{r i}$ ，作业完成时刻为

t

o

i

t_{oi}

$t_{o i}$ 。

作业的周转时间 $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

$T_{i} = t_{o i} - t_{s i} ， i = 1, 2, \dots, 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

$W_{i} = T_{i} / t_{r i} ， i = 1, 2, \dots, n$
n个作业的平均周转时间T为：
$T=frac{1}nsum_{i=1}^{n}T_i T=n1i=1∑nTi$
n个作业的平均周转系数W为：
$W=frac{1}nsum_{i=1}^{n}W_i W=n1i=1∑nWi$

二、代码概览

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 + \frac{t _{o i} - s i}{t _{r} i}$

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;
  }
}