操作系统实验_实验3

XX大学学生实验报告

开课学院及实验室：计算机科学与工程实验室2021 年12月1日 实验课

操作系统实验成绩

程名称 实验项

内存管理指导教师

目名称

(***报告只能为文字和图片, 教师评语将添加到此处 , 学生请勿作答 ***) 一、实验目的

通过模拟实现请求页式存储管理的几种根本页面置换算法，了解虚拟存储

技术的特点，掌握虚拟存储请求页式存储管理中几种根本页面置换算法的根本思想和实现过程，

并比拟它们的效率。 二、实验内容

实验 1：

设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。 1、最正确淘汰算法〔OPT〕 2、先进先出的算法〔FIFO 〕 3、最近最久未使用算法〔LRU 〕 4、最不经常使用算法〔LFU 〕 5、最近未使用算法〔NUR 〕

命中率＝１－页面失效次数／页地址流长度 实验 2：

在 Linux 环境下利用以下系统调用 malloc() ， free()编写一段程序实现内存分配与回收的管理。

要求：

1、返回已分配给变量的内存地址； 2、返回释放后的内存地址；

3、释放已分配的内存空间后，返回释放内存后未使用内存的大小。 三、实验原理

UNIX中，为了提高内存利用率，提供了内外存进程对换机制；内存空间的分配和回 收均以页为单位进展；一个进程只需将其一局部〔段或页〕调入内存便可运行；还支持请求调页的存储管理方式。

当进程在运行中需要访问某局部程序和数据时，发现其所在页面不在内存，就立即提出请求〔向 CPU 发出缺中断〕，由系统将其所需页面调入内存。这种页面调入方式叫请求调页。为实现请求调页，核心配置了四种数据构造：页表、页框号、访问位、修改位、有效位、保护位等。

当 CPU 接收到缺页中断信号，中断处理程序先保存现场，分析中断原因，转入缺页中断处理程序。该程序通过查找页表，得到该页所在外存的物理块号。如果此时内存未满，

能容纳新页，那么启动磁盘I/O 将所缺之页调入内存，然后修改页表。如果内存已满，那么须 按某种置换算法从内存中选出一页准备换出，是否重新写盘由页表的修改位决定，然后将缺页调入，修改页表。利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。整个页面的调入过程对用户是透明的。

----

----

四、实验设备

安装了 Linux 系统的电脑 五、实验程序 实验 1：

#include #include #define TRUE 1 #define FALSE 0

#define INV ALID -1 //#define NULL 0

#define total_instruction 320 #define total_vp 32 #define clear_period 50 typedef struct {

int pn,pfn,counter,time; }pl_type;

pl_type pl[total_vp]; struct pfc_struct{ int pn,pfn;

struct pfc_struct *next; };

typedef struct pfc_struct pfc_type; pfc_type

pfc[total_vp],*freepf_head,*busypf_head,*busypf_tail; int diseffect, a[total_instruction];

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,j;

srand(10*getpid());

