CLOCK时钟置换算法.docx

青岛理工大学 操作系统课程设计报告 院（系）： 计算机工程学院 专业： 软件工程 学生姓名: ＿＿ 　　 班级：＿ ＿＿　学号: 题目： 采用CLOCK置换算法仿真请求分页系统 起迄日期: 2012.7.6--2012.7.13 ＿ ＿＿＿ 设计地点: 实验楼 指 导 教 师: 2011—2012年度 第 2 学期 完成日期: 2012 年 7 月 12 日 课程设计目的 操作系统课程设计是为了对学习的操作系统课程更深刻的理解和巩固，对操作系统的整体进行一个模拟。通过实践加深对各个部分的管理功能的认识，还能进一步分析各个部分之间的联系，最后达到对完整系统的理解。同时，可以提高运用操作系统知识解决实际问题的能力；锻炼实际的编程能力、创新能力及团队组织、协作开发软件的能力；还能提高调查研究、查阅技术文献、资料以及编写软件设计文档的能力。 课程设计是自己独立完成一项任务的过程，编程过程中要充分调动个人的积极性，提高自身解决实际问题的能力，发现自身的编程错误习惯，提高编写程序的质量。同时，也为以后深入层次的学习及研究打基础。 编程中少不了难题，遇到难题时需要的是用程序员的思维方式去考虑问题解决问题，还需要很大的精力和耐心，对于我们来说都是磨练和提高。 课程设计内容与要求 1、设计内容：用高级语言编写和调试一个内存分配程序，加深对内存分配算法的理解。 2、设计要求： 实现请求分页存储管理方式的页面置换算法：CLOCK算法 内存物理块数固定为15个，对多个作业采用可变分配全局置换的策略分配物理块 作业数量与作业大小（10-20页）可在界面进行设置 所有作业按RR算法进行调度，时间片长度为1秒 可为每个作业随机产生引用的页面串，也可以人工输入引用的页面串，页面串长度50100，要求必须包括作业所有的页面，可作为样例数据保存 可读取样例数据（要求存放在外部文件中）进行作业数量、作业大小、页面串长度的初始化 要求采用可视化界面，模拟内存分配和使用情况图，可在运行过程中随时暂停，查看当前内存物理块使用情况。 每次全部作业运行结束后，要求打印出访问命中率 系统分析与设计 1、系统分析 CLOCK页面置换算法是根据进程的实际需要，动态地为之分配内存空间。在实现可变分区分配时，将涉及到分区分配中所用的数据结构、分区分配算法和分区的分配和回收操作这样三个问题。为了实现分区分配，系统中必须配置相应的数据结构，用来描述空闲区和已分配区的情况，为分配提供依据。常用的数据结构有两种形式：空闲分区表和空闲分区链。为把一个新作业装入内存，须按照一定的算法，从空闲分区表或空闲分区链中选出一个分区分配给该作业。在动态分区存储管理方式中，主要操作是分配内存和回收内存。 信息。 本系统完成的是对作业数量不固定，作业大小、进入内存时间、运行时间需要通过界面进行输入，或者从文件读取的作业基本信息，内存（15——20）的处理信息是处理对于各种作业完成动态的内存分配，回收和紧凑。 行为。完全描述系统状态变化所需处理或功能； 本系统处理了RR时间片轮转算法对内存的动态分配，每一个作业都是按照先进先出的原则进入内存当地一个作业进入内存后，会长生一个时钟信号，依次递增，当一个作业从进入时间开始到运行时间结束，会动态的释放所占大小的内存区间，直到时钟信号等于最后一个作业释放他所占的内存区间，此时所有的作业运行完，内存也回收完。 表示。详细描述系统的对外接口与界面。 本系统采用的VC编写的，在DOS界面下运行 2、系统设计： 系统利用RR时间片轮转算法掉调度作业，并从内存区动态分配内存。设内存区的大小为number，表中每个空闲分区的大小可表示为nunber个。虚拟存储区采用page类型二维数组实现，然后将虚拟存储区的首址返回给调用者。当进程运行完毕释放内存时，系统根据回收区的首址，从内存区表中按CLOCK算法找到相应的插入点。 2.1、模块设计： RR算法(next fit)(详见程序流程图) 先将所有的进程排成一队，按先来先服务原则排列，先调度首进程按时间片轮转执行。当执行到队尾时再从头执行，详细参看课本95页3.3.3节时间片轮转法 改进型CLOCK算法(best fit/worst fit) 根据页面的访问位A和修改位M确定调出页面执行四步循环找出要置换页面，详细介绍参看课本153页4.8.3节CLOCK置换算法 虚拟存储区 采用的page二维数组模拟 内