FPF和RR调度算法.doc

郑州轻工业学院本科实验报告设计题目： 实现FPF和RR调度算法 学生姓名： 李洋 系 别： 计算机与通信工程学院 专 业： 网络运维 班 级： 13-03 学 号： 521507110314 指导教师： 吴庆岗 2015 年 11 月 18 日一、实验目的编写程序，实现FPF和RR算法，模拟进程调度过程，加深对作业调度的理解。二、实验内容实现FPF和RR调度算法。 数据结构设计（PCB，进程就绪队列） 算法实现与模拟（排序、调度） 输出调度结果，展示调度过程并解释三、实验要求1. 设计进程控制块(PCB)的数据结构 应包含实验必须的数据项，如进程ID、需要的服务时间、进入系统时间、完成时间、周转时间、优先权、进程状态（R-运行，W-等待），以及实验者认为有必要的其他数据项。2. 实现排序算法（将就绪队列中的进程排序） RR：只需在开始时排序，按FCFS策略将进程依次插入就绪队列。开始运行后不再需要排序，按RR策略将每一个刚刚运行完一个时间片的进程插入到队尾。 FPF：每次调度前排序，按计算所得的动态优先权排成有序队列，最高优先权排进程在队首，优先权相同的进程按FCFS策略排队。3. 实现RR调度过程模拟每个进程用一个PCB表示，按FCFS策略排成就绪队列，按照固定的周期循环调度。选择队首的进程，将其从就绪队列移出，修改其状态为R。经过一个时间片，如果正在执行的进程没有执行完，修改其状态为W，插入到就绪队列尾部。如果执行完毕，计算其周转时间。进行下一次调度（去往第步），直到就绪队列为空。4. 实现FPF调度过程模拟每个进程用一个PCB表示。计算动态优先权，按优先权高低排入就绪队列，如果相同，则按FCFS排队。系统开始时调度，每个进程结束时进行调度。选择队首的作业，将其从后备队列移出计算选中作业的周转时间（进程运行过程，在本实验中，无需实现，可认为就绪队列上的进程一但被调度程序选出，就顺利运行结束）进行下一次调度（去往第步）5.实现结果输出 输出进程状态表，展示调度过程 初始进程状态（未调度时） 每次调度后的进程状态6.撰写实验报告 包含实验要求中14项内容，要求有设计图（结构图/流程图）和源代码。 注明使用的编程语言和环境。注意事项 实验中注重实现算法本质（高优先权优先FPF，时间片轮转RR）。 两个算法可以选做一个，量力而行，鼓励多做。 FPF算法也适用于作业调度。关于作业调度和进程调度的区别，只要求概念上理解清楚，不要求实现。#include #include struct PCB char p_name20; int p_priority; int p_needTime; int p_runTime; char p_state; struct PCB* next;void HighPriority();void RoundRobin();void Information();char Choice();struct PCB* SortList(PCB* HL);int main() Information(); char choice = Choice(); switch(choice) case 1: system(cls); HighPriority(); break; default: break; system(pause); return 0;void Information() printf( 按回车键进入演示程序); getchar(); system(cls);char Choice() printf(nn); printf( 1.演示最高优先数优先算法。); printf( 按1继续:); char ch = getchar(); return ch; system(cls);void HighPriority() struct PCB *processes, *pt; /pt作为临时节点来创建链表，使用for语句，限制进程数为5个 processes = pt = (struct PCB*)malloc(sizeof(struct PCB); for (int i = 0; i != 5; +i) struct PCB *p = (struct PCB*)malloc(sizeof(struct PCB); printf(进程号No.%d：n, i); printf(输入进程名：); scanf(%s, p-p_name); printf(输入进程优先数：); scanf(%d, &p-p_priority); printf(输入进程运行时间：); scanf(%d, &p-p_needTime); p-p_runTime = 0; p-p_state = W; p-next = NULL; pt-next = p; pt = p; printf(nn); getchar(); /接受回车 /processes作为头结点来存储链表 processes = processes-next; int cases = 0; struct PCB *psorted = processes; while (1) +cases; pt = processes; /对链表按照优先数排序 /psorted用来存放排序后的链表 psorted = SortList(psorted); printf(The execute number: %dnn, cases); printf(* 当前正在运行的进程是：%sn, psorted-p_name); psorted-p_state = R; printf(qname state super ndtime runtimen); printf(%st%ct%dt%dt%dtnn, psorted-p_name, psorted-p_state, psorted-p_priority, psorted-p_needTime, psorted-p_runTime); pt-p_state = W; psorted-p_runTime+; psorted-p_priority-; printf(* 当前就绪状态的队列为：nn); /pt指向已经排序的队列 pt = psorted-next; while (pt != NULL) printf(qname state super ndtime runtimen); printf(%st%ct%dt%dt%dtnn, pt-p_name, pt-p_state, pt-p_priority, pt-p_needTime, pt-p_runTime); pt = pt-next; /pt指向已经排序的链表，判断链表是否有已用时间啊等于需要时间的 pt = psorted; struct PCB *ap; ap = NULL; /ap指向pt的前一个节点 while (pt != NULL) if (pt-p_needTime = pt-p_runTime) if (ap = NULL) pt = psorted-next; psorted = pt; else ap-next = pt-next; ap = pt; pt = pt-next; if (psorted-next = NULL) break; getchar(); struct PCB* SortList(PCB* HL) struct PCB* SL; SL = (struct PCB*)malloc(sizeof(struct PCB); SL = NULL; struct PCB* r = HL; while (r != NULL) struct PCB* t = r-next; struct PCB* cp = SL; struct PCB* ap = NULL