动态规划-流水作业调度报告

一、问题描述给定n个作业，每个作业有两道工序，分别在两台机器上处理。

一台机器一次只能处理一道工序，并且一道工序一旦开始就必须进行下去直到完成。

一个作业只有在机器1上的处理完成以后才能由机器2处理。

假设已知作业i在机器j上需要的处理时间为t[i,j]。

流水作业调度问题就是要求确定一个作业的处理顺序使得尽快完成这n个作业。

二、算法分析n个作业{1,2,…,n}要在由2台机器M和2M组成的流水线上完成加工。

每1个作业加工的顺序都是先在M上加工，然后在2M上加工。

1M和2M加工作业i所1需要的时间分别为t[i,1]和t[i,2], n1.流水作业调度问题要求确定这ni≤≤个作业的最优加工顺序，使得从第一个作业在机器M上开始加工，到最后一个1作业在机器M上加工完成所需的时间最少。

2从直观上我们可以看到，一个最优调度应使机器M没有空闲时间，且机器2M1的空闲时间是最少。

在一般情况下，机器M上会有机器空闲和作业积压两种情2况。

设全部作业的集合为}N=。

N2,1{n,....,S⊆是N的作业子集。

在一般情况下，机器M开始加工S中作业时，机器2M还在加工其他作业，要等时间t后才能利1用。

将这种情况下完成S中作业所需的最短时间计为),ST。

流水作业调度问题(t的最优解为)0,T。

