作业调度算法例题

㈠ 关于作业调度的算法怎么写

网络上搜一下就有了，我做这个就是找的

㈡ 有一个具有两道作业的批处理系统，作业调度采用短作业优先调度算法，进程调度采用以优先数为基础的抢占式

本题中的系统是两道作业系统，因此每次只能有两个作业进入系橡逗统，作业调度采

用短作业优先算法，只有调度进入系统的进程方能参与进程调度；进程调度采用

基于优先数的抢占式调度算法，高优先级的进程可以抢占系统处理机。

本题的作业和进程的推进过程如下：

10：00 A作业到达，被作业调度程序调度进入系统，被进程调度程序调度开始运行

10：20 A作业运行20分钟，剩余20分钟，由于优先级低，被进程调度程序调度处于就绪状态

B作业到达，被作业调度程序调度进入系统，由于优先级高，被进程调度程序调度处于开始运行状梁槐卖态

10：30 A作明拆业等待10分钟，剩余20分钟，继续等待

B作业运行10分钟，剩余20分钟，继续运行

C作业到达，等待被作业调度程序调度

10：50 A作业等待30分钟，剩余20分钟，由于优先级高，被进程调度程序调度处于开始运行状态

B作业运行30分钟，作业完成，结束运行

C作业等待20分钟，由于估计运行时间较长，仍未被调入系统中运行

D作业到达，被进程调度程序调度处于就绪状态

11：10 A作业运行40分钟，作业完成，结束运行

C作业等待30分钟，被作业调度程序调度进入系统，由于优先级高，被进程调度程序调度处于开始运行状态

D作业等待10分钟，由于优先级低，被进程调度程序调度处于就绪状态

12：00 C作业运行50分钟，作业完成，结束运行

D作业等待70分钟，被进程调度程序调度处于开始运行状态

12：20 D作业运行20分钟，作业完成，结束运行

各作业周转时间为：

作业A 70，作业B 30，作业C 90，作业D 90。

平均作业周转时间为70分钟。

参考1.网页链接

2.网页链接

略改动。

㈢ 操作系统的调度算法

1)10:00Job1到达并投入运行。此时内存中有作业:Job1
2)10:05 Job2到达并进入内存。此时，Job1运行时间剩余是25min， Job2运行剩余时间是20min，根据SRTF，Job2开始运行。
3)10:25 Job2运行结束。Job3、Job4在后备队列中，据SJF，Job3进入内存，据SRTF，Job3开始运行。内存：Job1、Job3
4)10:30 Job3运行结束。Job4在后备队列中，Job4进入内存，据SRTF，Job4开始运行。内存：Job1、Job4
5)10:40 Job4运行结束。Job1重新继续运行。
6)11:05 Job1运行结束。

㈣ 编写代码实现作业的三种调度算法

#include<windows.h>
#include<iostream>
#include<stdio.h>
#include<string>
using namespace std;
const int maxnum=100;
int N; /*进程数*/
double start[maxnum],endtime[maxnum],arrive[maxnum],runtime[maxnum],zhou[maxnum];
double averagezhou; // 平均周转时间
double average_zhou; //平均带权周转时间
char name; //进程名
double dqzhou[maxnum]; //带权周转时间
typedef struct node
{
char name[10]; //进程名
int round; //进程时间轮转时间片
int cputime; //进程占用CPU时间
int needtime; //进程到完成还要的时间
char state; //进程的状态
struct node *next; //链指针
}PCB;
PCB *finish,*ready,*tail,*run; /*队列指针*/

