操作系统课程设计页面置换算法

枣 庄 学 院 信息科学与工程学院 课程设计任务书

题目： 页面置换算法的模拟实现

学 生1： XXX（XXXXXXXX） 学 生2： XXX（XXXXXXXX） 专 业： 计算机应用技术 课 程： 操作系统 指导教师： 燕孝飞 职称： 讲 师 完成时间： 2013年 12月----2014 年 1月

枣庄学院信息科学与工程学院制

2013年12月20日

课程设计任务书及成绩评定

课程设计的任务和具体要求 操作系统课程设计是操作系统课程学习的延续。主要目的是配合操作系统课程的学习，对Linux操作系统有一定掌握，能够熟练操作，并能在Linux系统下模拟实现操作系统的功能，有助于对操作系统的理解。 本次课程设计共分两部分，其中第一部分为操作题，同学们需要对Linux的基本的命令（常用的几个，讲课的时候强调的），这部分，任课教师实时检查，让学生用命令完成一定的功能，然后，根据完成情况评定成绩。第二部分为编程设计题，每组同学必须独立完成，可以选择进程调度，也可以根据自己的兴趣，选择模拟实现磁盘调度、银行家算法、页面置换算法等。 指导教师签字： 日期： 指导教师评语 成绩： 指导教师签字： 日期：

课程设计所需软件、硬件等 1、硬件 CPU：Intel T2080D-0 内存：2G 硬盘空间：320G 2、软件 操作系统：Windows XP Linux虚拟机 课程设计进度计划 起至日期 2013.12.18-2013.12.22 2013.12.23-2013.12.27 2013.12.28-2013.12.30 工作内容 收集资料、设计方案 编写程序、实施设计方案 完成课程设计，打印 备注 参考文献、资料索引 序号 文献、资料名称 编著者 出版单位 [1] 操作系统原理与实训教程 范 辉谢、青松 高等教育出版社 [2] 操作系统基础 屠祁、屠立德 清华大学出版社 [3] 计算机操作系统 梁红兵、汤小丹 西安电子科技大学出版社

摘 要

在地址映射过程中，若在页面中发现所要访问的页面不再内存中，则产生缺页中断。当发生缺页中断时操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。

在进程运行过程中，若其所要访问的页面不在内存需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。但应将哪个页面调出，所以需要根据一定的算法来确定。

常用的算法有先进先出置换算法（FIFO）, 最近最久未使用置换算法（LRU）和最佳置换算法（OPT），该设计是在VC++6.0环境下分别用LRU和FIFO来实现页面置换算法的模拟程序，并测试。

关键词：操作系统; 页面置换算法模拟; 进程调度; FIFO; LRU

目 录

第1章 引言................................................................................................................ 1

1.1Linux的出现................................................................................................... 1 1.2 Linux内核..................................................................................................... 1 1.3基本思想......................................................................................................... 2 第2章 Linux系统常用基本命令............................................................................. 2

2.1 Linux目录管理有关命令 ............................................................................. 2 2.2更改目录或文件访问权限命令...................................................................... 2 2.3显示文件内容命令 ............................................................................................. 3 2.4文件管理命令 ................................................................................................. 3 2.4 vi操作的方式（几个常用键） ..................................................................... 4 第3章页面置换…………………………………………………………………………………4

3.1 关于页面置换算法......................................................................................... 4

3.1.1页面置换算法及其分类...................................................................... 4 3.1.2关于页面置换算法模拟程序问题的产生........................................... 5 3.2．相关知识....................................................................................................... 5

3.2.1虚拟存储器的引入............................................................................... 5 3.2.2虚拟存储器的定义............................................................................... 5 3.2.3虚拟存储器的实现方式....................................................................... 6 3.2.4页面分配............................................................................................... 6

第4章 设计简介及设计方案论述............................................................................ 6

4.1程序运行平台.................................................................................................. 6 4.2．设计思想....................................................................................................... 7 4.3总体实验流程图.............................................................................................. 7 第5章 实验程序...................................................................................................... 9

