A*算法详解
今天刚开通了百度博客，这也是我在这里的第一篇文章,以后会在此写下我学习AS3的一些心得和技巧,方便自己日后的复习也让一些新手门能快速的入门,那么，开门见山,第一篇就写AS3版的A*算法吧。
那么，我个人习惯不喜欢把简单的东西往复杂了搞，虽然复杂代表着规范，和严谨，但是处于学习的目的，我给出的A*算法，相当的简单和实用,当然重点是算法思想，下面就跟随我的指示太了解A*算法吧。
那么什么是A*，其实就是在很多障碍物的地图上，物体从A点移动到B点的路径,当然，光要路径也不对，我们要找的就是其中最短的一条，这样问题就来了，如何才能找到最短的一条呢？首先，我们得有一个标准来验证。我们需要一个探路器和节点,比如我们每走一步都会用探路器在我们周围的8个点上放上节点,然后每个节点会返回出他们的代价,我们根据探路器的指示，找到代价最少的节点，然后下一步就走到了那里，然后继续上面的操作,那么，原理是很简单的，我们先需要一个节点类(node),节点类要做的事情就是返回出代价，至于怎么返回请看下面:
假设我们在地图上每走一步都需要消耗代价,比如直线走一格是10代价,斜线走是14代价,那么我们可以根据以下的公式计算代价:
F=H+G
总代价=目标到当前的直线代价+从开始节点到当前节点的移动代价
那么，其实看到这里我们就只要，需要3个函数,F函数和H函数还有G函数，那么可以写成:
function F():int{
H()+G();
}
好了，到了这里，A*算法我们已经完成一半了,现在只要去实现H和G了，那么继续看:
public function getH():int {
return Math.abs(h - Goal_node.h) * 10 + Math.abs(l - Goal_node.l) * 10;
//返回目标到当前的直线代价
}
哇，好少了啊，对，就一行,H计算的是目标节点到当前节点所消耗的代价,注意了：只需要计算行和列，斜线的不算，当然不能少了取绝对值,我们不需要负数,之前我们说了直线的代价是10，所以我们把他们的代价都*上10，当然你可以根据自己需求来*上不同的代价,OK,H
搞定了,下面来看看G：
public function getG():int {
if (Math.abs(h - Start_node.h) == 1&& Math.abs(l - Start_node.l) == 1) {
return 14+Father_int;
//返回父节点的带价值和当前节点到开始节点值等于一路走过来的带价值
} else {
return Math.abs(h - Start_node.h) * 10 + Math.abs(l - Start_node.l) * 10 + Father_int;
//同上
}
}
//返回从开始节点到当前节点的移动代价
//G函数比H函数多了一点，就是计算斜角的代价，但是，记住，这个斜角只是当前节点的左上，左下，右上，右下的那一格，那么如何来计算是否是斜角呢？其实只要计算当前行减去父节点和列减去父节点的列是否都等于1，这里也一样需要取绝对值，如果都为1则说明不在同一行也不在同一列,Father_int是什么呢？是父节点的代价,G函数计算的是当前的代价还要加上父节点的代价，才能算出开始节点到当前节点的总代价,到了这里A*逻辑部分已经完成一大半了，最后我们还需要将找到的路径保存进一个数组里,看下面代码:
public function getPath():Array {
if (Father_node== this) {
var ccc:Array=new Array();
ccc=[[h, l]];
return ccc;
} else {
var aa:Array = Father_node.getPath();
var answer:Array=aa.slice(0,aa.length);
answer[aa.length] =[h, l];
return answer;
}
}
太少了,对，就是这么简单啦,首先我们检测目标节点的父节点是否等于自己,等于自己说明达到了起点,因为起点是没有父节点的，所以我们就设为是自己,好,先就此打住，看看下面的else,这里我们用了递归来寻找节点,首先我们新建立一个数组等于父节点返回的节点,然后在把它拷贝一份进新的输入,因为FLASH的数组是动态的，所以我们直接在尾部answer[aa.length] 添加进当前节点的行和列,最后返回,直到返回到父节点也把自己的坐标返回了，整个递归调用结束,最后我们需要知道我们是否已经找到目标了,其实我们就可以直接判断当前的节点是否是目标节点:
public function equals(me:Object):Boolean {
if (me is node) {
if (me.h == h && me.l == l) {
return true;
} else {
return false;
}
} else {
return false;
}
}
对啊，就是判断行和列就OK啦，这个方法如果返回真了就是找到了，如果返回假就说明没找到,
自此整个节点核心算法完毕,
下面是整个节点类:
package {
public class node {
public var h:int;
public var l:int;
public var Father_node:node;
public var Goal_node:node;
public var Start_node:node;
public var Father_int:int;
public function node(h:int,l:int,Father_node:node,Goal_node:node,Start_node:node) {
this.h=h;
//接受行
this.l=l;
//接受列
this.Father_node=Father_node;
//接受父类节点
this.Goal_node=Goal_node;
//接受目标节点
this.Start_node=this.Father_node;
//接受开启节点
if (Father_node==null) {
this.Father_node=this;
}
if (Goal_node==null) {
this.Goal_node=this;
}
if (Start_node==null) {
this.Start_node=this;
}
//如果没有，则等于自己(用于起点和重点)
if (Start_node!=null) {
Father_int=Start_node.getG();
}
//获得父类节点的代价
}
public function getH():int {
return Math.abs(h - Goal_node.h) * 10 + Math.abs(l - Goal_node.l) * 10;
//返回目标到当前的直线代价
}
public function getG():int {
if (Math.abs(h - Start_node.h) == 1&& Math.abs(l - Start_node.l) == 1) {
return 14+Father_int;
//返回父节点的带价值和当前节点到开始节点值等于一路走过来的带价值
} else {
return Math.abs(h - Start_node.h) * 10 + Math.abs(l - Start_node.l) * 10 + Father_int; //同上
}
}
//返回从开始节点到当前节点的移动代价
public function getF():int {
return getH() + getG();
}
public function equals(me:Object):Boolean {
if (me is node) {
if (me.h == h && me.l == l) {
return true;
} else {
return false;
}
} else {
return false;
}
}
public function getPath():Array {
if (Father_node== this) {
var ccc:Array=new Array();
ccc=[[h, l]];
return ccc;
} else {
var aa:Array = Father_node.getPath();
var answer:Array=aa.slice(0,aa.length);
answer[aa.length] =[h, l];
return answer;
}
}
}
}
好了，节点我们搞定了，剩下的就是探路器的问题了(Find),那么我们的探路器的工作主要是负责，摆放节点到各个节点,那么这里我们需要知道什么位置需要放什么位置不需要，比如放过节点的位置当然就不需要了,呵呵,然后探路器会分析哪个节点返回的代价最少,最后当探路器找到目标之后会把整个路径返回出去,那么说到这里了，我们不得不说下列表问题,探路器是通过列表来选择是否放置节点,一共有2个,开启列表和关闭列表,首先,我们得知道，被放置的节点是否在某个列表里,如下函数:
public function detection_listing(h:int,l:int,vec:Array):node {
for (var i:int=0; i < vec.length; i++) {
var mc:node=vec[i];
if (h == mc.h && l == mc.l) {
return mc;
}
}
return null;
}
//检测是否在列表里(检测当前行当前列是否与开启列表里的元素一样)
现在我们只要把列表(数组)丢进去再丢行和列就好了,再下来，我们需要知道斜角的地方是否有障碍物,如下函数:
public function bianyuan(h:int,l:int,hh:int,ll:int,map:Array):Boolean {
if (hh-1==h&&ll-1==l) {
if (map[h][l+1]==1||map[h+1][l]==1) {
//trace("左上")
return false;
}
} else if (hh-1==h&&ll+1==l) {
if (map[h][l-1]==1||map[h+1][l]==1) {
//trace("右上")
return false;
}
} else if (hh+1==h&&ll-1==l) {
if (map[h-1][l]==1||map[h][l+1]==1) {
//trace("左下")
return false;
}
} else if (hh+1==h&&ll+1==l) {
if (map[h][l-1]==1||map[h-1][l]==1) {
//trace("右下")
return false;
}
}
return true
//判断当前节点的斜角上周围是否有障碍物
}
我们需要丢一个行和列进去,然后再丢另一组行和列进去,然后是地图,判断第一组的行和列在第二组的行和列的什么位置,最后再判断是否有障碍物. if (map[h][l-1]==1||map[h-1][l]==1) ,这里我设置障碍物是1,再后来，我们需要知道是否找不到路:
if(Start_listing.length==0&&Current_node.equals(Goal_node)==false){
trace("没有路了")
kaishi=false
}
嗯，开启列表已经没有东西了，但是路径返回返回假，就说明寻路失败,我这里设置了一个布尔值为假:好了，辅助函数都写好了,关键时刻到了,现在我们需要使用探路，探测身边周围的8个点,方法如下:
for (var j:int=-1; j<2; j++) {
for (var k:int=-1; k<2; k++) {
}
}
对，2个for循环,看看，当前节点的行加上J，和当前节点的列加上K，是否就是当前节点周围的8个点,好了，下面是上面的函数的完整应用:
public function aido(map:Array) {
if (shanchu.length!=0) {
for (var t:int=0; t shanchu[t]=null; trace("删除了") } } //如果删除列表不为空,则删除里面所有元素,等待系统回收 shanchu=new Array(); //初始化删除列表 Start_listing=new Array; //开启列表 Stop_listing=new Array; //关闭列表 Start_listing.push(Start_node); //把当前节点放入开启列表 shanchu.push(Start_node); //把当前节点放入删除列表 do { Current_node=Start_listing[0]; //获取开启列表的第一个元素 for (var i:int=1; i if (Start_listing[i].getF() Current_node=Start_listing[i]; } } //比较数组里的元素，如果数组里的元素的F值比当前的小，则把当前的替换成数组里的 if (Current_node.equals(Goal_node)) { //trace("找到路了"); fruit=Current_node.getPath(); kaishi=true break } //是否找到路径 Stop_listing.push(Current_node); //添加当前节点到关闭列表 Start_listing.splice(Start_listing.indexOf(Current_node),1); //删除开始列表把当前节点从 for (var j:int=-1; j<2; j++) { for (var k:int=-1; k<2; k++) { //遍历当前节点周围的位置 if (Current_node.h+j==0&&Current_node.l+k==0) { continue; } if (Current_node.h+j>=map.length||Current_node.h-j<0) { continue; } if (Current_node.l+k>=map[0].length||Current_node.l-k<0) { continue; } //判断是否遍历到了自己，是否超出了边界,如果是，则返回出去，重新遍历 if (bianyuan(Current_node.h+j,Current_node.l+k,Current_node.h,Current_node.l,map)&&detection _fraise(Current_node.h+j,Current_node.l+k,map)&&detection_border(Current_node.h+j,Current _node.l+k,map)&&detection_listing(Current_node.h+j,Current_node.l+k,Stop_listing)==null) { //如果周边的节点不在关闭列表里,是不是障碍物，斜角的周边是否有障碍物 About_node=detection_listing(Current_node.h+j,Current_node.l+k,Start_listing); //判断周边的节点,传递行，列，开启列表 //如果当前对象在开启列表里，则函数会返回空，如果不在，则会创建新的节点 if (About_node==null) { //如果为空则不用多说了，像病毒一样扩散开来 About_node=new node(Current_node.h+j,Current_node.l+k,Current_node,Goal_node,Current_node); //初始化节点,传递行，列，父节点(当前的节点),目标节点(上面当鼠标点击时6了一个),开始节点(游戏运行时6了一个) Start_listing.push(About_node); shanchu.push(About_node); //如果周边的节点为空,则在周边扩散节点,将扩散的节点放入开启列表，以备下次检测需要,也放入删除列表，待找到路径后删除删除列表里所有的节点,等待系统回收} else { var oldG:int=About_node.getG(); //保存零时变量为开启列表里的G值 var Father:node=About_node.Father_node; //保存开启列表里的父节点 About_node.Father_node=Current_node; //替换开启列表里的父节点为当前节点 if (About_node.getG() >= oldG) { //trace("被替换了") //比较被替换父节点的开启列表里的节点的值是否大于最开始的G值 About_node.Father_node=Father; //如果大于则,被替换的开启列表里的节点的父节点又被送了回来给与了开启列表里的节点 } //如果周边节点移动的代价比当前节点移动的代价要少的话,就替换当前节点的父节点,递归路径时遍会递归到最短路径的父类 } } } } } while (Start_listing.length!=0); //如果开启列表为空，停止寻路 if(Start_listing.length==0&&Current_node.equals(Goal_node)==false){ trace("没有路了") kaishi=false } } 首先，我们定义了一个寻路函数,只接收地图,然后我们初始化了开启列表和关闭列表,最后将当前节点放入开启列表和关闭列表,其实我们就是把起点放进去,仔细看，这个动作是在for 循环外面，既然是寻路，所以我们要有个开头，对吧,最后我们用do...while() 循环来执行核心部分,在开始部分，我们先来了一次冒泡排序,就是找出开启列表里代价最小的节点,然后让零时节点等于这个节点,然后再比较，这个节点是否是目标节点，如果是，则找到路径,返回路径,如果不是，继续，只要是检测过的节点，都不需要再检测，所以我们把当前节点放入关闭列表,同时也在开启列表里删除当前节点,最后,我们通过for循环，检测当前节点周围的8个点,判断如果超出了边界则放弃掉，进行下一次循环,然后再判断当前节点是否不在关闭列表里,旁边是否有障碍物,自己本上是否是障碍物,如果都没有，则检测是否在开启列表里,如果也不在开启列表里，则放置节点到当前的点上,把当前的点放入开启列表，等待下一次的循环检测,如果在开启列表里，则检测开启列表里的G指是否小于当前的G值，如果小于，则替换父节点,因为递归寻路是通过父节点的坐标,我们需要保证我们找到的路径是最短的,如果开启列表不为空，则继续循环,好，至此整个探路器核心介绍完毕，下面是完整代码: package { public class Find { private var h:int; private var l:int; private var fruit:Array; //路径数组 private var Start_listing:Array; //开启列表 private var Stop_listing:Array; //关闭列表 public var Goal_node:node; //目标节点 public var Start_node:node; //开始节点 public var Current_node:node; //当前节点 public var Fairly_node:node; //比较节点 public var About_node:node; //零时节点 private var shanchu:Array; static public var kaishi:Boolean public function AIdo(h:int,l:int,hh:int,ll:int,map:Array):Array { shanchu=new Array(); //初始化删除列表 Start_listing=new Array; //开启列表 Stop_listing=new Array; //关闭列表 Goal_node=new node(hh,ll,null,null,null); //目标节点 Start_node=new node(h,l,null,Goal_node,null); //开始节点 aido(map); //开始寻路 return fruit; //返回寻路后的结果数组 } public function aido(map:Array) { if (shanchu.length!=0) { for (var t:int=0; t shanchu[t]=null; trace("删除了") } } //如果删除列表不为空,则删除里面所有元素,等待系统回收 shanchu=new Array(); //初始化删除列表 Start_listing=new Array; //开启列表 Stop_listing=new Array; //关闭列表 Start_listing.push(Start_node); //把当前节点放入开启列表 shanchu.push(Start_node); //把当前节点放入删除列表 do { Current_node=Start_listing[0]; //获取开启列表的第一个元素 for (var i:int=1; i if (Start_listing[i].getF() Current_node=Start_listing[i]; } } //比较数组里的元素，如果数组里的元素的F值比当前的小，则把当前的替换成数组里的 if (Current_node.equals(Goal_node)) { //trace("找到路了"); fruit=Current_node.getPath(); kaishi=true break } //是否找到路径 Stop_listing.push(Current_node); //添加当前节点到关闭列表 Start_listing.splice(Start_listing.indexOf(Current_node),1); //删除开始列表把当前节点从 for (var j:int=-1; j<2; j++) { for (var k:int=-1; k<2; k++) { //遍历当前节点周围的位置 if (Current_node.h+j==0&&Current_node.l+k==0) { continue; } if (Current_node.h+j>=map.length||Current_node.h-j<0) { continue; } if (Current_node.l+k>=map[0].length||Current_node.l-k<0) { continue; } //判断是否遍历到了自己，是否超出了边界,如果是，则返回出去，重新遍历 if (bianyuan(Current_node.h+j,Current_node.l+k,Current_node.h,Current_node.l,map)&&detection _fraise(Current_node.h+j,Current_node.l+k,map)&&detection_border(Current_node.h+j,Current _node.l+k,map)&&detection_listing(Current_node.h+j,Current_node.l+k,Stop_listing)==null) { //如果周边的节点不在关闭列表里,是不是障碍物，斜角的周边是否有障碍物 About_node=detection_listing(Current_node.h+j,Current_node.l+k,Start_listing); //判断周边的节点,传递行，列，开启列表 //如果当前对象在开启列表里，则函数会返回空，如果不在，则会创建新的节点 if (About_node==null) { //如果为空则不用多说了，像病毒一样扩散开来 About_node=new node(Current_node.h+j,Current_node.l+k,Current_node,Goal_node,Current_node); //初始化节点,传递行，列，父节点(当前的节点),目标节点(上面当鼠标点击时6了一个),开始节点(游戏运行时6了一个) Start_listing.push(About_node); shanchu.push(About_node); //如果周边的节点为空,则在周边扩散节点,将扩散的节点放入开启列表，以备下次检测需要,也放入删除列表，待找到路径后删除删除列表里所有的节点,等待系统回收} else { var oldG:int=About_node.getG(); //保存零时变量为开启列表里的G值 var Father:node=About_node.Father_node; //保存开启列表里的父节点 About_node.Father_node=Current_node; //替换开启列表里的父节点为当前节点 if (About_node.getG() >= oldG) { //trace("被替换了") //比较被替换父节点的开启列表里的节点的值是否大于最开始的G值 About_node.Father_node=Father; //如果大于则,被替换的开启列表里的节点的父节点又被送了回来给与了开启列表里的节点 } //如果周边节点移动的代价比当前节点移动的代价要少的话,就替换当前节点的父节点,递归路径时遍会递归到最短路径的父类 } } } } } while (Start_listing.length!=0); //如果开启列表为空，停止寻路 if(Start_listing.length==0&&Current_node.equals(Goal_node)==false){ trace("没有路了") kaishi=false } } public function bianyuan(h:int,l:int,hh:int,ll:int,map:Array):Boolean { if (hh-1==h&&ll-1==l) { if (map[h][l+1]==1||map[h+1][l]==1) { //trace("左上") return false; } } else if (hh-1==h&&ll+1==l) { if (map[h][l-1]==1||map[h+1][l]==1) { //trace("右上") return false; } } else if (hh+1==h&&ll-1==l) { if (map[h-1][l]==1||map[h][l+1]==1) { //trace("左下") return false; } } else if (hh+1==h&&ll+1==l) { if (map[h][l-1]==1||map[h-1][l]==1) { //trace("右下") return false; } } return true //判断当前节点的斜角上周围是否有障碍物 } public function detection_fraise(h:int,l:int,map:Array):Boolean { if (map[h][l]==1) { return false; } else { return true; } } //检测是否有障碍物 public function detection_border(h:int,l:int,map:Array):Boolean { return h < map.length && l < map[0].length && h >= 0 && l >= 0; } //检测是否超出边界 public function detection_listing(h:int,l:int,vec:Array):node { for (var i:int=0; i < vec.length; i++) { var mc:node=vec[i]; if (h == mc.h && l == mc.l) { return mc; } } return null; } //检测是否在列表里(检测当前行当前列是否与开启列表里的元素一样) } } 用法很简单,这是一个静态的方法,Find.AIdo(起点行,起点列,终点行,终点列,地图)以后只要用A*，找到这个2个类文件，调用这个方法就会返回一个2维数组，其中第2维的0代表行，1代表列。 学号： 姓名： 班级： 实验时间： 2011-10-10 实验编号 002 实验名称 作业调度算法 实验目的和 要求 通过对作业调度算法的模拟加深对作业概念和作业调度算法的理解 实验内容 （1） 模拟FCFS 算法实现作业调度 （2） 模拟短作业优先算法实现作业调度 模拟最高相应比优先算法实现作业调度 一、 实验题目 输入：作业流文件，其中存储的是一系列要执行的作业， 每个作业包括三个数据项： 作业号、作业进入系统的时间（用一小数表示，如10：10，表示成10.10）、估计执行时间（单位小时，以十进制表示） 参数用空格隔开，下面是示例： 1 8.00 0.5 2 8.15 0.3 3 8.30 0.25 4 8.35 0.20 5 8.45 0.15 6 9.00 0.10 7 9.20 0.05 其中调度时刻为最后一个作业到达系统的时间！ 输出：作业号 进入内存的时间，每行输出一个作业信息。 并输出每一种调度算法的平均周转时间和平均带权周转时间。 二、 算法设计思路 首先用一个switch 函数做界面选择进入哪一种算法。用一个内来定义作业 float s;//提交时间 float j;//执行时间 float k;//开始时间 float w;//完成时间 float z;//周转时间 float d;//带权周转时间 1， 先来先服务，首先计算第一个作业的完成时间，周转时间，带权周转时间。再用for 循 环来计算剩下每一个作业的完成时间，周转时间，带权周转时间。然后再算出平均周转时间和平均带权周转时间。 2， 短作业有优先，首先计算第一个作业的完成时间，周转时间，带权周转时间。再用来计 算其他作业的。其中在for 循环中嵌套while 函数，在每一次计算前判断处于等待状态 计算机操作系统 实验报告 处理器调度 选择题 当CPU执行操作系统代码时，则处理机处于( )。 A．执行态 B．目态 C．管态 D．就绪态 ( )是机器指令的扩充，是硬件的首次延伸，是加在硬件上的第一层软件。 A．系统调用 B．操作系统 C．内核 D．特权指令 操作系统提供给程序员的接口是( )。 A．进程 B．系统调用 C．库函数 D．B和C 用户程序向系统提出使用外设的请求方式是( )。 A．作业申请 B．原语 C．系统调用 D．I／O指令 当作业正常完成进入完成状态时，操作系统( )。 A．将输出该作业的结果并删除内存中的作业 B．将收回该作业的所占资源并输出结果 C．将收回该作业的所占资源及输出结果，并删除该作业 D．将收回该作业的所占资源及输出结果，并将它的控制块从当前的队列中删除 下列选项是关于作业和进程关系的描述，其中哪一个是不正确的( )。 A．作业的概念主要用在批处理系统中，而进程的概念则用在几乎所有的OS中。 B．作业是比进程低一级的概念。 C．一个作业至少由一个进程组成。 D．作业是用户向计算机提交任务的实体，而进程是完成用户任务的执行实体以及向系统申请分配资源的基本单位。 作业从后备作业到被调度程序选中的时间称为( )。 周转时间B．响应时间C．等待调度时间D．运行时间 设有三个作业J1，J2，J3，它们同时到达，运行时间分别为T1，T2，T3，且T1≤T2≤T3，若它们在一台处理机上按单道运行，采用短作业优先算法，则平均周转时间为( )。 A．T1+T2+T3 B．1／3(T1+T2+T3) C．T1+2／3T2+1／3T3 D．T1+1／3T2+2／3T3 从作业提交给系统到作业完成的时间间隔称为作业的( )。 A．中断时间 B．等待时间 C．周转时间 D．响应时间 设有四个作业同时到达，每个作业执行时间均为2 h，它们在一台处理机上按单道方式运行，则平均周转时间为( )。 A．1 h B．5 h C．2．5 h D．8 h FCFS调度算法有利于( )。 A．长作业和CPU繁忙型作业 B．长作业和I／O繁忙型作业 C．短作业和CPU繁忙型作业 D．短作业和I／O繁忙型作业 下列哪种说法不是SJ(P)F调度算法的缺点( )。 A．对于长作业(进程)不利 B．未考虑作业(进程)的紧迫程度 C．不能有效降低作业(进程)的平均等待时间 D．由于根据的是用户提供的估计执行时间，因此不一定真正做到短而优先。 选择排队进程中等待时间最长的进程被优先调度，该调度算法是( )。 A．先来先服务调度算法B．短进程优先调度算法 C．优先权调度算法D．高响应比优先调度算法 在采用动态优先权的优先权调度算法中，如果所有进程都具有相同优先权初值，则此时的优先权调度算法实际上和( )相同。 操作系统之调度算法和死锁中的银行家算法习 题答案 集团文件发布号：（9816-UATWW-MWUB-WUNN-INNUL-DQQTY- 1. 有三个批处理作业，第一个作业 10:00 到达，需要执行 2 小时；第二个作业在10:10到达，需要执行 1 小时；第三个作业在 10:25 到达，需要执行 25 分钟。分别采用先来先服 务，短作业优先和最高响应比优先三种调度算法，各自的平均周转时间是多少？解： 先来先服务： （结束时间=上一个作业的结束时间+执行时间 周转时间=结束时间-到达时间=等待时间+执行时间） 按到达先后，执行顺序：1->2->3 短作业优先： 1)初始只有作业1，所以先执行作业1，结束时间是12:00，此时有作业2和3； 2)作业3需要时间短，所以先执行； 3)最后执行作业2 最高响应比优先： 高响应比优先调度算法既考虑作业的执行时间也考虑作业的等待时间，综合了先来先服务和最短作业优先两种算法的特点。 1)10:00只有作业1到达，所以先执行作业1； 2)12:00时有作业2和3， 作业2：等待时间=12:00-10:10=110m;响应比=1+110/60=2.8； 作业3：等待时间=12:00-10:25=95m，响应比=1+95/25=4.8； 所以先执行作业3 3)执行作业2 2. 在一单道批处理系统中，一组作业的提交时刻和运行时间如下表所示。试计算一下三种 作业调度算法的平均周转时间 T 和平均带权周转时间 W。 （ 1）先来先服务；（ 2）短作业优先（ 3）高响应比优先 解： 先来先服务： 作业顺序：1,2,3,4 短作业优先： 作业顺序： 《操作系统》实验报告 题目：作业调度算法 班级：网络工程 姓名：朱锦涛 学号：E31314037 一、实验目的 用代码实现页面调度算法，即先来先服务（FCFS）调度算法、短作业优先算法、高响应比优先调度算法。通过代码的具体实现，加深对算法的核心的理解。 二、实验原理 1.先来先服务（FCFS）调度算法 FCFS是最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，系统将按照作业到达的先后次序来进行调度，或者说它是优先考虑在系统中等待时间最长的作业，而不管该作业所需执行的时间的长短，从后备作业队列中选择几个最先进入该队列的作业，将它们调入内存，为它们分配资源和创建进程。然后把它放入就绪队列。 2.短作业优先算法 SJF算法是以作业的长短来计算优先级，作业越短，其优先级越高。作业的长短是以作业所要求的运行时间来衡量的。SJF算法可以分别用于作业和进程调度。在把短作业优先调度算法用于作业调度时，它将从外存的作业后备队列中选择若干个估计运行时间最短的作业，优先将它们调入内存。 3、高响应比优先调度算法 高响应比优先调度算法则是既考虑了作业的等待时间，又考虑了作业的运行时间的算法，因此既照顾了短作业，又不致使长作业等待的时间过长，从而改善了处理机调度的性能。 如果我们引入一个动态优先级，即优先级是可以改变的令它随等待的时间的延长而增加，这将使长作业的优先级在等待期间不断地增加，等到足够的时间后，必然有机会获得处理机。该优先级的变化规律可以描述为： 优先权 = （等待时间 + 要求服务时间）/要求服务时间 三、实验内容 源程序： #include 第二讲作业调度算法主讲教师：张新彩 3.2 作业调度算法 3.2.1 先来先服务算法 3.2.2 短作业 / 进程优先算法 3.2.3 优先级调度算法 3.2.4 高响应比优先调度算法 3.2.1 先来先服务算法 ?适用于作业调度 ?从后备作业队列中选择一个或多个最先进入的作业，将 它们调入内存，为它们分配资源、创建进程，然后放入 就绪队列。 ?适用于进程调度 ?从就绪进程队列中选择一个最先进入的进程，为之分配 处理机，使之投入运行；直到运行完成或阻塞，才会让 出处理机。 3.2.1 先来先服务算法 4 平均周转时间为（4+6+10+11+14）/5=9 作业A 、B 、C 、D 、E 分别在0、1、2、3、4时刻到达，需要的服务时间分别为4、3、5、2、4。请用先来先服务算法计算它们的完成时间、周转时间、带权周转时间和平均周转时间。 作业 名 到达 时间 服务 时间 开始执 行时间 完成 时间 周转 时间 带权周 转时间 A 4 B 1 3 C 2 5 D 3 2 E 4 4 4 7 12 14 1 2 2 5.5 0 4 7 12 4 6 10 11 18 3.5 14 14 简单易实现，有利于长作业，不利于短作业 3.2.2 短作业 / 进程优先算法 ?短作业优先（SJF） ?从后备队列中选择一个或多个估计运行时间最短的作业 调入内存。 ?短进程优先（SPF） ?从就绪队列中选出一个估计运行时间最短的进程，将处 理机分配给它，使它立即执行。 3.2.2 短作业 / 进程优先算法 6 平均周转时间为（4+3+8+9+16）/5=8 作业 名 到达 时间 服务 时间 开始执 行时间 完成 时间 周转 时间 带权周 转时间 作业A 、B 、C 、D 、E 分别在0、1、2、3、4时刻到达，需要的服务时间分别为4、3、5、2、4。请用短作业优先算法计算它们的完成时间、周转时间、带权周转时间和平均周转时间。 4 1 0 4 6 1. 5 4 3 9 8/3 6 8 13 9/4 9 9 18 16/5 13 16 D 3 2 B 1 3 E 4 4 C 2 5 A 0 4 1 填空题 1 若采用短作业优先调度策略，作业单道串行运行时的调度次序为J1,J3,J2 ，平均周转时间= 8 。 2．进程间通信的类型有：基于内存通信、基于文件通信、基于网络通信和基于报文传递通信。 3．在响应比最高者优先的作业调度算法中，当各个作业等待时间相同时，运行时间短作业将得到优先调度；当各个作业要求运行的时间相同时，等待时间长得到优先调度。 4.有三个同时到达的作业J1，J2和J3，它们的执行时间分别是T1，T2和T3，且T1 课程设计 采用短作业优先调度算法调度程序 学号： 姓名： 专业： 指导老师： 日期： 目录 一、实验题目 (3) 二、课程设计的目的 (3) 三、设计内容 (3) 四、设计要求 (3) 五、主要数据结构及其说明 (4) 六、程序运行结果 (5) 七、流程图 (7) 八、源程序文件 (9) 九、实验体会 (13) 十、参考文献 (13) 摘要 在多道程序环境下，主存中有着多个进程，其数目往往多于处理机数目。这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。分配处理机的任务是由处理机调度程序完成的。由于处理机是最重要的计算机资源，提高处理机的利用率及改善系统性能（吞吐量、响应时间），在很大程度上取决于处理机调度性能的好坏，因而，处理机调度便成为操作系统设计的中心问题之一。 在多道程序系统中，一个作业被提交后必须经过处理机调度后，方能获得处理机执行。对于批量型作业而言，通常需要经历作业调度和进程调度两个过程后方能获得处理机。作业调度是对成批进入系统的用户作业，根据作业控制块的信息，按一定的策略选取若干个作业使它们可以去获得处理器运行的一项工作。而对每个用户来说总希望自己的作业的周转时间是最小的，短作业优先（SJF）便是其中一种调度方法。本次课程设计主要是模拟短作业优先(SJF)调度算法。 一、实验题目 采用短作业优先算法的的进程调度程序 二、课程设计的目的 操作系统课程设计是计算机专业重要的教学环节，它为学生提供了一个既动手又动脑，将课本上的理论知识和实际有机的结合一起，独立分析和解决实际问题的机会。 进一步巩固和复习操作系统的基础知识。 培养学生结构化程序、模块化程序设计的方法和能力。 提高学生调试程序的技巧和软件设计的能力。 提高学生分析问题、解决问题以及综合利用C语言进行程序设计的能力。 三、设计内容 设计并实现一个采用短作业优先算的进程调度算法演示程序 四、设计要求 1. 每一个进程有一个PCB，其内容可以根据具体情况设定。 2. 进程数、进入内存时间、要求服务时间、优先级等均可以在界面上设定 3. 可读取样例数据（要求存放在外部文件中）进行进程数、进入内存时间、时间片长度、进程优先级的初始化 4. 可以在运行中显示各进程的状态：就绪、执行（由于不要求设置互斥资源与进程间同步关系，故只有两种状态） 5. 采用可视化界面，可在进程调度过程中随时暂停调度，查看当前进程的状态以及相应的阻塞队列 处理器调度习题 处理器调度 选择题 ?当CPU执行操作系统代码时，则处理机处于( )。 ?A．执行态 B．目态 C．管态 D．就绪态 ?( )是机器指令的扩充，是硬件的首次延伸，是加在硬件上的第一层软件。 ?A．系统调用 B．操作系统 C．内核 D．特权指令 ?操作系统提供给程序员的接口是( )。 ?A．进程 B．系统调用 C．库函数 D．B和C ?用户程序向系统提出使用外设的请求方式是( )。 ?A．作业申请 B．原语 C．系统调用 D．I／O指令 ?当作业正常完成进入完成状态时，操作系统( )。 ?A．将输出该作业的结果并删除内存中的作业 ?B．将收回该作业的所占资源并输出结果 ?C．将收回该作业的所占资源及输出结果，并删除该作业 ?D．将收回该作业的所占资源及输出结果，并将它的控制块从当前的队列中删除 ?下列选项是关于作业和进程关系的描述，其中哪一个是不正确的( )。 ?A．作业的概念主要用在批处理系统中，而进程的概念则用在几乎所有的OS中。 ?B．作业是比进程低一级的概念。 ?C．一个作业至少由一个进程组成。 ?D．作业是用户向计算机提交任务的实体，而进程是完成用户任务的执行实体以及向系统申请分配资源的基本单位。 ?作业从后备作业到被调度程序选中的时间称为( )。 ?周转时间B．响应时间C．等待调度时间D．运行时间 ?设有三个作业J1，J2，J3，它们同时到达，运行时间分别为T1，T2，T3，且T1≤T2≤T3，若它们在一台处理机上按单道运行，采用短作业优先算法，则平均周转时间为( )。 ?A．T1+T2+T3 B．1／3(T1+T2+T3) ?C．T1+2／3T2+1／3T3 D．T1+1／3T2+2／3T3 ?从作业提交给系统到作业完成的时间间隔称为作业的( )。 ?A．中断时间 B．等待时间 C．周转时间 D．响应时间 ?设有四个作业同时到达，每个作业执行时间均为2 h，它们在一台处理机上按单道方式运行，则平均周转时间为( )。 ?A．1 h B．5 h C．2．5 h D．8 h ?FCFS调度算法有利于( )。 ?A．长作业和CPU繁忙型作业 B．长作业和I／O繁忙型作业 ?C．短作业和CPU繁忙型作业 D．短作业和I／O繁忙型作业 ?下列哪种说法不是SJ(P)F调度算法的缺点( )。 ?A．对于长作业(进程)不利 ?B．未考虑作业(进程)的紧迫程度 ?C．不能有效降低作业(进程)的平均等待时间 ?D．由于根据的是用户提供的估计执行时间，因此不一定真正做到短而优先。 ?选择排队进程中等待时间最长的进程被优先调度，该调度算法是( )。 ?A．先来先服务调度算法B．短进程优先调度算法 ?C．优先权调度算法D．高响应比优先调度算法 ?在采用动态优先权的优先权调度算法中，如果所有进程都具有相同优先权初值，则此时的优先权调度算法实际上和( )相同。 ?A．先来先服务调度算法B．短进程优先调度算法 操作系统》实验一实验报告 【实验题目】：先来先服务FCFS 和短作业优先SJF进程调度算法【实验目的】 通过这次实验，加深对进程概念的理解，进一步掌握进程状态的转变、进程调度的策略及对系统性能的评价方法。 【实验内容】 问题描述： 设计程序模拟进程的先来先服务FCFS 和短作业优先SJF 调度过程。假设有n个进程分别在T1, ?,T n时刻到达系统，它们需要的服务时间分别为S1, ?,S n。分别采用先来先服务FCFS和短作业优先SJF 进程调度算法进行调度，计算每个进程的完成时间，周转时间和带权周转时间，并且统计n 个进程的平均周转时间和平均带权周转时间。 程序要求如下： 1）进程个数n；每个进程的到达时间T1, ?,T n 和服务时间S1, ?,S n；选择算法1-FCFS，2-SJF。 2）要求采用先来先服务FCFS 和短作业优先SJF分别调度进程运行，计算每个进程的周转时间，带权周转时间，并且计算所有进程的平均周转时间，带权平均周转时间； 3）输出：要求模拟整个调度过程，输出每个时刻的进程运行状态，如“时刻3：进程 B 开始运行”等等； 4）输出：要求输出计算出来的每个进程的周转时间，带权周转时间， 所有进程的平均周转时间，带权平均周转时间 【实验过程】 #include . 题目先来先服务FCFS和短作业优先SJF进程调度算法 姓名： 学号： 专业： 学院： 指导教师：林若宁 二零一八年十一月 一、实验目的 模拟单处理器系统的进程调度，分别采用短作业优先和先来先服务的进程调度算法作为进程设计算法，以加深对进程的概念及进程调度算法的理解． 二、实验内容 1. 短作业优先调度算法原理 短作业优先调度算法，是指对短作业或断进程优先调度的算法。它们可以分别可以用于作业调度和进程调度。短作业优先调度算法，是从后备队列中选择一个或若干个运行时间最短的作业，将它们调入内存运行。短进程优先调度算法，是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。 2. 先来先服务调度算法原理 先来先服务(FCFS)调度算法是一种最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。 三、程序设计 1.概要设计 程序包括主函数、FCFS算法函数、SJF算法函数、输出函数；主函数流程：输入文件中的数据—显示各进程数据—选择算法—调用相应算法的函数—输出结果 2.算法流程 SJF算法流程图： 3.详细设计 （1）定义一个结构体 typedef struct PCB { char job_id[10]; //作业ID float Arr_time; //到达时刻 float Fun_time; //估计运行时间 float Wait_time; //等待时间 float Start_time; //开始时刻 float Fin_time; //完成时刻 float Tur_time; //周转时间 float WTur_time; //带权周转时间 int Order; //优先标记 }list; （2）先来先服务算法函数 void fcfs(list *p,int count) //先来先服务算法{ list temp; //临时结构体变量int i; int j; 江南大学现代远程教育第二阶段练习题 考试科目:《操作系统》第5章至第7章（总分100分） ______________学习中心（教学点）批次：层次： 专业：学号：身份证号： 姓名：得分： 一、名词解释（12分） 1、死锁 2、逻辑地址 3、物理地址 4、地址重定位 二、试举例说明死锁？（6分） 三、采用静态资源分配预防死锁时，有哪些缺点？（6分） 四、有序资源分配法破坏的是产生死锁必要条件中的什么条件？（5分） 五、作业调度和进程调度的任务各是什么？（6分） 六、进程调度的时机有哪几种？（5分） 七、为什么要进行逻辑地址到物理地址的转换？（6分） 八、某系统的进程状态变迁图如图所示（该系统的进程调度方式为非剥夺方式），请说明： （20分） （1）一个进程发生变迁3的原因是什么？发生变迁2、变迁4的原因又是什么？ （2）下述因果变迁是否会发生，如果有可能的话，在什么情况下发生？ （3）（a）2→1；（b）3→2；（c）4→5；（d）4→2；（e）3→5 （4）根据此状态变迁图叙述该系统的调度策略、调度效果。 九、在单道批处理系统中，有下列三个作业用先来先服务调度算法和最短作业优先调度算法 进行调度，哪一种算法调度性能好些？请完成下表中未填写的各项。（8分） 十、 分区分配方法中的主要缺点是什么？如何克服这一缺点？（6分） 十一、 如图，主存中有两个空白区，现有这样一个作业序列： 作业1 要求50KB 作业2 要求60KB 作业3 要求70KB 若用首次适应算法和最佳适应算法来处理这个作业序列，试问哪一种算法可以分配得下，为什么？（10分） 十二、 选择填空题（10分） 1、死锁的四个必要条件是__________、不剥夺条件、__________和环路条件。 2、在分区存储管理中，最佳适应算法要求对空闲区表项按( )进行排列。 A.地址从大到小 B.地址从小到大 C.尺寸从大到小 D.尺寸从小到大 3、进程调度又称为（ ） A 、线程 B 、宏观 C 、微观 D 、作业 4、段式存储管理中的地址格式是（ ）地址。 A ．线性 B ．一维 C ．二维 D ．三维 参考答案 一、 名词解释 015KB 25KB 操作系统上机测试作业调度算法算法 一、实验目的和要求（供参考） 1.掌握作业调度功能和调度程序常用算法。 2.掌握利用C语言设计实现不同调度策略的作业调度算法。 3.验证不同作业调度算法对性能的影响。 二、实验环境（供参考） 1.知识准备：学过进程管理、作业管理、处理机调度等章节的内容。 2.开发环境与工具： 硬件平台——个人计算机。 软件平台——C语言开发环境。 三、实验内容 用“先来先服务（FCFS）”算法和“最短作业优先（SJF）”算法模拟作业调度。 要求：按作业的到达顺序输入各作业需要的运行时间，按算法调度输出平均周转时间。 例如(FCFS)，输入：8（到达时间0），5（到达时间2），7（到达时间3），1（到达时间6）J1 J2 J3 J4 0 8 13 20 21 输出：aver=(8+(13-2)+(20-3)+(21-6))/4=51/4 例如(SJF)，输入：8（到达时间0），5（到达时间2），7（到达时间3），1（到达时间6）J1 J4 J2 J3 0 8 9 14 21 输出：aver=(8+(9-6)+(14-2)+(21-3))/4=42/4 注：输入的格式任意，只要输出平均周转时间即可。 四、代码（带注释） 1、先来先服务 实验结果（截图呈现） 代码： #include 实验二作业调度实验 一. 目的要求： 用高级语言编写和调试一个或多个作业调度的模拟程序，以加深对作业调度算法的理解。 二. 例题：为单道批处理系统设计一个作业调度程序。 由于在单道批处理系统中，作业一投入运行，它就占有计算机的一切资源直到作业完成为止，因此调度作业时不必考虑它所需要的资源是否得到满足，它所占用的 CPU时限等因素。 作业调度算法：采用先来先服务（FCFS）调度算法，即按作业提交的先后次序进行调度。总是首先调度在系统中等待时间最长的作业。 每个作业由一个作业控制块JCB表示，JCB可以包含如下信息：作业名、提交时间、所需的运行时间、所需的资源、作业状态、链指针等等。 作业的状态可以是等待W(Wait)、运行R(Run)和完成F(Finish)三种状态之一。每个作业的最初状态总是等待W。 各个等待的作业按照提交时刻的先后次序排队，总是首先调度等待队列中队首的作业。 每个作业完成后要打印该作业的开始运行时刻、完成时刻、周转时间和带权周转时间，这一组作业完成后要计算并打印这组作业的平均周转时间、带权平均周转时间。 调度算法的流程图如下图所示。 三 . 实习题： 1、编写并调试一个单道处理系统的作业等待模拟程序。 作业等待算法：分别采用先来先服务（FCFS），最短作业优先（SJF）、响应比高者优先（HRN）的调度算法。 对每种调度算法都要求打印每个作业开始运行时刻、完成时刻、周转时间、带权周转时间，以及这组作业的平均周转时间及带权平均周转时间，以比较各种算法的优缺点。 2、编写并调度一个多道程序系统的作业调度模拟程序。 作业调度算法：采用基于先来先服务的调度算法。可以参考课本中的方法进行设计。 对于多道程序系统，要假定系统中具有的各种资源及数量、调度作业时必须考虑到每个作业的资源要求。 3、编写并调试一个多道程序系统的作业调度模拟程序。 作业调度算法：采用基于优先级的作业调度。 可以参考课本中的例子自行设计。 三 . 实验过程： 1、编写并调试一个单道处理系统的作业等待模拟程序。 先来先服务（FCFS）： main.cpp: /* **先来先服作业调度算法模拟 */ #include 第三章处理机调度与死锁 1，高级调度与低级调度的主要任务是什么？为什么要引入中级调度？ 【解】（1）高级调度主要任务是用于决定把外存上处于后备队列中的那些作业调入内存，并为它们创建进程，分配必要的资源，然后再将新创建的进程排在就绪队列上，准备执行。（2）低级调度主要任务是决定就绪队列中的哪个进程将获得处理机，然后由分派程序执行把处理机分配给该进程的操作。（3）引入中级调度的主要目的是为了提高内存的利用率和系统吞吐量。为此，应使那些暂时不能运行的进程不再占用宝贵的内存空间，而将它们调至外存上去等待，称此时的进程状态为就绪驻外存状态或挂起状态。当这些进程重又具备运行条件，且内存又稍有空闲时，由中级调度决定，将外存上的那些重又具备运行条件的就绪进程重新调入内存，并修改其状态为就绪状态，挂在就绪队列上，等待进程调度。 3、何谓作业、作业步和作业流？ 【解】作业包含通常的程序和数据，还配有作业说明书。系统根据该说明书对程序的运行进行控制。批处理系统中是以作业为基本单位从外存调入内存。作业步是指每个作业运行期间都必须经过若干个相对独立相互关联的顺序加工的步骤。 作业流是指若干个作业进入系统后依次存放在外存上形成的输入作业流；在操作系统的控制下，逐个作业进程处理，于是形成了处理作业流。 4、在什么情冴下需要使用作业控制块JCB？其中包含了哪些内容？ 【解】每当作业进入系统时，系统便为每个作业建立一个作业控制块JCB，根据作业类型将它插入到相应的后备队列中。 JCB 包含的内容通常有：1) 作业标识2)用户名称3)用户账户4)作业类型（CPU 繁忙型、I/O芳名型、批量型、终端型）5)作业状态6)调度信息（优先级、作业已运行）7)资源要求8)进入系统时间9) 开始处理时间10) 作业完成时间11) 作业退出时间12) 资源使用情况等 5．在作业调度中应如何确定接纳多少个作业和接纳哪些作业？ 【解】作业调度每次接纳进入内存的作业数，取决于多道程序度。应将哪些作业从外存调入内存，取决于采用的调度算法。最简单的是先来服务调度算法，较常用的是短作业优先调度算法和基于作业优先级的调度算法。 7．试说明低级调度的主要功能。 【解】（1）保存处理机的现场信息（2）按某种算法选取进程（3）把处理机分配给进程。 8、在抢占调度方式中，抢占的原则是什么？ 【解】剥夺原则有：（1）时间片原则各进程按时间片运行，当一个时间片用完后，便停止该进程的执行而重新进行调度。这种原则适用于分时系统、大多数实时系统，以及要求较高的批处理系统。（2）优先权原则通常是对一些重要的和紧急的作业赋予较高的优先权。当这种作业到达时，如果其优先权比正在执行进程的优先权高，便停止正在执行的进程，将处理机分配给优先权高的进程，使之执行。（3）短作业（进程）优先原则当新到达的作业（进程）比正在执行的作业（进程）明显地短时，将剥夺长作业（进程）的执行，将处理机分配给短作业（进程），使之优先执行。 9、选择调度方式和调度算法时，应遵循的准则是什么？ 【解】应遵循的准则有（1）面向用户的准则：周转时间短，响应时间快，截止时间的保证，优先权准则。（2）面向系统的准则：系统吞吐量高，处理机利用率好，各类资源的平衡利用。 10、在批处理系统、分时系统和实时系统中，各采用哪几种进程（作业）调度算法？ 【解】 批处理系统：FCFS算法、最小优先数优先算法、抢占式最小优先数优先算法 2 分时系统：可剥夺调度、轮转调度 实时系统：时间片轮转调度算法、非抢占优先权调度算法、基于时钟中断抢占的优先权调度算法、立即抢占的优先权调度。 11、何谓静态和动态优先权？确定静态优先权的依据是什么？ 【解】静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变。动态优先权是指，在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。确定静态优先权的依据是：（1）进程类型，通常系统进程的优先权高于一般用户进程的优先权。（2）进程对资源的需要。（3）用户要求，用户进程的紧迫程度及用户所付费用的多少来确定优先权的。 12、试比较FCFS和SPF两种进程调度算法。 【解】FCFS算法按照作业提交或进程变为就绪状态的先后次序，分派CPU。当前作业或进程占有CPU，直到执行完或阻塞，才让出CPU。在作业或进程唤醒后，并不立即恢复执行，通常等到当前作业或进程让出CPU。FCFS比较有利于长作业，而不利于短作业；有利于CPU繁忙的作业，而不利于I/O繁忙的作业。SPF有利于短进程调度，是从就绪队列中选出一估计运行时间最短的进 实验二作业调度 一.实验题目 1、编写并调试一个单道处理系统的作业等待模拟程序。 作业调度算法：分别采用先来先服务（FCFS），最短作业优先（SJF）、响应比高者优先（HRN）的调度算法。 （1）先来先服务算法：按照作业提交给系统的先后顺序来挑选作业，先提交的先被挑选。 （2）最短作业优先算法：是以进入系统的作业所提出的“执行时间”为标准，总是优先选取执行时间最短的作业。 （3）响应比高者优先算法：是在每次调度前都要计算所有被选作业（在后备队列中）的响应比，然后选择响应比最高的作业执行。 2、编写并调度一个多道程序系统的作业调度模拟程序。 作业调度算法：采用基于先来先服务的调度算法。可以参考课本中的方法进行设计。 对于多道程序系统，要假定系统中具有的各种资源及数量、调度作业时必须考虑到每个作业的资源要求。 二.实验目的： 本实验要求用高级语言（C语言实验环境）编写和调试一个或多个作业调度的模拟程序，了解作业调度在操作系统中的作用，以加深对作业调度算法的理解 三 .实验过程 <一>单道处理系统作业调度 1)单道处理程序作业调度实验的源程序: 执行程序: 2)实验分析： 1、由于在单道批处理系统中，作业一投入运行，它就占有计算机的一切资源直到作业完成为止，因此调度作业时不必考虑它所需要的资源是否得到满足，它所占用的 CPU 时限等因素。 2、每个作业由一个作业控制块JCB 表示，JCB 可以包含如下信息：作业名、提交时间、所需的运行时间、所需的资源、作业状态、链指针等等。作业的状态可以是等待W(Wait)、运行R(Run)和完成F(Finish)三种状态之一。每个作业的最初状态总是等待W 。 3、对每种调度算法都要求打印每个作业开始运行时刻、完成时刻、周转时间、带权周转时间，以及这组作业的平均周转时间及带权平均周转时间。 3)流程图: 二.最短作业优先算法 三.高响应比算法 图一.先来先服务流程图 4)源程序: #include <> #include <> #include <> #define getpch(type) (type*)malloc(sizeof(type)) #define NULL 0 int n; 代替 代替 处理器调度 选择题 ?当CPU执行操作系统代码时，则处理机处于( )。 ?A．执行态B．目态C．管态D．就绪态 ?( )是机器指令的扩充，是硬件的首次延伸，是加在硬件上的第一层软件。 ?A．系统调用B．操作系统C．内核D．特权指令 ?操作系统提供给程序员的接口是( )。 ?A．进程B．系统调用C．库函数D．B和C ?用户程序向系统提出使用外设的请求方式是( )。 ?A．作业申请B．原语C．系统调用D．I／O指令 ?当作业正常完成进入完成状态时，操作系统( )。 ?A．将输出该作业的结果并删除内存中的作业 ?B．将收回该作业的所占资源并输出结果 ?C．将收回该作业的所占资源及输出结果，并删除该作业 ?D．将收回该作业的所占资源及输出结果，并将它的控制块从当前的队列中删除 ?下列选项是关于作业和进程关系的描述，其中哪一个是不正确的( )。 ?A．作业的概念主要用在批处理系统中，而进程的概念则用在几乎所有的OS中。 ?B．作业是比进程低一级的概念。 ?C．一个作业至少由一个进程组成。 ?D．作业是用户向计算机提交任务的实体，而进程是完成用户任务的执行实体以及向系统申请分配资源的基本单位。 ?作业从后备作业到被调度程序选中的时间称为( )。 ?周转时间B．响应时间C．等待调度时间D．运行时间 ?设有三个作业J1，J2，J3，它们同时到达，运行时间分别为T1，T2，T3，且T1≤T2≤T3，若它们在一台处理机上按单道运行，采用短作业优先算法，则平均周转时间为( )。 ?A．T1+T2+T3 B．1／3(T1+T2+T3) ?C．T1+2／3T2+1／3T3 D．T1+1／3T2+2／3T3 ?从作业提交给系统到作业完成的时间间隔称为作业的( )。 ?A．中断时间B．等待时间C．周转时间D．响应时间 ?设有四个作业同时到达，每个作业执行时间均为2 h，它们在一台处理机上按单道方式运行，则平均周转时间为( )。 ?A．1 h B．5 h C．2．5 h D．8 h ?FCFS调度算法有利于( )。 ?A．长作业和CPU繁忙型作业B．长作业和I／O繁忙型作业 ?C．短作业和CPU繁忙型作业D．短作业和I／O繁忙型作业 ?下列哪种说法不是SJ(P)F调度算法的缺点( )。 ?A．对于长作业(进程)不利 ?B．未考虑作业(进程)的紧迫程度 ?C．不能有效降低作业(进程)的平均等待时间 ?D．由于根据的是用户提供的估计执行时间，因此不一定真正做到短而优先。 ?选择排队进程中等待时间最长的进程被优先调度，该调度算法是( )。 ?A．先来先服务调度算法B．短进程优先调度算法 ?C．优先权调度算法D．高响应比优先调度算法 ?在采用动态优先权的优先权调度算法中，如果所有进程都具有相同优先权初值，则此时的优先权调度算法实际上和( )相同。 ?A．先来先服务调度算法B．短进程优先调度算法 ?C．时间片轮转调度算法D．长进程优先调度算法 《操作系统》课程实验报告实验名称：短作业优先调度算法 姓名：陈凯 学号：541413430202 地点：四教楼301 指导老师：张旭 专业班级：嵌入式软件14-02 一、实验目的： 测试数据可以随即输入或从文件中读入。 必须要考虑到作业的到达时间 最终能够计算每一个作业的周转时间。 二、实验内容： 模拟实现短作业调度算法，具体如下： 设置作业体：作业名，作业的到达时间，服务时间，作业间的链接指针 进程初始化：由用户输入作业名、作业的到达时间和服务时间进行初始化。 显示函数：1、显示当前调度的是哪个作业，后备队列中有哪些作业 2、最终显示每个作业的作业名、到达时间、服务时间、完成时间和周转时间 排序函数：对就已到达的作业按照服务时间进行排序。注意考虑到达时间 调度函数：每次从已到达的作业队列队首调度优一个作业执行。 删除函数：作业结束后撤销。 三、实验代码 #include 题目：作业调度算法 班级：网络工程 姓名：朱锦涛 学号：E 一、实验目的 用代码实现页面调度算法，即先来先服务（FCFS）调度算法 、短作业优先算法、高响应比优先调度算法。通过代码的具体实现，加深对算法的核心的理解。 二、实验原理 1.先来先服务（FCFS）调度算法 FCFS是最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，系统将按照作业到达的先后次序来进行调度，或者说它是优先考虑在系统中等待时间最长的作业，而不管该作业所需执行的时间的长短，从后备作业队列中选择几个最先进入该队列的作业，将它们调入内存，为它们分配资源和创建进程。然后把它放入就绪队列。 2.短作业优先算法 SJF算法是以作业的长短来计算优先级，作业越短，其优先级越高。作业的长短是以作业所要求的运行时间来衡量的。SJF算法可以分别用于作业和进程调度。在把短作业优先调度算法用于作业调度时，它将从外存的作业后备队列中选择若干个估计运行时间最短的作业，优先将它们调入内存。 3、高响应比优先调度算法 高响应比优先调度算法则是既考虑了作业的等待时间，又考虑了作业的运行时间的算法，因此既照顾了短作业，又不致使长作业等待的时间过长，从而改善了处理机调度的性能。 如果我们引入一个动态优先级，即优先级是可以改变的令它随等待的时间的延长而增加，这将使长作业的优先级在等待期间不断地增加，等到足够的时间后，必然有机会获得处理机。该优先级的变化规律可以描述为： 优先权 = （等待时间 + 要求服务时间）/要求服务时间 三、实验内容 源程序： #include<> #include<> #include<> struct work { i nt id; i nt arrive_time; i nt work_time; i nt wait; f loat priority;作业调度算法C++实现
处理器调度习题
操作系统之调度算法和死锁中的银行家算法习题答案
作业调度算法(先来先服务算法,短作业算法)
3-2 作业调度算法
操作系统作业二
操作系统短作业优先调度算法
处理器调度习题教学内容
先来先服务和短作业优先调度算法
操作系统实验 FCFS和短作业优先SJF调度算法模拟
操作系统第2阶段练习题
操作系统作业调度算法
各类作业调度算法
计算机操作系统课后习题答案第三章(第四版)
作业调度实验报告
处理器调度习题
短作业优先调度算法
作业调度算法(先来先服务算法,短作业算法)
相关主题
文本预览