计算机操作系统实验四存储管理-阿里云开发者社区

计算机操作系统实验四存储管理

2023-07-14 335

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 计算机操作系统实验四存储管理

一、实验目的

通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。

二、实验内容

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

1、最佳（Optimal）置换算法

2、先进先出（FIFO）置换算法

3、最近最久未使用（LRU）置换算法

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

三、实验代码及注释

1、数据结构

（1）页面类型

1. typedef struct     /*页面结构*/
2. {
3.    int pn,pfn,time;
4. }pl_type;

其中pn为页面号，pfn为页帧号，time为访问时间

（2）页帧控制结构

1. struct pfc_struct{     /*页帧控制结构*/
2.    int pn,pfn;
3.    struct pfc_struct *next;
4. };
5. typedef struct pfc_struct pfc_type;
6. pfc_type pfc[total_vp],*freepf_head,*busypf_head,*busypf_tail;

其中pfc_type pfc[total_vp]定义用户进程虚页控制结构

*freepf_head为空闲页帧头的指针

*busypf_head为忙页帧头的指针

*busypf_tail忙页帧尾的指针

2、函数定义

void initialize(int):初始化函数

void OPT(int):计算使用OPT算法时的命中率

void FIFO(int):计算使用FIFO算法时的命中率

void LRU(int):计算使用LRU算法时的命中率

3、变量定义

int a[total_instruction]:指令流数组

int diseffect:页面失效次数

int page[total_instruction]:每条指令所属页面号

int offset[total_instruction]:每页装入10条指令后取模运算得出的页内偏移地址

int total_pf:用户进程的内存页面数

参考代码

