新建 文本文档 (2).txt

模拟实现可变分区存储管理 一、设计目的 在熟练掌握计算机分区存储管理方式的原理的基础上

武汉工业学院

计算机与信息工程系




操 作 系 统   课程设计报告
  






 专    业:     计算机科学与技术
电    邮:     [e-mail]
姓    名:     陈  磊          
指导老师:     左爱群          

2005-6-26
模拟实现可变分区存储管理
一、设计目的
在熟练掌握计算机分区存储管理方式的原理的基础上，利用C程序设计语言在windows操作系统下模拟实现操作系统的可变分区存储管理的功能，一方面加深对原理的理解，另一方面提高根据已有原理通过编程解决实际问题的能力，为进行系统软件开发和针对实际问题提出高效的软件解决方案打下基础。
二、各功能模块分析实现
设计合理的数据结构来描述存储空间：
对于未分配出去的部分，用空闲分区链表来描述。
struct freeList               
{
int startAddress;          /* 分区起始地址 */
int size;                 /* 分区大小 */
struct freeList *next;       /* 分区链表指针 */
}
对于已经分配出去的部分，由装入内存的作业占据。
struct usedList	            
{
int startAddress;          /* 分区起始地址 */
int jobID;               /* 分区中存放作业ID */
struct usedList *next;      /* 分区链表指针 */
}
将作业组织成链表。
struct jobList
{
int id;                   /* 作业ID */
int size;                 /* 作业大小（需要的存储空间大小） */
int status; /* 作业状态 0 : new job ,1 : in the memory , 2 : finished . */
struct jobList *next;       /* 作业链表指针 */
}
以上将存储空间分为空闲可占用两部分，在usedlist中设jobID而不设size，可以在不增加空间复杂度（与freelist相比）的同时更方便的实现可变分区存储管理（从后面的一些函数的实现上可以得出这个结论）。
尽管设置joblist增加了空间复杂度，但它的存在，使得该程序可以方便的直接利用D盘中的JOB文件。该文件可以认为是一个和其他进程共享的资源。通过这个文件，其他进程写入数据供读取。这中思想在操作系统设计中体现的很多。
实现分区存储管理的内存分配功能，选择适应算法（首次适应算法，最佳适       应算法，最后适应算法，最坏适应算法）。
基本原理分析： 
1） Best fit ：将空闲分区按大小从小到大排序，从头找到大小合适的分区。
2） Worst fit：将空闲分区按大小从大到小排序，从头找到大小合适的分区。
3） First fit ：将空闲分区按起始地址大小从小到大排序，……
4） Last fit ：将空闲分区按起始地址大小从大到小排序，……
由此，可将空闲分区先做合适的排序后用对应的适应算法给作业分配存储空间。排序函数 order（bySize为零则按分区大小排序，否则按分区起始地址；inc为零从小到大排序，否则从大到小排序；通过empty指针返回结果）。
void order(struct freeList **empty,int bySize,int inc)
{
struct freeList *p,*q,*temp;
	int startAddress,size;
	for(p = (*empty) -> next;p;p = p -> next)
	{    /* 按bySize和inc两个参数寻找合适的节点，用temp指向它 */
		for(temp = q = p;q;q = q -> next)
		{
			switch(bySize)
			{
				case 0 : switch(inc)
					{
						case 0:if(q->size < temp->size)
								temp = q;break;
						default:if(q->size > temp->size)
								temp = q;break;
					}  break;
				default: switch(inc)
					{
						case 0:if(q->startAddress < temp->startAddress)
								temp = q;break;
						default:if(q->startAddress > temp->startAddress)
								temp = q;break;
					}  break;
			}
		}                                 /* 交换节点的成员值 */ 
		if(temp != p)
		{  
			startAddress = p->startAddress;
			size = p->size;
			p->startAddress = temp->startAddress;
			p->size = temp->size;
			temp->startAddress = startAddress;
			temp->size = size;
		}
	}
}
实现分区存储管理的内存回收算法：
void insertFreeNode(struct freeList **empty,int startAddress,int size)
插入回收的空节点分区，处理回收分区与空闲分区的四种邻接关系。
{
	struct freeList *p,*q,*r;
  	for(p = *empty;p -> next;p = p -> next)  ;    /* 处理链表尾部的邻接情况 */
	if(p == *empty || p -> startAddress + p -> size < startAddress)/* 与尾部不相邻*/
	{
		makeFreeNode(&r,startAddress,size); /* 通过r指针返回创建的空闲节点*/
		r -> next = p -> next;                      /* 插入独立的空闲节点 */
		p -> next = r;
		return ;
	}
	if(p -> startAddress + p -> size == startAddress)           /* 与尾部上邻 */
	{
		p -> size += size;                     			   /* 合并尾部节点 */
		return ;
	}
	q = (*empty) -> next;                   /* 处理链表首节点的邻接情况 */
	if(startAddress + size == q -> startAddress)             /* 与首节点下邻 */
	{
		q -> startAddress = startAddress;                    /* 合并首节点 */
		q -> size += size;
	}
	else if(startAddress + size < q -> startAddress)         /* 与首节点不相邻 */
	{
		makeFreeNode(&r,startAddress,size);
		r -> next = (*empty) -> next;
		(*empty) -> next = r;
	}
	else 
	{                                     /* 处理链表中间的邻接情况 */
		while(q -> next && q -> startAddress < startAddress)
		{
			p = q;
			q = q -> next;
		}
		if(p -> startAddress + p -> size == startAddress &&\
		   q -> startAddress == startAddress + size)      /* 上下邻，合并节点 */
		{
			p -> size += size + q -> size;
			p -> next = q -> next;
			free(q);                                   /* 删除多余节点 */
		}
		else if(p -> startAddress + p -> size == startAddress &&\
			   q -> startAddress != startAddress + size) /*上邻，增加节点的大小*/
		{
				p -> size += size;
		}
		else if(p -> startAddress + p -> size != startAddress &&\
			   q -> startAddress == startAddress + size)             /* 下邻 */
		{
				q -> startAddress = startAddress;       /* 修改节点起始地址 */
				q -> size += size;                      /* 修改节点的大小 */
		}
		else
		{                                              /* 上下不相邻 */
			makeFreeNode(&r,startAddress,size);
			r -> next = p -> next;
			p -> next = r;
		}
	}
}
当碎片产生时，进行碎片的拼接。
void moveFragment(struct jobList *jobs,struct freeList **empty,struct usedList **used)
{
	int size,status;
	struct usedList *p;
	int address = memoryStartAddress; /*全局变量，初始化时分配存储空间始址*/
	if((*empty)->next == NULL)       /* 空闲分区链表为空，提示并返回 */
	{
printf("\nThe memory was used out at all.\nMay be you should finish some jobs first or press any key to try again !");
		getch();
		return;
	}
	for(p = (*used) -> next;p;p = p-> next)     /* 循环的修改占用分区的始址 */
	{
		p -> startAddress = address;
		getJobInfo(jobs,p -> jobID,&size,&status); /* 由作业ID获得作业大小 */
		address += size;
	}
	(*empty)->next->startAddress = address;/*修改空闲分区的首节点始址、大小*/
	(*empty) -> next -> size = memorySize - (address - memoryStartAddress);
	(*empty) -> next -> next = NULL;          /* 删除首节点后的所有节点 */
}
空闲分区队列显示：int showFreeList(struct freeList *empty)
作业占用链表显示：int showUsedList(struct jobList *jobs,struct usedList *used) 
从头到尾显示used链，同时通过其中的作业ID在jobs中查对应的大小。
从键盘输入作业到D盘的JOB文件：void inputJob(void)
从JOB文件中读出作业并创建作业链表：int makeJobList(struct jobList **jobs)
显示作业链表：int showJobList(struct jobList *jobs) 
10.更新作业链表中作业的状态： int updateJobFile(struct jobList *jobs)
11.根据作业链表更新JOB文件： int updateJobFile(struct jobList *jobs)  
12.为作业分配存储空间、状态必须为0：int allocate(struct freeList **empty,int size)            
13.结束一个作业号为id的作业，释放存储空间（由*startAddress返回空间的起始地址）：int finishJob(struct usedList **used,int id,int *startAddress)
14.插入释放的空间到used链表中（作业号为id，startAddress由函数13返回）：
void insertUsedNode(struct usedList **used,int id,int startAddress)
15.获取作业的信息： void getJobInfo(struct jobList *jobs,int id,int *size,int *status)
16.初始化存储空间起始地址、大小：void iniMemory(void)
17.选择适应算法：char selectFitMethod(void)
18.根据参数startAddress、size创建空闲节点，由empty指针返回：
void makeFreeNode(struct freeList **empty,int startAddress,int size)
19.以要求的方式打开文件：void openFile(FILE **fp,char *filename,char *mode)
20.出现严重错误时显示信息并结束程序；void errorMessage(void)
三、总体界面与程序流程分析
Dynamic Zonal Memory Management

