有n个独立的作业{1，2，..，n}，由m台相同的机器进行加工处理。作业i所需的处理时间为ti。现约定，任何作业可以在任何一台机器上加工处理，但未完工前不允许中断处理。任何作业不能拆分成更小的作业。多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成（n>m）。对于多级调度问题，使用以下哪种贪心策略比较合适（）A、作业从小到大依次分配给空闲的机器B、作业从大到小依次分配给空闲的机器C、每个机器分配一样的作业数D、使用以上几种贪心策略都能找到最优解，所以都合适

阅读下列算法说明和流程图，根据要求回答问题1～问题3。

[说明]

某机器上需要处理n个作业job1，job2，…，jobn，其中：

(1)每个作业jobi(1≤i≤n)的编号为i，jobi有一个收益值P[i]和最后期限值d[i]；

(2)机器在一个时刻只能处理一个作业，而且每个作业需要一个单位时间进行处理，一旦作业开始就不可中断，每个作业的最后期限值为单位时间的正整数倍；

(3)job1～jobn的收益值呈非递增顺序排列，即p[1]≥p[2]≥…≥p[n]；

(4)如果作业jobi在其期限之内完成，则获得收益p[i]；如果在其期限之后完成，则没有收益。

为获得较高的收益，采用贪心策略求解在期限之内完成的作业序列。图3-25是基于贪心策略求解该问题的流程图。

(1)整型数组J[]有n个存储单元，变量k表示在期限之内完成的作业数，J[1..k]存储所有能够在期限内完成的作业编号，数组J[1..k)里的作业按其最后期限非递减排序，即d[J[1]]≤…≤d[J[k]]。

(2)为了便于在数组J中加入作业，增加一个虚拟作业job0，并令d[0]=0，J[0]=0。

(3)算法大致思想是：先将作业job1的编号1放入J[1]，然后，依次对每个作业jobi(2≤i≤n)进行判定，看其能否插入到数组J中。若能，则将其编号插入到数组J的适当位置，并保证J中作业按其最后期限非递减排列；否则不插入。

jobi能插入数组J的充要条件是：jobi和数组J中已有作业均能在其期限之内完成。

(4)流程图中的主要变量说明如下。

i：循环控制变量，表示作业的编号；

k：表示在期限内完成的作业数；

r：若jobi能插入数组J，则其在数组J中的位置为r+1；

q：循环控制变量，用于移动数组J中的元素。

请将图3-25中的(1)～(3)空缺处的内容填写完整。

阅读下列说明和图，回答问题1至问题3，将解答填入对应栏内。

【说明】

某机器上需要处理n个作业．job1，job2，…，jobn，其中：

(1)每个作jobi(1≤i≤n)的编号为i，jobi有一个收益值p[i]和最后期限值d[i]小

(2)机器在一个时刻只能处理一个作业，而且每个作业需要一个单位时间进行处理，一旦作业开始就不可中断，每个作业的最后期限值为单位时间的正整数倍；

(3)job1～jobn的收益值呈非递增顺序排列，即p[1)≥P[2]≥…[n)：

(4)如果作业jobi在其期限之内完成，则获得收益9[i]；如果在其期限之后完成，则没有收益。

为获得较高的收益，采用贪心策略求解在期限之内完成的作业序列。图4*1是基于贪心策略求解该问题的流程图。

(1)整型数组J[]有n个存储单元，变量k众表示在期限之内完成的作业J[1..k]存储所有能够在期限内完成的作业编号，数组J[1..k]里的作业按其最后期限非递减排序，即d[J[1]]≤…≤d[J[k]]。

(2)为了便于在数组J中加入作业，增加一个虚拟作业Job0，并令d[0]=0，j[0]=0。

(3)算法大致思想：先将作业．job1的编号1放入J[1]，然后，依次对每个作业．jobi (2≤i≤n)进行判定，看其能否插入到数组J中。若能，则将其编号插入到数组J的适当位置，并保证J中作业按其最后期限非递减排列；否则不插入。

