操作系统概论:第四章 内存管理 操作系统内存管理机制

内存管理的目标:

1.实现内存分配、内存回收等操作

2.提高内存利用率和内存的访问速度（即充分利用现有的内存资源，为应用程序提供方便的内存使用 方式和一个快速、安全且充分大的存储器）

程序的链接和装入：

链接 要解决的问题是将编译后的目标模块装配成一个可执行程序，分为静态链接和动态链接。

1. 静态链接:在程序运行前，用链接程序将目标模块筑接成一个完整的装 入模块,任务:一是对逻楫地址迸行修改，二是变换外部调用符号。

优点：运行速度较快

缺点：可执行文件较大，占用空间大，系统开销大， 程序开发不够灵活，修改一个模块会导致整个程序重新链接

2. 动态链接：可将某些目标模块的链接推迟到这些模块中的函数要被调用时再进行。

优点：节省内存和外存空间，方便程序开发。

缺点：增加了 运行的时间开销，使程序运行时的速度变慢。

程序装入：

装入方式：绝对装入方式、可重定位装入（静态装入方式）和动态运行时装入 方式

绝对装入方式：编译程序已知程序在内存中的位置，编译时产生物理地址的目标代码，装入程序按照装入模块的物理地址将程序和数据装入内存档‘

可重定位装入方式：编译时不知道程序在内存手的隼置,那么编译时就必须生成可重定位的代码，其中的地址都是逻辑地址，在程序装入内存时，再把逻辑 地址映射为物理地址。

程序装入时对目标程序中的指令和数据地址修改的过程 称为重定位。

静态装入方式的特点:

1..编译程序使目标模块的地址从0开始

2. 程序装入时， 装入程序根据内存的使用情况将装入模块装入到内存的某个位置，并对模块进行重定位。物理地址=有效逻辑地址+程序在内存中的起始地址

动态运行时装入：当一个进程在被换出之前的内存地址与后来被从外存调入时，地址映射延迟到进程执行时再进行

连续分配的存储管理方式:

类型：

1.单一连续区分配方式

适用于单用户单任务系统，内存分为系统区和用户区

2.固定分区分配方式

将用户内存空间分配成若干固定大小的区域，每一个区域 运行一道用户程序；分区的数量是固定的，大小也是固定的,每个分区大小相等的分配方式缺点是内存利用率比较低，主要用于一个计算机去控制多个相同对象的场合,如冶炼炉,超〈 分区大小不等：可以更好的利用内存 际乂归 分区结构：分区编号，分区大小,分区起始地址，分区状态 在一些实时系统中，固定分区的分配方式还是简单而有效的

3.动态分区分配方式

用户分区的数量和大小都是动态变化的

分配原理：系统初始只有一个大的空闲分区，当进程请求内存资源时，系统根 据请求资源的大小分配一片空闲区域给进程，当运行一段时间后，空闲分区可 能会散布在不连续的区域，这时系统会维护一个记录当前空闲分区情况的数据 结构，当进程请求内存时，系统从所有空闲分区中找一个合适大小的空间给进 程。

数据结构:空闲分区表和空闲分区链

空闲分区链可以动态的为每个分区建立一个节点，每个节点包括分区大小、分 区起始地址、指向前一个空闲分区节点的指针、指向后一个空闲分区节点的指 针。每个节点占用的内存可以动态分配、动态回收。

动态分区分配算法：

1 ) 首次适应算法FF

要求空闲分区链以地址递增的顺序进行链接，每次从链首开始查找，低地址空 间可能会被反复划分 缺点：造成空间浪金，内存碎片

2 ) 循环首次适应算法NF

不再每次从链首开始查找，而是从上一次查找的空闲分区的下一个空闲分区开 始查找，每次应设者一个起始查找指针,指示下一次查找的分区 优点：空闲区分布均匀，查找开销小，缺点：缺少空闲大的分区 3 ) 最佳适应算法BF

为了方便查找，把所有空闲区按照空闲分区的大小递增的顺序进行排列，总是 把大小和进程所请求的内存空间大小最接近的空闲分区分配给进程。

优点：避免了大材小用，提高了内存的利用率缺点：容易留下难以利用的小空闲区

? 基本分页存储管理方式：

把进程禽散的存储在内存中物理地址不连续的区域，这种内存管理方式称为离 散内存管理方式。

离散内存管理分配内存空间的管理方式：分页存储管理，分 段存储管理、段页式存储管理

基本概念：

页：将一个进程的逻辑地址空间分成若干个大小相等的片，称为页。

页框：将物理内存地址分成与页大小相同的若干个存储块，称为页框或页帧

分页存储：为进程分配内存时，以页框为单位将进程中的若干页分别装入多个 可以不相邻的页框中。

页内碎片：进程的最后一页一般装不满一个页框，而形成了不可利用的碎片， 称为「页内碎片L是一种内部碎片

页表：实现页号到页框号的映射，在基本的分页机制中，每个进程有一个页表， 进程的每一页在页表中有一个对应的页表项，页表在内存中连续存放。

分页存储管理方式的地址结构：

若用m位表示逻辑地址，页大小为2的n次方字节，则用低n位表示页内偏

移量w ,用高m-n位表示页号Po

公式：P=INT（A/L） W=MOD（A/L） A为逻辑地址L是页大小

分页地址变换：实现逻辑地址到物理地址的转换

公式：物理地址=页框号x页框大小+页内偏移量

