计算机系保研南大面试课程

第4章 存储管理存储器存储器有多大，程序就会有多长存储器的属性容量速度价格易失/非易失存储器的层次结构价格与速度成正比速度与容量成反比寄存器高速缓存内存磁盘第2页

共

页存储器管理第3页

共

页物理内存分配记录物理存储器的使用情况，即哪些部分正被使用，哪些部分还空闲着。进程的内存管理当进程需要存储空间时，就分配给它；然后当它运行结束后，再把存储空间回收回来。逻辑地址到物理地址的映射方法。交换如果内存太小，容不下所有的进程，那么就需要把内存中暂时不能运行的进程送到磁盘上，然后再把磁盘上的另一个进程装入内存。4.1

基本的存储管理(1）固定分区单道程序系统第5页

共

页把整个内存划分为两个区域，即系统区和用户区。

每一次把一个应用程序装入到用户区去运行，由它和操作系统来共享整个内存。操作系统被放在了内存的最低端（在早期的大型机和小型机中）。操作系统被放在了内存地址的最高端，而且是放在了只读存储器(Read-Only

Memory，ROM)里面（掌上型电脑和嵌入式系统中）。操作系统被分成两部分，一部分是设备驱动程序，被放在内存高端的ROM中；另一部分则放在了内存地址的最低端（早期的个人计算机系统中，如MS-DOS）。（2）固定分区的多道程序系统多个输入队列

缺点：不均衡。分区4分区3分区2分区1操作系统第6页

共

页（2）固定分区的多道程序系统单个输入队列选择离队首最近的、能够装入该分区的进程。浪费内存空间。选择能够装入该分区的最大进程。不利于那些比较小的进程。始终保留至少一个小分区。规定一个进程被忽略的次数不能超过k次。IBM大型机的OS／360。第7页

共

页（3）重定位和存储保护第8页

共

页重定位链接器告诉装载程序，哪些地方是需要修改的地址，哪些地方是不能修改的操作码、常量数据等。链接器在可执行文件中包含一个链表或位图，列出各个需要重定位的地址单元的位置。在机器中增加两个特殊的硬件寄存器，即基地址(base)寄存器和边界(limit)寄存器。把该进程所在的分区的起始地址，放在基地址寄存器中。把这个分区的长度，放在边界寄存器中。在进程的运行过程中，当它需要访问内存单元的时候，硬件就会自动地把相应的内存地址加上基地址寄存器的值，从而得到真正的目标地址。（3）重定位和存储保护第9页

共

页存储保护IBM采用的保护360机器的办法。将内存划分为2KB的块，并为每个块分配一个4位的保护码。在CPU的程序状态字(ProgramStatusWord，PSW)中包含一个4位的密钥。如果它访问的内存单元的保护码与PSW中的密钥不符，那么360的硬件就会引起一个陷入。基地址(base)寄存器和边界(limit)寄存器。Intel

8086CPU有基地址寄存器，但没有边界寄存器。4.2

交换技术第10页

共

页4.2

交换技术可变分区交换

分区的位置大小可变第11页

共

页4.2

交换技术不连续的黑洞。获得必要的空间内存紧缩。进程移动到另一个足够大的空间。把一个或多个进程交换出去

以生成一个足够大的空闲区。额外的内存在进程被换入或移动时为它分配一点额外的内存。进程的栈段位于内存地址的顶端向下增长。位于数据段上面的动态数据向上增长。第12页

共

页4.2

交换技术—基于位图的存储管理位图指示内存被划分为很多个分配单元每个分配单元都对应于位图中的某个数据位。0表示该单元是空闲的1

表示该单元已经被占用。分配搜索连续的k个0。内存内存单元位图位第13页

共

页4.2

交换技术—链表表示法{占用状况,起始，长度}搜索速度。排序。更新链表，合并、分割。分配策略。AXBAXXBXABAB之前之后第14页

共

页4.2

交换技术—分配算法第15页

共

页最先匹配法(first

fit)从链表的首结点开始，直到找到第一个长度大于等于进程的内存要求长度M的结点。把它所对应的空闲分区分割为两个小的分区，一个用来装入这个进程，另一个是剩余的空闲区域。与之相对应，链表结点也要一分为二，分裂成两个结点，并修改相应的内容。下次匹配法每一次当它找到一个合适的空闲结点时，就会把当前位置记录下来。下一次就从这个位置开始继续往下找。最佳匹配法搜索整个链表，将能够装得下该进程的最小空闲分区分配出去。碎片最坏匹配法4.2

交换技术—分配算法第16页

共

页占用链表与空闲链表分离空闲链表按照长度的大小排序。最先匹配与最佳匹配就相同了。快速匹配法按照常用的请求大小排成多个队列，每个队列上空闲块大小相同。4.3

虚拟存储管理第17页

共

页4.3

虚拟存储管理第18页

共

页覆盖块(overlay)把该程序划分为若干个部分，称为覆盖块(overlay)。只把那些当前需要用到的指令和数据保存在内存中，而把其余的指令和数据保存在外存中。由程序员来手工地把一个大的程序划分为若干个小的功能模块。虚拟存储器操作系统自动地把当前需要用到的那些部分保留在内存中，而把其余部分保存在磁盘上。（1）虚拟页式存储管理第19页

共

页操作系统能在指令执行前知道指令请求的内存是否已经在内存中吗？操作系统很难知道在一个代码片段中会请求那个变量。操作系统难以在指令执行前决定是否应该讲在外存的数据片段换入内存。如何自动地交换？执行指令，在指令执行过程中决定是否需要交换。（1）虚拟页式存储管理第20页

共

页分离程序员角度的地址、处理器角度的地址。虚拟地址（Virtual

Address，VA）这个范围的大小由CPU地址线的位数决定。物理地址（Physical

Address，PA）存储单元（ROM、设备寄存器、内存片）的地址。内存管理单元(Memory

Management

Unit,MMU)。（1）虚拟页式存储管理—MMU的功能将虚拟地址映射为物理地址Intel虚拟地址→线性地址→物理地址：段页式存储管理虚拟地址=线性地址→物理地址：页式存储管理虚拟地址→线性地址=物理地址：段式存储管理CPU执行单元发出的内存地址将被MMU截获从CPU到MMU的地址称为虚拟地址VA。MMU将这个地址翻译成另一个地址发到CPU芯片的外部地址引脚上.将VA映射成物理地址PA。第21页

共

页（1）虚拟页式存储管理—MMU的功能MMU在指令执行过程中决定是否需要交换。虚拟地址在MMU映射之前无法它被映射成的物理地址是否有效。MMU在映射过程中可以发现该虚拟地址对应存储单元是否在内存。如果不在，通过异常的机制通知操作系统来交换。虚拟块映射状态：0→2，2→1，3→4，5→0，6→3这样的数据MMU能发现吗？好发现吗？物理块第22页

共

页（1）虚拟页式存储管理虚拟块物理块大小要一样虚拟块 物理块数据结构要集中第23页

共

页虚拟块 物理块 状态页表MMU如何是否需要交换（1）虚拟页式存储管理—MMU的内部操作页号虚拟页号4位，所以表长是16。物理页号3位，所以只有一半是有效的。页的长度物理页和虚拟页的单元必须一一对应，所以必须一样长。对应若干位的编码，所以必须是2的幂。映射用物理页号取代虚拟页号。第24页

共

页（2）页表第25页

共

页页表可能会非常大32位的虚拟地址为4GB，需要220≈100万页表项。地址映射必须十分迅速页表全部放在寄存器中页表太大，价格太贵进程切换时间较长页表全部放在内存，用寄存器指向页表基地址。需要多次访问内存。（2）页表——多级页表页目录每个表项指向一个页表页表每一个表项指向一个页。X86的处理器情况一个页表映射4M物理页。最底端和最顶端的几个表项才是常用的。大量的页表可以不创建。页表占用的空间实际不大。第26页

共

页（2）页表——页表项的结构第27页

共

页以Intel

32位为例页目录和页表中的偏移地址是页对齐的，所以只要20位，剩余12位。可以用来表示页表和页面的属性。页目录项第28页

共

页311211109876543210页表基地址系统软件可用GPS0APCDPWTU/SR/WP页目录项P:存在位；R/W：0=只读，1=读写；

U/S：0=特权级为0、1、2的用户PWT：level

Write

Through,

1=write

through（写cache时同时写

RAM）,0=write-back（修改过的cache换出时才写入内存）PCD：level

Cache

Disable，1=禁止页面或页表缓存；0=允许

A：当页面装入内存时清除该标志，存取该页面时设置该标志。

PS：0=页面大小为4k，1=页面大小为4M。G：用来防止经常使用的页的页表项从TLB中换出。cr4寄存器中的

PGE位置位时这个标记才起作用。页表项第29页

共

页311211109876543210页表基地址系统软件可用G0DAPCDPWTU/SR/WP页表项P:存在位，当页表或页框不在时，对它的访问产生页失效异常，操作系统处理该异常；R/W：0=只读，1=读写；U/S（用户/系统）：0=特权级为0、1、2的用户PWT：levelWrite

Through,1=write

through,

0=write-backPCD：level

Cache

Disable，1=禁止页面或页表缓存；0=允许

A：当页面装入内存时清除该标志，存取该页面时设置该标志。

D（Dirty）：当页面装入内存时清除该标志，写该页面时设置该标志。

G:全局页。在页快表TLB中，全局页不能被设为无效。（3）关联存储器(Translation

Lookaside

Buffer,TLB)访问内存中变量的问题为了确定变量实际的物理地址逻辑上需要用到内存的页目录和页表。快速查找硬件，即TLB(Translation

Lookaside

Buffer)或者称为关联存储器(associative

memory)。用来存放那些最常用的页表项。TLB通常位于MMU中，包含了少量的表项，一般不超过64个。有效位虚拟页面号修改位保护码物理页面号11401RW311200RX3811301RW2911291RW621190RX501210RX4518601RW1418611RW75第30页

共

页（3）关联存储器(Translation

Lookaside

Buffer,TLB)TLB相关的操作并行查找访问权限检查更新TLB有效位虚拟页面号修改位保护码物理页面号11401RW311200RX3811301RW2911291RW621190RX501210RX4518601RW1418611RW75第31页

共

页3）关联存储器(TLB)第32页

共

页软件操作TLB在一些现代的RISC机中，包括SPARC，MIPS，HPPA和PowerPC，几乎所有的页面管理工作都是由软件来完成的。TLB表项是由操作系统来负责装入的。如果发生TLB未命中的情形，产生一个TLB中断，把问题交给操作系统。由操作系统负责找到相应的页面，并从TLB中淘汰一个表项，装入新访问的这个表项。3）关联存储器(TLB)第33页

共

页降低TLB的未命中率。操作系统有时可以预测出哪些页面即将被访问。将预测的页面预先装入TLB。用来存放页表的页面本身可能就不在TLB中。将一些经常要访问的内存缓冲区（如页目录、页表）所在的页面的页表项始终位于TLB中。(4)

反置页表页表项数量的问题根据进程的虚拟页面号来索引的页页表。32位的虚拟地址空间需要220=1M个页表项，占4M空间。64位的虚拟地址空间需要252个页表项，占255空间。反置页表方案用物理页面号来作为访问页表的索引。从虚拟页面号到物理页面号的转换问题TLB方法哈希表(哈希表的表项个数与物理页面的个数一样多)。第34页

共

页4.4

页面置换算法第35页

共

页（1）置换问题第36页

共

页页面置换问题缺页中断发生时如果还有空闲的物理页面，分配物理页面，装入页面数据；如果没有空闲的页面了，腾出一个已经分配的物理页面，装入新的页面。如何腾出一个已经分配的物理页面？其它置换问题内存高速缓存TLB高速缓存Web页面缓存（2）最优页面置换算法第37页

共

页基本思路是对于内存中的每一个虚拟页面，计算在它的下一次访问之前，还需要等待多长的时间，用指令数表示。给每一个页面标注一个指令数，表示要执行完这么多条指令之后，才会第一次去访问该页面。选择等待时间最长(标注的指令数最大)的那个页面，把它作为被置换的页面。这个算法唯一的缺点就是它是无法实现的（因而是无法克服、不能忍受的）。可用之处：评价的标准。在一个模拟器上运行某个程序，并且记录下每一次的页面访

问情况，有了这些数据以后，在第二次运行这个程序的时候，就可以采用最优算法，计算出最少的缺页次数，然后把它和

其他算法的运行结果做一个比较。（3）最近未使用页面置换算法第38页

共

页访问R最近访问过，则可能还要访问，尽量不要换出。修改M修改过，如果换出，就要写辅存，代价较高，也尽量不要换出。第0类：未被访问，未被修改。第1类：未被访问，已被修改。第2类：已被访问，未被修改。第3类：已被访问，已被修改。优先换出：未被访问，未被修改。尽量不换：已被访问，已被修改。未被访问，已被修改。要写辅存已被访问，未被修改。再次访问随机地从编号最小的非空类中挑选一个页面，把它淘汰出去。什么是最近未使用？从上一个时钟中断到当前的这一段时间。（4）

先进先出页面置换算法第39页

共

页先进先出(First-In，First-Out，FIFO)算法。理由：每个对象越早出现，越早淡出。像有生命的生物体。问题：多样性。不同种类的生物寿命不同。同种类的寿命页也不一样。有长生不老的神仙。（5）第二次机会页面置换算法FIFO的问题在哪？无视神仙的存在。解决办法：承认有仙药，吃一粒仙药，焕发一次青春。算法（正视多样性，区别对待）按照装入的时间排队。页面被访问一次，就将其置于最年轻的一头。最先装入的页面 最后装入的页面A

B

C

D

E

F

G

HBAC

D

E

F

G

HA页面的R=1，放入最后，将R清0，就像新装入一样第40页

共

页两种算法的比较最近未使用页面置换算法与第二次机会页面置换算法的比较最近未使用页面置换算法只考虑一个时间段，但考虑R和M。第二次机会页面置换算法考虑多个时间段，但只考虑R。能考虑多个时间段，并且同时考虑R和M吗？多因素、多标准如果A比B老，但A修改过，B没有修改过。··第41页

共

页（6）最近最久未使用（LRU）页面置换算法第42页

共

页第二次机会页面置换算法与FIFO的区别是，如果最老的页面被访问过，重新放入队列。如果大家都被访问过，则最老的仍然被淘汰（因为大家R位都被清除）。只考虑是否访问过，不考虑是否频繁，访问时刻是否更近。最近最久未使用(Least

Recently

Used，LRU)不但要考虑是否访问，还要考虑哪个最后一次访问更久。如何记录没有被访问的时间？链表最后使用的页面放在队头。最长时间未被使用的放在队尾。开销太大。（6）

LRU页面置换算法第43页

共

页硬件（1）在硬件上有一个64位的计数器C，在每条指令执行完后C的值会自动加1。在每个页表项中，必须有一个足够大的字段来存放该计数器的值。在每一次内存访问后，C的当前值会被存放在被访问页面的页表项中。（6）最近最久未使用页面置换算法硬件（2）n×n矩阵，行置1，列置0。证明：如果是i→j(j被访问之后i没有被访问),则第j行的每一位都不比第i行的每一位小，但第i位大。之后第i位不会被清除。页面访问次序：0,1,2,3,2,1,0,3,2,3ijxxx0xi00j111010第44页

共

页（6）

LRU页面置换算法第45页

共

页LRU考虑的是最后1次访问时间一个页面最近一段时间没有使用，原来使用很频繁。

？软件（Not

Frequently

Used,NFU）对于每一个页面，算法将设置一个软件计数器，它的初值为0。在每次时钟中断时，操作系统将对内存中的所有页面进行扫描，把每个页面的R位(0或1)的值加到它的计数器上。当需要淘汰页面时，计数器值最小的那个页面将被淘汰出局。NFU的问题前一阶段使用频繁，这一阶段不再使用了。谁知道进入了一个新的阶段。OS不知道用户进程的状态是OS来猜测还是设法告诉OS（6）最近最久未使用页面置换算法—aging最后一次的R位放在最左边（权数最重）。依次类推。最小的，就是最后一次访问时刻离现在最远。在第3轮中哪个页面最后被访问没有记录。第46页

共

页4.5

页式管理中的设计问题第47页

共

页（1）工作集模型第48页

共

页访问的局部性(Locality

of

reference)进程当前正在使用的页面集合称为它的工作集(working

set)。抖动（Thrashing)如果分配给一个进程的物理页面数太少，不能包含整个工作集，这时，进程将会造成很多的缺页中断，需要频繁地在内存与外存之间置换页面。工作集模型存储管理系统试图记录每个进程的工作集，并确保在进程运行之前，它的工作集都在内存中。预先调页（prepaging）随着时间的变化，进程的工作集的内容也会发生变化。（1）工作集模型大多数程序的工作集随着时间的增长会慢慢稳定下来。随着时间的变化，工作集也会发生变化。实现工作集模型。利用老化（aging）算法，对于任何一个页面，如果在它的计数值的高n位中包含有一个1，那么这个页面就是工作集的一个成员。如果一个页面连续n个时钟周期未被访问，就把它从工作集中删除。第49页

