基于Linux的主存空间分配与回收
设计内容：
采用可变式分区管理，使用首次或最佳适应算法实现主存的分配与回收。可以采用分区说明表或空闲区链来进行。可变式分区管理是指在处理作业过程中建立分区，使分区大小正好适合作业的需要，并且分区个数是可以调整的。当要装入一个作业时，根据作业需要的主存量，查看是否有足够的空闲空间，若有，则按需求量分割一部分给作业；若无；则作业等待。随着作业的装入、完成，主存空间被分割成许多大大小小的分区。有的分区被作业占用，有的分区空闲。
基本要求
- 调用相关的Linux系统内核函数
- 设计多个作业或进程动态请求内存资源的模拟系统；
- 使用首次、最佳适应算法等实现内存的分配与回收；
- 实现可变式分区管理；
- 设计相应的内存分配算法，定义相关数据结构；
- 输出显示每次请求分配内存的结果和内存的已分配和未分配的状况。
1.1课程概述
1.1.1设计目的
为了能够将用户程序装入内存， 必须为它分配一定大小的内存空间。连续分配方式是最早出现的一直存储器分配方式。动态分区分配又称为可变分区分配，它是根据进程的实际需要，动态的为之分配内存空间。
1.1.2功能模块分析
（1）实现手动创建或者随机创建几个进程或作业
（2）实现初始化空闲链表
（3）实现内存分配算法
（4）实现首次适应算法
（5）实现最佳适应算法
（6）实现内存回收
（7）可变式分区的设计和管理；
1.2设计方案
创建进程或作业(该程序中使用进程代替作业)，通过调用内核函数创建进程在，并赋值。
采用可变式分区管理，使用首次或最佳适应算法实现主存的分配与回收。可以采用分区说明表和空闲区链来进行说明内存结构。可变式分区管理可以在处理作业过程中建立分区，使分区大小正好适合作业的需要，并且分区个数是可以调整的。当要装入一个作业时，根据作业需要的主存量，查看是否有足够的空闲空间，若有，则按需求量分割一部分给作业；若无；则作业等待。随着作业的装入、完成，主存空间被分割成许多大大小小的分区。有的分区被作业占用，有的分区空闲。
首次适应算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始循序查找，直到找到一个大小能满足要求的空闲分区为止。然后再按作业的大小，从该分区中划出一块内存空间，分配给请求者，余下的空闲分区仍然留在空闲链表。
最佳首次适应算法是将空闲分区按照其容量以从小到大的顺序排列成一个空闲分区链，这样第一次找到的能满足要求的空闲分区就是最佳的。
1.3开发平台
虚拟机：VMware
Linux坏境：Ubuntu
2总体设计
2.1功能模块
2.1.1 最佳适应算法
它从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区，这种方法能使碎片尽量小。为适应此算法，空闲分区表（空闲区链）中的空闲分区要按从小到大进行排序，自表头开始查找到第一个满足要求的*分区分配。该算法保留大的空闲区，但造成许多小的空闲区。
2.1.2 首次适应算法
首次适应算法从空闲分区表的第一个表目起查找该表，把最先能够满足要求的空闲区分配给作业，这种方法目的在于减少查找时间。为适应这种算法，空闲分区表(空闲区链)中的空闲分区要按地址由低到高进行排序。该算法优先使用低址部分空闲区，在低址空间造成许多小的空闲区，在高地址空间保留大的空闲区。该算法倾向于优先利用内存中低址部分的空闲分区，从而保留了高址部分的大空闲区，这为以后到达的大作业分配大的内存空间创造了条件。该算法是缺点是低址部分不断被划分，会留下许多难以利用的，很小的空闲分区，称为碎片。而每次查找又都是从低址部分开始的，这无疑又会增加查找可用空闲分区时的开销。
2.1.3 内存分配
系统应用某种分配算法，从空闲分区链中找到所需大小的分区。设请求的分区大小的为u.seze,表中的每个空闲分区的大小可以表示为m.size。若m.size≤size(size是事先给定的不在切割的剩余分区的大小)，说明分区太小，可不再切割，将整个分区分配给请求者。否则，便从该分区中安请求的大小划分出一块内存空间分配出去，余下的部分任留在空闲分区表中。然后将分配区的首地址返回给调用者使用。一首次适应算法为例运行流程图如图2.1。
2.2系统流程图
3 相关函数说明
3.1 malloc函数
3.1.1 相关原理阐述
malloc函数的实质体现在，它有一个将可用的内存块连接为一个长长的列表的所谓空闲链表。调用malloc函数时，它沿连接表寻找一个大到足以满足用户请求所需要的内存块。然后，将该内存块一分为二（一块的大小与用户请求的大小相等，另一块的大小就是剩下的字节）。接下来，将分配给用户的那块内存传给用户，并将剩下的那块（如果有的话）返回到连接表上。调用free函数时，它将用户释放的内存块连接到空闲链上。到最后，空闲链会被切成很多的小内存片段，如果这时用户申请一个大的内存片段，那么空闲链上可能没有可以满足用户要求的片段了。于是，malloc函数请求延时，并开始在空闲链上翻箱倒柜地检查各内存片段，对它们进行整理，将相邻的小空闲块合并成较大的内存块。
3.1.2 函数功能
void *malloc (long numbytes)：该函数负责分配 numbytes 大小的内存，并返回指向第一个字节的指针。用于申请一块连续的指定大小的内存块区域以void*类型返回分配的内存区域地址，当无法知道内存具体位置的时候，想要绑定真正的内存空间，就需要用到动态的分配内存，且分配的大小就是程序要求的大小。
3.1.3 流程图
图3.1 malloc函数原理流程图
3.2 fork函数
3.2.1 相关原理阐述
现在的Linux内核采用一种更为有效的方法，称之为写时复制（Copy On Write，COW）。这种思想相当简单：父进程和子进程共享页帧而不是复制页帧。然而，只要页帧被共享，它们就不能被修改，即页帧被保护。无论父进程还是子进程何时试图写一个共享的页帧，就产生一个异常，这时内核就把这个页复制到一个新的页帧中并标记为可写。原来的页帧仍然是写保护的：当其他进程试图写入时，内核检查写进程是否是这个页帧的唯一属主，如果是，就把这个页帧标记为对这个进程是可写的。
写时复制技术允许父子进程读相同物理页，只要两者中有一个试图写一个物理页，内核就把这个页的内容拷贝到一个新的物理页，并把这个物理页分配给正在写的进程。 轻量级进程允许父子空间共享进程在内核的许多数据结构，如页表（整个用户态地址空间）、打开文件表及信号处理。
fork系统调用用于创建一个新进程，称为子进程，它与进程（称为系统调用fork的进程）同时运行，此进程称为父进程。创建新的子进程后，两个进程将执行fork（）系统调用之后的下一条指令。子进程使用相同的pc（程序计数器），相同的CPU寄存器，在父进程中使用的相同打开文件。
3.3.2函数功能
fork()会从已经存在的进程中创建一个子进程，而原进程称为父进程。
3.2.3 流程图
3.3 _exit（0）函数
3.3.1 相关原理阐述
在Linux的标准函数库中，有一套称作”高级I/O”的函数，我们熟知的printf()、fopen()、fread()、fwrite()都在此 列，它们也被称作”缓冲I/O（buffered I/O）”，其特征是对应每一个打开的文件，在内存中都有一片缓冲区，每次读文件时，会多读出若干条记录，这样下次读文件时就可以直接从内存的缓冲区中读取，每次写文件的时候，也仅仅是写入内存中的缓冲区，等满足了一定的条件（达到一定数量，或遇到特定字符，如换行符和文件结束符EOF）， 再将缓冲区中的 内容一次性写入文件，这样就大大增加了文件读写的速度，但也为我们编程带来了一点点麻烦。如果有一些数据，我们认为已经写入了文件，实际上因为没有满足特 定的条件，它们还只是保存在缓冲区内，这时我们用_exit()函数直接将进程关闭，缓冲区中的数据就会丢失，反之，如果想保证数据的完整性，就一定要使用exit()函数。
3.3.2函数功能
直接使进程停止运行，清除其使用的内存空间，并销毁其在内核中的各种数据结构。
3.3.3 流程图
4详细设计
4.1 数据结构
/* 进程数据结构*/
int pid = 1421;
typedef struct process {
int pid;//进程编号
char pname[20];//进程名
int request;//进程所需要的内存空间
int address;//始地址
} Process;
/* 空闲区分表数据结构*/
typedef struct freeArea {
int state; //分区状态
int size; //分区大小
int ID; //分区编号
int address;//分区首地址
} Elemtype;
/* 空闲区分链数据结构*/
typedef struct Free_Node {
Elemtype date;
struct Free_Node *front;//前趋
struct Free_Node *next;//后继
} Free_Node,*FNodeList;4.2 排序算法
4.2.1 算法原理
这程序中多次用到排序算法，此次使用的冒泡排序算法。冒泡排序的原理是：重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
4.2.1 算法代码
void sortBySize() {
FNodeList p1 = head->next;
FNodeList p2 = p1->next;
FNodeList sw = p1;
while(p1) {
int size = 100000;
p2 = p1;
while(p2) {
if(p2->date.size<size) {
sw = p2;
size = p2->date.size;
}
p2 = p2->next;
}
Elemtype em;
em = p1->date;
p1->date = sw->date;
sw->date = em;
p1 = p1->next;
}
}
4.3 最佳适应算法
4.3.1 算法原理
它从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区，这种方法能使碎片尽量小。为适应此算法，空闲分区表（空闲区链）中的空闲分区要按从小到大进行排序，自表头开始查找到第一个满足要求的*分区分配。
4.2.1 算法代码
//最佳适应算法
void best_fit(Process pbc, int i) {
int flag = 0;
sortBySize();
FNodeList p = head->next;
while(p) {
if(p->date.state==Free&&p->date.size>=pbc.request) {
flag = 1;
if(p->date.size-pbc.request<=SIZE) { //多余空间太小不用分割
p->date.state = Busy;
break;
} else {
//为申请作业开辟新空间
FNodeList fnode = (FNodeList)malloc(sizeof(Free_Node));
fnode->date.size = pbc.request;
fnode->date.state = Busy;
fnode->date.ID = p->date.ID;
fnode->date.address = p->date.address;
p->date.address = fnode->date.address+fnode->date.size;
p->date.ID++;
p->date.size = p->date.size-fnode->date.size;
fnode->front = p->front;
p->front->next = fnode;
fnode->next = p;
p->front = fnode;
break;
}
}
p = p->next;
}
if(flag==0){
printf("第 %d 个作业因为内存不够分配失败。\n", i);
}else{
printf("第 %d 个作业分配成功。\n", i);
}
}
5心得体会
这一次课程设计，我主要负责实现创建数据结构，初始化链表，编写最佳适应算法。编程实现用的是C语言，我比较熟悉。而且所用的算法也比较简单。这次最大的难点是在于调用linux的系统函数。我们实现的存储器内存的分配，虽然查阅了大量的资料，但是还是没有把心中的想法给写出来。最后在老师修改要求好我们选择使用模拟的方式来完成此次课程设计。
这次课程设计与以往最大的不同是在linux环境下编译和运行代码。虽然好多技术宅的程序员都熟悉linux的操作，但是这确实是我第一次接触linux系统。经过这次课设我感觉打开了一扇新世界的大门。我会借着这次课程设计的机遇对linux的操作系统往深了挖。不仅是熟悉基本操作，而且有机会要看看内核代码。看看我们课本上的东西是怎么在linux系统上得到应用的。