实验2最短剩余时间调度算法

sjf算法例题详解SJF算法例题解析什么是SJF算法•SJF（Shortest Job First）算法是一种非抢占式的调度算法，也被称为最短作业优先算法。

•SJF调度算法根据进程的执行时间来进行调度，先执行执行时间短的任务，以减少平均等待时间。

SJF算法的执行过程1.将进程按照执行时间从小到大进行排序，得到一个等待队列。

2.从等待队列中选择执行时间最短的进程进行执行。

3.若有多个进程的执行时间相同，则根据其到达时间进行选择，选择最先到达的进程执行。

4.执行完当前进程后，更新等待队列，继续选择执行时间最短的进程进行执行，直到所有进程执行完毕。

SJF算法的例题解析•假设有以下五个进程需要执行，进程的执行时间和到达时间如下：进程 | 到达时间 | 执行时间 |—- | | |P1 | 0 | 5 |P2 | 1 | 3 |P3 | 2 | 8 |P4 | 3 | 6 |P5 | 4 | 4 |1.首先，将进程按照到达时间进行排序：进程 | 到达时间 | 执行时间 |—- | | |P1 | 0 | 5 |P2 | 1 | 3 |P3 | 2 | 8 |P4 | 3 | 6 |P5 | 4 | 4 |2.然后，根据执行时间进行排序，若执行时间相同，则根据到达时间进行选择：进程 | 到达时间 | 执行时间 |—- | | |P2 | 1 | 3 |P5 | 4 | 4 |P1 | 0 | 5 |P4 | 3 | 6 |P3 | 2 | 8 |3.根据执行时间选择要执行的进程：进程 | 到达时间 | 执行时间 |—- | | |P2 | 1 | 3 |4.执行完P2进程后，更新等待队列：进程 | 到达时间 | 执行时间 |—- | | |P5 | 4 | 4 |P1 | 0 | 5 |P4 | 3 | 6 |P3 | 2 | 8 |5.继续选择执行时间最短的进程执行，执行完毕后更新等待队列，直到所有进程执行完毕。

最短寻道时间优先调度算法在计算机存储系统中，磁盘调度算法对于提高磁盘 I/O 性能起着至关重要的作用。

其中，最短寻道时间优先（Shortest Seek Time First，SSTF）调度算法是一种常见且具有一定特点的算法。

要理解最短寻道时间优先调度算法，首先得明白磁盘的工作原理。

想象一下磁盘就像一个旋转的唱片，上面划分了很多的扇区，数据就存储在这些扇区里。

而磁头则像唱针一样，需要移动到特定的位置才能读取或写入数据。

磁头在磁盘上的移动需要时间，而且移动的距离越远，花费的时间就越长。

SSTF 算法的核心思想就是每次选择距离当前磁头位置最近的请求进行服务。

打个比方，如果当前磁头在 50 号磁道，而等待队列中有请求访问 40 号磁道、80 号磁道和 60 号磁道的任务，那么算法会先选择访问 60 号磁道的任务，因为它距离当前位置更近。

这种算法的优点是直观且相对简单，能够在一定程度上减少平均寻道时间。

因为它总是优先处理距离当前磁头位置较近的请求，所以在短期内可以提高磁盘的 I/O 效率。

然而，SSTF 算法并非完美无缺。

它可能会导致某些请求长时间得不到服务，从而产生“饥饿”现象。

比如，如果不断有距离当前磁头位置较近的新请求加入，那么那些距离较远的请求就可能一直被搁置。

为了更清楚地说明 SSTF 算法的工作过程，我们来看一个具体的例子。

假设有一系列磁盘访问请求，磁道号依次为 90、180、35、120、10、160、80。

初始时，磁头位于 50 号磁道。

首先，距离 50 号磁道最近的是 80 号磁道，所以磁头移动到 80 号磁道处理请求。

接下来，距离 80 号磁道最近的是 90 号磁道，磁头移动到 90 号磁道。

然后是 10 号磁道、35 号磁道、120 号磁道、160 号磁道、180 号磁道。

通过计算磁头移动的总距离，可以评估 SSTF 算法的性能。

在这个例子中，磁头移动的总距离相对较短，相比于一些其他不太优化的算法，如先来先服务算法，平均寻道时间有所减少。

