课程设计报告设计题目：内存的连续分配算法班级: 1003学号：211011023姓名：指导老师：设计时间：2012年8月摘要1、主要算法包括：固定分区分配、动态分区分配、伙伴算法、可重定位分区分配。

2、内容要求：1）定义与算法相关的数据结构，如PCB，空闲分区表；2）至少实现两种以上分配算法，且用户可以选择在某次执行过程中使用何种算法；3）在使用动态分区分配或可重定位分区分配算法时必须实现紧凑和对换功能；4）动态分区分配和可重定位分区分配必选一个实现。

本系统模拟了操作系统内存分配算法的实现，实现了固定分区分配和动态分区分配，以及可重定位分区分配算法，采用PCB 定义结构体来表示一个进程，定义了进程的名称和大小，进程内存起始地址和进程状态。

内存分区表采用单链表来模拟实现。

关键词：固定分区分配、动态分区分配、可重定位分区分配。

目录1. 概述 (4)2. 课程设计任务及要求2.1 设计任务 (4)2.2 设计要求 (4)3. 算法及数据结构3.1算法的总体思想（流程） (5)3.2 PCB模块3.2.1 功能（运算） (5)3.2.2 数据结构（存储结构） (5)3.2.3 算法（实现） (5)3.3 进程队列模块3.3.1功能 (6)3.3.2 数据结构 (6)3.3.3算法 (6)4. 程序设计与实现4.1 程序流程图 (7)4.2 程序说明（代码）4.3 实验结果 (9)5. 结论 (10)6. 参考文献。

(10)7. 收获、体会和建议。

(10)一：概述本系统模拟了操作系统内存分配算法的实现，实现了固定分区分配和动态分区分配，以及可重定位分区分配算法，采用PCB定义结构体来表示一个进程，定义了进程的名称和大小，进程内存起始地址和进程状态。

内存分区表采用单链表来模拟实现。

固定分区实现就是将单链表的每个节点的大小设为固定大小，系统默认如果按固定分区分配的话，只能分成20个相等大小的分区，因此系统只能最多运行20个进程。

动态分区的实现是根据进程所申请的内存大小来决定动态的有系统进行分配内存空间大小，因此分区表里的空闲分区个数是不定的，根据进程数和进程大小决定的。

可重定位分区算法比动态分区算法增加了紧凑和进程对换的功能。

二：课程设计任务及要求设计任务：使用C++ MFC实现模拟操作系统内存分配算法的实现，定义结构体数据结构表示进程，定义单链表表示内存分区表。

设计要求：定义与算法相关的数据结构，如PCB，空闲分区表；至少实现两种以上分配算法，且用户可以选择在某次执行过程中使用何种算法；在使用动态分区分配或可重定位分区分配算法时必须实现紧凑和对换功能；动态分区分配和可重定位分区分配必选一个实现。