共

页（2）局部与全局分配策略第50页

共

页以LRU算法为例局部算法为每个进程分配固定大小的内存空间，淘汰页面在固定数量的页面中进行。如果工作集增大时，即使内存中还有大量的空闲页面，也可能会导致抖动现象；而如果工作集收缩了，那么又会浪费内存空间。全局算法在所有进程之间动态地分配物理页面，因此分配给各个进程的物理页面数是随时间变化的。监视由年龄位指出的工作集的大小，但这种办法并不足以阻止抖动。（2）局部与全局分配策略第51页

共

页可以按照进程大小的比例来为它们分配页面300KB的进程所得到的份额就是10KB进程的30倍。给每一个进程都规定一个最小的物理页面数，这样不管多么小的进程都可以运行。缺页率(Page

FaultFrequency，PFF)算法统计过去几秒钟内缺页率的一个平均值。某个进程的缺页率高于上界，就给这个进程分配更多的物理页面。某个进程的缺页率低于下界，就从它的手里拿走一些页面。（2）局部与全局分配策略第52页

共

页如果系统发现内存中的进程太多，无法使所有进程的缺页率都低于上界，那么就必须把一些进程置换出去，从而腾出它们所占用的内存空间。（2）局部与全局分配策略如果系统发现内存中的进程太多，无法使所有进程的缺页率都低于上界，那么就必须把一些进程置换出去，从而腾出它们所占用的内存空间。第53页

