操作系统-第四章存储器管理

4.1 存储器概述

内存和外存，计算机的存储结构

　　内存是CPU直接存取指令和数据的存储器。任何一个程序（包括应用程序和OS本身）必须被装入内存，才可能被执行。尽管RAM芯片集成度越来越高，价格不断降低，由于其需求量大，整体价格仍较昂贵，而且受CPU寻址能力的限制，内存容量仍有限。因此，对主存的管理和有效利用仍然是当今操作系统十分重要的内容。内存区域被分为两大区域：系统空间，用户进程空间。本章主要讲述用户区域的管理方法和基本技术。
　　外存主要用于存放数据和文件，在设备管理部分进行介绍。
　　目前，计算机系统均采用层次结构的存储子系统，以便在容量、速度和价格等因素中取得平衡点，获得较好的性能价格比。

存储管理任务

内存分配和回收
存储器管理模块需要记录内存的使用情况，为每道申请内存的进程分配内存空间，使它们“各得其所”。
静态分配：在目标模块装入内存时一次分配进程所需的内存空间，它不允许进程在运行过程中再申请内存空间。
动态分配：在目标模块装入内存时分配进程所需的基本内存空间，并允许进程在运行过程中申请附加的内存空间。
进程执行结束后，操作系统回收系统或用户释放的内存空间，提高内存利用率。

静态分配就是一次性全部装入，动态分配需要虚拟存储技术，可以多次装入。
地址变换
静态地址重定位和动态地址重定位。
静态地址重定位就是在程序装入内存的时候，一次性计算好所有逻辑地址对应的物理地址，因此他不能移动。
动态地址重定位就是在程序运行的时候，遇到了一个逻辑地址，就将它与寄存器中值（起始物理地址）相加计算出物理地址。
两者主要区别就在于时间的不同，动态地址充定位还需要硬件的支持。
内存保护
内存扩充

4.2 程序的装入和链接

三种装入方式

绝对装入

逻辑地址=物理地址，不需要地址重定位。
这种方式不适合多道程序。

可重定位装入

必须得进行地址映射。
对应静态重定位，需要连续的地址空间。

动态运行时装入

需要寄存器。

三种链接方式

静态链接

在装入前进行链接。
缺点：如果只修改了一个模块，整个程序都要重新链接；有些模块重复链接，不能实现共享；造成内存浪费；处理器呀资源也浪费，链接的时候需要，装入的时候有需要；有些模块运行的时候不要要也链接进来，浪费空间。
优点：简单，易于实现。

装入时动态链接

优点：便于模块的修改和更新，可以实现共享。
缺点：装入的结构依然是静态的。

运行时动态装入

优点：减少内存和处理机的浪费。
缺点：管理难度大。

4.3 连续分配方式

连续分配方式，是指为一个用户分配一个连续的存储空间。
连续分配方式可进一步分为：

单一连续分配
固定分区分配
动态分区分配
动态重定位分区分配

单一连续分配

只能用在单用户、单任务的操作系统
将内存分为系统区和用户区，系统区仅提供给OS使用；用户区提供给用户作业使用，一次只允许一个作业进入内存，内存利用率极低。
可以采用三种程序装入方式之一
存储保护机制：“界地址寄存器”
不支持多道程序运行环境，不能有效地利用系统资源

固定分区分配

基本思想：将内存区域划分成若干个大小固定的区域，每个区域称为一个分区，每个分区存放一道进程对应的程序和数据，使进程在内存中占用一个连续的区域，而且进程只能在所在分区内运行。
划分分区的方法
- 分区大小相等。
- 分区大小不等。
需要数据结构——分区说明表，包括区号、分区长度、起始地址、状态。
分配算法：
- 分区说明表不同的排序方法
- 可以按地址从高到低或者从低到高找到合适的分区，
- 按分区的长度排序，按分区长度从大到小寻找，可以节省检索时间如果比这个进城需要长度更大的分区都没有了，那说明分配不了了；
- 也可以按分区长度从小到大寻找，可以更好利用；
地址变换你可以静态，也可以动态。
浪费存储空间，会有很多内碎片。
分区总数限制了并发的度。