三：算法及数据结构#define free 0 //表示进程状态空闲#define busy 1 //表示进程状态忙typedef int Status; //表示进程状态struct PCB //表示进程PCB结构体{CString name; //进程nameStatus status; //进程状态busy or freeint lStartAddres; //进程起始地址int Size; //进程大小};struct Node //表示组成链表的结点结构体{PCB data;Node *next;};class Queue //表示分区表的单链表类{public:Queue();~Queue(){}//void Show(); //内存区分配情况显示int GetLength();int GetAllFree(); //获得所有空闲分区总大小void InitialMemory(int ); //初始化内存区域大小void FixedPartitonAlloc(); //固定分区分配初始化空闲内存链表bool AllocProFixed(CString ,int ); //为进程分配内存(执行固定分区分配算法)bool AllocProDynamic(CString ,int ); //为进程分配内存（动态分区分配）bool FreeMemory(CString ); //释放进程内存bool AllMerge(int); //内存紧凑分区算法bool Swaping(int ,PCB&); //进程对换算法Node *GetFirst(); //返回头结点void Clear(); //链表节点清除private:Node *first;};#include "StdAfx.h"#include "Queue.h"Queue::Queue(){//默认头结点数据first = new Node;first->data.lStartAddres=0;first->="";first->data.Size=0;first->data.status=busy;first->next=NULL;}int Queue::GetLength(){int n=0;Node *p=first;while(p->next){p=p->next;n++;}return n;}Node *Queue::GetFirst(){return first;}int Queue::GetAllFree(){int n=0;Node *p=first;while(p->next){p=p->next;if (p->data.status==free){n+=p->data.Size;}}return n;}//void Queue::Show()// Node *p=first;// while(p->next)// {// p=p->next;// cout<<"分区号："<<p-><<endl;// cout<<"分区状态："<<(p->data.status==busy ?"busy":"free")<<endl;// cout<<"分区起始地址："<<p->data.lStartAddres<<endl;// cout<<"分区大小："<<p->data.Size<<endl;// cout<<"--------------------------------\n";// }//}void Queue::InitialMemory(int i){PCB tmp;="";tmp.status=free;tmp.lStartAddres=0;tmp.Size=i;Node *s=new Node;s->data=tmp;first->next=s;s->next=NULL;}void Queue::Clear(){Node *q;Node *p=first->next;while(p->next){q=p;p=p->next;delete q;}}void Queue::FixedPartitonAlloc() {PCB tmp;int AllSize=first->next->data.Size;int perSize=AllSize/20;first->next->data.Size=perSize;Node *p= first;for (int i=1;i<20;i++){while(p->next){p=p->next;}="";tmp.status=free;tmp.lStartAddres=i*perSize+1;tmp.Size=perSize;Node *s= new Node;s->data=tmp;p->next=s;s->next=NULL;}}bool Queue::AllocProFixed(CString _name,int _size) {PCB tmp;Node *p= first;while(p->next){p=p->next;if (p->data.Size>=_size&&p->data.status==free){p->=_name;p->data.status=busy;return true;}}return false;}void Queue::SortList(){Node *p=NULL;Node *q=NULL;for(p=first->next;p->next;p=p->next)for (q=p->next;q;q=q->next){if (p->data.Size>q->data.Size){PCB tmp;tmp=p->data;p->data=q->data;q->data=tmp;}}}//动态分区分配算法(最佳适应算法)bool Queue::AllocProDynamic(CString _name,int _size) {Node *p=first;Node *q=NULL; //用来记录最佳插入点位置int ch=0; //用来记录最小碎片值while(p->next){p=p->next;//分区大小正好和进程大小相等if (p->data.status==free&&p->data.Size==_size){p->=_name;p->data.status=busy;return true;}if (p->data.status==free&&p->data.Size>_size) {ch=p->data.Size-_size;q=p;break;}/*//分区大小大于进程大小，分割分区，并按大小分区排序if (p->data.Size>_size&&p->data.status==free) {Node *s=new Node;int tmp=p->data.Size-_size;if (tmp>_size){s->data.lStartAddres=p->data.lStartAddres;s->data.Size=_size;s->=_name;s->data.status=busy;p->data.lStartAddres+=_size;p->data.Size=tmp;s->next=q->next;q->next=s;SortList(); //对分区链表进行按大小有小到大排序return true;}else{s->data.lStartAddres=p->data.lStartAddres+tmp;s->=_name;s->data.Size=_size;s->data.status=busy;p->data.Size=tmp;s->next=p->next;p->next=s;SortList(); //对分区链表进行按大小有小到大排序return true;}*/}while(p){if (p->data.status==free&&p->data.Size>=_size) {if (p->data.Size-_size<ch){ch=p->data.Size-_size;q=p;}}p=p->next;}if(q==NULL){return false;}else{Node *s=new Node;s->data.lStartAddres=q->data.lStartAddres+ch;s->=_name;s->data.Size=_size;s->data.status=busy;q->data.Size=ch;s->next=q->next;q->next=s;return true;}}bool Queue::FreeMemory(CString _name){Node *p=first;Node *q;while(p->next){q=p;p=p->next;if (p->==_name){p->="";p->data.status=free;//进行相邻分区合并if (q->data.status==free){q->data.Size+=p->data.Size;q->next=p->next;}//判断是否为链表尾if (p->next!=NULL){if (p->next->data.status==free){p->data.Size+=p->next->data.Size;p->next=p->next->next;}}return true;}}return false;}bool Queue::AllMerge(int _size){Node *p=first;Node *q;int sum=0;bool flag=true; //标志是否为第一次找到free分区while(p->next){while(p->next){q=p;p=p->next;if (p->data.status==free&&flag){sum=p->data.Size;q->next=p->next;flag=false;break;}if (!flag&&p->data.status==busy){//对数据进行重定位p->data.lStartAddres-=sum;}if (p->data.status==free&&!flag) {p->data.Size+=sum;//对数据进行重定位p->data.lStartAddres-=sum;if (p->data.Size>=_size){return true;}q->next=p->next;sum=p->data.Size;break;}}while(p){q=p;p=p->next;if (p->data.status==free){p->data.Size+=sum;//对数据进行重定位p->data.lStartAddres-=sum;if (p->data.Size>_size){return true;}q->next=p->next;sum=p->data.Size;break;}else{//对数据进行重定位p->data.lStartAddres-=sum;}}}return false;}bool Queue::Swaping(int needSize ,PCB &pro) {Node *p=first;//Node *q;while(p->next){p=p->next;if (p->data.Size>=needSize){pro=p->data;p->="";p->data.status=free;return true;}}return false;}四：程序设计与实现。