操作系统：页面置换算法（FIFO算法、LRU算法、LFU算法、NRU算法）实验报告_lru算法实验总结

操作系统实验报告

一、实验名称 ：页面置换算法

二、实验目的：

在实验过程中应用操作系统的理论知识。

三、实验内容：

采用C/C++编程模拟实现：FIFO算法、LRU算法、LFU算法、NRU算法四个页面置换算法。并设置自动数据生成程序，比较四个算法的缺页出现概率。

四、程序代码：

/*
FIFO: 简单的先进先出，用队列模拟即可 prio 表示入队时间（小值先出）
LRU: 淘汰最久没有被访问的页面 prio 表示上一次入队的时间（小值先出）
LFU: 淘汰最少访问次数的页面 prio 表示被访问的次数
NRU: 四类 prio表示状态类数
    第0类：没有被访问，没有被修改。00
    第1类：没有被访问，已被修改。  01
    第2类：已被访问，没有被修改。  10
    第3类：已被访问，已被修改     11
*/

#include<bits/stdc++.h>
#define xcx(x) printf("ojbk %d\n",x)
using namespace std ;
const int PAGE_NUM = 20 ;
const int MEM_SIZE = 3 ;
const double NRU_LIMIT = 3 ;
bool in_mem[ PAGE_NUM+1 ] ;
struct page{
    int val, prio, pos ; // val:页数 pos:占内存位置
    page () {}
    page ( int val , int prio , int pos ) {
        this->val = val ;
        this->prio = prio ;
        this->pos = pos ;
    }
};