共

页（3）

页面大小页面大小的选择需要平衡各种相互矛盾的因素，没有全局性的最优解。小页面那么内碎片（一个页面未被用户程序使用的部分）就越少。同一个程序来说，它就需要越多的页表项，所以页表就越庞大。进程切换时（可能需要）装入页表所需要的时间长。以页面为单位传输，I/O性能降低。大页面内碎片大。公式𝑝=2se仅仅考虑的是页表占用空间的优化，但更重要的是运行的性能。第54页

共

页（4）虚拟存储器接口第55页

共

页内存映射让两个或多个进程可以共享同一段内存空间。一个进程就有可能把自己的一块内存区域的名字告诉另一个进程，使该进程也可以把它映射进来。如果两个(或多个)进程共享相同的页面，进程之间就可以有一个高速的数据共享。页面共享还可以用来实现高性能的消息传递系统。分布式共享存储器。4.6

段式存储管理第56页

共

页（1）分段问题页式存储管理针对的是线性的地址空间。对于许多程序来说多个不同类型的数据。每种类型的数据长度动态变化。问题：程序员需要考虑不同数据类型的边界限制。第57页

共

页（1）分段问题独立的地址空间，称为段(segment)在每个段的内部，是一个一维的线性地址序列，从0开始，一直到某个最大值。在执行过程中，段的长度可以动态变化。二维地址：（段，偏移）第58页