void firstin() /*将就绪队列中的第一个进程投入运行*/
{
run=ready; /*就绪队列头指针赋值给运行头指针*/
run->state='R'; /*进程状态变为运行态*/
ready=ready->next; /*就绪对列头指针后移到下一进程*/
}
void print1(PCB *q) /*进程PCB输出*/
{
printf("进程名 已运行时间 还需要时间 时间片 状态\n");
printf(" %-10s%-15d%-10d%-10d %-c\n",q->name,q->cputime,q->needtime,q->round,q->state);
}
void print() /*输出函数*/
{
PCB *p;
if(run!=NULL) /*如果运行指针不空*/
print1(run); /*输出当前正在运行的PCB*/
p=ready; /*输出就绪队列PCB*/
while(p!=NULL)
{
print1(p);
p=p->next;
}
p=finish; /*输出完成队列的PCB*/
while(p!=NULL)
{
print1(p);
p=p->next;
}
}
void insert(PCB *p2) //轮转法插入函数
{
tail->next=p2; //将新的PCB插入在当前就绪队列的尾
tail=p2;
p2->next=NULL;
}
void create() /*创建进程PCB*/
{
PCB *p;
int i,time;
char na[10];
ready=NULL;
finish=NULL;
run=NULL;
printf("请输入进程名称和所需要CPU的时间:\n");
for(i=1;i<=N;i++)
{
p=(PCB *)malloc(sizeof(PCB));
scanf("%s",na);
scanf("%d",&time);
strcpy(p->name,na);
p->cputime=0;
p->needtime=time;
if(i==1)
p->state='R';
else
p->state='W';
p->round=1; /*时间片*/
if(ready!=NULL)
insert(p);
else
{
p->next=ready;
ready=p;
tail=p;
}
}
printf("------------------------------------------------------------------\n");
print(); /*输出进程PCB信息*/
run=ready; /*将就绪队列的第一个进程投入运行*/
ready=ready->next;
run->state='R';
}
void RR() //时间片轮转调度
{
while(run!=NULL)
{
run->cputime=run->cputime+1;
run->needtime=run->needtime-1;
if(run->needtime==0) /*运行完将其变为完成态，插入完成队列*/
{
run->next=finish;
finish=run;
run->state='F';
run=NULL;
if(ready!=NULL)
firstin(); /*就绪对列不空，将第一个进程投入运行*/
}
else
if(ready!=NULL) /*如就绪队列不空*/
{
run->state='W'; /*将进程插入到就绪队列中等待轮转*/
insert(run);
firstin(); /*将就绪对列的第一个进程投入运行*/
}
printf("------------------------------------------------------------------\n");
print(); /*输出进程信息*/
}
}

void FCFS(double *arrive,double *runtime,double n) //先来先服务调度算法
{
start[0]=arrive[0]; //开始执行时间=到达时间
endtime[0]=start[0]+runtime[0]; //完成时间=开始时间+服务时间
zhou[0]=endtime[0]-arrive[0]; //周转时间=完成时间-到达时间
dqzhou[0]=zhou[0]/runtime[0];
for(int i=0;i<n;i++)
{
if(endtime[i-1]>arrive[i]||endtime[i-1]==arrive[i])
endtime[i]=endtime[i-1]+runtime[i];
else
endtime[i]=arrive[i]+runtime[i];
zhou[i]=endtime[i]-arrive[i];
dqzhou[i]=zhou[i]/runtime[i];
averagezhou+=zhou[i];
average_zhou+=dqzhou[i];
}
averagezhou=averagezhou/n;
average_zhou=average_zhou/n;
cout<<"完成时间为:"<<endl;
for(int j=0;j<n;j++)
cout<<endtime[j]<<" "<<endl;
cout<<"周转时间为:"<<endl;
for(int k=0;k<n;k++)
cout<<zhou[k]<<" "<<endl;
cout<<"带权周转时间为:"<<endl;
for(int m=0;m<n;m++)
cout<<dqzhou[m]<<" "<<endl;
cout<<"平均周转时间为:"<<endl;
cout<<averagezhou<<" "<<endl;
cout<<"平均带权周转时间为:"<<endl;
cout<<average_zhou<<" "<<endl;
}

