fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4.  
  5. #define INSTR_NUM 320
  6. #define INSTR_PER_PAGE 32
  7. #define VIRTUAL_PAGES (INSTR_NUM / INSTR_PER_PAGE)   // 10 pages
  8.  
  9. // 生成随机指令序列
  10. void generate_instructions(int instr[]) {
  11.     for (int i = 0; i < INSTR_NUM; i++) {
  12.         instr[i] = rand() % INSTR_NUM;  // 0 ~ 319
  13.     }
  14. }
  15.  
  16. // 指令地址转页面号
  17. void convert_to_pages(int instr[], int pages[]) {
  18.     for (int i = 0; i < INSTR_NUM; i++) {
  19.         pages[i] = instr[i] / INSTR_PER_PAGE;
  20.     }
  21. }
  22.  
  23. // FIFO 算法
  24. int simulate_fifo(int pages[], int capacity) {
  25.     int faults = 0;
  26.     int frames[40];
  27.     int front = 0, rear = 0, count = 0;
  28.  
  29.     int in_frame[40] = {0};
  30.  
  31.     for (int i = 0; i < INSTR_NUM; i++) {
  32.         int p = pages[i];
  33.  
  34.         if (!in_frame[p]) {
  35.             // 缺页
  36.             faults++;
  37.  
  38.             if (count < capacity) {
  39.                 frames[rear] = p;
  40.                 rear = (rear + 1) % capacity;
  41.                 count++;
  42.             } else {
  43.                 // 淘汰最早进入的页面
  44.                 int old = frames[front];
  45.                 in_frame[old] = 0;
  46.                 front = (front + 1) % capacity;
  47.  
  48.                 frames[rear] = p;
  49.                 rear = (rear + 1) % capacity;
  50.             }
  51.             in_frame[p] = 1;
  52.         }
  53.     }
  54.     return faults;
  55. }
  56.  
  57. // LRU 算法
  58. int simulate_lru(int pages[], int capacity) {
  59.     int faults = 0;
  60.     int frames[40];
  61.     int last_used[40]; // 记录最近访问时间
  62.  
  63.     for (int i = 0; i < capacity; i++) frames[i] = -1;
  64.     for (int i = 0; i < 40; i++) last_used[i] = -1;
  65.  
  66.     int time = 0;
  67.  
  68.     for (int i = 0; i < INSTR_NUM; i++) {
  69.         int p = pages[i];
  70.         int hit = 0;
  71.  
  72.         // 是否命中
  73.         for (int j = 0; j < capacity; j++) {
  74.             if (frames[j] == p) {
  75.                 hit = 1;
  76.                 last_used[p] = time++;
  77.                 break;
  78.             }
  79.         }
  80.  
  81.         if (!hit) {
  82.             faults++;
  83.  
  84.             // 找空位置
  85.             int placed = 0;
  86.             for (int j = 0; j < capacity; j++) {
  87.                 if (frames[j] == -1) {
  88.                     frames[j] = p;
  89.                     last_used[p] = time++;
  90.                     placed = 1;
  91.                     break;
  92.                 }
  93.             }
  94.  
  95.             // 若无空位，找最久未使用
  96.             if (!placed) {
  97.                 int lru_page = frames[0];
  98.                 int lru_index = 0;
  99.  
  100.                 for (int j = 1; j < capacity; j++) {
  101.                     if (last_used[frames[j]] < last_used[lru_page]) {
  102.                         lru_page = frames[j];
  103.                         lru_index = j;
  104.                     }
  105.                 }
  106.  
  107.                 frames[lru_index] = p;
  108.                 last_used[p] = time++;
  109.             }
  110.         }
  111.     }
  112.     return faults;
  113. }
  114.  
  115. // OPT 算法
  116. int simulate_opt(int pages[], int capacity) {
  117.     int faults = 0;
  118.     int frames[40];
  119.  
  120.     for (int i = 0; i < capacity; i++) frames[i] = -1;
  121.  
  122.     for (int i = 0; i < INSTR_NUM; i++) {
  123.         int p = pages[i];
  124.         int hit = 0;
  125.  
  126.         for (int j = 0; j < capacity; j++) {
  127.             if (frames[j] == p) {
  128.                 hit = 1;
  129.                 break;
  130.             }
  131.         }
  132.  
  133.         if (!hit) {
  134.             faults++;
  135.  
  136.             // 找空位
  137.             int placed = 0;
  138.             for (int j = 0; j < capacity; j++) {
  139.                 if (frames[j] == -1) {
  140.                     frames[j] = p;
  141.                     placed = 1;
  142.                     break;
  143.                 }
  144.             }
  145.  
  146.             if (!placed) {
  147.                 int farthest_index = -1;
  148.                 int replace_pos = 0;
  149.  
  150.                 for (int j = 0; j < capacity; j++) {
  151.                     int next_use = -1;
  152.  
  153.                     for (int k = i + 1; k < INSTR_NUM; k++) {
  154.                         if (pages[k] == frames[j]) {
  155.                             next_use = k;
  156.                             break;
  157.                         }
  158.                     }
  159.  
  160.                     if (next_use == -1) {
  161.                         replace_pos = j;  // 不再使用，直接换掉
  162.                         break;
  163.                     }
  164.  
  165.                     if (next_use > farthest_index) {
  166.                         farthest_index = next_use;
  167.                         replace_pos = j;
  168.                     }
  169.                 }
  170.  
  171.                 frames[replace_pos] = p;
  172.             }
  173.         }
  174.     }
  175.  
  176.     return faults;
  177. }
  178.  
  179. int main() {
  180.     srand(time(NULL));
  181.  
  182.     int instructions[INSTR_NUM];
  183.     int pages[INSTR_NUM];
  184.  
  185.     generate_instructions(instructions);
  186.     convert_to_pages(instructions, pages);
  187.  
  188.     printf("内存容量\tFIFO命中率\tLRU命中率\tOPT命中率\n");
  189.  
  190.     for (int cap = 4; cap <= 32; cap++) {
  191.         int fifo_fault = simulate_fifo(pages, cap);
  192.         int lru_fault = simulate_lru(pages, cap);
  193.         int opt_fault = simulate_opt(pages, cap);
  194.  
  195.         double fifo_hit = 1 - fifo_fault / (double)INSTR_NUM;
  196.         double lru_hit  = 1 - lru_fault  / (double)INSTR_NUM;
  197.         double opt_hit  = 1 - opt_fault  / (double)INSTR_NUM;
  198.  
  199.         printf("%3d\t\t%.4f\t\t%.4f\t\t%.4f\n",
  200.                cap, fifo_hit, lru_hit, opt_hit);
  201.     }
  202.  
  203.     return 0;
  204. }
  205.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
