操作系统内存动态分配模拟算法

malloc分配内存的算法malloc是一个常用的内存分配器，负责动态分配内存空间，以满足程序的需要。

在C/C++程序中，当需要动态申请内存空间时，常常使用malloc函数来完成。

malloc函数的使用非常常见，但究竟malloc如何进行内存分配的呢？接下来，我们将从几个方面来介绍malloc的内存分配算法。

1. 首先，当调用malloc函数申请内存时，malloc会先查询内部数据结构（堆）来寻找一块大小合适的未分配空间。

如果找到了，则将该空间分配给程序使用。

2. 如果堆中没有找到合适的未分配空间，则malloc会寻找一块比所需空间大的已分配空间，并将其切割成两块。

一块分配给程序使用，另一块作为新的未分配空间待分配。

这种方式可以避免由于内存碎片造成的内存使用不充分的问题。

3. 在内存分配之前，malloc会根据需要分配的内存大小选择一个合适的内存池进行内存分配。

例如，如果需要分配的内存较小，则会选择小块内存池，而需要分配较大内存时，则会选择大块内存池。

这样可以提高内存分配的效率。

4. malloc还会将小块内存进行分类，按照不同大小进行区分，从而让内存分配更加高效。

例如，当需要分配16字节以内的内存时，会从16字节的小块内存池中进行分配，而不是从其他大小的内存池中。

5. malloc会使用类似于引用计数的技术来管理内存使用情况，防止出现内存泄漏或者未释放内存的情况。

当程序申请内存时，malloc会为该内存块添加引用计数。

当该内存块不再被程序所使用时，引用计数会减一。

当引用计数为0时，该内存块会被释放掉。

综上所述，malloc作为一种常用的内存分配器，通过选择合适的内存池、将空闲内存块进行合理切割以及使用引用计数技术等方式来提高内存分配效率和内存使用情况。

在实际的软件开发中，应该根据具体的应用场景选择合适的内存分配方案，以充分利用内存，提高程序性能。

实验5 动态异长分区的存储分配与回收算法5.1 实验目的理解存储管理的功能，掌握动态异长分区的存储分配与回收算法。

存储器是计算机系统中的关键资源，存储管理一直是操作系统的最主要功能之一。

存储管理既包括内存资源管理，也包括用于实现分级存储体系的外存资源的管理。

通常，内存与外存可采用相同或相似的管理技术，如内存采用段式存储管理，则外存也采用段式存储管理。

存储管理需要完成如下功能：存储分配、存储共享、存储保护、存储扩充、地址映射。

当一个作业进入内存时，由操作系统将其变为进程,并为进程分配存储空间。

进程运行结束时, 由操作系统将其所占用的存储空间收回。

不同的操作系统对内存空间的划分与分配方法是不同的，通常分为两类：静态等长分区的分配和动态异长分区的分配。

静态等长分区常用于页式存储管理方式与段页式存储管理方式，存储空间被静态地划分为若干个长度相等的区域，每个区域被称作一个页面。

动态异长分区常用于界地址存储管理方式与段式存储管理方式，存储空间被动态地划分为若干个长度不等的区域。

5.2 实验要求本实验要求模拟动态异长分区的分配算法、回收算法和碎片整理算法。

5.3 实验步骤5.3.1 数据结构分析为了实现存储资源的分配和回收，操作系统需要记录内存资源使用情况，即哪些区域尚未分配，哪些区域已经分配以及分配给哪些进程等。

为此一般需要两个表，一个为分配表, 另外一个为空闲区域表。

前者记录已经分配的区域, 后者记录着所有当前未被进程占用的空闲区域, 如图5-1所示。

显然, 没有记录于表中的区域即为已被进程所占用的非空闲区域，在实际的操作系统中，这些区域登记在进程的PCB 中。

而PCB 中除了关于内存资源的信息外，还有其它大量信息。

由于本实验是对存储管理算法的模拟，所以用一个线程来代表一个进程，用线程驻留区域表来描述线程占用的内存空间，如图5-2所示。

图5-1 空闲区域表同时，需要一张表来记录各个线程对内存的请求信息，如图5-3所示。

实验5 动态异长分区的存储分配与回收算法5.1 实验目的理解存储管理的功能，掌握动态异长分区的存储分配与回收算法。