void SJF(double *arrive,double *runtime,double n) //短作业优先调度算法
{
int end[maxnum]; //用于标记进程是否已经执行，应经执行end[i]=1,否则为0;
for(int k=0;k<n;k++)
end[k]=0;
int temp,now=0,next=1,p=1; //now表示刚执行完的进程号，next表示下一个要执行的进程号
start[0]=arrive[0]; //开始执行时间=到达时间
endtime[0]=start[0]+runtime[0]; //完成时间=开始时间+服务时间
zhou[0]=endtime[0]-arrive[0]; //周转时间=完成时间-到达时间
dqzhou[0]=zhou[0]/runtime[0]; //带权周转时间=周转时间/服务时间
averagezhou=zhou[0];
average_zhou=dqzhou[0];
end[now]=1; //执行完的进程设置为1；
for(int i=1;i<n;i++)
{
int j;
for(j=1;j<n;)
{
if(arrive[j]<endtime[now]||arrive[j]==endtime[now])
j++;
else
break;
}
temp=j;
int min=p;
for(j=1;j<=temp;j++)
{
if(runtime[min]>runtime[j] && end[j]==0)
min=j;
}
next=min;
endtime[next]=endtime[now]+runtime[next];
zhou[next]=endtime[next]-arrive[next];
dqzhou[next]=zhou[next]/runtime[next];
averagezhou+=zhou[next];
average_zhou+=dqzhou[next];
end[next]=1;
now=next;
next=p;
while(end[p]!=0)
p++;
}
averagezhou=averagezhou/n;
average_zhou=average_zhou/n;
cout<<"完成时间为:"<<endl;
for(int j=0;j<n;j++)
cout<<endtime[j]<<" "<<endl;
cout<<"周转时间为:"<<endl;
for(k=0;k<n;k++)
cout<<zhou[k]<<" "<<endl;
cout<<"带权周转时间为:"<<endl;
for(int m=0;m<n;m++)
cout<<dqzhou[m]<<" "<<endl;
cout<<"平均周转时间为:"<<endl;
cout<<averagezhou<<" "<<endl;
cout<<"平均带权周转时间为:"<<endl;
cout<<average_zhou<<" "<<endl;
}

int EDF() //最早截止时间的调度算法
{
int arrive_A,arrive_B; //标记进程A,进程B的到达时间
int zhouqi_A,zhouqi_B,serve_A,serve_B; //进程的周期时间和服务时间
int i,j,a=0,b=0,ka=0,kb=0; //ka,kb为开关,i,j,a,b为进程下标
int num_a=0,num_b=0; //服务累计时间
printf("输入进程A的周期时间,服务时间: ");
scanf("%d%d",&zhouqi_A,&serve_A);
printf("输入进程B的周期时间,服务时间: ");
scanf("%d%d",&zhouqi_B,&serve_B);
for(int T=0;T<=100;T++)
{
if(num_a==serve_A) //进程A完成
{
num_a=serve_A+1;
printf("当T=%d时",T);
printf("进程A%d结束\n",a);
if(num_b<serve_B)
{
printf(" 调用进程B%d\n",b);
kb=1;
}
ka=0;
}
if(num_b==serve_B)
{
num_b=serve_B+1;
printf("当T=%d时",T);
printf("进程B%d结束\n",b);
if(num_a<serve_A)
{
printf(" 调用进程A%d\n",a);
ka=1;
}
kb=0;
}
if(T%zhouqi_A==0 && T%zhouqi_B==0)
{
arrive_A=arrive_B=T;
j=++a;
i=++b;
printf("当T=%d时,进程A%d和进程B%d同时产生，此时，",T,j,i);
if(zhouqi_A<=zhouqi_B)
{
printf("调用进程A%d，阻塞进程B%d\n",j,i);
ka=1;
kb=0;
}
else
{
printf("调用进程B%d，阻塞进程A%d\n",i,j);
ka=0;
kb=1;
}
num_a=num_b=0;
}
if(T%zhouqi_A==0&&T%zhouqi_B!=0)
{
arrive_A=T;
printf("当T=%d时",T);
printf("进程A%d产生 ",++a); //不可能与进程A竞争处理器
num_a=0;
if(num_b<serve_B) //进程B没有完成
if(arrive_B+zhouqi_B>arrive_A+zhouqi_A) //若进程B最早截止时间大于进程A的,则执行进程A
{
printf("进程A%d执行。\n",a);
ka=1;
kb=0;
}
else //若进程B最早截止时间小于等于进程A的
printf("进程B%d继续执行。\n",b);
else //进程B完成
{
printf("进程A%d执行。\n",a);
ka=1;
}
}
if(T%zhouqi_A!=0 && T%zhouqi_B==0)
{
arrive_B=T;
printf("当T=%d时",T);
printf("进程B%d产生，",++b); //不可能与进程B竞争处理器
num_b=0;
if(num_a<serve_A) //进程A没有完成
if(arrive_B+zhouqi_B>=arrive_A+zhouqi_A) //进程A的最早截止时间不小于B
printf("进程A%d继续执行。\n",a);
else
{
printf("进程B%d执行。\n",b);
kb=1;
ka=0;
}

else //进程A完成
{
printf("进程B%d执行。\n",b);
kb=1;
}
}
if(ka)
num_a++;
if(kb)
num_b++;
}
return 1;
}

