page.c

虚拟内存分配、回收和内外存交换的算法

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

struct PAGE   
{
	int pn;   //逻辑页号
	int pfn;  //内存页号
	int count;//计数器
	int flag; //中断位
};//页表项结构

struct THRLIST               
{
	pthread_t id;              //线程id
	struct PAGE pagelist[500]; //线程对应的页表
};//线程链

struct THRLIST thrlist[10];//规定有十个线程运行

typedef struct pagetext
{
	pthread_t id;   //线程id
	int pn;         //逻辑页号
	int pfn;        //内存页号
	char text[1008];//程序和数据段
	struct pagetext *next;
}TEXT;//页面结构(1K)

TEXT list[1024];  //模拟内存

TEXT vlist[10240];//交换区

TEXT *freehead;   //空闲页面链头指针

pthread_mutex_t m1,m2,m3;//m1用于内存分配互斥，m2用于外存分配互斥，m3用于打印互斥

void initialize()  //初始化
{
	int i;
	FILE *fp;
	if((fp=fopen("swap.txt","w"))==NULL)
	{
		printf("Cannot open swap.txt for write!\n");
		return;
	}
	for(i=1;i<1024;i++)  //初始化内存页面
	{
		list[i-1].id=-1;
		list[i-1].pfn=i-1;
		list[i-1].next=&list[i];
	}
	list[i-1].id=-1;
	list[i-1].pfn=i-1;
	list[i-1].next=NULL;
	freehead=&list[0];
	for(i=1;i<10240;i++)  //初始化交换区页面
	{
		vlist[i-1].id=-1;
		vlist[i-1].pn=i-1;
		vlist[i-1].next=&vlist[i];
	}
	vlist[i-1].id=-1;
	vlist[i-1].pn=i-1;
	vlist[i-1].next=NULL;
	for(i=0;i<10240;i++)
		fwrite(&vlist[i],sizeof(TEXT),1,fp);
	return;
}

void print()  //输出
{
	int j,thr,left=1024,takeup=0;
	pthread_mutex_lock(&m3);
	printf("\n***************************************\n");
	printf("     id                 space\n");
	for(thr=0;thr<10;thr++)
	{
		if(thrlist[thr].id!=-1)
		{
			for(j=0;j<500;j++)
				if(list[j].id==thrlist[thr].id)
					takeup++;
			printf("\n    %d                 %d\n",thrlist[thr].id,takeup);
		}
		left-=takeup;
		takeup=0;
	}
	printf("\n   space left:             %d\n",left);
	printf("\n***************************************\n");
	pthread_mutex_unlock(&m3);
	return;
}

void distribute(int need,int thr)  //为线程分配磁盘空间
{
	int i,j;
	FILE *fp;
	if((fp=fopen("swap.txt","w"))==NULL)
	{
		printf("cannot open file!\n");
		return;
	}
	for(i=0;i<need;i++)  //初始化页表
	{
		thrlist[thr].pagelist[i].count=0;  //计数器清零
		thrlist[thr].pagelist[i].flag=-1;  //中断位置空
	}
	while(1)
	{
		for(i=0;i<10240;i++)
			if(vlist[i].id==-1)
				j++;  //统计空闲页面数
		if(j<need)  //不够则等待 
			sleep(1);
		else
			break;
	}
	pthread_mutex_lock(&m2);
	for(i=0,j=0;i<10240,j<need;i++)
	{
		if(vlist[i].id==-1)
		{
			thrlist[thr].pagelist[j].pn=i;  //改写页表
			j++;
			vlist[i].id=thrlist[thr].id;  //分配磁盘空间
			fseek(fp,i*sizeof(TEXT),0);
			fwrite(&vlist[i],sizeof(TEXT),1,fp);  //写回 
		}
	}
	pthread_mutex_unlock(&m2);
	return;
}

void in(int want,int thr)  //换入
{
	freehead->id=thrlist[thr].id;
	freehead->pn=thrlist[thr].pagelist[want].pn;
	thrlist[thr].pagelist[want].pfn=freehead->pfn;
	thrlist[thr].pagelist[want].flag=1;
	freehead=freehead->next;
	return;
}

