内存

内存适用于存放数据的硬件程序执行前需要先放到内存中才能被CPU处理。

如果计算机按字节编制，则每个存储单元大小为一字节，即8个二进制位。

如果字长为16位的计算机按字编址，则每个存储单元大小为一个字，每个字的大小为16个二进制位。

绝对装入

在编译时如果知道程序将放到内存中的哪个位置，编译程序将产生绝对地址的目标代码。装入程序按照装入模块中的地址将程序和数据装入内存。

绝对装入只适用于单道程序环境。

静态重定位

又称可重定位装入。编译链接后的装入模块的地址都是从0开始的指令中使用的地址数据存放的地址，都是相对于起始地址而言的逻辑地址。

可根据内存的当前情况，将装入模块装入到内存的适当位置。

装入时对地址进行重定位，将逻辑地址变化为物理地址。

静态重定位的特点是在一个作业装入内存时，必须分配其要求的全部内存空间，如果没有足够的内存，就不能装入该作业。

作业一旦进入内存后，在运行期间就不能再移动，也不能再申请内存空间。

动态重定位

装入程序吧，装入模块装入内存后，并不会立即把逻辑地址转换为物理地址，而是把地址转换推迟到程序真正要运行时才进行。

装入内存后，所有的地址依然是逻辑地址，这种方式需要一个重定位寄存器的支持。

并且可将程序分配到不连续的存储区中，在程序运行前只需装入它的部分代码即可投入运行，然后在程序运行期间根据需要动态申请分配内存，便于程序段的共享。

链接的三种方式

• 静态链接
  • 在程序运行之前，先将各目标模块及他们所需的库函数连接成一个完整的可执行文件，之后便不再拆开。
• 装入时动态链接
  • 将各目标模块装入内存是边装入边链接的链接方式。
• 运行时动态链接
  • 在程序执行中需要该目标模块时才对它进行链接，其优点是便于修改和更新，便于实现对目标模块的共享。

内存管理

覆盖技术

将程序分为多个段，常用的段常驻内存，不常用的段在需要时调用内存。

内存中分为一个固定区和若干个覆盖区。

需要常驻内存的段放入固定区中，调入后就不再调出。

必须由程序员声明覆盖结构，操作系统完成自动覆盖。

对用户不透明，增加了用户编程负担。

交换技术

内存空间紧张时，系统将内存中的某些进程暂时换出外层，把外存中某些已具备运行条件的进程换入内存。

具有对换功能的操作系统中，通常把磁盘空间分为文件区和对换区两部分。

文件区主要用于存放文件，主要追求存储空间的利用率，因此对文件区空间的管理采用离散分配方式。

对换区空间只占磁盘空间的小部分，被换出的进程数据就存放在对换区。

由于兑换的速度直接影响到系统的整体速度，因此兑换区的空间管理主要追求换入换出速度，因此通常对换区采用连续分配方式。

换区的IO速度比文件区更快。

交换通常在许多进程运行且内存吃紧时运行，而系统负荷降低就暂停。

可优先换出阻塞进程，可换出优先级低的进程，为了防止优先级低的进程在被调入内存后又很快被调出，有的系统还会考虑进程内存的驻留时间。

PCB会常驻内存，不会被换出外存。

连续分配管理方式

单一连续分配

在单一连续分配方式中，内存被分为系统区和用户区。

系统区通常位于内存的低地址，部分用于存放操作系统相关数据。

用户需用于存放用户进程相关数据。

内存中只能有一道用户程序，用户程序独占整个用户区空间。

优点:实现简单，无外部碎片，可以采用覆盖技术扩充内存，不一定需要采取内存保护。

缺点:只能用于单用户单任务的操作系统中。有内部碎片，存储器利用率极低。

固定分区分配

将整个用户空间划分为若干个固定大小的分区，在每个分区中只装入一道作业。

分区大小相等:缺乏灵活性，但是很适合用于用一台计算机控制多个相同对象的场合。

分区大小不等:增加了灵活性

分区说明表

当某用户程序要装入内存时，由操作系统内核程序根据用户程序大小检索该表，从中找到一个满足大小的未分配的分区，将之分配给该程序，然后修改状态为已分配。

优点:实现简单，无外部碎片

缺点:当用户程序太大时，可能所有的分区都不能满足需求，此时不得不采用覆盖技术来解决，但这又会降低性能。

会产生内部碎片，内存利用率低。

动态分区分配

这种分配方式不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态的建立分区，并使分区的大小正好合适进程的需要。

因此系统分区的大小和数目是可变的。

空闲分区表

空闲分区链:每个分区的起始部分和末尾部分分别设置前项指针和后项指针，其实部分处还可记录分区大小等信息。

动态分区分配没有内部碎片，但是有外部碎片。

可通过紧凑技术解决

动态分区分配算法

首次适应算法

每次都从低地址开始查找，找到第1个能满足大小的空闲分区。

空闲分区以地址递增的次序排列，每次分配内存时顺序查找空闲分区表，找到大小能满足要求的第一个空闲分区。

最佳适应算法

空闲分区按容量递增次序链接，每次分配内存时顺序查找空闲分区链，找到大小能满足要求的第一个空闲分区。

缺点:每次都选最小的分区进行分配，会留下越来越多的很小的难以利用的内存块。

因此这种方法会产生很多的外部碎片。

最坏适应算法

