批处理作业调度（回溯法）（操作系统作业调度问题，请具体详细解答一下每一个作业的开始，完成，）

本文目录

• 操作系统作业调度问题，请具体详细解答一下每一个作业的开始，完成，
• 编程高手进，批处理作业调度和流水作业调度区别!
• 作业调度算法的选择原则有哪几个
• 回溯法 批处理作业调度
• 五个回归溯源报告怎么写范文
• 两道作业的批处理系统怎么算
• 实时操作系统常用任务调度算法有哪些
• 一个批处理型作业，从进入系统并驻留在外存的后备队列上开始，直至运行完毕，可能经历的3种调度是哪3种

操作系统作业调度问题，请具体详细解答一下每一个作业的开始，完成，

给定n个作业的集合{J1,J2,…,Jn}。每个作业必须先由机器1处理，然后由机器2处理。作业Ji需要机器j的处理时间为tji。对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和。
批处理作业调度问题要求对于给定的n个作业，制定最佳作业调度方案，使其完成时间和达到最小。
例：设n=3，考虑以下实例：
这3个作业的6种可能的调度方案是1,2,3；1,3,2；2,1,3；2,3,1；3,1,2；3,2,1；它们所相应的完成时间和分别是19，18，20，21，19，19。易见，最佳调度方案是1,3,2，其完成时间和为18。
限界函数
批处理作业调度问题要从n个作业的所有排列中找出具有最小完成时间和的作业调度，所以如图，批处理作业调度问题的解空间是一颗排列树。
在作业调度问相应的排列空间树中，每一个节点E都对应于一个已安排的作业集。以该节点为根的子树中所含叶节点的完成时间和可表示为：
设|M|=r，且L是以节点E为根的子树中的叶节点，相应的作业调度为{pk,k=1,2,……n}，其中pk是第k个安排的作业。如果从节点E到叶节点L的路上，每一个作业pk在机器1上完成处理后都能立即在机器2上开始处理，即从pr+1开始，机器1没有空闲时间，则对于该叶节点L有：
注：(n-k+1)t1pk,因为是完成时间和，所以，后续的(n-k+1)个作业完成时间和都得算上t1pk。
如果不能做到上面这一点，则s1只会增加，从而有：。
类似地，如果从节点E开始到节点L的路上，从作业pr+1开始，机器2没有空闲时间，则：
同理可知，s2是的下界。由此得到在节点E处相应子树中叶节点完成时间和的下界是：
注意到如果选择Pk，使t1pk在k》=r+1时依非减序排列，S1则取得极小值。同理如果选择Pk使t2pk依非减序排列，则S2取得极小值。
这可以作为优先队列式分支限界

编程高手进，批处理作业调度和流水作业调度区别!

流水作业调度的最终目标是要求完成所有任务的时间最短，所以把最后一个任务的完成时间作为标准；而批处理作业调度的目的是要让每一个作业都尽快得到处理，所以要把每个作业的完成时间之和作为标准。两者看上去相似，但实际上还是有区别的，可能在某些情况下调度是顺序是一样的。
批处理作业采用回溯法，一定能够得到最优解，因为你搜索的是整个解空间；
流水作业调度采用动态规划法，同样能够等到最优解，这个是可以证明的。

作业调度算法的选择原则有哪几个

批处理作业的调度算法主要有以下几种：
①先来先服务算法。原则上按照作业进入输入井的次序调度，如果作业的资源得不到满足，将会推迟调度，它的资源得到满足的时候会优先被调度进来。
优点：具有一定的公平性。
缺点：系统的吞吐率低，平均周转时间长，有大作业到来的时，许多小作业推迟调度。
②计算时间短的作业优先．优先调度计算时间短的作业进行调度，资源不满足的情况下推迟调度。在这种调度算法下，要求用户要对作业的计算时间预先有一个估计，调度以此为依据。
优点：由于被选中的作业计算时间，所以不能尽快地完成并退出系统，降低了作业的平均等待时间，提高了系统的吞吐率。
缺点：大作业会不满意，而且极限情况下使得某些大作业始终得不到调度。
③响应比高者优先算法。该算法考虑了计算时间等待时间，既考虑了计算时间短的作业优先，又考虑了大作业长期等待的问题。所谓响应比是按照以下公式来定义的：
响应比R=等待时间/计算时间
这里的计算时间是估计的作业计算时间，从公式看，计算时间越短，响应比越高；而另一方面，大作业等待时间越长，响应比也会越大。一个作业完成以后，需要重新计算一下在输入井中的各个作业的响应比，最高的将优先调度。
④优先数调度算法。为每一个作业指定一个优先数，优先数高的作业先被调度。对于优先数相等的作业采用先来先服务的策略。优先数的制定原则是：作业的缓急程序，估计的计算时间，作业的等待时间，资源申请情况等因素综合考虑。
⑤均衡调度算法。使用不同资源的进程同时执行，减少作业等待同类设备而耗费的时间，加快作业的执行。