动态分区分配

每次进程需要多少就分配多少
也需要一定的分配算法，检索空闲分区表或空闲分区链
- 首次适应算法（first fit）
  基本思想：总是从内存的某一端（一般从低地址端）开始查找，选择一个超过进程申请大小的空闲分区。
  为此，可以将空闲分区表中登记的空闲分区按照其起始地址由小到大的次序排列，系统查找空闲分区时，从表头开始查找，取第一个满足要求的分区分配给进程。
  若找到的空闲分区恰好与进程申请的存储空间大小相等，或分配给该进程后，仅剩下一个非常小的空间（小于系统设置的阀值），则将该分区全部分给申请进程。
  否则，系统将该分区划分成两个分区，一个分区的长度等于进程申请的空间大小，并将其分配给申请进程。然后，将另一个子分区链接到空闲分区链表中。
  优点：尽量使用低地址空间，因而在高地址的空间可能会保留较大的空闲分区。所以，大进程申请的存储空间大都能在高地址端得到满足。
  缺点：由于每次只简单的使用找到的第一个分区，结果可能导致较大的空闲分区不断地分割为较小的空闲分区。
- 循环首次适应算法（next fit）
  循环首次适应算法，能记住上次分配分区的位置，下一次实施分配时，从上一次分配位置之后开始查找，选择一个大小足够的空闲分区。
  该算法常常会导致内存中缺乏大分区，因为它会均衡的利用空闲分区，包括分割较大的空闲分区，从而使得大进程无法装入内存。
- 最佳适应算法（best fit）
  总是选择满足申请要求且长度最小的空闲空间。
  为了提高查找效率，可以将所有空闲分区按照长度由小到大的次序依次排列在空闲分区表中。
  为进程分配存储空间时，从表头开始查找，第一个满足进程申请存储空间大小的分区就是最合适的分区。
  优点：尽量不分割大的空闲分区
  缺点：可能形成大量较小的、难以再分配的分区。
  最佳适应算法并非是最好的算法。
- 最坏适应算法
  最佳是从小到大，最坏就是从大到小。
- 总结一下
  首次适应就是每次从地址从小到大找；循环首次适应从上一次的地址之后找；最佳适应就是找到大小最合适的。
有外碎片
分区回收：如果要回收的分区和空闲区相邻，就合并。
地址变换可以采用动态地址重定位。
分区保护。

动态重定位分区分配

什么时候进行紧凑？
和动态分配分区的区别就是加入紧凑技术。

对换

四种连续分配方式小总结

整体思路就是不断提高内存的资源利用率。单一连续分配只能让一个进城使用，于是有了固定分区分配。固定分区分配会有比较多的内碎片，有了动态分区分配，让每个进程按需分配。再加上动态地址重定位技术和紧凑技术，有动态重定位分区分配进一步提高内存利用率。

4.4 基本分页存储管理方式

将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页加以编号，从0开始，如第0页、第1页等。
把内存空间分成与页面相同大小的若干个存储块，称为(物理)块或页框(frame)， 也同样为它们加以编号，如0＃块、1＃块等等。
这样在为进程分配内存时，可以将进程中的若干个页分别装入到多个可以不相邻的物理块中。