int main()
{
system("color 0b"); //设置颜色
cout<<"最早截止时间的调度算法如下: "<<endl<<endl;
EDF();
int n;
cout<<endl;
cout<<"请输入进程的数目: ";
cin>>n;
cout<<"请按进程到达时间从小到大依次输入n个进程的到达时间: "<<endl;
for(int i=0;i<n;i++)
cin>>arrive[i];
cout<<"请按上面进程的顺序依次输入n个进程的服务时间: "<<endl;
for(int j=0;j<n;j++)
cin>>runtime[j];
cout<<"先来先服务调度算法如下: "<<endl;
FCFS(arrive,runtime,n);
cout<<endl<<endl;
cout<<"短作业优先调度算法如下: "<<endl;
SJF(arrive,runtime,n);
cout<<endl<<endl;
printf("轮转调度算法如下:\n\n");
printf("输入创建进程的数目:\n");
scanf("%d",&N);
create();
RR();
return 0；
}

㈤ 在各种作业调度算法中若所有作业同时到达

答案是短作业优先,但是不利于长作业执行.

㈥ 有关作业调度优先算法问题

短作业优先调度算法纳肢，作业运行时间短的先运行，但是J1作业先来先运行。所以为C.J1-J3-J4-J2。
。结束时间减去提交宴弯时间就是周转时间平均周转时间=周转时间（晌茄闷J1+J2+J3+J4）/4。答案：c。d

㈦ 以下五个作业，fcfs sjf hrrn三种调度算法平均周转时间，高响应比怎么算

作业调度算法 .

1. 先来先服务（FCFS, First Come First Serve）是最简单的调度算法，按先后顺序进行调度。

定义：

按照作业提交或进程变为就绪状态的先后次序，分派CPU；

当前作业或进程占用CPU，直到执行完或阻塞，才出让CPU（非抢占方式）。

在作业或进程唤醒后（如I/O完成），并不立即恢复执行，通常等到当前作业或进程出让CPU。

适用场景：

比较有利于长作业，而不利于短作业。因为长作业会长时间占据处理机。

有利于CPU繁忙的作业，而不利于I/O繁忙的作业。

算法实现原理图：

2. 轮转法(Round Robin)

轮转法是让每个进程在就绪队列中的等待时间与享受服务的时间成正比例。

定义：

将系统中所有的就绪进程按照FCFS原则，排成一个队列。

每次调度时将CPU分派给队首进程，让其执行一个时间片。时间片的长度从几个ms到几百ms。

在一个时间片结束时，发生时钟中断。

调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程。

进程可以未使用完一个时间片，就出让CPU（如阻塞）。

时间片长度的确定：

时间片长度变化的影响

过长－>退化为FCFS算法，进程在一个时间片内都执行完，响应时间长。

过短－>用户的一次请求需要多个时间片才能处理完，上下文切换次数增加，响应时间长。