1. #include <stdlib.h>
2. #include<stdio.h>
3. #define TRUE 1
4. #define FALSE 0
5. #define INVALID -1
6. #define total_instruction  12     /*指令流长*/
7. #define total_vp  6               /*虚页长*/
8. typedef struct                 
9. {
10.        int pn,pfn,time;
11. }pl_type;
12. pl_type pl[total_vp];             
13. struct pfc_struct{                 
14.        int pn,pfn;
15.        struct pfc_struct *next;
16. };
17. typedef struct pfc_struct pfc_type;
18. pfc_type pfc[total_vp],*freepf_head,*busypf_head,*busypf_tail;
19. int diseffect,a[total_instruction];
20. int page[total_instruction],offset[total_instruction];
21. void initialize(int total_pf)      /*初始化相关数据结构*/
22. {
23.        int i;
24.        diseffect=0;
25.        for(i=0;i<total_vp;i++)
26.        {
27.               pl[i].pn=i;
28.               pl[i].pfn=INVALID;       
29.               pl[i].time=-1;        
30.        }
31.        for(i=0;i<total_pf-1;i++)
32.        {
33.               pfc[i].next=&pfc[i+1];
34.               pfc[i].pfn=i;
35.        }   /*建立pfc[i-1]和pfc[i]之间的链接*/
36.        pfc[total_pf-1].next=NULL;
37.        pfc[total_pf-1].pfn=total_pf-1;
38.        freepf_head=&pfc[0];         /*空页面队列的头指针为pfc[0]*/
39. }
40. void OPT(int total_pf)       /*最佳置换算法*/
41. {
42.        int i,j, max,maxpage,d,dist[total_vp];
43.        initialize(total_pf);
44.        for(i=0;i<total_instruction;i++)
45.        {
46.               if(pl[page[i]].pfn==INVALID)      /*页面失效*/
47.               {
48.                     diseffect++;
49.                     if(freepf_head==NULL)         /*无空闲页面*/
50.                      {
51.                             for(j=0;j<total_vp;j++)
52.                                    if(pl[j].pfn!=INVALID)
53.                             dist[j]=32767;  /* 最大"距离" */
54.                             else dist[j]=0;
55.                             d=1;
56.                             for(j=i+1;j<total_instruction;j++)
57.                             {
58.                                    if(pl[page[j]].pfn!=INVALID)
59.                                           if(dist[page[j]]==32767)
60.                                                  dist[page[j]]=d;
61.                                               d++;
62.                             }
63.                             max=-1;
64.                             for(j=0;j<total_vp;j++)
65.                             if(max<dist[j]){
66.                                    max=dist[j];
67.                                    maxpage=j;
68.                             }
69.                             freepf_head=&pfc[pl[maxpage].pfn];
70.                             freepf_head->next=NULL;
71.                             pl[maxpage].pfn=INVALID;
72.                      }
73.                      pl[page[i]].pfn=freepf_head->pfn;
74.                      freepf_head=freepf_head->next;
75.               }
76.        }
77.        printf("OPT:%6.4f ",1-(float)diseffect/total_instruction);
78. }
79. void FIFO(int total_pf)              /*先进先出算法*/
80. {
81. int i,j;
82. pfc_type *p;
83. initialize(total_pf);       
84. busypf_head=busypf_tail=NULL; /*忙页面队列头，队列尾链接*/
85. for(i=0;i<total_instruction;i++){
86. if(pl[page[i]].pfn==INVALID)   /*页面失效*/
87. {
88. diseffect+=1;                  /*失效次数*/
89. if(freepf_head==NULL)         /*无空闲页面*/
90. {
91. p=busypf_head->next;
92. pl[busypf_head->pn].pfn=INVALID;
93. freepf_head=busypf_head;  /*释放忙页面队列的第一个页面*/
94. freepf_head->next=NULL;
95. busypf_head=p;
96. }
97. p=freepf_head->next;         /*按FIFO方式调新页面入内存页面*/
98. freepf_head->next=NULL;
99. freepf_head->pn=page[i];
100. pl[page[i]].pfn=freepf_head->pfn;
101. if(busypf_tail==NULL)
102. busypf_head=busypf_tail=freepf_head;
103. else{
104. busypf_tail->next=freepf_head;  /*free页面减少一个*/
105. busypf_tail=freepf_head;
106. }
107. freepf_head=p;
108. }
109. }
110. printf("FIFO:%6.4f ",1-(float)diseffect/total_instruction);
111. }
112. void LRU (int total_pf)       /*最近最久未使用算法*/
113. {
114.        int min,minj,i,j,present_time;
115.        initialize(total_pf);
116.        present_time=0;
117.        for(i=0;i<total_instruction;i++){
118.            if(pl[page[i]].pfn==INVALID)             /*页面失效*/
119.            {
120.                diseffect++;
121.              if(freepf_head==NULL)              /*无空闲页面*/
122.              {
123.                min=32767;
124.                for(j=0;j<total_vp;j++)            /*找出time的最小值*/
125.                  if(min>pl[j].time&&pl[j].pfn!=INVALID){
126.                               min=pl[j].time;
127.                               minj=j;
128.                           }
129.                 freepf_head=&pfc[pl[minj].pfn];   //腾出一个单元
130.                 pl[minj].pfn=INVALID;
131.                 pl[minj].time=-1;
132.                 freepf_head->next=NULL;
133.              }
134.              pl[page[i]].pfn=freepf_head->pfn;   //有空闲页面,改为有效
135.              pl[page[i]].time=present_time;
136.                      freepf_head=freepf_head->next;      //减少一个free 页面
137.             }
138.            else
139.                   pl[page[i]].time=present_time;        //命中则增加该单元的访问次数
140.                   present_time++;
141.        }
142.        printf("LRU:%6.4f ",1-(float)diseffect/total_instruction);
143. }
144. int main( )
145. {
146.        int i;
147. a[0]=41;a[1]=31;a[2]=21;a[3]=11;a[4]=41;a[5]=31;a[6]=52;a[7]=42;a[8]=32;a[9]=22;a[10]=11;a[11]=51;/* 假如一个作业的页面走向为4，3，2，1，4，3，5，4，3，2，1，5*/
148.        for (i=0;i<total_instruction;i++) /*将指令序列变换成页地址流*/
149.        {
150.             page[i]=a[i]/10;
151.             offset[i]=a[i]%10;
152.        }
153.        for(i=3;i<=5;i++)   /*用户内存工作区从3个页帧到4个页帧*/
154.        {
155.               printf("%2d page frames ",i);
156.               OPT(i);
157.               FIFO(i);
158.               LRU(i);
159.               printf("\n");
160.         }
161. }

四、运行结果截图

五、调试和运行程序过程中产生的问题及采取的措施

问题：文件名创建不正确，命令使用错误。

措施：请教老师，在同学的讨论下完成。

计算机操作系统实验四存储管理

龙蜥操作系统

热门文章

最新文章

相关课程

相关电子书

相关实验场景

推荐镜像

计算机操作系统实验四 存储管理

龙蜥操作系统

热门文章

最新文章

相关课程

相关电子书

相关实验场景

推荐镜像

计算机操作系统实验四存储管理