共

页（1）分段问题第59页

共

页如果每个函数都位于不同的段中，只要使用二维地址(n，0)，就可以跳转到该函数的人口地址。如果第n个段中的那个函数随后被修改并重新进行了编译，而且新版本比旧版本要长，那么并不会影响到其他的函数，其他的函数不用做任何的修改。

在一维地址中，函数被一个挨一个紧紧地放在一起，中间没有空隙，因此，如果修改了一个函数的长度，将会影响到其他函数的起始地址。分段也有助于在几个进程之间共享函数和数据。段是一个逻辑实体，如函数、数组或栈，因此，不同的段应该具有不同的保护模式。（1）分段问题—页式和段式存储管理的比较第60页

共

页考虑的问题页式存储管理段式存储管理程序员需要知道正在使用这种技术？不需要需要有多少个线性地址空间？一个多个地址空间可以超过物理内存的大小吗？可以可以数据和函数可以区别开来、分别进行保护吗？不可以可以能够很容易地容纳长度经常变化的表？不能能用户之间的函数共享是否方便？否是为什么要发明这项技术？为了在物理内存空间不变的情形下，得到更大的线性地址空间。为了能将代码和数据划分为逻辑独立的地址空间，为了帮助实现共享和保护（2）纯分段系统的实现跳棋盘(checkerboarding)或外碎片(external

fragmentation)内存紧缩（compaction）。第61页

