‘壹’ 可变分区管理内存分配算法有那些,各有什么有缺点
连续分配： 首次适应算法（较快，简单，碎片多），最大适应分配算法（以期不留下小碎片）， 最佳适应分配算法（慢，复杂，碎片少）。 都需要碎片整理。
离散分配：分段管理（逻辑性好），分页管理，段页式管理（最好，当然也复杂）。
‘贰’ 内存状态分区管理中最佳适应算法的空白区是
实验五 内存分区管理实验
一、单项选择题（共5题,每题10分,共50分）
1、最佳适应算法的空白区是__B__.
A.按大小递减顺序连在一起 B.按大小递增顺序连在一起
C.按地址由小到大排列 D.按地址由大到小排序
2、在固定分区分配中,每个分区的大小是__C__.
A.相同 B.随作业长度变化
C.可以不同但预先固定 D.可以不同但根据作业长度固定
3、采用__B__不会产生内部碎片.
A.分页式存储管理 B.分段式存储管理
C.固定分区式存储管理 D.段页式存储管理
4、在可变式分区存储管理中的拼接技术可以_A___.A.集中空闲区 B.增加内存容量
C.缩短访问周期 D.加速地址转换
5、采用分段存储管理的系统中,若地址用24位表示,其中8位表示段号,则允许每段的最大长度是_B___.
二、填空题（共4题,每题5分,共20分）
1、在分区分配算法中,首次适应算法倾向于优先利用内存中的_低地址___部分的空闲分区,从而保留了__高地址__部分的大空闲区.
2、在可变分区存储管理中,分区的保护通常采用_地址越界___和__非法操作__两种方法.
3、3、采用交换技术获得的好处是以牺牲_增大系统开销___为代价的.
4、在采用请求分页式存储管理的系统中,地址变换过程可能会因为_缺页___、_越界___和_访问权限错误___等原因而产生中断.
三、 简答题（共2题,每题15分,共30分） 1、可采用哪几种方式将程序装入内存?它们分别适用于何种场合?
a.首先由编译程序将用户源代码编译成若干目标模块,再由链接程序将编译后形成的目标模块和所需的
---库函数链接在一起,组成一个装入模块,再由装入程序将装入模块装入内存；
b.装入模块的方式有:绝对装入方式,可重定位方式和动态运行时装入方式；
c.绝对装入方式适用于单道程序环境下；
d.可重定位方式适用于多道程序环境下；
e.动态运行时装入方式也适用于多道程序环境下.
2、何谓静态链接?何谓装入时动态链接和运行时的动态链接?
a.静态链接是指事先进行链接形成一个完整的装入模块,以后不再拆开的链接方---式；
b.装入时动态链接是指目标模块在装入内存时,边装入边链接的链接方式；
c.运行时的动态链接是将某些目标模块的链接推迟到执行时才进行.
‘叁’ 连续分配存储管理方式
一、单一连续分配
最简单的一种存储管理方式，只能用于单用户、单任务的操作系统中。
优点：易于管理。
缺点：对要求内存空间少的程序，造成内存浪费；程序全部装入，很少使用的程序部分也占用内存。
二、固定分区分配
把内存分为一些大小相等或不等的分区(partition)，每个应用进程占用一个分区。操作系统占用其中一个分区。支持多个程序并发执行，适用于多道程序系统和分时系统。最早的多道程序存储管理方式。
缺点：内碎片（一个分区内的剩余空间）造成浪费；划分为几个分区，便只允许几道作业并发，分区总数固定，限制并发执行的程序数目。
三、动态分区分配
1、分区的大小不固定：在装入程序时根据进程实际需要，动态分配内存空间，即——需要多少划分多少。
2、空闲分区表项：从1项到n项：内存会从初始的一个大分区不断被划分、回收从而形成内存中的多个分区。
3、优点：并发进程数没有固定数的限制，不产生内碎片。缺点：有外碎片（分区间无法利用的空间）
4、分区分配算法
①首次适应算法FF(first-fit)
空闲分区排序：以地址递增的次序链接。
检索：分配内存时，从链首开始顺序查找直至找到一个大小能满足要求的空闲分区；
分配：从该分区中划出一块作业要求大小的内存空间分配给请求者，余下的空闲分区大小改变仍留在空闲链中。
若从头到尾检索不到满足要求的分区则分配失败
优点：优先利用内存低址部分，保留了高地址部分的大空闲区；
缺点：但低址部分不断划分，会产生较多小碎片；而且每次查找从低址部分开始，会逐渐增加查找开销。
②循环首次适应算法
空闲分区排序：按地址
检索：从上次找到的空闲分区的下一个空闲分区开始查找，直到找到一个能满足要求的空闲分区。为实现算法，需要设置一个起始查寻指针并采用循环查找方式
分配：分出需要的大小
优点：空闲分区分布均匀，减少查找开销
缺点：缺乏大的空闲分区
③最佳适应算法
总是把能满足要求、又是最小的空闲分区分配给作业，避免“大材小用”。
空闲分区排序：所有空闲分区按容量从小到大排序成空闲分区表或链。
检索：从表或链的头开始，找到的第一个满足的就分配
分配：分出需要的大小
缺点：每次找到最合适大小的分区割下的空闲区也总是最小，会产生许多难以利用的小空闲区（外碎片）
④最差适应算法/最坏匹配法
基本不留下小空闲分区，但会出现缺乏较大的空闲分区的情况。
⑤快速适应算法
根据进程常用空间大小进行划分，相同大小的串成一个链，需管理多个各种不同大小的分区的链表。进程需要时，从最接近大小需求的链中摘一个分区。
能快速找到合适分区，但链表信息会很多；实际上是空间换时间。
5、回收分区
(1)回收区（首址a）与一个分区f1末尾（首址b+大小）邻接：将回收区与f1合并，修改f1的表项的分区大小
(2)回收区（首址a+大小）与一个分区f2的首址b邻接：将回收区与f2合并，修改f2的表项的首址、分区大小
(3) （1）（2）两种情况都有，则将回收区与前后两个分区F1、F2邻接：将三个分区合并，使用F1的表项和F1的首址，取消F2的表项，大小为三者之和
(4) 回收区没有邻接的分区：为回收区单独建立新表项，填写回收区的首址与大小，根据其首址插到空闲链中的适当位置
四、动态重定位分区分配——有紧凑功能的动态分区分配
动态重定位分区分配算法与动态分区分配算法基本相同，差别在于增加了紧凑的功能。
伙伴系统
分区大小有规定，且分区动态变化
1、无论已分配还是空闲分区，大小都为2的k此幂。若整个可分配空间大小为2m，则1≤k≤m.
2、随着系统运行，内存被不断划分，形成若干不连续的空闲分区。对每一类具有相同大小的空闲分区设置一双向链表，即会有k个链表，链表中的分区大小都是2m。
3、进程申请n个大小的空间时，计算n= 2i。则找i对应的链表。若i大小的链表没有，则找i+1的链表。找到的分区对半划分后，一半用于分配，一半链接到较小一级的链表里去。
4、一次分配和回收都可能对应多次的划分和合并。
五、内存空间管理之对换
当内存空间还是满足不了需求时，把内存中暂时不能运行、或暂时不用的程序和数据调到外存上，以腾出足够的内存；把已具备运行条件的进程和进程所需要的程序和数据，调入内存。
整体对换(或进程对换)：以整个进程为单位（连续分配）
页面对换或分段对换：以页或段为单位（离散分配）
‘肆’ 【我的笔记】内存管理（二）分区方法（静态、动态、伙伴、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所属队列。