操作系统课程设计计划.doc

课程设计报告书

2012 / 2013 学年 第 2 学期

课程名称： 操作系统课程设计
专业班级： 计算机1102班
学 号： 110405213
姓 名： 石 佳
指导教师： 邵 虹

题目1 银行家算法的实现
1．1 题目的主要研究内容及预期达到的目标
（1） 理解死锁避免相关内容
（2） 掌握银行家算法主要流程
（3） 掌握安全性检查流程
1．2 题目研究的工作基础或实验条件
（1）硬件环境：windows计算机
（2）软件环境：Visual C++
1．3 设计思想
银行家算法是避免死锁的一种重要方法。通过编写一个模拟动态资源分配的银行家算法程序，进一步深入理解死锁、产生死锁的必要条件、安全状态等重要概念，并掌握避免死锁的具体实施方法。
设Request[i] 是进程i的请求向量，如果Request[i，j]=K,表示进程i需要K个j类型的资源。当i发出资源请求后，系统按下述步骤进行检查：
1) 如果Request i ≤Need，则转向步骤2；否则，认为出错，因为它所请求的资源数已超过它当前的最大需求量。
2) 如果Request i ≤Available，则转向步骤3；否则，表示系统中尚无足够的资源满足i的申请，i必须等待。
3) 系统试探性地把资源分配给进程i，并修改下面数据结构中的数值：
Available = Available - Request i
Allocation i= Allocation i+ Request i
Need i= Need i - Request i
4) 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。如果安全才正式将资源分配给进程i，以完成本次分配；否则，将试探分配作废，恢复原来的资源分配状态，让进程i等待。
1．4 流程图
（见下页）

开始

N
Y
N
Y
N
N
Y
输入进程个数m

输入资源类数n

输入进程最大需求矩阵Max、已分配矩阵Allocation和可利用资源矩阵Available

Need[][]=Max[][]-Allocation[][]

打印输出此时资源分配情况表

输入欲申请资源进程号

输入是否合法

输入该进程申请的资源量

继续分配(Y)?
or
退出(N)?
Request[]>Need[][]?
Y

Request[]>Available[][]?

预分配

调用check()函数进行安全性检查

退出系统

图 1-1 银行家算法流程图
输出提示：系统不安全

输出安全序列，并打印出当前资源分配情况

图 1-2 安全性检查流程图
调用check()函数
work[]=available[]
finish[]=false
need[][]<=work[]
finish[]=false ?

work[]=work[]+allocation[][]
finish[]=true
Y
N
所有进程的finish[]==true?
Y
N

输出提示：系统不安全
结束

题目2 进程调度算法的实现
2．1 题目的主要研究内容及预期达到的目标
（1） 理解进程调度相关理论
（2） 掌握时间片调度原理
（3） 掌握高优先级调度原理
2．2 题目研究的工作基础或实验条件
（1）硬件环境：windows计算机
（2）软件环境：Visual C++
2．3 设计思想
将所有的就绪进程按照先来先服务的原则，排成一个队列，每次调度时，将CPU分配给队首进程，并令其执行一个时间片。当时间片用完时，由一个计时器发出时钟中断请求，调度程序把此进程终止，把该进程放到队尾。
优先级体现了进程的重要程度或紧迫程度，在大多数现代操作系统中，都采用了优先级调度策略。对每个进程确定一个优先数，该算法总是让优先数最高的进程先使用处理器。对具有相同优先数的进程，再来采用先来先服务的次序分配处理器。系统常与任务的紧迫性和系统效率等因素确定进程的优先数。进程的优先数可以固定的，也可随进程执行过程动态变化。一个高优先数进程占用处理器后，系统处理该进程时有两种算法，一是“非抢占式”，另一种是“可抢占式”。前者是次进程占用处理器后一直运行到结束，除非本身主动让出处理器；后者则是严格保证在任何时刻总是让优先数最高的进程在处理器上运行。
时间片和优先级调度的结合，在系统中，每个优先级对应一个就绪队列，在每个就绪队列内，采用时间片调度。当高优先级进程队列调度完成后，才能转入更低优先级的就绪队列调度。

2．4 流程图
（见下页）

开始

选择调度算法

输入进程信息

将输入容器中以满足进入条件的进程调入就绪队列

判断就绪容器和输入容器是否为空
按照选择的算法开始选择就绪队列的进程开始执行

打印各进程信息
y
进行统计计算周转时间差

结束

图2-1 进程调度流程图

