深圳幻海软件技术有限公司 欢迎您!

【操作系统】FIFO先进先出页面置换算法(C语言实现)

2023-06-30

FIFO页面置换算法,计算缺页率,文末附代码,及例题解析1、内容    在地址映射过程中,若在页面中发现所要访问的页面不在内存中,则产生缺页中断。当发生缺页中断时,如果操作系统内存中没有空闲页面,则操作系统必须在内存选择一个页面将其移出内存,以便为即将调入的页

FIFO页面置换算法,计算缺页率,文末附代码,及例题解析

1、内容

        在地址映射过程中,若在页面中发现所要访问的页面不在内存中,则产生缺页中断。当发生缺页中断时,如果操作系统内存中没有空闲页面,则操作系统必须在内存选择一个页面将其移出内存,以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。

        模拟内存的页式管理,实现内存的分配和调用,完成虚拟内存地址序列和物理内存的对应。在内存调用出现缺页时,调入程序的内存页。在出现无空闲页面时,使用先进先出(FIFO)算法实现页面置换。

2、页的结构

页的结构如下:

  页号、页面号、时间戳(在本算法中未使用,在LRU中使用)

名称

符号

功能

页号

Page_num

记录页号

页面号

Pframe_num

记录页面号

      FIFO页面置换算法选择在主存中停留时间最长(即最老)的一页置换,即先进入内存的页,先退出内存。理由是:最早调入内存的页,其不再被使用的可能性比刚调入内存的可能性大。建立一个FIFO队列,收容所有在内存中的页。被置换页面总是在队列头上进行。当一个页面被放入内存时,就把它插在队尾上

       通过使用线性表来实现页表,在每次需要淘汰页时,都是淘汰最先进入的页,这样就可以实现淘汰在主存中停留时间最长的页。

流程如下:

3、例题解析

在页式管理系统中,访问的顺序(访问串)为:1,2,3,4,1,2,5,1,2,3,4,5,当分配的页面数量为3时,请分别计算使用下述(1)替换算法的缺页次数,并画出页面置换图。

(1)  FIFO。

访问串123412512345
页面1123412555344
页面212341222533
页面31234111255
是否缺页

缺页率:9/12=0.75

