操作系统实验指导书--实验一 基于优先级的进程调度.docx

操作系统实验指导书实验一基于优先级的进程调度一、实验名称进程调度算法的模拟实现二、实验目标进程调度是处理机管理的核心内容。本实验要求用高级程序设计语言编写和调试一个简单的进程调用程序，模拟完成进程控制及进程调度算法。进程控制包括进程的创建、阻塞、唤醒和撤销，进程调度算法包括先来先服务、优先级（包括动态和静态）和论证法。通过本实验可以使学生加深对进程控制块和进程队列的概念的理解，并了解循环轮转调度和优先级调度的实现方法。三、实验环境要求：1 .PC机。2 .Dos;Windows；Linux环境。3 .BorlandC+forDos；VisualC÷+6.0forWindows；g+forLinuxo四、实验基本原理1 .设计进程控制块PCB结构，PCB结构包括以下信息：进程ID,用户ID,进程状态，进程优先数（或轮转时间片），进程创建时间，进程开始执行时间，进程执行完的时间，进程所占用的CPU时间，进程预计执行时间，进程剩余的执行时间等。2 .模拟实现进程调度算法，包括：FCFS（先来先服务）、RoundRobin（轮转法）、PRI（优先级法，包括静态和动态优先级）。FCFS调度算法：将进程按提交时间的先后顺序排成队列，并按照先来先服务(firstcomefirstserve)的方式进行调度处理。RoundRobin调度算法：其基本思想是让每个进程在就绪队列中的等待时间与享受服务的时间成一定的比例关系。系统给每一个进程分一段CPU时间，这段时间称为进程时间片。运行进程时间片用完后，系统将发生中断，强制该进程退出CPU,并释放相关资源，此进程进入就绪队列尾部等待CPU再次调度。PRI调度算法：其基本思想是每个进程都有一个优先权，在进程调度时，系统选取优先级最高的进程占有CPU。在dynamicPRI调度算法中，随着运行进程的执行，系统将不断地重新评估其优先级。而在StatiCPRl调度算法中，进程优先级初始化后直到进程执行完毕不再发生改变。PRI算法的核心是，一旦就绪进程中有更高优先级的进程时，立即发生高优先级中断。运行进程按优先级序列插入就绪队列等待，高优先级的进程被调度，占有CPU。五、数据结构设计(1)进程控制块:系统中PCB块同操作系统中的PCB并不完全相同，考虑到调度算法的可行性问题，将PCB中的部分信息忽略，以简化算法；主要提取了进程描述和控制信息，这些是算法实现所必需的基本信息。ClassPCBProcessControlBlock(intID;进程IDintuserID;用户IDintstatus;进程状态intpriority;进程优先级intSubmitTime;进程创建时间intStartTime;进程开始执行时间intfinishTime;进程执行完的时间inttotalCpuTime;/进程预计执行时间intIeftCpuTime;进程剩余的执行时间intOneCpuTime;进程时间片(2)进程控制预处理信息保存类：保存进程控制的基本信息，主要是进程ID和发生时间。进程控制包括进程阻塞、唤醒和撤销。ClassBarrageWakeintid;进程IDinttime;时间)(3)进程队列控制类：最核心的数据类型，是进程调度算法的实现类。其功能有，初始化用户输入数据，创建预处理信息，管理各进程队列，实现进程调度算法。ClassPCBQueuepublic:intinitialize。；读取输入文件信息，并进程预处理intretractProcess(int);/撤销进程intWakeProcess(int);唤醒进程intbarrageProcess(int);阻塞进程voidSubmitProcessO；创建进程voidinspector();CPU控制函数，检测进程控制信息voidFCFS();先来先服务(firstcomefirstserive)voidroundRobin();轮转法(roundrobin)voidStaticPRIO;静态优先级(StatiCPRDvoiddynamicPRI();动态优先(dynamicPRI)private:intCPU_TIME;intCurrentTime;当前时间inttimeSlice;时间片PCB*running;运行进程PCB*submissionHead,*submissionTail;预处理信息记录PCB*readyHead,*readyTail;就绪队列头(尾)指针PCB*waitHead,*waitTail;等待队列头(尾)指针PCB*finishHead,*finishTail;完成队列头(尾)指针BarrageWake*barrageHead,*barrageTail;预阻塞进程BarrageWake*awakenHead,*awakenTail;预唤醒进程BarrageWake*retractHead,*retractTail;预撤销进程；(4)PCB画图类：描述PCB块的画图类，用于显示系统中，它提取了PCB块中的部分信息，去除了一些不必要的信息。其中的部分信息将在动态显示过程中传递给用户。ClasspcbDrawpublic:intID;进程ID号intpriority;进程优先级inttotalCpuTime;进程需运行的总CPU时间intIeftCpuTime;进程剩余的CPU时间intOneCpuTime;进程时间片；(5)画图控制系统：可视化平台的实现部分；包括初始化显示系统，初始化系统设置，读取系统和用户调度过程的记录文件，可视化显示运行进程和各进程队列，错误检测和错误信息显示与记录机制。Classdrawpublic:voidinitRoom(int);初始化显示系统voidinitSystem();初始化系统设置intreadinformations(int);读取调度过程记录信息voiddrawing(int);在屏幕上画出PCB队列和各PCB块voidcompareO;错误检测private:intmode,debug;系统模式和运行模式interror_count,warning_count;/记录错误和警告interror;错误标志ints_time,u_time;系统CPU时间和用户CPU时间intsys_slice,use_slice;系统时间片和用户时间片pcbRect*user,*system;封装的系统和用户进程队列；六、流程图开始图2优先级进程调度算法流程图图4优先级调度算法中的中断处理程序七、源代码/进程调度算法的模拟实现#include"string.h"#include"stdio.h,#include<stdlib.h>#defineNUMBER5#defineNULLO#definePCBSTRUCTstructPCBSTRtypedefPcbstruct*pcb；enumAlgorithmPR,RR;charMeans3;charb;PCBSTRUCT(charName10;intProi;Round;CpuTime;NeedTime;Count;charState;Pcbstruct*Next；;/创建PCB结构体PCBFinish,Ready,Tail,Run;voidFirstln()(Run=Ready;Run->State='R'Ready=Ready->Next;voidPrintl()(if(strcmp(Means,"PR")=O)(strcmp(Means,"pr")=O)printf("nNameCpuTimeNeedTimePrioprityStaten'r);elseprintf("nNameCpuTimeNeedTimeCountRoundStaten");if(strcmp(Means,"PR")=O)(strcmp(Means,"pr")=O)printf("%8s%6d%8d%10d%8cn",temp->Name,temp->CpuTime,temp->NeedTime,temp->Proi,temp->State);elseprintf(',%8s%6d%8d%8d%8d%8cn",temp->Name,temp->CpuTime,temp->NeedTime,temp->Count,temp->Round,temp->State);)输出结果显示voidprint()(PCBp;Print1();printf("It'stheRunqueuen);if(Run!=NULL)Print2(Run);p=Ready;printf(',It'stheReadyqueuen");while(p!=NULL)(Print2(p);p=p->Next;)printf("It'stheFinishedqueuen);p=Finish;while(p!=NULL)p=p->Next;)printf("nn");)按优先级从高到低插入就绪队列voidInsertl(PCBq)intb;PCBpl,s,r;s=q;pI=Ready;r=pl;b=l;WhiIe(P1!=NULL)&&b)if(pl->Proi>=s->Proi)F=P1;pl=pl->Next;)elseb=0;if(r!=pl)(r->Next=s;s->Next=p1;elses->Next=pl;Ready=s;IvoidInsert2(PCBp2)(Tail->Next=p2;Tail=p2;p2->Next=NULL;voidCreate(enumAlgorithmalg)(PCBp;inti,time;charNa10;intprio;Ready=NULL;Finish=NULL;Run=NULL;if(alg=PR)for(i=l;i<=5;i+)p=(PCB)malloc(sizeof(PCBSTRUCT);scanf("%s",Na);scanf("%d",(fetime);scanf("%d",&prio);strcpy(p->Name,Na);p->CpuTime=0;p->NeedTime=time;p->State='W;p->Proi=prio;if(Ready!=NULL)Insertl(p);else1p->Next=Ready;Ready=p;)elseReady=NULL;for(i=0;i<5;i+)(scanf(',%s",Na);scanf("%d",&time);p=(PCB)malloc(sizeof