欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

计算机操作系统实验三：动态分区分配方式的模拟

程序员文章站 2024-03-17 09:57:34
...

一、实验目的

    ~~~~ 了解动态分区分配方式中的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解

2、实验内容

  1. 用C语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程和回收过程。其中，空闲分区通过空闲分区链（表）来管理；在进行内存分配时，系统优先使用空闲区低端的空间。
  2. 假设初始状态下，可用的内存空间为640KB，并有下列的请求序列：
    •作业1申请130KB
    •作业2申请60KB
    •作业3申请100KB
    •作业2释放60KB
    •作业4申请200KB
    •作业3释放100KB
    •作业1释放130KB
    •作业5申请140KB
    •作业6申请60KB
    •作业7申请50KB
    •作业8申请60KB
    请分别采用首次适应算法和最佳适应算法进行内存的分配和回收，要求每次分配和回收后显示出空闲内存分区链的情况。

三、思考：讨论各种分配算法的特点。

  1. 首次适应算法：
    算法思想：将空闲分区链以地址递增的顺序连接；在进行内存分配时，从链首开始顺序查找，直到找到一块分区的大小可以满足需求时，按照该作业的大小，从该分区中分配出内存，将剩下的空闲分区仍然链在空闲分区链中。
    优点：高址部分的大的空闲分区得到保留，为大作业的内存分配创造了条件；
    缺点：（1）每次都是优先利用低址部分的空闲分区，造成低址部分产生大量的外碎 片。（2）每次都是从低址部分查找，使得查找空闲分区的开销增大；

  2. 最佳适应算法：
    算法思想：将空闲分区链中的空闲分区按照空闲分区由小到大的顺序排序，从而形成空闲分区链。每次从链首进行查找合适的空闲分区为作业分配内存，这样每次找到的空闲分区是和作业大小最接近的，所谓“最佳”。
    优点：第一次找到的空闲分区是大小最接近待分配内存作业大小的；
    缺点:产生大量难以利用的外部碎片。

四、实现思路

  1. 首次适应算法
    我们以空闲分区链为例来说明采用FF算法时的分配情况。FF算法要求空闲分区链以地址递增的次序链接。
    1.在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止；
    2.然后再按照作业的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲链中。
    3.若从链首直至链尾都不能找到一个能满足要求的分区，则此次内存分配失败，返回。
  2. 最佳适应算法：
    1.将空闲分区链中的空闲分区按照空闲分区由小到大的顺序排序，从而形成空闲分区链。
    2.每次从链首进行查找合适的空闲分区为作业分配内存，余下的空闲分区仍留在空闲链中。
    3.若从链首直至链尾都不能找到一个能满足要求的分区，则此次内存分配失败，返回。

五、主要的数据结构

包含分区号、分区开始地址 、空闲地址 、剩余空间 、状态信息的Partition结构体

六、算法流程图

  1. 首次适应算法
    计算机操作系统实验三：动态分区分配方式的模拟

  2. 最佳适应算法
    计算机操作系统实验三：动态分区分配方式的模拟

七、运行与测试

  1. 首次适应算法
    计算机操作系统实验三：动态分区分配方式的模拟
  2. 最佳适应算法
    计算机操作系统实验三：动态分区分配方式的模拟

八、总结

    ~~~~ 通过本次实验，编写并调试了动态分区分配方式的模拟程序，更加熟悉了动态分区分配方式的过程，我采用了动态分区分配，动态分区分配也包含了几个算法，分别是首次适应算法，和最佳适应算法，提高了计算机的分配效率。

九、代码附录

#include<stdio.h>
#include<malloc.h>
#include<string.h>

#define TOTAL_MEMORY 200


typedef struct partition {
	int num;			//分区号 
	int startAdress;    //分区开始地址 
	int leisureAdress;  //空闲地址 
	int size;			//剩余空间 
	int state;         //状态 , 0未分配，1已分配 
	struct partition *next;
}partition, *PART;

void printPartitionQue(PART partHead) {
	PART mPart = partHead;
	printf("分区号      起址       空闲起址       空闲空间       状态\n");
	while (mPart != NULL) {
		printf("%3d          ", mPart->num);
		printf("%3d          ", mPart->startAdress);
		printf("%3d          ", mPart->leisureAdress);
		printf("%3d           ", mPart->size);
		printf("%3d           ", mPart->state);
		printf("\n");
		mPart = mPart->next;
	}
	printf("\n");
}

/**
*	创建分区
*/
PART createPartition() {
	PART partHead = NULL, mPart = NULL;
	int sizes[4] = { 64, 16, 128, 32 };
	//	int sizes[4] = {128, 64, 32, 12};
	int startAdress = 20;
	for (int i = 1; i <= 4; i++) {
		if (i == 1) {
			mPart = partHead = (PART)malloc(sizeof(partition));
			mPart->num = i;
			mPart->startAdress = startAdress;
			mPart->leisureAdress = startAdress;
			mPart->size = sizes[i - 1];
			mPart->state = 0;
			startAdress += mPart->size;
			mPart->next = NULL;
		}
		else {
			mPart->next = (PART)malloc(sizeof(partition));
			mPart = mPart->next;
			mPart->num = i;
			mPart->startAdress = startAdress;
			mPart->leisureAdress = startAdress;
			mPart->size = sizes[i - 1];
			mPart->state = 0;
			startAdress += mPart->size;
			mPart->next = NULL;
		}
	}
	return partHead;
}