计算机操作系统实验报告实验二进程调度算法一、实验名称：进程调度算法二、实验内容：编程实现如下算法：1.先来先服务算法；2.短进程优先算法；3.时间片轮转调度算法。

三、问题分析与设计：1.先来先服务调度算法先来先服务调度算法是一种最简单的调度算法，该算法既可以用于作业调度，也可用于进程调度。

当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将他们调入内存，为它们分配资源、创建进程，然后放入就绪队列。

在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。

该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。

FCFS算法比较有利于长作业（进程），2.短作业（进程）优先调度算法短作业（进程）优先调度算法SJ（P）F，是指对短作业或短进程优先调度的算法。

它们可以分别用于作业调度和进程调度。

短作业优先（SJF）的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。

而短进程（SPF）调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机再重新调度。

SJ(P)F调度算法能有效地降低作业（进程）的平均等待时间，提高系统吞吐量。

该算法对长作业不利，完全未考虑作业的紧迫程度。

3.时间片轮转算法在时间片轮转算法中，系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。

当执行的时间片用完时，由一个计数器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。

这样就可以保证就绪队列中的所有进程在一给定的时间内均能获得一时间片的处理机执行时间。

换言之，系统能在给定的时间内响应所有用户的请求。

操作系统教程——进程调度算法院系计算机与软件学院班级08软件工程2班学号20081344066姓名何丽茗进程调度算法的模拟实现⏹实验目的1．本实验模拟在单处理机情况下的处理机调度问题，加深对进程调度的理解。

2．利用程序设计语言编写算法，模拟实现先到先服务算法FCFS、轮转调度算法RR、最短作业优先算法SJF、优先级调度算法PRIOR、最短剩余时间优先算法SRTF。

3．进行算法评价，计算平均等待时间和平均周转时间。

⏹实验内容及结果1．先来先服务算法2．轮转调度算法3. 优先级调度算法4. 最短时间优先算法5. 最短剩余时间优先算法实验总结在此次模拟过程中，将SRTF单独拿了出来用指针表示，而其余均用数组表示。

