《nur页面置换算法》由会员分享,可在线阅读,更多相关《nur页面置换算法(5页珍藏版)》请在金锄头文库上搜索。
1、NRU页面置换算法1)假设每个页面中可存放10条指令,分配给作业的内存块数为4。2)用C语言模拟一个作业的执行过程,该作业共有320条指令,即它的地址空间为32页,目前它的所有页都还未调入内存。在模拟过程中,如果所访问的指令已在内存,则显示其物理地址,并转下一条指令。如果所访问的指令还未装入内存,则发生缺页,此时需记录缺页的次数,并将相应页调入内存。如果4个内存块均已装入该作业,则需进行页面置换,最后显示其物理地址,并转下一条指令。在所有320指令执行完毕后,请计算并显示作业运行过程中发生的缺页率。3)置换算法:最近最不经常使用(NRU)算法。#include#include#include#
2、define N 4#define size 320typedef struct Pageint page_num;int flag_A; /访问位int flag_M; /修改位int read_or_write; /0表示不被修改,1表示被修改PAGE;typedef struct Blockint block_num; /块号PAGE page; /所装页的信息struct Block *next;BLOCK,*BLOCKLIST;typedef struct instruct /指令数据结构int address; /指令地址PAGE page; /对应页的信息INSTRUCTION,
3、*INSTRUCTIONLIST;INSTRUCTION instructionssize;/定义320个指令BLOCKLIST block_head; /块的头指针int diseffect=0; /缺页次数int blockSize=0;void Init_Instructions()for(int i=0;i320;i+)instructionsi.address=rand()%320;for(int k=0;k320;k+)instructionsk.page.page_num=(int)instructionsk.address/10;instructionsk.page.flag_
4、A=0;instructionsk.page.read_or_write=rand()%2;if(instructionsk.page.read_or_write=0)instructionsk.page.flag_M=0;else instructionsk.page.flag_M=1;BLOCKLIST Init_block()BLOCKLIST head=(BLOCKLIST)malloc(sizeof(BLOCK) ;BLOCKLIST p;for(int i=1;inext=(BLOCKLIST)malloc(sizeof(BLOCK);p=p-next;p-block_num=i;
5、p-page.page_num=-1;p-page.flag_A=0;p-page.flag_M=0;p-next=head;return head;void display(INSTRUCTION instructions)BLOCKLIST p=block_head;printf(The new page: (page_num=%d), (flag_M=%d), (address=%d)n,instructions.page.page_num,instructions.page.flag_M,instructions.address);printf(block_num,page_num,f
6、lag_A,flag_Mn);doprintf( %2d %10d%9d%8dn,p-block_num,p-page.page_num,p-page.flag_A,p-page.flag_M);p=p-next;while(p!=block_head);void show_physical_address(BLOCKLIST &p,INSTRUCTION instructions)int address;printf(physical address:);address=p-block_num*1024+instructions.address%10;/页面大小为1kprintf(%dnn,
7、address);/查找四个块中是否有此页面int Find_page_in_block(INSTRUCTION instructions,BLOCKLIST &p)p=block_head;doif(p-page.page_num=instructions.page.page_num)p-page.flag_A=1;if(p-page.flag_M=0)p-page.flag_M=instructions.page.flag_M;return 1;p=p-next;while(p!=block_head);return 0;/先将四个块中装满void loadpage(PAGE page)B
8、LOCKLIST p;p=block_head;while(p-page.page_num!=-1)p=p-next;p-page.page_num=page.page_num;p-page.flag_A=1;p-page.flag_M=page.flag_M;blockSize+;/第一次循环扫描 A=0 M=0int cscanf1(BLOCKLIST &p)p=block_head;doif(p-page.flag_A=0 & p-page.flag_M=0)return 1;p=p-next;while(p!=block_head);return 0;/第二次循环扫描 A=0 M=1i
9、nt cscanf2(BLOCKLIST &p)p=block_head;do /把扫面过后的A=1,M=0 或A=1,M=1中的A置0if(p-page.flag_A=1 & (p-page.flag_M=0 | p-page.flag_M=1)p-page.flag_A=0;p=p-next;continue;if(p-page.flag_A=0 & p-page.flag_M=1)return 1;p=p-next;while(p!=block_head);return 0;/第三次扫描将所有的A置为0int cscanf3(BLOCKLIST &p)p=block_head;dop-p
10、age.flag_A=0;p=p-next;while(p!=block_head);return 1;/用于换进页面void assignment(BLOCKLIST &p,INSTRUCTION instructions)p-page.page_num=instructions.page.page_num;p-page.flag_A=1;p-page.flag_M=instructions.page.flag_M;/NRU页面替换算法void replace_page(INSTRUCTION instructions,BLOCKLIST &p)if(cscanf1(p)assignment
11、(p,instructions);else if(cscanf2(p)assignment(p,instructions);else if(cscanf3(p)if(cscanf1(p)assignment(p,instructions);else cscanf2(p);assignment(p,instructions);void main()BLOCKLIST p;Init_Instructions();block_head=Init_block();for(int i=0;isize;i+) if(Find_page_in_block(instructionsi,p)display(instructionsi);show_physical_address(p,instructionsi);getchar();continue;else if(blockSize4)show_physical_address(p,instructionsi);getchar();printf(NRU %fn,(float)diseffect/size);getchar();getchar();getchar();