clock.cpp

大学计算机操作系统课程设计

// FIFO.cpp : Defines the entry point for the application.
//

#include"StdAfx.h"
#include<stdio.h>
#include <time.h>
#include <stdlib.h>
#define M 3      //内存物理块数
#define N 20     //虚拟内存尺寸


int P;    //工作集的起始位置
int nin;  //记录缺页次数


//用于CLOCK算法的页面定义
typedef struct page_clock
{
       int num; 
       int visit;   
}Page_clock;  

//用于改进的CLOCK算法的页面定义
typedef struct page
{
       int num;      //页面号
       int visit;    //是否访问
	   int modify;   //是否修改
}Page;                

Page_clock b_clock[M]; //内存单元数 Clock
Page b[M];            //updating_clock
int opt[M];           //opt
int ran[M];           //random replacement
int fifo[M];          //FIFO
int c[M][N];          //存储每个阶段状态

//访问序列随机生成e个，e是工作集中包含的页数，m是工作集移动率
void generate_list(int *list, int e, int m, int t)
{
	int i, j = 0, q =P, r;
	srand((unsigned)time(NULL));
	while (j < e)
	{
		for (i = j;i < j + m;i++)
		{
			if (i == e)
				break;
			list[i] = (q + rand() % e) % N;   /*保证在虚拟内存的页号内*/
		}
		j = i;
		r = rand() % 100;
		if (r < t)
			q = rand() % N;
		else
			q = (q + 1) % N;
	}
}

//随机生产是否被修改的情况，prop(0...100)，prop/100的概率未被修改
void generate_modify(int *mo, int e, int prop)
{
	int i, t;

	for (i = 0;i < e;i++)
	{
		t = rand() % 100;
		if (t > prop)
			mo[i] = 0;
		else
			mo[i] = 1;
	}
}

//格式输出
void print_format(int e)
{
	int i;
	printf("  ");
	for (i = 1;i < e;i++)
		printf("    ");
	printf(" \n");
}





//结果输出
void print(int e,int *a)
{
	
	int j, i;
	print_format(e);
	for(j = 0;j < e;j++)
	{
		printf(" %2d ",a[j]); //读入内存顺序
	}
	printf(" \n");
	printf("置换过程：");
	print_format(e);
	for(i = 0;i < M;i++)
    { 
		for(j = 0;j < e;j++)
		{
			if(c[i][j] == -1)
				printf("  %c ",' ');
			else
				printf(" %2d ",c[i][j]);
			
		}
		printf(" \n");
	}
	print_format(e);
}



//Clock算法初始化
void Init_Clock(Page_clock *b_clock)
{
	nin = 0;
	int i, j;
	for(i = 0;i < M;i++)
    {
		b_clock[i].num = -1;
		b_clock[i].visit = 0; 
	}
	for(i = 0;i < M;i++)
	   {
		for(j = 0;j < N;j++)
		{
			c[i][j] = -1;
		}	  
	}
}

//改进的Clock算法初始化
void Init_updatingClock(Page *b)
{
	nin = 0;
	int i, j;
	for(i = 0;i < M;i++)
    {
		b[i].num = -1;
		b[i].visit = 0; 
		b[i].modify = 0;
	}
	for(i = 0;i < M;i++)
	{
		for(j = 0;j < N;j++)
		{
			c[i][j] = -1;
		}	  
	}
}

//Clock算法
void Clock(int fold,Page_clock *b_clock)
{
	int i, val = -1, p = 0; //p为查询指针
	for (i = 0;i < M;i++)
	{
		if (fold == b_clock[i].num)
			val = i;
	}
	//页面在内存中
	if (val >= 0)
	{
		b_clock[val].visit = 1;
		for(i = 0;i < M;i++)
		{
			if (i != val)
			{
				b_clock[i].visit = 0;
			}
		}
	}
	else
	{
		nin++;
		//初始化内存
		for (i = 0;i < M;i++)
		{
			if (b_clock[i].num == -1)
			{
				val = i;
				break;
			}
		}
		while (val < 0)
		{
			if (b_clock[p].visit == 0)
				val = p;
			else
				b_clock[p].visit = 0;
			p = (p + 1) % M;
		}
		b_clock[val].num = fold;
		b_clock[val].visit = 1;
		for(i = 0;i < M;i++)
		{
			if (i != val)
			{
				b_clock[i].visit = 0;
			}
		}
	}
}