4、代码如下:

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #define MAX_PAGES 20
  5. #define MAX_PFRAME 20
  6. #define INVALID -1
  7. typedef struct {
  8. int page_num;
  9. int pframe_num;
  10. int count;
  11. int timestamp;
  12. }page_type;
  13. page_type page[MAX_PAGES];
  14. typedef struct pf_struct {
  15. int pframe_num;//页面号
  16. struct pf_struct* next;
  17. }pf_type;
  18. pf_type pframe[MAX_PFRAME];
  19. int diseffct = 0;//缺页记录
  20. void InitPage(const int* page_n, const int* pframe_n)
  21. {
  22. int total_vp = *page_n, total_pf = *pframe_n;
  23. int i = 0;
  24. diseffct = 0;
  25. for (i = 0; i < total_vp; i++)//虚拟页
  26. {
  27. page[i].page_num = i;
  28. page[i].pframe_num = INVALID;
  29. page[i].count = 0;
  30. page[i].timestamp = -1;
  31. }
  32. for (i = 0; i < total_pf - 1; i++)
  33. {
  34. pframe[i].next = &pframe[i];
  35. pframe[i].pframe_num = i;
  36. }
  37. pframe[total_pf - 1].next = NULL;
  38. pframe[total_pf - 1].pframe_num = total_pf - 1;
  39. }
  40. double miss_page_rate(int pframe_order[100]) {
  41. int i = 0;
  42. double missrate = 0, count = 0;
  43. while (pframe_order[i] != -1)
  44. {
  45. count++;
  46. i++;
  47. }
  48. missrate = diseffct / count;
  49. return missrate;
  50. }
  51. void menu(int* page_n, int* pframe_n)
  52. {
  53. int a, b;
  54. printf("---------------------------------------------\n");
  55. printf("请输入页面的数量:");
  56. scanf("%d", page_n);
  57. printf("请输入页的数量:");
  58. scanf("%d", pframe_n);
  59. printf("--------------------------------------------\n");
  60. }
  61. int get_input_order(int fprame_order[100], int pframe_n)
  62. {
  63. int p = 0;
  64. int tmp = 0;
  65. printf("请输入访问串(1到%d中的数字,每输入一个数输入一次回车,输入-1表示结束):\n", pframe_n);
  66. while (1)
  67. {
  68. scanf("%d", &tmp);
  69. fprame_order[p] = tmp;
  70. p++;
  71. if (tmp == -1)
  72. {
  73. break;
  74. }
  75. }
  76. return p;
  77. }
  78. int check_all_page(int page_num, int target)
  79. {
  80. int judge = 0;
  81. for (int i = 0; i < page_num; i++)
  82. {
  83. if (page[i].pframe_num == target)
  84. {
  85. judge = 1;
  86. }
  87. }
  88. if (judge == 1)
  89. {
  90. return 1;
  91. }
  92. else
  93. {
  94. diseffct++;//全程序只在本处处理缺页次数
  95. return 0;
  96. }
  97. }
  98. void display(int page_num, int judge)//就是打印出所有的页
  99. {
  100. printf("页面号\t页号\t时间戳\n");
  101. for (int i = 0; i < page_num; i++)
  102. {
  103. printf("%d\t%d\t%d\n", page[i].page_num, page[i].pframe_num, page[i].timestamp);
  104. }
  105. if (judge == 1) {
  106. printf("不缺页\n");
  107. }
  108. else
  109. {
  110. printf("缺页\n");
  111. }
  112. }
  113. void FIFO(int page_num, int pframe_id)//page_num为页的数量,pframe_id为页面号
  114. {
  115. int i, j;
  116. pf_type* p;
  117. for (i = page_num - 2; i >= 0; i--)
  118. {
  119. //page[i + 1].count = page[i].count;
  120. page[i + 1].pframe_num = page[i].pframe_num;
  121. }
  122. page[0].pframe_num = pframe_id;
  123. }
  124. void execute_pagef(int pframe_order[100], int page_num)//page_num为虚拟页的数量,page_n指针和page_num的值一样
  125. {
  126. int i = 0, jugde = 0;
  127. while (pframe_order[i] != -1)
  128. {
  129. printf("************************************\n");
  130. printf("使用页 %d\n", pframe_order[i]);
  131. jugde = check_all_page(page_num, pframe_order[i]);
  132. if (jugde == 1) {//在虚拟页内
  133. i++;
  134. }
  135. else//不在页内就调用页面置换算法
  136. {
  137. FIFO(page_num, pframe_order[i]);
  138. i++;
  139. }
  140. display(page_num, jugde);
  141. }
  142. }
  143. int main()
  144. {
  145. int* page_n = (int*)malloc(sizeof(int));
  146. int* pframe_n = (int*)malloc(sizeof(int));
  147. int pframe_order[100];
  148. int order_num = 0;
  149. menu(page_n, pframe_n);
  150. InitPage(page_n, pframe_n);
  151. order_num = get_input_order(pframe_order, *pframe_n);
  152. execute_pagef(pframe_order, *page_n);
  153. //printf("%d %d\n", *page_n, *pframe_n);
  154. printf("\n缺页率为: %lf", miss_page_rate(pframe_order));
  155. free(page_n);
  156. free(pframe_n);
  157. return 0;
  158. }

5、运行如下:

程序分为5个页,内存中有3个页面,访问串是1、2、3、2、4、5、2

缺页率为:0.857143

文章知识点与官方知识档案匹配,可进一步学习相关知识
算法技能树首页概览48594 人正在系统学习中
html>