实验 4 FIFO 算法和 LRU 算法-C 程序实现

Question

FIFO：定义4个物理块，输入8个物理块号，将其一一放入，若4个块满了，则将第一个块覆盖掉，若输入的物理块号存在，则表示命中，覆盖原来的。
LRU：定义 4 个物理块，输入 8 个物理块号，并引入 time 来标记他们的存在时间，初始值为 0，每引入一个数则 time+1，若有相同的值，则该块的time清0，等4个物理块满了以后，之后输入的值将time 最大的那个块的值覆盖。
将两个算法放在一个C语言中。

Answer 1

#include <stdio.h>
 
#define SIZE 4
 
void FIFO(int arr[], int n) {
    int memory[SIZE] = {0};  // 物理块数组初始化为0
    int hit_count = 0;  // 命中的次数
 
    printf("======算法FIFO======\n");
    for (int i = 0; i < n; i++) {
        int found = 0;  // 是否找到相同的物理块号
 
        // 检查输入的物理块号是否已经在物理块数组中
        for (int j = 0; j < SIZE; j++) {
            if (memory[j] == arr[i]) {
                found = 1;
                hit_count++;
                break;
            }
        }
 
        if (!found) {
            // 物理块数组已经满了，需要覆盖最早放入的块
            if (memory[SIZE-1] != 0) {
                for (int j = 0; j < SIZE-1; j++) {
                    memory[j] = memory[j+1];
                }
            }
 
            // 将新的物理块号放入物理块数组的最后一块
            memory[SIZE-1] = arr[i];
        }
 
        // 打印物理块数组
        printf("第%d次访问。。。。", i+1);
        for (int j = SIZE-1; j >= 0; j--) {
            printf("%d ", memory[j]);
        }
        printf("\n");
    }
 
    printf("\n命中次数： %d\n", hit_count);
}
 
void LRU(int arr[], int n) {
  int frames[SIZE] = {0};
  int time[SIZE] = {0};
  
  printf("======算法LRU======\n");
  
  for (int i = 0; i < n; i++) {
    int found = 0;
    int minTime = time[0];
    int minIndex = 0;
    
    for (int j = 0; j < SIZE; j++) {
      if (frames[j] == arr[i]) {
        found = 1;
        time[j] = 0;
      } else {
        time[j]++;
      }
      
      if (time[j] > minTime) {
        minTime = time[j];
        minIndex = j;
      }
    }
    
    if (found) {  // 命中
      printf("第%d次访问。。。。", i+1);
      for (int j = 0; j < SIZE; j++) {
        printf("%d ", frames[j]);
      }
      printf("时间 ");
      for (int j = 0; j < SIZE; j++) {
        printf("%d ", time[j]);
      }
      printf("\n");
    } else {  // 未命中
      frames[minIndex] = arr[i];
      time[minIndex] = 0;
      printf("第%d次访问。。。。", i+1);
      for (int j = 0; j < SIZE; j++) {
        printf("%d ", frames[j]);
      }
      printf("时间 ");
      for (int j = 0; j < SIZE; j++) {
        printf("%d ", time[j]);
      }
      printf("\n");
    }
  }
}
 
int main() {
  int size;
  printf("请输入要存入的数据的长度：");
  scanf("%d", &size);
  
  int input[size];
  printf("请输入要存入的数据，用空格分隔：");
  for(int i=0; i<size; i++){
    scanf("%d", &input[i]);
  }
  
  printf("======要存入的数据======\n");
  for (int i = 0; i < size; i++) {
    printf("%d ", input[i]);
  }
  printf("\n\n");
  
  FIFO(input, size);
  printf("\n");
  LRU(input, size);
  
  return 0;
}