对响应时间的要求：T(响应时间)=N(进程数目)*q(时间片)

就绪进程的数目：数目越多，时间片越小

系统的处理能力：应当使用户输入通常在一个时间片内能处理完，否则使响应时间，平均周转时间和平均带权周转时间延长。

算法实现原理图：

3. 多级反馈队列算法(Round Robin with Multiple Feedback)

多级反馈队列算法是轮转算法和优先级算法的综合和发展。

定义：

设置多个就绪队列，分别赋予不同的优先级，如逐级降低，队列1的优先级最高。每个队列执行时间片的长度也不同，规定优先级越低则时间片越长，如逐级加倍。

新进程进入内存后，先投入队列1的末尾，按FCFS算法调度；若按队列1一个时间片未能执行完，则降低投入到队列2的末尾，同样按FCFS算法调度；如此下去，降低到最后的队列，则按“时间片轮转”算法调度直到完成。

仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。如果进程执行时有新进程进入较高优先级的队列，则抢先执行新进程，并把被抢先的进程投入原队列的末尾。

优点：

为提高系统吞吐量和缩短平均周转时间而照顾短进程。

为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程。

不必估计进程的执行时间，动态调节

几点说明：

I/O型进程：让其进入最高优先级队列，以及时响应I/O交互。通常执行一个小时间片，要求可处理完一次I/O请求的数据，然后转入到阻塞队列。

计算型进程：每次都执行完时间片，进入更低级队列。最终采用最大时间片来执行，减少调度次数。

I/O次数不多，而主要是CPU处理的进程。在I/O完成后，放回优先I/O请求时离开的队列，以免每次都回到最高优先级队列后再逐次下降。

为适应一个进程在不同时间段的运行特点，I/O完成时，提高优先级；时间片用完时，降低优先级。

算法实现原理图：

4. 优先级法（Priority Scheling）

优先级算法是多级队列算法的改进，平衡各进程对响应时间的要求。适用于作业调度和进程调度，可分成抢先式和非抢先式。

静态优先级：

作业调度中的静态优先级大多按以下原则确定：

由用户自己根据作业的紧急程度输入一个适当的优先级。

由系统或操作员根据作业类型指定优先级。

系统根据作业要求资源情况确定优先级。

进程的静态优先级的确定原则：

按进程的类型给予不同的优先级。

将作业的情态优先级作为它所属进程的优先级。

动态优先级：

进程的动态优先级一般根据以下原则确定：

根据进程占用有CPU时间的长短来决定。

根据就绪进程等待CPU的时间长短来决定。

5．短作业优先法（SJF, Shortest Job First）

短作业优先又称为“短进程优先”SPN(Shortest Process Next)；这是对FCFS算法的改进，其目标是减少平均周转时间。

定义：

对预计执行时间短的作业（进程）优先分派处理机。通常后来的短作业不抢先正在执行的作业。

SJF的特点：

(1) 优点：

比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间；

提高系统的吞吐量；

(2) 缺点：

对长作业非常不利，可能长时间得不到执行；

未能依据作业的紧迫程度来划分执行的优先级；

难以准确估计作业（进程）的执行时间，从而影响调度性能。

SJF的变型：

“最短剩余时间优先”SRT(Shortest Remaining Time)（允许比当前进程剩余时间更短的进程来抢占）

“最高响应比优先”HRRN(Highest Response Ratio Next)（响应比R = (等待时间 + 要求执行时间) / 要求执行时间，是FCFS和SJF的折衷）

6. 最高响应比优先法(HRN，Highest Response_ratio Next)

最高响应比优先法是对FCFS方式和SJF方式的一种综合平衡。FCFS方式只考虑每个作业的等待时间而未考虑执行时间的长短，而SJF方式只考虑执行时间而未考虑等待时间的长短。因此，这两种调度算法在某些极端情况下会带来某些不便。HRN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的作业投入执行。

响应比R定义如下： R =(W+T)/T = 1+W/T