内存容量	FIFO命中率	LRU命中率	OPT命中率
  4		0.4125		0.3969		0.6344
  5		0.4844		0.5000		0.7281
  6		0.5938		0.5844		0.7969
  7		0.6813		0.6969		0.8562
  8		0.7719		0.7875		0.9062
  9		0.8938		0.8969		0.9437
 10		0.9688		0.9688		0.9688
 11		0.9688		0.9688		0.9688
 12		0.9688		0.9688		0.9688
 13		0.9688		0.9688		0.9688
 14		0.9688		0.9688		0.9688
 15		0.9688		0.9688		0.9688
 16		0.9688		0.9688		0.9688
 17		0.9688		0.9688		0.9688
 18		0.9688		0.9688		0.9688
 19		0.9688		0.9688		0.9688
 20		0.9688		0.9688		0.9688
 21		0.9688		0.9688		0.9688
 22		0.9688		0.9688		0.9688
 23		0.9688		0.9688		0.9688
 24		0.9688		0.9688		0.9688
 25		0.9688		0.9688		0.9688
 26		0.9688		0.9688		0.9688
 27		0.9688		0.9688		0.9688
 28		0.9688		0.9688		0.9688
 29		0.9688		0.9688		0.9688
 30		0.9688		0.9688		0.9688
 31		0.9688		0.9688		0.9688
 32		0.9688		0.9688		0.9688
https://ideone.com/DkoFW3
language:
C (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!