jobi能插入数组J的充要条件是：jobi和数组J中已有作业均能在其期限之内完成。

(4)流程图中的主要变量院明如下。

i：循环控制变量，表示作业的编号；

k：表示在期限内完成的作业数：

r：若．jobi能插入数组J，则其在数组了中的位置为r+1：

q：循环控制变量，用于移动数组J中的元素。

请填充图4-1中的空缺(1)、(2)和(3)处。

在进行批处理作业的调度时候，主要采用( )来完成调度。

A．操作控制命令

B．作业控制语言

C．作业调度算法

D．作业控制

作业管理的主要任务包括作业输入、作业处理和作业输出，其中作业处理的工作是(15)。在操作系统中，对批处理作业的控制方式是(16)。若系统中有四个作业，它们的到达时间、运行时间、开始时间、完成时间和周转时间如下表所示，则该系统采用的作业调度算法是(17)。

A．作业控制

B．作业调度

C．作业控制与作业调度

D．作业控制，作业调度与作业后备

试题四（共15分）

阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。

【说明】

用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为ai和bi。由于各个作业的特点和机器性能的关系，对某些作业，在A上处理时间长，而对某些作业在B上处理时间长。一台处理机在某个时刻只能处理一个作业，而且作业处理是不可中断的，每个作业只能被处理一次。现要找出一个最优调度方案，使得n个作业被这两台处理机处理完毕的时间（所有作业被处理的时间之和）最少。

算法步骤：

（1）确定候选解上界为R短的单台处理机处理所有作业的完成时间m，

（2）用p（x,y,k）=1表示前k个作业可以在A用时不超过x且在B用时不超过y时间 内处理完成，则p（x,y,k）=p（x-ak,y,k-1）||p（x,y-bk,k-1）（||表示逻辑或操作）。

（3）得到最短处理时问为min（max（x，y））。

【C代码】

下面是该算法的C语言实现。

（1）常量和变量说明

n: 作业数

m: 候选解上界

a: 数组，长度为n，记录n个作业在A上的处理时间，下标从0开始

b: 数组，长度为n，记录n个作业在B上的处理时间，下标从0开始

k: 循环变量

p: 三维数组，长度为（m+1）*（m+1）*（n+1）

temp: 临时变量

max: 最短处理时间

（2）C代码

include<stdio.h>

int n, m;

int a[60], b[60], p[100][100][60];

void read(){ /*输入n、a、b，求出m，代码略*/}

