欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

最近最久未使用(LRU)算法

程序员文章站 2024-03-18 13:18:04
...

算法原理

#include <iostream>
#include <cstdio>//LRU
#include <windows.h>
using namespace std;

struct page{
  int time;//多久未使用 
  int value;//页面号 
};

int find_(int x);//判断物理块中是否有该页面有就返回该索引 
int findMaxTime_();//找到放在物理块中最久未使用页面 
void print_();//打印当前物理块中的页面 

const int memoryLength = 4;//物理块个数 
int memoryPosition = 0;// 
int findPosition; //标记找到的页面的位置 

struct page memory[memoryLength];

int page[25] = {0, 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3,
                  2, 1, 2, 0, 1, 7, 0, 1};//第一个不算(页面号) 

int main() {
  //初始化开始时间为0 
  for (int i = 0; i < memoryLength; i++) {
    memory[i].time = 0;
  }
  //LRU算法进行页面置换过程 
  for (int i = 1; i <= 20; i++) {
    Sleep(500); 
    printf("当前进入物理块的页面号:%d\n", page[i]); 
    if (memoryPosition < memoryLength) {
      findPosition = find_(page[i]);

      for (int j = 0; j < memoryPosition; j++) memory[j].time++;

      if (findPosition != -1)  memory[findPosition].time = 0;
      else {
        memory[memoryPosition].value = page[i];
        memory[memoryPosition].time = 0;
        memoryPosition++;
      }

      print_();
      //memoryPosition等于memoryLength时表示物理块已填满 
    }else {
      for (int j = 0; j < memoryLength; j++) memory[j].time++;

      findPosition = find_(page[i]);//断物理块中是否有该页面有就返回该索引
      if (findPosition == -1) {
        findPosition = findMaxTime_();//找到最久未使用页面的物理块位置 
        memory[findPosition].value = page[i];
        memory[findPosition].time = 0;
      }else {
        memory[findPosition].time = 0;
      }

      print_();
    }
  }
  return 0;
}

int find_(int x) {//查找物理块中是否有该页面 
  for (int i = 0; i < memoryPosition; i++) {
    if (x == memory[i].value) return i;
  }
  return -1;
}


void print_() {
  for (int i = 0; i < memoryPosition; i++) {
    printf("页面号:%d 未使用时间%d\n", memory[i].value, memory[i].time);
    //printf("%d ", memory[i].value);
  }
  printf("\n");
}

int findMaxTime_() {
  int max_ = -1;
  int maxPosition;
  for (int i = 0; i < memoryPosition; i++) {
    if (memory[i].time > max_) {
      max_ = memory[i].time;
      maxPosition = i;
    }
  }
  return maxPosition;
}
相关标签: LRU