bool operator < ( const page &l , const page &r ) {
    if (  l.prio== r.prio ) {
        return l.pos < r.pos ;
    }
    return l.prio > r.prio ;
}
vector< int > CreatSeq ( int n ) { // 随机生成长度为 n 的访问序列
    vector< int > ret ;
    for( int i=0; i<n; i++ ) {
        ret.push_back( rand()%PAGE_NUM+1 ) ;
    }
    return ret ;
}
void Init ( vector< vector<int> > &ret , vector< bool > &is_miss , const vector< int > &seq ) {
    vector< int > e( MEM_SIZE ) ;
    memset( in_mem, false, sizeof(in_mem) ) ;
    is_miss.clear() ;   ret.clear() ;
    for( int i=0; i<seq.size(); i++ ) {
        is_miss.push_back( 0 ) ;
        ret.push_back( e ) ;
    }
}
vector< vector<int> > FIFO ( const vector< int > &seq , vector< bool > &is_miss ) {
    vector< vector<int> > ret ;
    Init( ret , is_miss , seq ) ;
    queue< page > q ;
    bool is_full = false ;
    int num = 0, mem_pos[ MEM_SIZE ] = {0} ;
    for( int i=0; i<seq.size(); i++ ) {
        if ( in_mem[seq[i]] == false ) { // 不在mem
            is_miss[i] = true ;
            if ( is_full == true ) { // mem已满，淘汰
                page temp = q.front() ;
                q.pop() ;   in_mem[ temp.val ] = false ;
                q.push( page( seq[i], i+1, temp.pos ) );    in_mem[ seq[i] ] = true ;
                mem_pos[temp.pos] = seq[i] ;
            }
            else { // mem未满，添加
                q.push( page( seq[i], i+1, num ) );
                in_mem[ seq[i] ] = true ;
                mem_pos[ num++ ] = seq[i] ;
                if ( num >= MEM_SIZE ) is_full = true ;
            }
        }
        ///存储当前状态
        for( int j=0; j<MEM_SIZE; j++ ) {
            ret[i][j] = mem_pos[j] ;
        }
    }
    return ret;
}
vector< vector<int> > LRU ( const vector< int > &seq , vector< bool > &is_miss ) {
    vector< vector<int> > ret ;
    Init( ret , is_miss , seq ) ;
    vector< page > q ;
    bool is_full = false ;
    int num = 0, mem_pos[ MEM_SIZE ] = {0} ;
    for( int i=0; i<seq.size(); i++ ) {
        if ( in_mem[seq[i]] == false ) { // 不在 mem
            is_miss[i] = true ;
            if ( is_full == true ) { // mem已满，淘汰
                page temp = q[0] ;
                q[0] = page( seq[i], i+1, temp.pos ) ;
                in_mem[ temp.val ] = false ;    in_mem[ seq[i] ] = true ;
                mem_pos[temp.pos] = seq[i] ;
            }
            else { // mem未满，添加
                q.push_back( page( seq[i], i+1, num ) );
                in_mem[ seq[i] ] = true ;
                mem_pos[ num++ ] = seq[i] ;
                if ( num >= MEM_SIZE ) is_full = true ;
            }
        }
        else { // 在 mem
            for( int i=0; i<q.size(); i++ ) {
                if ( q[i].val == seq[i] ) {
                    q[i].prio = i ;
                }
            }
        }
        sort( q.begin() , q.end() ) ;
        ///存储当前状态
        for( int j=0; j<MEM_SIZE; j++ ) {
            ret[i][j] = mem_pos[j] ;
        }
    }
    return ret;
}
vector< vector<int> > LFU ( const vector< int > &seq , vector< bool > &is_miss ) {
    vector< vector<int> > ret ;
    Init( ret , is_miss , seq ) ;
    vector< page > q ;
    bool is_full = false ;
    int num = 0, mem_pos[ MEM_SIZE ] = {0} ;
    for( int i=0; i<seq.size(); i++ ) {
        if ( in_mem[seq[i]] == false ) { // 不在 mem
            is_miss[i] = true ;
            if ( is_full == true ) { // mem已满，淘汰
                page temp = q[0] ;
                q[0] = page( seq[i], 1, temp.pos ) ;
                in_mem[ temp.val ] = false ;    in_mem[ seq[i] ] = true ;
                mem_pos[temp.pos] = seq[i] ;
            }
            else { // mem未满，添加
                q.push_back( page( seq[i], 1, num ) );
                in_mem[ seq[i] ] = true ;
                mem_pos[ num++ ] = seq[i] ;
                if ( num >= MEM_SIZE ) is_full = true ;
            }
        }
        else { // 在 mem
            for( int i=0; i<q.size(); i++ ) {
                if ( q[i].val == seq[i] ) {
                    q[i].prio++ ;
                    break ;
                }
            }
        }
        sort( q.begin() , q.end() ) ;
        ///存储当前状态
        for( int j=0; j<MEM_SIZE; j++ ) {
            ret[i][j] = mem_pos[j] ;
        }
    }
    return ret;
}
vector< vector<int> > NRU ( const vector< int > &seq , vector< bool > &is_miss ) {
    double T_start, T_end ;
    T_start = clock() ;
    vector< vector<int> > ret ;
    Init( ret , is_miss , seq ) ;
    vector< page > q ;
    bool is_full = false ;
    int num = 0, mem_pos[ MEM_SIZE ] = {0} , prio[ PAGE_NUM ] = {0} ;
    for( int i=0; i<seq.size(); i++ ) {
        if ( in_mem[seq[i]] == false ) { // 不在 mem
            is_miss[i] = true ;
            if ( is_full == true ) { // mem已满，淘汰
                page temp = q[0] ; in_mem[ temp.val ] = false ;
                q[0] =  page( seq[i], 0, temp.pos ) ;    in_mem[ seq[i] ] = true ;
                prio[ seq[i] ] |= 1 ; // 视为修改
                mem_pos[temp.pos] = seq[i] ;
            }
            else { // mem未满，添加
                q.push_back( page( seq[i], 0, num ) );
                prio[ seq[i] ] |= 2 ; // 视为访问
                in_mem[ seq[i] ] = true ;
                mem_pos[ num ] = seq[i] ;
                num++;
                if ( num >= MEM_SIZE ) is_full = true ;
            }
        }
        else { // 在 mem
            prio[ seq[i] ] |= 2 ; // 视为访问
        }
        if ( clock() - T_start > NRU_LIMIT ) { // 更新
            T_start = clock() ;
            for( int i=0; i<PAGE_NUM; i++ ) {
                prio[i] &= 1 ;
            }
        }
        for( int i=0; i<q.size(); i++ ) {
            q[i].prio = prio[ q[i].val ] ;
        }
        sort( q.begin() , q.end() ) ;
        ///存储当前状态
        for( int j=0; j<MEM_SIZE; j++ ) {
            ret[i][j] = mem_pos[j] ;
        }
    }
    return ret;
}
void PrintTable ( const vector< vector<int> > &ans , const vector< bool > &is_miss , string type ) {
    int num = 0 ;
    printf( "%s\n", type.c_str() ) ;
    for( int i=0; i<MEM_SIZE ; i++ ) {
        printf( "\tmem unit %d :\t", i ) ;
        for( int j=0; j<ans.size(); j++ ) {
            if ( ans[j][i] != 0 ) {
                printf( "%3d", ans[j][i] ) ;
            }
            else {
                printf( "   " ) ;
            }
        }
        printf( "\n" ) ;
    }
    printf( "\tis miss :\t") ;
    for( int i=0; i<is_miss.size(); i++ ) {
        if ( is_miss[i] == true ) {
            num++ ;
            printf( "  Y" ) ;
        }
        else {
            printf( "  N" ) ;
        }
    }
    printf( "\n miss num : %d \n", num ) ;
}
const string type[4] = { "FIFO", "LRU", "LFU", "NRU" };

int main() {
    vector< int > seq = CreatSeq( 19 ) ;
    printf( "page seq:\t" ) ;
    for( int i=0; i<seq.size(); i++ ) {
        printf( "%3d", seq[i] ) ;
    }
    printf( "\n" ) ;
    vector< bool > is_miss ;
///FIFO:
    vector< vector < int > > ans_FIFO = FIFO( seq , is_miss ) ;
    PrintTable( ans_FIFO , is_miss , type[0] ) ;
///LRU:
    vector< vector < int > > ans_LRU = LRU( seq , is_miss ) ;
    PrintTable( ans_LRU , is_miss , type[1] ) ;
///LFU:
    vector< vector < int > > ans_LFU = LFU( seq , is_miss ) ;
    PrintTable( ans_LFU , is_miss , type[2] ) ;
///NRU:
    vector< vector < int > > ans_NRU = NRU( seq , is_miss ) ;
    PrintTable( ans_NRU , is_miss , type[3] ) ;

    return 0;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253

五、运行结果：

六、实验总结：

通过编程模拟四个页面淘汰算法的操作，实际了解了四个算法的淘汰方法以及核心思路，更了解了他们之间的关系和不同点。通过输入不同的数据比较四种方法的效率，确定的他们适用的情况。