操作系统实验:存储管理

一、实验目的

1、了解虚拟存储技术的特点，掌握请求页式存储管理的主要页面置换算法原理。

2、掌握请求页式存储管理中页面置换算法的模拟设计方法。

3、通过随机产生页面访问序列开展有关算法的测试及性能比较。

二、实验内容

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

①先进先出的算法（FIFO）；

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

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

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

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

（其中③④为选择内容）

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

三、设计原理（或方案）及相关算法

  1.fifo算法流程图

     

 2.Lru算法流程图

  

 3.opt算法流程图

运行结果及分析：

 

分析：通过多次运行结果发现，OPT算法淘汰页面最少，命中率始终最高，FIFO算法和LRU算法命中率差不多，但是淘汰页面大有不同。

源程序：

1.  
   #include <stdio.h>
2.  
   #include <stdlib.h>
3.  
   #include <time.h>
4.  
   #define N 320//随机数列的长度
5.  
   #define B 4//内存的页面数
6.  
   int IsInBuf(int buf[],int x)//返回某个数X有没有在缓冲区buf[]中
7.  
   {
8.  
   int i,j=-1;
9.  
   for(i=0;i<B;i )
10.  
    {
11.  
    if(buf[i]==x)
12.  
    {
13.  
    j=i;
14.  
    break;
15.  
    }else if(buf[i]==-1)
16.  
    {
17.  
    buf[i]=x;
18.  
    j=i;
19.  
    break;
20.  
    }
21.  
     
22.  
    }
23.  
    return j;
24.  
    }
25.  
    int oldest(int list[],int buf[],int f[],int start)//返回最近最久未使用的页面的位置
26.  
    {
27.  
    int i,j;
28.  
    for(i=0;i<B;i )
29.  
    {
30.  
    for(j=start;j<N;j )
31.  
    {
32.  
    if(buf[i]==list[j])break;
33.  
    }
34.  
    f[i]=j;
35.  
    }
36.  
    return oldest2(f);
37.  
    }
38.  
    int oldest2(int f[])//返回最长时间不使用的页面的位置
39.  
    {
40.  
    int i,j=0,max=-1;
41.  
    for(i=0;i<B;i )
42.  
    {
43.  
    if(f[i]>max){max=f[i];j=i;}
44.  
    f[i] ;
45.  
    }
46.  
    return j;
47.  
    }
48.  
    void main()
49.  
    {
50.  
    int list[N];
51.  
    int buf[B],f[B],i,j,k,max,min;
52.  
    int old=0;
53.  
    int change=0;
54.  
    printf("本程序假设内存为程序分配的内存块数是4!\n");
55.  
    srand((int)time(NULL));//生成一系列随机数并初始化环境
56.  
    for(i=0;i<B;i )buf[i]=f[i]=-1;
57.  
    printf("产生的随机数列为:\n");
58.  
    for(i=0;i<N;i )
59.  
    {
60.  
    list[i]=(int)rand()%10;//产生随机数列
61.  
    printf("-",list[i]);
62.  
    }
63.  
    printf("\n");
64.  
    printf("\nOPT淘汰页面的序列为:\n");
65.  
    change=0;
66.  
    for(i=0;i<B;i )buf[i]=f[i]=-1;
67.  
    for(i=0;i<N;i )
68.  
    {
69.  
    j=IsInBuf(buf,list[i]);
70.  
    if(j==-1)
71.  
    {
72.  
    old=oldest(list,buf,f,i);
73.  
    printf("-",buf[old]);
74.  
    buf[old]=list[i];
75.  
    f[old]=0;
76.  
    change ;
77.  
    }
78.  
    else
79.  
    {
80.  
    printf("");
81.  
    }
82.  
    }
83.  
    printf("\nOPT算法的命中率为:%f\n",1-(float)change/320);
84.  
    printf("\nFIFO淘汰页面的序列为:\n");
85.  
    change=0;
86.  
    for(i=0;i<B;i )buf[i]=-1;
87.  
    for(i=0;i<N;i )
88.  
    {
89.  
    j=IsInBuf(buf,list[i]);
90.  
    if(j==-1)
91.  
    {
92.  
    if(buf[old]==-1)printf("");
93.  
    else printf("-",buf[old]);
94.  
    buf[old]=list[i];
95.  
    old=(old 1)%(int)B;
96.  
    change ;
97.  
    }
98.  
    else
99.  
    printf("");
100.  
     }
101.  
     printf("\nFIFO算法的命中率为:%f\n",1-(float)change/320);
102.  
     printf("\nLRU淘汰页面的序列为:\n");
103.  
     change=0;
104.  
     for(i=0;i<B;i )buf[i]=f[i]=-1;
105.  
     for(i=0;i<N;i )
106.  
     {
107.  
     j=IsInBuf(buf,list[i]);
108.  
     old=oldest2(f);
109.  
     if(j==-1)
110.  
     {
111.  
     printf("-",buf[old]);
112.  
     buf[old]=list[i];
113.  
     f[old]=0;
114.  
     change ;
115.  
     }
116.  
     else
117.  
     {
118.  
     f[j]=0;
119.  
     printf("");
120.  
     }
121.  
      
122.  
     }
123.  
     printf("\nLRU算法的命中率为:%f\n",1-(float)change/320);
124.  
     }
125.  
      
126.  
      
127.  
      

这篇好文章是转载于：学新通技术网