//改进的Clock算法
void Updating_Clock(int fold,int modiff, Page *b)
{      int i, p = -1; //p是查询指针
       int val = -1;

	   //找是否在内存中
	   for(i = 0;i < M;i++)
       {
              if (fold == b[i].num)
                     val = i;
       }
       
       if (val >= 0)
       {
		   b[val].visit = 1; //被访问
		   b[val].modify = modiff;
           for(i = 0;i < M;i++)
		   {
			   if (i != val)
			   {
				   b[i].visit = 0;
			   }
		   }
       }
       else
       {
		   nin++;
		   //初始化内存
		   for (i = 0;i < M;i++)
		   {
			   if (b[i].num == -1)
			   {
				   val = i;
				   break;
			   }
		   }
		   while (val < 0)
		   {
			   //第一步扫描
			   for (i = 0;i < M;i++)
			   {
				   p = (p + 1) % M;
				   if ((b[p].modify == 0) && (b[p].visit == 0))
				   {
					   val = p;
					   break;
				   }
			   }
			   //第二步扫描
			   if (val < 0)
			   {
				   for (i = 0;i < M;i++)
				   {
					   p = (p + 1) % M;
					   if ((b[p].modify == 1) && (b[p].visit == 0))
					   {
						   val = p;
						   break;
					   }
					   else
					   {
						   b[p].visit = 0;
					   }
				   }
			   }
		   }
		
		   //找到后，其他设置为未访问
		   b[val].num = fold;
		   b[val].modify = modiff;
		   b[val].visit = 1;
		   for(i = 0;i < M;i++)
		   {
			   if (i != val)
			   {
				   b[i].visit = 0;
			   }
		   }
       }
}

//主程序
void main()
{
       int a[N];
	   int mo[N];
       int i,j;
       
	   //产生随机访问串及是否修改串
	   P = 1;
	   int e, m, prop, t;
	   printf("请输入工作集中包含的页数e和工作集移动率m:\n");
	   scanf("%d %d",&e,&m);
	   t = 50;
	   generate_list(a, e, m, t);
	   printf("请输入页面被修改的概率(*100):\n");
	   scanf("%d",&prop);
	   generate_modify(mo, e, prop);

       //Clock算法实现
	   Init_Clock(b_clock);
	   for(i = 0;i < e;i++)
       {
		   Clock(a[i],b_clock);
		   for(j = 0;j < M;j++)
		   {
			   c[j][i] = b_clock[j].num;
		   }

       }
	   printf("Clock算法的内存状态为：\n");
	   print(e, a);
	   nin = nin - M;
	   printf("缺页次数为：%d\n缺页率：%.2f\n",nin,nin * 1.0 / e);
	   printf("\n");

	   //改进的Clock算法实现
	   Init_updatingClock(b);
	   for(i = 0;i < e;i++)
       {
		   Updating_Clock(a[i], mo[i], b);
		   for(j = 0;j < M;j++)
		   {
			   c[j][i] = b[j].num;
		   }
       }
	   printf("改进的Clock算法的内存状态为：\n");
	   print(e, a);
	   for(j = 0;j < e;j++)
	   {
		   printf(" %2d ",mo[j]); //是否修改序列串
	   }
	   printf(" \n");
	   print_format(e);
	   nin = nin - M;
	   printf("缺页次数为：%d\n缺页率：%.2f\n",nin,nin * 1.0 / e);
	   printf("\n");
}