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

一、实验目的

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

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;
}
版权声明：本文为weixin_37537818原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/weixin_37537818/article/details/89486644

智能推荐

Python 学习记录-list类方法补充 Day9

<1>clear() #清空列表 输出结果： [] 认识深浅拷贝方法前的知识点补充****************************** 数据类型在内存的指向情况如下几种： ***第一种情况：列表指向相同的内存地址 输出结果： [11, 22, 33] [11, 22, 33] li1与li2指向相同的内存地址！！ 输出结果： [11, 22, 33, 44] [11, 22, ...

java压缩文件并加密，发送到邮箱

日常记录 目标，我们需要把文件进行压缩 并进行加密设置密码，并发送到指定的邮箱，这是需求    首先把工具类贴出来 我们需要导入一个jar包 winzipaes-1.0.1.jar 上传了一下，告诉已经存在了所以，有看到的去找下吧， 应该很好找的 用法在下面 下面介绍一下用法 直接调用方法即可，第一个参数是你的文件名称，第二个事压缩完后的文件名称，第三个是压缩加密的密...

使用@Slf4j的正确方法

环境说明 Windows 10 1803 IDEA 2018.2.EAP Maven 3.5.2 这是正文 POM文件 这里要吐槽一下，其实不想写这篇的，因为网上一搜有很多，但是，我真的被坑到了，很多篇教程都是复制，依赖不全，导致我总是运行不了。教程教程，就是给人学习的，你不能默认你的读者掌握了其他相关的东西。 好了，在pom中添加上面的所有依赖，很多教程里都只说添加lombok依赖就行了，其实不...

2020南京邮电大学Mooc—在线期末考试主观卷

为客观卷部分，自取。 2020南京邮电大学Mooc—在线期末考试客观卷 1 ( 20分 ) 请对序列进行快速排序，写出前5趟的排序过程，按照如下答题格式进行答题，答题时注意不要漏掉下划线，下划线标错扣分。 答题格式： 第1趟： 第2趟：____________________________ 第3趟：____________________________ 第4趟：__________...

入门图论、图论的一些基本概念及实战

图论的一些基本概念及实战 基本概念 主要思想 实战 例题1-无向图的广深优先遍历 例题2--有向图的深度优先遍历（城市地图） 例题3--最少转机 基本概念 图就是有N个顶点和M条边组成的集合。图分为有向图和无向图，如果给图的每条边规定一个方向，那么得到的图称为有向图，其他边也称为有向边。在有向图中，与一个点相关联的边有出边和入边之分，而与一个有向边关联的两个点也有始点和终点之分。边没有方向的图称为...

猜你喜欢

maven 保姆教程

什么是Maven？ 如今我们构建一个项目需要用到很多第三方的类库，如写一个使用Spring的Web项目就需要引入大量的jar包。一个项目Jar包的数量之多往往让我们瞠目结舌，并且Jar包之间的关系错综复杂，一个Jar包往往又会引用其他Jar包，缺少任何一个Jar包都会导致项目编译失败。 以往开发项目时，程序员往往需要花较多的精力在引用Jar包搭建项目环境上，而这一项工作尤为艰难，少一个Jar包、多...

动态规划类问题解题步骤 --附例题（小偷问题）

动态规划类问题解题步骤 --附例题（小偷问题） 动态规划 基本思想 适用情况 优点 解题步骤 实例分析 问题 解题步骤 动态规划 基本思想 动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。 适用情况 最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优...

C++：点 线 位置关系

一、不带方向        分享给有需要的人，代码质量勿喷 二、带方向  左右位置 2.1 ΔX=0            2.2 ΔX>0 2.3 ΔX<0 分享给有需要的人，代码质量勿喷  ...

从Java到Android_Java基础_6.Java数组

6.Java数组 一、数组 1.使用数组的原因 2.什么是数组 3.数组声明 4.数组创建 5.数组在内存中的存储 6.局部变量和数组的默认值 7.数组的初始化 8.数组元素的引用 9.数组长度 二、一维数组 1.默认值 2.循环赋值 3.循环输出 4.数组下标越界异常 三、应用 1.求整数数组的累加和 2.求数组元素最大值 四、增强型for循环 1.增强型for循环 2.foreach循环应用 ...

通过修改MotorControl Workbench生成的程序来改变死区时间

本例程是基于MotorControl Workbench 5.2.0版本生成的HALL传感器的FOC控制程序。 程序的修改是在drive_parameters.h文件里211行处，如下图：...