进程调度算法.doc

1 课程设计说明书 设计名称 进程调度算法设计 题 目 进程调度算法设计 学生姓名 专 业 计算机应用技术 班 级 09 计算机专科 学 号 309104 指导教师 日 期 2011 年 5 月 5 日 2 课程设计任务书 计算机应用技术 专业 09 年级 专科 班 一 一 设计题目设计题目 进程调度算法的设计 二 二 主要内容主要内容 1 设计进程控制块 PCB 表结构 分别适用于优先数调度算法和循环轮转调 度算法 2 建立进程就绪队列 对两种不同算法编制入链子程序 3 编制两种进程调度算法 1 优先数调度 2 循环轮转调度 开发环境 VC 语言的编程环境 三 三 具体要求具体要求 1 本程序用两种算法对五个进程进行调度 每个进程可有三个状态 并假 设初始状态为就绪状态 2 为了便于处理 程序中的某进程运行时间以时间片为单位计算 各进程 的优先数或轮转时间数以及进程需运行的时间片数的初始值均由用户给 定 3 在优先数算法中 优先数的值为 50 与运行时间的差值 即 P TIME process needtime 进程每执行一次 优先数减 3 CPU 时间片数加 1 进程还需要的时间片数减 1 在轮转算法中 采用固定时间片 即 每执行一次进程 该进程的执行时间片数为已执行了 2 个单位 这时 CPU 时间片数加 2 进程还需要的时间片数减 2 并排列到就绪队列的 尾上 4 对于遇到优先数一致的情况 采用 FIFO 策略解决 开发环境 VC 语言的编程环境 四 进度安排进度安排 1 资料查找 系统分析 数据流程分析 概要设计 2 系统详细设计 功能设计 3 3 算法实现 编程调试 4 资料整理 课程设计说明书编写 五 五 完成后应上交的材料完成后应上交的材料 1 课程设计说明书 2 相关源程序文件 六 六 总评成绩总评成绩 指导教师 签名日期 年 月 日 系 主 任 审核日期 年 月 日 4 目目 录录 一 设计目的 4 二 设计内容 4 三 设计原理 5 3 1 优先数调度算法 5 3 2 循环轮转调度算法 5 四 设计步骤 5 4 1 任务分析 5 4 2 概要设计 6 4 3 详细设计 6 4 4 流程图 7 4 5 源程序 7 4 6 程序测试数据及结果 13 4 6 1 程序测试数据 13 4 6 2 运用优先数调度算法的执行结果 如下图 13 4 6 3 运用循环轮转调度算法的执行结果 如下图 14 五 设计总结 18 六 参考文献 18 5 一一 设计目的设计目的 通过这次课程设计 加深理解有关进程控制块 进程队列的概念 并体会 和了解优先数和循环轮转调度算法的具体实施办法 培养程序设计的方法和技 巧 提高编制清晰 合理 可读性好的系统程序的能力 同时加深对操作系统 课程的理解 二二 设计内容设计内容 1 用语言来实现对 n 个进程采用不同调度算法的进程调度 2 每个用来标识进程的进程控制块 PCB 用结构来描述 包括以下字段 1 进程优先数 ID 其中 0 为闲逛进程 用户进程的标识数为 1 2 3 2 进程优先级 Priority 闲逛进程 idle 的优先级为 0 用户进程的 优先级大于 0 且随机产生 优先数越大 优先级越高 3 进程占用的 CPU 时间 CPUtime 进程每运行一次 累计值等于 4 4 进程总共需要运行时间 Alltime 利用随机函数产生 5 进程状态 0 就绪态 1 运行态 2 阻塞态 6 队列指针 next 用来将多个进程控制块 PCB 链接为队列 3 优先数改变的原则 1 进程在就绪队列中每呆一个时间片 优先数增加 1 2 进程每运行一个时间片 优先数减 3 4 在调度前 系统中拥有的进程数 PCB number 由键盘输入 经初始化后 所有的进程控制块 PCB 链接成就绪队列 三三 设计原理设计原理 3 1 优先数调度算法优先数调度算法 对每个进程确定一个优先数 该算法总是让优先数最高的进程先使用处理 器 对具有相同优先数的进程 再来采用先来先服务的次序分配处理器 系统 常与任务的紧迫性和系统效率等因素确定进程的优先数 进程的优先数可以固 定的 也可随进程执行过程动态变化 一个高优先数进程占用处理器后 系统 处理该进程时有两种算法 一是 非抢占式 另一种是 可抢占式 前者是 次进程占用处理器后一直运行到结束 除非本身主动让出处理器 后者则是严 格保证在任何时刻总是让优先数最高的进程在处理器上运行 3 2 循环轮转调度算法循环轮转调度算法 循环轮转调度算法的具体原理是 每个进程被分配一个时间片 即该进程 允许运行的时间 就绪的进程都存放在一个就绪链表中 队首的进程将获得时 6 间片 如果在时间片结束时进程还在运行 则 CPU 将剥夺并分配给下一个进程 调度程序所要做的就是维护一张就绪进程列表 当进程用完它的时间片后 它 被移到队列的末尾 四 设计步骤四 设计步骤 4 1 任务分析任务分析 1 PCB 结构通常包括以下信息 进程名 进程优先数 轮转时间片 进程 已占用的 CPU 时间 进程还需要的 CPU 时间 进程的状态 当前队列指针等 可根据实验的不同 PCB 结构的内容可以作适当的增删 2 本程序用两种算法对五个进程进行调度 每个进程可有三个状态 就绪 执行 完成 并假设初始状态为就绪状态 3 为了便于处理 程序中的某进程运行时间以时间片为单位计算 各进程 的优先数或轮转时间数以及进程需运行的时间片数的初始值均由用户给定 4 在优先数算法中 优先数可以先取值为一个常数减去进程所需要的时间 片数目 进程每执行一次 优先数减 3 CPU 时间片数加 1 进程还需要的时间 片数减 1 在轮转算法中 采用固定时间片 即 每执行一次进程 该进程的 执行时间片数为已执行了 2 个单位 这时 CPU 时间片数加 2 进程还需要的 时间片数减 2 并排列到就绪队列的尾上 5 对于遇到优先数一致的情况 采用 FIFO 策略解决 4 2 概要设计概要设计 1 本程序用两种算法对五个进程进行调度 每个进程可有三个状态 并假 设初始状态为就绪状态 2 为了便于处理 程序中的某进程运行时间以时间片为单位计算 各进程 的优先数或轮转时间数以及进程需运行的时间片数的初始值均由用户给定 3 在优先数算法中 优先数的值为 50 与运行时间的差值 即 P TIME process needtime 进程每执行一次 优先数减 3 CPU 时间片数加 1 进程 还需要的时间片数减 1 在轮转算法中 采用固定时间片 即 每执行一次进 程 该进程的执行时间片数为已执行了 2 个单位 这时 CPU 时间片数加 2 进程还需要的时间片数减 2 并排列到就绪队列的尾上 4 对于遇到优先数一致的情况 采用 FIFO 策略解决 4 3 详细设计详细设计 1 struct pcb 定义 pcb 块 2 Void display 显示结果信息函数 3 int process finish pcb q 进程完成标示 4 void display round 显示循环轮转调度算法运行结果 5 priority cal 优先数调度算法 7 6 void cpu round 处理器的工作状态 4 4 流程图流程图 开始 生成并按生成次序 排列进程控制块链 链首进程投入运行 时间片到 进程时 间片减 1 优先级减 3 撤销该进程 运行进程退出 取 链首进程投入运行 时间片为 0 优先级大于队列中优先 级最高的进程 进程队列 为空 结束 4 5 源程序源程序 源程序如下 8 include include include include include include define P NUM 5 define P TIME 50 enum state ready execute block finish struct pcb char name 4 int priority int cputime int needtime int count int round state process pcb next pcb get process pcb get process pcb q pcb t pcb p int i 0 cout input name and time endl while i q name cin q needtime q cputime 0 q priority P TIME q needtime q process ready q next NULL if i 0 p q t q else t next q t q i while return p void display pcb p 9 cout name cputime needtime priority state endl while p cout name cout cout cputime cout cout needtime cout cout priority cout process case ready cout ready endl break case execute cout execute endl break case block cout block endl break case finish cout finish next int process finish pcb q int bl 1 while bl q q next return bl void cpuexe pcb q pcb t q int tp 0 while q if q process finish q process ready if q needtime 0 q process finish if tppriority t q q q next 10 if t needtime 0 t priority 3 t needtime t process execute t cputime void priority cal pcb p system cls p get process int cpu 0 system cls while process finish p cpu cout cputime cpu endl cpuexe p display p Sleep 100 getch system cls printf All processes have finished press any key to exit getch void display menu cout CHOOSE THE ALGORITHM endl cout 1 PRIORITY endl cout 2 ROUNDROBIN endl cout 3 EXIT endl pcb get process round pcb q pcb t pcb p int i 0 cout input name and time endl while i q name cin q needtime q cputime 0 q round 0 q count 0 11 q process ready q next NULL if i 0 p q t q else t next q t q i while return p void cpu round pcb q q cputime 2 q needtime 2 if q needtimeneedtime 0 q count q round q process execute pcb get next pcb k pcb head pcb t t k do t t next while t if t NULL t head while t next k return t void set state pcb p while p if p needtime 0 p process finish if p process execute p process ready 12 p p next void display round pcb p cout NAME CPUTIME NEEDTIME COUNT ROUND STATE endl while p cout name cout cout cputime cout cout needtime cout cout count cout cout round cout process case ready cout ready endl break case execute cout execute endl break case finish cout finish next void round cal pcb p pcb r system cls p get process round int cpu 0 system cls r p while process finish p cpu 2 cpu round r r get next r p cout cpu cpu endl display round p set state p Sleep 100 getch system cls void main 13 display menu int k scanf d switch k case 1 priority cal break case