第一节

内存管理功能概括

内存空间的分配与回收、地址转换、内存共享、存储保护

进程的链接与装入

绝对装入、静态重定向、动态重定向

静态链接、装入时动态链接、运行时动态链接

绝对装入：逻辑地址等同物理地址、程序中一般采用符号地址代表绝对地址，不考

静态重定位：逻辑地址一整段直接映射到内存物理地址，占用连续内存空间、一次性分配、不可变、不可移动

动态重定位：先装一部分到某不知名区域，等真正需要执行时才进行物理地址转换，需要重定向寄存器、支持离散分配、可变大小、可以浮动、按需分配进入内存

静态链接：装入前一次性链接各个模块、变更各个模块内部地址与符号为逻辑地址

装入时动态链接：边装入边链接各个模块、形成各个模块逻辑地址

运行时动态链接：当真正需要执行时才开始链接形成逻辑地址，有必要才链接，不需要用的不链接

注：想象链接为将一系列模块串成一串链条，并形成逻辑地址，会是精确形象的理解

物理地址与逻辑地址

物理地址大小取决于硬件性能、逻辑地址大小取决于编址空间位数(地址线

进程各模块于链接阶段形成逻辑地址、操作系统于装入阶段将逻辑地址变为物理地址

逻辑地址转为物理地址的过程也被称为地址重定位

进程内存映像

计组中有对应内容，可以结合进程切换学习，意义不大

内存保护

上下限寄存器(物理地址上下限)；重定向寄存器、界地址寄存器；只于内核态修改访问

内存共享

页式共享、段式共享；共享段表、内存映射文件

共享段表/页表：作用与进程的页表项/段表项的意义一样，但其目的在于减少内存消耗

这样理解，多个进程共享一段代码，各自需要设置一个段表/多个页表项

当进程数量多时就浪费内存去存储重复的引用项，直接设一个共享表即可避免冗余

内存分配方式

单一连续分配、固定分区分配、动态分区分配，均为高级调度之事

固定分区分配：分区使用表；分区大小相同/不同；内部碎片、灵活度低、利用率一般

注：与磁盘分区分配策略需要有一定区分

动态分区分配：按需于装入前分配

动态分区内存回收：与前者相邻、与后者相邻、与前后均相邻，各自合并策略

分配算法：数据结构基于空闲分区链表；顺序、索引

顺序：首次、邻近、最佳、最坏；

/首次与邻近不需要排序，默认按地址查询即可

/最佳、最坏需要按容量排序，第一块最佳、第一块最差，相互对应容量递增与递减

/最佳适应是最烂的，产生最多的外部碎片(doges

索引：伙伴系统、哈希…

基本分页、基本分段

分页、分段目的不同，一者提高内存利用率，一者方便编程

均需要硬件地址变换机构，地址变换由操作系统发出、硬件执行，地址变换为硬件自动

页表项内容：页号、页内偏移量；段表项内容：段号、段长、段始地址

其中段、页号均是隐藏连续的，只需要知道段表、页表起始地址，即可算对应表项地址

页式中进程分配、主存分配均为页框；但Cache与主存交互依旧为块，主存按字读取

磁盘扇区，物理块大小一般与页面大小相同

页表寄存器、段表寄存器存储均为物理地址，而非虚拟地址

页表、段表项大小的计算，隐藏页号、段号，计算页内偏移量，段长、段首地址定位数

每个进程均对应一个页表寄存器、段表寄存器，但这是从分时角度谈的

基本页式/段式不存在缺页中断，全部页面均存于内存之中

基本页式/段式，分别需检查页号、段号、段长是否越界，一维、二维，页内不会越界

多级页表，其目的是将连续存放的页表变为离散分配，甚至可能被分散到磁盘，去读盘

多级页表的页表项数量不变，变的仅仅是存放的连续性；段/页内连续，段/页间随意

带快表的段、页式，主存与快表可串行亦可并行，多级页表建议使用快表

快表内提供的是页号、段初始地址、段长的直接映射，无论多级与否均直接访问

段页式，每个段一个页表，段表项中起始地址为页表地址，页表项大小必须是整数倍

注：页面大小一旦固定基本不变，由段本身补充长度去适应页面大小

访存次数而言，基本类型与多级类似略有区分，多级若有读盘，需要访盘再访存

随记

物理存取速度无法提升、逻辑存取速度可以由缓存等提升

地址转换机构存在意义为动态重定位，静态重定位不需任何寄存器，动态需至少一个

单一连续分配、固定分区分配适用静态重定位，其余均为动态重定位

因为仅有该两者连续分配、一次性、不需要浮动、不需要申请变换内存所需大小

动态重定位的地址重定位在执行时才开始，其余装入过程之内即完成地址转换

页式、段式不适合静态重定位，因为内存分配不连续、进程需要浮动变化分配大小

共享段表概念已有解释，本质是减少内存损耗提出的解决策略

地址转换包含工作：越界判定、快表寻找、多级页表/段表寻找、读取地址、形成地址

页表、段表的查询工作均为硬件自动实现，属于机制

进程页表不一定全部含于内存中，多级页表可能在磁盘，但无必要则常驻内存

注意一些细节：0-10位，表示11位的地址空间…

统考的陷阱：虚存中，地址变换机构形成物理地址，则，谁形成逻辑地址，于是

碎片是指空闲的一块，而不是指有数据的一块，对内碎、外碎均如此

综合题

3：段、页项的内容分别为：页号、页内偏移量；段号、段始址、段长；

页号、段号均是隐藏连续的，不占用存储空间，存于内存中可随机访问如数组般

段内容为起始地址，页内容为页号，五位页号只能三十二个，五位地址则可随意表示

何况页内偏移、段内偏移叠加至对应页号、块号上会发现明显的越界

4：十进制可以直接转十六进程，而不需要先转二进制再十六进制，是能口算的

5、7：基本页式/段式不需要考虑缺页中断的可能性，因为所有页均保持于内存中

只需要考虑当前访问地址是否合法即可：页式看页号、段式看段号和段长即可

10：当页式时，内存的分配均以块为标准，因而可以直接填作业号

11：关键在于第三小题

已知当前页面物理上连续存放，自然很容易得出第二页的物理地址

从物理地址也很容易得到两个页表项的页框号，直接截取前面几位就是物理页号

重点在于页表项地址的计算，需要从逻辑地址出发

当前页面的逻辑地址中可得出为第八号页面，因而对应第八号页表项，其中存储实页框

而由页表项地址和页表初始地址的连续关系，可以直接得到页表项的物理地址

那么第二个怎么办？逻辑上这是连续的一段代码，分散于两个页面，页号自然连续

何况图上也给出了解释，页表项、页均是连续对应的

对应第二个页面，虽然物理上相邻并不意味着逻辑上必须相邻，但题目给出图示信息

两者页表项是连续的，因而页面物理相邻逻辑也同样相邻，题设信息的一部分

统考-55题：

页面大小4KB，页内占12位，页号为2；

页号为2，对应页不存在；因而对应页框号无用

系统分配两个“固定页框”，因而采用Clock算法替换一页换出内存，将页号2，换入

因而换入位置为页框60；页框物理位置是不变的，只是内容变化了而已；

毕竟页表的内容：页号、页框号（内存物理地址号）

第二节

局部性原理

时间局部性：未来一段时间内可能会重复访问该数据

空间局部性：未来一段时间内可能会访问内存地址物理上邻接的数据

虚存特性

多次性：动态链接、动态装入；逻辑上提升访存、访盘速度

对换性：中级调度、非常驻内存性（PCB，页表，这类内容依旧常驻内存）

虚拟性：装入、调度、置换用户不可视；逻辑上提升容量与访问速度

虚存技术特征

一定容量的内存与外存、地址编址空间(地址总线)；页表机制、中断机构、地址变换

页表机制：软件维护、硬件使用和访问

中断机构：中断处理程序由软件提供，中断处理由硬件实现

地址变换机构：操作系统引用，地址变换机构硬件实现，界地址、重定位寄存

其中需要注意的是，地址变换机构在转换地址过程中就引用了页表机制

页表、中断、地址变换机制实现

页表机制：页表项中额外增加状态位、访问位、修改位，访问位长度不固定，其余固定

缺页中断机构：阻塞进程、中断处理、唤醒进程；属于异常、执行中的异常

缺页中断与地址变换、页面调度、虚存运行过程：

注：快表访问后得到的就是实页号，不用怀疑，无非需要访存得到数据罢了

注：访存得到数据的过程可以结合计组存储系统共同复习，即为对主存的数据访问

页框分配与调度细节知识点

驻留集：进程驻留于内存中页框的数量，也是分配数量；多了少了都不好

内存分配策略：固定分配局部、可变分配全局、可变分配局部；统考中考察第一者为主

固定分配又可分为平均分配、比例分配、混合式分配

可变分配全局、可变分配局部需要记忆各自特性，考察虽不深刻

调度时机可分为：请求式、预调式(参考流水线预调入，但性能远不如流水线预调好)

调度来源：磁盘交换区，本调度即为中级调度本身；分为充足交换区、不充足、UNIX类

页面置换算法

FIFO、LRU、CLOCK、改进型CLOCK

置换算法优先保留已访问页，去除未访问页；访问保留优先级大于修改

抖动与工作集

抖动根本原因是分配物理块太少或内存太小，导致频繁磁盘中级调度

工作窗口是过去一段时间内进程访问的页面集合，工作窗口同样是过去页面去重集合

其可帮助预测未来访问可能性，驻留集需要大于等于工作集，仍然强调一件事：未来

内存映射文件

系统调用，产生请求式调页文件，调入仅是映像，真正使用到某页才调入

内存映射文件被关闭时，才会一次性写回磁盘，回写法，不可能采用全写法，计组内容

共享内存的实现基于内存映射文件实现，只需要让页表项指向对应物理地址即可

虚存性能

页面越大，命中率越高、缺页次数越少、页内碎片越大、页表越短、页表项越少

页面越小，命中率越低、缺页次数越多、页表越长

缺页率与置换算法、分配的物理块数、内存容量、进程数量、访问方式均有关

基本页式、虚存页式中，页面的大小往往和磁盘块/扇区大小统一，方便数据传输分配

计组、虚存、Cache

虚存是计算机形成实际地址并决定访存的过程，高速缓存后是真正访存的过程

两者属于不同时期与步骤，虚存交互为页、Cache与主存交互为块

假如产生缺页中断，缺页中断处理完后对主存的访问，Cache必然缺失，主存必不缺失

缺页中断属于异常，因而处理完成后重新对产生异常语句进行一次运行

因而第一次缺页中断后，第二次会重新进行地址转换，第一次访问必为快表必命中

在不存在快表的虚存机构中，也同样会再度访问慢表一次，相当于重新执行一次该语句

上述为核心考点，且运行步骤极为重点，需要牢记

Cache，在虚存体系下的运行：

TLB、Cache，均为，SRAM

虚存实际容量与最大容量

实际容量受硬件容量限制，如磁盘与内存大小；受虚存分配方式影响：页、段、段页

不同的内存分配方式或是虚存方式会影响能提供的存储空间大小，因为机制复杂度不同

虚存最大容量受可编址空间影响，一般存储方式同样受地址总线宽度影响

随记

页面越大缺页中断越少、页面越小缺页中断越多，覆盖面越大自然中断次数越少

驻留集一般而言越大缺页中断越少，但可能存在BELADY现象，反之则一定会导致增加

快表是慢表的一个副本，题目中只印一部分是因为没必要再重印一遍

虚存是一类高速缓存，若程序无良好局部性，就会陷入频繁中断，导致虚存形同虚设

若有良好局部性，则逻辑上提供的庞大地址空间可使得逻辑访问速度较快

关于访存次数，牢记快表命中只需一次访存，多级页表则至少多级，多层访存

关于I/O开销问题：纯页式中，小页面、大页面均占用一个盘块，访盘时间基本相同

因为I/O的开销主要在于寻道而不在于读盘

置换算法中开销排序，LRU>CLOCK>FIFO

请求分段、段式更加适合动态链接，请求分页适合但不是主要特征和优势

处理器与主存的访问、快表与主存的访问既可以是并行也可是串行，命中废主存即可

页面调度，即中级调度，是和处理器速度完全无关的，理解为中级调度更容易判定

虚存，指代内存与外存两者，因而进程本身页面在虚存不能保证不会缺页，还可在外存

磁盘交换区利用率的含义为：10G交换区，已用9.7G，表明交换区存了一堆页面

间接说明内存中能够存放的页面太少，导致全都放在暂存调出页面的磁盘交换区中

而频繁的调入调出就会使得大量处理器时间耗费在等待磁盘上，导致抖动

对磁盘交换区进行提速的效果非常有限，最为有效的操作是增加内存的容量，减少调出

快表容量不变的情况下，扩大页面大小，可以使得快表覆盖更大空间，提高命中率

页表项中地址的增加量导致页表项的减少相对于页表项表示容量的增量，可以忽略不计

虚存体系平均访存时间的含义为最终形成物理地址并访存得到数据的时间

页缓冲队列是把已淘汰的页存放在内存缓冲区中，当缓冲区满时一次性写回磁盘

实际上是将缺页中断处理过程的访盘变为访存，不会影响缺页率，只影响缺页处理速度

页缓冲队列的思想本质来源于磁盘延迟写，操作系统最后一节内容

延迟写的含义即为，该缓冲区被其他进程申请占用时，才将内部的数据一次性写回

如果其他进程不申请该缓冲区，那么数据将会一直存放于内存缓冲区之内

真题汇总

14：访问时间考察访问流程；考察进程页面分配方式，固定分配局部置换

2362：快表未命中、慢表命中、访存

1565：快表未命中、慢表未命中、缺页中断、快表命中、访存

25A5：快表命中、访存

此时固定分配页框暂未满，不需要替换，只需要装入即可

详细阐述下运行流程：

给定地址，判定是否该进程页号范围内，否则越界、是则访问该页号表项，不考虑快表

固定分配下，若当前分配未满且缺页，取一固定分配页框号填入当前页表项

若当前分配已满，从固定分配页框中选取一块替换，并将该页框号填至对应页表项内

本质为页框号是固定的，页表项的页号也处于一定范围内，将页框号填入不同页表项罢

17：虚存体系多级页表是索引式访问，依旧是随机存取的类型

类似于取一个页面的内容，只需要按照索引顶多访问两次，即可得到，不会访问多次

不是顺序访问，是索引式随机访问

18：键盘输入过程，已经连续考察多次，因而作为重点展开讲解

1.系统调用的触发

用户态下调用 scanf(): 当程序执行 scanf() 时，进程从用户态转入内核态，触发系统调用

系统调用接口: scanf() 调用会调用一个底层的系统调用（如 read()）以从标准输入设备（通常是键盘）读取数据

2.进程状态转换

陷入内核态: 触发系统调用时，CPU 会执行陷入（trap）指令，从用户态切换到内核态。此时，操作系统接管控制权

进程阻塞: 因为 scanf() 需要等待用户输入字符，此时进程会进入阻塞状态（I/O等待状态），并从运行队列中移除。这让 CPU 可以调度其他进程执行

3.等待输入

设备驱动程序工作: 操作系统调用相关设备的驱动程序，来等待键盘输入。当用户按下按键时，键盘控制器生成一个硬件中断信号

中断处理: 键盘控制器发送中断信号到 CPU，通知有输入数据需要处理。此时，CPU 暂停当前正在执行的任务，转而处理中断

4.处理输入

内核处理中断: 操作系统内核的中断处理程序会从键盘控制器中读取输入字符，将其存储在内核缓冲区中，并清除中断信号

进程唤醒: 当用户输入的数据满足 scanf() 所需的条件（如按下回车键），内核会将数据复制到用户进程的缓冲区，并将该进程从阻塞状态转为就绪状态

5.返回用户态
重新调度: 操作系统将进程重新放入就绪队列中，当进程再次被调度时，它会恢复运行

从内核态返回用户态: 进程返回到用户态，继续执行 scanf() 函数后面的代码

注解：进程调度属于内核态执行的事件，因而先重新调度，再从内核态返回用户态执行

6.系统调用返回
返回结果: scanf() 从内核接收输入的字符，并将其处理为适当的格式（例如将字符串转换为整数）

继续执行: 用户进程使用从 scanf() 返回的结果继续执行剩余的程序

点评：

键盘设备驱动器生成中断信号、由中断处理程序将键盘内容读入系统缓冲区

进程将先被唤醒插入就绪队列，再从系统调用中返回

整体处理过程均为内核态下，唯有初始阶段的系统调用、最终返回运行为用户态

上述内容多次作为考点，因而需要重点关注

20：页目录号的计算同样作为多次出现的考察重点，需要清晰其过程

首先需要明确页表项的页号，即该页表项对应页面的虚拟地址，虚拟地址中包含页号

确定页号以后，再确定页表项的大小，页表的基础物理地址

然后页表基地址+页表项大小·页号，即为页表项所对应的物理地址，页表项连续存放

在多级页表的情况下，前多级页表的页表项内容，均为下一级页表的基地址

若还可考更深，即为多级页表本身的页表项同样可以考察，这就需要多层回归计算

综合题汇总

1：更新快表、慢表是操作系统的任务，软硬件协同的含义为操作系统发指令硬件执行

3：引用串即为下面一段时间需要访问的页面序列

最少每次重复页面的访问都不会缺页，最差每一页均缺页

5：再次赘述磁盘交换区利用率的含义，为占用利用率，即10G占9.7G，即为97%利用率

说明当前大量页面内存放不下，只能放在外存，而外存交换区甚至都快放满

而结合处理器基本空闲，即可明确进程几乎没有运行，处于频繁的页面置换之中

侧面说明内存容量严重不足

7：不论多少级页表，快表提供的均是页号与最终实页框号的映射关系

也可以如此说，如果快表命中，访存只可能是一次，而其他情况下访存次数则不确定

在多级页表的情况下，甚至还会涉及磁盘的访问，因为页表被分散到整个虚存内

13：虚存空间并不一定全部用上，地址空间高位是可能有空闲的，切记从低位开始数位

从高位开始数就是默认地址空间全部用上，而实际上未必如此