CPU调度算法

操作系统中的CPU调度一、CPU调度的基本概念CPU调度是操作系统的一个非常重要的功能，它控制着CPU 在多任务环境下的运作。

在多任务环境下，CPU必须要对不同的进程进行处理，CPU调度就是指根据一定的算法，在所有可执行的进程中选择一个进程，让它占用CPU，运行一段时间，并在执行完毕后释放CPU，然后选择下一个可执行的进程进行处理，这样就能够合理地利用CPU资源，提高系统的响应速度和吞吐量。

二、CPU调度的基本算法CPU调度的主要任务是在可执行的进程中选择一个进程让其运行，并在一定的时间之后切换到另一个进程进行处理。

但是，在实际中需要考虑的问题是如何选择进程，并且进程切换所带来的开销不能太大。

因此，CPU调度的算法就成了关键。

CPU调度算法主要有以下几种：1. 先来先服务算法（FCFS）FCFS是最早的调度算法，它简单易懂，就是按照进程到达的顺序来排序，先到达的进程先执行，完成后才能运行后面到达的进程。

但是，这种算法存在“饥饿”现象，即如果某个进程运行时间过长，其他进程就无法得到及时的处理。

2. 最短作业优先算法（SJF）SJF算法是根据进程的运行时间来排序的。

处理器会选择那些需要时间最短的进程进行处理。

这种算法速度快，但是会出现“饥饿”现象，即某些进程的运行时间太长，导致其他进程无法得到及时的处理。

3. 时间片轮转算法（RR）RR算法是在时间片为单位对进程进行轮流处理。

每个进程分配一个时间片，当时间片用完时，处理器会停止这个进程的运行，并且把它放到等待队列的末尾，然后从队列的头部选择下一个进程。

这种算法能够避免“饥饿”的现象，但是会带来一定的上下文切换开销。

4. 优先级算法（Priority）Priority算法是根据进程的优先级进行判断的。

进程的优先级越高，就越容易被处理器调度。

但是，这种算法存在的问题就是某些优先级低的进程可能会一直得不到执行。

5. 多级反馈队列算法（MFQ）MFQ算法是一种复杂的算法，它将进程划分为多个队列，分配不同的时间片用于不同的队列。

CPU时间管理思维方法1. 引言在计算机领域，CPU（Central Processing Unit）被认为是计算机系统中最重要的组件之一。

它负责执行所有的指令和处理数据，因此对于优化CPU的使用非常重要。

时间管理是一种思维方法，旨在最大程度地利用CPU的时间，以提高计算机系统的整体性能和效率。

本文将介绍几种CPU时间管理的思维方法，并讨论它们在不同情况下的应用。

2. 抢占式调度方法抢占式调度是一种常见的CPU时间管理方法，主要用于多任务操作系统中。

在抢占式调度中，操作系统可以随时剥夺当前运行的进程的CPU时间，并将其分配给其他就绪的进程。

这种方法可以确保高优先级的任务优先得到执行，并提高系统的响应能力。

抢占式调度方法适用于需要实时响应的系统，如实时操作系统和多媒体应用程序。

通过灵活地分配CPU时间，可以避免某个进程长时间占用CPU，从而保证系统的平稳运行。

3. 时间片轮转调度算法时间片轮转调度算法是一种常见的抢占式调度方法，它将CPU时间分为固定长度的时间片，每个进程在一个时间片内运行一段时间，然后被剥夺CPU时间，给其他进程运行的机会。

被剥夺的进程将排在就绪队列的末尾，等待下一次调度。

时间片轮转调度算法的优点是公平性，所有进程在长时间内都有机会获得CPU时间。

然而，它也存在一些缺点，如进程切换的开销较大，会影响系统的响应时间。

4. 优先级调度算法优先级调度算法是一种非抢占式调度方法，根据进程的优先级来分配CPU时间。

高优先级的进程将优先获得CPU时间，而低优先级的进程则被推迟执行。

这种方法适用于那些对实时性要求不是很高或没有硬实时要求的系统。

优先级调度算法的好处是可以通过调整进程的优先级来灵活地分配CPU时间，以适应不同的情况和需求。

