主存空间的分配和回收 采用可变分区管理.doc

主存空间的分配和回收 采用可变分区管理1、 采用可变分区管理，使用首次获最佳适应算法实现主存的分配和回收要求采用分区说明表进行。提示：（1）可变式分区管理是指在处理作业过程中建立分区，使分区大小正好适合作业的需要，并且分区个数是可以调整的。当要装入一个作业时，根据作业需要的主存量，查看是否有足够的空闲空间，若有，则按需求量分割一部分给作业；若无，则作业等待。随着作业的装入、完成，主存空间被分割成许多大大小小的分区。有的分区被作业占用，有的分区空闲。例如，某时刻主存空间占用情况如图3-1所示。为了说明哪些分区是空闲的，可以用来装入新作业，必须要有一张空闲区说明表，如图3-2所示。图3-1 内存空闲分区图长度起始地址状态32k20k未分配8k72k未分配120k100k未分配331k320k未分配空表目空表目图3-2 空闲区说明表其中，起始地址指出各空闲区的主存起始地址，长度指出空闲区的大小。状态：未分配-该栏目记录的是有效的空闲区；空表目-没有登记信息。由于分区数目不定，所以空闲区说明表中应有足够的空表目项。否则造成溢出，无法登记。同样，再设一个已分配区表，记录作业或进程的主存占用情况。（2）当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。有时找到的空闲区可能大于作业需求量，这时应将空闲区一分为二。一个分给作业；另一个仍作为空闲区留在空闲区表中。为了尽量减少由于分割造成的碎片，尽可能分配低地址部分的空闲区，将较大空闲区留在高地址端，以利于大作业的装入。为此在空闲区表中，按空闲区首地址从低到高进行登记。为了便于快速查找，要不断地对表格进行紧缩，即让“空表目”项留在表的后部。（3）当一个作业执行完成时，作业所占用的分区应归还给系统。在归还时要考虑相邻空闲区合并的问题。作业的释放区与空闲区的邻接分以下四种情况考虑： 释放区下邻（低地址邻接）空闲区； 释放区上邻（高地址邻接）空闲区 释放区上下都与空闲区邻接； 释放区与空闲区不邻接。（4）请按首次（或最佳）适应分配算法设计主存分配和回收程序。自己设计一个作业申请队列及作业完成后的释放顺序，实现主存的分配和回收。把空闲区说明表的变化情况以及各作业的申请、释放情况显示或打印出来。/*/* 分段内存管理* date:2007-12-2*/#include #include using namespace std;#define MAX_MEM 256 /内存总量#define OS_MEM 60 /系统占用内存#define TOTLE_LEFT 196 /除系统占用内存外的剩余内存/空闲分区表节点struct Free int start; int length; Free(int s,int l);Free:Free(int s,int l) start = s; length = l;/已分配分区表节点struct Task string name; int start; int length; Task(string n,int s,int l);Task:Task(string n,int s,int l) name = n; start = s; length = l;/声明空闲分区表list free_list;list task_list;/分配可用起始地址int get_free(int size) int start = -1; /查找适当的空闲分区 list:iterator it=free_list.begin(); bool find = false; while(it!=free_list.end() if(*it)-length=size) find=true; start = (*it)-start; /大于就分割把低地址分配出去 if(*it)-lengthsize) (*it)-start += size; (*it)-length -= size; /等于就从空闲分区中删掉 else free_list.erase(it); break;/找到就跳出循环 it+; return start;void do_request(string name,int size) if(name=SYSTEM) cout 申请不合法！非法进程名！ TOTLE_LEFT) cout 申请不合法！超出最大可用内存！ endl; return; /查找是否已存在同名进程 bool find = false; list:iterator it=task_list.begin(); while(it!=task_list.end() if(*it)-name=name) find=true; break; it+; if(find) cout 此进程已存在！ endl; return; /从空闲分区选择合适的空间 int start=get_free(size); /未找到合适空间 if(start=-1) cout 系统内存不足！进程等待！ endl; return; Task *ta = new Task(name,start,size); task_list.push_back(ta); cout 进程申请内存成功！ endl;/插入到空闲分区表,按照起始地址从小到大void free_task(int start,int length) /查找要插入的位置 list:iterator init_it,last_it; last_it = init_it; list:iterator it=free_list.begin(); while(it!=free_list.end() if(*it)-start start) break; last_it = it; it+; bool link_prev=false; bool link_next=false; /有前一个时 if(last_it!= init_it) if(*last_it)-start+(*last_it)-length = start) link_prev = true; /有后一个时 if(it!=free_list.end() if(start+length=(*it)-start) link_next = true; /与前后都相连 if(link_prev & link_next) (*last_it)-length += length + (*it)-length; free_list.erase(it); /只与前相连 else if(link_prev) (*last_it)-length += length; /只与后相连 else if(link_next) (*it)-start = start; (*it)-length += length; /前后都不相连 else Free *fr = new Free(start,length); free_list.insert(it,fr); void do_revoke(string name) if(name=SYSTEM) cout 错误！不能回收系统内存！ endl; return; /查找要回收的进程是否存在 bool find = false; list:iterator it=task_list.begin(); while(it!=task_list.end() if(*it)-name=name) find=true; break; it+; if(!find) cout 错误！要回收的进程不存在！ start,(*it)-length); task_list.erase(it); cout 回收进程占用内存成功！ endl;void print_task() cout 进程名称 起始地址 大小 endl; for(list:iterator it=task_list.begin();it!=task_list.end();it+) cout name start length endl; void print_free() cout 以下是空闲分区表的状态 endl 起始地址 大小 endl; for(list:iterator it=free_list.begin();it!=free_list.end();it+) cout start length endl; int main() /把系统占用后剩余的内存空间计入空闲分区表 Free *fr = new Free(OS_MEM,TOTLE_LEFT); free_list.push_back(fr); Task *ta = new Task(SYSYEM,0,OS_MEM); task_list.push_back(ta); print_free(); bool quit=false; while(!quit) cout ; int op; cin op; if(op=1) cout name; cin size; do_request(name