动态分区存储管理算法分配与回收实现

⑴ System memory是什么意思

System memory是系统存储器的意思。存储系统是指计算机中由存放程序和数据的各种存储设备、控制部件及管理信息调度的设备（硬件）和算法（软件）所组成的系统。

计算机存储系统的核心是存储器，存储器是计算机中必不可少、用来存储程序和数据的记忆设备。内部存储器（简称内存）主要存储计算机当前工作需要的程序和数据，包括高速缓冲存储器（Cache，简称缓存）和主存储器。目前构成内存的主要是半导体存储器。

外部存储器（简称外存）主要有磁性存储器、光存储器和半导体存储器三种实现方式，存储介质有硬磁盘、光盘、磁带和移动存储器等。

(1)动态分区存储管理算法分配与回收实现扩展阅读

分配存储管理

1、单一连续分配

在单道程序环境下，内存分为系统区和用户区，系统区只留给OS时候，放在低地址部分，用户区仅装有一道用户程序。

2、固定分区分配

将内存的用户空间划分为若干个固定大小的分区，，并为之建立一张分区使用表，包含每个分区的起始地址，大小，状态.

3、动态分区分配

要实现动态分区分配，必须解决分区所用的数据结构，分区分配算法和分区的分配与回收这三个问题。

⑵ 在分页存储管理方式下应怎样实现主存空间的分配和回收

2.1 模拟包括3部分：
1）实现特定的内存分配算法
2）实现内存回收模拟
3）每种内存分配策略对应的碎片数统计
2.2 固定分区存储管理
假设内存容量为120KB，并且分别划分成8,16,32,64KB大小的块各一块。
一个进程所需要的内存为0到100个KB。同时假设一个进程在运行过程中所需内存的大小不变。
模拟五个进程到达请求分配与运行完回收情况,输出主存分配表.
2.3 动态分区分配存储管理
采用连续分配方式之动态分区分配存储管理，使用首次适应算法、下次适应算法、最佳适应算法和最坏适应算法4种算法完成设计(任选两种算法)。

⑶ 动态分区分配算法实现报告理解在动态分区分配存储管理方式下怎样实现主存

创建程序，用梯形图编程语言创建一个与模板相连结或与模板无关的程序并存储用户管理器设置，用户管理器用于分配和控制用户的单个组态和运行系统编辑器的

⑷ 分区存储管理中常用哪些分配策略

1、固定分区存储管理
其基本思想是将内存划分成若干固定大小的分区，每个分区中最多只能装入一个作业。当作业申请内存时，系统按一定的算法为其选择一个适当的分区，并装入内存运行。由于分区大小是事先固定的，因而可容纳作业的大小受到限制，而且当用户作业的地址空间小于分区的存储空间时，造成存储空间浪费。

一、空间的分配与回收

系统设置一张“分区分配表”来描述各分区的使用情况，登记的内容应包括：分区号、起始地址、长度和占用标志。其中占用标志为“0”时，表示目前该分区空闲；否则登记占用作业名（或作业号）。有了“分区分配表”，空间分配与回收工作是比较简单的。

二、地址转换和存储保护

固定分区管理可以采用静态重定位方式进行地址映射。

为了实现存储保护，处理器设置了一对“下限寄存器”和“上限寄存器”。当一个已经被装入主存储器的作业能够得到处理器运行时，进程调度应记录当前运行作业所在的分区号，且把该分区的下限地址和上限地址分别送入下限寄存器和上限寄存器中。处理器执行该作业的指令时必须核对其要访问的绝对地址是否越界。

三、多作业队列的固定分区管理

为避免小作业被分配到大的分区中造成空间的浪费，可采用多作业队列的方法。即系统按分区数设置多个作业队列，将作业按其大小排到不同的队列中，一个队列对应某一个分区，以提高内存利用率。

2、可变分区存储管理
可变分区存储管理不是预先将内存划分分区，而是在作业装入内存时建立分区，使分区的大小正好与作业要求的存储空间相等。这种处理方式使内存分配有较大的灵活性，也提高了内存利用率。但是随着对内存不断地分配、释放操作会引起存储碎片的产生。

一、空间的分配与回收

采用可变分区存储管理，系统中的分区个数与分区的大小都在不断地变化，系统利用“空闲区表”来管理内存中的空闲分区，其中登记空闲区的起始地址、长度和状态。当有作业要进入内存时，在“空闲区表”中查找状态为“未分配”且长度大于或等于作业的空闲分区分配给作业，并做适当调整；当一个作业运行完成时，应将该作业占用的空间作为空闲区归还给系统。

可以采用首先适应算法、最佳（优）适应算法和最坏适应算法三种分配策略之一进行内存分配。

