精华内容
下载资源
问答
  • 内存分配方式与内存分配算法

    千次阅读 2018-03-14 20:24:56
    内存分配算法,其实就是:有一大块空闲的资源,如何合理地分配资源?内存分配的思想可以用到很多其他的领域。比如Java虚拟机是如何将内存分配与回收的?再比如文件系统是如何将磁盘块分配与回收的?其本质就是如何把...

    内存分配方式有两种,连续内存分配方式和离散内存分配方式。不同的分配方式又有不同的分配算法。

    内存分配算法,其实就是:有一大块空闲的资源,如何合理地分配资源?内存分配的思想可以用到很多其他的领域。比如Java虚拟机是如何将内存分配与回收的?再比如文件系统是如何将磁盘块分配与回收的?其本质就是如何把空闲的资源分配出去,分配之后又如何回收?目标就是分配快,回收也快,而且还不浪费。那么,就需要根据资源的特点、以及应用场景做权衡从而选择何种方式进行分配与回收。

    ①连续内存分配方式

    1)固定分区分配

    将内存划分成若干个固定大小的块。将程序装入块中即可。内存划分成各个块之后,块大小不再改变。当然,划分块的方式有:所有的块大小相等;划分的块大小不相等。

    这种方式,在实际的内存分配之前,就已经知道了所有的内存块大小了。

    2)动态分区分配

    需要一个空闲表 或者 空闲链 来记录目前系统中空间的内存区域。在内存分配时,需要查找空间表或空闲链找到一块内存分配给当前进程。

    动态分区分配算法:

    a)首次适应法

    b)循环首次适应法

    c)最佳适应法

    d)最坏适应法

    e)快速适应法

    3)可重定位分区分配

    说白了,就是增加了内存移动的功能。由于若干次内存分配与回收之后,各个空闲的内存块不连续了。通过“重定位”,将已经分配的内存“紧凑”在一块(就类似于JVM垃圾回收中的复制算法)从而空出一大块空闲的内存出来。

    ”紧凑“是需要开销的,比如需要重新计算 地址,这也为什么JVM垃圾回收会导致STW的原因。

    而离散分配方式–不管是分页还是分段,都是直接将程序放到各个离散的页中。从而就不存在“紧凑”一说了。

    连续内存分配方式涉及两种操作:内存分配操作 和 内存回收操作

    ②离散内存分配方式

    内存资源是有限的,程序要运行,必须得加载到内存。如果内存已经满了,而现在又有新的程序要运行,怎么办?—SWAP

    把当前不用的程序(数据)先换出内存,从而就有空间 加载当前需要运行的程序的一部分数据进入内存,这样大大提高了内存的利用率。

    由于牵涉到换入与换出,前面的连续内存分配方式就有点不适用了。因为,最明显的一个问题:对于连续内存分配方式,究竟换出哪部分数据呢?

    而这种只装入部分”数据”就可以使程序运行的机制,就是虚拟存储器的本质。

    1)分页存储管理

    将进程的逻辑地址空间分成若干大小相等的页面;同时,也将物理内存分成相等大小的页面(称为块或frame)。在为进程分配内存时,以块为单位将进程的若干页 可以 装入到内存中多个不邻接的物理块中。

    从上可以看出:“离散” 体现在:进程在内存中分配的空间(物理块)是不连续的。而对于连续分配方式,进程在内存的分配的空间是连续的。

    现在考虑32位系统,每个物理块的大小为4KB。如何把逻辑地址 转换成 物理地址?

    对每个进程而言,都有着自己的页表。页表的本质就是逻辑地址到物理地址的映射。

    分页存储中的逻辑地址的结构如下:

    这里写图片描述

    1)由于进程的逻辑页面大小与物理块(页帧)大小相同,故都为4K,因此需要12个位表示4K的大小(2^12=4K),即图中的【0-11】

    2)【12-31】表示的是页号。一共有20个位表示页号,也即:对于一个进程而言,一共可以有1M(2^20=1M)个页。

    3)每个进程的逻辑地址空间范围为0-2^32-1,因为:每个页大小为4K,一共有1M个页。故进程可用的逻辑空间为2^32B

    逻辑地址到物理地址的转换需要用到页表。具体细节是有一个“地址变换机构”,它有一个寄存器保存页表在内存的起始地址 以及 页表的长度。

    上面提到,一个进程最多可以有1M个页,故页表就有1M个页表项。假设每个页表项只有1B,那页表的大小也有1MB,所以:一般而言,页表也是很大的,不能全放在寄存器中,故页表也是存储在内存中的。(有些机器有“快表”,快表就是一个寄存器,它保存了页表中的部分表项);其次,也可以使用多级页表以解决单个页表太大的问题。

    那现在给定一个逻辑地址,怎么知道其物理地址呢?

    ①将【12-31】位的页号与 页表的长度比较。页号不能大于页表长度,否则越界。

    ②根据页号 找到 该页号所在的页表项,即该页号对应着哪个页表项。因为,页表项里面就存放着物理地址。

    那如何查找页表项呢?将页号乘以页表项的长度(每个页表项,其实就是一个逻辑的页 到 物理页 的映射信息),就知道了该逻辑页对应着哪个页表项(根据页号匹配页表项一般是由硬件完成的)

    然后,正如前面提到,页表也是保存在内存中的,故需要页表的内存始址(这是也为什么地址变换机构 保存 页表在内存的起始地址的原因),将页表始址 与 上面的乘积相加,就得到了该逻辑页对应的页表项的物理地址。读这个页表项的物理地址中的内容,就知道了该逻辑页对应的物理块地址(物理地址)。从而,就完成了逻辑地址到物理地址的转换。

    从上面可以看出,CPU每存取一个数据时,需要两次访问主存。一次是访问页表项的物理地址,得到了数据的物理块地址。第二次拿着物理块地址去取数据。

    在分页存储管理方式下:由于取一个数据,需要二次访存,CPU处理速度降低了一半,正由于这个原因:引入了“快表”(又称TLB(Translation Lookaside Buffer)),快表是个寄存器,用来保存那些当前访问过的页表项。从而,读页表项时,不需要再访存了,而是直接从寄存器中读取。

    虚拟存储器

    谈到虚拟存储器,总是说它从逻辑上扩充了内存的容量,why?

    内存是有限的,作业初始时保存在磁盘上的,如果要运行,必须得将相应的程序(数据)加载到内存中。那如果要运行的作业特别多,无法一下子装入内存,怎么办?

    一种方式是加内存条,这是从物理上扩充内存的容量。

    另一种方式是:先把作业的一部分程序(数据)装入内存,先让它运行着,运行过程中发现: 咦,我还需要其他的数据,而这些数据还未装入内存,因此就产生中断(缺页中断)再将数据加载到内存。

    采用这种方式,系统一次就可以将很多作业装入内存运行了。这时,从物理上看,内存还是原来的大小,但是它能运行的作业多了,因此说从逻辑上扩充了内存。

    将虚拟存储器这种思想与分页存储管理结合,一次只将作业的部分页面加载到内存中,形成了一个强大的内存分配与管理系统了。引入了虚拟存储器,同样需要有页表,记录逻辑地址到物理地址的映射,只不过此时的页表更复杂了,因为,有些页可能还在磁盘上。;还需要有缺页中断处理机构,因为毕竟只将一部分数据装入内存,会引起缺页中断嘛,就需要处理中断嘛;还需要地址变换机构,这里的地址变换机构功能更多,因为需要处理中断情况下的地址变换。

    转载自:https://www.cnblogs.com/hapjin/p/5689049.html

    展开全文
  • 掌握为实现多道程序并发...系统如何为进入内存的作业分配内存空间,实现多道作业同时驻留内存,就绪进程队列中的多个进程是如何以分式方式共享CPU,作业运行完成离开系统时,系统如何进行内存回收,计算进程周转时间。
  • 精品文档 课程设计报告 设计题目 内存的连续分配算法 班级 : 学号 姓名 指导老师 设计时间 摘要 精品文档 精品文档 1主要算法包括 固定分区分配动态分区分配伙伴算法可重定位分区分配 2 内容要求 1定义与算法相关的...
  • 课程设计报告 设计题目内存的连续分配算法 班级 : 学号 姓名 指导老师 设计时间 2012年8月 1 摘要 1主要算法包括 固定分区分配动态分区分配伙伴算法可重定位分区分配 2内容要求 1定义与算法相关的数据结构如PCB空闲...
  • 组号 成绩计算机操作系统课程设计报告题目 内存的连续分配算法基于动态分区分配的内存管理的...设计内容本系统模拟操作系统内存分配算法的实现,实现动态分区分配,算法,采用PCB定义结构体来表示一个进程,定义了进...

    组号 成绩

    计算机操作系统

    课程设计报告

    题目 内存的连续分配算法

    基于动态分区分配的内存管理的模拟设计与实现

    专业:

    班级:

    学号+姓名:

    指导教师:

    2016年12月 22 日

    一.设计目的

    掌握内存的连续分配方式的各种分配算法。

    二.设计内容

    本系统模拟操作系统内存分配算法的实现,实现动态分区分配,算法,采用PCB定义结构体来表示一个进程,定义了进程的名称和大小,进程内存起始地址和进程状态。内存分区表采用单链表来模拟实现。定义与算法相关的数据结构,如PCB,空闲分区;在使用动态分区分配算法时必须实现紧凑功能。

    三.设计原理

    1.首次适应算法分配内存:空闲分区链以地址递增的次序链接。进行内存分配时,从链首开始顺序查找,直到找到一个大小能满足要求的空闲分区为止。然后再按照作业的大小,从该分区中划出一块内存空间,分配给请求者,余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区,则表明系统中已没有足够大的内存分配给该进程,内存分配结束,返回。

    2.回收内存:当进程运行完毕释放内存时,系统根据回收区的首址,从空闲区链中找到相应的插入点:

    (1)回收区与插入点的前一个空闲分区F1相邻接,此时应将回收区与插入点的前一分区合并,不必为回收分区分配新表项,而只需要修改前一分区F1的大小。

    (2)回收区与插入点的后一个空闲分区F2相邻接,此时将两分区合并形成新的空闲分区,但用回收区的首址作为新空闲区的首址,大小为两者之和。

    (3)回收区与插入点的前后两个空闲分区相邻接,此时将三个分区合并,使用F1的表项和F1的首址,取消F2的表项,大小为三者之和。

    (4)回收区与插入点的前后两个空闲分区均不相邻接,此时应为回收区单独建立一个新表项,填写回收区的首址和大小,并根据其首址插入到空闲链中的适当位置。

    3.紧凑:将内存中的所有作业移动,使他们全都相邻接。可以把原来分散的多个空闲小分区拼接成一个大分区,可将一个作业装入该区。这种技术称为“紧凑”。

    四.详细设计及编码

    1.模块分析

    ①paixu():排序算法。按分区的起始位置以递增的次序排序。

    ②compact():紧凑算法。记录每个忙碌分区的首址及大小,改变其首址。计算所有空闲分区的大小为新空闲分区的大小,首址为所有忙碌分区的大小总和。

    ③show(FENQU *p):输出函数。输出分区信息(首址,大小,状态,进程号)。

    ④input():输入函数。输入分区信息(分区个数,各分区首址,大小,状态,进程号)。调用show(FENQU *p)函数。

    ⑤FENQU *scsf():(递归算法)首次适应算法。进行内存分配时,从链首开始顺序查找,直到找到一个大小能满足要求的空闲分区为止。调用compact()函数。

    ⑥FENQU * huishou():回收算法。当进程运行完毕释放内存时,系统根据回收区的首址,从空闲区链中找到相应的插入点,判断相应情况进行后续动作。

    ⑦void function():逻辑函数。从键盘输入选择,实现相应操作。调用scsf(),huishou(),show(p)函数。

    ⑧int main():主函数。调用input(),function()函数。

    流程图

    检索空闲分区链

    检索空闲分区链

    进行紧凑形成连续空闲区

    空闲分区总和≥u.size?

    N

    Y

    N

    找到>u.size的分区?

    无法分配,返回

    请求分配u.size分区

    修改有关的数据结构

    进行紧凑形成连续空闲区

    按动态分区方式进行分配

    Y

    返回分区号及首址

    代码实现

    #include

    #include

    #include

    typedef struct memory{

    int startaddress;//首址

    int size;//大小

    char state[10];//状态

    int number;//进程号

    struct memory *next;

    }FENQU;

    FENQU *ready=NULL, *p;

    void paixu();

    int len();

    void compact();

    void show(FENQU *p){

    printf("%d\t",p->startaddress);

    printf("%d\t",p->size);

    printf("%s\t",p->state);

    printf("%d\t\n\n",p->number);

    }

    //输入分区信息

    vo

    展开全文
  • 内存分配方式及分配算法优劣

    千次阅读 2020-08-30 09:31:05
    内部碎片的产生:因为所有的内存分配必须起始于可被 4、8 或 16 整除(视 处理器体系结构而定)的地址或者因为MMU的分页机制的限制,决定内存分配算法仅能把预定大小的内存块分配给客户。假设当某个客户请求一个 43 ...

    什么是内存碎片?

    内部碎片的产生:因为所有的内存分配必须起始于可被 4、8 或 16 整除(视 处理器体系结构而定)的地址或者因为MMU的分页机制的限制,决定内存分配算法仅能把预定大小的内存块分配给客户。假设当某个客户请求一个 43 字节的内存块时,因为没有适合大小的内存,所以它可能会获得 44字节、48字节等稍大一点的字节,因此由所需大小四舍五入而产生的多余空间就叫内部碎片。
    外部碎片的产生: 频繁的分配与回收物理页面会导致大量的、连续且小的页面块夹杂在已分配的页面中间,就会产生外部碎片。假 设有一块一共有100个单位的连续空闲内存空间,范围是0-99。如果你从中申请一块内存,如10个单位,那么申请出来的内存块就为0-9区间。这时候你 继续申请一块内存,比如说5个单位大,第二块得到的内存块就应该为10-14区间。如果你把第一块内存块释放,然后再申请一块大于10个单位的内存块,比 如说20个单位。因为刚被释放的内存块不能满足新的请求,所以只能从15开始分配出20个单位的内存块。现在整个内存空间的状态是0-9空闲,10-14 被占用,15-24被占用,25-99空闲。其中0-9就是一个内存碎片了。如果10-14一直被占用,而以后申请的空间都大于10个单位,那么0~9就 永远用不上了,变成外部碎片。

    内存分配方式

    内存分配方式主要有连续型分配方式和非连续型分配方式,顾名思义,连续型分配方式就是分配连续的空间,非连续型分配方式就是分配非连续的内存空间。

    -连续型分配内存方式:

    • 单一连续分配:
      最简单的分配方式,采用覆盖技术。优点是无外部碎片,缺点是只能用于单用户、有内部碎片、存储利用率低。
      内存在此方式下分为系统区和用户区,系统区仅提供给操作系统使用,通常在低地址部分;用户区是为用户提供的、除系统区之外的内存空间。这种方式无需进行内存保护。

    • 固定分区分配:
      最简单的多道程序存储管理方式,它将用户内存空间划分为若干个固定大小(可以相等,也可以不等,同为4的倍数或其他 如图1所示),每个分区只装入一道作业。图1
      为便于内存分配,通常将分区按大小排队,并为之建立一张分区说明表,其中各表项包括每个分区的起始地址、大小及状态(是否已分配),如图2所示。当有用户程序要装入时,便检索该表,以找到合适的分区给予分配并将其状态置为”已分配”;未找到合适分区则拒绝为该用户程序分配内存。存储空间的分配情况如图3所示。
      图2

    这种分区方式存在两个问题
    一是程序可能太大而放不进任何一个分区中,这时用户不得不使用覆盖技术来使用内存空间;
    二是主存利用率低,当程序小于固定分区大小时,也占用了一个完整的内存分区空间,这样分区内部有空间浪费,这种现象称为内部碎片

    固定分区是可用于多道程序设计最简单的存储分配,无外部碎片,但不能实现多进程共享一个主存区,所以存储空间利用率低。固定分区分配很少用于现在通用的操作系统中,但在某些用于控制多个相同对象的控制系统中仍发挥着一定的作用。

    -动态分区分配:
    不预先划分内存,在程序装入内存时,根据进程的大小动态地建立分区,并使得分区的大小正好适合进程的需要,因此系统中分区的大小和数目是可变的。
    图4
    如图4所示,系统有64MB内存空间,其中低8MB固定分配给操作系统,其余为用户可用内存。开始时装入前三个进程,在它们分别分配到所需空间后,内存只剩下4MB,进程4无法装入。
    在某个时刻,内存中没有一个就绪进程,CPU出现空闲,操作系统就换出进程2,换入进程4。由于进程4比进程2小,这样在主存中就产生了一个6MB的内存块。之后CPU又出现空闲,而主存无法容纳进程2,操作系统就换出进程1,换入进程2。

    动态分区分配内存方式刚开始是很好地,但是,之后会导致内存出现很多的小的内存块,也就是外部碎片。外部碎片可以通过紧凑来解决,就是操作系统不时地对进程进行移动和整理。 但是这需要动态重定位寄存器的支持,且相对费时。紧凑的过程实际上类似于Windows系统中的磁盘整理程序,只不过后者是对外存空间的紧凑。

    动态分区的分配策略

    在进程装入或换入主存时,如果内存中有多个足够大的空闲块,操作系统必须确定分配哪个内存块给进程使用,这就是动态分区的分配策略。

    1)首次适应:地址递增,顺序查找,第一个能满足的即分配给进程。

    2)最佳适应:容量递增,找到第一个能满足要求的空闲分区。

    3)最坏适应:容量递减,找到第一个能满足要求的分区。

    4)邻近适应:循环首次适应算法。

    在这几种方法中,首次适应算法不仅是最简单的,而且通常也是最好和最快的。 在UNIX 系统的最初版本中,就是使用首次适应算法为进程分配内存空间,其中使用数组的数据结构 (而非链表)来实现。不过,首次适应算法会使得内存的低地址部分出现很多小的空闲分区,而每次分配查找时,都要经过这些分区,因此也增加了查找的开销。

    邻近适应算法试图解决这个问题,但实际上,它常常会导致在内存的末尾分配空间(因为在一遍扫描中,内存前面部分使用后再释放时,不会参与分配),分裂成小碎片。它通常比首次适应算法的结果要差。

    最佳适应算法虽然称为“最佳”,但是性能通常很差,因为每次最佳的分配会留下很小的难以利用的内存块,它会产生最多的外部碎片。

    最坏适应算法与最佳适应算法相反,选择最大的可用块,这看起来最不容易产生碎片,但是却把最大的连续内存划分开,会很快导致没有可用的大的内存块,因此性能也非常差。

    Kunth和Shore分别就前三种方法对内存空间的利用情况做了模拟实验,结果表明:

    首次适应算法可能比最佳适应法效果好,而它们两者一定比最大适应法效果好
    另外注意,在算法实现时,分配操作中最佳适应法和最大适应法需要对可用块进行排序或遍历查找,而首次适应法和邻近适应法只需要简单查找
    回收操作中,当回收的块与原来的空闲块相邻时(有三种相邻的情况,比较复杂),需要将这些块合并。在算法实现时,使用数组或链表进行管理。除了内存的利用率,这里的算法开销也是操作系统设计需要考虑的一个因素。
    图6
    参考文献:
    1.内存分配方式及内存碎片
    2.8.内存连续分配方式采用的几种算法及各自优劣

    展开全文
  • 给予一块内存把三角形分配内存里面去。 要求: 三角形不能重叠,不能缩放,不能分割,不能变形。 可以旋转,反转。 使内存尽可能小,尽可能紧凑 1万个三角形尽可能耗时不超过0.6ms [img=...
  • 为一个用户程序分配连续的内存空间 早期的分类:单一连续分配 固定分区分配 动态分区分配 动态重定位分区分配 其他    1.单一连续分配  内存分为系统区(仅供给OS使用,通常放在内存的低址部分)和用户区...

    4---2

    二、连续分配方式

    为一个用户程序分配连续的内存空间

    早期的分类:单一连续分配  固定分区分配  动态分区分配  动态重定位分区分配 其他

     

       1.单一连续分配

         内存分为系统区(仅供给OS使用,通常放在内存的低址部分)和用户区(除系统区外的全部内存空间,提供给用户使用)两部分

         这是最简单的一种存储管理方式,只能用于单用户、单任务操作系统中

    优点  易于管理

    缺点  对要求内存空间少的程序,造成内存浪费;程序全部装入,很少使用的程序部分也占用内存。

       2.固定分区分配

         把内存分为一些大小相等或不等的分区,每个进程占用一个分区。操作系统占用其中的一个分区。

         提高:支持多个程序并发执行,适用于多道程序系统和分时系统。最早的多道程序存储管理方式。划分为几个分区,便只允许几道作业并发

     

         具体实现

         (1)如何划分分区大小

                       若分区大小相等,只适用于多个相同的并发执行(处理多个类型相同的对象),缺乏灵活性。

            若分区大小不等,多个小分区、适量的中等分区、少量的大分区。 根据程序大小,分配当前空闲的、适当大小的分区。

              (2)需要的数据结构

            建立一记录相关信息的分区表  表项有  |起始位置|大小|状态|

    分区表中,表项值随着内存的分配和释放而动态改变。

     

    (3)程序分配内存的过程

    也可将分区表分为两个表格:空闲分区表/占用分区表。从而减小每个表格长度。

    检索算法:空闲分区表可能按不同分配算法采用不同方式对表项排序(将分区按大小排队或按分区地址高低排序)。

    过程:检索空闲分区表;找出一个满足要求且尚未分配的分区,分配给请求程序;若未找到大小足够的分区,则拒绝为该用户程序分配内存。

     

    固定分配的不足:内碎片造成浪费     分区总数固定,限制并发执行的程序的数目

      3.动态分区分配

         分区大小不固定:在装入程序时根据进程实际需要,动态分配内存空间,即——需要多少划分多少。

         空闲分区表项:从1项到n项    内存会从初始的一个大分区不断被划分、回收从而形成内存中的多个分区。

     

      优点:并发进程数没有固定数的限制,不产生内碎片。

      缺点:有外碎片(分区间无法利用的空间)。

     

      具体实现

      (1)分区分配中的数据结构

              <1>空闲分区表:

    记录每个空闲分区的情况。

    每个空闲分区对应一个表目,包括分区序号、分区始址及分区的大小等数据项。

    <2>空闲分区链:

    每个分区的起始部分,设置用于控制分区分配的信息,及用于链接各分区的前向指针;

    分区尾部则设置一后向指针,在分区末尾重复设置状态位和分区大小表目方便检索。

      (2)分区分配算法

             动态分区方式,分区多、大小差异各不相同,此时把一个新作业装入内存,更需选择一个合适的分配算法,从空闲分区表中选出一合适分区

    <1>首次适应算法FF

    <2>循环首次适应算法

    <3>最佳适应算法

    <4>最差适应算法

    <5>快速适应算法

     

    <1>首次适应算法FF

    空闲分区排序:以地址递增的次序链接。

    检索:分配内存时,从链首开始顺序查找直至找到一个大小能满足要求的空闲分区;

    分配:从该分区中划出一块作业要求大小的内存空间分配给请求者,余下的空闲分区大小改变仍留在空闲链中。

    !!若从头到尾检索不到满足要求的分区则分配失败

     

    优点:优先利用内存低址部分,保留了高地址部分的大空闲区

    缺点:但低址部分不断划分,会产生较多小碎片;而且每次查找从地址部分开始,会逐渐增加查找开销。

     

      <2>循环首次适应算法

    • 空闲分区排序:按地址
    • 检索:从上次找到的空闲分区的下一个空闲分区开始查找,直到找到一个能满足要求的空闲分区。为实现算法,需要:

    设置一个起始查寻指针

    采用循环查找方式

    • 分配:分出需要的大小

      优点:空闲分区分布均匀,减少查找开销

    缺点:缺乏大的空闲分区

     

    <3>最佳适应算法

       总是把能满足要求、又是最小的空闲分区分配给作业

     

     

     

     

     

    • 空闲分区排序:所有空闲分区按容量从小到大排序成空闲分区表或链。
    • 检索:从表或链的头开始,找到的第一个满足的就分配
    • 分配:分出需要的大小

    缺点:每次找到最合适大小的分区割下的空闲区也总是最小,会产生许多难以利用的小空闲区(外碎片)

     

    <4>最差适应算法/最坏匹配算法

       基本不留下小空闲分区,但会出现缺乏较大的空闲分区的情况。

     

    <5>快速适应算法

    根据进程常用空间大小进行划分,相同大小的串成一个链,需管理多个各种不同大小的分区的链表。进程需要时,从最接近大小需求的链中摘一个分区。类似的:伙伴算法

    能快速找到合适分区,但链表信息会很多;实际上是空间换时间。

     

     (3)分区分配操作

    分配内存

    ·找到满足需要的合适分区,划出进程需要的空间

       ··if s<=size,将整个分区分配给请求者

    ··if s> size,按请求的大小划出一块内存空间分配出去,余下部分留在空闲链中,将分配区首址返回给调用者。

     

    回收内存

    ·进程运行完毕释放内存时,系统根据回收区首址a,在空闲分区链(表)中找到相应插入点,根据情况修改空闲分区信息,可能会进行空闲分区的合并:

     

    动态连续分配方式无法解决“外碎片”问题

     

     

    若当前内存分配有3个小碎片,分别为30K,64K,40K。若有一个120K的作业申请一块连续空间,无法满足。

    解决思路:移动分区位置,将小碎片整合为一个足够大小可被使用的分区。即紧凑思想

    因此出现

    4.动态重定位分区分配——有紧凑功能的动态分区分配

    用户程序在内存中移动,将空闲空间紧凑起来提高空间利用率。但必然需要地址变化,增加“重定位”工作。

     

     

    地址变换过程是在程序执行过程期间(相对地址与重定位寄存器中的地址相加),随着对每条指令的访问自动进行,称为动态重定位。

    动态重定位分区分配算法与动态分区分配算法基本相同,差别在于增加了紧凑的功能。

     

     

    伙伴系统

    ·分区大小有规定,且分区动态变化

    1)无论已分配还是空闲分区,大小都为2的k次幂。若整个可分配空间大小为2的m次幂,则1≤k≤m.

    2)随着系统运行,内存被不断划分,形成若干不连续的空闲分区。对每一类具有相同大小的空闲分区设置一双向链表,即会有k个链表,链表中的分区大小都是2m。

    3)进程申请n个大小的空间时,计算n= 2i。则找i对应的链表。若i大小的链表没有,则找i+1的链表。找到的分区对半划分后,一半用于分配,一半链接到较小一级的链表里去。

    4)一次分配和回收都可能对应多次的划分和合并。

     

    找合适的链的方法:哈希算法

     

     

     

     

    5.内存空间管理之对换

    当内存空间还是满足不了需求时,引入“对换”

    把内存中暂时不能运行、或暂时不用的程序和数据调到外存上,以腾出足够的内存;把已具备运行条件的进程和进程所需要的程序和数据,调入内存。

     

     

    按对换单位分类:

    整体对换(或进程对换):以整个进程为单位(连续分配)

    页面对换或分段对换:以页或段为单位(离散分配)

     

    实现进程对换,系统必须具备的功能:

    对换空间的管理

    进程的换出、换入操作

     

    在系统中设置相应的数据结构以记录对换区的使用情况

    对换空间的分配与回收是连续方式,与动态分区方式时的内存分配与回收雷同。

    展开全文
  • 动态分区分配算法5.1首次适应算法5.2最佳适应算法5.3最坏适应算法5.4邻近适应算法5.5总结6.基本分页存储管理6.1把“固定分区分配“改造为”非连续分配版本“6.2分页存储管理的基本管理6.3如何实现地址的转换?6.4...
  • 动态分区分配算法

    千次阅读 2019-06-21 21:40:30
    掌握动态分区分配方式中的数据结构、分配算法,针对不同的分配算法如何实现内存空间的分配与回收,必要时如何实现“紧凑”。
  • 内存分配方式与内存分配算法 内存分配方式有两种,连续内存分配方式和离散内存分配方式。不同的分配方式又有不同的分配算法。 内存分配算法,其实就是:有一大块空闲的资源,如何合理地分配资源?内存分配的思想...
  • 动态内存分配之循环首次适应算法

    千次阅读 2016-12-22 17:11:04
    1.已分配区和空闲区是分别表示的 2.采用的是单向链表 3.采用了尾指针tail,单纯的用来指向尾空闲区域 4.写了3天,好吧,我确实很菜,但是引用请注明出处,谢谢了 #include #include #include <malloc.
  • 内存分配方式

    千次阅读 2018-05-05 20:14:42
    不同的分配方式又有不同的分配算法。①连续内存分配方式1)固定分区分配将内存划分成若干个固定大小的块。将程序装入块中即可。内存划分成各个块之后,块大小不再改变。当然,划分块的方式有:所有的块大小相等;...
  • 操作系统的课程设计报告...用C语言编写的程序,实现了可重定向动态分区分配算法,选取首次适应算法,实现紧凑功能,用单链表模拟内存状态。因为网上几乎没有紧凑功能的代码,所以自己写了,希望造福人类。可能有些小bug
  • 分配功能:要求至少使用两种算法,用户可以选择使用。 回收功能: 空闲块的合并:即紧凑功能,用以消除碎片。当做碎片整理时,需要跟踪分配的空间,修改其引用以保证引用的正确性。 显示当前内存的使用状态...
  • 进程分配内存空间让其正常支行的三种方式: 1)连续内存分配(为一个进程分配一片连续的内存空间) 2)非连续内存分配 3)虚拟内存管理 连续内存分配方案 ...关于动态内存分配的管理算法这里不作记
  • 内部碎片的产生:因为所有的内存分配必须起始于可被 4、8 或 16 整除(视 处理器体系结构而定)的地址或者因为MMU的分页机制的限制,决定内存分配算法仅能把预定大小的内存块分配给客户。假设当某个客户请求一个 43 ...
  • 深入理解Java虚拟机-垃圾回收器与内存分配策略

    万次阅读 多人点赞 2020-01-04 13:08:32
    Java与C++之间有一堵由内存动态分配和垃圾收集技术所围成的"高墙",墙外面的人想进去,墙里面的人却想出来。 文章目录概述对象已死吗引用计数法可达性分析算法再谈引用生存还是死亡回收方法区垃圾收集算法标记-清除...
  • 内存管理之内存分配

    千次阅读 2013-07-24 14:11:37
     连续分配方式指的是为一个用户程序划分为连续的内存空间。可以把连续分配方式进一步分为单一连续分配、固定分区分配、动态分区分配和可重定位分区分配四种方式。 1.单一连续分配  在单道程序系统中,任何时刻只有...
  • 在划分时,若剩余的内存小于等于minsize,则将整块内存分配给该进程不再进行划分。 根据菜单选择相应的操作: 1.初始化:输入内存的大小和阈值minsize,初始状态下空闲分区名字为“void”。 2.分配:输入申请进程的...
  • 1:连续内存分配 1.计算机体系结构和内存层次
  • 用C++实现一个完整的(可变)动态分区管理器,包括分配,回收,分区碎片整理等。实现如下功能: 1.初始化功能:内存状态设置为初始状态。 2.分配功能:要求至少使用两种算法,用户可以选择使用...该算法分配和释放的
  • C#内存分配

    2013-06-22 23:10:07
    在32位的Windows操作系统中,每个进程都可以使用4GB的内存,这得益于虚拟寻址技术,在这4GB的内存中存储着可执行代码、代码加载的DLL和程序运行的所有变量,在C#中,虚拟内存中有个两个存储变量的区域,一个称为堆栈...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 15,534
精华内容 6,213
关键字:

内存分配算法紧凑