LRU页面置换算法_lru进行页面置换的方法

LRU页面置换算法

---

前言

LRU页面置换算法是虚拟存储器中使用的算法，通过选取最近最少使用的页面换出

---

一、LRU算法介绍

LRU（最近最少使用）页面置换算法是根据过去使用次数来预测将来的页面使用情况，具体过程如下：
当发生缺页而分配给进程的物理块耗尽时，需要将所需页面置换入内存，被换出的页面是最近最少被使用的页面。具体的实现方法为为每个内存中的页面配置一个移位寄存器，每过一段时间（如10ms）将其中的数字右移。当该页面被访问时，将最高位置一，这样，最近被访问的页面寄存器中的数字是最大的，需要换出页面时，只需选取数值最小的页面换出；另一种方法是为每个进程配置一个栈，页面进入内存时将其压入栈中，当访问内存中的页面时，将其重新压入栈顶，如此最近被访问的页面就在栈顶，需要置换页面时，只需将栈底的页面置换出即可。下面代码使用的是第一种方法。

二、代码

1.源程序

#include <iostream>
#include <vector>
using namespace std;

typedef struct
{
    unsigned visit;
    ///int block = ;
    int state;
    int pageId;
}PageItem,*itemp;

itemp initItem(int pageId)
{
    itemp aItemp = new PageItem;
    aItemp->visit = 0b0;
    aItemp->state = 0;
    aItemp->pageId = pageId;
    return aItemp;
}

void moveright(itemp items[],int num)
{
    for(int i=0;i<num;i++)
        items[i]->visit = (items[i]->visit)>>1;
}
void LRU(itemp items[],int num,int pageId,vector<int>& blocks)
{
    int id = 0;
    unsigned visit = 0xFFFFFFFF;
    for(int i=0;i<num;i++)
    {
        if(visit>items[i]->visit && items[i]->state==1)
        {
            visit = items[i]->visit;
            id = items[i]->pageId;
        }
    }
    for(int i=0;i<num;i++)
    {
        if(items[i]->pageId==id)
        {
            items[i]->visit = 0b0;
            items[i]->state = 0;
        }
        if(items[i]->pageId==pageId)
            items[i]->state = 1;
    }
    for(vector<int>::iterator i=blocks.begin();i!=blocks.end();i++)
    {
        if(*i==id)
        {
            *i = pageId;
            break;
        }
    }
}

int main()
{
    int invoke = 0;
    int blocknum = 0;
    int next = 0;
    int blockTaken = 0;
    vector<int> blocks(0);
    itemp items[8] = {};
    for(int i=0;i<8;i++)
        items[i] = initItem(i);
    ///PageTable table(5,items);
    cout << "为此进程分配的物理块个数：";
    cin >> blocknum;
    cout << "调用页面的次数：";
    cin >> invoke;
    for(int i=0;i<invoke;i++)
    {
        cout << "下次要调用的页面是：";
        cin >> next;
        bool in = false;
        for(vector<int>::iterator i=blocks.begin();i!=blocks.end();i++)
        {
            if(next == *i)
            {
                in = true;
                break;
            }
        }
        if(in)
        {
            cout << "页面在内存中\n";
        }
        else if(blockTaken<blocknum)
        {
        	//页面不在内存中并且物理块还未耗尽
            blocks.push_back(next);
            cout << "页面载入内存，当前物理块：";
            for(vector<int>::iterator i=blocks.begin();i!=blocks.end();i++)
                cout << *i << '\t';
            cout << endl;
            items[next]->state = 1;
            blockTaken++;
        }
        else if(blockTaken>=blocknum)
        {
            cout << "物理块满，调用LRU页面置换算法\n";
            cout << "当前物理块分配为：";
            for(vector<int>::iterator i=blocks.begin();i!=blocks.end();i++)
                cout << *i << '\t';
            LRU(items,5,next,blocks); //物理块耗尽，使用LRU算法置换页面
            cout << endl << "置换后物理块分为：";
            for(vector<int>::iterator i=blocks.begin();i!=blocks.end();i++)
                cout << *i << '\t';
            cout << endl;
        }

        items[next]->visit+=0b10000000000000000000000000000000;
        moveright(items,8);
    }
    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

2.运行结果

以上是我对LRU算法的理解，如有谬误，欢迎斧正。
	
1
2