二、地址转换和存储保护

可变分区存储管理一般采用动态重定位的方式，为实现地址重定位和存储保护，系统设置相应的硬件：基址/限长寄存器（或上界/下界寄存器）、加法器、比较线路等。

基址寄存器用来存放程序在内存的起始地址，限长寄存器用来存放程序的长度。处理机在执行时，用程序中的相对地址加上基址寄存器中的基地址，形成一个绝对地址，并将相对地址与限长寄存器进行计算比较，检查是否发生地址越界。

三、存储碎片与程序的移动

所谓碎片是指内存中出现的一些零散的小空闲区域。由于碎片都很小，无法再利用。如果内存中碎片很多，将会造成严重的存储资源浪费。解决碎片的方法是移动所有的占用区域，使所有的空闲区合并成一片连续区域，这一技术称为移动技术（紧凑技术）。移动技术除了可解决碎片问题还使内存中的作业进行扩充。显然，移动带来系统开销加大，并且当一个作业如果正与外设进行I/O时，该作业是无法移动的。

3、页式存储管理

基本原理

1．等分内存

页式存储管理将内存空间划分成等长的若干区域，每个区域的大小一般取2的整数幂，称为一个物理页面有时称为块。内存的所有物理页面从0开始编号，称作物理页号。

2．逻辑地址

系统将程序的逻辑空间按照同样大小也划分成若干页面，称为逻辑页面也称为页。程序的各个逻辑页面从0开始依次编号，称作逻辑页号或相对页号。每个页面内从0开始编址，称为页内地址。程序中的逻辑地址由两部分组成：

逻辑地址
页号p
页内地址 d

3．内存分配

系统可用一张“位示图”来登记内存中各块的分配情况，存储分配时以页面（块）为单位，并按程序的页数多少进行分配。相邻的页面在内存中不一定相邻，即分配给程序的内存块之间不一定连续。

对程序地址空间的分页是系统自动进行的，即对用户是透明的。由于页面尺寸为2的整数次幂，故相对地址中的高位部分即为页号，低位部分为页内地址。

3.5.2实现原理

1．页表

系统为每个进程建立一张页表，用于记录进程逻辑页面与内存物理页面之间的对应关系。地址空间有多少页，该页表里就登记多少行，且按逻辑页的顺序排列，形如：

逻辑页号
主存块号

0
B0

1
B1

2
B2

3
B3

2．地址映射过程

页式存储管理采用动态重定位，即在程序的执行过程中完成地址转换。处理器每执行一条指令，就将指令中的逻辑地址（p,d）取来从中得到逻辑页号(p)，硬件机构按此页号查页表，得到内存的块号B’，便形成绝对地址（B’,d）,处理器即按此地址访问主存。

3．页面的共享与保护

当多个不同进程中需要有相同页面信息时，可以在主存中只保留一个副本，只要让这些进程各自的有关项中指向内存同一块号即可。同时在页表中设置相应的“存取权限”，对不同进程的访问权限进行各种必要的限制。

4、段式存储管理

基本原理

1．逻辑地址空间

程序按逻辑上有完整意义的段来划分，称为逻辑段。例如主程序、子程序、数据等都可各成一段。将一个程序的所有逻辑段从0开始编号，称为段号。每一个逻辑段都是从0开始编址，称为段内地址。

2．逻辑地址

程序中的逻辑地址由段号和段内地址（s,d）两部分组成。

3．内存分配

系统不进行预先划分，而是以段为单位进行内存分配，为每一个逻辑段分配一个连续的内存区（物理段）。逻辑上连续的段在内存不一定连续存放。

3．6．2实现方法

1．段表

系统为每个进程建立一张段表，用于记录进程的逻辑段与内存物理段之间的对应关系，至少应包括逻辑段号、物理段首地址和该段长度三项内容。

2．建立空闲区表

系统中设立一张内存空闲区表，记录内存中空闲区域情况，用于段的分配和回收内存。

3．地址映射过程

段式存储管理采用动态重定位，处理器每执行一条指令，就将指令中的逻辑地址（s,d）取来从中得到逻辑段号(s)，硬件机构按此段号查段表，得到该段在内存的首地址S’， 该段在内存的首地址S’加上段内地址d，便形成绝对地址（S’+d），处理器即按此地址访问主存。

5、段页式存储管理

页式存储管理的特征是等分内存，解决了碎片问题；段式存储管理的特征是逻辑分段，便于实现共享。为了保持页式和段式上的优点，结合两种存储管理方案，形成了段页式存储管理。

段页式存储管理的基本思想是：把内存划分为大小相等的页面；将程序按其逻辑关系划分为若干段；再按照页面的大小，把每一段划分成若干页面。程序的逻辑地址由三部分组成，形式如下：

