设计1进程调度算法的模拟

山东科技大学学生课程设计 1 设计设计 1 1 进程调度算法的模拟进程调度算法的模拟 一 设计目的一 设计目的 1 通过编程实现进程调度算法的模拟 了解进程调度的过程 理解 进程调度各方法的特点 二 设计要求二 设计要求 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 山东科技大学学生课程设计 2 4 在调度前 系统中拥有的进程数 PCB number 由键盘输入 经初 始化后 所有的进程控制块 PCB 链接成就绪队列 三 设计说明三 设计说明 1 1 FCFSFCFS 模块模块 开始 初始化 PCB 输入进程 信息 FCFS 算法 按照进程先后 顺序输出 RR 算法 按照时间片依次 执行进程 ALLTIME 4 优先级算法 按照优先从 大到小输出 进程执行依 次 P 3 就绪队列中的进程 P 1 SJS 算法 按照 ALLTIME 从小到大依次输出 结束 山东科技大学学生课程设计 3 1 11 1 功能功能 对于先到达的进程优先分配 CPU 按照先来先服务的原则依次执 行各进程 1 21 2 数据结构数据结构 typedef struct PCB int ID 进程优先数 用于标示不同的进程 int Priority 进程优先级 int CPUTime 进程占用的 CPU 时间 CPUtime 进程 每运行一次 累计值等于 4 int ALLTime 进程总共需要运行时间 Alltime int Status 用于表示进程状态 0 就绪态 1 运 行态 2 阻塞态 PCB 1 31 3 算法算法 void FCFS 山东科技大学学生课程设计 4 Node p head next while p NULL cout 执行进程 endl data ID p p next cout endl cout 所有进程都执行完成 next NULL pmin head2 next for p head2 next p NULL p p next if pmin data ALLTime p data ALLTime pmin p 山东科技大学学生课程设计 6 cout 执行剩余区间长度最短的进程 endl data ID for p head2 p NULL p p next if p next pmin p next p next next free pmin printf n printf 所有进程都执行完成 n n 3 3 SearchMaxPRISearchMaxPRI 模块模块 3 13 1 功能功能 按照优先级从高到低依次执行程序 3 23 2 数据结构数据结构 q0 指向 q 的前一个进程 便于删除进程 p 返回优先级最大进程 q 用于遍历链表 山东科技大学学生课程设计 7 3 33 3 算法算法 void SearchMaxPRI int m Node p head next Node q head next Node q0 head while q NULL if q data ALLTime 0 cout 进程已执行完成 endl data ID n q0 next q0 next next free q q q0 next else 山东科技大学学生课程设计 8 if q data Priority p data Priority p q q0 q0 next q q next if n 0 action p 按照轮转的次序分配给每个程序一定的时间执行 执行完成后执 行后面的进程 依次循环执行直到所有进程执行完成 4 24 2 数据结构数据结构 4 34 3 算法算法 void RR int m Node p while head1 next NULL 山东科技大学学生课程设计 9 p head1 next Node prep head1 Node q while p NULL cout 执行进程一个时间片 data ID for q head1 q next NULL q q next if q next p p data ALLTime 4 p data CPUTime 4 if p data ALLTime 0 cout 进程已执行完成 data ID prep next prep next next 山东科技大学学生课程设计 10 free p p prep next else prep prep next p p next cout endl cout 进入下一次轮转 endl cout 所有进程都执行完成 endl 四 运行结果及分析四 运行结果及分析 山东科技大学学生课程设计 11 该程序实现了进程调度的四种不同调度算法下的调度顺序的输出情 况 山东科技大学学生课程设计 12 五 总结五 总结 通过该程序的实现 对进程的调度有了更多的了解 对于不同的系统和系 统目标 通常采用不同的调度算法 有的算法适用于为数众多的短作业调 度 有的算法为系统合理的响应时间提供了保证 调度算法的选择的合适 与否很重要 源代码 include include include include include define TRUE 1 define FALSE 0 define OK 1 typedef struct PCB int ID int Priority int CPUTime 山东科技大学学生课程设计 13 int ALLTime int Status PCB typedef PCB Dt typedef struct Node Dt data struct Node next Node Node head Node malloc sizeof Node Node head1 Node malloc sizeof Node Node head2 Node malloc sizeof Node int n void create int n int i 1 srand int time 0 head next NULL Node q head 山东科技大学学生课程设计 14 cout 优先数 优先级 CPUTime AllTime Status endl while idata ID i p data CPUTime 0 p data Status 0 p data Priority rand 10 1 p data ALLTime rand 8 1 cout data ID data Priority data CPUTime data ALLTime data Status next NULL q next p q q next i Node p0 head1 山东科技大学学生课程设计 15 head1 next NULL for q head next q NULL q q next Node r Node malloc sizeof Node r data ID q data ID r data CPUTime q data CPUTime r data Status q data Status r data Priority q data Priority r data ALLTime q data ALLTime p0 next r r next NULL p0 p0 next Node p1 head2 head2 next NULL for q head next q NULL q q next Node k Node malloc sizeof Node k data ID q data ID 山东科技大学学生课程设计 16 k data CPUTime q data CPUTime k data Status q data Status k data Priority q data Priority k data ALLTime q data ALLTime p1 next k k next NULL p1 p1 next void FCFS Node p head next while p NULL cout 执行进程 endl data ID p p next cout endl 山东科技大学学生课程设计 17 cout 所有进程都执行完成 next NULL pmin head2 next for p head2 next p NULL p p next if pmin data ALLTime p data ALLTime pmin p cout 执行剩余区间长度最短的进程 endl data ID for p head2 p NULL p p next if p next pmin 山东科技大学学生课程设计 18 p next p next next free pmin cout endl cout 所有进程都执行完成 next while q NULL cout data ID 执行一个时间片的进程 data Priority q data Priority 1 else 山东科技大学学生课程设计 19 q data Priority q data Priority 3 if q data ALLTime 4 q data ALLTime 4 else q data ALLTime 0 q data Status 1 q q next void SearchMaxPRI int m Node p head next Node q head next Node q0 head while q NULL 山东科技大学学生课程设计 20 if q data ALLTime 0 cout data ID 进程已执行完成 next q0 next next free q q q0 next else if q data Priority p data Priority p q q0 q0 next q q next if n 0 action p 山东科技大学学生课程设计 21 void RR int m Node p while head1 next NULL p head1 next Node prep head1 Node q while p NULL cout data ID 执行进程一个时间片 next NULL q q next if q next p p data ALLTime 4 山东科技大学学生课程设计 22 p data CPUTime 4 if p data ALLTime 0 cout data ID 进程已执行完成 next prep next next free p p prep next else prep prep next p p next cout endl cout 进入下一次轮转 endl 山东科技大学学生课程设计 23 cout 所有进程都执行完成 endl int main cout 请输入系统进程数 n int m n if n 0 cout 此时没有就绪进程 endl else create n cout endl cout 先来先服务调度 endl FCFS cout endl cout 最短作业优先调度 endl SJF 山东科技大学学生课程设计 24 cout endl cout 优先权的分时调度 next NULL SearchMaxPRI m cout 所有进程都执行完成 endl cout endl cout 轮转法调度 endl RR m 山东科技大学学生课程设计 25 设计设计 2 2 模拟银行家算法模拟银行家算法 一 设计目的一 设计目的 1 通过对银行家算法的模拟 理解银行家算法的实现过程 了解系 统解决死锁的方法 二 设计要求二 设计要求 1 编程序模拟银行家算法 2 能体现算法的全过程 三 设计说明三 设计说明 山东科技大学学生课程设计 26 1 1 bankbank 模块模块 1 11 1 功能功能 利用银行家算法 给系统分配资源 避免死锁 1 21 2 数据结构数据结构 Typedef struct RESOURCE int available R 系统可用资源数 int allocation W R M 个进程已经得到 N 类资源的资源量 int need W R M 个进程还需要 N 类资源的资源量 int request R 请求资源个数 RESOURCE 1 31 3 算法算法 int i 0 j 0 char choice Y while choice Y choice y i 1 while i M 山东科技大学学生课程设计 27 cout endl i if i M cout 进程号不存在 重新输入 endl cout 请输入进程 i 申请各类资源的数量 endl for j 0 j N j cout 资源 j request j if request j need i j cout endl 进程 i 申请的资源数大于进程 i 还需要 j 类资源的数量 cout 若继续执行系统将处于不安全状态 available j cout endl 进程 i 申请的资源数大于系统 可用 j 类资源的数量 cout 继续执行系统将处于不安全状态 endl choice N break if choice Y choice y distribute i if check restore i print 山东科技大学学生课程设计 29 else print else cout endl cout choice 2 2 checkcheck 模块模块 2 12 1 功能功能 检查资源分配后系统是否处于安全状态 2 22 2 数据结构数据结构 Typedef struct RESOURCE int available R 系统可用资源数 int allocation W R M 个进程已经得到 N 类资源的资源量 int need W R M 个进程还需要 N 类资源的资源量 int request R 请求资源个数 山东科技大学学生课程设计 30 RESOURCE 2 32 3 算法算法 int work R finish W int i j for j 0 j N j work j available j for i 0 i M i finish i FALSE for i 0 i M i for j 0 j N j if finish i FALSE finish i TRUE 山东科技大学学生课程设计 31 for i 0 i M i if finish i FALSE cout endl cout 系统不安全 资源申请失败 endl cout endl return 1 else cout 系统安全 分配成功 endl return 0 四 运行结果及分析四 运行结果及分析 山东科技大学学生课程设计 32 山东科技大学学生课程设计 33 通过实验结果可知银行家算法中 当进程申请的资源大于声明所需的 最大资源或者大于系统当前可用的资源时 系统将处于不安全状态 资源 分配失败 从而防止了死锁的产生 五 总结五 总结 通过该算法的模拟可知银行家算法是一种最有代表性的避免死锁的算 法 在避免死锁方法中允许进程动态地申请资源 但系统在进行资源分配 之前 应先计算此次分配资源的安全性 若分配不会导致系统进入不安全 状态 则分配 否则等待 为实现银行家算法 系统必须设置若干数据结 构 源代码 山东科技大学学生课程设计 34 include include include define FALSE 0 define TRUE 1 define W 10 define R 10 int allresource W int max W R int available R int allocation W R int need W R int request R int M int N void print int i j cout 各种资源总量 endl 山东科技大学学生课程设计 35 for j 0 j N j cout 资源 j allresource j endl cout 目前各种资源可利用数量 endl for j 0 j N j cout 资源 j available j endl cout 各进程还需要的资源数量 endl endl cout resourceA resourceB resourceC endl for i 0 i M i cout 进程 i for j 0 j N j cout need i j cout endl cout 各进程已经得到的资源量 endl endl cout resourceA resourceB resourceC endl for i 0 i M i 山东科技大学学生课程设计 36 cout 进程 i for j 0 j N j cout allocation i j cout endl void distribute int l 分配资源 int j for j 0 j N j available j available j request j allocation l j allocation l j request j need l j need l j request j void restore int l 恢复资源 int j 山东科技大学学生课程设计 37 for j 0 j N j available j available j request j allocation l j allocation l j request j need l j need l j request j int check int work R finish W int i j for j 0 j N j work j available j for i 0 i M i finish i FALSE for i 0 i M i for j 0 j N j if finish i FALSE finish i TRUE for i 0 i M i if finish i FALSE cout endl cout 系统不安全 资源申请失败 endl cout endl return 1 else cout 系统安全 分配成功 endl return 0 山东科技大学学生课程设计 39 void bank int i 0 j 0 char choice Y while choice Y choice y i 1 while i M cout endl i if i M cout 进程号不存在 重新输入 endl cout 请输入进程 i 申请各类资源的数量 endl for j 0 j N j cout 资源 j request j if request j need i j cout endl 进程 i 申请的资源数大于进程 i 还需 要 j 类资源的数量 cout 若继续执行系统将处于不安全状态 available j cout endl 进程 i 申请的资源数大于系统可用 j 类资源的数量 cout 继续执行系统将处于不安全状态 endl choice N break 山东科技大学学生课程设计 41 if choice Y choice y distribute i if check restore i print else print else cout endl cout choice int main 山东科技大学学生课程设计 42 int i 0 j 0 p cout t 银行家算法演示 endl cout endl M cout N cout 请输入各类资源总数 for i 0 i allresource i cout 输入各进程所需要的各类资源的最大数量 endl for i 0 i M i for j 0 j max i j 山东科技大学学生课程设计 43 if max i j allresource j cout endl 占有资源超过了声明的该资源总数 请重新输入 allresource j cout 输入各进程已经占据的各类资源的数量 endl for i 0 i M i for j 0 j allocation i j if allocation i j max i j cout endl 占有资源超过了声明的最大资源 请重新输入 max i j 山东科技大学学生课程设计 44 for j 0 j N j p allresource j for i 0 i M i p p allocation i j available j p if available j 0 available j 0 for i 0 i M i for j 0 j N j need i j max i j allocation i j print bank 山东科技大学学生课程设计 45 设计设计 3 3 磁盘调度算法磁盘调度算法 一 设计目的一 设计目的 1 通过对磁盘调度算法的实现 了解磁盘调度的算法已经其寻道时 间 二 设计要求二 设计要求 编程序实现下述磁盘调度算法 并求出每种算法的平均寻道长度 1 先来先服务算法 FCFS 2 最短寻道时间优先算法 SSTF 3 扫描算法 SCAN 4 循环扫描算法 CSCAN 三 设计说明三 设计说明 1 1 FCFSFCFS 模块模块 1 11 1 功能功能 山东科技大学学生课程设计 46 按先来先服务的策略输出磁盘请求序列 求平均寻道长度 1 21 2 数据结构数据结构 1 31 3 算法算法 void FCFS int cidao int m int now sum 0 j i a char str 100 float ave cout 磁盘请求序列为 for i 0 i m i cout cidao i 山东科技大学学生课程设计 47 cout endl cout str a check str if a 0 cout 输入数据的类型错误 请重新输入 endl goto B else now change str a sum abs cidao 0 now cout 磁盘扫描序列为 for i 0 i m i cout cidao i for i 0 j 1 j m i j 山东科技大学学生课程设计 48 sum abs cidao j cidao i ave float sum float m cout endl cout 平均寻道长度 ave endl 2 2 SSTFSSTF 模块模块 2 12 1 功能功能 根据前磁道在已排的序列中的位置 选择扫描的顺序 求出平均 寻道长度 输出移动的平均磁道数 2 22 2 数据结构数据结构 山东科技大学学生课程设计 49 2 32 3 算法算法 void SSTF int cidao int m int k 1 now l r i j sum 0 a char str 100 float ave cidao order cidao m cout str a check str if a 0 山东科技大学学生课程设计 50 cout 输入数据的类型错误 请重新输入 endl goto C else now change str a if cidao m 1 now cout 0 i cout cidao i now cout 磁盘扫描序列为 for i 0 i m i cout cidao i cidao 0 while cidao k 0 sum now cidao l now cidao l l l 1 山东科技大学学生课程设计 52 else cout cidao r sum cidao r now now cidao r r r 1 if l 1 for j r j m j cout cidao j 0 j 山东科技大学学生课程设计 53 cout cidao j sum cidao m 1 cidao 0 ave float sum float m cout endl cout 平均寻道长度 ave endl 3 3 SCANSCAN 模块模块 3 13 1 功能功能 选择移动臂的移动方向 根据当前磁道在已排的序列中的位置 选择扫描的顺序 求出平均寻道长度 输出移动的平均磁道数 3 23 2 数据结构数据结构 山东科技大学学生课程设计 54 3 33 3 算法算法 void SCAN int cidao int m int k 1 now l r d i j sum 0 a char str 100 float ave cidao order cidao m 山东科技大学学生课程设计 55 cout str a check str if a 0 cout 输入数据的类型错误 请重新输入 endl goto D else now change str a if cidao m 1 now cout 0 i cout cidao i now 山东科技大学学生课程设计 56 cout 磁盘扫描序列为 for i 0 i m i cout cidao i cidao 0 l k 1 r k cout d if d 0 cout 0 j cout cidao j for j r j m j cout cidao j sum now 2 cidao 0 cidao m 1 else cout 磁盘扫描序列为 for j r j m j cout cidao j 0 j 山东科技大学学生课程设计 58 cout cidao j sum now cidao 0 2 cidao m 1 ave float sum float m cout endl cout 平均寻道长度 ave endl 4 4 CSCANCSCAN 模块模块 4 14 1 功能功能 规定移动臂单向反复的从内向外移动 根据当前磁道在已排的序 列中的位置 选择扫描的顺序 求出平均寻道长度 输出移动的 平均磁道数 4 24 2 数据结构数据结构 山东科技大学学生课程设计 59 4 34 3 算法算法 void CSCAN int cidao int m int k 1 now l r i j sum 0 a char str 100 float ave cidao order cidao m cout str a check str if a 0 cout 输入数据的类型错误 请重新输入 endl goto E else now change str a if cidao m 1 now cout 磁盘扫描序列为 for i 0 i m i cout cidao i now cout 磁盘扫描序列为 for i 0 i m i 山东科技大学学生课程设计 61 cout cidao i cidao 0 while cidao k now k l k 1 r k for j r j m j cout cidao j for j 0 j r j cout cidao j 山东科技大学学生课程设计 62 sum 2 cidao m 1 cidao l now 2 cidao 0 ave float sum float m cout endl cout 平均寻道长度 ave endl 四 运行结果及分析四 运行结果及分析 山东科技大学学生课程设计 63 从实验结果可知各种磁盘调度 山东科技大学学生课程设计 64 的磁道顺序以及寻道时间 由此可以比较出各种调度算法的优缺点 五 总结五 总结 通过改程序对操作系统的基础知识了解得更透彻了 同时对磁盘调度 的四种算法 先来先服务算法 FCFS 最短寻道时间优先算法 SSTF 扫描算法 SCAN 循环扫描算法 CSCAN 有了更深刻的理解和掌握 使 我能够为磁盘调度选择适当的算法 提高 CPU 工作效率 源代码 include include include include define maxsize 1000 int bubble int cidao int m int i j int temp for i 0 i m i for j i 1 jcidao j temp cidao i cidao i cidao j cidao j temp cout 排序后的磁盘序列为 for i 0 i m i cout cidao i cout endl return cidao void FCFS int cidao int m int now sum 0 j i float ave 山东科技大学学生课程设计 66 cout 磁盘请求序列为 for i 0 i m i cout cidao i cout endl cout now sum abs cidao 0 now cout 磁盘扫描序列为 for i 0 i m i cout cidao i for i 0 j 1 j m i j sum abs cidao j cidao i ave float sum float m 山东科技大学学生课程设计 67 cout endl cout 平均寻道长度 ave endl void SSTF int cidao int m int k 1 now l r i j sum 0 float ave cidao bubble cidao m cout now if cidao m 1 now cout 0 i cout cidao i now 山东科技大学学生课程设计 68 cout 磁盘扫描序列为 for i 0 i m i cout cidao i cidao 0 while cidao k 0 sum now cidao l now cidao l l l 1 else cout cidao r sum cidao r now now cidao r r r 1 if l 1 for j r j m j cout cidao j 0 j cout cidao j sum cidao m 1 cidao