5.1 FIFO算法...................................................................................................... 9 5.2 LRU算法...................................................................................................... 10 第6章 实验结果...................................................................................................... 12

6.1 FIFO(四内存块)如图6-1所示................................................................. 12 6.2 LRU(五内存块)如图6-2所示................................................................. 12 总 结........................................................................................................................ 13

第1章 引言

1.1Linux的出现

Linux 是一种类UNIX 计算机操作系统，最早开始于一位名叫Linus

Torvalds的计算机业余爱好者，当时他是芬兰赫尔辛基大学的学生。他的目的是想设计一个代替Minix（是由一位名叫Andrew Tannebaum的计算机教授编写的一个操作系统示教程序）的操作系统，这个操作系统可用于386、486或奔腾处理器的个人计算机上，并且具有Unix操作系统的全部功能。

Linux操作系统是UNIX操作系统的一种克隆系统，它诞生于1991 年的

10 月5 日（这是第一次正式向外公布的时间）。以后借助于Internet网络，并通过全世界各地计算机爱好者的共同努力，已成为今天世界上使用最多的一种UNIX 类操作系统，并且使用人数还在迅猛增长。

Linux是一种自由和开放源码的类Unix操作系统，存在着许多不同的

Linux版本，但它们都使用了Linux内核。严格来讲，Linux这个词本身只表示Linux内核，但实际上人们已经习惯了用Linux来形容整个基于Linux内核，并且使用GNU 工程各种工具和数据库的操作系统。

1.2 Linux内核

Linux是最受欢迎的自由电脑操作系统内核。它是一个用C语言写成，符合POSIX标准的类Unix操作系统。Linux最早是由芬兰黑客 Linus Torvalds为尝试在英特尔x86架构上提供自由免费的类Unix操作系统而开发的。技术上说Linux是一个内核。“内核”指的是一个提供硬件抽象层、磁盘及文件系统控制、多任务等功能的系统软件。一个内核不是一套完整的操作系统。一套基于Linux内核的完整操作系统叫作Linux操作系统，或是GNU/Linux。

1

1.3基本思想

Linux的基本思想有两点：第一，一切都是文件；第二，每个软件都有确定的用途。其中第一条详细来讲就是系统中的所有都归结为一个文件，包括命令、硬件和软件设备、操作系统、进程等等对于操作系统内核而言，都被视为拥有各自特性或类型的文件。至于说Linux是基于Unix的，很大程度上也是因为这两者的基本思想十分相近。

第二章 Linux系统常用基本命令

2.1 Linux目录管理有关命令

1.pwd ---显示当前工作目录的绝对路径 格式: pwd

2. cd ---改变当前工作目录 命令格式：cd [目录名] 3.Ls--- 列出文件目录的信息

命令格式：ls [可选项] [子目录名] [文件名] 4.mkdir --- 建立目录

命令格式：mkdir [可选项] [目录名] 5.rmdir ---删除目录

本命令用于删除指定的一个或多个目录，必须保证要删除的目录中没有任何文件。

命令格式：rmdir [可选项] [目录名]

2.2更改目录或文件访问权限命令

1.Ls---查看访问权限 格式: ls –l 文件名

2

2.chmod ---改变文件或目录的访问权限

命令格式：chmod [可选项] [权限] [目录或文件名] 3.chgrp命令 ----改变文件或目录所属的组。 命令格式：chgrp [选项] group filename

选项： -R：递归式地改变指定目录及其下的所 有子目录和文件的属组 4.chown ----更改某个文件或目录的属主和属组

命令格式：chown [选项] 文件或目录的新属主[.文件或目录所在的新组] [文件名|目录]

2.3显示文件内容命令

1.cat ----显示，新建，连接文件

2.more ---在终端屏幕按屏显示文本文件。 命令格式： more [ - 选项 ] 文件 3.Head---显示文件或标准输入的头几行 命令格式：head [- n ] 文件 4.tail---显示文件的尾部