逻辑地址
段号s
页号p
页内地址d

内存是以页为基本单位分配给每个程序的，在逻辑上相邻的页面内存不一定相邻。

系统为每个进程建立一张段表，为进程的每一段各建立一张页表。地址转换过程，要经过查段表、页表后才能得到最终的物理地址。

⑸ 【我的笔记】内存管理（二）分区方法（静态、动态、伙伴、Slab）

由操作系统或系统管理员预先将内存划分成若干个分区。在系统运行过程中，分区的边界不再改变。分配时，找一个空闲且足够大的分区。如没有合适的分区：①让申请者等待。②先换出某分区的内容，再将其分配出去。

为申请者分配指定的分区或任选一个分区。如果没有空闲分区，可将一个分区的内容换出。可能需要重定位。

会出现内部碎片，无法满足大内存的需求。

可减少内部碎片。减少对大内存需求的限制。

①固定分配：只分配某种尺寸的特定分区，如分区已被使用，申请者必须等待。

可能出现不公平等待：虽有更大尺寸的空闲分区，却必须等待。

②最佳适应分配：分配能满足需要的最小尺寸的空闲分区，只有当所有分区都已用完时，申请者才需要等待。灵活，但可能产生较大的内部碎片。

3、静态分区：内存利用率低，产生内部碎片；尺寸和分区数量难以确定。

1、不预先确定分区的大小和数量，将分区工作推迟到实际分配内存时进行。  Lazy

初始情况下，把所有的空闲内存看成一个大分区。分配时，按申请的尺寸，找一块足够大的空闲内存分区，临时从中划出一块构成新分区。新分区的尺寸与申请的大小相等，不会出现内部碎片。回收时，尽可能与邻近的空闲分区合并。在内存紧缺时，可将某个选定的分区换出。

2、会产生外部碎片，如下图（内部碎片是指 eg：要 1M，分了 8M，产生 7M 的碎片）：

移动内存中的进程，将碎片集中起来，重新构成大的内存块。需要运行时的动态重定位，费时。

（1）紧缩方向：向一头紧缩，向两头紧缩。

（2）紧缩时机：①在释放分区时，如果不能与空闲分区合并，则立刻进行紧缩。

好处是不存在外部碎片，坏处是费时。

②在内存分配时，如果剩余的空闲空间总量能满足要求但没有一个独立的空闲块能满足要求，则进行紧缩。

好处是减少紧缩次数。Lazy。

①最先适应算法（First fit）：从头开始，在满足要求的第一个空闲块中分配。

分区集中在内存的前部，大内存留在后面，便于释放后的合并。

②最佳适应算法（Best fit）：遍历空闲块，在满足要求的最小空闲块中分配。

留下的碎片最小，基本无法再用，需要更频繁地紧缩。

③下一个适应算法（Next fit）：从上次分配的位置开始，在满足要求的下一个空闲块中分配。

对内存的使用较平均，不容易留下大的空闲块。

④最差适应算法（Worst Fit）：遍历空闲块，在满足要求的最大空闲块中分配。

留下的碎片较大，但不会剩余大内存。

最先适应算法较优，最佳适应算法较差。

伙伴算法：将动态分区的大小限定为 2^k  字节，分割方式限定为平分，分区就会变得较为规整，分割与合并会更容易，可以减少一些外部碎片。平分后的两块互称伙伴。

1、

分配时可能要多次平分，释放时可能要多次合并。举例：

记录大小不同的空闲页：

示意图：

2、

伙伴算法是静态分区和动态分区法的折中，比静态分区法灵活，不受分区尺寸及个数的限制；比动态分区法规范，不易出现外部碎片。会产生内部碎片，但比静态分区的小。

Linux、Windows、Ucore等都采用伙伴算法管理物理内存。

一般情况下，将最小尺寸定为 2^12 字节（1页，4K=4096B），最大尺寸定为1024页，11个队列。

Linux、Windows、Ucore 等都将伙伴的最小尺寸限定为1页。

ucore 用 page，在内存初始化函数 page_init 中为系统中的每个物理页建立一个 page 结构。

页块（pageblock）是一组连续的物理页。

5、

（1）判断伙伴关系/寻找伙伴

最后两行是指，B1和B2只有第i位相反。

（2）判断伙伴是否空闲：

ucore 用 free_area[ ]数组定义空闲页块队列。

（3）确定伙伴是否在 order 队列中：

7、

（1）解决内部碎片过大问题（eg：申请5页，分配8页，浪费3页）：

ucore 在前部留下需要的页数，释放掉尾部各页。每次释放1页，先划分成页块，再逐个释放。