碎片问题。只有最后一页可能会存在碎片。
页面大小的选择。太小：映射多，页表大，碎片少；太大：碎片大，页表短。512字节到8K。
原来一维的逻辑地址，可以分为（页号，页内地址）。
页表：记录页号和块号之间的映射关系。经常访问。常驻内存。一个进程一个页表，进程多少页，页表就有多长。
地址变换机构
- 一个进程的页表的地址会放在寄存器当中。单处理机试运行一个进城，所以寄存器里就放当前进程的页表的地址。其他进程的防灾PCB中。
- 基本的地址变换机构
  - 页表寄存器当中存页表的起始地址和页表长度。
  - 有一个逻辑地址，先拿它对页面大小取整，得到页号。比如：逻辑地址2500，页面大小为1K，那他的页号就是2500/1k取整等于2.一般化为二进制，2500化为二进制后（根据系统有效地址长度来，这里假如是16位），1K是10位，那搞6位就是页号，后面的 10位就是页内地址。
  - 如果算出来的页号在页表长度范围内，就好，如果超出，就中断。
  - 根据页号和页表起始地址、页表每一项的长度，在页表中找到块号。
  - 因为块大小和页面大小一样大，所以可以算出块的物理起始地址，在加上业内地址，就得到了物理地址。在二进制表示中，就是将块号和业内地址进行拼接。
- 基本的地址变换机构，在地址变换的过程中访问了两次内存，一次是访问页表，一次是访问物理地址获取数据。
快表。因为程序在运行的时候，在一段时间内，只会访问部分的数据，所以可以将一部分数据放在缓存当中，增加访问地址的速度。如果快表里没有，再去内存页表里找。
两级和多级页表。如果页表特别长，超过了一个页面的大小，那就采用两级或多级页表。
页面共享。可重入代码(Reentrant Code)又称为“纯代码”(Pure Code) ，是一种允许多个进程同时访问的代码。为使各个进程所执行的代码完全相同，绝对不允许可重入代码在执行中有任何改变。因此，可重入代码是一种不允许任何进程对它进行修改的共享代码。为了保证可重入代码不被修改，每个进程中都配以局部数据区，把进程执行中改变的代码拷贝到该数据区。为了实现对共享页面的合理访问，系统可在进程的页表中增加一些控制位，用于说明各个页面的访问控制信息，如可读、可写或可执行等。
优缺点：
- 优点：
  一个程序不必连续存放，消除了外碎片；
  程序的逻辑页放置策略简单。
- 缺点：
  采用动态地址映射进行地址变换，增加了计算机成本，降低了程序执行速度；
  页表的建立和管理也需要一定的系统开销；
  每个进程平均拥有半页的内碎片；
  如果共享内容跨页存放，则不易于实现共享；
  程序需要全部装入内存，增加了内存的存储压力。

4.5 基本分段存储管理方式

引入：方便编程；信息共享；信息保护；动态增长；动态链接。
页的大小是系统来划分的，段是由用户来划分的。
数据结构——段表。段号，段长，基址。需要判断两次越界，段号有没有越界，段内地址有没有越界。也是访问两次内存。
分段比分页更好信息共享。
段页式存储管理方式。程序依然按段分，存储的时候按页分。每一个段对应一个页表。会三次访问内存：访问段表，访问页表，访问物理地址。

4.6 虚拟存储器的基本概念

常规存储器的特征有一次性和驻留性，带来的问题有：

有的作业很大，可能不能一次性装入内存当中；
要运行的作业很多，但因为容量有限，一次只能装入比较少的进程。

解决方法：从屋里上加大内存容量；从逻辑上增加容量。

虚拟存储技术广泛使用是在20世纪70年代初以后
其基本思想：是用软硬件技术把内存与外存这两级存储器当成一级存储器来用，从而给用户提供了一个比实际内存大得多的虚拟存储器。虚拟存储管理只要求把进程在最近一段时间内的执行部分装入内存。
好处：用户编程时几乎不用考虑内存限制，给用户编程带来极大的方便；有利于在主存中同时存放多道进程，为提高系统并发程度奠定了基础。

虚拟存储技术的理论依据——局部性原理
时间局部性：一条指令在执行后一段时间后可能会再次执行；
空间局部性：某个存储单元被访问了，一段时间后，它附近的存储单元也可能会被访问到。

所以什么事虚拟存储器？
所谓虚拟存储器，是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而每位的成本却又接近于外存。可见，虚拟存储技术是一种性能非常优越的存储器管理技术，故被广泛地应用于大、中、小型机器和微型机中。