完整代码【Srtf.cpp代码如下：】//最短剩余时间优先算法的实现#include<stdio.h>#include<stdlib.h>#include<time.h>typedef struct{int remain_time; //进程剩余执行时间int arrive_time; //进程到达时间int Tp; //进入就绪队列的时间int Tc; //进入执行队列的时间int To; //进程执行结束的时间int number; //进程编号}Process_Block; //定义进程模块typedef struct _Queue{Process_Block PB;struct _Queue *next;}_Block,*Process; //定义一个进程模块队列中结点typedef struct{Process head; //队列头指针Process end; //队列尾指针}Process_Queue; //进程队列Process_Queue PQ; //定义一个全局队列变量int t; //全局时间Process Run_Now; //当前正在运行的进程，作为全局变量void InitQueue(Process_Queue PQ){PQ.head ->next = NULL;PQ.end ->next = PQ.head;}/*初始化队列*/int IsEmpty(Process_Queue PQ){if(PQ.end->next == PQ.head)return 1; //队列空的条件为头指针指向尾指针并且尾指针指向头指针return 0;}/*判定队列是否为空队列*/void EnQueue(Process_Queue PQ,Process P){Process temp =(Process)malloc(sizeof(_Block));temp = PQ.end;temp->next->next = P;PQ.end->next = P;}/*插入队列操作*/Process DeQueue(Process_Queue PQ){if(IsEmpty(PQ))return NULL;Process temp = PQ.head->next;PQ.head->next= temp ->next;if(PQ.end->next == temp)PQ.end->next = PQ.head;return temp;}/*出列操作*/Process ShortestProcess(Process_Queue PQ){if(IsEmpty(PQ)) //如果队列为空，返回{if(!Run_Now)return NULL;elsereturn Run_Now;}Process temp,shortest,prev;int min_time;if(Run_Now) //如果当前有进程正在执行，{shortest = Run_Now; //那么最短进程初始化为当前正在执行的进程，min_time = Run_Now->PB.remain_time;}else//如果当前没有进程执行，{shortest = PQ.head->next; //则最短进程初始化为队列中第一个进程min_time = PQ.head->next->PB.remain_time;}temp = PQ.head;prev = temp;while(temp->next)if(temp->next->PB.remain_time <min_time) //如果当前进程的剩余时间比min_time短，{shortest = temp->next; //则保存当前进程，min_time = shortest->PB.remain_time;prev=temp; //及其前驱}temp=temp->next;}if(shortest == PQ.end->next) //如果最短剩余时间进程是队列中最后一个进程，PQ.end->next = prev; //则需要修改尾指针指向其前驱prev->next = shortest->next; //修改指针将最短剩余时间进程插入到队头return shortest;}/*调度最短剩余时间的进程至队头*/void Run(){Run_Now->PB.remain_time--; //某一时间运行它的剩余时间减return;}/*运行函数*/void Wait(){return ;}int sum(int array[],int n){int i,sum=0;for(i=0;i<n;i++)sum+=array[i];return sum;}int main(){PQ.head = (Process)malloc(sizeof(_Block));PQ.end = (Process)malloc(sizeof(_Block));Run_Now = (Process)malloc(sizeof(_Block));Run_Now =NULL;InitQueue(PQ);int i,N,Total_Time=0; //Total_Time为所有进程的执行时间之和printf("请输入计算机中的进程数目:\n");scanf("%d",&N);Process *P,temp;P = (Process*)malloc(N*sizeof(Process));int *wt,*circle_t;wt =(int*)malloc(N*sizeof(int));circle_t =(int*)malloc(N*sizeof(int));for(i=0;i<N;i++){P[i] = (Process)malloc(sizeof(_Block));P[i]->PB.number =i+1;P[i]->next =NULL;wt[i] =0;circle_t[i] =0;printf("输入第%d个进程的到达时间及剩余执行时间:\n",i+1);scanf("%d %d",&P[i]->PB.arrive_time,&P[i]->PB.remain_time);}for(i=0;i<N;i++)Total_Time+=P[i]->PB.remain_time;printf("\n进程按顺序运行依次为:\n");i=0;int k=0;for(t=0;;t++){if(Run_Now) //如果当前有进程正在执行{Run();if(t == P[i]->PB.arrive_time) //如果当前时间正好有进程进入{if(P[i]->PB.remain_time < Run_Now->PB.remain_time){temp = P[i];P[i] = Run_Now;Run_Now = temp; //则调度它至运行队列中，Run_Now->PB.Tp=t;Run_Now->PB.Tc=t;wt[Run_Now->PB.number-1]+=Run_Now->PB.Tc-Run_Now->PB.Tp;printf("%d ",Run_Now->PB.number);}EnQueue(PQ,P[i]); //并将当前运行进程重新插入队列中P[i]->PB.Tp=t;k++;i=(i+1)>(N-1)?(N-1):(i+1);}if(Run_Now->PB.remain_time == 0) //如果当前进程运行结束，{Run_Now->PB.To=t; //进程运行结束的时间circle_t[Run_Now->PB.number-1] +=t-Run_Now->PB.arrive_time;free(Run_Now); //则将它所占资源释放掉，Run_Now =NULL; //并修改Run_Now为NULLRun_Now = ShortestProcess(PQ); //从就绪队列中调出最短剩余时间进程至队头，if(!Run_Now) //如果队列为空，转为等待状态{if(IsEmpty(PQ) && k >= N) break;Wait();continue;}else{Run_Now->PB.Tc=t;wt[Run_Now->PB.number-1]+=Run_Now->PB.Tc-Run_Now->PB.Tp;printf("%d ",Run_Now->PB.number);}}}else//如果当前运行进程为空，那么{if(t == P[i]->PB.arrive_time) //如果正好这时有进程入队{k++;EnQueue(PQ,P[i]);Run_Now = DeQueue(PQ); //则直接被调入运行队列中Run_Now->PB.Tp=t;Run_Now->PB.Tc=t;printf("%d ",Run_Now->PB.number);i=(i+1)>(N-1)?(N-1):(i+1);}else{Wait();continue;}}}printf("\n");printf("平均等待时间是:\n%f\n",((float)sum(wt,N))/N);printf("平均周转时间是:\n%f\n",((float)sum(circle_t,N))/N);return 0;}//////////////////////////////////////////////////////【Process.cpp代码如下：】#include<iostream>#include<string>using namespace std;class Process{public:string ProcessName; // 进程名字int Time; // 进程需要时间int leval; // 进程优先级int LeftTime; // 进程运行一段时间后还需要的时间};void Copy ( Process proc1, Process proc2); // 把proc2赋值给proc1 void Sort( Process pr[], int size) ; // 此排序后按优先级从大到小排列void sort1(Process pr[], int size) ; // 此排序后按需要的cpu时间从小到大排列void Fcfs( Process pr[], int num, int Timepice); // 先来先服务算法void TimeTurn( Process process[], int num, int Timepice); // 时间片轮转算法void Priority( Process process[], int num, int Timepice); // 优先级算法void main(){int a;cout<<endl;cout<<" 选择调度算法："<<endl;cout<<" 1: FCFS 2: 时间片轮换 3: 优先级调度 4: 最短作业优先 5: 最短剩余时间优先"<<endl;cin>>a;const int Size =30;Process process[Size] ;int num;int TimePice;cout<<" 输入进程个数:"<<endl;cin>>num;cout<<" 输入此进程时间片大小: "<<endl;cin>>TimePice;for( int i=0; i< num; i++){string name;int CpuTime;int Leval;cout<<" 输入第"<< i+1<<" 个进程的名字、cpu时间和优先级:"<<endl;cin>>name;cin>> CpuTime>>Leval;process[i].ProcessName =name;process[i].Time =CpuTime;process[i].leval =Leval;cout<<endl;}for ( int k=0;k<num;k++)process[k].LeftTime=process[k].Time ;//对进程剩余时间初始化cout<<" ( 说明: 在本程序所列进程信息中，优先级一项是指进程运行后的优先级!! )";cout<<endl; cout<<endl;cout<<"进程名字"<<"共需占用CPU时间 "<<" 还需要占用时间 "<<" 优先级"<<" 状态"<<endl;if(a==1)Fcfs(process,num,TimePice);else if(a==2)TimeTurn( process, num, TimePice);else if(a==3){Sort( process, num);Priority( process , num, TimePice);}else// 最短作业算法，先按时间从小到大排序，再调用Fcfs算法即可{sort1(process,num);Fcfs(process,num,TimePice);}}void Copy ( Process proc1, Process proc2){proc1.leval =proc2.leval ;proc1.ProcessName =proc2.ProcessName ;proc1.Time =proc2.Time ;}void Sort( Process pr[], int size) //以进程优先级高低排序{// 直接插入排序for( int i=1;i<size;i++){Process temp;temp = pr[i];int j=i;while(j>0 && temp.leval<pr[j-1].leval){pr[j] = pr[j-1];j--;}pr[j] = temp;} // 直接插入排序后进程按优先级从小到大排列for( int d=size-1;d>size/2;d--){Process temp;temp=pr [d];pr [d] = pr [size-d-1];pr [size-d-1]=temp;} // 此排序后按优先级从大到小排列}/* 最短作业优先算法的实现*/void sort1 ( Process pr[], int size) // 以进程时间从低到高排序{// 直接插入排序for( int i=1;i<size;i++){Process temp;temp = pr[i];int j=i;while(j>0 && temp.Time < pr[j-1].Time ){pr[j] = pr[j-1];j--;}pr[j] = temp;}}/* 先来先服务算法的实现*/void Fcfs( Process process[], int num, int Timepice){ // process[] 是输入的进程，num是进程的数目，Timepice是时间片大小while(true){if(num==0){cout<<" 所有进程都已经执行完毕!"<<endl;exit(1);}if(process[0].LeftTime==0){cout<<" 进程"<<process[0].ProcessName<< " 已经执行完毕!"<<endl;for (int i=0;i<num;i++)process[i]=process[i+1];num--;}else if(process[num-1].LeftTime==0){cout<<" 进程"<<process[num-1].ProcessName<< " 已经执行完毕!"<<endl;num--;}else{cout<<endl; //输出正在运行的进程process[0].LeftTime=process[0].LeftTime- Timepice; process[0].leval =process[0].leval-1;cout<<" "<<process[0].ProcessName <<""<<process[0].Time <<" ";cout<<process[0].LeftTime <<""<<process[0].leval<<" 运行";cout<<endl;for(int s=1;s<num;s++){cout<<" "<<process[s].ProcessName <<""<<process[s].Time <<" ";cout<<process[s].LeftTime <<""<<process[s].leval<<" 等待"<<endl; ;}} // elsecout<<endl;system(" pause");cout<<endl;} // while}/* 时间片轮转调度算法实现*/void TimeTurn( Process process[], int num, int Timepice){while(true){if(num==0){cout<<" 所有进程都已经执行完毕!"<<endl;exit(1);}if(process[0].LeftTime==0){cout<<" 进程"<<process[0].ProcessName<< " 已经执行完毕!"<<endl;for (int i=0;i<num;i++)process[i]=process[i+1];num--;}if( process[num-1].LeftTime ==0 ){cout<<" 进程" << process[num-1].ProcessName <<" 已经执行完毕! "<<endl;num--;}else if(process[0].LeftTime > 0){cout<<endl; //输出正在运行的进程process[0].LeftTime=process[0].LeftTime- Timepice;process[0].leval =process[0].leval-1;cout<<" "<<process[0].ProcessName <<""<<process[0].Time <<" ";cout<<process[0].LeftTime <<""<<process[0].leval<<" 运行";cout<<endl;for(int s=1;s<num;s++){cout<<" "<<process[s].ProcessName <<""<<process[s].Time <<" ";cout<<process[s].LeftTime <<""<<process[s].leval;if(s==1)cout<<" 就绪"<<endl;elsecout<<" 等待"<<endl;}Process temp;temp = process[0];for( int j=0;j<num;j++)process[j] = process[j+1];process[num-1] = temp;} // elsecout<<endl;system(" pause");cout<<endl;} // while}/* 优先级调度算法的实现*/void Priority( Process process[], int num, int Timepice){while( true){if(num==0){cout<< "所有进程都已经执行完毕!"<<endl;exit(1);}if(process[0].LeftTime==0){cout<<" 进程" << process[0].ProcessName <<" 已经执行完毕! "<<endl; for( int m=0;m<num;m++)process[m] = process[m+1]; //一个进程执行完毕后从数组中删除num--; // 此时进程数目减少一个}if( num!=1 && process[num-1].LeftTime ==0 ){cout<<" 进程" << process[num-1].ProcessName <<" 已经执行完毕!"<<endl;num--;}if(process[0].LeftTime > 0){cout<<endl; //输出正在运行的进程process[0].LeftTime=process[0].LeftTime- Timepice;process[0].leval =process[0].leval-1;cout<<" "<<process[0].ProcessName <<" "<<process[0].Time <<" ";cout<<process[0].LeftTime <<""<<process[0].leval<<" 运行";cout<<endl; // 输出其他进程for(int s=1;s<num;s++){cout<<" "<<process[s].ProcessName <<" "<<process[s].Time <<" ";cout<<process[s].LeftTime <<""<<process[s].leval ;if(s==1)cout<<" 就绪"<<endl;elsecout<<" 等待 "<<endl;}} // elseSort(process, num);cout<<endl;system(" pause");cout<<endl;} // while}。

