操作系统实验—存储管理

article/2025/10/29 3:30:05

操作系统实验—存储管理

所有实验源码：

gitee：https://gitee.com/infiniteStars/os-project

github：https://github.com/helloworldzsq/OSproject

1.实验内容

设计一个虚拟存储区和内存工作区，并使用下述方法计算访问命中率。

① 进先出的算法（FIFO）；

②最近最少少使用算法(LRU);

③最佳淘汰算法(OPT):选淘汰最不常用的页地址;

④最少访问页面算法(LFR);

⑤最近最不经常使用算法(NUR)；

⑥简单 Clock 淘汰算法及改进型 Clock 淘汰算法.

（其中④⑤⑥为选择内容）

命中率= 1 - 页面失效次数 / 页地址流长度

2.实验要求

本实验课题功能设计要求如下：

（1）编程设计实现最佳淘汰算法、先进先出淘汰算法、最近最久未使用淘汰算法、最少访问页面算法(LFR)、最近最不经常使用算法(NUR).；

（2）编程设计实现页面访问序列的随机产生机制，包括各页面读写访问方式的设定算法的要求；

（3）在执行进程和访问各页面过程中，每访问一个（或一次）页面应显示输出当时的进程页表内容（包括页号、物理块号、状态位、读/写访问方式等字段）及本次页面访问操作情况（譬如页面已在内存或触发缺页中断）；

（4）基于相同的条件，包括系统均采用固定分配局部置换策略、相同的进程逻辑地址空间大小（暨逻辑页面数，设进程逻辑地址空间的页面总数为 N，则其页号取值区间为[0, N)）、分配给进程同样多的物理块（设进程分配获得 S 个物理块，则相应物理块号分别标记为 PF0 、 PF1、……、PFN-1）、相同的页面访问序列（整数序列，整数取值区间为[0, N)）、均预装入前三个页面，进行有关算法的测试；

（5）变换上述条件实施多次测试，统计分析和比较有关算法的性能（譬如缺页率、淘汰页、查找时间开销）。

3.运行结果

  • 可以看到随着页面数量的不断增多，各种算法的命中率也逐渐增加

image-20211216153644638