共

页（3）段页式存储管理第62页

共

页GDT

、LDT选择符段描述符虚拟地址→线性地址→物理地址调用门、任务门、终端门。一致段、非一致段。（3）段页式存储管理第63页

共

页如何保证不同的段之间不相交？4.7 LINUX

内存管理第64页

共

页郭玉东主编，Linux操作系统结构分析，西安电子科技大学出版社，2002

年1月。Linux内存管理结构第65页

共

页物理内存管理器物理内存管理器负责物理内存的分配、释放与回收，它以页为单位实施管理。其目的是提高性能、减少碎块。内核内存管理器。由于内核经常需要小内存用于建立各种管理结构，而物理内存管理器过于粗放，所以Linux提供了内核内存管理器，专门负责内核中小内存的分配和回收。Linux的内核内存管理器采用

Slab算法。虚拟内存管理器。虚拟内存管理器在物理内存管理器的基础上，通过页目录、页表及交换机制，为系统中每个进程模拟了一个大小为4GB的虚拟地址空间。由于虚拟内存管理器的作用，用户进程几乎不受实际物理内存大小的限制。Linux内存管理结构第66页

共

页内核虚拟内存管理器。如果内核需要较大的内存，物理内存管理器和内核内存管理器都不能很好地工作，原因是它们只能分配有限大小的、物理上连续的内存。为了满足内核对大内存的需求，Linux利用虚拟内存管理的思想，在内核虚拟地址空间(3GB以上)实现了内核虚拟内存管理器。用户空间内存管理器。该管理器负责进程用户态虚拟内存的动态分配和回收(如C语言中的malloc、free等)，它管理的内存在进程的堆中。用户空间内存管理器一般在库(如Libc)中实现，不属于内核，但内核对其提供有相应的支持。Linux内存管理结构用户内存管理内核虚拟内存管理虚拟内存管理内核

内存管理物理内存管理第67页

共

页第68页

共

页4.7.1物理内存管理器—mem_map_t第69页

共

页struct

page*next;双向链表struct

page*prev;双向链表struct

inode*inode;当页用于存储文件的数据时，inode标识文件，offset表示页在文件中的位置。unsignedlongoffset;struct

page*next_hash;用于在页缓存Hash表中建立页的双向链表，atomic_tcount;引用计数unsignedlongflags;PG_dirty,

PG_DMA,

PG_locked,

PG_locked,……struct

wait_queue*wait;等待操作物理页的进程队列struct

page**pprev_hash;用于文件映射页的缓存。struct

buffer_head*

buffers;由物理页构成的所有buffer连成一个循环链表整个内存管理的基础。系统中对于内存的需求最终都要由物理内存管理器来满足。在Intel系列CPU上，一个物理页的大小是4KB(目前的体系结构也支持4MB的页)。系统中所有的物理页用一个mem_map_t结构的数组mem_map描述。该数组的大小由系统中实际物理内存的大小决定。每一个mem_map_t结构描述系统中的一个物理页。typedef

struct

page

{……}

mem_map_t;4.7.1物理内存管理器—位图与链表第70页

共

页管理物理内存最常用的方法有两种：位图和链表。位图记录内存单元的使用情况。如果内存的分配单元是页4KB，则1

