#define TRUE 1
#define FALSE 0
#define INVALID -1
#define NULL 0

#define NUMBER_OF_INSTRUCTION 320  //指令流的指令條數(shù)
#define NUMBER_OF_VP 32            //進程的虛頁頁數(shù)

#define LINEAR_ADDRESS
       
typedef struct
{
    int no_of_vp;            //虛擬頁號
    int no_of_pp;            //物理頁號
    int counter_in_period;   //一周期內(nèi)訪問的次數(shù)
    int time;               //訪問時間
}vp_struct;    //頁面類型

vp_struct vp_array[NUMBER_OF_VP];        //頁面結(jié)構(gòu)數(shù)組

struct pp_struct           //物理頁面結(jié)構(gòu)
{
    int no_of_vp;
    int no_of_pp;
    struct pp_struct *next;
};

typedef struct pp_struct pp_type;
pp_type pp_control[NUMBER_OF_VP],*free_pp_head,*busy_pp_head,*busy_pp_tail;

int counter_page_default;
int address_of_instruction[NUMBER_OF_INSTRUCTION];

int page_of_instruction[NUMBER_OF_INSTRUCTION],offset_of_instruction[NUMBER_OF_INSTRUCTION];

int MAXINT=((1<<30)-1)*2+1; //2^31-1 2147483647
       
void initialize(int);

void FIFO(int);  //先進先出
void LRU(int);   //最近最久未使用頁面淘汰算法（least recently used）

int main()
{
	int S,i;
	srand( (int)getpid() ); 
  S=(int)rand() % 320;
  for(i=0;i<NUMBER_OF_INSTRUCTION;i+=1)  /*產(chǎn)生指令隊列*/
	{
		address_of_instruction[i]=S;                               /*任選一指令訪問點*/
		address_of_instruction[i+1]=address_of_instruction[i]+1;   /*順序執(zhí)行一條指令*/
		address_of_instruction[i+2]=(int)rand()%320;               /*執(zhí)行前地址指令m'*/
		address_of_instruction[i+3]=address_of_instruction[i+2]+1; /*執(zhí)行后地址指令*/
		S=(int)rand()%320;
	}

	for(i=0;i<NUMBER_OF_INSTRUCTION;i++)               /*將指令序列變換成頁地址流*/
	{       
		page_of_instruction[i]=address_of_instruction[i]/10;
		offset_of_instruction[i]=address_of_instruction[i]%10;
	}
	
	for(i=4;i<=32;i++)                        /*用戶內(nèi)存工作區(qū)從4個頁面到32個頁面*/
	{
		printf("%2d 物理塊：",i);
		FIFO(i);
		LRU(i);
		printf("\n");
	}
	
	return 0;
}


void FIFO(int total_pf)
{
    int i,j;
    pp_type *p,*t;
    initialize(total_pf);
    busy_pp_head=busy_pp_tail=NULL;
    for(i=0;i<NUMBER_OF_INSTRUCTION;i++)
    {
    if(vp_array[page_of_instruction[i]].no_of_pp==INVALID)
    {
        counter_page_default+=1;
        if(free_pp_head==NULL)
        {
			p=busy_pp_head->next;
			vp_array[busy_pp_head->no_of_vp].no_of_pp=INVALID;
			free_pp_head=busy_pp_head;
			free_pp_head->next=NULL;
			busy_pp_head=p;
        }
        p=free_pp_head->next;
        free_pp_head->next=NULL;
        free_pp_head->no_of_vp=page_of_instruction[i];
        vp_array[page_of_instruction[i]].no_of_pp=free_pp_head->no_of_pp;
        if(busy_pp_tail==NULL)
			busy_pp_head=busy_pp_tail=free_pp_head;
        else
        {
            busy_pp_tail->next=free_pp_head;
            busy_pp_tail=free_pp_head;
        }
        free_pp_head=p;      
    }
    }
    printf("FIFO缺頁率：%6.4f     ",1-(float)counter_page_default/320);
    return;
}

void LRU(int total_pf)
{
    int min,minj,i,j,present_time;//訪問時刻
    initialize(total_pf);
    present_time=0;
    for(i=0;i<NUMBER_OF_INSTRUCTION;i++)
    {
    if(vp_array[page_of_instruction[i]].no_of_pp==INVALID)
    {
        counter_page_default++;
        if(free_pp_head==NULL)  //無空閑頁面
        {
        min=MAXINT;
        for(j=0;j<NUMBER_OF_VP;j++)
            if(min>vp_array[j].time&&vp_array[j].no_of_pp!=INVALID)
            {
                 min=vp_array[j].time;minj=j;
            }
        free_pp_head=&pp_control[vp_array[minj].no_of_pp];
        vp_array[minj].no_of_pp=INVALID;
        vp_array[minj].time=-1;
        free_pp_head->next=NULL;
        }
        vp_array[page_of_instruction[i]].no_of_pp=free_pp_head->no_of_pp;
        vp_array[page_of_instruction[i]].time=present_time;
        free_pp_head=free_pp_head->next;
    } 
    else
        vp_array[page_of_instruction[i]].time=present_time;// 使用
    
    present_time++;
    }
    printf("LRU缺頁率：%6.4f     ",1-(float)counter_page_default/320);
    return ;
}


void initialize(int total_pf)
{
    int i;
    counter_page_default=0;
    for(i=0;i<NUMBER_OF_VP;i++)
    {
		vp_array[i].no_of_vp=i;
		vp_array[i].no_of_pp=INVALID;
		vp_array[i].counter_in_period=0;
		vp_array[i].time=-1;
    }
    for(i=1;i<total_pf;i++)
    {
		pp_control[i-1].next=&pp_control[i];  //建立pp_control[i-1]和ptf[i]之間的鏈接
		pp_control[i-1].no_of_pp=i-1;
    }
    pp_control[total_pf-1].next=NULL;
    pp_control[total_pf-1].no_of_pp=total_pf-1;
    free_pp_head=&pp_control[0];
    return;
}