存储器是计算机系统中的关键资源，存储管理一直是操作系统的最主要功能之一。

存储管理既包括内存资源管理，也包括用于实现分级存储体系的外存资源的管理。

通常，内存与外存可采用相同或相似的管理技术，如内存采用段式存储管理，则外存也采用段式存储管理。

存储管理需要完成如下功能：存储分配、存储共享、存储保护、存储扩充、地址映射。

当一个作业进入内存时，由操作系统将其变为进程,并为进程分配存储空间。

进程运行结束时, 由操作系统将其所占用的存储空间收回。

不同的操作系统对内存空间的划分与分配方法是不同的，通常分为两类：静态等长分区的分配和动态异长分区的分配。

静态等长分区常用于页式存储管理方式与段页式存储管理方式，存储空间被静态地划分为若干个长度相等的区域，每个区域被称作一个页面。

动态异长分区常用于界地址存储管理方式与段式存储管理方式，存储空间被动态地划分为若干个长度不等的区域。

5.2 实验要求本实验要求模拟动态异长分区的分配算法、回收算法和碎片整理算法。

5.3 实验步骤5.3.1数据结构分析为了实现存储资源的分配和回收，操作系统需要记录内存资源使用情况，即哪些区域尚未分配，哪些区域已经分配以及分配给哪些进程等。

为此一般需要两个表，一个为分配表, 另外一个为空闲区域表。

前者记录已经分配的区域, 后者记录着所有当前未被进程占用的空闲区域, 如图51所示。

显然, 没有记录于表中的区域即为已被进程所占用的非空闲区域，在实际的操作系统中，这些区域登记在进程的PCB 中。

而PCB 中除了关于内存资源的信图51 空闲区域表息外，还有其它大量信息。

由于本实验是对存储管理算法的模拟，所以用一个线程来代表一个进程，用线程驻留区域表来描述线程占用的内存空间，如图52所示。

同时，需要一张表来记录各个线程对内存的请求信息，如图53所示。

内存分配---FF、BF、WF三种算法动态分区分配是根据进程的实际需要，动态的为之分配内存空间。

⽽在实现可变分区分配时，将涉及到分区分配中所⽤的数据结构、分区分配算法和分区的分配与内存回收的过程。

分区分配中的数据结构：（1）描述空闲块的数据结构。

（2）内存块的描述。

#define PROCESS_NAME_LEN 32 //进程名长度#define MIN_SLICE 10 //最⼩碎⽚的⼤⼩#define DEFAULT_MEM_SIZE 1024 //内存⼤⼩#define DEFAULT_MEM_START 0 //起始位置//内存分配算法#define MA_FF 1#define MA_BF 2#define MA_WF 3//描述每⼀个空闲块的数据结构struct free_block_type{int size; //空闲块⼤⼩int start_addr; //空闲块起始位置struct free_block_type *next; //指向下⼀个空闲块};//指向内存中空闲块链表的⾸地址struct free_block_type *free_block= NULL;//每个进程分配到的内存块的描述struct allocated_block{int pid;int size; //进程⼤⼩int start_addr; //进程分配到的内存块的起始地址char process_name[PROCESS_NAME_LEN]; //进程名struct allocated_block *next; //指向下⼀个进程控制块};//进程分配内存块链表的⾸指针struct allocated_block *allocated_block_head= NULL;int free_block_count= 0; //空闲块的个数int mem_size= DEFAULT_MEM_SIZE; //内存⼤⼩int current_free_mem_size= 0; //当前空闲内存⼤⼩int ma_algorithm= MA_FF; //当前分配算法static int pid= 0;int flag= 0; //设置内存⼤⼩标志，表⽰内存⼤⼩是否设置分区分配算法：（1）⾸次适应算法（First Fit）：从空闲分区表的第⼀个表⽬起查找该表，把最先能够满⾜要求的空闲区分配给作业，这种⽅法的⽬的在于减少查找时间。

内核物理内存分配是操作系统内核管理物理内存的过程，不同的操作系统可能采用不同的内存分配方式。

一般来说，常见的内核物理内存分配方式包括以下几种：
1. 固定分区分配（Fixed Partition Allocation）：
在这种方式下，物理内存被划分为若干固定大小的分区，每个分区用于分配给特定的内核模块或任务使用。