void schedule(){ /*求解过程*/

int x,y,k;

for（x=0；x<=m；x++）{

for(y=0；y<m；y++）{

（1）

for（k=1；k<n；k++）

p[x][y][k]=0；

}

}

for（k=1；k<n；k++）{

for（x=0；x<=m；x++）{

for（y=0；y<=m；y++）{

if（x - a[k-1]>=0） （2） ；

if（ （3） ）p[x][y][k]=(p[x][y][k] ||p[x][y-b[k-1]][k-1]);

}

}

}

}

void write(){ /*确定最优解并输出*/

int x，y，temp，max=m;

for（x=0；x<=m；x++）{

for（y=0;y<=m;y++）{

if( （4） ）{

temp=（5） ；

if（temp< max）max = temp;

}

}

}

printf("\n%d\n"，max）,

}

void main(){read();schedule();write();}

【问题1】 （9分）

根据以上说明和C代码，填充C代码中的空（1）～（5）。

【问题2】（2分）

根据以上C代码，算法的时间复杂度为（6）（用O符号表示）。

【问题3】（4分）

考虑6个作业的实例，各个作业在两台处理机上的处理时间如表4-1所示。该实例的最优解为（7），最优解的值（即最短处理时间）为（8）。最优解用（x1,x2,x3,x4,x5,x6）表示，其中若第i个作业在A上赴理，则xi=l，否则xi=2。如（1，1，1，1，2，2）表示作业1，2，3和4在A上处理，作业5和6在B上处理。

一个有两个作业管理进程的批处理系统，作业调度采用最高响应比优先的算法，进程调度采用基于优先数(优先数大表示优先级别高)的算法。有以下作业序列：

作业F的运行结束时间为(26)(假定在作业运行期间，除了有空闲的作业管理进程以外，系统不进行调度工作)。

A．14：50

B．15：30

C．13：40

D．13：10

一个有两个作业管理进程的批处理系统，作业调度采用基于优先数(优先数大表示优先级别高)的算法，进程调度采用短作业优先的算法(按剩余运行时间计算作业的长短)。有以下作业序列：

作业F的运行结束时间为(23)(假定在作业运行期间，除了有空闲的作业管理进程以外，系统不进行调度工作)

A．14：50

B．15：30

C．13：40

D．13：10

若操作系统中有n个作业Ji(i=1,2,…,n)，分别需要Ti(i=1,2,…,n)的运行时间，采用(23)的作业调度算法可以使平均周转时间最短。

A．先来先服务(FCFS)

B．最短作业优先(SJF)

C．响应比高者优先(HRN)

D．优先级

试题四(共15 分)

阅读下列说明和图，回答问题 1 至问题 3，将解答填入答题纸的对应栏内。

【说明】

某机器上需要处理 n 个作业 job1, job2, …, jobn，其中：

(1) 每个作业jobi(1≤i≤n)的编号为 i， jobi有一个收益值 p[i]和最后期限值 d[i]；

(2) 机器在一个时刻只能处理一个作业，而且每个作业需要一个单位时间进行处理，

一旦作业开始就不可中断，每个作业的最后期限值为单位时间的正整数倍；

(3) job1～jobn 的收益值呈非递增顺序排列，即p[1]≥p[2]≥…≥p[n]；

(4) 如果作业jobi在其期限之内完成，则获得收益 p[i]；如果在其期限之后完成，

则没有收益。

为获得较高的收益，采用贪心策略求解在期限之内完成的作业序列。图 4-1 是基于贪

心策略求解该问题的流程图。

(1) 整型数组 J[]有 n 个存储单元，变量 k 表示在期限之内完成的作业数，J[1..k]存储所有能够在期限内完成的作业编号， 数组 J[1..k]里的作业按其最后期限非递减排序，即d[J[1]]≤ … ≤d[J[k]]。

(2) 为了方便于在数组 J 中加入作业，增加一个虚拟作业 job0，并令d[0] = 0， J[0] = 0。

(3) 算法大致思想：先将作业 job1 的编号 1 放入 J[1]，然后，依次对每个作业 jobi (2≤i≤n)进行判定，看其能否插入到数组 J 中，若能，则将其编号插入到数组 J 的适当位置，并保证 J 中作业按其最后期限非递减排列，否则不插入。 jobi能插入数组 J 的充要条件是：jobi 和数组 J 中已有作业均能在其期限之内完成。

(4) 流程图中的主要变量说明如下：

i：循环控制变量，表示作业的编号；

k：表示在期限内完成的作业数；

r：若jobi能插入数组 J，则其在数组 J 中的位置为 r+1；

q：循环控制变量，用于移动数组 J 中的元素。

【问题 1】 （9 分）

请填充图4-1 中的空缺(1)、(2)和(3)处。

【问题 2】(4 分)

假设有 6 个作业 job1, job2, …, job6；

完成作业的收益数组 p=(p[1],p[2],p[3],p[4],p[5],p[6]) = (90,80,50,30,20,10)；

每个作业的处理期限数组 d=(d[1],d[2],d[3],d[4],d[5],d[6]) = (1,2,1,3,4,3)。

请应用试题中描述的贪心策略算法，给出在期限之内处理的作业编号序列 (4)

（按作业处理的顺序给出） ，得到的总收益为 (5) 。

【问题 3】(2 分)

对于本题的作业处理问题， 用图 4-1的贪心算法策略， 能否求得最高收益？ (6) 。

用贪心算法求解任意给定问题时，是否一定能得到最优解？ (7) 。