然而，如果不合理地设置优先级，可能会导致低优先级进程被长时间忽视，从而降低系统的公平性和性能。

5. 后台任务调度方法在某些情况下，系统中可能存在一些后台任务，它们不需要实时响应，但对系统的整体性能和效率有一定的影响。

处理机调度算法的比较计算机科学学院计算机科学与技术2009摘要：处理机调度基本概念、调度算法优劣的评价准则、多种处理机调度算法的介绍引言操作系统是处理计算机硬件的一层软件和作为计算机用户与计算机硬件的中间的协调者。

操作系统的CPU调度器负责给各个任务分发CPU带宽资源。

调度算法负责管理当前执行任务等额顺序和性能3 内容：3.1 处理机调度的基本概念高/中/低级调度1. 高级调度（作业调度）决定把外存上处于后备队列中的哪些作业调入内存，并为它们创建进程、分配必要的资源，准备执行。

2. 低级调度（进程调度）决定就绪队列中的哪个进程应获得处理机，然后再由分派程序执行把处理机分配给该进程的具体操作。

非抢占方式和抢占方式3. 中级调度决定把又具备运行条件的挂起进程重新调入内存，挂到就绪队列上，准备执行。

3.2 调度算法优劣的评价准则衡量和比较调度算法性能优劣主要有一下几个因素：（1）CPU利用率。

CPU是计算机系统中最重要的资源，所以应尽可能使CPU保持忙，使这一资源利用率最高。

（2）吞吐量。

CPU运行时表示系统正处于工作状态，工作量的大小是以每单位时间所完成的作业数目来描述的，这就叫吞吐量。

（3）周转时间。

指从作业提交到作业完成所经过的时间，包括作业等待，在就绪队列中排队，在处理机上运行以及进行输入/输出操作所花时间的总和。

（4）等待时间。

处理机调度算法实际上并不影响作业执行或输入/输出操作的时间，只影响作业在就绪队列中等待所花的时间。

因此，衡量一个调度算法优劣常常简单的考察等待时间。

（5）响应时间。

指从作业提交到系统作出相应所经过的时间。

在交互式系统中，作业的周转时间并不一定是最好的衡量准则，因此，常常使用另一种度量准则，即相应时间。

从用户观点看，响应时间应该快一点好，但这常常要牺牲系统资源利用率为代价。

（6）公平性——确保每个用户每个进程获得合理的 CPU 份额或其他资源份额，不会出现饿死情况。

当然，这些目标本身就存在着矛盾之处，操作系统在设计时必须根据其类型的不同进行权衡，以达到较好的效果。

CPU调度CPU调度引⼊了线程，对于⽀持它们的操作系统，是内核级的线程被操作系统调度，⽽不是进程。

不过，术语线程调度或进程调度常常被交替使⽤。

在讨论普通调度概念时使⽤进程调度，特别指定为线程概念时使⽤线程调度。

基本概念CPU-I/O区间周期CPU的成功调度依赖于进程的如下属性：进程执⾏由CPU执⾏和I/O等待周期组成。

进程在这两个状态之间切换。

进程执⾏从CPU区间（CPU burst）开始，在这之后是I/O区间（I/O burst），接着是另⼀个CPU区间，然后是另⼀个I/O区间，如此进⾏下去。

CPU调度程序每当CPU空闲时，操作就必须从就绪队列中选择⼀个进程来执⾏。

进程选择由短期调度程序（short-term scheduler）或CPU调度程序执⾏。

调度程序从内核中选择⼀个能够执⾏的进程，并为之分配CPU。

就绪队列不必是先进先出（FIFO）队列。

就绪队列可实现为FIFO队列，优先队列，树或简单的⽆序链表。

不过从概念上来说，就绪队列内的所有进程都要排队以等待在CPU上运⾏。

队列中的记录通常为进程控制块（PCB）。

抢占调度CPU调度决策可在如下4种环境下发⽣:当⼀个进程从运⾏状态切换到等待状态（例如，I/O请求，或调⽤wait等待⼀个⼦进程的终⽌）。

