下载文档原格式
先来先服务,时间片调度,优先级调度算法实验报告实验报告1. 引言进程调度是操作系统中非常重要的一部分，它决定了进程在CPU上执行的顺序和时间长度。
在本次实验中，我们通过实现先来先服务调度算法、时间片调度算法和优先级调度算法，并对其性能进行比较，来深入了解各种调度算法的工作原理及优缺点。
2. 先来先服务调度算法先来先服务调度算法按照进程到达的先后顺序进行调度。
当一个进程到达时，如果CPU空闲，则将其分配给CPU进行执行；如果CPU 正在执行其他进程，则该进程将等待直到CPU空闲。
优点是简单易实现，适用于长作业。
缺点是可能出现饥饿现象，即低优先级的进程可能会一直等待高优先级进程的执行。
3. 时间片调度算法时间片调度算法将CPU的执行时间划分为固定长度的时间片，每个进程在一个时间片内执行，当时间片用完后，系统将切换到下一个进程执行。
该算法确保每个进程都有公平的执行时间，避免了饥饿现象。
然而，对于CPU利用率较高的情况下，可能会导致进程频繁地切换，增加了上下文切换的开销。
4. 优先级调度算法优先级调度算法根据进程的优先级来进行调度，优先级较高的进程将具有更高的执行优先级。
当多个进程同时到达CPU时，系统将选择优先级最高的进程先执行。
该算法可以分为静态优先级调度和动态优先级调度两种方式。
优点是可以根据进程的重要性灵活调整执行顺序。
缺点是可能导致优先级低的进程长时间等待，造成饥饿现象。
5. 实验结果与分析我们通过模拟多个进程的到达和执行过程，在不同的场景下比较了先来先服务调度算法、时间片调度算法和优先级调度算法的性能。
实验结果显示，在长作业的情况下，先来先服务调度算法表现较好；在要求公平性的场景下，时间片调度算法比较适合；而对于需要根据优先级来调度的场景，优先级调度算法可以更好地满足需求。
6. 结论不同的进程调度算法在不同的场景下有各自的优劣。
先来先服务调度算法简单易实现，适用于长作业；时间片调度算法保证了公平性，适用于要求公平的场景；而优先级调度算法则可以根据进程的重要性进行调度。
最⾼优先级算法——进程调度原创最近⼏周操作系统实习，要求完成⼏道题⽬，下⾯是⾃⼰敲出来的模拟在单处理器情况下的进程调度算法（说算法可能过于⾼⼤尚），采⽤的是短作业优先调度算法、时间⽚轮转调度、最⾼优先级优先算法三种算法中的最⾼优先级算法。
题⽬阐述如下： 设计⼀：进程调度设计⽬的：进程管理是操作系统中的重要功能，⽤来创建进程、撤消进程、实现进程状态转换，它提供了在可运⾏的进程之间复⽤CPU的⽅法。
在进程管理中，进程调度是核⼼，因为在采⽤多道程序设计的系统中，往往有若⼲个进程同时处于就绪状态，当就绪进程个数⼤于处理器数⽬时，就必须依照某种策略决定哪些进程优先占⽤处理器。
本设计模拟在单处理器情况下的进程调度，⽬的是加深对进程调度⼯作的理解，掌握不同调度算法的优缺点。
设计内容：设计程序模拟单处理机系统中的进程调度算法，在短作业优先调度算法、时间⽚轮转调度、最⾼优先级优先算法三种算法中选择两种实现。
每个进程由⼀个进程控制块（PCB）表⽰。
进程控制块可以包含如下信息：进程名、优先数、到达时间、需要运⾏时间、已⽤CPU时间、进程状态等。
进程的优先数及需要的运⾏时间可以事先⼈为地指定（也可以由随机数产⽣）。
进程的到达时间为进程输⼊的时间。
进程的运⾏时间以时间⽚为单位进⾏计算。
每个进程的状态可以是就绪W（Wait）、运⾏R(Run)或完成F(Finish)3中状态之⼀。
以下是最⾼优先级优先算法思想：就绪进程获得CPU后都只能运⾏⼀个时间⽚，⽤已占⽤CPU时间加1来表⽰。
如果运⾏⼀个时间⽚后，进程的已占⽤CPU时间已达到所需要的运⾏时间，则撤销该进程，如果运⾏⼀个时间⽚后进程的已占⽤CPU时间还未达到所需要的运⾏时间，也即进程还需要继续运⾏，此时应将进程的优先数减1（即降低⼀级），然后把它插⼊就绪队列等待CPU。
每进⾏⼀次调度程序都打印⼀次运⾏进程、就绪队列以及各个进程的PCB，以便进⾏检查。
重复以上过程，直到所有进程都完成为⽌。
设计一个按优先数调度算法实现处理器调度的进程
一．处理器调度的简介
处理器调度是指在若干作业并发处理时，对处理器分配工作的动态过程。
它是操作系统中的一种重要技术，其主要功能是控制并发作业的执行，使他们得到公平的分配，正确的完成执行，以达到有效利用处理机资源，
提高系统的工作效率。
处理器调度技术包括：处理机调度算法、处理机调
度技术等。
处理机调度算法就是基于计算机系统的工作机制，根据不同的作业在
处理机上的执行情况，系统在不同的阶段，根据量的不同，采用不同的算法，按优先级、分时等原则进行处理机调度，使作业在不同的阶段得到公
平的分配，以达到有效利用处理机资源，提高系统工作效率的目的。
按优先数调度算法( Priority Scheduling Algorithm )是指根据作
业的优先级先后来分配处理机资源，使作业能够按照优先级依次被处理，
使得系统性能有所提高。
1．处理器调度的算法流程
按优先数调度算法的处理器调度的过程，如下：
首先，从队列中取出一个作业，检查是否具有最高优先级，如果是，
则将其分配给处理机，否则，该作业放回队列，继续下一步判断；
其次，在没有作业可以处理时，处理机将停止运转。
操作系统中的进程调度算法研究与优化操作系统是计算机软件的核心，负责管理和控制计算机硬件资源，提供良好的运行环境和服务。
而进程调度算法则是操作系统的重要组成部分，它决定了操作系统如何合理地分配CPU资源，使得多个进程能够高效地并发运行。
本文将探讨进程调度算法的研究与优化问题。
一、进程调度算法的基本原理在了解进程调度算法之前，我们首先需要了解什么是进程。
简单来说，进程是计算机中正在执行的一个程序，它是分配给各个任务和用户的资源的单位。
进程的调度就是指操作系统将CPU的使用权从一个进程转移到另一个进程的过程。
目前常见的进程调度算法主要有以下几种：先来先服务（FCFS）、短作业优先（SJF）、时间片轮转（RR）和优先级调度等。
不同的调度算法具有不同的特点和适用场景。
二、进程调度算法的研究与实践1. 先来先服务（FCFS）调度算法FCFS调度算法是最简单的一种调度算法，它按照进程到达的顺序进行调度，即先到先服务。
简单、直观的调度方式使得FCFS调度算法易于实现和理解。
然而，这种算法存在一个严重的问题，即“饥饿”现象。
如果长时间运行的进程抢占了CPU资源，那么其他进程就会一直等待，无法得到执行机会。
为了解决FCFS调度算法的问题，短作业优先（SJF）调度算法被提出。
2. 短作业优先（SJF）调度算法SJF调度算法通过预测进程执行时间，将最短执行时间的进程优先调度。
这种算法可以最大程度地减少平均等待时间和响应时间。
然而，由于无法准确预测进程的执行时间，SJF调度算法在实际运用中面临着很大的挑战。
为了解决SJF调度算法的问题，引入了时间片轮转（RR）调度算法。
3. 时间片轮转（RR）调度算法RR调度算法将CPU的使用权按照时间片进行轮转，每个进程都能在一个时间片内得到执行。
时间片的大小通常根据进程的特点和需求来设定。
RR调度算法公平地分配CPU资源，提高了系统的吞吐量。
然而，如果时间片过长，会导致长时间等待的进程响应较慢；如果时间片过短，会导致调度开销过大，降低系统性能。
1.实验名称：动态优先权调度过程中就绪队列的模拟2.实验要求：采用动态优先权的进程调度算法，用C语言编程模拟调度过程中每个时间片内的就绪队列。
3.实验内容：（1）每个进程控制块PCB用结构描述，包括以下字段：*进程标识符id*进程优先数priority,并规定优先数越大的进程，其优先权越高。
*进程已占用的CPU时间cputime*进程还需占用的CPU时间alltime，当进程运行完毕时，aiitime变为0*进程的阻塞时间startblock,当进程再运行startblock个时间片后，进程将进入阻塞状态*进程被阻塞的时间blocktime,已阻塞的进程再等待blocktime个时间片后，将转换成就绪状态*进程状态state*队列指针next,将PCB排成队列。
2）调度前，系统中有五个进程，它们的初始状态如下：3）进程在就绪队列呆一个时间片,优先数增加1。
4）进程每运行一个时间片，优先数减3。
5）按下面格式显示每个时间片内就绪队列的情况：READY_QUEUE:->id1->id24.任务分析进程控制块用结构体来表示，包含它的各项属性。
建立两个队列：一个就绪队列，一个阻塞队列。
创建一个进程控制块表示当前正在运行的进程。
程序开始运行时，所有进程都在就绪队列中。
当startblock减少到0时，进程进入阻塞队列。
在阻塞队列中的进程，当blocktime减少到0时，转入就绪队列。
在就绪队列中的进程，如果优先级比当前正在执行的进程高，就可以取代当前进程获取时间片。
当前进程如果运行完毕，就绪队列中优先级最高的进程就可以成为新当前进程。
5.程序流程图#include〈iostream〉#include〈string〉usingnamespace std;#define LEN5typedefenum STATE{READYBLOCKEND}STATE;//定义进程控制块typedefstruct PCB{int id;int priority;int cputime;int alltime;int startblock;int blocktime;STATE state;}PCB;//定义队列typedefstruct queue{int si ze;PCB*data[LEN];}Queue;PCB ps[LEN];PCB*cp; //进程最大数量//进程状态//就绪//阻塞//完成//进程标识符//进程优先级//已占用的CPU时间//还需占用的CPu时间//阻塞时间//被阻塞时间//进程状态//队列中进程的数量//进程的指针//进程数组//当前正在运行的进程6.程序清单Queue rQueue,bQueue;//就绪队列和阻塞队列//就绪队列按优先级降序排序(使用了冒泡排序法)void rQueueSort(){ PCB*temp;for(int i=0;i<rQueue.size-1;i++){for(int j=0;j<rQueue.size-1-i;j++){if(rQueue.data[j]-〉priority<rQueue.data[j+1]-〉priority){temp=rQueue.data[j];rQueue.data[j]=rQueue.data[j+1];}}rQueue.dataj+1]=temp;}}//初始化void init(){//给进程赋值for(int i=0;i<LEN;i++){ps[i].id=i;ps[i].state=READY;ps[i].cputime=0;ps[i].alltime=3;ps[i].blocktime=0;ps[i].startblock=T;}ps[0].priority=9;ps[1].priority=38;ps[2].priority=30;ps[3].priority=29;ps[4].priority=0;ps[2].alltime=6;ps[4].alltime=4;ps[0].startblock=2;ps[0].blocktime=3;cp=NULL;//当前进程赋空bQueue.size=0;//阻塞队列没有进程for(int i=0;i<LEN;i++){bQueue.data[i]=NULL;rQueue.data[i]=&ps[i];}rQueue.size=5;//所有进程全部进入就绪队列rQueueSort();//对就绪队列排序}//打印void print(){cout〈〈"\nRUNNINGPROG:";if(cp!=NULL){cout〈〈cp->id;}cout<<"\nREADY_QUEUE:";for(int i=0;i<rQueue.size;i++){cout〈〈"-〉"〈〈rQueue.data[i]-〉id; }cout<<"\nBLOCK_QUEUE:";for(int i=0;i<bQueue.size;i++){cout〈〈"-〉"〈〈bQueue.data[i]-〉id; }cout〈〈"\n"<<endl;cout<<"ID\t\t";for(int i=0;i<LEN;i++){cout〈〈ps[i].id<<"\t";}cout<<"\nPRI0RITY\t";for(int i=0;i<LEN;i++){cout〈〈ps[i].priority〈〈"\t";}cout<<"\nCPUTIME\t\t";for(int i=0;i<LEN;i++){cout〈〈ps[i].cputime〈〈"\t";}cout<<"\nALLTIME\t\t";for(int i=0;i<LEN;i++){cout〈〈ps[i].alltime〈〈"\t";}cout<<"\nSTARTBLOCK\t";for(int i=0;i<LEN;i++){cout〈〈ps[i].startblock<<"\t";}cout<<"\nBLOCKTIME\t";for(int i=0;i<LEN;i++){cout〈〈ps[i].blocktime<<"\t";}cout<<"\nSTATE\t\t";for(int i=0;i<LEN;i++){if(ps[i].state==READY){cout<<"READY"<<"\t";}elseif(ps[i].state==BLOCK){cout<<"BLOCK"<<"\t";}elseif(ps[i].state==END){cout〈〈"END"<<"\t";}}cout〈〈endl;}//出队，返回进程指针PCB*pop(Queue*q){PCB*temp;if(q-〉size>0){temp=q-〉data[0];//取出队首进程for(int i=0;i<q-〉size-1;i++){q-〉data[i]=q-〉data[i+1];//其他进程依次向前移动}q->size__;return temp;//返回队首进程}return NULL;}//入队void push(Queue*q,PCB*p){if(q_>size<LEN){q_>data[q_〉size]=p;//将入队的进程放在队尾q_>size++;}return;}//运行进程void run(){if(rQueue.size〉0||bQueue.size〉0){if(cp==NULL){//程序一开始运行时，从就绪队列取出首进程cp=pop(&rQueue);}//当前进程没有结束，但优先级比就绪队列首进程低if(cp_〉alltime〉0&&cp_>priority<rQueue.data[0]_〉priority){}push(&r Queue,c//改变进程状态//从就绪队列取出新的当前进程//修改当前进程的状态 //将当前进程加入阻塞队列 //从就绪队列取出新的当前进程{//当前进程的startblock 为正数时//运行一次减一个时间片//减到0时，修改进程状态//每运行一个时间片//就绪队列中的进程优先级+1//每运行一个时间片//阻塞队列中的进程blocktime-1//将当前进程放入就绪队列 //就绪队列队首进程成为当前进程if (cp-〉alltime==0){cp->state =END ;cp=pop(&rQueue); }//如果当前进程运行结束//startblock 为0,标志着当前进程要进入阻塞状态if (cp —>startblock==0&&cp —>blocktime>0){cp —>state=BLOCK ; push(&bQueue,cp); cp=pop(&rQueue); }elseif (cp —>startblock>0)cp —>st artblock 一; }cp —>alltime ——;if (cp —>alltime==0){cp —>state=END ;for (int i=0;i<rQueue.size;i++){rQueue.data[i]-〉priority++; }for (int i=0;i<bQueue.size;i++){if (bQueue.data[i]-〉blocktime>0){bQueue.data[i]-〉blocktime--; }//当阻塞队列队首进程blocktime 为0时if (bQueue.size 〉0&&bQueue.data[0]-〉blocktime==0){bQueue.data[0]-〉state=READY ;//修改进程状态push(&rQueue,pop(&bQueue));//将阻塞队列首进程取出，放入就绪队列cp —〉priority-=3;//修改当前进程的优先级cp —>cputime++; //当前进程占用CPU 时间片+1 if (cp —>alltime>0){//当前进程还需运行的时间片-1}//每运行一个时间片，就绪队列排一次序rQueueSort();} }//主函数int main(){init();//初始化 print();//打印进程信息 while (1){_sleep(1000);if (rQueue.size==0&&bQueue.size==0){//当两个队列都为空时，结束程序cp-〉state=END ;break ; }run();//运行进程 print();//打印进程信息 }return 0; }7.实验过程记录m 匚:\WINDQWS\system32\cmd.exe程序开始执行，当前进程是优先级最高的1号进程，1号进程的优先级减3、cputime++、执行几次之后，1号进程执行完毕而且优先级也不是最高的了，所以优先级为33的2号进程成为当前进程，开始执行。
先来先服务,时间片调度,优先级调度算法实验报告先来先服务、时间片调度、优先级调度算法实验报告1. 引言本次实验旨在研究和比较先来先服务（FCFS）、时间片调度（RR）和优先级调度（Priority Scheduling）三种常见的进程调度算法。
进程调度是操作系统中的重要概念之一，合理的进程调度算法可以提高系统效率，优化资源利用。
2. 先来先服务算法•先来先服务算法是一种简单的调度算法，按照进程到达的顺序进行调度。
•优点：简单易实现，适用于长作业。
•缺点：容易造成短作业等待时间过长，无法满足实时性要求。
3. 时间片调度算法•时间片调度算法将CPU时间划分为一段一段的时间片，每个进程在一个时间片内执行。
•若进程未完成，会被放入就绪队列的末尾，等待下一个时间片。
•优点：公平，适用于短作业，能满足实时性要求。
•缺点：时间片过长，会导致长作业等待时间过长。
4. 优先级调度算法•优先级调度算法根据进程的优先级来确定调度顺序，拥有最高优先级的进程先执行。
•静态优先级可在创建进程时确定，动态优先级可根据进程执行情况进行调整。
•优点：适用于实时任务和长作业，可根据需求调整优先级。
•缺点：可能导致低优先级任务等待时间过长，存在优先级反转问题。
5. 实验结果与分析通过对三种调度算法的实验测试，得出以下结论：•FCFS算法在长作业的情况下表现较好，但对于短作业不友好，容易造成长时间等待；•RR算法适用于短作业，能保证公平性，但时间片过长可能导致长作业等待时间过长；•优先级调度算法较为灵活，能满足实时性要求，但可能导致低优先级任务长时间等待。
综上所述，不同的调度算法适用于不同的场景，根据需求选择合适的算法可提高系统效率。
6. 总结本次实验对先来先服务、时间片调度和优先级调度算法进行了研究和比较。
通过对三种算法的分析，我们可以根据任务特点和需求选择合适的调度算法，以提高系统的效率和资源利用率。
同时，在实际应用中也需要考虑进程的实时性要求，避免长时间等待等问题的出现。
作业调度算法【摘要】在多道系统中，对批处理作业需要进行作业调度。
作业调度是在资源满足的条件下，将处于后储备状态的作业调入内存，同时生成与作业相对应的进程，并为这些进程提供所需要的资源。
作业调度程序只能保证被调度的作业有获得处理器的资格，而处理器的分配则需要进程调度才能完成。
作业调度需要根据作业控制块中的信息，检查系统是否满足作业的资源需求。
只有在满足作业的资源需求的情况下，系统才能进行作业调度。
下面是几种常见的作业调度算法：先来先服务、轮换法、多级反馈队列算法、优先算法、短作业优先法以及最高响应比优先法。
本文将对这几种算法进行详细的介绍。
【关键词】先来先服务；轮换法；多级反馈队列算法；优先算法；短作业优先法；最高响应比优先法1.先来先服务1.1定义先来先服务（fcfs, first come first serve）是最简单的调度算法，按先后顺序进行调度。
按照作业提交或进程变为就绪状态的先后次序，分派cpu；当前作业或进程占用cpu，直到执行完或阻塞，才出让cpu（非抢占方式）。
在作业或进程唤醒后（如i/o 完成），并不立即恢复执行，通常等到当前作业或进程出让cpu。
1.2适用场景比较有利于长作业，而不利于短作业。
有利于cpu繁忙的作业，而不利于i/o繁忙的作业。
2.轮转法2.1定义轮转法(round robin)是让每个进程在就绪队列中的等待时间与享受服务的时间成正比例。
将系统中所有的就绪进程按照fcfs原则，排成一个队列。
每次调度时将cpu分派给队首进程，让其执行一个时间片。
时间片的长度从几个ms到几百ms。
在一个时间片结束时，发生时钟中断。
调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程。
进程可以未使用完一个时间片，就出让cpu（如阻塞）。
2.2时间片长度的确定时间片长度变化的影响：过长会导致退化为fcfs算法，进程在一个时间片内都执行完，响应时间长。
进程调度模拟设计——先来先服务最高响应比优先调度算法进程调度是操作系统中非常重要的一部分，它负责根据一定的调度算法从就绪态的进程队列中选择下一个运行的进程。
在这篇文章中，我将介绍两种常见的进程调度算法：先来先服务调度（FCFS）和最高响应比优先调度（HRRN）。
1.先来先服务调度（FCFS）：先来先服务调度算法是一种非抢占式调度算法，按照进程到达的顺序依次进行调度。
即当一个进程到达后，它将被插入到就绪队列的末尾。
当前运行的进程执行完毕后，将选择队列中的第一个进程来执行。
先来先服务调度算法的优点是简单、公平，不会发生饥饿现象。
然而，它有一个显著的缺点，即无法考虑进程的执行时间和优先级。
如果一个长时间运行的进程到达了队列，所有其他进程都要等待它完成，这可能导致其他进程的等待时间较长。
2.最高响应比优先调度（HRRN）：最高响应比优先调度算法是一种动态优先级调度算法，它考虑了进程的等待时间和执行时间。
响应比定义为(等待时间+服务时间)/服务时间。
当一个进程等待的时间越长，它的响应比越高，优先级越高。
最高响应比优先调度算法会选择具有最高响应比的进程来执行。
如果两个进程的响应比相同，则按照先来先服务的原则进行选择。
当一个进程到达后，它将被插入到就绪队列中，并根据响应比进行排序。
最高响应比优先调度算法的优点是可以避免长时间运行的进程造成其他进程的饥饿现象，提高了系统的响应性。
然而，它的实现相对复杂，需要计算每个进程的响应比。
下面是两种调度算法的模拟设计：先来先服务调度模拟设计：1.定义一个就绪队列，用来保存到达的进程。
2.当一个新的进程到达时，将其加入到就绪队列的末尾。
3.当前运行的进程执行完毕后，从就绪队列中选择队列的第一个进程来执行。
4.执行进程，更新进程的状态和执行时间，直到所有进程执行完毕。
最高响应比优先调度模拟设计：1.定义一个就绪队列，用来保存到达的进程。
2.当一个新的进程到达时，将其加入到就绪队列中，并计算每个进程的响应比。
进程调度模拟设计——先来先服务优先级法首先，我们来介绍先来先服务调度算法。
FCFS调度算法的原则是按照进程到达的先后顺序进行调度，即先到先执行。
具体步骤如下：1.首先，将所有等待执行的进程按照到达的时间进行排序，即按照先后顺序排列进程队列。
2.选择队列中的第一个进程执行，其余的进程处于等待状态。
3.当当前进程执行完毕或者发生阻塞时，调度器从进程队列中选择下一个进程执行。
4.重复以上步骤，直到所有进程执行完毕。
虽然FCFS调度算法的实现简单，但是存在一个明显的问题，即“饥饿问题”，即如果队列中存在一个长时间执行的进程，其他进程会一直等待，无法得到执行机会。
为了解决饥饿问题，我们引入优先级法调度算法。
优先级法调度算法基于每个进程的优先级来决定调度顺序，具体步骤如下：1.对每个进程设置一个优先级，取值范围从1到n，数值越高表示优先级越高。
2.调度器根据进程的优先级将进程排序，高优先级的进程排在前面。
3.选择优先级最高的进程执行，其余进程处于等待状态。
4.当当前进程执行完毕或者发生阻塞时，调度器从进程队列中选择下一个优先级最高的进程执行。
5.重复以上步骤，直到所有进程执行完毕。
优先级法调度算法解决了饥饿问题，使得所有进程都有机会执行。
然而，优先级法调度算法可能存在一个问题，即“优先级反转问题”。
如果一个低优先级的进程持有一个高优先级的资源，那么其他高优先级的进程就会一直等待，无法得到高优先级资源的使用权。
为了解决优先级反转问题，可以引入优先级继承机制或者抢占式调度策略。
总结起来，先来先服务调度算法按照进程到达的先后顺序进行调度，实现简单但容易导致饥饿问题；优先级法调度算法根据进程的优先级进行调度，避免了饥饿问题但可能导致优先级反转问题。
需要根据不同的应用场景和需求来选择合适的调度算法。
采用短进程优先算法模拟实现进程调度短进程优先(SJF)是一种基于优先级的调度算法，其中短的进程优先
被调度。
在这种算法中，短暂的进程拥有优先级，因此优先调度。
SJF的工作原理是：在进程结束之前，它会检查新到达的进程，把它
们按照任务的执行时间排序，并把时间最短的进程调度到CPU中去执行。
这种算法的目的是让整个调度过程更有效率，减少CPU的空闲时间，由于
短进程可以被快速地完成，CPU在等待长进程完成的时间就可以更有效地
被利用。
短进程优先算法可以使用多种方法来实现，最常用的是基于优先级的
算法，即让较短的进程具有较高的优先级，让长进程具有较低的优先级。
在这种方法中，到达进程被排序，然后CPU根据优先级调度拥有最高优先
级的进程。
有的时候短进程优先算法也可以使用时间片轮转(Round Robin)的方法，即把每个进程分配一个时间片，时间片的大小取决于任务的执行时间。
在这种方法中，每个时间片之间调度一个进程，直到每个进程的时间片都
被使用完，然后重新调度下一个时间片。
SJF调度算法的优点是可以有效地减少CPU的空闲时间，可以提高整
个系统的性能，而且它可以运行时间较短的程序。
题目操作系统课程设计实验一：进程调度算法1.实验目的通过优先权法和轮转算法的模拟加深对进程概念和进程调度过程的理解，掌握进程状态之间的切换，同时掌握进程调度算法的实现方法和技巧。
2.实验内容1）用C语言或C++语言来实现对n个进程采用优先权算法以及轮转算法的进程调度。
2）每个用来标识进程的进程控制块PCB用结构来描述，包括以下字段：（1）进程标识ID，其中0为闲逛进程，用户进程标识数为1，2，3…。
（2）进程优先级Priority，闲逛进程（idle）的优先级为0，用户进程的优先级大于0，且随机产生，标识数越大，优先级越高。
（3）进程占用CPU时间CPUtime，进程每运行一次，累计值等于4.（4）进程总共需要运行时间Alltime，利用随机函数产生。
（5）进程状态，0-就绪态；1-运行态；2-阻塞态。
（6）队列指针next，用来将多个进程控制块PCB链接为队列。
3）优先数改变的原则（1）进程在就绪队列中每呆一个时间片，优先数增加1。
（2）进程每运行一个时间片，优先数减3.4）在调度前，系统中拥有的进程数PCB_number由键盘输入，经初始化后，所有的进程控制块PCB链接成就绪队列。
3.实验步骤a)画出程序流程图a)动态优先权的进程调度算法模拟流程b)轮转法进程调度算法模拟流程b)程序算法如下：#include "stdafx.h"#define NULL 0#include <stdio.h>#include <stdlib.h>#include <iostream>using namespace std;/*进程PCB结构*/struct PCB{int ID; //进程标识int priority; //优先级int CPUtime; // 进程占用CPU的时间int ALLtime; // 进程总共需要运行的时间int State; // 进程状态struct PCB *next; // 指向下一节点的指针};typedef struct PCB pcb;void init(); //产生idle进程，输入用户进程数目，//调用insert（）void print(PCB *pcb); //输出进程属性信息void print_init(PCB *pcb);void insert(); //生成进程属性信息,插入进程就绪队列void run_priority(PCB *pcb); //运行进程,随机阻塞进程,产生新进程,插入就绪队列,唤醒阻塞进程void run_loop(PCB *pcb); //运行进程,随机阻塞进程,产生新进程,插入就绪队列,唤醒阻塞进程void block(PCB *pcb); //调用destroy(),将进程插入阻塞队列void wakeup_priority(); //唤醒进程,插入就绪队列void wakeup_loop(); //唤醒进程,插入就绪队列void proc_priority(); //优先权调度算法模拟void proc_loop(); //轮转法调度算法模拟void update(PCB *pcb);//更新进程信息PCB *ready_queue,*block_queue,*idleprocess; //就绪队列,阻塞队列及闲逛进程指针变量int main(int argc, char* argv[]){int i=0;while(1){cout<<("\n Please select a number (1,2,0)");cout<<("\n 1--priority");cout<<("\n 2--loop");cout<<("\n 0--exit\n");cin>>i;if(i==1){cout<<("\nThis is an example for priority processing:\n");init();::proc_priority();}else if(i==2){cout<<("\nThis is an example for round robin processing:\n");init();proc_loop();}else if(i==0)exit(1);}return 0;}//输出所有PCB的初始值,此函数用于测试程序void print_init(PCB *pcb){PCB *temp=pcb->next ;cout<<("\n ID priority CPUtime ALLtimeState\n");while(temp!=NULL){cout<<"\n"<<" "<<temp->ID<<" "<<temp->priority <<""<<temp->CPUtime <<" "<<temp->ALLtime;if(temp->State ==0)cout<<(" ready");else if(temp->State ==1)cout<<(" running");elsecout<<(" blocked");temp=temp->next ;}}//输出进程属性信息void print(PCB *pcb){PCB *temp;temp=pcb;if(pcb->ID ==0)cout<<("\n\t The idle process is running!");else{cout<<"\n"<<" "<<temp->ID<<" "<<temp->priority <<" "<<temp->CPUtime <<" "<<temp->ALLtime;if(temp->State ==0)cout<<(" ready");else if(temp->State ==1)cout<<(" running");elsecout<<(" blocked");}}void insert_queue(PCB *queue,PCB *item){//将item插入到队列中,使得插入后队列中按照优先级从高到低有序PCB *p,*q;q=queue;p=q->next ;while(p!=0 && p->priority >= item->priority ){q=p;p=p->next ;}if(p==0){//在队尾插入item->next =0;q->next =item;}else{//在q之后,p之前插入item->next =p;q->next =item;}}void pushback_queue(PCB *queue,PCB *item){//将item插入到队列尾部PCB *p,*q;q=queue;p=q->next ;while(p!=0){q=p;p=p->next ;}item->next =q->next ;q->next =item;}//对queue中的节点进行排序,按照优先级从大到小void sort_queue(PCB *&queue){PCB *temp=new PCB;temp->next =0;while(queue->next ){PCB *p;p=queue->next ;queue->next =p->next ;::insert_queue (temp,p);}queue->next =temp->next;delete temp;}//生成进程属性信息,插入进程就绪队列,显示进程信息void insert(){PCB *newp=0;static long id=0;newp=new PCB;id++;newp->ID =id;newp->State =0;newp->CPUtime =0;newp->priority =rand()%3+1;newp->ALLtime =rand()%3+1;newp->next =NULL;::pushback_queue (ready_queue,newp);//将新生成进程插入到就绪队列尾部print(newp);cout<<("\t建立： Creating-> ready\n");}//生成进程属性信息,插入进程就绪队列,显示进程信息void insert(int n){for(int i=1;i<n;i++){insert();}}//产生idle进程,输入用户进程数目,调用insert()void init(){//为每个队列设立头结点,便于插入删除操作block_queue=new PCB;block_queue->next =0;ready_queue=new PCB;ready_queue->next =0;//int i;int pcb_number=-1;idleprocess=NULL; //设置闲逛进程PCB各字段值idleprocess=(PCB*)malloc(sizeof(PCB));idleprocess->ID =0;idleprocess->State =0;idleprocess->CPUtime =0;idleprocess->priority =0;idleprocess->ALLtime =1;idleprocess->next =NULL;//闲逛进程放入就绪对列idleprocess->next =ready_queue->next ;ready_queue->next =idleprocess;//也可假定初始时系统中只有一个idle进程//输出初始时进程的个数/* while(pcb_number<0){cout<<("Input the number of the PCB to be started:");cin>>pcb_number;}cout<<("\n ID priority CPUtime ALLtime State\n");for(i=0;i<pcb_number;i++)insert();//insert(pcb_number);*/cout<<"就绪队列初始化成功！"<<endl;::print_init (ready_queue);cout<<endl;}//调用destory(),将进程插入阻塞队列void block(PCB *pcb){//将pcb插入到阻塞队列pcb->State =2; //将PCB所指进程的状态设置为阻塞pcb->CPUtime -=2; //设进程执行半个时间片单位后被阻塞// pcb->next =NULL;print(pcb);cout<<(" 变迁2：running->blocked\n");//将pcb插入到阻塞队列//插入方式参考唤醒条件//因为是随机唤醒一个进程，所以简单的把它放置在阻塞队列的头部pcb->next =block_queue->next ;block_queue->next =pcb;}void update(PCB *pcb){//就绪队列中进程的优先级均增加1PCB *temp=ready_queue->next ;while(temp && temp->next ){//就绪队列的最后一个是闲逛进程temp->priority ++;temp=temp->next ;}}void run_priority(PCB *pcb){//如果pcb是闲逛进程，则不作处理，再次放入就绪队列ready_queueif(pcb->ID ==0){::insert_queue (ready_queue,pcb);print(pcb);cout<<(" 变迁1：ready->running\n");}else{//如果不是闲逛进程，则进行如下处理pcb->State =1;//设置该进程的状态为“运行”pcb->CPUtime +=4;//累计该进程占用CPU的时间pcb->priority =pcb->priority - 3;//每运行一个时间片，其优先数减3if(pcb->priority <1)pcb->priority =1;print(pcb);cout<<(" 变迁1：ready->running\n");if(rand()%3==1)//PCB不是闲逛进程，满足条件则阻塞此进程{if(pcb->CPUtime - 2 < pcb->ALLtime )block(pcb);else{//已经执行完毕，应该销毁进程cout<<endl;cout<<"\t the process no "<<pcb->ID<<" is completed! 销毁：running->Destroy"<<endl;delete pcb;}}else{//否则看该进程是否执行完毕，如果执行完毕，则释放，否则再次放入就绪队列if(pcb->CPUtime >= pcb->ALLtime ){//释放cout<<endl;cout<<"\t the process no "<<pcb->ID<<" is completed! 销毁：running->Destroy"<<endl;delete pcb;}else{//再次放入就绪队列，按照优先级有序::insert_queue (ready_queue,pcb);}}}update(ready_queue);//更新就绪队列进程优先数if(rand()%5==1){insert(3);//创建3个新进程::sort_queue (ready_queue);}if(rand()%7==1)wakeup_priority(); //唤醒一个进程//返回当前进程是否被阻塞，1（已阻塞），0（未阻塞）}void run_loop(PCB *pcb){//如果pcb是闲逛进程，则不作处理，再次放入就绪队列ready_queueif(pcb->ID ==0){::pushback_queue (ready_queue,pcb);print(pcb);cout<<(" 变迁1：ready->running\n");}else{//如果不是闲逛进程，则进行如下处理pcb->State =1;//设置该进程的状态为“运行”pcb->CPUtime +=4;//累计该进程占用CPU的时间print(pcb);cout<<(" 变迁1：ready->running\n");if(rand()%3==1)//PCB不是闲逛进程，满足条件则阻塞此进程{if(pcb->CPUtime - 2 < pcb->ALLtime )block(pcb);else{//已经执行完毕，应该销毁进程cout<<endl;cout<<"\t the process no "<<pcb->ID<<" is completed! 销毁：running->Destroy"<<endl;delete pcb;}}else{//否则看该进程是否执行完毕，如果执行完毕，则释放，否则再次放入就绪队列if(pcb->CPUtime >= pcb->ALLtime ){//释放//释放cout<<endl;cout<<"\t the process no "<<pcb->ID<<" is completed! 销毁：running->Destroy"<<endl;delete pcb;}else{//再次放入就绪队列::pushback_queue (ready_queue,pcb);}}}if(rand()%5==1){insert(3);//创建3个新进程}if(rand()%7==1)wakeup_loop();//唤醒一个进程//返回当前进程是否被阻塞，1（已阻塞），0（未阻塞）}void wakeup_priority(){//随机唤醒一个阻塞进程//采用遍历阻塞队列的方法，每访问一个，就产生一个随机数//如果该随机数对20求余恰好是1，则当前节点被唤醒，就纳入就绪队列if(block_queue->next ==0)//此时没有被阻塞的进程，不需唤醒return;PCB *p,*q;//下面遍历阻塞队列q永远指向p的前驱while(true){q=block_queue;p=q->next ;while(p && rand()%20!=1){q=p;p=p->next ;}if(p!=0){//p就是要唤醒的进程q->next =p->next ;break;}}p->State =0;cout<<endl;::print (p);cout<<" 变迁3：blocked->ready"<<endl;::insert_queue (ready_queue,p)}void wakeup_loop(){//随机唤醒一个阻塞进程//采用遍历阻塞队列的方法，每访问一个，就产生一个随机数//如果该随机数对20求余恰好是1，则当前节点被唤醒，就纳入就绪队列if(block_queue->next ==0)//此时没有被阻塞的进程，不需唤醒return;PCB *p,*q;//下面遍历阻塞队列q永远指向p的前驱while(true){q=block_queue;p=q->next ;while(p && rand()%20!=1){q=p;p=p->next ;}if(p!=0){//p就是要唤醒的进程q->next =p->next ;break;}}p->State =0;cout<<endl;::print (p);cout<<" 变迁3：blocked->ready"<<endl;::pushback_queue (ready_queue,p);}//优先权优先调度算法void proc_priority(){::sort_queue (ready_queue);PCB *temp=0,*running=0;//running 的PCB指针int times;//block_queue=NULL;//for(times=0;times<300;times++)for(times=0;times<10;times++){//找到优先级最高的进程，并将之从队列中删除cout<<"本次调度前："<<endl;::print_init (ready_queue);running=ready_queue->next ;//running 指向就绪队列的队首PCB ready_queue->next =running->next ;cout<<endl;cout<<"本次调度开始"<<endl;::run_priority (running);cout<<"\n本次调度结束."<<endl;}}//轮转法进程调用算法void proc_loop(){PCB *temp=0,*running=0;//running 的PCB指针int times;//block_queue=NULL;//for(times=0;times<300;times++)for(times=0;times<10;times++){//将running 从队列中删除cout<<"本次调度前："<<endl;::print_init (ready_queue);running=ready_queue->next ;//running 指向就绪队列的队首PCBready_queue->next =running->next ;cout<<endl;cout<<"本次调度开始"<<endl;::run_loop (running);cout<<"\n本次调度结束."<<endl;}}c)写出程序并运行，运行界面如下：选择1，进行优先权调度，得到结果如下：选择2，进行时间片轮转调度，结果为:选择0，退出运行界面。
