操作系统学习记录3-内存管理

内存管理功能

内存的作用是缓和CPU和硬盘之间的速度矛盾

内存地址从0开始，每一个地址对应一个存储单元

计算机按字节编址，每个存储单元大小为一字节，8bit

计算机按字编址，每个存储大小为一个字，16bit

 

程序运行的顺序：编译源代码文件-编译-链接-装入

编译：由源代码文件生成目标模块（高级语言-》机器语言）

链接：将目标模块生成装入模块，链接后形成完整的逻辑地址

装入：将装入模块装入内存，装入后形成物理地址

 

三种链接方式：

静态链接：装入前链接成一个完整的输入模块

装入时动态链接：运行时边装入边链接

运行时动态链接：运行时需要目标模块才装入并链接

三种装入方式：

绝对装入：编译时产生绝对地址（物理地址）

可重定位装入：装入时将逻辑地址转换为物理地址

动态运行时装入：运行时将逻辑地址转换为物理地址，需设置重定位寄存器

 

内存分配与回收：提高效率

地址映射：逻辑地址与物理地址的转换

采用三种装入方式

内存扩充：虚拟存储技术

内存保护：内存中的进程互不干扰

方法一：设置一对上下限寄存器，存放进程的上下限地址，进程的指令要访问某个地址时，CPU检查是否越界。

方法二：采用重定位寄存器（基址寄存器），界地址寄存器（限长寄存器）进行越界检查。重定位寄存器中存放的是进程的起始物理地址。界地址寄存器中存放的是进程的最大逻辑地址。

内存共享：允许多个进程共享内存区

覆盖与交换

覆盖是设置一个固定区和若干覆盖区。固定区中的程序段在运行过程中不会调入调出。覆盖区中的程序段在运行过程中会根据需要调入调出。必须要由程序员声明覆盖结构，对用户不透明。

交换是指内存紧张时，换出某些进程以腾出内存空间，再换入某些进程。磁盘分为文件区和对换区，换出的进程再对换区。

覆盖与交换的区别：覆盖是在同一个程序或进程中的，交换是在不同进程或者作业中的。

 

内存分配

连续分配（单一连续分配、固定分区分配、动态分区分配）

单一连续分配：

单一连续分配只支持单道程序，将内存划分为系统区和用户区，用户程序放在用户区。无外部碎片，有内部碎片。

固定分区分配：

支持多道程序，内存用户空间分为若干固定大小的分区，每个分区只能装一道程序。无外部碎片，有内部碎片

动态分区分配：

支持多道程序，进程装入内存时，根据进程的大小动态地建立分区。有外部碎片，无内部碎片。可以使用紧凑的技术解决外部碎片。

回收内存分区时，可能遇到四种情况：回收区之后有相邻的空闲分区、回收区之前有相邻的空闲分区、回收前后都有相邻的空闲分区，回收区前后都没有相邻的空闲分区。（相邻的空闲分区要合并）

内部碎片，分配给某进程的内存区域中，有些部分没有用上

外部碎片，内存中的某些空闲分区因为太小而无法利用

 

动态分区分配算法：

首次适应算法：每次从低地址开始查找，找到第一个能满足大小的空闲分区。空闲分区按地址递增的次序排列

最佳适应算法：尽可能留下大片的空闲区，优先使用更小的空闲区。按容量递增次序链接，会产生大量外部碎片

最坏适应算法：最大适应算法，每次分配优先使用最大的空闲区。按容量递减次序链接。但不利于大进程，开销大。

邻近适应算法：空闲分区按地址递增次序排列，每次分配内存从上次查找结束的位置开始查找空闲分区链。开销小，但是高地址的大分区也被用完。

四种算法中，首次适应算法的效果更好。

单一连续分配

非连续分配（分页管理、分段管理、段页式管理）

分页管理

概念：页框、页帧、内存块、物理块、物理页、页、页面

页表记录了页面和实际存放的内存块之间的映射关系。

一个进程对应一张页表，进程的每一页对应一个页表项，每个页表项由页号和块号构成。

每个页表项的大小相同，页号是隐含的。