void LFU(int *want,int need,int thr)  //LFU页面替换算法
{
	int i,j,min,minpage;
	pthread_mutex_lock(&m1);
	for(i=0,j=0;i<1024,j<100;i++)  //采用固定驻留集(100)
	{
		if(thrlist[thr].pagelist[want[i]].flag==-1)
		{
			in(want[i],thr);  //调入缺少的页面
			j++;
			print();  //输出已用内存页面数和剩余内存页面数
			sleep(1);  //便于察看输出结果
		}
		else
			thrlist[thr].pagelist[want[i]].count++;
	}
	pthread_mutex_unlock(&m1);
	if(i<1024)  //采用局部替换算法
	{
		for(;i<1024;i++)
		{
			if(thrlist[thr].pagelist[want[i]].flag==-1)
			{
				min=32767;
				for(j=0;j<need;j++)
				{
					if(min>thrlist[thr].pagelist[j].count&&thrlist[thr].pagelist[j].flag!=-1)
					{
						min=thrlist[thr].pagelist[j].count;
						minpage=j;
					}
					thrlist[thr].pagelist[j].count=0;  //计数器清零
				}
				thrlist[thr].pagelist[minpage].flag=-1;  //换出内存(改写中断位)
				list[thrlist[thr].pagelist[minpage].pfn].pn=thrlist[thr].pagelist[want[i]].pn;//换入内存
				thrlist[thr].pagelist[want[i]].flag=1;  //改写中断位
			}
			else
				thrlist[thr].pagelist[want[i]].count++;
		}
	}
}

void run(int need,int thr)  //线程模拟运行函数
{
	int i,want[1024];
	for(i=0;i<1024;i++)  //随机产生需要的页面号
	{
		do
		{
			want[i]=rand()/327670;
		}while(want[i]<0||want[i]>=need);
	}
	LFU(want,need,thr);
	return;
}

void release(int need,int thr)  //释放磁盘与内存空间
{
	int i;
	FILE *fp;
	if((fp=fopen("swap.txt","w"))==NULL)
	{
		printf("Cannot open swap.txt for write!\n");
		return;
	}
	pthread_mutex_lock(&m1);
	for(i=0;i<need;i++)
	{
		if(thrlist[thr].pagelist[i].flag==1)
		{
			list[thrlist[thr].pagelist[i].pfn].id=-1;  //释放内存空间
			list[thrlist[thr].pagelist[i].pfn].next=freehead->next;
			freehead=&list[thrlist[thr].pagelist[i].pfn];  //挂入内存空闲页面链
		}
		vlist[thrlist[thr].pagelist[i].pn].id=-1;  //释放磁盘空间
		fseek(fp,thrlist[thr].pagelist[i].pn*sizeof(TEXT),0);
		fwrite(&vlist[thrlist[thr].pagelist[i].pn],sizeof(TEXT),1,fp);  //写回
	}
	printf("\nrelease %d\n",thr);
	print();
	sleep(1);
	pthread_mutex_unlock(&m1);
	return;
}

void *thread(void *thr)
{
	int need;
	do
	{
		need=rand()/327670;
	}while(need<50||need>500);
	initialize();               //初始化
	distribute(need,(int)thr);  //分配空间
	run(need,(int)thr);         //模拟运行
	release(need,(int)thr);     //释放空间
	pthread_exit(0);            //线程结束
}

main()
{
	int thr;
	pthread_mutex_init(&m1,NULL);
	pthread_mutex_init(&m2,NULL);
	pthread_mutex_init(&m3,NULL);  //初始化互斥锁
	for(thr=0;thr<10;thr++)
		pthread_create(&thrlist[thr].id,NULL,thread,(void *)thr);  //创建线程
	for(thr=0;thr<10;thr++)
		pthread_join(thrlist[thr].id,(void *)NULL);  //等待线程结束
	exit(0);
}