这种方式简单直观，但会导致内存碎片问题，限制了内存的灵活利用。

2. 动态分区分配（Dynamic Partition Allocation）：
这种方式下，物理内存被动态划分为不同大小的分区，内核可以根据需要动态分配和回收这些分区。

这种方式相对灵活，但也容易产生内存碎片，并且需要更复杂的内存管理算法来进行内存分配和回收。

3. 页式内存分配（Paging）：
在页式内存管理中，物理内存和逻辑内存都被划分为固定大小的页面（Page），内核将逻辑地址空间映射到物理地址空间的页面上。

这种方式可以有效解决内存碎片问题，但需要额外的页表来进行地址映射。

4. 段式内存分配（Segmentation）：
段式内存管理将逻辑地址空间划分为若干个段（Segment），每个
段的大小可以不同，而物理内存则被划分为相应的物理段。

内核通过段描述符来管理逻辑地址到物理地址的映射关系。

在实际的操作系统中，通常会综合利用以上多种内存分配方式，例如采用页式内存管理来解决内存碎片问题，同时结合动态分区分配来处理不同大小的内存请求。

内核物理内存分配的方式取决于操作系统的设计和内存管理算法的选择，不同的内存分配方式都有各自的优缺点，需要根据具体情况进行选择和权衡。

动态异长分区内存分配与去配算法的设计-最佳适应算法动态异长分区内存分配与去配算法的设计-最佳适应算法
动态异长分区内存分配是一种内存管理方式，它将物理内存划分为若干个不同大小的分区。

在应用程序运行时，系统会根据需要为程序分配相应大小的内存分区，使得程序能够正常运行。

在程序运行结束后，系统需要将分配的内存空间释放，以供其他程序使用。

最佳适应算法是一种常用的动态异长分区内存分配算法。

该算法在为程序分配内存分区时，会选择最小的能够容纳该程序的空闲分区。

如果不存在这样的分区，则会将内存空间进行分裂，以满足程序的需要。

在释放内存空间时，该算法会将相邻的空闲分区进行合并，以增加可用内存空间的大小。

最佳适应算法的优点在于，它能够更好地利用内存空间，减少内存浪费。

但是，该算法需要对空闲分区进行排序，以便快速找到最合适的空闲分区。

这会增加算法的时间复杂度和内存消耗。

总的来说，最佳适应算法是一种高效的动态异长分区内存分配算法，它能够更好地利用内存空间，减少内存浪费。

但是，该算法需要对空闲分区进行排序，可能会增加算法的时间复杂度和内存消耗。

操作系统课程设计动态分区分配学院专业学号学生姓名指导教师姓名2014年3月12日目录一、引言 (1)二、总体设计 (2)1. 数据处理类设计 (2)2. 相关消息映射设计 (3)3. 相关流图 (5)三、实验验证 (6)1. 结果截图 (6)2. 代码分析 (9)四、总结 (15)五、参考资料 (16)一、引言连续分配方式，是指为一个用户程序分配一个连续的内存空间。

这种分配方式曾被广泛应用于20世纪60~70年代的OS中，它至今仍在内存分配方式中占有一席之地；又可把连续分配方式进一步分为单一连续分配、固定分区分配、动态分区分配以及动态重定位分区分配四种方式。

动态分区分配是根据进程的实际需要，动态地为之分配内存空间。

在实现可变分区分配时，将涉及到分区分配中所用的数据结构、分区分配算法和分区的分配与回收操作这样的三个问题。

最佳适应算法（best fit）所谓“最佳”是指每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业，避免“大财小用”。

为了加速寻找，该算法要求将所有的空闲分区按其容量以从小到大的顺序形成一个空闲分区链。

这样，第一次找到的能满足要求的空闲区，必然是最佳的。

最坏适应算法（worst fit）最坏适应算法与最佳适应算法对应，具体实现过程中，仅仅对空闲分区链的创建不同。

最坏适应算法是以从大到小的方式创建的。

本次课设，对最佳适应算法与最坏适应算法两种算法进行模拟，程序的数据处理由标准的C++类设计完成。

程序采用了可视化程序界面的设计方法，协调完成各项要求。

【关键词】操作系统课设，动态分区分配，C++，MFC。