题目3 P、V原语的模拟实现
3．1 题目的主要研究内容及预期达到的目标
（1） 理解信号量相关理论
（2） 掌握记录型信号量结构
（3） 掌握P、V原语实现机制
3．2 题目研究的工作基础或实验条件
（1）硬件环境 windows计算机
（2）软件环境 Visual C++
3．3 设计思想
信号量的数值仅能由P，V原语操作改变。采用P，V原语，可以把类名为S的临界区描述为When S do P(sem)临界区V(sem)do。 这里，sem是与临界区内所使用的公用资源有关的信号量。一次P原语操作使得信号量sem减1，而一次V原语操作使得信号量sem加1。
当某个进程正在临界区内执行时，其他进程如果执行了P原语操作，则该进程并不像调用lock时那样因进不了临界区而返回到lock的起点，等以后重新执行测试，而是在等待队列中等待有其他进程做V原语操作释放资源后，进入临界区，这时，P原语的执行才算真正结束。另外，当有好几个进程执行P原语操作未通过而进入等待状态之后，如有某进程作了V原语操作，则等待进程中的一个可以进入临界区，但其他进程必须等待。
本实验模拟生产者与消费者问题，两个进程共享一个公共的固定大小的缓冲区。其中一个是生产者，用于将消息放入缓冲区；另外一个是消费者，用于从缓冲区中取出消息。问题出现在当缓冲区已经满了，而此时生产者还想向其中放入一个新的数据项的情形，其解决方法是让生产者此时进行休眠，等待消费者从缓冲区中取走了一个或者多个数据后再去唤醒它。同样地，当缓冲区已经空了，而消费者还想去取消息，此时也可以让消费者进行休眠，等待生产者放入一个或者多个数据时再唤醒它。
3．4 流程图
（见下页）

开 始
是
该缓冲区是否已上锁？

是否有满缓冲区？
否
是
对该缓冲区上锁
模拟消费
解 锁
结 束
阻 塞
否
开 始
是
该缓冲区是否已上锁？

是否有空缓冲区？
否
是
对该缓冲区上锁
模拟生产
解 锁
结 束
阻 塞
否

图3-1 生产者流程图 图3-2 消费者流程图

题目4 页面置换算法的实现
4．1 题目的主要研究内容及预期达到的目标
（1） 理解页面置换算法相关内容
（2） 掌握页面置换算法主要流程
（3） 掌握常用页面置换算法的实
4．2 题目研究的工作基础或实验条件
（1）硬件环境：windows计算机
（2）软件环境：Visual C++
4．3 设计思想
（1）页面的随机生成
使用rand（）函数随机产生页面号，用数组装入页面号，模拟页面调入内存中发生页面置换的过程。整个过程，都是使用数组来实现每个算法，模拟队列，模拟堆栈的功能，实现每一个置换算法。
（2）最佳置换算法（OPT）
选择永不使用或是在最长时间内不再被访问（即距现在最长时间才会被访问）的页面淘汰出内存。用于算法评价参照。
（3）先进先出置换算法（FIFO）
选择最先进入内存即在内存驻留时间最久的页面换出到外存。
（4）最近最久未使用置换算法（LRU）
以“最近的过去”作为“最近的将来”的近似，选择最近一段时间最长时间未被访问的页面淘汰出内存。
4．4 流程图
（见下页）

开始

页面走向存入数组p[]中，内存块用page[]表示初始化为0

当前p[]中第i个元素是否已在内存

Y
i++

N

Page[]是否有空

Y N
把p[i]的内容直接装入最上面一个空内存块，i++
把page[]中以后一段时间都不使用或是使用时间离现在最远的换出，i++

输出当前内存块状态

结束

图4-1 OPT算法流程图

开始

页面走向存入数组p[]中，内存块用page[]表示初始化为0

当前p[]中第i个元素是否已在内存中

i++
Y

Page[]是否有空
N

N
把p[i]的内容直接装入最上面一个空内存块，i++
把page[]中最先装入的页面置换出去，i++
Y

输出当前内存块状态

结束

图4-2 FIFO算法流程图

开始

页面走向存入数组p[]中，内存块用page[]表示初始化为0

当前p[]中第i个元素是否已在内存

i++
Y

N
Page[]是否有空

Y N

把p[i]的内容直接装入最上面一个空内存块，i++
把page[]中最近最久未使用的页面置换出去，i++

输出当前内存块状态

结束

图4-3 LRU算法流程图