命令格式：tail [+ / - num ] [参数] 文件

2.4文件管理命令

1.touch ---功能：将文件的修改时间改为当前时间，如果文件不存在则建立一个空文件。

命令格式： touch [ - 选项 ] 文件

2. cp ---功能：文件或目录的拷贝 ，如同dos的copy 命令格式： cp [选项] 源文件或目录 目标文件或目录

3. mv ---功能：为文件或目录改名或将文件由一个目录移入另一 个目录中 命令格式： mv [选项] 源文件或目录 目标文件或目录

4. rm ---功能：删除一个目录中的一个或多个文件或目录，它也可以将某个

3

目录及其下的所有文件及子目录均删除 命令格式： rm [选项] 文件 ……

2.4 vi操作的方式（几个常用键）

语法]：vi [-wn] [-R] 文件… 例如：进入vi

在系统提示符号输入vi及文件名称后，即可进入vi全屏幕编辑画面： $ vi testfile

有一点要特别注意，就是您进入vi之后是处于“Command mode”下，您要切换到Insert mode才能输入文字。初次用vi的用户都会想先用上下左右键移动光标，结果电脑一直叫，把自己气个半死，所以进入vi后，先不要乱动，转换入Insert后再说。

?切换至Insert mode编辑文件

在Command mode下按?i?、?a?或?o?三键就可进入Insert mode。这时候您就可以开始输入文字了。

i: 插入，从目前光标所在之处插入所输入的文字。 a: 增加，目前光标所在的下一个字开始输入文字。 o: 插入新的一行，从行首开始输入文字

第3章 页面置换

3.1 关于页面置换算法

3.1.1页面置换算法及其分类

在地址映射过程中，若在页面中发现所要访问的页面不再内存中，则产生缺页中断。当发生缺页中断时操作系统必须在内存选择一个页面将其移出内 存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。

常见的置换算法有：

4

1．最佳置换算法（OPT）（理想置换算法） 2．先进现出置换算法（FIFO）： 3．最近最久未使用（LRU）算法

4．Clock置换算法（LRU算法的近似实现） 5．最少使用（LFU）置换算法 6．页面缓冲置换算法

3.1.2关于页面置换算法模拟程序问题的产生

在各种存储器管理方式中，有一个共同的特点，即它们都要求将一个作业全部装入内存方能运行，但是有两种情况：（1） 有的作业很大，不能全部装入内存，致使作业无法运行；（2） 有大量作业要求运行，但内存容量不足以容纳所有这些作业。而虚拟内存技术正式从逻辑上扩充内存容量，将会解决以上两个问题。

从内存中调出一页程序或数据送磁盘的对换区中，通常，把选择换出的页面的算法称为页面置换算法（Page-Replacement Algorithms）。进而页面置换算法模拟程序能客观的将其工作原理展现在我们面前。

3.2．相关知识

3.2.1虚拟存储器的引入

局部性原理：程序在执行时在一较短时间内仅限于某个部分；相应的，它所访问的存储空间也局限于某个区域，它主要表现在以下两个方面：时间局限性和空间局限性。

3.2.2虚拟存储器的定义

虚拟存储器是只具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。

5

3.2.3虚拟存储器的实现方式

分页请求系统，它是在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的页面形式虚拟存储系统。

请求分段系统，它是在分段系统的基础上，增加了请求调段及分段置换功能后，所形成的段式虚拟存储系统。 3.2.4页面分配

平均分配算法，是将系统中所有可供分配的物理块，平均分配给各个进程。 按比例分配算法，根据进程的大小按比例分配物理块。

考虑优先的分配算法，把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据个进程的优先权，适当的增加其相应份额后，分配给各进程。

第4章 设计简介及设计方案论述

4.1程序运行平台

VC++6.0

具体操作如下：在VC++6.0的环境下准备用时钟函数调用库函数（#include ）、 取时钟时间并存入t调用库函数（t=time(NULL)）、 用时间t初始化随机数发生器调用 库函数（srand(t)返回一个1~10之间的随机数（x=rand( )+1） 。编写三种算法。

