多进程调度课程设计.doc

综合设计报告 设计名称 设计名称 操作系统综合设计操作系统综合设计 设计题目 设计题目 模拟进程调度功能的设计与实现模拟进程调度功能的设计与实现 学生学号 学生学号 专业班级 专业班级 学生姓名 学生姓名 学生成绩 学生成绩 指导教师 职称 指导教师 职称 课题工作时间 课题工作时间 2011 年年 6 月月 6 日日 至至 2011 年年 6 月月 29 日日 四 综合设计 课程设计 摘要 中文 进程调度方式分为非剥夺方式和剥夺方式 调度算法又有先进先出 短时间调 度 优先级调度 高响应比调度 时间片调度 多级反馈调度 进程调度模块通过 PCB 变化来掌握系统中存在的所有进程的执行情况和状态特征 并在适当的时机从就 绪队列中选择出一个进程占据处理机 无论是在批处理系统还是分时系统中 用户进 程数一般都多于处理机数 这将导致它们互相争夺处理机 另外 系统进程也同样需 要使用处理机 这就要求进程调度程序按一定的策略 动态地把处理机分配给处于就 绪队列中的某一个进程 以使之执行 每个进程三种状态 运行态 等待态 就绪态 通过对进程的合理调度 使得系统能够安全有序的良好运转 关键字 进程调度 处理机 PCB 进程状态 五 综合设计 课程设计 Abstract 英文 Abstract Divided into the process scheduling way and deprivation deprived scheduling algorithm and a fifo short time scheduling priority scheduling high response than scheduling time piece of scheduling multilevel feedback scheduling Process scheduling module through the PCB change to master the existing in the system of the implementation of all process and characteristic and the state at the right time ready queue from a selection of a process occupy processor Whether in batch system or a time sharing system user process several generally more than processor number this will lead to them for each other processor In addition the system process using the processor is also required This requires process scheduler according to certain strategy dynamically assigned to the processor in ready queue in a process to execution Each process three states operation state waiting for the state the state is ready Through the process of the reasonable dispatch the system can be safely and orderly good operation Key words process scheduling processor PCB process state 目录目录 摘 要 II ABSTRACT II 第一章 课题背景 1 1 1 设计背景 1 1 2 设计任务 1 1 3 设计目的 1 1 4 设计要求 1 第二章 设计简介及设计方案论述 2 2 1 设计理论依据 2 第三章 详细设计 6 3 1数据结构 6 3 2 程序功能划分 6 3 3 主要介绍 6 3 3 1 程序主框架 6 3 3 2 程序结点数据结构 7 3 3 3 主要程序框图 7 第四章 设计结果及分析 8 4 1 设计结果显示 8 4 1 1 进程的创建 8 4 1 2 进程正在执行 8 4 1 3 执行时间完 调度另一进程 9 4 1 4 撤销进程 9 4 1 5 进程阻塞 10 4 1 6 唤醒进程 10 4 2 程序结果分析 11 总结 12 致谢 13 参考文献 14 附录重要代码 15 I 摘 要 无论是在批处理系统还是分时系统中 用户进程数一般都多于处理机数 这将导 致它们互相争夺处理机 另外 系统进程也同样需要使用处理机 这就要求进程调度 程序按一定的策略 动态地把处理机分配给处于就绪队列中的某一个进程 以使之执 行 每个进程三种状态 运行态 等待态 就绪态 通过对进程的合理调度 使得系 统能够安全有序的良好运转 进程调度方式分为非剥夺方式和剥夺方式 调度算法又有先进先出 短时间调度 优先级调度 高响应比调度 时间片调度 多级反馈调度 进程调度模块通过 PCB 变 化来掌握系统中存在的所有进程的执行情况和状态特征 并在适当的时机从就绪队列 中选择出一个进程占据处理机 关键字 进程调度 处理机 PCB 进程状态 Abstract Whether in batch system or a time sharing system user process several generally more than processor number this will lead to them for each other processor In addition the system process using the processor is also required This requires process scheduler according to certain strategy dynamically assigned to the processor in ready queue in a process to execution Each process three states operation state waiting for the state the state is ready Through the process of the reasonable dispatch the system can be safely and orderly good operation Divided into the process scheduling way and deprivation deprived scheduling algorithm and a fifo short time scheduling priority scheduling high response than scheduling time piece of scheduling multilevel feedback scheduling Process scheduling module through the PCB change to master the existing in the system of the implementation of all process and characteristic and the state at the right time ready queue from a selection of a process occupy processor Key words process scheduling processor PCB process state 0 第一章 课题背景 1 1 设计背景 21 世纪是高科技和高效率的时代 经济的飞速发展也展示了飞速增长的压力 也 对工作效率提出了进一步的要求 而计算机高效率的自动化能力在这一方面展示了巨 大的前景 所以 利用计算机编程技术安排合适而正确的工作流程来实现事物处理的 自动化 成为本报告解释和描述所编辑工程的重点 利用此次的模拟来提高对流程的 控制能力 1 2 设计任务 确定开发的项目名称 并熟悉相关知识 确定开发工具并实现开发环境的安装配置 实现用户界面的开发 实现进程调度子系统如下功能模块 1 3 设计目的 在多道程序和多任务系统中 系统内同时处于就绪状态的进程可能有若干个 也就是说能运行的进程大于处理机的个数 为了使系统中的进程能有条不紊的工 作 必须选用某种调度策略 选择一进城占用处理剂 要求学生设计一个模拟处 理剂调度算法 以巩固和加深处理机调度的概念 1 4 设计要求 进程调度算法包括 时间片轮换算法 动态优先级算法 短作业算法等 可选择进程的数量 本程序包括一种算法 即进程的多级反馈队列调度算法 实验每人一组 每人交一份设计报告 1 第二章 设计简介及设计方案论述 2 1 设计理论依据 1 进程控制块的内容如右图所示 图 2 1 其中进程优先数是赋给进城的优先级 都是总是选取优先级高的进程优先运行 2 每个进程的优先数 运行时间由程序任意给定 3 为了调度方便 把进程按给定优先级从小到大排成一个队列 按给定的运行时间 从小到大排成一个队里啊用一个指针变量作为首指针 指向队列的第一个进程 4 处理机调度总是选队首进程运行 由于本实验是模拟调度 所以选中的进程并不是 启动运行 而是执行 5 进程概念 进程是被独立分配资源的最小单位 进程是动态概念 必须程序运行 才有进程的产生 6 进程的状态模型 运行 进程已获得处理机 当前处于运行状态 就绪 进程已经准备好 一旦有处理器就可运行 7 处理机调度 在多道程序设计系统中 内存中有多道程序运行 他们相互争夺处 理机这一重要的资源 处理机调度就是从就绪队列中 按照一定的算法选择一个进 程并将处理机分配给它运行 以实现进程并发地执行 8 进程调度算法的功能 记录系统中所有进程的执行情况 选择占有处理机的进程 进行进程的上下文切换 9 进程调度的算法 1 先来先服务算法如图 2 2 2 图 2 2 先来先服务算法流程图 2 优先数算法 即进程的执行顺序由高优先级到低优先级 系统或用户按某 种原则为进程指定一个优先级来表示该进程所享有的确调度优先权 该算 法核心是确定进程的优先级 3 时间片轮转算法 固定时间片 每个进程在执行一个时间片后 轮到下一 进程执行 知道所有的进程执行完毕 处理器同一个时间只能处理一个任 务 处理器在处理多任务的时候 就要看请求的时间顺序 如果时间一致 就要进行预测 挑到一个任务后 需要若干步骤才能做完 这些步骤中有 些需要处理器参与 有些不需要 如磁盘控制器的存储过程 不需要处理 器处理的时候 这部分时间就要分配给其他的进程 原来的进程就要处于 等待的时间段上 经过周密分配时间 宏观上就象是多个任务一起运行一 样 但微观上是有先后的 就是时间片轮换 其算法流程如图 2 3 3 图 2 3 时间片轮换算法流程图 4 多级反馈轮转法 允许进程在队列之间移动 在系统中设置多个就绪队列 每个队列对应 一个优先级 第一个队列的优先级最高 第二队列次之 以下各队列的 优先级逐步低 各就绪队列中的进程的运行时间片不同 高优先级队列的时间片小 低 优先级队列的时间片大 进程并非总是固定在某一队列中 新进程进入 系统后 被存放在第一个队列的末尾 如果某个进程在规定的时间片内 没有完成工作 则把它转入到下一个队列的末尾 直至进入最后一个队 列 系统先运行第一个队列中的进程 当第一队列为空时 才运行第二个队 列中的进程 依此类推 仅当前面所有的队列都为空时 才运行最后一 个队列中的进程 当处理器正在第 i 个队列中为某个进程服务时 又有新 进程进入优先级最高的队列 第 1 i 1 中的任何一个对列 则此新 进程要抢占正在运行进程的处理器 即由调度程序把正在运行的进程放 4 回第 i 队列的末尾 把处理器分配给新到的高优先级进程 除最低优先权 队列外的所有其他队列 均采用相同的进程调度算法 即按时间片轮转 的 FIFO 先进先出 算法 最后一个队列中的进程按按时间片轮转或 FCFS 策略进行调度 它是综 合了 FIFO RR 和剥夺式 HPF 的一种进程调度算法 主要设计流程如下 图 2 4 图 2 4 多级反馈轮转算法的流程图 5 第三章 详细设计 3 1 数据结构 进程控制块 PCB 名称字段为 char 型的数组 所需时间为整型 优先级为整型 并且值小的优先级高 设置一个整型变量表示 CPU 的时间片 3 2 程序功能划分 创建进程 根据编辑框中的信息创建新进程 并将其插入就绪队列 若当前 无 进程运行或新进程的优先级高于正在运行的进程 则重新调度 完成后显示更新 撤消进程 撤消正在运行的进程 重新调度 完成后显示更新 阻塞进程 将正在运行的进程控制块 PCB 插入阻塞队列 重新调度 完成后 显示更新 唤醒进程 唤醒阻塞队列队首的进程 将其插入到与其优先级相对应的就绪 队列 重新调度 完成后显示更新 执行进程 将正在运行进程的所剩时间减 1 同时将 CPU 时间片减 1 判断执 行结果 若时间片未用完 进程也未结束 更新显示正在运行的进程 若时 间片未用完 进程结束 则重新调度 并显示更新 若时间片用完 进程结 束 则重新调度 并显示更新 若时间片用完 进程未结束 则将进程插入 到下一级就绪队列 重新调度 并显示更新 进程调度 判断当前是否有进程在运行 若有则将正在运行的进程插入到相 应的就绪队列 然后由优先级高到低的顺依次探寻各就绪队列 给第一个不 为空的就绪队列队首进程分配处理机 再根据队列的优先级为之分配时间片 先来先服务是根据进程到达的先后次序来决定的 而短作业优先则是根据作 业运行所需要的 cpu 时间的长短来确定的 3 3 主要介绍 3 3 1 程序主框架 进入主程序 6 3 3 2 程序结点数据结构 图 3 1 3 3 3 主要程序框图 创建进程撤销进程阻塞进程唤醒进程 7 图 3 2 第四章 设计结果及分析 4 1 设计结果显示 4 1 1 进程的创建 图 4 1 进程创建 8 4 1 2 进程正在执行 图 4 2 进程执行 4 1 3 执行时间完 调度另一进程 图 4 3 进程调度 9 4 1 4 撤销进程 图 4 4 进程撤销 4 1 5 进程阻塞 图 4 5 进程阻塞 10 4 1 6 唤醒进程 图 4 6 进程唤醒 4 1 7 短作业优先 图 4 7 短作业优先 11 4 2 程序结果分析 创建完进程之后 各个进程进入到就绪队列中按 enter 健执行进程调度 每按 一次 时间计数器的值加 1 直到进程被阻塞或者是所分配的时间片用完 开始 调度下一个进程 撤销进程之后 正在运行的进程停止执行 继续执行就绪队列中下一个进程 对于就绪队列中排在队首的进程优先执行 进程阻塞之后 该进程排到优先级更低的就绪队列的末尾 然后开始调度下一 个进程 时间片也翻了倍 然后唤醒该进程 把进程调到就绪队列中准备执行 多级反馈队列调度算法是综合了先来先服务算法 时间片轮换算法的一种调度 算法 有更好的实时性 整个程序包含三种算法 先来先服务算法 短作业优先算法 还有就是多级反 馈队列调度算法 可以根据所给的菜单来选择不同的进程调度算法 先来先服 务算法是根据进程被创建的时间来决定进程调度顺序的 短作业算法是根据所 给的作业运行时间来确定调度顺序的 多级调度算法是这几种算法的综合 12 总结 通过为期两个星期的操作系统课程设计 我对课程设计有了更深的了解 没做课 程设计以前 一直对课程设计的概念很模糊 就以为课程设计只是单纯的对本学期所 学知识的一个总结 后来上了课程设计才知道 课程设计并不只是简单的总结 更多 的是对书本知识一个更深层次的理解 回忆此次课程设计 至今仍然感慨很多 刚开始接到通知说要做课程设计的时候 因为我们的专业课考试很多 加上自己所学的编程语言知识很有限 所以很担心自己 不能如期的做好设计 后来 觉得这种担心是多余的 与其担心 不如好好的做 多 学点知识 整个过程 从理论到实践 整整两个星期的日子里面 可以说是苦多于甜 有的时候做出个函数会遇到很多错误 到后来都没信心了 但在老师和同学的帮助下 也一直坚持不懈的做下来了 学到了很多东西 不仅仅是专业知识 所以说这一切都 是值得的 除了书本上面的知识得到了巩固 我还了解了更多的关于计算机方面的知 识 不仅仅限于操作系统 比如说 MFC Java 等 这些编程语言以及它的使用以前从 来都没有尝试过 但在课程设计课堂上面 刘老师带着我们一起认识了一下 Java 让 我们这些从没有接触过 Java 的同学也开始了解到 Java 是什么 虽然说知道的很少 但这至少是一个开始 希望自己以后能利用空余时间学好 Java 这次课程设计原来打算用 MFC 写出来的 但在编写过程中遇到了很多困难 最后 在同学的帮助下 用 MFC 写出来了一个很小的程序 自己在课下也试图想完全靠自己 做出一个完整的界面 但最后都因为自己所积累的知识有限 没有做成功 这次课程设计使用 C 写的 也花了一定时间 做出来的程序是参考老师所给的例 子一点一点看懂了 然后在自己慢点摸索的 同时也上网搜集了很多资料 关于 MFC 以及 Java 虽然题目不难 但通过这次课程设计 我对面向对象的编程语言有了一个 更深的了解 在设计过程中也遇到了不少的问题 1 调度时机决策 2 多级反馈队列兼容 3 设备的分配和释放 4 进程的抢占 对应的解决办法是 1 设置进程的相应状态 2 采用单一就绪队列 各进程转入就绪队列进行插入到相应的位置 3 每执行一次 判断就绪队列首端元素是否有更高的优先级 通过这次课程设计 我深刻的认识到理论联系实际的重要性 只有在把书本知识 学得扎实的基础上 课后要勤动手 才能算是收获 无论是哪门课程 特别是计 算机相关课程 动手能力是很重要的 所以课后一定要多加练习 学会多用所学 的知识 课后要做的更多的是多看一些课外书籍 学一些语言 不能仅仅靠课堂 上面讲的内容 所以以后一定会多加动手练习 紧紧的结合所学知识 争取把各 方面都发展平衡 13 致谢 在短短两个星期的时间里 完成了课程设计的任务 除了自身的努力之外 更离 不开老师和同学们的帮助 老师们细心的指导 在我有困难时同学们不厌其烦的解答 我的课程设计完成的才会顺利 由此 衷心的感谢大家 14 参考文献参考文献 1 梁小丹 梁红兵 哲风屏 汤子瀛 计算机操作系统第三版 西安电子科技大 学出版社 2007 年 2 张尧学 计算机操作系统教程第 2 版 习题与实验指导 2000 年 3 侯俊杰 深入浅出 MFC 第二版 M 华中科技大学出版社 2001 年 4 李晓玲 张俊 姬涛等 程序设计基础 M 中国铁道出版社 2008 371 页 5 张俊 张彦铎 C 面向对象程序设计 M 中国铁道出版社 2008 379 页 6 周爱武 汪海威 李知兵等 计算机操作系统教程 M 清华大学出版社 2011 280 页 7 张尧学 史美玲 张高等 计算机操作系统教程 M 清华大学出版社 2006 302 页 8 张尧学 计算机操作系统教程第 2 版 M 清华大学出版社 习题与实验指 导 2000 年 129 页 15 附录重要代码 include include include include include include define MAX 10 using namespace std define TRUE 1 define FALSE 0 define OK 1 define ERROR 0 define INFEASIBLE 1 define OVERFLOW 2 class Process public 进程名字 int Time 进程需要时间 int leval 进程优先级 typedef struct node char name 5 进程名字 char ProcessName 5 int prio 进程优先级 int timeType 分配的时间片 int time cpu 执行时间 int need 进程执行所需要的时间 char state 进程的状态 struct node next 链表指针 int LeftTime 进程运行一段时间后还需要的时间 PCB int count 0 时间计数变量 typedef struct Queue PCB Rlink 就绪队列中的进程对劣指针 16 int prio 本就绪队列中的优先级 int time 本就绪队列中分配的时间片 PCB front 队头指针 PCB rear 队尾指针 LinkQueue LinkQueue qRun qWait qReady1 qReady2 qReady3 qReady4 对各函数的声明 int InitQueue LinkQueue int creatPro LinkQueue void dealTime void runPro void void ShortTime void run void wait void wake void endPro int InitQueue LinkQueue 存储分配失败 Q front next NULL return OK int EnQueue LinkQueue if p PCB malloc sizeof PCB 存储分配失败 exit OVERFLOW strcpy p name e p time proTime p timeType tType p next NULL Q rear next p Q rear p return OK int DeQueue LinkQueue if Q front Q rear return ERROR p Q front next 17 strcpy e p name Q front next p next if Q rear p Q rear Q front free p return OK int QueueTraverse LinkQueue p Q front next while p printf s t p name printf d p time cout next printf n return OK void print if qRun front qRun rear QueueTraverse qRun 17 5 if qWait front qWait rear QueueTraverse qWait 17 8 if qReady1 front qReady1 rear QueueTraverse qReady1 17 11 if qReady2 front qReady2 rear QueueTraverse qReady2 17 14 if qReady3 front qReady3 rear QueueTraverse qReady3 17 17 if qReady4 front qReady4 rear QueueTraverse qReady4 17 20 int creatPro LinkQueue int proTime PCB p cout 进程名 proName cout 所需时间 proTime if proTime 0 cout name proName p time proTime p timeType 10 进入时间片为 10 的就绪队列 即优先级最高的就绪队列 p next NULL quePro rear next p quePro rear p return OK void dealTime char e 5 int tType qRun front next timeType count qRun front next time if qRun front next time 0 DeQueue qRun e runPro count 0 else if qRun front next timeType count if qRun front next timeType 10 EnQueue qReady2 qRun front next name qRun front next time tType 10 if qRun front next timeType 20 EnQueue qReady3 qRun front next name qRun front next time tType 20 19 if qRun front next timeType 40 EnQueue qReady4 qRun front next name qRun front next time 80 if qRun front next timeType 80 EnQueue qReady4 qRun front next name qRun front next time 80 DeQueue qRun e runPro count 0 void runPro void char e 5 int pTime f1 0 f2 0 f3 0 f4 0 if qReady1 front qReady1 rear pTime qReady1 front next time EnQueue qRun qReady1 front next name pTime qReady1 front next timeType DeQueue qReady1 e f1 1 else if qReady2 front qReady2 rear pTime qReady2 front next time EnQueue qRun qReady2 front next name pTime qReady2 front next timeType DeQueue qReady2 e f2 1 else if qReady3 front qReady3 rear pTime qReady3 front next time EnQueue qRun qReady3 front next name pTime qReady3 front next timeType DeQueue qReady3 e f3 1 else if qReady4 front qReady4 rear 20 pTime qReady4 front next time EnQueue qRun qReady4 front next name pTime qReady4 front next timeType DeQueue qReady4 e f4 1 if f1 0 void run if qRun front qRun rear runPro else dealTime void endPro char e 5 if qRun front qRun rear cout 信息提示 无运行进程 请按 Enter 键运行进程 endl else DeQueue qRun e cout 信息提示 选择菜单功能或按 Enter 键执行进程 next name qRun front next time qRun front next timeType DeQueue qRun e print cout 信息提示 选择菜单功能或按 Enter 键执行进程 endl else cout 信息提示 无运行进程 请输入其他功能选项 next name qWait front next time qWait front next timeType DeQueue qWait e print cout 信息提示 选择菜单功能或按 Enter 键执行进程 endl else cout 信息提示 无等待进程 请输入其他功能选项 next time EnQueue qRun qReady1 front next name pTime qReady1 front next timeType DeQueue qReady1 e void dealTime2 char e 5 qRun front next time if qRun front next time 0 DeQueue qRun e void dealTime3 char e 5 int tType qRun front next timeType count qRun front next time if qRun front next time 0 DeQueue qRun e runPro count 0 else if qRun front next timeType count EnQueue qReady1 qRun front next name qRun front next time tType DeQueue qRun e runPro count 0 char process MAX 进程标识 int arrivetime MAX 达到时间 int servicetime MAX 服务时间 int finishtime MAX 完成时间 23 int init void FCFS int init cout 输入进程队列标识 用单个字母表示一个进程 字母间用 tab 间隔 endl int i 0 while i MAX cin g