实验六 请求分页系统页面置换算法.doc

实验六 请求分页系统页面置换算法实验目的： 实现分页式存储地址转换过程，在此基础上实现请求分页的地址转换。实现请求分页式地址转换中出现的缺页现象中，用到的FIFO、LRU、OPT置换算法。 实现方法： 用一张位示图，来模拟内存的分配情况，利用随机数产生一组0和1的数对应内存的使用情况。 利用结构体数组将页表和内存块封装。 实现过程： cpp view plaincopy01.#include 02.#include 03.#include 04.#include 05.struct Page 06. 07. int kuai; 08. int stage; 09.FPage1000,LPage1000; 10. 11.struct Memory 12. 13. int num; 14. int page; 15.FMemory1000,LMemory1000,OMemory1000; 16. 17.int PageLength; /*页表长度*/ 18.int Memsize; /*内存块数*/ 19.int FAbsent,LAbsent,OAbsent,visit; /*FIFO中的缺页次数 LRU中的缺页次数 访问内存次数 */ 20.int Logical; /*逻辑地址*/ 21.int Pagenumber,Pageaddr;/*页号 页内地址*/ 22.int Physical; /*物理地址*/ 23.int PageSize; /*块的大小*/ 24.int Freemem; /*空闲内存*/ 25. 26.int G88; 27. 28.int opt10000; int oth=0; 29.int temp1000; 30. 31.void GShow() 32. 33. int i,j; 34. printf(位式图：n); 35. for(i=0;i8;i+) 36. 37. printf(t); 38. for(j=0;j8;j+) 39. printf(%d ,Gij); 40. printf(n); 41. 42. 43. 44. 45.void init() /*初始化*/ 46. 47. srand(unsigned)time(NULL); 48. int i,j; 49. for(i=0;i8;i+) 50. G0i=1; 51. for(i=1;i8;i+) 52. 53. for(j=0;j8;j+) 54. Gij=rand()%2; 55. 56. 57. for(i=0;iPageLength;i+) 58. 59. FPagei.kuai=-1; FPagei.stage=0; 60. LPagei.kuai=-1; LPagei.stage=0; 61. 62. for(i=0;iMemsize;i+) 63. 64. FMemoryi.page=-1; 65. 66. for(i=0;iMemsize;i+) 67. 68. LMemoryi.page=-1; 69. 70. for(i=0;iMemsize;i+) 71. 72. OMemoryi.num=i; 73. OMemoryi.page=-1; 74. 75. 76. FAbsent=LAbsent=visit=0; 77. 78. 79. 80.void Show() 81. 82. int i; 83. 84. printf(FPage：tttttLPage:n); 85. printf(t页号t块号t状态位ttt页号t块号t状态位n); 86. for(i=0;i=0;i-) 104. 105. printf(t%dt,i); 106. if(FMemoryi.page=-1) 107. printf( tt); 108. else 109. printf(%dtt,FMemoryi.page); 110. printf(tt%dt,i); 111. if(LMemoryi.page=-1) 112. printf(n); 113. else 114. printf(t%dn,LMemoryi.page); 115. 116. printf(Logical: %dn,Logical); 117. printf(Count: %d %dn,Pagenumber,Pageaddr); 118. printf(Physical: %dn,Physical); 119. printf(PageSize: %dn,PageSize); 120. printf(Visit: %dn,visit); 121. printf(FAbsent: %d LAbsent: %dn,FAbsent,LAbsent); 122. printf(FRate: %.2f% LRate: %.2f%n,(double)FAbsent*100/(double)visit,(double)LAbsent*100/(double)visit); 123. 124. 125. 126.void FIFO() /*FIFO算法*/ 127. 128. int i; 129. int m,n; 130. 131. 132. if(FPagePagenumber.stage=1) /*命中*/ 133. ; 134. else /*缺页*/ 135. 136. FAbsent+; 137. FPagePagenumber.stage=1; 138. 139. for(i=0;iMemsize;i+) 140. 141. if(FMemoryi.page=-1) 142. 143. for(m=1;m8;m+) 144. 145. for(n=0;n8;n+) 146. if(Gmn=0) 147. 148. break; 149. 150. if(n8) 151. break; 152. 153. Freemem=(m-1)*8+n; 154. FMemoryi.page=Pagenumber; 155. FPagePagenumber.kuai=Freemem; 156. 157. break; 158. 159. 160. if(i=Memsize) 161. 162. FPagePagenumber.kuai=FPageFMemory0.page.kuai; 163. FPageFMemory0.page.kuai=-1; 164. FPageFMemory0.page.stage=0; 165. for(i=0;iMemsize-1;i+) 166. FMemoryi.page=FMemoryi+1.page; 167. FMemoryi.page=Pagenumber; 168. 169. 170. 171. 172.void LRU() /*LRU算法*/ 173. 174. int i,j,m,n,l; 175. 176. /bool flag=true; 177. 178. for(l=0;lMemsize;l+) 179. if(LMemoryl.page=-1) 180. break; 181. 182. if(LPagePagenumber.stage=1)/*命中*/ 183. 184. for(i=0;il;i+) 185. 186. if(LMemoryi.page=Pagenumber) 187. 188. for(j=i;jl-1;j+) 189. 190. LMemoryj.page=LMemoryj+1.page; 191. 192. LMemoryj.page=Pagenumber; 193. break; 194. 195. 196. 197. else /*没命中*/ 198. 199. LAbsent+; 200. LPagePagenumber.stage=1; 201. 202. if(lMemsize) /问题出在这里,l+之前需要判断一下 如果lmemsize说明有空闲块，则l+ ,否则块已经满了,l不能+ . 203. l+; 204. for(i=0;il;i+) 205. 206. if(LMemoryi.page=-1) 207. 208. for(m=1;m8;m+) 209. 210. for(n=0;n8;n+) 211. if(Gmn=0) 212. 213. Gmn=1; 214. break; 215. 216. if(n8) 217. break; 218. 219. Freemem=(m-1)*8+n; 220. LMemoryi.page=Pagenumber; 221. LPagePagenumber.kuai=Freemem; 222. for(j=i;jl-1;j+) 223. 224. LMemoryj.page=LMemoryj+1.page; 225. 226. LMemoryj.page=Pagenumber; 227. break; 228. 229. 230. if(i=l) 231. 232. LPageLMemory0.page.stage=0; 233. LPagePagenumber.kuai=LPageLMemory0.page.kuai; 234. LPageLMemory0.page.kuai=-1; 235. for(j=0;j=0;i-) 247. 248. if(OMemoryi.page=-1) 249. printf( ); 250. else 251. printf( %d,OMemoryi.page); 252. 253. printf(n); 254. 255. 256.void OPT() 257. 258. printf(nOPTMemory：n); 259. printf(t 2 1 0nn); 260. int i,j,k,l,m,n; 261. int count=0; 262. for(i=0;ioth;i+) 263. 264. for(j=0;jMemsize;j+) 265. 266. if(OMemoryj.page=opti) 267. break; 268. 269. if(jMemsize) 270. ; 271. else 272. 273. for(j=0;jMemsize;j+) 274. 275. if(OMemoryj.page=-1) /*如果此时内存没满还有空缺 就直接将页号写进去*/ 276. 277. OMemoryj.page=opti; 278. break; 279. 280. 281. if(j=Memsize) /*需要发生置换*/ 282. 283. OAbsent+; 284. for(n=0;nMemsize;n+) 285. tempn=0; 286. 287. for(k=i+1;koth;k+) 288. 289. for(l=0;lMemsize;l+) 290. 291. if(OMemoryl.page=optk) 292. 293. templ+; 294. break; 295. 296. 297. count=0; 298. for(m=0;m1&koth-1) 304. ; 305. else 306. 307. for(m=0;m=PageLength) 340. 341. printf(越界中断.!n); 342. continue; 343. 344. optoth+=Pagenumber; 345. GShow(); 346. FIFO(); 347. LRU(); 348. 349. Physical=Freemem*PageSize*1024+Pageaddr; 350