当⼀个进程从运⾏状态切换到就绪状态（例如，当出现中断时）当⼀个进程从等待状态切换到就绪状态（例如，I/O完成）当⼀个进程终⽌对于第1和第4两种情况，没有选择⽽只有调度。

⼀个新进程（如果就绪队列中已有⼀个进程存在）必须被选择执⾏。

不过，对于第2和第3两种情况，可以进⾏选择。

当调度只能发⽣在第1和第4两种情况下时，称调度⽅案是⾮抢占的(nonpreemptive)的或协作的(cooperative);否则，称调度⽅案是抢占的(preemptive)。

采⽤⾮抢占调度，⼀旦CPU分配给⼀个进程，那么该进程会⼀直使⽤CPU知道进程终⽌或切换到等待状态。

中断能随时发⽣，⽽且不能总是被内核所忽视，所以受中断影响的代码段必须加以保护以避免同时访问。

一、优先级调度算法原理优先级调度算法是一种用于操作系统中的进程调度的算法。

该算法根据每个进程的优先级来决定它在CPU上的执行顺序。

优先级通常是一个整数值，较小的优先级值表示较高的优先级。

当一个进程需要被调度时，系统会选择具有最高优先级的进程来执行。

1.1 优先级调度算法的工作原理在优先级调度算法中，每个进程被分配一个优先级值。

当系统需要选择一个进程来执行时，它会选择具有最高优先级的进程。

如果有多个进程具有相同的最高优先级，那么系统可能会根据其他因素来进行决策，比如先到先服务（FIFO）的原则。

1.2 优先级调度算法的特点优先级调度算法的特点是能够根据进程的优先级来进行调度，从而有效地提高系统的响应速度。

然而，如果进程的优先级分配不合理，可能会导致低优先级的进程长时间得不到执行的机会，造成饥饿现象。

1.3 优先级调度算法的应用场景优先级调度算法通常适用于对实时性要求较高的系统，比如多媒体应用或者交互式应用。

在这些系统中，需要优先处理一些关键的任务，以确保系统的响应速度和稳定性。

二、短进程优先调度算法原理短进程优先调度算法是一种按照进程需要的CPU时间长度进行调度的算法。

该算法先选择需要运行时间最短的进程来执行，从而能够有效地提高系统的吞吐量和响应速度。

2.1 短进程优先调度算法的工作原理在短进程优先调度算法中，系统会根据每个进程需要运行的时间长度来进行调度。

当系统需要选择一个进程来执行时，它会选择需要运行时间最短的进程。

这样可以确保每个进程都能够及时得到执行，并且能够有效地提高系统的吞吐量和响应速度。

2.2 短进程优先调度算法的特点短进程优先调度算法的特点是能够有效地提高系统的吞吐量和响应速度。

由于选择运行时间最短的进程来执行，可以确保每个进程都能够及时得到执行，从而减少了平均等待时间和平均周转时间。

2.3 短进程优先调度算法的应用场景短进程优先调度算法通常适用于需要平衡系统的吞吐量和响应速度的场景，比如多用户系统或者交互式系统。

[整理]操作系统的三⼤调度机制及算法⽬录操作系统的三⼤调度机制，分别是「进程调度/页⾯置换/磁盘调度算法」。

进程调度算法进程调度算法也称 CPU 调度算法，毕竟进程是由 CPU 调度的。

当 CPU 空闲时，操作系统就选择内存中的某个「就绪状态」的进程，并给其分配 CPU。

什么时候会发⽣ CPU 调度呢？通常有以下情况：1. 当进程从运⾏状态转到等待状态；2. 当进程从运⾏状态转到就绪状态；3. 当进程从等待状态转到就绪状态；4. 当进程从运⾏状态转到终⽌状态；其中发⽣在 1 和 4 两种情况下的调度称为「⾮抢占式调度」，2 和 3 两种情况下发⽣的调度称为「抢占式调度」。

⾮抢占式的意思就是，当进程正在运⾏时，它就会⼀直运⾏，直到该进程完成或发⽣某个事件⽽被阻塞时，才会把 CPU 让给其他进程。

⽽抢占式调度，顾名思义就是进程正在运⾏的时，可以被打断，使其把 CPU 让给其他进程。

