精华内容
下载资源
问答
  • 页面置换算法实验报告.docx
  • 页面置换算法 实验报告 实验目的 设计和实现最佳置换算法 随机置换算法 先进先出置换算法 最近最久未使用 置换算法 简单 Clock 置换算法及改进型 Clock 置换算法通过支持页面访问序 列随机发生实现有关算法的测试及...
  • 页面置换算法实验报告 一 实验目得 : 设计与实现最佳置换算法 随机置换算法 先进先出置换算法 最近最久未使用置换算法简单 Clock 置换算法及改进型 C ock 置换算法 ; 通过支持页面访问序列随机发生实现有关算法得...
  • 页面置换算法实验报告 页面置换算法 实验报告 实验目的 设计和实现最佳置换算法随机置换算法先进先出置换算法最近最久未使用置换算法简单Clock置换算法及改进型Clock置换算法通过支持页面访问序列随机发生实现有关...
  • 学 海 无 涯 页面置换算法 实验报告 一实验目的 设计和实现最佳置换算法随机置换算法先进先出置换算法最近最久未使用 置换算法简单Clock 置换算法及改进型Clock 置换算法通过支持页面访问序 列随机发生实现有关算法...
  • 操作系统 页面置换算法 实验报告 16281027 1.实验目的及基本要求 设计和实现最佳置换算法、先进先出置换算法、最近最久未使用置换算法、页面缓冲置换算法; 通过页面访问序列随机发生器实现对上述算法的测试及性能...

    操作系统 页面置换算法 实验报告 16281027

    1.实验目的及基本要求

    设计和实现最佳置换算法、先进先出置换算法、最近最久未使用置换算法、页面缓冲置换算法;
    通过页面访问序列随机发生器实现对上述算法的测试及性能比较。

    2.页面置换算法背景知识说明
    (1)请求分页虚拟内存管理
    在这里插入图片描述

    (2)工作集与缺页率
    多数程序都显示出高度的局部性,也就是说,在一个时间段内,一组页面被反复引用。
    这组被反复引用的页面随着时间的推移,其成员也会发生变化。有时这种变化是剧烈的,有时则是渐进的,我们把这组页面集合称为工作集。

    缺页率 = 缺页中断次数/页面总访问次数。

    3.课题假设前提说明
    页表用整数数组或结构数组来表示。
    页面访问序列串是一个整数序列,整数的取值范围为0到 N - 1。
    页面访问序列串中的每个元素 p 表示对页面 p 的一次访问。

    符合局部访问特性的随机工作集的生成算法:
    确定虚拟内存的尺寸 N,工作集的起始位置 p,工作集中包含的页数e,
    工作集移动率m(每处理 m个页面访问则将起始位置 p +1),以及一个范围在 0 和 1 之间的值 t;
    生成m个取值范围在 p 和 p + e间的随机数,并记录到页面访问序列串中;
    生成一个随机数 r,0 ≤ r ≤ 1;
    如果 r < t,则为 p 生成一个新值,否则 p = (p + 1) mod N;
    如果想继续加大页面访问序列串的长度,返回第2步,否则结束。

    4.算法说明
    (1)最佳置换算法optimal OPT
    选择永不使用或是在最长时间内不再被访问(即距现在最长时间才会被访问)的页面淘汰出内存。
    OPT属于理想化算法,具有最好性能(对于固定分配页面方式,本法可保证获得最低的缺页率),但实际上却无法实现,主要用于算法评价参照。

    (2)先进先出置换算法 FIFO
    选择最先进入内存即在内存驻留时间最久的页面换出到外存。进程已调入内存的页面按进入先后次序链接成一个队列,并设置替换指针以指向最老页面。
    该算法简单直观,但不符合进程实际运行规律,性能较差,故实际应用极少。

    (3)最近最久未使用置换算法 LRU
    以“最近的过去”作为“最近的将来”的近似,选择最近一段时间最长时间未被访问的页面淘汰出内存。适用于各种类型的程序,性能较好,但需要较多的硬件支持。

    (4)改进型Clock算法
    ① 从查寻指针当前位置起扫描内存分页循环队列,选择A=0且M=0的第一个页面淘汰;
    若未找到,转②;
    ② 开始第二轮扫描,选择A=0且M=1的第一个页面淘汰,同时将经过的所有页面访问位置为0;
    若不能找到,转①。
    即总是尽可能地替换掉既未被访问又未被修改(A=0且M=0)的页面,若遍历一遍找不到满足条件的页面,则淘汰第一个未被访问(A=0且M=1)的页面。

    (5)PBA页面缓冲算法
    用 FIFO 算法选择被置换页,选择换出的页面不是立即换出,而是放入两个链表之一,如果页面未被修改,就将其归入到空闲页面链表的末尾,否则将其归入已修改页面链表末尾。这些空闲页面和已修改页面会在内存中停留一段时间。如果这些页面被再次访问,只需将其从相应链表中移出,就可以返回进程,从而减少一次 I/O 开销。
    需调入新页,则将新页读入到空闲页面链表的第一个页面中,然后将其从该链表中移出。当已修改的页面达到一定数目后,再将它们一起写入磁盘。这样能大大减少 I/O 操作的次数。

    5.实验设计
    (1)数据结构
    使用generate函数生成具有局部随机特性的工作集access[MAX],并使用int型数组存储,其中access[i]表示第i+1个需要进入内存的页面的标号。
    对于FIFO页面置换算法,使用了一个队列结构Queue来实现先进先出特性。
    对于改进型Clock算法,定义了一个带有int型访问位A和修改位M的node结构体。
    对于PBA页面置换算法,使用了一个链表结构nodes来表示装入内存的页块节点,定义了idle链表和modified链表,分别表示空闲链表和已修改页面链表。

    (2)函数功能说明

    void initQueue (pQueue q); //队列初始化
    void push (pQueue q, int num); //页面节点进入队列中
    void pop (pQueue q); //将页面移出内存,即从队列中弹出对应节点
    void destroy (pQueue q); //清空并销毁队列
    bool findInQueue (pQueue q, int num); //查找指定页面是否已调入内存
    void generate(); //生成具有局部随机特性的工作集
    void testFIFO(); //FIFO算法测试,计算缺页率
    void fifo (pQueue q, int num); //实现FIFO算法

    void Optimal (int n); //实现最佳置换算法
    void testOptimal(); //计算最佳置换算法的缺页率

    void LRU (int n); //实现LRU算法
    void testLRU(); //计算LRU算法的缺页率

    void Clock (int n); //改进型clock算法实现函数
    void testClock(); //计算clock算法的缺页率

    bool isInNodes (int n); //判断页面是否已经在链表中
    void addToLink (int data, int type); //将页面添加到已修改页面链表和空闲链表上
    void emptyIdle(); //将空闲链表上的所有页面送出内存
    void emptyModi(); //将已修改页面链表上所有的链表送出内存
    void PBA (int n); //PBA算法实现函数

    (3)页面置换算法实现

    1.FIFO 先进先出页面置换算法

    void FIFO(pQueue q, int num) //实现先入先出置换算法
    {
    	if (findInQueue(q, num)){;}//检查是否缺页,若不缺页,则继续
    	else{
    		if (q->n == size){ 
    			pop(q);
    			push(q, num); //弹出队头,新页面入队尾,缺页数+1
    			lost++;
    		}
    		else{
    			push(q, num);
    			lost++;
    		}
    	}
    }
    

    2.OPT 最佳置换算法

    void Optimal(int n)
    {
    	int i = 0, j = 0;
    	if (isInMemory(n)){
    		;//未发生缺页,继续
    	}
    	else
    		if (index == size){
    			lost++;		//缺页数+1
    			int max = 0;
    			int position, tag;
    			for (i = 0; i < size; i++){
    				tag = -1;
    				for (j = n + 1; j < MAX; j++){	
    				//遍历得到在整个工作集中找出距现在最长时间才会被访问的页面号
    					if (access[j] == memory[i]){
    						tag = j;
    						break;
    					}
    				}
    				if (tag == -1) //往后不会被访问,直接弹出{
    					max = MAX;
    					position = i;
    					break;
    				}
    				else{
    					if (max < tag){
    						max = tag;
    						position = i;
    					}
    				}
    			}
    			memory[position] = access[n];
    		}
    		else {
    			memory[index] = access[n];
    			index++;
    		}
    }
    

    3.LRU 最近最久未使用页面置换算法

    void LRU(int n)
    {
    	int i, j;
    	if (isInMemory(n)){
    		;//未发生缺页,继续
    	}
    	else
    		if (index == size){
    			int max = n, pos = -1, tag;
    			for (i = 0; i < size; i++){
    				for (j = n - 1; j >= 0; j--){ //向前查找
    					if (access[j] == memory[i]){
    						tag = j;
    						break;
    					}
    				}
    				if (tag < max){ //通过比较得出最近一段时间最长时间未被访问的页面
    					max = tag;
    					pos = i;
    					if (max == 0)
    					{
    						break;
    					}
    				}
    			}
    			memory[pos] = access[n];
    			lost++;
    		}
    		else{
    			memory[index] = access[n];
    			index++;
    		}
    }
    
    

    4.Clock 改进型页面置换算法

    void Clock(int n)
    {
    	if (isInNodes(n)){
    		;//未发生缺页,继续
    	}
    	else
    		if (index == size){
    			lost++;
    			int i = 0, tag = -1;
    			while (true){ //循环遍历内存块
    				if ((i / size) % 2 == 0){
    					if (nodes[i % size].A == 0 && nodes[i % size].M == 0) 						
    					//A=0且M=0
    					{
    						tag = i % size;
    						break;
    					}
    				}
    				if ((i / size) % 2 == 1){
    					if (nodes[i % size].A == 0 && nodes[i % size].M == 1) 						
    					//A=0且M=1
    					{
    						tag = i % size;
    						break;
    					}
    					else{
    						nodes[i % size].A = 0; 
    						//将经过的所有页面访问位置为0
    					}
    				}
    				i++;
    			}
    			nodes[tag].data = access[n];
    			nodes[tag].A = 1;
    			if (rand() % 10 < 4){
    				nodes[tag].M = 1;
    			}
    			else{
    				nodes[tag].M = 0;
    			}
    		}
    		else{
    			nodes[index].data = access[n];
    			nodes[index].A = 1;
    			if (rand() % 10 < 4){
    				nodes[index].M = 1;
    			}
    			else{
    				nodes[index].M = 0;
    			}
    			index++;
    		}
    }
    

    5.PBA 页面缓冲置换算法

    void PBA(int n)
    {
    	if (isInNodes(n))
    	{
    		; //未缺页,继续
    	}
    	else
    		if (index == size)
    		{
    			LNode *p;
    			if ((p = isinLinks(n)) != NULL)
    			{
    				nodes = (LNode*)realloc(nodes, (size + 1) * sizeof(LNode));
    				nodes[size].data = p->data;
    				nodes[size].flag = p->flag;
    				nodes[size].modify = p->modify;
    				nodes[size].next = p->next;
    				size++;
    				index++;
    				free(p);
    			}
    			else
    			{
    				lost++;//缺页数+1
    				if (nodes[n % 3].modify == 1)//当前页面已修改,type为1
    				{
    					addToLink(nodes[n % 3].data, 1);
    				}
    				else//未修改
    				{
    					addToLink(nodes[n % 3].data, 0);
    				}
    				nodes[n % 3].data = access[n];
    				nodes[n % 3].flag = 1;
    				nodes[n % 3].next = NULL;
    				if (rand() % 10 < 4)
    				{
    					nodes[n % 3].modify = 0;
    				}
    				else
    				{
    					nodes[n % 3].modify = 1;
    				}
    			}
    		}
    		else
    		{
    			nodes[index].data = access[n];
    			nodes[index].flag = 1;
    			nodes[index].next = NULL;
    			if (rand() % 10 < 4)
    			{
    				nodes[index].modify = 1;
    			}
    			else
    			{
    				nodes[index].modify = 0;
    			}
    			index++;
    		}
    }
    

    6.生成局部随机工作集

    void generate()
    {
    	srand((unsigned)time(NULL));
    	p = rand() % 64;
    	int m = 8, e = 8;	//工作集移动率为m
    	int i, j;
    	double t;
    	t = rand() % 10 / 10.0;		//t取0到1的随机值
    	for (i = 0; i < 4000; i++) 	//共循环4000*m次,每次生成一个页面号
    	{
    		for (j = i * m; j < (i + 1) *m; j++)
    		{//生成m个取值范围在p到p+e间的随机数
    			access[j] = (p + rand() % e) % 64;
    		}
    		double r = (rand() % 10) / 10.0;
    		if (r < t)
    		{
    			p = rand() % 64;//为p生成一个新随机值
    		}
    		else
    		{
    			p = (p + 1) % 64;
    		}
    	}
    }
    

    6.实验结果
    定义页表的总大小为32K(#define MAX 32000),内存块数为3,
    使用上述算法生成的随机具有局部特性的随机工作集进行实验。
    分别使用上述五种页面置换算法得到的结果如下:
    在这里插入图片描述可以看到

    可以看到最佳置换算法总是效果最好的。
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    实验代码已上传至GitHub,链接如下:
    https://github.com/Bismarck0116/OS-homework-experiment/tree/master/Experiment 4

    展开全文
  • 页面置换算法实验报告_16281100_雷兵

    万次阅读 2019-05-28 14:35:35
    页面置换算法实验报告 1实验题目 设计和实现最佳置换算法、先进先出置换算法、最近最久未使用置换算法、页面缓冲置换算法;通过页面访问序列随机发生器实现对上述算法的测试及性能比较。 2实验要求 假设前提 ...

    页面置换算法实验报告

    1实验题目

    设计和实现最佳置换算法、先进先出置换算法、最近最久未使用置换算法、页面缓冲置换算法;通过页面访问序列随机发生器实现对上述算法的测试及性能比较。

    2实验要求

    1. 假设前提
    1. 模拟的虚拟内存的地址为16位,页面大小为1K,模拟的物理内存有32K;
    2. 页表用整数数组或结构数组来表示;
    3. 页面访问序列串是一个整数序列,整数的取值范围为0到N - 1。页面访问序列串中的每个元素p表示对页面p的一次访问。

     

    1. 性能测评及问题说明

    测试不同的页面访问序列及不同的虚拟内存尺寸,并从缺页率、算法开销等方面对各个算法进行比较。(同时请给出在给定页面访问序列的情况下,发生页面置换次数的平均值)

     

    3概要设计

    3.1模块设计

    总模块图

    3.2功能

    1. 随机访问序列生成
    1. 确定虚拟内存的尺寸N,工作集的起始位置p,工作集中包含的页数e,工作集移动率m(每处理m个页面访问则将起始位置p +1),以及一个范围在0和1之间的值t;
    2. 生成m个取值范围在p和p + e间的随机数,并记录到页面访问序列串中;
    3. 生成一个随机数r,0 ≤ r ≤ 1;
    4. 如果r < t,则为p生成一个新值,否则p = (p + 1) mod N;
    5. 如果想继续加大页面访问序列串的长度,请返回第2步,否则结束。

     

    1. 最佳置换算法OPT

    选择永不使用或是在最长时间内不再被访问(即距现在最长时间才会被访问)的页面淘汰出内。

     

    1. 先进先出置换算法FIFO

    选择最先进入内存即在内存驻留时间最久的页面换出到外存。

    进程已调入内存的页面按进入先后次序链接成一个队列,并设置替换指针以指向最老页面。

     

    1. 最近最久未使用置换算法LRU

    以“最近的过去”作为“最近的将来”的近似,选择最近一段时间最长时间未被访问的页面淘汰出内存。

     

    1. 改进型Clock置换算法CLO

    ① 从查寻指针当前位置起扫描内存分页循环队列,选择A=0且M=0的第一个页面淘汰;若未找到,转②

    ② 开始第二轮扫描,选择A=0且M=1的第一个页面淘汰,同时将经过的所有页面访问位置0;若不能找到,转①

     

    4详细设计

    4.1程序流程

    程序总流程图

    先进先出页面置换算法流程图

     

    最近久未使用置换算法流程图

    最佳置换算法流程图

     

    改进型Clock置换算法流程图

    4.3程序代码

    #include<stdio.h>
    #include<string.h>
    #include<iostream>
    #include<stdlib.h>
    #include<time.h>
    #define N 64   //虚拟内存大小
    #define MAX 2000    //引用串的长度
    #define P 32  //物理内存大小
    
    using namespace std;
    int result;  //置换次数
    int RS[100] = {};  //RS串
    int M[P] = {0};   // 物理内存大小
    
    void PRS()
    {
    	int p = 1;//工作集的起始位置p
    	int e = 40;//工作集中包含的页数e
    	int m = 64;//工作集移动率m
    	double t = 0.5;
    	int judge = 1;
    	int count = 0;
    	double r;
    	while(judge == 1)
    	{
    		srand((unsigned)time(NULL));
    		for(int i = 0;i < m;i++)
    		{
    			RS[count] = rand()%e+p;
    			count++;
    		}
    		r = (rand()%9+1)/10;
    		if(r < t)
    		{
    			p = rand()%N+1;
    		}
    		else
    		{
    			p = (p+1)%N;
    		}
    		if(count >= MAX){
                printf("以下是生成的引用串:\n");
                for(int i = 0;i < count;i++)
                {
                    printf("%d ",RS[i]);
                }
                printf("\n");
                break;
    		}
    	}
    }
    
    void print(int c)
    {
    	printf("以下为物理内存情况:\n");
    	for(int i = 0;i < c;i++)
    	{
    		printf("%d ",M[i]);
    	}
    	printf("\nend**********************\n");
    }
    
    //判断物理内存是否已满
    int full(int c,int j)
    {
    	int judge = 0;
    	for(int i = 0;i < c;i++)
    	{
    		if(RS[j] == M[i])
    		{
    			judge = 1;
    			break;
    		}
    	}
    	if(!judge)
    	{
    		M[c] = RS[j];
    		c++;
    	}
    	return c;
    }
    
    //判断是否为缺页
    int lack(int c, int j)
    {
    	int judge = 0;
    	for(int i = 0;i < c;i++)
    	{
    		if(RS[j] == M[i])
    		{
    			judge = 1;
    			break;
    		}
    	}
    	return judge;
    }
    
    
    //最佳置换算法
    int OPT()
    {
    	result = 0;
    	int count = 0;
    	for(int j = 0;j < MAX;j++)
    	{
    		int judge = 0;
    		if(count < P)
    		{
    			count = full(count,j);
    		}
    		else
    		{
    			int number;
    			judge = lack(count,j);
    			if(!judge)   //没有找到,需进行置换
    			{
    				result++;
    				int s;  //用于存放没有找到的页面的数组下标
    				for(int k = 0;k < count;k++)
    				{
    					number = -1;
    					for(int i = j+1;i < MAX;i++)
    					{
    						if(M[k] == RS[i])
    						{
    							if(number < i)
    							{
    								number = i;
    								s = k;
    							}
    							break;
    						}
    					}
    					//没有找到,说明此页面不会再被使用,所以直接进行替换
    					if(number == -1)
    					{
    						s = k;
    						break;
    					}
    				}
    				M[s] = RS[j];
    			}
    		}
    	}
    	return result;
    }
    
    //先进先出置换算法
    int FIFO()
    {
    	result = 0;
    	int p = 0;
    	int count = 0;
    	for(int j = 0;j < MAX;j++)
    	{
    		int judge = 0;
    		if(count < P)
    		{
    			count = full(count,j);
    		}
    		else
    		{
    			//判断是否是缺页
    			judge = lack(count,j);
    			//是缺页,进行置换
    			if(!judge)
    			{
    				result++;
    				M[p] = RS[j];
    				p = (p+1)%P;
    			}
    		}
    	}
    	return result;
    }
    
    //最近最久未使用置换算法
    int LRU()
    {
    	result = 0;
    	int a[P];  //辅组数组,队尾为最近访问页面
    	int count = 0;
    	for(int j = 0;j < MAX;j++)
    	{
    		int judge = 0;
    		if(count < P)
    		{
    			for(int i = 0;i < count;i++)
    			{
    				if(RS[j] == M[i])
    				{
    					judge = 1;
    					//将页面提到队尾
    					int change = M[i];
    					for(int k = i;k < count-1;k++)
    					{
    						a[k] = a[k+1];
    					}
    					a[count-1] = change;
    
    					break;
    				}
    			}
    			if(!judge)
    			{
    				a[count] = RS[j];
    				M[count] = RS[j];
    				count++;
    			}
    		}
    		else
    		{
    			//判断是否是缺页
    			for(int i = 0;i < count;i++)
    			{
    				if(RS[j] == M[i])
    				{
    					judge = 1;
    					//将页面提到队首
    					int change = M[i];
    					for(int k = i;k < P-1;k++)
    					{
    						a[k] = a[k+1];
    					}
    					a[P-1] = change;
    
    					break;
    				}
    			}
    			//是缺页,进行置换
    			if(!judge)
    			{
    				result++;
    				for(int i = 0;i < P;i++)
    				{
    					if(a[0] == M[i])
    					{
    						M[i] = RS[j];
    						for(int k = 0;k < P-1;k++)
    						{
    							a[k] = a[k+1];
    						}
    						a[P-1] = RS[j];
    
    						break;
    					}
    				}
    			}
    		}
    	}
    	return result;
    }
    
    //Clock置换算法
    int CLO()
    {
    	result = 0;
    	int p = 0;
    	int a[MAX];   //辅助数组
    	int count = 0;
    	for(int j = 0;j < MAX;j++)
    	{
    		int judge = 0;
    		if(count < P)
    		{
    			for(int i = 0;i < count;i++)
    			{
    				if(M[i] == RS[j])
    				{
    					a[i] == 1;
    					judge = 1;
    					break;
    				}
    			}
    			if(!judge)
    			{
    				a[count] = 1;
    				M[count] = RS[j];
    				count ++;
    			}
    		}
    		else
    		{
    			for(int i = 0;i < count;i++)
    			{
    				if(M[i] == RS[j])
    				{
    					judge = 1;
    					a[i] = 1;
    					break;
    				}
    			}
    			//是缺页,进行置换
    			if(!judge)
    			{
    				result++;
    				while(1)
    				{
    					if(a[p] == 1)
    					{
    						a[p] = 0;
    						p = (p+1)%P;
    					}
    					else
    					{
    						a[p] = 1;
    						M[p] = RS[j];
    						p = (p+1)%P;
    						break;
    					}
    				}
    			}
    		}
    	}
    	return result;
    }
    
    int main()
    {
    	int condition = 1;
    	while(condition)
    	{
    		//先调用函数生成引用串
    		PRS();
    
    		//对于生成的引用串用各个算法进行效率的测试
    		char a[4][30] = {"最佳置换算法","先进先出置换算法",\
    					     "最近最久未使用置换算法","Clock置换算法"};
    		int r[5];
    		r[0] = OPT();
    		r[1] = FIFO();
    		r[2] = LRU();
    		r[3] = CLO();
    		printf("\n****************************\n");
    		printf("最终结果:\n");
    		for(int i = 0;i < 4;i++)
    		{
    		    double q=(float)r[i]/MAX;
    			printf("%s置换次数:%d,缺页率:%.3f\n",a[i],r[i],q);
    		}
    		printf("1.继续;\n");
    		printf("0.退出;\n");
    		scanf("%d",&condition);
    	}
    	return 0;
    }
    

    5运行结果及分析

    虚拟内存64

     

    算法

    平均置换次数

    最佳置换

    305

    先进先出置换

    389

    最近未使用置换

    1045

    Clock置换

    227

     

    虚拟内存128

    算法

    平均置换次数

    最佳置换

    164

    先进先出置换

    1002

    最近未使用置换

    1028

    Clock置换

    636

     

     

    展开全文
  • 操作系统实验四:页面置换算法 实验报告 1、实验目的 设计和实现最佳置换算法、先进先出置换算法、最近最久未使用置换算法、页面缓冲置换算法;通过页面访问序列随机发生器实现对上述算法的测试及性能比较。 2、页面...

    操作系统实验四:页面置换算法 实验报告

    1、实验目的
    设计和实现最佳置换算法、先进先出置换算法、最近最久未使用置换算法、页面缓冲置换算法;通过页面访问序列随机发生器实现对上述算法的测试及性能比较。

    2、页面置换算法背景知识
    (1) 请求分页虚拟内存管理
    请求分页虚拟内存管理是建立在基本分页基础上的,为了能支持虚拟存储器功能,而增加了请求调页功能和置换功能。
    (2) 工作集
    多数程序都显示出高度的局部性,也就是说,在一个时间段内,一组页面被反复引用。这组被反复引用的页面随着时间的推移,其成员也会发生变化。有时这种变化是剧烈的,有时这种变化则是渐进的。我们把这组页面的集合称为工作集
    (3) 缺页率
    缺页中断次数/总的页面访问次数

    3、实验假设
    (1)模拟的虚拟内存的地址为16位,页面大小为1K,模拟的物理内存有32K。
    (2)表用整数数组或结构数组来表示
    (3) 页面访问序列串是一个整数序列,整数的取值范围为0到N - 1。页面访问序列串中的每个元素p表示对页面p的一次访问
    (4) 符合局部访问特性的随机生成算法

    确定虚拟内存的尺寸N,工作集的起始位置p,工作集中包含的页数e,工作集移动率m(每处理m个页面访问则将起始位置p +1),以及一个范围在0和1之间的值t
    生成m个取值范围在p和p + e间的随机数,并记录到页面访问序列串中
    生成一个随机数r,0 ≤ r ≤ 1
    如果r < t,则为p生成一个新值,否则p = (p + 1) mod N
    如果想继续加大页面访问序列串的长度,请返回第2步,否则结束
    4、实验算法介绍
    (1) 最佳置换算法
    最佳置换算法的主要思想是,在发生页面替换时,被替换的对象应该满足,在以后的页面访问中,该对象不会再次被访问或者较晚被访问。是一种理想化算法,具有最好性能(对于固定分配页面方式,本法可保证获得最低的缺页率),但实际上却难于实现,故主要用于算法评价参照。

    (2) 先进先出置换算法
    先进先出置换算法的主要思想是,在发生页面替换时,被替换的对象应该是最早进入内存的。

    (3) 最近最久未使用置换算法
    最近最久未使用置换算法的主要思想是,在发生页面替换时,被替换的页面应该满足,在之前的访问队列中,该对象截止目前未被访问的时间最长。

    (4) 改进型Clock置换算法
    改进型Clock置换算法的主要思想是,在每次页面替换时,总是尽可能地先替换掉既未被访问又未被修改的页面。

    (5) 页面缓冲算法
    设立空闲页面链表和已修改页面链表采用可变分配和基于先进先出的局部置换策略,并规定被淘汰页先不做物理移动,而是依据是否修改分别挂到空闲页面链表或已修改页面链表的末尾,空闲页面链表同时用于物理块分配,当已修改页面链表达到一定长度如Z个页面时,一起将所有已修改页面写回磁盘,故可显著减少磁盘I/O操作次数。

    5、主要函数功能说明
    (1) 全局共享函数

    void InitMemo();//初始化存储空间,主要是设置分配空间的大小
    void Generate();//生成访问序列
    bool IsInMemo (int n); //指定页号是否已经在内存中

    (2) 最佳置换算法

    void Optimal (int n); //访问一个页面,执行一次最佳置换算法
    void MainOptimal();//算法实现函数

    (3) 先进先出置换算法

    void InitQueue (pQueue q);//初始化队列
    void Qpush (pQueue q, int num);//队列中加入新的页面结点
    void Qpop (pQueue q);//将页面移出内存
    void Qdestroy (pQueue q);//销毁队列
    bool FindQueue (pQueue q, int num);//查找页面是否已经调入内存
    void MainFIFO();//每访问一个页面,执行一次算法
    void FIFO (pQueue q, int num);//先进先出置换算法实现函数

    (4) 最近最久未使用置换算法

    void LRU (int n);//LRU算法实现函数
    void MainLRU();//每访问一个新的页面,执行一次算法

    (5) 改进型clock置换算法

    void UpdatedClock (int n);//改进型clock算法实现函数
    void MainClock();//每访问一个新的页面,执行一次算法

    (6) 页面缓冲算法

    bool IsInPNodes (int n); //页面是否已经在链表中
    void AddLink (int data, int type);//页面添加到已修改页面链表和空闲链表上
    void FreeIdle();//将空闲链表上的所有页面送出内存
    void FreeMod();//将已修改页面链表上所有的链表送出内存
    void PBA (int n);//PBA算法实现函数
    void MainPBA();//每访问一个新的页面,执行一次算法

    6、程序运行结果
    (一)某次的程序运行结果如下
    (1)最佳置换算法
    在这里插入图片描述
    (2)先进先出算法
    在这里插入图片描述
    (3)最近最久未使用置换算法
    在这里插入图片描述
    (4)改进型Clock置换算法
    在这里插入图片描述
    (5)页面缓冲置换算法
    在这里插入图片描述

    (二)多次运行程序,生成不同的访问序列,记录每种算法的缺页情况,最终整理如下
    (1)测试序列1

    置换算法 缺页数 缺页率
    最佳置换算法 17 0.53125
    先进先出置换算法 21 0.65625
    最近最久未使用算法 22 0.6875
    改进型clock置换算法 21 0.65625
    页面缓冲置换算法 15 0.46875
    (2)测试序列2

    置换算法 缺页数 缺页率
    最佳置换算法 14 0.4375
    先进先出置换算法 19 0.59375
    最近最久未使用算法 17 0.53125
    改进型clock置换算法 19 0.59375
    页面缓冲置换算法 18 0.5625
    (3)测试序列3

    置换算法 缺页数 缺页率
    最佳置换算法 14 0.4375
    先进先出置换算法 17 0.53125
    最近最久未使用算法 15 0.46875
    改进型clock置换算法 18 0.5625
    页面缓冲置换算法 16 0.5
    注:访问序列长度为32,默认初始分配给每种算法的内存空间块数为3。
    (三)访问序列长度为32,默认初始分配给每种算法的内存空间块数为5,运行结果如下

    置换算法 缺页数 缺页率
    最佳置换算法 8 0.25
    先进先出置换算法 10 0.3125
    最近最久未使用算法 11 0.34375
    改进型clock置换算法 11 0.34375
    页面缓冲置换算法 9 0.28125
    访问序列长度为32,默认初始分配给每种算法的内存空间块数为8,运行结果如下

    置换算法 缺页数 缺页率
    最佳置换算法 2 0.0625
    先进先出置换算法 6 0.1875
    最近最久未使用算法 4 0.125
    改进型clock置换算法 4 0.125
    页面缓冲置换算法 9 0.28125
    7、实验总结
    根据实验结果可以看出,对同一种算法,对于不同的访问序列,其缺页率是不同,会有所变化。总的来看,最佳置换算法的缺页率是最低的,然后页面缓冲算法的缺页率要低于其他置换算法。改进型clock算法稍微好于先进先出算法和最近最久未使用算法。先进先出算法和最近最久未使用算法性能相近。
    https://github.com/KTlc/lc/blob/master/实验4.cpp

    展开全文
  • 操作系统课程设计报告 课程名称 操作系统课程设计 课程设计题目 页面置换算法 学院 计算机科学与技术学院 专业 科技 小组成员: 庞思慧 E01114081 王蒙 E01114161 慧乔 E01114349 朱潮潮 E01114408 指导老师 邱剑锋 ...
  • 华南理工大学2020秋季作业算法模拟。。。。
  • PAGE PAGE 1 操作系统课程设计报告 课程名称 操作系统课程设计 课程设计题目 页面置换算法 学院 计算机科学与技术学院 专业 科技 小组成员: 庞思慧 E01114081 王蒙 E01114161 姚慧乔 E01114349 朱潮潮 E01114408 ...
  • 操作系统课程设计报告 课 程 名 称 操 作 系 统 课 程 设 计 课程设计题目 页面置换算法 学院 计算机科学与技术学院 专 业 科 技 小 组 成 员 : 庞 思 慧 E01114081 王 蒙 E01114161 姚 慧 乔 E01114349 朱 潮 潮 E...
  • 学 海 无 涯 操作系统课程设计报告 课程名称 操作系统课程设计 课程设计题目 页面置换算法 学院 计算机科学与技术学院 专业 科技 小组成员: 庞思慧 E01114081 王蒙 E01114161 姚慧乔 E01114349 朱潮潮 E01114408 ...
  • 学 海 无 涯 三实验环境 操作系统Windows 7 软件 VC++6.0 四实验设计 本实验包含六种算法基本内容相差不太在实现方面并没有用统一的 数据结构实现而是根据不同算法的特点用不同的数据结构来实现 1最佳置换和随机置换...
  • 学 海 无 涯 操作系统课程设计报告 课程名称 操作系统课程设计 课程设计题目 页面置换算法 学院 计算机科学与技术学院 专 业 科 技 小组成员: 庞思慧 E01114081 1 王蒙 E01114161 姚慧乔 E01114349 朱潮潮 E01114408...
  • 实用标准文案 实验三实验报告 实验源码 #include "stdio.h" #include <iostream.h> #include <stdlib.h> #define DataMax 100 // 常量 DataMax #define BlockNum 10 // 常量 BlockNum int DataShow[BlockNum]...
  • 软件学院设计性实验报告 学院:软件学院 专业:计算机科学与技术 年级/班级:19级JAVA2班 2020—2021学年第二学期 课程名称 操作系统 指导教师 学号姓名 ...

    软件学院设计性实验报告

    学院:软件学院        专业:计算机科学与技术   年级/班级: 19级JAVA2班

    2020—2021学年第二学期

    课程名称

    操作系统

    指导教师

    学号姓名

     魏一鸣

    实验地点

    计算机学院楼111实验室

    实验时间

    6月11日, 6月18日10:10-11:50

    项目名称

    页面置换算法

    实验类型

    综合性

    • 实验目的

    1 、加深对虚拟存储器的理解。

    2 、熟练掌握常用页面置换算法的实现原理。

      • OPT页面置换算法

    OPT所选择被淘汰的页面是已调入内存,且在以后永不使用的,或是在最长时间内不再被访问的页面。因此如何找出这样的页面是该算法的关键。可为每个页面设置一个步长变量,其初值为一足够大的数,对于不在内存的页面,将其值重置为零,对于位于内存的页面,其值重置为当前访问页面与之后首次出现该页面时两者之间的距离,因此该值越大表示该页是在最长时间内不再被访问的页面,可以选择其作为换出页面。

      • FIFO页面置换算法

    FIFO总是选择最先进入内存的页面予以淘汰,因此可设置一个先进先出的忙页帧队列,新调入内存的页面挂在该队列的尾部,而当无空闲页帧时,可从该队列首部取下一个页帧作为空闲页帧,进而调入所需页面。

      • LRU页面置换算法

    LRU是根据页面调入内存后的使用情况进行决策的,它利用“最近的过去”作为“最近的将来”的近似,选择最近最久未使用的页面予以淘汰。该算法主要借助于页面结构中的访问时间来实现,记录一个页面上次的访问时间,因此,当须淘汰一个页面时,选择处于内存的页面中其time值最小的页面,即最近最久未使用的页面予以淘汰。

      • LFU页面置换算法

    LFU要求为每个页面配置一个计数器(即页面结构中的counter),一旦某页被访问,则将其计数器的值加1,在需要选择一页置换时,则将选择其计数器值最小的页面,即内存中访问次数最少的页面进行淘汰。

      • NUR页面置换算法

    NUR要求为每个页面设置一位访问位(该访问位仍可使用页面结构中的counter表示),当某页被访问时,其访问位counter置为1。需要进行页面置换时,置换算法从替换指针开始(初始时指向第一个页面)顺序检查处于内存中的各个页面,如果其访问位为0,就选择该页换出,否则替换指针下移继续向下查找。如果内存中的所有页面扫描完毕未找到访问位为0的页面,则将替换指针重新指向第一个页面,同时将内存中所有页面的访问位置0,当开始下一轮扫描时,便一定能找到counter为0的页面。

    • 实验设备

    实验机房虚拟机里的中linux系统

    • 实验要求
    1. 在FIFO置换算法的基础上,编写实现LRU页面置换算法;
    2. 按如下的访问序列:12560365365604270435,

    在物理块数分别为3和4时,分别调用FIFO和LRU算法,计算并输出相应的命中率。

    • 实验代码
      
      #include <stdio.h>
      
      /*初始化队列*/
      void initializeList(int list[],int number){
          int i;
          for ( i = 0; i < number; i ++) {
              list[i] = -1;
          }
      }
      /*展示队列状态*/
      void showList(int list[], int number){
         int i;
          for ( i = 0; i < number; i ++) {
              printf("%2d",list[i]);
          }
          printf("\n");
      }
      
      /*展示当前内存状态*/
      void showMemoryList(int list[],int phyBlockNum){
          int i;
      
          for ( i = 0; i < phyBlockNum; i ++) {
              if (list[i] == -1) {
                  break;
              }
              printf(" |%d|",list[i]);
          }
          printf("\n");
      }
      
      void informationCount(int missingCount,int replaceCount,int pageNum){
          printf("缺页次数:%d   缺页率:%d/%d\n",missingCount,missingCount,pageNum);
          double result = (double)(pageNum - missingCount)/(double)pageNum;
          printf("置换次数:%d  命中率:%.2f\n",replaceCount,result);
      }
      
      /*找到该页面下次要访问的位置*/
      int getNextPosition(int currentPage,int currentPosition,int strList[],int pageNum){
          int i;
          for ( i = currentPosition+1; i < pageNum; i ++) {
              if (strList[i] == currentPage) {
                  return i;
              }
          }
          
          return 100;
      }
      
      
      /*先进先出置换算法*/
      void replacePageByFIFO(int memoryList[],int phyNum,int strList[],int pageNum){
          
          /*置换次数*/
          int replaceCount = 0;
          /*缺页次数*/
          int missingCount = 0;
          
          /*记录当前最早进入内存的下标*/
          int pointer = 0;
          
          /*记录当前页面的访问情况: 0 未访问*/
          int isVisited = 0;
          int i;
          for (i = 0; i < pageNum; i ++) {
              isVisited = 0;
              
              /*判断是否需要置换->内存已满且需要访问的页面不在内存中*/
              int j;
              for (j = 0; j < phyNum; j ++) {
                  if (memoryList[j] == strList[i]) {
                      /*该页面已经存在内存中*/
                      /*修改访问情况*/
                      isVisited = 1;
                      /*修改访问时间*/
                      /*展示*/
                      printf("%d\n",strList[i]);
                      break;
                  }
                  if (memoryList[j] == -1) {
                      /*页面不在内存中且内存未满->直接存入*/
                      memoryList[j] = strList[i];
                      /*修改访问情况*/
                      isVisited = 1;
                      missingCount ++;
                     /* 展示*/
                      printf("%d\n",strList[i]);
                      showMemoryList(memoryList, phyNum);
                      break;
                  }
              }
              
              if (!isVisited) {
                  /*当前页面还未被访问过->需要进行页面置换*/
                  /*直接把这个页面存到所记录的下标中*/
                  memoryList[pointer] = strList[i];
                  
                  /*下标指向下一个*/
                  pointer ++;
                  
                  /*如果到了最后一个,将下标归零*/
                  if (pointer > phyNum-1) {
                      pointer = 0;
                  }
                  
                  
                  missingCount ++;
                  replaceCount ++;
                  
                 /* 展示*/
                  printf("%d\n",strList[i]);
                  showMemoryList(memoryList, phyNum);
              }
          }
          informationCount(missingCount, replaceCount, pageNum);
      }
      
      
      
      /*最近最久未使用置换算法*/
      void replacePageByLRU(int memoryList[],int phyNum,int strList[],int pageNum){
          
          /*置换次数*/
          int replaceCount = 0;
          /*缺页次数*/
          int missingCount = 0;
      
          /*记录内存中最近一次访问至今的时间*/
          int timeRecord[phyNum];
          /*初始化*/
          initializeList(timeRecord, phyNum);
      
          /*记录当前页面的访问情况: 0 未访问*/
          int isVisited = 0;
          
          /*记录已经在内存中的页面数量*/
          int pageCount = 0;
          int i;
          for ( i = 0; i < pageNum; i ++) {
              isVisited = 0;
              
             /* 时间加一*/
             int p;
              for (p = 0; p < pageCount; p ++) {
                  if (memoryList[p] != -1) {
                      timeRecord[p] ++;
                  }
              }
              
              /*是否需要置换*/
              int j;
              for ( j = 0; j < phyNum; j ++) {
                  if (memoryList[j] == strList[i]) {
                      /*该页面已经存在内存中*/
                      /*修改访问情况*/
                      isVisited = 1;
                     /*重置访问时间*/
                      timeRecord[j] = -1;
                      /*展示*/
                      printf("%d\n",strList[i]);
                      break;
                  }
                  if (memoryList[j] == -1) {
                      /*页面不在内存中且内存未满->直接存入*/
                      memoryList[j] = strList[i];
                      pageCount ++;
                      /*修改访问情况*/
                      isVisited = 1;
                      /*修改访问时间*/
                      timeRecord[j] ++;
                      
                      missingCount ++;
                      /*展示*/
                      printf("%d\n",strList[i]);
                      showMemoryList(memoryList, phyNum);
                      break;
                  }
              }
      
              if (!isVisited) {
                 /* 需要置换*/
                  /*1.遍历时间记录表,寻找最久未访问的页面所在的内存下标*/
                  int max = 0;
                  int k;
                  for ( k = 0; k < phyNum; k ++) {
                      if (timeRecord[max] < timeRecord[k]) {
                          max = k;
                      }
                  }
      
                  /*2.将该位置的页面换出*/
                  memoryList[max] = strList[i];
                  timeRecord[max] = -1;
                  
                  missingCount ++;
                  replaceCount ++;
      
                  /*展示*/
                  printf("%d\n",strList[i]);
                  showMemoryList(memoryList, phyNum);
                  
              }
          }
          informationCount(missingCount, replaceCount, pageNum);
      }
      
      int main(int argc, const char * argv[]) {
          
          /*物理块的数量*/
          int phyBlockNum;
          printf("请输入物理块数量:\n");
          scanf("%d",&phyBlockNum);
          
          /*生成内存队列*/
          int memoryList[phyBlockNum];
          /*初始化内存状态*/
          initializeList(memoryList, phyBlockNum);
          showMemoryList(memoryList,phyBlockNum);
          
          /*页面数量*/
          int pageNum;
          printf("请输入要访问的页面总数:\n");
          scanf("%d",&pageNum);
          
          /*保存页面号引用串*/
          int pageNumStrList[pageNum];
          printf("请输入要访问的页面号:\n");
          int i;
          for (i = 0; i < pageNum; i ++) {
              scanf("%d",&pageNumStrList[i]);
          }
          showList(pageNumStrList, pageNum);
          
          int chose;
          while (1) {
              printf("请选择所需的置换算法:\n");
              printf("1.FIFO 2.LRU 3.退出\n");
              scanf("%d",&chose);
              
              switch (chose) {
                  
                  case 1:
                      showList(pageNumStrList, pageNum);
                      replacePageByFIFO(memoryList, phyBlockNum, pageNumStrList, pageNum);
                      /*重新初始化内存*/
                      initializeList(memoryList , phyBlockNum);
                      break;
                  case 2:
                      showList(pageNumStrList, pageNum);
                      replacePageByLRU(memoryList, phyBlockNum, pageNumStrList, pageNum);
                      /*重新初始化内存*/
                      initializeList(memoryList, phyBlockNum);
                      break;
                  default:
                      return 0;
                      break;
              }
          }
          
          return 0;
      }
      

    • 结果分析与总结

    物理块数为3

    调用FIF0算法结果:

    调用LRU算法结果:

    物理块为4

    调用FIFO算法结果:

    调用LRU算法结果:

    展开全文
  • 页面置换算法演示 实验目的 1. 分析内存管理办法中每个页面置换算法原理; 2. 掌握页面置换算法执行过程。 二、实验预备内容 1. 熟悉内存管理办法; 2. 熟悉页面置换算法原理; 3. 熟悉不同页面置换算法的置换过程。...
  • 操作系统实验七:内存页面置换算法实验报告。加深对于存储管理的了解,掌握虚拟存储器的实现原理;观察和了解重要的页面置换算法和置换过程。练习模拟算法的编程技巧,锻炼分析试验数据的能力。实验内容:在以上示例...
  • 编程实现页面置换算法,最少实现两种算法,比较算法的优劣,并将调试结果显示在计算机屏幕上,检测机算和笔算的一致性。 (1)采用页式分配存储方案,通过分别计算不同算法的命中率来比较算法的优劣,同时也考虑页面...
  • 页面置换算法课题实验报告

    千次阅读 2019-05-28 00:20:18
    安全1601_沈香港_16281077_操作系统lab4页面置换算法实验目的以及基本要求一、概要设计1.1模块1.2功能二、实现2.1数据结构设计2.2随机生成页面访问序列2.3模拟运行OPT页面替换算法2.4模拟运行LRU页面替换算法2.5模拟...
  • 实验编号 名称 页面置换算法模拟 实验目的 通过请求页式存储管理中页面置换算法模拟设计以便 1了解虚拟存储技术的特点 2掌握请求页式存储管理中页面置换算法 实验内容与步骤 设计一个虚拟存储区和内存工作区并使用 ...
  • 操作系统原理 实验报告 实验三 页面置换算法实验 专业 计算机科学与技术 学号 030840204 姓名 简郸 实验日期 2010-5-22 实验目的 通过模拟实现请求页式存储管理的几种基本页面置换算法了解虚拟存储技术的特点掌握...
  • 页面置换算法模拟(实验报告

    千次阅读 2020-01-02 14:52:20
    (2) 深入了解FIFO、LRU页面置换算法 实验内容 在集成开发环境下使用C++语言设计并实现FIFO、LRU页面置换算法,并进行相应的测试。 实验原理 (1) 分别实现FIFO、LRU页面置换算法; (2) 页面序...
  • 一、实验题目:页面置换算法(请求分页) 二、实验目的: 进一步理解父子进程之间的关系。 1) 理解内存页面调度的机理。 2) 掌握页面置换算法的实现方法。 3) 通过实验比较不同调度算法的优劣。 4) 培养综合...
  • 操作系统 课程设计报告 院 系 衡阳师范学院 专 业 计算机科学与技术 姓 名: 陈建元 齐欢 班 级 1103班 学 号: 11190301 11190316 题 目 页面置换算法 指导教师: 王玉奇 2013年12月10日至12月28日 目 录 TOC \o "1-3...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 697
精华内容 278
关键字:

页面置换算法实验报告