空闲分区按容量递减次序链接。

缺点:每次都选最大的分区进行分配，虽然可以让分配后留下的空闲区更大更可用，但是这种方式会导致较大的连续空闲区被迅速用完。

邻近适应算法

空闲分区以地址递增的顺序排列，每次分配内存时，从上次查找结束的位置，开始查找空闲分区链。

首次适应算法，每次都要从头查找，每次都需要检索低地址的小分区。

当地地址部分有更小的分区，可以满足需求时，会更有可能用到低地址部分的小分区，也会更有可能把高地址部分的大分区保留下来。

临近适应算法的规则可能会导致无论低地址高地址部分的空闲分区都有相同的概率被使用，也就导致了高地址分，部分的大分区更可能被使用划分为小分区，最后导致无大分区可用。

基本分页存储管理

将内存空间分为一个个大小相等的分区，每个分区就是一个页框或称页帧、内存块、物理块。每个页框有一个编号及页框号。

将用户程序的地址空间也分为与页框大小相等的一个个区域，成为页或页面，每个页面也有一个编号，即页号。

操作系统以页框为单位，为各个进程分配内存空间。进程的每个页面分别放入一个页框中。进程的页面与内存的页框有一一对应的关系。

1. 算出逻辑地址对应的页号。
2. 要知道该页号对应页面在内存中的起始地址。
3. 算出逻辑地址在页面内的偏移量。

页号 = 逻辑地址÷页面长度

页内偏移量 = 逻辑地址%页面长度

如果每个页面大小为2的k次方B，则末尾开位即为页内偏移量，其余部分就是页号。

如果有k位表示业内偏移量，则说明该系统中一个页面的大小是2的k次方的内存单元。

如果有M位表示夜号，则说明在该系统中一个进程最多允许有2的M次方和页面。

页表

为了能知道进程的每个页面在内存中存放的位置，操作系统要为每个进程建立一张页表。

• 一个进程对应一张页表
• 进程的每一页对应一个页表项
• 每个页表项由页号和块号组成
• 页表记录进程页面和实际存放的内存块之间的对应关系

基本分段存储管理

分段

按照程序自身的逻辑关系划分为若干个段，每个段都有一个段名，每段从0开始编址。

以段为单位进行分配，每个段在内存中占据连续空间，但各段之间可以不相邻。

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

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

段表

各个段表项的长度是相同的。

段页式管理方式

	优点	缺点
分页管理	内存空间利用率高，不会产生外部碎片，只会有少量的页内碎片。	不方便按照逻辑模块实现信息的共享和保护。
分段管理	很方便按照逻辑模块实现信息的共享和保护。	如果断场过大为其分配很大的连续空间会很不方便，段式管理会产生外部碎片。

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

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

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

页面置换算法

OPT最佳置换算法

每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面。

最佳置换算法是无法实现的。

FIFO先进先出

Belady异常:单位进程分配的物理块增大时缺页次数不减反增。

LRU最近最久未使用

赋予每个页面相应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间。

该算法的实现需要专门的硬件支持，虽然算法性能好，但是实现困难，开销大。

CLOCK时钟置换算法

为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。

当某页被访问时，其访问位置为1。当需要淘汰一个页面时，只需检查页的访问位，如果是0就选择该页换出。

如果是1则将它置于0，暂不换出继续检查下一个页面，做第一轮扫描中所有页面都是一则将这些页面的访问位依次置为0后再进行第2轮扫描。

改进型时钟置换

除了考虑一个页面最近有没有被访问过外，操作系统还应考虑页面有没有被修改过。

第一轮:从当前位置开始扫描到第一个0，0的帧用于替换，本轮扫描不修改任何标志位。

第二轮:若第一轮扫描失败，则重新扫描查找第一个0，1的帧用于替换，本轮将所有扫描过的帧访问位设为0。

第三轮:若第二轮扫描失败，则重新扫描查找第一个0，0的帧，用于替换本轮扫描，不修改任何标志位。

第四轮:若第三轮扫描失败，则重新扫描查找第一个0，1的针用于替换。

虚拟内存

传统存储管理方式

很多暂时用不到的数据也会长期占用内存，导致内存利用率不高。

一次性:作业必须一次性全部装入内存后才能开始运行，这会造成两个问题:

①作业很大时不能全部装入内存，导致大作业无法运行。

②当大量作业要求运行时，由于内存无法容纳所有作业，因此只有少量作业能运行，导致多道程序并发度下降。

驻留性:一旦作业被装入内存，就会一直驻留在内存中，直至作业运行结束。事实上在一个时间段内，只需要访问作业的一小部分数据即可正常运行，这就导致了内存中会不留大量的暂时用不到的数据，浪费了宝贵的内存资源。

局部性原理

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

空间局部性:一旦程序访问了某个存储单元，在不久之后其附近的存储单元也很可能被访问。

虚拟内存的定义和特征

基于局部性原理，在程序装入时，可以将程序中很快会用到的部分装入内存，暂时用不到的部分留在外存，就可以让程序开始执行。

在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外省调入内存，然后继续执行程序。

如果内存空间不够，由操作系统负责将内存中暂时用不到的信息放出到外存。

虚拟内存的最大容量是由计算机的地址结构(Cpu寻址范围)确定的。

虚拟内存的实际容量 = min(内存和外存容量之和，Cpu寻址范围)

多次性:无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存。

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

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