Demo entry 6688142

tanxy

   

Submitted by anonymous on Jan 02, 2018 at 04:48
Language: C. Code size: 4.4 kB.

//
//  paging_emulator.c
//  
//
//  Created by Jianwei Liao on 11/30/12.
//  Copyright (c) 2012 Southwest University. All rights reserved.
//

#include <stdlib.h>
#include <stdio.h>

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

 
#define INSTRUCT_CNT 320         	/* length of instruction stream */
#define VIRTUAL_PAGE_LEN 32        	/* length of virtual page */

typedef struct{
	int pn,			/* page number */
		pfn;		/* page frame number */
}page_struct_type;

page_struct_type page_array[VIRTUAL_PAGE_LEN];                 /* page struct array */

struct pf_ctl_struct{                   	/* page frame control struct */
	int pn,			/* page number */
		pfn;		/* page frame number */
	struct pf_ctl_struct *next;		/* to next */
};

/* used for paging replacement, such as free page frame list or busy page frame list */
typedef struct pf_ctl_struct pf_ctl_t;
pf_ctl_t pfc[VIRTUAL_PAGE_LEN],
		 *freepf_head,    	/* head of free page frame list */
		 *busypf_head,		/* head of busy page frame list */
		 *busypf_tail;		/* tail of busy page frame list */

int page_fault_cnt;			/* number of page fault */
int	a[INSTRUCT_CNT];		/* the instruction list, which contains the logical address */
int page[INSTRUCT_CNT];		/* page number, the instruction<> */

void initialize(int total_page_frame); 
void FIFO(int total_page_frame) ; 


int main(void){

	/* generate the instruction stream randomly */
	int S,i;
	srand(10*37);               
	S=(float) ((INSTRUCT_CNT-1)*rand()/(RAND_MAX+1.0));  //FLOAT 
	printf("%2d RAND_MAX\n",RAND_MAX);
	for (i=0;i<INSTRUCT_CNT;i+=4){
		a[i]=S;                                     
		a[i+1]=a[i]+1;                              
		a[i+2]=(float)a[i]*rand()/RAND_MAX;              
		a[i+3]=a[i+2]+1;                            
		S=(float)rand()*(INSTRUCT_CNT -2 -a[i+2])/RAND_MAX+a[i+2]+2;
		//printf("%d		", a[i]);
	}
	printf("\n页面访问序列:\n\n");
	
	 /* change the instruction sequence to page address stream */
	 
	for (i=0;i<INSTRUCT_CNT;i++){
		printf("%d\t", a[i]);
		page[i]=a[i]/10;
	}

	 /* use memory page frames from 4 pages to 32 pages */
	 printf("\n\nFIFO页面置换算法:\n\n");

	for (i=4;i<=32;i++){
		printf("%2d page frames ",i);
		FIFO(i);
		printf("缺页次数:%4d 缺页率:%9f",page_fault_cnt,(float)(page_fault_cnt)/320);
		printf("\n");
	}
	return 0;
}


void FIFO(int total_page_frame)                                 /*FIFO ALGORITHM*/
{
	int i;
	pf_ctl_t *p;
	page_fault_cnt = 0;
	

	 /* initialize the associated page control struct */
	initialize(total_page_frame);
     
	/* busy page frame head, busy page frame tail */                     	
	busypf_head=busypf_tail=NULL; 
	p = busypf_head;//保存busypf头结点,用p来代替busypf_head
	int sum = 0;//记录已经用了多少页框     
	/* I leave it to you*/
	for (i = 0; i <=319;++i)
	{
		if (page_array[page[i]].pfn == INVALID &&sum<total_page_frame) //如果当前页不在内存,还有空闲页框,就调入
			{
				++page_fault_cnt ;
				++sum;
				page_array[page[i]].pfn = 1;
				freepf_head->pn = page[i];
		
				if (busypf_head == NULL)
				{
				p = busypf_head = busypf_tail = freepf_head;
				freepf_head = freepf_head->next;
				}
				else
				{
				p->next = freepf_head;
				p = p->next;
				busypf_tail->next = freepf_head;
				busypf_tail = busypf_tail->next;
				freepf_head = freepf_head->next;
				}
			}
		else if (page_array[page[i]].pfn == INVALID && sum>=total_page_frame) //如果当前页不在内存,没有空闲页框,就置换
			{
				++page_fault_cnt;
				++sum;
				page_array[busypf_head->pn].pfn = INVALID;
				page_array[page[i]].pfn = 1;
				busypf_head->pn = page[i];
				busypf_tail->next=busypf_head;
				busypf_tail = busypf_tail->next;
				busypf_head = busypf_head->next;
			}
	}
}


 /* initialize the associated page control struct */
void initialize(int total_page_frame)             
{
	int i;
	page_fault_cnt=0;

	for(i=0;i<VIRTUAL_PAGE_LEN;i++){
		page_array[i].pn=i;
		/* INVALID shows the page is not in the memory */
		page_array[i].pfn=INVALID;              	
	}

	for(i=1;i<total_page_frame;i++){       
		/* set link between pfc[i-1] and pfc[i] */
		pfc[i-1].next=&pfc[i];
		pfc[i-1].pfn=i-1;
	}
	/* page frame control */
	pfc[total_page_frame-1].next=NULL;
	pfc[total_page_frame-1].pfn=total_page_frame-1;
	 /* the head pointer of free page array is pfc[0] */
	freepf_head=&pfc[0];              
}

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).