二、总体设计1.数据处理类设计数据处理是本次实验的设计的核心，具体算法的实现均是在此类中设计完成的。

作业节点类（class pcb）作为内嵌类，该类的主要作用是作为相关分区链节点。

该类的定义如下：class pcb{private:int ID;int FirstAddr;int len;int arrive_time;int holding_time;int run_time;public:pcb() { ID = 0; FirstAddr = len = arrive_time = holding_time = run_time = 0; }void setID(int N) { ID = N; }void setFA(int fa) { FirstAddr = fa; }void setLen(int l) { len = l; }void setAT(int at) { arrive_time = at; }void setHT(int ht) { holding_time = ht; }void setRT(int rt) { run_time = rt; }int getFA() const { return FirstAddr; }int getLen() const { return len; }int getAT() const { return arrive_time; }int getHT() const { return holding_time; }int getRT() const { return run_time; }int getID() const { return ID; }};分区链类主要处理空闲分区节点和作业节点的分配，实现最佳分配算法和最坏分配算法。

实验三动态分区存储管理一：实验目的了解动态分区存储管理方式中的数据结构和分配算法，加深对动态分区存储管理方式及其实现技术的理解。

二：实验内容用C语言或Pascal语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程Allocate()和回收过程Free()。

其中，空闲分区采用空闲分区链来组织，内存分配时，优先使用空闲区低地址部分的空间。

