操作系统 实验一.doc

姓名学号实验成绩华中师范大学计算机科学系实 验 报 告 书实验题目： 进程调度算法 课程名称： 操作系统 主讲教师： 实验时间： 2015年12月 一、 实验目的：1、 掌握作业调度的基本思想2、 熟练使用各种作业调度算法描述的过程3、 掌握各种算法的优缺点二、实验内容：进程调度是处理机管理的核心内容。本实验要求用高级程序语言编写和调试一简单的进程调用程序，模拟完成进程控制及进程调度算法。进程控制包括进程的创建、阻塞、唤醒和撤销，进程调度算法包括优先级和轮转法。通过本实验可加深学生对进程控制块和进程队列的概念的理解，并了解循环轮转调度和优先级调度的实现方法。三、实验环境：实践平台：Windows编写环境：VC+6.0四、实验设计原理1设计进程控制块PCB结构，PCB结构包括以下信息：进程ID，用户ID, 进程状态，进程优先数（或轮转时间片），进程创建时间，进程开始执行时间，进程执行完的时间，进程所占用的CPU时间，进程预计执行时间，进程剩余的执行时间等。2模拟实现进程调度算法，包括： RoundRobin（轮转法）、PRI(优先级算法)RoundRobin调度算法：其基本思想是让每个进程在就绪队列中的等待时间与享受服务的时间成一定的比例关系。系统给每一个进程分一段CPU时间，这段时间称为进程时间片。运行进程时间片用完后，系统将发生中断，强制该进程退出CPU，并释放相关资源，此进程进入就绪队列尾部等待CPU再次调度。PRI调度算法：其基本思想是每个进程都有一个优先权，在进程调度时，系统选取优先级最高的进程占有CPU。在dynamicPRI调度算法中，随着运行进程的执行，系统将不断地重新评估其优先级。而在StaticPRI调度算法中，进程优先级初始化后直到进程执行完毕不再发生改变。PRI算法的核心是，一旦就绪进程中有更高优先级的进程时，立即发生高优先级中断。运行进程按优先级序列插入就绪队列等待，高优先级的进程被调度，占有CPU。五、实验详细实现过程与算法流程（1）进程控制块:系统中PCB块同操作系统中的PCB并不完全相同，考虑到调度算法的可行性问题，将PCB中的部分信息忽略，以简化算法；主要提取了进程描述和控制信息.Class PCB/Process Control Blockint ID; /进程IDint userID; /用户IDint status; /进程状态 int priority; /进程优先级int submitTime; /进程创建时间int startTime; /进程开始执行时间int finishTime; /进程执行完的时间int totalCpuTime;/进程预计执行时间int leftCpuTime; /进程剩余的执行时间int oneCpuTime; /进程时间片（2）进程控制预处理信息保存类: 保存进程控制的基本信息，主要是进程ID和发生时间。进程控制包括进程阻塞、唤醒和撤销。Class BarrageWakeint id; /进程IDint time; /时间（3）进程队列控制类：最核心的数据类型，是进程调度算法的实现类。其功能有，初始化用户输入数据，创建预处理信息，管理各进程队列，实现进程调度算法。Class PCBQueuepublic:int initialize(); /读取输入文件信息，并进程预处理int retractProcess(int); / 撤销进程int wakeProcess(int); /唤醒进程int barrageProcess(int); /阻塞进程void submitProcess(); /创建进程void inspector(); /CPU控制函数，检测进程控制信息void FCFS(); /先来先服务（first come first serive）void roundRobin();/轮转法（round robin）void staticPRI(); /静态优先级（static PRI）void dynamicPRI();/动态优先（dynamic PRI）private:int CPU_TIME; int currentTime; /当前时间int timeSlice; /时间片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块中的核心信息，其中的部分信息将在动态显示过程中传递给用户。Class pcbDrawpublic:int ID;/进程ID号int priority;/进程优先级int totalCpuTime;/进程需运行的总CPU 时间int leftCpuTime; /进程剩余的CPU时间int oneCpuTime; /进程时间片;（5）画图控制系统：可视化平台的实现部分；包括初始化显示系统，初始化系统设置，读取系统和用户调度过程的记录文件，可视化显示运行进程和各进程队列，错误检测和错误信息显示与记录机制。Class drawpublic:void initRoom(int);/初始化显示系统void initSystem(); /初始化系统设置int readInformations(int); /读取调度过程记录信息void drawing(int);/在屏幕上画出PCB队列和各PCB块void compare(); /错误检测private:int mode，debug; /系统模式和运行模式int error_count，warning_count; /记录错误和警告int error;/错误标志int s_time， u_time;/系统CPU时间和用户CPU时间int sys_slice， use_slice;/系统时间片和用户时间片pcbRect *user，*system; /封装的系统和用户进程队列;NNNNNYYYY开始CPU中断检测是否有中断中断处理程序CPU空否就绪队列空否就绪队列头部进程进入CPU退出控制程序将此进程的时间片赋给时间片计数器1. 运行进程剩余时间减1.2. 时间计数片减1.进程是否完成进程入完成队列CPU置空CPU空置一个CPU时间退出YYNYYNNN开始CPU中断检测是否有中断中断处理程序CPU空否就绪队列空否就绪队列头部进程进入CPU退出控制程序1. 运行进程剩余时间减1.2. 运行进程优先级减2.2. 运行进程优先级减2.进程是否完成进程入完成队列CPU置空CPU空置一个CPU时间退出图2 优先级进程调度算法流程图中断类型分析进程提交进程阻塞提交进程唤醒进程撤销创建PCB入对列尾部查找相应的PCB的ID号找到否相应的处理高优先中断运行进程按优先级序列插入就绪队列中CPU置空六、源程序（加注释）#include string.h#include stdio.h#define NUMBER 5#define NULL 0#define PCBSTRUCT struct PCBSTRtypedef PCBSTRUCT* PCB;enum Algorithm PR,RR;char Means3;char b;PCBSTRUCT char Name10; int Proi; int Round; int CpuTime; int NeedTime; int Count; char State; PCBSTRUCT* Next;PCB Finish,Ready,Tail,Run;/完成、就绪、运行、当前(Tail)进程void FirstIn() /取下一个就绪队列中的进程运行 Run = Ready; Run-State = R; /就绪的第一个进程转为运行态 Ready = Ready-Next;/就绪队列变化void Print1() if (strcmp(Means,PR)=0)|(strcmp(Means,pr)=0) printf(n Name CpuTime NeedTime Prioprity Staten); else printf(n Name CpuTime NeedTime Count Round Staten);void Print2(PCB temp)if (strcmp(Means,PR)=0)|(strcmp(Means,pr)=0) printf(%8s %6d %8d %10d %8cn,temp-Name,temp-CpuTime, temp-NeedTime,temp-Proi,temp-State);else printf(%8s %6d %8d %8d %8d %8cn,temp-Name,temp-CpuTime, temp-NeedTime,temp-Count,temp-Round,temp-State);void print()PCB p;Print1();printf(Its the Run queuen);if (Run != NULL) Print2(Run);p = Ready;printf(Its the Ready queuen);while (p != NULL) Print2(p); p = p-Next;printf(Its the Finished queuen);p = Finish;while (p != NULL) Print2(p); p = p-Next;printf(nn);/按优先级从高到低插入就绪队列void Insert1(PCB q)PCB forReady = Ready;PCB parent = NULL;if(q-ProiProi) Tail-Next = q; Tail = q; q-Next= NULL;else while(forReady!=NULL & q-ProiProi) parent=forReady; forReady=forReady-Next;if(parent!=NULL) q-Next = forReady; parent-Next = q;else q-Next = Ready; Ready=q;void Insert2(PCB p2)Tail-Next = p2;Tail = p2;p2-Next = NULL;void Create(enum Algorithm alg)PCB p;int i,time,priority;char Na10;Ready = NULL;Finish = NULL;Run = NULL;if (alg = PR)Ready = NULL;for (i=0;iName,Na);p-CpuTime = 0;p-NeedTime = time;p-Proi = priority;p-Count = 0;p-State = W;p-Round = 1;if (Ready != NULL)Insert1(p);elsep-Next = Ready;Ready = p;Tail = p;elseReady = NULL;for (i=0;iName,Na);p-CpuTime = 0;p-NeedTime = time;p-Count = 0;p-State = W;p-Round = 2;if (Ready != NULL)Insert2(p);elsep-Next = Ready;Ready = p;Tail = p;if (alg = PR) printf(Output Of Priority:n);elseprintf(Output of RoundRobin:n);Run = Ready;Ready = Ready-Next;Run- State = R;void PriSch() /这是优先级高者优先算法 while (Run != NULL) if(Ready!=NULL)if(Ready-ProiProi)Run-CpuTime = Run-CpuTime + 1; Run-NeedTime = Run-NeedTime - 1;Run-Count = Run-Count + 1; if (Run-NeedTime = 0)Run-Next = Finish; Finish = Run;Run-State = F; Run = NULL; if (Ready != NULL) FirstIn();elsePCB saver;saver=Run;saver-State=W;Insert1(saver);Run = Ready;Ready-State=R;Ready=Ready-Next; else Run-CpuTime = Run-CpuTime + 1; Run-NeedTime = Run-NeedTime - 1;Run-Count = Run-Count + 1; if (Run-NeedTime = 0)Run-Next = Finish; Finish = Run;Run-State = F; Run = NULL; print(); getch(); void RoundSch() while (Run != NULL) Run-CpuTime = Run-CpuTime + 1;Run-