0956104 朱文君操作系统上机报告一、实验目的：1.学习处理器各种调度算法的基本思想；2.通过上机实习，编写程序实现处理器的调度加深对各种算法的理解。

二、实验内容：1.实验平台：Microsoft Visual C++ 6.0编程环境、Microsoft Office Word软件平台；2.用C语言编程实现处理器的调度算法：①先来先服务算法②最短作业优先算法③最短剩余时间优先算法；三、实验步骤：（一）先来先服务算法1.说明：先来先服务算法（First Come First Served，FCFS）按照作业进入系统后备作业队列的先后次序来挑选作业，先进入系统的作业将优先被挑选进入主存，创建用户进程，分配所需资源，然后，移入就绪队列。

2.算法实现：#include<stdio.h>void main(){int i,a,T=0,N,add;float sum=0;printf("输入进程数：");scanf("%d",&N);for(i=1;i<=N;i++){printf("\n第%d个进程所需的时间：",i);scanf("%d",&a);T=T+a;sum+=T;printf("\n是否有新的进程进入，输入新的进程数：");scanf("%d",&add);N=N+add;}printf("\n T=%f",sum/N);}3.运行结果演示：(二)最短作业优先算法1.说明：最短作业优先算法（Shortest Job First，SFJ）以进入系统的作业所要求的CPU运行时间的长短为标准，总是选取预计计算时间最短的作业投入运行。

