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

操作系统实验指导书实验一 基于优先级的进程调度一、 实验名称进程调度算法的模拟实现二、 实验目标进程调度是处理机管理的核心内容。本实验要求用高级程序设计语言编写和调试一个简单的进程调用程序，模拟完成进程控制及进程调度算法。进程控制包括进程的创建、阻塞、唤醒和撤销，进程调度算法包括先来先服务、优先级（包括动态和静态）和论证法。通过本实验可以使学生加深对进程控制块和进程队列的概念的理解，并了解循环轮转调度和优先级调度的实现方法。三、实验环境要求：1.PC机。2.Dos；Windows；Linux环境。3.Borland C+ for Dos；Visual C+ 6.0 for Windows；g+ for Linux。四、实验基本原理1设计进程控制块PCB结构，PCB结构包括以下信息：进程ID，用户ID, 进程状态，进程优先数（或轮转时间片），进程创建时间，进程开始执行时间，进程执行完的时间，进程所占用的CPU时间，进程预计执行时间，进程剩余的执行时间等。2模拟实现进程调度算法，包括：FCFS（先来先服务）、RoundRobin（轮转法）、PRI（优先级法，包括静态和动态优先级）。FCFS调度算法：将进程按提交时间的先后顺序排成队列，并按照先来先服务（first come first serve）的方式进行调度处理。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时间退出图1 轮转调度算法流程图YYNYYNNN开始CPU中断检测是否有中断中断处理程序CPU空否就绪队列空否就绪队列头部进程进入CPU退出控制程序1. 运行进程剩余时间减1.2. 运行进程优先级减2.2. 运行进程优先级减2.进程是否完成进程入完成队列CPU置空CPU空置一个CPU时间退出图2 优先级进程调度算法流程图中断类型分析进程提交进程阻塞提交进程唤醒进程撤销创建PCB入对列尾部查找相应的PCB的ID号找到否相应的处理高优先中断运行进程按优先级序列插入就绪队列中CPU置空图3 轮转调度算法中的中断处理程序N中断类型分析进程提交进程阻塞提交进程唤醒进程撤销创建PCB入对列尾部图3 优先级进程调度算法流程图查找相应的PCB的ID号找到否相应的处理时间片用完运行进程被切换到就绪队列尾部等待CPU置空Y图4 优先级调度算法中的中断处理程序七、源代码/进程调度算法的模拟实现#include "string.h"#include "stdio.h"#include<stdlib.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结构体PCB Finish,Ready,Tail,Run;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->