FPF和RR调度算法

郑州轻工业学院本科本科 实验报告实验报告 设计题目设计题目 实现 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 撰写实验报告 包含实验要求中 1 4 项内容 要求有设计图 结构图 流程图 和源代码 注明使用的编程语言和环境 注意事项 实验中注重实现算法本质 高优先权优先 FPF 时间片轮转 RR 两个算法可以选做一个 量力而行 鼓励多做 FPF 算法也适用于作业调度 关于作业调度和进程调度的区别 只要求概念上理解清楚 不要求实现 include include struct PCB char p name 20 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 n n 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 printf 输入进程运行时间 scanf d p p runTime 0 p p state W p next NULL pt next p pt p printf n n 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 d n n cases printf 当前正在运行的进程是 s n psorted p name psorted p state R printf qname state super ndtime runtime n printf s t c t d t d t d t n n 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 当前就绪状态的队列为 n n pt 指向已经排序的队列 pt psorted next while pt NULL printf qname state super ndtime runtime n printf s t c t d t d t d t n n 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 c