(N1.证明流水作业调度问题具有最优子结构设a是所给n个流水作业的一个最优调度，它所需要的加工时间为']1),1([T a t +。

其中，'T 是在机器2M 的等待时间为]2),1([a t 时，安排作业)(),......,3(),2(n a a a 所需的时间。

记)}1({a N S -=，则我们可以得到])2),1([,('a t S T T =。

事实上，有T 的定义可知])2),1([,('a t S T T ≥.若])2),1([,('a t S T T >，设'a 是作业集S 在机器2M 的等待时间为]2),1([a t 情况下的一个最优调度。

流水作业调度一、 可行性分析与项目开发计划ｎ个作业}{n ,...2,1要在由2台机器M1和M2组成的流水线上完成加工。

每个作业的顺序都是现在M1上加工，然后再M2上加工。

M1和M2加工作业i 所需的时间分别是i a 和i b ，1<=i<=n.流水作业调度问题要求确定这n 个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需要的时间最少。

直观上，一个最优调度应该使得机器M1没有空闲时间，而且机器M2的空闲时间最少，在一般情况下，机器M2上会出现机器空闲和作业积压两种情况。

设全部作业的集合为N={1,2，…n}。

N S ⊆是N 的作业子集，在一般情况下，机器M1开始加工作业S 中作业时，机器M2还在加工其他作业，要等时间t 后才可以利用。

将这种情况下完成S 中作业所需要的最短时间记做T(S,t),则流水作业调度问题的最优值就是T(N,0).我们通过分析可以知道流水作业调度问题具有最优子结构的性质，因此考虑用动态规划算法自后向前来解决其最优问题。

这就需要通过建模来得出最优子结构的递归式子，从而设计算法求解最优值。

二、 需求分析1、 用户可以根据自己的需要输入想要进入流水线的作业数。

2、 用户可以输入这几个作业在机器M1和M2上的加工时间。

3、 由主函数调用流水作业调度的Johnson 算法来实现对流水作业的安排。

4、 输出经过Johnson 算法安排后的作业序列，这就是最终的一个最优调度。

三、 概要设计 总体设计：假定这n 个作业在机器M1上加工时间为i a ,在机器M2上加工时间为i b ，1<=i<=n. 由流水作业调度问题具有最优子结构性质可知，)}},{(min{)0,(i i b i N T a N T =+= 1<=i<=n 推广到一般情况下，})}0,m a x {},{({),(i a t b i S T a t S T i i -+-+= S i ∈ 式子中，}0,max{i a t -这一项是由于在机器M2上，作业i 必须在},max{i a t 时间之后才能开工，因此，在机器M1上完成作业加工i 之后，在机器还需要}0,max{},max{i i i i i a t b a a t b -+=-+时间完成对作业i 的加工。

操作系统实验报告作业调度操作系统实验报告：作业调度引言作业调度是操作系统中的重要部分，它负责管理和调度系统中的各种作业，以最大化系统资源的利用率和提高作业的执行效率。

在本次实验中，我们将探讨作业调度的基本原理和实现方法，并通过实验验证其效果。

实验目的本次实验的主要目的是通过实际操作，了解作业调度的基本原理和实现方法，掌握作业调度的相关算法，并通过实验验证其有效性。

实验内容1. 实现作业调度的基本算法在本次实验中，我们将实现作业调度的基本算法，包括先来先服务（FCFS）、最短作业优先（SJF）、优先级调度（Priority Scheduling）和多级反馈队列调度（Multilevel Feedback Queue Scheduling）等。

通过编写代码，模拟这些算法的执行过程，并观察它们的效果。

2. 实验验证我们将设计一些测试用例，通过模拟作业的执行过程，分别使用不同的作业调度算法，并比较它们的执行效果。

通过实验验证，我们将得出不同算法的优劣势，并分析其适用场景。

实验结果经过实验验证，我们得出以下结论：1. 先来先服务（FCFS）算法适用于作业执行时间相对均匀的情况，但可能会导致平均等待时间较长。

2. 最短作业优先（SJF）算法能够最大程度地减少平均等待时间，但可能会出现作业饥饿现象。

3. 优先级调度（Priority Scheduling）算法能够根据作业的优先级进行调度，适用于有明确优先级需求的情况。

4. 多级反馈队列调度（Multilevel Feedback Queue Scheduling）算法能够根据作业的执行情况动态调整优先级，适用于各种类型的作业。

结论作业调度是操作系统中的重要组成部分，不同的作业调度算法适用于不同的场景。

通过本次实验，我们深入了解了作业调度的基本原理和实现方法，掌握了不同算法的优劣势，并通过实验验证了它们的有效性。

这将对我们进一步深入学习操作系统和提高系统性能有着重要的意义。

动态规划算法实验报告实验标题1、矩阵连乘2、最长公共子序列3、最大子段和4、凸多边形最优三角剖分5、流水作业调度6、0-1背包问题7、最优二叉搜索树实验目的掌握动态规划法的基本思想和算法设计的基本步骤。

实验内容与源码1、矩阵连乘#include<iostream>#include<cstdlib>using namespace std;const int size=4;//ra,ca和rb,cb分别表示矩阵A和B的行数和列数void matriMultiply(int a[][4],int b[][4],int c[][4],int ra ,int ca,int rb ,int cb ){if(ca!=rb) cerr<<"矩阵不可乘";for(int i=0;i<ra;i++)for(int j=0;j<cb;j++){int sum=a[i][0]*b[0][j];for(int k=1;k<ca;k++)sum+=a[i][k]*b[k][j];c[i][j]=sum;}}void MatrixChain(int *p,int n,intm[][4],int s[][4]){for(int i=1;i<=n;i++) m[i][i]=0;//对角线for(int r=2;r<=n;r++)//外维for(int i=1;i<=n-r+1;i++)//上三角{int j=i+r-1;m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];s[i][j]=i;for(int k=i+1;k<j;k++){intt=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];if(t<m[i][j]){m[i][j]=t;s[i][j]=k;}}}}void Traceback(int i,int j,int s[][4]){if(i == j){cout<<"A"<<i;}else if(i+1 == j){cout<<"(A"<<i<<"A"<<j<<")";}else{cout<<"(";Traceback(i,s[i][j],s);Traceback(s[i][j]+1,j,s);cout<<")";}int main(){int w;cout<<"矩阵个数：";cin>>w;int p[w],s[w][w];cout<<"输入矩阵A1维数：";cin>>p[0]>>p[1];for(int i=2 ; i<=w ; i++){int m = p[i-1];cout<<"输入矩阵A"<<i<<"维数：";cin>>p[i-1]>>p[i];if(p[i-1] != m){cout<<endl<<"维数不对，矩阵不可乘！"<<endl;exit(1);}Traceback(1,w,s);return 0;}运行结果2、最长公共子序列#include<cstring>#include<iostream>#define N 100using namespace std;//str1存储字符串x，str2存储字符串y char str1[N],str2[N];//lcs存储最长公共子序列char lcs[N];//c[i][j]存储str1[1...i]与str2[1...j]的最长公共子序列的长度int c[N][N];//flag[i][j]==0为str1[i]==str2[j] //flag[i][j]==1为c[i-1][j]>=s[i][j-1] //flag[i][j]==-1为c[i-1][j]<s[i][j-1] int flag[N][N];//求长度int LCSLength(char *x, char *y) {int i,j;//分别取得x,y的长度int m = strlen(x);int n = strlen(y);for(i=1;i<=m;i++)c[i][0] = 0;for(i=0;i<=n;i++)c[0][i] = 0;for(i=1;i<=m;i++)for(j=1;j<=n;j++){if(x[i-1]==y[j-1]){c[i][j] = c[i-1][j-1] +1;flag[i][j] = 0;}else if(c[i-1][j]>=c[i][j-1]){c[i][j] = c[i-1][j];flag[i][j] = 1;}else{c[i][j] = c[i][j-1];flag[i][j] = -1;}}return c[m][n];}//求出最长公共子序列char* getLCS(char *x, char *y,int len,char *lcs){int i = strlen(x);int j = strlen(y);while(i&&j){if(flag[i][j]==0){lcs[--len] = x[i-1];i--;j--;}else if(flag[i][j]==1)i--;elsej--;}return lcs;}int main(){int i;cout<<"请输入字符串x："<<endl;cin>>str1;cout<<"请输入字符串y："<<endl;cin>>str2;int lcsLen = LCSLength(str1,str2);cout<<"最长公共子序列长度："<<lcsLen<<endl;char *p =getLCS(str1,str2,lcsLen,lcs);cout<<"最长公共子序列为：";for(i=0;i<lcsLen;i++)cout<<lcs[i]<<" ";return 0;}运行结果3、最大子段和//分治法求最大子段和#include<iostream>using namespace std;int MaxSubSum(int *a,int left,int right) {int sum=0;if(left==right)sum=a[left]>0?a[left]:0;else{int center = (left+right)/2;//最大子段和在左边intleftsum=MaxSubSum(a,left,center);//最大子段和在右边intrightsum=MaxSubSum(a,center+1,right);//最大子段和在中间int s1=0;int lefts=0;for(int i=center;i>=left;i--){lefts+=a[i];if(lefts>s1) s1=lefts;}int s2=0;int rights=0;for(int i=center+1;i<=right;i++){rights+=a[i];if(rights>s2) s2=rights;}sum=s1+s2;//前后子段和相加//判断最大子段和if(sum>leftsum)sum=leftsum;if(sum>rightsum)sum=rightsum;}return sum;}int MaxSum(int *a,int n){return MaxSubSum(a,1,n-1);}int main(){int a[8]={2,-3,-5,4,1,7,1,-5};cout<<"最大子段和为："<<MaxSum(a,8);return 0;}//动态规划法#include<iostream>using namespace std;int MaxSum(int *a,int n){int sum=0,b=0;for(int i=1;i<n;i++)//此处不能=n，{if(b>0) b+=a[i];else b=a[i];if(b>sum) sum=b;}return sum;}int main(){int a[8]={2,-3,-5,4,1,7,1,-5};cout<<"最大子段和为："<<MaxSum(a,8);return 0;}运行结果4、凸多边形最优三角剖分#include<iostream>#include<cmath>#include<cstdlib>#define N 50using namespace std;struct point{int x;int y;};int distance(point X, point Y)//两点距离{int dis = (Y.x-X.x)*(Y.x-X.x) + (Y.y-X.y)*(Y.y-X.y);return (int)sqrt(dis);}int w(point a, point b, point c)//权值{return distance(a,b) + distance(b,c) + distance(a,c);}bool JudgeInput()//判断是否能构成凸多边形{point *v; //记录凸多边形各顶点坐标int *total; //记录坐标在直线方程中的值int m,a,b,c;cout<<"请输入凸多边形顶点个数：";cin>>m;int M = m-1;for(int i=0 ; i<m ; i++){cout<<"输入顶点v"<<i<<"的坐标：";cin>>v[i].x>>v[i].y;}//根据顶点坐标判断是否能构成一个凸多边形for(int j=0 ; j<m ; j++){int p = 0;int q = 0;if(m-1 == j){a = v[m-1].y - v[0].y;b = v[m-1].x - v[0].y;c = b * v[m-1].y - a *v[m-1].x;}else{a = v[j].y - v[j+1].y;b = v[j].x - v[j+1].x;c = b * v[j].y - a * v[j].x;}for(int k=0 ; k<m ; k++){total[k] = a * v[k].x - b * v[k].y + c;if(total[k] > 0){p = p+1;}else if(total[k] < 0){q = q+1;}}if((p>0 && q>0) || (p==0 &&q==0)){cout<<"无法构成凸多边形！"<<endl;exit(1);}}}bool minWeightTriangulation()//计算最优值算法{int M;int **t, **s;point *v;for(int i=1 ; i<=M ; i++)t[i][i] = 0;for(int r=2 ; r<=M ; r++)for(int i=1 ; i<=M-r+1 ; i++){int j = i+r-1;t[i][j] = t[i+1][j] +w(v[i-1],v[i],v[j]);s[i][j] = i;for(int k=i+1 ; k<i+r-1 ; k++){int u = t[i][k] +t[k+1][j] + w(v[i-1],v[k],v[j]);if(u < t[i][j]){t[i][j] = u;s[i][j] = k;}}}return true;}void Traceback(int i, int j, int **s){if(i == j)return;Traceback(i,s[i][j],s);Traceback(s[i][j]+1,j,s);cout<<"三角形：v"<<i-1<<"v"<<s[i][j]<<"v"<<j<<endl; }int main(){int **s; //记录最优三角剖分中所有三角形信息int **t; //记录最优三角剖分所对应的权函数值point *v; //记录凸多边形各顶点坐标int *total; //记录坐标在直线方程中的值int M=0;t = new int *[N];s = new int *[N];for(int i=0 ; i<N ; i++){t[i] = new int[N];s[i] = new int[N];}v = new point[N];total = new int[N];if(JudgeInput()){if(minWeightTriangulation()){Traceback(1,M,s);cout<<endl;cout<<"最优权值之和为："<<t[1][M]<<endl;}}return 0;}运行结果：5、流水作业调度#include<iostream>#define N 100using namespace std;class Jobtype{public:/* int operator<=(Jobtype a)const{return(key<=a.key);}*/int key;int index;bool job;};void sort(Jobtype *d,int n){int i,j;Jobtype temp;bool exchange; //交换标志for(i = 0;i < n;i ++){ //最多做n-1趟排序exchange = false; //本趟排序开始前，交换标志应为假for(j = n - 1;j >= i;j --)if(d[j+1].key < d[j].key){temp = d[j+1];d[j+1] = d[j];d[j] = temp;exchange=true; //发生了交换，故将交换标志置为真}if(!exchange) //本趟排序未发生交换，提前终止算法return;}}int FlowShop(int n,int *a,int *b,int *c) {Jobtype *d = new Jobtype[n];for(int i=0;i<n;i++)//初始化{d[i].key=a[i]>b[i]?b[i]:a[i];// 执行时间d[i].job=a[i]<=b[i];// 作业组d[i].index=i;//作业序号}sort(d,n);;int j=0;int k=n-1;for(int i=0;i<n;i++)//最优调度{if(d[i].job){c[j++]=d[i].index;}else{c[k--]=d[i].index;}}j=a[c[0]];k=j+b[c[0]];for(int i=1;i<n;i++){j+=a[c[i]];k=j<k?k+b[c[i]]:j+b[c[i]];}delete d;//回收空间return k;//返回调度时间}int main(){int n,*a,*b,*c;cout<<"作业数：";cin>>n;Jobtype *d = new Jobtype[N];a=new int[N];b=new int[N];c=new int[N];cout<<"请输入作业号和时间：";for(int i=0;i<n;i++){cin>>d[i].index>>d[i].key;}cout << endl;int k=FlowShop(n,a,b,c);cout<<"\n调度时间："<<k<<endl;cout<<"最优调度序列:";for (int i = 0; i < n; i++) // 输出最优调度序列{cout << c[i] << " ";}return 0;}运行结果：6、0-1背包问题#include <iostream>#include <iomanip>using namespace std;const int C=10;//容量const int N=5;//个数int max(const int a,const int b){return a>b?a:b;}int min(const int a,const int b){return a<b?a:b;}/*m为记录数组m[i][j]代表在剩有j容量的条件下，从i开始往后的物品中可以取得的最大价值w为重量数组，v为价值数组n为物品个数，c为开始容量则m[1][c]即此背包能剩下的最大价值*/void knapsack(int **m,int n, int c,int *w, int *v){int jMax = min(w[n]-1,c);//前n-1个物品for(int j=0;j<=jMax;j++)m[n][j]=0;for(int j=w[n];j<=c;j++)m[n][j]=v[n];for(int i=n-1;i>1;i--){jMax=min(w[i]-1,c);for(int j=0;j<=jMax;j++)m[i][j] = m[i+1][j];for(int j=w[i];j<=c;j++)m[i][j] = max(m[i+1][j],m[i+1][j-w[i]]+v[i]);}m[1][c]=m[2][c];if(c>=w[1])m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);}//找出最优解，0表示不能装，1表示能装void traceback(int **m,int n,int c,int *x,int *w){for(int i=1;i<n;i++){if(m[i][c]==m[i+1][c]) x[i]=0;else{x[i]=1;c-=w[i];}}x[n]=(m[n][c]==0)?0:1;}int main(){int *v=new int[N+1];int *w=new int[N+1];int **m=new int* [N+1];int *x=new int [N+1];for(int i=0;i<N+1;i++){m[i]=new int[C+1];}cout<<"输入重量序列,"<<N<<"个"<<endl;for(int i=1;i<=N;i++)cin>>w[i];cout<<"输入价值序列,"<<N<<"个"<<endl;for(int i=1;i<=N;i++)cin>>v[i];knapsack(m,N,C,w,v);traceback(m,N,C,x,w);cout<<"最优值："<<m[1][C]<<endl;cout<<"是否装入背包的情况：";for(int i=1;i<=N;i++){cout<<x[i];}for(int i=0;i<N+1;i++){delete m[i];}delete []m;return 0;}运行结果7、最优二叉搜索树#include<iostream>#include<cmath>#include<limits>#define N 100using namespace std;const double MAX =numeric_limits<double>::max(); //double 的最大值//a[i]为结点i被访问的概率//b[i]为“虚结点”i被访问的概率//m[i][j]用来存放子树（i，j）的期望代价//w[i][j]用来存放子树（i，j）的所有结点（包括虚结点）的a,b概率之和//s[i][j]用来跟踪root的void OptimalBinarySearchTree(double *a,double *b,int n){int s[N][N];double m[N][N];double w[N][N];int i,j,l,r;for(i=1; i<=n+1; i++){m[i][i-1] = b[i-1];w[i][i-1] = b[i-1];}for(l=1; l<=n; l++){for(i=1; i<=n-l+1; i++){j = l+i-1;m[i][j] = MAX;w[i][j] = w[i][j-1] + a[j]+b[j];for(r=i; r<=j; r++){double k = m[i][r-1] + w[i][j] + m[r+1][j];if(k<m[i][j]){m[i][j] = k;s[i][j] = k;}}}}cout<<m[1][n];}int main(){double a[N],b[N];int n;double sum = 0;int i,j,l;cout<<"请输入关键字的个数："<<endl;cin>>n;cout<<"请输入每个关键字的概率："<<endl;for(i=1; i<=n; i++){cin>>a[i];sum += a[i];}cout<<"请输入每个虚拟键的概率："<<endl;for(i=0; i<=n; i++){cin>>b[i];sum += b[i];}if(abs(sum-1)>0.01){cout<<"输入的概率和不为1,请重新输入"<<endl;}cout<<"最优二叉查找树的期望搜索代价为：";OptimalBinarySearchTree(a,b,n);return 0;}运行结果：实验总结通过实现动态规划的这个题目，对动态规划算法有了进一步的了解。

动态规划算法在任务调度中的应用随着科技的不断发展和进步，现代社会需要处理和完成的任务也越来越多。

为了提高效率、优化资源，人们需要对这些任务进行科学合理的调度。

而动态规划算法，正是一种在这方面被广泛应用的算法。

动态规划算法是一种基于分治思想的算法，通过将问题分解为子问题的方式，从而达到优化解决问题的效果。

它将问题分成多个子问题，对每个子问题均采用递归的方式进行求解，然后将子问题的解组合成最终的解。

在任务调度中，动态规划算法可以用来确定每项任务的完成时间、资源分配等。

它可以针对不同的任务情况设置不同的约束条件，通过优化不同的目标函数，达到更好的调度效果。

以下是动态规划算法在任务调度中的两个典型应用案例:1. 多机调度问题在多机调度问题中，需要将多个任务分配给不同的机器，并按照机器的加工速度和任务的处理时间，进行合理分配。

该问题通常采用动态规划算法进行求解，最终得到每个任务的完成时间和资源分配情况。

多机调度问题的求解思路是，先将整个调度问题分解成多个单机调度的子问题，再对每个子问题采用动态规划算法进行求解。

最终，将每个子问题的最优解组合成整体的最优解。

在求解多机调度问题时，动态规划算法的核心是贪心算法。

贪心算法指的是，优先考虑当前最优的解决方案，而不是考虑是否存在更好的解决方案。

因此，每个任务的处理时间和临近任务的时间关系，以及机器的处理速度等因素，均需要考虑其中。

2. 总收益最大化问题在总收益最大化问题中，需要将受理的任务分配给不同的执行人员。

执行人员的工作效率不同，同时还存在成本和资源限制。

因此，最终需要确定每个任务的分配方案，以及分配给不同执行人员的任务数量和执行时间。

总收益最大化问题的求解思路是，将任务分解为多个子问题，分别对每个子问题进行求解，然后将每个子问题的最优解组合成整体的最优解。

其中，采用了动态规划算法和线性规划算法等技术，通过数学模型的建立和求解，最终得到调度方案及其最终效益。

总收益最大化问题的求解涉及到非常复杂的约束条件与目标函数，因此需要运用较高级的数学模型和算法方法。

第1篇本实验报告针对动态规划算法进行深入研究和实践，旨在通过一系列实验，加深对动态规划思想、基本原理及实际应用的理解。

实验内容涵盖了动态规划算法的多个经典问题，包括找零钱问题、独立任务最优调度问题、最长公共子序列问题、矩阵连乘问题、剪绳子问题以及0-1背包问题等。

一、实验目的1. 理解动态规划算法的概念，掌握动态规划的基本思想和解决问题的基本步骤。

2. 学习动态规划算法设计策略，提高算法设计能力。

3. 通过实际案例，体会动态规划算法在解决实际问题中的应用价值。

二、实验内容与步骤1. 找零钱问题实验要求设计一个动态规划算法，对给定面值的硬币组合，计算出所有可能找零方式的硬币个数。

通过实验，掌握了动态规划算法的基本原理，并熟悉了动态规划在解决组合优化问题中的应用。

2. 独立任务最优调度问题实验要求设计一个动态规划算法，使得两台处理机处理完n个作业的时间最短。

通过实验，了解了动态规划在解决调度问题中的应用，并掌握了多阶段决策问题的求解方法。

3. 最长公共子序列问题实验要求找出两个序列的最长公共子序列。

通过实验，学习了动态规划在解决序列匹配问题中的应用，并掌握了如何通过动态规划算法优化问题求解过程。

4. 矩阵连乘问题实验要求确定计算矩阵连乘积的计算次序，使得所需数乘次数最少。

通过实验，了解了动态规划在解决矩阵连乘问题中的应用，并掌握了如何通过动态规划算法优化计算过程。

5. 剪绳子问题实验要求将一根绳子剪成m段，使得各段乘积最大。

通过实验，掌握了动态规划在解决资源分配问题中的应用，并学会了如何通过动态规划算法找到最优解。

6. 0-1背包问题实验要求用动态规划算法解决0-1背包问题。

通过实验，了解了动态规划在解决背包问题中的应用，并掌握了如何通过动态规划算法优化问题求解过程。

三、实验结果与分析通过对以上问题的动态规划算法实现，实验结果表明：1. 动态规划算法能够有效地解决组合优化问题、调度问题、序列匹配问题、矩阵连乘问题、资源分配问题以及背包问题等。

作业调度实验报告作业调度实验报告引言：作业调度是计算机操作系统中的一个重要概念，它涉及到如何合理地安排和管理计算机系统中的各个作业的执行顺序，以提高计算机系统的效率和资源利用率。

本实验旨在通过模拟不同的作业调度算法，探究它们在不同场景下的性能表现。

实验目的：1. 了解作业调度的基本概念和原理；2. 掌握作业调度算法的实现方法；3. 分析不同作业调度算法在不同场景下的优缺点。

实验过程：1. 实验环境的搭建在实验开始前，我们需要搭建一个适合进行作业调度实验的环境。

我们选择了一台配置较高的计算机，并安装了操作系统和相关的开发工具。

2. 实验数据的准备为了模拟真实的作业调度场景，我们需要准备一些作业数据。

这些数据包括作业的到达时间、执行时间、优先级等信息。

我们通过编写程序生成了一批随机的作业数据，并将其保存在文件中。

3. 实验算法的实现根据实验要求，我们实现了三种常见的作业调度算法：先来先服务（FCFS）、最短作业优先（SJF）和优先级调度算法（Priority Scheduling）。

我们使用C语言编写了相应的代码，并对其进行了测试和调试。

4. 实验结果的分析我们将不同作业调度算法在相同作业数据下的运行结果进行了比较和分析。

通过观察和统计，我们得到了各个算法的平均周转时间、平均等待时间等性能指标。

同时，我们还通过绘制图表的方式直观地展示了这些数据。

实验结果与讨论：1. 先来先服务算法（FCFS）先来先服务算法是最简单的作业调度算法之一，它按照作业到达的顺序依次执行。

在实验中，我们发现该算法对于短作业来说表现较好，但对于长作业来说会导致平均等待时间较长。

2. 最短作业优先算法（SJF）最短作业优先算法是一种非抢占式的调度算法，它优先执行执行时间最短的作业。

在实验中，我们发现该算法能够有效减少平均等待时间，但对于长作业来说可能会导致饥饿现象。

3. 优先级调度算法（Priority Scheduling）优先级调度算法根据作业的优先级来安排执行顺序。

动态规划-流水作业调度报告C1 问题描述和分析N个作业{1,2,………,n}要在由两台机器M1和M2组成的流水线上完成加工。

每个作业加工的顺序都是先在M1上加工，然后在M2上加工。

M1和M2加工作业i所需的时间分别为ai和bi，1≤i≤n。

流水作业高度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。

设全部作业的集合为N={1,2,…,n}, S⊆N,,一般情况下,机器M1开始加工作业S时,机器M2还在加工其他作业,要等时间t后才可利用.将这种情况下完成S中作业所需的最短时间记为T(S,t).流水作业调度的最优值为T(N,0)即,设π是所给n个流水作业的一个最优调度,它所需的加工时间为a(π1)+T’.其中T’是在此机器M2的等待时间为b(π1)时,安排作业π1, π2,…πn所需时间.所以S=N-{π1},有T’=T(S,b(π1)).由T的定义知T’≥T(S,b(π1)).若T’＞T(S,b(π1)),设π’是作业集S在机器M2的等待时间为b(π1)情况下的一个最优调度.则π1, π’2,…, π’n是N的一个调度,且该调度所需的时间为a(π1)+T(S,b(π1))＜a(π1)+T’.这与π是N的最优调度矛盾.故T’≤T(S,b(π1).从而T’=T(S,b(π1).即当机器M1为空闲即未安排任何加工任务时，则任何一个作业的第一个任务（第一道工序）都可以立即在M1上执行，无须任何先决条件。

因此容易知道，必有一个最优调度使得在M1上的加工是无间断的。

实际上，如某个最优调度π在M1上安排的加工是有间断的，则我们可以把所有在M1上出现间断处的任务的开始加工时间提前，使得在M1上的加工是无间断的；而在M2上仍按π原先的安排。

把这样调整之后的调度记作为π’。

由于在调度π’下，任何一个任务在M1上加工的结束时间不晚于在调度π下的结束时间，故调度π’不会影响在M2上进行加工的任何一个任务的开始时间。

作业调度算法-实验报告作业调度算法模拟一、课题内容和要求常见的作业调度算法有先来先服务算法、最短作业优先算法、响应比优先调度算法。

(1)参考操作系统教材理解这3种算法。

(2)实现这3个算法。

(3)已知若干作业的到达时间和服务时间，用实现的算法计算对该组作业进行调度的平均周转时间Ttime和平均带权周转时间WTtime。

(4)作业的到达时间和服务时间可以存放在文本文件record.txt中。

(5)设计简单的交互界面，演示所设计的功能。

(可以使用MFC进行界面的设计) （6）可根据自己能力，在完成以上基本要求后，对程序功能进行适当扩充。

二、需求分析模拟实现作业调度算法，包括：FCFS（先来先服务算法）、SJF （短作业优先算法）、HRN（最高响应比优先算法）、HPF（基于优先数调度算法）。

先来先服务算法：按照各个作业进入系统（输入井）的自然次序来调度算法。

短作业优先算法：优先调度并处理短作业。

所谓的“短作业”并不是指物理作业长度短，而是指作业的运行时间短。

最高响应比优先算法：优先调度并处理响应比最高的作业。

三、概要设计函数中一些类：Time类int hour 小时int minute 分钟Job类Int ID作业编号Time start开始时间Time enter进入时间Time end结束时间int requesttime估计运行时间int Ttime周转时间int priority优先数double WTtime带权周转时间Schedule 类 int size 作业数 schedule()构造函数 Job *job 作业数组 void readFile() 从文件读信息 int *r 排序用数组 void FCFS() 先来先服务 Int Differ() 求时间差void SJF() 短作业优先 void HRN()最高响应比优先主要功能函数的流程图 1、2、先来先服务：YN开始j ob[0]结束job[i] i<="">readFile()给变量赋值OnButton2()SJFEDIT4 平均周转时间EDIT5 平均带权周转时间EDIT2 平均周转时间EDIT1 平均带权周转时间EDIT6 平均周转时间EDIT7 平均带权周转时间结束OnButton1()FCFSOnButton3()HRN3、最短作业优先：开始j ob[0]剩余作业按运行时间最短排序job[i]Yi<size< p="">N结束4、最高响应比：开始job[0]计算各作业响应比剩余作业按响应比排序job[i]Yi<size< p="">N结束四、详细设计1、程序代码MFC头文件a.h内容：const int defMaxJobNumber = 10; //作业数量的最大值class Time //时间类{public:int hour;int minute;};class Job//作业类{public:int ID; //作业编号Time enter; //进入时间int requesttime; //估计运行时间int priority; //优先数Time start; //开始时间Time end; //结束时间int Ttime; //周转时间double WTtime; //带权周转时间};class schedule //调度类{public:int size; //作业数Job *job; //作业数组int *r; //排序用数组int Differ(Time t1,Time t2) //求两个时刻间的时间差t2-t1{int borrow = (t2.minute<="" 1="" :="" ?="" p="">return ((t2.hour-t1.hour-borrow)*60+(borrow*60+t2.minute-t1.minute));}public:schedule() //构造函数{size = 0;job = new Job[defMaxJobNumber];r = new int[defMaxJobNumber-1];}void readFile() //从文件读信息{ifstream txtfile;txtfile.open("record.txt");int i = 0;int entertime;while(!txtfile.eof()){txtfile>>job[i].ID>>entertime>>job[i].requesttime>>job[i]. priority;job[i].enter.hour = entertime / 100; //取小时job[i].enter.minute = entertime % 100; //取分钟i++;size++;}txtfile.close();}void FCFS()//先来先服务(First Come First Serve){int hour,minute,carry;job[0].start = job[0].enter;hour = job[0].requesttime / 60;minute = job[0].requesttime % 60;job[0].end.minute = (job[0].start.minute + minute) % 60;carry = (job[0].start.minute + minute) / 60; //carry是分钟累积超过60商job[0].end.hour = job[0].start.hour + hour + carry;job[0].Ttime = job[0].requesttime;job[0].WTtime = ((double)job[0].Ttime) / job[0].requesttime;for(int i=1;i<size;i++)< p="">{job[i].start = job[i-1].end;hour = job[i].requesttime / 60;minute = job[i].requesttime % 60;job[i].end.minute = (job[i].start.minute + minute) % 60;carry = (job[i].start.minute + minute) / 60;job[i].end.hour = job[i].start.hour + hour + carry;job[i].Ttime = Differ(job[i].enter,job[i].end); //周转时间job[i].WTtime = ((double)job[i].Ttime) / job[i].requesttime; //带权周转时间}}void SJF()//短作业优先(Shortest Job First){int hour,minute,carry;job[0].start = job[0].enter;hour = job[0].requesttime / 60;minute = job[0].requesttime % 60;job[0].end.minute = (job[0].start.minute + minute) % 60;carry = (job[0].start.minute + minute) / 60; //carry是分钟累积超过60的商job[0].end.hour = job[0].start.hour + hour + carry;job[0].Ttime = job[0].requesttime; //周转时间job[0].WTtime = ((double)job[0].Ttime) / job[0].requesttime; //带权周转时间for(int i=1;i<size;i++)< p="">r[i] = i;for(i=1;i<="">{int index = i;for(int j=i+1;j<size;j++)< p="">if(job[r[j]].requesttime<job[r[index]].requesttime)< p="">index = j;if(index!=i){int w = r[i];r[i] = r[index];r[index] = w;}}int dest=0;for(i=1;i<="">{int index = r[i];job[index].start = job[dest].end;hour = job[index].requesttime / 60;minute = job[index].requesttime % 60;job[index].end.minute = (job[index].start.minute + minute) % 60;carry = (job[index].start.minute + minute) / 60;job[index].end.hour = job[index].start.hour + hour + carry;job[index].Ttime = Differ(job[index].enter,job[index].end);job[index].WTtime = ((double)job[index].Ttime) / job[index].requesttime;dest = index;}}void HRN() //最高响应比优先(Highest Response_ratio Next){int hour,minute,carry;job[0].start = job[0].enter;hour = job[0].requesttime / 60;minute = job[0].requesttime % 60;job[0].end.minute = (job[0].start.minute + minute) % 60;carry = (job[0].start.minute + minute) / 60; //carry是分钟累积超过60的商job[0].end.hour = job[0].start.hour + hour + carry;job[0].Ttime = job[0].requesttime; //周转时间job[0].WTtime = ((double)job[0].Ttime) / job[0].requesttime; 带权周转时间int dest=0;for(int i=1;i<size;i++)< p="">r[i] = i;for(i=1;i<size;i++)< p="">{int index = i;for(int j=i+1;j((double)Differ(job[r[index]].enter,job[dest].end))/job[r[inde x]].requesttime)//响应比=作业周转时间/作业处理时间index = j;if(index!=i){int w = r[i];r[i] = r[index];r[index] = w;}//按排序后的作业序继续执行index = r[i];job[index].start = job[dest].end;hour = job[index].requesttime / 60;minute = job[index].requesttime % 60;job[index].end.minute = (job[index].start.minute + minute) % 60;carry = (job[index].start.minute + minute) / 60;job[index].end.hour = job[index].start.hour + hour + carry;job[index].Ttime = Differ(job[index].enter,job[index].end);job[index].WTtime = ((double)job[index].Ttime) / job[index].requesttime;dest = index;}}};五、测试数据及其结果分析从文本文件中读取数据（书上的例子）：1 800 120 22 850 50 33 900 10 14 950 20 4输出的平均周转时间、平均带权周转时间结果正确。

实验二作业调度实验题目1、编写并调试一个单道解决系统的作业等待模拟程序。

作业调度算法:分别采用先来先服务（FCFS）,最短作业优先（SJF）的调度算法。

（1 ）先来先服务算法:按照作业提交给系统的先后顺序来挑选作业，先提交的先被挑选。

（2）最短作业优先算法：是以进入系统的作业所提出的“执行时间”为标准,总是优先选取执行时间最短的作业。

二.实验目的：本实验规定用高级语言（C语言实验环境）编写和调试一个或多个作业调度的模拟程序，了解作业调度在操作系统中的作用，以加深对作业调度算法的理解三.实验过程〈一〉单道解决系统作业调度1）单道解决程序作业调度实验的源程序:zuoye.c 执行程序：zu o y e.exe2）实验分析：1、由于在单道批解决系统中，作业一投入运营，它就占有计算机的一切资源直到作业完毕为止，因此调度作业时不必考虑它所需要的资源是否得到满足，它所占用的CP U时限等因素。

2、每个作业由一个作业控制块JCB表达,JCB可以包含如下信息:作业名、提交时间、所需的运营时间、所需的资源、作业状态、链指针等等。

作业的状态可以是等待W（Wait）、运营R（Run）和完毕F（Finish）三种状态之一。

每个作业的最初状态else i f (p->n e e d time<min->need t ime) m in=p； p= p ->next；( while (p!=NULL);i f (iden) {i—；/ / pr i n tf ("\nt i m e =%d: \ t no JCB sub mib.. . wait . . . t ime);tim e s++；i f ( times> 10 0) {prin t f("\nru n t ime i s too Ion g . .. error z，) ;g etc h () ； ))e 1 s e{ru n ning(m i n, m) ；//调用running ()函数}} //forf i na 1 (); 〃调用r u nn i ng()函数)voi d fefs (int m)〃先来先服务算法(int i, iden;syst e m ("cl s ");i ni t a 1 ();f or(i=0;i<n;i++)(p= r ea d y； i d en=l;do{if (p-> s tate= = , W* & &p ->reach t i me<=t i mes) i d e n=0：i f (i d e n )p= p -> n ext;}while(p!=NULL&&iden);if (i d on){i——；prin tf(〃\ n没有满足规定的进程，需等待”)；t imes++;i f (time s >1 0 0 ) {prin t f ("\n 时间过长")；getch () ;})e 1 se{runn i ng(p, m); 〃调用r u nn i n g ()函数))final () ;//调用ru n n i n g ()函数}void muneO{int m;s y s tem (〃 c 1 s〃)；p r i n t f (z/\ n\n\t\t *** 火 * ****** * ***** * ***** *** *** * *** * **** ***** **\ t \ t\n ");P rintf ('\t \ t \ t\t 作业调度演示\ n ")；pr i ntf( " \t\t^ ***** * * *** * *** * ******** * * **** * ******** * * *** * \t\P r intf(*\n\n\n\t\ t \tl.先来先服务算法.;pr i nt f ("\n\t\ t \ t2.最短作业优先算法.;printfC\n\ t \ t \t3.响应比高者优先算法");prin t f ( ° \0.退出程序.;P rintfC \n\n\t \t\ t \t 选择所要操作:");s c anf (*%d*, &m);sw i tc h (m)(c ase 1:f c f s (m);getchO ；s y stem("c 1 s");mune();brea k ;c a se 2 :sjf (m):getch ();system ( " cis*)；mune ();break；case 3 :hr n (m);g e t c h ();sys t em("cls");mune ()；br e a k ；case 0:system ("cis");break;d e f a u 1 t :pr intf(〃选择错误，重新选择getchO ;system ("c Is");muneO ;))main ()//主函数(i niz e ();muneO ;)5)调试结果：i.选择操作的界面程课件'计算机操作系统联作系统实验八作业调度\zuoye.exe ，作业调度演示.先来先服务算法.1 .最短企业优先算法.2 .响应居意者优先萱法 4战出程序.选择所要操作:2.输入操作初始信息:c 「E:\课程课件'计算机》3 .先来先服务算法作业调度结果：（调度顺序：a -> b ->c->d->e ）输入作业数：5输入作业数：5太人作业名:a7、侬、|到达时间:0要运行的时间：4 必法崎松时间其要运行的时间：3植入作业名:c 作业默认到达时间:2 曲人作批要运行的时间;5 植入作业名:d 伟业默认到达时间：3 曲入作要运行的时间;2 检入作业名:e 伟业默认到达时间;4 输入作业要运行的时间;4作业证在运行，估计其运行情况: 开始运宜时刻：。

动态规划算法在任务调度中的应用效果与优化方法动态规划（Dynamic Programming）算法是一种针对多阶段决策问题的优化算法，该算法通过将问题分解成多个相互联系的子问题，并依次求解这些子问题的最优解来得到整体问题的最优解。

在任务调度领域，动态规划算法具有广泛的应用，能够有效地提高任务调度的效率与质量。

一、动态规划算法在任务调度中的应用效果1. 任务相互依赖性考虑：在任务调度中，任务之间通常存在着相互依赖的关系。

动态规划算法通过将问题拆分为多个子问题，再通过子问题之间的关系来求解整体问题，可以很好地考虑到任务之间的相互依赖，确保任务调度的合理性。

2. 最优解保证：动态规划算法能够通过求解子问题的最优解来得到整体问题的最优解。

在任务调度中，通过动态规划算法可以找到使得调度质量最优的调度方案，保证任务能够按照最优的方式被分配和执行。

3. 资源利用率最大化：在任务调度中，资源的利用率是一个重要的指标。

动态规划算法通过对任务执行过程进行建模，并结合任务之间资源的使用情况，可以最大化资源的利用率，提高系统的整体效率。

4. 可扩展性：动态规划算法具有较强的可扩展性，可以应对不同规模的任务调度问题。

通过将问题拆分为多个子问题，并通过动态规划算法进行求解，可以很好地应对复杂的任务调度场景，满足不同任务规模下的需求。

二、动态规划算法在任务调度中的优化方法1. 状态空间的优化：在动态规划算法中，状态空间的大小直接影响算法的复杂度。

因此，对于任务调度问题，可以通过定义合适的状态来减少状态空间的大小，从而减少算法的计算量。

2. 子问题的划分策略优化：在任务调度问题中，合理地划分子问题对于算法的效率至关重要。

可以通过合理地定义子问题的范围和划分策略，将任务调度问题转化为适合动态规划算法求解的形式，提高算法的效率。

3. 限制条件的引入：任务调度问题通常会受到一些限制条件的约束，如任务执行时间、资源消耗等。

通过引入这些限制条件，可以对动态规划算法进行约束，从而缩小问题的解空间，提高算法的求解效率。

算法设计与分析——流⽔作业调度（动态规划）⼀、问题描述N个作业{1,2,………,n}要在由两台机器M1和M2组成的流⽔线上完成加⼯。

每个作业加⼯的顺序都是先在M1上加⼯，然后在M2上加⼯。

M1和M2加⼯作业i所需的时间分别为ai和bi，1≤i≤n。

流⽔作业⾼度问题要求确定这n个作业的最优加⼯顺序，使得从第⼀个作业在机器M1上开始加⼯，到最后⼀个作业在机器M2上加⼯完成所需的时间最少。

⼆、算法思路直观上，⼀个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。

在⼀般情况下，机器M2上会有机器空闲和作业积压2种情况。

最优调度应该是：1. 使M1上的加⼯是⽆间断的。

即M1上的加⼯时间是所有ai之和，但M2上不⼀定是bi之和。

2. 使作业在两台机器上的加⼯次序是完全相同的。

则得结论：仅需考虑在两台机上加⼯次序完全相同的调度。

设全部作业的集合为N={1，2，…，n}。

S是N的作业⼦集。

在⼀般情况下，机器M1开始加⼯S中作业时，机器M2还在加⼯其他作业，要等时间t后才可利⽤。

将这种情况下完成S中作业所需的最短时间记为T(S,t)。

流⽔作业调度问题的最优值为T(N,0)。

这个T(S,t)该如何理解?举个例⼦就好搞了（⽤ipad pencil写的...没贴类纸膜，太滑，凑合看吧）1、最优⼦结构T(N,0)=min{ai + T(N-{i}, bi)}, i∈N。

ai：选⼀个作业i先加⼯，在M1的加⼯时间。

T(N-{i},bi}：剩下的作业要等bi时间后才能在M2上加⼯。

注意这⾥函数的定义，因为⼀开始⼯作i是随机取的，M1加⼯完了ai之后，要开始加⼯bi了，这⾥M1是空闲的可以开始加⼯剩下的N-i个作业了，但此时M2开始加⼯bi，所以要等bi时间之后才能重新利⽤，对应到上⾯函数T(s,t)的定义的话，这⾥就应该表⽰成T(N-{i},bi), 所以最优解可表⽰为T(N,0)=min{ai + T(N-{i}, bi)}, i∈N，即我们要枚举所有的⼯作i，使这个式⼦取到最⼩值。

作业调度（多通道）课程设计报告一、目的要求：用高级语言编写和调试一个或多个作业调度的模拟程序，以加深对作业调度算法的理解。

二、详细设计：在多通道批处理系统中，作业的运行除了考虑作业之间的优先关系之外，还必须考虑系统能否为其所需的资源分配资源。

因为在多通道批处理系统中同时有不只一道作业在CPU中运行，这样就会导致某个作业需要的资源正在被另一个作业占用，这样就会导致无法分配资源的作业进入等待状态，直到该资源被其它作业释放后才能重新激活。

①、作业调度算法该作业调度系统的调度算法是基于优先级的调度算法。

在作业提交后按预先设定的优先级的高低依次插入到就绪队列(ready),但在系统运行过程中，除了考虑优先级外（即优先级高只是表明该作业能较先运行），同时还应该考虑该作业所需的资源是否能够被分配到。

②、为作业分配资源在这里采用这样的方法判断资源能否分配：查看该作业运行所需的第一个资源，然后在系统资源中查看该资源是否还有空闲的，有则表示该资源可以插入到运行队列(run)中，准备在下一个时间片中运行。

③、设置同时运行的最大并行度这里设置一个量maxrun，这个量是系统允许同时并行运行的作业数量，当运行队列中的作业数目达到最大值maxrun后，即使某作业所需的资源系统还有空闲的，也不再允许继续分配。

④、作业模块每个作业由一个作业控制块JCB控制，相关信息将在代码中将详细给出。

⑤、所需资源模块每个作业的JCB模块中有个所需资源的链，其结构用needsource表示，相关信息将在代码中将详细给出。

⑥、系统资源模块（systemsource）将系统拥有的各个资源及其的数目链成链，在系统运行过程中通过这个链就可以查询某作业需要的资源系统是否可以分配。

每当为某作业分配了某个资源后，该资源的数目减1，而当某作业释放了某个资源后，该资源的数目又将加1。

相关信息将在代码中将详细给出。

三、调度算法流程图如下：作业调度的详细过程如下：四、程序代码如下：#include <iostream.h>#include <stdlib.h>#include "conio.h"#define GetSpace(type) (type*)malloc(sizeof(type)) //空间分配函数#define NULL 0#define sourcenum 8 //系统拥有的各种同类资源数目#define maxrun 3 //定义在CPU中能同时运行的作业总数char syssourcename[sourcenum] = {'A','B','C','D','E','F','G','H'};//系统资源名称int sournum[sourcenum] = {1,1,1,1,1,1,1,1}; //对应的系统资源数量int systemtime = 0; //系统时间，开始为零int runjcb = 0; //在运行队列中的作业数量，开始为零int JCBNum = 0; //总的作业数int JCBTime = 0; //总的周转时间float JCBTime_1 = 0; //总的带权周转时间struct systemsource{ //系统资源，包括名称和数量char name;int number;systemsource * link;}*systemsor;struct needsource{ //作业所需资源链表结构char name;needsource *link;}*sourcelink;struct jcb{ //作业结构char name[10]; //作业名称int ptime; //提交时间int rtime; //开始运行时间int ftime; //完成时间int super; //优先级int needtime; //所需运行时间needsource * source; //所需资源链表char state; //作业状态bool runflag; //标识该作业运行与否jcb * link;}*wait=NULL,*ready=NULL,*run=NULL,*p;typedef struct systemsource SYSTEM;typedef struct needsource NEED;typedef struct jcb JCB;//-----------------------------------------------------------------------------void init() //将系统资源名称和对应的资源数目放到系统资源队列中{systemsource *fir,*sec;for(int i=0;i < sourcenum;i++){fir = GetSpace(SYSTEM);fir = new SYSTEM;fir->name = syssourcename[i]; //系统资源名称fir->number = sournum [i]; //对应的数量fir->link = NULL;if(i==0)systemsor = fir; //生成系统资源链表systemsorelsesec->link = fir;sec = fir;}}//----------------------------------------------------------------------------- void sort(bool BOOL){//按作业的优先级的高低依次插入到相关队列//当BOOL为true时表明要插入到就绪队列，否则插入到等待队列jcb *fir,*sec;bool ins = true;if(BOOL) //插入就绪队列fir = ready;elsefir = wait;if((fir==NULL) || (p->super) > (fir->super)){p->link = fir;fir = p;if(BOOL)ready = fir;elsewait = fir;}else{sec = fir->link ;while(sec != NULL){if((p->super) > (sec->super)){p->link = sec;fir->link = p;sec = NULL;ins = false;}else{fir=fir->link;sec=sec->link;}}if(ins)fir->link = p;}}//----------------------------------------------------------------------------- void input(){int num;cout<<"\n输入作业个数： ";cin>>num;JCBNum += num; //将新加的作业个数加到总的作业数中for(int i=0; i<num; i++){p = GetSpace(JCB);p = new JCB;cout<<"\n\n输入作业 "<<i+1<<" 的名称： ";cin>>p->name ;cout<<"\n输入该作业的优先级： ";cin>>p->super;cout<<"\n输入该作业所需的资源数目： ";cin>>p->needtime;needsource *fir,*sec;systemsource *cur;sec = p->source;for(int j=0; j<p->needtime ; j++){bool BOOL=true;fir = GetSpace(NEED);while(BOOL){cur = systemsor; //指向系统资源链表cout<<"\n输入第 "<<j+1<<" 个资源的名称：";cin>>fir->name;fir->link = NULL;while(cur != NULL) //保证输入的资源是系统有的{if(fir->name == cur->name ) //输入的是合法资源{BOOL = false;break;}elsecur = cur->link ;}if(cur == NULL) //输入的是非法资源cout<<"\n该资源不是系统资源，请重新输入...\n\n";}if(j==0)p->source = fir;elsesec->link = fir;sec = fir;}p->ptime = systemtime; //提交时间为当前系统时间p->ftime = p->rtime = 0;p->runflag = false; //开始时运行状态为否p->state = 'O'; //状态为就绪Orderp->link = NULL;sort(true);//参数为true表示插入就绪链表，当参数为false是表示要插入等待链表}}//----------------------------------------------------------------------------- int space() //查看就绪队列是否为空，返回其长度{int len=0; jcb *fir;fir = ready;while(fir != NULL){len++;fir=fir->link ;}return len;}//----------------------------------------------------------------------------- void attemper() //为作业分配资源函数{jcb *fir,*sec,*thr;systemsource *res;if(run != NULL) //如果有作业正在运行的话，优先为它们分配资源{sec = fir = run;while(fir != NULL){res = systemsor; //指向系统资源链表while(res != NULL){if(fir->source->name == res->name){//找到运行队列中所有作业需要的资源//并查看系统能否为其分配资源if(res->number > 0) //可以为该作业分配资源{res->number --; //资源数减1sec = fir; //继续分配队列中其它作业需要的资源fir = fir->link;}else //不能分配，插入等待队列{if(fir == run) //如果的运行队列的队首{run = run->link ;p= fir;sec = fir = run;}else{sec->link = fir->link;p=fir;fir = fir->link;}p->link = NULL;p->state = 'W'; //作业状态为等待Waitp->super --; //优先级减1，从而保证其它作业能得到资源runjcb --; //运行的作业数减1sort(false); //插入等待队列}break;}elseres = res->link ;}}}//为就绪队列中的作业分配资源sec = fir = ready;jcb *cur;while(runjcb <= maxrun && fir != NULL) //运行队列中的总数小于允许同时运行的总数{res = systemsor; //指向系统资源链表while(res != NULL){if(fir->source->name == res->name){if(res->number > 0) //能够为该作业分配资源{res->number --; //对应资源数目减1runjcb ++; //运行队列作业树木加1thr = fir;cur = run;//将该作业移出就绪队列if(fir == ready){ready = ready->link ;sec = fir = ready;}else{sec->link = fir->link ;fir = fir->link ;}thr->link = NULL;thr->state = 'R';if(thr->runflag == false){//该作业第一次运行，开始运行时间等于当前系统时间thr->rtime = systemtime;thr->runflag = true; //表示已经运行}//插入到运行队列的队尾if(run == NULL)run = thr;else{while(cur->link != NULL) //找到运行队列的队尾cur = cur->link ;cur->link = thr; //在队尾插入该作业}}else{//准备为就绪队列中的下一个作业分配资源sec = fir;fir = fir->link;}break; //跳处内while循环}res = res->link ; //指向系统资源链表的下一个资源，继续查找}}}//----------------------------------------------------------------------------- void display(jcb *pr){needsource *res;cout<<"\n\t"<<pr->name<<"\t"<<pr->ptime<<"\t"<<pr->rtime<<"\t"<<pr->ftime<<"\t"<<pr->super<<"\t"<<pr->state<<"\t"<<pr->source->name<<endl;res = pr->source->link;while(res != NULL){ //将作业所需的资源列表逐一打印出来cout<<"\t\t\t\t\t\t\t"<<res->name<<endl;res = res->link;}cout<<endl;}//----------------------------------------------------------------------------- void check() //打印在运行队列，就绪队列和等待队列中的作业的信息{jcb *pr;if(run == NULL)cout<<"\n 当前在运行队列没有任何作业...\n";else{cout<<"\n 当前在运行队列的作业参数如下...\n\n";cout<<"\tname\tptime\trtimr\tftime\tsuper\tstate\tsource"<<endl;pr = run;while(pr != NULL){display(pr); //打印作业信息函数pr = pr->link ;}}if(ready == NULL)cout<<"\n 当前在就绪队列没有任何作业...\n";else{cout<<"\n 当前在就绪队列的作业参数如下...\n\n";cout<<"\tname\tptime\trtimr\tftime\tsuper\tstate\tsource"<<endl;pr = ready;while(pr != NULL){display(pr); //打印作业信息函数pr = pr->link ;}}if(wait == NULL)cout<<"\n 当前在等待队列没有任何作业...\n\n";else{cout<<"\n 当前在等待队列的作业参数如下...\n\n";cout<<"\tname\tptime\trtimr\tftime\tsuper\tstate\tsource"<<endl;pr = wait;while(pr != NULL){display(pr); //打印作业信息函数pr = pr->link ;}}cout<<endl;}//----------------------------------------------------------------------------- void activation(char ResName) //激活在等待队列中的作业{//ResName为刚刚释放的资源的名称//在等待队列中找到某作业所需资源队列的第一个资源名称跟其相同的，激活之jcb *fir,*sec;if(wait == NULL) //等待队列为空，返回return;if(wait->source->name == ResName) //等待队列中第一个作业就是需要该资源的作业 //激活之{p = wait;wait = wait->link ;p->state = 'O'; //作业状态为就绪Orderp->link = NULL;sort(true); //将该作业插入到就绪队列中}else{//在等待队列中查找需要该资源的作业fir = wait;sec=fir->link ;while(sec != NULL){if(sec->source->name == ResName){p = sec;fir->link = sec->link ;p->state = 'O';p->link = NULL;sort(true); //将该作业插入到就绪队列中break;}else{fir = sec;sec = sec->link ;}}}}//------------------------------------------------------------------------------------------------void destory(jcb *pr) //打印运行完成的作业信息，并撤消之{pr->ftime = systemtime;cout<<"\n\n\n 作业 "<<pr->name<<" 已经完成...\n\n";cout<<" 相关参数如下："<<endl;cout<<"\n提交时间： "<<pr->ptime;cout<<"\n---------------------------";cout<<"\n开始运行时间： "<<pr->rtime;cout<<"\n---------------------------";cout<<"\n完成时刻： "<<pr->ftime;cout<<"\n---------------------------";cout<<"\n所需运行时间： "<<pr->needtime;cout<<"\n---------------------------";cout<<"\n实际运行时间： "<<pr->ftime-pr->rtime; //实际运行时间等于完成时刻//开始运行时刻cout<<"\n---------------------------";cout<<"\n周转时间： "<<pr->ftime-pr->ptime;//周转时间德育完成时刻-提交时刻cout<<"\n---------------------------";cout<<"\n带权周转时间 "<<float(pr->ftime-pr->ptime)/float(pr->needtime);//带权周转时间等于周转时间/所需的运行时间cout<<"\n---------------------------"<<endl;JCBTime += systemtime-pr->ptime; //将该作业的周转时间加入到作业总周转时间JCBTime_1 += float(JCBTime)/float(pr->needtime); //更新总带权周转时间cout<<endl;delete pr;}//----------------------------------------------------------------------------- void running() //运行函数//每运行一次相当于把运行队列中所有作业所需的第一个资源从所需资源队列中撤消掉{jcb *fir;systemsource *res; //系统资源needsource *abandon;if(run == NULL) //运行队列为空，没有运行作业return;fir = run;while(fir != NULL){res = systemsor; //res指向系统资源链表的表头while(res != NULL){if(fir->source->name == res->name) //运行的结果是该作业取消所需的第一个资源{abandon = fir->source; //abandon为需要释放的资源fir->source = fir->source->link;res->number ++; //释放该作业占用的但已经完成的资源activation(res->name); //激活等待队列中需要该资源的作业delete abandon;break;}elseres = res->link ;}fir = fir->link ;}}//----------------------------------------------------------------------------- void displayResult() //检查是否有运行完的作业{jcb *fir,*sec,*thr;if(run == NULL) //运行队列为空，返回return;fir = sec = run; //在运行队列中找到已经完成的作业while(fir != NULL){if(run->source == NULL) //所需资源链表为空，该作业已经完成{thr = run;run = run->link ;fir = sec = run;destory(thr); //打印该作业的参数信息并撤消该作业runjcb --; //当前运行队列的作业数减1cout<<"\n按任意键继续..."<<endl;getch();}elseif(fir->source == NULL){thr = fir;sec->link = fir->link ;fir = fir->link ;destory(thr); //打印该作业的参数信息并撤消该作业runjcb --; //当前运行队列的作业数减1cout<<"\n按任意键继续..."<<endl;getch();}else{sec = fir;fir = fir->link ;}}}//----------------------------------------------------------------------------- void main(){int len,h=0;bool flag = true;init(); //初始化系统资源，形成链表input(); //输入作业及其相关信息len = space();systemtime = 0; //开始系统时间确保是零while((len != 0) && (flag)){system("cls");cout<<"\n 当前运行的步数："<< h+1<<endl;h++;attemper(); //作业调度check(); //查看当前作业的参数running(); //运行符合条件的作业systemtime ++; //系统时间加1cout<<"\n\n按任意键继续..."<<endl;getch();system("cls");displayResult(); //打印已经完成的作业参数if(ready == NULL){if(run == NULL)flag = false; //当运行队列和就绪队列都为空时，作业运行完成}}cout<<"\n\n 全部作业完成，当前系统时间为： "<<systemtime<<endl;cout<<"\n\n这组作业的平均周转时间："<<float(JCBTime)/float(JCBNum)<<endl;cout<<"这组作业的平均带权周转时间： "<<JCBTime_1/float(JCBNum)<<endl;cout<<"\n\n 按任意键退出..."<<endl;getch();}五、系统演示⒈开始（初始化JCB）2．输入四个作业（A，B，C，D），它们所需的资源有冲突，调度算法第一次分配资源的情况如下：运行队列（最大并行度为3）就绪队列和等待队列：3．从运行队列中可以看到作业B和A在第二部都需要资源‘D‘，但系统的D资源只有一个，所以接下来B和A发生冲突，将优先极低的作业插入等待队列，如下：4．当有作业完成，打印其信息：5．该组作业全部完成：六、总结至此，作业调度（多通道）课程设计全部完成…刘金宏2006-5-18（注：可编辑下载，若有不当之处，请指正，谢谢!）。

作业调度一、实验要求:编写一个作业调度程序，用一种调度算法，实现对一个给定的作业序列的调度。

并计算平均周转时间和加权周转时间。

二、设计思想:1.填写资源表,记录打印机和磁带机的分配情况；2. 填写内存自由区表,实现内存的分配和回收；3. 填写作业表JCB,记录作业所需的资源,和运行的过程；4.设立三个队列,后备队列,阻塞队列,运行队列。

5.算法流程初始化:将作业队列压入后备队列.置counttime指针为0(用来表示系统时间).循环:a)判断该时刻运行队列中有无作业到达终止时间.到达就退出队列.b)判断该时刻后备队列中有无作业要求进入运行队列.有者压入阻塞队列. 这里采用的是FCFS调度算法,所以先要将作业压入阻塞队列,等待先前进入阻塞队列的作业先运行.c)看阻塞队列是否有作业要运行,有就判断条件是否符合.资源是否足够.若运行,看运行队列中有多少作业在运行.用并行算法算出终止时间, 压入运行队列.d)counttime++,循环,直至所有队列为空.二、主要数据结构程序采用VC6MFC环境开发，（用到MFC的数组类）为了演示方便，本程序模拟1-5个作业,打印机数量为1台，磁带机为2台struct JCB{UINT ID; //作业号UINT RunTime;//实际运行时间UINT SetTime;//放入队列时间UINT TakeMem;//占用内存UINT MemSize;//内存大小float TakeTime;//要求计算时间UINT PrintNum;//申请的打印机数量UINT TapeNum;//申请的磁带机数量};struct RC{UINT Type; //资源类型是打印机还是磁带机?int User; //标识哪个作业使用了本资源int yPos; //用于画图状态图的参数COLORREF tagColor;//区别各个作业的颜色，用于图形显示};struct FBT{UINT size; //空闲块大小UINT addr; //空闲块首址};CArray<JCB,JCB>JCBList; //后备队列CArray<JCB,JCB>JCBWait; //阻塞队列CArray<JCB,JCB>JCBRun; //运行队列CArray<FBT,FBT>FBTList; //内存自由区表RC RCList[3]; //描述资源设备使用情况的结构数组UINT nTaper //可使用的磁带机数量UINT nPrinter //可使用的打印机数量三、主要算法与部分代码申请内存资源(成功返回内存块首址，失败返回0)int CTab1::get_block(UINT NeedSize){int i=0;int p;while (FBTList[i].size>0 && FBTList[i].size<NeedSize && i<FBTList.GetSize()) i++;if(i>=FBTList.GetSize()) return 0;p=FBTList[i].addr+FBTList[i].size-NeedSize;FBTList[i].size-=NeedSize;ShowMemList();return p; //返回分得的内存块首址}1.回收申请的内存块，并分三种情况合并空闲区bool CTab1::free_block(int addr,int size) //回收已分配的内存并修改自由区表{bool flag=false;int i=0;int nIndex;while (i<FBTList.GetSize()) //第一遍循环判断回收的块是否有下接区，有就合并，并向下执行。

流水作业调度1.问题描述：定义：设有n个作业，每一个作业Ti均被分解为m项任务：Ti1, Ti2, …, Tim(1≤i ≤n)，要把这些任务安排到m台机器上进行加工。

如果任务的安排满足下列3个条件，则称该安排为流水作业调度：1.每个作业i的第j项任务Tij (1≤i≤n, 1≤j≤m) 只能安排在机器Mj上进行加工2.作业i的第j项任务Tij(1≤i≤n, 2≤j≤m)的开始加工时间均安排在第j-1项任务Ti,j-1加工完毕之后，即任何一个作业的任务必须依次完成，前一项任务完成之后才能开始着手下一项任务；3.任何一台机器在任何一个时刻最多只能承担一项任务。

设任务Tij在机器Mj上进行加工需要的时间为tij。

如果所有的tij (1≤i≤n, 1≤j≤m)均已给出，要找出一种安排作业的方法，使得完成这n个作业的加工时间为最少。

完成n个作业的加工时间为从安排的第一个作业开始加工, 到最后一个作业加工完毕，其间所需要的时间。

2.分析：一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。

在一般情况下，机器M2上会有机器空闲和作业积压2种情况。

设全部作业的集合为N={1, 2, …, n}。

S N是N的作业子集。

在一般情况下，机器M1开始加工S中作业时，机器M2还在加工其它作业，要等时间t后才可利用。

将这种情况下完成S中作业所需的最短时间记为T(S, t)。

流水作业调度问题的最优值为：T(N,0)。

设M1和M2加工作业i所需的时间分别为ai和bi。

n个流水作业的一个最优调度，它所需的加工时间为 a(1)+T’。

T’：是在机器M2的等待时间为b(1)(2), …, (n)所需的时间。

记S=N - {(1)}，则有T’=T(S, b(1))流水作业调度的Johnson法则S在机器M2的等待时间为t时的任一最优调度。

若π(1)=i, π(2)=j，则由动态规划递归式可得：T（s,t）=ai+T(S-{is],bi+max{t-ai,0})=ai+aj+T(s-{i,j},tij)若作业i和j满足，则称作业i和j满足Johnson不等式。

0018算法笔记——【动态规划】流水作业调度问题与Johnson 法则1、问题描述：n个作业{1，2，…，n}要在由2台机器M1和M2组成的流水线上完成加工。

每个作业加工的顺序都是先在M1上加工，然后在M2上加工。

M1和M2加工作业i所需的时间分别为ai和bi。

流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。

2、问题分析直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。

在一般情况下，机器M2上会有机器空闲和作业积压2种情况。

设全部作业的集合为N={1，2，…，n}。

S是N的作业子集。

在一般情况下，机器M1开始加工S中作业时，机器M2还在加工其他作业，要等时间t后才可利用。

将这种情况下完成S中作业所需的最短时间记为T(S,t)。

流水作业调度问题的最优值为T(N,0)。

设π是所给n个流水作业的一个最优调度，它所需的加工时间为aπ(1)+T’。

其中T’是在机器M2的等待时间为bπ(1)时，安排作业π(2)，…，π(n)所需的时间。

记S=N-{π(1)}，则有T’=T(S,bπ(1))。

证明：事实上，由T的定义知T’>=T(S,bπ(1))。

若T’>T(S,bπ(1))，设π’是作业集S在机器M2的等待时间为bπ(1)情况下的一个最优调度。

则π(1)，π'(2)，…，π'(n)是N的一个调度，且该调度所需的时间为aπ(1)+T(S,bπ(1))<aπ(1)+T’。

这与π是N的最优调度矛盾。

故T’<=T(S,bπ(1))。

从而T’=T(S,bπ(1))。

这就证明了流水作业调度问题具有最优子结构的性质。

由流水作业调度问题的最优子结构性质可知:从公式（1）可以看出，该问题类似一个排列问题，求N个作业的最优调度问题，利用其子结构性质，对集合中的每一个作业进行试调度，在所有的试调度中，取其中加工时间最短的作业做为选择方案。

操作系统实验报告：作业调度1. 引言作业调度是操作系统中的一个重要概念，它涉及到如何合理地安排计算机系统中的作业执行顺序，以最大程度地提高系统的效率和性能。

本文将介绍作业调度的基本概念和主要算法，以及在实验中的应用。

2. 作业调度的概念作业调度是指根据一定的策略和算法，按照一定的顺序从作业队列中选取作业，将其分配给可用资源来执行的过程。

作业调度的目标是实现公平、高效的任务分配，以提高系统的整体性能。

3. 作业调度算法3.1 先来先服务（FCFS）先来先服务是最简单的作业调度算法，即按照作业提交的顺序来执行。

当一份作业到达系统后，它将被放入作业队列的末尾。

一旦当前执行的作业完成，系统将选择队列中的下一个作业来执行。

3.2 短作业优先（SJF）短作业优先算法是根据作业的执行时间来进行调度，执行时间越短的作业优先级越高。

当一个作业进入系统时，系统会检查队列中的所有作业，并选择执行时间最短的作业来执行。

3.3 优先级调度优先级调度算法是根据作业的优先级来进行调度，优先级越高的作业优先级越高。

每个作业都会被分配一个优先级值，系统会按照优先级从高到低的顺序来执行作业。

3.4 时间片轮转调度时间片轮转调度算法将作业分为多个时间片，每个时间片的执行时间相等。

当一个作业进入系统时，系统会分配给它一个时间片，如果在时间片内作业没有完成，则将其放回队列的末尾，并执行下一个作业。

4. 实验中的应用在操作系统实验中，作业调度是一个重要的实验内容。

通过实验，我们可以深入了解不同调度算法的特点和适用场景。

实验中，我们可以使用模拟器来模拟作业调度的过程。

我们可以创建一个作业队列，然后使用不同的调度算法来执行这些作业，并记录它们的执行时间和系统的吞吐量。

通过实验，我们可以比较不同算法在不同场景下的表现，选择最适合当前系统的作业调度算法。

5. 结论作业调度是一个重要的操作系统概念，它决定了系统的性能和效率。

在本文中，我们介绍了作业调度的基本概念和常用算法，并讨论了在实验中的应用。

0018算法笔记——【动态规划】流水作业调度问题与Johnson 法则1、问题描述：n个作业{1，2，…，n}要在由2台机器M1和M2组成的流水线上完成加工。

每个作业加工的顺序都是先在M1上加工，然后在M2上加工。

M1和M2加工作业i所需的时间分别为ai和bi。

流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。

2、问题分析直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。

在一般情况下，机器M2上会有机器空闲和作业积压2种情况。

设全部作业的集合为N={1，2，…，n}。

S是N的作业子集。

在一般情况下，机器M1开始加工S中作业时，机器M2还在加工其他作业，要等时间t后才可利用。

将这种情况下完成S中作业所需的最短时间记为T(S,t)。

流水作业调度问题的最优值为T(N,0)。

设π是所给n个流水作业的一个最优调度，它所需的加工时间为aπ(1)+T’。

其中T’是在机器M2的等待时间为bπ(1)时，安排作业π(2)，…，π(n)所需的时间。

记S=N-{π(1)}，则有T’=T(S,bπ(1))。

证明：事实上，由T的定义知T’>=T(S,bπ(1))。

若T’>T(S,bπ(1))，设π’是作业集S在机器M2的等待时间为bπ(1)情况下的一个最优调度。

则π(1)，π'(2)，…，π'(n)是N的一个调度，且该调度所需的时间为aπ(1)+T(S,bπ(1))<aπ(1)+T’。

这与π是N的最优调度矛盾。

故T’<=T(S,bπ(1))。

从而T’=T(S,bπ(1))。

这就证明了流水作业调度问题具有最优子结构的性质。

由流水作业调度问题的最优子结构性质可知:从公式（1）可以看出，该问题类似一个排列问题，求N个作业的最优调度问题，利用其子结构性质，对集合中的每一个作业进行试调度，在所有的试调度中，取其中加工时间最短的作业做为选择方案。