内存分块.c

包含操作系统原理书籍中所提到的很多方法的实现函数

/*采用存储分块表实现主存的分配与回收
  该程序是在图形模式下运行。运行时，不需要进行任何数据收入，只要按回车键，
  程序自动模拟主存的分配与回收
  */
#include <stdio.h>
#include <graphics.h>
#include <stdlib.h>
#include <conio.h>
#include <stdlib.h>
#include <math.h>

struct MemoryBlock    /*定义内存块的结构*/
{
	int BlockLength;    /*内存块的大小*/
	int Empty;   /*内存块是否为空*/
	int JobIndex; /*内存块存放的作业号*/
};
struct MemoryBlock MemBlock[20];  /*共有20个内存块*/
struct JCBInfo      /*作业控制块信息结构*/
{             
	char JobName[30];   /*作业名*/
	int JobIndex;     /*作业序号*/
	int JobLength;     /*作业大小*/
	int *JobPageTable; /*页表首地址*/
};
struct JCBInfo Jobs[5]=       /*定义5个作业*/
{
	{"Job", 1, 500, NULL},
	{"Job", 2, 480, NULL},
	{"Job", 3, 180, NULL},
	{"Job", 4, 690, NULL},
	{"Job", 5, 900 , NULL}
};
struct EmptyBlockInfo          /*空块的结构信息*/
{
	int BlockIndex;            /*空块在内存的序号*/
	struct EmptyBlockInfo *NextBlock;
};
struct EmptyBlockInfo *Head;      /*空块链表的头结点*/
int JobPageTable[5][7]=         /*指定了文件存放位置*/
{
	{0, 3, 5, 7, 8, -1,-1},
	{1, 2, 9, 13, 16,-1,-1},
	{4, 12, -1, -1, -1,-1, -1},
	{6, 10, 11, 14, 15, 17, 18}
};
void DrawMemory(void)              /*在屏幕上画出内存的使用情况*/
{

	int i, j, Tempx,  Maxy=480;
	for(i=0; i<=19; i++)
	{
		Tempx=10+i*30;
		if (MemBlock[i].Empty==0)   
		{
			j=MemBlock[i].JobIndex;
			switch(j)
			{
			case 1:
				setfillstyle(SOLID_FILL, GREEN);
				break;
			case 2:
				setfillstyle(SOLID_FILL, CYAN);
				break;
			case 3:
				setfillstyle(SOLID_FILL, RED);
				break;
			case 4:
				setfillstyle(SOLID_FILL, BROWN);
				break;
			case 5:
				setfillstyle(SOLID_FILL, YELLOW);
				break;
			}
			bar(Tempx, Maxy/9, Tempx+28, 2*Maxy/9);
		}
		else
		{
			setfillstyle(SOLID_FILL, WHITE);
			bar(Tempx, Maxy/9, Tempx+28, 2*Maxy/9);
		}
	}
}
void  DrawScreen (void)     /*分为两个区域，在屏幕上画出内存块*/
{
	int GraphDriver=DETECT, GraphMode, ErrorCode;
	int Maxx=640,  Maxy=480,  i,  Tempx;
	char TempString[3];
	initgraph(&GraphDriver, &GraphMode, "");
	cleardevice();
	setfillstyle (SOLID_FILL, BLUE);   /*分为两个区域*/
	bar(0,0, Maxx, Maxy/3);
	setfill_style(SOLID_FILL, RED);
	bar(0, Maxy/3+1, Maxx, Maxy);
	outtextxy(5,  15, "This is the figure of memory usage.");
	for(i=0; i<=19; i++) /*画出内存块*/
	{
		Tempx=10+i*30;
		setfillstyle(SOLID_FILL, WHITE);
	}
	cleardevice();
	setfillstyle(SOLID_FILL, BLUE);
	bar(0, 0, Maxx, Maxy/3);
	setfillstyle(SOLID_FILL, RED);
	bar(0, Maxy/3+1, Maxx, Maxy);
	outtextxy(5, 15, "This is the figure of memory usage.");
	for(i=0; i<=19; i++)
	{
		Tempx=10+i*30;
		setfillstyle(SOLID_FILL, WHITE);
		bar(Tempx, Maxy/9, Tempx+28, 2*Maxy/9);
		itoa(i+1, TempString, 10);
		outtextxy(Tempx, 110, TempString);
	}
}
void CloseScreen(void)     /*关闭图形模式*/
{
	closegraph();
	restorecrtmode();
}
void InitMemoryBlock(void) /*初始化内存*/
{
	int i;
	for(i=0; i<=19; i++)
	{
		MemBlock[i].BlockLength=100; /*内存的大小*/
		MemBlock[i].Empty=1;         /*内存为空*/
		MemBlock[i].JobIndex=0;       /*无作业*/
	}
}
void JobMessage(void)              /*显示5个作业的信息*/
{
	int i;
	char TempInt[1], TempString[3];
	outtextxy(5, 215, "The are five jobs waiting for  dealting.");
	for(i=0; i<5; i++)
	{
		outtextxy(5, 225+i*10, "Job");
		itoa(i+1, TempInt, 10);
		outtextxy(30, 225+i*10, TempInt);
		outtextxy(36, 225+i*10, ":");
		itoa(Jobs[i].JobLength, TempString, 10);
		outtextxy(44, 225+i*10, TempString);
	}
	outtextxy(5, 285, "Press any key to continue...");
	getch();
}
void InitEmptyBlock(void)  /*建立空块链表并初始化*/
{
	struct EmptyBlockInfo *TempBlockInfo, *TempBlockInfo1=NULL;
	int i;
	Head=(struct EmptyBlockInfo *)malloc(sizeof(struct EmptyBlockInfo));
	Head->BlockIndex=20;  /*头节点的块号记录的是空块数*/
	TempBlockInfo1=Head;
	for(i=0; i<=19; i++)
	{
		TempBlockInfo=(struct EmptyBlockInfo *)malloc(
							sizeof(struct EmptyBlockInfo));
		
		TempBlockInfo->BlockIndex=i;
		TempBlockInfo->NextBlock=NULL;
		TempBlockInfo1->NextBlock=TempBlockInfo;
		TempBlockInfo1=TempBlockInfo;
		TempBlockInfo=NULL;
		/*
		if(i==0)
		{
			Head->NextBlock=TempBlockInfo;  //=Head;
		}
		while(TempBlockInfo!=NULL)
		{
			if((TempBlockInfo->NextBlock)->BlockIndex==i && i!=19)
			{
				TempBlockInfo1=TempBlockInfo->NextBlock;
				TempBlockInfo->NextBlock=TempBlockInfo1->NextBlock;
				free(TempBlockInfo1);
				break;
			}
			else if(TempBlockInfo->NextBlock->BlockIndex==i && i==19)
            {
				free(TempBlockInfo->NextBlock);
				TempBlockInfo->NextBlock=NULL;
                break;
			}
			TempBlockInfo=TempBlockInfo->NextBlock;
		}
		*/
	}
}