回溯法 批处理作业调度

总的完成时间可以认为是第二台机器完成最后一个作业的时间，所以19是从第二台机器完成作业的时间得来，根据课本提供的数据，就以1 2 3调度顺序为例：第二台机器完成第1个作业时共用了3小时（其中2小时是第一台机器处理作业1时机器2空闲的时间），第二台机器完成第2个作业时共用了6小时（其中前5小时是前面作业1和机器2的空闲造成的），第二台机器完成第3个作业时共用了10小时（其中前7小时是前面作业1、作业2和机器2的空闲造成的），所以3+6+10=19

五个回归溯源报告怎么写范文

五个回路溯源分析1. 回溯法的基本概念用回溯法求解问题时，应明确问题的解空间，问题的解空间至少应包含问题的一个最优解，确定了解空间的组织结构后，回溯法从开始结点（根结点）出发，以深度优先方式搜索整个解空间，这个开始结点成为活结点，同时成为当前的扩展结点，在当前扩展结点处，如果在当前扩展结点处不能在向纵深方向移动，则当前扩展结点就成为死结点，此时应往回移动（回溯）至最近的一个活结点处，并让这个活结点成为当前的扩展结点，回溯法以这种工作方式递归的在解空间中搜索，直至找到所要求的的解或解空间中已无活结点时为止2. 回溯法搜索空间树时，通常采用两种策略来避免无效的搜索，提高回溯法的搜索效率是用约束函数在扩展结点剪去不满足约束的子树是用限界函数剪去得不到最优解的子树，这两类函数称之为剪枝函数3. 回溯法的基本算法框架递归回溯迭代回溯子集树算法框架排列树算法框架5. 采用回溯法解决的经典问题转载问题批处理作业二调度问题符号三角形问题n后问题0-1背包问题最大团问题图的m着色问题旅行售货员问题圆排列问题电路板排列问题连续邮资问题
￥
5.9
百度文库VIP限时优惠现在开通,立享6亿+VIP内容
立即获取
五个回路溯源分析
智阳文库
五个回路溯源分析
1. 回溯法的基本概念
用回溯法求解问题时，应明确问题的解空间，问题的解空间至少应包含问题的一个最优解，确定了解空间的组织结构后，回溯法从开始结点（根结点）出发，以深度优先方式搜索整个解空间，这个开始结点成为活结点，同时成为当前的扩展结点，在当前扩展结点处，如果在当前扩展结点处不能在向纵深方向移动，则当前扩展结点就成为死结点，此时应往回移动（回溯）至最近的一个活结点处，并让这个活结点成为当前的扩展结点，回溯法以这种工作方式递归的在解空间中搜索，直至找到所要求的的解或解空间中已无活结点时为止
第 1 页
2. 回溯法搜索空间树时，通常采用两种策略来避免无效的搜索，提高回溯法的搜索效率
是用约束函数在扩展结点剪去不满足约束的子树
是用限界函数剪去得不到最优解的子树，这两类函数称之为剪枝函数
3. 回溯法的基本算法框架
递归回溯
迭代回溯
子集树算法框架

两道作业的批处理系统怎么算

两道作业的批处理系统采用短作业优先调度算法。在一个有两道作业的批处理系统中，作业调度采用短作业优先调度算法，进程调度采用抢占式优先级调度算法。其中给出的作业优先数即为相应进程的优先数。其数值越小，优先级越高。

实时操作系统常用任务调度算法有哪些

实时操作系统常用任务调度算法有哪些
操作系统常用的批处理作业调度算法
1．先来先服务调度算法
先来先服务(FCFS)调度算法是一种最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。
2．短作业(进程)优先调度算法

一个批处理型作业，从进入系统并驻留在外存的后备队列上开始，直至运行完毕，可能经历的3种调度是哪3种

一个批处理型作业可能经历的三种调度是：
1.入内存调度（进入系统调度）：当一个作业进入系统时，它通常位于外存的后备队列上等待分配内存。入内存调度的任务是从后备队列中选择一个作业，并将其调度到内存中开始执行。
2.进程调度（就绪队列调度）：一旦作业被调度到内存并准备好执行，它将进入就绪队列等待进一步的调度。进程调度的任务是从就绪队列中选择一个作业，分配处理器资源，使其进入运行状态开始执行。
3.出内存调度（完成调度）：当一个作业完成执行后，它将进入完成状态，并需要被移出内存以腾出空间给其他作业。出内存调度的任务是选择一个已经完成的作业，将其从内存中移出，并释放相关资源，使其离开系统。
这三种调度在批处理系统中起着不同的作用，确保作业能够被有效地调度和执行，从而实现系统资源的最大化利用和作业完成的顺利进行。