/**
*	按可用空间大小按升序 选择排序
*/
PART  sort(PART partHead, int totalPart) {
	PART sortHead = NULL;
	PART nPart = NULL, tPart = NULL;;
	PART temp;
	int min = 0;
	while (totalPart != 0) {
		min = partHead->size;
		nPart = partHead->next;
		//获取最小的大小赋值给min 
		while (nPart != NULL) {
			if (min > nPart->size) {
				min = nPart->size;
			}
			nPart = nPart->next;
		}
		nPart = partHead;
		while (nPart != NULL) {
			if (nPart->size == min) {
				temp = nPart;
				if (sortHead == NULL) {
					tPart = sortHead = (PART)malloc(sizeof(partition));
					tPart->num = nPart->num;
					tPart->startAdress = nPart->startAdress;
					tPart->leisureAdress = nPart->leisureAdress;
					tPart->size = nPart->size;
					tPart->state = nPart->state;
					tPart->next = NULL;
				}
				else {
					tPart->next = (PART)malloc(sizeof(partition));
					tPart = tPart->next;
					tPart->num = nPart->num;
					tPart->startAdress = nPart->startAdress;
					tPart->leisureAdress = nPart->leisureAdress;
					tPart->size = nPart->size;
					tPart->state = nPart->state;
					tPart->next = NULL;
				}
				PART mPart = partHead;
				while (mPart != NULL) {
					if (mPart == temp) {
						partHead = partHead->next;
						totalPart--;
						break;
					}
					else if (mPart->next == temp) {
						mPart->next = temp->next;
						totalPart--;
						break;
					}
					mPart = mPart->next;
				}
			}

			nPart = nPart->next;
		}
	}
	return sortHead;
}

/**
*	首次适应算法分配内存核心代码
*/
void assignOfFirstFit(PART partHead, PART mPart, int size) {
	mPart = partHead;
	while (mPart != NULL) {
		if (mPart->size >= size) {
			mPart->size -= size;
			mPart->leisureAdress += size;
			mPart->state = 1;
			printf("***********************成功分配后的分区列表***********************\n");
			printPartitionQue(partHead);
			break;
		}
		mPart = mPart->next;
	}
	if (mPart == NULL) {
		printf("内存不足!\n");
	}
}

/**
*	循环首次适应算法分配内存核心代码
*/
PART assignOfNextFit(PART partHead, PART mPart, int size, int totalPart) {
	while (totalPart != 0) {
		if (mPart != NULL) {
			if (mPart->size >= size) {
				mPart->size -= size;
				mPart->leisureAdress += size;
				mPart->state = 1;
				printf("***********************成功分配后的分区列表***********************\n");
				printPartitionQue(partHead);
				return mPart->next;
			}
			mPart = mPart->next;
			totalPart--;
		}
		else {
			mPart = partHead;
		}
	}
	if (totalPart == 0) {
		printf("内存不足!\n");
		return mPart;
	}
}


//	最佳适应算法

PART assignOfBestFit(PART partHead, PART mPart, int size) {
	mPart = sort(partHead, 4);
	partHead = mPart;
	while (mPart != NULL) {
		if (mPart->size >= size) {
			mPart->size -= size;
			mPart->leisureAdress += size;
			mPart->state = 1;
			printf("***********************成功分配后的分区列表***********************\n");
			partHead = sort(partHead, 4);
			printPartitionQue(partHead);
			return partHead;
		}
		mPart = mPart->next;
	}
	if (mPart == NULL) {
		printf("内存不足!\n");
		return partHead;
	}
}

/**
*  分配内存
*/
void assignMemory(PART partHead, int assignType) {
	int totalPart = 4;
	PART mPart = partHead;
	char c;
	char name[10] = "";
	int size = 0;
	printf("是否输入作业(Y/N)：");
	scanf("%c", &c);
	while (c == 'Y' || c == 'y') {
		printf("请输入作业名：");
		scanf("%s", &name);
		printf("请输入作业大小：");
		scanf("%d", &size);

		switch (assignType) {
		case 1:
			assignOfFirstFit(partHead, mPart, size);
			break;
		case 2:
			partHead = assignOfBestFit(partHead, mPart, size);
			break;
		}

		printf("是否输入作业(Y/N)：");
		getchar();
		scanf("%c", &c);
	}
}

/**
*	最佳适应算法
*/
void BestFit(PART partHead) {
	printf("***********************排序前的分区列表***********************\n");
	printPartitionQue(partHead);
	//分配内存
	assignMemory(partHead, 2);
}


/**
*	首次适应算法
*/
void FirstFit(PART partHead) {
	printf("***********************分配前的分区列表***********************\n");
	printPartitionQue(partHead);
	//分配内存 
	assignMemory(partHead, 1);
}

int main() {
	int k;
	PART partHead = createPartition();
	printf("*****************************动态分区分配方式的模拟*************************");
	printf("\n                          1、首次适应算法                                 ");
	printf("\n                          2、最佳适应算法                                 ");
	printf("\n                          3、退出                                         ");
	printf("\n请输入对应序号选择相应的算法：");
	scanf("%d", &k);
	getchar();
	switch (k) {
	case 1:
		FirstFit(partHead);
		break;
	case 2:
		BestFit(partHead);
		break;
	case 3:
		break;
	default:
		printf("选择错误，请重新选择。");
	}
	return 0;
}

上一篇： ubuntu 12.04 LTS下安装zabbix 博客分类： 监控 zabbix系统监控 

下一篇： BitmapData 博客分类： Flex

推荐阅读