其中T为该作业估计需要的执行时间，W为作业在后备状态队列中的等待时间。每当要进行作业调度时，系统计算每个作业的响应比，选择其中R最大者投入执行。这样，即使是长作业，随着它等待时间的增加，W / T也就随着增加，也就有机会获得调度执行。这种算法是介于FCFS和SJF之间的一种折中算法。由于长作业也有机会投入运行，在同一时间内处理的作业数显然要少于SJF法，从而采用HRN方式时其吞吐量将小于采用SJF 法时的吞吐量。另外，由于每次调度前要计算响应比，系统开销也要相应增加。

㈧ 求一份儿C语言优先级调度算法要求如下

#include "string.h"
#define n 10 /*假定系统中可容纳的作业数量为n*/
typedef struct jcb
{char name[4]; /*作业名*/
int length; /*作业长度，所需主存大小*/
int printer; /*作业执行所需打印机的数量*/
int tape; /*作业执行所需磁带机的数量*/
int runtime; /*作业估计执行时间*/
int waittime; /*作业在系统中的等待时间*/
int next; /*指向下一个作业控制块的指针*/
}JCB; /*作业控制块类型定义*/
int head; /*作业队列头指针定义*/
int tape,printer;
long memory;
JCB jobtable[n]; /*作业表*/
int jobcount=0; /*系统内现有作业数量*/
shele( )
/*作业调度函数*/
{float xk,k;
int p,q,s,t;
do
{p=head;
q=s=-1;
k=0;
while(p!=-1)
{ if(jobtable[p].length<=memory&&jobtable[p].tape<=tape&&jobtable[p].printer<=printer)
{ /*系统可用资源是否满足作业需求*/
xk=(float)(jobtable[p].waittime)/jobtable[p].runtime;
if(q==0||xk>k) /*满足条件的第一个作业或者作业q的响应比小于作业p的响应比*/
{k=xk; /*记录响应比*/
q=p;
t=s;
}/*if*/
}/*if*/
s=p;
p=jobtable[p].next; /*指针p后移*/
}/*while*/
if(q!=-1)
{ if(t==-1) /*是作业队列的第一个*/
head=jobtable[head].next;
else
jobtable[t].next=jobtable[q].next;
/*为作业q分配资源：分配主存空间；分配磁带机;分配打印机*/
memory=memory-jobtable[q].length;
tape=tape-jobtable[q].tape;
printer=printer-jobtable[q].printer;
printf("选中作业的作业名：%s\n",jobtable[q].name);
}
}while(q!=-1);
}/*作业调度函数结束*/

main( )
{char name[4];
int size,tcount,pcount,wtime,rtime;
int p;
/*系统数据初始化*/
memory=65536;
tape=4;
printer=2;
head=-1;
printf("输入作业相关数据(以作业大小为负数停止输入)：\n");
/*输入数据，建立作业队列*/
printf("输入作业名、作业大小、磁带机数、打印机数、等待时间、估计执行时间\n");
scanf("%s%d%d %d %d %d",name,&size,&tcount,&pcount,&wtime,&rtime);
while(size!=-1)
{/*创建JCB*/
if(jobcount<n)p=jobcount;
else { printf("无法再创建作业\n");
break;
}
jobcount++;
/*填写该作业相关内容*/
strcpy(jobtable[p].name,name);
jobtable[p].length=size;
jobtable[p].printer=pcount;
jobtable[p].tape=tcount;
jobtable[p].runtime=rtime;
jobtable[p].waittime=wtime;
/*挂入作业队列队首*/
jobtable[p].next=head;
head=p;
/* 输入一个作业数据*/
printf("输入作业名、作业大小、磁带机数、打印机数、等待时间、估计执行时间\n");
scanf("%s%d%d%d%d%d",name,&size,&tcount,&pcount,&wtime,&rtime);
}/*while*/
shele( ); /*进行作业调度*/
}/*main( )函数结束*/

㈨ 作业调度算法一道题的解析——FCFS算法

