作業調度演算法例題

㈠ 關於作業調度的演算法怎麼寫

網路上搜一下就有了，我做這個就是找的

㈡ 有一個具有兩道作業的批處理系統，作業調度採用短作業優先調度演算法，進程調度採用以優先數為基礎的搶占式

本題中的系統是兩道作業系統，因此每次只能有兩個作業進入系橡逗統，作業調度采

用短作業優先演算法，只有調度進入系統的進程方能參與進程調度；進程調度採用

基於優先數的搶占式調度演算法，高優先順序的進程可以搶占系統處理機。

本題的作業和進程的推進過程如下：

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 運行結束。