6

4.2．设计思想

选择置换算法，先输入所有页面号，为系统分配物理块，依次进行置换：

OPT基本思想：是用一维数组page[pSIZE]存储页面号序列，memery[mSIZE]是存储装入物理块中的页面。数组next[mSIZE]记录物理块中对应页面的最后访问时间。每当发生缺页时，就从物理块中找出最后访问时间最大的页面，调出该页，换入所缺的页面。

【特别声明】

若物理块中的页面都不再使用，则每次都置换物理块中第一个位置的页面。 FIFO基本思想：是用队列存储内存中的页面，队列的特点是先进先出，与该算法是一致的，所以每当发生缺页时，就从队头删除一页，而从队尾加入缺页。或者借助辅助数组time[mSIZE]记录物理块中对应页面的进入时间，每次需要置换时换出进入时间最小的页面。

LRU基本思想：是用一维数组page[pSIZE]存储页面号序列，memery[mSIZE]是存储装入物理块中的页面。数组flag[10]标记页面的访问时间。每当使用页面时，刷新访问时间。发生缺页时，就从物理块中页面标记最小的一页，调出该页，换入所缺的页面。

4.3总体实验流程图

如图4-1所示:

7

输入页面访问序列 取访问的页号 查页表 是 否 是否缺页？ 置缺页标志flag为’*’ 按算法不同淘汰一页面 调入所访问的页面 图4-1程序流程图

8

第5章 实验程序

5.1 FIFO算法

#include \#define n 20 #define m 4 void main() {

int ym[n],i,j,q,mem[m]={0},table[m][n]; char flag,f[n];

printf(\请输入页面访问序列\\n\); for(i=0;i

for(i=0;i

{

q=0;

while((ym[i]!=mem[q])&&(q!=m)) q++;

if(q==m) flag='*'; //缺页，则置标志flag为‘*’ else flag=' ';

if(flag=='*') {

for(j=m-1;j>0;j--) //淘汰最先调入的页面调入当前访问的

mem[j]=mem[j-1]; mem[0]=ym[i]; }

for(j=0;j

9

f[i]=flag;

}

printf(\输出结果为下表（0代表为空，*代表有缺页）：\\n\); for(i=0;i

for(j=0;j

for(i=0;i

5.2 LRU算法

#include \#define n 20 #define m 5 void main() {

int ym[n],i,j,q,mem[m]={0},table[m][n]; char flag,f[n]; printf(\请输入页面访问序列\\n\ for(i=0;i

for(i=0;i

while((ym[i]!=mem[q])&&(q!=m)) q++;

10

if(q==m) flag='*'; //缺页，则置标志flag为‘*’ else flag=' '; for(j=q;j>0;j--) mem[j]=mem[j-1]; mem[0]=ym[i]; for(j=0;j

}

printf(\输出结果为下表（0代表为空，*代表有缺页）：\\n\ for(i=0;i

for(j=0;j

for(i=0;i

11

第6章 实验结果

6.1 FIFO(四内存块)

图6-1四块内存图

6.2 LRU(五内存块)

图6-2五块内存图

12

总 结

通过对页面置换算法模拟程序的程序设计，让我对虚拟页式存储管理有了更深的了解。刚开始拿到这个题目觉得很难，不知道该怎么下手，因为是自己第一次用C语言编写操作系统程序。但是搞懂了页面置换的思想以后，对编程就有了一定的思路。经过几天的编写，程序也终于写出来啊。但是却遇到了许多困难，程序的调试也出现了许多的错误。但是经过几次上机操作，在老师的指导和帮助下，程序最终还是完成了。通过这次的程序设计，让我对C语言有了更深一步的了解和认识，编程能力也有了提高，我认到学好计算机要重视实践操作，只有真正动手了才知道自己还有那些不足之处。

13

本文来源：https://www.bwwdw.com/article/1el6.html