FIFO 和 LRU 页面置换算法
FIFO页面置换算法
问题：随机一访问串和驻留集的大小，通过模拟程序显示淘汰的页号并统计命中率。示例：
输入访问串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1
驻留集大小：3
算法的实现：FIFO淘汰算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面进行淘汰。该算法实现只需把一个进程已调入内存的页面，按访问的时间先后顺序链接成一个队列，并设置一个指针，该指针始终指向“最老“的页面。
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1
7 7 7 2 2 2 2 4 4 4 0 0 0 0 0 0 0
0 0 0 0 3 3 3 2 2 2 2 2 1 1 1 1
1 1 1 1 0 0 0 3 3 3 3 3 2 2 2
7 0 1 2 3 0 4 2 3
红色表示：指针指向调入内存的页面中“最老“的页面
通过模拟程序输出淘汰的页号分别为：7 0 1 2 3 0 4 2 3
命中率为：5/13
注意：内存的页面中“最老“的页面，会被新的网页直接覆盖，而不是“最老“的页面先出队，然后新的网页从队尾入队。
代码：
#include <stdio.h>#include <string.h>#include <malloc.h>int len;typedef struct Queue{ int * pBase; int front;//队列头 int rear;//队列尾}QUEUE;void init(QUEUE *pQ){ int N = len+1; pQ->pBase = (int *)malloc(sizeof(int ) * N);//N为数组长度 //初始化为0 pQ->front = 0; pQ->rear = 0;}int full_queue(QUEUE *pQ){ int N = len+1; if((pQ->rear +1)%N == pQ->front)//循环队列 return 1; else return 0;}int en_queue(QUEUE *pQ, int val)//入队前判断队列是否已满{ int N = len+1; if( full_queue(pQ) ) { return 0; } else { pQ->pBase[pQ->rear] = val;//压栈在队尾 pQ->rear = (pQ->rear+1) % N; return 1; }}int empty_queue(QUEUE *pQ){ int N = len+1; if(pQ->front == pQ->rear) return 1; else return 0;}int out_queue(QUEUE *pQ, int *pVal)//出队前判断队列是否为空{ int N = len+1; if(empty_queue(pQ)) { return 0; } else { *pVal = pQ->pBase[pQ->front];//把出队的元素保存起来 pQ->front = (pQ->front+1)%N; return 1; }}int same_queue(QUEUE *pQ, int x){ int N = len+1; int i = pQ->front; while( i != pQ->rear) { if( pQ->pBase[i] == x) return 1; i = (i+1) % N; } return 0;}int main(){ int cnt = 0;//记没命中次数 int i, val, data; char str[1000]; scanf("%d", &len);//驻留集大小 scanf("%s", str); QUEUE Q; init (&Q); for(i=0; str[i] != '\0'; i++) { if(str[i] >= '0' && str[i] <= '9') { val= str[i] - '0'; if( !full_queue(&Q) && !(same_queue(&Q, val))) { en_queue(&Q, val); cnt++; } else if( full_queue(&Q) && !(same_queue(&Q, val)) ) { out_queue(&Q, &data); printf("%d ",data); en_queue(&Q, val); cnt++; } } } printf("\n%d/%d", strlen(str)- cnt, strlen(str)); return 0;}
LRU页面置换算法
问题：随机一访问串和驻留集的大小，通过模拟程序显示淘汰的页号并统计命中率。示例：
输入访问串：7 0 1 2 0 3 0 4 2 3 0 3 2
驻留集大小：3
算法的实现：由于LRU算法淘汰的是上次使用距离t时刻最远的页，故需记录这个距离。
计数器：可使用计数器，给每一个页帧增设一个计数器。每访问一页，就把对应页帧的计数器清零，其余页帧的计数器加1.因此，计数器值为最大的页即上次访问距当前最远的页。
7 0 1 2 0 3 0 4 2 3 0 3 2
0/7 1/7 2/7 0/2 1/2 2/2 3/2 0/4 1/4 2/4 0/0 1/0 2/0
0/0 1/0 2/0 0/0 1/0 0/0 1/0 2/0 0/3 1/3 0/3 1/3
0/1 1/1 2/1 0/3 1/3 2/3 0/2 1/2 2/2 3/2 0/2
缺 缺 缺 缺 命 缺 命 缺 缺 缺 缺 命 命
红色表示：每个页帧对应的计数器值
通过模拟程序输出淘汰的页号分别为：7 1 2 3 0 4
命中率为：4/13
代码：
#include <stdio.h>#include <string.h>#include <malloc.h>int len;typedef struct LRU{ int data; int time;//计次数} LRU;typedef struct Queue{ LRU *pBase;//结构数组 int front;//队列头 int rear;//队列尾}QUEUE;void init(QUEUE *pQ){ int N = len+1; pQ->pBase = (LRU*)malloc(sizeof(LRU ) * N); pQ->front = pQ->rear = 0; //初始化为0}int full_queue(QUEUE *pQ){ int N = len+1; if((pQ->rear +1)%N == pQ->front)//循环队列 return 1; else return 0;}int en_queue(QUEUE *pQ, int val)//入队前判断队列是否已满{ int N = len+1; if( full_queue(pQ) ) { return 0; } else { pQ->pBase[pQ->rear].data = val;//压栈在队尾 pQ->pBase[pQ->rear].time = 0;//初始化次数为0 pQ->rear = (pQ->rear+1) % N; return 1; }}int empty_queue(QUEUE *pQ)//1-->空 0-->非空{ int N = len+1; if(pQ->front == pQ->rear) return 1; else return 0;}int out_queue(QUEUE *pQ, int *pVal)//出队前判断队列是否为空{ int N = len+1; if(empty_queue(pQ)) { return 0; } else { *pVal = pQ->pBase[pQ->front].data;//把出队的元素保存起来 pQ->front = (pQ->front+1)%N; return 1; }}void add_time(QUEUE *pQ){ int N = len+1; int i = pQ->front; while( i != pQ->rear) { pQ->pBase[i].time ++; i = (i + 1) % N; //printf("%d %d", pQ->pBase[i].time, i); }}void Set_time_shot(QUEUE *pQ, int x)//若待入队元素与队中元素相同，将次数置为0{ int N = len + 1; int i = pQ->front; while( i != pQ->rear) { if( pQ->pBase[i].data == x) { pQ->pBase[i].time = 0; } i = (i+1) % N; }}int Find_big_time(QUEUE *pQ){ int N = len + 1; int i = pQ->front; int max_i = i; int max_time = pQ->pBase[pQ->front].time; while( i != pQ->rear) { if( pQ->pBase[i].time > max_time) { max_i = i; max_time = pQ->pBase[i].time; } i = (i+1) % N; } return max_i;}void Replace_big_time(QUEUE *pQ, int x)//若待入队元素与队中元素不相同，替换元素，并将次数置为0{ int max_time = Find_big_time(pQ); printf("%d ", pQ->pBase[max_time].data); pQ->pBase[max_time].data = x; pQ->pBase[max_time].time = 0;}int same_queue(QUEUE *pQ, int x)//判断待入队元素是否与队中元素相同{ int N = len+1; int i = pQ->front; while( i != pQ->rear) { if( pQ->pBase[i].data == x) return 1; i = (i+1) % N; } return 0;}int main(void){ char str[100]; int val, data; int i, cnt = 0; scanf("%d", &len); scanf("%s", str); QUEUE Q; init(&Q); for(i=0; str[i] != '\0'; i++) { val = str[i] - '0'; if ( empty_queue( &Q ) )//如果队列为空 { en_queue(&Q, val); } else { add_time(&Q); if(full_queue(&Q))//如果队列已满 { if( !same_queue(&Q, val)) { Replace_big_time(&Q, val); } else { Set_time_shot(&Q, val); cnt++; } } else//如果队列没满也不为空 { if( !same_queue(&Q, val)) { en_queue(&Q, val); } else { Set_time_shot(&Q, val); cnt++; } } } } printf("\n%d/%d", cnt, strlen(str)); return 0;}
总结：
虽然两个算法都是用队列这种数据结构实现的，但具体操作不完全遵从队列的原则。这一点不必纠结。
命中率是指在队满的情况下，新的元素的加入，不影响队列其它元素。即该元素已存在在队列中。