devbox
Cpp五条
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

操作系统实验四 页面置换算法（fifo 算法代码------页面置换代码集合）_fifo页面置换算法实验目的

作者：Cpp五条 | 2024-06-08 00:13:12

赞

踩

fifo页面置换算法实验目的

实验四 存储器管理

一、     实验目的

1.       理解连续存储管理方式的原理和分类。 

2.       理解离散存储管理方式的原理和分类。

3.       理解虚拟存储器的原理和分类。

4.       掌握动态分区分配的常用算法。

5.       掌握页式虚拟管理中常用页面置换算法。 

二、     实验设备

1.     安装windows或者linux操作系统的PC机

2.     C程序编译环境

三、     实验内容

用C语言编程模拟实现一种或多种动态分区分配算法或页面置换算法。常见的动态分区分配算法有最先适应算法、循环首次适应算法、最佳适应算法、最坏适应算法等，常见的页面置换算法有先进先出(FIFO)页面置换算法、最近最久未使用(LRU)置换算法、最少使用(LFU)置换算法等。

四、     实验要求

1.     上机编写并调试动态分区分配算法(或页面置换算法)的模拟程序。

2.     要把相应的程序代码及程序运行结果写入实验报告中。


 先进先出(FIFO)页面置换算法

  1. #include "stdio.h"
  2.  
  3. #include "stdlib.h"
  4.  
  5. #include "math.h"
  6.  
  7. #include "conio.h"
  8.  
  9. #include "time.h"
  10.  
  11. #define TRUE 1
  12.  
  13. #define FALSE 0
  14.  
  15. #define NULL 0
  16.  
  17. #define total_instruction 20
  18.  
  19. #define total_vp 10
  20.  
  21. typedef struct
  22.  
  23. { int pn,pfn;
  24.  
  25. }pv_type;
  26.  
  27. pv_type pv[10];
  28.  
  29. typedef struct pf_struct
  30.  
  31. { int pn,pfn;
  32.  
  33. struct pf_struct *next;
  34.  
  35. }pf_type;
  36.  
  37. pf_type pf[20],*free_head,*busy_head,*busy_tail,*q;
  38.  
  39. int page[total_instruction];
  40.  
  41. int total_pf;
  42.  
  43. int count;
  44.  
  45. void initialiaze()
  46.  
  47. { int i;
  48.  
  49. count=0;
  50.  
  51. for(i=0;i<total_vp;i++)
  52.  
  53. { pv[i].pn=i;
  54.  
  55. pv[i].pfn=-1;
  56.  
  57. }
  58.  
  59. printf("请输入实页数目:");
  60.  
  61. scanf("%d",&total_pf);
  62.  
  63. for(i=0;i<=total_pf-1;i++)
  64.  
  65. { pf[i].next=&pf[i+1];
  66.  
  67. pf[i].pfn=i+1;
  68.  
  69. pf[i].pn=-1;
  70.  
  71. }
  72.  
  73. pf[total_pf-1].next=NULL;
  74.  
  75. free_head=&pf[0];
  76.  
  77. printf("随机产生的页地址流为：\n");
  78.  
  79. for(i=0;i<total_instruction;i++)
  80.  
  81. { page[i]=rand()%10;
  82.  
  83. printf("%2d",page[i]);
  84.  
  85. }
  86.  
  87. }
  88.  
  89. void FIFO()
  90.  
  91. { int i,j;
  92.  
  93. pf_type *p;
  94.  
  95. q=busy_head=busy_tail=NULL;
  96.  
  97. for(i=0;i<=total_instruction-1;i++)
  98.  
  99. { printf("\n第%d次执行:",i+1);
  100.  
  101. if(pv[page[i]].pfn==-1)
  102.  
  103. { count+=1;
  104.  
  105. printf("缺页，缺页次数count=%d,",count);
  106.  
  107. if(free_head==NULL)
  108.  
  109. {
  110.  
  111. printf("实页%d中的页面%d将被置换出去",busy_head->pfn,busy_head->pn);
  112.  
  113. p=busy_head->next;
  114.  
  115. pv[busy_head->pn].pfn=-1;
  116.  
  117. free_head=busy_head;
  118.  
  119. free_head->next=NULL;
  120.  
  121. busy_head=p;
  122.  
  123. }
  124.  
  125. p=free_head->next;
  126.  
  127. free_head->next=NULL;
  128.  
  129. free_head->pn=page[i];
  130.  
  131. pv[page[i]].pfn=free_head->pn;
  132.  
  133. if(busy_tail==NULL)
  134.  
  135. busy_head=busy_tail=free_head;
  136.  
  137. else
  138.  
  139. { busy_tail->next=free_head;
  140.  
  141. busy_tail=free_head;
  142.  
  143. }
  144.  
  145. free_head=p;
  146.  
  147. }
  148.  
  149. else printf("命中，缺页次数不变，仍为count=%d",count);
  150.  
  151. printf("\npfn pn");
  152.  
  153. for(j=0;j<=total_pf-1;j++)
  154.  
  155. {if(pf[j].pn!=-1)
  156.  
  157. printf("\n%d%8d",pf[j].pfn,pf[j].pn);
  158.  
  159. }
  160.  
  161. }
  162.  
  163. printf("\n先进先出算法的命中率为:%6.4f\n缺页总次数为%d\n",1-(float)count/20,count);
  164.  
  165. }
  166.  
  167. int main()
  168.  
  169. {
  170.  
  171. srand((unsigned)time(NULL));
  172.  
  173. initialiaze();
  174.  
  175. FIFO();
  176.  
  177. return 0;
  178. <h2 style="text-align: center;">}
  179. 常见的页面置换算法有先进先出(FIFO)页面置换算法、最近最久未使用(LRU)置换算法、最少使用(LFU)置换算法等。</h2>

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. /*È«¾Ö±äÁ¿*/
  4. int mSIZE; /*ÎïÀí¿éÊý*/
  5. int pSIZE; /*Ò³ÃæºÅÒýÓô®¸öÊý*/
  6. static int memery[10]={0}; /*ÎïÀí¿éÖеÄÒ³ºÅ*/
  7. static int page[100]={0}; /*Ò³ÃæºÅÒýÓô®*/
  8. static int temp[100][10]={0}; /*¸¨ÖúÊý×é*/
  9. /*Öû»Ëã·¨º¯Êý*/
  10. void FIFO();
  11. void LRU();
  12. void OPT();
  13. /*¸¨Öúº¯Êý*/
  14. void print(unsigned int t);
  15. void designBy();
  16. void download();
  17. void mDelay(unsigned int Delay);
  18. /*Ö÷º¯Êý*/
  19. int main()
  20. {
  21.     int i,k,code;
  22. 	system("color 0A");
  23. 	designBy();
  24. 	printf("©§Çë°´ÈÎÒâ¼ü½øÐгõʼ»¯²Ù×÷...                       ©§\n");
  25. 	printf("©»©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¿\n");
  26. 	printf(" >>>");
  27. 	getchar();
  28. 	system("cls");
  29. 	system("color 0B");
  30. 	printf("ÇëÊäÈëÎïÀí¿éµÄ¸öÊý(M<=10)£º");
  31. 	scanf("%d",&mSIZE);
  32. 	printf("ÇëÊäÈëÒ³ÃæºÅÒýÓô®µÄ¸öÊý(P<=100)£º");
  33. 	scanf("%d",&pSIZE);
  34. 	puts("ÇëÒÀ´ÎÊäÈëÒ³ÃæºÅÒýÓô®(Á¬ÐøÊäÈ룬ÎÞÐè¸ô¿ª)£º");
  35. 	for(i=0;i<pSIZE;i++)
  36.         scanf("%1d",&page[i]);
  37. 	download();
  38. 	system("cls");
  39. 	system("color 0E");
  40.     do{ 
  41. 		puts("ÊäÈëµÄÒ³ÃæºÅÒýÓô®Îª£º");
  42. 		for(k=0;k<=(pSIZE-1)/20;k++)
  43. 		{
  44. 			for(i=20*k;(i<pSIZE)&&(i<20*(k+1));i++)
  45. 			{
  46. 				if(((i+1)%20==0)||(((i+1)%20)&&(i==pSIZE-1)))
  47. 					printf("%d\n",page[i]);
  48. 				else
  49. 					printf("%d   ",page[i]);
  50. 			}
  51. 		}
  52. 		printf("* * * * * * * * * * * * * * * * * * * * * * *\n");
  53.         printf("* ÇëÑ¡ÔñÒ³ÃæÖû»Ëã·¨£º\t\t\t    *\n");
  54. 		printf("* ----------------------------------------- *\n");
  55.         printf("* 1.ÏȽøÏȳö(FIFO)    2.×î½ü×î¾ÃδʹÓÃ(LRU) *\n");
  56. 		printf("* 3.×î¼Ñ(OPT)         4.Í˳ö                *\n");
  57. 		printf("* * * * * * * * * * * * * * * * * * * * * * *\n");
  58.         printf("ÇëÑ¡Ôñ²Ù×÷£º[ ]\b\b");
  59.         scanf("%d",&code);
  60.         switch(code)
  61.         {
  62.         case 1:
  63.             FIFO();
  64.             break;
  65.         case 2:
  66.             LRU();
  67.             break;
  68.         case 3:
  69.             OPT();
  70.             break;
  71.         case 4:
  72. 			system("cls");
  73. 			system("color 0A");
  74. 			designBy(); /*ÏÔʾÉè¼ÆÕßÐÅÏ¢ºóÍ˳ö*/
  75. 			printf("©§Ð»Ð»Ê¹ÓÃÒ³ÃæÖû»Ëã·¨ÑÝʾÆ÷!                       ©§\n");
  76. 			printf("©»©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¿\n");
  77.             exit(0);
  78. 		default:
  79. 			printf("ÊäÈë´íÎó£¬ÇëÖØÐÂÊäÈ룺");
  80.         }
  81. 		printf("°´ÈÎÒâ¼üÖØÐÂÑ¡ÔñÖû»Ëã·¨£º>>>");
  82. 		getchar();
  83. 		system("cls");
  84.     }while (code!=4);
  85. 	getch();
  86. 	return 0;
  87. }
  88. /*ÔØÈëÊý¾Ý*/
  89. void download()
  90. {
  91. 	int i;
  92. 	system("color 0D");
  93. 	printf("¨X¨T¨T¨T¨T¨T¨T¨T¨T¨T¨T¨T¨T¨[\n");
  94. 	printf("¨UÕýÔÚÔØÈëÊý¾Ý£¬ÇëÉÔºò !!!¨U\n");
  95. 	printf("¨^¨T¨T¨T¨T¨T¨T¨T¨T¨T¨T¨T¨T¨a\n");
  96. 	printf("Loading...\n");
  97. 	printf("                                                  O");
  98. 	for(i=0;i<51;i++)
  99. 		printf("\b");
  100. 	for(i=0;i<50;i++)
  101. 	{
  102. 		mDelay((pSIZE+mSIZE)/2);
  103. 		printf(">");
  104. 	}
  105. 	printf("\nFinish.\nÔØÈë³É¹¦£¬°´ÈÎÒâ¼ü½øÈëÖû»Ë㷨ѡÔñ½çÃ棺>>>");
  106. 	getchar();
  107. }
  108. /*ÉèÖÃÑÓ³Ù*/
  109. void mDelay(unsigned int Delay)
  110. { 
  111.     unsigned int i; 
  112.     for(;Delay>0;Delay--) 
  113. 	{   
  114. 		for(i=0;i<124;i++) 
  115. 		{
  116. 			printf(" \b");
  117. 		} 
  118. 	} 
  119. }
  120. /*ÏÔʾÉè¼ÆÕßÐÅÏ¢*/ 
  121. void designBy()
  122. {
  123. 	printf("©³©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©·\n");
  124. 	printf("©§             ʵÑéËÄ£ºÒ³ÃæÖû»Ëã·¨                 ©§\n");
  125. 	printf("©§                °à¼¶£º                            ©§\n");
  126. 	printf("©§                  ÐÕÃû£ºÕÅͬѧ                    ©§\n");
  127. 	printf("©Ç©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©¥©Ï\n");
  128. }
  129. void print(unsigned int t)
  130. {
  131. 	int i,j,k,l;
  132. 	int flag;
  133. 	for(k=0;k<=(pSIZE-1)/20;k++)
  134. 	{
  135. 		for(i=20*k;(i<pSIZE)&&(i<20*(k+1));i++)
  136. 		{
  137. 			if(((i+1)%20==0)||(((i+1)%20)&&(i==pSIZE-1)))
  138. 				printf("%d\n",page[i]);
  139. 			else
  140. 				printf("%d   ",page[i]);
  141. 		}
  142. 		for(j=0;j<mSIZE;j++)
  143. 		{
  144. 			for(i=20*k;(i<mSIZE+20*k)&&(i<pSIZE);i++)
  145. 			{
  146. 				if(i>=j)
  147. 					printf(" |%d|",temp[i][j]);
  148. 				else
  149. 					printf(" | |");
  150. 			}
  151. 			for(i=mSIZE+20*k;(i<pSIZE)&&(i<20*(k+1));i++)
  152. 			{
  153. 				for(flag=0,l=0;l<mSIZE;l++)
  154. 					if(temp[i][l]==temp[i-1][l])
  155. 						flag++;
  156. 				if(flag==mSIZE)/*Ò³ÃæÔÚÎïÀí¿éÖÐ*/
  157. 					printf("    ");
  158. 				else
  159. 					printf(" |%d|",temp[i][j]);
  160. 			}
  161. 			/*ÿÐÐÏÔʾ20¸ö*/
  162. 			if(i%20==0)
  163. 				continue;
  164. 			printf("\n");
  165. 		}
  166. 	}
  167. 	printf("----------------------------------------\n");
  168. 	printf("ȱҳ´ÎÊý£º%d\t\t",t+mSIZE);
  169. 	printf("ȱҳÂÊ£º%d/%d\n",t+mSIZE,pSIZE);
  170. 	printf("Öû»´ÎÊý£º%d\t\t",t);
  171. 	printf("·ÃÎÊÃüÖÐÂÊ£º%d%%\n",(pSIZE-(t+mSIZE))*100/pSIZE);
  172. 	printf("----------------------------------------\n");	
  173. }
  174. /*¼ÆËã¹ý³ÌÑÓ³Ù*/
  175. void compute()
  176. {
  177. 	int i;
  178. 	printf("ÕýÔÚ½øÐÐÏà¹Ø¼ÆË㣬ÇëÉÔºò");
  179. 	for(i=1;i<20;i++)
  180. 	{
  181. 		mDelay(15);
  182. 		if(i%4==0)
  183. 			printf("\b\b\b\b\b\b      \b\b\b\b\b\b");
  184. 		else
  185. 			printf("¦¨");
  186. 	}
  187. 	for(i=0;i++<30;printf("\b"));
  188. 	for(i=0;i++<30;printf(" "));
  189. 	for(i=0;i++<30;printf("\b"));
  190. }
  191. /*ÏȽøÏȳöÒ³ÃæÖû»Ëã·¨*/
  192. void FIFO()
  193. {
  194.     int memery[10]={0};
  195.     int time[10]={0}; /*¼Ç¼½øÈëÎïÀí¿éµÄʱ¼ä*/
  196.     int i,j,k,m;
  197.     int max=0; /*¼Ç¼»»³öÒ³*/
  198.     int count=0; /*¼Ç¼Öû»´ÎÊý*/
  199. 	/*Ç°mSIZE¸öÊýÖ±½Ó·ÅÈë*/
  200.     for(i=0;i<mSIZE;i++)
  201.     {
  202.         memery[i]=page[i];
  203.         time[i]=i;
  204.         for(j=0;j<mSIZE;j++)
  205. 			temp[i][j]=memery[j];
  206.     }
  207.     for(i=mSIZE;i<pSIZE;i++)
  208.     {
  209. 		/*ÅжÏÐÂÒ³ÃæºÅÊÇ·ñÔÚÎïÀí¿éÖÐ*/
  210.         for(j=0,k=0;j<mSIZE;j++)
  211.         {
  212.             if(memery[j]!=page[i])
  213.                 k++;
  214.         }
  215.         if(k==mSIZE) /*Èç¹û²»ÔÚÎïÀí¿éÖÐ*/
  216.         {
  217.             count++;
  218. 			/*¼ÆËã»»³öÒ³*/
  219.             max=time[0]<time[1]?0:1;
  220. 			for(m=2;m<mSIZE;m++)
  221. 				if(time[m]<time[max])
  222. 					max=m;
  223.             memery[max]=page[i];
  224.             time[max]=i; /*¼Ç¼¸ÃÒ³½øÈëÎïÀí¿éµÄʱ¼ä*/
  225.             for(j=0;j<mSIZE;j++)
  226. 				temp[i][j]=memery[j];
  227.         }
  228.         else
  229.         {
  230.             for(j=0;j<mSIZE;j++)
  231. 				temp[i][j]=memery[j];
  232.         } 
  233.     }
  234. 	compute();
  235. 	print(count);
  236. }
  237. /*×î½ü×î¾ÃδʹÓÃÖû»Ëã·¨*/
  238. void LRU()
  239. {
  240.     int memery[10]={0};
  241.     int flag[10]={0}; /*¼Ç¼ҳÃæµÄ·ÃÎÊʱ¼ä*/
  242.     int i,j,k,m;
  243.     int max=0; /*¼Ç¼»»³öÒ³*/
  244.     int count=0; /*¼Ç¼Öû»´ÎÊý*/
  245. 	/*Ç°mSIZE¸öÊýÖ±½Ó·ÅÈë*/
  246.     for(i=0;i<mSIZE;i++)
  247.     {
  248.         memery[i]=page[i];
  249.         flag[i]=i;
  250.         for(j=0;j<mSIZE;j++)
  251. 			temp[i][j]=memery[j];
  252.     }
  253.     for(i=mSIZE;i<pSIZE;i++)
  254.     {
  255. 		/*ÅжÏÐÂÒ³ÃæºÅÊÇ·ñÔÚÎïÀí¿éÖÐ*/
  256.         for(j=0,k=0;j<mSIZE;j++)
  257.         {
  258.             if(memery[j]!=page[i])
  259.                 k++;
  260.             else 
  261. 				flag[j]=i; /*ˢиÃÒ³µÄ·ÃÎÊʱ¼ä*/
  262.         }
  263.         if(k==mSIZE) /*Èç¹û²»ÔÚÎïÀí¿éÖÐ*/
  264.         {
  265.             count++;
  266. 			/*¼ÆËã»»³öÒ³*/
  267.             max=flag[0]<flag[1]?0:1;
  268. 			for(m=2;m<mSIZE;m++)
  269. 				if(flag[m]<flag[max])
  270. 					max=m;
  271.             memery[max]=page[i];
  272.             flag[max]=i; /*¼Ç¼¸ÃÒ³µÄ·ÃÎÊʱ¼ä*/
  273.             for(j=0;j<mSIZE;j++)
  274. 				temp[i][j]=memery[j];
  275.         }
  276.         else
  277.         {
  278.             for(j=0;j<mSIZE;j++)
  279. 				temp[i][j]=memery[j];
  280.         }
  281.     }
  282. 	compute();
  283. 	print(count);
  284. }
  285. /*×î¼ÑÖû»Ëã·¨*/
  286. void OPT()
  287. {
  288.     int memery[10]={0};
  289.     int next[10]={0}; /*¼Ç¼ÏÂÒ»´Î·ÃÎÊʱ¼ä*/
  290.     int i,j,k,l,m;
  291.     int max; /*¼Ç¼»»³öÒ³*/
  292.     int count=0; /*¼Ç¼Öû»´ÎÊý*/
  293. 	/*Ç°mSIZE¸öÊýÖ±½Ó·ÅÈë*/
  294.     for(i=0;i<mSIZE;i++)
  295.     {
  296.         memery[i]=page[i];
  297.         for(j=0;j<mSIZE;j++)
  298. 			temp[i][j]=memery[j];
  299.     }
  300.     for(i=mSIZE;i<pSIZE;i++)
  301.     {
  302. 		/*ÅжÏÐÂÒ³ÃæºÅÊÇ·ñÔÚÎïÀí¿éÖÐ*/
  303.         for(j=0,k=0;j<mSIZE;j++)
  304.         {
  305.             if(memery[j]!=page[i])
  306.                 k++;
  307.         }
  308.         if(k==mSIZE) /*Èç¹û²»ÔÚÎïÀí¿éÖÐ*/
  309.         {
  310. 			count++;
  311. 			/*µÃµ½ÎïÀí¿ìÖи÷Ò³ÏÂÒ»´Î·ÃÎÊʱ¼ä*/
  312. 			for(m=0;m<mSIZE;m++)
  313. 			{
  314. 				for(l=i+1;l<pSIZE;l++)
  315. 					if(memery[m]==page[l])
  316. 						break;
  317. 				next[m]=l;
  318. 			}
  319. 			/*¼ÆËã»»³öÒ³*/
  320. 			max=next[0]>=next[1]?0:1;
  321. 			for(m=2;m<mSIZE;m++)
  322. 				if(next[m]>next[max])
  323. 					max=m;
  324. 			/*ÏÂÒ»´Î·ÃÎÊʱ¼ä¶¼ÎªpSIZE,ÔòÖû»ÎïÀí¿éÖеÚÒ»¸ö*/
  325. 			memery[max]=page[i];
  326. 			for(j=0;j<mSIZE;j++)
  327. 				temp[i][j]=memery[j];
  328.         }
  329.         else {
  330.             for(j=0;j<mSIZE;j++)
  331. 				temp[i][j]=memery[j];
  332.         }
  333.     }
  334. 	compute();
  335. 	print(count);
  336. }



声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Cpp五条/article/detail/687641
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号