4. 实验源码

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#define TRUE 1
#define FALSE 0
#define INVALID -1
#define NULL  0
#define  total_instruction 320     //指令数
#define  total_vp  32               //虚拟页数量
#define  clear_period  50           //清0周期//页面结构
typedef struct
{int pn;      //进程的页号int pfn;     //物理内存的块号int counter; //一个周期内访问该页面的次数int time;    //访问时间
}pl_type;pl_type pl[total_vp];                      /*页面线性结构---指令序列需要使用地址*///页面控制结构
typedef struct pfc_struct
{int pn;int pfn;struct pfc_struct *next;
}pfc_type;//1.定义用户进程虚页控制结构 result.空页面头指针 3. 忙页面头指针  4. 忙页面尾指针
pfc_type pfc[total_vp], *freepf_head, *busypf_head, *busypf_tail;
//1.页面失效次数  result.a[]  指令序列
int diseffect,  a[total_instruction];
//1. 每条指令所在的页号 result.每页装入10条指令后取模运算页号偏移值
int page[total_instruction],  offset[total_instruction];int  initialize(int);
int  FIFO(int);
int  LRU(int);
int  LFU(int);
int  NUR(int);
int  OPT(int);
int main( )
{int s,i;srand(10*getpid());                    /*由于每次运行时进程号不同，故可用来作为初始化随机数队列的“种子”*///rand() 返回一个范围在 0 到 RAND_MAX 之间的伪随机数。//RAND_MAX 是一个常量，它的默认值在不同的实现中会有所不同，但是值至少是 32767s=(float)319*rand()/32767+1;for(i=0;i<total_instruction;i+=4)        /*产生指令队列*/{if(s<0||s>319){printf("When i==%d,Error,s==%d\n",i,s);exit(0);}a[i]=s;                                   /*任选一指令访问点m*/a[i+1]=a[i]+1;                            /*顺序执行一条指令*/a[i+2]=(float)a[i]*rand()/32767;          /*执行前地址指令m*/a[i+3]=a[i+2]+1;                          /*顺序执行一条指令*/s=(float)(318-a[i+2])*rand( )/32767+a[i+2]+2;if((a[i+2]> 318)|| (s>319))printf("a[%d+result],a number which is :%d and s==%d\n",i,a[i+2],s);}//将指令序列转换成页号，偏移值for (i=0;i<total_instruction;i++) /*将指令序列变换成页地址流*/{page[i]=a[i]/10;offset[i]=a[i]%10;}//   从四个页面到32个，查看命中率for(i=4;i<=32;i++){printf("---%2d page frames---\n",i);//先进先出置换算法FIFO(i);//最近最久未使用算法LRU(i);//最近不经常使用算法LFU(i);//最近最不经常使用算法NUR(i);//最佳置换算法OPT(i);}return 0;
}/*初始化相关数据结构 total_pf表示内存的块数 */
int initialize(int total_pf)
{int i;diseffect=0;for(i=0;i<total_vp;i++){pl[i].pfn=INVALID;       /*置页面控制结构中的页号，页面为空*/pl[i].counter=0;         /*页面控制结构中的访问次数为0*/pl[i].time=-1;           /*访问的时间*/}for(i=0;i<total_pf-1;i++)	/*建立pfc[i-1]和pfc[i]之间的链接*/{pfc[i].next=&pfc[i+1];pfc[i].pfn=i;}pfc[total_pf-1].next=NULL;pfc[total_pf-1].pfn=total_pf-1;freepf_head=&pfc[0];         /*空页面队列的头指针为pfc[0]*/return 0;
}int FIFO(int total_pf)              /*先进先出算法total_pf:用户进程的内存页面数*/
{int i;pfc_type *p;					/*中间变量*/initialize(total_pf);         /*初始化相关页面控制用数据结构*/busypf_head=busypf_tail=NULL; /*忙页面队列头，队列尾链接*/for(i=0;i<total_instruction;i++){if(pl[page[i]].pfn==INVALID)   /*页面失效*/{diseffect+=1;                  /*失效次数*/if(freepf_head==NULL)         /*无空闲页面*/{p=busypf_head->next;//将第一个忙页面释放pl[busypf_head->pn].pfn=INVALID;freepf_head=busypf_head;  /*释放忙页面队列的第一个页面*/freepf_head->next=NULL;  /*表明还是缺页*/busypf_head=p;}p=freepf_head->next;freepf_head->pn=page[i];pl[page[i]].pfn=freepf_head->pfn;freepf_head->next=NULL;if(busypf_tail==NULL){busypf_tail = busypf_head = freepf_head;}else{busypf_tail->next=freepf_head;busypf_tail=freepf_head;}freepf_head=p;}}//命中率  %6.4含义：总共六位数，四位小数，一个小数点，整数1位printf("FIFO : %6.4f " , 1-(float)diseffect/320);return 0;
}
int LRU (int total_pf)       /*最近最久未使用算法least recently used*/
{int min,minj,i,j,present_time; /*minj为最小值下标*/initialize(total_pf);present_time=0;for(i=0;i<total_instruction;i++){if(pl[page[i]].pfn==INVALID)             /*页面失效*/{diseffect++;if(freepf_head==NULL)              /*无空闲页面*/{min=32767;						/*设置最大值*/for(j=0;j<total_vp;j++)            /*找出time的最小值*/{if(min>pl[j].time&&pl[j].pfn!=INVALID){min=pl[j].time;minj=j;}}freepf_head=&pfc[pl[minj].pfn];   //腾出一个单元pl[minj].pfn=INVALID;pl[minj].time=0;freepf_head->next=NULL;}pl[page[i]].pfn=freepf_head->pfn;   //有空闲页面,改为有效pl[page[i]].time=present_time;freepf_head=freepf_head->next;      //减少一个free 页面}else{pl[page[i]].time=present_time;        //命中则增加该单元的访问次数present_time++;}}printf("LRU:%6.4f ",1-(float)diseffect/320);return 0;
}int NUR(int  total_pf )                  /*最近未使用算法Not Used recently count表示*/
{int i,j,dp,cont_flag,old_dp;pfc_type *t;initialize(total_pf);dp=0;for(i=0;i<total_instruction;i++){if (pl[page[i]].pfn==INVALID)         /*页面失效*/{diseffect++;if(freepf_head==NULL)               /*无空闲页面*/{cont_flag=TRUE;old_dp=dp;while(cont_flag){if(pl[dp].counter==0&&pl[dp].pfn!=INVALID)cont_flag=FALSE;else{dp++;if(dp==total_vp)dp=0;if(dp==old_dp)for(j=0;j<total_vp;j++)pl[j].counter=0;}}freepf_head=&pfc[pl[dp].pfn];pl[dp].pfn=INVALID;freepf_head->next=NULL;}pl[page[i]].pfn=freepf_head->pfn;freepf_head->pn=page[i];freepf_head=freepf_head->next;}elsepl[page[i]].counter=1;if(i%clear_period==0)for(j=0;j<total_vp;j++)pl[j].counter=0;}printf("NUR:%6.4f ",1-(float)diseffect/320);return 0;
}int OPT(int total_pf)       /*最佳置换算法*/
{int i,j, max,maxpage,d,dist[total_vp];pfc_type *t;initialize(total_pf);for(i=0;i<total_instruction;i++){if(pl[page[i]].pfn==INVALID)      /*页面失效*/{diseffect++;if(freepf_head==NULL)         /*无空闲页面*/{for(j=0;j<total_vp;j++){if(pl[j].pfn!=INVALID)dist[j]=32767;elsedist[j]=0;}for(j=0;j<total_vp;j++){if((pl[j].pfn!=INVALID)&&(dist[j]==32767)){dist[j]=j;}}max=0;for(j=0;j<total_vp;j++)if(max<dist[j]){max=dist[j];maxpage=j;}freepf_head=&pfc[pl[maxpage].pfn];freepf_head->next=NULL;pl[maxpage].pfn=INVALID;}pl[page[i]].pfn=freepf_head->pfn;freepf_head=freepf_head->next;}}printf("OPT:%6.4f\n",1-(float)diseffect/320);return 0;
}
/*该算法时根据已知的预测未知的，least frequency  Used是最不经常使用置换法*/
int  LFU(int total_pf)
{int i,j,min,minpage;pfc_type *t;initialize(total_pf);for(i=0;i<total_instruction;i++){if(pl[page[i]].pfn==INVALID)      /*页面失效*/{diseffect++;if(freepf_head==NULL)          /*无空闲页面*/{min=32767;/*获取counter的使用用频率最小的内存*/for(j=0;j<total_vp;j++){if(min>pl[j].counter&&pl[j].pfn!=INVALID){min=pl[j].counter;minpage=j;}}freepf_head=&pfc[pl[minpage].pfn];pl[minpage].pfn=INVALID;pl[minpage].counter=0;freepf_head->next=NULL;}pl[page[i]].pfn=freepf_head->pfn;   //有空闲页面,改为有效pl[page[i]].counter++;freepf_head=freepf_head->next;      //减少一个free 页面}else{pl[page[i]].counter;pl[page[i]].counter=pl[page[i]].counter+1;}}printf("LFU:%6.4f ",1-(float)diseffect/320);return 0;
}

http://chatgpt.dhexx.cn/article/QRTac6fW.shtml

相关文章

操作系统实验——磁盘调度算法

操作系统实验——磁盘调度算法

文章目录 前言一、实验目的二、实验内容和要求三、实验程序四、运行结果运行结果截图 五、思考和分析程序实现(思路)&#xff1a;分析几种算法&#xff1a; 附 前言 提示&#xff1a;本次实验在Linux(Ubuntu)中运行&#xff0c;程序中读取的文件需放在与c文件同一个文件夹中&a…
阅读更多...
北航操作系统实验入门

北航操作系统实验入门

有北航操作系统实验平台账号的部分读者反映不会操作。为了让读者尽快了解实验平台的操作&#xff0c;下面介绍lab0的实验步骤&#xff0c;希望读者能尽快掌握实验平台的使用方法。 1. 用学生账号登录 2. 点击【操作系统实验】进入实验界面 3. lab0实验环境介绍&#xff0c;仔细…
阅读更多...
操作系统实验三进程间通信

操作系统实验三进程间通信

文末也可直接获取实验文档 实验三 进程间通信 目录 1实验目的2 实验内容3实验详细操作步骤及程序清单&#xff1a;4相关问题及思考5总结6背景知识 1实验目的 1、了解linux系统中进程通信的基本原理。 2、分析进程竞争资源现象&#xff0c;学习解决进程互斥的方法。 2 实验内…
阅读更多...
操作系统实验——进程控制

操作系统实验——进程控制

操作系统实验——进程控制 预习内容&#xff1a; 1.进程的概念 ⑴程序的并发执行 ⑵进程的定义 2.进程的描述 ⑴进程控制块 ⑵进程上下文 ⑶进程上下文切换 ⑷进程空间与大小 3. 进程状态及其转换 ⑴进程状态 ⑵进程状态转换 4.进程控制 ⑴进程创建与撤销 ⑵进程的阻塞与唤醒…
阅读更多...
操作系统实验一

操作系统实验一

操作系统实验一 进程调度算法 一、实验目的 1.理解操作系统进程管理中进行进程调度的过程和调度算法的思想原理&#xff1b; 创建进程控制块PCB&#xff0c;并合理组织就绪队列。 2.理解进程的状态及变化&#xff0c;动态显示每个进程的当前状态及进程的调度情况。 掌握几…
阅读更多...
操作系统实验一·创建进程

操作系统实验一·创建进程

创建进程 1实验目的2实验内容&#xff1a;2.1Windows实现2.2Linux实现 3实验环境3.1Windows3.2Linux虚拟机 4程序设计和实现4.1Windows实现4.1.1函数解释4.1.2程序代码4.1.3运行结果 4.2Linux实现4.2.1函数解释4.2.2程序代码4.2.3运行结果 Use system calls to implement a “m…
阅读更多...
操作系统实验

操作系统实验

实验一 命令解释程序 实验内容 利用C语言编写一个微型命令解释程序minishell.c&#xff0c;该程序可接收并解释以下命令&#xff1a; (1) dir 列出当前目录 (2) cop file1 file2 拷贝文件 (3) era filename 删除文件 (4) disp string 显示字符串 (5) end 结束&#xff0c;退出…
阅读更多...
操作系统实验报告

操作系统实验报告

操作系统 一、实验一 通过 VMware 虚拟机软件安装 Linux二、实验目的三、实验内容&#xff08;实验原理/运用的理论知识、算法/程序流程图、步骤和方法、关键源代码&#xff09;四、实验结果与分析五、小结与心得体会 一、实验二 Windows 进程管理二、实验目的三、实验内容&…
阅读更多...
操作系统实验——银行家算法

操作系统实验——银行家算法

文章目录 一、实验目的二、实验内容和要求三、实验原理算法实现 四、实验程序代码如下&#xff1a; 五、验证数据和运行结果运行结果截图 六、思考与分析附 一、实验目的 掌握银行家算法思想&#xff0c;并能编程实现。 二、实验内容和要求 1、在Linux环境下编译运行程序&am…
阅读更多...
操作系统实验（进程调度）

操作系统实验（进程调度）

操作系统实验&#xff08;进程调度&#xff09; 一、实验目的二、实验内容三、实验准备3.1优先权算法3.2时间片轮转调度算法 四、实验 一、实验目的 1.1理解有关进程控制块、进程队列的概念。   1.2掌握进程优先权调度算法和时间片轮转调度算法的处理逻辑。 二、实验内容 2.1…
阅读更多...
【MFC】CCriticalSection类在Release编译下调用Lock函数会报0xC0000008错误

【MFC】CCriticalSection类在Release编译下调用Lock函数会报0xC0000008错误

【MFC】CCriticalSection类在Release编译下调用Lock函数会报错0xC0000008 问题描述方法一 CRITICAL_SECTION代替CCriticalSection方法二 使用WaitForSingleObject和ReleaseMutex()结语 问题描述 通过以下伪代码方式描述问题&#xff1a; 主对话框类内创建成员变量及结构体变量…
阅读更多...
联合使用类CCriticalSection和类CSingleLock同步线程

联合使用类CCriticalSection和类CSingleLock同步线程

&#xff08;1&#xff09;新建一个控制台工程SellTicketTest2&#xff0c;并在向导的“应用程序设置”中勾选“MFC”。 &#xff08;2&#xff09;打开SellTicketTest2.cpp&#xff0c;在开头中引入头文件。 #include "afxmt.h"&#xff08;3&#xff09;添加变量&…
阅读更多...
单独使用CCriticalSection对象来同步线程

单独使用CCriticalSection对象来同步线程

&#xff08;1&#xff09;新建一个控制台工程SellTicketTest&#xff0c;并在向导的“应用程序设置”中勾选“MFC”&#xff0c;因为CCriticalSection属于MFC类&#xff0c;如图所示。 &#xff08;2&#xff09;在SellTicketTest.cpp开头中引入头文件。 #include "afx…
阅读更多...
linux查看java线程死锁_ccriticalsection 多线程 死锁_c++ 线程死锁_linux 线程 死锁

linux查看java线程死锁_ccriticalsection 多线程 死锁_c++ 线程死锁_linux 线程 死锁

qq_407283393122018-12-10 一个很蠢的造成死锁的问题 wanglt3113172018-12-12 什么是死锁&#xff0c;死锁的原因&#xff0c;如何避免 apanying902019-01-09 c3p0连接死锁 Cain_1507662016-09-20 notify产生死锁的场景(备忘) liuchuanyangyan9132017-02-23 C3P0配置错误导致的…
阅读更多...
MFC线程同步—— CCriticalSection类使用

MFC线程同步—— CCriticalSection类使用

多个线程访问临界区时&#xff0c;可以使用临界区对象。临界区对象是一个独占性共享资源&#xff0c;任一时刻只有一个线程可以拥有临界区。拥有临界区的线程可以访问被保护起来的资源或代码段&#xff0c;其他希望进入临界区的线程将被挂起等待&#xff0c;直到拥有临界区的线…
阅读更多...
CCriticalSection与CSingleLock

CCriticalSection与CSingleLock

CCriticalSection An object of class CCriticalSection represents a “critical section” — a synchronization object that allows one thread at a time to access a resource or section of code. Critical sections are useful when only one thread at a time can be …
阅读更多...
关键部分CCriticalSection使用

关键部分CCriticalSection使用

类CCriticalSection的对象表示一个“临界区”&#xff0c;它是一个用于同步的对象&#xff0c;同一时刻仅仅同意一个线程存取资源或代码区。临界区在控制一次仅仅有一个线程改动数据或其他的控制资源时很实用。比如&#xff0c;在链表中添加一个结点就仅仅同意一次一个线程进行…
阅读更多...
模拟售票大厅实例——多线程时访问共享变量时的安全（CMutex或CCriticalSection的应用)

模拟售票大厅实例——多线程时访问共享变量时的安全（CMutex或CCriticalSection的应用)

当程序运行时&#xff0c;可以通过多线程来提高程序运行的效率和拥有更好的体验。但多线程&#xff08;或多进程&#xff09;同时也带来很多的问题&#xff1a;最严重的莫过于对同一个对象或变量访问时&#xff0c;由于线程运行异步的原因&#xff0c;会造成程序运行出现无法控…
阅读更多...
在MFC下面实际演示CCriticalSection 的使用

在MFC下面实际演示CCriticalSection 的使用

Q&#xff1a;CCriticalSection是什么&#xff1f; A&#xff1a;CCriticalSection是一种线程同步策略 或者说技术 或者方法 总之呢就是这么个意思。。。。 参考资料&#xff1a; http://blog.csdn.net/akof1314/article/details/5773076 http://www.cnblogs.com/hlxs/archi…
阅读更多...
Android对话框总结(普通对话框,单选对话框，多选对话框，自定义对话框)

Android对话框总结(普通对话框,单选对话框，多选对话框，自定义对话框)

个人推荐: &#x1f4e2;&#x1f4e2;&#x1f4e2; 前些天发现了一个蛮有意思的人工智能学习网站,8个字形容一下 "通俗易懂&#xff0c;风趣幽默"&#xff0c;感觉非常有意思,忍不住分享一下给大家。点击跳转到教程。 一:AlterDialog对话框 二:普通对话框 运行效果…
阅读更多...
推荐文章

Copyright @ 2022~2023