进程调度算法__操作系统课程设计

北京大学操作系统课程设计 计算机科学与应用系计算机科学与应用系 操作系统原理操作系统原理 课程设计报告课程设计报告 题目 进程调度算法 班级 软 0742 姓名 Darren 专业 计算机科学与技术 指导老师 XXXX 北京大学操作系统课程设计 2 进程调度算法 一 实验目的 通过优先权法与轮转调度算法的模拟加深对进程概念和进程调度过程的理 解 掌握进程状态之间的切换 同时掌握进程调度算法的实现方法和技巧 二 实验内容 1 用 C 语言或 C 语言来实现对 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 进程每运行一个时间片 优先数增加 1 4 在调度前 系统中拥有的进程数 PCB number 有键盘输入 进初始化后 所有的进程控制块 PCB 连接成就绪队列 5 为了清楚的观察诸进程的调度过程 程序应将每个时间片内的进程的情 况显示出来 三 实验步骤 1 进程管理程序调式好后 运行进程管理程序 北京大学操作系统课程设计 3 Y N N Y Y N N Y Y N N Y ready queue 是否为 空 将 Running 从 ready queue 中删除 再将 running 加入 block queueb 将其从 blick queuek 队列是中删除 再将其加入 ready queuek 输入开始进程数 n 随机 对 block queue 中的进程 PCB 询问是否要唤醒 创建新进程并加入到 ready queue 中 Running 逐个将 redy pc 中的 PCB 创建 n 个 PCB 并加入 ready queue 中 处理完了吗 阻塞 Running 是否要唤醒 是否创建新 PCB Running idle 更新新进程就绪队列进程优先数 优先数加 1 Running id 北京大学操作系统课程设计 4 2 优先权调度 1 输入 1 选择优先权调度算法模拟 2 输入开始进程个数 n 创建 n 个 PCB 并加入就绪队列 ready queue 中 3 就绪队列 ready queue 不为空 调度就绪队列中第一个进程运行 否 则 从闲逛队列 idleprocess 中调度闲逛进程运行 4 在运行过程中 当遇到阻塞 则该进程插入到阻塞队列 block queue 中 且将该进程从 ready queue 中删除 5 如果运行时间 CPUtime 大于等于 Alltime 该进程运行完毕 释放该 进程 否则插入到就绪队列中 6 更新就绪队列中的优先级数 7 随机对阻塞队列 block queue 中的进程 PCB 询问是否要唤醒 唤醒 即从唤醒队列中选择第一个进程 且插入就绪队列中 阻塞队列中没有阻塞进 程返回 8 重复上述步骤 直到本次调度结束 北京大学操作系统课程设计 5 3 轮转调度 1 输入 2 选择优先权调度算法模拟 2 输入开始进程个数 n 创建 n 个 PCB 并加入就绪队列 ready queue 中 3 就绪队列 ready queue 不为空 调度就绪队列中第一个进程运行 否 则 从闲逛队列 idleprocess 中调度闲逛进程运行 4 在运行过程中 当遇到阻塞 则该进程插入到阻塞队列 block queue 中 且将该进程从 ready queue 中删除 5 如果运行时间 CPUtime 大于等于 Alltime 该进程运行完毕 释放该 进程 否则插入到就绪队列中 6 随机对阻塞队列 block queue 中的进程 PCB 询问是否要唤醒 唤醒 即从唤醒队列中选择第一个进程 且插入就绪队列中 阻塞队列中没有阻塞进 程返回 7 如果时间到 本次调度结束 否则重复上述步骤 直到本次调度结束 北京大学操作系统课程设计 6 Y N ready queue 是否为 空 输入开始进程数 n Running 逐个将 redy pc 中的 PCB 创建 n 个 PCB 并加入 ready queue 中 Running id 北京大学操作系统课程设计 7 N Y Y N N Y Y N N Y Y 四 实验过程中遇到的问题及解决方案 1 请仔细阅读动态优先权的进程调度算法的模拟实现代码 说明该算法与 教材中介绍的算法做了哪些简单化处理 优先权模拟时优先权是随机产生 在实际的系统中 系统进程的优先权高 于一般用户进程的优先权 2 为什么对进程的优先数可按上述原则进行修改 最高优先权调度算法仅照顾了优先权高的进程 当不断有优先权高的进程 需调度时 而优先权低的进程将很难得到处理机的调度 所以进程在就绪队列 中每呆一个时间片 优先数增加 1 使优先权低的进程不总是忙等 3 请给出设计实现的轮转发进程调度算法的设计思想 时间轮转调度算法 系统将所有的就像进程按先来先服务的原则 排成一 个队列 每次调度时 把 CPU 分配给首进程 并令其执行一个时间片 当执行 将 Running 从 ready queue 中删除 再将 running 加入 block queueb 将其从 blick queuek 队列是中删除 再将其加入 ready queuek 随机 对 block queue 中的进程 PCB 询问是否要唤醒 创建新进程并加入到 ready queue 中 处理完了吗 阻塞 Running 是否要唤醒 是否创建新 PCB Running idle 北京大学操作系统课程设计 8 的时间片用完时 发出中断请求 调度程序便据此信号来停止该进程的执行 并将其送到就绪队列的末尾 如此反复 就可以保证就绪队列中的所有进程在 一个给定的时间内 均能获得一时间片处理机执行时间 4 在实际的进程调度中 除了按调度算法选择下一个执行的进程外 还应 处理哪些工作 最高优先权调度算法 常用于批处理系统中 作为作业调度算法 也作为 多种操作系统中的进程调度算法 还可以用于实时系统中 时间轮转调度算法 一般用于分时系统中 五 课程设计总结 1 当把该算法用于作业调度时 系统将从后备队列中选择若干个优先权最 高的作业 装入内存 当用于进程调度算法时 该算法是把处理及分配给就绪 队列中优先权最高的进程 2 当系统空闲 就绪队列为空 时 系统运行闲逛进程 否则运行其他进 程 发生变迁 就绪 运行 3 在运行进程 包括闲逛进程 的过程中 可能发生变迁 2 运行 阻塞 即将运行进程插入到阻塞队列 闲逛进程不能不被阻塞 可能有其他的进程创 建 PCB 还可能唤醒阻塞队列中的某些进程 PCB 发生变迁 3 阻塞 就绪 即从阻塞队列中插入就绪队列中 4 时间片运行结束后 若进程累积占用 CPU 时间大于等于进程需要运行时 间 则进程执行结束 释放其 PCB 若进程累积占用 CPU 时间小于进程需要运 行时间 发生变迁 4 运行 就绪 即将当前运行的进程插入就绪队列中 附 进程调度算法代码 process cpp Defines the entry point for the console application include stdafx h include stdio h include stdlib h include iostream h define NULL 0 define false 0 define true 1 bool state 0 北京大学操作系统课程设计 9 struct PCB int ID int priority int CPUtime int ALLtime int State PCB next void init 产生 idle 进程 输入用户进程数目 调用 insert void print PCB pcb 输出进程属性信息 void print init PCB pcb 输出所有 PCB 的初始值 void insert 生成进程属性信息 插入进程就绪队列 void Run priority PCB pcb 运行进程 随机阻塞进程 产生新进程 插入就绪队列 唤醒阻塞进程 void block PCB pcb 调用 destroy 将进程插入阻塞队列 void wakeup 唤醒进程 插入就绪队列 void proc priority 优先权调度算法模拟 void Run loop PCB pcb void proc loop 轮转法调度算法模拟 void update PCB pcb 更新进程信息 void pushback queue PCB queue PCB item 将 item 插入到队列的尾部 void insert queue PCB queue PCB item 将 item 插入到队列中 使得插入后 队列 中按照优先级从高到低有序 void sort queue PCB 对 queue 中的结点进行排序 按照优先级从大到小 PCB ready queue block queue idleprocess 就绪队列 阻塞队列及闲逛进程指针变 量 int main int argc char argv int i 0 while 1 cout PROCESS cout n Please select a num in 1 2 0 cout n 1 priority cout n 2 loop cout n 0 exit n cout i while i 北京大学操作系统课程设计 10 if i 1 cout n This is a example for priority processing n init proc priority else if i 2 cout n This is a example for round robin processing n init proc loop else cout Please select a num in 1 2 0 n cout i return 0 输出所有 PCB 的初始值 void print init PCB pcb PCB temp pcb next cout nID priority CPUtime ALLtime State while temp NULL cout n ID priority CPUtime ALLtime if temp State 0 cout State 1 cout running else cout next 输出进程属性信息 void print PCB pcb 北京大学操作系统课程设计 11 PCB temp temp pcb if pcb ID 0 cout nThe idle peocess id running else cout n ID priority CPUtime ALLtime if temp State 0 cout State 1 cout running else cout next while p 0 p p next if p 0 item next 0 q next item else item next p q next item 将 item 插入到阻塞队列的尾部 void pushback queue PCB queue PCB item PCB p q q queue p q next while p 0 北京大学操作系统课程设计 12 q p p p next item next q next q next item 对 queue 中的结点进行排序 按照优先级从大到小 void sort queue PCB temp next 0 while queue next PCB p p queue next queue next p next insert queue temp p queue next temp next delete temp 生成进程属性信息 插入进程就绪队列 显示进程信息 void insert PCB newp 0 static long id 0 newp new PCB id newp ID id newp State 0 newp CPUtime 0 newp priority rand 3 1 newp ALLtime rand 3 1 newp next NULL pushback queue ready queue newp print newp cout ready n 生成 n 个进程属性信息 插入进程就绪队列 显示进程信息 void insert int n for int i 0 inext 0 ready queue new PCB ready queue next 0 int i 0 pcb number 1 闲逛进程放入就绪队列 idleprocess NULL idleprocess PCB malloc sizeof PCB idleprocess ID 0 idleprocess State 0 idleprocess CPUtime 0 idleprocess priority 0 idleprocess ALLtime 0 idleprocess next NULL idleprocess next ready queue next 闲逛进程放入就绪队列 ready queue next idleprocess 也可以假定初始时系统中只有一个 idle 进程 输入初始进程的个数 while pcb number 0 cout pcb number cout nID priority CPUtime ALLtime State n for i pcb number i insert cout 就绪队列初始化成功 endl print init ready queue cout State 2 pcb CPUtime 2 if pcb CPUtimeCPUtime 2 北京大学操作系统课程设计 14 cout nThe process no ID is blocked print pcb cout blocked n pcb next block queue next block queue next pcb 更新进程信息 就绪队列中进程的优先级均增加 1 void update PCB pcb PCB temp pcb next while temp temp temp next 唤醒进程 插入就绪队列 void wakeup if block queue next 0 此时没有阻塞的进程 无所谓的唤醒 return PCB q p while true q block queue p q next while p p p next if p 0 q next p next break p State 0 cout endl print p cout ready ID 0 insert queue ready queue pcb print pcb cout running n else pcb State 1 pcb CPUtime 4 pcb priority pcb priority 3 每运行一个时间片 其优先数减 3 if pcb priority priority 1 print pcb printf 变迁 1 ready running n if rand 3 1 PCB 不是闲逛进程 满足条件侧阻塞此进程 if pcb CPUtime 2ALLtime block pcb else 已执行完毕 应该销毁进程 cout n cout The process no ID Destroy CPUtime pcb ALLtime 释放 cout n cout The process no ID Destrory ID 0 insert queue ready queue pcb print pcb cout running n else pcb State 1 pcb CPUtime pcb ALLtime print pcb printf 变迁 1 ready running n if rand 3 1 PCB 不是闲逛进程 满足条件侧阻塞此进程 state 1 block pcb else cout n cout The process no ID Destrory endl delete pcb if rand 5 1 insert 3 if rand 7 1 北京大学操作系统课程设计 17 wakeup 优先权调度算法模拟 void proc priority sort queue ready queue PCB temp 0 running 0 int times 0 cout 调度前 print init ready queue for timesnext ready queue next running next cout endl cout 调度开始 endl Run priority running cout n 本次调度结束 endl 轮转调度算法模拟 void proc loop PCB temp 0 running 0 int times 10 cout next ready queue next running next cout 0 times times running ALLtime 每次运行一个进程减去 ALLtime if times 0 Run loop running else if state 如果运行时被阻塞 则运行 2 个时间单位 times times 2 state 0 北京大学操作系统课程设计 18 cout 5487584574389574 fgfgfgfgf gfgfg38954378954375894378954375 else pushback queue block queue running 时间不过 则阻塞该进程 放到阻塞队列 else if times 0 cout n 本次调度时间片到 break cout n 本次调度结束 endl 北京大学操作系统课程设计 19 Linux 进程管理 一 实验目的 进程描述符即为进程控制块 Linux 的进程控制块由 task struct 结果表 示 其结构在 sched h 里定义 主要进城标识 调度相关信息 进程虚拟空间 信息 文件相关信息 信号处理信息 记账信息及统计信息 描述进程间关系 的指针等 加深对进程概念的理解 明确进程和程序的区别 进一步认识并发的实质 通过分析进程争用资源的现象 学习解决进程互斥的方法 了解 Linux 系统中 进程通信的基本原理 北京大学操作系统课程设计 20 二 实验内容 阅读 Linux 的 sched h 源码文件 加深对进程管理概念的理解 阅读 Linux 的 fork c 源码文件 分析进程的创建过程 学习 Linux 系统进行 C 程序的编译调式方法 GCC 是 GNU project Cand C compiler 宿写 是 C C 语言的编译器 因其后来可以多种语言的开发 现 在改变为 GNC Compiler Collection 使用 gcc hello c o hello 可以生成执 行的文件 hello Linux 的进程状态有五种 TASK RUNNING 运行 无论进程是否正在占用 CPU 只要具备运行条件 都处于该状态 Linux 把处于该状态的所有 PCB 组织成一个可运行队列 run queue 调度程序从这个队列只中选择进程运行 TASK INTERRUPTIBLE 可中断阻塞 Linux 将阻塞态划分成 TASK UNINTERRUPTIBLE TASK STOPPED TASK ZOMBILE 三种不同的状态 TASK UNINTERRUPTIBLE 不可中断唤醒 处于该状态的进程只有当资源有效 时被唤醒 不能通过信号或定时中断唤醒 TASK STOPPED 暂停 处于该状 态的进程只能通过其他进程的信号才能唤醒 TASK ZOMBILE 僵死 进程已 结束但尚未消亡 已经释放了大部分资源 PCB 仍未被释放 处于 TASK UNINTERRUPTIBLE 状态的进程资源有效时被唤醒 也可以通过信号或定时 中断唤醒 三 实验步骤 1 进程的创建 编写一段程序 使用系统调用 fork 创建两个进程 当此程序运行 时 在系统中有一个父进程和两个子进程活动 让每个进程在屏幕上显示一个 字符 父进程显示字符 A 子进程分别显示字符 B 和字符 C include void main int p1 p2 while p1 fork 1 创建子进程 if p1 0 putchar b else while p2 fork 1 创建子进程 if p2 0 putchar c else putchar a 父进程 2 进程的控制 include 北京大学操作系统课程设计 21 void main int p1 p2 while p1 fork 1 创建子进程 if p1 0 for int i i 10 i printf daugheter d n i else while p2 fork 1 创建子进程 if p2 0 for int i i 10 i printf son d n i else for int i i 10 i printf parent d n i include include include include include include void main int fd spid ppid char str 80 fd open myfile O RDWR O CREAT 0644 if cpid fork 1 lseek fd 0 0 exit 1 else if cpid 0 lseek fd 0 0 if lockf fd 0 0 1 perror lock failure exit 1 北京大学操作系统课程设计 22 printf I am a parent process my pid is d n getid printf Please input a string n scanf s str lseek fd 0 0 write fd str sizeof str lseek fd 0 0 if lockf fd 0 0 1 perror unlock failure exit 1 else sleep 1 lseek fd 0 0 if lockf fd 0 0 1 perror lock failure exit 1 lseek fd 0 0 read fd str sizeof str lseek fd 0 0 if lockf fd 0 0 1 perror unlock failure exit 1 printf nI am a parent process my pid is d n getid printf Please input a string n printf s n str 3 软中断通信 编制一段程序 使其实现进程的软中断通信 使用系统调度 fork 创建两个子进程 再用系统调用 signal 让 父进程捕捉键盘上来的中断信号 即按 Del 键 当捕捉到中断信号后 父进程 用系统调用 kill 向两个子进程发出信号 子进程捕捉到信号后分别输出下 列信息后中止 Child Process 1 is killed by Parent Child Process 2 is killed by Parent 北京大学操作系统课程设计 23 include include include void stop int wait mark void main int p1 p2 stdout while p1 fork 1 if p1 0 while p2 fork 1 if p2 0 wait mark 1 printf Input any char to stop getchar kill p1 16 kill p2 17 wait 0 wait 0 printf Parent process is killed n exit 0 else wait mark 1 signal 17 stop while wait mark 0 lockf stdout 1 0 printf Child process 2 is killed by parent n locf stdout 0 0 exit 0 else wait mark 1 while wait mark 0 lockf stdout 1 0 printf Child process 1 is killed by parent n lockf std 0 0 北京大学操作系统课程设计 24 exit 0 void stop wait mark 0 4 进程的管道通信 编制一段通信 实现进程的管道通