2.算法实现：#include<stdio.h>int De_a(int x,int y,int a[]){int i;if(x==y)a[x]=0;else{for(i=x;i<y;i++){a[i]=a[i+1];}a[i]=0;}return 1;}void main(){int N,M,i,j,k,add,flag,a[1000]={0};float T=0.000,W=0.000,sum=0;printf("输入进程数：");scanf("%d",&N);for(i=1;i<=N;i++){printf("\n第%d个进程所需的时间：",i);scanf("%d",&a[i]);}M=N;for(i=1;i<=N;i++){a[0]=a[1];for(j=1;j<=M;j++){if(a[0]>=a[j]){a[0]=a[j];flag=j;}}T=T+(float)a[flag];sum+=T;W=W+(float)T/a[flag];printf(" %f ",W);De_a(flag,M,a);printf("\n是否有新的进程进入，输入新的进程数：");scanf("%d",&add);for(k=1;k<=add;k++){printf("\n第%d个进程所需的时间：",i);scanf("%d",&a[k+M-1]);}N=N+add;M=M+add-1;}printf("平均作业周转时间T=%f\n",sum/N);printf("平均带权作业周转时间W=%f\n",W/N);}3.运行结果演示：（三）最短剩余时间优先算法1.说明：最短剩余时间优先算法（Shortest Remaining Time First，SRTF）即当前某进程/线程正在运行，如果有新进程/线程移入就绪队列，若它所需要的CPU运行时间比当前运行进程/线程所需要的剩余CPU时间还短，抢占式最短作业优先算法强行剥夺当前执行者的控制权，调度新进程/线程执行。

