精华内容
下载资源
问答
  • 2021-05-18 14:43:09

    /*

    批处理作业调度

    输入: 3

    2 1

    3 1

    2 3

    输出:18

    1 3 2

    */

    #include

    #include

    #include

    #define MAXSIZE 100

    int n; //作业的个数

    int m1[MAXSIZE]; //每个作业在机器一上完成的时间

    int m2[MAXSIZE]; //每个作业在机器二上完成的时间

    int f1; //机器一完成的时间

    int f2[MAXSIZE]; //机器二完成的时间

    int cf; //当前所用时间

    int bestf; //当前最优时间

    int x[MAXSIZE]; //当前解

    int bestx[MAXSIZE]; //最优解

    //输入

    void input();

    //初始化

    void init();

    //回溯法

    void backtrack(int);

    //交换

    void Swap(int*, int*);

    int main(void)

    {

    int i = 1;

    while (1)

    {

    input();

    init();

    backtrack(1);

    printf("%d\n", bestf);

    for (i = 1; i <= n; ++i)

    {

    printf("%d ", bestx[i]);

    }

    printf("\n");

    }

    return 0;

    }

    void input()

    {

    int i = 1;

    printf("please enter n:");

    scanf("%d", &n);

    for (i = 1; i <= n; ++i)

    {

    scanf("%d %d", &m1[i], &m2[i]);

    }

    }

    void init()

    {

    int i = 1;

    cf = 0;

    bestf = INT_MAX;

    f1 = 0;

    for (i = 1; i <= n; ++i)

    {

    x[i] = i;

    f2[i] = 0;

    }

    }

    void backtrack(int t)

    {

    int i = 1;

    int j = 1;

    if (t > n)

    {

    if (cf < bestf)

    {

    bestf = cf;

    for (i = 1; i <= n; ++i)

    {

    bestx[i] = x[i];

    }

    }

    }

    else

    {

    for (j = t; j <= n; ++j)

    {

    f1 += m1[x[j]];

    f2[t] = (f1 > f2[t - 1] ? f1 : f2[t - 1]) + m2[x[j]];

    cf += f2[t];

    if (cf < bestf)

    {

    Swap(&x[t], &x[j]);

    backtrack(t + 1);

    Swap(&x[t], &x[j]);

    }

    f1 -= m1[x[j]];

    cf -= f2[t];

    }

    }

    }

    void Swap(int *a, int *b)

    {

    int temp = *a;

    *a = *b;

    *b = temp;

    }

    更多相关内容
  • 批处理作业调度问题给定n个作业的集合{J1J2…Jn}。每个作业必须先由机器1处理,然后由机器2处理。作业Ji需要机器j的处理时间为tji。对于一个确定的作业调度,设Fji是作业i在机器j上完成处理的时间。所有作业在机器2...
  • 课程的随堂作业,C语言的,用dev就能运行,萌新代码,勿喷,仅仅帮助不想写作业的朋友方便一下,反正老师也不会仔细检查的
  • 操作系统小作业
  • #include #include<queue> using namespace std; class MinHeapNode ... //当前作业调度 }; void MinHeapNode::Init(int n) { //最小堆结点初始化 x=new int[n]; for(int i=0;i;i++) x[i]=i;
  • 问题描述:/*************************************************************批处理作业调度给定n个作业的集合{J1,J2,…,Jn}。每个作业必须先由机器1处理,然后由机器2处理。作业Ji需要机器j的处理时间为tji。对于一...

    问题描述:

    /*************************************************************

    批处理作业调度

    给定n个作业的集合{J1,J2,…,Jn}。

    每个作业必须先由机器1处理,然后由机器2处理。

    作业Ji需要机器j的处理时间为tji。

    对于一个确定的作业调度,设Fji是作业i在机器j上完成处理的时间。

    所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和。

    f = F21 + F22 + F23 + ... + F2n

    批处理作业调度问题要求对于给定的n个作业,

    制定最佳作业调度方案,使其完成时间和达到最小。

    *************************************************************/

    public class FlowShop

    {

    int n,         //作业数;

    f1,        //机器1完成处理时间;

    f,         //完成时间和;

    bestf;     //当前最优值;

    int [][]m;      //各作业所需的处理时间;

    int []x;        //当前作业调度;

    int []bestx;    //当前最优作业调度;

    int []f2;       //机器2完成处理时间;

    private  void backtrack(int i)

    {

    if(i>n)

    {

    for (int j=1;j<=n;j++)

    {

    bestx[j]=x[j];

    System.out.print(x[j]+" ");

    }

    System.out.println();

    bestf=f;

    System.out.println("每条深度优先搜索结果为:"+bestf);

    }

    else

    for(int j=i;j<=n;j++)

    {

    f1+=m[x[j]][0];

    f2[i]=((f2[i-1]>f1)? f2[i-1]:f1)+m[x[j]][1];

    f+=f2[i];

    //      if(f

    if(true)

    {

    MyMath.swap(x,i,j);

    backtrack(i+1);

    MyMath.swap(x,i,j);

    }

    f1-=m[x[j]][0];

    f-=f2[i];

    }

    }

    public void ShowTest()

    {

    n=3;

    bestf=Integer.MAX_VALUE;

    f1=0;

    f=0;

    int [][]m={{0,0},{2,1},{3,1},{2,3}};

    int []x={0,1,2,3};

    int []bestx={0,1,2,3};

    f2=new int[4];

    this.m = m;

    this.x=x;

    this.bestx=bestx;

    this.f2=f2;

    backtrack(1);

    System.out.println("当前最优值:"+bestf);

    System.out.println("当前最优作业调度");

    for(int i=1;i<=n;i++)

    {

    System.out.print(bestx[i]+"  ");

    }

    }

    public static void main(String[] args)

    {

    // TODO Auto-generated method stub

    FlowShop fs=new FlowShop();

    fs.ShowTest();

    }

    }

    class MyMath

    {

    public MyMath(){}

    public static int[] swap(int[] x,int i,int j)

    {

    // int[] returnString=new int[3];

    int ss;

    ss=x[j];

    x[j]=x[i];

    x[i]=ss;

    return x;

    }

    }

    展开全文
  • 本次课程设计要求用高级语言编写和调试一个单道批处理系统的作业调度的模拟程序,了解作业调度在操作系统中的作用,以加深对作业调度算法的理解 2. 课程设计的开发语言 C语言 3. 功能描述 在批处理系统中,作业进入...
  • 单道批处理模拟作业调度: 模拟作业调度的实现,分别实现 先来先服务(FCFS)、最短作业优先(SJF)、响应比高者优先(HRN) 实现思想: 1) 先来先服务算法:是按照作业进入输入井的先后次序来挑选作业,先进入输入...

    单道批处理模拟作业调度:

    模拟作业调度的实现,分别实现

    先来先服务(FCFS)、最短作业优先(SJF)、响应比高者优先(HRN)

    实现思想:

    1) 先来先服务算法:是按照作业进入输入井的先后次序来挑选作业,先进入输入井的作业优先被挑选,当系统中现有的尚未分配的资源不能满足先进入输入井的作业时,那么顺序挑选后面的作业。

    2) 最短作业优先算法:在作业到达的情况下,总是按作业要求运行的时间来选择作业,每次挑选要求运行时间短且资源要求能满足的作业先进入主存执行。

    3) 当作业执行结束进入完成状态时,做好释放资源等善后工作。

    4) 本实验主要模拟作业调度,所以对处理器调度、作业控制过程简化。用输入随机数模拟处理器调度,用输出“用户名、作业名”模拟一个作业已经执行结束。

    5) 为作业分配资源可用修改资源分配表来代替。

    主程序流程图:

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QvXw3UIQ-1611392854678)(file:///C:/Users/www24/AppData/Local/Packages/oice_16_974fa576_32c1d314_35ca/AC/Temp/msohtmlclip1/01/clip_image002.gif)]

    先来先服务算法:

    流程图:

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-hedGlMTq-1611392809185)(file:///C:/Users/www24/AppData/Local/Packages/oice_16_974fa576_32c1d314_35ca/AC/Temp/msohtmlclip1/01/clip_image002.gif)]

    关键代码:

    public void fcfs()/*先来先服务*/ {    sort();    running();    output();}
    

    短作业优先:

    流程图:

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jwUyAe8O-1611392809186)(file:///C:/Users/www24/AppData/Local/Packages/oice_16_974fa576_32c1d314_35ca/AC/Temp/msohtmlclip1/01/clip_image004.gif)]

    关键代码:

    public void sjf()/*短作业优先*/ {
        int min;
    
        sort();
        for (m = 0; m < num; m++) {
            i = 0;
            if (m == 0)
                jk.get(m).finish = jk.get(m).arrivetime + jk.get(m).runtime;
            else
                jk.get(m).finish = jk.get(m - 1).finish + jk.get(m).runtime;
            for (n = m + 1; n < num; n++) {
                if (jk.get(n).arrivetime <= jk.get(m).finish)//判断每次作业完成之后又有多少作业到达
                    i++;
            }
    
            for (k = m + 1; k < i + m; k++)//找出到达后的作业中运行时间最小的作业
            {
                min = k;
                for (int j = k + 1; j < i + m + 1; j++) {
    
                    //printf("%f\n", jk[j].runtime);
                    //printf("%f\n", jk[min].runtime);
                    if (jk.get(j).runtime < jk.get(min).runtime) {
    
                        min = j;
    
                    }
                }
                Collections.swap(jk, k, min);
    
            }
        }
        running();
        output();
    }
    

    高响应比优先:

    流程图:

    在这里插入图片描述

    关键代码:

    public void hrrf()/*最高响应比优先*/ {
        int max;
    
        sort();
        for (m = 0; m < num; m++) {
            i = 0;
            if (m == 0)
                jk.get(m).finish = jk.get(m).arrivetime + jk.get(m).runtime;
            else
                jk.get(m).finish = jk.get(m - 1).finish + jk.get(m).runtime;
            for (n = m + 1; n < num; n++) {
                if (jk.get(n).arrivetime <= jk.get(m).finish)
                    i++;
            }
    
            for (k = m + 1; k < i + m; k++) {
                max = k;
                for (int j = k + 1; j < i + m + 1; j++) {
                    // printf("%d\n", i + m + 1);
                    if ((jk.get(m).finish - jk.get(max).arrivetime + jk.get(max).runtime) / jk.get(max).runtime <=
                            (jk.get(m).finish - jk.get(j).arrivetime + jk.get(j).runtime) / jk.get(j).runtime)//响应比大的先执行
                    {
                        max = j;
    
                    }
                }
    
                Collections.swap(jk, k, max);
    
            }
    
        }
        running();
        output();
    }
    

    重复调用的函数:

      public void output( ) {
            float numT = 0, numW = 0, avgT = 0, avgW = 0;
            System.out.println("-----------------------------------------------------------------------\n");
            System.out.println(" 作业名  提交时间  运行时间  开始时间  完成时间  周转时间  带权周转时间\n");
            for (i = 0; i < num; i++) {
                System.out.println(jk.get(i).name + "\t\t" + jk.get(i).arrivetime + "\t\t" +
                        jk.get(i).runtime + "\t\t" + jk.get(i).run + "\t\t" + jk.get(i).finish + "\t\t" + jk.get(i).T + "\t\t" + jk.get(i).W);
                System.out.println("\n");
                numT = numT + jk.get(i).T;
                numW = numW + jk.get(i).W;
            }
            System.out.println("-----------------------------------------------------------------------\n");
            avgT = numT / num;
            avgW = numW / num;
            System.out.println("平均作业周转时间:" + avgT);
            System.out.println("\n");
            System.out.println("平均带权作业周转时间:" + avgW);
            System.out.println("\n");
        }
    
       public void sort() {
            int i, j;
            for (j = 0; j < num; j++) {
                for (i = 0; i < num - j - 1; i++) {
                    if (jk.get(i).arrivetime > jk.get(i + 1).arrivetime) {
                        Collections.swap(jk, i, i + 1);
    
                    }
                }
            }
        }
        
        public void running() {
            for (k = 0; k < num; k++) {
                if (k == 0)/*运行第一个作业*/ {
                    jk.get(k).run = jk.get(k).arrivetime;
                    jk.get(k).finish = jk.get(k).run + jk.get(k).runtime;
                } else {
                    if (jk.get(k).arrivetime >= jk.get(k - 1).finish)/*当前作业已经结束,下一个作业还没有到达或者刚好到达*/ {
                        jk.get(k).run = jk.get(k).arrivetime;
                        jk.get(k).finish = jk.get(k).run + jk.get(k).runtime;
                    } else/*当前作业未完成,下一个作业已到达*/ {
                        jk.get(k).run = jk.get(k - 1).finish;
                        jk.get(k).finish = jk.get(k).run + jk.get(k).runtime;
                    }
                }
        
            }
            for (k = 0; k < num; k++) {
                jk.get(k).T = jk.get(k).finish - jk.get(k).arrivetime;
                jk.get(k).W = jk.get(k).T / jk.get(k).runtime;
            }
        }
    
    展开全文
  • 这是一个用Java实现解决批处理作业调度问题的算法
  • 用动态规划、分支限界、回溯解决01背包、批处理作业调度问题
  • 本例是java实现的批处理作业调度程序,采用的是回溯法,排列集合的方式,参考书籍为:算法设计与分析
  • 题目1 多道批处理作业调度模拟程序

    千次阅读 2020-04-14 16:48:38
    题目1 多道批处理作业调度模拟程序 一、目的: 熟悉作业调度算法及其实现 二、内容: 编写一个程序完成多道批处理作业调度 三、要求: 只考虑1个CPU的资源,其他资源不考虑 使用响应比高者优先算法 程序采用键盘输入...

    题目1 多道批处理作业调度模拟程序

    一、目的:

    熟悉作业调度算法及其实现

    二、内容:

    编写一个程序完成多道批处理作业调度

    三、要求:

    只考虑1个CPU的资源,其他资源不考虑
    使用响应比高者优先算法
    程序采用键盘输入,输入格式为:

    K
       TJ1    YS1
       …… 
       TJK    YSK
    

    其中K是作业数(>0),TJi提交时间,YSi (i=1~K)是作业预计的运行时间(以分钟计)TJ的输入格式是XXYY,其中XX是时,YY是分,如10点28分,输入为1028。但内部计算要以60进制来算。要求输出按照作业调度的先后次序输出结果,每行为一个作业状态,从左到右分别是调度次序,作业号,调度时间,周转时间和带权周转时间最后一行输出两个数,第一为平均周转时间,第二为平均带权周转时间。


    实验截图在这里插入图片描述##### 下载链接
    展开全文
  • . . .. . .. 专业.专注 .单道批处理系统作业调度课程设计的目的操作系统课程的一个非常重要的环节是培养计算机专业学生的系统程序设计能力。通过操作系...
  • 里面包含完整的FCFS.SJF以及HRN算法
  • 算法设计与分析——分支限界法之批处理作业调度问题
  • 回溯法之批处理作业调度1. 问题描述​n个作业集合{1, 2, ..., n}。每个作业先由机器1处理,再由机器2处理。作业i需要机器j处理的时间为Mij 。Mij机器1机器2作业121作业231作业323​对于一个确定的作业调度,设Fij 是...
  • 批处理作业调度问题的java实现(回溯法)具体问题描述以及C/C++实现参见网址http://blog.csdn.net/liufeng_king/article/details/8764319/*** 批处理作业调度问题--回溯法(排列树)* @author Administrator**/public ...
  • 代码: #include using namespace std; const int MAX=100; const int MACHINE=2; int n; int M[MAX][MACHINE];... printf("最优调度:\n"); for(int i=0; i printf("%d ", bestx[i]+1); printf("\n"); return 0; }
  • java实现的简易单道批处理,包括先来先服务(FCFS)、最短作业优先(SJF)、响应比高者优先(HRN)的调度算法。
  • 回溯法批处理作业调度问题(java实现) 问题描述:设有 n个作业{J1,J2,……Jn}需要处理,每个作业Ji(1≤ i ≤ n)都有两项任务组成。两项任务需要分别在2台机器即机器1和机器2上处理。要求每个作业Ji 的第一项...
  • 对于一个确定的作业调度,设Fji是作业i在机器j上完成处理时间。则所有作业在机器2上完成处理时间和f是指把F2i将i从1-n求和,称为该作业调度的完成时间和。2、简单描述对于给定的n个作业,指定最佳作业调度方案,使...
  • 【分支限界法】批处理作业调度问题 给定n个作业的集合{J1,J2,…,Jn}。每个作业必须先由机器1处理,然后由机器2处理。作业Ji需要机器j的处理时间为tji。对于一个确定的作业调度,设Fji是作业i在机器j上完成处理的时间...
  • 批处理作业调度分支限界算法(1)问题分析:给定n个作业的集合{J1,J2,…,Jn}。每个作业必须先由机器1处理,然后由机器2处理。作业Ji需要机器j的处理时间为tji。对于一个确定的作业调度,设Fji是作业i在机器j上完成处理...
  • 一.问题描述 给定n个作业的集合J=(J1, J2, … , Jn)。每一作业Ji都有两项 任务要分别在2台机器上完成. 每一作业须先由机器l处理, 再由机器2...批处理作业调度问题要从n个作业的所有排列中找出有最小完成时间和的作业
  • 题目是批量处理作业调度,那么我们可以得知,这是让我们完成一个作业之后再去完成另一个作业 思路: 1.姑且先给我们的作业边上序号 a,b,c三个作业,那么我们可以得知关于这三个作业的 的安排有6种方式,那么我们的...
  • 1、问题描述 每一个作业Ji都有两项任务分别在2台机器上完成。每个作业必须先有机器1处理,然后再...批处理作业调度旨在求出使其完成时间和达到最小的最佳调度序列; 流水线调度问题旨在求出使其最后一个作业的完成时
  • 批处理作业调度【回溯算法】

    千次阅读 多人点赞 2020-12-09 09:53:47
    批处理作业调度 问题描述       给定n个作业的集合 J=(J1J_1J1​,J2J_2J2​,……,JnJ_nJn​)。每个作业JiJ_iJi​都有两项任务分别在两台机器上完成。每个作业必须先由机器1处理...
  • 道批处理作业模拟程序 熟悉作业调度算法及其实现 只考虑一个CPU的资源 (考虑了空转的情况)
  • 批处理作业调度-分支界限法package test;import java.util.ArrayList;import java.util.Collections;import java.util.Comparator;import java.util.List;/*** Created by saishangmingzhu on 2018/12/6.* 批处理...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 22,162
精华内容 8,864
关键字:

单道批处理作业调度