页面置换算法的模拟-(1).docVIP

课程设计报告

课程名称：操作系统

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

日期：2010.07.01

目录TOC\o1-3\h\z\u

一、课程设计分析 1

二、相关知识 1

三、功能设计分析 2

四、程序设计 2

五、运行截图 4

六、参考程序 6

七、结果分析 14

八、心得体会 14

一、课程设计分析

编写程序实现页面置换算法中常用的FIFO、LRU。

FIFO页面置换算法：FIFO淘汰算法是最先使用的页面最先被淘汰。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。先进先出(FIFO)页面置换算法，是根据页面调入内存后的使用情况进行决策的。该算法是选择在内存中驻留时间最久的页面予以淘汰。该算法赋于请求调入页面一个空间〔工作集〕，淘汰掉最先调入的页，取而代之的是紧随它进来的页，这样就根本上实现了对最先进入内存的页面的淘汰。

LRU页面置换算法：该算法淘汰的页面是在最近一段时间里较久未被访问的那一页，它是根据程序执行时的局部性原理而设计的。

二、相关知识

1．虚拟存储器的引入

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

2．虚拟存储器的定义

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

3．虚拟存储器的实现方式

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

请求分段系统，它是在分段系统的根底上，增加了请求调段及分段置换功能后，所形成的段式虚拟存储系统。

4．页面分配

平均分配算法，是将系统中所有可供分配的物理块，平均分配给各个进程。

按比例分配算法，根据进程的大小按比例分配物理块。

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

5．页面置换算法

先进先出页面置换算法，该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间催久的页面予以淘汰。

6．最近最久未使用LRU置换算法

个页面时，选择现有页面中T最大的，即最近最久未使用的页面予以淘汰

三、功能设计分析

在掌握根本的算法理论原理的根底上，能够选取适宜的语言和开发工具，编写程序将虚拟存储管理中页面置换算法的机制动态的演示出来。具体功能主要包括：

①数据结构的定义：采用适宜的数据结构描述页表；

②页面置换：采用选定的页面置换算法来模拟管理页表中页的置换过程；

③界面设计：要求有图形界面，能够直观的了解页面置换的过程，能够给出当前被置换出的页号，以及总的缺页次数。

四、程序设计

①FIFO页面置换算法：

4*

4*

4*

3*

3*

3

3

0

0

0

1

1

√√√√

定义一个二维数组，行数表示系统分配给该作业的页架数，列数表示作业的页面访问序列的次数。算法可以设计：二维数组中每列的第一个数字表示的页面是当前最先进入主存的页面，意思就是说如果发生缺页中断，就应该将该页面移出，方法是将本列下面的两个数据前移，然后将移入的页面置入本列最后的位置。

算法的伪代码描述形式：

while(I页面访问序列的次数)

{

if(要访问的页面在当前第I列中)

不做任何处理，该列内容保持不变；

else(要访问的页面不在当前第I列中)

做页面置换处理；}

打印二维数组中的内容。

LRU页面置换算法：

4*

4

4

3

0

3*

3

0

1

0*

1*

3*

√√√√

定义一个二维数组，行数表示系统分配给该作业的页架数，列数表示作业的页面访问序列的次数。算法可以设计：二维数组中每列的第一个数字表示的页面是当前最近最少用的页面，意思就是说如果发生缺页中断，就应该将该页面移出，方法是将本列下面的两个数据前移，然后将移入的页面置入本列最后的位置。

算法的伪代码描述形式：

while(I页面访问序列的次数)

{

if(要访问的页面在当前第I列中)

将该页面前移至该列最后一个位置，其余页面数字向前移动一位；

else(要访问的页面不在当前第I列中)

做页面置换处理；}

打印二维数组中的内容。

五、运行截图

六、参考程序

#includeiostream.h

#defineBsize3

#definePsize20

structpageInfor