（2） 解决切分与合并过于频繁的问题：

用得较多的是单个页。位于处理器Cache中页称为热页（hot page），其余页称为冷页（cold page）。处理器对热页的访问速度要快于冷页。

可建一个热页队列（per_cpu_page），暂存刚释放的单个物理页，将合并工作向后推迟 Lazy。总是试图从热页队列中分配单个物理页。分配与释放都在热页队列的队头进行。

（3）解决内存碎化(有足够多的空闲页，但是没有大页块)问题：①将页块从一个物理位置移动到另一个物理位置，并保持移动前后逻辑地址不变（拷贝页块内容）；②逻辑内存管理器。

（4）满足大内存的需求：

（5）物理内存空间都耗尽的情况：

在任何情况下，都应该预留一部分空闲的物理内存以备急需。定义两条基准线low和high，当空闲内存量小于low时，应立刻开始回收物理内存，直到空闲内存量大于high。

（6）回收物理内存：

法一：启动一个守护进程，专门用于回收物理内存。周期性启动，也可被唤醒。

法二：申请者自己去回收内存。实际是由内存分配程序回收。回收的方法很多，如释放缓冲区、页面淘汰等。

1、

伙伴算法最小分配内存为页，对于更小的内存的管理 --> Slab 算法

内和运行过程中经常使用小内存（小于1页）eg：建立数据结构、缓冲区

内核对小内存的使用极为频繁、种类繁多、时机和数量难以预估。所以难以预先分配，只能动态地创建和撤销

2、

Slab 向伙伴算法申请大页块（批发），将其划分成小对象分配出去（零售）；将回收的小对象组合成大页块后还给伙伴算法。

Slab 采用等尺寸静态分区法，将页块预先划分成一组大小相等的小块，称为内存对象。

具有相同属性的多个Slab构成一个Cache，一个Cache管理一种类型（一类应该是指一个大小）的内存对象。当需要小内存时，从预建的Cache中申请内存对象，用完之后再将其还给Cache。当Cache中缺少对象时，追加新的Slab；当物理内存紧缺时，回收完全空闲的Slab。

Slab 算法的管理结构：

① Cache 管理结构：管理Slab，包括Slab的创建和销毁。

② Slab 管理结构：管理内存对象，包括小对象的分配与释放。

（Cache结构和Slab结构合作，共同实现内存对象的管理）

3、

（1）描述各个内存对象的使用情况

可以用位图标识空闲的内存对象。也可以将一个Slab中的空闲内存对象组织成队列，并在slab结构中记录队列的队头。

早期的Linux在每个内存对象的尾部都加入一个指针，用该指针将空闲的内存对象串联成一个真正的队列。（对象变长、不规范，空间浪费）

改进：将指针集中在一个数组中，用数组内部的链表模拟内存对象队列。

再改进：将数组中的指针换成对象序号，利用序号将空闲的内存对象串成队列。序号数组是动态创建的。

序号数组可以位于 Slab 内部，也可以位于 Slab 外部

（2）一个Cache会管理多个Slab，可以将所有Slab放在一个队列中。

Ucore为每个Cache准备了两个slab结构队列：全满的和不满的。Linux为每个Cache准备了三个slab结构队列：部分满的、完全满的和完全空闲的。

Linux允许动态创建Cache，Ucore不许。Ucore预定了对象大小，分别是32、64、128、256、512、1K、2K（4K、8K、16K、32K、64K、128K）。为每一种大小的对象预建了Cache。

（3）Slab是动态创建的，当Cache中没有空闲的内存对象时，即为其创建一个新的Slab。

Slab所需要的内存来自伙伴算法，大小是  2^page_order 个连续页。

4、小对象的尺寸

如按处理器一级缓存中缓存行（Cache Line）的大小（16、32字节）取齐，可使对象的开始位置都位于缓存行的边界处。

在将页块划分成内存对象的过程中，通常会剩余一小部分空间，位于所有内存对象之外，称为外部碎片。

Slab算法选用碎片最小的实现方案。

5、

（1）对象分配 kmalloc

① 根据size确定一个Cache。

② 如果Cache的slabs_notfull为空，则为其创建一个新的Slab。

③ 选中slabs_notfull中第一个Slab，将队头的小对象分配出去，并调整队列。

④ 对象的开始地址是：objp = slabp->s_mem + slabp->free * cachep->objsize;

（2）对象释放 kfree

① 算出对象所在的页号，找到它的 Page 结构。

② 根据 Page 找到所属的 Cache 和 Slab。

③ 算出对象序号：objnr = (objp - slabp->s_mem) / cachep->objsize;

④将序号插入Slab的free队列。

⑤整Slab所属队列。