FIFO页面置换算法

1）假设每个页面中可存放10条指令，分配给作业的内存块数为4。

2）用C语言模拟一个作业的执行过程，该作业共有320条指令，即它的地址空间为32页，目前它的所有页都还未调入内存。在模拟过程中，如果所访问的指令已在内存，则显示其物理地址，并转下一条指令。如果所访问的指令还未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。如果4个内存块均已装入该作业，则需进行页面置换，最后显示其物理地址，并转下一条指令。 在所有320指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。 3）置换算法：先进先出FIFO算法。

#include #include #include #define N 4 #define size 320

typedef struct Block{ int block_num; //块号 int page_num; //页号 struct Block *next; }BLOCK,*BLOCKLIST;

typedef struct instruct{ //指令数据结构 int address; //指令地址 int page_num; //指令所存的页号 }INSTRUCTION,*INSTRUCTIONLIST;

INSTRUCTION instructions[size]; //定义320条指令

BLOCKLIST block_head,front_in; //block_head指向块链表的头，front_in指向最老的页面，即被淘汰的页面

int diseffect=0; //缺页次数 int blockSize=0; //标记块是否满 //初始化指令

void Init_Instructions() { for(int i=0;i<320;i++) instructions[i].address=rand()%320; for(int k=0;k<320;k++) instructions[k].page_num=(int)instructions[k].address/10; }

//初始化块 （循环链表） BLOCKLIST Init_block() {

BLOCKLIST head=(BLOCKLIST)malloc(sizeof(BLOCK)) ; BLOCKLIST p; for(int i=1;i<=N;i++) { if(i==1) p=head; else { p->next=(BLOCKLIST)malloc(sizeof(BLOCK)); p=p->next; } p->block_num=i; p->page_num=-1; } p->next=head; return head; }

//显示块内的数据

void display(INSTRUCTION instructions) { BLOCKLIST p=block_head; printf(\"The new page: (page_num==%d),

(address==%d)\\n\ printf(\"block_num,page_num\\n\"); do{ printf(\" %2d %10d\\n\ 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; printf(\"%d\\n\\n\}

//查找该页是否存在，存在不要置换，否则置换

int Find_page_in_block(INSTRUCTION instructions,BLOCKLIST &p) { p=block_head; do{ if(p->page_num==instructions.page_num) return 1; p=p->next; }while(p!=block_head); return 0; }

//用于将四个块填满

void loadpage(INSTRUCTION instructions) { BLOCKLIST p; p=block_head; while(p->page_num!=-1) p=p->next; p->page_num=instructions.page_num; blockSize++; }

//按FIFO置换页面

void replace_page(INSTRUCTION instructions,BLOCKLIST &p) { front_in->page_num=instructions.page_num; p=front_in; front_in=front_in->next; }

void main() { BLOCKLIST p; Init_Instructions(); block_head=Init_block(); front_in=block_head; for(int i=0;i}