为了减少CPU在有效访问内存时间上的开销，提高访问内存的速度，引入了快 表机制。

快表：也称转换后援缓冲（TLB ）是为了提高访存速度而采用的专用缓存，存放最近被访问过的页表项。

? 两级页表和多级页表：

页表再分页，就形成了两级或多级页表。

两级页表：将页表再分页，使得每个页表分页的大小与内存页框的大小相同， 并为它们编号。

逻辑地址结构：

页目录号p1 |页号p2 |页内偏移地址d

页目录号实际是一个索引值，，根据p1从页目录表项中找到页表所在的页框号， 页号P2是页表中的偏移量，根据p2可以知道应该从页表中的第p2项找到进 程页所在的页框号。

公式：进程A的物理地址=进程页所在的页框号x页框大小十页内偏移地址d

?基于分页的虚拟存储系统：

虚拟存储技术实现的基本思想是：只把进程的一部分装入内存，在进程执行的 过程中，CPU访问内存时如果发现所访问的内容不在内存中，则通过异常处理 将所需要的内容从外存调入内存。

虚拟存储技术的好处：

1）提高内存利用率

2 ）提高多道程序度

3 ）把逻辑地址 空间和物理地址空间分开，程序员不用关心物理内存的容量对编程的限制。

虚拟存储技术的特征：1）离散性 2 ）多次性 3 ）对换性 4 ）虚拟性

页表：页表是请求分页系统最重要的数据结构，其作用是描述记录页的各种数 据结构，包括在实现逻辑地址到物理地址映射时需要的页号和页框号的对应关 系。同时增加了请求换入和页置换时需要的数据。

状态位：表示页是否在内存中 访问字段：记录页最近是否被访问过

修改位：表示页最近是否被修改过保护位：访问权限，1可读可写，0只读

缺页异常机构：主要作用是在访问内存过程中发现缺页产生缺页异常信号，使 CPU中断当前控制流的执行，转去执行缺页异常处理程序，完成请求调页。

? 页分配策略：问题，最少页框数？如何淘汰页？分配算法？

最少页框数：是指能保证进程正常运行所需要的最少页框数。操作系统为进程 分配的页应该大于或者等于最少页框数。

页分配和置换策略：

页分配策略：固定分配策略和可变分配策略

页置换策略：局部置换和全局置换。1）局部置换是指发生置换时，只从请求置 换的进程本身的内存页中选择一个淘汰页，腾出内存空间，调入请求页。2 ）全 局置换是指发生置换时，从所有进程的内存页中选择被淘汰的页。

两种组合：1）固定分配局部置换 2）可变分配局部置换 3）可变分配全局置换 分配算法：

1 ） 平均分配算法n进程m页框，则分配INT[m/n]个页框，余数放入缓冲

2 ） 按比例分配算法为进程分配的页框数=进程页数/所有进程页数的总和 x页框数

3 ） 考虑优先权的分配算法

? 页调入策略：

1）系统可以在进程需要时将页调入内存有利于提高内存的利用率，但是对 系统的时间性能不利

2）采用预先调入页的策略将预计不久之后会被访问的也预先调入内存

? 页置换算法：

1 ） 最佳置换算法ORA :该算法选择以后永远不会被访问的页或者很长时间

不会被访问的页作为换出页（看后面谁最长时间不会被访问到就换出）

2 ） 先进先出置换算法FIFO :最简单。该算法是为每个页记录该页调入内存 的时间，当选择换出页时，选择进入内存时间最早的页（用指针指示当

前调入新页时，应淘汰的那页在队列中的位置，换出后，指针指向下一 个应淘汰的页）

3 ） 最近最久未使用的LRU置换算法：性能较好的算法。该算法是选择最近 最久未使用的页换出（看前面谁进来的时间最久，最长时间没被访问过）

其他置换算法①附件引用位算法②简单dock算法②改进型dock算法④最少 使用置换算法⑤页缓冲算法

请求调入和置换技术都是以时间换空间的技术

缺页率对有效访存时间的影响：

有效访问时间是成访存所用的时间。假设P为缺页率，ma为存储器访问时间，

根据实际性能取ma=100ms=0.1us

有效访存时间=（1-P）xma + Px缺页异常时间

引入工作集机制是为了能有效降低缺页率，从而提高访存的时间效率

抖动：由于多道程序度太高，运行进程的大部分时间都用于进行页的换入、换 出，而几乎不能完成任何有效工作的状态称为抖动。

抖动的预防：1）采取局部置换策略2 ）在CPU调度程序中引入工作集算法

3）挂起若干进程

?分段存储管理

引入分段机制的优点是方便编程、分段共享、分段保护、动态链接以及存储空

间的动态增长

分段：系统为每个进程建立一个段表，段表的每一个表项记录了的信息包括段 号、段长和该段的基址，段表存放在内存中。

段表:段表是操作系统维护的用于支持分段存储管理地址映射的数据结构

段基址就是段在物理内存中的起始地址，段大小也称段界限。

? 分页和分段的主要区别：

联系：分段和分页都属于离散分配方式，都需要通过数据结构和硬件的配合实 现逻辑地址到物理地址的映射。

区别：

1.页是按物理单位划分的，分页的引入是为了提高内存的利用率和支持 虚拟存储；分段是按逻揖单位划分的，引入分段是为了方便程序员编程。

2.页的大小是固定的，段的大小是不固定的

3.分页的地址是一维的，分段的地址是二维的