10.1时，①装入主存，主存：15k，85k空闲，计算：①，等待队列：空
10.3时，②装入主存，主存：15k，60k，25k空闲，计算：①，等待队列：②
10.4时，①完成计算，主存：15k空闲，60k，25k空闲，计算：②，等待队列：空
10.5时，③要装入主存，但由于内存不足，等待
10.6时，④装入主存，主存：10k，5k空闲，60k，25k空闲，计算：②，等待队列：④
10.7时，⑤装入主存，主存：10k，5k空闲，60k，20k，5k空闲，计算：②，等待队列：④，⑤
10.9时，②完成计算，主存：10k，65k空闲，20k，5k空闲，计算：④，等待队列：⑤
10.9时，③由于存在超过50k的空间，装入主存，主存：10k，50k，15k空闲，20k，5k空闲
计算：④，等待：⑤，③（此时按照先来先服务调度，⑤为先来的作业）
10.13时，④完成计算，主存：10k空闲，50k，15k空闲，20k，5k空闲，计算：⑤，等待队列：③
10.15时，⑤完成计算，主存：15k空闲，60k，25k空闲，计算：②，等待队列：空
10.19时，③完成计算，主存：100k空闲，计算：空，等待队列：空
因此，顺序为①②④⑤③

㈩ 处理机调度在主存中的作业均分cpu时间

系统采用SJF 被更短作业抢占。(1)分别给出6个作业的执行时间序列、即开始执行时间、作业完成

(1) J2 到达时抢占J1 ; J3 到达时抢占J2 。