MB的内存可以利用

1024×1024／(4096×8)=32个字节的位图来记录。如果一次要分配5页的空间，内存管理程序只需在位图中找出5个连续的1即可。（1=空闲，0=已分配）。链表用数据结构表示内存单元，可分别建立已分配内存和空闲内存单元的链表。Limtx的物理内存管理器采用链表和位图相结合的方法。4.7.1物理内存管理器—位图与链表……struct

free_area_struct

{struct

page

*next;struct

page

*prev;unsigned

int

*

map;};static

struct

free_area_structfree_area[NR_MEM_LISTS];第71页

共

页free_area[0]上排队的是大小为1页的空闲页。在free_area[1]上排队的是大小为2页的空闲页。在freearea[2]上排队的是大小为4页的空闲页，依此类推。4.7.1物理内存管理器—伙伴位map是一个位图，用于记录页块及其伙伴是否在队列中。两个伙伴合用位图中的一位。例如，free_area[0]

中的页0和1合用一位，页2和3合用一位，页4和5合用一位，等等。在位图中，两伙伴合用位的使用如下：两伙伴全都不在队列中(已分配或己组成了更大的块)，它们合用的位为0。有一个在队列中，一个不在队列中，则它们合用的位为1。两个都在队列中，则它们应该合并成更大的块，加入到free_area数组中更上面的队列，所以它们合用的位为0。第72页

共

页4.7.1物理内存管理器—伙伴位map是一个位图，用于记录页块及其伙伴是否在队列中。两个伙伴合用位图中的一位。例如，free_area[0]

中的页0和1合用一位，页2和3合用一位，页4和5合用一位，等等。在位图中，两伙伴合用位的使用如下：两伙伴全都不在队列中(已分配或己组成了更大的块)，它们合用的位为0。有一个在队列中，一个不在队列中，则它们合用的位为1。两个都在队列中，则它们应该合并成更大的块，加入到free_area数组中更上面的队列，所以它们合用的位为0。第73页

共

页4.7.1物理内存管理器—系统空闲页数第74页

共

页Linux定义了一个结构变量freepagestypedefstruct

freepages_v1{unsigned

int

min；unsigned

int

low;unsigned

int

high；}

freepages_v1;typedef

freepages_v1

freepages_tfreepages_t

freepages;全局变量nr_free_pages记录了系统中当前空闲页数。当系统中空闲页数少于freepages.min时，应该回收内存；一旦开始收，每次分配前都要进行回收，直到当系统中空闲页数大于freepages.high。系统中空闲页数大于freepages.high，每次都直接进行内存分配，直到系统中空闲页数小于freepages.min。4.7.1物理内存管理器—页分配第75页

共

页

get_gree_jpages(int

gfp_mask,unsigned

long

order);如果order≥NR_MEM_LISTS，返回0，表示失败；否则转II。根据空闲物理页的总数，决定是立刻分配（转IV），还是先回收再分配（转III）；如果需要回收物理内存，则调用函数try_to_free_pages(gfp_mask)；①

唤醒内核交换的守护进程kswapd；②

根据标志位，决定自己直接调用do_try_to_free_pages()回收内存，或只唤醒kswapd，然后转IV直接分配内存。A.B.正常分配。查找free_area[order]元素所指引的链表。①

如果链表中有满足要求的页块，则将其从链表摘下;将free_area[order].map位图中相应的位取反；修改nr_free_pages;计算该页的起始地址；将页结构引用计数加1；返回物理页块首地址。②

如果该链表中没有满足要求的页块，则在free_area数组中顺序向上查找。如果都没有，此次分配失败。找到一个满足要求的块将其从链表上摘下；将free_area[x].map位图中相应的位取反；修改nr_free_pages;将页块分割，修改链表、free_area[…]。4.7.1物理内存管理器—页释放第76页

共

页void

free_pages(

unsigned

long

addr,

unsigned

long

order);根据addr计算该页在mem_map数组的索引；如果该页是保留的(内核在使用)，则不允许释放，返回。将页块第一页对应的mem_map_t结构中的count域减1，表示该页的使用者减了1个。如果count域的值不是0，说明它还有别的使用者，因此不能释放它。返回。页的引用计数为0，释放该页。清除页块第一页对应的mem_map_t结构的flags域中的PG_referenced位，表示该页块不再被引用。调整全局变量nr_free_pages，将其值加上回收的物理页数。将页块加入到数组free_area[order]的相应队列中。考虑伙伴，如果伙伴在，则合并成更大的块，考虑加入高一级的链表。4.7.2

内核内存管理—slab、cache主要是两个数据结构cache和slab。每个slab管理一组大小相等的内存块，用作一种数据结构。每个cache管理一组大小相等的内存块。cache的数据结构是：struct

kmem_cache_s。slab的数据结构式struct

kmem_slab_s。cache1cache2cache3cache4cache5slab1slab2slab3slab4cache_cachec_firstc_freepc_lastps_freep第77页

共

页4.7.2