s=(float)319*rand( )/32767/32767/2+1; for(i=0;iif(s<0||s>319) {

printf(\"When i==%d,Error,s==%d\\n\

----

----

exit(0); }

a[i]=s;

a[i+1]=a[i]+1;

a[i+2]=(float)a[i]*rand( )/32767/32767/2; a[i+3]=a[i+2]+1;

s=(float)(318-a[i+2])*rand( )/32767/32767/2+a[i+2]+2; if((a[i+2]>318)||(s>319))

printf(\"a[%d+2],a number which is :%d and s==%d\\n\}

for (i=0;ipage[i]=a[i]/10; offset[i]=a[i]%10; }

for(i=4;i<=32;i++) {

printf(\"---%2d page frames---\\n\FIFO(i); LRU(i); LFU(i); NUR(i); OPT(i); }

return 0; }

int initialize(total_pf) int total_pf; {

int i;

diseffect=0;

for(i=0;ipl[i].pn=i;

pl[i].pfn=INV ALID; pl[i].counter=0; pl[i].time=-1; }

for(i=0;ipfc[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]; return 0; }

int FIFO(total_pf) int total_pf; {

int i,j;

pfc_type *p;

initialize(total_pf);

busypf_head=busypf_tail=NULL; for(i=0;iif(pl[page[i]].pfn==INV ALID) {

diseffect+=1;

if(freepf_head==NULL) {

p=busypf_head->next;

pl[busypf_head->pn].pfn=INV ALID; freepf_head=busypf_head; freepf_head->next=NULL; busypf_head=p; }

p=freepf_head->next; freepf_head->next=NULL; freepf_head->pn=page[i];

pl[page[i]].pfn=freepf_head->pfn; if(busypf_tail==NULL)

busypf_head=busypf_tail=freepf_head; else {

busypf_tail->next=freepf_head; busypf_tail=freepf_head; }

freepf_head=p; } }

printf(\"FIFO:%6.4f\\n\return 0; }

int LRU (total_pf) int total_pf; {

----

----

int min,minj,i,j,present_time; initialize(total_pf); present_time=0;

for(i=0;iif(pl[page[i]].pfn==INV ALID) {

diseffect++;

if(freepf_head==NULL) {

min=32767;

for(j=0;jif(min>pl[j].time&&pl[j].pfn!=INVALID) {

min=pl[j].time; minj=j; }

freepf_head=&pfc[pl[minj].pfn]; pl[minj].pfn=INV ALID; pl[minj].time=-1;

freepf_head->next=NULL; }

pl[page[i]].pfn=freepf_head->pfn; pl[page[i]].time=present_time; freepf_head=freepf_head->next; } else

pl[page[i]].time=present_time; present_time++; }

printf(\"LRU:%6.4f\\n\return 0; }

int NUR(total_pf) int total_pf; {

int i,j,dp,cont_flag,old_dp; pfc_type *t;

initialize(total_pf); dp=0;

for(i=0;iif (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;jfreepf_head=&pfc[pl[dp].pfn]; pl[dp].pfn=INV ALID; freepf_head->next=NULL; }

pl[page[i]].pfn=freepf_head->pfn; freepf_head=freepf_head->next; } else

pl[page[i]].counter=1; if(i%clear_period==0) for(j=0;jprintf(\"NUR:%6.4f\\n\return 0; }

int OPT(total_pf) int total_pf;

{int i,j, max,maxpage,d,dist[total_vp]; pfc_type *t;

initialize(total_pf);

for(i=0;iif(pl[page[i]].pfn==INV ALID) {

diseffect++;

if(freepf_head==NULL) {for(j=0;j----

----

if(pl[j].pfn!=INVALID) dist[j]=32767; else dist[j]=0; d=1;

for(j=i+1;jif(pl[page[j]].pfn!=INV ALID) dist[page[j]]=d; d++; }

max=-1;

for(j=0;jmax=dist[j]; maxpage=j; }

freepf_head=&pfc[pl[maxpage].pfn]; freepf_head->next=NULL; pl[maxpage].pfn=INV ALID; }

pl[page[i]].pfn=freepf_head->pfn; freepf_head=freepf_head->next; } }

printf(\"OPT:%6.4f\\n\return 0; }

int LFU(total_pf) int total_pf; {

int i,j,min,minpage; pfc_type *t;

initialize(total_pf);

for(i=0;iif(pl[page[i]].pfn==INV ALID) {

diseffect++;

if(freepf_head==NULL) {

min=32767;

for(j=0;j{if(min>pl[j].counter&&pl[j].pfn!=INVALID) {

----

----

min=pl[j].counter; minpage=j; }

pl[j].counter=0; }

freepf_head=&pfc[pl[minpage].pfn]; pl[minpage].pfn=INV ALID; freepf_head->next=NULL; }

pl[page[i]].pfn=freepf_head->pfn; pl[page[i]].counter++;

freepf_head=freepf_head->next; } else

pl[page[i]].counter++; }

printf(\"LFU:%6.4f\\n\return 0; }

实验 2

#include using namespace std; #include #include #include //#include int main() {

int *string;

string=(int*) malloc(10); if(string==NULL)

printf(\"Insufficient memory available\\n\"); else {

printf(\"Memory space allocated for path name\\n\"); cout<<\"string=\"<printf(\"Memory freed\\n\"); }

int *stringy;

stringy=(int*)malloc(12);

----

----

if(stringy==NULL)

printf(\"Insufficient memory available\\n\"); else {

printf(\"Memory space allocated for path name\\n\"); cout<<\"stringy=\"<printf(\"Memory freed\\n\"); } }

六、实验结果 试验 1：

从几种算法的命中率看，OPT 最高，其次为NUR 几，最低的是LFU 。但每个页面执行结果会有所不同。 错误。

相对较高，而FIFO 与 LRU 相差无 OPT 算法在执行过程中可能会发生

----

----

试验 2：

第一次调用malloc ，申请 10 个字节大小的连续内存空间，返回该内存空间的首地址 string ，释放后，第二次调用malloc ，申请 12 个字节大小的内存空间，返回stringy ，与 string 值一样。在第一次调用并释放后，增加一句：string=NULL; 发现，此时第二次调用

malloc ，结果是： Insufficientmemory available ，说明，调用 malloc 后返回为空。在第二次 调用 malloc 时，实际上并没有重新申请空间。 七、问题答复分析

为什么 OPT 在执行时会有错误产生？

答： OPT 算法：在将来不出现的或最晚出现的先淘汰，可以看出，它是一种对未来的假设判断，假设知道了将来要使用的页面，从而根据该情况来作出选择，但是进程是动态执行的，未来是无法预知的，所以，当碰到这种未来假设与实际不符时就会出现错误。

----