操作系统讲义-第五章

操作系统讲义西安财经学院操作系统概述系统启动及用户界面进程管理与调度进程同步第一章第二章第三章第四章文件管理第七章Contents课程内容安排

西安财经学院设备管理第六章存储器管理

第五章第五章存储管理

连续内存分配方式

1存储器管理基础知识2离散分配方式3西安财经学院虚拟存储管理4Linux系统中的内存管理55.1存储器管理基础知识1、多级存储器结构按照访问速度、易修改性可划分为不同的层次存储器的分层2、程序的执行

3、地址的类型逻辑地址：程序内部的代码或数据地址。物理地址：代码或数据实际存放的内存单元地址。4、地址的绑定可以在三个阶段进行：编译阶段：形成绝对代码加载阶段：生成可重定位代码执行阶段：需要硬件支持的地址映射内存管理单元Memory-ManagementUnit(MMU)是硬件设备，负责将逻辑地址映射为物理地址动态重定位5.2、连续内存分配方式1、连续分配存储管理方式对换内存通常被划分为两个分区（partitions）:系统区：常驻操作系统，通常位于内存低端用户区：提供给用户（进程）使用，常位于内存高端连续内存分配是指：从用户区中为每个进程分配一个单独的、连续的内存空间。主要有以下两种方式单一连续分配方式多分区式分配方式固定分区式动态分区式（可变分区式）

单一连续分配方式最简单只能用于单用户、单任务系统存储保护机制存储管理单元，MMU或者不采用任何存储保护机制出于信任，或采用再启动方式，多分区式分配方式支持多道程序，用户区被进一步划分为若干个分区每一个分区装载一个进程多道程序度与分区的个数有关根据分区大小是固定的还是可变的固定分区方式大小固定；等大小or不等大小动态分区方式（可变分区方式）固定分区分配方式支持多道程序，用于60年代IBM－360的MFT中分区的划分方法，两种等大小不等大小但分区的大小一旦确定就不再发生变化分配算法：按大小顺序建立分区使用表操作系统作业A作业B作业C030K45K75K分区号大小（KB）起始地址(K)状态11530已分配23045已分配35075已分配4100125已分配缺点内存利用率低定义：内部碎片和外部碎片内部碎片：已经分配出去但得不到利用的存储区域外部碎片：不能被利用的小分区解决方案：动态分区动态分区分配方式能根据进程实际需要的内存大小，动态分配能减少内部碎片关键数据结构：记录内存的使用情况，特别是空闲内存分配算法分配和回收操作数据结构空闲分区表，占用额外的空间空闲分区链，利用空闲分区分区分配算法在将一个新作业装入内存时，要从空闲分区表或空闲分区链中，选出一个分区分配给该作业，有三种常见的分配算法首次适应算法FF：FirstFit最佳适应算法：BestFit=smallest最差适应算法：WorstFist＝largest分配设请求的分区大小为u.size；利用某种分配算法，找到待分配的分区，大小为m.size根据上述分区分配算法，有m.size>u.size判断m.size-u.size与min_size的大小

min_size为事先约定的最小分区大小>，分割，分割出来的分配出去，余下的加入空闲数据结构否则，直接分配将分配到的分区的首地址返回可以看出，动态分区分配方式中内部碎片最大不超过min_size回收要考虑合并向前合并只需修改前一个空闲分区表项中的大小向后合并只需修改后一个空闲分区表项中的起始地址和大小与前后同时合并修改前一个空闲分区表项中的大小，并取消后一个分区表项无相邻空闲分区，无需合并建立一个新的表项，填写相关信息，插入上述过程中，根据链表的维护规则，可能需要调整相应表项在空闲链表中的位置随着分配的进行，空闲分区可能分散在内存的各处尽管有回收，但内存仍然被划分的越来越碎，形成大量的外部碎片碎片整合解决方案之一：紧凑Compaction(移动、搬家)针对外部碎片：采用紧凑的方法紧凑：通过移动进程在内存中的位置，把多个分散的小分区拼成大分区需要动态重定位技术支持动态重定位分区分配算法：引入紧凑和动态重定位技术的动态分区分配算法基本与动态分区分配算法相同紧凑的时间开销Swapping对换（交换）对换是指把内存中暂时不能运行的进程，或暂时不用的程序和数据，换出到外存上，以腾出足够的内存空间，把已具备运行条件的进程，或进程所需要的程序和数据，换入内存。能提高内存利用率对换的单位：进程：整体对换；进程对换属于中级调度页、段：部分对换属于虚存管理对换技术需要实现三个方面的功能对换空间的管理进程的换出进程的换入对换空间高速磁盘区，足够存放所有用户的全部内存映像为提高速度，考虑连续分配方式，忽略碎片问题需提供数据结构对空闲盘块进行管理方法类似动态分区分配方法进程的换出第一步：选择被换出的进程算法：轮转法调度：配额用完后被换出基于优先级的调度：换出低优先级进程，换入高优先级进程第二步：换出确定要换出的内容非共享的程序和数据段的换出共享的程序和数据段的换出：计数器申请对换空间，换出，并修改相关数据结构进程的换入第一步：选择被换入的进程考虑“静止就绪状态”的进程＋其他原则第二部：申请内存并换入申请成功申请失败：利用对换技术腾出内存5.3、离散分配方式