内核内存管理第78页

共

页内核在运行过程中需要大量而频繁地使用内存，如建立各种用于管理的数据结构、缓冲区等。内核使用内存有以下特点：不参与交换，不会被内存回收程序回收。使用时间短。要求动态分配和回收。要求响应时间快。空间小，远远小于一页。Linux内核内存管理器用Slab分配器。4.7.3

虚拟内存管理—虚拟内存区域第79页

共

页每个进程的地址空间从0到TASK_SIZE-1(IA32是232-1)。用户空间0-3G，系统空间3-4G。所有的进程的系统空间都是相同的。不同的硬件实现方式可能有所不同。用户的进程有不同的段，具有不同的访问控制的属性，代码段可读、可执行、不可写。数据段可读、可写、不可执行。用户进程通常不能访问其他进程的空间，只有在权限控制下通过内核的服务才能访问与其他进程共享的空间。4.7.3

虚拟内存管理—虚拟内存区域第80页

共

页进程地址空间的布局。二进制代码text。程序使用的动态库。存储全局变量的数据data。存储动态变量的堆heap。局部变量、函数的参数的栈。环境变量、命令行参数。文件映射区域。虚拟区域数据结构struct

vm_area_struct

{ ……

}第81页

共

页struct

mm_struct*vm_mm;该虚拟区域所属的mm_structunsigned

longvm_start;该虚拟区域的起始地址unsigned

longvm_end;该虚拟区域后的第一个字节地址struct

vm_area_struct*vm_next;链表指针pgprot_tvm_page_prot;权限unsigned

longvm_flags;struct

rb_nodevm_rb;红黑树……struct

vm_operations_struct*vm_ops;该结构的操作函数指针struct

file*vm_file;如果是作文件映射区域的，指向文件结构，否则为空。……4.7.3

虚拟内存管理—内存管理结构第82页

共

页mm_struct

{……}struct

vm_area_struct*

mmap;按照地址大小顺序的链表struct

rb_rootmm_rb;虚拟区域的红黑树struct

vm_area_struct*

mmap_cache;最后一次使用的虚拟区域unsigned

long(*get_unmapped_area)

(struct

file*filp,unsigned

long

addr,

unsigned

longlen,unsigned

long

pgoff,

unsigned

longflags)void(*unmap_area)

(struct

mm_struct

*mm,unsigned

long

addr);unsigned

longmmap_base;内存映射的起始地址unsigned

longtask_size;二进制代码当前实际可见的地址空间长度。unsigned

longcached_hole_size;unsigned

longfree_area_cache;…………unsigned

longstart_code,

end_code,

start_data,

end_data;代码和数据区域unsigned

longstart_brk,

brk,

start_stack;堆的起始地址、当前地址、栈顶unsigned

longarg_start,

arg_end,

env_start,

env_end;参数和环境，在栈的最高位置…………4.7.3

虚拟内存管理—进程的虚拟空间布局Text栈TASK_SIZE第83页

共

页STACK_TOPMMAPmm->mmap_base(TASK_UNMAPPED_SIZE)≈≈TASK_UNMAPPED_SIZE一般等于1GB，这样可能堆不够用，可能会进入到映射区。4.7.3

虚拟内存管理—进程的虚拟空间布局Text栈TASK_SIZESTACK_TOPMMAPmm->mmap_baseLinux

2.6.7开始引入了新的虚拟地址空间布局。固定栈区。映射区域向下增长。第84页

共

页4.7.3

虚拟内存管理—虚拟内存拷贝第85页

共

页进程创建是代价极高的操作，主要原因是创建进程时要拷贝父进程的地址空间。很多进程在创建后会很快调用exit退出立刻调用exec函数运行一个新的程序，做与父进程完全不同的事情。BSD公司提供了另外一个进程创建函数vfork。该函数不拷贝地址空间，父进程将自己的地址空间传递给子进程然后睡眠，直到子进程调用exec运行一个新程序或调用exit退出，在此之前子进程可以一直使用父进程的地址空间。SystemV中采用了另外一种办法——CopyonWrite(写时拷贝)。进程创建时父子进程使用同一个虚拟地址空间，但有各自独立的页目录和页表。始时，父子进程页表项的内容基本相同，但各页的保护权限都被设置为只读。如果此后父进程或子进程要修改某个页面，系统会产生一个保护异常。异常处理函数识别出这种情况，而后为修改进程创建页面的一个新副本。如果没有修改页面的动作，父子进程就会一直共享同一个页面，不需要再拷贝。4.7.3

虚拟内存管理—虚拟内存拷贝第86页

共

页Linux提供了很灵活的进程创建机制，它同时支持上述两种改进。如果在进程创建标志中指出了CLONE_VM，则父子进程共用同一个虚拟地址空间，就连页目录都是共用的。一般的进程创建采用CopyonWrite技术。从父进程中拷贝页目录和页表，但将父子进程的页表项都设置为只读，页面的拷贝推迟到写操作真正发生时才进行。为了拷贝虚拟地址空间将父进程的内存结构mm_struct拷贝到子进程拷贝的内容包括父进程的各个内存区域结构

