©2010-2026 宁波自信网络信息技术有限公司 版权所有
客服电话：0574-28810668 投诉电话：18658249818
浙ICP备2021020529号-1 | 浙B2-20240490
关注我们 ：
1、 课程设计报告书 2012 / 2013 学年 第 2 学期 课程名称： 操作系统课程设计 专业班级： 计算机1102班 学 号： 110405213 姓 名： 石 佳 指导教师： 邵 虹 题目1 银行家算法的实现 1．1 题目的主要研究内容及预期达到的目标 （1） 理解死锁避免相关内容 （2） 掌握银行家算法主要流程 （3） 掌握安全
2、性检查流程 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；否则，认为出错，因为它所请求的资源数已超过它当前的
3、最大需求量。 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等待。
4、1．4 流程图 （见下页） 开始 N Y N Y N N Y 输入进程个数m 输入资源类数n 输入进程最大需求矩阵Max、已分配矩阵Allocation和可利用资源矩阵Available Need[][]=Max[][]-Allocation[][] 打印输出此时资源分配情况表 输入欲申请资源进程号 输入是否合法 输入该进程申请的资源量 继续分配(Y)? or 退出(N)? Request[]>Need[][]? Y Request[]
5、>Available[][]? 预分配 调用check()函数进行安全性检查 退出系统 图 1-1 银行家算法流程图 输出提示：系统不安全 输出安全序列，并打印出当前资源分配情况 图 1-2 安全性检查流程图 调用check()函数 work[]=available[] finish[]=false need[][]<=work[] finish[]=false ? work[]=work[]+allocation[][] finish[]=true Y N 所有进程的fin
6、ish[]==true? Y N 输出提示：系统不安全 结束 题目2 进程调度算法的实现 2．1 题目的主要研究内容及预期达到的目标 （1） 理解进程调度相关理论 （2） 掌握时间片调度原理 （3） 掌握高优先级调度原理 2．2 题目研究的工作基础或实验条件 （1）硬件环境：windows计算机 （2）软件环境：Visual C++ 2．3 设计思想 将所有的就绪进程按照先来先服务的原则，排成一个队列，每次调度时，将CPU分配给队首进程，并令其执行一个
7、时间片。当时间片用完时，由一个计时器发出时钟中断请求，调度程序把此进程终止，把该进程放到队尾。 优先级体现了进程的重要程度或紧迫程度，在大多数现代操作系统中，都采用了优先级调度策略。对每个进程确定一个优先数，该算法总是让优先数最高的进程先使用处理器。对具有相同优先数的进程，再来采用先来先服务的次序分配处理器。系统常与任务的紧迫性和系统效率等因素确定进程的优先数。进程的优先数可以固定的，也可随进程执行过程动态变化。一个高优先数进程占用处理器后，系统处理该进程时有两种算法，一是“非抢占式”，另一种是“可抢占式”。前者是次进程占用处理器后一直运行到结束，除非本身主动让出处理器；后者则是严
8、格保证在任何时刻总是让优先数最高的进程在处理器上运行。 时间片和优先级调度的结合，在系统中，每个优先级对应一个就绪队列，在每个就绪队列内，采用时间片调度。当高优先级进程队列调度完成后，才能转入更低优先级的就绪队列调度。 2．4 流程图 （见下页） 开始 选择调度算法 输入进程信息 将输入容器中以满足进入条件的进程调入就绪队列 判断就绪容器和输入容器是否为空 按照选择的算法开始选择就绪队列的进程开始执行
9、 打印各进程信息 y 进行统计计算周转时间差 结束 图2-1 进程调度流程图 题目3 P、V原语的模拟实现 3．1 题目的主要研究内容及预期达到的目标 （1） 理解信号量相关理论 （2） 掌握记录型信号量结构 （3） 掌握P、V原语实现机制 3．2 题目研究的工作基础或实验条件 （1）硬件环境 windows计算机 （2）软件环境 V
10、isual 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原语的执行才算真正结束。另外，当有好
11、几个进程执行P原语操作未通过而进入等待状态之后，如有某进程作了V原语操作，则等待进程中的一个可以进入临界区，但其他进程必须等待。 本实验模拟生产者与消费者问题，两个进程共享一个公共的固定大小的缓冲区。其中一个是生产者，用于将消息放入缓冲区；另外一个是消费者，用于从缓冲区中取出消息。问题出现在当缓冲区已经满了，而此时生产者还想向其中放入一个新的数据项的情形，其解决方法是让生产者此时进行休眠，等待消费者从缓冲区中取走了一个或者多个数据后再去唤醒它。同样地，当缓冲区已经空了，而消费者还想去取消息，此时也可以让消费者进行休眠，等待生产者放入一个或者多个数据时再唤醒它。 3．4 流程图
12、 （见下页） 开 始 是 该缓冲区是否已上锁？ 是否有满缓冲区？ 否 是 对该缓冲区上锁 模拟消费 解 锁 结 束 阻 塞 否 开 始 是 该缓冲区是否已上锁？ 是否有空缓冲区？ 否 是 对该缓冲区上锁 模拟生产 解 锁 结 束 阻 塞 否 图3-1 生产者流程图 图3-2 消费者流程图 题目4 页面置换算法的实现 4．1 题目的主要研究内容及预期达到的目标 （1） 理解页面置换算法相关内容 （2） 掌握页面
13、置换算法主要流程 （3） 掌握常用页面置换算法的实 4．2 题目研究的工作基础或实验条件 （1）硬件环境：windows计算机 （2）软件环境：Visual C++ 4．3 设计思想 （1）页面的随机生成 使用rand（）函数随机产生页面号，用数组装入页面号，模拟页面调入内存中发生页面置换的过程。整个过程，都是使用数组来实现每个算法，模拟队列，模拟堆栈的功能，实现每一个置换算法。 （2）最佳置换算法（OPT） 选择永不使用或是在最长时间内不再被访问（即距现在最长时间才会被访问）的页面淘汰出内存。用于算法评价参照。 （3）先进先出置换算法（FIFO） 选择最先
14、进入内存即在内存驻留时间最久的页面换出到外存。 （4）最近最久未使用置换算法（LRU） 以“最近的过去”作为“最近的将来”的近似，选择最近一段时间最长时间未被访问的页面淘汰出内存。 4．4 流程图 （见下页） 开始 页面走向存入数组p[]中，内存块用page[]表示初始化为0 当前p[]中第i个元素是否已在内存 Y i++ N Page[]是否有空
15、 Y N 把p[i]的内容直接装入最上面一个空内存块，i++ 把page[]中以后一段时间都不使用或是使用时间离现在最远的换出，i++ 输出当前内存块状态 结束 图4-1 OPT算法流程图 开始 页面走向存入数组p[]中，内存块用page[]表示初始化为0 当前p[]中第i个元素是否已在内存中
16、 i++ Y Page[]是否有空 N N 把p[i]的内容直接装入最上面一个空内存块，i++ 把page[]中最先装入的页面置换出去，i++ Y 输出当前内存块状态
17、 结束 图4-2 FIFO算法流程图 开始 页面走向存入数组p[]中，内存块用page[]表示初始化为0 当前p[]中第i个元素是否已在内存 i++ Y N Page[]是否有空 Y N 把p[i]的内容直接装入最上面一个空内存块，i++ 把page[]中最近最久未使用的页面置换出去，i++ 输出当前内存块状态 结束 图4-3 LRU算法流程图
©2010-2026 宁波自信网络信息技术有限公司 版权所有
客服电话：0574-28810668 投诉电话：18658249818
浙ICP备2021020529号-1 | 浙B2-20240490
关注我们 ：
