操作系统课程设计连续动态分区内存管理模拟实现.docx
《操作系统课程设计连续动态分区内存管理模拟实现.docx》由会员分享，可在线阅读，更多相关《操作系统课程设计连续动态分区内存管理模拟实现.docx（32页珍藏版）》请在冰点文库上搜索。
操作系统课程设计连续动态分区内存管理模拟实现
操作系统课程设计--连续动态分区内存管理模拟实现
（操作系统课程设计）
连续动态分区内存
管理模拟实现
《操作系统》课程设计....................................................... 1
引言......................................................................3
课程设计目的和内容......................................................3
需求分析.........................................................................3
概要设计...................................................................3
开发环境........................................................................4
系统分析设计.....................................................................4
有关了解内存管理的相关理论..................................................4
内存管理概念........................................................................4
内存管理的必要性..............................................................4
内存的物理组织.............................................................4
什么是虚拟内存.................................................................5
连续动态分区内存管理方式...................................................5
单一连续分配（单个分区）...................................................5
固定分区存储管理...............................................................5
可变分区存储管理（动态分区）..............................................5
可重定位分区存储管理........................................................5
问题描述和分析....................................................................6
程序流程图........................................................................6
数据结构体分析..................................................................8
主要程序代码分析...............................................................9
分析并实现四种内存分配算法.................................................11
最先适应算.....................................................................11
下次适应分配算法..........................................................13
最优适应算法...............................................................16
最坏适应算法...............................................................18
回收内存算法................................................................20
调试与操作说明.................................................................22
初始界面.......................................................................22
模拟内存分配...............................................................23
已分配分区说明表面............................................................24
空闲区说明表界面.............................................................24
内存管理的必要性：
内存管理对于编写出高效率的Windows程序是非常重要的，这是因为Windows是多任务系统，它的内存管理和单任务的DOS相比有很大的差异。
DOS是单任务操作系统，应用程序分配到内存后，如果它不主动释放，系统是不会对它作任何改变的；但Windows却不然，它在同一时刻可能有多个应用程序共享内存，有时为了使某个任务更好地执行，Windows系统可能会对其它任务分配的内存进行移动，甚至删除。
因此，我们在Windows应用程序中使用内存时，要遵循Windows内存管理的一些约定，以尽量提高Windows内存的利用率。
1.3内存的物理组织：
物理地址：
把内存分成若干个大小相等的存储单元，每个存储单元占8位，称作字节（byte）。
每个单元给一个编号，这个编号称为物理地址（内存地址、绝对地址、实地址）。
二、物理地址空间：
物理地址的集合称为物理地址空间（主存地址空间），它是一个一维空间。
什么是虚拟内存：
虚拟内存是内存管理技术的一个极其实用的创新。
它是一段程序（由操作系统调度），持续监控着所有物理内存中的代码段、数据段，并保证他们在运行中的效率以及可靠性，对于每个用户层（user-level）的进程分配一段虚拟内存空间。
当进程建立时，不需要在物理内存件之间搬移数据，数据储存于磁盘内的虚拟内存空间，也不需要为该进程去配置主内存空间，只有当该进程被被调用的时候才会被加载到主内存。
连续动态分区内存管理方式的实现
在早期的操作系统中，主存分配广泛采用连续分配方式。
连续分配方式，是指为一个用户程序分配一个连续的内存空间，该连续内存空间指的的是物理内存。
下面介绍连续分配的四种方式。
单一连续分配（单个分区）
最简单的存储管理方式，用于多道程序设计技术之前。
内存分为系统区和用户区，系统区由操作系统使用。
用户区作为一个连续的分区分配给一个作业。
分区存储管理是满足多道程序设计的最简单的一种存储管理方法，它允许多4个用户程序同时存在系统内存中，即共享内存空间。
按分区划分方式可分为固定分区和可变分区。
固定分区存储管理
把内存的用户区预先划分成多个分区，每个分区大小可以相同，也可以不同。
（分区的划分由计算机的操作员或者由操作系统给出，并给出主存分配表）分区个数固定，分区的大小固定。
一个分区中可装入一个作业，作业执行过程中不会改变存放区域。
早期的IBM的OS/MFT（具有固定任务数的多道程序系统）采用了这种固定分区的方法。
可变分区存储管理（动态分区）
内存不是预先划分好的，而是在系统运行的过程中建立分区.当作业装入主存时，根据作业所需要的主存容量查看是否有足够的主存空间，若有则按需要分割一个分区给该作业；否则令该作业等待。
分区长度不固定分区个数不固定。
这种存储管理的方法克服了固定分区严重浪费主存的问题，提高了主存资源的利用率。
ＩＢＭ操作系统ＯＳ／ＭＶＴ采用可变分区存储管理。
可重定位分区存储管理
解决碎片问题的一种简单方法是采用可重定位分区分配.。
其中心思想是，把不同程序，且在内存中地址不连续的想法让他们连续。
例：
内存中现有3个空闲区，现有一作业到达，要求获得30k内存空间，没有分区满足容量要求，若想把作业装入，可将内存中所有作业进行移动，这样把原来分散的空闲区汇集成一个大的空闲区。
将内存中的作业进行移动使它们连接在一起把原来分散的多个小分区拼接成一个大的空闲区.这个过程称为”紧凑”或”移动”。
需解决的问题:
每次”紧凑”后程序或数据装入的物理地址变化采用动态重定位。
问题描述和分析
系统应利用某种分配算法，从空闲分区链表中找到所需大小的分区，如果空闲分区大小大于请求分区大小，则从该分区中按改请求的大小划分出一块内存空间大小划分出一块内存空间分配出去，余下的部分仍留在空闲链表中。
然后，将分配区的首址返回给调用者。
当进程运行完毕师范内存时，系统根据回收区的首址，从空闲区中找到相应的插入点，此时可能出现以下四种情况之一：
⑴该空闲区的上下两相邻分区都是空闲区：
将三个空闲区合并为一个空闲区。
新空闲区的起始地址为上空闲区的起始地址，大小为三个空闲区之和。
空闲区合并后，取消可用表或自由链中下空闲区的表目项或链指针，修改上空闲区的对应项。
⑵该空闲区的上相邻区是空闲区：
将释放区与上空闲区合并为一个空闲区，其起始地址为上空闲区的起始地址，大小为上空闲区与释放区之和。
合并后，修改上空闲区对应的可用表的表目项或自由链指针。
⑶该空闲区的下相邻区是空闲区：
将释放区与下空闲区合并，并将释放区的起始地址作为合并区的起始地址。
合并区的长度为释放区与下空闲区之和。
同理，合并后修改可用表或自由链中相应的表目项或链指针。
⑷两相邻区都不是空闲区：
释放区作为一个新空闲可用区插入可用表或自由链。
程序流程图
内存分配流程图，如图
内存回收流程图，如图
数据结构体分析
⑴进程属性结构体
typedefstructreadyque
{
charname[10];
intsize;
}readyque,*readyqueue;
⑵空闲链表结构体
typedefstructidlyspace
{
intfrom;
intsize;
idlyspace*next;
}idlyspace,*idly;
⑶已分配链表结构体
typedefstructbusyspace
{
intfrom;
readyquer;
busyspace*next;
}busyspace,*busy
主要程序代码分析
⑴主函数//代码请添加适当的注释。
intmain（）
{
Is=（idly）malloc（sizeof（idlyspace））;
Is->from=0;
Is->size=256;
Is->next=NULL;
Is2=Is;
Bs=（busy）malloc（sizeof（busyspace））;
Bs->next=NULL;
intt,t1;
printf（"\n.......................欢迎来到动态分区存储管理系统..................\n\n"）;
printf（"...........................请选择要执行的算法:
...........................\n"）;
printf（".........................1.最先适应算法...............................\n"）;
printf（".........................2.下次适应算法............................\n"）;
printf（"..........................3.最优适应算法...............................\n"）;
printf（".........................4.最坏适应算法................................\n"）;
printf（"........................................................................\n"）;
printf（"请输入您的选择:
"）;
scanf（"%d",&t）;
inti;
while（i!
=5）
{
printf（"........................................................................\n"）;
printf（".........................操作菜单如下：
（请选择）.......................n"）;
printf（"..........................1.输入进程分配空间...........................n"）;
printf（".........................2.进程撤销回收空间...........................\n"）;
printf（".........................3.输出所有空闲分区..........................\n"）;
printf（"..........................4.输出所有已分配分区..........................\n"）;
printf（"..........................5.退出..........................\n"）;
printf（"........................................................................\n"）;
scanf（"%d",&i）;
switch（i）
{
case1:
switch（t）
{
case1:
t1=FF（）;
break;
case2:
t1=NF（）;
break;
case3:
t1=BF（）;
break;
case4:
t1=WF（）;
break;
default:
printf（"选择算法错误\n"）;
return1;
}
if（t1）
printf（"分配空间成功\n"）;
else
printf（"分配空间失败\n"）;
break;
case2:
t1=recover（）;
if（t1）
printf（"回收成功\n"）;
else
printf（"回收失败\n"）;
break;
case3:
Isprint（）;
break;
case4:
Bsprint（）;
break;
}
}
return0;
}
第三章：
分析并实现四种内存分配算法
最先适应算法
空闲区按地址从小到大的次序排列。
分配：
当进程申请大小为SIZE的内存时，系统顺序查找空闲区表（链），直到找到容量满足要求（≥SIZE）的空闲区为止。
从该空闲区中划出大小为SIZE的分区分配给进程，余下的部分仍作为一个空闲区，但要修改其首址和大小。
优点：
这种算法是尽可能地利用低地址部分的空闲区，而尽量地保证高地址6部分的大空闲区，有利于大作业的装入。
缺点:
主存低地址和高地址分区利用不均衡。
在低地址部分集中了许多非常小的空闲区碎片降低了主存的利用率。
最先适应算法
intFF（）
{
intt=0;
readyqueD;
printf“"请输入进程名:
\”"）;
scanf“"%”",D.name）;
printf“"输入进程申请空间大小:
\”"）;
scanf“"%”",&D.size）;
idlyl=Is;
intmt=256;
busyb=Bs;
idlymin=NULL;
while（l）
//寻找空闲表中大小满足申请进程所需大小并且起址最小的空闲结点
{
if（D.size<=l->size）
{
if（l->from{mt=l->from;min=l;t=1;
}
}
l=l->next;
}
if（mt!
=256）//如果找到则为进程分配空间
{
busyj;
j=（busy）malloc（sizeof（busyspace））;
j->from=min->from;
for（inti=0;i<10;i++）
{
j->r.name[i]=D.name[i];
}
j->r.size=D.size;
while（b->next）
{if（b->next->fromfrom）
b=b->next;else
break;
}
j->next=b->next;
b->next=j;
min->from=min->from+D.size;
min->size=min->size-D.size;
}
returnt;
}
下次适应分配算法
最先适应算法的变种。
总是从空闲区上次扫描结束处顺序查找空闲区表（链），直到找到第一个满足容量要求的空闲区为止，分割一部分给作业，剩余部分仍作为空闲区。
下次适应分配算法
intNF（）
{
intt=0;
readyqueD;
printf“"请输入进程名:
\”"）;
scanf“"%”",D.name）;
printf“"输入进程申请空间大小:
\”"）;
scanf“"%”",&D.size）;
intmt=256;
idlyl=Is2;
idlymin=NULL;
busyb=Bs;
while（l）
//寻找空闲表中大小满足申请进程所需大小并且起址最小的空闲结点
{
if（D.size<=l->size）
{
if（l->from{mt=l->from;min=l;t=1;
}
}
l=l->next;
}
if（mt!
=256）//如果找到则为进程分配空间
{
busyj;
j=（busy）malloc（sizeof（busyspace））;
j->from=min->from;
for（inti=0;i<10;i++）
{
j->r.name[i]=D.name[i];
}
j->r.size=D.size;
while（b->next）
{if（b->next->fromfrom）
b=b->next;else
break;
}
//将申请空间进程插入到已分配链表中
j->next=b->next;
b->next=j;
//修改相应空闲节点的起址和大小
min->from=min->from+D.size;
min->size=min->size-D.size;
Is2=min->next;//ls2指向修改结点的下一个结点
t=1;
returnt;
}
l=Is;//l指向空闲表的头
while（l!
=Is2）//循环查找
{
if（D.size<=l->size）
{
if（l->from{mt=l->from;min=l;t=1;
}
}
l=l->next;
}
if（mt!
=256）
{
busyj;
j=（busy）malloc（sizeof（busyspace））;
j->from=min->from;
for（inti=0;i<10;i++）
{
j->r.name[i]=D.name[i];
}
j->r.size=D.size;
while（b->next）
{if（b->next->fromfrom）
b=b->next;else
break;
}
j->next=b->next;
b->next=j;
min->from=min->from+D.size;
min->size=min->size-D.size;
Is2=min->next;
t=1;
returnt;
}
returnt;
}
最优适应算法
空闲区按容量递增的次序排列。
分配：
当进程申请存储空间，系统顺序查找空闲区表（链），直到找到第一个满足容量要求的空闲区为止。
采用最优适应算法选中的空闲区是满足容量要求的最小空闲区。
优点：
选中的空闲区是满足容量要求的最小空闲区，而不致于毁掉较大的空闲区。
缺点：
空闲区的大小一般与申请分区大小不相等，因此将其一分为二，留下来的空闲区一般情况下是很小的，以致无法使用。
随着时间的推移，系统中的小空闲区会越来越多，从而造成存储空间的浪费。
最优适应算法
intBF（）
{
intt=0;
readyqueD;
printf“"请输入进程名:
\”"）;
scanf“"%”",D.name）;
printf“"输入进程申请空间大小:
\”"）;
scanf“"%”",&D.size）;
idlyl=Is;
idlymin=NULL;
intmt=256;
busyb=Bs;
while（l）
//在空闲链中寻找第一个大于所输入的进程大小的空闲块
{
if（D.size<=l->size）
{
if（l->size{
mt=l->size;min=l;t=1;
}
}
l=l->next;
}
if（mt!
=256）//找到第一个满足要求的空闲块
{
busyj;
j=（busy）malloc（sizeof（busyspace））;//申请分配用于存放进程的内存空间
j->from=min->from;
//将第一个满足要求的空闲块（min）的首地址赋给j
fo
升级会员 