int ExistInEmptyBlock(int BlockIndex)  /*检测内存中该序列号的块是否被占用*/
{
	struct EmptyBlockInfo *Temp;
	Temp=Head->NextBlock;
	while(Temp!=NULL)
	{
		if(Temp->BlockIndex==BlockIndex)
			return 1;
		Temp=Temp->NextBlock;
	}
	return 0;

}

void DelInEmptyBlock(int BlockIndex)  /*从空闲块链表中删除该序列号的块*/
{
	struct EmptyBlockInfo *Temp1,*Temp2;
	Temp1=Head;
	Temp2=Temp1->NextBlock;
	while(Temp2!=NULL)
	{
		if(Temp2->BlockIndex==BlockIndex)
		{
			if(Temp2->NextBlock==NULL)
			{
				Temp1->NextBlock=NULL;
			}
			else
			{
				Temp1->NextBlock=Temp2->NextBlock;
			}
			free(Temp2);
			return ;
		}
		Temp1=Temp2;
		Temp2=Temp1->NextBlock;
	}
	return ;
}

void InputJobs(void)         /*输入并建立作业*/
{
	int i, j, BlockNum, GetEmptyBlock;
	for(i=0; i<=4; i++)
	{
		BlockNum=(int)ceil(Jobs[i].JobLength*1.0/100);
		if(BlockNum <= Head->BlockIndex)
		{
			for(j=0; j<BlockNum; j++)
			{	
				GetEmptyBlock=JobPageTable[i][j];
				do    
				{ 
					if(ExistInEmptyBlock(GetEmptyBlock)) /* my define*/
					{
						MemBlock[GetEmptyBlock].Empty=0;
						MemBlock[GetEmptyBlock].JobIndex=i+1;
						DelInEmptyBlock(GetEmptyBlock); /*my define*/
						break;
					}
				} while(1);
			}
			Head->BlockIndex=Head->BlockIndex-BlockNum;
		}
        else
        {
			outtextxy(5, 300, "The memery isn't enough to hold the job5.");
			outtextxy(5, 310,  "The job5 must be waiting...");
		}
	}

	DrawMemory();
	outtextxy(5, 330, "Job1:green");
	outtextxy(5, 340, "Job2:cyan");
	outtextxy(5, 350, "Job3:red");
	outtextxy(5, 360, "Job4:brown");
	getch();
	setfillstyle(SOLID_FILL, RED);
	bar(0, 480/3+1, 640, 480);
	outtextxy(5, 450, "Press any key to continue.  .");
}
void CreateJobPageTable(void)  /*建立作业页表*/
{
	int i, j, PageNum;
    for(i=0; i<=3; i++)
    {
		PageNum=(int)ceil(Jobs[i].JobLength*1.0/100);
		Jobs[i].JobPageTable=(int *)malloc(PageNum*sizeof(int));
		for(j=0; j<PageNum; j++)
		{
			Jobs[i].JobPageTable[j]=JobPageTable[i][j];
		}
    }
}
void AddInEmptyBlock(int i)  /*将一内存快装入空块链表*/
{
	struct EmptyBlockInfo *TempBlockInfo=Head, *TempBlockInfo1;
	while(TempBlockInfo!=NULL)
	{
		if(TempBlockInfo->NextBlock->BlockIndex>i)
		{
			TempBlockInfo1=(struct EmptyBlockInfo *)malloc(sizeof(
											struct EmptyBlockInfo));
			TempBlockInfo1->BlockIndex=i; 
			TempBlockInfo1->NextBlock=TempBlockInfo->NextBlock;
			TempBlockInfo->NextBlock=TempBlockInfo1;
			break;
		}
		else if(TempBlockInfo->NextBlock==NULL)
		{
			TempBlockInfo1=(struct EmptyBlockInfo *)malloc(sizeof(
											struct EmptyBlockInfo));
			TempBlockInfo1->BlockIndex=i;
			TempBlockInfo1->NextBlock=NULL;
			TempBlockInfo->NextBlock=TempBlockInfo1;
			break;
		}
		TempBlockInfo = TempBlockInfo->NextBlock;
	}
}
void LoadJob(int i)  /*装载作业*/
{
	struct EmptyBlockInfo *TempBlockInfo=Head->NextBlock, *TempBlockInfo1;
	int j, PageNum;
	PageNum=(int)ceil(Jobs[i].JobLength*1.0/100);
    for(j=0; j<PageNum; j++)
    {
		MemBlock[TempBlockInfo->BlockIndex].Empty=0;
		MemBlock[TempBlockInfo->BlockIndex].JobIndex=i+1;
		TempBlockInfo1=TempBlockInfo->NextBlock;
		DelInEmptyBlock(TempBlockInfo->BlockIndex);
		TempBlockInfo=TempBlockInfo1;
	}
	
	DrawMemory();
	outtextxy(5, 250, "The Job5 has loded in the memory");
	outtextxy(5, 270, "There are 3 Jobs in the memoey");
	outtextxy(5, 280, "Job3:red");
	outtextxy(5, 290, "Job4:brown");
	outtextxy(5, 300, "Job5: yellow");
}
void DeleteJob (void)  /*删除一个作业*/
{
	int i,  j, PageNum;
    int DeleteJobIndex[2]={0, 1};
	outtextxy(5, 175, "The Job1 and Job2 will be deleted");
	getch();
    for(j=0; j<=1; j++)
	{
		PageNum=(int)ceil(Jobs[DeleteJobIndex[j]].JobLength*1.0/100);
        for(i=0; i<PageNum; i++)   /*将作业占的内存块置空*/
		{
			MemBlock[Jobs[DeleteJobIndex[j]].JobPageTable[i]].Empty=1;
            /*在空块链表中加入此块*/
            AddInEmptyBlock(Jobs[DeleteJobIndex[j]].JobPageTable[i]);
		}
		free(Jobs[DeleteJobIndex[j]].JobPageTable); /*删除页表*/
		Head->BlockIndex=Head->BlockIndex+PageNum;
	}
	DrawMemory();
	outtextxy(5, 200, "The Job1 and Job2 have deleted.");
	outtextxy(5, 210,  "The while color indates the block is empty.");
	outtextxy(5, 220, " The Job5 will be loaded in the memory.");
	outtextxy(5, 270, "There are 2 Jobs in the memory");
	outtextxy(5, 280, "Job3:red");
	outtextxy(5, 290, "Job4:brown");
	getch();
	LoadJob(4);
	outtextxy(5, 350, "Press any key to end the programe!!!");
	getch();
}

void main(void)
{
	DrawScreen();
	outtextxy(5, 165, "The white color indates the block is empty.");
	outtextxy(5, 175, "There are 20 empty blocks in the memory.");
	outtextxy(5, 185, "The size of each block is 100.");
	outtextxy(5, 450, "Press any key to eontinue...");
	getch();
	InitMemoryBlock();   /*OK*/
	InitEmptyBlock();    /*我做了改动*/
	JobMessage();        /*OK*/
	InputJobs();		 /*OK*/
	CreateJobPageTable(); /*OK*/
	DeleteJob();  /*OK*/
	CloseScreen(); 
}

/*
  该程序是在图形模式下运行。运行时，不需要进行任何数据收入，只要按回车键，
  程序自动模拟主存的分配与回收
  */