i号页表项存放地址 = 页表初始地址 + i*页表项大小

页号=逻辑地址/页面大小

页面偏移量 = 逻辑地址%页面大小

 

快表（TLB）也叫联想寄存器，是访问速度比内存快很多的高速缓存（不是内存），用来存放最近访问的页表项的副本，内存中的页表也叫慢表

页表和普通cache的区别，TLB中只有页表项的副本，普通cache可能会有其他各种数据的样本。

查询内存中的页表时，由于局部性原理，可能连续多次都是查到同一个页表项。

基本地址变换需要访存2次，具有快表的地址变换机构中，快表命中只需要访问一次内存，未命中则需要访问2次内存

 

分段管理

进程的地址空间按照自身的逻辑划分为若干个段，每个段从0开始编址。内存以段为单位进行分配，每个段在内存中占据连续的空间，各段之间可以不相邻。用户编程更方便，程序的可读性更高。

逻辑地址结构由段号（段名）和段内地址（段内偏移量）组成。

段号的位数决定了每个进程可以分为多少个段

段内地址位数决定了每个段的最大长度是多少。

为了从物理内存中找到各个逻辑段的存放位置，需要为每一个进程建立一张段映射表，简称段表。

每个段表项记录了该段在内存中的起始地址（基址）和段的长度。

各个段表项的长度是相同的，段号是隐含的，不占用空间。

 

页是信息的物理单位，对用户不可见

段是信息的逻辑单位，分段对用户可见

分页的用户进程地址空间是一维的，一个记忆符就是一个地址。

分段的用户进程地址空间是二维的，一个地址标记时既要给出段名，又要给出段内地址。

分段比分页更容易实现信息的共享与保护。

不能被修改的代码被称为纯代码或可重入代码（不是临界资源），不能共享。

访问一次逻辑地址时

分页（单级页表）：第一次访存：查内存中的页表，第二次访存：访问目标内存单元。一共2次访存。

分段：第一次访存：查内存中的段表，第二次访存：访问目标内存单元。一共2次访存。

也可以引入快表机制，可以减少一次访存。

根据段表记录的段长，检查段内地址是否越界。

段页式管理

分页管理与分段管理的优缺点

分页管理

优点：空间利用率高，不会产生外部碎片，只有少量的页内碎片。

缺点：不方便按照逻辑模块实现信息共享与保护

分段管理

优点：方便按照逻辑模块实现信息共享与保护

缺点：段长过大，分配很大的连续空间会很不方便，会产生外部碎片（可以使用紧凑技术，但会消耗大量时间）

 

段页式系统的逻辑结构地址由段号、页号、页内地址（页内偏移量）组成。

段号的位数决定了每个进程最多分为几个段

页号位数决定了每个段最大有多少页

页内偏移量决定了页面大小，内存块大小是多少

段页式管理的地址结构是二维的

 

每个段对应一个段表项。每个段表项由段号（隐含）、页表长度、页表存放块号（页表起始地址）组成，每个段表现长度相等。

每个页面对应一个页表项，每个页表项由页号、页面存放的内存块号组成。每个页表项长度相等，页号是隐含的。

访问一个逻辑地址需要访存三次

第一次：查段表。第二次：查页表。第三次：访问目标单元

引入快表机制后。以段号和页号作为关键字查快表，只需一次访存。

 

虚拟内存管理

传统存储管理方式的特征和缺点：

一次性：作业必须全部装入内存才能运行。导致大作业无法运行，多道程序并发度下降。

驻留性：作业被装入内存中，就会一直驻留在内存中，直到作业结束。

 

局部性原理：时间局部性、空间局部性

时间局部性：如果执行了程序中的某条指令，那么不久后这条指令有可能再次执行。如果某个数据被访问过，那么不久之后该数据可能被再次访问。

空间局部性：一旦程序访问了某个存储单元，不久之后，其附近的存储单元很有可能再次被访问（因为很多数据是连续存放的）

 

根据局部性原理，很快会用到的部分装入内存，暂时用不到的部分留在外存。信息不在内存时，操作系统负责将外存调入内存中。内存空间不够时，操作系统负责将暂时用不到的信息换出外存。