操作系统中的调度算法分析操作系统是计算机系统中最为重要的组成部分之一，它负责管理计算机系统的资源，包括硬件和软件资源，并且为其它应用程序提供支持和服务。

在操作系统中，调度算法是其中非常重要的一部分，对于它的优化和改进有着非常重要的意义。

本文将按照类别对操作系统中的调度算法进行详细分析，包括批处理系统中的调度算法、交互式系统中的调度算法、实时系统中的调度算法，以及多处理器系统中的调度算法。

一、批处理系统中的调度算法批处理系统是指能够自动地运行一批作业的操作系统，它是在没有任何人的干预下完成作业的自动化系统。

在批处理系统中的调度算法，其主要目的是使各作业的吞吐率最大，并且减少响应时间和等待时间。

在批处理系统中的调度算法包括先来先服务（FCFS）算法、短进程优先（SJF）算法、最高响应比优先（HRRN）算法等。

1、先来先服务（FCFS）算法先来先服务算法，也称为先到先服务算法，是最简单的一种调度算法。

它的作用是按照进程的到达时间的先后顺序进行服务，先到达的进程先得到服务，后到达的进程则必须等待前面进程的服务结束才能够被执行。

优点是公平、简单，缺点是会导致长作业等待时间长，短作业等待时间短。

2、短进程优先（SJF）算法短进程优先算法，是按照进程的执行时间长度来排序，执行时间越短的进程优先得到服务，它可以使得等待时间总和最小，从而提高系统的吞吐率。

但是，如果遇到长作业，则会导致短作业等待时间过长。

3、最高响应比优先（HRRN）算法最高响应比优先算法，则是综合考虑前两种算法的优点而得到的一种调度算法，它会计算出每个进程的响应比，并且选择响应比最高的进程进行执行。

响应比的计算公式是：响应比 = (等待时间 + 执行时间) / 执行时间该算法可以最大限度地减少等待时间，并且适用于长作业与短作业的服务。

二、交互式系统中的调度算法相比于批处理系统，交互式系统强调用户体验，需要快速响应用户的指令请求。

因此，交互式系统中的调度算法，其主要目的是降低响应时间，尽可能快地处理用户的请求。