分页存储管理方式碎片<页分段存储管理从逻辑上进行分段段页式存储管理1、分页存储管理方式1）将一个进程的地址空间分成若干个大小相等的片，称为页面或页（pages）2）内存空间也分成与页大小相同的若干个存储块，称为物理页或页框（pageframes）序号：0，1，……，n页/页框大小：取2的幂，512~8192B（linux中是4k）地址结构页内偏移：相对于页（页框）起始地址的相对地址页（页框）号S对于32位地址长度若页（页框）的大小为4KB，则需要使用低端12位表示页内偏移剩余的高端20位可以表示220个页（页框），1M个必须在进程的逻辑地址空间和内存的物理地址空间之间建立一个映射关系。每个进程都拥有各自的页面映射表，即页表按序号，进程地址空间中的每个页在页表中都由一个页表项表示页表项中记录的对应的物理页框的序号可以实现从页号到页框号的映射地址映射示意图页表寄存器页表起始地址页表长度越界中断页号2页内地址逻辑地址页号页框号01231265843+>内存单元

物理地址页表+联想存储器，快表，(TLBs)每次访问指令或数据需要两次寻址内存，一次是访问页表，一次是访问数据/指令，因此使用快表可以提高效率。快表寄存器：一键一值与页表并行查询昂贵，通常8~2048项如果A´在快表中，输出页框号A’’否则从内存页表中获取页框号TLB缺失命中率页号可在快表中访问到的百分比进程切换时需要替换TLB中的内容具有块表的地址变换机构

页表寄存器页表起始地址页表长度越界中断页号2页内地址逻辑地址+>内存单元物理地址页表+页号页框号01231265843页号页框号12658

TLB多级页表：页目录指针表，页目录表，二级页表

反置页表：内存中存放的页表是按照页框号顺序排列。用哈希函数加快搜索。常用于PowerPC、UltraSPARC和IA-64体系结构中。2、分段存储管理方式引入分段的目的，是为了满足用户在编程和使用上的需求（逻辑上），如共享段、分段保护、动态链接等。在用户看来：程序是一些程序段的集合。如主程序，过程，函数，方法，对象等。程序中是二维地址编译器自动为程序构建段。分段的硬件支持：段表：段在内存中的基地址段的长度段表基址寄存器(STBR)指向段表在内存中的位置段表长度寄存器(STLR)存放一个程序中段的个数段号段内地址31016

15段表举例

分段的地址变换机构

段号0123段表寄存器段表起始地址段表长度越界中断段号2段内地址逻辑地址+>内存单元

物理地址段表+1K150200360FA1B658AA45704310段长基地址分页和分段的主要区别角度和目的不同分页：面向系统，物理上离散，减少外部和内部碎片，提高内存利用率页是信息的物理单位分段：面向用户，逻辑上离散，满足用户的需求段是信息的逻辑单位，意义相对完整分页管理中，地址空间是一维的，而分段管理中，地址空间是二维的。大小不同分页：大小固定，由硬件决定分段：不固定，划分由程序决定，在编译时确定分段的好处可重定位，方便共享，方便保护可以动态增长，动态链接针对段的内存管理由于段长不固定，采用动态分区管理方式分配：首次适应、最佳适应等等由于大小不固定，存在外部碎片要考虑“紧凑”由于采用动态分区管理方式内部碎片很少3、段页式存储管理方式考虑在分段的基础上分页与单纯的分段相比在段表项中存放的不是段的起始地址，而是段所对应的页表的起始地址例：IA32的地址转换（IntelArchitectual32CPU）逻辑地址——>线性地址——>物理地址段页式地址映射2-levelpagetable16位32位用户程序段页式地址映射示意图

5.4虚拟存储管理