虚拟内存的最大容量是计算机的地址结构（寻址范围）决定的。

虚拟内存的实际容量是min（内存与外存容量之和，寻址范围）

如计算机地址结构为32位，按字节编址，内存大小为512MB，外存大小为2GB。

虚拟内存的最大容量为B=4GB

虚拟内存的实际容量为2GB+512MB

 

虚拟内存的三个特性：

多次性：无需一次性装入内存，可以多次调入内存。

对换性：作业运行时无需一直常驻内存，允许在作业允许的过程中将作业换入换出。

虚拟性：从逻辑上扩充了内存的容量，使得用户看到的内存容量，远大于实际的容量。

 

虚拟内存的实现需要建立在离散分配的基础上

在程序执行过程中，访问的信息不在内存时，由操作系统负责将所需的信息从外存调入内存。内存空间不够时，将内存中暂时用不到的信息换出到外存。

 

请求分页和基本分页的区别：

在程序执行过程中，访问的信息不在内存时，由操作系统负责将所需的信息从外存调入内存。内存空间不够时，将内存中暂时用不到的信息换出到外存。操作系统提供请求调页和页面置换的功能。

在请求分页中，页表项增加了4个字段，状态位、访问字段、修改位、外存地址。

状态位记录是否已经调入内存。

访问字段记录最近访问过几次，或者记录上次访问的时间，供置换算法选择换出时页面参考。

修改位记录内存后是否被修改过。

外存地址记录页面在外存中的存放位置。

 

在请求分页中，页面不存在的时候，产生一个缺页中断，然后操作系统的缺页中断处理系统处理中断。

缺页的进程阻塞，完成后再将其唤醒。

有空闲块时，为进程分配一个空闲块

没有空闲块的时候，由页面置换算法选择一个页面淘汰。该页面在内存被修改，则需要写回外存，未修改过不用写。

缺页中断是因为当前指令想要访问的目标页面未调入内存而产生的，属于内中断。

一条指令在执行期间，可能产生多次缺页中断。

内中断：陷阱、陷入、故障（如缺页中断）、终止

外中断：I/O，人工干预

页面置换算法（需要最求更少的缺页率）：

最佳置换算法（OPT）：每次淘汰的页面是以后永不使用的，或是淘汰未来最迟被使用的页面。实际上无法实现。

先进先出置换算法（FIFO）：淘汰最先进入内存的页面。

只有FIFO算法有Belady异常，也就是说为进程分配的物理块增大的时候，缺页次数不减反增。实现简单，但是算法性能差。

最近最久未使用置换算法（LRU）：淘汰最近最久未使用的页面。

用访问字段记录页面自上次访问以来的时间t，每次淘汰页面时选择一个t值最大的。该算法性能好，但是实现困难，开销大。

做题时，逆向检查在内存中的几个页面号，最后一个出现的页号就是要淘汰的页面。

最少使用置换算法：淘汰最近时期使用最少的页面

Clock置换算法：为每页设置访问位和修改位。

为每个页面设置一个访问位，将内存中的页面通过链接指针链接成一个循环队列。被访问时，访问位置为1，淘汰一个页时，检查访问位，是0则将该页换出。是1则置为0，暂不换出。若第一轮扫描中，所有页面都是1，则将其置为0后，再进行第二轮扫描。简单的clock算法最多会经过2轮扫描。

 

改进型时钟置换算法。

简单的时钟置换算法只考虑一个页面最近是否被访问过。实际上只有被淘汰的页面被修改过时，才需要写回外存。在其他条件都相同的时候，应该优先淘汰没有修改过的页面。修改位=0，表示页面没有修改过；修改位=1，表示页面被修改过。

用（访问位，修改位）表示页面状态

第一轮（最近未访问且未修改）：开始扫描找到第一个（0，0）替换，不修改标志位

第二轮（最近未访问但修改过）：第一轮失败，重新扫描，找到第一个（0，1），并把所有扫描过的帧访问位置为0.

第三轮（最近已访问未修改）：第二轮失败，重新扫描，找到第一个（0，0）替换，不修改标志位

