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",instructions.page_num,instructions.address);

    printf("block_num,page_num\\n");

    do{

     printf(" %2d %10d\\n",p->block_num,p->page_num);

     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",address);

}

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

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        if(Find_page_in_block(instructions[i],p)){

            display(instructions[i]);

            show_physical_address(p,instructions[i]);

            getchar();

            continue;

        }

     else if(blockSize            diseffect++;

            loadpage(instructions[i]);

            display(instructions[i]);

        }

        else {

            diseffect++;

            replace_page(instructions[i],p);

            display(instructions[i]);

            show_physical_address(p,instructions[i]);

        }

        getchar();

    }    

    printf("NRU %f\\n",(float)diseffect/size);

    getchar();getchar();getchar();

}