5.4.1、虚拟存储管理的概念当程序的存储空间要求大于实际的内存空间时，就使得程序难以运行了．虚拟存储技术就是利用实际内存空间和相对大的多的外部储存器存储空间相结合构成一个远远大于实际内存空间的虚拟存储空间，程序就运行在这个虚拟存储空间中．能够实现虚拟存储的依据是程序的局部性原理，即程序在运行过程中经常体现出运行在某个局部范围之内的特点．在时间上，经常运行相同的指令段和数据（称为时间局部性），在空间上，经常运行与某一局部存储空间的指令和数据(称为空间局部性），有些程序段不能同时运行或根本得不到运行．虚拟存是把一个程序所需要的存储空间分成落干页或段，程序运行用到页和段就放在内存里，暂时不用就放在外存中．当用到外存中的页和段时，就把它们调到内存，反之就把它们送到外存中．装入内存中的页或段可以分散存放．5.4.2、虚拟（请求）页式存储管理

虚拟页式存储管理和一般的页式管理有相同之处，只不过各进程页表要增加指明每个页面所在的位置，也就是这个页面是在内存还是外存中的具体物理地址．当进程工作到需要使用某个页面时，如果通过查页表发现该页表是在外存中，此时要进行缺页中断处理．也就是暂停当前进程的运行，转而执行缺页中断处理程序，把所需要的页面调入内存，在页表上填写该页面的物理页面号，注名该页面已经进入内存，再恢复当前进程的运行。1、虚页管理中页表的形式为了处理虚存管理中的问题，需要对页表进行扩充。针对不同类型的CPU，页表中的访问控制信息可以有所不同。下图是AlphaAXP结构中的页表项：V

有效，置位表示该页有效。FOR``FaultonRead'',当该位置位时，若试图读取该页时报错，并将控制权交给操作系统。FOW``FaultonWrite'',写该页错误。FOE``FaultonExecute'',执行该页错误。ASMAddressSpaceMatch.用于操作系统从缓冲区中清除某些页。GHGranularityhint粒度设置，用一个转换区来匹配。KRE

内核模式代码可读。URE

用户模式代码可读。KWE

内核模式代码可写。UWE

用户模式代码可写。_PAGE_DIRTY

该页被修改过，需要写到交换文件。_PAGE_ACCESSED

该页被访问过。PFNpageframenumber

若该页V标志置位，该字段为物理页框号；若V标志未置位，则该字段表示外存地址。2、请求页式管理中的地址转换

请求分页管理中指令寻址的流程

3、页面置换页面调入/清除策略：请求式调入/清除，预测式调入/清除。页面分配策略：固定分配和动态分配。页面置换策略：局部置换和全局置换。固定分配与局部置换结合：分配给每个进程的页框数一定。动态分配与全局置换结合：先为每个进程分配初始页框，随缺页中断增加分配。页面置换算法采用局部性原理进行预测，常用固定分配页框数的条件下对算法进行评估。下面将用实例说明介绍一些经典算法。假设某进程有5页代码，系统给其分配3个页框，其运行过程可以用固定的12次访页轨迹来描述。1）、最佳置换算法(OPT)：前提是预先知道进程的运行轨迹。无法实现，用于评价其它算法。主要思想是将永不使用，或在最长时间内不被使用的页面换出内存页面走向 123412512345缺页及置换 *******112124125425325123产生了7次缺页中断，4次置换，缺页率=7/(7+5)=58.3%2）、先进先出置换算法（FIFO）选择最先进入内存的页面进行置换。页面走向1 23412512345缺页及置换*********112123413412512423532534产生了9次缺页中断，6次置换，缺页率=9/(9+3)=75%。实现简单（通过链表按照时间先后顺序链接），但容易产生Belady异常现象（分配更多的页框，却产生更多的缺页中断）。Belady现象如，给该进程分配4个页框时：页面走向 123412512345缺页及置换 **********1125234123451345124512345231234123产生了10次缺页中断，7次置换，缺页率=10/(10+2)=83.3%。3）、最近最久未使用算法（LRU）淘汰最长时间未被使用的页面。需设置页面访问记录（常采用移位寄存器或栈来实现）。移位寄存器：访问某页时，将其寄存器最高位置1，定期向右移动寄存器，高位补0。选择淘汰寄存器值最低的页面。栈：访问某页时将该页号从栈中移出，并将其压入栈顶。淘汰栈底的页。页面走向 123412512345缺页及置换 **********121432521143321321214152215543324产生10页中断，其中7置换，缺页率=10(10+2)=83.3%比FIFO实现代价高，不过一致性更好。没有Belady现象。在给定该进程4个页框的情况下：页面走向 123412512345缺页及置换 ********112521443211524215432155432321432114322143产生8次缺页中断，其中4次置换，缺页率=8/(8+4)=66.6%4）时钟置换算法/最近未使用算法（Clock/NRU）是LRU和FIFO的折衷。设置1位访问位，将内存中的页面循环链接。5）、最少使用算法（LFU）按照一段时间内对页面的访问频率大小来选择淘汰。与LRU采用同样的寄存器机制。4、请求页式管理性能分析1）缺页率和有效访问时间假设缺页率为p，有效访问时间=（1-p）×存储器访问时间+p×缺页中断时间有效访问时间与缺页率成正比。2）工作集 工作集np工作集：在某一段时间间隔内，进程实际要访问的页面的集合。为了减少缺页，尽量使工作集在内存中。工作集w(t,⊿)是二元函数，与时间t和窗口尺寸⊿有关。不同时刻的工作集不同，不同大小的窗口工作集也不同。抖动在内存中引入过多的进程，将会出现“抖动”现象。抖动产生的原因是进程之间循环地占用页面，导致进程循环产生缺页中断，致使就绪队列空，CPU利用率降低。系统为了提高CPU的利用率，有允许更多的进程建立，从而产生频繁的页面换入/换出的恶性循环。运行道数CPU利用率避免抖动的方法采取局部置换策略，缩小抖动范围。在CPU调度中引入工作集算法：在引入新进程时，检察现有进程的工作集。L=S准则：产生缺页的平均时间等于系统处理缺页的平均时间(实践经验)。挂起若干进程。5.4.3请求段式存储管理段表的结构

段号段地址段长度中断位存取方式访问位修改位增补位外存地址地址转换流程5.4.4请求段页式存储管理5.5Linux系统中的内存管理Linux系统对物理内存空间的分配进程虚存空间的分布静态变量控制寄存器控制寄存器（CR0～CR3）用于控制和确定处理器的操作模式以及当前执行任务的特性。CR0中含有控制处理器操作模式和状态的系统控制标志；CR0中的PE(ProtectionEnable)标志，用于启用保护模式。PG(Paging)标志，用于开启分页机制。ET(ExtensionType)标志，MP(MonitorCoprocessor)标志，EM(Emulation)标志和TS(TaskSwitched)标志相互组合，用于设置协处理器。CR1保留不用；CR2含有导致页错误的线性地址；CR3中含有页目录表物理内存基地址，因此该寄存器也被称为页目录基地址寄存器PDBR（DirectoryBaseaddressRegister）。控制寄存器（续）段选择符程序中由16位的段和32位的偏移地址构成48位的逻辑地址（虚拟地址）。段地址使用16位的段选择符指定，其中14位可以选择16k个段。段寄存器有cs,ss,ds,es,fs,gs（为16位）内存管理寄存器GDTR、LDTR、IDTR和TR都是段基址寄存器，这些段中含有分段机制的重要信息表。GDTR、IDTR和LDTR用于寻址存放描述符表的段。TR用于寻址一个特殊的任务状态段（TaskStateSegment，TSS）。TSS中包含着当前执行任务的所有执行现场信息。内存管理寄存器（续1）（1）全局描述符表寄存器GDTRGDTR寄存器中用于存放全局描述符表GDT的32位的线性基地址和16位的表限长值。基地址指定GDT表中字节0在线性地址空间中的地址，表长度指明GDT表的字节长度值。（2）中断描述符表寄存器IDTR与GDTR的作用类似，IDTR寄存器用于存放中断描述符表IDT的32位线性基地址和16位表长度值。内存管理寄存器（续2）（3）局部描述符表寄存器LDTRLDTR寄存器中用于存放局部描述符表LDT的32位线性基地址、16位段限长和描述符属性值。包含LDT表的段必须在GDT表中有一个段描述符项。当进行任务切换时，处理器会把新任务LDT的段选择符和段描述符自动地加载进LDTR中。（4）任务寄存器TRTR寄存器用于存放当前任务TSS段的16位段选择符、32位基地址、16位段长度和描述符属性值。它引用GDT表中的一个TSS类型的描述符。当执行任务切换时，处理器会把新任务的TSS的段选择符和段描述符自动加载进任务寄存器TR中。X86结构中的段描述符

一种段描述符表中的段描述符。段描述符与分页机制的连接

虚拟页式存储管理页表格式

P位是存在位，如果P=1，表示页表地址指向的该页在内存中，如果P=0，表示不在内存中。R/W位、U/S位，这两位为页目录项提供硬件保护。A:AccessedD:DirtyAVAIL位供系统员使用。2、Linux的内存管理机制每当启动一个新的进程，Linux都为其创建一个进程控制块(task_struct，include/linux/sched.h)。在创建过程中，每个进程(根据需要)创建并初始化新页目录，设置页目录基地址寄存器，在GDT中添加进程对应的TSS项和LDT项，创建并初始化该进程的LDT。

Linux虚拟存储管理采用“按需调页”的原则来分配内存页面，执行进程的页面总会在外存与内存之间不断交换，从而避免页表过多占用存储空间。创建一个进程时页面分配的情况：进程控制块(1页)，内核态堆栈(1页)，页目录(1页)，页表(需要的n页)。在进程以后的执行中，再根据需要逐渐分配更多的内存页面。

Linux交换空间交换空间是在外存中开辟一定的空间来临时存放从内存中调出的页面，其存储区域自然也是按页划分的。Linux采用了块设备和交换文件两种形式来保存换出的页面，但是这两种形式的内部结构是一致的。有时候，为了优化系统性能，会定义不止1个交换空间，因而Linux虚拟存储管理实现了并行管理多个交换空间，这些交换空间均定义在同一个数据结构中(swap_info_struct[MAX_SWAPFILES]，mm/swap.c，其中MAX_SWAPFILES定义为最大的交换空间数量)。Linux操作系统采用了请求式分页虚拟存储管理方法。系统为每个进程提供了4GB的虚拟内存空间。各个进程的虚拟内存彼此独立。3、进程虚存空间的管理3.1．内核空间和用户空间进程运行时能访问的存储空间只是它的虚拟内存空间。对当前该进程而言只有属于它的虚拟内存是可见的。在进程的虚拟内存包含着进程本身的程序代码和数据。进程在运行中还必须得到操作系统的支持。进程的虚拟内存中还包含着操作系统内核。Linux把进程的虚拟内存分成两部分，内核区和用户区。操作系统内核的代码和数据等被映射到内核区。进程的可执行映像（代码和数据）映射到虚拟内存的用户区。进程虚拟内存的内核区的访问权限设置为0级，用户区为3级。内核访问虚存的权限为0级，而进程的访问权限为3级地址映射P10G3G4GuserspacekernelP20G3G4GuserspacekernelPn0G3G4Guserspacekernel。。。CPU逻辑空间0G3G4GuserspacekernelPi物理内存0G1GnGuserspacekernel硬盘空间swapspace进程切换换入换出进程虚拟空间及内存映射3.2、Linux管理进程虚拟内存的用户区进程虚拟内存的用户区分成代码段、数据段、堆栈以及进程运行的环境变量、参数传递区域等。每一个进程，用一个mm_struct结构体来定义它的虚存用户区。mm_struct结构体首地址在任务结构体task_struct成员项mm中：structmm_struct*mm；mm_struct结构定义在/include/linux/schedul.h中。mm_struct表示进程的地址空间structmm_struct{ intcount; //引用计数 pgd_t*pgd;//指向进程页目录表 unsignedlongcontext;//当前进程使用的段起始地址 unsignedlongstart_code,end_code,start_data,end_data;//分别为代码段、数据段的首地址和终止地址 unsignedlongstart_brk,brk,start_stack,start_mmap;//未初始化数据段的起始地址，最后地址，用户态堆栈的起始地址 unsignedlongarg_start,arg_end,env_start,env_end;//分别为参数区、环境变量区的首地址和终止地址 unsignedlongrss,total_vm,locked_vm;//rss为进程内容驻留在物理内存的页面总数 unsignedlongdef_flags; structvm_area_struct*mmap;//虚拟内存区队列指针 structvm_area_struct*mmap_avl;//avl树指针 structsemaphoremmap_sem;//对mmap操作的互斥信号量};进程内存管理结构3.3、进程的虚存区域进程的虚拟存储空间由若干个虚拟存储区域组成。虚拟存储区域连接成一个AVL树。一个虚存区域是虚存空间中一个连续的区域，在这个区域中的信息具有相同的操作和访问特性。每个虚拟区域用一个vm_area_struct结构体进行描述，它定义在/include/linux/mm.h中：structvm_area_struct{//VM区参数 structmm_struct*vm_mm; unsignedlongvm_start，vm_end; pgprot_tvm_page_prot; unsignedshortvm_flags;//进程按地址排序的VM区的AVL树 shortvm_avl_height; structvm_area_struct*vm_avl_left; structvm_area_struct*vm_avl_right;进程按地址排序的VM区队列链接 structvm_area_struct*vm_next;对共享节点/内存的链接 structvm_area_struct*vm_next_share; structvm_area_struct*vm_prev_share; structvm_operations_struct*vm_ops; unsignedlongvm_offset; structinode*vm_inode; unsignedlongvm_pte;};vm_area_struct结构体（1）vm_mm指针指向进程的mm_struct结构体。（2）vm_start和vm_end虚拟区域的开始和终止地址。（3）vm_flags指出了虚存区域的操作特性：

VM_READ 虚存区域允许读取

VM_WRITE 虚存区域允许写入

VM_EXEC 虚存区域允许执行

VM_SHARED 虚存区域允许多个进程共享

VM_GROWSDOWN 虚存区域可以向下延伸

VM_GROWSUP 虚存区域可以向上延伸

VM_SHM 虚存区域是共享存储器的一部分

VM_LOCKED 虚存区域可以加锁

VM_STACK_FLAGS虚存区域做为堆栈使用（4）vm_page_prot虚存区域的页面的保护特性。（5）若虚存区域映射的是磁盘文件或设备文件的的内容，则vm_inode指向这个文件的inode结构体，否则vm_inode为NULL。（6）vm_offset是该区域的内容相对于文件起始位置的偏移量，或相对于共享内存首址的偏移量。（7）所有vm_area_struct结构体链接成一个单向链表，vm_next指向下一个vm_area_struct结构体。链表的首地址由mm_struct中成员项mmap指出。（8）vm_ops是指向vm_operations_struct结构体的指针。该结构体中包含着指向各种操作的函数的指针。（9）所有vm_area_struct结构体组成一个AVL树。进程虚拟空间管理AVL树是一种具有平衡结构的二叉树。

vm_avl_left左指针指向相邻的低地址虚存区域，

vm_avl_right右指针指向相邻的高地址虚存区域

mmap_avl表示进程AVL树的根，

vm_avl_hight表示AVL树的高度。（10）vm_next_share和vm_prev_share，把有关的vm_area_struct结合成一个共享内存时使用的双向链表。4、Linux的分页式存储管理页表是从线性地址向物理地址转换中不可缺少的数据结构，而且它使用的频率较高。页表必须存放在物理存储器中。虚存空间有4GB，按4KB页面划分页表可以有1M页。若采用一级页表机制，页表有1M个表项，每个表项4字节，这个页面就要占用4MB的内存空间。由于系统中每个进程都有自己的页表，如果每个页表占用4MB，对于多个进程而言就要占去大量的物理内存，这是不现实的。在目前用户的进程不可能需要使用4GB这么庞大的虚存空间，若使用1M个表项的一级页表，势必造成物理内存极大的浪费。为此，Linux采用了三级页表结构，以利于节省物理内存三级分页管理把虚拟地址分成四个位段：页目录、页中间目录、页表、页内偏址。系统设置三级页表系列：页目录PGD（PaGeDirectory）、页中间目录PMD（PageMiddleDirectory）页表PTE（PageTablE）。Intelx86上的linux页表结构三级分页结构是Linux提供的与硬件无关的分页管理方式。当Linux运行在某种机器上时，需要利用该种机器硬件的存储管理机制来实现分页存储。Linux内核中对不同的机器配备了不同的分页结构的转换方法。对x86，提供了把三级分页管理转换成两级分页机制的方法。其中一个重要的方面就是把PGD与PMD合二为一，使所有关于PMD的操作变为对PGD的操作在/include/asm-i386/pgtable.h中有如下定义：

#definePTRS_PER_PTE 1024#definePTRS_PER_PMD 1//页目录项个数#definePTRS_PER_PGD 1024地址映射地址映射就是在几个存储空间（逻辑地址空间、线形地址空间、物理地址空间）或存储设备之间进行的地址转换。5、物理内存空间的管理1．物理内存的页面管理Linux对物理内存空间按照分页方式进行管理，把物理内存划分成大小相同的物理页面。在x86机器中一个页面的大小为4KB，定义在include/asm-i386/page.h文件中：

#definePAGE_SHIFT 12#definePAGE_SIZE (1UL<<PAGE_SHIFT)在Alpha、Sparc中一个页面大小8KB：

#definePAGE_SHIFT 13#definePAGE_SIZE (1UL<<PAGE_SHIFT)物理页面的管理结构Linux设置了一个mem_map[]数组管理内存页面。

mem_map[]在系统初始化时由free_area_init()函数创建，它存放在物理内存的底部（低地址部分）mem_map[]数组的元素是一个个的page结构体，每一个page结构体对应一个物理页面。page结构进一步被定义为mem_map_t类型，其定义在/include/linux/mm.h中：typedefstructpage{ structpage*next; structpage*prev; structinode*inode; unsignedlongoffset; structpage*next_hash; atomic_tcount; unsignedflags; unsigneddirty:16,age:8; structwait_queue*wait; structbuffer_head*buffers; unsignedlongswap_unlock_entry; unsignedlongmap_nr; }mem_map_t;count：是共享该页面的进程计数。age：标志页面的“年龄”。dirty：表示该页面是否被修改过。prev和next：把page结构体链接成一个双向循环链表。prev_hash和next_hash：把有关page结构体连成一个哈希表inode和offset：有关文件的inode和它们在文件中的偏移量。wait：是等待该页资源的进程等待队列的指针。flag：页面标志：map_nr：该页面page结构体在mem_map[]数组中的下标值，也就是物理页面的页号。flag：页面标志符号常量意义PG_locked 页面处于闭锁状态，正在装入该页面PG_error 页面装入时发生错误PG_referenced 页面已装入，可以访问PG_uptodate 页面内容更新过PG_free_after 关于页面的I/O过程结束，页面被释放PG_decr_after 关于页面的I/O过程结束，页面计数减少PG_swap_unlock_after 读出交换页面后，页面解除闭锁PG_DMA 页面可以用于DMA传送PG_reserved 页面被保留以后使用，当前禁止使用6、空闲页面的管理—Buddy算法Linux对内存空闲空间的管理采用Buddy算法，Buddy是“伙伴”、“搭档”的意思。Buddy算法是把内存中的所有页面按照2n划分，其中n=0～5，对一个内存空间按1个页面、2个页面、4个页面、8个页面、16个页面、32个页面进行六次划分。划分后形成了大小不等的存储块，称为页面块，简称页块。包含1个页面的页块称为1页块，包含2个页面的称为2页块，依此类推。Linux把物理内存划分成了1、2、4、8、16、32六种页块。对于每种页面块按前后顺序两两结合成一对Buddy“伙伴”按照1页面划分后，0和1页、2和3页…是1页块Buddy。按照2页面划分，0-1和2-3、4-5和6-7…是2页块Buddy。Linux把空闲的页面按照页块大小分组进行管理，数组free_area[]来管理各个空闲页块组。在/mm/page_alloc.c中定义如下：#defineNR_MEM_LISTS6staticstructfree_area_structfree_area[NR_MEM_LISTS];structfree_area_struct{ structpage*next; structpage*prev; unsignedint*map;};Linux通过free_area[]数组

采取两种方法管理空闲页面一种是使用位图，主要用于回收内存页。另一种是使用空闲页块组链表。主要用于分配内存页。Linux对内存页面块的每种划分都对应一个位图map（bitmap），free_area[]各个元素中的指针map指向相应页面块的位图，free_area[0]中的map指向内存按照1个页面划分时的位图，free_area[1]中的map指向内存按照2个页面划分时的位图…。位图中每一位（bit）表示一对Buddy页面的使用情况当一对Buddy的两个页面块中有一个是空闲的，而另一个全部或部分被占用时，该位置1。当这两个页面块都是空闲，或都被全部或部分占用时，对应的位置0。free_area[]数组指向的六个位图，放在内存mem_map的上方bitmap区域内。用来记录页块组使用情况的位图的长度不同，页块越小位图越长。系统按照Buddy关系把具有相同大小的空闲页面块组成页块组，即1页块组、2页块组……32页块组。每个页块组用一个双向循环链表进行管理，共有６个链表，分别为1、2、4、8、16、32页块的链表。这些链表是由空闲页面的page结构体双向连接而成，分别挂到free_area[]数组上。free_area[]数组元素中指针prev和next指向链表。

free_area[0]的指针指向20，即1页面块的链表，

free_area[1]的指针指向21，即2页面块的链表

……，

free_area[5]的指针指向25，即32页面块的链表在页块组链表中的page结构体通过prev和next相互链接。在请求内存分配时，系统按照Buddy算法，根据请求的页面数在free_area[]对应的空闲页块组中搜索。若请求的页面数不是2的整数次幂，则按照稍大于请求数的2的整数次幂的值搜索相应的页面块组。当相应的页块组中没有可使用的空闲页面块时就查询更大一些的页块组，在找到可利用的空闲页面块后，分配所需的页面。当某一空闲页面块被分配后，若仍有剩余的空闲页面，则根据剩余页面的大小把它们加入到相应的页块组中。在内存页面释放时，系统将做为空闲页面看待。然后检查是否存在与这些页面相邻的其它空闲页块，

若存在，则合为一个连续的空闲区按Buddy算法重新分组。Slab分配小于一页的内存核心思想是“存储池”。小块内存被看作对象，使用完之后不直接释放，而是缓存在存储池，从而避免了频繁创建/销毁对象的开销。最高层是cache_chain，这是一个slab缓存的链接列表cache_chain的每个元素都是一个kmem_cache结构的引用（称为一个cache）。它定义了一个要管理的给定大小的对象池。每个缓存都包含了一个slabs

列表，这是一段连续的内存块。存在3种slab：slabs_full完全分配的slabslabs_partial部分分配的slabslabs_empty空slab，或者没有对象被分配7、内存的分配与释放kmalloc()和kfree()

用于分配和释放连续的内存空间。kmalloc()主要在堆空间进行分配。对应于c语言函数库中的malloc()和free()函数。1.内存分配与释放的数据结构:blocksize表kmalloc()和kfree()分配和释放内存是以块（block）为单位进行的。可以分配的空闲块的大小记录在blocksize表中，它是一个静态数组，定义在/mm/kmalloc.c中kmalloc()和kfree()用于申请/释放较小的内存块。这些内存块来自free_area数组，由block_size表，size表，page_descriptor和block_header结构共同管理。这种方法申请的内存不会产生缺页中断。申请/释放较大的内存空间使用vmalloc()和vfree().由vmlist管理Linux维护三种vm_area_struct的链表：1、由mmap,vm_next表示的单向链表2、由mmap_avl,vm_avl_left,vm_avl_right表示的avl树3、由attaches,vm_next_share,vm_prev_share表示的共享内存段链表。blocksize表#ifPAGE_SIZE==4096staticconstunsignedintblocksize[]={ 32,64,128,252,508,1020,2040, 4096-16,8192-16,16384-16, 32768-16,65536-16,131072-16, 0};kmalloc（）的策略在使用kmalloc（）分配空闲块时仍以Buddy算法为基础，即以free_area[]管理的空闲页面块做为分配对象。重新制定了分配的单位，blocksize[]数组中的块长度。它可以分配比1个页面更小的内存空间。blocksize[]中的前7个是在1个空闲页面内进行分配，其后的6种分别对应free_area[]的1至32空闲页面块，当申请分配的空间小于或等于1个页面时，从free_area[]管理的1页面块中查找空闲页面进行分配。若申请的空间大于一个页面时，按照blocksize[]后六个块单位进行申请，从free_area[]中与该块长度对应的空闲页块组中查找空闲页面块。page_descriptor对kmalloc()分配的内存页面块中加上一个信息头，它处于该页面块的前部。页面块中信息头后的空间是可以分配的内存空间。加在页面块前部的信息头称为页描述符，定义在/mm/kmalloc.c中：

structpage_descriptor{structpage_descriptor*next;/*指向下一个页面块的指针*/ structblock_header*firstfree;/*本页中空闲块链表的头*/ intorder;/*本页中块长度的级别*/ intnfree;/*本页中空闲的数目*/};具有相同块单位和使用特性的页面块组成若干个链表。sizes表Linux设置了sizes[]数组，对页面块进行描述。数组元素是size_descriptor结构体，定义在/mm/kmalloc.c中：

structsize_descriptor{ structpage_descriptor*firstfree;/*一般页块链表的头指针*/ structpage_descriptor*dmafree; /*DMA页块链表的头指针*/ intnblocks;/*页块中划分的块数目*/ intnmallocs;/*链表中各页块中已分配的块总数*/ intnfrees;/*链表中各页块中尚空闲的块总数*/ intnbytesmalloced;/*链表中各页块中已分配的字节总数*/ intnpages;/*链表中页块数目*/ unsignedlonggfporder; /*页块的页面数目*/};

staticstructsize_descriptorsizes[]={ {NULL,NULL,127,0,0,0,0,0}, {NULL,NULL,63,0,0,0,0,0}, {NULL,NULL,31,0,0,0,0,0}, {NULL,NULL,16,0,0,0,0,0}, {NULL,NULL,8,0,0,0,0,0}, {NULL,NULL,4,0,0,0,0,0}, {NULL,NULL,2,0,0,0,0,0}, {NULL,NULL,1,0,0,0,0,0}, {NULL,NULL,1,0,0,0,0,1}, {NULL,NULL,1,0,0,0,0,2}, {NULL,NULL,1,0,0,0,0,3}, {NULL,NULL,1,0,0,0,0,4}, {NULL,NULL,1,0,0,0,0,5}, {NULL,NULL,0,0,0,0,0,0}};blocksize[]与sizes[]元素数目相同，它们一一对应。由kmalloc()分配的每种块长度的页面块链接成两个链表，一个是DMA可以访问的页面块链表，dmafree指向这个链表。一个是一般的链表，firstfree指向这个链表。

成员项gfporder是0～5，它做为2的幂数表示所含的页面数。block_header由sizes[]管理的各个页面块中每个块（空闲块和占用块）的头部还有一个对该块进行描述的块头