第一篇：页式存储管理方案中的内存分配
页式存储管理方案中的内存分配
用户提出内存空间申请，按一定策略检查内存空间，找出满足请求的空闲页面，分给申请者
1首先接收输入文件：
（1）内存空闲物理页面文件（文本文件），包括若干行，每行2项（起始
物理页面号，连续的物理页面数）
（2）进程占用物理内存数据文件（文本文件），包括若干行，若干项（进
程号，物理页面号1，物理页面号2，……）建立空闲页面表，并在屏幕显示输出该表内容 20行
该表中记录了内存中可供分配的空闲页面的起始页号和连续空闲的页面数 3为每个进程建立一个页表，并在屏幕显示输出每个页表的内容
页表记录了每个进程逻辑页面与物理页面的对应关系在用户界面根据用户提示接收一个内存申请，格式为：进程名，申请空间大小（单位为K字节）为该进程建立一个页表，显示输出该表内容，检查空闲页面表，为该进程分配相应的物理页面，并修改有关的数据结构（空闲页面表，页表）假设页面大小为4K重复4，5直到输入特殊字符（0）在屏幕显示输出最新的空闲页面表内容
第二篇：可变分区存储管理方式的内存分配和回收
#include
#include
#include
#include
const int MJ=10;//假定系统允许的最大作业数量为10
typedef struct node{
int address;
int length;
char tag[10];
}job;
job frees[MJ];
int free_quantity;
job occupys[MJ];
int occupy_quantity;
int read()
{
FILE *fp;
char fn[10];
cout<<“请输入初始空闲表文件名:”;
cin>>fn;
if((fp=fopen(fn,“r”))==NULL){ 其意义是在当前目录下打开文件file a，只允许进行“读”操作，并使fp指向该文件
cout<<“错误,文件打不开,请检查文件名”< } else{ while(!feof(fp)){ fscanf(fp,“%d,%d”,&frees[free_quantity].address,&frees[free_quantity].length);free_quantity++;fscanf(文件指针，格式字符串，输入表列)； } return 1; } return 0; } void sort() { int i,j,p; for(i=0;i p=i; for(j=i+1;j if(frees[j].address p=j; } } if(p!=i){ frees[free_quantity]=frees[i]; frees[i]=frees[p]; frees[p]=frees[free_quantity]; } } } void view() { int i; cout< cout<<“输出空闲区表：n起始地址 分区长度状态n”< for(i=0;i cout.setf(2); cout.width(12); cout< cout.width(10); cout< cout.width(8); cout< } cout< cout<<“输出已分分区表：n起始地址 分区长度 占用作业名n”< for(i=0;i cout.setf(2); cout.width(12); cout< cout.width(10); cout< cout.width(8); cout< } } void ear() { char job_name[10]; int job_length; int i,j,flag,t; cout<<“请输入分配内存的作业名和空间大小:”; cin>>job_name; cin>>job_length; flag=0; for(i=0;i if(frees[i].length>=job_length){ flag=1; } } if(flag==0){//未找到空闲区，返回 cout< } else{ t=0; i=0; while(t==0){ if(frees[i].length>=job_length){//找到可用空闲区，开始分配 t=1; } i++; } i--; occupys[occupy_quantity].address=frees[i].address;//修改已分配区表 strcpy(occupys[occupy_quantity].tag,job_name); occupys[occupy_quantity].length=job_length; occupy_quantity++; if(frees[i].length>job_length){ frees[i].address+=job_length; frees[i].length-=job_length; } else{ for(j=i;j frees[j]=frees[j+1]; } free_quantity--; cout<<“内存空间成功:)”< } } } void reclaim()//回收作业所占的内存空间 { char job_name[20]; int i,j,flag,p=0; int address; int length;//寻找已分分区表中对应的登记项 cout<<“输入要回收分区的作业名:”; cin>>job_name; flag=-1; for(i=0;i if(!strcmp(occupys[i].tag,job_name)){ flag=i; address=occupys[i].address; length=occupys[i].length; } } if(flag==-1){ //在已分分区表中找不到作业 cout<<“没有这个作业名”< } else{//修改空闲区表，加入空闲表 for(i=0;i if((frees[i].address+frees[i].length)==address){ if(((i+1) for(j=i+1;j frees[j]=frees[j+1]; } free_quantity--; p=1; } else{ frees[i].length+=length; p=1; } } if(frees[i].address==(address+length)){ frees[i].address=address; frees[i].length+=length; p=1; } } if(p==0){ frees[free_quantity].address=address; frees[free_quantity].length=length; free_quantity++; }//删除分配表中的该作业 for(i=flag;i occupys[i]=occupys[i+1]; } occupy_quantity--; } } void main() { int flag=0; int t=1; int chioce=0; int i; for(i=0;i frees[i].address=-1;//空闲区表初始化 frees[i].length=0; strcpy(frees[i].tag,“free”); occupys[i].address=-1;//已分分区表初始化 occupys[i].length=0; strcpy(occupys[i].tag,“"); } free_quantity=0; occupy_quantity=0; flag=read(); while(flag==1){ sort(); cout<<”选择功能项:（0-退出，1-分配内存，2-回收内存，3-显示内存）n“< cin>>chioce; switch(chioce){ case 0: flag=0; break; case 1: ear(); break; case 2: reclaim(); break; case 3: view(); break; default: cout<<”没有该选项n"< } } } 栈, 临时变量，大小有限制,函数返回后就被回收 堆，可以动态分配，大小可近似认为无限制，可以一直存在 堆：malloc(), free()需要自己申请与自己负责释放!适用于事先不知道需要分配多大空间的情况。 栈：void fun(int x){int y;...}系统帮你分配与释放。 /////////////////////////////////////////////////////////////////// 一个由C/C++编译的程序占用的内存分为以下几个部分 1、栈区（stack）— 由编译器自动分配释放，存放函数的参数值，局部变量的值等。其 操作方式类似于数据结构中的栈。 2、堆区（heap）— 一般由程序员分配释放，若程序员不释放，程序结束时可能由OS回 收。注意它与数据结构中的堆是两回事，分配方式倒是类似于链表，呵呵。 3、全局区（静态区）（static）—，全局变量和静态变量的存储是放在一块的，初始化的 全局变量和静态变量在一块区域，未初始化的全局变量和未初始化的静态变量在相邻的另 一块区域。已初始化全局/静态变量，在整个软件执行过程中有效；.bss函数调用栈，其中的内容在函数执行期间有效，并由编译器负责分配和收回； .heap程序结束后由系统释放。 4、文字常量区 —常量字符串就是放在这里的。程序结束后由系统释放 5、程序代码区—存放函数体的二进制代码。 二、堆和栈的理论知识 2.1申请方式 stack: 由系统自动分配。例如，声明在函数中一个局部变量 int b;系统自动在栈中为b开辟空间 heap: 需要程序员自己申请，并指明大小，在c中malloc函数 如p1 =(char *)malloc(10);在C++中用new运算符 如p2 = new char[10];但是注意p1、p2本身是在栈中的。 2.2 申请后系统的响应 栈：只要栈的剩余空间大于所申请空间，系统将为程序提供内存，否则将报异常提示栈溢 出。 堆：首先应该知道操作系统有一个记录空闲内存地址的链表，当系统收到程序的申请时，会遍历该链表，寻找第一个空间大于所申请空间的堆结点，然后将该结点从空闲结点链表 中删除，并将该结点的空间分配给程序，另外，对于大多数系统，会在这块内存空间中的 首地址处记录本次分配的大小，这样，代码中的delete语句才能正确的释放本内存空间。 另外，由于找到的堆结点的大小不一定正好等于申请的大小，系统会自动的将多余的那部 分重新放入空闲链表中。 2.3申请大小的限制 栈：在Windows下,栈是向低地址扩展的数据结构，是一块连续的内存的区域。这句话的意 思是栈顶的地址和栈的最大容量是系统预先规定好的，在WINDOWS下，栈的大小是2M（也有 的说是1M，总之是一个编译时就确定的常数），如果申请的空间超过栈的剩余空间时，将 提示overflow。因此，能从栈获得的空间较小。 堆：堆是向高地址扩展的数据结构，是不连续的内存区域。这是由于系统是用链表来存储 的空闲内存地址的，自然是不连续的，而链表的遍历方向是由低地址向高地址。堆的大小 受限于计算机系统中有效的虚拟内存。由此可见，堆获得的空间比较灵活，也比较大。 2.4申请效率的比较： 栈由系统自动分配，速度较快。但程序员是无法控制的。 堆是由new分配的内存，一般速度比较慢，而且容易产生内存碎片,不过用起来最方便.另外，在WINDOWS下，最好的方式是用VirtualAlloc分配内存，他不是在堆，也不是在栈是 直接在进程的地址空间中保留一块内存，虽然用起来最不方便。但是速度快，也最灵活。 2.5堆和栈中的存储内容 栈： 在函数调用时，第一个进栈的是主函数中后的下一条指令（函数调用语句的下一条可 执行语句）的地址，然后是函数的各个参数，在大多数的C编译器中，参数是由右往左入栈 的，然后是函数中的局部变量。注意静态变量是不入栈的。 当本次函数调用结束后，局部变量先出栈，然后是参数，最后栈顶指针指向最开始存的地 址，也就是主函数中的下一条指令，程序由该点继续运行。 堆：一般是在堆的头部用一个字节存放堆的大小。堆中的具体内容由程序员安排。 2.6存取效率的比较 char s1[] = “aaaaaaaaaaaaaaa”;char *s2 = “bbbbbbbbbbbbbbbbb”;aaaaaaaaaaa是在运行时刻赋值的； 而bbbbbbbbbbb是在编译时就确定的； 但是，在以后的存取中，在栈上的数组比指针所指向的字符串(例如堆)快。 比如： #include void main(){ char a = 1;char c[] = “1234567890”; char *p =“1234567890”;a = c[1];a = p[1];return;} 对应的汇编代码 10: a = c[1]; 00401067 8A 4D F1 mov cl,byte ptr [ebp-0Fh] 0040106A 88 4D FC mov byte ptr [ebp-4],cl 11: a = p[1]; 0040106D 8B 55 EC mov edx,dword ptr [ebp-14h] 00401070 8A 42 01 mov al,byte ptr [edx+1] 00401073 88 45 FC mov byte ptr [ebp-4],al 第一种在读取时直接就把字符串中的元素读到寄存器cl中，而第二种则要先把指针值读到 edx中，再根据edx读取字符，显然慢了。 2.7小结： 堆和栈的区别可以用如下的比喻来看出： 使用栈就象我们去饭馆里吃饭，只管点菜（发出申请）、付钱、和吃（使用），吃饱了就走，不必理会切菜、洗菜等准备工作和洗碗、刷锅等扫尾工作，他的好处是快捷，但是自由度小。 使用堆就象是自己动手做喜欢吃的菜肴，比较麻烦，但是比较符合自己的口味，而且自由度大。(经典！) 一．实验目的 通过编写和调试存储管理的模拟程序以加深对存储管理方案的理解，熟悉可变分区存储管理的内存分配和回收。二．实验内容 1．确定内存空间分配表； 2．采用最优适应算法完成内存空间的分配和回收； 3．编写主函数对所做工作进行测试。 三．实验背景材料 实现可变分区的分配和回收，主要考虑的问题有三个：第一，设计记录内存使用情况的数据表格，用来记录空闲区和作业占用的区域；第二，在设计的数据表格基础上设计内存分配算法；第三，在设计的数据表格基础上设计内存回收算法。 首先，考虑第一个问题，设计记录内存使用情况的数据表格，用来记录空间区和作业占用的区域。 由于可变分区的大小是由作业需求量决定的，故分区的长度是预先不固定的，且分区的个数也随内存分配和回收变动。总之，所有分区情况随时可能发生变化，数据表格的设计必须和这个特点相适应。由于分区长度不同，因此设计的表格应该包括分区在内存中的起始地址和长度。由于分配时空闲区有时会变成两个分区：空闲区和已分分区，回收内存分区时，可能会合并空闲分区，这样如果整个内存采用一张表格记录己分分区和空闲区，就会使表格操作繁琐。分配内存时查找空闲区进行分配，然后填写己分配区表，主要操作在空闲区；某个作业执行完后，将该分区变成空闲区，并将其与相邻的空闲区合并，主要操作也在空闲区。由此可见，内存的分配和回收主要是对空闲区的操作。这样为了便于对内存空间的分配和回收，就建立两张分区表记录内存使用情况，一张表格记录作业占用分区的“己分分区表”；一张是记录空闲区的“空闲区表”。这两张表的实现方法一般有两种：一种是链表形式，一种是顺序表形式。在实验中，采用顺序表形式，用数组模拟。由于顺序表的长度必须提前固定，所以无论是“已分分区表”还是“空闲区表”都必须事先确定长度。它们的长度必须是系统可能的最大项数。 “已分分区表”的结构定义 #define n 10 //假定系统允许的最大作业数量为n struct { float address;//已分分区起始地址 float length;//已分分区长度、单位为字节 int flag;//已分分区表登记栏标志，“0”表示空栏目，实验中只支持一个字符的作业名 }used_table[n];//已分分区表 “空闲区表”的结构定义 #define m 10 //假定系统允许的空闲区最大为m struct { float address;//空闲区起始地址 float length;//空闲区长度、单位为字节 int flag;//空闲区表登记栏标志，“0”表示空栏目，“1”表示未分配 }used_table[n];//空闲区表 第二，在设计的数据表格基础上设计内存分配。 装入一个作业时，从空闲区表中查找满足作业长度的未分配区，如大于作业，空闲区划 第1页 分成两个分区，一个给作业，一个成为小空闲分区。 实验中内存分配的算法采用“最优适应”算法，即选择一个能满足要求的最小空闲分区。第三，在设计的数据表格基础上设计内存回收问题。内存回收时若相邻有空闲分区则合并空闲区，修改空闲区表。 四、参考程序 #define n 10 //假定系统允许的最大作业数量为n #define m 10 //假定系统允许的空闲区最大为m #define minisize 100 struct { float address;//已分分区起始地址 float length;//已分分区长度、单位为字节 int flag;//已分分区表登记栏标志，“0”表示空栏目，实验中只支持一个字符的作业名 }used_table[n];//已分分区表 struct { float address;//空闲区起始地址 float length;//空闲区长度、单位为字节 int flag;//空闲区表登记栏标志，“0”表示空栏目，“1”表示未分配 }used_table[n];//空闲区表 allocate(J,xk)//采用最优分配算法分配xk大小的空间 char J;float xk;{int i,k;float ad;k=-1;for(i=0;i //找到可用空闲区，开始分配；若空闲区大小与要求分配的空间差小于minisize大小，则空闲区全部分配； //若空闲区大小与要求分配的空间差大于minisize大小，则从空闲区划分一部分分配 if(free_table[k].length-xk<=minisize){free_table[k].flag=0;ad=free_table[k].address; 第2页 xk=free_table[k].length;} else {free_table[k].length=free_table[k].length-xk;ad=free_table[k].address+free_table[k].length;} //修改已分配区表 i=0;while(used_table[i].flag!=0&&i reclaim(J)//回收作业名为J的作业所占的内存空间 char J: {int i,k,j,s,t;float S,L;//寻找已分分区表中对应的登记项 S=0;while((used_table[S].flag!=J||used_table[S].flag==0)&&S used_table[S].flag=0;//取得归还分区的起始地址S和长度L S=used_table[S].address;L=used_table[S].length;j=-1;k=-1;i=0; 第3页 //寻找回收分区的上下邻空闲区，上邻表目K，下邻表目J while(i {free_table[k].length=free_table[j].length+free_table[k].length+L;free_table[j].flag+0;} else //上邻空闲区，下邻非空闲区，与上邻合并 free_table[k].length=free_table[k].length+L;else if(j!=-1)//上邻非空闲区，下邻空闲区，与下邻合并 {free_table[j].address=S;free_table[j].length=free_table[j].length+L;} else { //上下邻均为非空闲区，回收区域直接填入 t=0;//在空闲区表中寻找空栏目 while(free_table[t].flag==1&&t {printf(“内存空闲表没有空间，回收空间失败n”);used_table[S].flag=J;return;} free_table[t].address=s;free_table[t].length=l;free_table[t].flag=1;} return(true);} //内存回收函数结束 main(){ int i,a;float xk;char J;//空闲区表初始化 free_table[0].address=10240; 第4页 free_table[0].length=102400;free_table[0].flag=1;for(i=1;i case 1;//a=1 分配内存空间 printf(“输入作业名J和作业所需长度XK：”);scanf(“%c%c%f”,&j,&xk);allocate(j,xk);//分配内存空间 break;case 2;//a=2 回收内存空间 printf(“输入要回放分区的作业名”);scanf(“%c%c”,&j);reclaim(j);//回收内存空间 break;case 3;//a=3显示内存情况，输出空闲区表和已分分区表 printf(“输出空闲区表：n起始地址 分区长度 标志n”);for(i=0;i 第5页 实验三 可变分区存储管理方式的内存分配回收 一．实验目的 （1）深入了解可变分区存储管理方式的内存分配回收的实现。 二．实验内容 编写程序完成可变分区存储管理方式的内存分配回收，要求有内存空间分配表，并采用最优适应算法完成内存的分配与回收。 三．实验原理 在可变分区模式下，在系统初启且用户作业尚未装入主存储器之前，整个用户区是一个大空闲分区，随着作业的装入和撤离，主存空间被分成许多分区，有的分区被占用，而有的分区时空闲的。为了方便主存空间的分配和去配，用于管理的数据结构可由两张表组成：“已分配区表”和“未分配区表”。在“未分配表中”将空闲区按长度递增顺序排列，当装入新作业时，从未分配区表中挑选一个能满足用户进程要求的最小分区进行分配。这时从已分配表中找出一个空栏目登记新作业的起始地址和占用长度，同时修改未分配区表中空闲区的长度和起始地址。当作业撤离时已分配区表中的相应状态变为“空”，而将收回的分区登记到未分配区表中，若有相邻空闲区再将其连接后登记。可变分区的回收算法较为复杂，当一个作业撤离时，可分为4种情况：其临近都有作业（A和B），其一边有作业（A或B），其两边均为空闲区。尤其重要的是，在程序中利用“new类型T（初值列表）”申请分配用于存放T类型数据的内存空间，利用“delete指针名”释放指针所指向的内存空间。 四．实验部分源程序 #include int start,end;// 起始，结束 int length;// 长度大小 struct SNode *next;// 指向下一结点的指针 }* SP;SP Head=(SP)malloc(sizeof(SNode));// 全局变量，内存空间头结 void DispSpace(){ // 显示内存空间分配情况 SP p=Head->next; cout<<“n 空闲区说明表 n” <<“---地址--长度---n”; while(p) { cout<<“ ”< start <<“ ”< length< p=p->next; } cout<<“----------------n”;} void Initial(){ // 初始化说明表 SP p,q; p=(SP)malloc(sizeof(SNode)); q=(SP)malloc(sizeof(SNode)); p->start=14;p->length=12;p->end=26; q->start=32;q->length=96;q->end=128;// 指导书上的作业分配 Head->next=p;// 与头结点连接 p->next=q; q->next=NULL; DispSpace();} void Allocation(int len){ // 分配内存给新作业 SP p=Head->next,q; while(p){ if(p->length < len) p=p->next; else if(p->length > len) { p->start=p->start+len; p->length=p->length-len; cout<<“分配成功!n”; DispSpace();return; } else {//当两者长度相等 q=p->next; p->next=q->next; cout<<“分配成功!n”; DispSpace();return; } } cout<<“分配失败!n”; DispSpace();return;} void CallBack(int sta,int len){ // 回收内存 SP p=Head,q=p->next,r;// 开始地址和长度 p->end=0; int en=sta+len; while(q){ if(sta == 0){ // 初始地址为0 if(en == q->start){ // 正好回收 q->start=0; q->length=q->end; return; } else { r=(SP)malloc(sizeof(SNode)); r->start=sta;r->length=len;r->end=en; p->next=r; r->next=q; return; } } else if((p->end < sta)&&(q->start > en)){ // 上邻区 r=(SP)malloc(sizeof(SNode)); r->start=sta;r->length=len;r->end=en; p->next=r; r->next=q; return; } else if((p->end < sta)&&(q->start == en)){ // 邻区相接 q->start=sta; q->length=q->end-sta; return; } else if((p->end == sta)&&(q->start < en)){ // 下邻区 p->end=en; p->length=en-p->start; return; } else if(p->end==sta && q->start==en){ // 邻区相接 p->end=q->end; p->length=p->end-p->start; p->next=q->next; return; } else { p=p->next; q=q->next; } } } void main(){ Initial(); cout<<“现在分配大小为 6K 的作业 4 申请装入主存: ”; Allocation(6);// 分配时参数只有长度 //--------指导书测试数据演示---------- cout<<“现回收作业 3(起址10,长度4)n”; CallBack(10,4); DispSpace(); cout<<“现回收作业 2(起址26,长度6)n”; CallBack(26,6); DispSpace(); //---------------演示结束------------- system(“pause”);} 五．实验结果与体会 我的体会：第三篇：编程中内存分配总结
第四篇：可变分区存储管理方式的内存分配和回收实验报告
第五篇：操作系统实验报告-可变分区存储管理方式的内存分配回收
点击咨询 