第4章调度与死锁思考与练习题2．考虑下面的进程集合：（1）（2）分别对以上两个进程集合，计算使用先来先服务（FCFS）、时间片轮转法（时间片q=1）、短进程优先（SPN）、最短剩余时间优先（SRT，时间片q=1）、响应比高者优先（HRRN）及多级反馈队列（MFQ,第1个队列的时间片为1，第i(i<1)个队列的时间片q=2（i-1））算法进行CPU调度，请给出各进程的完成时间、周转时间、带权周转时间，及所有进程的平均周转时间和平均带权周转时间。

解答：（1）平均带权周转时间W=(1+1.4+3.5+1.2+1.6)/5=8.7/5=1.74平均带权周转时间W= (2+2.5+2+1.8+1.6)/5=9.4/5=1.98平均带权周转时间W=(1+1.8+1+1.2+1.6)/5=6.6/5=1.32平均带权周转时间W=(1+1.8+1+1.2+1.6)/5=6.6/5=1.32平均带权周转时间W=(1+1.4+3.5+1.2+1.6)/5=8.7/5=1.74多级反馈队列：第1个队列的时间片为1，第i(i<1)个队列的时间片q=2（i-1））即：平均带权周转时间W= (1.33+2.5+1.8+1.8+1.6)/5=9.03/5=1.806（2）平均带权周转时间W=(1+1+9+1.89)/4=3.22平均带权周转时间W=(1+1.89+1+1.89)/4=1.45平均带权周转时间W=3.22平均带权周转时间W=1.25平均带权周转时间W=3.22平均带权周转时间W=1.4453．考虑系统中出现的情况：（1）计算每个进程还可能需要的资源，并填入表的“仍然需要”栏目中。

（2）系统当前是否处于安全状态？为什么？（3）系统当前是否死锁？为什么？（4）如果进程P3又有新的请求（0，2，0，0），系统是否可以安全地接受此请求？解答：存在安全序列<P1,P4,P5,P2,P3>（3）不会发生死锁，因为存在安全序列，进程按此顺序执行可保证不死锁。

实验报告二——进程调度算法的设计姓名: xxxx 学号: xxxxx班级: xxxx一、实习内容•实现短进程优先调度算法（SPF）•实现时间片轮转调度算法（RR）二、实习目的•通过对进程调度算法的设计, 深入理解进程调度的原理。

进程是程序在一个数据集合上运行的过程, 它是系统进行资源分配和调度的一个独立单位。

进程调度分配处理机, 是控制协调进程对CPU的竞争, 即按一定的调度算法从就绪队列中选中一个进程, 把CPU的使用权交给被选中的进程。

三、实习题目• 1.先来先服务（FCFS）调度算法原理: 每次调度是从就绪队列中, 选择一个最先进入就绪队列的进程, 把处理器分配给该进程, 使之得到执行。

该进程一旦占有了处理器, 它就一直运行下去, 直到该进程完成或因发生事件而阻塞, 才退出处理器。

将用户作业和就绪进程按提交顺序或变为就绪状态的先后排成队列, 并按照先来先服务的方式进行调度处理, 是一种最普遍和最简单的方法。

它优先考虑在系统中等待时间最长的作业, 而不管要求运行时间的长短。

按照就绪进程进入就绪队列的先后次序进行调度, 简单易实现, 利于长进程, CPU繁忙型作业, 不利于短进程, 排队时间相对过长。

• 2.时间片轮转调度算法RR原理: 时间片轮转法主要用于进程调度。

采用此算法的系统, 其程序就绪队列往往按进程到达的时间来排序。

进程调度按一定时间片(q)轮番运行各个进程.进程按到达时间在就绪队列中排队, 调度程序每次把CPU分配给就绪队列首进程使用一个时间片, 运行完一个时间片释放CPU, 排到就绪队列末尾参加下一轮调度, CPU分配给就绪队列的首进程。

固定时间片轮转法:1 所有就绪进程按FCFS 规则排队。

2 处理机总是分配给就绪队列的队首进程。

3 如果运行的进程用完时间片, 则系统就把该进程送回就绪队列的队尾, 重新排队。

4 因等待某事件而阻塞的进程送到阻塞队列。

5 系统把被唤醒的进程送到就绪队列的队尾。