vm_area_struct和每个内存区域结构对应的页目录项、页表项，但不拷贝页面的内容。因为在拷贝时子进程中并没有对应的内存区域结构、页目录、页表等，所以要边拷贝边创建。4.7.3

虚拟内存管理—虚拟内存拷贝第87页

共

页如果标志clone_flags中设置了CLONE_VM，则父子进程要共用同样的内存结构mm_struct，因此只需将父进程内存结构的引用计数加1即可。返回0。向内核内存管理器申请一个mm_struct结构mm。从父进程拷贝该结构的内容。将该结构的引用计数值设为1。将申请到的mm_struct结构填入进程结构：tak->mm=mm。为新进程创建段LDT。向内核虚拟内存管理器申请64KB(16页)的空间，将父进程的LDT拷贝到该空间中，让新进程的mm->segments指向这个新建的LDT，并将新LDT加入

GDT表。用新LDT设置新进程状态段中的ldt域(tss.ldt)。为新进程建立页目录。申请一个物理页作为新进程的页目录，将它的用户页表部分(前0x300)清0，内核页表部分(后0x100)从init_task的页目录中拷贝。因此，所有进程页目录的后0x100项全都一样，也就是说，所有进程的虚拟地址空间中的3GB到4GB的内容都一样。4.7.3

虚拟内存管理—虚拟内存拷贝第88页

共

页将新页目录的首地址放到新进程TSS段的CR3域和新进程内存结构的页目录域中。将父进程的所有虚拟内存区域都拷贝到新进程中来。

Inline

int

dup_mmap（struct

mm_struct

*mm);4.7.3

虚拟内存管理—父进程虚拟内存区域拷贝第89页

共

页Inline

int

dup_mmap（struct mm_struct

*mm);找到父进程的vma链表：mpnt。如果mpnt为空，转(8)。从内核内存管理器申请一个vm_area_struct：tmp。拷贝父进程的vm_area_struct结构的信息*tmp=*mpnt。调整相应的域的内容。拷贝页目录、页表项。将tmp加入内存管理结构mm的vma的队列中。转（2）。建立avl树。刷新TLB表。4.7.3

虚拟内存管理—虚拟内存重建第90页

共

页进程创建时，通过虚拟内存拷贝，已经为子进程建立了虚拟地址空间(内存共享或Copy

on

Write)。当进程希望改变自己的行为时，它可以调用函数exec，根据新的执行映像重建自己的虚拟地址空间。函数exec所做的工作是从磁盘读入程序的执行映像、据此建立进程的虚拟地址空间，而后执行该映像。这是一件代价很高的工作，因此在操作系统的发展史上对该函数也有许多的改进。Linux采用的是SystemVRelease

4的内存映射机制。4.7.3

虚拟内存管理—虚拟内存重建第91页

共

页内存映射内存映射机制将虚拟内存和文件系统结合起来，用来直接将文件映射到进程的虚拟地址空间。当执行映像执行时，加载程序实际上并没有把它装入物理内存，而仅仅是在内存中建立了一系列的数据结构。只有当进程引用某一部分的映像时，这部分映像才真正加载到内存。这种映像文件和进程虚拟地址空间的连接叫做内存映射。虚拟地址与数据对象进程所有的有效虚拟地址就是那些映射到数据对象上的地址。对象(映射文件)为映射它的页面提供了持久性后备存储。物理内存只是映射对象的缓存而已。4.7.3

虚拟内存管理—虚拟内存重建第92页

共

页进程的内存管理结构mm_struct中，包括当前执行映像的信息和一组vm_area_struct结构。大部分vm_area_struct结构描述的是虚拟内存区域到映像文件的映射，其中包括该区域对应的映像文件以及它在文件中的位置、进程对该区域的访问权限和对该区域的缺省操作。当把一个执行映像映射到进程的虚拟地址空间时，会产生一组vm_area_struct结构。每一个vm_area_struct结构对应执行映像的一部分：执行代码、初始化数据(变量)、未初始化数据、共享库等。Linux支持一系列标准的虚拟内存操作，当

vm_area_stmct结构创建时，系统会为每个虚拟内存区域选择一组正确的虚拟内存操作。4.7.3

虚拟内存管理—虚拟内存重建第93页

共

页完成执行映像加载的函数是exec，该函数在处理完参数以后，最终会调用函数do_execve。执行映像文件有不同的格式，如aout、elf,，java、script等。不同格式的执行文件，其映射方式也不相同，但通常都把文件中有相同属性和相同操作的部分映射到一个内存区域，如代码区(txt)、初始化数据区(data)、末初始化数据区(bss)等。函数do_execve首先释放当前进程的虚拟地址空间，而后按照执行映像格式将执行映像划分成不同的区域，最后分别调用函数

do_mmap完成每个区域的映射。另外，专门构造一个堆栈(stack)区域，用做进程的用户堆栈，其