那抢占的原则⼀般有三种，分别是：时间⽚原则、优先权原则、短作业优先原则。

你可能会好奇为什么第 3 种情况也会发⽣ CPU 调度呢？假设有⼀个进程是处于等待状态的，但是它的优先级⽐较⾼，如果该进程等待的事件发⽣了，它就会转到就绪状态，⼀旦它转到就绪状态，如果我们的调度算法是以优先级来进⾏调度的，那么它就会⽴马抢占正在运⾏的进程，所以这个时候就会发⽣ CPU 调度。

那第 2 种状态通常是时间⽚到的情况，因为时间⽚到了就会发⽣中断，于是就会抢占正在运⾏的进程，从⽽占⽤ CPU。

调度算法影响的是等待时间（进程在就绪队列中等待调度的时间总和），⽽不能影响进程真在使⽤ CPU 的时间和 I/O 时间。

接下来，说说常见的调度算法：1. 先来先服务调度算法2. 最短作业优先调度算法3. ⾼响应⽐优先调度算法4. 时间⽚轮转调度算法5. 最⾼优先级调度算法6. 多级反馈队列调度算法先来先服务调度算法最简单的⼀个调度算法，就是⾮抢占式的先来先服务（First Come First Severd, FCFS）算法了。

一、设计目的通过CPU调度相关算法的实现，了解CPU调度的相关知识，通过实现CPU调度算法，理解CPU的管理，以及不同的CPU调度算法实现过程。

体会算法的重要性。

二、设计要求1、编写算法，实现FCFS、非抢占SJF、可抢占优先权调度2、针对模拟进程，利用CPU调度算法进行调度3、进行算法评估，计算平均周转时间和平均等待时间4、调度所需的进程参数由输入产生（手工输入或者随机数产生）5、输出调度结果6、输出算法评价指标三、设计说明1、采用数组、指针2、FCFS先来先服务调度算法是一种最简单的调度算法，当作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个最先进入该队列的作业3、非抢占SJF短作业优先调度算法，是指对短作业有限调度算法。

是从后备队列中选择一个估计运行时间最短的作业将他们调入内存。

4、可抢占优先权调度在这种方式下，系统把处理机分配给优先权最高的进程，使之执行。

但在其执行期间，只要出现另一个其优先权更高的进程，进程调度程序就立即停止当前进程（原优先权最高的进程）的执行，重新将处理及分配给新到的优先权最高的进程。

四、程序流程图。