三：实验类别动态分区存储管理四：实验类型模拟实验五：主要仪器计算机六:结果和小结七：程序#include<stdio.h>#include<time.h>#include<stdlib.h>#define SIZE 640 // 内存初始大小#define MINSIZE 5 // 碎片最小值struct memory{struct memory *former;//前向指针int address;//地址int num;//作业号int size;//分配内存大小int state;//状态0表示空闲，1表示已分配struct memory *next;//后向指针}linklist;void intmemory()// 初始化空闲分区链{memory *p=(memory *)malloc(sizeof(memory));// 分配初始分区内存p->address=0;// 给首个分区赋值p->size=SIZE;p->state=0;p->num=-1;p->former=&linklist;p->next=NULL;linklist.former=NULL;// 初始化分区头部信息linklist.next=p;}int firstFit(int num, int size)// 首次适应算法{memory *p = linklist.next;while(p != NULL){if(p->state == 0 && p->size >= size) // 找到要分配的空闲分区{if(p->size - size <= MINSIZE)// 整块分配{p->state = 1;p->num = num;}else // 分配大小为size的区间{memory *node=(memory *)malloc(sizeof(memory));node->address=p->address + size;node->size=p->size-size;node->state=0;node->num=-1;// 修改分区链节点指针node->former=p;node->next=p->next;if(p->next !=NULL){p->next->former=node;}p->next = node;// 分配空闲区间p->size = size;p->state = 1;p->num = num;}printf("内存分配成功！\n");return 1;}p = p->next;}printf("找不到合适的内存分区，分配失败...\n");return 0;}int bestFit(int num, int size)// 最佳适应算法{memory *tar=NULL;int tarSize=SIZE + 1;memory *p=linklist.next;while(p!=NULL){if(p->state==0 && p->size >= size && p->size < tarSize) //寻找最佳空闲区间{tar=p;tarSize=p->size;}p=p->next;}if(tar!=NULL){if(tar->size - size <= MINSIZE) //找到要分配的空闲分区{tar->state = 1;// 整块分配tar->num=num;}else // 分配大小为size的区间{memory *node = (memory *)malloc(sizeof(memory));node->address = tar->address + size;node->size = tar->size - size;node->state = 0;node->num = -1;// 修改分区链节点指针node->former = tar;node->next = tar->next;if(tar->next != NULL){tar->next->former = node;}tar->next = node;// 分配空闲区间tar->size = size;tar->state = 1;tar->num = num;}printf("内存分配成功！\n");return 1;} else{// 找不到合适的空闲分区printf("找不到合适的内存分区，分配失败!!\n");return 0;}}int freememory(int num)// 回收内存{int flag=0;memory *p=linklist.next, *pp;while(p!=NULL){if(p->state==1 && p->num==num){flag = 1;if((p->former!= &linklist && p->former->state == 0) && (p->next != NULL && p->next->state == 0)){// 情况1：合并上下两个分区// 先合并上区间pp=p;p=p->former;p->size+=pp->size;p->next=pp->next;pp->next->former=p;free(pp);// 后合并下区间pp=p->next;p->size+=pp->size;p->next=pp->next;if(pp->next!=NULL){pp->next->former=p;}free(pp);}else if((p->former==&linklist || p->former->state==1)&& (p->next!=NULL&&p->next->state ==0)) {// 情况2：只合并下面的分区pp=p->next;p->size+=pp->size;p->state=0;p->num=-1;p->next=pp->next;if(pp->next!= NULL){pp->next->former=p;}free(pp);}else if((p->former!=&linklist&&p->former->state==0)&& (p->next==NULL || p->next->state==1)) {// 情况3：只合并上面的分区pp=p;p=p->former;p->size+=pp->size;p->next=pp->next;if(pp->next != NULL) {pp->next->former = p;}free(pp);}else{// 情况4：上下分区均不用合并p->state=0;p->num=-1;}}p=p->next;}if(flag==1){// 回收成功printf("内存分区回收成功...\n");return 1;}else{// 找不到目标作业，回收失败printf("找不到目标作业，内存分区回收失败...\n");return 0;}}// 显示空闲分区链情况void showmemory(){printf(" 当前的内存分配情况如下：\n");printf("*********************************************\n");printf(" 起始地址| 空间大小| 工作状态| 作业号\n");memory *p=linklist.next;while(p!=NULL){printf("******************************************\n");printf("**");printf("%5d k |", p->address);printf("%5d k |", p->size);printf(" %5s |", p->state == 0 ? "0" : "1");if(p->num > 0) {printf("%5d ", p->num);} else {printf(" ");}p = p->next;}}int main(){int option, ope, num, size;// 初始化空闲分区链intmemory();// 选择分配算法l1: while(1){printf("***************************************\n");printf("请选择要模拟的分配算法:\n1表示首次适应算法\n2表示最佳适应算法\n");printf("***************************************\n");scanf("%d", &option);system("cls");if(option==1) {printf("你选择了首次适应算法，下面进行算法的模拟\n");break;} else if(option==2) {printf("你选择了最佳适应算法，下面进行算法的模拟\n");break;}else {printf("错误：请输入0/1\n\n");}}// 模拟动态分区分配算法while(1){printf("\n");printf("*********************************************\n");printf("1:分配内存\n 2:回收内存\n 3:返回上一级菜单\n\n");printf("*********************************************\n");scanf("%d", &ope);system("cls");if(ope==0) break;if(ope==1){// 模拟分配内存printf("请输入作业号：");scanf("%d", &num);printf("请输入需要分配的内存大小(KB)：");scanf("%d", &size);if(size<=0){printf("错误：分配内存大小必须为正值\n");continue;}// 调用分配算法if(option==0){firstFit(num, size);}else{bestFit(num, size);}// 显示空闲分区链情况showmemory();}else if(ope==2){// 模拟回收内存printf("请输入要回收的作业号：");scanf("%d", &num);freememory(num);// 显示空闲分区链情况showmemory();}else if(ope==3){goto l1;}else{printf("错误：请输入0/1/2\n");}}printf("分配算法模拟结束\n");return 0;}。

计算机与信息工程系实验报告
班级计算机
1001
姓名李双贺时间2011.11.09 地点A504
实验名称存储器管理——动态分区的分配与回收
实验目的
目的是在学习操作系统理论知识的基础上，对操作系统整体的一个模拟。

研究计算机操作系统的基本原理和算法，掌握操作系统的存储器管理的首次适应算法、循环首次适应算法、最佳适应算法的基本原理和算法。

提高运用操作系统知识和解决实际问题的能力；并且锻炼自己的编程能力、创新能力以及开发软件的能力。

使学生掌握基本的原理和方法，最后达到对完整系统的理解。

实验内容
内存调度策略可采用首次适应算法、循环首次适应算法和最佳适应法等，并对各种算法进行性能比较。

为了实现分区分配，系统中必须配置相应的数据结构，用来描述空闲区和已分配区的情况，为分配提供依据。

常用的数据结构有两种形式：空闲分区表和空闲分区链。

为把一个新作业装入内存，须按照一定的算法，从空闲分区表或空闲分区链中选出一个分区分配给该作业。

实验结果。