(2）但J4 到达时，因不满足SJF ，故J4 不能被运行，J3 继续执行5 分钟。

(3）由于是4 道的作业系统，故后面作业不能进入主存而在后备队列等待，直到有作业结束。

(4）根据进程调度可抢占原则，J3 第一个做完。而这时J5 、J6 均己进入后备队列，而J5 可进入主存。

(5）因J5 最短，故它第二个完成。这时J6 方可进入主存。因J6 最短，故它第三个完成。

(6）然后是：J4 、J2和J1

(7) T =( 155 + 95 + 20 + 55 + 15 + 20 ) / 6 = 60

有一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法，在下表所示的作业序列，作业优先数即为进程优

(1)(2)计算平均周转时间。

每个作业运行将经过两个阶段：作业调度(SJF算法) 和进程调度(优先数抢占式) 。另外，批处理最多容纳2道作业，更多的作业将在后备队列等待。

(2) 10:20，作业B 到达且优先权高于作业A ，故作业B 投入运行而作业A 在就绪队列等待。

(3) 10:30，作业C 到达，因内存中已有两道作业，故作业C 进入作业后备队列等待。

(4) 10:50，作业B 运行结束，作业D 到达，按SJF 短作业优先算法，或迅作业D 被装入内存进入就绪队列。而由于作业A 的优先级高于作业D ，故作业A 投入运行。

(5) 11:10，作业A 运行结束，作业C 被调入内存，且作业C 的优先级高于作业D ，故作业C 投入运行。

(6) 12:00，作业C 运行结束，作业D 投入运行。 (7) 12:20，作业，作业D 90。平均作业周转时间为70分钟。

某多道程序设计系统供用户使用的主存为100K ，磁带机2台，打印机1台。采用可变分

在

主存中的各作业平分CPU 时间。现求：(1)作业被调度的先后次序?(2)全部作业运行结束的时间?(3)作业平均周转时间为多少?(4)最大作业周转时间为多少? 答：(1)作业调度选择的作业次序为：作业1、作业3、作业4、作业2和作业5。 (2)全部作业尘兆运行结束的时间9:30。

(3)周转时间：作业1为30分钟、作业2为55分钟、作业3为40分钟、作业4

为40分钟和作业5为55分钟。 (4)平均作业周转时间=44分钟。 (5) )最大作业周转时间为55分钟。

分析：本题综合测试了作业调度、进程调度、及对外设的竞争、主存的竞争。 8 : 00 作业1 到达，占有资源并调入主存运行。 8 : 20 作业2 和3 同时到达，但作业2 因分不到打印机，只能在后备队列等待。作业3 资源满足，可进主存运行，并与作业1 平分CPU 时间。

8 : 30 作业1 在8 : 30 结派团租束，释放磁带与打印机。但作业2 仍不能执行，因不能移动而没有30KB 的空闲区，继续等待。作业4 在8 : 30 到达，并进入主存执行，与作业3 分享CPU

8 : 35 作业5 到达，因分不到磁带/打印机，只能在后备队列等待。 9 : 00 作业3 运行结束，释放磁带机。此时作业2 的主存及打印机均可满足，投入运行。作业5 到达时间晚，只能等待。

9 : 10 作业4 运行结束，作业5 因分不到打印机，只能在后备队列继续等待。 9：15 作业2 运行结束，作业5 投入运行。 9 : 30 作业全部执行结束。

某多道程序设计系统采用可变分区内存管理，供用户使用的主存为200K ，磁带机5台。采用静态方式分配外围设备，且不能移动在主存中的作业，忽略用户作业I/O时间。现

执行的次序及作业平均周转时间?

(1) FIFO算法选中作业执行的次序为：A 、B 、D 、C 和E 。作业平均周转时间为63分钟。详细说明：

1．先来先服务算法。说明：

(1) 8 : 30 作业A 到达并投入运行。注意它所占用的资源。 (2) 8 : 50 作业B 到达，资源满足进主存就绪队列等CPU 。

(3) 9 : 00 作业C 到达，主存和磁带机均不够，进后备作业队列等待。

(4) 9 : 05 作业D 到达，磁带机不够，进后备作业队列等待。后备作业队列有C 、D 。 (5) 9 : 10 作业A 运行结束，归还资源磁带，但注意主存不能移动（即不能紧缩）。作业B 投入运行。作业C 仍因主存不够而等在后备队列。这时作业E 也到达了。也由于主存不够进入后备作业队列。此时作业D 因资源满足（主存磁带均满足），进主存就绪队列等待。后备作业队列还有C 、E 。

(6) 9 : 35 作业B 运行结束，作业D 投入运行。这时作业C 因资源满足而调入主存进就绪队列等CPU 。而作业E 因磁带机不够继续在后备作业队列等待。

(7) 9 : 55 作业D 运行结束，作业C 投入运行。这时作业E 因资源满足而调入主存进就绪队列等CPU 。

(8) 10 : 30 作业C 运行结束，作业E 投入运行。 (9) 10 : 40 作业E 运行结束。

(2) SJF算法选中作业执行的次序为：A 、B 、D 、E 和C 。作业平均周转时间为58分钟。说明：

( 1 ) 8 : 30 作业A 到达并投入运行。注意它所占用的资源。 ( 2 ) 8 : 50 作业B 到达，资源满足进主存就绪队列等CPU 。

( 3 ) 9 : 00 作业C 到达，主存和磁带机均不够，进后备作业队列等待。

( 4 ) 9 : 05 作业D 到达，磁带机不够，进后备作业队列等待。后备作业队列有C 、D 。 ( 5 ) 9 : 10 作业A 运行结束，归还资源磁带，但注意主存不能移动（即不能紧缩）。作业B 投入运行。作业C 仍因主存不够而等在后备队列。这时作业E 也到达了，虽然该作业最短，也由于主存不够进入后备作业队列．此时作业D 因资源满足（主存磁带均满足），进主存就绪队列等待。后备作业队列还有C 、E 。

( 6 ) 9:35 作业B 运行结束，作业D 投入运行。这时作业C 和E 资源均满足，但按SJF 应把作业E 调入主存进就绪队列等CPU 。而作业C 因磁带机不够继续在后备作业队列等待。 ( 7 ) 9:55 作业D 运行结束，作业C 调入主存进就绪队列等CPU 。 ( 8 ) 10:05 作业E 运行结束，作业C 投入运行。 ( 9 ) 10:40 作业C 运行结束。