第四轮（最近已访问且已修改）：第三轮失败，重新扫描，找到第一个（0，1）替换。

改进型的clock算法淘汰一个页面会最多进行4轮扫描

 

内存映射文件

由一个文件到一块内存的映射，用于解决本地多个进程之间数据共享问题。是操作系统向上层程序员提供的功能（系统调用）方便程序员访问文件数据。方便多个进程共享同一个文件。

以访问内存的方式访问文件数据

文件数据的读入、写出由操作系统自动完成。进程关闭文件时，操作系统自动将文件被修改的数据写回磁盘。

在物理内存中，一个文件对应一份数据，当一个进程修改文件数据时，另一个进程可以马上看到

 

页面分配策略

驻留集

指请求分页存储管理给进程分配物理块的集合。

驻留集太小会导致缺页频繁，需要花费大量的时间处理缺页。

驻留集太大会导致多道程序并发度下降，资源利用率降低

页面分配、置换策略

 

固定分配：操作系统为每一个进程分配一组固定数目的物理块，在进程运行时大小不变

可变分配：先为每个进程分配一定数目的物理块，进程运行期间，可根据情况做适当的增加或者减少。驻留集大小可变。

局部置换：发生缺页时只能选进程自己的物理块进行置换。

全局置换：可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程。

固定分区局部置换：系统为每个进程分配一定数量的物理块，在整个运行期间都不改变。在运行中缺页，只能从该进程在内存中的页面选出一页换出。

可变分区全局置换：刚开始先分配一定数量空闲块，操作系统会保持一个空闲队列，发生缺页时，从空闲物理块取出一块分配给该进程。若无空闲物理块，选择一个未锁定的页面换出外存，并将该物理块分配给缺页的进程。只要进程发生缺页，就能获得新的物理块。当空闲物理块用完的时候，才选择未选择的页面。被选择的页面可能时任意一个进程的页，被选中的进程所拥有的物理块会减少，缺页率会增加。也就是说，只要缺页就分配新的物理块。

可变分区局部置换：刚开始先分配一定数量空闲块，发生缺页时，只允许从物理块分配给该进程。如果调入页面的时机频繁的换页，系统会多分配几个物理块。缺页率特别低，可以适当减少分配给该进程的物理块。也就是说，根据发生缺页的频率来动态地增加或者减少进程的物理块。

从何时调页

预调页策略：根据空间局部性原理，一次调入若干个相邻页面可能比一次调入一个页面更高效。用于进程的首次调入，由程序员指出调入哪些地方，主要用于进程的首次调入。

请求调页策略：在运行期间发现缺页时才将所缺页面调入内存。

从何处调页

1. 系统有足够的对换区空间。调入调出都是在内存与对换区进行，可以保证页面的调入调出速度很快。在进程运行时，需要将进程相关的数据从文件区复制到对换区。

2. 系统缺乏足够的对换区空间。凡是不被修改的数据直接从文件区调入，由于这些页面不会被修改，不必写回磁盘。对于可能被修改的部分，换出时需写回磁盘对换区，下次需要时再从对换区调入。

3. Unix方式。运行之前进程有关的数据全部放在文件区，未使用的页面，都可以从文件区调入。若使用过的页面需要换出，则写回对换区，下次需要时再从对换区调入。

抖动（颠簸）

刚刚换出的页面又马上换入内存，刚刚换入的页面马上又要换出外存，这种频繁的页面调度行为称为抖动，或者颠簸。主要原因是进程频繁访问的页面数目高于可用的物理块数。（分配给进程的物理块不够）物理块太少，会产生抖动现象。物理块太多，会降低系统整体的并发度，降低某些资源的利用率。

工作集

驻留集：请求分页存储管理中给进程分配的物理块的集合。

工作集：指在某段时间集合里，进程实际访问页面的集合。

操作系统会根据“窗口尺寸”来计算出工作集

选中一个正在运行的进程，往前数多少个窗口尺寸的进程便是工作集。

工作集大小可能小于窗口尺寸。驻留集大小不能小于工作集大小，否则进程运行过程中会频繁缺页。

 

虚拟存储器性能的影响因素及改进方法