操作系统进程控制和调度

操操作作系系统统实实验验报报告告 2012 年年 12 月月 19 日日 一 实验内容 1 自定义进程相关的数据结构 2 利用 MFC 类库中的栈 queue 链表 list 向量 vector 等模板模拟进程控制块队列 进 程控制块优先级队列 统计信息链表及其指令集合 3 利用 MSDN 和 MFC API 编程实现常见的进程控制和调度策略 先来先服务算法 时 间片轮转算法 最高优先权优先调度算法 最短进程优先调度算法 4 测试以上进程调度策略的周转时间 带权周转时间 平均周转时间和平均带权周转时间 并定性评价它们的性能 二 实验要求 用高级语言编写和调试进程调度的模拟程序 以加深对进程调度算法的理解 三 实验步骤 typedef struct PCBNode int ID int Priority int CPUtime int Alltime int Arrivetime int state int counter struct PCBNode next PCB 定义数据结构 PCB run PCB ready PCB over PCB head 定义状态量 int Min PCB head 挑选出队列中的拥有最小 alltime 值的块 返回块号 用于 sjf 算法 PCB p q 用来记录这个块的地址 int min id 记录最小值和块号 p head next if p min p Alltime id p ID while p next if min p next Alltime min p next Alltime id p next ID p p next else p p next return id int Max PCB head 挑选出队列中的拥有最大优先级的块 返回块号 用于 prio 算法 PCB p q 用来记录这个块的地址 int max id 记录最大和块号 p head next if p max p Priority id p ID while p next if maxnext Priority max p next Priority id p next ID p p next else p p next return id PCB CreatPCB int n int i PCB p q head PCB malloc sizeof PCB head next NULL p head for i 1 iID i q CPUtime 0 q Alltime rand 200 q Priority rand 10 q state Ready q Arrivetime 0 p next q p q q next NULL head next Priority 0 return head 创建 pcb 块 void Display PCB head PCB p p head next printf ID Arrivetime CPUtime 已占用 Alltime Priority state n while p printf d p ID printf d p Arrivetime printf d p CPUtime printf d p Alltime printf d p Priority printf d n p state p p next 显示 PCB 块 void FCFS PCB head PCB over PCB p q int j 0 int n 0 s 0 double m ready head p ready next q over while p p state Running ready next p next n p Alltime n p CPUtime p Alltime p Alltime 0 s s n p next NULL q next p p state Over q q next q next NULL p head next j printf 第 d 次执行算法后的就绪队列 n j Display head m double s j printf 完成顺寻为 n Display over printf n printf 每个进程等待的平均时间为 lf n m printf 所有进程等待的总时间为 d s void SJF PCB head PCB over sjf 算法 PCB p q b o b 用来记录该块的地址 int s 记录块号 int m n h 0 d 0 j 0 double f p head next q over o head printf 完成顺寻为 n m p ID n p Alltime s Min head b p next printf d n s while head next while s p ID o p p p next d p Alltime d p CPUtime p Alltime p Alltime 0 h d h b p q next b o next p next p head next b next NULL o head q q next s Min head j printf 第 d 次执行算法后的就绪队列 n j Display head f double h j printf 完成顺寻为 n Display over printf 每个进程等待的平均时间为 lf n f printf 所有进程等待的总时间为 d h void Prio PCB head PCB over PCB p q b o b 用来记录该块的地址 int s 记录块号 int m n h 0 d 0 j 0 double f p head next o head q over printf 当前拥有最大优先级的块号为 n m p ID n p Alltime s Max head b p next printf d n s while head next while s p ID o p p p next d p Alltime d p CPUtime p Alltime p Alltime 0 h d h b p q next b o next p next p head next b next NULL o head q q next s Max head j printf 第 d 次执行算法后的就绪队列 n j Display head f double h j printf 完成顺寻为 n Display over printf 每个进程等待的平均时间为 lf n f printf 所有进程等待的总时间为 d h void RR PCB head PCB over int t int k 时间片轮转法 k 用来记录剩余要执行的进程数目 PCB p q r o tail o 用来记录当前块的地址 int n 0 s 0 f double h f k p head next while p next tail p p p next printf 执行顺序为 n tail p o p 前驱 tail next head next p head next q over while k 0 r head next if p Alltime t 该进程还未执行完成 p Alltime p Alltime t n n t s s n o p printf 执行进程 d p ID printf 该进程的 Alltime 变为 d n p Alltime p p next else 该进程可以完成了 printf 完成进程 d n p ID n n p Alltime s s n p Alltime 0 o next p next q next p q q next