1、可抢占优先权调度算法2、FCFS3、非抢占SJF五、程序部分1、FCFS#include<>#include<>typedef struct PCB{char name[10];char state;int arrivetime;int starttime;int finishtime;int servicetime;float turnaroundtime;float weightedturnaroundtime;struct PCB *next;}pcb;int time;pcb *head=NULL,*p,*q;void run_fcfs(pcb *p1){time=p1->arrivetime>timep1->arrivetime:time;p1->starttime=time;printf("\n现在时间是%d,开始运行作业%s\n",time,p1->name);time+=p1->servicetime;p1->state="T";p1->finishtime=time;p1->turnaroundtime=p1->finishtime-p1->arrivetime;p1->weightedturnaroundtime=p1->turnaroundtime/p1->servicetime;printf(" 到达时间开始时间服务时间完成时间周转时间带权周转时间\n ");printf("%6d%10d%10d%8d%%\n",p1->arrivetime,p1->starttime,p1->servicetime,p1->finishtime,p1->turnaroundtime, p1->weightedturnaroundtime);}void fcfs(){int i,j;p=head;for(i=0;i<n;i++){if(p->state=='F'){q=p;run_fcfs(q);}p=p->next;}}void getInfo(){int num;printf("\n作业个数:");scanf("%d",&n);for(num=0;num<n;num++){p=(pcb*)malloc(sizeof(pcb));printf("依次输入:进程名到达时间服务时间\n");scanf("%s%d%d",&p->name,&p->arrivetime,&p->servicetime);if(head==NULL){head=p;q=p;time=p->arrivetime;}if(p->arrivetime<time)time=p->arrivetime;q->next=p;p->starttime=0;p->finishtime=0;p->turnaroundtime=0;p->weightedturnaroundtime=0;p->next=NULL;p->state='F';q=p;}}void main(){ system("graftabl 936");printf("先来先服务算法模拟");getInfo();p=head;fcfs();}2、非抢占SJF#include<>#include<>#define MAX 100struct jcb{char name[10];float arrivetime;float starttime;float finishtime;float servicetime;float zztime;float avezztime;};struct jcb a[MAX];void input(jcb *p,int N){ int i;printf("请分别输入\n\t进程名到达时间服务时间\n\n");for(i=0;i<=N-1;i++){printf("请输入第%d个进程信息:",i+1);scanf("%s%f%f",&p[i].name,&p[i].arrivetime,&p[i].servicetime);printf("\n");}}void Print(jcb *p, float arrivetime,float servicetime,float starttime,float finishtime,float zztime,float avezztime,int N){int k;printf("调度顺序:");printf("%s",p[0].name);for(k=1;k<N;k++){printf("-->%s",p[k].name);}printf("\n\n");printf("\t\t\t进程信息:\n");printf("\nname\tarrive\tservice\tstart\tfinish\tzz\tavezz\n");for(k=0;k<=N-1;k++){printf("%s\t%\t%\t%\t%\t%\t%\t\n",p[k].name,p[k].arrivetime,p[k].servicetime,p [k].starttime,p[k].finishtime,p[k].zztime,p[k].avezztime);}}void sort(jcb *p,int N){int i,j;for(i=0;i<=N-1;i++)for(j=0;j<=i;j++)if(p[i].arrivetime<p[j].arrivetime){jcb temp;temp=p[i];p[i]=p[j];p[j]=temp;}}void deal(jcb *p, float arrivetime,float servicetime,float starttime,float finishtime,float &zztime,float &avezztime,int N){int k;for(k=0;k<=N-1;k++){if(k==0){p[k].starttime=p[k].arrivetime;p[k].finishtime=p[k].arrivetime+p[k].servicetime;}else{p[k].starttime=p[k-1].finishtime;p[k].finishtime=p[k-1].finishtime+p[k].servicetime;}}for(k=0;k<=N-1;k++){p[k].zztime=p[k].finishtime-p[k].arrivetime;p[k].avezztime=p[k].zztime/p[k].servicetime;}}void jcbf(jcb *p,int N){ float arrivetime=0, servicetime=0, starttime=0, finishtime=0, zztime=0, avezztime=0;int m,n,next,k,i=0;float min;sort(p,N);for(m=0;m<N-1;m++){if(m==0)p[m].finishtime=p[m].arrivetime+p[m].servicetime;elsep[m].finishtime=p[m-1].finishtime+p[m].servicetime;for( n=m+1;n<=N-1;n++){if(p[n].arrivetime<=p[m].finishtime)i++;}min=p[m+1].servicetime;next=m+1;for(k=0;k<m+i;k++){if(p[k+1].servicetime<min){min=p[k+1].servicetime;next=k+1;}}{jcb temp;temp=p[m+1];p[m+1]=p[next];p[next]=temp;}deal(p,arrivetime,servicetime,starttime,finishtime,zztime,avezztime,N);Print(p,arrivetime,servicetime,starttime,finishtime,zztime,avezztime,N);}}int main(){int N,*b; char ch;while(1){system("CLS");system("graftabl 936");printf("\t\t\t------短作业优先调度算法------\n");printf("输入进程个数:");scanf("%d",&N);if(N>MAX){printf("\t!!输入的作业数目太大，请输入不大于%d的整数\n",MAX); printf("按Q或者q退出程序,按其他任意键继续测试...");ch=getch();if(ch=='Q'||ch=='q'){break;}else continue;}input(a,N);jcb *b=a;jcbf(b,N);printf("按Q或者q退出程序,按其他任意键继续测试...");ch=getch();if(ch=='Q'||ch=='q'){break;}}return 0;getch();}3、可抢占优先权调度算法#include<>#include<>#include<>#include<>#include<>#include<>typedef char string[10];struct task{string name;int arrTime;int serTime;int waiTime;int begTime;int finTime;int turTime;int wTuTime;int priority;int finish;}JCB[10];int num;void input(){int i;system("cls");printf("\n请输入作业数量:");scanf("%d",&num);for(i=0;i<num;i++){printf("\n请输入作业NO.%d:\n",i);printf("作业名称:");scanf("%s",JCB[i].name);printf("到达时间:");scanf("%d",&JCB[i].arrTime);printf("服务时间:");scanf("%d",&JCB[i].serTime);JCB[i].priority=0;JCB[i].finish=0;}}int HRN(int pre){int current=1,i,j;for(i=0;i<num;i++){JCB[i].waiTime=JCB[pre].finTime-JCB[i].arrTime;JCB[i].priority=(JCB[i].waiTime+JCB[i].serTime)/JCB[i].serTime;}for(i=0;i<num;i++){if(!JCB[i].finish){current=i;break;}}for(j=i;j<num;j++){if(!JCB[j].finish){if(JCB[current].arrTime<=JCB[pre].finTime){if(JCB[j].arrTime<=JCB[pre].finTime&&JCB[j].priority>JCB[current].priority) current=j;}else{if(JCB[j].arrTime<JCB[current].arrTime)current=j;if(JCB[j].arrTime==JCB[current].arrTime)if(JCB[j].priority>JCB[current].priority)current=j;}}}return current;}void runing(int i,int times,int pre,int staTime,int endTime){if(times=0){JCB[i].begTime=JCB[i].arrTime;JCB[i].finTime=JCB[i].begTime+JCB[i].serTime;JCB[i].turTime=JCB[i].serTime;JCB[i].wTuTime=;staTime=JCB[i].begTime;}else{if(JCB[i].arrTime>JCB[pre].finTime)JCB[i].begTime=JCB[i].arrTime;elseJCB[i].begTime=JCB[pre].finTime;JCB[i].finTime=JCB[i].begTime+JCB[i].serTime;JCB[i].turTime=JCB[i].finTime-JCB[i].arrTime;JCB[i].wTuTime=JCB[i].turTime/JCB[i].serTime;}if(times==num-1)endTime=JCB[i].finTime;JCB[i].finish=1;}void print(int i,int times){if(times==0){printf("名称到达时间服务时间开始时间完成时间周转时间带权周转时间\n");}printf("%3s%9d%9d%9d%9d%9d%9d\n",JCB[i].name,JCB[i].arrTime,JCB[i].serTime,JCB[ i].begTime,JCB[i].finTime,JCB[i].turTime,JCB[i].wTuTime);}void check(){int i;int staTime,endTime,sumTurTime=,sumWTuTime=,aveturTime,aveWTuTime;int current=0,times=0,pre=0;JCB[pre].finTime=0;for(i=0;i<num;i++){JCB[i].finish=0;}staTime,endTime,sumTurTime=,sumWTuTime=,aveturTime,aveWTuTime;current=0;times=0;pre=0;printf("-------------------------------------------\n");for(i=0;i<num;i++){JCB[i].finish=0;}staTime,endTime,sumTurTime=,sumWTuTime=,aveturTime,aveWTuTime;current=0;times=0;pre=0;printf("-------HRRN-------------------------------------\n");for(times=0;times<num;times++){current=HRN(pre);runing(current,times,pre,staTime,endTime);print(current,times);pre=current;}for(i=0;i<num;i++){sumTurTime+=JCB[i].turTime;sumWTuTime+=JCB[i].wTuTime;}aveturTime=sumTurTime/num;aveWTuTime=sumWTuTime/num;printf("<计与平均值>%9d%9d%9d%9d\n",NULL,sumTurTime,aveturTime,aveWTuTime);printf("-------------------------------------------------------\n");}void main(){char again;system("graftabl 936");do{system("cls");printf("请输入4组数据:");input();check();printf("Continue...(Y/N)：");do{again=getch();}while(again!='Y'&&again!='y'&&again!='N'&&again!='n');}while(again=='Y'||again=='y');getch();}六、运行结果七、实验总结1、FCFS算法，即先来先服务，就是每次从就绪队列中选择一个最先进入队列的进程，把CPU分配给它，令它运行。