虚拟存储器的实现方法
硬件支持：必须要有辅存；页表（段）机制；缺页中断机制；地址变换机构。
软件支持：必须是离散分配的管理方式上。
请求分页（分段）系统，就是分页（分段）分配方式的基础上，加入请求调页（段）和页面（段）置换功能。

虚拟存储器

多次性
对换性
虚拟性
三者的关系：虚拟性是以多次性和对换性为基础的；而多次性和对换性又必须建立在离散分配的基础上。

4.7 请求分页存储管理方式

当一个进程要求运行时，不是把整个进程的程序代码和数据全部装入内存，只需将当前要运行的那部分程序代码和数据所对应的页装入内存，便可启动运行。以后在进程运行的过程中，当需要访问某些页时，由系统自动地将需要的页从外存中调入内存。如果内存没有足够的空闲物理块，将暂不运行的页调出内存，以便装入新的页。
内存中的页称为“实页”，把在外存中页称为“虚页”。

硬件支持——页表

页号
物理块号
状态位P
用于指示该页是否已调入内存，供程序访问时参考
访问字段A
用于记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问过，供选择换出页面时参考。
修改位M
表示该页在调入内存后是否被修改过，供置换页面时参考。
外存地址
用于指出该页在外存上的地址，通常是物理块号，供调入该页时参考。

硬件支持——缺页中断机构

步骤的前面和基本分页一样，当要找的页面不在内存当中，就要从外存申请调入；如果内存足够，就直接调入；如果内存不够，就还要考虑置换。置换的时候，如果换出去的页被修改了，那要保证外存中是最新的。

虚拟存储系统的软件支持

驻留集管理（Resident Set Management）
进程的驻留集指，虚拟存储系统中，每个进程驻留在内存中的页面的集合，或进程分到的物理页框的集合。
驻留集管理主要解决的问题是，系统应当为每个活跃进程分配多少个页框。
分配给每个活跃进程的页框数越少，放置在内存的进程就会越多，减少了因为交换（这里应该是进程从挂起到就绪的交换）儿造成的的处理机开销。但是会增加缺页中断的概率。分配给每个活跃进程的页框数越少，因为局部性原理，不会显著减少缺页中断的概率，而且有些进城可能不需要那么大的物理快，会造成浪费。
分配策略：
```
  +  固定分配策略（Fixed-Allocation Policy）
            平均分、按比例分、优先级分。
        + 可变分配策略（Variable-Allocation Policy）
```
放置策略（Placement Policy）
主要是分段
解决的问题：系统应当在内存的什么位置为活跃进程分配页框？
一般地，对于一个分页系统或段页式系统，将进程的一个页面装入哪一个页框无关紧要。
对于分段系统，需要考虑将一个程序段装入哪一个合适的分区中，可采用的分配算法包括首次适应法、循环首次适应法、最佳适应法等。
获取策略（Fetch Policy）
解决的问题：系统应当在何时把一个页面装入内存（调入页面的时机）？
- 请求调页（Demand Paging）
  用到的时候请求调用。
- 预调页（Prepaging）
  先进行预判。
置换策略（Replacement Policy）
置换的范围：全局置换，局部置换。全局就是所有的，局部就是只能和自己的进程换。如果驻留集的分配策略是固定的，那就只能用局部置换；如果是可变的，那就都可以。
置换算法。好坏的评价：避免抖动，抖动就是刚换出去又换进来。
清除策略（Cleaning Policy）
负载控制（Load Control）

4.8 页面置换算法

最佳置换算法

先进先出(FIFO)

最近最久未使用(LRU)

Clock置换算法

系统会分配给进程一定数量的物理快，会有个指针循环遍历访问这些物理快。
页面会有个访问位，在第一次装入物理快和每次被访问过这个页面后，访问位都会置为1；
指针循环遍历的时候遇到访问位是1的就将它改为0.并指向下一个（指针始终都是指向下一位）；第一次遇到访问位是0的，就选择换出。
如果没有发生缺页中断，就是要访问的这个页面在内存中，就指针不动，访问了的那个页面的访问位置为1.

盛日辉的博客