其中1、Initializiation.按顺序利用了openFile()、iniMemory()、makeFreeNode()、inputJob()（选择利用D盘JOB文件时提供作业信息）、makeJobList()、allocate()、insertUsedNode()（选择利用D盘JOB文件时先将状态为1的作业放到存储空间中，以恢复上次的模拟实验，或使本次模拟时不出错）selectFitMethod()等自编函数。
		2、Put job into memory(allocate memory)按顺序利用了showJobList()（选手动逐个为作业分配存储空间时）、openFile()、order()、allocate()、errorMessage()、insertUsedNode()、updateJobStatus()updateJobFile()函数
（自动为如上作业分配存储后状态的变化——>）      
3、Finish job(reuse memory)按顺序利用了openFile()、showUsedList()、getJobInfo()、insert FreeNode()、updateJobStatus()、updateJobFile()、errorMessage()等自编函数。        
（完成部分作业后作业——>）

4、Show current free list 按顺序利用了openFile()、showFreeList()函数。                                  （如下图为当前空闲分区）

5、Show current memory used by jobs按顺序利用了openFile()、showUsedList()函数。         （如下图为当前作业占用的分区）

6、Move fragment together按顺序利用了openFile()、moveFragment()函数。
 整理 à   
7、Exit按顺序利用了openFile()、exit(0)函数。
四、主程序流程图

		


                                               step=’1’
                                  step=’2’       
                 
                                             step=’6’
                           step=’3’step=’4’ 

                                     step=’5’   


step=’7’


五、结果分析与总结
程序中创建的两个文件

1）Best fit算法验证： 
  如下图分配大小为50的8号作业，恰好占用大小为50的空闲而非大小为240的。
2）Worst fit算法验证：
如下图分配大小为50的8号作业，占用大小为100空闲而非大小为70的。

3）First fit算法验证：
如下图分配大小为50的8号作业，占用起始地址为110空闲而非350的。

4）Last fit算法验证：
如下图分配大小为50的8号作业，占用起始地址为350空闲而非110的。
总结：通过这次课程设计我练习了用C语言写系统软件，对OS中可变分区存储管理有了更深刻的了解。在写程序的时候也遇到了一些困难。比如在设计数据结构时特别犹豫，总想找一个很合适的。但是，后来才知道，关键要多尝试，而空想是没有用的。最后我证实了自己的设计的合理性。还有为了使程序更健壮，我尝试着将程序中的输入部分全部改为字符（串）。成功的避免了接受整型数据时输入字符后引起的错误，使程序能接受
任何输入而正常结束。很遗憾的是因为时间问题，没有把这个模拟程序写成动画形式，还可以加几句代码后实现动态的增加作业。